數(shù)據(jù)結(jié)構(gòu)教學(xué)課件：第2章 線性表

1、第2章 線性表1.線性表的定義：是由n(n=0)個數(shù)據(jù)元素（結(jié)點）a1,a2,a3, an組成的有限序列。其中：n為數(shù)據(jù)元素的個數(shù)，也稱為表的長度。當(dāng)n=0 時，稱為空表。非空的線性表(n0) 記作：（ a1,a2,a3, an） 2.線性表（a1,a2,a3, an）的邏輯特征：（4） ai是屬于某個數(shù)據(jù)對象的元素，它可以是一個數(shù)字、一個字母或一個記錄。（1）有且僅有一個頭結(jié)點。（2）有且僅有一個尾節(jié)點。（3）其余的結(jié)點ai 都有且僅有一個直接前趨ai-1和一個直接后繼ai+1 3.線性表的特性（1）線性表中的所有數(shù)據(jù)元素的數(shù)據(jù)類型是一致的。（2）數(shù)據(jù)元素 在線性表中的位置只取決于它的序號。

2、（3）結(jié)點間的邏輯關(guān)系是線性的。2.2 線性表的順序表示和實現(xiàn)1.順序表的存儲結(jié)構(gòu) 實現(xiàn)順序存儲結(jié)構(gòu)的方法是使用數(shù)組。數(shù)組把線性表的數(shù)據(jù)元素存儲在一塊連續(xù)地址空間的內(nèi)存單元中，這樣線性表中邏輯上相鄰的數(shù)據(jù)元素在物理存儲地址上也相鄰。數(shù)據(jù)元素間的邏輯上的前驅(qū)、后繼邏輯關(guān)系就表現(xiàn)在數(shù)據(jù)元素的存儲單元的物理前后位置上。順序表的存儲結(jié)構(gòu)如圖所示順序存儲結(jié)構(gòu)的線性表稱作順序表a0a1a2a3a4a5listsize=6MaxSize-1 0 1 2 3 4 5 6 其中a0 ,a1, a2等表示順序表中存儲的數(shù)據(jù)元素，list表示順序表存儲數(shù)據(jù)元素的數(shù)組，MaxSize表示存儲順序表的數(shù)組的最大存儲單元

3、個數(shù)，size表示順序表當(dāng)前存儲的數(shù)據(jù)元素個數(shù)。 typedef structDataType listMaxSize;int size; SeqList;2.順序表操作的實現(xiàn) （1）初始化ListInitiate(L)void ListInitiate(SeqList *L) L-size = 0;/*定義初始數(shù)據(jù)元素個數(shù)*/ （2）求當(dāng)前數(shù)據(jù)元素個數(shù)ListLength(L)int ListLength(SeqList L) return L.size; （3）插入數(shù)據(jù)元素ListInsert(L, i, x)int ListInsert(SeqList *L, int i, DataTy

4、pe x)int j;for(j = L-size; j i; j-) L-listj = L-listj-1; /*依次后移*/L-listi = x; /*插入x*/L-size +; /*元素個數(shù)加1*/return 1;?干嗎加星號？（4）刪除數(shù)據(jù)元素ListDelete(L, i, x)int ListDelete(SeqList *L, int i, DataType *x)int j;*x = L-listi;/*保存刪除的元素到x中*/for(j = i +1; j size-1; j+) L-listj-1 = L-listj; /*依次前移*/L-size-;/*數(shù)據(jù)元素個

5、數(shù)減1*/return 1;（5）取數(shù)據(jù)元素ListGet(L, i, x)int ListGet(SeqList L, int i, DataType *x)if(i L.size-1) printf(參數(shù)i不合法! n); return 0;else *x = L.listi; return 1;3.順序表操作的效率分析時間效率分析:算法時間主要耗費在移動元素的操作上，因此計算時間復(fù)雜度的基本操作(最深層語句頻度) T(n)= O(移動元素次數(shù)) 而移動元素的個數(shù)取決于插入或刪除元素的位置i.若i=size，則根本無需移動（特別快）；若i=0，則表中元素全部要后移（特別慢）；應(yīng)當(dāng)考慮在各種

6、位置插入（共n+1種可能）的平均移動次數(shù)才合理。設(shè)Pi是在第i個存儲位置插入一個數(shù)據(jù)元素的概率，順序表中的數(shù)據(jù)元素個數(shù)為n,當(dāng)在順序表的任何位置上插入數(shù)據(jù)元素的概率相等時，有Pi=1/(n+1),則 插入時的平均移動次數(shù)為: n(n+1)/2（n+1）n/2O(n)同理可證:順序表刪除一元素的時間效率為:T（n)=(n-1)/2 O(n) 插入效率：刪除效率：4.順序表應(yīng)用舉例 例：編程實現(xiàn)如下任務(wù):建立一個線性表，首先依次輸入數(shù)據(jù)元素1，2，3，10，然后刪除數(shù)據(jù)元素5，最后依次顯示當(dāng)前線性表中的數(shù)據(jù)元素。要求采用順序表實現(xiàn)，假設(shè)該順序表的數(shù)據(jù)元素個數(shù)在最壞情況下不會超過100個。實現(xiàn)方法：

7、1、采用直接編寫一個主函數(shù)實現(xiàn)。2、利用已設(shè)計實現(xiàn)的抽象數(shù)據(jù)類型模塊。（存放在頭文件名為SeqList.h中，通過 #include “SeqList.h” ）程序設(shè)計如下：#include #define MaxSize 100typedef int DataType;#include SeqList.hvoid main(void)SeqList myList;int i , x;ListInitiate(&myList);for(i = 0; i 10; i+) ListInsert(&myList, i, i+1);ListDelete(&myList, 4, &x);for(i =

8、0; i next = NULL;（2）求當(dāng)前數(shù)據(jù)元素個數(shù)ListLength(head)int ListLength(SLNode *head)SLNode *p = head;int size = 0;while(p-next != NULL)p = p-next;size +;return size; （3）插入ListInsert(head, i, x)int ListInsert(SLNode *head, int i, DataType x)SLNode *p, *q;int j;p = head;j = -1;while(p-next != NULL & j next;j+;if

9、(j != i - 1)printf(插入位置參數(shù)錯！);return 0; q = (SLNode *)malloc(sizeof(SLNode);/new SLNodeq-data = x;q-next = p-next; p-next = q;return 1;說明：要在帶頭結(jié)點的單鏈表第i（0 i size）個結(jié)點前插入一個存放數(shù)據(jù)元素x的結(jié)點，首先要在單鏈表中尋找到第i-1個結(jié)點并由指針p指示，然后動態(tài)申請一個結(jié)點存儲空間并由指針q指示，并把數(shù)據(jù)元素x的值賦予新結(jié)點的數(shù)據(jù)元素域（即q-data = x），最后修改新結(jié)點的指針域指向ai結(jié)點（即q-next = p-next），并修改a

10、i-1結(jié)點的指針域指向新結(jié)點q（即p-next = q）。循環(huán)條件由兩個子條件邏輯與組成，其中子條件p-next != NULL保證指針?biāo)附Y(jié)點存在，子條件j next != NULL & p-next-next!= NULL & j next;j+;if(j != i - 1)printf(插入位置參數(shù)錯！);return 0;s = p-next; *x = s-data;p-next = p-next-next; free(s);return 1;說明：要在帶頭結(jié)點的單鏈表中刪除第i（0 i size - 1）個結(jié)點，首先要在單鏈表中尋找到第i-1個結(jié)點并由指針p指示，然后讓指針s指向a

11、i結(jié)點（即s = p-next），并把數(shù)據(jù)元素ai的值賦予x（即*x = s-data），最后把a(bǔ)i結(jié)點脫鏈（即p-next = p-next-next），并動態(tài)釋放ai結(jié)點的存儲空間（即free(s)）。刪除過程如圖2-14所示。圖中的對應(yīng)算法中的刪除語句。 （5）取數(shù)據(jù)元素ListGet(head, i, x)int ListGet(SLNode *head, int i, DataType *x)SLNode *p;int j;p = head;j = -1;while(p-next != NULL & j next;j+;if(j != i)printf(取元素位置參數(shù)錯！);retu

12、rn 0;*x = p-data;return 1; （6）撤消單鏈表Destroy(head)void Destroy(SLNode *head)SLNode *p, *p1;p = *head;while(p != NULL) p1 = p;p = p-next;free(p1);*head = NULL;4.單鏈表操作的效率分析單鏈表的插入和刪除操作不需移動數(shù)據(jù)元素，只需比較數(shù)據(jù)元素。因此，當(dāng)在單鏈表的任何位置上插入數(shù)據(jù)元素的概率相等時，在單鏈表中插入一個數(shù)據(jù)元素時比較數(shù)據(jù)元素的平均次數(shù)為：刪除一個數(shù)據(jù)元素時比較數(shù)據(jù)元素的平均次數(shù)為：另外，單鏈表求數(shù)據(jù)元素個數(shù)操作的時間復(fù)雜度為O(n)。

13、和順序表相比主要優(yōu)點是不需要預(yù)先確定數(shù)據(jù)元素的最大個數(shù)，插入和刪除操作不需要移動數(shù)據(jù)元素；主要缺點是因為是鏈?zhǔn)巾樞虼鎯Y(jié)構(gòu)，所以，查找數(shù)據(jù)元素時需要順序進(jìn)行，不能像順序表那樣隨機(jī)查找任意一個數(shù)據(jù)元素。另外，每個結(jié)點中要有一個指針域，因此空間單元利用率不高。而且單鏈表操作的算法也較復(fù)雜。單鏈表和單鏈表相比，順序表的優(yōu)點和缺點正好相反。5.單鏈表應(yīng)用舉例 例：編程實現(xiàn)如下任務(wù):建立一個線性表，首先依次輸入數(shù)據(jù)元素1，2，3，10，然后刪除數(shù)據(jù)元素5，最后依次顯示當(dāng)前線性表中的數(shù)據(jù)元素。要求采用單鏈表實現(xiàn)。#include #include #include typedef int DataType

14、;#include LinList.hvoid main(void)SLNode *head;int i , x;ListInitiate(&head);for(i = 0; i 10; i+) ListInsert(head, i, i+1) ;ListDelete(head, 4, &x) ; for(i = 0; i next指向第i+1個數(shù)據(jù)元素結(jié)點，p-next-prior仍指向第i個數(shù)據(jù)元素結(jié)點，即p-next-prior=p;同樣p-prior-next=p。循環(huán)雙向鏈表的插入過程如圖示：a0aian-1headxsai-1p刪除過程如圖示：ai+1aian-1headai-1p

15、2.6 靜態(tài)鏈表在數(shù)組中增加一個(或兩個)指針域用來存放下一個(或上一個)數(shù)據(jù)元素在數(shù)組中的下標(biāo)，從而構(gòu)成用數(shù)組構(gòu)造的單鏈表。因為數(shù)組內(nèi)存空間的申請方式是靜態(tài)的，所以稱為靜態(tài)鏈表，增加的指針稱做仿真指針。結(jié)構(gòu)如下：ABCEheadD(a) 常規(guī)鏈表A1B2C3D4E-1(b) 靜態(tài)鏈表一data next01234maxSize-1A2E-1B4D1C3(b) 靜態(tài)鏈表一data next01234maxSize-12.7 設(shè)計舉例例2-4 設(shè)計一個順序表的刪除函數(shù)，把順序表L中的數(shù)據(jù)元素x刪除。算法思想：此刪除問題可通過一個循環(huán)比較過程來實現(xiàn)。int ListDataDelete(SeqLi

16、st *L, DataType x)int i, j;for(i = 0; i size; i+) if(x = L-listi) break;if(i = L-size) return 0;else for(j = i; j size; j+) L-listj = L-listj+1; L-size-; return 1; 例2-5 構(gòu)造一個順序表的刪除算法，把順序表L中所有值相同的數(shù)據(jù)元素x全部刪除。算法思想：此刪除問題是在例2-4所設(shè)計的刪除算法的基礎(chǔ)上再增加一重循環(huán)，來實現(xiàn)值相同數(shù)據(jù)元素x的全部刪除。int ListMoreDataDelete(SeqList *L, DataType

17、 x)int i, j;int tag = 0;for(i = 0; i size; i+) if(x = L-listi) for(j = i; j size-1; j+) L-listj = L-listj+1; L-size-;i-;tag = 1; return tag;例2-6設(shè)頭指針為head，并設(shè)帶頭結(jié)點單鏈表中的數(shù)據(jù)元素遞增有序，編寫算法將數(shù)據(jù)元素x插入到帶頭結(jié)點單鏈表的適當(dāng)位置上，要求插入后保持單鏈表數(shù)據(jù)元素的遞增有序。算法思想：從鏈表的第一個數(shù)據(jù)元素結(jié)點開始，逐個比較每個結(jié)點的data域值和x的值，當(dāng)data小于等于x時，進(jìn)行下一個結(jié)點的比較；否則就找到了插入結(jié)點的合適位置，此時申請新結(jié)點把x存入，然后把新結(jié)點插入；當(dāng)比較到最后一個結(jié)點仍有data小于等于x時，則把新結(jié)點插入單鏈表尾。void LinListInsert(SLNode *head, DataType x)SLNode *curr, *pre, *q;curr = head-next;pre = head;while(curr != NULL & curr-data next;q = (SLNode *)malloc(sizeof(SLNode);q-data = x;q-next = pre-next;pre-next = q;算法設(shè)計說明：（1）在循環(huán)