數(shù)據(jù)結(jié)構(gòu)DS02線性表

1、第2章 線性表 線性表的順序存儲(chǔ)線性表的鏈?zhǔn)酱鎯?chǔ)線性表兩種不同存儲(chǔ)結(jié)構(gòu)的比較線性表的應(yīng)用12.1 線性表的基本概念 線性結(jié)構(gòu)的基本特征是：有而且只有一個(gè)“第一元素”；有而且只有一個(gè)“最后元素”；除第一元素之外，其他元素都有唯一的直接前趨；除最后元素之外，其他元素都有唯一的直接后繼。線性表是一種常用的簡單的數(shù)據(jù)結(jié)構(gòu)，它屬于線性結(jié)構(gòu)的范疇。2線性表（Linear List）是具有相同數(shù)據(jù)類型的n(n0)個(gè)數(shù)據(jù)元素的有限序列，通常記為：( a1， a2， ai-1， ai， ai+1， an)其中，數(shù)據(jù)元素的個(gè)數(shù)n稱為線性表的長度。當(dāng)n0 時(shí)稱為空表。例2.3 26個(gè)大寫英文字母表（A,B,C,Z）

2、的表長是26，起始結(jié)點(diǎn)A沒有直接前趨，A的唯一的直接后繼是B；終端結(jié)點(diǎn)Z沒有直接后繼， Z的唯一的直接前趨是Y；而對于B,C,D, ,Y中的任意一個(gè)字母，都有一個(gè)唯一的直接前趨和一個(gè)唯一的直接后繼。 3線性表的基本操作 initList(L)：初始化操作，構(gòu)造一個(gè)空線性表L ClearList(L)：清除線性表L的內(nèi)容，將L置為空表 ListLength(L)：求表長(表中元素個(gè)數(shù)) ins(L，i，Item)：插入數(shù)據(jù) Del(L，i)：刪除數(shù)據(jù) 4線性表的基本操作（續(xù)）GetNode(L，i)：獲取表L中位置i的結(jié)點(diǎn)值 Loc(L，Item)：定位(按值查找) GetPrior(L，Ite

3、m，p)：獲取值為Item的結(jié)點(diǎn)的前趨結(jié)點(diǎn) GetNext(L，Item，p) :獲取值為Item的結(jié)點(diǎn)的后繼結(jié)點(diǎn)52.2 線性表的順序存儲(chǔ) 線性表的順序存儲(chǔ)方式，就是利用一段連續(xù)的內(nèi)存地址來存儲(chǔ)線性表的數(shù)據(jù)元素。在C語言中，是用一個(gè)數(shù)組來實(shí)現(xiàn)的。 線性表的這種機(jī)內(nèi)表示稱作線性表的順序存儲(chǔ)結(jié)構(gòu)或順序映象。同時(shí)，我們把這種順序存儲(chǔ)結(jié)構(gòu)的線性表稱為順序表。6 對線性表A ( a1， a2， ai-1， ai， ai+1， an)a1a2ai-1aiai+1an其順序存儲(chǔ)結(jié)構(gòu)可表示如下:7例2.4 一個(gè)順序存儲(chǔ)結(jié)構(gòu)的線性表（順序表）的例子。typedef struct char name20; /*

4、姓名*/ char no10; /*學(xué)號*/ float score; /*成績*/ STUDENT；STUDENT s20; 則s就是一個(gè)以STUDENT類型為數(shù)據(jù)元素的線性表。8 線性表L中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai)之間滿足如下關(guān)系： LOC(ai+1)=LOC(ai)+m 線性表L的第i個(gè)元素的存儲(chǔ)位置和第一個(gè)元素的存儲(chǔ)位置的關(guān)系為： LOC(ai)=LOC(a1)+(i-1)*m 其中LOC(a1)是線性表的第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置，通常稱為線性表的起始位置或基地址。9順序表的基本操作順序表的C語言描述typedef int

5、datatype; /*定義表元素類型*/ #define maxsize 1024 /*線性表的最大長度*/ typedef struct datatype elemmaxsize;/*存放表結(jié)點(diǎn)的數(shù)組*/ int length; /*表長*/sequenlist; 10順序表的基本操作順序表的初始化算法2.1 構(gòu)造一個(gè)空的順序表void InitList(sequenlist *L) L- length=0; 11順序表的基本操作清除一個(gè)線性表的內(nèi)容 要清除一個(gè)已經(jīng)存在的線性表的內(nèi)容，只需要把該線性表設(shè)置為空表，也就是把表長置為0。算法2.2 清除一個(gè)線性表的內(nèi)容void ClearLis

6、t(sequenlist *L) L-length=0; 本算法時(shí)間復(fù)雜度為O（1）。 12順序表的基本操作 定位(按值查找)： 要查找一個(gè)值，只需要從頭到尾的遍歷線性表，如果找到，則返回找到的位置，否則繼續(xù)，如果一直到最后一個(gè)位置都沒有找到，則返回0。 本算法中，可能找到Item，這時(shí)候，平均比較次數(shù)為O(n/2)，其中，n是線性表的長度；也可能找不到Item，這時(shí)候，算法的比較次數(shù)為O(n)。因此，總結(jié)起來，本算法的時(shí)間復(fù)雜度為O(n)。13算法2.3 定位（按值查找）int Loc(sequenlist L，datatype Item) int i,j; j=L.length; /*表的

7、長度*/ if( j= = 0) return FALSE; for(i=1;i=j;i+) if(L. datai= =Item) return i; printf(“找不到該值！”); return 0; 找到了值為item的結(jié)點(diǎn)14順序表的基本操作 插入數(shù)據(jù) 要在線性表中第i個(gè)位置插入一個(gè)數(shù)據(jù)元素，需要考慮以下因素： i是否在1和L.length之間，如果在，則先將原來最后一個(gè)數(shù)據(jù)元素直到第i個(gè)數(shù)據(jù)元素依次向后移動(dòng)一個(gè)位置，再將Item插到第i個(gè)位置，然后線性表長度加上1，返回TRUE；如果不在1和L.length之間，則說明插入位置不合適，返回FALSE。如圖2.2所示： 15插入前

8、插入后 圖2.2 在順序表中插入結(jié)點(diǎn)的示意圖16算法2.4 在表L的第i個(gè)位置插入數(shù)據(jù)itemint Ins(sequenlist *L，int i，datatype item)int j;if(iL-length) return FALSE； for(j=L-length;j=i;j-)/*注意數(shù)組的下標(biāo)從0開始*/ L-dataj=L- dataj-1;/*后移*/ L- datai-1=item; /*插入*/ L-length+; /*表長加1*/ return TRUE;17 本算法的時(shí)間主要花在移動(dòng)數(shù)據(jù)上，由于插入位置是隨機(jī)的，因此，移動(dòng)的平均次數(shù)為(n/2)，其中，n是線性表的長

9、度。因此，本算法的時(shí)間復(fù)雜度為O(n)。18順序表的基本操作刪除數(shù)據(jù) 刪除數(shù)據(jù)和插入數(shù)據(jù)很相似，都要求判斷i的值是否合適，如果位置合適，則把后面的數(shù)據(jù)元素依次向前移動(dòng)一個(gè)位置，刪除成功，表的長度減1，返回TRUE；否則，返回FALSE。如下圖所示： 19刪除前 刪除后 圖2.3 在順序表中刪除結(jié)點(diǎn)的示意圖20算法2.5 刪除線性表中第i個(gè)結(jié)點(diǎn)數(shù)據(jù)int Del(sequenlist *L，int i)int j;if(iL-length) return FALSE；for(j=i;jlength-1;j+) L- dataj=L- dataj+1; /*前移*/L-length-; /*表長減

10、1*/return TRUE；2123 線性表的鏈?zhǔn)酱鎯?chǔ) 下面介紹線性表的另一種存儲(chǔ)方式鏈?zhǔn)酱鎯?chǔ)。在鏈?zhǔn)酱鎯?chǔ)方式中，能夠方便地增加和刪除線性表中的元素，但是同時(shí)也使隨機(jī)存取、獲取直接前趨和直接后繼變得較為復(fù)雜。22 鏈表：以鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)的線性表稱之為鏈表（Linked List）。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元來存儲(chǔ)線性表的結(jié)點(diǎn)。也就是說，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)單元可以是相鄰的，也可以是不相鄰的；同時(shí)，相鄰的存儲(chǔ)單元中的數(shù)據(jù)，不一定是相鄰的結(jié)點(diǎn)。 23存儲(chǔ)地址數(shù)據(jù)域指針域1李407張15頭指針H15趙NULL20王140錢5454孫8383吳7例2.7 線性表（“王”，“李”，“錢”，“孫”

11、，“吳”，“張”，“趙”）的單鏈表示意圖。24 只有一個(gè)指針域的鏈表，稱為單鏈表。 用單鏈表表示線性表時(shí)，結(jié)點(diǎn)之間的邏輯關(guān)系是由結(jié)點(diǎn)中的指針指示的，如圖2.6所示。 圖2.6 單鏈表的圖示表示25單鏈表的C語言描述：typedef struct LNode ElemType data； Struct LNode *next; LinkList; LinkList *L, *head; 這里的L（或head）可以作為單鏈表的頭指針，它指向該鏈表的第一個(gè)結(jié)點(diǎn)。如果L=NULL，則表示該單鏈表為一個(gè)空表，其長度為0。26 為了更方便的判斷空表、插入和刪除結(jié)點(diǎn)，有時(shí)在單鏈表的第一個(gè)元素結(jié)點(diǎn)前面加上一個(gè)

12、附設(shè)的結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存儲(chǔ)一些附加信息；而頭結(jié)點(diǎn)的指針域存儲(chǔ)鏈表的首元結(jié)點(diǎn)的地址。 如果頭結(jié)點(diǎn)的指針域?yàn)椤翱铡?，即L-next=NULL，則表示該鏈表為空表。2728單鏈表的基本操作 清除帶頭單鏈表的內(nèi)容 分析：要清除鏈表的內(nèi)容，就必須從頭結(jié)點(diǎn)開始，依次的釋放每一個(gè)節(jié)點(diǎn)所占有的存儲(chǔ)空間，然后把表長設(shè)置為0，頭結(jié)點(diǎn)的next域設(shè)置為NULL。 29算法2.6 清除帶頭結(jié)點(diǎn)的單鏈表的內(nèi)容 int ClearList(LinkList *L) LinkList *temp; while(L-next != NULL) temp=L-next; /*使temp

13、指向首元結(jié)點(diǎn)*/ L-next=L-next-next; free(temp); return TRUE;tempL-next-next30 本算法首先將頭結(jié)點(diǎn)的指針域指向第二個(gè)元素結(jié)點(diǎn)，然后釋放第一個(gè)元素結(jié)點(diǎn)的存儲(chǔ)空間，依此類推。 要清除表的內(nèi)容，就必須對鏈表進(jìn)行一次遍歷，因此，時(shí)間復(fù)雜度為O(n)，其中，n表示鏈表的長度。 31單鏈表的基本操作 求表長： 分析：由于在結(jié)點(diǎn)中沒有保存鏈表的長度，因此，要獲得表長，必須對鏈表進(jìn)行一次完整的遍歷。32算法2.7 求帶頭結(jié)點(diǎn)的單鏈表的長度 int ListLength(LinkList *L)int len=0; LinkList *temp; t

14、emp=L; while(temp-next != NULL) len+;temp=temp-next; return len; 本算法時(shí)間復(fù)雜度為O(n)，其中n是鏈表的長度。 33單鏈表的基本操作 定位(按值查找)： 分析：與求鏈表長度類似，要在鏈表中查找給定值的結(jié)點(diǎn)，也需要對鏈表進(jìn)行遍歷。34算法2.8 在帶頭結(jié)點(diǎn)的單鏈表中按值查找定位int Loc(LinkList *L，ElemType Item)int i=0; /*查找值為Item 的結(jié)點(diǎn)在表中的位置*/ LinkList *temp; temp=L-next; /*使temp指向首元結(jié)點(diǎn)*/ while(temp!= NULL

15、 & temp-data != Item) i+; temp=temp-next; if(temp=NULL) return 0; else return i; 本算法的時(shí)間復(fù)雜度為O(n)。35單鏈表的基本操作 插入數(shù)據(jù)（在第i個(gè)結(jié)點(diǎn)的后面插入）： 分析：在鏈表中插入數(shù)據(jù)比較方便，不需要進(jìn)行大量的數(shù)據(jù)移動(dòng)。只需要找到插入點(diǎn)即可，我們給出的是一個(gè)后插入的算法，也就是在插入點(diǎn)的后面添加結(jié)點(diǎn)，如圖所示。插入點(diǎn)36算法2.9 在帶頭結(jié)點(diǎn)單鏈表的第i個(gè)結(jié)點(diǎn)之后插入結(jié)點(diǎn)int Ins(LinkList *L，int i，ElemType Item)int j=1; LinkList *node,*tem

16、p; node=(LinkList *) malloc(sizeof(LinkList); if(node=NULL) printf(“申請空間失敗!”);return FALSE; node-data=Item; temp=L-next; /*使temp指向首元結(jié)點(diǎn) */ if(temp=NULL) /*空表*/ if( i=0) /*作為首元結(jié)點(diǎn)插入*/存儲(chǔ)空間分配不成功37L-next=node;node-next=NULL;return TRUE;else/*插入位置不合理*/ return FALSE;while(jnext; j+; / *尋找第i-1個(gè)結(jié)點(diǎn), temp 指向該結(jié)點(diǎn)

17、*/ if(temp=NULL) /*找到表尾,無合適的插入點(diǎn)*/ return FALSE;/ *插入成功*/ node-next=temp-next;temp-next=node;return TRUE;38單鏈表的基本操作 刪除數(shù)據(jù)：刪除第i個(gè)結(jié)點(diǎn) 分析：在帶頭結(jié)點(diǎn)的單鏈表中，刪除數(shù)據(jù)和插入數(shù)據(jù)很相似。也是先尋找刪除點(diǎn)，找到后修改指針的值即可刪除結(jié)點(diǎn)。如下圖所示：39算法2.10 刪除第i個(gè)結(jié)點(diǎn)int Del(LinkList *L，int i) LinkList *temp,*q; int j=1; temp=L -next;if(temp=NULL) /*空表，無法刪除*/ retu

18、rn FALSE;while(jnext;/*尋找第i-1個(gè)結(jié)點(diǎn)*/if(temp= =NULL) /*第i-1個(gè)結(jié)點(diǎn)不存在*/ return FALSE;Else if (temp -next = =NULL) return FALSE; /*第i個(gè)結(jié)點(diǎn)不存在*/q=temp-next; /*q指向第i個(gè)結(jié)點(diǎn)*/temp-next=q-next;free(q);return TRUE;本算法的時(shí)間復(fù)雜度也是O(n)。40 循環(huán)鏈表（Circular Linked List）是一種首尾相接的鏈表。在單鏈表中，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭眨∟ULL），如果我們把該指針域指向鏈表的第一個(gè)結(jié)點(diǎn)（頭結(jié)點(diǎn)）

19、，則能構(gòu)成一個(gè)單鏈形式的循環(huán)鏈表，簡稱為單循環(huán)鏈表，帶頭結(jié)點(diǎn)的單循環(huán)鏈表如下圖所示。 41單循環(huán)鏈表的操作 循環(huán)鏈表的建立 分析：循環(huán)鏈表是對單向鏈表的一種改善。單向鏈表中末尾結(jié)點(diǎn)的next=NULL，只需要把這個(gè)結(jié)點(diǎn)的next域的值設(shè)置為頭結(jié)點(diǎn)的地址，就能夠獲得一個(gè)循環(huán)鏈表。 創(chuàng)建一個(gè)空循環(huán)鏈表的算法如下： 42算法2.11 創(chuàng)建單循環(huán)鏈表int InitCList(LinkList *L)L=( LinkList *) malloc (sizeof (LinkList); If(L=NULL) /*申請結(jié)點(diǎn)空間不成功*/ return FALSE;L-next=L; return TRUE

20、;43 本算法時(shí)間復(fù)雜度為O(1)，和創(chuàng)建單向空鏈表相同，唯一的區(qū)別是： 在帶頭結(jié)點(diǎn)的空單鏈表中，有 L-next=NULL 在帶頭結(jié)點(diǎn)的空循環(huán)鏈表中，有 L-next=L（頭結(jié)點(diǎn)的指針域指向該頭結(jié)點(diǎn)自身） 44單循環(huán)鏈表的操作(續(xù)) 判斷循環(huán)鏈表是否為空 分析：在單向鏈表中，判斷一個(gè)鏈表是否為空，只需要看頭結(jié)點(diǎn)的next域是否為NULL；相似的，在循環(huán)鏈表中，要判斷一個(gè)鏈表是否為空，只需要看頭結(jié)點(diǎn)的next域是否等于自身。算法如下： 45算法2.12 判斷單循環(huán)鏈表是否為空int isempty(LinkList *L) if(L-next=L) return TRUE; else retu

21、rn FALSE; 本算法時(shí)間復(fù)雜度為O(1)。 46單循環(huán)鏈表的操作(續(xù))算法2.13 插入結(jié)點(diǎn)(在i位置)int InsertCList(LinkList *L，int i，ElemType e)int j; LinkList *temp,*node; node=( LinkList *)malloc(sizeof(LinkList); if(node=NULL) return FALSE; /*申請結(jié)點(diǎn)空間失敗*/ temp=L -next; j=1; while(jnext; /*尋找插入位置*/47if(ji-1) | temp= =L) /*沒有合適的插入位置*/ return F

22、ALSE;node-next=temp-next; /*插入結(jié)點(diǎn)*/ temp-next=node;return TRUE; 本算法時(shí)間復(fù)雜度為O(n)，其中n是鏈表的長度。48帶頭結(jié)點(diǎn)單循環(huán)鏈表的操作(續(xù))刪除結(jié)點(diǎn)(刪除第i個(gè)結(jié)點(diǎn)) :int DelCList(LinkList *L,int i) int j; LinkList *t1, *t2, j=1; t1=L-next; t2=L; if (t1=t2|i1) return FALSE; /*空表或刪除位置i不合理*/ while(jnext; t2=t2-next; /*t2指向其前驅(qū)結(jié)點(diǎn)*/ if(ji)|(t1 = L ) r

23、eturn FALSE;/*找不到刪除點(diǎn)*/ else t2-next=t1-next; /*找到刪除點(diǎn),修改指針將其刪除*/ free(t1); /*釋放空間*/ return TRUE;49 帶頭結(jié)點(diǎn)的雙向鏈表 在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域：一個(gè)指向其直接前趨，另一個(gè)指向其直接后繼。如下圖所示。 (a) 非空表 (b) 空表圖2.11 帶頭結(jié)點(diǎn)的雙向鏈表示意圖50 在C語言中，雙向鏈表的存儲(chǔ)結(jié)構(gòu)可定義如下：typedef struct DNode struct DNode *prior; ElemType data; Struct DNode *next; DLinkList; DLin

24、kList *DL, *p;51 若指針p指向雙向鏈表中的某一結(jié)點(diǎn)，則有如下關(guān)系： p-next-prior=p p-prior-next=p 也就是說，結(jié)點(diǎn)*p的后繼的前趨指向該結(jié)點(diǎn)本身，同理，結(jié)點(diǎn)*p前趨的后繼也指向該結(jié)點(diǎn)本身。有時(shí)，雙向鏈表的這一性質(zhì)可稱為雙向鏈表結(jié)構(gòu)的對稱性。 52雙向鏈表的操作 雙向鏈表的建立 由于雙向鏈表具有指向前趨和指向后繼的兩個(gè)指針，因此，在創(chuàng)建空雙向鏈表的時(shí)候，需要對兩個(gè)指針賦值為NULL。 53算法2.15 建立一個(gè)空雙向鏈表int InitDList(DLinkList *DL)DL=(DNode *)malloc(sizeof(DNode);if(DL=

25、 =NULL) return FALSE;DL-prior=DL-next=NULL;return TRUE; 本算法時(shí)間復(fù)雜度為O(1)。 54雙向鏈表的操作雙向鏈表為空表的判斷 從圖中可以看出，雙向鏈表是否為空表，要看兩個(gè)指針域是否同時(shí)為NULL。 55算法2.16 判斷雙向鏈表是否為空表int DlEmpty(DLinkList *DL)if(DL-prior=DL-next & DL-prior=NULL) return TRUE;else return FALSE;56雙向鏈表的操作在雙向鏈表內(nèi)插入結(jié)點(diǎn)分析：在雙向鏈表中插入新的結(jié)點(diǎn)，則必須修改插入位置的前趨和后繼。57算法2.17

26、在雙向鏈表中插入數(shù)據(jù)int DLInsert(DLinkList *DL,int i,ElemType e) int j=1; /*在帶頭結(jié)點(diǎn)的雙向鏈表DL的第i個(gè)位置插入新結(jié)點(diǎn)e*/ DLinkList *temp，*node; temp=DL -next; while(jnext; if(ji-1)|(temp=NULL) return FALSE;/*找不到插入位置i*/ node=(DLinkList *)malloc(sizeof(DLinkList) if(node=NULL) return FALSE; /*申請空間失敗*/ node-data=e; node-prior=tem

27、p; node-next=temp-next; if (temp-next != NULL) temp-next-prior = node; temp-next=node; return TRUE; temp-next=NULL時(shí)為在表尾插入58雙向鏈表的操作 在雙向鏈表內(nèi)刪除結(jié)點(diǎn) 分析：和插入結(jié)點(diǎn)相似，雙向鏈表中刪除結(jié)點(diǎn)，也是要注意指針的修改。59算法2.18 在雙向鏈表中刪除數(shù)據(jù)int DLDelete(DLinkList *DL, int i) int j=1; DLinkList *temp; /*工作指針,指向被刪結(jié)點(diǎn)*/ temp=DL-next; while(jnext; if

28、(ji)| temp = NULL) /*被刪結(jié)點(diǎn)不存在*/ return FALSE; temp-prior-next=temp-next; if (temp-next != NULL) /*被刪結(jié)點(diǎn)不是尾結(jié)點(diǎn)*/ temp-next-prior=temp-prior; free(temp); return TRUE; 本算法時(shí)間復(fù)雜度為O(n)。 60雙向循環(huán)鏈表 將雙向鏈表中的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來，就構(gòu)成了雙向循環(huán)鏈表。如圖所示。61雙向循環(huán)鏈表的操作算法2.19 在雙向循環(huán)鏈表中刪除結(jié)點(diǎn)eint DLClist(DLinkList *DL, ElemType e)DLinkList

29、*temp; /*工作指針,指向被刪結(jié)點(diǎn)*/temp=DL-next;if(temp-next= =temp)/*空表*/ return FALSE;62while(temp-data!=e)&(temp!=DL) temp=temp-next; /*尋找結(jié)點(diǎn)*/if(temp != DL) /*找到要?jiǎng)h除的結(jié)點(diǎn)*/ temp-prior-next=temp-next; temp-next-prior=temp-prior; free(temp); /*釋放空間*/ return TRUE;else return FALSE; 63靜態(tài)鏈表 由于在C語言中使用標(biāo)準(zhǔn)函數(shù)malloc和free來動(dòng)態(tài)執(zhí)行內(nèi)存分配和回收，并用指針實(shí)現(xiàn)鏈表，因此稱為動(dòng)態(tài)鏈表。而因?yàn)橛械某绦蛟O(shè)計(jì)語言不支持指針類型，所以不能使用動(dòng)態(tài)鏈表。為此可以引入靜態(tài)鏈表的概念。 用數(shù)組描述的鏈表稱為靜態(tài)鏈表（Static Linked List）。在靜態(tài)鏈表中使用“游標(biāo)（Cursor）