单链表结构

链表是通过一组任意的存储单元来存储线性表中的数据元素。

那么怎样表示出数据元素之间的线性关系?

为建立起数据元素之间的线性关系,对每个数据元素 ai,除了存放数据元素自身的数据信息 ai 之外,还需要存放其后继 ai+1 所在的存储单元的地址,这两部分信息组成一个「结点」。

结点的图形表示
单链表结构

存放数据元素信息的域称为数据域,存放其后继数据元素地址的域称为指针域。

因此,n 个数据元素的线性表通过每个结点的指针域形成了一个「链」,称为链表。由于每个结点中只有一个指向后继的指针,所以称其为单链表。

链表是有一个个结点构成的,代码实现如下:

typedef int DataType;

class Item {
  public:
    DataType data;
    Item *next;
    Item() {	// 构造函数
      next = NULL;
    }
}

class Link {
  public:
    Item *head;   // 链表头指针

    Link() {     // 构造函数
      head = NULL;  
    }

    ~Link() {    // 析构函数
      DeleteAll();
    }

    void Initiate();  // 初始化

    void DeleteAll(); // 删除所有结点

    void HeadCreate(int n);   // 从头建链表

    void TailCreate(int n);   // 从尾建链表

    void HeadCreateWithHead(int n); // 建立带表头的链表(从头)

    void TailCreateWithHead(int n); // 建立带表头的链表(从尾)

    int Length();   // 求链表的长度

    Item *Locatex(DataType x);   // 查找值为x的数据元素

    Item *Locatei(int i); // 查找第i个元素

    DataType Get(int i);  // 取第i个元素值

    bool Insert(DataType x, int i);  // 在链表第i个结点之前插入x

    bool Deleted(int i);    // 删除表中第i个结点

    void Print();   // 打印链表
}

线性表(a1,a2,a3,a4,a5,a6,a7,a8)对应的链式存储结构示意图
单链表

用户头像
登录后发表评论