第二章線性表

1、主講人 陳玉華2022-3-3線性表定義： 線性表是由n(n0)個類型相同數(shù)據(jù)元素組成的有限序列，記作： (a1 ,a2 ,ai-1 ,ai ,ai+1 ,an )。首元尾元元素ai的前驅(qū)元素ai的后繼2022-3-3ADT LinearList 數(shù)據(jù)元素：D=ai|aiD0,i=1,2,n,n0,D0是某數(shù)據(jù)類型 結(jié)構(gòu)關(guān)系：R=|ai,ai+1D0，i=1,2,n 基本操作： 表的初始化 求表長 求表中第i個元素的值 插入元素 刪除元素 元素的查找（定位） 表的清空 表的判空ADT LinearList； 2022-3-3線性表的順序存儲： 用一組地址連續(xù)的存儲單元依次存儲線性表中的各個元素

2、，使得線性表中在邏輯上相鄰的數(shù)據(jù)元素存儲在連續(xù)的物理存儲單元中，即邏輯上相鄰的元素，其存儲位置也相鄰。2022-3-32022-3-3a1a2.ai.anai+1邏輯地址12.ii+1.n存儲地址Loc10001000+c.1000+(i-1)*c1000+i*c.1000+(n-1)*c空閑#define MAXSIZE 100typedef 已經(jīng)定義過的類型 ElemType；typedef struct ElemType elemMAXSIZE; int last;SeqList;2022-3-3 int int2022-3-3該運算的目的是建立一張空的順序表L。void InitSeq

3、List(SeqList void InitSeqList(SeqList * *L)L) 如何表示如何表示L L是一張空表？是一張空表？ 2022-3-3這個過程很重要！L-last=-1;該運算的目的是在順序表L的位置i插入某個元素e。插入成功返回1，否則返回0。int InsertSeqList(SeqList int InsertSeqList(SeqList * *L , int i , ElemType e)L , int i , ElemType e) 判滿判滿：首先判定表L是否還可以插入元素，如果不可以， 則返回0，否則進行插入操作。 插入插入： 將插入位置騰空 將要插入的元素

4、放置在插入位置上 表中的標(biāo)識表尾元素位置改變返回 12022-3-3不難看出，順序表的插入運算所花費時間不總是一樣的，在表尾插入一個元素和在表頭插入一個元素所花費的時間就不同。平均移動次數(shù)2022-3-3nniinsnkninninE1k1n1i11i211) 1(11) 1(P在順序表中查找一個元素，分為兩種情況：1）按序號查找：查找順序表L中的第i個位置上的元素2）按內(nèi)容查找：查找順序表中與給定值e相等的元素2022-3-3該函數(shù)的目的是查找順序表L中的第i個元素，如果該元素存在，則返回該元素，否則，返回一個表中不可能存在的數(shù)。ElemType GetData（SeqList L , in

5、t i) ElemType e=初始值； 如果表中的第i個元素存在，則更新e的值，并返回e； 如果表中的第i個元素的值不存在，則直接返回e2022-3-3在順序表L中去查找元素e，如果e在L中出現(xiàn)，則返回該元素在表中的位置，否則，返回0.int Locate(SeqList L , ElemType e) 從表的首元開始依次與e進行比較，如果相等，則查找成功結(jié)束，返回該元素在表中的序號； 如果e與表中的所有元素都不想等，則查找失敗，返回02022-3-3該運算的目的是刪除表中的第i個元素，如果刪除失敗，則返回0；如果刪除成功，則帶回被刪除的元素，并且返回1。 該算法實現(xiàn)中要注意的一個問題是，刪

6、除一個元素后，剩余的元素在存儲的時候仍然保證邏輯上相鄰的兩個元素存儲也是相鄰的。2022-3-3int DelSeqList( SeqList *L , int i , ElemType *e) 判斷表是否是空？如果空，則返回0 判斷被刪除的元素是否存在？若該元素不存在則返回0刪除： 獲取被刪除元素 采用元素覆蓋方式實現(xiàn)刪除 更改表尾元素位置返回1 2022-3-3與插入算法類似，我們對刪除算法的時間分析也是去計算平均移動次數(shù)平均移動次數(shù)2022-3-3nininkinkninninQ1110del211)(1)(E如果一個線性表中的數(shù)據(jù)元素是有序的序列，則稱該線性表為有序表。順序存儲的有序表

7、稱為有序順序表。兩個有有序表的合并算法中對兩個同順序（同是遞增順序，或者同是遞減順序）的有序表進行合并操作，要求合并之后的新表仍然是同順序的有序表。2022-3-32022-3-322 31 3 3 4ijk0 1 2 0 1 2 3 0 1 2 3 4 5 6 122 33 34void MergeList(SeqList void MergeList(SeqList * *LA, SeqList LA, SeqList * *LB, SeqList LB, SeqList * *Lc)Lc) int i , j, k ; int i , j, k ; /三個標(biāo)志變量三個標(biāo)志變量 i=j=k

8、=0; i=j=k=0; /標(biāo)志量初始值標(biāo)志量初始值 while(ilast & jlast) while(ilast & jlast) if(LA-elemielemj) if(LA-elemielemj) LC-elemk=LA-elemi; i+;k+; LC-elemk=LA-elemi; i+;k+; else else LC-elemk=LB-elemj;j+;k+; LC-elemk=LB-elemj;j+;k+; while(ilast) while(ilast) LC-elemk=LA-elemi; i+;k+; LC-elemk=LA-elemi; i+;k

9、+; while(jlast) while(jlast) LC-elemk=LB-elemj; j+; k+; LC-elemk=LB-elemj; j+; k+; 2022-3-3優(yōu)點： (1) 無須為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間，因為邏輯上相鄰的元素其存儲位置也相鄰。 (2) 對表中的元素的隨機訪問很方便。缺點： (1) 插入或刪除運算效率低。 (2) 靜態(tài)分配空間使得空間的使用不充分。2022-3-3采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表稱為線性鏈表。從鏈接方式的角度看，鏈表可分為單鏈表、循環(huán)鏈表和雙鏈表從實現(xiàn)角度看，鏈表可分為動態(tài)鏈表和靜態(tài)鏈表2022-3-3結(jié)點 單鏈表示意圖2022-

10、3-3data nextdata next指針域，專指針域，專門用來刻畫門用來刻畫邏輯后繼關(guān)邏輯后繼關(guān)系的系的數(shù)據(jù)域數(shù)據(jù)域A AB BC CD DE E 通過指針來描述數(shù)據(jù)元素間的邏輯關(guān)系H頭指針2022-3-3帶有頭結(jié)點的單鏈表帶有頭結(jié)點的單鏈表A AB BC CD D H頭結(jié)點2022-3-3單鏈表的存儲結(jié)構(gòu)單鏈表的存儲結(jié)構(gòu)typedef struct Node typedef struct Node ElemType data; ElemType data; struct Node struct Node * *next ; next ; Node , Node , * *LinkLis

11、t ; LinkList ; 2022-3-3Node e；/定義了一個結(jié)點類型的變量eNode *p；/定義了一個結(jié)點類型的指針變量pp-data/p指向的結(jié)點的數(shù)據(jù)域p-next/p指向的結(jié)點的后繼結(jié)點指針LinkList p；/與Node *p；作用相同2022-3-3定義了結(jié)點指針變量之后需要對變量進行賦值！比如：p=&e;/p指向了結(jié)點e更多的時候，我們?yōu)榱斯?jié)省變量的使用，不再定義結(jié)點變量，而是直接向內(nèi)存申請一個結(jié)點需要的空間，讓結(jié)點指針指向這個結(jié)點空間。操作如下：p=（Node*)malloc(sizeof(Node); /p指向由malloc函數(shù)申請的一個結(jié)點空間2022

12、-3-3如果有：p=(Node*)malloc(sizeof(Node);則該指針變量有兩個分量：p-data-用來存儲數(shù)據(jù)元素p-next-用來指向p的后繼結(jié)點2022-3-3p語句與對應(yīng)的示意圖：p=(Node*)malloc(sizeof(Node);p-data=A;A A pp-next=NULL;A Ap請根據(jù)如下語句畫出對應(yīng)的示意圖Node *q,*r;q=(Node*)malloc(sizeof(Node);q-data=3;r=(Node*)malloc(sizeof(Node);r-data=5;q-next=r;r-next=NULL;2022-3-3根據(jù)示意圖寫出對應(yīng)的

13、語句 Node *p; p=(Node*)malloc(sizeof(Node); p-data=A; Node *r; r=p; 2022-3-3A ApA Apr在這里，我們主要討論的單鏈表的基本運算有：l 初始化單鏈表l 建立單鏈表：頭部插入法和尾部插入法l 查找l 求表長l 單鏈表的插入l 單鏈表的刪除l 輸出一個單鏈表中的結(jié)點數(shù)據(jù)l 合并兩個單鏈表 .2022-3-3如果說順序表的操作是對表L的數(shù)組L.elem和表尾元素標(biāo)志L.last的操作，那么單鏈表的操作就是對結(jié)點指針p、結(jié)點的數(shù)據(jù)域p-data、結(jié)點的指針域p-next的操作。2022-3-32022-3-3初始化單鏈表的目的

14、是創(chuàng)建一張帶有頭結(jié)點的空的單鏈表。帶有頭結(jié)點的空單鏈表示意圖如下：InitList (LinkList *L) *L=(LinkList)malloc(sizeof(Node); (*L)-next=NULL;2022-3-3 L根據(jù)線性表的元素建立相對應(yīng)的單鏈表，比如有如下線性表： L=( 3，6，8，12)對應(yīng)著該線性表的單鏈表存儲示意圖為：單鏈表的創(chuàng)建其實就是從一個空單鏈表通過逐一將存放數(shù)據(jù)元素的結(jié)點鏈接到表中過程。2022-3-33 36 68 812 12 L2022-3-3 L3 36 68 812 12 L6 68 812 12 L8 812 12 L12 12 L3 36 68

15、 812 12 L頭部插入法頭部插入法：頭部插入法：void CreateFromHead(LinkList L)void CreateFromHead(LinkList L) Node Node * *s ; s ; int v; int v; int flag=1; int flag=1; while(flag) while(flag) scanf(“%d”,&v); scanf(“%d”,&v); if(v!=-100) if(v!=-100) s=(Node s=(Node* *)malloc(sizeof(Node);)malloc(sizeof(Node); s-d

16、ata=v; s-data=v; s-next=L-next; s-next=L-next; L-next=s; L-next=s; /if/if else flag=0; else flag=0; /while/while /CreateFromHead /CreateFromHead 2022-3-32022-3-3 L3 36 68 812 12 L3 36 68 8 L3 36 6 L3 3 L3 36 68 812 12 L尾部插入法尾部插入法：尾部插入法：void CreateFromTail(LinkList L)void CreateFromTail(LinkList L) N

17、ode Node * *r ,r ,* *s ; s ; int v , flag=1; int v , flag=1; r=L; r=L; while(flag) while(flag) scanf(“%d”,&v); scanf(“%d”,&v); if(v!=-100) if(v!=-100) s=(Node s=(Node * *)malloc(sizeof(Node);)malloc(sizeof(Node); s-data=v; s-data=v; r-next=s; r-next=s; r=s; r=s; /if/if else flag=0; r-next=NU

18、LL; else flag=0; r-next=NULL; /while/while /CreateFromTail /CreateFromTail 2022-3-3在順序表中，用數(shù)組下標(biāo)來表示數(shù)據(jù)元素的存儲地址，因此，如果當(dāng)前元素的位置為i，則它的后繼的存儲位置為i+1,換句話說，執(zhí)行一次i=i+1，就可以獲取當(dāng)前元素的后繼元素的下標(biāo)位置。在一個單鏈表中，如果已經(jīng)知道了當(dāng)前數(shù)據(jù)元素結(jié)點的存儲地址為p，那么，該結(jié)點的后繼結(jié)點的地址為什么？2022-3-3將單鏈表中的結(jié)點中的數(shù)據(jù)依次輸出。算法思想：首先從首元結(jié)點開始輸出其數(shù)據(jù)域中存儲的數(shù)據(jù)，然后輸出該結(jié)點的后繼結(jié)點的數(shù)據(jù)域中的數(shù)據(jù)，一直到該鏈表

19、的最后一個結(jié)點，也就是表尾結(jié)點為止。2022-3-32022-3-33 36 68 812 12 L3 6 8 12 0 1 2 3 4 MAXSIZE-1 i ip pL.elemL.elem要獲取當(dāng)前元素的后繼元素位置，就要執(zhí)行一次i=i+1要獲取當(dāng)前結(jié)點的后繼結(jié)點位置，就要執(zhí)行一次p=p-next3首元數(shù)據(jù)元素的位置為0,輸出當(dāng)前位置的數(shù)據(jù)元素指向首元結(jié)點的指針為L-next,輸出當(dāng)前指針?biāo)赶虻慕Y(jié)點的數(shù)據(jù)366881212L.last+1NULLi=0;/ 順序表首元的下標(biāo)位置,即從首元開始輸出while(inext; i+; return i;2022-3-3該算法的目的是查找單鏈表

20、中序號為i的那個結(jié)點，也就是第i個結(jié)點。方法：從頭結(jié)點開始依次順著鏈域掃描，用指針p指向當(dāng)前掃描到的結(jié)點。初始指向頭結(jié)點，用j作為計數(shù)器，初值為0，當(dāng)j=i的時候，指針p所指向的結(jié)點就是要找尋的第i個結(jié)點。2022-3-3請同學(xué)自己完成。2022-3-3該算法的目的是在單鏈表中查找是否有值等于e的結(jié)點。查找算法與順序表的按值查找類似，從頭結(jié)點出發(fā)，順鏈逐個將結(jié)點值和給定的值e作比較，若查找不成功，返回NULL，若查找成功，則返回該結(jié)點的地址（也就是指向該結(jié)點的指針）2022-3-3請同學(xué)們自己描述 ！2022-3-3該操作的目的是在單鏈表的第i個結(jié)點的位置上插入存儲數(shù)據(jù)為e的結(jié)點。我們可以理解

21、為在第i-1個結(jié)點的后面插入新結(jié)點。當(dāng)i=3,e=7時，觀察下面的示意圖，考慮插入前到插入后都發(fā)生了什么樣的變化。插入前：插入后：2022-3-33 36 68 812 12 L3 36 67 712 12 L8 82022-3-33 36 68 812 12 L3 36 67 712 12 L8 87 7prepres sp-nextp-nextpre-next=spre-next=ss-nexts-nexts-next=pre-nexts-next=pre-next2022-3-31.找到插入位置：從頭結(jié)點（第0個結(jié)點）開始，通過指針的移動獲得指向第i-1個結(jié)點的指針2.申請新結(jié)點空間，存

22、儲帶插入的數(shù)據(jù)3.改變結(jié)點的后繼指針，將待插入結(jié)點插入到插入位置后2022-3-3算法：int InsertLinkListint InsertLinkList（LinkList LLinkList L，int i int i ，ElemType e)ElemType e) Node Node * *pre , pre , * *s; int j ; s; int j ; pre=L; j=0; pre=L; j=0; while(pre!=NULL&ji-1) while(pre!=NULL&jnext; j+; pre=pre-next; j+; if(!pre)print

23、f(“ if(!pre)printf(“插入位置不合理！插入位置不合理！”);return 0”);return 0； s=(Node s=(Node* *)malloc(sizeof(Node);)malloc(sizeof(Node); s-data=e; s-data=e; s-next=p-next; p-next=s; s-next=p-next; p-next=s; return 1 return 1； 查看一下單鏈表的插入算法，看一看插入算法中最查看一下單鏈表的插入算法，看一看插入算法中最費時間的是什么操作？費時間的是什么操作？插入的過程時間復(fù)雜度為多少？插入的過程時間復(fù)雜度為多

24、少？2022-3-3該運算的目的是刪除單鏈表中的第i個結(jié)點，并帶回被刪除結(jié)點的數(shù)據(jù)。若i=3，查看一下刪除之前和刪除之后的狀態(tài)。刪除前：刪除后：2022-3-33 36 68 812 12 L3 36 67 712 12 L8 82022-3-33 36 68 812 12 L6 63 37 712 12 L8 8r rr-nextr-nextpreprepre-next=r-nextfree(r)1 . 找到待刪除結(jié)點的前驅(qū)結(jié)點并由指針pre指向2. 利用指針的賦值刪除第i個結(jié)點 3. 釋放被刪除結(jié)點所占用空間2022-3-3int DelList(LinkList L , int i ,

25、ElemType *e) Node *pre , *r ; int k ; pre=L; k=0; while(pre-next!=NULL & knext; k=k+1; if(!(pre-next)return 0; r=pre-next; pre-next=r-next; *e=r-data; free(r); return 1;2022-3-3有兩個單鏈表LA和LB，其元素均為非遞減有序排列。編寫一個算法，將它們合并成一個單鏈表LC，要求LC也是非遞減有序排列。要求：新表LC利用現(xiàn)有的LA和LB中的元素結(jié)點空間，而不要額外申請結(jié)點空間。2022-3-32022-3-32 22

26、23 3 LALA1 13 33 3LBLB4 4 LCLCpapapbpb r r將單鏈表的最后一個結(jié)點的指針域由NULL改為指向表頭結(jié)點，就是循環(huán)單鏈表。如下圖：很多情況下，采用帶有尾指針的循環(huán)單鏈表，如圖：2022-3-33 36 67 712 12 L8 83 36 67 712 12 8 8rearrear空的循環(huán)單鏈表示意圖什么樣？空的循環(huán)單鏈表示意圖什么樣？寫出初始化一個空循環(huán)單鏈表的的算寫出初始化一個空循環(huán)單鏈表的的算法法一個非空的循環(huán)單鏈表的表尾結(jié)點的一個非空的循環(huán)單鏈表的表尾結(jié)點的特征是什么？特征是什么？2022-3-3問題：有兩個帶有頭結(jié)點的循環(huán)單鏈表，編寫算法，問題：有兩個帶有頭結(jié)點的循環(huán)單鏈表，編寫算法，將兩個循環(huán)單鏈表鏈接成為一個循環(huán)單鏈表。將兩個循環(huán)單鏈表鏈接成為一個循環(huán)單鏈表。情況情況1 1：如果兩個循