链表是通过一组任意的存储单元来存储线性表中的数据元素。
那么怎样表示出数据元素之间的线性关系?
为建立起数据元素之间的线性关系,对每个数据元素 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)对应的链式存储结构示意图