數(shù)據(jù)結(jié)構(gòu)——使用C語言版(朱戰(zhàn)立)線性表

1、第第2章線性表章線性表主要知識點主要知識點線性表抽象數(shù)據(jù)類型線性表抽象數(shù)據(jù)類型順序表順序表循環(huán)單鏈表循環(huán)單鏈表循環(huán)雙向鏈表循環(huán)雙向鏈表靜態(tài)鏈表靜態(tài)鏈表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)。線性結(jié)構(gòu)線性結(jié)構(gòu):2.2.線性表抽象數(shù)據(jù)類型線性表抽象數(shù)據(jù)類型數(shù)據(jù)數(shù)據(jù): a0, a1, , an-1 , ai的數(shù)據(jù)類型為的數(shù)據(jù)類型為DataType操作操作:

2、(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ù)元素 a0, a1, , an-1 表示數(shù)據(jù)元素有次序關(guān)系表示數(shù)據(jù)元素有次序關(guān)系,簡稱序列。簡稱序列。2.22.2 線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn)1.順序表的存儲結(jié)構(gòu)順序表的存儲結(jié)構(gòu) 實現(xiàn)順序存儲結(jié)構(gòu)的方法是實現(xiàn)順序存儲結(jié)構(gòu)的方法是使用數(shù)組使用數(shù)組。數(shù)組把線性

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

4、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;2.順序表操作的實現(xiàn)順序表操作的實現(xiàn) （1）初始化）初始化ListInitiate(L)void ListInitiate(SeqList *L) L-size = 0;/定義初

5、始數(shù)據(jù)元素個數(shù)定義初始數(shù)據(jù)元素個數(shù) （2）求當前數(shù)據(jù)元素個數(shù)）求當前數(shù)據(jù)元素個數(shù)ListLength(L)int ListLength(SeqList L) return L.size; （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-listj = L-listj-1; / / /依次后移依次后移L-listi = x; /插入插入xL-size +; /元素個數(shù)加元素個數(shù)加1return 1; int List

6、Insert(SeqList int ListInsert(SeqList * *L, int i, DataType x)L, int i, DataType x)int j;int j; if(L-size = MaxSize) if(L-size = MaxSize) printf( printf(順序表已滿無法插入順序表已滿無法插入! n);! n); return 0; return 0; else if(i L-size ) else if(i L-size ) printf( printf(參數(shù)參數(shù)i i不合法不合法! n);! n); return 0; return 0; e

7、lse else for(j = L-size; j i; j-) for(j = L-size; j i; j-) L-listj = L-listj-1; L-listj = L-listj-1;L-listi = x;L-listi = x;L-size +;L-size +; return 1; return 1; 101112141516listlistMaxSize-10123456i=3Size=6size=713待插數(shù)據(jù) x710111213141516MaxSize-101234567i=3size=6.（4 4）刪除數(shù)據(jù)元素刪除數(shù)據(jù)元素ListDelete(L, i, x)

8、ListDelete(L, i, x)int 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; int ListDelete(SeqList int ListDelete(SeqList * *L, int i, DataType L, int i, DataType * *x

9、)x) int j;int j;if(L-size size = 0) printf( printf(順序表已空無數(shù)據(jù)元素可刪順序表已空無數(shù)據(jù)元素可刪! n);! n); return 0; return 0; else if(i L-size-1)else if(i L-size-1) printf( printf(參數(shù)參數(shù)i i不合法不合法);); return 0; return 0; elseelse* *x = L-listi;x = L-listi;for(j = i +1; j size-1; j+)for(j = i +1; j size-1; j+) L-listj-1 =

10、L-listj; L-listj-1 = L-listj;L-size-;L-size-;return 1; return 1; 10111213141516list刪 除 前101112141516list刪 除 后MaxSize-10123456MaxSize-10123456i=3size=7size=6要 刪 的 數(shù) 據(jù) x13.（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);

11、return 0; else *x = L.listi; return 1; 3.順序表操作的效率分析順序表操作的效率分析時間效率分析時間效率分析:算法時間主要耗費在移動元素的操作上算法時間主要耗費在移動元素的操作上 T(n)= O(移動元素次數(shù)移動元素次數(shù)) 而移動元素的個數(shù)取決于插入或刪除元素的位置而移動元素的個數(shù)取決于插入或刪除元素的位置i.若若i=size，則根本無需移動（特別快）；則根本無需移動（特別快）；若若i=0，則表中元素全部要后移（特別慢）；則表中元素全部要后移（特別慢）；應當考慮在各種位置插入（共應當考慮在各種位置插入（共n+1種可能）的平均移動次種可能）的平均移動次數(shù)才合

12、理。數(shù)才合理。 設設Pi是在第是在第i個存儲位置插入一個數(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 001()()12nnisiiinEp n in in110011()()2nndliiinEq ninin 順序表中的

13、其余操作都和數(shù)據(jù)元素個數(shù)順序表中的其余操作都和數(shù)據(jù)元素個數(shù)n無關(guān)，因此，在無關(guā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)缺點4.順序表應用舉例順序表應用舉例 例：編程實現(xiàn)如下任務例：編程實現(xiàn)如下任務: :建立一個線性表，首先依次建

14、立一個線性表，首先依次輸入數(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個。個。實現(xiàn)方法：實現(xiàn)方法：1 1、采用直接編寫一個主函數(shù)實現(xiàn)。、采用直接編寫一個主函數(shù)實現(xiàn)。2 2、利用已設計實現(xiàn)的抽象數(shù)據(jù)類型模塊。（存放在頭文件名、利用已設計實現(xiàn)的抽象數(shù)據(jù)類型模塊。（存放在頭文件名為為SeqList.hSeqList.h中，通過中，通過

15、 # #include include “SeqList.hSeqList.h” ）程序設計如下：程序設計如下：#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 = 0; i next

16、 = NULL;head)-next = NULL; （2）求當前數(shù)據(jù)元素個數(shù)求當前數(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; head.0a1a1na size=0(a).0a1a1na size=n(b)pphead（3）插入插入ListInsert(head, i, x)int ListInsert(SLNode *head, int i, DataType

17、x) SLNode *p, *q; int j; p = head; j = -1; while(p-next != NULL & j next; j+; if(j != i - 1) printf(“插入位置參數(shù)錯！插入位置參數(shù)錯！”); return 0; q = (SLNode *)malloc(sizeof(SLNode); q-data = x; q-next = p-next; p-next = q; return 1;0a.ia1na qx.1ia0a.ia1na .1iaxq(a)(c)(b)ppheadhead 說明：要在帶頭結(jié)點的單鏈表第說明：要在帶頭結(jié)點的單鏈表第

18、i（0 i size）個結(jié)點前插入一個存放數(shù)據(jù)元素個結(jié)點前插入一個存放數(shù)據(jù)元素x的結(jié)點，的結(jié)點，首先首先要在單鏈表中尋找到第要在單鏈表中尋找到第i-1個結(jié)點并由指針個結(jié)點并由指針p指示，指示，然后然后動態(tài)申請一個結(jié)點存儲空間并由指針動態(tài)申請一個結(jié)點存儲空間并由指針q指示，指示，并把數(shù)據(jù)元素并把數(shù)據(jù)元素x的值賦予新結(jié)點的數(shù)據(jù)元素域的值賦予新結(jié)點的數(shù)據(jù)元素域（即（即q-data = x），），最后最后修改新結(jié)點的指針域指修改新結(jié)點的指針域指向向ai結(jié)點（即結(jié)點（即q-next = p-next），），并修改并修改ai-1結(jié)結(jié)點的指針域指向新結(jié)點點的指針域指向新結(jié)點q（即即p-next = q）。）

19、。循環(huán)條件由兩個子條件邏輯與組成，其中子條循環(huán)條件由兩個子條件邏輯與組成，其中子條件件p-next != NULL保證指針所指結(jié)點存在，子保證指針所指結(jié)點存在，子條件條件j next != NULL & p-next-next!= NULL & j next;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; 0a

20、.ia1na .1ia(a)0a.1na .1ia(b)iaiasheadheadp 1ia1iap說明：要在帶頭結(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é)

21、點脫鏈（即結(jié)點脫鏈（即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所示。圖中的對應算法中的刪所示。圖中的對應算法中的刪除語句。除語句。（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; j = -1; wh

22、ile(p-next != NULL & j next;j+; if(j != i) printf(“取元素位置參數(shù)錯！取元素位置參數(shù)錯！”); return 0; *x = p-data; return 1; （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;001()()12nnisiiinEp ninin110011()()

23、2nndliiinEq ninin4.單鏈表操作的效率分析單鏈表操作的效率分析單鏈表的插入和刪除操作不需移動數(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ù)為：另外，單鏈表求數(shù)據(jù)元素個數(shù)操作的時間復雜度為另外，單鏈表求數(shù)據(jù)元素個數(shù)操作的時間復雜度為O(n)。和順

24、序表相比和順序表相比主要優(yōu)點是不需要預先確定數(shù)據(jù)元素的最大主要優(yōu)點是不需要預先確定數(shù)據(jù)元素的最大個數(shù)，插入和刪除操作不需要移動數(shù)據(jù)元素；個數(shù)，插入和刪除操作不需要移動數(shù)據(jù)元素；主要缺點是查找數(shù)據(jù)元素時需要順序進行，主要缺點是查找數(shù)據(jù)元素時需要順序進行，不能像順序表那樣隨機查找任意一個數(shù)據(jù)元不能像順序表那樣隨機查找任意一個數(shù)據(jù)元素。另外，每個結(jié)點中要有一個指針域，因素。另外，每個結(jié)點中要有一個指針域，因此空間單元利用率不高。而且單鏈表操作的此空間單元利用率不高。而且單鏈表操作的算法也較復雜。算法也較復雜。單鏈表單鏈表和順序表相比，單鏈表的優(yōu)點和缺點正好相反。和順序表相比，單鏈表的優(yōu)點和缺點正好相

25、反。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 #include #include typedef int DataType;#include LinList.h void main(void) SLNode *head; int i , x; ListInitiate(&h

26、ead); for(i = 0; i 10; i+) ListInsert(head, i, i+1) ; ListDelete(head, 4, &x) ; for(i = 0; i next!=NULL改為改為 p- next != head練習：編寫一個算法，逐個輸出循環(huán)單鏈表中所有數(shù)據(jù)元素。練習：編寫一個算法，逐個輸出循環(huán)單鏈表中所有數(shù)據(jù)元素。（假設是帶頭結(jié)點的循環(huán)單鏈表）（假設是帶頭結(jié)點的循環(huán)單鏈表）void DispList(SLNode ) SLNode *q; q = h-next; while(q!= ) printf(“ %dn”,q-data); ; void D

27、ispList(SLNode *h ) SLNode *q; q = h-next; while(q!= h ) printf(“ %dn”,q-data); q=q-next ; 提問：提問：假設是不帶頭結(jié)點的循環(huán)單鏈表，如何修改上述算法。假設是不帶頭結(jié)點的循環(huán)單鏈表，如何修改上述算法。2.5 2.5 雙向鏈表雙向鏈表 雙向鏈表是每個結(jié)點除后繼指針域外還有一個前驅(qū)指雙向鏈表是每個結(jié)點除后繼指針域外還有一個前驅(qū)指針域，它有帶頭結(jié)點和不帶頭結(jié)點，循環(huán)和非循環(huán)結(jié)構(gòu)，針域，它有帶頭結(jié)點和不帶頭結(jié)點，循環(huán)和非循環(huán)結(jié)構(gòu)，雙向鏈表是解決查找前驅(qū)結(jié)點問題的有效途徑。雙向鏈表是解決查找前驅(qū)結(jié)點問題的有效途徑。

28、結(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)單鏈表。head(a) 空鏈表空鏈表a0a1an-1head(b) 非空鏈表非空鏈表在雙向鏈表中在雙向鏈表中: 設指針設指針p指向第指向第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-

29、next=p。循環(huán)雙向鏈表的循環(huán)雙向鏈表的插入過程插入過程如圖示：如圖示：a0aian-1headxsai-1 p刪除過程刪除過程如圖示：如圖示：ai+1aian-1headai-1p 練習：已知練習：已知p p結(jié)點是雙向鏈表的中間結(jié)點，試從下列提供的答結(jié)點是雙向鏈表的中間結(jié)點，試從下列提供的答案中選擇合適的語句序列。案中選擇合適的語句序列。(1)p-next=p-next-next; (2)p-prior=p-prior-prior;(1)p-next=p-next-next; (2)p-prior=p-prior-prior;(3)p-next=s; (4)p-prior=s; (5)s-

30、next=p;(3)p-next=s; (4)p-prior=s; (5)s-next=p;(6)s-prior=p; (7)s-next=p-next; (8)s-prior=p-prior;(6)s-prior=p; (7)s-next=p-next; (8)s-prior=p-prior;(9)p-prior-next=p-next; (10)p-prior-next=p;(9)p-prior-next=p-next; (10)p-prior-next=p;(11)p-next-prior=p; (12) p-next-prior=s; (11)p-next-prior=p; (12)

31、p-next-prior=s; (13)p-prior-next=s; (14)p-next-prior=p- prior;(13)p-prior-next=s; (14)p-next-prior=p- prior;(15)q=p-next; (16)q=p-prior; (17)free(p); (18)free(q);(15)q=p-next; (16)q=p-prior; (17)free(p); (18)free(q);a.a.在在p p結(jié)點后插入結(jié)點后插入s s結(jié)點的語句序列是結(jié)點的語句序列是 。 b.在在p p結(jié)點前插入結(jié)點前插入s s結(jié)點的語句序列是結(jié)點的語句序列是 。 c.c.

32、刪除刪除p p結(jié)點的直接后繼結(jié)點的語句序列是結(jié)點的直接后繼結(jié)點的語句序列是 。d.刪除刪除p p結(jié)點的直接前驅(qū)結(jié)點的語句序列是結(jié)點的直接前驅(qū)結(jié)點的語句序列是 。e.e.刪除刪除p p結(jié)點的的語句序列是結(jié)點的的語句序列是 。 2.6 2.6 靜態(tài)鏈表靜態(tài)鏈表在數(shù)組中增加一個在數(shù)組中增加一個(或兩個或兩個)指針域用來存放下一個指針域用來存放下一個(或上一個或上一個)數(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)鏈表，增加的指針稱做增加的指針

33、稱做仿真指針仿真指針。結(jié)構(gòu)如下：。結(jié)構(gòu)如下：ABCEheadD(a) 常規(guī)鏈表常規(guī)鏈表A1B2C3D4E-1(b) 靜態(tài)鏈表靜態(tài)鏈表1data next01234maxSize-1A2E-1B4D1C3(b) 靜態(tài)鏈表靜態(tài)鏈表2data next01234maxSize-12.7 2.7 設計舉例設計舉例例例2-4 設計一個順序表的刪除函數(shù)，把順序表設計一個順序表的刪除函數(shù)，把順序表L中的數(shù)中的數(shù)據(jù)元素據(jù)元素x刪除。刪除。算法思想：算法思想：首先首先，找到要刪除元素的位置，找到要刪除元素的位置，然后然后，從這，從這個位置到最后一個元素，逐個前移，個位置到最后一個元素，逐個前移，最后最后，把元素

34、個數(shù)，把元素個數(shù)減減1。int ListDataDelete( , ) int i, j; for(i = 0; i ; i+) if(x = ) break; if(i = ) return 0; else for(j = ; j ; j+) ; ; return 1; int ListDataDelete(SeqList *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

35、-listj+1; L-size-; return 1; 例例2-5 構(gòu)造一個順序表的刪除算法，把順序表構(gòu)造一個順序表的刪除算法，把順序表L中所有值相中所有值相同的數(shù)據(jù)元素同的數(shù)據(jù)元素x全部刪除。全部刪除。算法思想：在例算法思想：在例2-4所設計的刪除算法的基礎上，增加外重所設計的刪除算法的基礎上，增加外重循環(huán)進行查找，查找到元素循環(huán)進行查找，查找到元素x則刪除，然后繼續(xù)進行這樣的則刪除，然后繼續(xù)進行這樣的過程和刪除過程，直到元素末尾結(jié)束。過程和刪除過程，直到元素末尾結(jié)束。int ListMoreDataDelete(SeqList *L, DataType x) int i, j; int

36、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 設頭指針為設頭指針為head，并設帶頭結(jié)點單鏈表中的數(shù)據(jù)元并設帶頭結(jié)點單鏈表中的數(shù)據(jù)元素遞增有序，編寫算法將數(shù)據(jù)元素素遞增有序，編寫算法將數(shù)據(jù)元素x插入到帶頭結(jié)點單鏈表插入到帶頭結(jié)點單鏈表的適當位置上，要求插入后保持單鏈表數(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é)點插入；