线性表的链式表示和实现

1第2章线性表2.1线性表的逻辑结构2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4一元多项式的表示和相加22.3线性表的链式表示和实现2.3.1链表的表示2.3.2链表的实现2.3.3一个带头结点的单链表类型2.3.4其它形式的链表3链式存储结构特点：其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。如何实现？通过指针来实现！让每个存储结点都包含两部分：数据域和指针域指针数据指针数据指针或样式：数据域：存储元素数值数据指针域：存储直接后继或者直接前驱的存储位置设计思想：牺牲空间效率换取时间效率2.3.1链表的表示4链表存放示意图如下：

a1heada2/\an……讨论1：每个存储结点都包含两部分：数据域和讨论2：在单链表中，除了首元结点外，任一结点的存储位置由

指示。

其直接前驱结点的链域的值(2)与链式存储有关的术语：1）结点：数据元素的存储映像。由数据域和指针域两部分组成；2）链表：

n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。只包含一个指针域的称为单链表或线性链表指针域53）头指针、头结点和首元结点的区别头指针头结点首元结点a1heada2…infoan^首元结点是指链表中存储线性表第一个数据元素a1的结点。头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；示意图如下：6讨论2：在链表中设置头结点有什么好处？讨论1：

如何表示空表？因为任何结点都有前驱结点，而在做插入和删除操作时，都需修改其前驱结点的指针域，因此对首元结点可以统一处理。即简化插入和删除操作；表头指针是指向头结点的非空指针，因此空表和非空表的处理一样。无头结点时，当头指针的值为空时表示空表；^头指针无头结点^头指针头结点有头结点有头结点时，当头结点的指针域为空时表示空表。头结点不计入链表长度！7一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31称：头指针H的值是31（3）举例例1：8

现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下图所示。其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？116NULL(0)100108112答：X=

Y=

Z=

,

首址=

末址=

。例2：Z47Y31V23X17U051001191041081161129讨论:

链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。答：设每个结点用变量node表示，其指针用p表示，两个分量分别用data和*next表示，这两个分量如何赋值？p*nextdatanode方式1：直接表示为

node.data＝'a'；node.next=q;方式2：p指向结点首地址p->data='a';p->next=q;方式3：p指向结点首地址(*p).data='a'；(*p).next＝q;10单链表的抽象数据类型描述如下（参见教材P28）：typedefstructLNode

{ElemTypedata;//数据域

structLNode*next;//指针域}LNode,*LinkList;

//*LinkList为Lnode类型的指针Q1：第一行的LNode

与最后一行的LNode是不是一回事？A1：不是。前者LNode是结构名，后者LNode是对整个struct类型的一种“缩写”，是一种“新定义名”，它只是对现有类型名的补充，而不是取代。这就是我们在复习c语言时讲的自引用结构11Q2：那为何两处要同名(LNode和LNode）？太不严谨了吧？A2：同名是为了表述起来方便。因为描述的对象相同，方便阅读和理解。Q3：结构体中间的那个struct

LNode是何意？A3：在“缩写”

LNode还没出现之前，只能用原始的structLNode来进行变量说明。此处说明了指针分量的数据类型是structLNode。返回122.3.2链表的实现（1）单链表的存取（2）单链表的插入（3）单链表的删除（4）单链表的建立13（1）单链表的存取思路：要存取第i个数据元素，必须从头指针起一直找到该结点的指针p，然后才能执行p->data=new_value。访问第i个数据元素的操作函数可写为：Status

GetElem_L(LinkListL,inti,ElemTypee){p=L->next;j=1;//带头结点的链表while(p&&j<i){p=p->next;++j;}if(!p||j>i)returnERROR;//i不合法

p->data=e;//若是读取则为：e=p->data;

returnOK;}//

GetElem_L缺点：想寻找单链表中第i个元素，只能从头指针开始逐一查询（顺藤摸瓜），无法随机存取。14在链表中第i个位置前插入一个元素x的示意图如下：Xsai-1aip链表插入的核心语句：Step1：s->next=p->next;p->nexts->next思考：Step1和2能互换么？X结点的生成方式：s=(Lnode*)malloc(m);s->data=x;s->next=?aiai-1p插入X（2）单链表的插入（重点）Step2:p->next=s;15StatusListInsert_L(LinkListL,inti,ElemTypee){

}//LinstInsert_L算法的时间复杂度为:O(ListLength(L))p=L;j=0;while(p&&

j<i-1)

{p=p->next;++j;}

//寻找第i-1

个结点if(!p||j>i-1)returnERROR;//i不合法

s=(LinkList)malloc(sizeof(LNode))s->data=e;s->next=p->next;p->next=s;//插入returnOK;16在链表中删除某元素ai的示意图如下：ai+1ai-1aip删除动作的核心语句（要借助辅助指针变量q）：q=p->next;//首先保存ai的指针，靠它才能找到ai+1

p->next(p->next)->next×q（3）单链表的删除（重点）p->next=q->next；//将ai-1与ai+1两结点相连,淘汰ai结点×free(q);

17StatusListDelete_L(LinkListL,inti,ElemType&e){

//删除以L为头指针(带头结点)的单链表中第i个结点

}//ListDelete_L算法的时间复杂度为:O(ListLength(L))p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}

//寻找第i个结点，并令p指向其前趋if(!(p->next)||j>i-1)

returnERROR;//删除位置不合理q=p->next;p->next=q->next;//删除并释放结点

e=q->data;free(q);returnOK;18空间效率分析链表中每个结点都要增加一个指针空间，相当于总共增加了n个整型变量，空间复杂度为O(n)。在n个结点的单链表中要删除已知结点*P，需找到它的，其时间复杂度。

前驱结点的地址/指针O(n)练习：19操作步骤：一、建立一个“空表”；二、输入数据元素an，建立结点并插入；三、输入数据元素an-1，建立结点并插入表头；ananan-1四、依次类推，直至输入a1为止。（4）单链表的建立例如：头插法输入n个数据元素的值，建立带头结点的单链表。链表是一个动态的结构，它不需要预先分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。–头插法建表该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。。21voidCreateList_L(LinkList&L,intn){

//头插法建立带头结点的单链表}//CreateList_L算法的时间复杂度为:O(Listlength(L))L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一个带头结点的单链表for(i=n;i>0;--i){

s=(LinkList)malloc(sizeof(LNode));

scanf(&s->data);//输入元素值

s->next=L->next;①

L->next=s;

②

//插入}–尾插法建表该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点尾插法建表voidCreateList_L(LinkList&L,intn){

tail=L=(LinkList)malloc(sizeof(LNode));//尾指针初始化为表头指针L->next=NULL;for(i=n;i>0;--i){s=(LinkList)malloc(sizeof(LNode));scanf(&s->data);s->next=NULL;

tail->next=s;①

tail=s;②}}24算法要求：已知：线性表A和B，分别由单链表La和Lb存储，其中数据元素按值非递减有序排列（即已经有序）；要求：将A和B归并为一个新的线性表C,C的数据元素仍按值非递减排列。设线性表C由单链表Lc存储。假设：A=（3，5，8，11），B=（2，6，8，9，11）预测：合并后的C=（2,3,5,6,8,8,9,11，11）例1：两个链表的归并（教材P31例）算法设计：算法主要包括搜索、比较、插入三个操作：搜索：需要设立三个指针来指向La、Lb和Lc链表；请将该例子和ch2-1的ppt的第18页进行比较！25La3

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，Pc指向新链表当前结点。归并过程示意如下：Lc=LaPbPaPaPb比较：比较La和Lb表中结点数据的大小；插入：将La和Lb表中数据较小的结点插入新链表Lc。请注意链表的特点，仅改变指针便可实现数据的移动,即“数据不动，指针动”26

voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//已知单链线性表La和Lb的元素按值非递减排列。归并为Lc后也按值非递减排列。

free(Lb);

//释放Lb的头结点}//MergeList_L

pc->next=pa

?pa:pb;

//插入非空表的剩余段

while(pa&&pb)

//将pa、pb结点按大小依次插入Lc中

{if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}

else{pc->next=pb;pc=pb;pb=pb->next}}

pa=La->next;pb=Lb->next;Lc=pc=La；

//有头结点注：Lc用的是La的头指针思考：重复的数据元素不需要插入，怎么修改？练习：已知L是带头结点的非空单链表，指针p所指的结点既不是第一个结点，也不是最后一个结点删除*p结点的直接后继结点的语句序列

q=p->next;p->next=q->next;

free(q);删除*p结点的直接前驱结点的语句序列

q=L;while(q->next->next!=p)q=q->next;s=q->next;//s即所要找到的p的前驱q->next=p;//链接

free(s);删除*p结点的语句序列

q=L;while(q->next!=p)q=q->next;q->next=p->next;

free(p);删除首元结点的语句序列

q=L->next;L->next=q->next;

free(q);删除最后一个结点的语句序列

while(p->next->next!=NULL)p=p->next;q=p->next;p->next=NULL;

free(q);29用上述定义的单链表实现线性表的操作时，存在的问题：改进链表的设置：1．单链表的表长是一个隐含的值；1.增加“表长”、“表尾指针”和“当前位置的指针”三个数据域；

2.将基本操作中的“位序i”改变为“指针p”。2．在单链表的最后一个元素之后插入元素时，需遍历整个链表；3．在链表中，元素的“位序”概念淡化，结点的“位置”概念加强。返回30typedefstructLNode{

//结点类型Elemtypedata;

structLNode*next;}*Link,*Positiontypedefstruct

{

//链表类型

Linkhead,tail;

//分别指向链表头尾结点

intlen;

//链表中元素个数（长度）}Linklist;2.3.3一个带头结点的线性链表类型定义如下：

（用类C语言，见P37）：结点的结构表结构基本操作（略）返回31

最后一个结点的指针域的指针又指回第一个结点的链表。从表中任一结点出发均可找到表中其它结点

a1a2......an

1.循环链表

和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”即p->next?=headhead2.3.4其它形式的链表32单链表中查找只能从前往后，而不能从后往前查。为了查找方便，提高查找速度，可以在结点上增加一个指针域，用来存结点的直接前驱，这样的链表称为双向链表。其结点的结构为：typedefstructDuLNode{

ElemTypedata;//数据域

structDuLNode*prior;

//前驱指针域

structDuLNode*next;//后继指针域}DuLNode,*DuLinkList;

双向链表类型的定义如下：2.3.4其它形式的链表2.双向链表设指针p指向某一结点，则双向链表结构的对称性描述如下：–(p→prior)→next=p=(p→next)→prior,即结点*p的存储位置既存放在其前趋结点*(p→prior)的直接后继指针域中，也存放在它的后继结点*(p→next)的直接前趋指针域中ai-1aiai+1p343.双向循环链表空表非空表a1a2…...anhead->prior=head->next=headhead35双向链表插入操作（重点）：设p已指向第

i元素，请在第

i元素前插入元素x①ai-1的后继从

ai(指针是p)变为

x（指针是s):

s->next=p;

p->prior->next=s;

②ai的前驱从

ai-1(指针是p->prior)变为

x(指针是s);

s->prior=

p->prior;

p->prior

=s;

注意：要修改双向指针！x

sai-1

ai

p指针域的变化：××voiddinsertbefor(DuLNode*p，ElemTypex){DuLNode*s=malloc(sizeof(DuLNode));s—>data=x;s—>next=p;p—>prior—>next=s;s—>prior=p—>prior;p—>prior=s;}

问：（1）（2）（3）,（4）位置是否可交换？原则是什么？改成如下代码试试：s—>prior=p—>prior;s—>next=p;p—>prior—>next=s;p—>prior=s;改成如下代码试试：s—>next=p;s—>prior=p—>prior;p—>prior=s;p—>prior—>next=s;37指针域的变化：①ai-1的后继由ai变为ai+1(指针p->next

);

p->prior->next

=

p->next;

②

ai+1的前驱由ai变为ai-1

(指针p->prior);

p->next->prior

=p->prior;

ai-1

ai+1

ai

p双向链表删除操作：设p指向第i个元素,删除第i个元素注意：要修改双向指针！voidddeletenode(dlistnode*p){p–>prior–>next=p–>next;

p–>next–>prior=p–>prior;free(p);

39动态链表样式：静态链表样式：指针数据指针数据指针数据指示数据指示数据指示数据指示数据指示数据数组中每个元素都至少有两个分量，属于结构型数组。常用于无指针类型的高级语言中。用一片连续空间（一维数组）实现链式存储，这种方式称为静态链表。具体实现方法：定义一个结构型数组（每个元素都含有数据域和指示域），就可以完全描述链表，指示域就相当于动态链表中的指针,指示结点在数组中的相对位置。4.静态链表（自学）40

静态单链表的类型定义如下：#defineMAXSIZE1000//预分配链表的最大长度

typedefstruct{ElemTypedata;//数据域

intcur;

//指示域

}component

,SLinkList[MAXSIZE];

//这是一维结构型数组前例1：一线性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用静态链表如何表示？说明1：假设S为SLinkList型变量，则S[MAXSIZE]

为一个静态链表；S[0].cur则表示第1个结点在数组中的位置。41说明2：如果数组的第i个分量表示链表的第k个结点，则：S[i].data表示第k个结点的数据；

S[i].cur

表示第k+1个结点(即k的直接后继)的位置。data1ZHAO3LI5QIAN6WU0ZHOU4SUN2…………0123456…1000curi头结点说明3：静态链表的插入与删除操作与普通链表一样，不需要移动元素，只需修改指示器就可以了。例如：在线性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)的QIAN,SUN之间插入新元素LIU，可以这样实现：42Step1:将QIAN的指示器原内容备份到临时变量temp：temp=S[3].cur；Step2:将QIAN的指示器换为新元素LIU的位置：S[3].cur=7；Step3: