1、第2章 線性表線性結構 線性結構是一個數據元素的有序（次序）集合。它有四個基本特征：1集合中必存在唯一的一個第一元素；2集合中必存在唯一的一個最后元素；3除最后元素之外，其它數據元素均有唯一的后繼；4除第一元素之外，其它數據元素均有唯一的前驅。第一節 線性表的類型定義 2.1.1 抽象數據類型線性表的定義 通常可以下列 n 個數據元素的序列表示線性表 (Linear_List) ( a1, a2,.,ai-1,ai,ai+1,.,an)序列中數據元素的個數 n 定義為線性表的表長 n=0 時的線性表被稱為空表 稱 i 為ai在線性表中的位序 線性表的抽象數據類型的定義 ADT List 數據對

2、象：Dai | ai ElemSet, i=1,2,.,n, n0 數據關系：R1 | ai-1,aiD, i=2,.,n 基本操作：結構初始化InitList( &L )操作結果：構造一個空的線性表 L 。 銷毀結構DestroyList( &L )初始條件：線性表 L 已存在。操作結果：銷毀線性表 L 。引用型操作ListEmpty( L )初始條件：線性表L已存在。操作結果：若 L 為空表，則返回 TRUE，否則返回 FALSE。ListLength( L )初始條件：線性表 L 已存在。操作結果：返回 L 中元素個數。 PriorElem( L, cur_e, &pre_e )初始條件

3、：線性表 L 已存在。操作結果：若 cur_e 是 L 中的數據元素，則用 pre_e 返回它的前驅，否則操作失敗，pre_e 無定義。 NextElem( L, cur_e, &next_e )初始條件：線性表 L 已存在。操作結果：若 cur_e 是 L 中的數據元素，則用 next_e 返回它的后繼，否則操作失敗，next_e 無定義。 GetElem( L, i, &e )初始條件：線性表 L 已存在，1iLengthList(L)。操作結果：用 e 返回 L 中第 i 個元素的值。LocateElem( L, e, compare( ) ) 初始條件：線性表 L 已存在 pare(

4、) 是元素判定函數。操作結果：返回 L 中第1個與 e 滿足關系 compare( ) 的元素的位序。若這樣的元素不存在，則返回值為0。ListTraverse(L, visit( )初始條件：線性表 L 已存在，visit( ) 為元素的訪問函數。操作結果：依次對 L 的每個元素調用函數 visit( )。一旦 visit( ) 失敗，則操作失敗。加工型操作 ClearList( &L )初始條件：線性表 L 已存在。操作結果：將 L 重置為空表。 PutElem( &L, i, &e )初始條件：線性表L已存在，1iLengthList(L)。操作結果：L 中第 i 個元素賦值同 e 的值

5、。 ListInsert( &L, i, e )初始條件：線性表 L 已存在，1iLengthList(L)+1。操作結果：在 L 的第 i 個元素之前插入新的元素 e，L 的長度增1。 ListDelete( &L, i, &e )初始條件：線性表 L 已存在且非空，1iLengthList(L)。操作結果：刪除 L 的第 i 個元素，并用 e 返回其值，L 的長度減1。 ADT List2.1.2 線性表類型的應用 例1 已知集合 A 和 B，求兩個集合的并集，使 AAB，且 B 不再單獨存在。 分析:以線性表 LA 和 LB 分別表示集合 A 和 B，對集合 B 中的所有元素一個一個地檢

6、查，將存在于線性表 LB 中而不存在于線性表 LA 中的數據元素插入到線性表 LA 中去。具體操作步驟為：1從線性表 LB 中取出一個數據元素；2依值在線性表 LA 中進行查詢；3若不存在，則將它插入到 LA 中。重復上述三步直至 LB 為空表止。 對應的線性表基本操作：1. ListDelete( LB, 1, e );2. LocateElem( LA, e, equal() ); 3. ListInsert( LA, n+1,e )void union(List &LA, List &LB)La_len = ListLength(LA);/ 求得線性表 LA 的長度while (!Lis

7、tEmpty(LB) / 依次處理 LB 中元素直至 LB 為空表止 / 從 LB 中刪除第1個數據元素并賦給 e ListDelete(LB,1,e); / 當LA中不存在和 e 值相同的數據元素時進行插入 if (!LocateElem(LA,e,equal( ) ListInsert(LA,+La_len,e); DestroyList(LB);/ 銷毀線性表 LB / union例2 已知一個“非純集合” B，試構造一個集合 A，使 A 中只包含 B 中所有值各不相同的數據元素。 分析:將每個從 B 中取出的元素和已經加入到集合 A 中的元素相比較。 void purge(List &

8、LA, List LB) / 構造線性表LA，使其只包含LB中所有值不相同的數據元素,算法不改變線性表LBInitList(LA); / 創建一個空的線性表 LALa_len = 0;Lb_len = ListLength(LB); / 求線性表 LB 的長度for (i = 1; i item=(EntryType*)malloc (LIST_MAX_LENGTH *sizeof(EntryType); /分配空間 if (L-item=NULL) return ERROR; /若分配空間不成功，返回ERROR L-length=0; /將當前線性表長度置0 return OK; /成功返回

9、OK2. 銷毀線性表Lvoid DestroyList(SQ_LIST &L) if (L-item) free(L-item); /釋放線性表占據的所有存儲空間3. 清空線性表Lvoid ClearList(SQ_LIST &L) L-length=0; /將線性表的長度置為04. 求線性表L的長度int GetLength(SQ_LIST L) return (L.length); 5. 判斷線性表L是否為空int IsEmpty(SQ_LIST L) if (L.length=0) return TRUE; else return FALSE;6. 獲取線性表L中的某個數據元素的內容in

10、t GetElem(SQ_LIST L,int i,EntryType &e) if (iL.length) return ERROR; /判斷i值是否合理，若不合理，返回ERROR e=L.itemi-1; /數組中第i-1的單元存儲著線性表中第i個數據元素的內容 return OK;7. 在線性表L中檢索值為e的數據元素int LocateELem(SQ_LIST L,EntryType e) for (i=0;ilength=LIST_MAX_LENGTH) return ERROR; if (iL-length+1) return ERROR; /i值是否合理 for (j=L-len

11、gth-1;j=i-1;i+) /將線性表第i個元素之后的所有元素向后移動 L.-itemj+1=L-itemj; L-itemi-1=e; /將新元素的內容放入線性表的第i個位置 L-length+; return OK;9. 將線性表L中第i個數據元素刪除int ListDelete(SQ_LIST &L,int i,EntryType &e) if (IsEmpty(L) return ERROR; /檢測線性表是否為空 if (iL-length) return ERROR; /檢查i值是否合理 e=L-itemi-1; /將欲刪除的數據元素內容保留在e所指示的存儲單元中 for (j

12、=i;jlength-1;j+) /將線性表第i+1個元素之后的所有元素向前移動 L-itemj-1=L-itemj; L-length-;return OK;2.3 線性表的鏈式存儲結構線性表順序存儲結構的特點:它是一種簡單、方便的存儲方式。它要求線性表的數據元素依次存放在連續的存儲單元中，從而利用數據元素的存儲順序表示相應的邏輯順序，這種存儲方式屬于靜態存儲形式。暴露的問題 l在做插入或刪除元素的操作時，會產生大量的數據元素移動； l對于長度變化較大的線性表，要一次性地分配足夠的存儲空間，但這些空間常常又得不到充分的利用； l線性表的容量難以擴充。鏈式存儲結構是指用一組任意的存儲單元（可以

13、連續，也可以不連續）存儲線性表中的數據元素。為了反映數據元素之間的邏輯關系，對于每個數據元素不僅要表示它的具體內容，還要附加一個表示它的直接后繼元素存儲位置的信息。假設有一個線性表（a,b,c,d）術語每個數據元素的兩部分信息組合在一起被稱為結點其中表示數據元素內容的部分被稱為數據域（data）表示直接后繼元素存儲地址的部分被稱為指針或指針域（next）單鏈表簡化的圖形描述形式headd cbahead是頭指針，它指向單鏈表中的第一個結點，這是單鏈表操作的入口點由于最后一個結點沒有直接后繼結點，所以，它的指針域放入一個特殊的值NULL。NULL值在圖示中常用（）符號表示。headd cba帶頭

14、結點的單鏈表為了簡化對鏈表的操作，人們經常在鏈表的第一個結點之前附加一個結點，并稱為頭結點。這樣可以免去對鏈表第一個結點的特殊處理。headd cba鏈式存儲結構的特點（1）線性表中的數據元素在存儲單元中的存放順序與邏輯順序不一定一致（2）在對線性表操作時，只能通過頭指針進入鏈表，并通過每個結點的指針域向后掃描其余結點，這樣就會造成尋找第一個結點和尋找最后一個結點所花費的時間不等，具有這種特點的存取方式被稱為順序存取方式。鏈式存儲結構的類型定義typedef strcut node /結點類型 EntryType item; struct node *next;NODE;typedef str

15、uct /鏈表類型 NODE *head;LINK_LIST;典型操作的算法實現1. 初始化鏈表Lint InitList(LINK_LIST &L) L-head=(*NODE)malloc(sizeof(NODE); /為頭結點分配存儲單元 if (L-head) L-head-next=NULL; return OK; else return ERROR ;L-headd cba2. 銷毀鏈表L void DestoryList(LINK_LIST &L) NODE *p; while (L-head) /依次刪除鏈表中的所有結點 p=L-head; L-head=L-head-next

16、; free(p); L-headd cba3. 清空鏈表L void ClearList(LINK_LIST &L) NODE *p; while (L-head-next) p=L-head-next; /p指向鏈表中頭結點后面的第一個結點 L-head-next=p-next; /刪除p結點 free(p); /釋放p結點占據的存儲空間 L-headd cba4. 求鏈表L的長度int ListLength(LINK_LIST L) NODE *p; int len; for(p=L.head, len=0;p-next=NULL; p=p-next,len+); return(len)

17、;L-headd cba5. 判鏈表L空否。 int IsEmpty(LINK_LIST L) if (L.head-next=NULL) return TRUE; else return FALSE; L-headd cba6. 通過e返回鏈表L中第i個數據元素的內容void GetElem(LINK_LIST L,int i,EntryType &e) NODE *p; int j; if (iListLength(L) exit ERROR; /檢測i值的合理性 for (p=L.head,j=0; j!=i;p=p-next,j+); /找到第i個結點 e=p-item; /將第i個結

18、點的內容賦給e指針所指向的存儲單元中L-headd cba7. 在鏈表L中檢索值為e的數據元素NODE *LocateELem(LINK_LIST L,EntryType e) NODE *p; for (p=L.head-next;p&p-item!=e;p=p-next); /尋找滿足條件的結點 return(p);L-headd cba8. 返回鏈表L中結點e的直接前驅結點NODE *PriorElem(LINK_LIST L,NODE * e) NODE *p; if (L.head-next=e) return NULL; /檢測第一個結點 for (p=L.head;p-next&p-next!=e;p=p-next); if (p-next=e) return p; esle return NULL; L-headd cba9. 返回鏈表L中結點e的直接后繼結點NODE *NextElem(LINK_LIST L,NODE * e) NODE *p; for(p=L.head-nex