第2章線性表第3節(jié)

會計學1第2章線性表第3節(jié)循環(huán)鏈表的優(yōu)點：假設(shè)有兩個鏈表，要想將這兩個鏈表連接起來，若是單鏈表需要找到前一個鏈表的最后一個結(jié)點，時間復雜度為O(n)，而對指向尾結(jié)點的單循環(huán)鏈表而言，只需要改變一個指針就可以了，時間復雜度為O（1）合并鏈表la,lb的基本操作為：(1)la,lb為單鏈表（帶頭結(jié)點）

p=la->next；

while(p->next!=NULL)p=p->next;p->next=lb->next(合并后以la為頭指針）（2）la,lb為指向尾結(jié)點的單循環(huán)鏈表（帶頭結(jié)點）

p=la->next;la->next=lb->next->next;lb->next=p;第1頁/共20頁

2.雙向鏈表（DoublyLinkedList)typedefstructDuLNode{ElemTypedata;

//數(shù)據(jù)域

structDuLNode*prior;

//指向前驅(qū)的指針域

structDuLNode*next;

//

指向后繼的指針域}DuLNode,*DuLinkList;對指向雙向鏈表任一結(jié)點的指針d，有下面的關(guān)系：d->next->prior=d->prior->next=d即當前結(jié)點后繼的前趨是自身，當前結(jié)點前趨的后繼也是自身定義：每個結(jié)點中有兩個指針域，其一指向直接后繼，另一指向直接前趨。

問題：執(zhí)行前插操作或刪除操作時，如何操作？第2頁/共20頁雙向鏈表的操作特點：“查詢”和單鏈表相同?！安迦搿焙汀皠h除”時需要同時修改兩個方向上的指針。雙向鏈表的優(yōu)點：可以克服單鏈表的單向性的缺點。查找前驅(qū)很方便。第3頁/共20頁ai-1aies->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;psai-1ai插入第4頁/共20頁ai-1刪除aiai+1p->prior->next=p->next;p->next->prior=p->prior;ai-1第5頁/共20頁3.雙向循環(huán)鏈表空表非空表a1a2…...an第6頁/共20頁構(gòu)造一個完整的鏈表結(jié)構(gòu)//節(jié)點結(jié)構(gòu)

typedefstructLnode{Elemtypedata;structLnode*next;}*Link;//鏈表結(jié)構(gòu)

typedefstruct{Linkhead,tail;intlen;}linklist;第7頁/共20頁

2.4有序表定義：若線性表中的數(shù)據(jù)元素之間可以相互比較，并且數(shù)據(jù)元素在線性表中依值非遞減或非遞增有序排列，即ai>=ai+1或ai<=ai+1.如何在順序有序表中插入一個元素仍然保持有序第8頁/共20頁(12,23,34,45,56,67,78,89,98,45)例如:若

e=45,

則

q指向

若e=88,

則q指向表示值為88的元素應插入在該指針所指結(jié)點之后。

2.4有序表第9頁/共20頁1.順序有序表中插入一個元素仍然保持有序voidOrdInsert(SqList*L,ElemTypex){i=L->length-1;//從最后一個元素起進行查找比較while(i>=0&&x<L->elem[i]){L->elem[i+1]=L->elem[i];i--;}L->elem[i+1]=x;L->length++;}

2.4有序表第10頁/共20頁2.順序有序表中刪除值相同的多余元素voidpurge(SqList*L)//表必須不是空表{i=0;j=1;//設(shè)新的La表為只有一個元素表

while(j<L->length){if(L->elem[i]!=L->elem[j])L->elem[++i]=L->elem[j];j++;}L->length=i+1;}voidpurge(SqList*L)//表可以是空表也可以不是空表{i=-1;j=0;//設(shè)新的La表為只有一個元素表

while(j<L->length){if(j==0||L->elem[i]!=L->elem[j])L->elem[++i]=L->elem[j];j++;}L->length=i+1;}

2.4有序表第11頁/共20頁3.指向尾結(jié)點的循環(huán)有序鏈表求并集（帶頭結(jié)點），原兩個表不存在la為交集表的頭指針voidunion_OL(LinkList&La，LinkList&Lb){pa=La->next->next;pb=Lb->next->next;rc=La->next;while(pa!=La->next&&pb!=Lb->next){if(pa->data<pb->data){rc->next=pa;rc=pa;pa=pa->next;}elseif(pa->data>pb->data){rc->next=pb;rc=pb;pb=pb->next;}else{rc->next=pa;rc=pa;pa=pa->next;qb=pb;pb=pb->next;deleteqb;}}if(pb==Lb->next)rc->next=pa;else{rc->next=pb;pb=Lb->next;Lb->next=La->next;La=Lb;}deletepb;}

2.4有序表第12頁/共20頁3.指向尾結(jié)點的循環(huán)有序鏈表求并集（帶頭結(jié)點），原兩個表不存在la為交集表的頭指針（算法改進）voidunion_OL_1(LinkList&La，LinkList&Lb){La->next->data=MAX;Lb->next->data=MAX;pa=La->next->next;pb=Lb->next->next;rc=La->next;while(pa!=La->next||pb!=Lb->next){if(pa->data<pb->data){rc->next=pa;rc=pa;pa=pa->next;}elseif(pa->data>pb->data){rc->next=pb;rc=pb;pb=pb->next;}else{rc->next=pa;rc=pa;pa=pa->next;qb=pb;pb=pb->next;deleteqb;}}rc->next=La;//封閉鏈環(huán)

deleteLb->next;//釋放B表的表頭}

2.4有序表第13頁/共20頁4.有序單鏈表判斷兩個集合是否相等boolisequal_OL(LinkListA,LinkListB){pa=A->next;pb=B->next;while(pa&&pb&&pa->data==pb->data){pa=pa->next;pb=pb->next;}if(pa==NULL&&pb==NULL)returnTRUE;elsereturnFALSE;}時間復雜度為O(n)

2.4有序表第14頁/共20頁基于空間的考慮

在鏈表中的每個結(jié)點，除了數(shù)據(jù)域外，還要額外設(shè)置指針（或光標）域，從存儲密度來講，這是不經(jīng)濟的。所謂存儲密度(StorageDensity),是指結(jié)點數(shù)據(jù)本身所占的存儲量和整個結(jié)點結(jié)構(gòu)所占的存儲量之比，存儲密度越大，存儲空間的利用率就越高。當線性表的長度變化不大，易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表作為存儲結(jié)構(gòu)。2.基于查找時間的考慮

順序表是由向量實現(xiàn)的，它是一種隨機存取結(jié)構(gòu)，對表中任一結(jié)點都可以在O(1)時間內(nèi)直接地存取，而鏈表中的結(jié)點，需從頭指針起順著鏈找才能取得。因此，若線性表的操作主要是進行查找，很少做插入和刪除時，宜采用順序表做存儲結(jié)構(gòu)。2．5順序表和鏈表的綜合比較第15頁/共20頁2.線性表有兩種存儲結(jié)構(gòu)：順序表，鏈表。問題：（1）如果有n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)變化，線性表的總數(shù)也會自動地改變。在此情況下，應選用哪種存儲結(jié)構(gòu)？為什么？(2)若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應采用哪種存儲結(jié)構(gòu)？為什么？2．5順序表和鏈表的綜合比較答：（1）選鏈式存儲結(jié)構(gòu)。它可動態(tài)申請內(nèi)存空間，不受表長度（即表中元素個數(shù)）的影響，插入、刪除時間復雜度為O（1）。

（2）選順序存儲結(jié)構(gòu)。順序表可以隨機存取，時間復雜度為O(1)。對于頻繁進行插入和刪除的線性表，宜采用鏈表做存儲結(jié)構(gòu)。若表的插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。

第16頁/共20頁第17頁/共20頁本課題目：實驗二線性表的鏈式存儲實驗實驗目的：掌握鏈表的定義及操作的C++語言實現(xiàn)方法實驗重點：鏈表的操作的C++語言實現(xiàn)方法實驗難點：鏈表的操作的C++語言實現(xiàn)方法實驗內(nèi)容：1建立頭文件，包含數(shù)據(jù)類型定義和基本操作。2建立程序文件利用鏈表完成基本的刪除，插入，查找等各種功能。3上機基本步驟：DEFINE宏定義INCLUDE語句類型定義編寫實現(xiàn)各個功能的函數(shù)編寫調(diào)用各個函數(shù)的主程序（main函數(shù)）2.3線性表的鏈式表示和實現(xiàn)上機實習第18頁/共20頁voidListInsert_L(LinkList&L,L