线性表的链式存储

第3章线性表的链式存储主要知识点：●线性表的链式存储结构。●链表中有关概念的含义，如头结点、头指针，首元结点、尾元结点的区别，以及循环链表、双向链表的区别等。●各种链表上实现线性表各种操作的方法即有关算法的设计。●建立利用数据结构知识进行程序设计的思考方式。教学重点与难点重点：单链表结构的各种基本算法，以及相关的时间性能分析。难点：设计链表结构算法解决线性表相关实际问题。

思考问题：1、线性表链式结构特点2、如何利用线性表链式结构的知识解决实际问题，确定线性表链式结构的应用题目。课程任务：线性表链式结构案例理解，完成课程任务设计。1、考核方式：课程报告和程序设计2、作业题目：依据选定的线性表结构实用案例题目，设计完成课程任务。例如：课程任务实例“饮食中心订餐管理系统”。3、作业要求：分析案例实现方法，结合案例设计自己的作业任务。3.1线性表的链式存储结构3.1.1为什么要使用链式存储结构【案例】：物流配送货单管理。

图3.1物流配送信息20087711刘佳佳哈尔滨20087707邓玉莹齐齐哈尔20087714魏秀婷牡丹江需求分析：1、不需要事先准备一张足够大的纸；2、每张小纸条写完以后，把这张纸条排列到正确位置时，不会影响到其他的纸条；3、配送顾客完成后，把记录该顾客信息的纸条抽出来销毁（或存档）。4、数据元素之间的逻辑关系为线性关系。3.1线性表的链式存储结构问题思考：1、采用顺序表存储结构存在的问题。

2、考虑采用链式存储结构的解决。3.1.2单链表的数据定义链表的存储特点：

1、用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的），例如三个配送顾客的配送数据信息的存储空间是可以定义在任意的存储区域。

2、链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，三个配送顾客的配送数据的逻辑次序与物理存储次序不相同。200030001000刘佳佳配送信息3000邓玉莹配送信息1000魏秀婷配送信息0000Head(a)刘佳佳配送信息邓玉莹配送信息魏秀婷配送信息^Head2000(b)问题思考：总结链式存储结构的特点数据域指针域结点结构:数据域：存放结点数据信息值，例如配送顾客数据信息。

指针域：存放结点的直接后继的地址（位置）。

注意：

（1）、链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。

（2）、每个结点只有一个链域的链表称为单链表（SingleLinkedList）。

单链表定义的一般形式：由分别表示a1,a2,…,an,的n个结点依次相链构成的链表，称为线性表的链式存储表示，由于此类链表的每个结点中只包含一个指针域，故称为单链表或线性链表。3.1.2单链表的数据定义任务1：举例说明为什么要使用链式存储结构。3.1.3静态链的实现

静态链表特点：

●用数组来存储元素的值和地址。●程序运算过程中，数组元素的个数固定不变。例3-1：物流配送货单管理静态链表存储结构设计（1）存储结构分析序号数据域指针域0邓玉莹配送信息11魏秀婷配送信息-12刘佳佳配送信息0………Head

2（2）存储结构C语言定义如下：定义顾客信息数据类型:typedefstruct{chardelivery_number[10];charname[10]; /*姓名*/charadress[20];/*地址*/}ElemType;

定义结点类型:typedefstructnode{ElemTypedata;/*数据域*/intnext;/*指针域*/}SLNode;

定义静态单链表：SLNodeletter[100]；任务2：静态链表存储结构举例并采用C语言定义序号数据域指针域0邓玉莹配送信息11魏秀婷配送信息-12刘佳佳配送信息0………Head

2

使用链表的原因：第一，如果系统不能提供足够大的地址连续的内存空间时，可以考虑使用链表；第二，需要对线性表频繁地进行插入和删除操作时，也考虑使用链表。3.1.4动态链表的实现动态链表结点定义一般形式：typedefstructnode{ElemTypedata;/*数据域*/structnode*next;/*指针域*/}LNode，*LinkList;刘佳佳配送信息邓玉莹配送信息魏秀婷配送信息^Head刘佳佳配送信息邓玉莹配送信息^Head刘佳佳配送信息^Headtypedefstructnode{ElemTypedata;/*数据域*/structnode*next;/*指针域*/}LNode，*LinkList;（1）.定义元素数据类型typedefstruct{charnumber[7];/*序号*/chardelivery_number[10];/*配送编号*/charname[10];/*姓名*/charaddress[20];/*地址*/}ElemType;3.1.4动态链表的实现例3-2：物流配送货单管理动态链表存储结构设计1．存储结构分析：在C语言程序设计中，可以用malloc函数申请动态变量（存储空间），用free释放变量（存储空间）。动态链表中的结点是以变量形式申请或者释放的。2.顾客信息的动态链类型：typedefstructnode{ElemTypedata;/*数据域*/structnode*next;/*指针域*/}LNode，*LinkList;3.1.4动态链表的实现C语言知识回顾：typedefstructnodeLNode;typedefstructnode*LinkList;等价于Structnode{ElemTypedata;/*数据域*/structnode*next;/*指针域*/};定义变量：Structnodex,*Head;/*结点变量x，结点指针变量Head

*/或LNodex,*Head;/*结点变量x，结点指针变量Head

*/或LinkListHead;/*结点指针变量Head

*/（1）.定义元素数据类型typedefstruct{charnumber[7];/*序号*/chardelivery_number[10];/*配送编号*/charname[10];/*姓名*/charaddress[10];/*地址*/}ElemType;刘佳佳配送信息邓玉莹配送信息魏秀婷配送信息^Headtypedefstructnode

{ElemTypedata;/*数据域*/

structnode*next;/*指针域*/

}LNode,*LinkList;3.C语言描述说明

（1）LinkList和LNode*是不同名字的同一个指针类型（命名的不同是为了概念上更明确）。

（2）LinkList类型的指针变量head表示它是单链表的头指针。

（3）LNode*类型的指针变量p表示它是指向某一结点的指针。

为了便于描述，下面给出有关链表的术语。在一个链表中称表头结点指针为头指针。由于从头指针出发可以搜索到链表中各结点，因而常用头指针作为链表的名称。4.定义链表变量两种定义形式：（1）LinkListHead；（2）LNode*Head；（2）.定义链表及结点类型【知识拓展】：指针变量和结点变量的关系（1）生成结点变量的标准函数

p=(LNode*)malloc(sizeof(LNode))；

//函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中。

（2）释放结点变量空间的标准函数

free(p)；//释放p所指的结点变量空间。

（3）结点分量的访问

利用结点变量的名字*p访问结点分量

方法一：(*p).data和(*p).next

方法二：p-﹥data和p-﹥next

（4）指针变量p和结点变量*p的关系

指针变量p的值——结点地址

结点变量*p的值——结点内容

(*p).data的值——p指针所指结点的data域的值

(*p).next的值——*p后继结点的地址

*((*p).next)——*p后继结点头结点及作用：头结点是在链表的开始结点之前附加一个结点。它具有两个优点:

（1）由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理;

（2）无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。注意：

头结点数据域的阴影表示该部分不存储信息。在有的应用中可用于存放表长等附加信息。3.2基于单链表的算法实现【例3-3】：以“物流配送货单管理”任务为例，采用带头结点的动态链表设计数据结构。单链表类型定义：（1）定义元素数据类型typedefstruct{charnumber[7];/*序号*/chardelivery_number[10];/*配送编号*/charname[10];/*姓名*/charaddress[20];/*地址*/}ElemType;（2）定义链表及结点类型typedefstructnode{ElemTypedata;/*数据域*/structnode*next;/*指针域*/}LNode,*LinkList;3.2基于单链表的算法实现3.2.1单链表的基本算法实现1．构造一个空表

intInit_LinkList(LinkListHead)/*构造一个空表*/{LinkListp;p=(LinkList)malloc(sizeof(LNode));/*分配一个结点*/if(p==NULL)returnOverFlow;/*分配失败*/Head=p;/*头指针指向新结点*/returnOK;/*构造成功，返回*/}子函数参数说明：typedefstructnode{ElemTypedata;/*数据域*/structnode*next;/*指针域*/}LNode，*LinkList

intInsertL_i(LinkListHead,ElemTypex,inti)/*在第i个结点后面插入*/{LNode*p,*q;intk=0;p=(LinkList)malloc(sizeof(Node));/*分配一个结点*/

if(p==NULL)returnOverFlow;/*分配失败*//*数据域赋值*/strcpy(p->data.number,x.number);/*输入序号*/strcpy(p->data.number,x.deliery_number);/*输入配送编号*/strcpy(p->,);/*输入姓名*/ strcpy(p->data.time,x.address);/*输入地址*/ q=Head;while(q!=NULL&&k!=i-1)/*q指向第一个元素*/{q=q->next;k++;/*q取后继元素的指针*/}if(q==NULL)printf(“序号错/n”);else{p->next=q->next;/*设置新结点的指针指向第i个结点的后继结点*/q->next=p;/*设置第i个结点的指针域指向新结点*/returnOK;/*插入成功，返回*/}returnError;/*插入未成功*/}【算法3.3】查找指定元素x（查找姓名字段，类型为字符数组）。

LNode*Location_LLinkList(LinkListHead,char*name)/*查找指定关键字信息*/{Node*p;p=Head->next;while(p!=NULL)/*未到链尾*/{/*关键字姓名相等*/if(strcmp(p->,name)==0)returnp;/*找到返回指针*/elsep=p->next;/*p取后继结点的地址*/}returnNULL;/*未找到，返回空指针*/}【问题思考】（1）查找指定位置的元素如何设计。（2）结合实际应用设计关键字字段。4.删除指定元素删除运算是将表值为x的元素结点删去。具体步骤是，找到ai-1的存储位置q（因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中）,令p-＞next指向ai的直接后继结点（即把ai从链上摘下）,释放结点ai的空间，将其归还给"存储池"。【算法3.4】删除线性表中值为x的元素（删除姓名字段，类型为字符数组）。

intDelete_LLinkList(LinkListHead,char*name){Node*p,*q;q=Head;/*q指向头结点*/p=q->next;/*p取其后继结点的地址*/while(p!=NULL)/*p不为空*/{if(strcmp(p->,name)==0)/*找到被删除元素*/{q->next=p->next;/*q所指结点的指针设置为p所指结点的指针*/free(p);/*释放p所指结点*/returnOK;/*删除成功*/}q=p;p=p->next;/*q取p的值，p取其后继结点的地址*/}returnError;/*删除失败*/}【问题思考】（1）删除结点的关键字设计。（2）删除指定位置的元素如何设计。5.遍历带表头结点的单循环链表【算法3.5】遍历带表头结点的单循环链表

voidShow_LLinkList(LinkListHead)/*遍历线性表*/{LNode*p;printf("\n");p=Head->next;/*p指向第一个结点（非头结点）*/if(p==NULL)printf("\n空表！NULL");while(p!=NULL)/*未结束遍历*/{printf("%s%s%s%s\n",p->data.number,p->data.deliery_number,p->,p->address);/*输出数据*/p=p->next;/*p取后继结点的地址*/}}

说明：显示结点数据为分别输出数据域各个成员项的值。6.清空带表头结点的单循环链表【算法3.6】清空带表头结点的单循环链表。

voidSetNull_LLinkList(LinkListHead)/*清空线性表*/{LNode*p,*q;q=Head;p=q->next;/*p取头指针*/while(p!=NULL){q=p;/*q指向p的前驱结点*/p=p->next;/*p指向其后继结点*/free(q);}Head->next=NULL;/*设置头结点/*/}

7.计算带表头结点的单循环链表的长度【算法3.7】计算带表头结点的单循环链表的长度。

intLength_LLinkList(LinkListHead)/*计算线性表的长度*/{LNode*p;intsum=0;p=Head->next;/*p取头指针的后继*/while(p!=NULL)/*p与Head不相等*/{sum++;/*累加器加1*/p=p->next;/*p指向其后继结点*/}returnsum;}3.2.2单链表中插入运算的进一步讨论1.尾插【算法3.8】插入一个元素（在最后一个结点之后插入，带表头结点的单链表）

intInsertL_Last(LinkListHead,ElemTypex)/*在最后一个结点后面插入*/{LNode*p,*q;intk=0;p=(LinkList)malloc(sizeof(Node));/*分配一个结点*/if(p==NULL)returnOverFlow;/*分配失败*//*数据域赋值*/strcpy(p->data.number,x.number);/*输入序号*/strcpy(p->data.number,x.deliery_number);/*输入配送编号*/strcpy(p->,);/*输入姓名*/ strcpy(p->data.time,x.address);/*输入地址*/p->next=NULL；

q=Head;while(q!=NULL)/*q指向最后一个元素*/q=q->next;/*q取后继元素的指针*/q->next=p;/*设置第i个结点的指针域指向新结点*/returnOK;}2.头插【算法3.9】插入一个元素（在头结点之后插入，带表头结点的单链表）

intInsertL_First(LinkListHead,ElemTypex)/*在头结点后面插入*/{LNode*p;p=(LinkList)malloc(sizeof(Node));/*分配一个结点*/if(p==NULL)returnOverFlow;/*分配失败*//*数据域赋值*/strcpy(p->data.number,x.number);/*输入序号*/strcpy(p->data.number,x.deliery_number);/*输入配送编号*/strcpy(p->,);/*输入姓名*/ strcpy(p->data.time,x.address);/*输入地址*/p->next=Head->next;Head->next=p;returnOK;}【例3-3】“物流货单配送管理”的实现问题描述物流公司根据配货单配送给顾客。功能主要包括插入配货信息、退订某人货单、浏览全部货单、统计全部货单数量等功能。3.2.3带表头结点的单链表应用举例基本要求由于每天配送顾客数量不确定，并且随时都有退单的可能性，存在频繁的插入与删除操作。因此采用带有头结点的单链表数据结构。模块划分①建立带头结点的单链表Init_LLinkList，该模块完成初始化功能。②插入货单配送信息服务InsertL_Last,该模块将新的配送信息插入到单链表的尾部。③退订货单服务Delete_LLinkList,该模块根据输入配送顾客的姓名，首先在链表中进行查找，若找到相应结点，则将其从物流配货单链表中摘下。若没有找到相应结点，则给出不存在该顾客配送信息。④查找某人的货单信息Location_LinkList，找出指定姓名的顾客配送信息。⑤显示物流货单配送信息服务Show_LinkList，该模块将单链表中所有的结点元素数据信息显示出来。⑥统计配送顾客数量Length_LinkList，该模块计算单链表结点数量。⑦清除单链表模块SetNull_LinkList，将所使用的单链表归还系统。⑧主函数main，构造仅有头结点的物流配送货单单链表，调用Init_LLinkList建立货单配送信息，显示货单顾客配送信息、退订货单配送、统计全部预定数量、退出菜单等功能。据（对菜单的）相应选择调用模块或终止程序运行。程序设计#include"stdio.h“#defineMaxSize20#defineOverFlow-1#defineOK1#defineError-1typedefstruct/*定义元素数据类型*/{charnumber[7];/*序号*/chardeliery_number;/*配送编号*/charname[10]; /*姓名*/charaddress[20];/*时间*/}ElemType;typedefstructnode/*定义链表及结点类型*/{ElemTypedata;/*数据域*/structnode*next;/*指针域*/}LNode,*LinkList;voidmain(){LinkListHead;inti; LNode*loca;ElemTypex;charname_x[10];Init_LinkList(Head);do{printf("\n");printf(“1---登记一个配送数据(Insert)\n");printf(“2---查询指定配送数据(Locate)\n");printf(“3---删除一个配送数据(Delete\n");printf(“4---显示所有配送数据(Show)\n");printf(“5---统计配送数量(Length)\n");printf("6---退出\n");scanf("%d",&i);switch(i){case1:printf("Pleaseenternumber:");/*输入序号*/scanf("%s",x.number);printf(“Pleaseenterdeliery_number:”);/*输入配送编号*/scanf("%s",x.deliery_number);printf("Pleaseentername:");/*输入姓名*/scanf("%s",);printf(“Pleaseenteraddress:”);/*输入地址*/scanf("%s",x.time);if(Insert_Last(Head,x)!=OK)printf("插入失败\n");break;case2:printf(“请输入要查询的配送顾客姓名research：\n");printf("Pleaseentername:");/*输入姓名*/scanf("%s",name_x);loca=Location_LinkList(Head,name_x);if(loca!=NULL)printf(“查找成功(Found)!");elseprintf(“查找失败!Fault，该顾客不存在！");break;case3:printf(“请输入要退单的信息delete\n");printf("Pleaseentername:");/*输入姓名*/scanf("%s",name_x);if(Delete_LinkList(Head,name_x)==OK)printf(“撤销配送\n");elseprintf(“没有找到制定顾客配送信息Fault\n");break;case4:Show_LinkList(Head);break;case5:printf(“货单数量是amount%d!\n",Length_LinkList(Head));break;case6:break;default:printf("错误选择！Error请重选");break;}}while(i!=6);SetNull_LinkList(Head);/*清空线性表*/}3.3链式存储的其它方法

3.3.1链式存储结构循环链表特点:是表中最后一个结点的指针不再是空，而是指向头结点（带头结点的单链表）或第一个结点（不带头结点的单链表），整个链表形成一个环，这样从表中任一结点出发都可找到其它的结点。注意：判断空链表的条件是head==head->next;a1a2…an带头结点的循环单链表(a)空循环链表(b)非空循环链表headhead【例3-4】在链表上实现将两个线性表（a1，a2，…，an）和（b1，b2，…，bm）连接成一个线性表（a1，…，an，b1，…bm）的运算。

分析：若在单链表或头指针表示的单循环表上做这种链接操作，都需要遍历第一个链表，找到结点an，然后将结点b1链到an的后面，其执行时间是O(n)。若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O(1)。算法设计：

LinkListConnect(LinkListA,LinkListB)

{//假设A，B为非空循环链表的尾指针

LinkListp=A->next;//①保存A表的头结点位置

A->next=B->next->next;//②B表的开始结点链接到A表尾

free(B->next);//③释放B表的头结点

B->next=p;//④

returnB;//返回新循环链表的尾指针

}

1、双向链表（DoubleLinkedList）双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。

注意：

①双链表由头指针head惟一确定的。

②带头结点的双链表的某些运算变得方便。

③将头结点和尾结点链接起来，为双（向）循环链表。3.3.2链式存储结构双链表2、双向链表的结点结构和C语言形式描述

①结点结构②形式描述

typedefstructdlistnode{

DataTypedata;

structdlistnode*prior,*next;

}DListNode;

typedefDListNode*DLinkList;

DLinkList