顺序表的存贮特点是利用物理上的相邻关系表达出逻辑上的前驱和后继关系它要求用连续的存储单元顺序存储线性表中各元素因此对顺序表进行插入和删除时需要通过移动数据元素来实现线性表的逻辑上的相邻关系从而影响其运行效率本节介绍线性表的另一种存储形式——链式存储结构它不需要用地址连续的存储单元来实现而是通过链建立起数据元素之间的次序关系因此它不要求逻辑上相邻的两个数据元素在物理结构上也相邻在插入和删除时无需移动元素从而提高其运行效率链式存储结构主要有单链表循环链表双向链表静态链表等几种形式
单链表
链表是通过一组任意的存储单元(可以连续也可不连续)来存储线性表中的数据元素根据线性表的逻辑定义单链表的存储单元不仅能够存储元素而且要求能表达元素与元素之间的线性关系对数据元素ei而言除存放数据元素自身的信息ei之外还需要存放后继元素ei+所在存贮单元的地址这两部分信息组成一个结点每个结点包括两个域数据域——存放数据元素本身的信息;指针域——存放其后继结点的地址结点的结构如图 所示因此n个元素的线性表通过每个结点的指针域构成了一个链条称之为链表因为每个结点中只有一个指向后继的指针所以称其为单链表为了访问单链表我们只要知道第一个结点地址就能访问第一个元素通过第一个元素的指针域得到第二个结点的地址……以此类推可以访问所有元素这样称第一个元素的地址为头指针
例如假设有线性表(ABCDEFGH)对应的链式存储结构如图所示头指针为H最后一个结点没有后继 其指针域必需置空(以NULL表示)表明此表到此结束这样就可以从第一个结点的地址开始顺籐摸瓜找到每个结点
[] [] [] []