1、12學習提要： 1.了解線性表的邏輯結構和存儲結構。了解線性表的邏輯結構和存儲結構。 2.掌握兩種存儲結構的描述方法以及在掌握兩種存儲結構的描述方法以及在每種存儲結構上的基本操作的實現。每種存儲結構上的基本操作的實現。 3.理解兩種存儲結構的特點及其使用場理解兩種存儲結構的特點及其使用場合。合。重難點內容： 順序表、鏈表及其操作實現順序表、鏈表及其操作實現3線性結構的線性結構的基本特征基本特征:線性結構是一個數據元素的線性結構是一個數據元素的 有序（次序）集有序（次序）集 。1集合中必存在唯一的一個集合中必存在唯一的一個“第一元素第一元素”；2集合中必存在唯一的一個集合中必存在唯一的一個 “最

2、后元素最后元素” ；3除最后元素在外，均有除最后元素在外，均有 唯一的后繼唯一的后繼；4除第一元素之外，均有除第一元素之外，均有 唯一的前驅唯一的前驅。4線性表：線性表：n個數據元素組成的有限序列。個數據元素組成的有限序列。 表示為（表示為（a1，a2，ai，ai+1，an)例：英文字母表（例：英文字母表（a,b,c,a,b,c,.z).z)是一個線性表是一個線性表例：例：學號姓名年齡001張三18002李四19數據元素數據元素5線性表的長度：線性表的長度：表中元素的個數表中元素的個數n(n=0)n(n=0)，n=0 n=0 空表空表。位序：位序：元素元素a ai i在表中的位置數在表中的位置

3、數i i 。邏輯特征：邏輯特征：v1in時時lai的的直接前驅直接前驅是是ai-1，a1無直接前驅無直接前驅lai的的直接后繼直接后繼是是ai+1，an無直接后繼無直接后繼v元素同構，且不能出現缺項元素同構，且不能出現缺項6抽象數據類型線性表線性表的定義如下：adt list 數據對象數據對象：d ai | ai elemset, i=1,2,.,n, n0 數據關系數據關系：r1 |ai-1 ,aid, i=2,.,n 7 基本操作：基本操作： 結構初始化操作結構初始化操作結構銷毀操作結構銷毀操作 引用型操作引用型操作 加工型操作加工型操作 adt list8 initlist( &

4、l )操作結果：操作結果： 構造一個空的線性表l。初始化操作初始化操作: : 結構銷毀操作結構銷毀操作: :destroylist( &l )初始條件：初始條件：操作結果：操作結果：銷毀線性表 l。線性表 l 已存在。9listempty( 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( )引用型操作引用型操作: :

5、10 listempty( l )初始條件：初始條件：操作結果：操作結果：線性表l已存在。若l為空表，則返回true，否則false。（線性表判空）listlength( l )初始條件：初始條件：操作結果：操作結果：線性表l已存在。返回l中元素個數。（求線性表的長度）11 priorelem( l, cur_e, &pre_e )初始條件：初始條件：操作結果：操作結果：線性表l已存在。若cur_e是l的元素，但不是第一個，則用pre_e 返回它的前驅，否則操作失敗，pre_e無定義。（求數據元素的前驅）12nextelem( l, cur_e, &next_e )初始條件：初

6、始條件：操作結果：操作結果：線性表l已存在。若cur_e是l的元素，但不是最后一個，則用next_e返回它的后繼，否則操作失敗，next_e無定義。（求數據元素的后繼）13getelem( l, i, &e )初始條件：初始條件： 操作結果：操作結果：線性表l已存在，且 1ilengthlist(l)。用 e 返回l中第 i 個元素的值。（求線性表中某個數據元素）14locateelem( l, e, compare( ) )初始條件：初始條件：操作結果：操作結果：線性表l已存在，e為給定值， compare( )是元素判定函數。返回l中第中第1個個與e滿足滿足關系compare( )

7、的元素的位序。若這樣的元素不存在，則返回值為0。（定位函數）15 listtraverse(l, visit( )初始條件：操作結果：線性表l已存在，visit() 為某個訪問函數。依次依次對l的每個元素調用函數visit( )。一旦visit( )失敗，則操作失敗。（遍歷線性表）16加工型操作加工型操作: : clearlist( &l )putelem( &l, i, e )listinsert( &l, i, e )listdelete(&l, i, &e) 17clearlist( &l )初始條件：初始條件：操作結果：操作結果：線性表l

8、已存在。將l重置為空表。（線性表置空）putelem( &l, i, e )初始條件：操作結果：線性表l已存在，且 1ilengthlist(l) 。l中第i個元素賦值同e的值。（改變數據元素的值）18 listinsert( &l, i, e )初始條件：操作結果：線性表l已存在， 且1ilengthlist(l)+1 。在l的第i個元素之前插入插入新的元素e，l的長度增1。（插入數據元素）19listdelete(&l, i, &e)初始條件：操作結果：線性表l已存在且非空， 1ilengthlist(l) 。刪除l的第i個元素，并用e返回其值，l的長度減1

9、。（刪除數據元素）20假設假設:有兩個集合有兩個集合a 和和 b 分別用兩個線分別用兩個線性表性表 la 和和 lb 表示，即：線性表中的表示，即：線性表中的數據元素即為集合中的成員。數據元素即為集合中的成員。現要求一個新的集合現要求一個新的集合aab。 利用上述定義的線性表可以實現其利用上述定義的線性表可以實現其它它更復雜的操作更復雜的操作。例例2-121 要求對線性表作如下操作：擴大線性表 la，將存在于線性存在于線性表表lb 中而不存在于線性表不存在于線性表 la 中的數據元素插入到線性表插入到線性表 la 中去。算法思想：算法思想：221. 從線性表lb中依次察看每個數據元素;2. 依

10、值在線性表la中進行查訪; 3. 若不存在，則插入之。getelem(lb, i,&e) locateelem(la, e, equal( ) listinsert(la, n+1, e)操作步驟：操作步驟：23 getelem(lb, i, e); / 取取lb中第中第i個數據元素賦給個數據元素賦給e if ( ! locateelem(la, e, equal( ) ) listinsert(la, +la_len, e); / la中不存在和中不存在和 e 相同的數據元素，則插入之相同的數據元素，則插入之 void union(list &la, list lb) la_

11、len = listlength(la); / 求線性表的長度求線性表的長度 lb_len = listlength(lb); for (i = 1; i = lb_len; + i) / uniono(listlength(la)listlength(lb)；24例例2-2 已知線性表la和lb是非遞減的，將兩表合并合并成新的線性表lc，且lc也是非遞減的。 25算法思想：算法思想： 將將la、lb兩表中的元素逐一按序加入兩表中的元素逐一按序加入到一個新表到一個新表lc中。中。 設設 la = (a1, , ai, , an)， lb = (b1, , bj, , bm) ， lc = (c

12、1, , ck, , cm+n) 1. 分別從分別從la和和lb中取得當前元素中取得當前元素ai和和bj； 2. 若若aibj，則將，則將ai插入到插入到lc中，否則將中，否則將bj插入到插入到lc中。中。操作步驟：操作步驟：26void mergelist(list la, list lb, list &lc) / 本算法將非遞減的有序表本算法將非遞減的有序表 la 和和 lb 歸并為歸并為 lc / merge_list while (i = la_len) & (j = lb_len) / la 和 lb 均不空 while (i=la_len) / 若 la 不空 wh

13、ile (j=lb_len) / 若 lb 不空 initlist(lc); / 構造空的線性表構造空的線性表 lc i = j = 1; k = 0; la_len = listlength(la); lb_len = listlength(lb);o(listlength(la)listlength(lb)27 while (i=la_len)&(j=lb_len) /la和lb均非空 getelem(la,i,ai); getelem(lb,j,bj); if(ai=bj) listinsert( lc, +k, ai); +i; else listinsert( lc, +k,

14、 bj); +j; 28 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 表中剩余元素表中剩余元素29線性表的順序表示：線性表的順序表示： 用一組用一組地址連續地址連續的儲存單元的儲存單元依次依次存放存放線性表的數據元素。線性表的數據元素。 a1 a2 ai-1 ai an線性表的線性表的

15、起始地址起始地址稱作線性表的稱作線性表的基地址基地址30以“存儲位置相鄰存儲位置相鄰”表示有序對 即：loc(ai) = loc(ai-1) + l 一個數據元素所占存儲量一個數據元素所占存儲量所有數據元素的存儲位置均取決于所有數據元素的存儲位置均取決于第一第一個數據元素個數據元素的存儲位置，即的存儲位置，即 loc(ai) = loc(a1) + (i-1)l 基地址基地址31a1a2aibb+lb+(i-1)l12i內存狀態內存狀態 儲存地址儲存地址位序位序b+(maxlen-1)lb+(n-1)lanb+nln 空閑空閑32順序映像的順序映像的 c 語言描述：語言描述： typedef

16、struct sqlist; / 俗稱 順序表順序表#define list_init_size 80 / 線性表存儲空間的初始分配量#define listincrement 10 / 線性表存儲空間的分配增量elemtype *elem; / 存儲空間基址int length; / 當前長度int listsize; / 當前分配的存儲容量 / (以sizeof(elemtype)為單位)33線性表的基本操作在順序表中的實現：線性表的基本操作在順序表中的實現：initlist(&l) / 結構初始化locateelem(l, e, compare() / 查找listinsert(

17、&l, i, e) / 插入元素listdelete(&l, i,&e) / 刪除元素34status initlist_sq( sqlist& l ) / 構造一個空的線性表 / initlist_sq算法時間復雜度時間復雜度：o(1)l.elem = (elemtype*) malloc (list_ init_size sizeof (elemtype);if (!l.elem) exit (overflow);l.length = 0;l.listsize = list_init_sizereturn ok;結構初始化結構初始化initlist(&

18、;l)3523 75 41 38 54 62 17l.eleml.lengthl.listsizee =38pppppi 1 2 3 4 1 850p基本操作基本操作是：是：將順序表中的元素逐將順序表中的元素逐個和給定值個和給定值 e e 相比較。相比較。查找操作查找操作locateelem(l, e, compare() 36 int locateelem_sq(sqlist l, elemtype e, status (*compare)(elemtype, elemtype) / 在順序表中查詢第一個滿足判定條件的數據元素， / 若存在，則返回它的位序，否則返回 0 / locateel

19、em_sq o( listlength(l) )算法的算法的時間復雜度時間復雜度為：為： i = 1; / i 的初值為第 1 元素的位序 p = l.elem; / p 的初值為第 1 元素的存儲位置 while (i = l.length & !(*compare)(*p+, e) +i; if (i = l.length) return i; else return 0;(*compare)(*p+, e)37 (a1, , ai-1, ai, , an) 改變為改變為 (a1, , ai-1, e, ai, , an)a1 a2 ai-1 ai ana1 a2 ai-1 ai

20、ean, 表的長度增加插入操作插入操作listinsert_sq(&l, i, e) 3821 18 30 75 42 56 8721 18 30 75例如：listinsert_sq( l, 5, 66 ) l.length-10pppq87564266pq = &(l.elemi-1); / q 指示插入位置for (p = &(l.eleml.length-1); p = q; -p) *(p+1) = *p;for( j=n-1; j=i-1; -j) l.elemj+1= l.elemj;l.elemj+1=e;39 status listinsert_sq(

21、sqlist &l, int i, elemtype e) / 在順序表l的第 i 個元素之前插入新的元素e, / i 的合法范圍為 1il.length+1 / listinsert_sq q = &(l.elemi-1); / q 指示插入位置for (p = &(l.eleml.length-1); p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移元素右移*q = e; / 插入e+l.length; / 表長增1return ok;算法時間復雜度算法時間復雜度為為: :o( listlength(l) )40if (l.length

22、= l.listsize) / 當前存儲空間已滿，增加分配 newbase = (elemtype *) realloc (l.elem, (l.listsize+listincrement)*sizeof (elemtype); if (!newbase) exit(overflow); / 存儲分配失敗 l.elem = newbase; / 新基址 l.listsize += listincrement; / 增加存儲容量if (i l.length+1) return error; / 插入位置不合法41考慮移動元素的平均情況考慮移動元素的平均情況: : 假設在第 i 個元素之前插入的

23、概率為 ， 則在長度為n 的線性表中插入一個元素所需插入一個元素所需移動元素次數的期望值移動元素次數的期望值為：ip11) 1(niiisinpe11) 1(11niisinne2n 若假定假定在線性表中任何一個位置上進行插入插入的概率的概率都是相等相等的，則移動元素的期望值移動元素的期望值為：42 (a1, , ai-1, ai, ai+1, , an) 改變為改變為 (a1, , ai-1, ai+1, , an)ai+1 an, 表的長度減少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 刪除操作刪除操作listdelete(&l, i, &e)4321

24、18 30 75 42 56 8721 18 30 75l.length-10pppq8756例如：listdelete_sq(l, 5, e) pp = &(l.elemi-1); e=*p;q = l.elem+l.length-1;for (+p; p = q; +p) *(p-1) = *p; 44status listdelete_sq (sqlist &l, int i, elemtype &e) / listdelete_sqfor (+p; p = q; +p) *(p-1) = *p; / 被刪除元素之后的元素左移-l.length; /表長減1ret

25、urn ok;算法算法時間復雜度時間復雜度為為: : o( listlength(l)p = &(l.elemi-1); / p 為被刪除元素的位置e = *p; /被刪除元素的值賦給 eq = l.elem+l.length-1; /表尾元素的位置 if (i l.length) return error; /刪除位置不合法45考慮移動元素的平均情況考慮移動元素的平均情況: : 假設刪除第 i 個元素的概率為 , 則在長度為n 的線性表中刪除刪除一個元素所需移動元移動元素次數的期望值素次數的期望值為：iqniidlinqe1)(nidlinne1)(121n若假定在線性表中任何一個位

26、置上進行刪除的概率都是相等的，則移動元素的期望值移動元素的期望值為：46v優點優點l邏輯相鄰，物理也相鄰邏輯相鄰，物理也相鄰l可隨機存取任一元素可隨機存取任一元素l存儲空間使用緊湊存儲空間使用緊湊v缺點缺點l插入、刪除操作需要移動大量的元素插入、刪除操作需要移動大量的元素l需事先分配一定大小的連續的存儲空需事先分配一定大小的連續的存儲空間間順序存儲線性表的優缺點：順序存儲線性表的優缺點：4748用一組用一組任意任意的存儲單元存儲線性表的存儲單元存儲線性表的數據元素。的數據元素。數據域 指針域結點以元素元素(數據元素的映象數據元素的映象) + 指針指針(指示后繼元素存儲位置指示后繼元素存儲位置)

27、 = 結點結點 (表示數據元素 或 數據元素的映象數據元素的映象)49zhaoqiansunlizhouwuzhengwangh例例 線性表線性表 (zhao, qian, sun, li, zhou, wu, zheng, wang)37null4313171925數據域數據域指針域指針域liqiansunwangwuzhaozhengzhou存儲地址存儲地址1713192531374331h頭指針50 以線性表中第一個數據元素以線性表中第一個數據元素 的存儲的存儲地址地址作為線性表的地址，稱作線性表的作為線性表的地址，稱作線性表的頭指針頭指針。1a頭結點頭結點 a1 a2 . an 頭指針

28、頭指針 有時為了操作方便，在第一個結點之有時為了操作方便，在第一個結點之前虛加一個前虛加一個“頭結點頭結點”，以，以指向頭結點指向頭結點的指針的指針為鏈表的頭指針為鏈表的頭指針。空指針線性表為空表時，頭結點的指針域為空 51typedef struct lnode / 定義單鏈表結點定義單鏈表結點 elemtype data; /數據域 struct lnode *next； / 指向后繼的指針域lnode, *linklistlnode *p;datanextp結點（*p）(*p)表示表示p所指向的結點所指向的結點(*p).datap-data表示表示p指向結點的數據域指向結點的數據域(*p

29、).nextp-next表示表示p指向結點的指針域指向結點的指針域二、結點和單鏈表的二、結點和單鏈表的 c c 語言描述語言描述aiai+1pp-nextlinklist l； / l 為單鏈表的頭指針為單鏈表的頭指針52三、單鏈表操作的實現三、單鏈表操作的實現getelem(l, i, e) / 取第取第i i個數據元素個數據元素listinsert(&l, i, e) / 插入插入數據元素數據元素listdelete(&l, i, e) / 刪除刪除數據元素數據元素clearlist(&l) / 重置線性表為空表重置線性表為空表createlist(&l,

30、n) / 生成含生成含 n 個數據元素的鏈表個數據元素的鏈表53 getelem(l, i, &e) 因此，查找第因此，查找第 i 個數據元素的基本操個數據元素的基本操作為：作為：移動指針，比較移動指針，比較 j 和和 i 。 單鏈表是一種順序存取的結構，為單鏈表是一種順序存取的結構，為找第找第 i 個數據元素，必須先找到第個數據元素，必須先找到第 i-1 個個數據元素。數據元素。 令指針令指針 p 始終指向線性表中第始終指向線性表中第 j 個個數據元素。數據元素。54l a1a2ai-1aianpj=1while (p&jnext; j = 1; / p p指向第一個結點，指

31、向第一個結點，j j為計數器為計數器while (p & jnext; +j; / 順指針向后查找，直到順指針向后查找，直到 p p 指向第指向第 i i 個元素個元素 / 或或 p p 為空為空if ( !p | ji ) return error; / 第第 i i 個元素不存在個元素不存在e = p-data; / 取得第取得第 i i 個元素個元素return ok;56ai-1線性表的操作線性表的操作listinsert(&l, i, e) 在單鏈表中的實現在單鏈表中的實現： 有序對有序對 改變為改變為 和和 eaiai-157 因此，在單鏈表中第因此，在單鏈表中第

32、i i 個結點之前個結點之前進行插入的基本操作為進行插入的基本操作為: : 找到線性表中找到線性表中第第i-1i-1個結點個結點，然后，然后修修改其指向后繼的指針改其指向后繼的指針。 可見，在鏈表中插入結點只需要修可見，在鏈表中插入結點只需要修改指針。但同時，若要在第改指針。但同時，若要在第 i 個結點之個結點之前插入元素，修改的是第前插入元素，修改的是第 i-1 個結點的個結點的指針。指針。58 status listinsert_l(linklist l, int i, elemtype e) / l 為帶頭結點的單鏈表的頭指針，本算法為帶頭結點的單鏈表的頭指針，本算法 / 在鏈表中第在鏈

33、表中第i 個結點之前插入新的元素個結點之前插入新的元素 e / linstinsert_l算法的算法的時間復雜度時間復雜度為:o(listlength(l)p = l; j = 0;while (p & j next; +j; / 尋找第尋找第 i-1 個結點個結點if (!p | j i-1) return error; / i 大于表長或者小于大于表長或者小于1 59s = (linklist) malloc ( sizeof (lnode); / 生成新結點s-data = e; s-next = p-next; p-next = s; / 插入return ok; eai-1a

34、iai-1sp60線性表的操作線性表的操作listdelete (&l, i, &e) 在鏈表中的實現在鏈表中的實現:有序對有序對 和和 改變為改變為 ai-1aiai+1ai-161 在單鏈表中刪除第刪除第 i i 個結點個結點的基本基本操作操作為:找到線性表中第找到線性表中第i-1i-1個結點，修個結點，修改其指向后繼的指針。改其指向后繼的指針。ai-1aiai+1ai-1q = p-next; p-next = q-next; e = q-data; free(q);pq62 status listdelete_l(linklist l, int i, elemtype

35、&e) / 刪除以 l 為頭指針(帶頭結點)的單鏈表中第 i 個結點 / listdelete_l算法的算法的時間復雜度時間復雜度為: o(listlength(l)p = l; j = 0;while (p-next & j next; +j; / 尋找第 i 個結點，并令 p 指向其前趨if (!(p-next) | j i-1) return error; / 刪除位置不合理q = p-next; p-next = q-next; / 刪除并釋放結點e = q-data; free(q);return ok;63操作操作 clearlist(&l) 在鏈表中的實現

36、在鏈表中的實現:void clearlist(&l) / 將單鏈表重新置為一個空表 while (l-next) p=l-next; l-next=p-next; / clearlistfree(p);算法時間復雜度：o(listlength(l)64如何從線性表得到單鏈表？如何從線性表得到單鏈表？鏈表是一個動態的結構，它不需要鏈表是一個動態的結構，它不需要予分配空間，因此予分配空間，因此生成鏈表的過程生成鏈表的過程是一個結點是一個結點“逐個插入逐個插入” ” 的過程。的過程。65例如：例如：逆位序逆位序輸入輸入 n n 個數據元素的值，個數據元素的值， 建立帶頭結點的單鏈表。建立帶頭

37、結點的單鏈表。操作步驟：操作步驟：一、建立一個一、建立一個“空表空表”；二、輸入數據元素二、輸入數據元素an， 建立結點并插入；建立結點并插入；三、輸入數據元素三、輸入數據元素an-1， 建立結點并插入；建立結點并插入；ananan-1四、依次類推，直至輸入四、依次類推，直至輸入a a1 1為止。為止。66void createlist_l(linklist &l, int n) / 逆序輸入 n 個數據元素，建立帶頭結點的單鏈表 / createlist_l算法的算法的時間復雜度時間復雜度為:o(listlength(l)l = (linklist) malloc (sizeof (

38、lnode);l-next = null; / 先建立一個帶頭結點的單鏈表for (i = n; i 0; -i) p = (linklist) malloc (sizeof (lnode); scanf(&p-data); / 輸入元素值 p-next = l-next; l-next = p; / 插入67補充作業：補充作業：寫出按寫出按正位序正位序建立一個單鏈表的建立一個單鏈表的算法。算法。68回顧回顧 2.1 節中兩個例子的算法，節中兩個例子的算法，看一下當線性表分別以順序存看一下當線性表分別以順序存儲結構和鏈表存儲結構實現時，儲結構和鏈表存儲結構實現時，它們的時間復雜度為多少

39、？它們的時間復雜度為多少？69void 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控制結構：控制結構：基本操作：基本操作：for 循環循環getelem, locateelem 和 listinsert當以順序映像實現抽象數據類型線性表時為: o(

40、 listlength(la)listlength(lb) ) 當以鏈式映像實現抽象數據類型線性表時為: o( listlength(la)listlength(lb) )例例2-170void mergelist(list la, list 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);

41、if (ai = bj) listinsert(lc, +k, ai); +i; else listinsert(lc, +k, bj); +j; 控制結構：控制結構：基本操作：基本操作：三個并列的三個并列的while循環循環getelem, listinsert當以順序映像實現抽象數據類型線性表時為: o( listlength(la)+listlength(lb) )當以鏈式映像實現抽象數據類型線性表時為: o( (listlength (la)+listlength (lb)2 )例例2-2713115la15296lblcpcpapbpbpcpcpapcpapcpbpcpbpcpa=n

42、ullwhile ( pa & pb ) if ( padataprior-next= p= p-next-proir;75 a1 a2 . an雙向循環鏈表雙向循環鏈表空表空表非空表非空表76雙向鏈表的操作特點：雙向鏈表的操作特點：“查詢查詢” ” 和單鏈表相同。和單鏈表相同。 “ “插入插入” ” 和和“刪除刪除”時需要時需要同時修改兩個方向上的指針。同時修改兩個方向上的指針。77ai-1aies-prior= p-prior; p-prior -next=s;s-next = p; p-prior = s ;psai-1aiv插入操作插入操作78ai-1v刪除操作刪除操作aiai

43、+1p-prior-next = p-next;p-next-prior = p-prior;pai-179nnnxpxpxppxp.)(2210在計算機中，可以用一個線性表來表示在計算機中，可以用一個線性表來表示: p = (p0, p1, ，pn)一元多項式一元多項式80但是對于形如但是對于形如 s(x) = 1 + 3x10000 2x20000的多項式，上述表示方法是否合適？的多項式，上述表示方法是否合適？81 一般情況下的一般情況下的一元稀疏多項式一元稀疏多項式可寫成可寫成 pn(x) = p1xe1 + p2xe2 + + pmxem其中其中：pi 是指數為是指數為ei 的項的非零

44、系數的項的非零系數， 0 e1 e2 em = n可以下列線性表表示：可以下列線性表表示：（p1, e1）, (p2, e2), , (pm,em) ）82 p999(x) = 7x3 - 2x12 - 8x999例如例如:可用線性表可用線性表 ( (7, 3), (-2, 12), (-8, 999) )表示表示83adt polynomial 數據對象數據對象： 數據關系數據關系：抽象數據類型一元多項式的定義：d ai | ai termset, i=1,2,.,m, m0 termset 中的每個元素包含一個每個元素包含一個 表示表示系數的實數系數的實數和表示和表示指數的整數指數的整數

45、r1 |ai-1 ,aid, i=2,.,n 且ai-1中的指數值中的指數值ai中的指數值中的指數值 84 creatpolyn ( &p, m ) destroypolyn ( &p ) printpolyn ( &p ) 基本操作基本操作：操作結果操作結果：輸入輸入 m 項的系數和指數，項的系數和指數， 建立一元多項式建立一元多項式 p。初始條件初始條件：一元多項式一元多項式 p 已存在已存在。操作結果操作結果：銷毀一元多項式銷毀一元多項式 p。初始條件初始條件：一元多項式一元多項式 p 已存在已存在。操作結果操作結果：打印輸出一元多項式打印輸出一元多項式 p。85

46、 polynlength( p ) addpolyn ( &pa, &pb ) subtractpolyn ( &pa, &pb ) adt polynomial初始條件初始條件：一元多項式一元多項式 p 已存在已存在。操作結果操作結果：返回一元多項式返回一元多項式 p 中的項數中的項數。初始條件初始條件：一元多項式一元多項式 pa 和和 pb 已存在已存在。操作結果操作結果：完成多項式相加運算，即：完成多項式相加運算，即： pa = papb，并銷毀一元多項式，并銷毀一元多項式 pb。86單鏈表的結點定義：單鏈表的結點定義：typedef struct node float coef； /系數 int exp； /指數 struct node *next；polynomial；coefexpnext8717787178522117)()()(9228)(5937)(