第二章線性表

1、 線性結(jié)構(gòu)的線性結(jié)構(gòu)的特點(diǎn)特點(diǎn)： 在數(shù)據(jù)元素的有限集合中：在數(shù)據(jù)元素的有限集合中：l存在存在的一個(gè)被稱作的一個(gè)被稱作“”的數(shù)據(jù)元素的數(shù)據(jù)元素l存在存在的一個(gè)被稱作的一個(gè)被稱作“”的數(shù)據(jù)元素的數(shù)據(jù)元素l除第一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均除第一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均l除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均2.1 線性表的類型定義線性表的類型定義2.3 線性表類型的實(shí)現(xiàn)線性表類型的實(shí)現(xiàn) 鏈?zhǔn)接诚箧準(zhǔn)接诚?.4 一元多項(xiàng)式的表示一元多項(xiàng)式的表示2.2 線性表類型的實(shí)現(xiàn)線性表類型的實(shí)現(xiàn) 順序映象順序映象2.5 小結(jié)及習(xí)題小結(jié)及習(xí)題l定義：一個(gè)線性表是定義：一個(gè)線性

2、表是n n個(gè)數(shù)據(jù)元素的有限序列個(gè)數(shù)據(jù)元素的有限序列niaaaa,21如例例1 英文字母表（英文字母表（A,B,C,Z)是一個(gè)線性表是一個(gè)線性表例例2學(xué)號(hào)姓名年齡001張三18002李四19數(shù)據(jù)元素?cái)?shù)據(jù)元素l特征：特征：u元素個(gè)數(shù)元素個(gè)數(shù)n(n0) 稱為稱為表長度，表長度，n=0空表空表u1in時(shí)時(shí)uai的直接的直接前驅(qū)前驅(qū)是是ai-1，a1無直接前驅(qū)無直接前驅(qū)uai的直接的直接后繼后繼是是ai+1，an無直接后繼無直接后繼u元素同構(gòu)元素同構(gòu)（屬于同一數(shù)據(jù)對(duì)象）（屬于同一數(shù)據(jù)對(duì)象），且不能出現(xiàn)缺項(xiàng)，且不能出現(xiàn)缺項(xiàng) 記錄記錄文件文件抽象數(shù)據(jù)類型線性表線性表的定義如下：ADT List 數(shù)據(jù)對(duì)象數(shù)據(jù)

3、對(duì)象：D ai | ai ElemSet, i=1,2,.,n, n0 其中n 為線性表的表長表長; 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：R1 |ai-1 ,aiD, i=2,.,n 設(shè)線性表為設(shè)線性表為 (a1，a2, . . . ，ai，. . . ，an), 稱稱 i 為為 ai 在線性表中的在線性表中的位序位序。 基本操作：基本操作： 結(jié)構(gòu)初始化操作結(jié)構(gòu)初始化操作結(jié)構(gòu)銷毀操作結(jié)構(gòu)銷毀操作 引用型操作引用型操作 加工型操作加工型操作 ADT List InitList( &L )操作結(jié)果：操作結(jié)果：構(gòu)造一個(gè)空的線性表L。初始化操作初始化操作 結(jié)構(gòu)銷毀操作結(jié)構(gòu)銷毀操作DestroyList( &am

4、p;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( )引用型操作引用型操作: : ListEmpty( L )初始條件：操作結(jié)果：線性表L已存在。若L為空表，則返回TRUE，否則FALSE。（線性表判空）ListLength( L )初始條件

5、：操作結(jié)果：線性表L已存在。返回L中元素個(gè)數(shù)。（求線性表的長度） PriorElem( L, cur_e, &pre_e )初始條件：操作結(jié)果：線性表L已存在。若cur_e是L的元素，但不是第一個(gè)，則用pre_e 返回它的前驅(qū)，否則操作失敗，pre_e無定義。（求數(shù)據(jù)元素的前驅(qū)）NextElem( L, cur_e, &next_e )初始條件：操作結(jié)果：線性表L已存在。若cur_e是L的元素，但不是最后一個(gè)，則用next_e返回它的后繼，否則操作失敗，next_e無定義。（求數(shù)據(jù)元素的后繼）GetElem( L, i, &e ) 初始條件： 操作結(jié)果：線性表L已存在，

6、且 1iLengthList(L)用 e 返回L中第 i 個(gè)元素的值。（求線性表中某個(gè)數(shù)據(jù)元素）LocateElem( L, e, compare( ) )初始條件：操作結(jié)果：線性表L已存在，e為給定值， compare( )是元素判定函數(shù)。返回L中第中第1個(gè)個(gè)與e滿足滿足關(guān)系compare( )的元素的位序。若這樣的元素不存在，則返回值為0。（定位函數(shù)） ListTraverse(L, visit( )初始條件：操作結(jié)果：線性表L已存在。Visit() 為某個(gè)訪問函數(shù)。依次依次對(duì)L的每個(gè)元素調(diào)用函數(shù)visit( )。一旦visit( )失敗，則操作失敗。（遍歷線性表）加工型操作加工型操作 C

7、learList( &L )ListInsert( &L, i, e )ListDelete(&L, i, &e) ClearList( &L )初始條件：操作結(jié)果：線性表L已存在。將L重置為空表。（線性表置空） ListInsert( &L, i, e )初始條件：操作結(jié)果：線性表L已存在， 且 1iLengthList(L)+1在L的第i個(gè)元素之前插入插入新的元素e，L的長度增1。（插入數(shù)據(jù)元素）ListDelete(&L, i, &e)初始條件：操作結(jié)果：線性表L已存在且非空， 1iLengthList(L)刪除L的第i個(gè)元

8、素，并用e返回其值，L的長度減1。（刪除數(shù)據(jù)元素）利用上述定義的線性表線性表 可以實(shí)現(xiàn)其它更復(fù)雜的操作例例 2-2例例 2-3例例 2-1 假設(shè):有兩個(gè)集合集合 A 和和 B 分別用兩個(gè)線性表線性表 LA 和和 LB 表示，即：線性表中的數(shù)據(jù)元素即為集合中的成員。 現(xiàn)要求一個(gè)新的集合現(xiàn)要求一個(gè)新的集合AAB。例例 2-1 要求對(duì)線性表作如下操作：擴(kuò)大線性表 LA，將存在于線性表存在于線性表LB 中中而不存在于線性表不存在于線性表 LA 中中的數(shù)據(jù)元素插入到線性表插入到線性表 LA 中中去。上述問題可演繹為：1從線性表LB中依次察看每個(gè)數(shù)據(jù)元素;2對(duì)其在線性表LA中進(jìn)行比較; 3若不存在，則插入

9、之。GetElem(LB, i,e) LocateElem(LA, e, equal( ) ListInsert(LA, +n, e)操作步驟：操作步驟： GetElem(Lb, i, e); / 取取Lb中第中第i個(gè)數(shù)據(jù)元素賦給個(gè)數(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); / 求線性表的長度求線性表的

10、長度 Lb_len = ListLength(Lb); for (i = 1; i = Lb_len; i+) / union 已知已知一個(gè) B，試構(gòu)造構(gòu)造一個(gè) A，使使 A 包含包含 B 中所有出現(xiàn)過中所有出現(xiàn)過的數(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);

11、 / union GetElem(Lb, i, e); / 取取Lb中第中第 i 個(gè)數(shù)據(jù)元素賦給個(gè)數(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,

12、n)，則稱該線性表為試改變結(jié)構(gòu)，以有序表有序表表示集合。例如例如:（2，3，3，5，6，6，6，8，12）對(duì)集合 B 而言， 值相同的數(shù)據(jù)元素必定相鄰值相同的數(shù)據(jù)元素必定相鄰對(duì)集合 A 而言， 數(shù)據(jù)元素依值從小至大的順序插入數(shù)據(jù)元素依值從小至大的順序插入因此，數(shù)據(jù)結(jié)構(gòu)改變了，數(shù)據(jù)結(jié)構(gòu)改變了， 解決問題的策略也相應(yīng)要改變。解決問題的策略也相應(yīng)要改變。例例 2-2 已知已知一個(gè)非純集合非純集合 B，試構(gòu)造構(gòu)造一個(gè)純集合純集合 A，使使 A 包含包含 B 中所有出現(xiàn)過的數(shù)據(jù)元素中所有出現(xiàn)過的數(shù)據(jù)元素。 （用非遞減有序的順序表表示A、B）void purge(List &La, List Lb

13、) InitList(La); La_len = ListLength(La); Lb_len =ListLength(Lb); / 求線性表的長度求線性表的長度 for (i = 1; i = Lb_len; i+) / purge GetElem(Lb, i, e); / 取取Lb中第中第i個(gè)數(shù)據(jù)元素賦給個(gè)數(shù)據(jù)元素賦給 eif (!equal (en, e) ListInsert(La, +La_len, e); en = e; / La中不存在和中不存在和 e 相同的數(shù)據(jù)元素，則插入之相同的數(shù)據(jù)元素，則插入之則則 歸并兩個(gè)“其數(shù)據(jù)元素按值非遞減有其數(shù)據(jù)元素按值非遞減有序排列序排列”的有序

14、表 LA 和 LB，求得有序表 LC 也具有同樣特性。設(shè)設(shè) La = (a1, , ai, , an), Lb = (b1, , bj, , bm) Lc = (c1, , ck, , cm+n)且且已由(a1, , ai-1)和(b1, ,bj-1)歸并得歸并得 (c1, , ck-1)jijjiikbabbaac例例 2-3k = 1, 2, , m+n1初始化初始化 LC 為空表；為空表；基本操作：2分別從分別從 LA和和LB中取得當(dāng)前元素中取得當(dāng)前元素 ai 和和 bj；3若若 aibj，則將，則將 ai 插入到插入到 LC 中，否則將中，否則將 bj 插入到插入到 LC 中；中；4重

15、復(fù)重復(fù) 2 和和 3 兩步，直至兩步，直至 LA 或或 LB 中元素中元素 被取完為止；被取完為止；5將將 LA 表或表或 LB 表中剩余元素復(fù)制插入到表中剩余元素復(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); +i; else / 將 bj 插入到 Lc 中 ListInsert(Lc, +k, bj); +j; void MergeList(List La, L

16、ist 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(La);Lb_len = ListLength(Lb); while (i = La_len) / 當(dāng)La不空時(shí) GetElem(L

17、a, i+, ai); ListInsert(Lc, +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ù)地址連續(xù)的存儲(chǔ)

18、單元 依次存放依次存放線性表中的數(shù)據(jù)元素 a1 a2 ai-1 ai an線性表的線性表的起始地址起始地址，稱作線性表的基地址基地址以“存儲(chǔ)位置相鄰存儲(chǔ)位置相鄰”表示有序?qū)?即：LOC(ai) = LOC(ai-1) + C 所有數(shù)據(jù)元素的存儲(chǔ)位置均取決于所有數(shù)據(jù)元素的存儲(chǔ)位置均取決于 第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置 LOC(ai) = LOC(a1) + (i-1)C 基地址基地址順序映象的順序映象的 C 語言描述語言描述typedef struct SqList; / 也稱 順序表順序表#define LIST_INIT_SIZE 80 / 線性表存儲(chǔ)空間的初始分配量#d

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

20、tList_Sq( SqList& L, int maxsize ) / 構(gòu)造一個(gè)最大容量為 maxsize 的順序表 / InitList_Sq算法時(shí)間復(fù)雜度時(shí)間復(fù)雜度：O(1)L.elem = new ElemTypemaxsize; / 為順序表分配大小為 maxsize 的數(shù)組空間if (!L.elem) exit(OVERFLOW);L.length = 0;L.listsize = maxsize;return OK;順序表的查找 例如：23 75 41 38 54 62 17L.elemL.length = 7L.listsizee =38pppppi 1 2 3 4 1

21、 850p查找的基本操作是查找的基本操作是: : 將順序表中的將順序表中的 元素逐個(gè)和給定元素逐個(gè)和給定 值值e e相比較。相比較。查找成功，返回i值！查找不成功，返回0！p int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在順序表中查詢第一個(gè)滿足判定條件的數(shù)據(jù)元素，在順序表中查詢第一個(gè)滿足判定條件的數(shù)據(jù)元素， / 若存在，則返回它的位序，否則返回若存在，則返回它的位序，否則返回 0 0 / LocateElem_Sq O( ListLength(L) )算法的算法的時(shí)間復(fù)雜度時(shí)間復(fù)

22、雜度為：為：i = 1; / i i 的初值為第的初值為第 1 1 元素的位序元素的位序p = L.elem; / p p 的初值為第的初值為第 1 1 元素的存儲(chǔ)位置元素的存儲(chǔ)位置while (i = 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í)，線性表的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)發(fā)生什么變化發(fā)生什么變化？ (a1, , ai-1, ai, , an) 改變

23、為a1 a2 ai-1 ai ana1 a2 ai-1 ai ean, 表的長度增加(a1, , ai-1, e, ai, , an) Status ListInsert_Sq(SqList &L, int i, 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; -

24、p) *(p+1) = *p; / 插入位置及之后的元素右移元素右移*q = e; / 插入e+L.length; / 表長增1return OK;元素右移元素右移（合法性檢查、分配空間滿需追加空間等）（合法性檢查、分配空間滿需追加空間等）if (L.length = L.listsize) / 當(dāng)前存儲(chǔ)空間已滿，增加分配 newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); / 存儲(chǔ)分配失敗 L.elem = newba

25、se; / 新基址 L.listsize += LISTINCREMENT; / 增加存儲(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考慮移動(dòng)元素的平均情況考慮移動(dòng)元素的平均情況: : 假設(shè)在第 i 個(gè)元素之前插入的

26、概率為 ， 則在長度為n 的線性表中插入一個(gè)元素所需插入一個(gè)元素所需移動(dòng)元素次數(shù)的期望值移動(dòng)元素次數(shù)的期望值為：ip11) 1(niiisinpE11) 1(11niisinnE2n 若假定假定在線性表中任何一個(gè)位置上進(jìn)行插入插入的概率的概率都是相等相等的，則移動(dòng)元素的期望值移動(dòng)元素的期望值為：線性表操作 ListDelete(&L, i, &e)的實(shí)現(xiàn)：首先分析：刪除元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？ (a1, , ai-1, ai, ai+1, , an) 改變?yōu)閍i+1 an, 表的長度減少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 (a1, ,

27、ai-1, ai+1, , an)Status ListDelete_Sq (SqList &L, int i, ElemType &e) / ListDelete_Sqfor (+p; p = q; +p) *(p-1) = *p; / 被刪除元素之后的元素左移被刪除元素之后的元素左移-L.length; / 表長減表長減1 1return OK;為為: : O( ListLength(L)p = &(L.elemi-1); / p 為被刪除元素的位置為被刪除元素的位置e = *p; / 被刪除元素的值賦給被刪除元素的值賦給 eq = L.elem+L.length-

28、1; / 表尾元素的位置表尾元素的位置if (i L.length) return ERROR; / 刪除位置不合法刪除位置不合法元素左移元素左移考慮移動(dòng)元素的平均情況考慮移動(dòng)元素的平均情況: : 假設(shè)刪除第 i 個(gè)元素的概率為 , 則在長度為n 的線性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值移動(dòng)元素次數(shù)的期望值為：iqniidlinqE1)(nidlinnE1)(121n若假定在線性表中任何一個(gè)位置上進(jìn)行刪除的概率都是相等的，則移動(dòng)元素的期望值移動(dòng)元素的期望值為：21 18 30 75 42 56 8721 18 30 75L.length-10pppq8756p = &(L.ele

29、mi-1);q = L.elem+L.length-1;for (+p; p next; j = 1; / p p指向第一個(gè)結(jié)點(diǎn)，指向第一個(gè)結(jié)點(diǎn)，j j為計(jì)數(shù)器為計(jì)數(shù)器while (p & jnext; +j; / 順指針向后查找，直到順指針向后查找，直到 p p 指向第指向第 i i 個(gè)元素個(gè)元素 / 或或 p p 為空為空if ( !p | ji ) return ERROR; / 第第 i i 個(gè)元素不存在個(gè)元素不存在e = p-data; / 取得第取得第 i i 個(gè)元素個(gè)元素return OK;ai-1 線性表的操作 ListInsert(&L, i, e) 在單鏈表

30、中的實(shí)現(xiàn)： 有序?qū)τ行驅(qū)?改變?yōu)楦淖優(yōu)?和和 eaiai-1 因此，在單鏈表中第因此，在單鏈表中第 i 個(gè)結(jié)點(diǎn)之前進(jìn)個(gè)結(jié)點(diǎn)之前進(jìn)行插入的基本操作為行插入的基本操作為: 找到線性表中第找到線性表中第i-1i-1個(gè)結(jié)點(diǎn)，然后修改個(gè)結(jié)點(diǎn)，然后修改其指向后繼的指針。其指向后繼的指針。 可見，在鏈表中插入結(jié)點(diǎn)只需要修改可見，在鏈表中插入結(jié)點(diǎn)只需要修改指針。但同時(shí)，若要在第指針。但同時(shí)，若要在第 i 個(gè)結(jié)點(diǎn)之前個(gè)結(jié)點(diǎn)之前插入元素，修改的是第插入元素，修改的是第 i-1 個(gè)結(jié)點(diǎn)的指?jìng)€(gè)結(jié)點(diǎn)的指針。針。 Status ListInsert_L(LinkList L, int i, ElemType e) / L

31、 為帶頭結(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)個(gè)結(jié)點(diǎn)if (!p | j i-1) return ERROR; / i 大于表長或者小于大于表長或者小于1 s = new LNode; / 生成新結(jié)點(diǎn)s-data = e; s-next = p-next; p-next = s; /

32、插入return OK; eai-1aiai-1sp在鏈表的第在鏈表的第i個(gè)位置上插入元素：個(gè)位置上插入元素： （先查找插入位置）前插（先查找插入位置）前插/后插后插 O(n)；在指針在指針p所指的結(jié)點(diǎn)上插入元素：所指的結(jié)點(diǎn)上插入元素： 前插前插O(n),后插后插O(1) 前插如何改進(jìn)前插如何改進(jìn)?的操作ListDelete (&L, i, &e)在鏈表中的實(shí)現(xiàn):有序?qū)τ行驅(qū)?和和 改變?yōu)楦淖優(yōu)?ai-1aiai+1ai-1 在單鏈表中刪除第刪除第 i i 個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)的基本基本操作操作為:找到線性表中第找到線性表中第i-1i-1個(gè)結(jié)點(diǎn)，修個(gè)結(jié)點(diǎn)，修改其指向后繼的指針。改其指向

33、后繼的指針。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é)點(diǎn))的單鏈表中第 i 個(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) re

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

35、預(yù)分配空間，因此生成鏈表的過程生成鏈表的過程是一個(gè)結(jié)點(diǎn)是一個(gè)結(jié)點(diǎn)“逐個(gè)插入逐個(gè)插入” ” 的過程。的過程。1、由表頭插入：得到逆序 - 頭插法2、由表尾插入：得到正序 - 尾插法例如：逆位序輸入例如：逆位序輸入 n n 個(gè)數(shù)據(jù)元素的值，個(gè)數(shù)據(jù)元素的值， 建立帶頭結(jié)點(diǎn)的單鏈表。建立帶頭結(jié)點(diǎn)的單鏈表。操作步驟：操作步驟：一、建立一個(gè)一、建立一個(gè)“空表空表”；二、輸入數(shù)據(jù)元素二、輸入數(shù)據(jù)元素an， 建立結(jié)點(diǎn)并插入；建立結(jié)點(diǎn)并插入；三、輸入數(shù)據(jù)元素三、輸入數(shù)據(jù)元素an-1， 建立結(jié)點(diǎn)并插入；建立結(jié)點(diǎn)并插入；ananan-1四、依次類推，直至輸入四、依次類推，直至輸入a a1 1為止。為止。void H

36、CreateList_L(LinkList &L, int n) / 逆序輸入 n 個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表 / HCreateList_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; / 插

37、入void TCreateList_L(LinkList &L, int n) / 順序輸入 n 個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表 / TCreateList_L算法的算法的時(shí)間復(fù)雜度時(shí)間復(fù)雜度為:O(Listlength(L)L = (LinkList) malloc (sizeof (LNode);L-next = NULL; / 先建立一個(gè)帶頭結(jié)點(diǎn)的空單鏈表 / q始終指向表尾結(jié)點(diǎn)用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時(shí)，用上述定義的單鏈表實(shí)現(xiàn)線性表的操作時(shí)，存在的存在的問題問題： 改進(jìn)鏈表的設(shè)置：改進(jìn)鏈表的設(shè)置：1單鏈表的表長是一個(gè)隱含的值；單鏈表的表長是一個(gè)隱含的值； 1增加增加

38、“表長表長”、“表尾指針表尾指針” 和和 “當(dāng)前當(dāng)前位置的位置的 指針指針” 三個(gè)數(shù)據(jù)域；三個(gè)數(shù)據(jù)域；2在單鏈表的最后一個(gè)元素之后插入元素時(shí)，在單鏈表的最后一個(gè)元素之后插入元素時(shí)， 需遍歷整個(gè)鏈表；需遍歷整個(gè)鏈表；3在鏈表中，元素的在鏈表中，元素的“位序位序”概念淡化，結(jié)點(diǎn)的概念淡化，結(jié)點(diǎn)的 “位置位置”概念加強(qiáng)。概念加強(qiáng)。2將基本操作中的將基本操作中的“位序位序 i ”改變?yōu)楦淖優(yōu)椤爸羔樦羔?p ”。 1. 雙向鏈表雙向鏈表四、其它形式的鏈表四、其它形式的鏈表typedef struct DuLNode ElemType ; / 數(shù)據(jù)域 struct DuLNode ; / 指向前驅(qū)的指針域

39、 struct DuLNode ; / 指向后繼的指針域 DuLNode, *DuLinkList; 最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)的鏈表。 a1 a2 . an 2. 循環(huán)鏈表循環(huán)鏈表 和單鏈表的差別在于，判別鏈表中最后一個(gè)結(jié)點(diǎn)的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點(diǎn)”。如何判空？雙向循環(huán)鏈表雙向循環(huán)鏈表空表空表非空表非空表 a1 a2 . an雙向鏈表的操作特點(diǎn)：雙向鏈表的操作特點(diǎn)：u“查詢查詢” ” 和單鏈表相同和單鏈表相同u“插入插入” ” 和和“刪除刪除”時(shí)需要同時(shí)時(shí)需要同時(shí) 修改兩個(gè)方向上的指針。修改兩個(gè)方向上的指針。ai-1aies-next = p-ne

40、xt; p-next = s;s-next-prior = s; s-prior = p;psai-1ai插入插入ai-1aies-prior = p- prior ; p- prior = s;s-next =p ; s- prior -next = s;pai-1ai若在指針p所指結(jié)點(diǎn)之前插入結(jié)點(diǎn),如何實(shí)現(xiàn)此插入算法？s雙向鏈表插入結(jié)點(diǎn)時(shí)算法有多種，關(guān)鍵是不要斷鏈：只要不先執(zhí)行 p- prior = s p- prior = s 語句 即可。ai-1刪除刪除aiai+1p-next = p-next-next;p-next-prior = p;pai-1u如何刪除指針p所指結(jié)點(diǎn)？ai-1a

41、iai+1ai-1ppp-next -next - prior = p;p-next = p-next-next;五、有序表類型五、有序表類型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 S, xi-1 xi, i=2,3,n 基本操作：基本操作： LocateElem( L, e, &q, int(*compare)(ElemType,ElemType) )初始條件初始條件：有序表L已存在。操作結(jié)果操作結(jié)果：若有序表L中

42、存在元素e，則 q指示L中第一個(gè)值為第一個(gè)值為 e 的元素的元素的位置，并返回函數(shù)值TRUE；否則 q 指示第一個(gè)大第一個(gè)大于于 e 的元素的前驅(qū)的元素的前驅(qū)的位置，并返回函數(shù)值FALSE。Compare是一個(gè)是一個(gè)有序判定函數(shù)有序判定函數(shù)( 12, 23, 34, 45, 45, 56, 67, 78, 89, 98)例如例如:若若 e = 45, 則則 q 指向指向 若若 e = 88, 則則 q 指向指向表示值為表示值為 88 的元素應(yīng)插入的元素應(yīng)插入在該指針?biāo)附Y(jié)點(diǎn)之后。在該指針?biāo)附Y(jié)點(diǎn)之后。nnnxpxpxppxp.)(2210在計(jì)算機(jī)中，可以用一個(gè)線性表來表示在計(jì)算機(jī)中，可以用一個(gè)

43、線性表來表示: P = (p0, p1, ，pn)一元多項(xiàng)式一元多項(xiàng)式但是對(duì)于形如但是對(duì)于形如 S(x) = 1 + 3x10000 2x20000的多項(xiàng)式，上述表示方法是否合適？的多項(xiàng)式，上述表示方法是否合適？ 一般情況下的一元稀疏多項(xiàng)式一元稀疏多項(xiàng)式可寫成 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)系：抽象數(shù)據(jù)類型一元多項(xiàng)式的定義如下：D ai | ai TermSet, 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ù)