數(shù)據(jù)結(jié)構(gòu)之線性表課件-閱讀頁
2024-09-20 09:01本頁面
【正文】 間，利用率低； 速度慢。 ?循環(huán)鏈表并不多占存儲單元，但從循環(huán)鏈表的任一個(gè)結(jié)點(diǎn)出發(fā)都可以訪問到此鏈表的每一個(gè)結(jié)點(diǎn)，因?yàn)楫?dāng)訪問到表尾結(jié)點(diǎn)后又能返回到頭結(jié)點(diǎn)。 ?表空時(shí)空表頭結(jié)點(diǎn)的指針指向其本身，如下面的圖所示為空循環(huán)鏈表。 h e a d ?若 pnext=head，則 p就是指向最后一個(gè)結(jié)點(diǎn)； ?若 headnext=head，則為空表。設(shè)編號為1,2,……,n(n0) 個(gè)人，按順時(shí)針圍坐一圈，每人有一正整數(shù)密碼 m。 對給定的 m（第 1次給定 m，以后即為結(jié)點(diǎn)的pwd），從第一個(gè)結(jié)點(diǎn)開始，尋找第 m個(gè)結(jié)點(diǎn)，將其輸出，并取出該結(jié)點(diǎn)的 pwd，執(zhí)行 m=pwd；從下一個(gè)結(jié)點(diǎn)繼續(xù)尋找第 m個(gè)結(jié)點(diǎn) ,……, 直到表空為止。 int pwd。 } clinklist。 for ( i=josephus_seqlength。 i) s1=(s1+m1)%i。 printf(“ ”,w)。因?yàn)槲步Y(jié)點(diǎn)由尾指針 rear來指示，則頭結(jié)點(diǎn)的位置是 rearnextnext。 ?雙鏈表的結(jié)點(diǎn)形式為： 其中鏈域 prior和 next分別指向本結(jié)點(diǎn)的直接前趨和直接后繼結(jié)點(diǎn)。 head ?雙向鏈表為空鏈表時(shí)， head 即 headnext=null ? ? ?雙鏈表較單鏈表雖然要多占用一些存儲單元，但對其插入和刪除操作以及查找結(jié)點(diǎn)的前趨和后繼都非常方便。 ?結(jié)點(diǎn)定義為： Typedef struct dbnode { elementtype data。 struct dbnode *next。 1. 雙鏈表的插入 ?設(shè)要在 p所指結(jié)點(diǎn)的 前面 插入一個(gè)新結(jié)點(diǎn)*q，則需要修改 4個(gè)指針 ： qprior=pprior。 (pprior)next=q。 p q ① ③ ④ ② 2. 雙鏈表的刪除 ?設(shè) p指向待刪除的結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)步驟為： (pprior) next=pnext。 ?這兩個(gè)語句的執(zhí)行順序可以顛倒，執(zhí)行這兩個(gè)語句之后，可調(diào)用 free(p),將 *p結(jié)點(diǎn)釋放。 ?1. 如果用 數(shù)組來表示一元多項(xiàng)式 ，以各項(xiàng)的指數(shù)作為下標(biāo)，將各個(gè)系數(shù)存入一維數(shù)組中。 求此兩多項(xiàng)式之和 C(x)=A(x)+B(x)。 Int exp。 } polyn。 基本思想 ：設(shè) A和 B為多項(xiàng)式 A和 B的搜索指針，比較其指數(shù)項(xiàng)， 若 AexpBexp, 則 A結(jié)點(diǎn)應(yīng)是和多項(xiàng)式中的一項(xiàng)， A后移； 若 AexpBexp, 將 B結(jié)點(diǎn)插入到 A結(jié)點(diǎn)之前， B后移； 若 Aexp=Bexp, 則兩結(jié)點(diǎn)的系數(shù)相加，若和不為 0，修改 A結(jié)點(diǎn)的系數(shù)， A,B后移；若為 0，刪除兩結(jié)點(diǎn)。 例 ? 一個(gè)單鏈表 L(至少有一個(gè)結(jié)點(diǎn) )，其頭結(jié)點(diǎn)指針為 head，編寫一個(gè)函數(shù)將 L倒置。 最后將第一個(gè)結(jié)點(diǎn)的 next域置為 NULL，并將頭指針指向最后一個(gè)結(jié)點(diǎn)。 p=head。 while(q!=NULL) /*沒有后繼時(shí)停止 */ { r=qnext。 p=q。 } headnext=NULL。 } 例 ?有兩個(gè)循環(huán)單鏈表，頭指針分為 head1和 head2，編寫函數(shù)將鏈表 head2鏈接到鏈表 head1之后，鏈接后的鏈表仍保持是循環(huán)鏈表的形式。 h e a d 1 a 1 a n a 2 h e a d 2 b 1 b n b 2 例3.2算法 link(node *head1, *head2) { node *p,*q。 while(pnext!=head1) p=pnext。 while(qnext!=head2) q=qnext。 qnext=head1。 ?解：在前面雙鏈表一節(jié)中，已經(jīng)給出了在一個(gè)結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)的方法，在一個(gè)結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)的思想與前面是一樣的。 int j。 /*建立一個(gè)待插入的結(jié)點(diǎn) ， 由 s指向 */ sdata=x。 headprior=s。 } 例3.3算法續(xù) else { p=head。 while(p!=NULL amp。 ji) { j++。 } if(p!=NULL) /*若查找成功 ， 把 s插入到 p之后 */ if(pnext==NULL) /*若 p是最后一個(gè)結(jié)點(diǎn)，則直接把 s結(jié)點(diǎn)鏈入 */ 例3.3算法續(xù) { pnext=s。 sprior=p。 pnextprior=s。 sprior=p。 } } 返回 小結(jié) ?單鏈表 ?循環(huán)鏈表 ?雙向鏈表 ?雙向循環(huán)鏈表 ?十字鏈表 返回 習(xí)題與練習(xí) ?一、基礎(chǔ)知識題 1. 試比較順序表與鏈表的優(yōu)缺點(diǎn)。 3. 為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好？ 4. 寫出在循環(huán)雙鏈表中的 p所指結(jié)點(diǎn)之后插入一個(gè) s所指結(jié)點(diǎn)的操作。 6. 請利用鏈表來表示下面一元多項(xiàng)式 781194)( 3811 ????? xxxxxA?二、算法設(shè)計(jì)題 1. 有一個(gè)有 n個(gè)結(jié)點(diǎn)的單鏈表，設(shè)計(jì)一個(gè)函數(shù)將第 i1個(gè)結(jié)點(diǎn)與第 i個(gè)結(jié)點(diǎn)互換，但指針不變。 3. 已知一個(gè)單鏈表，編寫一個(gè)刪除其值為 x的結(jié)點(diǎn)的前趨結(jié)點(diǎn)的算法。 5. 已知一個(gè)遞增有序的單鏈表，編寫一個(gè)函數(shù)向該單鏈表中插入一個(gè)元素為 x的結(jié)點(diǎn)，使插入后該鏈表仍然遞增有序。 7. 有一個(gè)共 10個(gè)結(jié)點(diǎn)的單鏈表，試設(shè)計(jì)一個(gè)函數(shù)將此單鏈表分為兩個(gè)結(jié)點(diǎn)數(shù)相等的單鏈表。 9. 已知一個(gè)指針 p指向單循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，編寫一個(gè)對此單循環(huán)鏈表進(jìn)行遍歷的算法。 11. 在雙鏈表中，若僅知道指針 p指向某個(gè)結(jié)點(diǎn)，不知頭指針，能否根據(jù) p遍歷整個(gè)鏈表？若能，試設(shè)計(jì)算法實(shí)現(xiàn)。
法律信息相關(guān)推薦
鄂ICP備17016276號-1