扫码获取更多资源

线性表顺序存储结构的特点是逻辑关系上相邻的两个数据元素在 物理位置上也相邻，因此可以随机存取表中任一元素。 然而，从另一个方面来看，这个特点 也铸成了这种存储结构的弱点：在作插入或删除操作时，需要移动大量的数据元素，操作不 便，特别是当元素信息量较多时，时间开销相当大。本节将讨论线性表的另一种表示方法, 即链式存储结构，由于它不要求逻辑上相邻的数据元素在物理位置上也相邻，因此它可以克 服顺序存储结构的不足，但同时也失去了顺序表可以随机存取的优点。

●单链表的定义

用一组任意的存储单元存放线性表的数据元素，且元素的逻辑次序和物理次序不一定 相同。为了能够正确表示数据元素之间的逻辑关系，在存储元素值的同时，还必须存储指示 其后继的地址信息，称为指针(Pointer)或链(Link)，这两部分组成一个结点(Node)表示线 性表中的一个数据元素。 通过每个结点的指针将线性表中的数据元素按照其逻辑顺序链接 在一起的存储方式称为线性表的链式存储结构，采用这种存储结构的线性表称为链表 (Linked List) o每个结点只有一个指针域的链表称为单链表(Single Linked List) o

单链表的结点结构

单链表的结点结构如图2-4所示。其中，data为数据域，存放数据元素的值；next为指 针域，存放后继元素的地址。 例如，线性表(5,8,9,21,4,19,15,17)的线性链式存储结构如图2-5所示。整个链表的 存取必须从头指针Head开始进行，头指针指示单链表中第一个结点的存储地址。因为最 后一个数据元素没有后继，所以其结点指针域中的指针为空(NULL),通常称为“空指针”。

单链表的逻辑状态表示

由于在使用单链表时，常常只注重结点之间的逻辑顺序，而不关心每个结点在存储器中 的实际物理位置，因此可以把单链表画成用箭头相连接的结点序列，结点之间的箭头表示指 针域中的指针。如图2-5所示的线性链表就可以画成如图2-6所示的形式， 其中：Head是 头指针，指示链表中第一个结点的存储位置；空指针用“ A ”表示。

单链表的头结点和头指针

从图2-6所示的单链表可以看到，除了第一个结点外，其他每个结点的存储地址都存放 在其前驱的指针域中，而第一个结点则由头指针指示。这个特例需要在单链表实现时做特 殊处理，这必然增加了程序的复杂性和出现bug(计算机系统或者程序中存在的任何一种破 坏正常运转能力的问题或者缺陷)的概率。因此,通常的做法是在单链表第一个结点之前附 设一个同结构的结点，称为头结点(Head Node)0头结点的数据域可以不存储任何信息，也 可以存储如线性表的长度等附加信息；头结点的指针域存储指向单链表第一个结点的存储 地址，如图2-7(a)所示。 当头结点的指针域为“空”时，单链表为空链表，如图2-7(b)所示。

单链表的类型定义

在这里丄inkList和LNode *是不同名字的同一个指针类型(命名的不同是为了概念 上更明确)。 LinkList类型的指针变量L表示它是单链表的头指针,LNode •类型的指针 变量表示它是指向某一结点的指针。

线性表的删除操作是使长度为n的线性表（a】日2 ,a3,a—i斗，ai+1• ,an）变成长度 为n— 1的线性表（a】形挪3,…,a—】,ai+1• ,an）,数据元素a—i和ai+1之间的逻辑关系发 生了变化。

单链表的主要特点

在单链表中，结点之间的逻辑关系由结点中的指针指示， 逻辑上相邻的两个结点其存储 的物理位置不要求相邻，因此这种存储结构不是顺序结构。

联系我们：