[理學(xué)]第四章線性表(編輯修改稿)
2024-11-15 01:05 本頁面
【文章內(nèi)容簡介】 DT Node 3. 單鏈表基本操作算法 (1) Node類聲明： template class T class Node { private: Node T * next。 public: T data。 // 構(gòu)造函數(shù) Node ( const Tamp。 item , Node T * ptrnext = NULL)。 // 在當(dāng)前結(jié)點(diǎn)之后插入指針 p 所指結(jié)點(diǎn) void InsertAfter(Node T *p)。 // 刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn) Node T * DeleteAfter(void)。 // 返回指向當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)的指針 Node T * NextNode(void) const。 }。 (2) Node類的實(shí)現(xiàn) ① 構(gòu)造函數(shù) template class T Node T :: Node(const Tamp。 item , Node T * ptrnext）： data(item),next(ptrnext) { } ② 返回當(dāng)前結(jié)點(diǎn)的 next 域的值 C++： template class T Node T * Node T :: nextNode(void) const { return next 。 } ADL: 算法 NextNode() NextNode1[取當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn) ] p ?next(this). ▌ ③ 在當(dāng)前結(jié)點(diǎn)之后插入結(jié)點(diǎn) p //ADL描述 算法 InsertAfter（ this ， p ） IA1 [將當(dāng)前結(jié)點(diǎn)的 next域值賦給 P的 next域 ] next（ p） ? next（ this） . IA2 [將 P賦給當(dāng)前結(jié)點(diǎn)的 next域 ] next（ this） ? p . ▌ … FAT HAT … this GAT p ④ 刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn) //ADL描述 算法 DeleteAfter（ this . tempptr） DA1 [this的 next域值 = NULL？ ] IF next（ this） = NULL THEN tempptr ? NULL ELSE（ tempptr ? next（ this） . next（ this） ? next（ tempptr） ） . ▌ … FAT HAT … this GAT tempptr (3) 構(gòu)造鏈表 //ADL描述 ① 創(chuàng)建一個(gè) data域值為 item,next 域值為 nextptr的結(jié)點(diǎn)。 算法 GetNode（ item ， nextptr . newNode） GN1 [為新結(jié)點(diǎn)申請空間 ] newNode ? AVAIL . GN2 [為結(jié)點(diǎn)諸域賦值 ] data（ newNode） ? item. next（ newNode） ? nextptr. ▌ item NewNode nextptr ② 在頭指針為 head 的鏈表中，插入一個(gè) data 域?yàn)? item 的新結(jié)點(diǎn)作為該鏈表的表頭結(jié)點(diǎn)。 算法 InsertFront（ head ， item） IF1 [調(diào)用函數(shù) GetNode] GetNode（ item， head. newNode） . IF2 [head指向新結(jié)點(diǎn) ] head ? newNode. ▌ 表頭插入結(jié)點(diǎn)演示 HAT head GAT ∧ item newNode head head (4)遍歷鏈表 遍歷鏈表演示 算法 PrintList（ head） //輸出頭指針為 head的鏈表 ,每輸出 5個(gè)元素?fù)Q行 PL 1 [取表頭 ， 計(jì)數(shù)器初始化 ] currptr ? head . count ? 0 . a c b head currptr ∧ PL 2 [遍歷并輸出鏈表結(jié)點(diǎn)的 data值 ] WHILE（ currptr ≠ NULL） DO （ PRINT（ data（ currptr）） . count ? count + 1. IF（ MOD（ count， 5） = 0 ） THEN PRINT . currptr ? next（ currptr） . ） ▌ a c b head currptr currptr currptr currptr ∧ (5)表尾插入結(jié)點(diǎn) 表尾插入 結(jié)點(diǎn)演示 算法 InsertRear（ head ， item ） // 在頭指針為 head的鏈表尾部插入 data域值 // 為 item的結(jié)點(diǎn)； IR1 [取頭指針 ] currptr ? head . a c b head currptr ∧ IR2 [currptr = NULL？ ] IF currptr = NULL THEN InsertFront（ head ， item） head=NULL currptr=NULL head item head NULL IR2 [currptr = NULL？ ] IF currptr = NULL THEN InsertFront（ head ， item） ELSE （ WHILE（ nex
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1