数据结构(C语言版)-胡学钢02-线性表

11数据结构

DataStructure主讲人：朱一峰通信工程系1第二章线性表

第二章线性表

2.1线性表的定义和运算

2.2顺序表

2.3链表

2.4其它结构形式的链表

2.5串

2本章要点1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。3线性结构的基本特征为:1．集合中必存在唯一的一个“第一元素”；2．集合中必存在唯一的一个“最后元素”；3．除最后元素在外，其他元素均有唯一的后继；4．除第一元素之外，其他元素均有唯一的前驱。一个数据元素的有序（次序）集线性表是一种最简单的线性结构42.1线性表的定义和运算定义：线性表L是由n个元素a1，a2，……，an组成的有限

序列。记作L=（a1，a2，……，an）其中n>=0为表长；n=0时为L空表，记作L=（）元素ai的含义(数据关系)：同一表中，元素类型相同。在不同的场合有不同的含义例：字母表（A，B，C，D，……，Z）；数字表（0，1，2，3，4，……，9）；每月天数（31,29,31,30,31,30,31,31,30,31,30,31）;{设线性表为(a1，a2,...，ai，...，an),

称i为ai

在线性表中的位序。}52.1线性表的定义和运算

基本运算：

(1)初始化

initial_List(L)建立线性表的初始结构，即建空表(2)求长度

List_length(L)即求表中的元素个数(3)按序号取元素

get_element(L,i)取出表中序号为i的元素(4)按值查找元素

List_locate(L,x)取出指定值为x的元素，若存在则返回其地址；否则返回特殊值(5)插入

List_insert(L,i,x)在表L的第i个位置上插入值为x的元素(1<=i<=n+1)(6)删除List_delete（L,i）删除表L中序号为i的元素1<=i<=n6initial_List(L)操作结果：构造一个空的线性表L。初始化操作2.1线性表的定义和运算建立线性表的初始结构，即建空表7List_length(L)

初始条件：操作结果：线性表L已存在。返回L中元素个数。求线性表的长度，即求表中的元素个数2.1线性表的定义和运算

求长度8get_element(L,i)

初始条件：

操作结果：线性表L已存在，且1≤i≤List_length(L)

。返回L中第i

个元素的值。求线性表中某个数据元素,取出表中序号为i的元素2.1线性表的定义和运算按序号取元素9List_locate(L,x)初始条件：操作结果：线性表L已存在，X为给定值，

返回L中第1个与X相等的元素的位序。若这样的元素不存在，则返回值为0。定位函数，取出指定值为x的元素，若存在则返回其地址；否则返回特殊值2.1线性表的定义和运算按值查找元素10List_insert(L,i,x)初始条件：操作结果：线性表L已存在，且1≤i≤LengthList(L)+1。在L的第i个元素之前插入新的元素e，L的长度增1。插入数据元素，在表L的第i个位置上插入值为x的元素(1<=i<=n+1)2.1线性表的定义和运算插入元素11List_delete（L,i）初始条件：操作结果：线性表L已存在且非空，

1≤i≤LengthList(L)。删除L的第i个元素，并用e返回其值，L的长度减1。删除数据元素，删除表L中序号为i的元素1<=i<=n2.1线性表的定义和运算删除元素122.1线性表的定义和运算

其他运算：

(1)删除表(2)清空表(3)遍历(4)求前驱(5)求后继(6)改变元素值13

结构销毁操作DestroyList(&L)初始条件：操作结果：线性表L已存在。销毁线性表L。2.1线性表的定义和运算

删除表14ClearList(&L)初始条件：操作结果：线性表L已存在。将L重置为空表。（线性表置空）2.1线性表的定义和运算清空表15

ListTraverse(L,visit())初始条件：操作结果：线性表L已存在，Visit()为某个访问函数。依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。（遍历线性表）遍历2.1线性表的定义和运算16

PriorElem(L,cur_e,&pre_e)初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。（求数据元素的前驱）求前驱2.1线性表的定义和运算17NextElem(L,cur_e,&next_e)初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。（求数据元素的后继）求后继2.1线性表的定义和运算18PutElem(&L,i,&e)初始条件：操作结果：线性表L已存在，且1≤i≤LengthList(L)。L中第i个元素赋值同e的值。（改变数据元素的值）2.1线性表的定义和运算改变元素值192.2顺序表存储结构：顺序表类型描述 #definemaxlen100//假设元素个数最大为100

typedef

struct{

elementtype

data[maxlen];//存储表中元素的数组

int

listlen;//表长度 }seqlist;顺序表的特点：逻辑上相邻的元素，其存储地址也相邻。20

用一组地址连续的存储单元

依次存放线性表中的数据元素

a1a2

…ai-1

ai

…an线性表的起始地址称作线性表的基地址2.2顺序表21以“存储位置相邻”表示有序对<ai-1，ai>

即：LOC(ai)=LOC(ai-1)+C

一个数据元素所占存储量↑所有数据元素的存储位置均取决于第一个数据元素的存储位置

LOC(ai)=

LOC(a1)+(i-1)×C

↑基地址2.2顺序表222.2顺序表–初始化、长度、按序号求元素、按元素找序号运算实现： voidinitial_List（seqlist*L）{L->listlen=0;}

int

List_length（seqlistL）{returnL.listlen;} voidget_element（seqlistL，inti,elementtype&x）{ if（i<1||i>L.listlen）error(“超出范围”); elsex=L.data[i-1]; }int

List_locate（seqlistL，elementtypex）{

inti; for(i=0;i<L.listlen;i++) if(L.data[i]==x)return(i+1); return(0); }23线性表操作

List_insert(L,i,x)的实现：首先分析:插入元素时，线性表的逻辑结构发生什么变化？2.2顺序表—插入24

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

(a1,…,ai-1,X,

ai,…,an)a1a2

…ai-1

ai

…ana1a2

…ai-1

…ai

Xan<ai-1,ai><ai-1,X>,

<X,

ai>表的长度增加2.2顺序表—插入252.2顺序表—插入voidList_insert（seqlist*L，elementtypex，inti）{

intj; if（L->listlen==maxlen） error（“overflow”）; elseif（i<1||i>L->listlen+1）

error(“positionerror”）; else{ for（j=L->listlen-1;j>=i-1;j--） L->data[j+1]=L->data[j]; L->data[i-1]=x;L->listlen++; }}a1a2a3ai…

an

012i-1n-1maxlen-1x条件：顺序表不满；序号正确，在[1,n+1]中操作：ai~an后移;填入x;

listlen++算法分析26考虑移动元素的平均情况:假设在第

i个元素之前插入的概率为，

则在长度为n的线性表中插入一个元素所需移动元素次数的期望值为：若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：2.2顺序表—插入27线性表操作List_delete（L,i）的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？2.2顺序表—删除28

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

(a1,…,ai-1,ai+1,…,an)ai+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的长度减少a1a2

…ai-1

ai

ai+1

…ana1a2

…ai-1

2.2顺序表—删除292.2顺序表—删除voidList_delete(seqlist*L,inti){

intj; if(L->listlen<=0)error(“下溢出错”); if(i>L->listlen||i<=0)error(“删除位置出错”); else{for(j=i;j<=L->listlen-1;j++) L->data[j-1]=L->data[j]; L->listlen--; } }a1a2a3ai…an

012i-1n-1maxlen-1算法分析30考虑移动元素的平均情况:假设删除第

i个元素的概率为

,则在长度为n的线性表中删除一个元素所需移动元素次数的期望值为：若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：2.2顺序表—删除312.2顺序表算法分析：插入时在i=1,2,…,n+1，元素移动的次数分别为n,n-1,…,0。在等概率的情况下，平均移动(n+1)n/2(n+1)=n/2次删除时在i=1,2,…,n，元素移动的次数分别为n-1,n-2,…,0。在等概率的情况下，平均移动(n-1)n/2n=(n-1)/2次结论：n较大时，大量移动元素，耗时解决：考虑不移动元素教材P17例32

用一组地址任意的存储单元存放线性表中的数据元素。单链表以元素(数据元素的映象)

+指针(指示后继元素存储位置)=结点

(表示数据元素或数据元素的映象)以“结点的序列”表示线性表

称作链表2.3链表33

以线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头指针。头结点

a1a2…...an^头指针头指针

有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。空指针线性表为空表时，头结点的指针域为空2.3链表342.3链表——基本结构以链接形式连接元素次序。a1a2a3a4^L=(a1,a2,a3,a4)结点包括元素和地址。datanext35如何从线性表得到单链表？链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。2.3链表——基本结构36例如：逆位序输入n个数据元素的值，建立带头结点的单链表。操作步骤：一、建立一个“空表”；二、输入数据元素an，建立结点并插入；三、输入数据元素an-1，

建立结点并插入；ananan-1四、依次类推，直至输入a1为止。2.3链表——基本结构37用上述定义的单链表实现线性表的操作时，存在的问题：

改进链表的设置：1．单链表的表长是一个隐含的值；

1．增加“表长”、“表尾指针”和“当前位置的指针”三个数据域；2．在单链表的最后一个元素之后插入元素时，需遍历整个链表；3．在链表中，元素的“位序”概念淡化，结点的“位置”概念加强。2．将基本操作中的“位序i”改变为“指针p”。2.3链表——基本结构382.3链表——存储实现（静态链表）1、静态链表——用数组C3A2B0D5F-1E4datanext012345L=(A,B,C,D,E,F)head392.3链表——存储实现（动态链表）2、动态链表——用指针和动态变量实现（1）结点结构datanext（2）类型定义

typedef

struct{elementtypedata;node*next;}node;

引用：node*head；402.3链表－图例a1a2a3a4^Head*HeadHead->next首元素412.3链表—基本运算

运算：

(1)初始化

initial_List(L)建立表的初始结构，即建空表(2)求长度

List_length(L)即求表中的元素个数(3)按序号取元素

get_element(L,i)取出表中序号为i的元素(4)按值查找元素

List_locate(L,x)取出指定值为x的元素，若存在则返回其地址；否则返回特殊值(5)插入

List_insert(L,i,x)在表L的第i个位置上插入值为x的元素(1<=i<=n+1)(6)删除List_delete（L,i）删除表L中序号为i的元素1<=i<=n42ai-1

线性表的操作

List_insert(L,i,x)

在单链表中的实现：

有序对<ai-1,ai>

改变为<ai-1,x>

和<x,

ai>

xaiai-12.3链表——讨论(插入操作)43因此，在单链表中第i个结点之前进行插入的基本操作为:

找到线性表中第i-1个结点，然后修改其指向后继的指针。可见，在链表中插入结点只需要修改指针。但同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。2.3链表——讨论(插入操作)442.3链表——讨论(插入操作)插入（一般位置）：假设被插入位置的前一个结点的指针P已找到，插入由S指向的结点：Pa1a2a3a4^headxS×①②①S->next=P->next;②P->next=S;注意：两个操作不能交换如果是作为第一个结点插入，过程如下：×①②①S->next=head;②head=S;a1a2a3

a4^headxS452.3链表——讨论(引入头结点)为保持插入操作一致，引入头结点。注意：头结点与首元素的区别。a1a2a3^xheadSP①S->next=P->next;②P->next=S;46线性表的操作ListDelete(&L,i,&e)在链表中的实现:有序对<ai-1,ai>和<ai,ai+1>

改变为<ai-1,ai+1>ai-1aiai+1ai-12.3链表——讨论(删除操作)47

在单链表中删除第

i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;free(q);pq2.3链表——讨论(删除操作)482.3链表——讨论(删除操作)删除（一般位置）：假设被删除的前一个结点的指针P已找到：Pa1a2a3a5^heada4

×P->next=P->next->next;如果是删除第一个结点，过程如下：head=head->next;a1a2a3a5^heada4

×讨论结果：引入头结点P->next=P->next->next;×a1a2a4^heada3

P492.3链表——运算的实现（有头结点）

1、初始化单链表（建空表）L^voidinitial_List(node&*L){ L=newnode;//L=(node*)malloc(sizeof(node)); L->next=NULL;}502.3链表——求表长（1）2、求单链表表长a1a2a3^LPlen=0P=L->next;len=0;P!=NULLreturn(len);P=P->next;len++;YNint

List_length(node*L){P=L->next;

len=0;

while(P!=NULL){P=P->next;len++;}

return(len);}512.3链表——求表长（2）2、求单链表表长a1a2a3^Lint

List_length(node*L){P=L;len=0;

while(P->next!=NULL){P=P->next;len++;}

return(len);}Plen=0P=L;len=0;P->next!=NULLreturn(len);P=P->next;len++;YN522.3链表——按序号取值3、按序号取值—返回指向结点的指针,否则返回NULLa1a2a3^LPj=0node*get(node*L,inti){P=L;j=0;

while(P->next!=NULL&&j!=i){P=P->next;j++;}

return(P);}P=L;j=0;P->next!=NULLreturn(P);P=P->next;j++;YNj==iYNreturn(P);532.3链表——按值查询

4、按值查询——返回元素结点指针，否则返回NULL；a1a2a3^LPP=L->next;P->data!=xreturn(P);P=P->next;YNP!=NULLNYreturn(P);node*locate(node*L,elementtypex){P=L->next;

while(P!=NULL&&P->data!=x)P=P->next;

return(P);}542.3链表——插入5、插入ai-1aixSP×分析：A、搜索位置；B、装入x；C、插入x；P=get(L,i-1);if(P==NULL)error(“序号错”);else{S=newnode;S->data=x;S->next=P->next;P->next=S;}voidinsert(node&*L,elementtype

x,inti){}552.3链表——删除6、删除Pai-1aiai+1

×分析：A、搜索位置；B、删除结点；C、释放结点；P=get(L,i-1);if(P==NULL)error(“序号错”);else{u=P->next;P->next=P->next->next;deleteu;//free(u);}voiddelete(node&*L,inti){}562.3链表——单链表的应用(头结点)链表的遍历：访问链表每个结点一次且仅一次。基本算法如下：voidprint(node*L){P=L->next;

while(P!=NULL){visit(P->data);P=P->next;}}a1a2a3^LP572.3链表——单链表的应用(头结点)设计算法，判断带头结点单链表L是否递增？若递增，则返回true，否则返回false。分析：（1）链表空，返回true；（2）只有一个结点，返回true；（3）每个元素都小于其直接后继，返回true；否则，返回false；例582.3链表——单链表的应用(头结点)由分析得如下流程图：P=L->next;P=P->next;P!=NULLP->next!=NULLP->data<P->next->dataYYY返回true返回trueNN返回fasleNbool

Judge(node*L){P=L->next;

if(P==NULL)return(true);

while(P->next!=NULL){if(P->data<P->next->data)P=P->next;elsereturn(false);}

return(true);}592.3链表——构造链表构造链表基本方法：从键盘输入数据，每读入一个元素，产生结点装入，插入链表中，重复上述操作X不是结束符cin>>xs=newnode;s->data=x;插入操作讨论：产生结点：s=newnode;s->data=x;插入链表：插入位置如何确定，有表头/表尾两个位置可选

头插法

尾插法重复上述操作：何时结束?a1a2a3^L602.3链表——头插法头插法运算实现：voidcreate_List(node*&L){ L=newnode;L->next=NULL;

cin>>x; while(x!=End_of_Num){ u=newnode;u->data=x; u->next=L->next; L->next=u;

cin>>x; }}a1a2an^……UxLX不是结束符cin>>xu=newnode;u->data=x;u->next=L->next;L->next=u;612.3链表——尾插法尾插法运算实现： voidcreate_List(node*&L){ L=newnode; R=L;//尾指针

cin>>x;

while(x!=End_of_Numo){ u=newnode;u->data=x; R->next=u; R=u;

cin>>x; } R->next=NULL; }a1a2an^……x^uLR622.3链表——练习题P31例2.6、2.7、2.81）链表A，B，设计算法求C＝A∩B，并分析其时间复杂度2）递增链表A，B，设计算法求C＝A∩B，并分析其时间复杂度632.4其他结构形式的链表单循环链表（优点：可在表中反复搜索）初始化操作为：

head=newnode;head->next=head;求长度：

p=head->next;n=0;while(p!=head){p=p->next;n++;}应用：

m人开m把锁问题（每人一把钥匙，要求所有锁都能开）约瑟夫环问题（利用循环队列，不带头结点的循环链表都可）a1a2an……headhead642.4其他结构形式的链表带尾指针的单循环链表（优点：表尾操作方便）

应用：将A、B两链表首尾相连

实现部分语句为：

u=A->next;1:A->next=B->next->next;2:free(B->next);3:B->next=u;4:A=B;

a1a2an……reara1a2an……a1a2an……BAu123652.4其他结构形式的链表双链表（优点：求前驱后继都方便）带头结点或者不带头结点

typedef

struct{

elementtypedata;

dnode*prior,*next;}dnode;双循环链表priordatanexta1a2an……head662.4其他结构形式的链表初始化：

head=newnode;head->prior=head->next=head;求长度查找类似插入时：

s->prior=p->prior;s->next=p;p->prior=s;s->prior->next=s;删除时：

p->prior->next=p->next;p->next->prior=p->prior;deletep;应用：判断双循环链表是否对称双循环链表倒置（动指针、动结点值）head

aiai+1xspai-1

aiai+1p672.4其他结构形式的链表小结：

线性表逻辑上相邻的元素顺序表物理上也相邻插入、删除需移动元素链表物理上不一定相邻插入、删除不需移动元素682.5串定义：串：由n个字符a1,a2,…,an组成的有限序列（n>=0）元素是字符的线性表，记作S=“a1,a2,…,an”，其中n为串长度。n=0时为空串。注意：空串和空格串的区别。 空串——没有元素。 空格串—