數(shù)據(jù)結(jié)構(gòu)之線性表課件-wenkub.com
2024-08-27 09:01 本頁面
【正文】 11. 在雙鏈表中，若僅知道指針 p指向某個(gè)結(jié)點(diǎn)，不知頭指針，能否根據(jù) p遍歷整個(gè)鏈表？若能，試設(shè)計(jì)算法實(shí)現(xiàn)。 7. 有一個(gè)共 10個(gè)結(jié)點(diǎn)的單鏈表，試設(shè)計(jì)一個(gè)函數(shù)將此單鏈表分為兩個(gè)結(jié)點(diǎn)數(shù)相等的單鏈表。 3. 已知一個(gè)單鏈表，編寫一個(gè)刪除其值為 x的結(jié)點(diǎn)的前趨結(jié)點(diǎn)的算法。 3. 為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好？ 4. 寫出在循環(huán)雙鏈表中的 p所指結(jié)點(diǎn)之后插入一個(gè) s所指結(jié)點(diǎn)的操作。 sprior=p。 sprior=p。 ji) { j++。 } 例3.3算法續(xù) else { p=head。 /*建立一個(gè)待插入的結(jié)點(diǎn) ， 由 s指向 */ sdata=x。 ?解：在前面雙鏈表一節(jié)中，已經(jīng)給出了在一個(gè)結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)的方法，在一個(gè)結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)的思想與前面是一樣的。 while(qnext!=head2) q=qnext。 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。 } headnext=NULL。 while(q!=NULL) /*沒有后繼時(shí)停止 */ { r=qnext。 最后將第一個(gè)結(jié)點(diǎn)的 next域置為 NULL，并將頭指針指向最后一個(gè)結(jié)點(diǎn)。 基本思想 ：設(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)。 Int exp。 ?1. 如果用 數(shù)組來表示一元多項(xiàng)式 ，以各項(xiàng)的指數(shù)作為下標(biāo)，將各個(gè)系數(shù)存入一維數(shù)組中。 p q ① ③ ④ ② 2. 雙鏈表的刪除 ?設(shè) p指向待刪除的結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)步驟為： (pprior) next=pnext。 1. 雙鏈表的插入 ?設(shè)要在 p所指結(jié)點(diǎn)的 前面 插入一個(gè)新結(jié)點(diǎn)*q，則需要修改 4個(gè)指針 ： qprior=pprior。 ?結(jié)點(diǎn)定義為： Typedef struct dbnode { elementtype data。 ?雙鏈表的結(jié)點(diǎn)形式為： 其中鏈域 prior和 next分別指向本結(jié)點(diǎn)的直接前趨和直接后繼結(jié)點(diǎn)。 printf(“ ”,w)。 for ( i=josephus_seqlength。 int pwd。設(shè)編號(hào)為1,2,……,n(n0) 個(gè)人，按順時(shí)針圍坐一圈，每人有一正整數(shù)密碼 m。 ?表空時(shí)空表頭結(jié)點(diǎn)的指針指向其本身，如下面的圖所示為空循環(huán)鏈表。 ?順序表：在已知元素個(gè)數(shù)的情況下，空間利用率 高； 在未知元素個(gè)數(shù)的情況下，可能浪費(fèi)空 間，利用率低； 速度慢。 }slinklist。 } return(head)。 p=pnext。 p=headnext。 x head ∧ p q 刪除算法 Linklist * Delete (head, x) linklist *head。 } return(head) } 3. 刪除 ?假設(shè)單鏈表 帶有頭結(jié)點(diǎn) ，頭指針為 head，刪除單鏈表上一個(gè) 其值為 x的結(jié)點(diǎn) 。 If (pre==null) /*插入的結(jié)點(diǎn)位于鏈 { snext=head。 while [(p!=null) $$ (jk)] /*找出第 k個(gè)結(jié)點(diǎn)的 {pre=p； /*指針 p和它的前趨 p=pnext。 結(jié)點(diǎn)之 前 插入 X int k。 } s=(linklist *)malloc(sizeof(linklist)) if (s= =null) { printf (“沒有足夠的空間 ” ) Return(null) } snext=pnext。 head a1 a 2 a i a n ∧ a i +1 S x P insert(head) /*在第 i個(gè)結(jié)點(diǎn) 后 插入結(jié)點(diǎn) S { linklist *p=head。 可通過 C的庫函數(shù) malloc(size)來產(chǎn)生 。 2. 插入 ?所謂插入是指在單鏈表中第 i個(gè)結(jié)點(diǎn) (i≥0)之后插入一個(gè)元素為 x的結(jié)點(diǎn)。 } return(count)。 ?假設(shè) head是單鏈表的頭指針，計(jì)算一個(gè)已建立好的單鏈表的結(jié)點(diǎn)個(gè)數(shù)的算法如下： 計(jì)算結(jié)點(diǎn)個(gè)數(shù)算法 int length(head) /*求表 head的長(zhǎng)度 */ { int count=0。 該指針（若不是 NULL）指向的某個(gè) node型結(jié)點(diǎn)用 *p來標(biāo)識(shí)。 h e a d a 1 a 2 a i a n ∧ 單鏈表的類型定義 ?單鏈表的的結(jié)點(diǎn)類型定義如下： typedef struct Lnode { elementtype data。 ? 其中， data部分稱為數(shù)據(jù)域，用于存儲(chǔ)線性表的一個(gè)元素， next部分稱為指針域或鏈域，用于存放一個(gè)指針，即存放該結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的地址。 break。 While(I) { If ([I]!=x) I++。 ?刪除一個(gè)值為
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1