動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)ppt課件(編輯修改稿)
2025-06-02 12:08 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 t LNode *next。 }LNode, * LinkList。 38 typedef struct Node { ElemType data。 struct Node *next。 } LNode,* LinkList。 等價(jià)于 struct Node { ElemType data。 struct Node *next。 }。 typedef struct Node LNode。 typedef struct Node* LinkList。 39 說(shuō)明： ? typedef 語(yǔ)句定義了一個(gè)結(jié)構(gòu)體類(lèi)型和鏈表類(lèi)型 (結(jié)構(gòu)體指針類(lèi)型 )。 ? Node 是一個(gè)結(jié)點(diǎn)的類(lèi)型名稱(chēng) 。它有兩個(gè)成員，一個(gè)名稱(chēng)為data ，類(lèi)型為數(shù)據(jù)元素的類(lèi)型，用來(lái)存放一個(gè)數(shù)據(jù)元素的值；另一個(gè)成員名稱(chēng)為 next，類(lèi)型為指向本結(jié)構(gòu)體類(lèi)型的指針類(lèi)型，用來(lái)存放邏輯上排在本結(jié)點(diǎn)后面的結(jié)點(diǎn)的首地址。 ? LNode類(lèi)型等價(jià)于 struct Node類(lèi)型，也等價(jià)于 Node類(lèi)型。 ? LinkList類(lèi)型等價(jià)于 LNode 的指針類(lèi)型。 ? ElemType 是數(shù)據(jù)元素的類(lèi)型的一般性描述 ，當(dāng)我們具體寫(xiě)程序時(shí)，應(yīng)該用確定類(lèi)型名稱(chēng)來(lái)替換，例如， int、 float 、 char等。 40 例：鏈表中的數(shù)據(jù)元素用來(lái)存放整數(shù)，定義鏈表的結(jié)點(diǎn)類(lèi)型的語(yǔ)句格式為： typedef struct Node { int data。 struct Node *next。 } LNode,*LinkList。 41 1. 定義一個(gè)結(jié)點(diǎn)類(lèi)型的變量的語(yǔ)句： struct Node q。 LNode q 。 2. 定義一個(gè)指向結(jié)點(diǎn)類(lèi)型的指針變量的語(yǔ)句： struct Node * p。 LNode* p 。 LinkList L。 3. 訪問(wèn)結(jié)點(diǎn)變量的各個(gè)成員： , pdata , pnext Ldata , Lnext 42 ?鏈表的建立 1. 構(gòu)造一個(gè) 空線性鏈表 首先，構(gòu)造一個(gè)空的線性鏈表。為了描述方便，通常將鏈表的第一個(gè)結(jié)點(diǎn)空置，不存放數(shù)據(jù)元素，只是作為鏈表的開(kāi)始標(biāo)志，稱(chēng)為 頭結(jié)點(diǎn) 。數(shù)據(jù)元素從鏈表的第二個(gè)結(jié)點(diǎn)開(kāi)始存放。 空的線性表 定義為沒(méi)有數(shù)據(jù)元素的表 。 一個(gè)空的線性鏈表就規(guī)定為，只有一個(gè)頭結(jié)點(diǎn)的鏈表。所以， 構(gòu)造一個(gè)空的線性鏈表就是建立只有一個(gè)頭結(jié)點(diǎn)的鏈表。 44 程序： /*構(gòu)造一個(gè)空的線性鏈表 */ LNode* InitList () { LinkList L。//頭結(jié)點(diǎn)指針 L = (LNode*) malloc(sizeof(LNode ))。 /*申請(qǐng)一結(jié)點(diǎn)空間 */ if ( !L) exit ( 0 )。/*申請(qǐng)不成功，異常結(jié)束程序運(yùn)行 */ Lnext = NULL。/*申請(qǐng)成功，頭結(jié)點(diǎn)的 next域置空 */ return(L)。 } 45 2．逆序輸入 n個(gè)數(shù)據(jù)元素，建立帶表頭結(jié)點(diǎn)的單向鏈表 ? 現(xiàn)在開(kāi)始建立一個(gè)非空的線性鏈表。這里所建的鏈表的第一個(gè)結(jié)點(diǎn)都是 頭結(jié)點(diǎn) 。數(shù)據(jù)元素從鏈表的第二個(gè)結(jié)點(diǎn)開(kāi)始存放。 ? 一個(gè)非空的線性鏈表 是除了頭結(jié)點(diǎn)以外至少有一個(gè)數(shù)據(jù)元素的鏈表。 線性鏈表由若干個(gè)數(shù)據(jù)元素結(jié)點(diǎn)組成。那么，構(gòu)造一個(gè)非空的線性鏈表的過(guò)程就是逐個(gè)建立數(shù)據(jù)元素結(jié)點(diǎn)，并將它們依次插入到鏈表中的過(guò)程。 46 頭插入 ，即每次將數(shù)據(jù)元素結(jié)點(diǎn)插入到表頭結(jié)點(diǎn)的之后，第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)之前。 插入過(guò)程如下圖所示： ∧ 初始狀態(tài)： 插入第一個(gè)結(jié)點(diǎn)之后： an ∧ 頭結(jié)點(diǎn) 47 ? 插入第二個(gè)結(jié)點(diǎn)之后： ? 插入第三個(gè)結(jié)點(diǎn)之后： ?插入最后一個(gè)結(jié)點(diǎn)之后： an1 an ∧ an1 an2 an ∧ an1 a1 an ∧ … … 48 LNode* CreateList(int n) { int i。 LNode *p。 LinkList L 。 L = (LNode*) malloc(sizeof(LNode))。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1