【正文】 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 雙親表示法 基本思想： 用一維數(shù)組來存儲樹的各個結(jié)點（一般按 層序 存儲），數(shù)組中的一個元素對應(yīng)樹中的 一個結(jié)點，包括結(jié)點的數(shù)據(jù)信息以及該結(jié)點的雙親在數(shù)組中的下標(biāo)。 樹的邏輯結(jié)構(gòu) 層序遍歷序列： A B C D E F G H I A C B G F E D H I 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 樹的存儲結(jié)構(gòu) 實現(xiàn)樹的存儲結(jié)構(gòu)，關(guān)鍵是什么 ? 什么是存儲結(jié)構(gòu) ? 樹中結(jié)點之間的邏輯關(guān)系是什么 ? 思考問題的出發(fā)點：如何表示結(jié)點的雙親和孩子 如何表示樹中結(jié)點之間的邏輯關(guān)系。 樹的邏輯結(jié)構(gòu) 前序遍歷序列： A B D E H I F C G A C B G F E D H I 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 后序遍歷 樹的后序遍歷操作定義為： 若樹為空 ， 則空操作返回；否則 ⑴ 按照從左到右的順序后序遍歷根結(jié)點的每一棵子樹； ⑵ 訪問根結(jié)點 。 樹的邏輯結(jié)構(gòu) 樹結(jié)構(gòu) （ 非線性結(jié)構(gòu) ） → 線性結(jié)構(gòu) 。 如何理解 訪問 ? 抽象 操作， 可以是對結(jié)點進(jìn)行的各種處理，這里 簡化為輸出結(jié)點的數(shù)據(jù)。 樹的邏輯結(jié)構(gòu) 樹的基本術(shù)語 A 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 同構(gòu)： 對兩棵樹 ， 若通過對結(jié)點適當(dāng)?shù)刂孛?，就可以使這兩棵樹完全相等 （ 結(jié)點對應(yīng)相等 ， 結(jié)點對應(yīng)關(guān)系也相等 ） ， 則稱這兩棵樹同構(gòu) 。 樹的邏輯結(jié)構(gòu) 樹的基本術(shù)語 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 有序樹、無序樹： 如果一棵樹中結(jié)點的各子樹從左到右是有次序的，稱這棵樹為有序樹；反之，稱為無序樹。 樹的深度： 樹中所有結(jié)點的最大層數(shù)，也稱 高度 。 C G B D E F K L H M I J A 樹的邏輯結(jié)構(gòu) 樹的基本術(shù)語 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 祖先、子孫： 在樹中，如果有一條路徑從結(jié)點 x到結(jié)點 y， 那么 x就稱為 y的祖先，而 y稱為 x的子孫。 C G B D E F K L H M I J A 樹的基本術(shù)語 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 孩子、雙親： 樹中某結(jié)點子樹的根結(jié)點稱為這個結(jié)點的 孩子結(jié)點 ，這個結(jié)點稱為它孩子結(jié)點的 雙親結(jié)點 ； 兄弟： 具有同一個雙親的孩子結(jié)點互稱為兄弟。 樹的邏輯結(jié)構(gòu) C G B D E F K L H M I J A 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 樹的邏輯結(jié)構(gòu) 葉子結(jié)點： 度為 0的結(jié)點，也稱為終端結(jié)點。 樹的邏輯結(jié)構(gòu) 樹的定義是采用遞歸方法 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 (a) 一棵樹結(jié)構(gòu) (b)一個非樹結(jié)構(gòu) (c)一個非樹結(jié)構(gòu) 樹的邏輯結(jié)構(gòu) 樹的定義 A C B G F E D H I A C B G F D A C B G F D E 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 樹的應(yīng)用舉例 —— 文件結(jié)構(gòu) 樹的邏輯結(jié)構(gòu) My Computer C: D: E: etc WINDOWS Program Files Picture Music ?? ?? ?? ?? ?? ?? ?? ?? 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 樹的基本術(shù)語 結(jié)點的度： 結(jié)點所擁有的子樹的個數(shù)。長度、深度 ⑵ ADT定義 鏈接存儲 頭尾表示法 轉(zhuǎn)置算法 第四章 廣義線性表 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 ?樹的邏輯結(jié)構(gòu) ?樹的存儲結(jié)構(gòu) ?二叉樹的邏輯結(jié)構(gòu) ?二叉樹的存儲結(jié)構(gòu)及實現(xiàn) ?樹、森林與二叉樹的轉(zhuǎn)換 ?哈夫曼樹 第 5 章 樹和二叉樹 本章的主要內(nèi)容是 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 樹的定義 樹： n（ n≥ 0） 個 結(jié)點 的有限 集合 。廣義表定義 三角矩陣 } 廣義線性表 —— 廣義表 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 廣義線性表 多維數(shù)組 廣義表 邏輯結(jié)構(gòu) 存儲結(jié)構(gòu) 邏輯結(jié)構(gòu) 存儲結(jié)構(gòu) ⑴數(shù)組的定義 ⑵基本操作 ⑶ ADT定義 順序存儲 壓縮存儲 特殊矩陣 p = p。 while (p) { dep = Depth(p)。 max=0。 } 廣義線性表 —— 廣義表 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 廣義表的操作 —— 求廣義表的深度 template class T int Lists::Depth(GLNodeT *ls) { if (ls==NULL) return 1。 ls = ls1。 }。 GLNode *Tail( )。 int Depth(GLNodeT *ls)。 ~Lists( )。 廣義線性表 —— 廣義表 廣義表的存儲結(jié)構(gòu) —— 頭尾表示法 定義結(jié)點結(jié)構(gòu) tag=1 hp tp tag=0 data 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 廣義線性表 —— 廣義表 廣義表的存儲結(jié)構(gòu) —— 頭尾表示法 A ＝ ( ) B ＝ (e) C ＝ (a, (b， c， d)) NULL A 1 B 0 e ∧ 1 C 0 a ∧ 1 1 0 b 1 0 c ∧ 1 0 d 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 廣義線性表 —— 廣義表 廣義表的存儲結(jié)構(gòu) —— 頭尾表示法 1 B 0 e ∧ 1 C 0 a ∧ 1 1 0 b 1 0 c ∧ 1 0 d A ＝ ( ) B ＝ (e) C ＝ (a, (b， c， d)) D ＝ (A, B, C) 1 D ∧ 1 1 ∧ 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 廣義線性表 —— 廣義表 廣義表的存儲結(jié)構(gòu) —— 頭尾表示法 E ＝ (a, E) F ＝ (( )) 1 E 0 a 1 ∧ 1 F ∧ ∧ 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 template class T class Lists { public: Lists( ) 。 }。 struct { GLNode *hp, *tp。 template class T struct GLNode { Elemtag tag。 采用頭尾表示法存儲廣義表 如何采用鏈接存儲結(jié)構(gòu)存儲廣義表？ 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 廣義表的存儲結(jié)構(gòu) —— 頭尾表示法 廣義線性表 —— 廣義表 廣義表中的數(shù)據(jù)元素既可以是廣義表也可以是單元素 頭尾表示法中的結(jié)點結(jié)構(gòu)？ 表結(jié)點 —— 存儲廣義表；元素結(jié)點 —— 存儲單元素 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 tag=1 hp tp tag=0 data 表結(jié)點 元素結(jié)點 tag： 區(qū)分表結(jié)點和元素結(jié)點的標(biāo)志； hp： 指向表頭結(jié)點的指針； tp： 指向表尾結(jié)點的指針； data： 數(shù)據(jù)域 ， 存放單元素 。 廣義線性表 —— 廣義表 廣義表 ( )和廣義表 (( ))不同？ 廣義表的基本概念 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 A ＝ ( ) B ＝ (e) C ＝ (a, (b， c， d)) D ＝ (A, B, C) E ＝ (a, E) F ＝ (( )) 廣義線性表 —— 廣義表 廣義表的示例 長度？深度？表頭？表尾？ 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 A ＝ ( ) B ＝ (e) C ＝ (a, (b， c， d)) D ＝ (A, B, C) E ＝ (a, E) F ＝ (( )) 廣義線性表 —— 廣義表 廣義表的圖形表示 A B e C a b c d D 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 廣義線性表 —— 廣義表 廣義表可以采用順序存儲結(jié)構(gòu)嗎？ 由于廣義表中的數(shù)據(jù)元素的類型不統(tǒng)一，因此難以采用順序存儲結(jié)構(gòu)來存儲。 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 長度： 廣義表 LS中的直接元素的個數(shù)； 深度： 廣義表 LS中括號的最大嵌套層數(shù)。 廣義線性表 —— 廣義表 廣義表的邏輯結(jié)構(gòu)：直接元素之間是線性關(guān)系 。 矩陣的壓縮存儲 三元組順序表轉(zhuǎn)置算法 —— 算法 Ⅱ 如何確定當(dāng)前從 A中取出的三元組在 B中的位置？ 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 矩陣的壓縮存儲 三元組順序表轉(zhuǎn)置算法 —— 算法 Ⅱ row col item 0 1 2 3 4 5 6 MaxTerm1 6（矩陣的行數(shù)） 5（矩陣的列數(shù)） 7（非零元個數(shù)） 0 0 15 0 4 91 1 1 11 2 1 3 3 0 22 3 2 6 5 0 15 第 0列第 1個非零元素 第 0列有 2個非零元素 第 1列第 1個非零元素 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 引入兩個數(shù)組作為輔助數(shù)據(jù)結(jié)構(gòu)： num[nu]： 存儲矩陣 A中某列的非零元素的個數(shù)； cpot[nu]： 初值表示矩陣 A中某列的第一個非零元素在 B中的位置。 基本思想： 順序取，直接存。 col=最大列號 。即 在 A的三元組順序表中 依次 找第 0列、第 1列、 … 直到最后一列的三元組，并將找到的每個三元組的行、列交換后 順序 存儲到 B的三元組順序表中。 //行數(shù) ， 列數(shù) ， 非零元個數(shù) }。 template class T struct SparseMatrix { T data[MaxTerm]。 將稀疏矩陣中的每個非零元素表示為 ： (行號，列號，非零元素值 )—— 三元組 矩陣的壓縮存儲 稀疏矩陣的壓縮存儲 定義三元組 ： 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 三元組表 ： 將稀疏矩陣的非零元素對應(yīng)的三元組所構(gòu)成的集合， 按行優(yōu)先的順序排列成一個線性表。 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 template class T struct element { int row, col。 矩陣的壓縮存儲 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 矩陣中任一元素 aij在 數(shù)組 中的下標(biāo) k與 i、 j的對應(yīng)關(guān)系： i (i＋ 1)/2＋ j 當(dāng) i≥j n (n＋ 1)/2 當(dāng) i＜ j k= 下三角矩陣的壓縮存儲 0 1 2 3 4 5 k n(n+1)/2 第 1行 第 0行 a00 a10 a11 a20 a21 aij … an1n1 … 第 2行 c a22 矩陣的壓縮存儲 存儲 下三角 元素 對角線上方的常數(shù) —— 只存一個 數(shù)據(jù)結(jié)構(gòu)（ C++版） 清華大學(xué)出版社 矩陣中任一元素 aij在 數(shù)組 中的下標(biāo) k與 i、 j的對應(yīng)