1、第第2章線性表章線性表主要知識點主要知識點線性表抽象數據類型線性表抽象數據類型順序表順序表循環(huán)單鏈表循環(huán)單鏈表循環(huán)雙向鏈表循環(huán)雙向鏈表靜態(tài)鏈表靜態(tài)鏈表2.12.1 線性表抽象數據類型線性表抽象數據類型1.1.線性表的定義線性表的定義 線性表是一種可以在線性表是一種可以在任意位置插入任意位置插入和和刪除刪除數數據元素操作、由據元素操作、由n(n0)個相同類型數據元素個相同類型數據元素a0, a1, an-1組成的組成的線性結構線性結構。線性結構線性結構:2.2.線性表抽象數據類型線性表抽象數據類型數據數據: a0, a1, , an-1 , ai的數據類型為的數據類型為DataType操作操作:

2、(1) ListInitiate(L) 初始化線性表初始化線性表(2) ListLength(L) 求當前數據元素個數求當前數據元素個數(3) ListInsert(L,i,x) 插入數據元素插入數據元素(4) ListDelete(L,i,x) 刪除數據元素刪除數據元素(5) ListGet(L,i,x) 取數據元素取數據元素 a0, a1, , an-1 表示數據元素有次序關系表示數據元素有次序關系,簡稱序列。簡稱序列。2.22.2 線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn)1.順序表的存儲結構順序表的存儲結構 實現(xiàn)順序存儲結構的方法是實現(xiàn)順序存儲結構的方法是使用數組使用數組。數組把線性

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

4、a1, a2等表示順序表中存儲的數據元素，等表示順序表中存儲的數據元素，list表示表示順序表存儲數據元素的數組，順序表存儲數據元素的數組，MaxSize表示存儲順序表的數表示存儲順序表的數組的最大存儲單元個數，組的最大存儲單元個數，size表示順序表當前存儲的數據元表示順序表當前存儲的數據元素個數。素個數。 typedef struct DataType listMaxSize; int size; SeqList;2.順序表操作的實現(xiàn)順序表操作的實現(xiàn) （1）初始化）初始化ListInitiate(L)void ListInitiate(SeqList *L) L-size = 0;/定義初

5、始數據元素個數定義初始數據元素個數 （2）求當前數據元素個數）求當前數據元素個數ListLength(L)int ListLength(SeqList L) return L.size; （3）插入數據元素插入數據元素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 +; /元素個數加元素個數加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(參數參數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待插數據 x710111213141516MaxSize-101234567i=3size=6.（4 4）刪除數據元素刪除數據元素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-;/數據元素個數減數據元素個數減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(順序表已空無數據元素可刪順序表已空無數據元素可刪! n);! n); return 0; return 0; else if(i L-size-1)else if(i L-size-1) printf( printf(參數參數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要 刪 的 數 據 x13.（5 5）取數據元素）取數據元素ListGet(L, i, x)ListGet(L, i, x)int ListGet(SeqList L, int i, DataType *x) if(i L.size-1) printf(參數參數i不合法不合法! n);

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

12、理。數才合理。 設設Pi是在第是在第i個存儲位置插入一個數據元素的概率，順個存儲位置插入一個數據元素的概率，順序表中的數據元素個數為序表中的數據元素個數為n,當在順序表的任何位置上插入當在順序表的任何位置上插入數據元素的概率相等時，有數據元素的概率相等時，有Pi=1/(n+1),則則 插入時的平均移動次數為插入時的平均移動次數為: : n(n+1)/2（n+1）n/2同理可證同理可證: :順序表刪除一元素的時間效率為順序表刪除一元素的時間效率為: :T（n)=(n-1)/2 001()()12nnisiiinEp n in in110011()()2nndliiinEq ninin 順序表中的

13、其余操作都和數據元素個數順序表中的其余操作都和數據元素個數n無關，因此，在無關，因此，在順序表中插入和刪除一個數據元素的時間復雜度為順序表中插入和刪除一個數據元素的時間復雜度為O(n),其余其余操作的時間復雜度都為操作的時間復雜度都為O(1)主要優(yōu)點是算法簡單，空間單元利用率高；主要優(yōu)點是算法簡單，空間單元利用率高；主要缺點是需要預先確定數據元素的最大主要缺點是需要預先確定數據元素的最大個數，插入和刪除時需要移動較多的數據個數，插入和刪除時需要移動較多的數據元素。元素。主要優(yōu)缺點主要優(yōu)缺點4.順序表應用舉例順序表應用舉例 例：編程實現(xiàn)如下任務例：編程實現(xiàn)如下任務: :建立一個線性表，首先依次建

14、立一個線性表，首先依次輸入數據元素輸入數據元素1 1，2 2，3 3，1010，然后刪除數據元素，然后刪除數據元素5 5，最，最后依次顯示當前線性表中的數據元素。要求采用順序表實后依次顯示當前線性表中的數據元素。要求采用順序表實現(xiàn)，假設該順序表的數據元素個數在最壞情況下不會超過現(xiàn)，假設該順序表的數據元素個數在最壞情況下不會超過100100個。個。實現(xiàn)方法：實現(xiàn)方法：1 1、采用直接編寫一個主函數實現(xiàn)。、采用直接編寫一個主函數實現(xiàn)。2 2、利用已設計實現(xiàn)的抽象數據類型模塊。（存放在頭文件名、利用已設計實現(xiàn)的抽象數據類型模塊。（存放在頭文件名為為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）求當前數據元素個數求當前數據元素個數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(“插入位置參數錯！插入位置參數錯！”); 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 說明：要在帶頭結點的單鏈表第說明：要在帶頭結點的單鏈表第

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

19、。循環(huán)條件由兩個子條件邏輯與組成，其中子條循環(huán)條件由兩個子條件邏輯與組成，其中子條件件p-next != NULL保證指針所指結點存在，子保證指針所指結點存在，子條件條件j next != NULL & p-next-next!= NULL & j next;j+; if(j != i - 1) if(j != i - 1) printf(“ printf(“插入位置參數錯！插入位置參數錯！”);”); 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說明：要在帶頭結點的單鏈表中刪除第說明：要在帶頭結點的單鏈表中刪除第i i（0 i size - 10 i size - 1）個結點，個結點，首先首先要在單鏈表中尋找到第要在單鏈表中尋找到第i-1i-1個結點并由指針個結點并由指針p p指示指示，然后然后讓指針讓指針s s指向指向a ai i結點（即結點（即s = p-nexts = p-next），），并把數據元素并把數據元素a ai i的值賦予的值賦予x x（即即* *x = s-datax = s-data），），最后最后把把a ai i結

21、點脫鏈（即結點脫鏈（即p-p- next = p-next-nextnext = p-next-next），），并動態(tài)釋放并動態(tài)釋放a ai i結點的存儲空間（即結點的存儲空間（即free(s)free(s)）。）。刪除過程如圖刪除過程如圖2-142-14所示。圖中的對應算法中的刪所示。圖中的對應算法中的刪除語句。除語句。（5 5）取數據元素）取數據元素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(“取元素位置參數錯！取元素位置參數錯！”); 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.單鏈表操作的效率分析單鏈表操作的效率分析單鏈表的插入和刪除操作不需移動數據元素，只需比較數據單鏈表的插入和刪除操作不需移動數據元素，只需比較數據元素。因此，當在單鏈表的任何位置上插入數據元素的概率元素。因此，當在單鏈表的任何位置上插入數據元素的概率相等時，在單鏈表中插入一個數據元素時比較數據元素的平相等時，在單鏈表中插入一個數據元素時比較數據元素的平均次數為：均次數為：刪除一個數據元素時比較數據元素的平均次數為：刪除一個數據元素時比較數據元素的平均次數為：另外，單鏈表求數據元素個數操作的時間復雜度為另外，單鏈表求數據元素個數操作的時間復雜度為O(n)。和順

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

25、反。5.單鏈表應用舉例單鏈表應用舉例 例：編程實現(xiàn)如下任務例：編程實現(xiàn)如下任務: :建立一個線性表，首先依次輸入建立一個線性表，首先依次輸入數據元素數據元素1 1，2 2，3 3，1010，然后刪除數據元素，然后刪除數據元素5 5，最后依次，最后依次顯示當前線性表中的數據元素。要求采用單鏈表實現(xiàn)。顯示當前線性表中的數據元素。要求采用單鏈表實現(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)單鏈表中所有數據元素。練習：編寫一個算法，逐個輸出循環(huán)單鏈表中所有數據元素。（假設是帶頭結點的循環(huán)單鏈表）（假設是帶頭結點的循環(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 ; 提問：提問：假設是不帶頭結點的循環(huán)單鏈表，如何修改上述算法。假設是不帶頭結點的循環(huán)單鏈表，如何修改上述算法。2.5 2.5 雙向鏈表雙向鏈表 雙向鏈表是每個結點除后繼指針域外還有一個前驅指雙向鏈表是每個結點除后繼指針域外還有一個前驅指針域，它有帶頭結點和不帶頭結點，循環(huán)和非循環(huán)結構，針域，它有帶頭結點和不帶頭結點，循環(huán)和非循環(huán)結構，雙向鏈表是解決查找前驅結點問題的有效途徑。雙向鏈表是解決查找前驅結點問題的有效途徑。

28、結點結構如圖示：結點結構如圖示：prior data next下圖是帶頭結點的循環(huán)雙向鏈表的結構，可見，其前驅指下圖是帶頭結點的循環(huán)雙向鏈表的結構，可見，其前驅指針和后繼指針各自構成自己的循環(huán)單鏈表。針和后繼指針各自構成自己的循環(huán)單鏈表。head(a) 空鏈表空鏈表a0a1an-1head(b) 非空鏈表非空鏈表在雙向鏈表中在雙向鏈表中: 設指針設指針p指向第指向第i個數據元素結點，則個數據元素結點，則p-next指向第指向第i+1個數據元素結點，個數據元素結點，p-next-prior仍指向第仍指向第i個數據元素結點，個數據元素結點，即即p-next-prior=p;同樣同樣p-prior-

29、next=p。循環(huán)雙向鏈表的循環(huán)雙向鏈表的插入過程插入過程如圖示：如圖示：a0aian-1headxsai-1 p刪除過程刪除過程如圖示：如圖示：ai+1aian-1headai-1p 練習：已知練習：已知p p結點是雙向鏈表的中間結點，試從下列提供的答結點是雙向鏈表的中間結點，試從下列提供的答案中選擇合適的語句序列。案中選擇合適的語句序列。(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結點后插入結點后插入s s結點的語句序列是結點的語句序列是 。 b.在在p p結點前插入結點前插入s s結點的語句序列是結點的語句序列是 。 c.c.

32、刪除刪除p p結點的直接后繼結點的語句序列是結點的直接后繼結點的語句序列是 。d.刪除刪除p p結點的直接前驅結點的語句序列是結點的直接前驅結點的語句序列是 。e.e.刪除刪除p p結點的的語句序列是結點的的語句序列是 。 2.6 2.6 靜態(tài)鏈表靜態(tài)鏈表在數組中增加一個在數組中增加一個(或兩個或兩個)指針域用來存放下一個指針域用來存放下一個(或上一個或上一個)數據元素在數組中的下標，從而構成用數組構造的單鏈表。數據元素在數組中的下標，從而構成用數組構造的單鏈表。因為數組內存空間的申請方式是靜態(tài)的，所以稱為靜態(tài)鏈表，因為數組內存空間的申請方式是靜態(tài)的，所以稱為靜態(tài)鏈表，增加的指針稱做增加的指針

33、稱做仿真指針仿真指針。結構如下：。結構如下：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 設計一個順序表的刪除函數，把順序表設計一個順序表的刪除函數，把順序表L中的數中的數據元素據元素x刪除。刪除。算法思想：算法思想：首先首先，找到要刪除元素的位置，找到要刪除元素的位置，然后然后，從這，從這個位置到最后一個元素，逐個前移，個位置到最后一個元素，逐個前移，最后最后，把元素

34、個數，把元素個數減減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 構造一個順序表的刪除算法，把順序表構造一個順序表的刪除算法，把順序表L中所有值相中所有值相同的數據元素同的數據元素x全部刪除。全部刪除。算法思想：在例算法思想：在例2-4所設計的刪除算法的基礎上，增加外重所設計的刪除算法的基礎上，增加外重循環(huán)進行查找，查找到元素循環(huán)進行查找，查找到元素x則刪除，然后繼續(xù)進行這樣的則刪除，然后繼續(xù)進行這樣的過程和刪除過程，直到元素末尾結束。過程和刪除過程，直到元素末尾結束。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，并設帶頭結點單鏈表中的數據元并設帶頭結點單鏈表中的數據元素遞增有序，編寫算法將數據元素素遞增有序，編寫算法將數據元素x插入到帶頭結點單鏈表插入到帶頭結點單鏈表的適當位置上，要求插入后保持單鏈表數據元素的遞增有的適當位置上，要求插入后保持單鏈表數據元素的遞增有序。序。算法思想：從鏈表的第一個數據元素結點開始，逐個比較算法思想：從鏈表的第一個數據元素結點開始，逐個比較每個結點的每個結點的data域值和域值和x的值，當的值，當data小于等于小于等于x時，進行時，進行下一個結點的比較；否則就找到了插入結點的合適位置，下一個結點的比較；否則就找到了插入結點的合適位置，此時申請新結點把此時申請新結點把x存入，然后把新結點插入；