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