[理學(xué)]數(shù)據(jù)結(jié)構(gòu)第2章線性表b-閱讀頁
2025-01-29 17:12本頁面
【正文】 單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置 由 指示。由數(shù)據(jù)域和指針域兩部分組成； 2）鏈表： n 個(gè)結(jié)點(diǎn)由 指針鏈 組成一個(gè)鏈表。 3）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表 ： ? 結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱為 單鏈表 或 線性鏈表 ； ? 有兩個(gè)指針域的鏈表，稱為 雙鏈表 （但未必是雙向鏈表） ； ? 有多個(gè)指針域的鏈表，稱為 多鏈表 ； ? 首尾相接的鏈表稱為 循環(huán)鏈表 。 首元結(jié)點(diǎn) 是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素 a1的結(jié)點(diǎn)。 答： 無頭結(jié)點(diǎn)時(shí)，當(dāng)頭 指針 的值為 空 時(shí)表示空表； ^ 頭指針 無頭結(jié)點(diǎn) ^ 頭指針 頭結(jié)點(diǎn) 有頭結(jié)點(diǎn) 有頭結(jié)點(diǎn)時(shí)，當(dāng)頭 結(jié)點(diǎn) 的 指針域?yàn)榭?時(shí)表示空表。 7 ZHAO H 31 稱：頭指針 H的值是 31 （ 3）舉例 例 1： 上例鏈表的邏輯結(jié)構(gòu)示意圖有以下 兩種形式 ： ① ZHAO QIAN LI SUN ZHOU WU ZHENG /\ WANG H ② ZHAO QIAN LI SUN ZHOU WU ZHENG /\ WANG H 區(qū)別： ① 無頭結(jié)點(diǎn) ② 有頭結(jié)點(diǎn) 頭結(jié)點(diǎn)不計(jì)入 鏈表長度！ 線性表具有兩種存儲(chǔ)方式 ， 即順序方式和鏈接方式 。 其中指針 X， Y， Z的 值 分別為多少 ？ 該線性表的 首結(jié)點(diǎn)起始地址 為多少 ？ 末結(jié)點(diǎn)的起始地址 為多少 ？ Z 47 Y 31 V 23 X 17 U 05 100 119 104 108 116 112 116 NULL(0) 100 108 112 答： X= Y= Z= , 首址 = 末址 = 。 答： 以 26個(gè)字母的鏈表為例，每個(gè)結(jié)點(diǎn)都有兩個(gè)分量： 字符型 指針型 設(shè)每個(gè)結(jié)點(diǎn)用變量 node表示，其指針用 p表示，兩個(gè)分量分別用 data和*next表示，這兩個(gè)分量如何賦值？ p *next data node 方式 1： 直接表示為 ＝ 39。； =q 方式 2： p指向結(jié)點(diǎn)首地址，然后 pdata=39。 pnext=q。a39。 練習(xí)： pdata ai的值 pnext ai+1的地址 sizeof(x)—— 計(jì)算 x的長度 malloc(m) — 開 m字節(jié) 空間 free(p) —— 刪除一個(gè)變量 問 1： 自定義結(jié)構(gòu)類型變量 node的長度 m是多少？ 問 2： 結(jié)構(gòu)變量 node的首地址 (指針 p）是多少？ 問 3： 怎樣刪除結(jié)構(gòu)變量 node？ *next data node， 長度為 m字節(jié) p m＝ sizeof(node) //單位是字節(jié) p＝ (node*)malloc(m) free(p) //只能借助 node的指針刪除！ Pdata=‘a(chǎn)’。 //數(shù)據(jù)域 struct Lnode *next。 // *LinkList為 Lnode類型的指針 至此應(yīng)可看懂教材 P22關(guān)于順序表 動(dòng)態(tài)分配 的存儲(chǔ)結(jié)構(gòu)。 如何具體編程來建立和訪問鏈表？ —— 鏈表的實(shí)現(xiàn) Typedef struct Lnode { ElemType data。 }Lnode, *LinkList。前者 Lnode是結(jié)構(gòu)名，后者 Lnode是對(duì)整個(gè)struct類型的一種 “ 縮寫 ” ，是一種 “ 新定義名 ” ，它只是對(duì)現(xiàn)有類型名的補(bǔ)充，而不是取代。 Typedef struct Lnode { ElemType data。 }Lnode, *LinkList。例如，若結(jié)構(gòu)名為 student，其新定義名縮寫也最好寫成 student，因?yàn)槊枋龅膶?duì)象相同，方便閱讀和理解。此處說明了指針分量的數(shù)據(jù)類型是 struct Lnode。 int age。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1