数据结构 课件 链表部分

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

线性表是由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线性表的类型定义二、抽象数据类型线性表的定义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顺序表示（存储）：指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。线性表顺序存储结构示意图2.2线性表的顺序表示和实现数据元素存储位置表示设a１的存储地址为Loc(a１)，每个数据元素占l个存储地址，则第i个数据元素的地址为：

Loc(ai)=Loc(a１)+(i-1)*l

，1≤i≤n逻辑上相邻的ai和ai+1以相邻的存储位置。确定起始位置后，顺序表中任一数据元素都可随机存取。顺序表是一种随机存取的存储结构。高级语言中一般用数组来描述顺序存储。#include<stdio.h>#defineMAXSIZE100typedef

int

ElemType;typedef

struct{

ElemType

a[MAXSIZE];

intlength;}Sqlist;因为线性表长度可变，且所需最大空间随问题不同而不同，所以用动态分配的一维数组(P22)。为使得算法简明扼要，暂使用静态数组。线性表的建立、输出算法初始化voidinitlist(Sqlist*L){L->length=0;}建立顺序表voidcreat_sqlist(Sqlist

&L){

int

i,n;

cout<<"n=?;

cin>>n;

L.length=n;for(i=0;i<n;i++)

cin>>L.a[i];}voidinitlist(Sqlist&L){

L.length=0;}Sqlist

Sl;initlist(&Sl);Sqlist

Sl;initlist(Sl);输出顺序表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;}

(a1,…,ai-1,ai,…,an)改变为

(a1,…,ai-1,e,ai,…,an)a1a2

…ai-1

ai

…ana1a2

…ai-1

…aiean表的长度加1插入：在线性表第i（1≤i≤n+1）个位置上插入元素e线性表主要操作的实现注意：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++; }}这里的问题规模是表的长度，设它的值为n。该算法的时间主要花费在循环的元素后移语句上，所需移动元素的次数不仅依赖于表的长度，而且还与插入位置有关。

i位置 移动次数

1 n 2 n-1 ︰ ︰ i n-i+1︰ ︰ n1 n+1 0插入操作时间复杂度分析最好情况下：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)

(a1,…,ai-1,ai,ai+1,…,an)改变为

(a1,…,ai-1,ai+1,…,an)（1≤i≤n）ai+1…an表的长度减1a1a2

…ai-1

ai

ai+1

…ana1a2

…ai-1

删除：在线性表中删除第i个元素，使ElemType

delete_sq(Sqlist&L,inti){

int

x,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; }}算法的时间复杂度分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。

i位置 移动次数

1 n-1 2 n-2︰ ︰ i n-i︰ ︰n-11n 0删除操作时间复杂度分析最好情况下：T(n)=O(1)最坏情况下：T(n)=O(n-1)平均时间复杂度：与插入运算相同，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素ai+1～an都要向上移动一个位置，共移动了n-i个元素，所以平均移动数据元素的次数：在等概率情况下，pi=1/n，则：这说明顺序表上作删除运算时大约需要移动表中一半的元素，显然该算法的时间复杂度为Ｏ(n)。

顺序表的优点：

（1）各结点存储单元物理位置上的邻接关系表示了结点间的逻辑关系，因此，无须增加额外的存储空间表示结点间的逻辑关系。（2）因其为随机存储结构，故可以随机存取表中任一结点。顺序表的缺点：（1）插入和删除不方便，通常须移动大量结点，效率较低。（2）难以进行连续的存储空间的预分配，尤其是当表变化较大时。重要结论在顺序存储表示的线性表中插入或删除一个数据元素，平均约需要移动一半的元素因此，顺序存储表示仅适用于不经常进行插入和删除操作并且表中元素相对稳定的表查找：在线性表L中查找值为e的元素，如果存在，返回位置(>0)，否则返回-1，表示未找到。int

locate_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);}合并：两表分别非递减有序(递增或等值)，合并后仍然非递减有序。voidmerge_list(Sqlista,Sqlistb,Sqlist&c){

int

i,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++;}}单链表循环链表双向链表静态链表单链表应用举例2.3线性表的链式表示与实现线性表的链式表示和实现链式分配线性表数据元素的存储单元可以不连续，存放数据元素的结点至少包括两个域（数据域、指针域），也可以包含若干个数据域、指针域。单链表：每个结点只有一个指针域链表链接的顺序和数据元素的逻辑顺序一致，结点的物理位置可任意安排头指针：存放第一个结点的存储地址（附加）头结点：在单链表第一个结点之前附设一个结点a1heada2a6^…a57a41a26a13a32a6null123456785headheada1a6^…头结点头指针头指针空表^head存储表示typedef

struct

LNode{

ElemTypedata;//数据域

struct

LNode*next;//指针域}LNode,*linklist;其中linklist等价于LNode*若设LNode*p,*q;LinkListH;则p,q,H都是指针变量,p->data表示数据域p->next表示指针域线性表的单链表函数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;用的少)指针指向结点p=qqp指针指向后继

p=q->next指针移动

p=p->nextqppp指针赋值的操作pqp->next=qp->next=q->nextpq创建链表单链表的基本运算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为全局变量voidcreate(LNode*L){ int

i,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为局部变量LNode*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为全局变量输出链表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;}取已知的线性链表的第i个元素的值，由函数名返回ElemType

GetElem(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<<"GetElem

is

"<<GetElem(head,4)<<endl;语句频度：i<1，0次1≤i≤n，i-1次i>n，n次平均为n数量级，故T(n)=O(n)在带头结点的单链表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个结点，其数据元素由函数名返回ElemType

delete_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); }}voidlistdelete_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中元素不重复）链表合并—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)链式存储结构小结：

（1）a1,ai+1地址可不连续；（2）不能直接存取，需先移动指针到ai

；（3）插入、删除时，不需大量移动元素。以上是动态链表的基本操作，另外还有静态链表，课下自己了解，适用于BASIC语言。最后一个结点的指针域的指针又指回第一个结点的链表和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。a1a2an…H

(a)^H

(b)单循环链表循环链表p=A→next;

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

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

…A…B…A…B//-----线性表的双向链表存储结构-----typedef

struct

DuLNode

{

ElemTypedata;//数据域

struct

DuLNode*prior;//指向前驱的指针域

struct

DuLNode*next;//

指向后继的指针域}DuLNode,*DuLinkList;双向链表^a1a2an^head……双向链表ai-1aies->prior=p->prior;psai-1ai插入p->prior->next=s;s->next=p;p->prior=s;ai-1删除aiai+1p->prior->next=p->next;p->next->prior=p->prior;free(p);pai-1本章介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链表。顺序存储有三个优点：

(1)方法简单，各种高级语言中都有数组，容易实现。

(2)不用为表示结点间的逻辑关系而增加额外的存储开销。

(3)顺序表具有按元素序号随机访问的特点。顺序表和链表的比较但它也有两个缺点：⑴在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。⑵需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。链表的优缺点恰好与顺序表相反。⒈基于存储的考虑

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

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

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

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

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

S(x)=1+3x10000–2x20000的多项式，上述表示方法是否合适？2.4线性表的应用__一元多项式相加

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

Pn(x)=p1xe1+p2xe2+┄+pmxem其中：pi

是指数为ei

的项的非零系数，

0≤e1<e2<…<em=n可以下列线性表表示:（（p1,e1）,(p2,e2),┄,(pm,em)）

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

((7,3),(-2,12),(-8,999))表示ADTPolynomial{…}p40可用顺序表示typedef

struct{ floatcoef;

intexp;}ElemType;typedef

struct{

ElemType

a[MAXSIZE];

intlength;}Sqlist;SqlistL;如果要访问第五项：L.a[4].coefL.a[4].exp链式表示typedef

structpoly{ floatcoef;

intexp;

structpoly*next;}poly;加法操作的实现：设有两个多项式

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

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

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

C=A+B设p和q分别指向A,B中当前进行比较的某一结点，比较结