《數(shù)據(jù)結(jié)構(gòu)C語言版》第02章

1、數(shù)據(jù)結(jié)構(gòu)C語言版第02章 第第2 2章章 線性表線性表 主要知識點主要知識點 線性表抽象數(shù)據(jù)類型線性表抽象數(shù)據(jù)類型 順序表順序表 循環(huán)單鏈表循環(huán)單鏈表 循環(huán)雙向鏈表循環(huán)雙向鏈表 靜態(tài)鏈表靜態(tài)鏈表 設計舉例設計舉例 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 2.12.1 線性表抽象數(shù)據(jù)類型線性表抽象數(shù)據(jù)類型 1.1.線性表的定義線性表的定義 線性表是一種可以在任意位置插入和刪除數(shù)線性表是一種可以在任意位置插入和刪除數(shù) 據(jù)元素操作、由據(jù)元素操作、由n(n0)個相同類型數(shù)據(jù)元素個相同類型數(shù)據(jù)元素a0, a1, an-1組成的線性結(jié)構(gòu)。組成的線性結(jié)構(gòu)。 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 2.2.線性表抽象數(shù)據(jù)類型線性表抽象數(shù)

2、據(jù)類型 數(shù)據(jù)集合數(shù)據(jù)集合: a0, a1, , an-1 , ai的數(shù)據(jù)類型為的數(shù)據(jù)類型為DataType 操作集合操作集合: (1) ListInitiate(L) 初始化線性表初始化線性表 (2) ListLength(L) 求當前數(shù)據(jù)元素個數(shù)求當前數(shù)據(jù)元素個數(shù) (3) ListInsert(L,i,x) 插入數(shù)據(jù)元素插入數(shù)據(jù)元素 (4) ListDelete(L,i,x) 刪除數(shù)據(jù)元素刪除數(shù)據(jù)元素 (5) ListGet(L,i,x) 取數(shù)據(jù)元素取數(shù)據(jù)元素 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 2.22.2 線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn) 1.順序表的存儲結(jié)構(gòu)順序表的存儲結(jié)構(gòu) 實現(xiàn)順序

3、存儲結(jié)構(gòu)的方法是使用數(shù)組。數(shù)組把線性表的實現(xiàn)順序存儲結(jié)構(gòu)的方法是使用數(shù)組。數(shù)組把線性表的 數(shù)據(jù)元素存儲在一塊連續(xù)地址空間的內(nèi)存單元中，這樣線性數(shù)據(jù)元素存儲在一塊連續(xù)地址空間的內(nèi)存單元中，這樣線性 表中邏輯上相鄰的數(shù)據(jù)元素在物理存儲地址上也相鄰。數(shù)據(jù)表中邏輯上相鄰的數(shù)據(jù)元素在物理存儲地址上也相鄰。數(shù)據(jù) 元素間的邏輯上的前驅(qū)、后繼邏輯關系就表現(xiàn)在數(shù)據(jù)元素的元素間的邏輯上的前驅(qū)、后繼邏輯關系就表現(xiàn)在數(shù)據(jù)元素的 存儲單元的物理前后位置上。存儲單元的物理前后位置上。 順序表的存儲結(jié)構(gòu)如圖所示順序表的存儲結(jié)構(gòu)如圖所示 順序存儲結(jié)構(gòu)的順序存儲結(jié)構(gòu)的線性表稱作順序表線性表稱作順序表 數(shù)據(jù)結(jié)構(gòu)C語言版第02章

4、a0a1a2a3a4a5 list size=6 MaxSize-1 0 1 2 3 4 5 6 其中其中a0 ,a1, a2等表示順序表中存儲的數(shù)據(jù)元素，等表示順序表中存儲的數(shù)據(jù)元素，list表示表示 順序表存儲數(shù)據(jù)元素的數(shù)組，順序表存儲數(shù)據(jù)元素的數(shù)組，MaxSize表示存儲順序表的數(shù)表示存儲順序表的數(shù) 組的最大存儲單元個數(shù)，組的最大存儲單元個數(shù)，size表示順序表當前存儲的數(shù)據(jù)元表示順序表當前存儲的數(shù)據(jù)元 素個數(shù)。素個數(shù)。 typedef struct DataType listMaxSize; int size; SeqList; 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 2.順序表操作的實現(xiàn)順序表操作

5、的實現(xiàn) （1）初始化）初始化ListInitiate(L) void ListInitiate(SeqList *L) L-size = 0;/*定義初始數(shù)據(jù)元素個數(shù)定義初始數(shù)據(jù)元素個數(shù)*/ （2）求當前數(shù)據(jù)元素個數(shù)）求當前數(shù)據(jù)元素個數(shù)ListLength(L) int ListLength(SeqList L) return L.size; 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 （3）插入數(shù)據(jù)元素插入數(shù)據(jù)元素ListInsert(L, i, x) int ListInsert(SeqList *L, int i, DataType x) int j; for(j = L-size; j i; j-) L

6、-listj = L-listj-1; / /* *依次后移依次后移* */ / L-listi = x; /*插入插入x*/ L-size +; /*元素個數(shù)加元素個數(shù)加1*/ return 1; 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 101112141516list list MaxSize-1 0123456 i=3 Size=6 size=7 13待插數(shù)據(jù) x 7 10111213141516 MaxSize-1 01234567 i=3size=6 . . 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 （4 4）刪除數(shù)據(jù)元素刪除數(shù)據(jù)元素ListDelete(L, i, x)ListDelete(L, i, x) i

7、nt ListDelete(SeqList *L, int i, DataType *x) int j; *x = L-listi;/ /* *保存刪除的元素到保存刪除的元素到x x中中* */ / for(j = i +1; j size-1; j+) L-listj-1 = L-listj; / /* *依次前移依次前移* */ / L-size-;/ /* *數(shù)據(jù)元素個數(shù)減數(shù)據(jù)元素個數(shù)減1 1* */ / return 1; 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 10111213141516list 刪 除 前 101112141516list 刪 除 后 MaxSize-1 01234 56 Ma

8、xSize-1 0123456 i=3 size=7 size=6 要 刪 的 數(shù) 據(jù) x13 . . 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 （5 5）取數(shù)據(jù)元素）取數(shù)據(jù)元素ListGet(L, i, x)ListGet(L, i, x) int ListGet(SeqList L, int i, DataType *x) if(i L.size-1) printf(參數(shù)參數(shù)i不合法不合法! n); return 0; else *x = L.listi; return 1; 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 3.順序表操作的效率分析順序表操作的效率分析 時間效率分析時間效率分析: 算法時間主要耗費在移動元素的操

9、作上，因此計算時間復算法時間主要耗費在移動元素的操作上，因此計算時間復 雜度的基本操作雜度的基本操作(最深層語句頻度最深層語句頻度) T(n)= O(移動元素次數(shù)移動元素次數(shù)) 而移動元素的個數(shù)取決于插入或刪除元素的位置而移動元素的個數(shù)取決于插入或刪除元素的位置i. 若若i=size，則根本無需移動（特別快）；則根本無需移動（特別快）； 若若i=0，則表中元素全部要后移（特別慢）；則表中元素全部要后移（特別慢）； 應當考慮在各種位置插入（共應當考慮在各種位置插入（共n+1種可能）的平均移動次種可能）的平均移動次 數(shù)才合理。數(shù)才合理。 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 設設Pi是在第是在第i個存儲位置插

10、入一個數(shù)據(jù)元素的概率，順序表個存儲位置插入一個數(shù)據(jù)元素的概率，順序表 中的數(shù)據(jù)元素個數(shù)為中的數(shù)據(jù)元素個數(shù)為n,當在順序表的任何位置上插入數(shù)據(jù)當在順序表的任何位置上插入數(shù)據(jù) 元素的概率相等時，有元素的概率相等時，有Pi=1/(n+1),則則 插入時的平均移動次數(shù)為插入時的平均移動次數(shù)為: : n(n+1)/2（n+1）n/2 同理可證同理可證: :順序表刪除一元素的時間效率為順序表刪除一元素的時間效率為: : T（n)=(n-1)/2 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 插入效插入效 率：率： 刪除效刪除效 率：率： 00 1 ()() 12 nn isi ii n Ep nini n 11 00 11

11、()() 2 nn dli ii n Eq nini n 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 順序表中的其余操作都和數(shù)據(jù)元素個數(shù)順序表中的其余操作都和數(shù)據(jù)元素個數(shù)n無關，因此，在無關，因此，在 順序表中插入和刪除一個數(shù)據(jù)元素的時間復雜度為順序表中插入和刪除一個數(shù)據(jù)元素的時間復雜度為O(n),其余其余 操作的時間復雜度都為操作的時間復雜度都為O(1) 主要優(yōu)點是算法簡單，空間單元利用率高；主要優(yōu)點是算法簡單，空間單元利用率高； 主要缺點是需要預先確定數(shù)據(jù)元素的最大主要缺點是需要預先確定數(shù)據(jù)元素的最大 個數(shù)，插入和刪除時需要移動較多的數(shù)據(jù)個數(shù)，插入和刪除時需要移動較多的數(shù)據(jù) 元素。元素。 主要優(yōu)缺點主要優(yōu)缺

12、點 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 4.順序表應用舉例順序表應用舉例 例：編程實現(xiàn)如下任務例：編程實現(xiàn)如下任務: :建立一個線性表，首先依次建立一個線性表，首先依次 輸入數(shù)據(jù)元素輸入數(shù)據(jù)元素1 1，2 2，3 3，1010，然后刪除數(shù)據(jù)元素，然后刪除數(shù)據(jù)元素5 5，最，最 后依次顯示當前線性表中的數(shù)據(jù)元素。要求采用順序表實后依次顯示當前線性表中的數(shù)據(jù)元素。要求采用順序表實 現(xiàn)，假設該順序表的數(shù)據(jù)元素個數(shù)在最壞情況下不會超過現(xiàn)，假設該順序表的數(shù)據(jù)元素個數(shù)在最壞情況下不會超過 100100個。個。 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 實現(xiàn)方法：實現(xiàn)方法： 1 1、采用直接編寫一個主函數(shù)實現(xiàn)。、采用直接編寫一個主函

13、數(shù)實現(xiàn)。 2 2、利用已設計實現(xiàn)的抽象數(shù)據(jù)類型模塊。（存放在頭文件名、利用已設計實現(xiàn)的抽象數(shù)據(jù)類型模塊。（存放在頭文件名 為為SeqList.hSeqList.h中，通過中，通過 # #include “SeqList.h” include “SeqList.h” ） 程序設計如下：程序設計如下： #include #define MaxSize 100 typedef int DataType; #include SeqList.h 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 void main(void) SeqList myList; int i , x; ListInitiate( for(i = 0;

14、 i 10; i+) ListInsert( ListDelete( for(i = 0; i next = NULL;head)-next = NULL; 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 （2 2）求當前數(shù)據(jù)元素個數(shù)求當前數(shù)據(jù)元素個數(shù)ListLength(head)ListLength(head) int ListLength(SLNode *head) SLNode *p = head; int size = 0; while(p-next != NULL) p = p-next; size +; return size; 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 head. 0 a 1 a 1n a size

15、=0 (a) . 0 a 1 a 1n a size=n (b) p p head 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 （3 3）插入插入ListInsert(head, i, x)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+; if(j != i - 1) printf(“插入位置參數(shù)錯！插入位置參數(shù)錯！”); return 0; q = (SLNode *)malloc(size

16、of(SLNode); q-data = x; q-next = p-next; p-next = q; return 1; 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 0 a. i a 1n a qx . 1i a 0 a . i a 1n a . 1i a xq (a) (c) (b) p p head head 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 說明：要在帶頭結(jié)點的單鏈表第說明：要在帶頭結(jié)點的單鏈表第i i（0 i size0 i size） 個結(jié)點前插入一個存放數(shù)據(jù)元素個結(jié)點前插入一個存放數(shù)據(jù)元素x x的結(jié)點，首先要在單鏈的結(jié)點，首先要在單鏈 表中尋找到第表中尋找到第i-1i-1個結(jié)點并由指針個結(jié)點并由指針p

17、p指示，然后動態(tài)申請指示，然后動態(tài)申請 一個結(jié)點存儲空間并由指針一個結(jié)點存儲空間并由指針q q指示，并把數(shù)據(jù)元素指示，并把數(shù)據(jù)元素x x的值的值 賦予新結(jié)點的數(shù)據(jù)元素域（即賦予新結(jié)點的數(shù)據(jù)元素域（即q-data = xq-data = x），），最后修改最后修改 新結(jié)點的指針域指向新結(jié)點的指針域指向a ai i結(jié)點（即結(jié)點（即q-next = p-nextq-next = p-next），）， 并修改并修改a ai-1 i-1結(jié)點的指針域指向新結(jié)點 結(jié)點的指針域指向新結(jié)點q q（即即p-next = qp-next = q）。）。 循環(huán)條件由兩個子條件邏輯與組成，其中子條件循環(huán)條件由兩個子條件

18、邏輯與組成，其中子條件p-p- next != NULLnext != NULL保證指針所指結(jié)點存在，子條件保證指針所指結(jié)點存在，子條件j i - j next != NULL j+; if(j != i - 1) if(j != i - 1) printf(“ printf(“插入位置參數(shù)錯！插入位置參數(shù)錯！”);); return 0; return 0; s = p-next; *x = s-data; p-next = p-next-next; free(s); return 1; 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 0 a. i a 1n a . 1i a (a) 0 a. 1n a . 1i

19、 a (b) i ai a s head head p 1i a 1i a p 說明：要在帶頭結(jié)點的單鏈表中刪除第說明：要在帶頭結(jié)點的單鏈表中刪除第i i（0 i size - 10 i size - 1） 個結(jié)點，首先要在單鏈表中尋找到第個結(jié)點，首先要在單鏈表中尋找到第i-1i-1個結(jié)點并由指針個結(jié)點并由指針p p指示，指示， 然后讓指針然后讓指針s s指向指向a ai i結(jié)點（即結(jié)點（即s = p-nexts = p-next），），并把數(shù)據(jù)元素并把數(shù)據(jù)元素a ai i 的值賦予的值賦予x x（即即* *x = s-datax = s-data），），最后把最后把a ai i結(jié)點脫鏈（即結(jié)

20、點脫鏈（即p-p- next = p-next-nextnext = p-next-next），），并動態(tài)釋放并動態(tài)釋放a ai i結(jié)點的存儲空間（即結(jié)點的存儲空間（即 free(s)free(s)）。）。刪除過程如圖刪除過程如圖2-142-14所示。圖中的對應算法中的刪所示。圖中的對應算法中的刪 除語句。除語句。 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 （5 5）取數(shù)據(jù)元素）取數(shù)據(jù)元素ListGet(head, i, x)ListGet(head, i, x) int ListGet(SLNode *head, int i, DataType *x) SLNode *p; int j; p = head;

21、 j = -1; while(p-next != NULL j+; if(j != i) printf(“取元素位置參數(shù)錯！取元素位置參數(shù)錯！”); return 0; *x = p-data; return 1; 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 （6 6）撤消單鏈表撤消單鏈表Destroy(head)Destroy(head) void Destroy(SLNode *head) SLNode *p, *p1; p = *head; while(p != NULL) p1 = p; p = p-next; free(p1); *head = NULL; 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 00 1 ()()

22、 12 nn isi ii n Ep nini n 11 00 11 ()() 2 nn dli ii n Eq nini n 4.單鏈表操作的效率分析單鏈表操作的效率分析 單鏈表的插入和刪除操作不需移動數(shù)據(jù)元素，只需比較數(shù)據(jù)單鏈表的插入和刪除操作不需移動數(shù)據(jù)元素，只需比較數(shù)據(jù) 元素。因此，當在單鏈表的任何位置上插入數(shù)據(jù)元素的概率元素。因此，當在單鏈表的任何位置上插入數(shù)據(jù)元素的概率 相等時，在單鏈表中插入一個數(shù)據(jù)元素時比較數(shù)據(jù)元素的平相等時，在單鏈表中插入一個數(shù)據(jù)元素時比較數(shù)據(jù)元素的平 均次數(shù)為：均次數(shù)為： 刪除一個數(shù)據(jù)元素時比較數(shù)據(jù)元素的平均次數(shù)為：刪除一個數(shù)據(jù)元素時比較數(shù)據(jù)元素的平均次數(shù)為

23、： 另外，單鏈表求數(shù)據(jù)元素個數(shù)操作的時間復雜度為另外，單鏈表求數(shù)據(jù)元素個數(shù)操作的時間復雜度為O(n)。 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 和順序表相比和順序表相比 主要優(yōu)點是不需要預先確定數(shù)據(jù)元素的最大主要優(yōu)點是不需要預先確定數(shù)據(jù)元素的最大 個數(shù)，插入和刪除操作不需要移動數(shù)據(jù)元素；個數(shù)，插入和刪除操作不需要移動數(shù)據(jù)元素； 主要缺點是因為是順序存儲結(jié)構(gòu)，所以，查主要缺點是因為是順序存儲結(jié)構(gòu)，所以，查 找數(shù)據(jù)元素時需要順序進行，不能像順序表找數(shù)據(jù)元素時需要順序進行，不能像順序表 那樣隨機查找任意一個數(shù)據(jù)元素。另外，每那樣隨機查找任意一個數(shù)據(jù)元素。另外，每 個結(jié)點中要有一個指針域，因此空間單元利個結(jié)點中要有

24、一個指針域，因此空間單元利 用率不高。而且單鏈表操作的算法也較復雜。用率不高。而且單鏈表操作的算法也較復雜。 單鏈表單鏈表 和單鏈表相比，順序表的優(yōu)點和缺點正好相反。和單鏈表相比，順序表的優(yōu)點和缺點正好相反。 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 5.單鏈表應用舉例單鏈表應用舉例 例：編程實現(xiàn)如下任務例：編程實現(xiàn)如下任務: :建立一個線性表，首先依次輸入建立一個線性表，首先依次輸入 數(shù)據(jù)元素數(shù)據(jù)元素1 1，2 2，3 3，1010，然后刪除數(shù)據(jù)元素，然后刪除數(shù)據(jù)元素5 5，最后依次，最后依次 顯示當前線性表中的數(shù)據(jù)元素。要求采用單鏈表實現(xiàn)。顯示當前線性表中的數(shù)據(jù)元素。要求采用單鏈表實現(xiàn)。 #include

25、 #include #include typedef int DataType; #include LinList.h 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 void main(void) SLNode *head; int i , x; ListInitiate( for(i = 0; i 10; i+) ListInsert(head, i, i+1) ; ListDelete(head, 4, for(i = 0; i !=NULL改為改為 p-!=head 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 2.5 2.5 雙向鏈表雙向鏈表 雙向鏈表是每個結(jié)點除后繼指針域外還有一個前驅(qū)指雙向鏈表是每個結(jié)點除后繼指針域外還有

26、一個前驅(qū)指 針域，它有帶頭結(jié)點和不帶頭結(jié)點，循環(huán)和非循環(huán)結(jié)構(gòu)，針域，它有帶頭結(jié)點和不帶頭結(jié)點，循環(huán)和非循環(huán)結(jié)構(gòu)， 雙向鏈表是解決查找前驅(qū)結(jié)點問題的有效途徑。雙向鏈表是解決查找前驅(qū)結(jié)點問題的有效途徑。 結(jié)點結(jié)構(gòu)如圖示：結(jié)點結(jié)構(gòu)如圖示： prior data next 下圖是帶頭結(jié)點的循環(huán)雙向鏈表的結(jié)構(gòu)，可見，其前驅(qū)指下圖是帶頭結(jié)點的循環(huán)雙向鏈表的結(jié)構(gòu)，可見，其前驅(qū)指 針和后繼指針各自構(gòu)成自己的循環(huán)單鏈表。針和后繼指針各自構(gòu)成自己的循環(huán)單鏈表。 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 head (a) 空鏈表空鏈表 a0a1an-1 head (b) 非空鏈表非空鏈表 在雙向鏈表中在雙向鏈表中: 設指針設指針p

27、指向第指向第i個數(shù)據(jù)元素結(jié)點，則個數(shù)據(jù)元素結(jié)點，則p-next指向第指向第i+1 個數(shù)據(jù)元素結(jié)點，個數(shù)據(jù)元素結(jié)點，p-next-prior仍指向第仍指向第i個數(shù)據(jù)元素結(jié)點，個數(shù)據(jù)元素結(jié)點， 即即p-next-prior=p;同樣同樣p-prior-next=p。 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 循環(huán)雙向鏈表的插入過程如圖示：循環(huán)雙向鏈表的插入過程如圖示： a0aian-1 head xs ai-1 p 刪除過程如圖示：刪除過程如圖示： ai+1aian-1 head ai-1 p 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 2.6 2.6 靜態(tài)鏈表靜態(tài)鏈表 在數(shù)組中增加一個在數(shù)組中增加一個(或兩個或兩個)指針域用來存

28、放下一個指針域用來存放下一個(或上一個或上一個) 數(shù)據(jù)元素在數(shù)組中的下標，從而構(gòu)成用數(shù)組構(gòu)造的單鏈表。數(shù)據(jù)元素在數(shù)組中的下標，從而構(gòu)成用數(shù)組構(gòu)造的單鏈表。 因為數(shù)組內(nèi)存空間的申請方式是靜態(tài)的，所以稱為靜態(tài)鏈表，因為數(shù)組內(nèi)存空間的申請方式是靜態(tài)的，所以稱為靜態(tài)鏈表， 增加的指針稱做仿真指針。結(jié)構(gòu)如下：增加的指針稱做仿真指針。結(jié)構(gòu)如下： ABCE head D (a) 常規(guī)鏈表常規(guī)鏈表 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 A1 B2 C3 D4 E-1 (b) 靜態(tài)鏈表靜態(tài)鏈表1 data next 0 1 2 3 4 maxSize-1 A2 E-1 B4 D1 C3 (b) 靜態(tài)鏈表靜態(tài)鏈表2 data

29、 next 0 1 2 3 4 maxSize-1 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 2.7 2.7 設計舉例設計舉例 例例2-4 設計一個順序表的刪除函數(shù)，把順序表設計一個順序表的刪除函數(shù)，把順序表L中的數(shù)據(jù)元中的數(shù)據(jù)元 素素x刪除。刪除。 算法思想：此刪除問題可通過一個循環(huán)比較過程來實算法思想：此刪除問題可通過一個循環(huán)比較過程來實 現(xiàn)?，F(xiàn)。 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 int ListDataDelete(SeqList *L, DataType x) int i, j; for(i = 0; i size; i+) if(x = L-listi) break; if(i = L-size) ret

30、urn 0; else for(j = i; j size; j+) L-listj = L-listj+1; L-size-; return 1; 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 例例2-5 構(gòu)造一個順序表的刪除算法，把順序表構(gòu)造一個順序表的刪除算法，把順序表L中所有值相中所有值相 同的數(shù)據(jù)元素同的數(shù)據(jù)元素x全部刪除。全部刪除。 算法思想：此刪除問題是在例算法思想：此刪除問題是在例2-4所設計的刪除算法的所設計的刪除算法的 基礎上再增加一重循環(huán)，來實現(xiàn)值相同數(shù)據(jù)元素基礎上再增加一重循環(huán)，來實現(xiàn)值相同數(shù)據(jù)元素x的全部刪的全部刪 除。除。 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 int ListMoreDataDe

31、lete(SeqList *L, DataType 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; 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 例例2-6設頭指針為設頭指針為head，并設帶頭結(jié)點單鏈表中的數(shù)據(jù)元素并設帶頭結(jié)點單鏈表中的數(shù)據(jù)元素 遞增有序，編寫算法將數(shù)據(jù)元素遞增有序，編寫算法將數(shù)據(jù)元素x插入到帶頭結(jié)點單鏈表的插入到帶頭結(jié)點單鏈表的 適當位置上，要求插入后保持

32、單鏈表數(shù)據(jù)元素的遞增有序。適當位置上，要求插入后保持單鏈表數(shù)據(jù)元素的遞增有序。 算法思想：從鏈表的第一個數(shù)據(jù)元素結(jié)點開始，逐個比較算法思想：從鏈表的第一個數(shù)據(jù)元素結(jié)點開始，逐個比較 每個結(jié)點的每個結(jié)點的data域值和域值和x的值，當?shù)闹?，當data小于等于小于等于x時，進行時，進行 下一個結(jié)點的比較；否則就找到了插入結(jié)點的合適位置，下一個結(jié)點的比較；否則就找到了插入結(jié)點的合適位置， 此時申請新結(jié)點把此時申請新結(jié)點把x存入，然后把新結(jié)點插入；當比較到最存入，然后把新結(jié)點插入；當比較到最 后一個結(jié)點仍有后一個結(jié)點仍有data小于等于小于等于x時，則把新結(jié)點插入單鏈表時，則把新結(jié)點插入單鏈表 尾。尾

33、。 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 void LinListInsert(SLNode *head, DataType x) SLNode *curr, *pre, *q; curr = head-next; pre = head; while(curr != NULL q = (SLNode *)malloc(sizeof(SLNode); q-data = x; q-next = pre-next; pre-next = q; 數(shù)據(jù)結(jié)構(gòu)C語言版第02章 算法設計說明：算法設計說明： （1）在循環(huán)定位插入位置時，循環(huán)條件必須首先是）在循環(huán)定位插入位置時，循環(huán)條件必須首先是curr != NULL，然后是然后是curr-data data不