线性表的链式存储结构

2.3　线性表的链式存储结构

链式存储是最常用的动态存储方式。为了克服顺序表的缺点,可以采用链式存储方式来存储线性表。通常将链式方式存储的线性表称为线性链表。

2.3.1　单链表

在顺序表中,用一组地址连续的存储单元依次存放线性表的结点,因此线性表的逻辑顺序和物理顺序是一致的,而链表则不同。链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。链表由一系列结点（链表中每一个元素称为结点）组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。线性链表正是通过每过结点的指针域将线性表的n个结点按其逻辑顺序链接在一起的。由于此链表中的每一个结点只有一个next指针域,所以将这种链表称为单链表。如图2－5所示。

图2－5　单链表的结点结构

由于单链表中每个结点的存储地址是存放在其前驱结点的指针域中的,而第一个结点无前驱,因而应设一个头指针head指向第一个结点。同时,由于表中最后一个结点没有直接后继,则指定线性表中最后一个结点的指针域为“空”（NULL）。这样,对于整个链表的存取必须从头指针开始。

通常,将链表画成用箭头相连接的结点序列,结点之间的箭头表示指针字段的值。使用这种方式描述链表是因为,在使用链表时人们只关心结点之间的逻辑顺序,而结点的实际存储地址是无关紧要的,如图2－6所示。

图2－6　单向链表

单向链表的画法如图2－6所示,其中,图2－6（a）所示的是4个结点的线性表（a,b,c,d）,图2－6（b）所示的是空表。图2－6中的变量head称为表头结点,用于存放链表的第一个结点地址（对于空表,其值为“NULL”）。对于链表的存储,必须从头指针开始,顺着指针链依次进行。由于最后一个结点没有后继,所以最后一个结点指针字段的值为“NULL”,在图中用“∧”表示空指针。

为了操作的统一、方便,可以在单链表的第一个结点之前附设一个头结点,头结点的数据域可以存储一些关于线性表长度等的附加信息,也可以不存储任何信息。头结点的数据信息没有任何规定,而头结点的指针域则存储第一个结点的地址。此时,头指针就不再指向链表中的第一个结点,而是指向头结点。如果线性表为空,则头结点的指针域为“NULL”。如图2－7所示。

图2－7　带头结点的单链表

单链表的存储结构描述如下。

head是单链表的头指针,它指向头结点,若head－＞next＝＝NULL,则表示单链表为空表,其长度为0；如不带头结点,则head＝＝NULL,表示单链表为空表。

2.3.2　单链表上的基本运算

1.初始化单链表

初始化单链表的算法如下。

2.建立单链表

假设线性表中的结点数据类型为字符型,那么,可以逐个输入字符,并以“＃”作为输入结束标志符,动态地建立单链表。常见链表建立的方法有如下两种。

1）尾插法建立单链表

【算法思想】　从一个空表开始,每次读入一个输入,生成新的结点,将读入的数据放入新结点的数据域中,然后将新结点插入到当前单链表的表尾上,直到读入结束标志为止。为此,需要增加一个尾指针r,使之指向单链表的表尾。用尾插法建立的单链表的逻辑顺序与输入元素顺序相同。用尾插法建立单链表的流程如图2－8所示。

图2－8　尾插法建立单链表

具体算法如下。

2）头插法建立单链表

【算法思想】　头插法建立单链表的方法是将新结点插入到当前链表的表头结点之后。用头插法建立的单链表的逻辑顺序与输入元素的顺序相反,如图2－9所示。

图2－9　头插法建立单链表

具体算法如下。

3.查找

1）按序号查找

在单链表中,由于每个结点的存储地址都存放在其前一结点的指针域next域中,因而即使知道被访问结点的序号i,也不能像顺序表那样直接按序号i访问一维数组中的相应元素,实现随机存取；而只能从链表的头指针出发,顺着指针域next逐个结点进行搜索,直至搜索到第i个结点为止。

【算法思想】　设带头结点的单链表的长度为n,要查找表中的第i个结点,则需要从单链表的头指针head出发,从头结点（head－＞next）开始顺着链域扫描。用指针p指向当前扫描到的结点,初值指向头结点,用j做计数器,累计当前扫描过的结点数（初值为0）,当j＝i时,指针p所指的结点就是要找的第i个结点。

具体算法如下。

2）按值查找

【算法思想】　按值查找是指在单链表中查找是否有结点值等于x的结点,如果有则返回首次找到的值为x的结点的存储地址,否则返回NULL。查找过程从单链表的头指针指向的头结点开始,顺着链表逐个将结点的值与给定值x作比较。

4.插入

在单链表中插入是指在第i个结点的后面插入一个数值为x的新结点,用i＝0表示将新结点插入到表头结点之后,成为线性表的第一个结点。

【算法思想】　首先,判断i是否正确,若i＜0或i＞head－＞n,则说明参数i不正确,不能进行插入操作；然后,在单链表中找到第i个结点,或者调用定位函数getdatai（head,i）,确定第i个结点的地址p,在p结点的后面插入一个新结点,具体步骤如下。

（1）为新结点分配存储单元。

（2）将x存入新结点的数据域中。

（3）让新结点指向p所指向结点的后续结点（即第i＋1个结点）。

（4）让p所指结点指向新结点。

（5）线性表长度加1。

详细流程如图2－10所示。

图2－10　插入新结点

具体算法如下。

5.删除

单链表中的删除操作用于删除线性表中的第i个结点。

【算法思想】　首先判断参数i是否正确,若i＜1或i＞head－＞n,则说明参数不正确；然后,在单链表中找到第i－1个结点,或者调用定位函数getdatai（head,i－1）来确定第i－1个结点的地址p,删除p结点的下一个结点（第i个结点）,具体步骤如下。

（1）让q指针指向第i个结点（q＝p－＞next）。

（2）让p指针所指结点指向q指针所指结点的下一结点（p－＞next＝q－＞next）。

（3）释放q结点所占用的存储空间。

（4）线性表长度减1。

详细流程如图2－11所示。

图2－11　删除结点

具体算法如下。

链表的一个重要特点是插入、删除操作灵活方便,不需移动结点,只需改变结点中指针域的值即可。而数组由于使用存储单元的邻接性体现数组中元素的逻辑顺序关系,因此,对数组进行插入和删除运算时,可能需要移动大量的元素,以保持这种物理和逻辑的一致性。例如,数组中有m个元素,往第i（i＜m）个元素后面插入一个新元素,需要将第i＋1个元素至第m个元素共m－i个元素向后移动。