2線性表(福建教師招考信息技術算法和程序部分)

1、第二章 線形表1、線性表(Linear List) ：定義：由n(n0)個數(shù)據(jù)據(jù)元素(結點)a1，a2， an組成的有有限序列列。記作作：L=(a1，a2，ai-1，ai，ai+1，an)其中數(shù)據(jù)據(jù)元素的的個數(shù)n定義為為表的長長度。當當n=0時稱為為空表，常常將將非空的的線性表表(n0)這這里的的數(shù)據(jù)元元素ai(1in)只是一一個抽象象的符號號，其具具體含義義在不同同的情況況下可以以不同。例1、26個英英文字母母組成的的字母表表（A，B，C、Z）例2、某某校從1978年到1983年各種種型號的的計算機機擁有量量的變化化情況。（6，17，28，50，92，188）例3、學學生健康康情況登登記表如

2、如下：例4、一一副撲克克的點數(shù)數(shù)（2，3，4，J，Q，K，A）姓 名學 號性 別年齡 健康情況王小林790631 男 18 健康陳 紅790632 女 20 一般劉建平790633 男 21 健康張立立790634 男 17 神經(jīng)衰弱 . . .線性表元素及元元素之間間的關系系為線性性線性：（1）有且僅僅有一個個開始節(jié)節(jié)點（該該節(jié)點只只有一個個后繼節(jié)節(jié)點，沒沒有前趨趨節(jié)點）（2）有且僅僅有一個個結束節(jié)節(jié)點（該該節(jié)點只只有一個個前趨節(jié)節(jié)點，沒沒有后繼繼節(jié)點）（3）除首節(jié)節(jié)點，其其余節(jié)點點有且僅僅有一個個前趨k1k2k3k4k1k2k3（4）除尾節(jié)節(jié)點，其其余節(jié)點點有且僅僅有一個個后繼數(shù)據(jù)的運運算

3、是定定義在邏邏輯結構構上的，而運算算的具體體實現(xiàn)則則是在存存儲結構構上進行行的。線性表的的類型定定義抽象數(shù)據(jù)據(jù)類型線線性表的的定義ADTList數(shù)據(jù)對象象：D ai |aiElemSet, i=1,2,.,n,n0數(shù)據(jù)關系系：R1|ai-1 ,aiD,i=2,.,n基本操作作： 初始始化InitList(&L )操作結果果：構造造一個空空的線性性表L。 結構構銷毀DestroyList(&L )初始條件件：線性性表L已已存在。操作結果果：銷毀毀線性表表L。 引用用型操作作 ListEmpty( L)初始條件件：線性性表L已已存在。操作結果果：若L為空表表，則返返回TRUE，否則FALSE。Li

4、stLength(L )初始條件件：線性性表L已已存在。操作結果果：返回回L中元元素個數(shù)數(shù)。ADTListGetElem(L,i,&e )初始條件件：線性性表L已已存在，1iLengthList(L)操作結果果：用e返回L中第i個元素素的值。LocateElem(L,e,compare() )初始條件件：線性性表L已已存在，compare()是是元素判判定函數(shù)數(shù)。操作結果果：返回回L中第1個與e滿足關系compare()的元素素的位序序。若這這樣的元元素不存存在，則則返回值值為0。PriorElem( L, cur_e,&pre_e)初始條件件：線性性表L已已存在。操作結果果：若cur_e是L

5、的元素素，但不不是第一一個，則則用pre_e 返回回它的前前驅，否否則操作作失敗，pre_e無無定義。NextElem(L,cur_e,&next_e)初始條件件：線性性表L已已存在。操作結果果：若cur_e是L的元素素，但不不是最后后一個，則用next_e返返回它的的后繼，否否則操作作失敗，next_e無定義義。ListTraverse(L,visit( )初始條件件：線性性表L已已存在。操作結果果：依次對L的每每個元素素調(diào)用函函數(shù)visit()。一一旦visit()失敗，則操作作失敗。ADTList 加工工型操作作 ClearList(&L )初始條件件：線性性表L已已存在。操作結果果：將

6、L重置為為空表。PutElem(L,i,&e )初始條件件：線性性表L已已存在，1iLengthList(L)操作結果果：L中中第i個個元素賦賦值同e的值。ListInsert(&L,i,e )初始條件件：線性性表L已已存在，1iLengthList(L)+1操作結果果：在L的第i個元素素之前插插入新的的元素e，L的的長度增增1。ListDelete(&L,i,&e)初始條件件：線性性表L已已存在且且非空，1iLengthList(L)操作結果果：刪除除L的第第i個元元素，并并用e返返回其其值，L的長度度減1。 ADTList舉例假設線性性表L=(23,56,89,76,18),i=3,x=5

7、6,y=88,則對對L的一一組操作作及結果果如下：ListLength(L )/所得得結果為為5GetElem(L,i,&e)/所得得結果為為89PriorElem( L,x, &pre_e)/所得得結果為為23NextElem(L,x, &next_e)/所得得結果為為89LocateElem(L,x,equal)/所得得結果為為2ListInsert(&L,i,y) /所得結結果為(23,56,88,89,76,18)ListDelete(&L,i+1, &e)/所得結結果為(23,56,88,76,18)89如何實現(xiàn)現(xiàn)線性表表的其它它操作例2-1 利用用兩個線線性表LA和LB分別別表示兩

8、兩個集合合A和B，現(xiàn)要要求一個個新的集集合A=AB。設計思想想：擴大線性性表LA，將存存在于線線性表LB中而而不存在在于線性性表LA中的數(shù)數(shù)據(jù)元素素插入到到線性表表LA中中去。分下列三三步進行行：1從線線性表LB中依依次取得得每個數(shù)數(shù)據(jù)元素素;2依值值在線性性表LA中進行行查訪;3若不不存在，則插入入之。A=AB算法描述述：/將將所有在在線性表表Lb中中但不在在La中中的數(shù)據(jù)據(jù)元素插插入到La中void Union(List &La，List Lb)/求求線性表表的長度度La-len=ListLength(La);Lb-len=ListLength(Lb);for( i=1;i=Lb-len;

9、 i+)/取取Lb中中第i個個數(shù)據(jù)元元素賦給給eGetElem(Lb，i，e);/La中中不存在在和e 相同同的數(shù)據(jù)據(jù)元素，則插入入之if(!LocateElem( La，e，equal)ListInsert(La，+La-en，e); /UnionA=AB時間復雜雜度分析析：GetElem取遍Lb表元元素需Lb_len=ListLength(Lb)次；循環(huán)體內(nèi)內(nèi)的Locate操作作平均需需ListLength(La)次次最壞情況況為：ListLength(La)總的時間間復雜度度：OListLength(Lb)* ListLength(La)例 2-1-2已知一個個非純集集合B，試構構造集合

10、合A，要要求集合合A中只只包含集集合B中中所有值值不相同同的數(shù)據(jù)據(jù)元素。設計思想想：解法一：同上例，分別以以線性表表LA和和LB表表示集合合A和B，則首首先初始始化線線性表LA為空空表，之之后的操操作和例例2-1完全相相同。解法二：仍以線性性表表示示集合。只是求求解之前前先對線線性表LB中的的數(shù)據(jù)據(jù)元素進進行排序序，即線線性表LB中的的數(shù)據(jù)元元素依其其值從小小到大大有序排排列，則則值相同同的數(shù)據(jù)據(jù)元素必必相鄰。則上述述操作作中的第第二步就就不需要要進行從從頭至尾尾的查詢詢。A =Bvoid purge(List&La,List Lb) /已已知線性性表Lb中的數(shù)數(shù)據(jù)元素素依值非非遞減有有序排列

11、列，現(xiàn)構構造線性性表La，/使使La中中只包含含Lb中中所有值值不相同同的數(shù)據(jù)據(jù)元素InitList（La）；/初初始化La為空空表La_len=ListLength(La);Lb_len=ListLength(Lb);/求求線性表表的長度度for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);/取取Lb中第i個數(shù)據(jù)據(jù)元素賦賦給eif( ListEmpty( La )|!equal(en，e)ListInsert(La,+La_len,e);/La中不不存在和和 e相相同的的數(shù)據(jù)元元素，則則插入入之en= e;/en，La中的已已插入元元素 / for / purgeA =B

12、時間復雜雜度分析析：GetElem取遍Lb表元元素需Lb_len=ListLength(Lb)次；解法一:循環(huán)體內(nèi)內(nèi)的Locate操作作平均需需ListLength(Lb)次次故時間復復雜度為為：O(ListLength2(LB)；解法二的的時間復復雜度：循環(huán)體內(nèi)內(nèi)的基本本操作與與表長無無關故時間復復雜度為為：O(ListLength(Lb)C =AB例2-2巳巳知線性性表LA和線性性表LB中的數(shù)數(shù)據(jù)元素素按值非非遞減有有序排列列，現(xiàn)要要求將LA和LB歸并并為一個個新的線線性表LC，且且LC中中的元素素仍按值值非遞減減有序排排列。設計思想想：1、LC為空表表，用來來存放LA和LB的元元素2、表

13、LA和LB的元元素逐一一進行比比較取小小者放入入表LC中3、插入入表LA或表LB中剩剩余的元元素算法描述述：/已已知線性性表La和Lb中的元元素按值值非遞減減排列列。/歸歸并La和Lb得到新新的線性性表Lc，Lc的元元素也按按值非遞遞減排列列。void 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)/La和Lb均非非空GetElem(La,i,ai);GetElem(Lb,j,b

14、j);if(ai=bj)ListInsert(Lc,+k,ai);+i;elseListInsert(Lc,+k,bj);+j;C =ABwhile(i=La_len)GetElem(La,i+, ai);ListInsert(Lc,+k, ai);while(j=Lb_len)GetElem(Lb,j+, bj);ListInsert(Lc,+k, bj); / MergeListC =AB時間復雜雜度分析析：該算法中中包含了了三個WHILE語句句，其中中，第一一個處理理了某一一張表的的全部元元素和另另一張表表的部分分元素；后兩個個WHILE循循環(huán)只可可能有一一個執(zhí)行行，用來來完成將將未歸并

15、并到LC中的的余下部部分元素素插入到到LC中中?！安迦搿笔枪懒苛繗w并算算法時間間復雜度度的基本本操作，其語句句頻度為為：LENGTH（LA）+LENGTH（LB）該算法的的時間復復雜度為為：O（LENGTH（LA）+LENGTH（LB）若LA和LB的元素個個數(shù)為同同數(shù)量級級n，則該該算法的的時間間復雜度度為:O(n)線性表的的順序表表示和實實現(xiàn)一、線性性表的順順序存儲儲結構順序表：線性表的的順序存存儲結構構把線性表表的結點點按邏輯輯順序（順序）依依次存放放在一組組地址連續(xù)的存儲單單元里。1、線性性表的地地址計算算：假設線性性表的每每個元素素需占用用l個存儲單單元，并并以所占占的第一一個單元元的

16、存儲儲地址作作為數(shù)據(jù)據(jù)元素的的存儲位位置（首首地址）。則線線性表中中第i+1個數(shù)據(jù)元元素的存存儲位置置LOC( ai+1)和第i個數(shù)據(jù)元素素的存儲儲位置LOC(ai)之間滿足足下列關關系：LOC(ai+1) =LOC(ai) +l線性表的的第i個個數(shù)據(jù)元元素ai的存儲儲位置為為：LOC(ai) =LOC(a1) +(i-1)*l存儲示意意：線性表的的順序存存儲用數(shù)組實實現(xiàn)線性性表（順順序存儲儲、順序序表）線性表元元素：a1、a2、a3、a4.數(shù)組元素素：a0、a1、a2、a3線性關系系：a1a2a3a4數(shù)組下標標大小注意：C語言中的的數(shù)組下下標從“0”開始，因因此，若若L是Sqlist類型的順

17、順序表，則表中中第i個元素是是l.datai-1。ElemType*getElem(intpos);/若若1=pos=cursize,則則返回指指示第pos個個元素/的位位置;否否則返回回NULLintLocation(ElemType&e);/返返回其值值和e所所指元素素值相同同的數(shù)據(jù)據(jù)元素在在線性/表中中的序號號，若不不存在這這樣的數(shù)數(shù)據(jù)元素素，則返返回0/modificationvoidclearList(void);StatusputElem(intpos,constElemType&e);/若若1=pos=cursize,則則修改線線性表中中第pos個數(shù)數(shù)/據(jù)元元素的值值，并且且返回

18、OK;否否則不不進行修修改并返返/回ERRORStatusInsert (intpos,constElemType&e);/若若1=pos=cursize+1, 則插插入元素素e在線線性表/中第第pos個數(shù)據(jù)據(jù)元素之之前，并并且返返回OK;否否則不/進行行插入并并返回ERRORStatus*Delete(intpos, ElemType&e);/若若1=posMAXLISTSIZE)?MAXLISTSIZE:size;elemPtr =newElemTypesize;cursize =0;插入示意意：插入運算算插入運算算問題描述述以a1開開始的線線性表中中在第i個個元素前前插入一一個新元元素n

19、ew_node。a1a2ai-1aiana1a2ai-1newnodeai+1aianai+1插入運算算從ai開開始向后后移動從an開開始向前前每個元元素向后后移一格格a1a2ai-1aiai+1.anaiaiaiaia1a2ai-1aiai+1ananai+1aifor( j=i;j i;j-)L.elem j+1 =L.elem j;newnode算法思想想： 進行行合法性性檢查，1=i=n+1； 利用用線性表表是否已已滿； 將第第n個至至第i個個元素逐逐一后移移一個單單元； 在第第i個位位置處插插入新元元素； 將表表的長度度加1。StatusListInsert_Sq(Sqlist&L，

20、int i， ElemTypee) /在在順序序線性表表L中第第 i個個位置置之前插插入新的的元素e/i的的合法法值為1 iListLength_Sq(L)+ 1if(i L.length+1)returnERROR; / i值值不合法法if(L.length=L.ListSize)exit(overflow);for(i=L.length-1;i=I-1;i-)L.elemi+1=L.elemi;L.elemI-1=x;l.length+;刪除示意意：anai刪除運算算刪除運算算問題描述述：刪除除第i個個元素算法實現(xiàn)現(xiàn)分析a1a2aianai1a1a2ai1ai+1ananai+1刪除運算算

21、算法實現(xiàn)現(xiàn)分析從an開開始向前前逐個元元素向前前移動從ai1開始向后后逐個元元素向前前移動a1a2ai+1aianai-1anananfor( i=L.length-1;i i;i-)L.elem i-1 =L.elem i;a1a2ai-1aiai+1anfor( i=i;i L.length-1;i+)L.elem i=L.elem i+1;算法思想想： 進行行合法性性檢查，i是否否滿足1=i=n； 判線線性表是是否已空空，v.last=0； 將第第i+1至第n個元素素逐一向向前移一一個位置置； 將表表的長度度減1。StatusListDelete_Sq(SqList&L,inti,Ele

22、mType&e)/ListDelete_Sqfor(+p;p = q; +p)*(p-1)= *p;/被刪除元元素之后后的元素素左移-L.length;/表長減1returnOK;算法時間間復雜度度為:O(ListLength(L)p =&(L.elemi-1);/p為被刪除除元素的的位置e =*p;/被刪除元元素的值值賦給eq =L.elem+L.length-1;/表尾元素素的位置置if(i L.length)returnERROR;/刪除位置置不合法法元素左移移考慮移動動元素的的平均情情況: 假設刪除第 i 個元素的概率為 , 則在長度為n 的線性表中刪除一個元素所需移動元素次數(shù)的期望值

23、為：若假定在在線性表表中任何何一個位位置上進進行刪除除的概率都是相等的，則移動元素素的期望望值為：p21 18 30 75 42 56 8721 18 30 75L.length-10ppq8756p =&(L.elemi-1);q =L.elem+L.length-1;for(+p;p = q; +p)*(p-1)= *p;例如：ListDelete_Sq(L, 5, e)pintLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)/在順序表表中查詢詢第一個個滿足判判定條件件的數(shù)據(jù)據(jù)元素，/若存在，則返回回它的

24、位位序，否否則返回回 0/LocateElem_SqO(ListLength(L) )算法的時間復雜雜度為：i =1;/i 的初初值為第第 1元元素的的位序p =L.elem;/p 的初初值為第第 1元元素的的存儲位位置while(i=L.length&!(*compare)(*p+, e)+i;if(i=L.length)returni;elsereturn0;(*compare)(*p+, e)利用順序序表類實實現(xiàn)線性性表的其其它操作作例如：順順序表23 75 41 38 54 62 17L.elemL.length = 7L.listsizee =38pppppi12341850p可見，

25、基基本操作作是，將順序表表中的元元素逐個和給給定值e相比較。集合歸并并：#include#includeSqList.hSqListmerge(Sqlist&a,SqList&b)ElemType*ai,*bj;intm =a.Length( );intn =b.Length( );SqListc(m+n);inti =1;intj =1;intk =c.Length( );while(i=m)&(j=n)ai= a.getElem(i);bj= b.getElem(j);switch(compare(*ai,*bj) case1:case0:c.Insert(+k, ai);i+;break

26、;case1:c.Insert(+k, bj);j+;break;default:;/switch/while利用順序序表類實實現(xiàn)線性性表的其其它操作作while(i=m)ai= a.getElem(i+);c.Insert(+k, ai);while(j next=next;next =p;Node*Node:deleteAfter(void)/刪刪除并返返回后繼繼結點Node*s =next;next =s next;returns;L線性表的的操作GetElem(L, i, &e)在單鏈表表中的實實現(xiàn):211830754256pppj123因此，查查找第i個個數(shù)據(jù)元元素的基基本操作作為：

27、移動指針針，比較較 j和和i單鏈表是是一種順順序存取取的結構構，為找找第i 個數(shù)數(shù)據(jù)元素素，必須須先找到到第i-1個個數(shù)據(jù)據(jù)元素。令指針p始終指向線性表中中第j個數(shù)據(jù)元元素StatusGetElem_L(LinkListL,inti,ElemType&e)/L是帶頭結結點的鏈鏈表的頭頭指針，以e 返回回第i 個元元素/GetElem_L算法時間復雜雜度為:O(ListLength(L)p =L-next;j =1;/p指向第第一個結結點，j為計數(shù)數(shù)器while(p&jnext;+j;/順指針向向后查找找，直到到 p指指向第第 i個個元素素/或 p為為空if(!p | ji)returnERRO

28、R;/第 i個個元素素不存在在e =p-data;/取得第i個個元素returnOK;ai-1線性表的的操作ListInsert(&L,i,e)在單鏈表表中的實實現(xiàn)：有序對改變?yōu)?和 eaiai-1因此，在在單鏈表表中第i個個結點之之前進行行插入的的基本操操作為:找到線性性表中第第i-1個結點點，然后后修改其其指向后后繼的指指針?？梢?，在在鏈表中中插入結結點只需需要修改改指針。但同時時，若要要在第i個個結點之之前插入入元素，修改的的是第i-1 個結結點的指指針。StatusListInsert_L(LinkListL,inti,ElemTypee)/L為帶頭結結點的單單鏈表的的頭指針針，本算算

29、法/在鏈表中中第i個個結點點之前插插入新的的元素e/LinstInsert_L算法的時間復雜雜度為:O(ListLength(L)p =L;j= 0;while(p&j next;+j;/尋找第i-1 個結結點if(!p|j i-1)returnERROR;/i 大于于表長或或者小于于1s =newLNode;/生生成新結結點s-data =e;s-next =p-next;p-next =s;/插插入returnOK; eai-1aiai-1sp線性表的操作ListDelete (&L,i,&e)在鏈表中中的實現(xiàn)現(xiàn):有序對 和改變?yōu)閍i-1aiai+1ai-1在單鏈表表中刪除第i 個結結點的

30、基本操作作為:找到線性性表中第第i-1個結點點，修改改其指向向后繼的的指針。ai-1aiai+1ai-1q =p-next;p-next =q-next;e =q-data;free(q);pqStatusListDelete_L(LinkListL,inti,ElemType&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)returnERROR;/

31、刪刪除位置置不合理理q =p-next;p-next =q-next;/刪刪除并釋釋放結點點e =q-data;free(q);returnOK;操作ClearList(&L)在鏈表中中的實現(xiàn)現(xiàn):voidClearList(&L)/將單鏈表表重新置置為一個個空表while(L-next)p=L-next;L-next=p-next;/ClearListfree(p);算法時間復雜雜度：O(ListLength(L)如何從線線性表得得到單鏈鏈表？鏈表是一一個動態(tài)態(tài)的結構構，它不不需要予予分配空空間，因因此生成鏈表表的過程程是一個結結點“逐個插入入” 的過過程。例如：逆位序輸輸入n 個數(shù)數(shù)據(jù)元素素

32、的值，建立帶頭頭結點的的單鏈表表。操作步驟驟：1、建立立一個“空表”；2、輸入入數(shù)據(jù)元元素an，建立結點點并插入入；3、輸入入數(shù)據(jù)元元素an-1，建立結點點并插入入；ananan-14、依次次類推，直至輸輸入a1為止。如何從線線性表得得到單鏈鏈表？鏈表是一一個動態(tài)態(tài)的結構構，它不不需要予予分配空空間，因因此生成鏈表表的過程程是一個結結點“逐個插入入” 的過過程。voidCreateList_L(LinkList&L,intn)/逆序輸入入 n個個數(shù)據(jù)據(jù)元素，建立帶帶頭結點點的單鏈鏈表/CreateList_L算法的時間復雜雜度為:O(Listlength(L)L =(LinkList)mall

33、oc(sizeof(LNode);L-next =NULL;/先建立一一個帶頭頭結點的的單鏈表表for(i= n; i0;-i)p =(LinkList)malloc(sizeof(LNode);scanf(&p-data);/輸入元素素值p-next =L-next;L-next= p;/插入回顧2.1節(jié)中三個個例子的的算法，看一下下當線性性表分別別以順序序存儲結結構和鏈鏈表存儲儲結構實實現(xiàn)時，它們的的時間復復雜度為為多少？voidunion(List&La,ListLb)La_len=ListLength(La);Lb_len=ListLength(Lb);for(i= 1;i = Lb_

34、len;i+)GetElem(Lb, i, e);if(!LocateElem(La, e, equal()ListInsert(La, +La_len,e);/for/union控制結構構：基本操作作：for循循環(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算法時間間復雜度度 voidpurge(List&La,ListLb)InitList(LA);

35、La_len=ListLength(La);Lb_len=ListLength(Lb);for(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控制結構構：基本操作作：for循環(huán)GetElem和ListInsert當以順序映像像實現(xiàn)抽象象數(shù)據(jù)類類型線性性表時為為:O(ListLength(Lb)當以鏈式映像像實現(xiàn)抽象象數(shù)據(jù)類類型線性性表時為為:O(ListLength2(Lb) )例2-2算法時間間復雜度度voidMergeLi

36、st(ListLa,ListLb,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(ainext =L.current-next;L.current-next=s;if(L.tail =L.current)L.tail =s;L.current=s;returnOK;StatusDelAfter(LinkList&L,ElemType&e )/若當前指指針及

37、其其后繼在在鏈表中中，則刪刪除線性性鏈表L中當前前/指針所指指結點之之后的結結點，并并返回OK;否則返回回ERROR。/DelAfterif(!(L.current&L.current-next)returnERROR;q =L.current-next;L.current-next=q-next;if(L.tail =q)L.tail= L.current;e=q-data;FreeNode(q);returnOK;例一StatusListInsert_L(LinkListL,int i, ElemType e)/在帶頭結結點的單單鏈線性性表L 的第第 i個個元素素之前插插入元素素 e/Li

38、stInsert_L利用上述述定義的的線性鏈鏈表如何何完成線線性表表的其它它操作？if(!LocatePos(L, i-1)returnERROR;/i值不合法法，第i-1 個結結點不存存在if(InsAfter(L, e)returnOK;/完成插入elsereturnERROR;StatusMergeList_L(LinkList&Lc,LinkList&La,LinkList&Lb，int(*compare)(ElemType,ElemType)/歸并有序序表La和Lb,生成新新的有序序表Lc,/并在歸并并之后銷銷毀La和Lb,/compare為指定的的元素大大小判定定函數(shù)/MergeL

39、ist_L例二if(!InitList(Lc)returnERROR;/存儲空間間分配失失敗while(!( a=MAXC&b=MAXC)/La或Lb非空LocatePos(La,0);LocatePos(Lb, 0);/當前指針針指向頭頭結點if(DelAfter(La, e)a =e;/取得La表表中第一一個元素素 aelsea =MAXC;/MAXC為常量最最大值if(DelFirst(Lb, e)b =e;/取得Lb表表中第一一個元素素 belseb =MAXC;/a和b為兩表中中當前比比較元素素DestroyList(La);DestroyList(Lb);/銷毀鏈表表La和Lbre

40、turnOK;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-1ADTOrdered_List數(shù)據(jù)對象象:S =xi|xiOrderedSet，i=1,2,n, n0 集合中任意兩個個元素之間間均可以進行比較較數(shù)據(jù)關系系:R = |xi-1, xi S,xi-1xi, i=2,3,n回顧例2-2的兩個算算法六、有序序表類型型基本操作作：LocateElem(L,e,&q,int(*com

41、pare)(ElemType,ElemType)初始條件件：有序表表L已存在。操作結果果：若有序序表L中存在元元素e，則q指示L中第一個值值為e的元素的位置，并返回回函數(shù)值值TRUE；否則q指示第一個大大于e的元素的的前驅的位置，并返回回函數(shù)值值FALSE。Compare是一個有有序判定定函數(shù)(12,23, 34,45,56, 67,78,89, 98,45)例如:若e =45,則q指向若 e=88,則 q指指向表示值為為 88 的元元素應插插入在該該指針所所指結點點之后。voidunion(List&La,ListLb)/Lb為為線性表表InitList(La);/構造(空空的)線線性表LA

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

43、的長度度for(i= 1;i = Lb_len;i+) /purgeGetElem(Lb,i,e);/取Lb中中第i個個數(shù)據(jù)元元素賦給給 eif(ListEmpty(La)|!equal(en,e)ListInsert(La,+La_len,e);en= e;/La中不不存在和和 e相相同的的數(shù)據(jù)元元素，則則插入之之算法時間間復雜度度：O(n)2.4一一元多多項式的的表示在計算機機中，可可以用一一個線性性表來表表示:P =(p0, p1, ，pn)但是對于于形如S(x) =1+ 3x10000 2x20000的多項式式，上述述表示方方法是否否合適？一元多項項式一般情況況下的一元稀疏疏多項式式可寫成Pn(x)=p1xe1+ p2xe2+ pmxem其中：pi是指數(shù)為為ei的項的非非零系數(shù)數(shù)，0e1 e2 em= n可以下列列線性表表表示：（p1, e1）,(p2, e2), (pm,em) ）P999(x)=7x3- 2x12- 8x999例如:可用線性性表( (7,3),(-2,12), (-8,999)表示ADTPolynomial數(shù)據(jù)對象象：數(shù)據(jù)關系系：抽象數(shù)據(jù)據(jù)類型一一元多項項式的定定義如下下：Dai| aiTermSet,