第二章數(shù)據(jù)結(jié)構(gòu)-線性表

1、第二章 線性表楊衛(wèi)民EMAIL：線性結(jié)構(gòu)的線性結(jié)構(gòu)的基本特征基本特征為為: :1集合中必存在唯一的一個集合中必存在唯一的一個“第一元素第一元素”；2集合中必存在唯一的一個集合中必存在唯一的一個 “最后元素最后元素” ；3除最后元素在外，均有除最后元素在外，均有 唯一的后繼唯一的后繼；4除第一元素之外，均有除第一元素之外，均有 唯一的前驅(qū)唯一的前驅(qū)。 線性結(jié)構(gòu)線性結(jié)構(gòu) 是是 一個數(shù)據(jù)元素的一個數(shù)據(jù)元素的有序（次序）集有序（次序）集線性表線性表是一種最簡單的線性結(jié)構(gòu)線性結(jié)構(gòu)2.1 線性表的類型定義線性表的類型定義2.3 線性表類型的實現(xiàn)線性表類型的實現(xiàn) 鏈式映象鏈式映象2.4 一元多項式的表示一元

2、多項式的表示2.2 線性表類型的實現(xiàn)線性表類型的實現(xiàn) 順序映象順序映象2.1線性表的類型定義線性表的類型定義抽象數(shù)據(jù)類型線性表線性表的定義如下：ADT List 數(shù)據(jù)對象數(shù)據(jù)對象：D ai | ai ElemSet, i=1,2,.,n, n0 稱 n 為線性表的表長表長; 稱 n=0 時的線性表為空表空表。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：R1 |ai-1 ,aiD, i=2,.,n 設(shè)線性表為 (a1，a2, . . . ，ai，. . . ，an), 稱 i 為 ai 在線性表中的位序位序。 基本操作：基本操作： 結(jié)構(gòu)初始化操作結(jié)構(gòu)初始化操作結(jié)構(gòu)銷毀操作結(jié)構(gòu)銷毀操作 引用型操作引用型操作 加工型操作加工

3、型操作 ADT List InitList( &L )操作結(jié)果：操作結(jié)果：構(gòu)造一個空的線性表L。初始化操作初始化操作 結(jié)構(gòu)銷毀操作結(jié)構(gòu)銷毀操作DestroyList( &L )初始條件：操作結(jié)果：線性表 L 已存在。銷毀線性表 L。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( )引用型

4、操作引用型操作: : ListEmpty( L )初始條件：操作結(jié)果：線性表L已存在。若L為空表，則返回TRUE，否則FALSE。（線性表判空）ListLength( L )初始條件：操作結(jié)果：線性表L已存在。返回L中元素個數(shù)。（求線性表的長度） PriorElem( L, cur_e, &pre_e )初始條件：操作結(jié)果：線性表L已存在。若cur_e是L的元素，但不是第一個，則用pre_e 返回它的前驅(qū)，否則操作失敗，pre_e無定義。（求數(shù)據(jù)元素的前驅(qū)）NextElem( L, cur_e, &next_e )初始條件：操作結(jié)果：線性表L已存在。若cur_e是L的元素，但不

5、是最后一個，則用next_e返回它的后繼，否則操作失敗，next_e無定義。（求數(shù)據(jù)元素的后繼）GetElem( L, i, &e ) 初始條件： 操作結(jié)果：線性表L已存在，且 1iLengthList(L)。用 e 返回L中第 i 個元素的值。（求線性表中某個數(shù)據(jù)元素）LocateElem( L, e, compare( ) )初始條件：操作結(jié)果：線性表L已存在，e為給定值， compare( )是元素判定函數(shù)。返回L中第中第1個個與e滿足滿足關(guān)系compare( )的元素的位序。若這樣的元素不存在，則返回值為0。（定位函數(shù)） ListTraverse(L, visit( )初始條件

6、：操作結(jié)果：線性表L已存在，Visit() 為某個訪問函數(shù)。依次依次對L的每個元素調(diào)用函數(shù)visit( )。一旦visit( )失敗，則操作失敗。（遍歷線性表）加工型操作加工型操作 ClearList( &L )PutElem( &L, i, &e )ListInsert( &L, i, e )ListDelete(&L, i, &e) ClearList( &L )初始條件：操作結(jié)果：線性表L已存在。將L重置為空表。（線性表置空）PutElem( &L, i, &e )初始條件：操作結(jié)果：線性表L已存在，且 1iLeng

7、thList(L) 。L中第i個元素賦值同e的值。（改變數(shù)據(jù)元素的值） ListInsert( &L, i, e )初始條件：操作結(jié)果：線性表L已存在， 且 1iLengthList(L)+1 。在L的第i個元素之前插入插入新的元素e，L的長度增1。（插入數(shù)據(jù)元素）ListDelete(&L, i, &e)初始條件：操作結(jié)果：線性表L已存在且非空， 1iLengthList(L) 。刪除L的第i個元素，并用e返回其值，L的長度減1。（刪除數(shù)據(jù)元素）利用上述定義的線性表線性表 可以實現(xiàn)其它更復(fù)雜的操作例例 2-2例例 2-3例例 2-1 假設(shè):有兩個集合集合 A 和和 B

8、 分別用兩個線性表線性表 LA 和和 LB 表示，即：線性表中的數(shù)據(jù)元素即為集合中的成員。 現(xiàn)要求一個新的集合現(xiàn)要求一個新的集合AAB。例例 2-1 要求對線性表作如下操作：擴大線性表 LA，將存在于線性表存在于線性表LB 中中而不存在于線性表不存在于線性表 LA 中中的數(shù)據(jù)元素插入到線性表插入到線性表 LA 中中去。上述問題可演繹為：1從線性表LB中依次察看每個數(shù)據(jù)元素;2依值在線性表LA中進行查訪; 3若不存在，則插入之。GetElem(LB, i,&e) LocateElem(LA, e, equal( ) ListInsert(LA, n+1, e)操作步驟：操作步驟： Get

9、Elem(Lb, i, e); / 取取Lb中第中第i個數(shù)據(jù)元素賦給個數(shù)據(jù)元素賦給e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的數(shù)據(jù)元素，則插入之相同的數(shù)據(jù)元素，則插入之void union(List &La, List Lb) La_len = ListLength(La); / 求線性表的長度求線性表的長度 Lb_len = ListLength(Lb); for (i = 1; i = Lb_len; i+) / union 已知已知一個非純集合非純集合 B，

10、試構(gòu)造構(gòu)造一個純集合純集合 A，使使 A中只包含中只包含 B 中所有值各中所有值各不相不相 同的數(shù)據(jù)元素同的數(shù)據(jù)元素。所謂非純集合意為該集合中存在相同元素。仍選用線性表線性表表示集合。例例 2-2集合集合 B集合集合 A從集合 B 取出物件放入集合 A要求集合A中同樣物件不能有兩件以上同樣物件不能有兩件以上因此，算法的策略應(yīng)該和例算法的策略應(yīng)該和例2-1相同相同void union(List &La, List Lb) La_len=ListLength(La); Lb_len=ListLength(Lb); / union GetElem(Lb, i, e); / 取取Lb中第中第

11、i 個數(shù)據(jù)元素賦給個數(shù)據(jù)元素賦給 e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的數(shù)據(jù)元素，則插入之相同的數(shù)據(jù)元素，則插入之for (i = 1; i = Lb_len; i+) InitList(La); / 構(gòu)造(空的)線性表LA若線性表中的數(shù)據(jù)元素相互之間可以比比較較，并且數(shù)據(jù)元素在線性表中依值非遞依值非遞減或非遞增有序減或非遞增有序排列，即 aiai-1 或 aiai-1(i = 2,3, n)，則稱該線性表為有序表有序表(Ordered List)(Ordered

12、List)。試改變結(jié)構(gòu)，以有序表有序表表示集合。例如例如：（2，3，3，5，6，6，6，8，12）對集合 B 而言， 值相同的數(shù)據(jù)元素必定相鄰；值相同的數(shù)據(jù)元素必定相鄰；對集合 A 而言， 數(shù)據(jù)元素依值從小至大的順序插入。數(shù)據(jù)元素依值從小至大的順序插入。因此，數(shù)據(jù)結(jié)構(gòu)改變了，數(shù)據(jù)結(jié)構(gòu)改變了， 解決問題的策略也相應(yīng)要改變。解決問題的策略也相應(yīng)要改變。void purge(List &La, List Lb) InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); / 求線性表的長度求線性表的長度 for (i = 1;

13、 i = Lb_len; i+) / purge GetElem(Lb, i, e); / 取取Lb中第中第i個數(shù)據(jù)元素賦給個數(shù)據(jù)元素賦給 eif (ListEmpty(La) | !equal (en, e) ListInsert(La, +La_len, e); en = e; / La中不存在和中不存在和 e 相同的數(shù)據(jù)元素，則插入之相同的數(shù)據(jù)元素，則插入之 / La 和 Lb 均非空，i = j = 1, k = 0 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) / 將 ai 插入到 Lc 中 ListInsert(Lc, +

14、k, ai); +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;

15、La_len = ListLength(La);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 表中剩余元素表中剩余元素課本課本P20 P20 算法算法2.12.1 T(n)=O(ListLength(La)*ListLength(Lb)課

16、本課本P21 P21 算法算法2.22.2 T(n)=O(ListLength(La)+ListLength(Lb)最簡單的一種順序映象方法是：最簡單的一種順序映象方法是： 令令 y y 的存儲位置和的存儲位置和 x x 的存儲位置的存儲位置相鄰相鄰。順序映象順序映象 以以 x 的存儲位置和的存儲位置和 y 的存儲位置的存儲位置之間某種關(guān)系表示邏輯關(guān)系之間某種關(guān)系表示邏輯關(guān)系。 用一組地址連續(xù)地址連續(xù)的存儲單元 依次存放依次存放線性表中的數(shù)據(jù)元素 a1 a2 ai-1 ai an線性表的線性表的起始地址起始地址稱作線性表的基地址基地址以“存儲位置相鄰存儲位置相鄰”表示有序?qū)?即：LOC(ai)

17、 = LOC(ai-1) + C 一個數(shù)據(jù)元素所占存儲量一個數(shù)據(jù)元素所占存儲量所有數(shù)據(jù)元素的存儲位置均取決于所有數(shù)據(jù)元素的存儲位置均取決于 第一個數(shù)據(jù)元素的存儲位置第一個數(shù)據(jù)元素的存儲位置 LOC(ai) = LOC(a1) + (i-1)C 基地址基地址順序映像的順序映像的 C 語言描述語言描述typedef struct SqList; / 俗稱 順序表順序表#define LIST_INIT_SIZE 100 / 線性表存儲空間的初始分配量#define LISTINCREMENT 10 / 線性表存儲空間的分配增量ElemType *elem; / 存儲空間基址,elem中存放Elem

18、Type型數(shù)據(jù)的基址 int length; / 當前長度(數(shù)據(jù)元素的個數(shù)) int listsize; / 當前分配的存儲容量 / (以sizeof(ElemType)為單位)線性表的基本操作在順序表中的實現(xiàn)線性表的基本操作在順序表中的實現(xiàn)InitList_Sq(&L) / 結(jié)構(gòu)初始化結(jié)構(gòu)初始化LocateElem_Sq(L, e, compare() / 查找查找ListInsert_Sq(&L, i, e) / 插入元素插入元素ListDelete_Sq(&L, i) / 刪除元素刪除元素Status InitList_Sq( SqList & L) /

19、構(gòu)造一個空的線性表 / InitList_Sq算法時間復(fù)雜度時間復(fù)雜度：O(1)L.elem = (ElemType *) malloc (LIST_ INIT_SIZE sizeof (ElemType);/將這片連續(xù)空間的基址強制轉(zhuǎn)換為ElemType型指針賦給L.elem if (!L.elem) exit(OVERFLOW); /存儲分配失敗,則返回(OVERFLOW) L.length = 0; / 否則設(shè)置空表長度為0 L.listsize = LIST_INIT_SIZE; /初始存儲容量為LIST_INIT_SIZE個分配單位 return OK;例如：順序表23 75 41

20、38 54 62 17L.elemL.lengthL.listsizee =38pppppi 1 2 3 4 1 850p可見，基本操作是：將順序表中的元素逐個和給定值 e 相比較。 int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在順序表中查詢第一個滿足判定條件的數(shù)據(jù)元素，在順序表中查詢第一個滿足判定條件的數(shù)據(jù)元素， / 若存在，則返回它的位序，否則返回若存在，則返回它的位序，否則返回 0 0 / Status( Status( * * compare)(ElemType,Elem

21、Type) compare)(ElemType,ElemType)整體是整體是LocateElem_SqLocateElem_Sq的的一個一個形形參參 ,將將函數(shù)指針變量函數(shù)指針變量comparecompare作為形參，作為形參，comparecompare中放的是函數(shù)的入口地址。函數(shù)中放的是函數(shù)的入口地址。函數(shù)需要兩個需要兩個ElemTypeElemType型參數(shù)，函數(shù)自身返回型參數(shù)，函數(shù)自身返回StatusStatus型結(jié)果。型結(jié)果。 / LocateElem_Sq O( ListLength(L) )算法的算法的時間復(fù)雜度時間復(fù)雜度為：為：i = 1; / i i 的初值為第的初值為第

22、1 1 元素的位序元素的位序p = L.elem; / p p 的初值為第的初值為第 1 1 元素的存儲位置元素的存儲位置while (i = L.length & !(*compare)(*p+, e) +i; /(/(* *compare)(compare)(* *p+, e)p+, e)是檢查表是檢查表L L中的元素即中的元素即* *p+p+所表示的元素與給定所表示的元素與給定元素元素e e是否滿足是否滿足compare(),compare(),相等返回相等返回1,1,不相等返回不相等返回0. 0. if (i = L.length) return i; /如果如果(i= L.l

23、ength)(i= L.length)說明在說明在L L中已找中已找到這樣的元素。到這樣的元素。 else return 0;線性表操作 ListInsert_Sq(&L, i, e)的實現(xiàn)：首先分析首先分析:插入元素時，線性表的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)發(fā)生什么變化發(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的第

24、i 個元素之前插入新的元素e, / i 的合法范圍為 1iL.length+1 / ListInsert_Sq 算法時間復(fù)雜度算法時間復(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;元素右移元素右移if (L.length = L.listsize) / 當前存儲空間已滿，增加分配 newbase

25、= (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType); /realloc()的功能是重新分配主存,將L.elem所指的對象改為新的空間大小,舊空間的內(nèi)容拷貝進來. if (!newbase) exit(OVERFLOW); / 存儲分配失敗 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存儲容量if (i L.length+1) return ERROR; / 插入位置不合法考慮移動元素的平均情況考慮移動元素的平均情況: : 假設(shè)在

26、第 i 個元素之前插入的概率為 ， 則在長度為n 的線性表中插入一個元素所需插入一個元素所需移動元素次數(shù)的期望值移動元素次數(shù)的期望值為：ip11) 1(niiisinpE11) 1(11niisinnE2n 若假定假定在線性表中任何一個位置上進行插入插入的概率的概率都是相等相等的，則移動元素的期望值移動元素的期望值為：21 18 30 75 42 56 8721 18 30 75例如：ListInsert_Sq(L, 5, 66) L.length-10pppq87564266q = &(L.elemi-1); / q 指示插入位置for (p = &(L.elemL.leng

27、th-1); p = q; -p) *(p+1) = *p;p線性表操作 ListDelete_Sq(&L, i, &e)的實現(xiàn)：首先分析：刪除元素時，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？ (a1, , ai-1, ai, ai+1, , an) 改變?yōu)?(a1, , ai-1, ai+1, , an)ai+1 an, 表的長度減少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)

28、*(p-1) = *p; / 被刪除元素之后的元素左移被刪除元素之后的元素左移-L.length; / 表長減表長減1 1return OK;算法時間復(fù)雜度算法時間復(fù)雜度為為: : O( ListLength(L)p = &(L.elemi-1); / p 為被刪除元素的位置為被刪除元素的位置e = *p; / 被刪除元素的值賦給被刪除元素的值賦給 eq = L.elem+L.length-1; / 表尾元素的位置表尾元素的位置if (i L.length) return ERROR; / 刪除位置不合法刪除位置不合法元素左移元素左移考慮移動元素的平均情況考慮移動元素的平均情況: :

29、假設(shè)刪除第 i 個元素的概率為 , 則在長度為n 的線性表中刪除一個元素所需移動元素次數(shù)的期望值移動元素次數(shù)的期望值為：iqniidlinqE1)(nidlinnE1)(121n若假定在線性表中任何一個位置上進行刪除的概率都是相等的，則移動元素的期望值移動元素的期望值為：21 18 30 75 42 56 8721 18 30 75L.length-10pppq8756p = &(L.elemi-1);q = L.elem+L.length-1;for (+p; p data=ai , 則則 p-next-data=ai+1pp-next三、單鏈表操作的實現(xiàn)三、單鏈表操作的實現(xiàn)GetE

30、lem(L, i, e) / 取第取第i i個數(shù)據(jù)元素個數(shù)據(jù)元素ListInsert(&L, i, e) / 插入插入數(shù)據(jù)元素數(shù)據(jù)元素ListDelete(&L, i, e) / 刪除刪除數(shù)據(jù)元素數(shù)據(jù)元素ClearList(&L) / 重置線性表為空表重置線性表為空表CreateList(&L, n) / 生成含生成含 n 個數(shù)據(jù)元素的鏈表個數(shù)據(jù)元素的鏈表L 線性表的操作 GetElem(L, i, &e)在單鏈表中的實現(xiàn): (假如：i=3)211830754256pppj1 2 3 因此，查找第因此，查找第 i 個數(shù)據(jù)元素的基本個數(shù)據(jù)元素的基本操作為：

31、操作為：移動指針，比較移動指針，比較 j 和和 i 。 單鏈表是一種順序存取的結(jié)構(gòu)，為找單鏈表是一種順序存取的結(jié)構(gòu)，為找第第 i 個數(shù)據(jù)元素，必須先找到第個數(shù)據(jù)元素，必須先找到第 i-1 個數(shù)個數(shù)據(jù)元素。據(jù)元素。 令指針令指針 p p 始終始終指向指向線性表中線性表中第第 j j 個數(shù)據(jù)元素。個數(shù)據(jù)元素。 Status GetElem_L(LinkList L, int i, ElemType &e) / L是帶頭結(jié)點的鏈表的頭指針，以是帶頭結(jié)點的鏈表的頭指針，以 e 返回第返回第 i 個元素個元素 / GetElem_L算法算法時間復(fù)雜度時間復(fù)雜度為為:O(ListLength(L)

32、p = L-next; j = 1; / p p指向第一個結(jié)點，指向第一個結(jié)點，j j為計數(shù)器為計數(shù)器while (p & jnext; +j; / 順指針向后查找，直到順指針向后查找，直到 p p 指向第指向第 i i 個元素個元素 / 或或 p p 為空為空if ( !p | ji ) return ERROR; / 第第 i i 個元素不存在個元素不存在e = p-data; / 取得第取得第 i i 個元素個元素return OK;注意：注意：在循環(huán)進入前和循環(huán)結(jié)束后：在循環(huán)進入前和循環(huán)結(jié)束后：（1 1）指針）指針p p的位置關(guān)系的位置關(guān)系（2 2）當前位置）當前位置 j j

33、與目標位置與目標位置 i i 的關(guān)系的關(guān)系（3 3）語句的前后邏輯次序）語句的前后邏輯次序ai-1 線性表的操作 ListInsert(&L, i, e) 在單鏈表中的實現(xiàn)： 有序?qū)τ行驅(qū)?改變?yōu)楦淖優(yōu)?和和 eaiai-1 因此，在單鏈表中第因此，在單鏈表中第 i 個結(jié)點之前進個結(jié)點之前進行插入的基本操作為行插入的基本操作為: 找到線性表中第找到線性表中第i-1i-1個結(jié)點，然后修改個結(jié)點，然后修改其指向后繼的指針。其指向后繼的指針。 可見，在鏈表中插入結(jié)點只需要修改可見，在鏈表中插入結(jié)點只需要修改指針。但同時，若要在第指針。但同時，若要在第 i 個結(jié)點之前個結(jié)點之前插入元素，修改的

34、是第插入元素，修改的是第 i-1 個結(jié)點的指個結(jié)點的指針。針。 Status ListInsert_L(LinkList L, int i, ElemType e) / L 為帶頭結(jié)點的單鏈表的頭指針，本算法為帶頭結(jié)點的單鏈表的頭指針，本算法 / 在鏈表中第在鏈表中第i 個結(jié)點之前插入新的元素個結(jié)點之前插入新的元素 e / LinstInsert_L算法的算法的時間復(fù)雜度時間復(fù)雜度為:O(ListLength(L)p = L; j = 0; / p p是一個指針變量，此時是一個指針變量，此時p p的值就是頭結(jié)點的起始位置的值就是頭結(jié)點的起始位置, ,/ 而而p-nextp-next的值則是頭結(jié)

35、點的指針域值的值則是頭結(jié)點的指針域值, ,指向第指向第1 1個結(jié)點的起個結(jié)點的起始位置。始位置。 while (p & j next; +j; / 尋找第尋找第 i-1 個結(jié)點個結(jié)點/ / /若條件成立第若條件成立第1 1次進入循環(huán)時次進入循環(huán)時j j的值為的值為0 0，第，第1 1次循環(huán)結(jié)束時次循環(huán)結(jié)束時j j的值為的值為1 1/做完第做完第1 1次次whilewhile循環(huán)時，循環(huán)時，p p 的值就成了第的值就成了第1 1個結(jié)點的起始位置。個結(jié)點的起始位置。/以此類推，在完成第以此類推，在完成第i-1i-1次循環(huán)時次循環(huán)時p p的值就成了第的值就成了第i-1i-1個結(jié)點的起始位置。

36、個結(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 = s; / 插入return OK; eai-1aiai-1sp線性表的操作ListDelete (&L, i, &e)在鏈表中的實現(xiàn):有序?qū)τ行驅(qū)?和和 改變?yōu)楦淖優(yōu)?ai-1aiai+1ai-1 在單鏈表中刪除第刪除第 i i 個結(jié)點個結(jié)點的基本基本操作操作為:找到線性表中第找到線性表中

37、第i-1i-1個結(jié)點，修個結(jié)點，修改其指向后繼的指針。改其指向后繼的指針。ai-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ù)雜度時間復(fù)雜度為: O(ListLength(L)p = L; j = 0;while (p-next & j next; +j; / 尋找第 i 個結(jié)點，并令 p

38、指向其前趨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) 在鏈表中的實現(xiàn):void ClearList(&L) / 將單鏈表重新置為一個空表 while (L-next) p=L-next; L-next=p-next; / ClearListfree(p);算法時間復(fù)雜度：O(ListLength(L)如何從線性表得到單鏈表？如何從線性表得到單鏈表？鏈表是一個動態(tài)的

39、結(jié)構(gòu)，它不需要鏈表是一個動態(tài)的結(jié)構(gòu)，它不需要予分配空間，因此予分配空間，因此生成鏈表的過程生成鏈表的過程是一個結(jié)點是一個結(jié)點“逐個插入逐個插入” ” 的過程。的過程。例如：逆位序輸入例如：逆位序輸入 n n 個數(shù)據(jù)元素的值，個數(shù)據(jù)元素的值， 建立帶頭結(jié)點的單鏈表。建立帶頭結(jié)點的單鏈表。( (頭插法）頭插法）操作步驟：操作步驟：一、建立一個一、建立一個“空表空表”；二、輸入數(shù)據(jù)元素二、輸入數(shù)據(jù)元素an， 建立結(jié)點并插入；建立結(jié)點并插入；三、輸入數(shù)據(jù)元素三、輸入數(shù)據(jù)元素an-1， 建立結(jié)點并插入；建立結(jié)點并插入；ananan-1四、依次類推，直至輸入四、依次類推，直至輸入a a1 1為止。為止。v

40、oid CreateList_L(LinkList &L, int n) / 逆序輸入 n 個數(shù)據(jù)元素，建立帶頭結(jié)點的單鏈表 / CreateList_L算法的算法的時間復(fù)雜度時間復(fù)雜度為:O(Listlength(L)L = (LinkList) malloc (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; /

41、 插入回顧回顧 2.1 節(jié)中三個例子的算法，節(jié)中三個例子的算法，看一下當線性表分別以順序存看一下當線性表分別以順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)實現(xiàn)時，儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)實現(xiàn)時，它們的時間復(fù)雜度為多少？它們的時間復(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);

42、/for / union控制結(jié)構(gòu)：控制結(jié)構(gòu)：基本操作：基本操作：for 循環(huán)循環(huán)GetElem, LocateElem 和 ListInsert當以順序映像實現(xiàn)抽象數(shù)據(jù)類型線性表時為: O( ListLength(La)ListLength(Lb) ) 當以鏈式映像實現(xiàn)抽象數(shù)據(jù)類型線性表時為: O( ListLength(La)ListLength(Lb) )例例2-1算法時間復(fù)雜度算法時間復(fù)雜度void purge(List &La, List Lb) InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); for

43、 (i = 1; i = Lb_len; i+) GetElem(Lb, i, e); if (ListEmpty(La) | !equal (en, e) ListInsert(La, +La_len, e); en = e; /for / purge控制結(jié)構(gòu)：控制結(jié)構(gòu)：基本操作：基本操作：for 循環(huán)GetElem 和 ListInsert當以順序映像實現(xiàn)抽象數(shù)據(jù)類型線性表時為: O( ListLength(Lb) )當以鏈式映像實現(xiàn)抽象數(shù)據(jù)類型線性表時為: O( ListLength2(Lb) )例例2-2算法時間復(fù)雜度算法時間復(fù)雜度void MergeList(List La, Lis

44、t Lb, List &Lc) InitList(Lc); i = j = 1; k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb); while (i = La_len) & (j = Lb_len) GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai next = L.current-next; L.current-next = s; if (L.tail = L.current) L.tail = s; L.current = s; return OK;Status De

45、lAfter( LinkList& L, ElemType& e ) / 若當前指針及其后繼在鏈表中，則刪除線性鏈表L中當前 / 指針所指結(jié)點之后的結(jié)點，并返回OK; 否則返回ERROR。 /DelAfterif ( !(L.current & L.current-next ) ) return ERROR;q = L.current-next;L.current-next = q-next;if (L.tail = q) L.tail = L.current;e=q-data; FreeNode(q);return OK; 例一例一Status ListInsert_

46、L(LinkList L, int i, ElemType e) / 在帶頭結(jié)點的單鏈線性表在帶頭結(jié)點的單鏈線性表 L 的第的第 i 個元素之前插入元素個元素之前插入元素 e / ListInsert_L 利用上述定義的線性鏈表如何完成利用上述定義的線性鏈表如何完成 線性表的其它操作線性表的其它操作 ？if (!LocatePos (L, i-1) return ERROR; / i 值不合法，第 i-1 個結(jié)點不存在if (InsAfter (L, e) return OK; / 完成插入else return ERROR;Status MergeList_L(LinkList &L

47、c, LinkList &La, LinkList &Lb ，int (*compare) (ElemType,ElemType) / 歸并有序表 La 和 Lb ,生成新的有序表 Lc, / 并在歸并之后銷毀La 和 Lb, / compare 為指定的元素大小判定函數(shù) / MergeList_L例二例二if ( !InitList(Lc) return ERROR; / 存儲空間分配失敗while (!( a=MAXC & b=MAXC) / La 或或 Lb 非空非空 LocatePos (La, 0); LocatePos (Lb, 0); / 當前指針指向頭結(jié)

48、點當前指針指向頭結(jié)點if ( DelAfter( La, e) a = e; / 取得取得 La 表中第一個元素表中第一個元素 aelse a = MAXC; / MAXC為常量最大值if ( DelAfter( Lb, e) b = e; / 取得取得 Lb 表中第一個元素表中第一個元素 belse b = MAXC; / a 和和 b 為兩表中當前比較元素為兩表中當前比較元素DestroyList(La); DestroyList(Lb); / 銷毀鏈表銷毀鏈表 La 和和 Lbreturn OK; if (*compare)(a, b) next = p-next; p-next = s

49、;s-next-prior = s; s-prior = p;psai-1ai插入插入ai-1刪除刪除aiai+1p-next = p-next-next;p-next-prior = p;pai-1六、有序表類型六、有序表類型ADT Ordered_List 數(shù)據(jù)對象數(shù)據(jù)對象: S = xi|xi OrderedSet ， i=1,2,n, n0 集合中任意兩個元素之間均可以進行比較數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系: :R = | xi-1, xi S, xi-1 xi, i=2,3,n 回顧例回顧例2-2的兩個算法的兩個算法 LocateElem( L, e, &q, int(*compare)(

50、ElemType,ElemType) )初始條件初始條件：有序表L已存在。操作結(jié)果操作結(jié)果：若有序表L中存在元素e，則 q指示L中第一個值為第一個值為 e 的元素的元素的位置，并返回函數(shù)值TRUE；否則 q 指示第一個大第一個大于于 e 的元素的前驅(qū)的元素的前驅(qū)的位置，并返回函數(shù)值FALSE。 基本操作：基本操作： Compare是一個是一個有序判定函數(shù)有序判定函數(shù)( 12, 23, 34, 45, 56, 67, 78, 89, 98, 45 )例如例如:若若 e = 45, 則則 q 指向指向 若若 e = 88, 則則 q 指向指向表示值為表示值為 88 的元素應(yīng)插入的元素應(yīng)插入在該指針

51、所指結(jié)點之后。在該指針所指結(jié)點之后。void union(List &La, List Lb) / Lb 為線性表 InitList(La); / 構(gòu)造(空的)線性表LA La_len=ListLength(La); Lb_len=ListLength(Lb); for (i = 1; i = Lb_len; i+) GetElem(Lb, i, e); / 取取Lb中第中第 i 個數(shù)據(jù)元素賦給個數(shù)據(jù)元素賦給 e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的數(shù)據(jù)元素，

52、則插入之相同的數(shù)據(jù)元素，則插入之 / union算法時間復(fù)雜度：算法時間復(fù)雜度：O(n2)void purge(List &La, List Lb) / Lb為有序表 InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); / 求線性表的長度求線性表的長度 for (i = 1; i = Lb_len; i+) / purge GetElem(Lb, i, e); / 取取Lb中第中第i個數(shù)據(jù)元素賦給個數(shù)據(jù)元素賦給 eif (ListEmpty(La) | !equal (en, e) ListInsert(La,

53、+La_len, e); en = e; / La中不存在和中不存在和 e 相同的數(shù)據(jù)元素，則插入之相同的數(shù)據(jù)元素，則插入之算法時間復(fù)雜度：算法時間復(fù)雜度：O(n)nnnxpxpxppxp.)(2210在計算機中，可以用一個線性表來表示在計算機中，可以用一個線性表來表示: P = (p0, p1, ，pn)一元多項式一元多項式但是對于形如但是對于形如 S(x) = 1 + 3x10000 2x20000的多項式，上述表示方法是否合適？的多項式，上述表示方法是否合適？ 一般情況下的一元稀疏多項式一元稀疏多項式可寫成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中其中：pi 是

54、指數(shù)為ei 的項的非零系數(shù)， 0 e1 e2 em = n可以下列線性表表示：（p1, e1）, (p2, e2), , (pm,em) ） P999(x) = 7x3 - 2x12 - 8x999例如例如:可用線性表 ( (7, 3), (-2, 12), (-8, 999) )表示ADT Polynomial 數(shù)據(jù)對象數(shù)據(jù)對象： 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：抽象數(shù)據(jù)類型一元多項式的定義如下：D ai | ai TermSet, i=1,2,.,m, m0 TermSet 中的每個元素包含一個每個元素包含一個 表示系數(shù)的實數(shù)和表示指數(shù)的整數(shù)表示系數(shù)的實數(shù)和表示指數(shù)的整數(shù) R1 |ai-1 ,aiD, i=2,.