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

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

p=la->next；

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

p=la->next;la->next=lb->next->next;lb->next=p;第1頁(yè)/共20頁(yè)

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

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

structDuLNode*prior;

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

structDuLNode*next;

//

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

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

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

typedefstruct{Linkhead,tail;intlen;}linklist;第7頁(yè)/共20頁(yè)

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

e=45,

則

q指向

若e=88,

則q指向表示值為88的元素應(yīng)插入在該指針?biāo)附Y(jié)點(diǎn)之后。

2.4有序表第9頁(yè)/共20頁(yè)1.順序有序表中插入一個(gè)元素仍然保持有序voidOrdInsert(SqList*L,ElemTypex){i=L->length-1;//從最后一個(gè)元素起進(jìn)行查找比較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頁(yè)/共20頁(yè)2.順序有序表中刪除值相同的多余元素voidpurge(SqList*L)//表必須不是空表{i=0;j=1;//設(shè)新的La表為只有一個(gè)元素表

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表為只有一個(gè)元素表

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頁(yè)/共20頁(yè)3.指向尾結(jié)點(diǎn)的循環(huán)有序鏈表求并集（帶頭結(jié)點(diǎn)），原兩個(gè)表不存在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頁(yè)/共20頁(yè)3.指向尾結(jié)點(diǎn)的循環(huán)有序鏈表求并集（帶頭結(jié)點(diǎn)），原兩個(gè)表不存在la為交集表的頭指針（算法改進(jìn)）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頁(yè)/共20頁(yè)4.有序單鏈表判斷兩個(gè)集合是否相等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;}時(shí)間復(fù)雜度為O(n)

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

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

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

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

第16頁(yè)/共20頁(yè)第17頁(yè)/共20頁(yè)本課題目：實(shí)驗(yàn)二線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)驗(yàn)實(shí)驗(yàn)?zāi)康模赫莆真湵淼亩x及操作的C++語(yǔ)言實(shí)現(xiàn)方法實(shí)驗(yàn)重點(diǎn)：鏈表的操作的C++語(yǔ)言實(shí)現(xiàn)方法實(shí)驗(yàn)難點(diǎn)：鏈表的操作的C++語(yǔ)言實(shí)現(xiàn)方法實(shí)驗(yàn)內(nèi)容：1建立頭文件，包含數(shù)據(jù)類型定義和基本操作。2建立程序文件利用鏈表完成基本的刪除，插入，查找等各種功能。3上機(jī)基本步驟：DEFINE宏定義INCLUDE語(yǔ)句類型定義編寫實(shí)現(xiàn)各個(gè)功能的函數(shù)編寫調(diào)用各個(gè)函數(shù)的主程序（main函數(shù)）2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)上機(jī)實(shí)習(xí)第18頁(yè)/共20頁(yè)voidListInsert_L(LinkList&L,L