Tim的资源站

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

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

为建立起数据元素之间的线性关系，对每个数据元素 a_i，除了存放数据元素自身的数据信息 a_i 之外，还需要存放其后继 a_i+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();   // 打印链表
}

线性表（a₁，a₂，a₃，a₄，a₅，a₆，a₇，a₈）对应的链式存储结构示意图