数据结构课件链表部分

回顾上次课内容数据结构的相关概念数据的存储结构逻辑结构存储结构集合线性结构树形结构图状结构或网状结构顺序存储结构链接存储结构算法分析方法回顾上次课内容数据结构的相关概念逻辑结构集合顺序存储结构算法1第二章线性表主要内容：线性表的类型定义线性表的顺序表示和实现线性表的链式表示和实现线性表的应用举例第二章线性表主要内容：2线性结构的特点存在惟一的一个开始结点，称做“第一个”的数据元素存在惟一的一个终端结点，称做“最后一个”的数据元素除第一个外，每个数据元素只有一个前驱除最后一个外，每个数据元素只有一个后继线性结构的特点存在惟一的一个开始结点，称做“第一个”的数据元31.描述:

线性表是由n(n>=0)个数据元素(结点)a1,a2,….,ai,….,an组成的有限序列。其中，数据元素的个数n定义为表长。当n=0时称为空表，非空的线性表(n>0)记为：(a1,a2,….,ai,…..,an)一、逻辑结构注意:

1.数据元素ai是一个抽象的符号2.ai可取各种数据类型3.同一线性表中的元素必定具有相同的特性，属于同一数据对象 4.相邻数据元素之间存在序偶关系5.i是数据元素ai在线性表中的位序(1≤i≤

n)2.逻辑特征：仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个前驱和一个后继线性表是一个线性结构2.1线性表的类型定义1.描述:线性表是由n(n>=0)个数据元素(结点4二、抽象数据类型线性表的定义ADTList{ 数据对象：D={ai︱ai∈Elemset,i=1,2,…,n,n≥0} 数据关系：R1={<ai-1,ai>︱ai-1,ai∈D,i=2,…,n} 基本操作： 构造、销毁、置空、判空、获取元素、插入、删除、定位等。 }ADTLista1是第一个元素，有且仅有一个直接后继元素a2；an是最后一个元素，有且仅有一个直接前趋元素an-1；其余ai(1<i<n)有且仅有一个直接前趋ai-1，有且仅有一个直接后继ai+1二、抽象数据类型线性表的定义5顺序表示（存储）：指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。线性表顺序存储结构示意图2.2线性表的顺序表示和实现顺序表示（存储）：指在内存中用地址连续的一块存储空间顺序存放6数据元素存储位置表示设a１的存储地址为Loc(a１)，每个数据元素占l个存储地址，则第i个数据元素的地址为：Loc(ai)=Loc(a１)+(i-1)*l，1≤i≤n逻辑上相邻的ai和ai+1以相邻的存储位置。确定起始位置后，顺序表中任一数据元素都可随机存取。顺序表是一种随机存取的存储结构。数据元素存储位置表示7高级语言中一般用数组来描述顺序存储。#include<stdio.h>#defineMAXSIZE100typedefintElemType;typedefstruct{ ElemTypea[MAXSIZE]; intlength;}Sqlist;因为线性表长度可变，且所需最大空间随问题不同而不同，所以用动态分配的一维数组(P22)。为使得算法简明扼要，暂使用静态数组。高级语言中一般用数组来描述顺序存储。8线性表的建立、输出算法初始化voidinitlist(Sqlist*L){L->length=0;}建立顺序表voidcreat_sqlist(Sqlist&L){inti,n;cout<<"n=?;cin>>n;L.length=n;for(i=0;i<n;i++)cin>>L.a[i];}voidinitlist(Sqlist&L){L.length=0;}SqlistSl;initlist(&Sl);SqlistSl;initlist(Sl);线性表的建立、输出算法初始化voidinitlist(Sq9输出顺序表voidoutputl(SqlistL){inti;cout<<"Listlength"<<L.length<<endl;for(i=0;i<L.length;i++){ cout<<L.a[i]<<""; if((i+1)%10==0)cout<<endl;}cout<<endl;}输出顺序表voidoutputl(SqlistL)10(a1,…,ai-1,ai,…,an)改变为(a1,…,ai-1,e,ai,…,an)a1a2

…ai-1ai

…ana1a2

…ai-1

…aiean表的长度加1插入：在线性表第i（1≤i≤n+1）个位置上插入元素e线性表主要操作的实现(a1,…,ai-1,ai,…,an)改变为a11注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是L.a[i-1]。voidinsert_sq(Sqlist&L,inti,ElemTypee){ intj; if(L.length==MAXSIZE)cout<<"ERROR!"<<endl; else if(i<1||i>L.length+1)cout<<"ERROR!"<<endl; else{ for(j=L.length;j>i-1;j--) L.a[j]=L.a[j-1]; L.a[i-1]=e; L.length++; }}注意：C语言中的数组下标从“0”开始，因此，若L是Sqlis12这里的问题规模是表的长度，设它的值为n。该算法的时间主要花费在循环的元素后移语句上，所需移动元素的次数不仅依赖于表的长度，而且还与插入位置有关。

i位置 移动次数 1 n 2 n-1 ︰ ︰ i n-i+1︰ ︰ n1 n+1 0插入操作时间复杂度分析这里的问题规模是表的长度，设它的值为n。该算法的时间13最好情况下：T(n)=O(1)最坏情况下：T(n)=O(n)平均时间复杂度：长度为n的顺序表中，插入一个结点，令E(n)表示移动结点的期望值(移动平均次数)，在表中第i个位置插入一个结点移动的次数为n-i+1.其中pi表示在表中第i位置插入结点的概率。Pi＝1/(n+1)计算得E(n)=n/2，所以平均时间复杂度为O(n)最好情况下：T(n)=O(1)14(a1,…,ai-1,ai,ai+1,…,an)改变为(a1,…,ai-1,ai+1,…,an)（1≤i≤n）ai+1…an表的长度减1a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

删除：在线性表中删除第i个元素，使(a1,…,ai-1,ai,ai+1,…,an15ElemTypedelete_sq(Sqlist&L,inti){ intx,j; if(L.length==0) { cout<<"ERROR!"<<endl; return(-1); } elseif(i<1||i>L.length) { cout<<"ERROR!“<<endl; return(-1); } else{ x=L.a[i-1]; for(j=i;j<=L.length-1;j++)L.a[j-1]=L.a[j]; L.length--; returnx; }}ElemTypedelete_sq(Sqlist&L,16算法的时间复杂度分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。 i位置 移动次数 1 n-1 2 n-2︰ ︰ i n-i︰ ︰n-11n 0删除操作时间复杂度分析算法的时间复杂度分析与插入算法相似，结点的移动次数也是由表长17最好情况下：T(n)=O(1)最坏情况下：T(n)=O(n-1)平均时间复杂度：与插入运算相同，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素ai+1～an都要向上移动一个位置，共移动了n-i个元素，所以平均移动数据元素的次数：在等概率情况下，pi=1/n，则：这说明顺序表上作删除运算时大约需要移动表中一半的元素，显然该算法的时间复杂度为Ｏ(n)。

最好情况下：T(n)=O(1)18顺序表的优点：

（1）各结点存储单元物理位置上的邻接关系表示了结点间的逻辑关系，因此，无须增加额外的存储空间表示结点间的逻辑关系。（2）因其为随机存储结构，故可以随机存取表中任一结点。顺序表的缺点：（1）插入和删除不方便，通常须移动大量结点，效率较低。（2）难以进行连续的存储空间的预分配，尤其是当表变化较大时。顺序表的优点：顺序表的缺点：19重要结论在顺序存储表示的线性表中插入或删除一个数据元素，平均约需要移动一半的元素因此，顺序存储表示仅适用于不经常进行插入和删除操作并且表中元素相对稳定的表重要结论在顺序存储表示的线性表中插入或删除一个数据元素，平均20查找：在线性表L中查找值为e的元素，如果存在，返回位置(>0)，否则返回-1，表示未找到。intlocate_sq(SqlistL,ElemTypee){ inti; i=0; while(i<=L.length-1&&L.a[i]!=e)i++; if(i<=L.length-1)return(i+1); return(-1);}查找：在线性表L中查找值为e的元素，如果存在，返回位置(>021合并：两表分别非递减有序(递增或等值)，合并后仍然非递减有序。voidmerge_list(Sqlista,Sqlistb,Sqlist&c){ inti,j,k; i=j=k=0; c.length=a.length+b.length; while(i<=a.length-1&&j<=b.length-1) { if(a.a[i]<=b.a[j]){c.a[k]=a.a[i];i++;k++;} else{c.a[k]=b.a[j];j++;k++;} } while(i<=a.length-1){c.a[k]=a.a[i];i++;k++;} while(j<=b.length-1){c.a[k]=b.a[j];j++;k++;}}合并：两表分别非递减有序(递增或等值)，合并后仍然非递减有序22单链表循环链表双向链表静态链表单链表应用举例2.3线性表的链式表示与实现单链表2.3线性表的链式表示与实现23线性表的链式表示和实现链式分配线性表数据元素的存储单元可以不连续，存放数据元素的结点至少包括两个域（数据域、指针域），也可以包含若干个数据域、指针域。单链表：每个结点只有一个指针域链表链接的顺序和数据元素的逻辑顺序一致，结点的物理位置可任意安排头指针：存放第一个结点的存储地址（附加）头结点：在单链表第一个结点之前附设一个结点线性表的链式表示和实现链式分配24a1heada2a6^…a57a41a26a13a32a6null123456785headheada1a6^…头结点头指针头指针空表^heada1heada2a6^…a57a41a26a13a32a6n25存储表示typedefstructLNode{ElemTypedata;//数据域structLNode*next;//指针域}LNode,*linklist;其中linklist等价于LNode*若设LNode*p,*q;LinkListH;则p,q,H都是指针变量,p->data表示数据域p->next表示指针域线性表的单链表存储表示线性表的单链表26函数mallocfree(p);访问结点指针赋值的操作P=(LNode*)malloc(sizeof(LNode));产生一个Lnode类型结点，把首地址送给P变量系统回收P所指向的结点（若干字节），P中无所指向Lnode*p,s;p->data=20;p->next=null;(s.data=20;s.next=null;用的少)函数mallocfree(p);访问结点指针赋值的操作P=(27指针指向结点p=qqp指针指向后继p=q->next指针移动p=p->nextqppp指针赋值的操作指针指向结点p=qqp指针指向后继p=q->next指针28pqp->next=qp->next=q->nextpqpqp->next=qp->next=q->nextpq29创建链表单链表的基本运算voidcreat_list(){ ElemTypex; LNode*ptr,*p; p=head; cout<<"x=?"; cin>>x; while(x!=999){ ptr=newLNode; ptr->data=x; ptr->next=NULL; p->next=ptr; p=ptr; cout<<"x=?"; cin>>x; }}调用语句：head=newLNode;head->next=NULL;creat_list();定义head为全局变量创建链表单链表的基本运算voidcreat_list()30voidcreate(LNode*L){ inti,n; LNode*s,*p; p=L; cout<<"inputthelengthofthelist:"; cin>>n; for(i=1;i<=n;i++) { s=newLNode; cout<<"element:"; cin>>s->data; p->next=s; p=s; } p->next=NULL;}调用语句：head=newLNode;head->next=NULL;create(head);定义head为局部变量voidcreate(LNode*L)调用语句：定义he31LNode*Creat_L(intn){ inti; LNode*L,*p; L=newLNode; L->next=NULL; for(i=n;i>=1;i--) { p=newLNode; cout<<"element:"; cin>>p->data; p->next=L->next; L->next=p; } return(L);}调用语句：head=Creat_L(5);定义head为全局变量LNode*Creat_L(intn)调用语句：定义he32输出链表voidout_list(){ LNode*q; q=head->next; if(q==NULL)cout<<"Emptylist!\n"; else{ while(q!=NULL){ cout<<q->data<<""; q=q->next; } } cout<<endl;}输出链表voidout_list()33取已知的线性链表的第i个元素的值，由函数名返回ElemTypeGetElem(LNode*L,inti){ intj; LNode*p; p=L->next; j=1; while(p&&j<i){p=p->next;j++;} if(!p||j>i)return(-1); elsereturn(p->data);}调用语句：cout<<"GetElemis"<<GetElem(head,4)<<endl;语句频度：i<1，0次1≤i≤n，i-1次i>n，n次平均为n数量级，故T(n)=O(n)取已知的线性链表的第i个元素的值，由函数名返回ElemTy34在带头结点的单链表L中第i结点之前插入元素evoidInsert_L(LNode*L,inti,ElemTypee){ LNode*p,*s; intj; p=L; j=1; while(p!=NULL&&j<i){p=p->next;j++;} if(p==NULL||j>i) cout<<"ERROR!"<<endl; else {s=newLNode; s->data=e; s->next=p->next; p->next=s; }}在带头结点的单链表L中第i结点之前插入元素evoidIn35删除带头结点的单链表L中第i个结点，其数据元素由函数名返回ElemTypedelete_list(LNode*L,inti){ LNode*p,*q; intj; ElemTypee; p=L; j=0; while(p->next!=NULL&&j<i-1){p=p->next;j++;} if(p->next==NULL||j>i-1)cout<<"ERROR!"<<endl; else{ q=p->next; e=q->data; p->next=q->next; delete(q); return(e); }}删除带头结点的单链表L中第i个结点，其数据元素由函数名返回36voidlistdelete_L(LNode*L,ElemTypex){ LNode*p,*q; p=L; while(p->next&&p->next->data!=x)//找x的前驱 p=p->next; if(!p->next)cout<<"Notfindelement"<<endl; else{ q=p->next; p->next=q->next; delete(q);//删除x结点 }}在带头结点的单链表L中，查找值x的元素，删除之。（假设L中元素不重复）voidlistdelete_L(LNode*L,Ele37链表合并—La,Lb有序递增，合并为Lc，仍非递减有序LNode*merge_list(LNode*La,LNode*Lb){ LNode*Lc,*pa,*pb,*pc; Lc=La;pc=La;//以La链为基础 pa=La->next;pb=Lb->next; while(pa!=NULL&&pb!=NULL) { if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;} else{pc->next=pb;pc=pb;pb=pb->next;} } if(pa!=NULL)pc->next=pa; elsepc->next=pb; delete(Lb); return(Lc);}T(n)=O(m+n)链表合并—La,Lb有序递增，合并为Lc，仍非递减有序LN38链式存储结构小结：

（1）a1,ai+1地址可不连续；（2）不能直接存取，需先移动指针到ai；（3）插入、删除时，不需大量移动元素。以上是动态链表的基本操作，另外还有静态链表，课下自己了解，适用于BASIC语言。链式存储结构小结：以上是动态链表的基本操作，另外还有静态链表39最后一个结点的指针域的指针又指回第一个结点的链表和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。a1a2an…H(a)^H(b)单循环链表循环链表最后一个结点的指针域的指针又指回第一个结点的链表a1a2an40p=A→next;

A→next=B→next→next;B→next=p;A=B;

操作和线性链表基本一致，有时在循环链表中设立尾指针可使操作简化。见下图

…A…B…A…Bp=A→next;

A→next=B→41//-----线性表的双向链表存储结构-----typedefstructDuLNode{ElemTypedata;//数据域structDuLNode*prior;//指向前驱的指针域structDuLNode*next;//

指向后继的指针域}DuLNode,*DuLinkList;双向链表^a1a2an^head……双向链表//-----线性表的双向链表存储结构-----双向链表42ai-1aies->prior=p->prior;psai-1ai插入p->prior->next=s;s->next=p;p->prior=s;ai-1aies->prior=p->prior;43ai-1删除aiai+1p->prior->next=p->next;p->next->prior=p->prior;free(p);pai-1ai-1删除aiai+1p->prior->next=p44本章介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链表。顺序存储有三个优点：(1)方法简单，各种高级语言中都有数组，容易实现。(2)不用为表示结点间的逻辑关系而增加额外的存储开销。(3)顺序表具有按元素序号随机访问的特点。顺序表和链表的比较本章介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链45但它也有两个缺点：⑴在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。⑵需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。链表的优缺点恰好与顺序表相反。但它也有两个缺点：46⒈基于存储的考虑

对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低。⒉基于运算的考虑

如果经常做的运算是按序号访问数据元素，顺序表优于链表；在顺序表中做插入、删除操作时平均移动表中一半的元素，在链表中作插入、删除操作，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑后者优于前者。⒊基于环境的考虑

顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。

总之，两种存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。在实际中怎样选取存储结构呢？通常有以下几点考虑：⒈基于存储的考虑在实际中怎样选取存储结构呢？通常有以下几点47

在计算机中，可以用一个线性表来表示:P=(p0,p1,…，pn)一、一元多项式的表示但是对于形如

S(x)=1+3x10000–2x20000的多项式，上述表示方法是否合适？2.4线性表的应用__一元多项式相加在计算机中，可以用一个线性表来表示:一、一元多项式的表示但48

一般情况下的一元稀疏多项式可写成

Pn(x)=p1xe1+p2xe2+┄+pmxem其中：pi是指数为ei的项的非零系数，

0≤e1<e2<…<em=n可以下列线性表表示:（（p1,e1）,(p2,e2),┄,(pm,em)）一般情况下的一元稀疏多项式可写成可以下列线性表表示:49

P999(x)=7x3-2x12-8x999例如:可用线性表

((7,3),(-2,12),(-8,999))表示ADTPolynomial{…}p40P999(x)=7x3-2x12-8x999例50可用顺序表示typedefstruct{ floatcoef; intexp;}ElemType;typedefstruct{ ElemTypea[MAXSIZE]; intlength;}Sqlist;SqlistL;如果要访问第五项：L.a[4].coefL.a[4].exp链式表示typedefstructpoly{ floatcoef; intexp; structpoly*next;}poly;可用顺序表示如果要访问第五项：链式表示51加法操作的实现：设有两个多项式

A(x)=7+3x+9x8+5x17

B(x)=8x+22x7-9x8可用两个带头结点的单链表表示如下：图中每个结点表示多项式中的一项.相加的运算规则：

指数相同项相加若和不为零，则构成“和多项式”中的一项，所有指数不相同的项均复抄到“和多项式”中。“和多项式”链表中的结点无须另外生成，只需将B加到A上。一元多项式的相加加法操作的实现：设有两个多项式

A(x)=7+3x+9x852C=A+B设p和q分别指向A,B中当前进行比较的某一结点，比较结点指数项有三种情况：1、若p->exp=q->exp则将两结点中的系数相加，当和不为零时修改p结点中的系数域，将p所指结点加入C;p、q后移。2、若p->exp<q->exp

则将p所指结点加入C。p后移。3、若p->exp>q->exp

则q所指结点加入C。q后移。C=A+B53typedefstructpoly{ floatcoef;//系数 intexp;//指数 structpoly*next;}poly;结点的数据元素类型定义为:元多项式的实现typedefstructpoly{结点的数据元素类型定54poly*add_poly(poly*La,poly*Lb){ poly*Lc,*pa,*pb,*pc,*s1,*s2; intx; Lc=La;pc=La;//以La链为基础 pa=La->next;pb=Lb->next;delete(Lb); while(pa&&pb) { if(pa->exp<pb->exp){pc->next=pa;pc=pa;pa=pa->next;} elseif(pa->exp>pb->exp){pc->next=pb;pc=pb;pb=pb->next;}poly*add_poly(poly*La,poly55else{ x=pa->coef+pb->coef; if(x==0){ s1=pa;s2=pb; pc->next=pa->next; pa=pa->next;pb=pb->next; delete(s1);delete(s2);} else{s2=pb; pc->next=pa;pa->coef=x; pc=pa;pa=pa->next;pb=pb->next; delete(s2);} } }else{ x=pa->coef+pb->coef56本章小结1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。本章小结1.了解线性表的逻辑结构特性是数据元素之间存在着线性57思考题P29算法2.8，若L不是带头结点的单链表，要如何调整程序？想一想，增加头结点的目的是什么？思考题P29算法2.8，若L不是带头结点的单链表，要如何58实验：有一个单链表的第一个结点指针为head,编写一个函数将该单链表逆置,即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点。在逆置中不能建立新的单链表调试好后，老师检查，计入实验成绩。上机后写实验报告。编程环境：VC6.0++实验：59回顾上次课内容数据结构的相关概念数据的存储结构逻辑结构存储结构集合线性结构树形结构图状结构或网状结构顺序存储结构链接存储结构算法分析方法回顾上次课内容数据结构的相关概念逻辑结构集合顺序存储结构算法60第二章线性表主要内容：线性表的类型定义线性表的顺序表示和实现线性表的链式表示和实现线性表的应用举例第二章线性表主要内容：61线性结构的特点存在惟一的一个开始结点，称做“第一个”的数据元素存在惟一的一个终端结点，称做“最后一个”的数据元素除第一个外，每个数据元素只有一个前驱除最后一个外，每个数据元素只有一个后继线性结构的特点存在惟一的一个开始结点，称做“第一个”的数据元621.描述:

线性表是由n(n>=0)个数据元素(结点)a1,a2,….,ai,….,an组成的有限序列。其中，数据元素的个数n定义为表长。当n=0时称为空表，非空的线性表(n>0)记为：(a1,a2,….,ai,…..,an)一、逻辑结构注意:

1.数据元素ai是一个抽象的符号2.ai可取各种数据类型3.同一线性表中的元素必定具有相同的特性，属于同一数据对象 4.相邻数据元素之间存在序偶关系5.i是数据元素ai在线性表中的位序(1≤i≤

n)2.逻辑特征：仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个前驱和一个后继线性表是一个线性结构2.1线性表的类型定义1.描述:线性表是由n(n>=0)个数据元素(结点63二、抽象数据类型线性表的定义ADTList{ 数据对象：D={ai︱ai∈Elemset,i=1,2,…,n,n≥0} 数据关系：R1={<ai-1,ai>︱ai-1,ai∈D,i=2,…,n} 基本操作： 构造、销毁、置空、判空、获取元素、插入、删除、定位等。 }ADTLista1是第一个元素，有且仅有一个直接后继元素a2；an是最后一个元素，有且仅有一个直接前趋元素an-1；其余ai(1<i<n)有且仅有一个直接前趋ai-1，有且仅有一个直接后继ai+1二、抽象数据类型线性表的定义64顺序表示（存储）：指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。线性表顺序存储结构示意图2.2线性表的顺序表示和实现顺序表示（存储）：指在内存中用地址连续的一块存储空间顺序存放65数据元素存储位置表示设a１的存储地址为Loc(a１)，每个数据元素占l个存储地址，则第i个数据元素的地址为：Loc(ai)=Loc(a１)+(i-1)*l，1≤i≤n逻辑上相邻的ai和ai+1以相邻的存储位置。确定起始位置后，顺序表中任一数据元素都可随机存取。顺序表是一种随机存取的存储结构。数据元素存储位置表示66高级语言中一般用数组来描述顺序存储。#include<stdio.h>#defineMAXSIZE100typedefintElemType;typedefstruct{ ElemTypea[MAXSIZE]; intlength;}Sqlist;因为线性表长度可变，且所需最大空间随问题不同而不同，所以用动态分配的一维数组(P22)。为使得算法简明扼要，暂使用静态数组。高级语言中一般用数组来描述顺序存储。67线性表的建立、输出算法初始化voidinitlist(Sqlist*L){L->length=0;}建立顺序表voidcreat_sqlist(Sqlist&L){inti,n;cout<<"n=?;cin>>n;L.length=n;for(i=0;i<n;i++)cin>>L.a[i];}voidinitlist(Sqlist&L){L.length=0;}SqlistSl;initlist(&Sl);SqlistSl;initlist(Sl);线性表的建立、输出算法初始化voidinitlist(Sq68输出顺序表voidoutputl(SqlistL){inti;cout<<"Listlength"<<L.length<<endl;for(i=0;i<L.length;i++){ cout<<L.a[i]<<""; if((i+1)%10==0)cout<<endl;}cout<<endl;}输出顺序表voidoutputl(SqlistL)69(a1,…,ai-1,ai,…,an)改变为(a1,…,ai-1,e,ai,…,an)a1a2

…ai-1ai

…ana1a2

…ai-1

…aiean表的长度加1插入：在线性表第i（1≤i≤n+1）个位置上插入元素e线性表主要操作的实现(a1,…,ai-1,ai,…,an)改变为a70注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是L.a[i-1]。voidinsert_sq(Sqlist&L,inti,ElemTypee){ intj; if(L.length==MAXSIZE)cout<<"ERROR!"<<endl; else if(i<1||i>L.length+1)cout<<"ERROR!"<<endl; else{ for(j=L.length;j>i-1;j--) L.a[j]=L.a[j-1]; L.a[i-1]=e; L.length++; }}注意：C语言中的数组下标从“0”开始，因此，若L是Sqlis71这里的问题规模是表的长度，设它的值为n。该算法的时间主要花费在循环的元素后移语句上，所需移动元素的次数不仅依赖于表的长度，而且还与插入位置有关。

i位置 移动次数 1 n 2 n-1 ︰ ︰ i n-i+1︰ ︰ n1 n+1 0插入操作时间复杂度分析这里的问题规模是表的长度，设它的值为n。该算法的时间72最好情况下：T(n)=O(1)最坏情况下：T(n)=O(n)平均时间复杂度：长度为n的顺序表中，插入一个结点，令E(n)表示移动结点的期望值(移动平均次数)，在表中第i个位置插入一个结点移动的次数为n-i+1.其中pi表示在表中第i位置插入结点的概率。Pi＝1/(n+1)计算得E(n)=n/2，所以平均时间复杂度为O(n)最好情况下：T(n)=O(1)73(a1,…,ai-1,ai,ai+1,…,an)改变为(a1,…,ai-1,ai+1,…,an)（1≤i≤n）ai+1…an表的长度减1a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

删除：在线性表中删除第i个元素，使(a1,…,ai-1,ai,ai+1,…,an74ElemTypedelete_sq(Sqlist&L,inti){ intx,j; if(L.length==0) { cout<<"ERROR!"<<endl; return(-1); } elseif(i<1||i>L.length) { cout<<"ERROR!“<<endl; return(-1); } else{ x=L.a[i-1]; for(j=i;j<=L.length-1;j++)L.a[j-1]=L.a[j]; L.length--; returnx; }}ElemTypedelete_sq(Sqlist&L,75算法的时间复杂度分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。 i位置 移动次数 1 n-1 2 n-2︰ ︰ i n-i︰ ︰n-11n 0删除操作时间复杂度分析算法的时间复杂度分析与插入算法相似，结点的移动次数也是由表长76最好情况下：T(n)=O(1)最坏情况下：T(n)=O(n-1)平均时间复杂度：与插入运算相同，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素ai+1～an都要向上移动一个位置，共移动了n-i个元素，所以平均移动数据元素的次数：在等概率情况下，pi=1/n，则：这说明顺序表上作删除运算时大约需要移动表中一半的元素，显然该算法的时间复杂度为Ｏ(n)。

最好情况下：T(n)=O(1)77顺序表的优点：

（1）各结点存储单元物理位置上的邻接关系表示了结点间的逻辑关系，因此，无须增加额外的存储空间表示结点间的逻辑关系。（2）因其为随机存储结构，故可以随机存取表中任一结点。顺序表的缺点：（1）插入和删除不方便，通常须移动大量结点，效率较低。（2）难以进行连续的存储空间的预分配，尤其是当表变化较大时。顺序表的优点：顺序表的缺点：78重要结论在顺序存储表示的线性表中插入或删除一个数据元素，平均约需要移动一半的元素因此，顺序存储表示仅适用于不经常进行插入和删除操作并且表中元素相对稳定的表重要结论在顺序存储表示的线性表中插入或删除一个数据元素，平均79查找：在线性表L中查找值为e的元素，如果存在，返回位置(>0)，否则返回-1，表示未找到。intlocate_sq(SqlistL,ElemTypee){ inti; i=0; while(i<=L.length-1&&L.a[i]!=e)i++; if(i<=L.length-1)return(i+1); return(-1);}查找：在线性表L中查找值为e的元素，如果存在，返回位置(>080合并：两表分别非递减有序(递增或等值)，合并后仍然非递减有序。voidmerge_list(Sqlista,Sqlistb,Sqlist&c){ inti,j,k; i=j=k=0; c.length=a.length+b.length; while(i<=a.length-1&&j<=b.length-1) { if(a.a[i]<=b.a[j]){c.a[k]=a.a[i];i++;k++;} else{c.a[k]=b.a[j];j++;k++;} } while(i<=a.length-1){c.a[k]=a.a[i];i++;k++;} while(j<=b.length-1){c.a[k]=b.a[j];j++;k++;}}合并：两表分别非递减有序(递增或等值)，合并后仍然非递减有序81单链表循环链表双向链表静态链表单链表应用举例2.3线性表的链式表示与实现单链表2.3线性表的链式表示与实现82线性表的链式表示和实现链式分配线性表数据元素的存储单元可以不连续，存放数据元素的结点至少包括两个域（数据域、指针域），也可以包含若干个数据域、指针域。单链表：每个结点只有一个指针域链表链接的顺序和数据元素的逻辑顺序一致，结点的物理位置可任意安排头指针：存放第一个结点的存储地址（附加）头结点：在单链表第一个结点之前附设一个结点线性表的链式表示和实现链式分配83a1heada2a6^…a57a41a26a13a32a6null123456785headheada1a6^…头结点头指针头指针空表^heada1heada2a6^…a57a41a26a13a32a6n84存储表示typedefstructLNode{ElemTypedata;//数据域structLNode*next;//指针域}LNode,*linklist;其中linklist等价于LNode*若设LNode*p,*q;LinkListH;则p,q,H都是指针变量,p->data表示数据域p->next表示指针域线性表的单链表存储表示线性表的单链表85函数mallocfree(p);访问结点指针赋值的操作P=(LNode*)malloc(sizeof(LNode));产生一个Lnode类型结点，把首地址送给P变量系统回收P所指向的结点（若干字节），P中无所指向Lnode*p,s;p->data=20;p->next=null;(s.data=20;s.next=null;用的少)函数mallocfree(p);访问结点指针赋值的操作P=(86指针指向结点p=qqp指针指向后继p=q->next指针移动p=p->nextqppp指针赋值的操作指针指向结点p=qqp指针指向后继p=q->next指针87pqp->next=qp->next=q->nextpqpqp->next=qp->next=q->nextpq88创建链表单链表的基本运算voidcreat_list(){ ElemTypex; LNode*ptr,*p; p=head; cout<<"x=?"; cin>>x; while(x!=999){ ptr=newLNode; ptr->data=x; ptr->next=NULL; p->next=ptr; p=ptr; cout<<"x=?"; cin>>x; }}调用语句：head=newLNode;head->next=NULL;creat_list();定义head为全局变量创建链表单链表的基本运算voidcreat_list()89voidcreate(LNode*L){ inti,n; LNode*s,*p; p=L; cout<<"inputthelengthofthelist:"; cin>>n; for(i=1;i<=n;i++) { s=newLNode; cout<<"element:"; cin>>s->data; p->next=s; p=s; } p->next=NULL;}调用语句：head=newLNode;head->next=NULL;create(head);定义head为局部变量voidcreate(LNode*L)调用语句：定义he90LNode*Creat_L(intn){ inti; LNode*L,*p; L=newLNode; L->next=NULL; for(i=n;i>=1;i--) { p=newLNode; cout<<"element:"; cin>>p->data; p->next=L->next; L->next=p; } return(L);}调用语句：head=Creat_L(5);定义head为全局变量LNode*Creat_L(intn)调用语句：定义he91输出链表voidout_list(){ LNode*q; q=head->next; if(q==NULL)cout<<"Emptylist!\n"; else{ while(q!=NULL){ cout<<q->data<<""; q=q->next; } } cout<<endl;}输出链表voidout_list()92取已知的线性链表的第i个元素的值，由函数名返回ElemTypeGetElem(LNode*L,inti){ intj; LNode*p; p=L->next; j=1; while(p&&j<i){p=p->next;j++;} if(!p||j>i)return(-1); elsereturn(p->data);}调用语句：cout<<"GetElemis"<<GetElem(head,4)<<endl;语句频度：i<1，0次1≤i≤n，i-1次i>n，n次平均为n数量级，故T(n)=O(n)取已知的线性链表的第i个元素的值，由函数名返回ElemTy93在带头结点的单链表L中第i结点之前插入元素evoidInsert_L(LNode*L,inti,ElemTypee){ LNode*p,*s; intj; p=L; j=1; while(p!=NULL&&j<i){p=p->next;j++;} if(p==NULL||j>i) cout<<"ERROR!"<<endl; else {s=newLNode; s->data=e; s->next=p->next; p->next=s; }}在带头结点的单链表L中第i结点之前插入元素evoidIn94删除带头结点的单链表L中第i个结点，其数据元素由函数名返回ElemTypedelete_list(LNode*L,inti){ LNode*p,*q; intj; ElemTypee; p=L; j=0; while(p->next!=NULL&&j<i-1){p=p->next;j++;} if(p->next==NULL||j>i-1)cout<<"ERROR!"<<endl; else{ q=p->next; e=q->data; p->next=q->next; delete(q); return(e); }}删除带头结点的单链表L中第i个结点，其数据元素由函数名返回95voidlistdelete_L(LNode*L,ElemTypex){ LNode*p,*q; p=L; while(p->next&&p->next->data!=x)//找x的前驱 p=p->next; if(!p->next)cout<<"Notfindelement"<<endl; else{ q=p->next; p->next=q->next; delete(q);//删除x结点 }}在带头结点的单链表L中，查找值x的元素，删除之。（假设L中元素不重复）voidlistdelete_L(LNode*L,Ele96链表合并—La,Lb有序递增，合并为Lc，仍非递减有序LNode*merge_list(LNode*La,LNode*Lb){ LNode*Lc,*pa,*pb,*pc; Lc=La;pc=La;//以La链为基础 pa=La->next;pb=Lb->next; while(pa!=NULL&&pb!=NULL) { if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;} else{pc->next=pb;pc=pb;pb=pb->next;} } if(pa!=NULL)pc->next=pa; elsepc->next=pb; delete(Lb); return(Lc);}T(n)=O(m+n)链表合并—La,Lb有序递增，合并为Lc，仍非递减有序LN97链式存储结构小结：

（1）a1,ai+1地址可不连续；（2）不能直接存取，需先移动指针到ai；（3）插入、删除时，不需大量移动元素。以上是动态链表的基本操作，另外还有静态链表，课下自己了解，适用于BASIC语言。链式存储结构小结：以上是动态链表的基本操作，另外还有静态链表98最后一个结点的指针域的指针又指回第一个结点的链表和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。a1a2an…H(a)^H(b)单循环链表循环链表最后一个结点的指针域的指针又指回第一个结点的链表a1a2an99p=A→next;

A→next=B→next→next;B→next=p;A=B;

操作和线性链表基本一致，有时在循环链表中设立尾指针可使操作简化。见下图

…A…B…A…Bp=A→next;

A→next=B→100//-----线性表的双向链表存储结构-----typedefstructDuLNode{ElemTypedata;//数据域structDuLNode*prior;//指向前驱的指针域structDuLNode*next;//

指向后继的指针域}DuLNode,*DuLinkList;双向链表^a1a2an^head……双向链表//-----线性表的双向链表存储结构-----双向链表101ai-1aies->prior=p->prior;psai-1ai插入p->prior->next=s;s->next=p;p->prior=s;ai-1aies->prior=p->prior;102ai-1删除aiai+1p->prior->next=p->next;p->next->prior=p->prior;free(p);pai-1ai-1删除aiai+1p->prior->next=p103本章介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链表。顺序存储有三个优点：(1)方法简单，各种高级语言中都有数组，容易实现。(2)不用为表示结点间的逻辑关系而增加额外的存储开销。(3)顺序表具有按元素序号随机访问的特点。顺序表和链表的比较本章介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链104但它也有两个缺点：⑴在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。⑵需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。链表的优缺点恰好与顺序表相反。但它也有两个缺点：105⒈基于存储的考虑

对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低。⒉基于运算的考虑

如果经常做的运算是按序号访问数据元素，顺序表优于链表；在顺序表中做插入、删除操作时平均移动表中一半的元素，在链表中作插入、删除操作，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑后者优于前者。⒊基于环境的考虑

顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲