[計(jì)算機(jī)軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)課件單鏈表(已修改)
2024-10-28 23:17 本頁面
【正文】 1 單鏈表 數(shù)據(jù)結(jié)構(gòu)電子教案 2 ? 特點(diǎn) ? 每個(gè)元素 (表項(xiàng) )由結(jié)點(diǎn) (Node)構(gòu)成。 ? 線性結(jié)構(gòu) ? 結(jié)點(diǎn)之間可以連續(xù)，可以不連續(xù)存儲 ? 結(jié)點(diǎn)的邏輯順序與物理順序可以不一致 ? 表可擴(kuò)充 單鏈表 (Singly Linked Chain) data link a1 a2 a3 a4 a5 Λ first 3 單鏈表的存儲映像 free (a) 可利用存儲空間 a0 a2 a1 a3 ? free first (b) 經(jīng)過一段運(yùn)行后的單鏈表結(jié)構(gòu) 4 單鏈表的結(jié)構(gòu)定義 ? 在 C中定義單鏈表的結(jié)構(gòu)十分簡單 ： typedef int T。 //結(jié)點(diǎn)數(shù)據(jù)的類型 typedef struct node { //結(jié)點(diǎn)結(jié)構(gòu)定義 T data。 //結(jié)點(diǎn)數(shù)據(jù)域 struct node *link。 //結(jié)點(diǎn)鏈接指針域 } ChainNode。 //結(jié)點(diǎn)命名 ? 這是一個(gè)遞歸的定義。 ? 在結(jié)構(gòu)定義時(shí)不考慮操作，以后在定義和實(shí)現(xiàn)鏈表操作時(shí)直接使用結(jié)構(gòu)的成分。 5 單鏈表的類定義 ? 使用面向?qū)ο蠓椒?，要把?shù)據(jù)與操作一起定義和封裝，用多個(gè)類表達(dá)一個(gè)單鏈表。 ? 鏈表結(jié)點(diǎn) (ChainNode)類 ? 鏈表 (Chain)類 ? 定義方式 ? 復(fù)合方式 ? 嵌套方式 ? 繼承方式 ? 結(jié)構(gòu)方式 6 class Chain。 //復(fù)合方式 class ChainNode { //鏈表結(jié)點(diǎn)類 friend class Chain。 //鏈表類為其友元類 private: int data。 //結(jié)點(diǎn)數(shù)據(jù) , 整型 ChainNode * link。 //結(jié)點(diǎn)指針 }。 class Chain { //鏈表類 private: ChainNode *first 。 //表頭指針 }。 7 class Chain { //嵌套方式 private: class ChainNode { //嵌套鏈表結(jié)點(diǎn)類 public: int data。 ChainNode *link。 }。 ChainNode *first。 //表頭指針 public: //鏈表操作 ……… }。 8 //鏈表類和鏈表結(jié)點(diǎn)類定義 (繼承方式 ) class ChainNode { //鏈表結(jié)點(diǎn)類 protected: int data。 ChainNode * link。 }。 class Chain : public class ChainNode { //鏈表類 , 繼承鏈表結(jié)點(diǎn)類的數(shù)據(jù)和操作 private: ChainNode *first。 //表頭指針 }。 9 ? 在 復(fù)合方式 中，鏈表
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1