线性表链式表示-C语言程序设计

1.单链表的定义和表示

和顺序表相比，链表存储结构在实现插入、删除的操作时，不需要移动大量数据元素，但不容易实现随机存取线性表的第i个数据元素的操作。所以，链表适用于经常需要进行插入和删除操作的线性表，如飞机航班的乘客表等。

用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。换句话说，指针为数据元素之间的逻辑关系的影像，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻。例如线性表（a1，a2，…，an），在链式存储结构中，数据元素ai的存储映射称为结点，它由数据域和指针域组成，数据域用来存放数据元素信息，指针域指向直接后继存储地址。在此链表结构中，每个结点只有一个指针域，所以称为线性链表或单链表。本节先讨论简单的单链表。

单链表的C语言描述如下：

/*单链表的存储结构*/

typedef struct LNode

｛

　Elem Type data；　　　　　　　//结点的数据域

　struct LNode*next；　//结点的指针域

｝LNode，*Link List；　　　　　//Link List为指向结构体LNode的指针类型

在顺序表中，逻辑上相邻的两个元素物理位置上也相邻，每个元素的存储位置都可从线性表的起始位置计算得到。而在单链表中，各个元素的存储位置是随意的，都包含在其直接前驱结点的指针域中。假设p是指向单链表中第i个数据元素（结点ai）的指针，则p－＞next是指向第i＋1个数据元素（结点ai＋1）的指针。因此单链表是非随机存取的存储结构，要取得第i个数据元素必须从头指针出发顺链进行寻找，称为顺序存取，基本操作的实现不同于顺序表。

2.单链表基本操作的实现

（1）初始化

初始化操作是构造一个空的单链表。

Status Init List（Link List&L）　//构造一个空的单链表L

｛

　L＝new LNode；　　　//生成新结点作为头结点，用头指针L指向头结点

　L－＞next＝NULL；　　//头结点的指针域置为空

　return OK；

｝

（2）取值

根据给定的结点位置序号i，获得结点数据域。与顺序表不同，不能随机访问，只能从链表的首元结点出发，顺着指针域所指向的结点向下访问。首元结点是指链表中存储第一个数据元素的结点a1。

Status GetElem（Link List L，int i，Elem Type&e）

｛

　p＝L－＞next；　　　　　　　　　　//初始化，p指向首元结点

　j＝1；　//计数器j初值赋1

　while（p&&j＜i）

　｛

p＝p－＞next；　//p指向下一个结点

＋＋j；　//计数器j加1

　｝

　if（！p||j＞i）return ERROR；　//i值不合法返回ERROR

　e＝p－＞data；　//将第i个结点的数据域赋给e

　return OK；

｝

（3）查找

查找操作从链表的首元结点出发，依次比较给定值和结点值，返回查找结果。

LNode*LocateElem（Link List L，Elem Type e）

｛

　p＝L－＞next；　　　　　　　　　　//初始化，p指向首元结点

　while（p&&p－＞data！＝e）　//直到p为空或p所指结点的数据域为e

p＝p－＞next；　//p指向下一个结点

　return p；　//查找成功返回e的结点地址p(www.xing528.com)

｝

（4）插入

假设要在单链表的两个数据元素a和b之间插入x，p为指向结点a的指针，s为指向结点x的指针，执行插入操作后a、b之间的逻辑关系发生变化。需要建立结点x，修改结点a的指针域使其指向x，结点x的指针域指向结点b。插入前后结点变化情况如图9.3所示。

Status ListInsert（Link List&L，int i，Elem Type e）

｛

　p＝L；

　j＝0；

　while（p&&（j＜i－1））

　｛

p＝p－＞next；　　　　　　　　　//查找第i－1个结点，p指向该结点

　＋＋j；

　｝

　if（！p||j＞i－1）return ERROR；

　s＝new LNode；　//生成新结点*s

　s－＞data＝e；　//将e赋给结点*s的数据域

　s－＞next＝p－＞next；　//让结点*s的指针域指向结点ai

　p－＞next＝s；　//将结点*p的指针域指向结点*s

　return OK；

｝

图9.3　单链表插入操作前后变化

（5）删除

要删除单链表中的b结点，首先应该找到该元素的前驱结点a，修改a的指针域使其指向结点c，如图9.4所示。

图9.4　删除操作前后结点变化

在删除结点b时，除了修改结点a的指针域外，还要释放结点b所占空间，所以在修改指针前，应引入另一指针q，临时保存结点b的地址以备释放。

Status List Delete（Link List&L，int i）

｛

　p＝L；

j＝0；

　while（（p－＞next）&&（j＜i－1））

｛

　p＝p－＞next；　　　　　　　　　//查找第i－1个结点，p指向该结点　

＋＋j；

　｝

　if（！（p－＞next）||（j＞i－1））return ERROR；

　q＝p－＞next；　//临时保存被删结点的地址

　p－＞next＝q－＞next；　//改变删除结点前驱结点的指针域

　delete q；　//释放删除结点的空间

　return OK；

｝