《數(shù)據(jù)結(jié)構(gòu)》課件第2章 線性表

1、第2章 線性表學(xué)習(xí)要點: 了解線性表的邏輯結(jié)構(gòu)特性熟練掌握線性表的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的描述方法熟練掌握線性表在這兩種存儲結(jié)構(gòu)上實現(xiàn)的基本操作查找、插入和刪除能夠從時間和空間復(fù)雜度的角度綜合比較線性表的兩種存儲結(jié)構(gòu)的不同特點及其適用場合線性表是一種最簡單的線性結(jié)構(gòu)。 線性結(jié)構(gòu) 是 一個數(shù)據(jù)元素的有序(次序)關(guān)系存在唯一的一個“第一個”的數(shù)據(jù)元素；存在唯一的一個“最后一個”的數(shù)據(jù)元素；除第一個數(shù)據(jù)元素外，均有唯一的前驅(qū)；除最后一個數(shù)據(jù)元素外，均有唯一的后繼。2.1 線性表的類型定義線性表是最常用而且最簡單的一種數(shù)據(jù)結(jié)構(gòu)。定義：線性表是n個數(shù)據(jù)元素的有限序列。記為：(a1, ., ai-1,

2、 ai, ai+1, ., an)26個字母表：(A，B，C，Z)是一個線性表例如：某校近4年計算機擁有量：(120，340，510，720)記錄文件特征：元素個數(shù)n表長度；n=0空表1in時ai的直接前驅(qū)是ai-1，a1無直接前驅(qū)ai的直接后繼是ai+1，an無直接后繼元素同構(gòu)，且不能出現(xiàn)缺項抽象數(shù)據(jù)類型線性表的定義如下：ADT List 數(shù)據(jù)對象：D ai | ai ElemSet, i=1,2,.,n, n0 稱 n 為線性表的表長; 稱 n=0 時的線性表為空表。數(shù)據(jù)關(guān)系：R1 |ai-1 ,aiD, i=2,.,n 設(shè)線性表為 (a1，a2, . . . ，ai，. . . ，an)

3、, 稱 i 為 ai 在線性表中的位序。 基本操作： 結(jié)構(gòu)初始化操作結(jié)構(gòu)銷毀操作 引用型操作 加工型操作 ADT List初始化操作： InitList( &L )操作結(jié)果：構(gòu)造一個空的線性表 L。結(jié)構(gòu)撤銷操作：引用型操作：ListEmpty( L )ListLength( L )PriorElem( L, cur_e, &pre_e )NextElem( L, cur_e, &next_e )GetElem( L, i, &e )LocateElem( L, e, compare( ) )ListTraverse(L, visit( )DestroyList( &L )初始條件：操作結(jié)果：線

4、性表 L 已存在。銷毀線性表 L。加工型操作：ClearList( &L )PutElem( &L, i, e )改變數(shù)據(jù)元素的值初始條件：線性表 L 已存在，且 1iLengthList(L)操作結(jié)果：L 中第 i 個元素賦值為 e 。ListInsert( &L, i, e )ListDelete(&L, i, &e)例2-1:假設(shè):有兩個集合A 和 B 分別用兩個線性表 LA 和 LB 表示，即：線性表中的數(shù)據(jù)元素即為集合中的成員?，F(xiàn)要求一個新的集合A=AB。 GetElem(Lb, i, e); / 取Lb中第i個數(shù)據(jù)元素賦給e if (!LocateElem(La, e, equal

5、( ) ) ListInsert(La, +La_len, e); / La中不存在和 e 相同的數(shù)據(jù)元素，則插入之 La_len = ListLength(La); / 求線性表的長度 Lb_len = ListLength(Lb); for (i = 1; i = Lb_len; i+) /for / unionvoid union(List &La, List Lb) 分析：操作步驟：從線性表 LB 中依次取出每個數(shù)據(jù)元素;依值在線性表 LA 中進行查訪;若不存在，則插入之。GetElem(LB, i)e LocateElem(LA, e, equal( ) ListInsert(LA,

6、 n+1, e)( n 表示線性表 LA 當前長度)例2-2:已知一個非純集合B，試構(gòu)造一個純集合 A，使A中只包含B中所有值各不相同的數(shù)據(jù)元素。分析：算法的策略應(yīng)該和例2-1基本相同,差別僅在于集合 A 的初始狀態(tài)是“空集”。集合 B集合 Avoid union(List &La, List Lb) La_len=ListLength(La); Lb_len=ListLength(Lb); / union GetElem(Lb, i, e); / 取Lb中第 i 個數(shù)據(jù)元素賦給 e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_le

7、n, e); / La中不存在和 e 相同的數(shù)據(jù)元素，則插入之for (i = 1; i = Lb_len; i+) InitList(La); / 構(gòu)造(空的)線性表LA思考：改變結(jié)構(gòu)，以有序表表示集合。則算法有什么不同？例如：集合B: (2，3，3，5，6，6，6，8，12)對構(gòu)造集合 A 而言，數(shù)據(jù)元素兩兩不同，且依值從小至大的順序插入。void purge(List &La, List Lb) InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); / 求線性表的長度 for (i = 1; i = Lb_len;

8、i+) / purgeGetElem(Lb, i, e); / 取Lb中第i個數(shù)據(jù)元素賦給 eif ( ) ListInsert(La, +La_len, e); en = e; /記錄剛插入的元素 / La中不存在和 e 相同的數(shù)據(jù)元素，則插入之ListEmpty(La)|!equal(en, e)例2-3:（P20，例2-2）歸并兩個“數(shù)據(jù)元素按值非遞減有序排列”的有序表 La 和 Lb，求得有序表 Lc 也具有同樣特性。設(shè) La = (a1, , ai, , an), Lb = (b1, , bj, , bm) Lc = (c1, , ck, , cm+n)且已由(a1, , ai-1)

9、和(b1, ,bj-1)歸并得 (c1, , ck-1)則k = 1, 2, , m+n基本操作：初始化 Lc 為空表；分別從 La和Lb中取得當前元素 ai 和 bj；若 aibj，則將 ai 插入到 Lc中，否則將bj 插入到 Lc 中；重復(fù)2和3兩步,直至 La 或 Lb 中元素被取完為止；將 La表或 Lb 表中剩余元素復(fù)制插入到Lc表中。/ La 和 Lb 均不空，i = j = 1, k = 0 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) / 將 ai 插入到 Lc 中 ListInsert(Lc, +k, ai); +

10、i; else / 將 bj 插入到 Lc 中 ListInsert(Lc, +k, bj); +j; void MergeList(List La, List Lb, List &Lc) / 本算法將非遞減的有序表 La 和 Lb 歸并為 Lc / merge_listwhile (i = La_len) & (j = Lb_len) / La 和 Lb 均不空 while (i=La_len) / 若 La 不空while (j=Lb_len) / 若 Lb 不空InitList(Lc); / 構(gòu)造空的線性表 Lci = j = 1; k = 0;La_len = ListLength(L

11、a);Lb_len = ListLength(Lb); while (i = La_len) / 當La不空時 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入 La 表中剩余元素 while (j = Lb_len) / 當Lb不空時 GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入 Lb 表中剩余元素定義：用一組地址連續(xù)的存儲單元依次存放線性表中的數(shù)據(jù)元素。以“存儲位置相鄰”表示有序?qū)?，則有：LOC(ai) = LOC(ai-1) + l 2.2 線性表類型的實現(xiàn)順序映像 a1 a2 ai-

12、1 ai an線性表的起始地址稱作線性表的基地址 LOC(ai) = LOC(a1) + (i-1)l 基地址一個數(shù)據(jù)元素所占存儲量特點：實現(xiàn)邏輯上相鄰物理地址相鄰實現(xiàn)隨機存取實現(xiàn)：可用C語言的一維數(shù)組實現(xiàn)typedef struct SqList; / 順序表#define LIST_INIT_SIZE 80 / 線性表存儲空間的初始分配量#define LISTINCREMENT 10 / 線性表存儲空間的分配增量ElemType *elem; / 存儲空間基址int length; / 當前長度int listsize; / 當前分配的存儲容量 / (以sizeof(ElemType)為

13、單位)數(shù)組指針線性表的基本操作在順序表中的實現(xiàn)結(jié)構(gòu)初始化：Status InitList_Sq( SqList& L ) / 構(gòu)造一個空的線性表 / InitList_Sq算法時間復(fù)雜度：O(1)線性階L.elem = (ElemType*) malloc (LIST_ INIT_SIZEsizeof (ElemType);if (!L.elem) exit(OVERFLOW); /存儲分配失敗L.length = 0; /空表長度為0L.listsize = LIST_INIT_SIZE; /初始存儲容量return OK;查找：例如：有一個順序表如下23 75 41 38 54 62 17

14、L.elemL.lengthL.listsizee =38pppppi12341850p可見，基本操作是：將順序表中的元素逐個和給定值 e 相比較。 int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在順序表中查詢第一個滿足判定條件的數(shù)據(jù)元素， / 若存在，則返回它的位序，否則返回 0 / LocateElem_Sq O( ListLength(L) )算法的時間復(fù)雜度為：i = 1; / i 的初值為第 1 元素的位序(注意：不是數(shù)組下標值！)p = L.elem; / p 的初值為

15、第 1 元素的存儲位置while (i = L.length & !(*compare)(*p+, e) +i;if (i = L.length) return i;else return 0;(*compare)(*p+, e)插入元素：分析：插入元素時，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？ (a1, , ai-1, ai, , an) 改變?yōu)?(a1, , ai-1, e, ai, , an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean, 表的長度增加 Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在順序表L的第

16、i 個元素之前插入新的元素e, / i 的合法范圍為 1iL.length+1 / ListInsert_Sq 算法時間復(fù)雜度為:O( ListLength(L) )q = &(L.elemi-1); / q 指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移*q = e; / 插入e+L.length; / 表長增1return OK;元素右移插入元素算法時間復(fù)雜度的進一步討論：考慮移動元素的平均情況: 假設(shè)在第i個元素之前插入的概率為 ，則在長度為n的線性表中插入一個元素所需移動元素次數(shù)的期望

17、值為： 若假定在線性表中任何一個位置上進行插入的概率pi都是相等的，則移動元素的期望值為：T(n)=O(n)O( ListLength(L) )if (L.length = L.listsize) / 當前存儲空間已滿，增加分配 newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); / 存儲分配失敗 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存儲容量i

18、f (i L.length+1) return ERROR; / 插入位置不合法例如： ListInsert_Sq(L, 5, 66) 21 18 30 75 42 56 8721 18 30 75L.length-10pppq87564266q = &(L.elemi-1); / q 指示插入位置for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;p刪除元素：分析：刪除元素時，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？ (a1, , ai-1, ai, ai+1, , an) 改變?yōu)?(a1, , ai-1, ai+1, , an)ai+1an, 表

19、的長度減少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 Status ListDelete_Sq (SqList &L, int i, ElemType &e) / ListDelete_Sqfor (+p; p = q; +p) *(p-1) = *p; / 被刪除元素之后的元素左移-L.length; / 表長減1return OK;算法時間復(fù)雜度為: O( ListLength(L)p = &(L.elemi-1); / p 為被刪除元素的位置e = *p; / 被刪除元素的值賦給 eq = L.elem+L.length-1; / 表尾元素的位置if (i L.len

20、gth) return ERROR; / 刪除位置不合法元素左移刪除元素算法時間復(fù)雜度的進一步討論：考慮移動元素的平均情況: 假設(shè)刪除第i個元素的概率為 ，則在長度為n的線性表中刪除一個元素所需移動元素次數(shù)的期望值為： 若假定在線性表中任何一個位置上進行刪除的概率都是相等的，則移動元素的期望值為：T(n)=O(n)例如： ListDelete_Sq(L, 5, e) 21 18 30 75 42 56 8721 18 30 75L.length-10pppq8756p = &(L.elemi-1);q = L.elem+L.length-1;for (+p; p next; j = 1; /

21、p指向第一個結(jié)點，j為計數(shù)器while (p & jnext; +j; / 順指針向后查找，直到p指向第i個元素 /或p為空if ( !p | ji ) return ERROR; / 第 i 個元素不存在e = p-data; / 取得第 i 個元素return OK;插入數(shù)據(jù)元素ListInsert(&L, i, e)：將有序?qū)?改變?yōu)?和可見，在鏈表中插入結(jié)點只需要修改指針。但同時，若要在第i個結(jié)點之前插入元素，修改的是第i-1個結(jié)點的指針。因此，在單鏈表中第i個結(jié)點之前進行插入的基本操作為：找到線性表中第i-1個結(jié)點，然后修改其指向后繼的指針。ai-1 eaiai-1? Status

22、ListInsert_L(LinkList L, int i, ElemType e) / L 為帶頭結(jié)點的單鏈表的頭指針，本算法 / 在鏈表中第i 個結(jié)點之前插入新的元素 e / LinstInsert_L算法的時間復(fù)雜度為:O(n) /修改指針p = L; j = 0;while (p & j next; +j; / 尋找第 i-1 個結(jié)點if (!p | j i-1) return ERROR; / i 大于表長或者小于1 s = (LinkList) malloc ( sizeof (LNode); / 生成新結(jié)點s-data = e; s-next = p-next; p-next

23、= s; / 插入return OK; eai-1aiai-1sp刪除數(shù)據(jù)元素ListDelete(&L, i, e)：將有序?qū)?和 改變?yōu)?在單鏈表中刪除第i個結(jié)點的基本操作為:找到鏈表中第i-1個結(jié)點，修改其指向后繼的指針。ai-1aiai+1ai-1ai-1aiai+1ai-1q = p-next; p-next = q-next; e = q-data; free(q);pq? Status ListDelete_L(LinkList L, int i, ElemType &e) / 刪除以 L 為頭指針(帶頭結(jié)點)的單鏈表中第 i 個結(jié)點 / ListDelete_L算法的時間復(fù)雜度

24、為:O(n)p = L; j = 0;while (p-next & j next; +j; / 尋找第 i 個結(jié)點，并令 p 指向其前趨if (!(p-next) | j i-1) return ERROR; / 刪除位置不合理q = p-next; p-next = q-next; / 刪除并釋放結(jié)點e = q-data; free(q);return OK;重置線性表為空表ClearList(&L)：void ClearList(&L) / 將單鏈表重新置為一個空表 while (L-next) p=L-next; L-next=p-next; / ClearListfree(p);算法

25、時間復(fù)雜度：O(n)注意：操作結(jié)束后，只剩一個頭結(jié)點，且它的指針域為空！生成含 n 個數(shù)據(jù)元素的鏈表CreateList(&L, n)：例如：逆位序輸入 n 個數(shù)據(jù)元素的值，建立帶頭結(jié)點的單鏈表。操作步驟：1.建立一個“空表”； 2.輸入數(shù)據(jù)元素an，建立結(jié)點并插入； 3.輸入數(shù)據(jù)元素an-1，建立結(jié)點并插入； 4.依次類推，直至輸入a1為止。ananan-1anan-1an-2.void CreateList_L(LinkList &L, int n) / 逆序輸入 n 個數(shù)據(jù)元素，建立帶頭結(jié)點的單鏈表 / CreateList_L算法的時間復(fù)雜度為:O(n)L = (LinkList) m

26、alloc (sizeof (LNode);L-next = NULL; / 先建立一個帶頭結(jié)點的單鏈表for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); scanf(&p-data); / 輸入元素值 p-next = L-next; L-next = p; / 插入比較：例2-1、2-2、2-3中的算法，當線性表分別以順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)實現(xiàn)時，它們的時間復(fù)雜度為多少？void union(List &La, List Lb) La_len = ListLength(La); Lb_len =ListLength(Lb); for (i = 1; i = Lb_len; i+) GetElem(Lb, i, &e); if (!LocateElem(La, e, equal( ) ListInsert(La, +La_len, e); /for / union控制結(jié)構(gòu)：基本操作：for 循環(huán)GetElem, LocateElem 和 ListInsert當以順序映像實現(xiàn)抽象數(shù)據(jù)類型線性表時為: O( ListLength(