算法與數(shù)據(jù)結(jié)構(gòu) C語言版 第二版 (陳守孔 孟佳娜 武秀川 著) 機(jī)械工業(yè)出版社課后答案 第2章 線性表
《算法與數(shù)據(jù)結(jié)構(gòu) C語言版 第二版 (陳守孔 孟佳娜 武秀川 著) 機(jī)械工業(yè)出版社課后答案 第2章 線性表》由會(huì)員分享,可在線閱讀,更多相關(guān)《算法與數(shù)據(jù)結(jié)構(gòu) C語言版 第二版 (陳守孔 孟佳娜 武秀川 著) 機(jī)械工業(yè)出版社課后答案 第2章 線性表(10頁珍藏版)》請?jiān)谘b配圖網(wǎng)上搜索。
1、 第2章 線性表 ? 一、基礎(chǔ)知識(shí)題 2.1 試述頭指針、頭結(jié)點(diǎn)、元素結(jié)點(diǎn)、首元結(jié)點(diǎn)的區(qū)別,說明頭指針和頭結(jié)點(diǎn)的作 【解答】指向鏈表第一個(gè)結(jié)點(diǎn)(或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn))的指針稱為頭指針?!邦^指針”具有標(biāo)識(shí)一個(gè)鏈表的作用,所以經(jīng)常用頭指針代表鏈表的名字,如鏈表L既是指鏈表的名字是L,也是指鏈表的第一個(gè)結(jié)點(diǎn)的地址存儲(chǔ)在指針變量L中,頭指針為“NULL”則表示一個(gè)空表。 有時(shí),我們在整個(gè)線性鏈表的第一個(gè)元素結(jié)點(diǎn)之前加入一個(gè)結(jié)點(diǎn),稱為頭結(jié)點(diǎn),它的數(shù)據(jù)域可以不存儲(chǔ)任何信息(也可以做監(jiān)視哨或存放線性表的長度等附加信息),指針域中存放的是第一個(gè)數(shù)據(jù)結(jié)點(diǎn)的地址,空表時(shí)為空。 “頭結(jié)點(diǎn)”的加入,使
2、插入和刪除等操作方便統(tǒng)一。 元素結(jié)點(diǎn)即是數(shù)據(jù)結(jié)點(diǎn),至少包括元素自身信息和其后繼元素的地址兩個(gè)域。 首元結(jié)點(diǎn)是指鏈表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn);為了操作方便,通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn),稱為頭結(jié)點(diǎn)。 ? 2.2分析順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn),說明何時(shí)應(yīng)該利用何種結(jié)構(gòu)。 【解答】①從空間上來看,當(dāng)線性表的長度變化較大,難以估計(jì)其規(guī)模時(shí),選用動(dòng)態(tài)的鏈表作為存儲(chǔ)結(jié)構(gòu)比較合適,但鏈表除了需要設(shè)置數(shù)據(jù)域外,還要額外設(shè)置指針域,因此當(dāng)線性表長度變化不大,易于事先確定規(guī)模時(shí),為了節(jié)約存儲(chǔ)空間,宜采用順序存儲(chǔ)結(jié)構(gòu)。 ②從時(shí)間上看,順序表具有按元素序號(hào)隨機(jī)訪問的特點(diǎn),在順序表中按序號(hào)訪問
3、數(shù)據(jù)元素的時(shí)間復(fù)雜度為O(1);而鏈表中按序號(hào)訪問的時(shí)間復(fù)雜度為O(n)。所以如果經(jīng)常按序號(hào)訪問數(shù)據(jù)元素,使用順序表優(yōu)于鏈表。 在順序表中做插入刪除操作時(shí),平均移動(dòng)大約表中一半的元素,因此n較大時(shí)順序表的插入和刪除效率低。在鏈表中作插入、刪除,雖然也要找插入位置,但操作主要是比較操作。從這個(gè)角度考慮顯然鏈表優(yōu)于順序表。 總之,兩種存儲(chǔ)結(jié)構(gòu)各有長短,選擇那一種存儲(chǔ)結(jié)構(gòu),由實(shí)際問題中的主要因素決定。 ? 2.3 分析在順序存儲(chǔ)結(jié)構(gòu)下插入和刪除結(jié)點(diǎn)時(shí)平均需要移動(dòng)多少個(gè)結(jié)點(diǎn)。 【解答】平均移動(dòng)表中大約一半的結(jié)點(diǎn),插入操作平均移動(dòng) 個(gè)結(jié)點(diǎn),刪除操作平均移動(dòng) 個(gè)結(jié)點(diǎn)。具體移動(dòng)的次數(shù)取決于表長和插
4、入、刪除的結(jié)點(diǎn)的位置。 ? 2.4 為什么在單循環(huán)鏈表中常使用尾指針,若只設(shè)頭指針,插入元素的時(shí)間復(fù)雜度如何? 【解答】單循環(huán)鏈表中無論設(shè)置尾指針還是頭指針都可以遍歷表中任一個(gè)結(jié)點(diǎn)。設(shè)置尾指針時(shí),若在表尾進(jìn)行插入元素或刪除第一元素,操作可在O(1)時(shí)間內(nèi)完成;若只設(shè)置頭指針,表尾進(jìn)行插入或刪除操作,需要遍歷整個(gè)鏈表,時(shí)間復(fù)雜度為O(n)。 ? 2.5 在單鏈表、雙鏈表、單循環(huán)鏈表中,若知道指針p指向某結(jié)點(diǎn),能否刪除該結(jié)點(diǎn),時(shí)間復(fù)雜度如何? 【解答:】以上三種鏈表中,若知道指針p指向某結(jié)點(diǎn),都能刪除該結(jié)點(diǎn)。雙鏈表刪除p所指向的結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1),而單鏈表和單循環(huán)鏈表上刪除p所
5、指向的結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(n)。 ? 2.6 下面算法的功能是什么? LinkedList Unknown(LinkedList la) {LNode *q,*p; if(la && la->next) {q=la; la=la->next; p=la; while(p->next) p=p->next; p->next=q; q->next=null; } return la; } 【解答】將首元結(jié)點(diǎn)刪除并插入到表尾(設(shè)鏈表長度大于1)。 ?
6、2.7 選擇題:在循環(huán)雙鏈表的*p結(jié)點(diǎn)之后插入*s結(jié)點(diǎn)的操作是( ) la、p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B、p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; lc、s->prior=p; s->next=p->next; p->next:=s; p->next->prior=s; D、s->prior=p; s>next=p>next; p>next->prio
7、r =s; p->next=s; 【解答】D ? 2.8 選擇題:若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算,則利用( )存儲(chǔ)方式最節(jié)省時(shí)間。 la.順序表 B.雙鏈表 lc.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D.單循環(huán)鏈表 【解答】la ? 二、算法設(shè)計(jì)題 2.9 設(shè)ha和hb分別是兩個(gè)帶頭結(jié)點(diǎn)的非遞減有序單鏈表的頭指針,試設(shè)計(jì)算法, 將這兩個(gè)有序鏈表合并成一個(gè)非遞增有序的單鏈表。要求使用原鏈表空間,表中無重復(fù)數(shù)據(jù)。 【題目分析】因?yàn)閮涉湵硪寻丛刂捣沁f減次序排列,將其合并時(shí),均從第一個(gè)結(jié)點(diǎn)起進(jìn)行比較,將小的鏈入鏈表中,同時(shí)后移鏈表
8、工作指針,若遇值相同的元素,則刪除之。該問題要求結(jié)果鏈表按元素值非遞增次序排列,故在合并的同時(shí),將鏈表結(jié)點(diǎn)逆置。 LinkedList Union(LinkedList ha,hb) ∥ha,hb分別是帶頭結(jié)點(diǎn)的兩個(gè)單鏈表的頭指針,鏈表中的元素值按遞增序排列 ∥本算法將兩鏈表合并成一個(gè)按元素值遞減次序排列的單鏈表,并刪除重復(fù)元素 { pa=ha->next; ∥pa是鏈表ha的工作指針 pb=hb->next; ∥pb是鏈表hb的工作指針 ha->next=null; ∥ha作結(jié)果鏈表的頭指針,先將結(jié)果鏈表初始化為空 while(pa!=nu
9、ll && pb!=null) ∥當(dāng)兩鏈表均不為空時(shí)作
{while(pa->next && pa->data==pa->next->data)
{u=pa->next; pa->next=u->next; free(u)}∥刪除pa鏈表中的重復(fù)元素
while(pb->next && pb->data==pb->next->data)
{u=pb->next; pb->next=u->next; free(u)}∥刪除pb鏈表中的重復(fù)元素
if(pa->data
10、>next; ∥將pa 的后繼結(jié)點(diǎn)暫存于r
pa->next=ha->next; ∥將pa結(jié)點(diǎn)鏈于結(jié)果表中,同時(shí)逆置
ha->next=pa;
pa=r; ∥恢復(fù)pa為當(dāng)前待比較結(jié)點(diǎn)
}
else if(pb->data
11、為當(dāng)前待比較結(jié)點(diǎn) } else{u=pb;pb=pb->next;free(u)}∥刪除鏈表pb和pa中的重復(fù)元素 }// while(pa!=null && pb!=null) if(pa) pb=pa; ∥避免再對pa寫下面的while語句 while(pb!=null) ∥將尚未到尾的表逆置到結(jié)果表中 {r=pb->next; pb->next=ha->next; ha->next=pb; pb=r; } return ha
12、 }∥算法Union結(jié)束 ? 2.10????????????? 設(shè)la是一個(gè)雙向循環(huán)鏈表,其表中元素遞增有序。試寫一算法插入元素x,使表中元素依然遞增有序。 【問題分析】雙向鏈表的插入與單鏈表類似,但需修改雙向指針。 DLinkedList DInsert(DLinkedList la, ElemType x) ∥在遞增有序的雙向循環(huán)鏈表la中插入元素x,使表中元素依然遞增有序 {p=la->next; ∥p指向第一元素 la->data=MaxElemType;∥MaxElemType是和x同類型
13、的機(jī)器最大值,用做監(jiān)視哨
while(p->data
14、鏈表中某結(jié)點(diǎn),刪除結(jié)點(diǎn)*p的直接前驅(qū)結(jié)點(diǎn),要找到*p的前驅(qū)結(jié)點(diǎn)的前驅(qū)*pre。進(jìn)行如下操作:u=pre->next; pre->next=u->next;free(u); LinkedList LinkedListDel(LinkedList la,LNode *p) {∥刪除單鏈表la上的結(jié)點(diǎn)*p的直接前驅(qū)結(jié)點(diǎn),假定*p存在 pre=la; if(pre-next==p) printf(“*p是鏈表第一結(jié)點(diǎn),無前驅(qū)\n”)?; exit(0)?; } while(pre->next->next !=p) pre=pre->next; u=pre->n
15、ext; pre->next=u->next; free(u); return(la); } 2.12????????????? 設(shè)計(jì)一算法,將一個(gè)用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式,使這兩個(gè)多項(xiàng)式各自僅有奇次冪或偶次冪項(xiàng),并要求利用原鏈表中的結(jié)點(diǎn)空間來構(gòu)造這兩個(gè)鏈表。 【題目分析】設(shè)循環(huán)鏈表表示的多項(xiàng)式的結(jié)點(diǎn)結(jié)構(gòu)為: typedef struct node {int power; ∥冪 float coef; ∥系數(shù)
16、 ElemType other; ∥其他信息 struct node *next; ∥指向后繼的指針 }PNode,*PolyLinkedList; 則可以從第一個(gè)結(jié)點(diǎn)開始,根據(jù)結(jié)點(diǎn)的冪是奇數(shù)或偶數(shù)而將其插入到奇次冪或偶次冪項(xiàng)的鏈表中。假定用原鏈表保存偶次冪,要為奇次冪的鏈表生成一個(gè)表頭,為了保持鏈表中結(jié)點(diǎn)的原來順序,用一個(gè)指針指向奇次冪鏈表的表尾,注意鏈表分解時(shí)不能“斷鏈”。 void PolyDis(PolyLinkedList poly) ∥將poly表示的多項(xiàng)式鏈表分解為各含奇次冪或偶次冪項(xiàng)的兩個(gè)循環(huán)鏈表 {PolyLink
17、edList poly2=(PolyLinkedList)malloc(sizeof(PNode)); ∥poly2表示只含奇次冪的多項(xiàng)式 r2=poly2; ∥r2是只含奇次冪的多項(xiàng)式鏈表的尾指針 r1=poly; ∥r1是只含偶次冪的多項(xiàng)式鏈表當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針 p=poly->next; ∥鏈表帶頭結(jié)點(diǎn),p指向第一個(gè)元素 while(p!=poly) if(p->power % 2)∥處理奇次冪 {r=p->next; ∥暫存后繼 r2->nex
18、t=p; ∥結(jié)點(diǎn)鏈入奇次冪鏈表 r2=p; ∥尾指針后移 p=r; ∥恢復(fù)當(dāng)前待處理結(jié)點(diǎn) } else ∥處理偶次冪 {r1->next=p; r1=p; p=p->next;} } r->next=poly2; r1->next=poly; ∥構(gòu)成循環(huán)鏈表 }∥PolyDis ? 2.13????????????? 以帶頭結(jié)點(diǎn)的雙向鏈表表示的線性表L=(a1,a2,…,an),試寫一時(shí)間復(fù)雜度為O(n)的算法,將L改造為L=(a1,a3,…,an,…,a4,a2)。 【題目分析】
19、分析結(jié)果鏈表,易見鏈表中位置是奇數(shù)的結(jié)點(diǎn)保持原順序,而位置是偶數(shù)的結(jié)點(diǎn)移到奇數(shù)結(jié)點(diǎn)之后,且以與原來相反的順序存放。因此,可從鏈表第一個(gè)結(jié)點(diǎn)開始處理,位置是奇數(shù)的結(jié)點(diǎn)保留不動(dòng),位置是偶數(shù)的結(jié)點(diǎn)插入到鏈表尾部,并用一指針指向鏈表尾,以便對偶數(shù)結(jié)點(diǎn)“尾插入”。 DLinkedList DInvert(DLinkedList L) ∥將雙向循環(huán)鏈表L位置是偶數(shù)的結(jié)點(diǎn)逆置插入到鏈表尾部 {p=L->next; ∥p指向第一元素 Q=p->prior; ∥Q指向最后一個(gè)元素 pre=L?; ∥pre指向
20、鏈表中位置為奇數(shù)的結(jié)點(diǎn)的前驅(qū) r=L?; ∥r指向鏈表中偶數(shù)結(jié)點(diǎn)的尾結(jié)點(diǎn) i=0?; ∥i記錄結(jié)點(diǎn)序號(hào) while(p?!= Q) ∥尋找插入位置 {i++?; if(i%2) ∥處理序號(hào)為奇數(shù)的結(jié)點(diǎn) {p->prior=pre?;pre->next=p?;pre=p; p=p->next;} else ∥處理序號(hào)為偶數(shù)的結(jié)點(diǎn) {u=p?; ∥記住當(dāng)前結(jié)點(diǎn) p=p->next?;∥p指向下個(gè)待處理結(jié)點(diǎn) u->prior=r->prio
21、r;?∥以下4個(gè)語句將結(jié)點(diǎn)插入鏈表尾 u->next=r; r->prior->next=u; r->prior=u; r=u; ∥指向新的表尾 } } 2.14????????????? 設(shè)單向鏈表的頭指針為head,試設(shè)計(jì)算法,將鏈表按遞增的順序就地排序。 【題目分析】本題中的“就地排序”,可理解為不另辟空間,這里利用直接插入原則把鏈表整理成遞增有序鏈表。 LinkedList LinkListInsertSort(LinkedList head) ∥head是帶頭結(jié)點(diǎn)的單鏈表,本算法利用直接插入原則將鏈表整理成
22、遞增的有序鏈表
{if(head->next!=null) ∥鏈表不為空表
{p=head->next->next; ∥p指向第一結(jié)點(diǎn)的后繼
head->next->next=null;
∥直接插入原則認(rèn)為第一元素有序,然后從第二元素起依次插入
while(p!=null)
{r=p->next; ∥暫存p的后繼
q=head;
while(q->next && q->next->data
23、>next=p; p=r; } } } ? 2.15????????????? 已知遞增有序的三個(gè)單鏈表分別代表集合A,B和C,設(shè)計(jì)算法實(shí)現(xiàn)A=A∪(B∩C),并使結(jié)果鏈表仍保持遞增。要求算法的時(shí)間復(fù)雜度為O(|A|+|B|+|C|)。其中,|A|為集合A的元素個(gè)數(shù)。 【題目分析】本題首先求B和C的交集,即求B和C中共有元素,再與A求并集,同時(shí)刪除重復(fù)元素,以保持結(jié)果A遞增。 LinkedList union(LinkedList A,B,C) ∥A、B和C均是帶頭結(jié)點(diǎn)的遞增有序的單鏈表,本算法實(shí)現(xiàn)A=A∪(B∩C) ∥使結(jié)果表A保持遞增有序 {pa=A->next
24、;pb=B->next;pc=C->next;∥設(shè)置三個(gè)工作指針
pre=A; ∥pre指向結(jié)果鏈表中當(dāng)前待合并結(jié)點(diǎn)的前驅(qū)
A->data=MaxElemType;∥同類型元素最大值,起監(jiān)視哨作用
while(pa || pb && pc)
{while(pb && pc)
if(pb->data
25、pa && pa->data
26、e->next=null; ∥當(dāng)B,C無公共元素,將A中剩余鏈入 }∥算法Union結(jié)束 2.16????????????? 順序表la與lb非遞減有序,順序表空間足夠大。試設(shè)計(jì)一種高效算法,將lb中元素合到la中,使新的la的元素仍保持非遞減有序。高效指最大限度地避免移動(dòng)元素。 【題目分析】順序存儲(chǔ)結(jié)構(gòu)的線性表的插入,其時(shí)間復(fù)雜度為O(n),平均移動(dòng)近一半的元素。線性表la和lb合并時(shí),若從第一個(gè)元素開始,一定會(huì)造成元素后移,這不符合本題“高效算法”的要求。應(yīng)從線性表的最后一個(gè)元素開始比較,大者放到最終位置上。設(shè)兩線性表的長度各為m和n ,則結(jié)果表的最后一個(gè)元素應(yīng)在m+
27、n位置上。這樣從后向前,直到第一個(gè)元素為止。 SeqList Union(SeqList la, SeqList lb) ∥la和lb是順序存儲(chǔ)的非遞減有序線性表,本算法將lb合并到la中,元素仍非遞減有序 { m=la.last;n=lb.last;∥m,n分別為線性表la和lb的長度 k=m+n-1; ∥k為結(jié)果線性表的工作指針(下標(biāo)) i=m-1;j=n-1; ∥i,j分別為線性表la和lb的工作指針(下標(biāo)) while(i>=0 && j>=0) if(la.data[i]>=
28、lb.data[j]) la.data[k--]=la.data[i--]; else la.data[k--]=lb.data[j--]; while(j>=0) la.data[k--]=lb.data[j--]; la.last=m+n; return la; } 【算法討論】算法中數(shù)據(jù)移動(dòng)是主要操作。在最佳情況下(lb的最小元素大于la的最大元素),僅將lb的n個(gè)元素移(拷貝)到la中,時(shí)間復(fù)雜度為O(n),最差情況,la的所有元素都要移動(dòng),時(shí)間復(fù)雜度為O(m+n)。因數(shù)據(jù)合并到la中,所以在退出第一個(gè)whi
29、le循環(huán)后,只需要一個(gè)while循環(huán),處理lb中剩余元素。第二個(gè)循環(huán)只有在lb有剩余元素時(shí)才執(zhí)行,而在la有剩余元素時(shí)不執(zhí)行。本算法 “最大限度的避免移動(dòng)元素”,是“一種高效算法”。 ? 2.17????????????? 已知非空線性鏈表由head指出,試寫一算法,將鏈表中數(shù)據(jù)域值最小的那個(gè)結(jié)點(diǎn)移到鏈表的最前面。要求:不得額外申請新的鏈結(jié)點(diǎn)。 【題目分析】 本題要求將鏈表中數(shù)據(jù)域值最小的結(jié)點(diǎn)移到鏈表的最前面。首先要查找最小值結(jié)點(diǎn)。將其移到鏈表最前面,實(shí)質(zhì)上是將該結(jié)點(diǎn)從鏈表上摘下(不是刪除并回收空間),再插入到鏈表的最前面。 LinkedList Delinsert(LinkedLi
30、st head)
∥本算法將非空線性鏈表head中數(shù)據(jù)域值最小的那個(gè)結(jié)點(diǎn)移到鏈表的最前面
{p=head->next;∥p是鏈表的工作指針
pre=head; ∥pre指向鏈表中數(shù)據(jù)域最小值結(jié)點(diǎn)的前驅(qū)
q=p; ∥q指向數(shù)據(jù)域最小值結(jié)點(diǎn),初始假定是第一結(jié)點(diǎn)
while (p->next)
{if(p->next->data
31、t; ∥將最小值結(jié)點(diǎn)從鏈表上摘下 q->next=head->next; ∥將q結(jié)點(diǎn)插到鏈表最前面 head->next=q; } }∥Delinsert ? 2.18 設(shè)la是帶頭結(jié)點(diǎn)的非循環(huán)雙向鏈表的指針,其結(jié)點(diǎn)中除有prior,data和next外,還有一訪問頻度域freq,其值在鏈表初始使用時(shí)為0。當(dāng)在鏈表中進(jìn)行ListLocate(la,x)運(yùn)算時(shí),若查找失敗,則在表尾插入值為x的結(jié)點(diǎn);若查找成功,值為x的結(jié)點(diǎn)的freq值增1,并要求鏈表按freq域值非增(遞減)的順序排列,且最近訪問的結(jié)點(diǎn)排在頻度相同的結(jié)點(diǎn)的后面,使頻繁訪問的結(jié)點(diǎn)總是靠近表頭
32、。試編寫符合上述要求的ListLocate(la,x)運(yùn)算的算法,返回找到結(jié)點(diǎn)的指針。 【題目分析】首先在雙向鏈表中查找數(shù)據(jù)值為x的結(jié)點(diǎn),查到后,將結(jié)點(diǎn)從鏈表上摘下,然后再順結(jié)點(diǎn)的前驅(qū)鏈查找該結(jié)點(diǎn)的位置。 DLinkList ListLocate(DLinkedList L,ElemType x) ∥ L是帶頭結(jié)點(diǎn)的按訪問頻度遞減的雙向鏈表,本算法先查找數(shù)據(jù)x ∥查找成功時(shí)結(jié)點(diǎn)的訪問頻度域增1,最后將該結(jié)點(diǎn)按頻度遞減插入鏈表中 {DLinkList p=L->next,q; ∥p為L表的工作指針,q為p的前驅(qū),用于查找插入位置 while(p && p->data!
33、=x) p=p->next;∥ 查找值為x的結(jié)點(diǎn)
if(!p) {printf(“不存在所查結(jié)點(diǎn)\n”); exit(0);}
else { p->freq++; ∥ 令元素值為x的結(jié)點(diǎn)的freq域加1
p->next->prior=p->prior; ∥ 將p結(jié)點(diǎn)從鏈表上摘下
p->prior->next=p->next;
q=p->prior; ∥ 以下查找p結(jié)點(diǎn)的插入位置
while(q !=L && q->freq
34、or; p->next=q->next; q->next->prior=p;∥ 將p結(jié)點(diǎn)插入 p->prior=q; q->next=p; } return(p); ∥返回值為x的結(jié)點(diǎn)的指針 } ∥ 算法結(jié)束 ? 2.19????????????? 三個(gè)帶頭結(jié)點(diǎn)的線性鏈表la、lb和lc中的結(jié)點(diǎn)均依元素值自小至大非遞減排列(可能存在兩個(gè)以上值相同的結(jié)點(diǎn)),編寫算法對la表進(jìn)行如下操作:使操作后的la中僅留下三個(gè)表中均包含的數(shù)據(jù)元素的結(jié)點(diǎn),且沒有值相同的結(jié)點(diǎn),并釋放所有無用結(jié)點(diǎn)。限定算法的時(shí)間復(fù)雜度為O(m+n+p)
35、,其中m、n和p分別為三個(gè)表的長度。 【題目分析】 留下三個(gè)鏈表中公共數(shù)據(jù),首先查找兩表la和B中公共數(shù)據(jù),再去lc中找有無該數(shù)據(jù)。要消除重復(fù)元素,應(yīng)記住前驅(qū),要求時(shí)間復(fù)雜度O(m+n+p),在查找每個(gè)鏈表時(shí),指針不能回溯。 LinkedList lcommon(LinkedList la,lb,lc) ∥本算法使la表留下la、lb和lc三個(gè)非遞減有序表共同結(jié)點(diǎn),無重復(fù)元素 {pa=la->next;pb=lb->next;pc=lc->next; ∥pa,pb和pc分別是la,lb和lc三個(gè)表的工作指針 pre=la; la->data=MaxElemType ∥pre是la
36、表當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針,頭結(jié)點(diǎn)作監(jiān)視哨
while(pa && pb && pc) ∥當(dāng)la,lb和lc表均不空時(shí),查找三表共同元素
{while(pa&&pa->data==pre->data)
{u=pa; pa=pa->next; free(u);}//刪la中相同元素
while(pb && pc)
if(pb->data
37、元素值相等的結(jié)點(diǎn)
if(pb && pc)
{while(pa && pa->data
38、>next;pc=pc->next; ∥鏈表的工作指針后移 }∥pc,pa和pb對應(yīng)結(jié)點(diǎn)元素值相等 } }∥while(pa && pb && pc) pre->next=null; ∥置新la表表尾 while(pa!=null) ∥刪除原la表剩余元素。 {u=pa;pa=pa->next;free(u);} }∥算法結(jié)束 【算法討論】 算法中l(wèi)a表、lb表和lc表均從頭到尾(嚴(yán)格說lb、lc中最多一個(gè)到尾)遍歷一遍,算法時(shí)間復(fù)雜度符合O(m+n+p)。算法主要由while(pa && pb && pc)控制。三表有一個(gè)到尾則結(jié)束循環(huán)。要注意頭結(jié)點(diǎn)的監(jiān)視哨的作用,否則第一個(gè)結(jié)點(diǎn)要特殊處理。算法最后要給新la表置結(jié)尾標(biāo)記,同時(shí)若原la表沒到尾,還應(yīng)釋放剩余結(jié)點(diǎn)所占的存儲(chǔ)空間。
- 溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 安全評價(jià)師基礎(chǔ)知識(shí)教程
- 19、雪孩子(教育精品)
- “綠色建筑”研討會(huì)
- 2022年浙教初中數(shù)學(xué)七上《絕對值》課件6
- 2022年北師大版小學(xué)數(shù)學(xué)《快樂的動(dòng)物》課件
- 中考語文課件中考語文議論文構(gòu)思課件
- 《己亥雜詩》教學(xué)課件
- 職場禮儀培訓(xùn)教材(PPT 33頁)
- 百分?jǐn)?shù)的認(rèn)識(shí)課件 (2)(教育精品)
- 2623求二次函數(shù)的表達(dá)式
- 三年級語文上冊 第三單元期末總復(fù)習(xí)課件 新人教版 (1038)
- 招聘選拔與培養(yǎng)
- 《鄒忌諷齊王納諫》課件
- 中職 CAXA電子圖板繪圖教程(2007版)(第2版)第9章電子課件(電子教案)
- 必修2近代工業(yè)的艱難起步課件