數(shù)據(jù)結(jié)構(gòu)課程chap02線性表ppt課件

1、第二章第二章線性表線性表線性構(gòu)造的根本特征為線性構(gòu)造的根本特征為: :1集合中必存在獨(dú)一的一個(gè)集合中必存在獨(dú)一的一個(gè)“第一元素；第一元素；2集合中必存在獨(dú)一的一個(gè)集合中必存在獨(dú)一的一個(gè) “最后元素最后元素 ；3除最后元素在外，均有除最后元素在外，均有 獨(dú)一的后繼；獨(dú)一的后繼；4除第一元素之外，均有除第一元素之外，均有 獨(dú)一的前驅(qū)。獨(dú)一的前驅(qū)。線性構(gòu)造線性構(gòu)造 是是 一類(lèi)數(shù)據(jù)元素的有序次序集一類(lèi)數(shù)據(jù)元素的有序次序集線性表是一種最簡(jiǎn)單的線性構(gòu)造線性表是一種最簡(jiǎn)單的線性構(gòu)造表頭元素表尾元素線性表的邏輯構(gòu)造表示圖a1aia2ai+1an2.1 線性表的類(lèi)型定義線性表的類(lèi)型定義2.3 線性表類(lèi)型的實(shí)現(xiàn)線

2、性表類(lèi)型的實(shí)現(xiàn) 鏈?zhǔn)接诚箧準(zhǔn)接诚?.4 一元多項(xiàng)式的表示一元多項(xiàng)式的表示2.2 線性表類(lèi)型的實(shí)現(xiàn)線性表類(lèi)型的實(shí)現(xiàn) 順序映象順序映象2.1線性表的類(lèi)型定義線性表的類(lèi)型定義籠統(tǒng)數(shù)據(jù)類(lèi)型線性表的定義如下：ADT List 數(shù)據(jù)對(duì)象：D ai | ai ElemSet, i=1,2,.,n, n0 稱(chēng) n 為線性表的表長(zhǎng); 稱(chēng) n=0 時(shí)的線性表為空表。數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R1 |ai-1 ,aiD, i=2,.,n 設(shè)線性表為 (a1，a2, . . . ，ai，. . . ，an), 稱(chēng) i 為 ai 在線性表中的位序。 根本操作： 構(gòu)造初始化操作構(gòu)造銷(xiāo)毀操作構(gòu)造銷(xiāo)毀操作 援用型操作援用型操作 加

3、工型操作加工型操作 ADT List InitList( &L )操作結(jié)果：操作結(jié)果：構(gòu)造一個(gè)空的線性表L。初始化操作初始化操作 構(gòu)造銷(xiāo)毀操作構(gòu)造銷(xiāo)毀操作DestroyList( &L )初始條件：操作結(jié)果：線性表 L 已存在。銷(xiāo)毀線性表 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已存在。假設(shè)L為空表，那么前往TRUE，否那么FALSE。線性表判空ListLength( L )初始條件：操作結(jié)果：線性表L已存在。前往L中元素個(gè)數(shù)。求線性表的長(zhǎng)度 PriorElem( L, cur_e, &pre_e )初始條件：操作結(jié)果：線性表L已存在。假設(shè)cur_e是L的元素，但不是第一個(gè)，那么用pre_e 前往它的前驅(qū)，否那么操作失敗，pre_e無(wú)定義。求數(shù)據(jù)元素的前驅(qū)NextElem( L, cur_e, &next_e )初始條件：操作結(jié)果：線性表L已存在。假設(shè)cur_e是

5、L的元素，但不是最后一個(gè)，那么用next_e前往它的后繼，否那么操作失敗，next_e無(wú)定義。求數(shù)據(jù)元素的后繼GetElem( L, i, &e ) 初始條件： 操作結(jié)果：線性表L已存在，且 1iLengthList(L)。用 e 前往L中第 i 個(gè)元素的值。求線性表中某個(gè)數(shù)據(jù)元素LocateElem( L, e, compare( ) )初始條件：操作結(jié)果：線性表L已存在，e為給定值， compare( )是元素?cái)喽ê瘮?shù)。前往L中第1個(gè)與e滿足關(guān)系compare( )的元素的位序。假設(shè)這樣的元素不存在，那么前往值為0。定位函數(shù)LocateElem( L, e, compare( )

6、)定位函數(shù) ListTraverse(L, visit( )初始條件：操作結(jié)果：線性表L已存在，Visit() 為某個(gè)訪問(wèn)函數(shù)。依次對(duì)依次對(duì)L L的每個(gè)元素調(diào)用的每個(gè)元素調(diào)用函數(shù)函數(shù)visit( )visit( )。一旦。一旦visit( )visit( )失敗，那么操作失敗。失敗，那么操作失敗。遍歷線性表加工型操作加工型操作 ClearList( &L )PutElem( &L, i, &e )ListInsert( &L, i, e )ListDelete(&L, i, &e) ClearList( &L )初始條件：操作結(jié)果：線性表

7、L已存在。將L重置為空表。線性表置空PutElem( &L, i, &e )初始條件：操作結(jié)果：線性表L已存在，且 1iLengthList(L) 。L中第i個(gè)元素賦值同e的值。改動(dòng)數(shù)據(jù)元素的值 ListInsert( &L, i, e )初始條件：操作結(jié)果：線性表L已存在， 且 1iLengthList(L)+1 。在L的第i個(gè)元素之前插入新的元素e，L的長(zhǎng)度增1。插入數(shù)據(jù)元素ListDelete(&L, i, &e)初始條件：操作結(jié)果：線性表L已存在且非空， 1iLengthList(L) 。刪除L的第i個(gè)元素，并用e前往其值，L的長(zhǎng)度減1。刪除數(shù)據(jù)

8、元素利用上述定義的線性表 可以實(shí)現(xiàn)其它更復(fù)雜的操作例例 2-2例例 2-3例例 2-1 假設(shè):有兩個(gè)集合 A 和 B 分別用兩個(gè)線性表 LA 和 LB 表示，即：線性表中的數(shù)據(jù)元素即為集合中的成員。 現(xiàn)要求一個(gè)新的集合AAB。例例 2-1 2-1 要求對(duì)線性表作如下操作：擴(kuò)展線性表 LA，將存在于線性表LB 中而不存在于線性表 LA 中的數(shù)據(jù)元素插入到線性表 LA 中去。上述問(wèn)題可演繹為：1從線性表從線性表LB中依次察看每個(gè)數(shù)據(jù)元素中依次察看每個(gè)數(shù)據(jù)元素;2依值在線性表依值在線性表LA中進(jìn)展查訪中進(jìn)展查訪; 3假設(shè)不存在，那么插入之。假設(shè)不存在，那么插入之。GetElem(LB, i)e Lo

9、cateElem(LA, e, equal( ) ListInsert(LA, n+1, e)操作步驟：操作步驟： GetElem(Lb, i, e); / 取Lb中第i個(gè)數(shù)據(jù)元素賦給e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和 e 一樣的數(shù)據(jù)元素，那么插入之void union(List &La, List Lb) La_len = ListLength(La); / 求線性表的長(zhǎng)度求線性表的長(zhǎng)度 Lb_len = ListLength(Lb); for (i = 1; i = Lb

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

11、ocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和 e 一樣的數(shù)據(jù)元素，那么插入之for (i = 1; i = Lb_len; i+) InitList(La); / 構(gòu)造構(gòu)造(空的空的)線性表線性表LA假設(shè)線性表中的數(shù)據(jù)元素相互之間可以比較，并且數(shù)據(jù)元素在線性表中依值非遞減或非遞增有序陳列，即 aiai-1 或 aiai-1(i = 2,3, n)，那么稱(chēng)該線性表為有序表(Ordered List)。試改動(dòng)構(gòu)造，以有序表表示集合。例如：例如：2，3，3，5，6，6，6，8，12對(duì)集合 B 而言， 值一樣的數(shù)據(jù)元

12、素必定相鄰；對(duì)集合 A 而言， 數(shù)據(jù)元素依值從小至大的順序插入。因此，數(shù)據(jù)構(gòu)造改動(dòng)了， 處理問(wèn)題的戰(zhàn)略也相應(yīng)要改動(dòng)。void purge(List &La, List Lb) InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); / 求線性表的求線性表的長(zhǎng)度長(zhǎng)度 for (i = 1; i = Lb_len; i+) / purge GetElem(Lb, i, e); / 取Lb中第i個(gè)數(shù)據(jù)元素賦給 eif (ListEmpty(La) | !equal (en, e) ListInsert(La, +La_le

13、n, e); en = e; / La中不存在和 e 一樣的數(shù)據(jù)元素，那么插入之 / La 和 Lb 均非空，i = j = 1, k = 0 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) / 將 ai 插入到 Lc 中 ListInsert(Lc, +k, ai); +i; else / 將 bj 插入到 Lc 中 ListInsert(Lc, +k, bj); +j; void MergeList(List La, List Lb, List &Lc) / 本算法將非遞減的有序表本算法將非遞減的有序表 La 和和 Lb 歸

14、并為歸并為 Lc / merge_listwhile (i = La_len) & (j = Lb_len) / La 和和 Lb 均不空均不空 while (i=La_len) / 假設(shè)假設(shè) La 不空不空while (j=Lb_len) / 假設(shè)假設(shè) Lb 不空不空InitList(Lc); / 構(gòu)造空的線性表 Lci = j = 1; k = 0;La_len = ListLength(La);Lb_len = ListLength(Lb); while (i = La_len) / 當(dāng)當(dāng)La不空不空時(shí)時(shí) GetElem(La, i+, ai); ListInsert(Lc, +

15、k, ai); / 插入插入 La 表中剩余元素表中剩余元素 while (j = Lb_len) / 當(dāng)Lb不空時(shí) GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入 Lb 表中剩余元素最簡(jiǎn)單的一種順序映象方法是：最簡(jiǎn)單的一種順序映象方法是： 令令 y y 的存儲(chǔ)位置和的存儲(chǔ)位置和 x x 的存儲(chǔ)位置的存儲(chǔ)位置相鄰。相鄰。順序映象順序映象 以以 x 的存儲(chǔ)位置和的存儲(chǔ)位置和 y 的存儲(chǔ)位置的存儲(chǔ)位置之間某種關(guān)系表示邏輯關(guān)系之間某種關(guān)系表示邏輯關(guān)系。 用一組地址延續(xù)的存儲(chǔ)單元用一組地址延續(xù)的存儲(chǔ)單元 依次存放線性表中的數(shù)據(jù)元素依次存放線性表中的數(shù)

16、據(jù)元素 a1 a2 ai-1 ai an線性表的起始地址線性表的起始地址稱(chēng)作線性表的基地址稱(chēng)作線性表的基地址以“存儲(chǔ)位置相鄰表示有序?qū)?即：LOC(ai) = LOC(ai-1) + C 一個(gè)數(shù)據(jù)元素所占存儲(chǔ)量一切數(shù)據(jù)元素的存儲(chǔ)位置均取決于一切數(shù)據(jù)元素的存儲(chǔ)位置均取決于 第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置 LOC(ai) = LOC(a1) + (i-1)C 基地址基地址順序映像的順序映像的 C 言語(yǔ)描畫(huà)言語(yǔ)描畫(huà)typedef struct SqList; / 俗稱(chēng)俗稱(chēng) 順序表順序表#define LIST_INIT_SIZE 80 / 線性表存儲(chǔ)空間的初始分配量線性表存儲(chǔ)空間的

17、初始分配量#define LISTINCREMENT 10 / 線性表存儲(chǔ)空間的分配增量線性表存儲(chǔ)空間的分配增量ElemType *elem; / 存儲(chǔ)空間基址int length; / 當(dāng)前長(zhǎng)度當(dāng)前長(zhǎng)度int listsize; / 當(dāng)前分配的存儲(chǔ)容量當(dāng)前分配的存儲(chǔ)容量 / (以以sizeof(ElemType)為單位為單位)線性表的根本操作在順序表中的實(shí)現(xiàn)線性表的根本操作在順序表中的實(shí)現(xiàn)InitList(&L) / 構(gòu)造初始化構(gòu)造初始化LocateElem(L, e, compare() / 查找查找ListInsert(&L, i, e) / 插入元素插入元素ListDe

18、lete(&L, i) / 刪除元素刪除元素Status InitList_Sq( SqList& L ) / 構(gòu)造一個(gè)空的線性表構(gòu)造一個(gè)空的線性表 / InitList_Sq算法時(shí)間復(fù)雜度：O(1)L.elem = (ElemType*) malloc (LIST_ INIT_SIZEsizeof (ElemType);if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = LIST_INIT_SIZEreturn OK;例如：順序表23 75 41 38 54 62 17L.elemL.lengthL.listsizee

19、=38pppppi 1 2 3 4 1 850p可見(jiàn)，根本操作是：將順序表中的元素逐個(gè)和給定值 e 相比較。 int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在順序表中查詢第一個(gè)滿足斷定條件的數(shù)據(jù)元素， / 假設(shè)存在，那么前往它的位序，否那么前往 0 / LocateElem_Sq O( ListLength(L) )算法的時(shí)間復(fù)雜度為：算法的時(shí)間復(fù)雜度為：i = 1; / i 的初值為第 1 元素的位序p = L.elem; / p 的初值為第 1 元素的存儲(chǔ)位置while (i

20、= L.length & !(*compare)(*p+, e) +i;if (i = L.length) return i;else return 0;(*compare)( *p+, e)線性表操作 ListInsert(&L, i, e)的實(shí)現(xiàn)：首先分析首先分析:插入元素時(shí)，線性表的邏輯構(gòu)造發(fā)生什么變化？ (a1, , ai-1, ai, , an) 改動(dòng)為 (a1, , ai-1, e, ai, , an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean, 表的長(zhǎng)度添加 Status ListInsert_Sq(SqList &L, int i

21、, ElemType e) / 在順序表L的第 i 個(gè)元素之前插入新的元素e, / i 的合法范圍為 1iL.length+1 / ListInsert_Sq 算法時(shí)間復(fù)雜度為算法時(shí)間復(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; / 表長(zhǎng)增1return OK;元素右移元素右移思索挪動(dòng)元素的平均情況思索挪動(dòng)元素的平均情況: : 假設(shè)在第

22、i 個(gè)元素之前插入的概率為 ， 那么在長(zhǎng)度為n 的線性表中插入一個(gè)元素所需挪動(dòng)元素次數(shù)的期望值為：ip11) 1(niiisinpE11) 1(11niisinnE2n 假設(shè)假定在線性表中任何一個(gè)位置上進(jìn)展插入的概率都是相等的，那么挪動(dòng)元素的期望值為：if (L.length = L.listsize) / 當(dāng)前存儲(chǔ)空間已滿，添加分配當(dāng)前存儲(chǔ)空間已滿，添加分配 newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); / 存儲(chǔ)

23、分配失敗存儲(chǔ)分配失敗 L.elem = newbase; / 新基址新基址 L.listsize += LISTINCREMENT; / 添加存儲(chǔ)容添加存儲(chǔ)容量量if (i L.length+1) return ERROR; / 插入位置不合法插入位置不合法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.length-1); p = q; -p) *(p+1) = *p;p

24、線性表操作 ListDelete(&L, i, &e)的實(shí)現(xiàn)：首先分析：刪除元素時(shí)，線性表的邏輯構(gòu)造發(fā)生什么變化？ (a1, , ai-1, ai, ai+1, , an) 改動(dòng)為 (a1, , ai-1, ai+1, , an)ai+1 an, 表的長(zhǎng)度減少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; / 被刪除元素之后的元素左移被刪除元素之后

25、的元素左移-L.length; / 表長(zhǎng)減表長(zhǎng)減1return OK;算法時(shí)間復(fù)雜度為算法時(shí)間復(fù)雜度為: : O( ListLength(L)p = &(L.elemi-1); / p 為被刪除元素的位置e = *p; / 被刪除元素的值賦給 eq = L.elem+L.length-1; / 表尾元素的位置if (i L.length) return ERROR; / 刪除位置不合法刪除位置不合法元素左移元素左移思索挪動(dòng)元素的平均情況思索挪動(dòng)元素的平均情況: : 假設(shè)刪除第 i 個(gè)元素的概率為 , 那么在長(zhǎng)度為n 的線性表中刪除一個(gè)元素所需挪動(dòng)元素次數(shù)的期望值為：iqniidlinq

26、E1)(nidlinnE1)(121n假設(shè)假定在線性表中任何一個(gè)位置上進(jìn)展刪除的概率都是相等的，那么挪動(dòng)元素的期望值為：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; / p指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器while (p & jnext; +j; / 順指針向后查找，直到順指針向后查找，直到 p 指向第指向第 i 個(gè)元素個(gè)元素 / 或或 p 為空為空if ( !p | ji ) return ERROR;

27、/ 第第 i 個(gè)元素不存在個(gè)元素不存在e = p-data; / 獲得第獲得第 i 個(gè)元素個(gè)元素return OK;ai-1 線性表的操作 ListInsert(&L, i, e) 在單鏈表中的實(shí)現(xiàn)： 有序?qū)?改動(dòng)為 和 eaiai-1 因此，在單鏈表中第因此，在單鏈表中第 i 個(gè)結(jié)點(diǎn)之前進(jìn)個(gè)結(jié)點(diǎn)之前進(jìn)展插入的根本操作為展插入的根本操作為: 找到線性表中第找到線性表中第i-1個(gè)結(jié)點(diǎn)，然后修正個(gè)結(jié)點(diǎn)，然后修正其指向后繼的指針。其指向后繼的指針。 可見(jiàn)，在鏈表中插入結(jié)點(diǎn)只需求修正可見(jiàn)，在鏈表中插入結(jié)點(diǎn)只需求修正指針。但同時(shí)，假設(shè)要在第指針。但同時(shí)，假設(shè)要在第 i 個(gè)結(jié)點(diǎn)之個(gè)結(jié)點(diǎn)之前插入元素

28、，修正的是第前插入元素，修正的是第 i-1 個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的指針。指針。 Status ListInsert_L(LinkList L, int i, ElemType e) / L 為帶頭結(jié)點(diǎn)的單鏈表的頭指針，本算法為帶頭結(jié)點(diǎn)的單鏈表的頭指針，本算法 / 在鏈表中第在鏈表中第i 個(gè)結(jié)點(diǎn)之前插入新的元素個(gè)結(jié)點(diǎn)之前插入新的元素 e / LinstInsert_L算法的時(shí)間復(fù)雜度為算法的時(shí)間復(fù)雜度為:O(ListLength(L)p = L; j = 0;while (p & j next; +j; / 尋覓第 i-1 個(gè)結(jié)點(diǎn)if (!p | j i-1) return ERROR; /

29、i 大于表長(zhǎng)或者小于1 s = (LinkList) malloc ( sizeof (LNode); / 生成新結(jié)點(diǎn)s-data = e; s-next = p-next; p-next = s; / 插入return OK; eai-1aiai-1sp線性表的操作ListDelete (&L, i, &e)在鏈表中的實(shí)現(xiàn):有序?qū)τ行驅(qū)?和和 ai, ai+1 改動(dòng)為改動(dòng)為 ai-1aiai+1ai-1 在單鏈表中刪除第 i 個(gè)結(jié)點(diǎn)的根本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，修正其指向后繼的指針。ai-1aiai+1ai-1q = p-next; p-next = q-next

30、; e = q-data; free(q);pq Status ListDelete_L(LinkList L, int i, ElemType &e) / 刪除以刪除以 L 為頭指針為頭指針(帶頭結(jié)點(diǎn)帶頭結(jié)點(diǎn))的單鏈表中第的單鏈表中第 i 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) / ListDelete_L算法的時(shí)間復(fù)雜度為算法的時(shí)間復(fù)雜度為: O(ListLength(L)p = L; j = 0;while (p-next & j next; +j; / 尋覓第 i 個(gè)結(jié)點(diǎn)，并令 p 指向其前趨if (!(p-next) | j i-1) return ERROR; / 刪除位置不合理q = p-

31、next; p-next = q-next; / 刪除并釋放結(jié)點(diǎn)刪除并釋放結(jié)點(diǎn)e = q-data; free(q);return OK;操作 ClearList(&L) 在鏈表中的實(shí)現(xiàn):void ClearList(&L) / 將單鏈表重新置為一個(gè)空表將單鏈表重新置為一個(gè)空表 while (L-next) p=L-next; L-next=p-next; / ClearListfree(p);算法時(shí)間復(fù)雜度：O(ListLength(L)如何從線性表得到單鏈表？如何從線性表得到單鏈表？鏈表是一個(gè)動(dòng)態(tài)的構(gòu)造，它不需求鏈表是一個(gè)動(dòng)態(tài)的構(gòu)造，它不需求予分配空間，因此生成鏈表的過(guò)程予

32、分配空間，因此生成鏈表的過(guò)程是一個(gè)結(jié)點(diǎn)是一個(gè)結(jié)點(diǎn)“逐個(gè)插入逐個(gè)插入 的過(guò)程。的過(guò)程。例如：逆位序輸入例如：逆位序輸入 n n 個(gè)數(shù)據(jù)元素的值，個(gè)數(shù)據(jù)元素的值， 建立帶頭結(jié)點(diǎn)的單鏈表。建立帶頭結(jié)點(diǎn)的單鏈表。操作步驟：操作步驟：一、建立一個(gè)一、建立一個(gè)“空表；空表；二、輸入數(shù)據(jù)元素二、輸入數(shù)據(jù)元素anan， 建立結(jié)點(diǎn)并插入；建立結(jié)點(diǎn)并插入；三、輸入數(shù)據(jù)元素三、輸入數(shù)據(jù)元素an-1an-1， 建立結(jié)點(diǎn)并插入；建立結(jié)點(diǎn)并插入；ananan-1四、依次類(lèi)推，直至輸入四、依次類(lèi)推，直至輸入a1a1為止。為止。void CreateList_L(LinkList &L, int n) / 逆序輸入逆

33、序輸入 n 個(gè)數(shù)據(jù)元素，建立帶頭結(jié)個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表點(diǎn)的單鏈表 / CreateList_L算法的時(shí)間復(fù)雜度為算法的時(shí)間復(fù)雜度為:O(Listlength(L)L = (LinkList) malloc (sizeof (LNode);L-next = NULL; / 先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); scanf(&p-data); / 輸入元素值輸入元素值 p-next = L-next; L-next = p; / 插入插入回想回想 2.1 2.1 節(jié)中三個(gè)

34、例子的算法，節(jié)中三個(gè)例子的算法，看一下當(dāng)線性表分別以順序存看一下當(dāng)線性表分別以順序存儲(chǔ)構(gòu)造和鏈表存儲(chǔ)構(gòu)造實(shí)現(xiàn)時(shí)，儲(chǔ)構(gòu)造和鏈表存儲(chǔ)構(gòu)造實(shí)現(xiàn)時(shí)，它們的時(shí)間復(fù)雜度為多少？它們的時(shí)間復(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控制構(gòu)造

35、：控制構(gòu)造：根本操作：根本操作：for 循環(huán)循環(huán)GetElem, LocateElem 和和 ListInsert當(dāng)以順序映像實(shí)現(xiàn)籠統(tǒng)數(shù)據(jù)類(lèi)型線性表時(shí)為: O( ListLength(La)ListLength(Lb) ) 當(dāng)以鏈?zhǔn)接诚駥?shí)現(xiàn)籠統(tǒng)數(shù)據(jù)類(lèi)型線性表時(shí)為: O( ListLength(La)ListLength(Lb) )例例2-1算法時(shí)間復(fù)雜度算法時(shí)間復(fù)雜度void purge(List &La, List Lb) InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); for (i = 1; i = Lb

36、_len; i+) GetElem(Lb, i, e); if (ListEmpty(La) | !equal (en, e) ListInsert(La, +La_len, e); en = e; /for / purge控制構(gòu)造：控制構(gòu)造：根本操作：根本操作：for 循環(huán)GetElem 和 ListInsert當(dāng)以順序映像實(shí)現(xiàn)籠統(tǒng)數(shù)據(jù)類(lèi)型線性表時(shí)為: O( ListLength(Lb) )當(dāng)以鏈?zhǔn)接诚駥?shí)現(xiàn)籠統(tǒng)數(shù)據(jù)類(lèi)型線性表時(shí)為: O( ListLength2(Lb) )例例2-2算法時(shí)間復(fù)雜度算法時(shí)間復(fù)雜度void MergeList(List La, List Lb, List &

37、;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 DelAfter( LinkLis

38、t& L, ElemType& e ) / 假設(shè)當(dāng)前指針及其后繼在鏈表中，那么刪除線性鏈表假設(shè)當(dāng)前指針及其后繼在鏈表中，那么刪除線性鏈表L中當(dāng)前中當(dāng)前 / 指針?biāo)附Y(jié)點(diǎn)之后的結(jié)點(diǎn)，并前往指針?biāo)附Y(jié)點(diǎn)之后的結(jié)點(diǎn)，并前往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)

39、;return OK;Status MergeList_L(LinkList &Lc, LinkList &La, LinkList &Lb ，int (*compare) (ElemType,ElemType) / 歸并有序表歸并有序表 La 和和 Lb ,生成新的有序表生成新的有序表 Lc, / 并在歸并之后銷(xiāo)毀并在歸并之后銷(xiāo)毀La 和和 Lb, / compare 為指定的元素大小斷定函數(shù)為指定的元素大小斷定函數(shù) / MergeList_L例二例二if ( !InitList(Lc) return ERROR; / 存儲(chǔ)空間分配失敗存儲(chǔ)空間分配失敗while (!

40、( a=MAXC & b=MAXC) / La 或或 Lb 非空非空 LocatePos (La, 0); LocatePos (Lb, 0); / 當(dāng)前指針指向頭結(jié)點(diǎn)if ( DelAfter( La, e) a = e; / 獲得獲得 La 表中第一個(gè)元素表中第一個(gè)元素 aelse a = MAXC; / MAXC為常量最大值為常量最大值if ( DelAfter( Lb, e) b = e; / 獲得獲得 Lb 表中第一個(gè)元素表中第一個(gè)元素 belse b = MAXC; / a 和和 b 為兩表中當(dāng)前比較元素為兩表中當(dāng)前比較元素DestroyList(La); DestroyL

41、ist(Lb); / 銷(xiāo)毀鏈表 La 和 Lbreturn OK; if (*compare)(a, b) next = p-next; p-next = s;s-next-prior = s; s-prior = p;psai-1ai插入插入ai-1刪除刪除aiai+1p-next = p-next-next;p-next-prior = p;pai-1六、有序表類(lèi)型六、有序表類(lèi)型ADT Ordered_List 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象: S = xi|xi OrderedSet ， i=1,2,n, n0 集合中恣意兩個(gè)元素之間均可以進(jìn)展比較數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系:R = | xi-1, xi :R

42、= | xi-1, xi S, S, xi-1 xi, i=2,3,n xi-1 xi, i=2,3,n 回想例回想例2-2的兩個(gè)算法的兩個(gè)算法 LocateElem( L, e, &q, int(*compare)(ElemType,ElemType) )初始條件：有序表L已存在。操作結(jié)果：假設(shè)有序表L中存在元素e，那么 q指示L中第一個(gè)值為 e 的元素的位置，并前往函數(shù)值TRUE；否那么 q 指示第一個(gè)大于 e 的元素的前驅(qū)的位置，并前往函數(shù)值FALSE。 根本操作： Compare是一個(gè)是一個(gè)有序斷定函數(shù)有序斷定函數(shù)( 12, 23, 34, 45, 56, 67, 78, 89

43、, 98, 45 )例如例如:假設(shè)假設(shè) e = 45, 那么那么 q 指指向向 假設(shè)假設(shè) e = 88, 那么那么 q 指向指向表示值為表示值為 88 的元素應(yīng)插入的元素應(yīng)插入在該指針?biāo)附Y(jié)點(diǎn)之后。在該指針?biāo)附Y(jié)點(diǎn)之后。void union(List &La, List Lb) / Lb 為線性表為線性表 InitList(La); / 構(gòu)造構(gòu)造(空的空的)線性表線性表LA La_len=ListLength(La); Lb_len=ListLength(Lb); for (i = 1; i = Lb_len; i+) GetElem(Lb, i, e); / 取取Lb中第中第 i 個(gè)

44、數(shù)據(jù)元素賦給個(gè)數(shù)據(jù)元素賦給 e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 一樣的數(shù)據(jù)元素，那么插入之一樣的數(shù)據(jù)元素，那么插入之 / union算法時(shí)間復(fù)雜度：算法時(shí)間復(fù)雜度：O(n2)void purge(List &La, List Lb) / Lb為有序表為有序表 InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); / 求線性表的長(zhǎng)度求線性表的長(zhǎng)度 for (i = 1; i = Lb_len;

45、 i+) / purge GetElem(Lb, i, e); / 取Lb中第i個(gè)數(shù)據(jù)元素賦給 eif (ListEmpty(La) | !equal (en, e) ListInsert(La, +La_len, e); en = e; / La中不存在和 e 一樣的數(shù)據(jù)元素，那么插入之算法時(shí)間復(fù)雜度：算法時(shí)間復(fù)雜度：O(n)nnnxpxpxppxp.)(2210在計(jì)算機(jī)中，可以用一個(gè)線性表來(lái)表示在計(jì)算機(jī)中，可以用一個(gè)線性表來(lái)表示: : P = (p0, p1, P = (p0, p1, ，pn)pn)一元多項(xiàng)式一元多項(xiàng)式但是對(duì)于形如但是對(duì)于形如 S(x) = 1 + 3x10000 2x2

46、0000的多項(xiàng)式，上述表示方法能否適宜？的多項(xiàng)式，上述表示方法能否適宜？ 普通情況下的一元稀疏多項(xiàng)式可寫(xiě)成 Pn(x) = p1xe1 + p2xe2 + + pmxem其中：pi 是指數(shù)為ei 的項(xiàng)的非零系數(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ù)對(duì)象：數(shù)據(jù)對(duì)象： 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：籠統(tǒng)數(shù)據(jù)類(lèi)型一元多項(xiàng)式的定義如下：D ai | ai TermSe

47、t, i=1,2,.,m, m0 TermSet 中的每個(gè)元素包含一個(gè)中的每個(gè)元素包含一個(gè) 表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù)表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù) R1 |ai-1 ,aiD, i=2,.,n 且且ai-1中的指數(shù)值中的指數(shù)值ai中的指數(shù)值中的指數(shù)值 CreatPolyn ( &P, m ) DestroyPolyn ( &P ) PrintPolyn ( &P ) 根本操作：根本操作：操作結(jié)果：輸入操作結(jié)果：輸入 m 項(xiàng)的系數(shù)和指數(shù)，項(xiàng)的系數(shù)和指數(shù)， 建立一元多項(xiàng)式建立一元多項(xiàng)式 P。初始條件：一元多項(xiàng)式初始條件：一元多項(xiàng)式 P 已存在。已存在。操作結(jié)果：銷(xiāo)毀一

48、元多項(xiàng)式操作結(jié)果：銷(xiāo)毀一元多項(xiàng)式 P。初始條件：一元多項(xiàng)式初始條件：一元多項(xiàng)式 P 已存在。已存在。操作結(jié)果：打印輸出一元多項(xiàng)式操作結(jié)果：打印輸出一元多項(xiàng)式 P。 PolynLength( P ) AddPolyn ( &Pa, &Pb ) SubtractPolyn ( &Pa, &Pb ) ADT Polynomial初始條件：一元多項(xiàng)式初始條件：一元多項(xiàng)式 P 已存在。已存在。操作結(jié)果：前往一元多項(xiàng)式操作結(jié)果：前往一元多項(xiàng)式 P 中的項(xiàng)數(shù)。中的項(xiàng)數(shù)。初始條件：一元多項(xiàng)式初始條件：一元多項(xiàng)式 Pa 和和 Pb 已存在。已存在。操作結(jié)果：完成多項(xiàng)式相加運(yùn)算，即：操作結(jié)果：完成多項(xiàng)式相加運(yùn)算，即： Pa = PaPb，并銷(xiāo)毀一元多項(xiàng)式，并銷(xiāo)毀一元多項(xiàng)式 Pb。一元多項(xiàng)式的實(shí)現(xiàn)：一元多項(xiàng)式的實(shí)現(xiàn)：typedef struct / 項(xiàng)的表示項(xiàng)的表示 float coef; / 系數(shù)系數(shù) int expn; / 指數(shù)指數(shù) term, ElemType; typedef OrderedLinkList polynomial; / 用帶表頭結(jié)點(diǎn)的有序鏈表表示多項(xiàng)式用帶表頭結(jié)點(diǎn)的有序鏈表表示多項(xiàng)式結(jié)點(diǎn)的