数据结构 第2章 线性表学习资料

1第2章线性表2.1线性表及其抽象数据类型2.2线性表的顺序存储结构2.3线性表的链式存储结构2.4一元多项式的表示及相加本章作业及上机题目2.5顺序表与链表的综合比较2.6总结与提高2第2章线性表2.1线性表及其抽象数据类型

定义：线性表(LinearList)是由n(n≥0)个类型相同的数据元素a1,a2,…，an组成的有限序列，记做（a1,a2,…，ai-1，ai，ai+1，…，an）。

数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继。逻辑结构图：3第2章线性表特点：①同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。②有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。③有序性：线性表中相邻数据元素之间存在着序偶关系<ai,ai+1>。2.1线性表及其抽象数据类型

4第2章线性表抽象数据类型定义：ADTLinearList{

数据元素：D={ai|ai∈D0,i=1,2,…，n;n≥0,D0为某一数据对象}

关系：Ｓ=<ai,ai+1>|ai,ai+1∈D0，i=1,2,…,n-1｝

基本操作：

（1）InitList（L）

操作前提：L为未初始化线性表。操作结果：将L初始化为空表。

（2）DestroyList(L)

操作前提：线性表L已存在。操作结果：将L销毁。

………p35}ADT

LinearList返回2.1线性表及其抽象数据类型

5第2章线性表2.2线性表的顺序存储结构定义:采用顺序存储结构的线性表通常称为顺序表。假设线性表中每个元素占k个单元，第一个元素的地址为loc(a1)，则第i个元素的地址为：loc(ai)=loc(a1)+(i-1)×k是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。6第2章线性表...loc(a1)+(maxlen-1)knan

loc(a1)+(n-1)k………

iai

loc(a1)+(i-1)k………

2a2

Loc(a1)+(2-1)k1a1Loc(a1)逻辑地址内存空间状态存储地址顺序存储结构示意图空闲2.2线性表的顺序存储结构7第2章线性表C语言定义#definemaxsize100/*线性表可能达到的最大长度*/typedefstruct{

ElemTypeelem[maxsize]；

intlast；

}SeqList； 2.2线性表的顺序存储结构8第2章线性表基本运算①查找操作②插入操作③删除操作2.2线性表的顺序存储结构9第2章线性表①查找操作按序号查找GetData(L,i)：要求查找线性表L中第i个数据元素，其结果是L.elem[i-1]。按内容查找Locate（L,e）:要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，如-1。2.2线性表的顺序存储结构10第2章线性表按内容查找Locate（L,e）:2.2线性表的顺序存储结构intLocate(SeqListL，ElemTypee){ i=0;while(L.elem[i]!=e)i++;return(i+1);

}((i<=L.last)&&(L.elem[i]!=e))if(i<=L.last)return(i+1);else return(-1);对吗？#definemaxsize100typedefstruct{

ElemTypeelem[maxsize]；

intlast；

}SeqList； 11第2章线性表2.2线性表的顺序存储②插入操作是指在表的第i(1≤i≤n+1)个位置，插入一个新元素e，使长度为n的线性表

(e1，…，ei-1，ei，…，en)

变成长度为n+1的线性表（e1，…,ei-1，e，ei，…，en）。例如：线性表(4,9,15,28,30,30,42,51,62)，需在第4个元素之前插入一个元素“21”。则需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”

插入到第4个位置。

(4,9,15,2128,30,30,42,51,62)12#defineOK1#defineERROR0intInsList(SeqList*L,inti,ElemTypee){intk;if((i<1)||(i>L->last+2)){printf(“插入位置i值不合法”)；

return(ERROR);}if(L->last>=maxsize-1){printf(“表已满无法插入”)；

return(ERROR);}

for(k=L->last;k>=i-1;k--)L->elem[k+1]=L->elem[k];

L->elem[i-1]=e;

L->last++;return(OK);}

时间复杂度：

O(n)#definemaxsize100typedefstruct{

ElemTypeelem[maxsize]；

intlast；

}SeqList； 判断插入位置是否合法判断表是否已满腾出第i个位置插入e13第2章线性表③删除操作是指将表的第i(1≤i≤n)个元素删去，使长度为n的线性表(e1，…,ei-1，ei，ei+1，…，en)，变成长度为n-1的线性表(e1，…,ei-1，ei+1，…，en)。2.2线性表的顺序存储结构14

intDelList(SeqList*L,inti,ElemType*e){intk;if((i<1)||(i>L->last+1)){printf(“删除位置不合法！”)；

return(ERROR)；

}*e=L->elem[i-1];

for(k=i;k<=L->last;k++)L->elem[k-1]=L->elem[k];L->last--;return(OK);}时间复杂度：O(n)#definemaxsize100typedefstruct{

ElemTypeelem[maxsize]；

intlast；

}SeqList； 15第2章线性表2.2线性表的顺序存储结构例2-1

：有两个顺序表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排列。算法思想：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、j分别指向表LA和LB中的元素，若LA.elem[i]>LB.elem[j]，则当前先将LB.elem[j]插入到表LC中，若LA.elem[i]≤LB.elem[j]，当前先将LA.elem[i]插入到表LC中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。16voidmerge(SeqList*LA,SeqList*LB,SeqList*LC){i=0;j=0;k=0;while(i<=LA->last&&j<=LB->last)if(LA->elem[i]<=LB->elem[j]){LC->elem[k]=LA->elem[i];i++;k++;}else{LC->elem[k]=LB->elem[j];j++;k++;}while(i<=LA->last){LC->elem[k]=LA->elem[i];i++;k++;}while(j<=LB->last){LC->elem[k]=LB->elem[j];j++;k++;}LC->last=LA->last+LB->last+1;}17第2章线性表优点：②可方便地随机存取表中的任一元素。缺点：①插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低；①无须为表示结点间的逻辑关系而增加额外的存储空间；②由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配。因此当表长变化较大时，难以确定合适的存储规模。返回2.2线性表的顺序存储结构18第2章线性表2.3线性表的链式存储结构定义:采用链式存储结构的线性表称为链表。动态链表静态链表单链表双链表循环链表实现角度链接方式19第2章线性表单链表：链表中的每个结点的指针域只有一个结点（Node）：单链表包括两个域数据域：指针域：用来存储结点的数据值用来存储数据元素的直接后继的地址（或位置）头指针：指向链表第一个结点的指针。为了正确地表示结点间的逻辑关系，必须在存储线性表的每个数据元素值的同时，存储指示其后继结点的地址（或位置）信息，这两部分信息组成的存储映象叫做结点。2.3线性表的链式存储结构20第2章线性表单链表头指针H存储地址数据域指针域1D437B1313C119HNULL25F3731A737G1943E2531AHBCDEFGH∧2.3线性表的链式存储结构21第2章线性表单链表头结点H∧带头结点的空单链表带头结点的单链表EFGH∧H2.3线性表的链式存储结构头指针：指向链表头结点的指针。22第2章线性表单链表存储结构描述typedefstructNode{

ElemTypedata；

structNode*next；}Node,*LinkList；2.3线性表的链式存储结构23第2章线性表单链表的基本运算①建立单链表②单链表查找

③单链表插入

④单链表删除⑤求单链表的长度2.3线性表的链式存储结构24第2章线性表①建立单链表尾插法建表sA∧s指向新申请的结点s->data=A;H∧sA∧插入第一个结点：插入某一个结点：sB∧将新结点插到当前单链表的表尾上。增加一个尾指针r，使之指向当前单链表的表尾。r->next=s;r=s;顺序可以颠倒吗？H∧初始化空表rrH∧A∧rr2.3线性表的链式存储结构25第2章线性表2.3线性表的链式存储②建立单链表尾插法建表算法LinklistCreateFromTail(){LinkListL;Node*r,*s;intflag=1;charc;L=(Node*)malloc(sizeof(Node));L->next=NULL;r=L;

while(flag){c=getchar();if(c!=’$’){s=(Node*)malloc(sizeof(Node));s->data=c;r->next=s;r=s;}else{flag=0;r->next=NULL;}}returnL;}typedefstructNode{ElemTypedata；

structNode*next；}Node,*LinkList；26第2章线性表①建立单链表头插法建表sA∧s指向新申请的结点s->data=A;H∧sA∧插入第一个结点：插入某一个结点：H∧A∧sB∧从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头结点之后，直至读入结束标志为止。×①s->next=H->next;②H->next=s;顺序可以颠倒吗？H∧初始化空表2.3线性表的链式存储结构27第2章线性表2.3线性表的链式存储①建立单链表头插法建表算法28LinkListCreateFromHead(){LinkListL;Node*s;charc;intflag=1;L=(Linklist)malloc(sizeof(Node))；

L->next=NULL;while(flag){c=getchar();if(c!=’$’){s=(Node*)malloc(sizeof(Node));s->data=c;

s->next=L->next;L->next=s;

}else flag=0;}returnL;}typedefstructNode{ElemTypedata；

structNode*next；}Node,*LinkList；29第2章线性表②单链表查找按序号查找

已知带头结点的单链表L，要查找表中第i个结点，则需要从单链表的头指针L出发，从第一个结点（L->next）开始顺着链域扫描。用指针p指向当前扫描到的结点,初值指向第一个结点（p=L->next），用j做记数器，累计当前扫描过的结点数（初值为0），当j=i时，指针p所指的结点就是要找的第i个结点。Node*Get(LinkListL,inti){Node*p；

p=L；

j=0；

while((p->next!=NULL)&&(j<i)){

p=p->next；

j++；

}if（i==j）returnp；

elsereturnNULL；

}2.3线性表的链式存储结构typedefstructNode{ElemTypedata；

structNode*next；}Node,*LinkList；没到表尾30第2章线性表③单链表查找按值查找

指在单链表中查找是否有结点值等于e的结点，若有的话，则返回首次找到的其值为e的结点的存储位置，否则返回NULL。查找过程从单链表的头指针指向的第一个结点出发，顺着链逐个将结点的值和给定值e作比较。Node*Locate(LinkListL,ElemTypekey){Node*p;p=L->next;while(p!=NULL)if(p->data!=key)

p=p->next;

elsebreak;returnp;}2.3线性表的链式存储结构typedefstructNode{ElemTypedata；

structNode*next；}Node,*LinkList；31第2章线性表③单链表插入

要在带头结点的单链表L中第i个数据元素之前插入一个数据元素e，需要首先在单链表中找到第i-1个结点并由指针pre指示，然后申请一个新的结点并由指针s指示，其数据域的值为e，并修改第i-1个结点的指针使其指向s，然后使s结点的指针域指向第i个结点。se∧×①s->next=pre->next;②pre->next=s;顺序可以颠倒吗？a1a2ai-1aian∧……preL2.3线性表的链式存储结构32算法实现第2章线性表2.3线性表的链式存储④单链表插入intInsList(LinkListL,inti,ElemTypee){ Node*pre,*s;intk=0;pre=L;while(pre!=NULL&&k<i-1){pre=pre->next;k=k+1;}if(k!=i-1){printf(“插入位置不合理！”)；

returnERROR;}s=(Node*)malloc(sizeof(Node));s->data=e;

s->next=pre->next;pre->next=s;returnOK;}33第2章线性表④单链表删除欲在带头结点的单链表L中删除第i个结点，则首先要通过计数方式找到第i-1个结点并使pre指向第i-1个结点，而后删除第i个结点并释放结点空间。×pre->next=pre->next->next;a1a2ai-1aian∧……preai+1rL

free(r);2.3线性表的链式存储结构34算法实现第2章线性表2.3线性表的链式存储⑤单链表删除intDelList(LinkListL,inti,ElemType*e){Node*pre,*r;pre=L;intk=0;while(pre->next!=NULL&&k<i-1){pre=pre->next;k=k+1;}if(k!=i-1){printf(“删除结点的位置i不合理！”);returnERROR;}

r=pre->next;pre->next=pre->next->next;

*e=r->data;free(r);returnOK;}35第2章线性表⑤求单链表的长度可以采用“数”结点的方法来求出单链表的长度，用指针p依次指向各个结点,从第一个元素开始“数”，一直“数”到最后一个结点（p->next=NULL）。算法实现int ListLength(LinkListL){Node*p;p=L->next; j=0;while(p!=NULL){ p=p->next;j++;}returnj;}2.3线性表的链式存储结构36第2章线性表2.3线性表的链式存储结构例2-2有两个单链表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个单链表LC，要求LC也是非递减有序排列。要求：新表LC利用原表的存储空间。LinkListMergeLinkList(LinkListLA,LinkListLB){Node*pa,*pb;LinkListLC;pa=LA->next;pb=LB->next;LC=LA;LC->next=NULL;r=LC;while(pa!=NULL&&pb!=NULL){if(pa->data<=pb->data){r->next=pa;r=pa;pa=pa->next;}else{r->next=pb;r=pb;pb=pb->next;}}if(pa)r->next=pa;elser->next=pb;free(LB);return(LC);}37第2章线性表循环链表(CircularLinkedList)：是一个首尾相接的链表。特点：将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，并称为循环单链表。在循环单链表中，表中所有结点被链在一个环上。L带头结点的空循环单链表a1a2ai-1aian……L带头结点的循环单链表a1a2ai-1aian……采用尾指针的循环单链表rear2.3线性表的链式存储结构38第2章线性表循环链表(CircularLinkedList)例2-3有两个带头结点的循环单链表LA、LB，编写一个算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。先找到两个链表的尾，并分别由指针p、q指向它们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个表的尾q，使它的链域指向第一个表的头结点。a1a2ai-1aian……LAb1b2bi-1bibn……LBpq

p->next=LB->next;q->next=LA;free(LB);2.3线性表的链式存储结构39第2章线性表循环链表(CircularLinkedList)算法实现1LinkListmerge_1(LinkListLA,LinkListLB){Node*p,*q;p=LA;q=LB;while(p->next!=LA)p=p->next; while(q->next!=LB)q=q->next;

p->next=LB->next;free(LB);

q->next=LA;

return(LA);}时间复杂度为

O(n)2.3线性表的链式存储结构40第2章线性表循环链表(CircularLinkedList)例2-3有两个采用带尾指针的循环链表LA、LB，编写一个算法，将两个循环单链表合并为一个循环单链表，返回其尾指针。执行时间可降低为O(1)。a1a2ai-1aian……RAb1b2bi-1bibn……RBpRA->next=RB->next->next;RB->next=p;free(RB->next);2.3线性表的链式存储结构41第2章线性表循环链表(CircularLinkedList)算法实现2LinkListmerge_2(LinkListRA,LinkListRB){Node*p;

p=RA->next;RA->next=RB->next->next;

free(RB->next);RB->next=p;return(RB);}2.3线性表的链式存储结构42第2章线性表双向链表(DoubleLinkedList)在单链表的每个结点里再增加一个指向其前趋的指针域prior。这样形成的链表中就有两条方向不同的链，我们称之为双(向)链表。结构定义：typedefstructDnode{ElemTypedata；

structDNode*prior，*next；}DNode, *DoubleList；datapriornext定义：2.3线性表的链式存储结构43第2章线性表双向链表(DoubleLinkedList)示意图：L空的双向循环链表L非空的双向循环链表abc2.3线性表的链式存储结构44第2章线性表双向链表(DoubleLinkedList)前插操作：ab……esp×①①

p->prior->next=s;②②s->prior=p->prior;顺序可以颠倒吗？×③③p->prior=s;④④s->next=p;顺序可以颠倒吗？顺序可以颠倒吗？2.3线性表的链式存储结构45第2章线性表2.3线性表的链式存储双向链表(DoubleLinkedList)前插操作算法实现：intDlinkIns(DoubleListL,inti,ElemTypee){DNode*s,*p;

p=search(L,i);if(p==NULL)returnERROR;s=(DNode*)malloc(sizeof(DNode));if(!s)returnERROR;s->data=e;

s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;returnOK;}46第2章线性表双向链表(DoubleLinkedList)删除操作：abc……p×①p->prior->next=p->next;①×②②p->next->prior=p->prior;free(p);2.3线性表的链式存储结构47第2章线性表双向链表(DoubleLinkedList)删除操作算法实现：int DlinkDel(DoubleListL,inti){ DNode*p;

p=search(L,i);if(p){p->prior->next=p->next;p->next->prior=p->prior;free(p);returnOK;}elsereturnERROR}返回2.3线性表的链式存储结构48第2章线性表静态链表(StaticLinkedList)一、静态链表的结构定义：#defineMaxsize链表可能达到的最大长度

typedefstruct{ElemTypedata;intcur;}Component,StaticList[Maxsize];2.3线性表的链式存储结构

在没有“指针”数据类型的高级语言中，可用“结构体”数组描述线性链表。2025/4/2849datacur

0

21b62a1...m-2xm-1m-1ymmz0

数组中cur域的内容为后继元素的下标(位置),其作用相当于指针，称其为游标。

该数组中元素的逻辑关系，取决于cur的值，而不取决于元素在数组中的相对位置。0号元素为头结点，cur值为0表示链表结束。

这种由数组描述的链表称为静态链表第2章线性表静态链表(StaticLinkedList)2.3线性表的链式存储结构2025/4/2850二、静态链表插入和删除示例：

线性表:

(a,b,c,d,f,g,h,i）

MaxSize=11

第2章线性表静态链表(StaticLinkedList)2.3线性表的链式存储结构0101011a21a21a22b32b32b33c43c43c44d54d94d95f65f65f66g76g76g87h87h87h88i08I08I099e59e5101010(a)初始化(b)插入e后(c)删除h后2025/4/2851三、静态链表初始化

初始化操作是指将静态单链表初始化为一个备用静态单链表。

设space为静态单链表的名字，av为备用单链表的头指针，其算法如下：voidinitial(StaticListspace,int*av){intk;space[0]->cur=0;/*设置静态单链表的头指针指向位置0*/for(k=0;k<Maxsize-1;k++) space[k]->cur=k+1;/*连链*/space[Maxsize-1]=0;/*标记链尾*/*av=1;/*设置备用链表头指针初值*/}第2章线性表静态链表(StaticLinkedList)2.3线性表的链式存储结构2025/4/2852四、静态链表结点的分配与回收

分配结点intgetnode(StaticListspace,int*av)/*从备用链表中取一个结点,分配给待插入的静态链表*/{inti=*av;*av=space[*av].cur;returni;}第2章线性表静态链表(StaticLinkedList)2.3线性表的链式存储结构结点回收voidfreenode(StaticListspace,int*av,intk)/*将下标为k的空闲结点插入到备用链表*/{space[k].cur=*av;*av=k;}2025/4/2853五、静态链表前插操作1、先从备用单链表上取一个可用的结点；2、将其插入到已用静态单链表第i个元素之前。voidinsbefore(StaticListspace,inti,int*av){j=getnode(space,av);/*修改备用表的头指针*/space[j].data=x; k=space[0].cur;for(m=1;m<i-1;m++)/*找第i-1个元素的位置k*/ k=space[k].cur;space[j].cur=space[k].cur;space[k].cur=j;}第2章线性表静态链表(StaticLinkedList)2.3线性表的链式存储结构2025/4/2854六、静态链表删除操作首先寻找第i-1个元素的位置，之后通过修改相应的游标域进行删除，并实现回收。voiddelete(StaticListspace;inti;int*av){k=space[0].cur;for(m=1;m<i-1;m++)k=space[k].cur;j=space[k].cur;space[k].cur=space[j].cur;freenode(space,av,j);/*回收*/}第2章线性表静态链表(StaticLinkedList)2.3线性表的链式存储结构55第2章线性表2.4一元多项式的表示及相加一个一元多项式pn(x)可按升幂的形式写成：

pn(x)=p0+p1x+p2x2+p3x3+…+pnxn可用单链表存储多项式的结点结构：typedefstructPolynode{intcoef;intexp;Polynode*next;}Polynode,*Polylist;56输入多项式的系数和指数，用尾插法建立一元多项式的链表。第2章线性表2.4一元多项式的表示及相加Polylistpolycreate(){Polynode*head,*rear,*s; intc,e;rear=head=(Polynode*)malloc(sizeof(Polynode));scanf(“%d,%d”,&c,&e);while(c!=0){s=(Polynode*)malloc(sizeof(Polynode));

s->coef=c;s->exp=e;rear->next=s; rear=s;

scanf(“%d,%d”,&c,&e);}rear->next=NULL;return(head);}

typedefstructPolynode{intcoef;intexp;Polynode*next;}Polynode,*Polylist;57第2章线性表2.4一元多项式的表示及相加两个多项式相加运算规则：两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复抄到“和多项式”中。若p->exp<q->exp，则结点p所指的结点应是“和多项式”中

的一项，令指针p后移；若p->exp=q->exp，则将两个结点中的系数相加，当和不为

零时修改结点p的系数域，释放q结点；

若和为零，则和多项式中无此项，删去p

和q结点，同时释放p和q结点;若p->exp>q->exp，则结点q所指的结点应是“和多项式”中

的一项，将结点q插入在结点p之前，且

令指针q在原来的链表上后移。58第2章线性表2.4一元多项式的表示及相加voidPolyAdd(Polylistpolya,Polylistpolyb){Polynode*rear,*p,*q,*temp; intsum;p=polya->next;q=polyb->next;rear=polya;free(polyb);while(p&&q){if(p->exp<q->exp){rear->next=p;rear=p;p=p->next;}elseif(p->exp>q->exp){rear->next=q;rear=q;q=q->next;}else{sum=p->coef+q->coef;if(sum){p->coef=sum;rear->next=p;rear=p;p=p->next;temp=q;q=q->next;free(temp);}else{temp=p;p=p->next;free(temp);temp=q;q=q->next;free(temp);}}}if(p)rear->next=p;elserear->next=q;}typedefstructPolynode{intcoef;int