循環(huán)鏈表雙向鏈表

1、主講人：陳紅麗主講人：陳紅麗 知識點回顧知識點回顧 單鏈表的定義與實現(xiàn)指針指針變量和結點變量和結點變量的區(qū)別變量的區(qū)別 單鏈表基本操作的實現(xiàn) 單鏈表的創(chuàng)建（2種方式） 單循環(huán)鏈表 雙向鏈表 對對循環(huán)鏈表，有時不給出頭指針，而給出循環(huán)鏈表，有時不給出頭指針，而給出尾尾指針，指針，可可以以更方便的找到更方便的找到第一個和最后一個第一個和最后一個結點結點reara1ai-1anai如何查找開始結點和終端結點？如何查找開始結點和終端結點？開始結點：開始結點：rear-next-next終端結點：終端結點：rear雙向雙向鏈表結點鏈表結點prior data next結點指向 p-prior-next

2、= p = p-next-priorp-p-nextpnext雙向鏈表的操作特點：雙向鏈表的操作特點：“查詢查詢”和單鏈表相同和單鏈表相同; “; “插入插入”和和“刪除刪除”需需要要同時修改兩個方向上的指針。同時修改兩個方向上的指針。插入插入ai-1aiesp先改變要插入的結點的先改變要插入的結點的指針域，再改變鏈表中指針域，再改變鏈表中結點的指針域。結點的指針域。s-next = p-next; s-prior = p; p-next = s;s-next-prior = s;ai+1aiai-1刪除刪除q=p-next；p-next = q-next;p-next-prior = p;d

3、elete q;q=NULL;qpai-12.6 2.6 順序表和鏈表的比較順序表和鏈表的比較存儲結構比較項目順序表鏈表空間存儲空間預先分配，會導致空間閑置或溢出現(xiàn)象動態(tài)分配，不會出現(xiàn)存儲空間閑置或溢出現(xiàn)象存儲密度不用為表示結點間的邏輯關系而增加額外的存儲開銷，存儲密度等于1需要借助指針來體現(xiàn)元素間的邏輯關系，存儲密度小于1時間存取元素隨機存取，按位置訪問元素的時間復雜度為O(1)順序存取，按位置訪問元素時間復雜度為O(n)插入、刪除平均移動約表中一半元素，時間復雜度為O(n)不需移動元素，確定插入、刪除位置后，時間復雜度為O(1)適用情況 表長變化不大，且能事先確定變化的范圍 很少進行插入或

4、刪除操作，經(jīng)常按元素位置序號訪問數(shù)據(jù)元素 長度變化較大 頻繁進行插入或刪除操作第第6講講2.7 2.7 線性表的應用線性表的應用2.7.1 2.7.1 線性表的合并線性表的合并問題描述：問題描述： 假設利用兩個線性表假設利用兩個線性表LaLa和和LbLb分別表示兩分別表示兩個集合個集合A A和和B,B,現(xiàn)要求一個新的集合現(xiàn)要求一個新的集合 A=ABLa=(7, 5, 3, 11)Lb=(2, 6, 3)La=(7, 5, 3, 11, 2, 6) .依次依次取出取出Lb Lb 中的每個元素，執(zhí)行以下操作：中的每個元素，執(zhí)行以下操作：在在LaLa中查找該元素中查找該元素如果找不到，則將其插入如果

5、找不到，則將其插入La的最后的最后【算法步驟算法步驟】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) ListInsert(&La,+La_len,e); 【算法描述算法描述】)()(LBListLengthLAListLengthO算法時間復雜度：問題描述：問題描述： 已知線性表已知線性表La La 和和LbLb中的數(shù)據(jù)元素按值中的數(shù)據(jù)元素按值非遞減非遞減有有序排列序排列,

6、 ,現(xiàn)要求將現(xiàn)要求將LaLa和和LbLb歸并為一個新的線性表歸并為一個新的線性表LcLc, ,且且LcLc中的數(shù)據(jù)元素仍按值非遞減有序排列中的數(shù)據(jù)元素仍按值非遞減有序排列. .La=(1 ,7, 8)Lb=(2, 4, 6, 8, 10, 11)Lc=(1, 2, 4, 6, 7 , 8, 8, 10, 11) 2.7.2 2.7.2 有序表的合并有序表的合并(1) (1) 創(chuàng)建一個空表創(chuàng)建一個空表LcLc(2) 依次從依次從 La La 或或 Lb Lb 中中“摘取摘取”元素值較小元素值較小的結點插入到的結點插入到 Lc Lc 表的最后，直至其中一個表表的最后，直至其中一個表變空為止變空為止

7、(3) (3) 繼續(xù)將繼續(xù)將 La La 或或 Lb Lb 其中一個表的剩余結點其中一個表的剩余結點插入在插入在 Lc Lc 表的最后表的最后【算法步驟算法步驟】有序的順序表合并有序的順序表合并【算法描述算法描述】void MergeList(OrderedList La, OrderedList Lb, OrderedList &Lc) / 本算法將非遞減的有序表 La 和 Lb 歸并為 Lc / Merge_Listwhile (i = La_len) & (j = Lb_len) / La 和和 Lb 均不空均不空 GetElem(La, i, ai); GetElem(Lb, j, b

8、j); if (ai = bj) / 將 ai 插入到 Lc 中 ListInsert(Lc, Lc.length+1, ai); +i; else / 將 bj 插入到 Lc 中 ListInsert(Lc, Lc.length+1, bj); +j; InitList(Lc); / 構造空的線性表構造空的線性表 Lci = j = 1; La_len = ListLength(La); Lb_len = ListLength(Lb); while (i = La_len ) / 當La不空時 GetElem( La, i+, ai ); ListInsert( Lc, Lc.length+

9、1, ai ); / 插入插入 La 表中剩余元素表中剩余元素 while (j = Lb_len ) / 當Lb不空時 GetElem( Lb, j+, bj ); ListInsert( Lc, Lc.length+1, bj ); / 插入插入 Lb 表中剩余元素表中剩余元素)()(LBListLengthLAListLengthO算法時間復雜度：void MergeList_Sq(SqList La,SqList Lb,SqList &Lc) i=1; j=1; /i和和j分別分別指示指示兩兩個表的第一個元素個表的第一個元素 cLength=La.length+Lb.length; /

10、新表長度為待合并兩表的長度之和新表長度為待合并兩表的長度之和 Lc.elem=new ElemTypecLength; /為合并后的新表分配一個數(shù)組空間為合并后的新表分配一個數(shù)組空間 Lc.length=0; k=1; /指示指示Lc表的插入位置表的插入位置 while(i=La.length & j=Lb.length) /兩個表都非空兩個表都非空 if(La.elemi-1=Lb.elemj-1) /依次依次“摘取摘取”兩表中值較小的結點兩表中值較小的結點 Lc.elemk-1=La.elemi-1; Lc.length+ ;k+;+i; else Lc.elemk-1=Lb.elemj-

11、1; Lc.length+ ;k+;+j; while(i =La.length ) Lc.elemk-1=La.elemi-1; Lc.length+ ;k+;+i; /LB表已到表已到達表尾達表尾 while(j =Lb.length ) Lc.elemk-1=Lb.elemj-1; Lc.length+ ;k+; +j; /LA表已表已到達表尾到達表尾 /MergeList_Sq S(n)= O(n) n=La.length+Lb.length【算法描述算法描述】有序的順序表合并有序的順序表合并void MergeList_Sq(SqList La,SqList Lb,SqList &L

12、c) i=1; j=1; /i和和j分別分別指示指示兩兩個表的第一個元素個表的第一個元素 Lc.Length=La.length+Lb.length; /新表長度為待合并兩表的長度之和新表長度為待合并兩表的長度之和 Lc.elem=new ElemTypeLc.Length; /為合并后的新表分配一個數(shù)組空間為合并后的新表分配一個數(shù)組空間 k=0; /指示指示Lc表的插入表的插入位置位置 while(i=La.length & j=Lb.length) /兩個表都非空兩個表都非空 if(La.elemi-1=Lb.elemj-1) /依次依次“摘取摘取”兩表中值較小的結點兩表中值較小的結點 L

13、c.elemk+=La.elemi-1; +i; else Lc.elemk+=Lb.elemj-1; +j; while(i =La.length ) Lc.elemk+=La.elemi-1; +i; /LB表已到達表尾表已到達表尾 while(j data data )pc-next = pa;PaLa(Lcbpb有序鏈表合并有序鏈表合并( pa-data data )pc-next = pa;pc= pa;1PcLa(Lcbpb有序鏈表合并有序鏈表合并( pa-data data )pc-next = pa;pc= pa;1Pcpa

14、= pa-next;PaLa(Lcbpb有序鏈表合并有序鏈表合并( pa-data pb-data )pc-next = pb;1PcpaLa(Lcbpb有序鏈表合并有序鏈表合并( pa-data pb-data )pc-next = pb;1paPcpc= pb;2La(Lcb有序鏈表合并有序鏈表合并( pa-data pb-data )pc-next = pb;1paPcpc= pb;2pb =pb-next;pbLa(Lc)12467881011有序鏈表合并有序鏈表合并pc- next=pa?pa:pb; pa

15、(NULL)pbpcLbLa(Lc)12467881011合并后合并后delete Lb;Lb=Null;有序鏈表合并有序鏈表合并Lbvoid MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) pa=La-next; pb=Lb-next; pc=Lc=La; /用用La的頭結點作為的頭結點作為Lc的頭結點的頭結點 while(pa & pb) if(pa-datadata) pc-next=pa;pc=pa;pa=pa-next; elsepc-next=pb; pc=pb; pb=pb-next; pc-next=pa?pa:pb; /

16、插入剩余段插入剩余段 delete Lb; /釋放釋放Lb的頭的頭結點結點 Lb=NULL: S(n)= O(1)()(LBListLengthLAListLengthO【算法描述算法描述】有序的鏈表合并有序的鏈表合并思考思考1：要求合并后的表無重復數(shù)據(jù)，如何實現(xiàn)？：要求合并后的表無重復數(shù)據(jù)，如何實現(xiàn)？提示：要單獨考慮提示：要單獨考慮pa-data = =pb-data La(Lc)12467881011要求結果鏈表仍使用原來兩個鏈表的存儲空要求結果鏈表仍使用原來兩個鏈表的存儲空間間, , 不另外占用其它的存儲空間。不另外占用其它的存儲空間。表中允許有重復的數(shù)據(jù)。表中允許有重復的數(shù)據(jù)。 思考思

17、考2：將兩個非遞減的有序鏈表合并為一個非遞：將兩個非遞減的有序鏈表合并為一個非遞增的有序鏈表，如何實現(xiàn)？增的有序鏈表，如何實現(xiàn)？改變插入位置在改變插入位置在表表頭結點頭結點之后即可之后即可2.8 2.8 案例分析與實現(xiàn)案例分析與實現(xiàn)指數(shù)（下標i）01234系數(shù)pi105-432P(x) = 10 + 5x - 4x2 + 3x3 + 2x4數(shù)組表示數(shù)組表示（每一項的指數(shù)（每一項的指數(shù)i隱含隱含在其系數(shù)在其系數(shù)pi的序號中）的序號中）Rn(x) = Pn(x) + Qm(x)線性表線性表R = (p0 + q0,p1 + q1,p2 + q2,pm + qm,pm+1,pn)下標i0123下標i

18、012系數(shù)ai7395系數(shù)bi822-9指數(shù)01817指數(shù)178多項式非零項非零項的數(shù)組表示 （a）A(x) = 7 + 3x + 9x8 + 5x17 （b）B(x) = 8x + 22x7 9x8 線性表線性表P =(p1, e1), (p2, e2),(pm, em)l創(chuàng)建一個創(chuàng)建一個新數(shù)組新數(shù)組c cl分別從頭遍歷比較分別從頭遍歷比較a a和和b b的每一項的每一項指數(shù)相同指數(shù)相同，對應系數(shù)相加，若其和不為零，則在，對應系數(shù)相加，若其和不為零，則在c c中增加一個新項中增加一個新項指數(shù)不相同指數(shù)不相同，則將指數(shù)較小的項復制到，則將指數(shù)較小的項復制到c c中中l(wèi)一個多項式已遍歷一個多項式

19、已遍歷完畢完畢時，將另一個剩余項依次復制到時，將另一個剩余項依次復制到c c中即可中即可l順序存儲結構存在問題順序存儲結構存在問題存儲空間分配不靈活存儲空間分配不靈活運算的空間復雜度高運算的空間復雜度高鏈式存儲結構鏈式存儲結構typedef struct PNode float coef;/系數(shù)系數(shù) int expn;/指數(shù)指數(shù) struct PNode *next;/指針域指針域PNode,*Polynomial; coef expdatanexttypedef struct / 項項的表示 float coef; / 系數(shù)系數(shù) int exp; / 指數(shù)指數(shù) ElemType; typed

20、ef LNode PolyNode;typedef LinkList PolyList; / 用帶頭結點的單鏈表表示多項式結點的數(shù)據(jù)元素類型定義為: 創(chuàng)建一個只有頭結點的空鏈表。 根據(jù)多項式的項的個數(shù)n，循環(huán)n次執(zhí)行以下操作：l生成一個新結點*s；l輸入多項式當前項的系數(shù)和指數(shù)賦給新結點*s的數(shù)據(jù)域；l設置一前驅指針pre，用于指向待找到的第一個大于輸入項指數(shù)的結點的前驅，pre初值指向頭結點；l指針q初始化，指向首元結點；l循鏈向下逐個比較鏈表中當前結點與輸入項指數(shù)，找到第一個大于輸入項指數(shù)的結點*q；l將輸入項結點*s插入到結點*q之前。多項式創(chuàng)建多項式創(chuàng)建-【算法步驟算法步驟】A17(x

21、)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-1703198517-181227-98ABvoid CreatePolyn(Polynomial &P,int n)/輸入輸入m項的系數(shù)和指數(shù)，建立表示多項式的有序鏈表項的系數(shù)和指數(shù)，建立表示多項式的有序鏈表P P=new PNode; P-next=NULL;/先建立一個帶頭結點的單鏈表先建立一個帶頭結點的單鏈表 for(i=1;is-coefs-expn;/輸入系數(shù)和指數(shù)輸入系數(shù)和指數(shù) pre=P;/pre用于保存用于保存q的前驅，初值為頭結點的前驅，初值為頭結點 q=P-next;/q初始化，指向首元結點初始化，指向首元結點 while(q&q-expnexpn)/找到第一個大于輸入項指數(shù)的項找到第一個大于輸入項指數(shù)的項*q pre=q; q=q-next; /while s-next=q;/將輸入項將輸入項s插入到插入到q和其前驅結點和其前驅結點pre之間之間 pre-next=s; /for 多項式創(chuàng)建多項式創(chuàng)建-【算法描述算法描述】11-1A7 0 1 9 8 5 17 -1B8 1 22 7 -9 8 papbC pc3r0rr17787178522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxxxApb=NULL 指針p1和p2初始化，分別指向Pa和Pb