數(shù)據(jù)結構(第2章)-清華大學

第二章線性表⒈教學內容：2.1線性表邏輯結構；

2.2線性表的順序存儲及運算實現(xiàn)；2.3線性表的鏈式存儲和實現(xiàn)。⒉教學目的：⑴理解線性表的定義及其運算；⑵理解順序表和鏈表的定義、組織形式、結構特征和類型說明；⑶掌握在這兩種表上實現(xiàn)的插入、刪除和按值查找的算法；⑷了解循環(huán)鏈表、雙(循環(huán))鏈表的結構特點和在其上施加的插入、刪除等操作。⒊教學重點：⑴線性表的定義及邏輯上的特點；⑵順序表上插入、刪除和定位運算的實現(xiàn)；⑶單鏈表的結構特點及類型說明；⑷頭指針和頭結點的作用及區(qū)別；⑸定位、刪除、插入運算在單鏈表上的實現(xiàn)；⑹循環(huán)鏈表、雙鏈表的結構特點，循環(huán)鏈表、雙鏈表上刪除與插入運算的實現(xiàn)。⒋教學難點：⑴線性表與線性結構的聯(lián)系與區(qū)別；⑵頭結點在鏈表中的作用；指針操作；⑶刪除、插入運算中的指針操作順序；⑷雙鏈表上指針的操作順序。⒌教學時數(shù)：

9學時（含習題課2學時）2/5/20231數(shù)據(jù)結構講義2.1線性表的邏輯結構線性表的定義線性表的基本操作2/5/20232數(shù)據(jù)結構講義2.1.1線性表的定義線性表是一種線性結構。線性結構的特點是數(shù)據(jù)元素之間是一種線性關系，數(shù)據(jù)元素“一個接一個的排列”。在一個線性表中數(shù)據(jù)元素的類型是相同的，或者說線性表是由同一類型的數(shù)據(jù)元素構成的線性結構。線性表是具有相同數(shù)據(jù)類型的n(n>=0)個數(shù)據(jù)元素的有限序列，通常記為：(a1，a2，…ai-1，ai，ai+1，…an)其中n為表長，n＝0時稱為空表。表中相鄰元素之間存在著順序關系。將ai-1稱為ai的直接前趨，ai+1稱為ai的直接后繼。就是說：對于ai，當i=2，...，n時，有且僅有一個直接前趨ai-1.，當i=1，2，...，n-1時，有且僅有一個直接后繼ai+1，而a1是表中第一個元素，它沒有前趨，an是最后一個元素無后繼。需要說明的是：ai為序號為i的數(shù)據(jù)元素（i=1,2,…,n），通常我們將它的數(shù)據(jù)類型抽象為datatype，datatype根據(jù)具體問題而定，如在學生情況信息表中，它是用戶自定義的學生類型；在字符串中，它是字符型；等等。2/5/20233數(shù)據(jù)結構講義2.1.2線性表的基本操作⑴線性表初始化：Init_List(L)

初始條件：表L不存在操作結果：構造一個空的線性表

⑵求線性表的長度：Length_List(L)

初始條件：表L存在操作結果：返回線性表中的所含元素的個數(shù)⑶取表元：Get_List(L,i)

初始條件：表L存在且1<=i<=Length_List(L)

操作結果：返回線性表L中的第ｉ個元素的值或地址⑷按值查找：Locate_List(L,x)，ｘ是給定的一個數(shù)據(jù)元素。初始條件：線性表L存在操作結果：返回在L中首次出現(xiàn)的值為ｘ的那個元素的序號或地址，稱為查找成功;否則，在L中未找到值為ｘ的數(shù)據(jù)元素，返回一特殊值表示查找失敗。⑸插入操作：Insert_List(L,i,x)

初始條件：線性表L存在，插入位置正確(1<=i<=n+1,ｎ為插入前的表長)。操作結果：在線性表L的第i個位置上插入一個值為x的新元素，這樣使原序號為i,i+1,...,n的數(shù)據(jù)元素的序號變?yōu)閕+1,i+2,...,n+1，插入后表長=原表長+1。⑹刪除操作：Delete_List(L,i)

初始條件：線性表L存在，1<=i<=n。

操作結果：在線性表L中刪除序號為i的數(shù)據(jù)元素，刪除后使序號為i+1,i+2,...,n的元素變?yōu)樾蛱枮閕,i+1,...,n-1，新表長＝原表長－１。需要說明的是：某數(shù)據(jù)結構上的基本運算，不是它的全部運算，而是一些常用的基本的運算，而每一個基本運算在實現(xiàn)時也可能根據(jù)不同的存儲結構派生出一系列相關的運算來。在上面各操作中定義的線性表Ｌ僅僅是一個抽象在邏輯結構層次的線性表，尚未涉及到它的存儲結構。2/5/20234數(shù)據(jù)結構講義2.2

線性表的順序存儲及運算實現(xiàn)線性表的順序存儲順序表上基本運算的實現(xiàn)順序表應用舉例2/5/20235數(shù)據(jù)結構講義2.2.1線性表的順序順序存儲線性表的順序存儲是指在內存中用地址連續(xù)的一塊存儲空間順序存放線性表的各元素，用這種存儲形式存儲的線性表稱其為順序表。設a１的存儲地址為Loc(a１)，每個數(shù)據(jù)元素占d個存儲地址，則第i個數(shù)據(jù)元素的地址為：

Loc(ai)=Loc(a１)+(i-1)*d1≤I≤n從結構性上考慮，通常將data和last封裝成一個結構作為順序表的類型：

typedefstruct

{datatypedata[MAXSIZE];

intlast;

}SeqList;

2/5/20236數(shù)據(jù)結構講義2.2.2順序表上基本運算的實現(xiàn)

⒈順序表的初始化

順序表的初始化即構造一個空表，對表是一個加工型的運算，因此，將L設為指針參數(shù)，首先動態(tài)分配存儲空間，然后，將表中l(wèi)ast指針置為－1，表示表中沒有數(shù)據(jù)元素。算法如下：

SeqList*init_SeqList(){SeqList*L;L=malloc(sizeof(SeqList));L->last=-1;

returnL;}2/5/20237數(shù)據(jù)結構講義⒉插入運算線性表的插入是指在表的第i個位置上插入一個值為x的新元素，算法如下：

intInsert_SeqList(SeqList*L，inti，datatypex){intj;if(L->last==MAXSIZE－1)

{printf(＂表滿＂);return(-1);}/*表空間已滿，不能插入*/

if(i<1||i>L->last+2)/*檢查插入位置的正確性*/{printf(＂位置錯＂);return(0);}

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

L->data[j+1]=L->data[j];/*結點移動*/

L->data[i-1]=x;/*新元素插入*/

L->last++;/*last仍指向最后元素*/

return(1);/*插入成功，返回*/}2/5/20238數(shù)據(jù)結構講義插入算法的時間性能分析順序表上的插入運算，時間主要消耗在了數(shù)據(jù)的移動上，在第i個位置上插入x，從ai到an都要向下移動一個位置，共需要移動n－i＋1個元素，而i的取值范圍為：1≤

i≤n+1，即有n＋1個位置可以插入。設在第i個位置上作插入的概率為Pi，則平均移動數(shù)據(jù)元素的次數(shù)：

設：Pi=1/(n+1)，即為等概率情況，則：這說明：在順序表上做插入操作需移動表中一半的數(shù)據(jù)元素。顯然時間復雜度為Ｏ(n)。2/5/20239數(shù)據(jù)結構講義⒊刪除運算線性表的刪除運算是指將表中第i個元素從線性表中去掉，算法如下：

intDelete_SeqList(SeqList*L;inti){intj;if(i<1||i>L->last+1)

/*檢查空表及刪除位置的合法性*/{printf(＂不存在第i個元素＂);

return(0);}for(j=i;j<=L->last;j++)L->data[j-1]=L->data[j];

/*向上移動*/

L->last--;return(1);

/*刪除成功*/}2/5/202310數(shù)據(jù)結構講義刪除算法的時間性能分析與插入運算相同，其時間主要消耗在了移動表中元素上，刪除第i個元素時，其后面的元素ai+1～an都要向上移動一個位置，共移動了n-i個元素，所以平均移動數(shù)據(jù)元素的次數(shù)：在等概率情況下，pi=1/n，則：這說明順序表上作刪除運算時大約需要移動表中一半的元素，顯然該算法的時間復雜度為Ｏ(n)。

2/5/202311數(shù)據(jù)結構講義⒋按值查找線性表中的按值查找是指在線性表中查找與給定值x相等的數(shù)據(jù)元素。算法如下：

intLocation_SeqList(SeqList*L,datatypex){

inti=0;while(i<=L.last&&L->data[i]!=x)

i++;if(i>L->last)return-1;elsereturni;

/*返回的是存儲位置*/}本算法的主要運算是比較。顯然比較的次數(shù)與x在表中的位置有關，也與表長有關。平均比較次數(shù)為（n+1）/2，時間性能為O(n)。2/5/202312數(shù)據(jù)結構講義2.2.3順序表應用舉例

例2.1將順序表(a1，a2，...，an)重新排列為以a1為界的兩部分：a1前面的值均比a1小，a1后面的值都比a1大。劃分的方法有多種，下面介紹的劃分算法其思路簡單，性能較差?；舅悸罚簭牡诙€元素開始到最后一個元素，逐一向后掃描：⑴當前數(shù)據(jù)元素aI比a1大時，表明它已經在a1的后面，不必改變它與a1之間的位置，繼續(xù)比較下一個。⑵當前結點若比a1小，說明它應該在a1的前面，此時將它上面的元素都依次向下移動一個位置，然后將它置入最上方。2/5/202313數(shù)據(jù)結構講義算法如下：

voidpart(SeqList*L){inti,j;datatypex,y;x=L->data[0];/*將基準置入x中*/

for(i=1;i<=L->last;i++)if(L->data[i]<x)/*當前元素小于基準*/{y=L->data[i];for(j=i-1;j>=0;j--)/*移動*/

L－>data[j+1]=L->data[j];L->data[0]=y;}}總的移動次數(shù)為：

即最壞情況下移動數(shù)據(jù)時間性能為Ｏ(ｎ２)。2/5/202314數(shù)據(jù)結構講義例2.2有順序表A和B，其元素均按從小到大的升序排列，編寫一個算法將它們合并成一個順序表C，要求C的元素也是從小到大的升序排列。算法思路：依次掃描通過A和B的元素，比較當前的元素的值，將較小值的元素賦給C，如此直到一個線性表掃描完畢，然后將未完的那個順序表中余下部分賦給C即可。C的容量要能夠容納A、B兩個線性表相加的長度。2/5/202315數(shù)據(jù)結構講義算法如下：voidmerge(SeqListA,SeqListB,SeqList*C){inti,j,k;i=0;j=0;k=0;while(i<=A.last&&j<=B.last)

if(A.date[i]<B.date[j])

C->data[k++]=A.data[i++];elseC->data[k++]=B.data[j++];while(i<=A.last)C->data[k++]=A.data[i++];while(j<=B.last)C->data[k++]=B.data[j++];C->last=k-1;}

算法的時間性能是O(m+n)，其中m是A的表長，n是B的表長。2/5/202316數(shù)據(jù)結構講義例2.3

比較兩個線性表的大小。兩個線性表的比較依據(jù)下列方法：設A、B是兩個線性表，均用向量表示，表長分別為m和n。A’和B’分別為A和B中除去最大共同前綴后的子表。例如A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，兩表最大共同前綴為(x,y,y,z)。則A’=（x,z），B’=（y,x,x,z），若A’=B’=空表，則A=B；若A’=空表且B’≠空表，或兩者均不空且A’首元素小于B’首元素，則A<B；否則，A>B。

算法思路：首先找出A、B的最大共同前綴；然后求出A’和B’，之后在按比較規(guī)則進行比較，A>B函數(shù)返回1；A=B返回0；A<B返回-1。2/5/202317數(shù)據(jù)結構講義算法如下：intcompare(A,B,m,n)intA[],B[];intm,n;{inti=0,j,AS[],BS[],ms=0,ns=0;

/*AS,BS作為A’,B’*/while(A[i]==B[i])i++;/*找最大共同前綴*/

for(j=i;j<m;j++){AS[j-i]=A[j];ms++;}

/*求A’,ms為A’的長度*/

for(j=i;j<n;j++){BS[j-i]=B[j];ns++;}/*求B‘,ms為B’的長度*/

if(ms==ns&&ms==0)return0;elseif(ms==0&&ns>0||ms>0&&ns>0&&AS[0]<BS[0])return–1;elsereturn1;}算法的時間性能是O(m+n)。2/5/202318數(shù)據(jù)結構講義2.3線性表的鏈式存儲和運算實現(xiàn)單鏈表循環(huán)鏈表雙向鏈表靜態(tài)鏈表單鏈表應用舉例2/5/202319數(shù)據(jù)結構講義2.3.1單鏈表鏈表是通過一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素的，對每個數(shù)據(jù)元素ai，除了存放數(shù)據(jù)元素的自身的信息ai之外，還需要和ai一起存放其后繼ai+1所在的存貯單元的地址，這兩部分信息組成一個“結點”。存放數(shù)據(jù)元素信息的稱為數(shù)據(jù)域，存放其后繼地址的稱為指針域。鏈表是由一個個結點構成的，結點定義如下：typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

定義頭指針變量：LinkListH；

Data

next單鏈表結點結構2/5/202320數(shù)據(jù)結構講義2.3.2單鏈表上基本運算的實現(xiàn)⒈建立單鏈表在鏈表的頭部插入結點建立單鏈表算法如下：LinkListCreat_LinkList1(){LinkListL=NULL；/*空表*/

Lnode*s;intx;

/*設數(shù)據(jù)元素的類型為int*/

scanf(＂%d＂,&x);while(x!=flag){s=malloc(sizeof(LNode));s->data=x;s->next=L;L=s;scanf(＂%d＂,&x);}returnL;}2/5/202321數(shù)據(jù)結構講義在單鏈表的尾部插入結點建立單鏈表算法如下：LinkListCreat_LinkList2(){LinkListL=NULL;Lnode*s,*r=NULL;intx;

/*設數(shù)據(jù)元素的類型為int*/

scanf(＂%d＂,&x);while(x!=flag){s=malloc(sizeof(LNode));s->data=x;if(L==NULL)L=s;

/*第一個結點的處理*/

elser->next=s;

/*其它結點的處理*/

r=s;

/*r指向新的尾結點*/

scanf(＂%d＂,&x);}if(r!=NULL)r->next=NULL;

/*對于非空表，最后結點的指針域放空指針*/

returnL;}2/5/202322數(shù)據(jù)結構講義⒉求表長設L是帶頭結點的單鏈表(線性表的長度不包括頭結點)。

算法如下：intLength_LinkList1(LinkListL){Lnode*p=L;

/*p指向頭結點*/

intj=0;while(p->next)

{p=p->next;j++}

/*p所指的是第j個結點*/

returnj;}2/5/202323數(shù)據(jù)結構講義設L是不帶頭結點的單鏈表。算法如下：intLength_LinkList2(LinkListL){Lnode*p=L;

intj;

if(p==NULL)return0;/*空表的情況*/

j=1;

/*在非空表的情況下，p所指的是第一個結點*/;

while(p->next){p=p->next;j++}returnj;}2/5/202324數(shù)據(jù)結構講義⒊查找操作按序號查找Get_Linklist(L,i)算法如下：Lnode*Get_LinkList(LinkListL,Inti);/*在單鏈表L中查找第i個元素結點，找到返回其指針，否則返回空*/{Lnode*p=L;intj=0;while(p->next!=NULL&&j<i)

{p=p->next;j++;}if(j==i)returnp;elsereturnNULL;}2/5/202325數(shù)據(jù)結構講義按值查找即定位Locate_LinkList(L,x)算法如下：Lnode*Locate_LinkList(LinkListL,datatypex)

/*在單鏈表L中查找值為x的結點，找到后返回其指針，否則返回空*/{Lnode*p=L->next;while(p!=NULL&&p->data!=x)

p=p->next;returnp;}2/5/202326數(shù)據(jù)結構講義⒋插入操作

后插結點：設p指向單鏈表中某結點，s指向待插入的值為x的新結點，將*s插入到*p的后面。操作如下：①s->next=p->next;②p->next=s;注意：兩個指針的操作順序不能交換。2/5/202327數(shù)據(jù)結構講義

前插結點：設ｐ指向鏈表中某結點，ｓ指向待插入的值為x的新結點，將*s插入到*p的前面。與后插不同的是：首先要找到*p的前驅*q，然后再完成在*q之后插入*s，設單鏈表頭指針為L，操作如下：q=L;while(q->next!=p)q=q->next;/*找*p的直接前驅*/s->next=q->next;q->next=s;2/5/202328數(shù)據(jù)結構講義

插入運算Insert_LinkList(L,i,x)算法思路：1.找到第i-1個結點；若存在繼續(xù)2，否則結束2.申請、填裝新結點；3.將新結點插入。結束。算法如下：intInsert_LinkList(LinkListL,inti,datatypex)

/*在單鏈表L的第i個位置上插入值為x的元素*/{Lnode*p,*s;p=Get_LinkList(L,i-1);

/*查找第i-1個結點*/

if(p==NULL){printf(”參數(shù)i錯”);return0;}

/*第i-1個不存在不能插入*/

else{s=malloc(sizeof(LNode));/*申請、填裝結點*/

s->data=x;s->next=p->next;/*新結點插入在第i-1個結點的后面*/

p->next=sreturn1;}2/5/202329數(shù)據(jù)結構講義⒌刪除操作設p指向單鏈表中某結點，刪除*p。要實現(xiàn)對結點*p的刪除，首先要找到*p的前驅結點*q，然后完成指針的操作即可。指針的操作由下列語句實現(xiàn)：

q->next=p->next;free(p);顯然找*p前驅的時間復雜性為O(n)。

若要刪除*p的后繼結點(假設存在)，則可以直接完成：

s=p->next;p->next=s->next;free(s);該操作的時間復雜性為O(1)。2/5/202330數(shù)據(jù)結構講義刪除運算：Del_LinkList(L,i)算法思路：1.找到第i-1個結點；若存在繼續(xù)2，否則結束；2.若存在第i個結點則繼續(xù)3，否則結束；3.刪除第i個結點，結束。intDel_LinkList(LinkListL，inti)

/*刪除單鏈表L上的第i個數(shù)據(jù)結點*/{LinkListp,s;p=Get_LinkList(L,i-1);/*查找第i-1個結點*/

if(p==NULL)

{printf(＂第i-1個結點不存在＂);return-1;}else{if(p->next==NULL)

{printf(＂第i個結點不存在＂);return0;}else{s=p->next;

/*s指向第i個結點*/

p->next=s->next;/*從鏈表中刪除*/

free(s);/*釋放*s*/return1;}}2/5/202331數(shù)據(jù)結構講義2.3.3循環(huán)鏈表對于單鏈表而言，最后一個結點的指針域是空指針，如果將該鏈表頭指針置入該指針域，則使得鏈表頭尾結點相連，就構成了單循環(huán)鏈表。在單循環(huán)鏈表上的操作基本上與非循環(huán)鏈表相同，只是將原來判斷指針是否為NULL變?yōu)槭欠袷穷^指針而已，沒有其它較大的變化。對于單循環(huán)鏈表則可以從表中任意結點開始遍歷整個鏈表；另外，有時對鏈表常做的操作是在表尾、表頭進行，此時可以改變一下鏈表的標識方法，不用頭指針而用一個指向尾結點的指針R來標識，可以使得操作效率提高。2/5/202332數(shù)據(jù)結構講義例：對兩個單循環(huán)鏈表H1、H2的連接操作，是將H2的第一個數(shù)據(jù)結點接到H1的尾結點，如用頭指針標識，則需要找到第一個鏈表的尾結點，其時間復雜性為O(n)，而鏈表若用尾指針R、R2來標識，則時間性能為O(1)。操作如下：P=R–>next;

/*保存第一個表的頭結點指針*/R->next=R2->next->next;

/*頭尾連接*/free(R2->next);

/*釋放第二個表的頭結點*/R2->next=P;/*組成循環(huán)鏈表*/2/5/202333數(shù)據(jù)結構講義2.3.4雙向鏈表單鏈表的結點中只有一個指向其后繼結點的指針域next，找后繼的時間性能是O(1)，找前驅的時間性能是O(n)；可以付出空間的代價使得找前驅的時間性達到O(1)：每個結點再加一個指向前驅的指針域。用這種結點組成的鏈表稱為雙向鏈表。雙向鏈表結點的定義如下：typedefstructdlnode{datatypedata;structdlnode*prior,*next;}DLNode,*DLinkList;2/5/202334數(shù)據(jù)結構講義

和單鏈表類似，雙向鏈表通常也是用頭指針標識，也可以帶頭結點和做成循環(huán)結構。通過某結點的指針p即可以直接得到它的后繼結點的指針p->next，也可以直接得到它的前驅結點的的指針p->prior。這樣在有些操作中需要找前驅時，則勿需再用循環(huán)。

p->prior->next==p==p->next->prior2/5/202335數(shù)據(jù)結構講義

在雙向鏈表中插入一個結點：設p指向雙向鏈表中某結點，s指向待插入的值為x的新結點，將*s插入到*p的前面。操作如下：①s->prior=p->prior;②p->prior->next=s;③s->next=p;④p->prior=s;

上面指針操作的順序不是唯一的，但也不是任意的，操作①必須要放到操作④的前面完成，否則*p的前驅結點的指針就丟掉了。2/5/202336數(shù)據(jù)結構講義在雙向鏈表中刪除指定結點：設p指向雙向鏈表中某結點，刪除*p。操作如下：①p->prior->next=p->next;②p->next->prior=p->prior;③free(p);

2/5/202337數(shù)據(jù)結構講義2.3.5靜態(tài)鏈表首先看一個例子：規(guī)模較大的結構數(shù)組sd[MAXSIZE]中有兩個鏈表：其中鏈表SL是一個帶頭結點的單鏈表，表示了線性表(a1,a2,a3,a4,a5)，而另一個單鏈表AV是將當前sd中的空結點組成的鏈表。數(shù)組sd的定義如下：#defineMAXSIZE…/*足夠大的數(shù)*/

typedefstruct

{datatypedata;intnext;}SNode;/*結點類型*/

SNodesd[MAXSIZE];

intSL,AV;/*兩個頭指針變量*/

2/5/202338數(shù)據(jù)結構講義

在例子中，SL是用戶的線性表，AV模擬的是系統(tǒng)存儲池中空閑結點組成的鏈表，當用戶需要結點時，例如向線性表中插入一個元素，需自己向AV申請，而不能用系統(tǒng)函數(shù)malloc來申請，相關的語句為：

if(AV!=-1){t=AV;

AV=sd[AV].next;}；所得到的結點地址(下標)存入了t中；不難看出當AV表非空時，摘下了第一個結點給用戶。當用戶不再需要某個結點時，需通過該結點的相對地址t將它還給AV，相關語句為：sd[t].next=AV;AV=t;交給AV表的結點鏈在了AV的頭部。2/5/202339數(shù)據(jù)結構講義例

在帶頭結點的靜態(tài)鏈表SL的第i個結點之前插入一個值為x的新結點。設靜態(tài)鏈表的存儲區(qū)域sd為全局變量。

intInsert_SList(intSL,datatypex,inti){intp=SL,j=0;while(sd[p].next!=-1&&j<i-1){p=sd[p].next;j++;}

/*找第i-1個結點*/

if(j==i-1)

if(AV!=-1)/*若AV表還有結點可用*/{t=AV;AV=sd[AV].next;sd[t].data=x;/*申請、填裝新結點*/

sd[t].next=sd[p].next;

/*插入*/

sd[p].next=t;return1;}/*正常插入成功返回*/

else{printf(”存儲池無結點”);return0;}

/*未申請到結點，插入失敗*/

else{printf(”插入的位置錯誤”);return-1;}

/*插入位置不正確，插入失敗*/}2/5/202340數(shù)據(jù)結構講義2.3.6單鏈表應用舉例例1

已知單鏈表H，寫一算法將其倒置。算法如下：voidreverse(LinklistH){LNode*p;p=H->next;/*p指向第一個數(shù)據(jù)結點*/

H->next=NULL;

/*將原鏈表置為空表H*/

while(p){q=p;p=p->next;q->next=H->next;/*將當前結點插到頭結點的后面*/

H->next=q;}}2/5/202341數(shù)據(jù)結構講義例2

已知單鏈表L，寫一算法，刪除其重復結點。voidpur_LinkList(LinkListH){LNode*p,*q,*r;p=H->next;