《数据结构与算法分析》课件第2章-线性表

第二章线性表线性表是程序设计中最常遇到的一种操作对象，也是数据结构中最简单、最重要的结构形式之一。线性表的概念及运算顺序表及基本运算的实现链表及基本运算的实现应用实例一个线性表是n（表长）个数据元素的有限序列，记为：

(a1,a2,a3…,an)线性表可描述为：Liner-list=(D,R)，

其中：

D={ai|ai∈dataobject,1≤i≤n,n≥0}R={<ai-1,ai>|ai-1,ai∈D,2≤i≤n}线性表的基本概念

线性表的定义【例1】

英文字母表（A,B,C,…..,Z)是一个线性表。【例2】数据元素

线性表的逻辑特点对于非空的线性表(a1,a2,a3…,an)，有且仅有一个开始结点a1，有且仅有一个终端结点an

当i=1,2,…n-1时，ai有且仅有一个直接后继ai+1

当i=2,…n时，ai有且仅有一个直接前趋ai-1线性表的基本概念线性表的抽象数据类型

ADTLinearlist

{

数据对象D：D={ai|ai∈dataobject,1≤i≤n,n≥0}

数据关系R：R={<ai,ai-1>|ai-1,ai∈D,2≤i≤n}

操作集合：CreatList(&L)构造空表Length(L)求表长Get(L,i)取结点Locate(L,x)定位Insert(L,x,i)插入Delete(L,i)删除Prior(L,ai)取直接前趋Next(L,ai)取直接后继}线性表的基本概念线性表的运算①CreatList(&L)构造空表②Length(L)求表长③Get(L,i)取结点⑦Prior(L,ai)取直接前趋④Locate(L,x)定位⑤Insert(L,x,i)插入⑥Delete(L,i)删除更复杂的运算可利用以上基本运算实现⑧Next(L,ai)取直接后继线性表的基本概念【例3】利用线性表的基本运算清除表L中多余的重复结点。voidPurge(Linear_list

L){

//删除Ｌ中重复出现的多余结点

inti=1,j,x,y;

while(i<Length(L)){

x=Get(L,i);//取当前第i个结点

j=i+1;

while(j<=Length(L)){

y=Get(L,j);//取当前第j个结点

if(x==y)Delete(L,j);//

删除当前第j个结点

elsej++;

}

i++;

}

}

线性表的基本概念顺序表用一组地址连续的存储单元依次存储线性表的元素。元素地址的计算Loc(ai)=Loc(a1)+(i-1)*LLoc(ai+1)=Loc(ai)+La1a2an01n-112n内存a数组下标元素序号M-1…......备用空间其中：L—元素占用的存储单元个数LOC(ai)—表中第i个元素的起始地址线性表的顺序存储结构顺序表的类型描述a1a2an01n-112n内存a数组下标元素序号M-1…......备用空间【例】

typedefstructstu

{

intnum;

charname[20];

floatscore;}datatype;#defineM1000datatypedata[M];typedefintdatatype;#defineM1000datatypedata[M];线性表的顺序存储结构data[MAX]lastL向量中最后元素的位置顺序表的类型描述线性表的顺序存储结构

typedefintdatatype;#defineMAX100typedefstruct

{

datatypedata[MAX];intlast;

}sequenlist;

sequenlist*L;也可定义成：顺序存储结构的特点顺序表是用向量实现的线性表；以元素在计算机内物理位置的紧邻来表示元素之间的逻辑关系。顺序存储结构是随机存取结构；线性表的顺序存储结构顺序表的运算——插入若在顺序表的第i（1

i

n+1）个位置插入一个新的数据元素x，则：实现：将第i

至第

n

共（n-i+1）个元素后移，并将x放置插入位置。(a1,…,ai-1,x,ai,

…,an)

(a1,…,ai-1,ai,

…,an)x内存a1a2aiai+1an01i-1下标n-1i12i元素序号i+1n..................内存a1a2aian01i-1下标n-1i12i元素序号i+1n............an-1n+1n......顺序表的运算——插入intInsert(sequenlist

L,intx,inti){

intj;

if((L->last)==maxsize

1)

{

//

表空间溢出

printf("overflow");

return(0);

}

else

if((i<1)||(i>(L->last+2)

{//

非法位置

printf("error");

return(0);

}

else

{

for(j=L->last;j>=i

1;j

)

L->data[j+1]=L->data[j];//

结点后移

L->data[i

1]=x;//插入x，存在L->data[i

1]中

L->last=L->last+1;//

终端结点下标加1

}

return1;

}顺序表的运算——插入若删除顺序表的第i（1

i

n）个位置的数据元素，则：实现：将第n

至第

i+1

共（n-i）个元素前移。(a1,…,ai-1,ai+1,

…,an)

(a1,…,ai-1,ai,

…,an)顺序表的运算——删除内存a1a2ai+101i-1a数组下标n-212i元素序号n-1............an......内存a1a2aiai+1an01i-1a数组下标n-1i12i元素序号i+1n..................顺序表的运算——删除intDelete(sequenlist

L,inti){

intj;

if((i<1)||(i>L->last+1)){//非法位置

print("error");

return0

;}

else{

for(j=i;j<=L->last;j++)//第i个结点下标值是i

1

L->data[j

1]=L->data[j];//结点前移

L->last

;//表长减1

}

return1;

}顺序表的运算——删除插入运算设pi是在第i个位置上插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动元素的平均次数为：期望值：离散型随机变量的一切可能的取值xi与对应的概率之积的和。即随机变量的平均取值。顺序表的运算——算法分析设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动元素的平均次数为：

删除运算顺序表的运算——算法分析

结论在顺序表上进行或删除运算时，均需移动表中约一半的元素。若表长为n，则两个算法的时间复杂度为O(n)。因此，当表长n较大时，算法的效率较低。顺序表的运算——算法分析线性表的链式存储结构

顺序存储结构的优点逻辑相邻，物理相邻；存储空间使用紧凑。顺序存储结构是随机存取结构，可随机存取任一元素，存储位置可用简单、直观公式表示；

顺序存储结构的缺点插入、删除操作需要移动大量的元素；预先分配空间需按最大空间分配，空间利用不充分；表的容量难以扩充。线性表的链式存储结构链式存储结点结构用一组任意的存储单元存储线性表的数据元素利用指针体现元素之间的逻辑关系每个ai除存储本身信息外，还需存储其直接后继地址信息数据域：元素本身信息指针域：指示直接后继的存储位置数据域指针域【例4】

线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)。LIQIANSUNWANGWUZHAOZHENGZHOU存储地址17131925313743链式存储无法表达元素间的逻辑关系ZHAOQIANSUNLIZHOUWUZHENGWANG顺序存储01i-16......存储地址线性表的链式存储结构头指针31HLIQIANSUNWANGWUZHAOZHENGZHOU存储地址17131925313743数据域指针域431371913NULL725ZHAOQIANSUNLIZHOUWUZHENGWANG∧H【例4】

线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)。线性表的链式存储结构结点中只含一个指针域的链表叫单链表。结点空间的分配与释放分配结点空间p=(linklist*)

malloc(sizeof(linklist))

;系统回收结点空间free(p);单链表特点非随机存取头指针唯一确定单链表typedefstructnode

{

datatypedata;structnode*next;}

linklist;linklist*head,*p;类型描述单链表从一个空表开始，重复读入数据，生成新结点，将数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直至数据输入结束。【例5】

建立单链表存放(a,b,c,d,e)。①s=(linklist*)malloc(sizeof(linklist));abheadd②s->data=‘d’;③s->next=head;④head=s;单链表的建立——头插法linklist

CreateListF(){

charch;

linklist

head,

s;

head=NULL;//

链表开始为空

ch=getchar();//

读入第一个结点的值

while(ch!='$'){

//

'$'为结束标志

s=(linklist

)malloc(sizeof(linlist));

s→data=ch;

s→next=head;

head=s;//将新结点插入到表头上

ch=getchar();//读入下一个结点的值

}

returnhead;//返回链表头指针}abheadsd单链表的建立——头插法【例6】

建立单链表存放(a,b,c,d,e)。ahead①s=(linklist*)malloc(sizeof(linklist));②s->data='c';③r->next=s;将新结点插入到当前链表的表尾上。为此必须增加一个尾指针r，使其始终指向当前链表的表尾。brc④r=s;单链表的建立——尾插法linkist

CreatListR(){

charch;

linklist

head,

s,

r;

head=NULL;r=head;//头指针、尾指针初值为空

ch=getchar();

while(ch!='$'){//'$'为输入结束符

s=(linklist

)malloc(sizeof(linklist));

s→data=ch;

if(head==NULL)head=s;

//新结点插入空表elser->next=s;

//

非空表，新结点插入表尾

r=s;

//尾指针r指向新的表尾

ch=getchar();

//读入下一个结点的值

}

if(r!=NULL)

r→next=NULL;

returnhead;

//返回表头指针}单链表的建立——尾插法分析上述算法必须对第一个位置上的插入操作进行特殊处理。改进：在开始结点之前附加一个头结点。头结点

head

…

∧非空表

head空表

∧单链表的建立——尾插法带头结点链表的优点（1）开始结点和其它结点处理一致；（2）空表和非空表的处理一致。linkist

CreatListR(){

charch;

linklist

head,

s,

r;

head=(linklist

)malloc(sizeof(linklist));

//

生成头结点

r=head;//尾指针指向头结点

ch=getchar();

while(ch!='$'){//

'$'为输入结束符

s=(linklist

)malloc(sizeof(linklist));

s→data=ch;

r→next=s;

//

新结点插入表尾

r=s;

//尾指针r指向新的表尾

ch=getchar();//

读入下一个结点的值

}

r→next=NULL;

returnhead;

//返回表头指针}单链表的建立——尾插法【例7】

查找单链表head中的第3个结点。①p=head;i=0;

//

i为计数器②while((i!=3)&&(p->next!=NULL)){p=p->next;i++;}ppp返回地址p

d∧cbaheadp单链表的查找——按序号//带头结点的单链表

linklist

Get(linklist

head,inti)

{

intj;

linklinst

p;

p=head;j=0;//从头结点开始扫描

while((p→next!=NULL)&&(j<i)

{

p=p→next;

//

扫描下一个结点

j++;//

已扫描结点计数器

}

if(j==i)

//找到了第i个结点

returnp;

else

returnNULL;//

i>n，找不到}

单链表的查找——按序号【例8】

查找单链表head中值为'c'的结点。①p=head;②while((p->data!='c')&&(p->next!=NULL))p=p->next;ppp返回地址p

d∧cbaheadp单链表的查找——按序号//带头结点的单链表linklinst

Locate(linklinst

head,datatypekey)

{

linklist

p;

p=head→next;

//从开始结点比较

while(p!=NULL)

if(p→data!=key)

p=p→next;//没找到，继续循环

else

break;//找到结点key，退出循环

returnp;//若p!=NULL，则找到结点}

单链表的查找——按值查pxs……③④②s->data=x;③s->next=p->next;④p->next=s;①s=(linklist*)malloc(sizeof(linklist));①②将结点*s插入到结点*p之后注意第③步和第④的次序单链表的插入

单链表的查找——按值查voidInsertAfter(linklist

p,datatypex){

linklist

s;

s=(linklist

)malloc(sizeof(linkist));s→data=x;

s→next=p→next;p→next=s;//

将*s插入*p之后

}算法评价：T(n)=O(1)算法：

单链表的查找——按值查voidInsertAfter(linklist

p,datatypex){

linklist

s;

s=(linklist

)malloc(sizeof(linkist));s→data=x;

s→next=p→next;p→next=s;//

将*s插入*p之后

}算法评价：T(n)=O(1)算法：

单链表的插入将结点*s插入到结点*p之前pxs……③⑤②s->data=x;③q=head;

whiel(q->next!=p)q=q->next;④q->next=s;①s=(linklist*)malloc(sizeof(linklist));①②q④⑤s->next=p;

单链表的插入算法：//

带头结点的单链表

voidInsertBefore(linkist

head,linkist

p,intx)

{

linklis

s,

q;

s=(linklist

)malloc(sizeof(linklist));

s→data=x;

q=head;//从头指针开始

while(q→next!=p)//查找

p的前趋结点

q

q=q→next;

s→next=p;

q→next=s;//将新结点

s插入

p之前

}(1)算法评价：T(n)=O(n)(3)如何修改算法，改进时间性能为：

T(n)=O(1)(2)若表无头结点，则*p是开始结点时，需特殊处理。…headp

单链表的插入改进算法：//算法T(n)=O(1)

voidInsertBefore(linkist

head,linkist

p,intx)

{

linklis

s,

q;

datatypet;

s=(linklist

)malloc(sizeof(linklist));

s→data=x;

s->next=p->next;

p->next=s;

//将*s插入到*p之后

t=s->data;//

交换数据

s->data=p->data;

p->data=t;

}

单链表的插入【例9】

在单链表上实现线性表的插入运算Insert(L,x,i)。…headpii-1voidInsert(linklist

L,datatypex,inti)

{

linklist

p;

intj;if((i<1)||(i>n)){printf(“error”);return(0);}

j=i

1;

p=GET(L,j);

//

找第i

1个结点

p

InsertAfter(p,x);

//将新结点插到

p之后}

单链表的删除删除结点*pp……②q->next=p->next;③free(p);①q=head;

whiel(q->next!=p)q=q->next;①q②③

存储池

单链表的删除算法：

void

Delete(linklist

p,linklist

head){

linklist

q;

q=head;

while(q→next!=p)//查找*p的前趋结点

q=q→next;

q→next=p→next;//删除结点

p

free(p);

//释放结点

p

}

单链表的删除【例10】

在单链表上实现线性表的删除运算Delete(L,i)。voidDelete(linklist

L,inti)

{

linklist

p,

r;intj;

j=i

1;

p=GET(L,j);//找第i

1个结点

if((p!=NULL)&&(p→next!=NULL)

{

r=p→next;//

*r为结点

p的后继

p→next=r→next;//

将结点*r从链表上摘下

free(r);//

释放结点*r

}

else//

i<1或i>n

printf(“error”)

}算法评价：T(n)=O(n)…headpir

单链表的运算【例11】将两个递增单链表合并为一个递增单链表(不另辟空间)。将lb中的结点依此插入到la中。分析：la1510∧lb241112∧p（1）if(p→data≤q→data)

{

r=p;

p=p→next;

}（2）if(p→data＞q→data){

u=q->next;

r→next=q;q→next=p;r=q;q=u;

}ulb241112∧rq

单链表的运算linklist*Union(linklist*la,linklist*lb){linklist*p,*q,*r,*u;p=la->next;q=lb->next;r=la;

while(p!=NULL)&&(q!=NULL){if(p→data≤q→data){r=p;p=p→next;}else{

u=q->next;r→next=q;

q→next=p;r=q;q=u;

}

}if(q!=NULL)r→next=q;returnla;}

算法：head空表head

非空表表中最后一个结点的指针指向头结点，使链表构成环状

特点：从表中任一结点出发均可找到表中其他结点，提高查找效率，方便操作。

操作与单链表基本一致，循环条件不同

单链表

p==NULL或

p->next==NULL

循环链表p==head或

p->next==head

循环链表【例12】

在循环链表的第i个元素之后插入元素x。voidInsert(linklist

head,datatypex,inti)

{

linklist

s;

intj;

p=head;j=0;

while((p→next!=head)&&(j<i))

{

p=p→next;j++;

}

if(i==j)

{

s=(

linklist)malloc(sizeof(linklist));

s→data=x;

//生成值为x的新结点

s→next=p→next;p→next=s;

//插入操作

}

elseprintf(“error”);}

循环链表L空双向循环链表非空双向循环链表LAB克服了单链表的单向性的缺点，便于操作。特点

双向链表typedefstructnode

{datatypedata;structnode*prior,*next;}dlinklist*head;类型描述L空双向循环链表bcapp->prior->next=p=p->next->proir

双向链表克服了单链表的单向性的缺点，便于操作。特点typedefstructnode

{datatypedata;structnode*prior,*next;}dlinklist*head;类型描述双向链表bcap②p->next->prior=p->prior;①p->prior->next=p->next;③free(p)voidDeleteNodeP(dlinklist*p)

{

p->prior->next=p->next;

p->next->prior=p->prior;

free(p);}算法：算法评价：T(n)=O(1)双向链表算法：baps①x②③④⑤⑥voidDINSERTBEFORE(dlinklist*p,dadatypex)

{

dlinklist*s;

s=(dlinklist*)malloc(sizeof(dlinklist));

s->data=x;s->prior=p->prior;

s->next=p;

p->prior->next=s;

p->prior=s;}算法评价：T(n)=O(1)应用实例——学生学籍信息管理问题要求实现学生信息的录入、查找、插入和删除等。数据结构