數(shù)據(jù)結(jié)構(gòu) 總復(fù)習(xí) 第一章 緒論 重點(diǎn)內(nèi)容 邏輯結(jié)構(gòu)和物理結(jié)構(gòu) 順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ) 算法的五個(gè)特性 算法的時(shí)間復(fù)雜度 邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。 物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，包括數(shù)據(jù)元素的表示和關(guān)系的表示。 3 基本概念和術(shù)語 順序存儲(chǔ)結(jié)構(gòu) ： 用數(shù)據(jù)元素在存儲(chǔ)器中的 相對(duì)位置 來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu) (關(guān)系 )。 數(shù)據(jù)元素存放的地址是連續(xù)的 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：借助指示元素存儲(chǔ)地址得指針表示數(shù)據(jù)之間的邏輯關(guān)系。 數(shù)據(jù)元素存放的地址是否連續(xù)沒有要求 4 基本概念和術(shù)語 5 順序存儲(chǔ) 以存儲(chǔ)位置的相鄰表示后繼關(guān)系 鏈?zhǔn)酱鎯?chǔ) 以附加信息 (指針 )表示后記關(guān)系，需要用一個(gè)和 x y 基本概念和術(shù)語 y x 算法是為了解決某類問題而給出的一個(gè)有限長(zhǎng)的 指令序列 。 算法有以下 5個(gè)特性： 有窮性：有窮步驟，每步都有有窮的時(shí)間 確定性：每條指令有確定的含義 可行性：是能行的，基本運(yùn)算的有限次運(yùn)算完成 輸入： 0個(gè)或多個(gè)輸入，取自某個(gè)特定對(duì)象集合 輸出：一個(gè)或多個(gè)輸出，同輸入有某些特定關(guān)系 6 算法與算法分析 一個(gè)“好”的算法需滿足： 7 算法與算法分析 正確 性 程序 中不含語法錯(cuò)誤； 程序?qū)τ趲捉M給定的輸入可得到滿足要求的結(jié)果 程序?qū)τ诰奶暨x的、典型的輸入也可得到滿足要求的結(jié)果 程序?qū)τ谝磺泻戏ǖ妮斎刖梢缘贸鰸M足要求的結(jié)果 8 算法與算法分析 可讀 性 算法主要是為 了人的閱讀與交流 ， 其次才是為計(jì)算機(jī)執(zhí) 行 。 因此算法應(yīng)該易于人的 理解 ； 另 一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試和修改。 9 算法與算法分析 健壯性 當(dāng) 輸入 的數(shù)據(jù)非法 時(shí)，算法應(yīng)當(dāng)給予 恰當(dāng)?shù)姆磻?yīng)或進(jìn)行相應(yīng)的處理 ，而不是產(chǎn)生系統(tǒng)錯(cuò)誤或莫名其妙的結(jié)果 。 處理出錯(cuò) 的方法不應(yīng)是中斷程序的執(zhí)行， 而應(yīng)該返回錯(cuò)誤提示 ，以便在更高抽象層次上進(jìn)行處理 。 10算法與算法分析 假設(shè)，隨著問題規(guī)模 法執(zhí)行時(shí)間的增長(zhǎng)率和 f(n)的增長(zhǎng)率相同，則可記作：T(n)=O(f(n) 稱 T(n)為算 法的（漸進(jìn)）時(shí)間復(fù)雜度 11算法與算法分析 原操作 ： 固有數(shù)據(jù)類型的操作。 （如： +， -， ，/， ， 因此， 鏈表不是隨機(jī)存取結(jié)構(gòu) 設(shè)單鏈表的長(zhǎng)度為 n，要查找表中第 當(dāng) 1 i 單鏈表的插入 實(shí)現(xiàn)步驟 ： 首先，找到 結(jié)點(diǎn) p 然后，生成一個(gè)數(shù)據(jù)域?yàn)?s， 為 b p a b p a e s s-e; s-p- p-s; 單鏈表的刪除 實(shí)現(xiàn)步驟 ： 首先找到 p； 然后令 p把 最后釋放結(jié)點(diǎn) ai p q=p-p-q- e=q- q); 靜態(tài)鏈表 0 1 1 2 3 4 5 6 7 8 9 10 0 1 1 2 3 4 5 6 7 8 9 10 0 1 1 2 3 4 5 6 7 8 9 10 修改前 在第 5個(gè)位置插入 除 環(huán)鏈表 循環(huán)鏈表 (是一種頭尾相接的鏈表。其特點(diǎn)是最后一個(gè)結(jié)點(diǎn)的指針域指向鏈表的頭結(jié)點(diǎn)， 整個(gè)鏈表的指針域鏈接成一個(gè)環(huán) 。 從循環(huán)鏈表的 任意一個(gè)結(jié)點(diǎn)出發(fā) 都可以找到鏈表中的其它結(jié)點(diǎn)，使得表處理更加方便靈活。 空表 非空表 an 向鏈表的插入 S e p a b S e p a b 雙向鏈表的插入 算法主要語句 S=(); S-e; S-p- p-; S-p; p-; 設(shè)要?jiǎng)h除 的結(jié)點(diǎn)為 p ，刪除時(shí)直接先斷鏈 ，再釋放結(jié)點(diǎn)。部分語句組如下： p-p-p-p-p); 與單鏈 表的插入和刪除操作不同的是，在雙向鏈表中 插入 和 刪除 必須同時(shí) 修改兩個(gè)方向上的指針域的指向 。 雙向鏈表的刪除 a1 a2 a3 p 優(yōu)點(diǎn) ：易于查詢，索引快 缺點(diǎn) ：擴(kuò)展性弱，不易刪除、添加。 優(yōu)點(diǎn) ：擴(kuò)展性強(qiáng)，易于刪除、添加 缺點(diǎn) ：不易于查詢，索引慢 二者優(yōu)缺點(diǎn)正好是互補(bǔ)關(guān)系，根據(jù)實(shí)際情況選擇使用 順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的對(duì)比 第三章 棧和隊(duì)列 重點(diǎn)內(nèi)容 棧和隊(duì)列邏輯結(jié)構(gòu)的特點(diǎn) 順序棧的棧滿、棧空判斷 循環(huán)隊(duì)列的滿與空的判斷 壓棧、出棧算法 進(jìn)隊(duì)列、出隊(duì)列算法 棧 (限制在表尾進(jìn)行插入和刪除操作的線性表。又稱為后進(jìn)先出 n 棧頂 (允許進(jìn)行插入、刪除操作的一端 棧底 (是固定端，又稱為表頭。 空棧 ： 滿棧 : a1 a2 棧頂 棧底 進(jìn)棧(出棧 ( 采用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素： 用 底固定不變的；棧頂則隨著進(jìn)棧和退棧操作而變化。 用 為棧頂指針 )指示當(dāng)前棧頂位置。 用 每次 結(jié)點(diǎn)進(jìn)棧 ：首先將數(shù)據(jù)元素保存到棧頂 (，然后執(zhí)行 ，使 結(jié)點(diǎn)出棧 ：首先執(zhí)行 ，使 后將棧頂元素取出 。 空棧 素 a 元素 b， a b c 元素 a b a b d e f 元素 d， e， 3 元素進(jìn)棧 , e) /* 使數(shù)據(jù)元素 */ ( = /棧滿 ) (* ! *=e ; /* 棧頂指針加 1 */ K; /* 壓棧成功 */ 4 彈棧 (元素 出棧 ) &S, &e ) /*彈出棧頂元素 */ /* ?？眨祷劐e(cuò)誤標(biāo)志 */ e=*K ; 隊(duì)列 隊(duì)列 (也是運(yùn)算受限的線性表。是 一種先進(jìn)先出 (n 簡(jiǎn)稱 線性表。 只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除 隊(duì)頭 (： 允許進(jìn)行刪除的一端稱為隊(duì)頭。 隊(duì)尾 (：允許進(jìn)行插入的一端稱為隊(duì)尾。 , a n 出隊(duì) 入隊(duì) 隊(duì)尾 隊(duì)頭 鏈 隊(duì)列 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列 它是限制僅在表頭進(jìn)行刪除操作和表尾進(jìn)行插入操作的單鏈表。 需要兩類不同的結(jié)點(diǎn)： 數(shù)據(jù)元素 結(jié)點(diǎn)，隊(duì)列的 隊(duì)首指針和隊(duì)尾指針 的結(jié)點(diǎn) a) 空隊(duì)列 (b) x c) y x (d) y x 隊(duì)列 設(shè)立一個(gè)隊(duì)首指針 一個(gè)隊(duì)尾指針 分別指向隊(duì)首和隊(duì)尾元素 。 初始化 ： 。 入隊(duì) ： 將新元素插入 后 。 出隊(duì) ： 刪去 后加 1并返回被刪元素。 隊(duì)列為空 ： 隊(duì)滿 ： 序 隊(duì)列 (a) 空隊(duì)列 b) 入隊(duì) 3個(gè)元素 a3 a2 c) 出隊(duì) 3個(gè)元素 d) 入隊(duì) 2個(gè)元素 a5 序隊(duì)列 將新元素插入 后 刪去 后加 1并返回被刪元素 隊(duì)列已滿，但仍有存儲(chǔ)空間 充分利用向量空間 ，克服上述“假溢出”現(xiàn)象 將為隊(duì)列分配的向量空間看成為一個(gè)首尾相接的圓環(huán)，并稱這種隊(duì)列為 循環(huán)隊(duì)列 循環(huán)隊(duì)列 1 2 3 4 5 0 循環(huán) 隊(duì)列 2 3 4 5 0 (a) 空隊(duì)列 b) d, e, b, d e b g c) d, b g d) i, j, b g i j k e) b, i j k f) r, p, s, i j k r p 環(huán)隊(duì)列 Q , e) /* 將數(shù)據(jù)元素 的隊(duì)尾 */ ()% /* 隊(duì)滿，返回錯(cuò)誤標(biāo)志 */ . e ; /* 元素 */ () % /* 隊(duì)尾指針向前移動(dòng) */ K; /* 入隊(duì)成功 */ 循環(huán)隊(duì)列 循環(huán)隊(duì)列 Q, &e) /* 將循環(huán)隊(duì)列 */ ( /* 隊(duì)空，返回錯(cuò)誤標(biāo)志 */ e = ; /* 取隊(duì)首元素 */ ()% /* 隊(duì)首指針向前移動(dòng) */ K ; 第四章 串 重點(diǎn)內(nèi)容 串的基本概念 串 (字符串 )：是零個(gè)或多個(gè)字符組成的有限序列 。記作 ： S= 其 中 i n)是單個(gè)， 可以是字母、數(shù)字或其它字符。 串值 ：雙引號(hào)括起來的字符序列是串值。 串長(zhǎng) ：串中所包含的字符個(gè)數(shù)稱為該串的長(zhǎng)度。 空串 (空的字符串 )： 長(zhǎng)度為零 的串稱為空串，它不包含任何字符。 空 格串 (空白串 )：構(gòu)成串的所有 字符都是空格 的串稱為空白串。 注意 ：空串和空白串的不同，例如 和分別表示長(zhǎng)度為 1的空白串和長(zhǎng)度為 0的空串。 第五章 數(shù)組和廣義表 重點(diǎn)內(nèi)容 稀疏矩陣的壓縮存儲(chǔ) 廣義表的基本概念、求表頭、表尾操作 兩種順序存儲(chǔ)方式 行優(yōu)先順序 (： 將數(shù)組元素按行排列，第i+1個(gè)行向量緊接在第 二維數(shù)組，按行優(yōu)先順序存儲(chǔ)的線性序列為： ,a 1n, a 2n , a m1, 列優(yōu)先順序 (： 將數(shù)組元素按列向量排列，第 j+1個(gè)列向量緊接在第 二維數(shù)組，按列優(yōu)先順序存儲(chǔ)的線性序列為： ,a a , a n1, 組的順序表示和實(shí)現(xiàn) = (a) 二維數(shù)組的表示形式 (b) 行優(yōu)先順序存儲(chǔ) (c) 列 優(yōu)先順序存儲(chǔ) 1 行 2 行 第 m 行 1 列 2 列 n 列 給每一對(duì)對(duì)稱 元素 ij)分配 1個(gè)存儲(chǔ)空間 ，則n(n+1)/2個(gè)存儲(chǔ)空間 假設(shè)按 行優(yōu)先順序 存儲(chǔ)下三角形中的元素。 設(shè)用一維數(shù)組 (向量 )n(n+1)/2 存儲(chǔ) 為便于訪問，找出矩陣 i,j） 和向量 sak的 下標(biāo)值 1 2 3 4 n(2 n(n+1)/2 對(duì)稱矩陣的 壓縮存儲(chǔ)示例 廣義表 (稱為列表 )：是由 n(n 0)個(gè)元素組成的有窮序列： ， 中第一個(gè)元素 )稱為 表頭 ； 其余元素組成的子表稱為 表尾 ； ( ， 廣義表中所包含的元素 (包括原子和子表 )的個(gè)數(shù)稱為 表的長(zhǎng)度 。 廣義表中括號(hào)的最大層數(shù)稱為表深 (度 )。 義表的定義 第六章 樹和二叉樹 重點(diǎn)內(nèi)容 樹和二叉樹的定義及相關(guān)概念 二叉樹的 5個(gè)性質(zhì) 二叉樹的各種存儲(chǔ)結(jié)構(gòu) 樹的各種存儲(chǔ)結(jié)構(gòu) 二叉樹的各種遍歷方法、中序遍歷算法 線索二叉樹的畫法 樹的兩種遍歷方法 哈夫曼樹的構(gòu)造、哈夫曼編碼方法 樹 的 基本術(shù)語 結(jié)點(diǎn) (數(shù)據(jù)元素 若干指向其子樹的分支 結(jié)點(diǎn)的度 (：結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)稱為結(jié)點(diǎn)的度 。 樹 的度： 樹中結(jié)點(diǎn)度的 最大值 。 A A B D C E G F H I M J N K L 只有根結(jié)點(diǎn) 樹的基本術(shù)語 葉子結(jié)點(diǎn) ： 即度為 0的結(jié)點(diǎn) 分支結(jié)點(diǎn) ： 除葉子結(jié)點(diǎn)之外的其它結(jié)點(diǎn) 孩子 ( 若結(jié)點(diǎn) 子樹的根結(jié)點(diǎn)是 雙親 ( 若 該 A B D C E G F H I M J N K L 樹的基本術(shù)語 兄弟結(jié)點(diǎn) ： 同一個(gè)雙親的孩子結(jié)點(diǎn) 祖先結(jié)點(diǎn) ： 從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng) 路徑 上的所有結(jié)點(diǎn)。 子孫結(jié)點(diǎn) ： 以某個(gè)結(jié)點(diǎn)為根的子樹 中的任何一個(gè)結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn) 結(jié)點(diǎn)的 層次 ：從根開始定義，根為第 1層，根的孩子為第 2層 堂兄弟 ： 雙親結(jié)點(diǎn)在同一層上 A B D C E G F H I J 樹的基本術(shù)語 有序樹 ： 樹中各個(gè)節(jié)點(diǎn)的子樹 2， 之間是 有次序的 ，即為有序樹。即各個(gè)子樹之間的左右次序不能互換 無序樹 ： 樹中各個(gè)節(jié)點(diǎn)的子樹 2， 之間 沒有次序關(guān)系 的，即為無序樹。 60A B C D E A C B D E 樹的基本術(shù)語 樹的深度 ： 樹中節(jié)點(diǎn)的 最大層次， 也稱為樹的高度或深度。 61A B C D D E F H I J K L M 第 1層 第 2層 第 3層 第 4層 62二叉樹的定義 二叉樹或者為空樹 或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為 左子樹和 右子樹 的、 互不相交 的二叉樹組成。 叉樹 E G B E F A A A A A (a) (b) (c) (d) (e) 叉樹 二叉樹有 5種基本形態(tài)： 二叉樹的特點(diǎn)： 1）每個(gè)結(jié)點(diǎn)的度 1，則其雙親結(jié)點(diǎn) i) 的編號(hào)是 i/2 。 如果 2in，則編號(hào)為 i 的結(jié)點(diǎn)無左孩子（編號(hào)為 i 的結(jié)點(diǎn)為葉子結(jié)點(diǎn)）；否則其左孩子結(jié)點(diǎn) i)的編號(hào)是 2i 。 如果 2i+1n，則編號(hào)為 i 的結(jié)點(diǎn)無右孩子；否則其右孩子結(jié)點(diǎn) i) 的編號(hào)是結(jié)點(diǎn) 2i+1。 叉樹 i i+1 2i 2i+1 2i+2 2i+3 i/2 (a) i和 i+1結(jié)點(diǎn)在同一層 i+1 2i+2 2i+3 i 2i 2i+1 (b) i和 i+1結(jié)點(diǎn)不在同一層 順序存儲(chǔ)結(jié)構(gòu) 二叉樹存儲(chǔ)結(jié)構(gòu)的類型定義： # 100 用一組地址連續(xù)的存儲(chǔ)單元依次 “ 自上而下 、 自左至右 ” 存儲(chǔ)完全二叉樹 的數(shù)據(jù)元素 。 對(duì)于完全二叉樹上 編號(hào)為 對(duì)于一般的二叉樹， 將其每個(gè)結(jié)點(diǎn)與完全二叉樹上的結(jié)點(diǎn)相對(duì)照 ， 存儲(chǔ)在一維數(shù)組中 叉樹 a b c d h i e j k l f g (a) 完全二叉樹 (b) 非完全二叉樹 a b c d e f g h 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 a b c d e f g h i j k l (c) 完全二叉樹的順序存儲(chǔ)形式 0 1 2 3 4 5 6 7 8 9 10 a b c d e 0 h 0 0 f g (d) 非完全二叉樹的順序存儲(chǔ)形式 叉樹 最壞的情況下，一個(gè)深度為 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 二叉鏈表 。 結(jié)點(diǎn)有三個(gè)域： 一個(gè)數(shù)據(jù)域 ，兩個(gè)分別指向左右子結(jié)點(diǎn)的 指針域 * * 叉樹 a) 二叉鏈表結(jié)點(diǎn) 三 叉鏈表 除二叉鏈表的三個(gè)域外，再增加一個(gè)指針域， 用來指向 結(jié)點(diǎn)的父結(jié)點(diǎn) * * * 叉鏈表結(jié)點(diǎn) 叉樹 (2) 二叉樹的鏈?zhǔn)酱鎯?chǔ)形式 (a) 二叉樹 a f e d c b g (c) 三 叉鏈表 a b c d e f g T (b) 二 叉鏈表 a b c d e g f T 叉樹 1 雙親表示法 ; r， n; / 根結(jié)點(diǎn)位置，結(jié) 點(diǎn)數(shù) F G H I R A B C D E 樹的雙親存儲(chǔ)結(jié)構(gòu) R A 0 1 B 0 2 C 0 3 D 1 4 E 1 5 F 3 6 G 6 7 H 6 8 I 6 9 r=0 n=10 這種存儲(chǔ)結(jié)構(gòu)利用了任一結(jié)點(diǎn)的雙親結(jié)點(diǎn)唯一的性質(zhì)。 可以方便地直接找到任一結(jié)點(diǎn)的雙親 但求結(jié)點(diǎn)的孩子結(jié)點(diǎn)時(shí)需要掃描整個(gè)數(shù)組。 樹的存儲(chǔ)結(jié)構(gòu) 8 9 3 5 0 1 2 6 0 1 2 3 4 5 6 7 8 9 r n A B C D E F G H I R 4 10 孩子鏈表存儲(chǔ)結(jié)構(gòu) 孩子鏈表表示法 F G H I R A B C D E (b) 樹 F G R A B C D E (c) 孩子兄弟存儲(chǔ)結(jié)構(gòu) R A D C G B F E 孩子結(jié)點(diǎn) 兄弟結(jié)點(diǎn) a) 結(jié)點(diǎn)結(jié)構(gòu) 3 孩子兄弟表示法 先左 后右的遍歷算法 先 (根 )序 的遍歷 算法 中 (根 )序 的遍歷 算法 后 (根 )序 的遍歷 算法 7根 左 子樹 右 子樹 歷二叉樹和線索二叉樹 歷二叉樹和線索二叉樹 遍歷序列可否唯一確定一棵二叉樹？ 先序序列： 序序列： B C I D E F G H J 遍歷二叉樹 的結(jié)果是求得結(jié)點(diǎn)的一個(gè)線性序列 。 指向該線 性序列中的前驅(qū)和后繼的指針，稱作 線索 。 包含 線索的 存儲(chǔ)結(jié)構(gòu) 稱作 線索鏈表 ；與其相應(yīng)的二叉樹，稱為 線索二叉樹 。 歷二叉樹和線索二叉樹 A F H I E G B D C A F H I E G B D C 序遍歷結(jié)點(diǎn)序列： F H I E G B D C (a) 二叉樹 (b) 先序線索樹的邏輯形式 結(jié)點(diǎn)序列： F H I E G B D C d) 后序線索樹的邏輯形式 結(jié)點(diǎn)序列： c) 中序線索樹的邏輯形式 結(jié)點(diǎn)序列： F H I E G B D C F H I E G B D C 線索二叉樹的指針信息存儲(chǔ)在哪里？ 設(shè)一棵二叉樹有 有 (指針連線 ) ， 而 ( ，顯然 有 n+1個(gè)空閑指針域 未用。 可以利用這些空閑的指針域來存放結(jié)點(diǎn)的 直接前驅(qū) 和 直接后繼 信息。 歷二叉樹和線索二叉樹 對(duì)結(jié)點(diǎn)的指針域做如下規(guī)定： 若結(jié)點(diǎn)有左子樹，則 0； 否則，指向其直接前驅(qū)， 1； 若結(jié)點(diǎn)有右子樹，則 0； 否則，指向其直接后繼， 1； 歷二叉樹和線索二叉樹 索二叉樹的結(jié)點(diǎn)結(jié)構(gòu) 0： 1： 0： 1： 樹和森林的遍歷 1 樹的遍歷 由樹結(jié)構(gòu)的定義可知，樹的遍歷有二種方法。 (1) 先根序遍歷 ：先訪問根結(jié)點(diǎn)，然后 先序遍歷完 每棵子樹。 (2) 后根序遍歷 ：先 依次后序遍歷完 每棵子樹，然后訪問根結(jié)點(diǎn)。 A B D C K G J I F H E 先序遍歷： 序遍歷： 本概念 結(jié)點(diǎn)路徑 ：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。 路徑長(zhǎng)度 ：結(jié)點(diǎn)路徑上的分支數(shù)目稱為路徑長(zhǎng)度 。 樹的路徑長(zhǎng)度 ：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和 。 夫曼樹及其應(yīng)用 A B D C K G J I F H E ：結(jié)點(diǎn)路徑 路徑長(zhǎng)度 (即邊的數(shù)目 )： 2 ； 樹的路徑長(zhǎng)度 ：31+52+23=19 結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度 ：從該結(jié)點(diǎn)的到樹的根結(jié)點(diǎn)之間的路徑長(zhǎng)度與結(jié)點(diǎn)的權(quán) (值 )的乘積 。 權(quán) (值 )：各種 開銷 、 代價(jià) 、 頻度 等的抽象稱呼 。 樹的帶權(quán)路徑長(zhǎng)度 ：樹中 所有葉子結(jié)點(diǎn) 的帶權(quán)路徑長(zhǎng)度之和，記做： w1l1+w2+wnwi (i=1,2,n) 其中： 具有 每個(gè)結(jié)點(diǎn)的權(quán)值為 的二叉樹不止一棵，但在所有的這些二叉樹中，必定存在一棵稱這棵樹為 或稱最優(yōu)樹 ) 。 基本概念 根據(jù) ,構(gòu)造成 ,其中每棵二叉樹只有一個(gè)權(quán)值為 有左、右子樹； 在 取兩棵根結(jié)點(diǎn)權(quán)值最小 的樹作為左 、 右子樹構(gòu)造一棵新的二叉樹，且新的二叉樹根結(jié)點(diǎn)權(quán)值為其左 、 右子樹根結(jié)點(diǎn)的權(quán)值之和； 在 時(shí)將新得到的樹加入 重復(fù)、，直到 規(guī)定 F=2, , 權(quán)值小 的二叉樹作為新構(gòu)造的二叉樹的 左子樹 ， 權(quán)值大的二叉樹作為新構(gòu)造的二叉樹的右子樹 ； 在取值相等時(shí)， 深度小 的二叉樹作為新構(gòu)造的二叉樹的 左子樹 ， 深度大的二叉樹作為新構(gòu)造的二叉樹的右子樹 。 權(quán)值集合 W=8, 3, 4, 6, 5, 5構(gòu)造 所構(gòu)造的 2+33+43+82+53+53 =79 3 4 5 5 6 8 第一步 5 5 6 8 第二步 3 4 7 6 8 第三步 3 4 7 5 5 10 8 第四步 5 5 10 6 3 4 7 13 第六步 1 1 1 1 1 0 0 0 0 0 8 5 5 10 18 6 3 4 7 13 31 第五步 8 5 5 10 18 6 3 4 7 13 例子 在電報(bào)收發(fā)等數(shù)據(jù)通訊中 ， 常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符 0、 1組成的字符串來傳輸 。 為了使收發(fā)的速度提高 ， 要求電文 編碼要盡可能短 。 要設(shè)計(jì) 長(zhǎng)短不等 的編碼，還必須保證 任意字符的編碼都不是另一個(gè)字符編碼的前綴 ，稱為 前綴編碼 。 設(shè)電文中的字符集 C=c1,各個(gè)字符出現(xiàn)的次數(shù)或頻度集 W=w1, 以 字符集 次數(shù)或頻度集 的權(quán)值 來構(gòu)造 規(guī) 定 0”，右分支代表 1” 。 從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)所經(jīng)歷 的路徑分支上的 0”或 1”所組成的字符串 ， 為該結(jié)點(diǎn)所對(duì)應(yīng)的編碼 ， 稱之為 *由于每個(gè)字符都是葉子結(jié)點(diǎn) ，不可能出現(xiàn)在根結(jié)點(diǎn)到其它字符結(jié)點(diǎn)的路徑上，所以一個(gè)字符的 第七章 圖 重點(diǎn)內(nèi)容 圖的定義及相關(guān)術(shù)語 圖的各種存儲(chǔ)結(jié)構(gòu) 圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷法 圖的最小生成樹的概念 克魯斯卡爾算法、普里姆算法生成最小生成樹 圖的拓?fù)渑判?、關(guān)鍵路徑的求法 圖的存儲(chǔ)結(jié)構(gòu) 圖的數(shù)組存儲(chǔ)表示法 基本思想 ： 對(duì)于 有 一維數(shù)組 n存儲(chǔ)頂點(diǎn)信 息 用二維數(shù)組 Ann存儲(chǔ)頂點(diǎn)之間關(guān)系的信 息 該二維數(shù)組稱為 鄰接矩陣 在鄰接矩陣中 ： 以頂 點(diǎn)在 的下標(biāo)代表頂點(diǎn) 鄰接矩陣中的 元素 Aij存放的是 頂點(diǎn) 信 息 921 無向圖的數(shù)組表示 (1) 無權(quán)圖的鄰接矩陣 無向無權(quán)圖 G=(V， E)有 n(n 1)個(gè)頂點(diǎn)，其鄰接矩陣是其元素的定義如下： 1 若 ( E，即 0 若 ( E，即 Aij= (a) 無向圖 a b c d (b) 頂點(diǎn)矩陣 a b c d 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 (c) 鄰接矩陣 (2) 帶權(quán)圖（網(wǎng)）的鄰接矩陣 無向帶權(quán)圖 G=(V， E) 的鄰接矩陣元素的定義如下： 帶權(quán)無向圖 鄰接矩陣 3 5 4 1 2 6 a b c d e 3 a b c d e 6 2 6 3 4 3 2 3 1 4 3 5 3 5 若 ( E，即 值為 若 ( E，即 Aij= 特點(diǎn)： 1、無向圖的鄰接矩陣是 對(duì)稱方陣 ； 2、頂點(diǎn) 第 0元素的個(gè)數(shù) ； 3、 無向圖的邊數(shù)是上 (或下 )三角形矩陣中 非 0元素個(gè)數(shù) 。 952 有向圖的數(shù)組表示 (1) 無權(quán)圖的鄰接矩陣 有向無權(quán)圖 G=(V， E)有 n(n 1)個(gè)頂點(diǎn)，則其鄰接矩陣是 素定義如下： 1 若 E，從 Aij= 0 若 E 從 有弧 (a) 有向圖 a c b d e (b) 頂點(diǎn)矩陣 a b c d e (c) 鄰接矩陣 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 (2) 帶權(quán)圖的鄰接矩陣 有向帶權(quán)圖 G=(V， E)的鄰接矩陣元素的定義如下： 若 E，即 值為 若 E，即 Aij= (b) 頂點(diǎn)矩陣 a b c d e (c) 鄰接矩陣 6 2 3 3 1 4 5 (a) 帶權(quán)有向圖 3 5 4 1 2 6 a b c d e 3 特點(diǎn)： 1、 對(duì)于頂點(diǎn) 第 非 0元素的個(gè)數(shù)是其出度OD( 第 非 0元素的個(gè)數(shù)是其入度 ID(。 2、鄰接矩陣中 非 0元素的個(gè)數(shù)就是圖的 弧的數(shù)目 。 鄰接鏈表法 基本 思想 ： 對(duì)圖 的 每個(gè)頂點(diǎn) 建立一個(gè) 單鏈表 ，存儲(chǔ)該頂點(diǎn)所有鄰接頂點(diǎn)及其相關(guān)信息 。 每一個(gè)單鏈表設(shè)一個(gè) 表頭結(jié)點(diǎn) 。 第 表示依附于頂點(diǎn) (對(duì)有向圖是以頂點(diǎn) )。 1 結(jié)點(diǎn)結(jié)構(gòu)與鄰接鏈表示例 鏈表中的結(jié)點(diǎn)稱為 表結(jié)點(diǎn) ，表結(jié)點(diǎn)由三個(gè)域組 成： 鄰 接點(diǎn)域：指示與頂點(diǎn) 的位置 鏈域：指向下一個(gè)與頂點(diǎn) 數(shù)據(jù)域：存儲(chǔ)和邊或弧相關(guān) 的信息，如權(quán)值等。 表頭結(jié)點(diǎn) (稱為 頂點(diǎn)結(jié)點(diǎn) )，由兩個(gè)域組成： 鏈域：指向鏈表 中的第一個(gè)結(jié)點(diǎn) 數(shù)據(jù)域 ： 存儲(chǔ)頂點(diǎn)名或其他信息。 結(jié)點(diǎn) ： 頭結(jié)點(diǎn) ： 所有 頂點(diǎn)結(jié)點(diǎn) 用一個(gè)向量以順序結(jié)構(gòu)形式存儲(chǔ)，可以隨機(jī)訪問任意頂點(diǎn)的鏈表，該向量稱為 表頭向量 向 量的下標(biāo)指示 頂點(diǎn)的位置 ？ v1 v2 v3 v4 1 2 3 4 v2 2 1 3 0 2 0 3 1 4 2 0 4 2 3 無向圖鄰接表 有向圖 v1 v2 v3 v4 3 0 1 4 2 3 0 1 2 3 4 v1 v3 鄰接鏈表 出度直觀 2 0 2 2 0 1 2 3 4 0 4 逆鄰接鏈表 入度直觀 有向圖鄰接表 有向圖的鄰接表有兩種： 正鄰接表 和 逆鄰接表 正鄰接表 是以頂點(diǎn) 立的鄰接表 ； 逆鄰接表 是以頂點(diǎn) 立的鄰接表； 2 鄰接表法的特點(diǎn) 表頭向量中每個(gè)分量就是一個(gè)單鏈表的頭結(jié)點(diǎn)， 分量個(gè)數(shù)就是圖中的頂點(diǎn)數(shù)目 ； 在 邊或弧稀疏 的情況下 ，用鄰接表表示比用鄰接矩陣表示節(jié)省存儲(chǔ)空間； 在無向圖， 頂點(diǎn) 在有向圖中 ，第 (或入 )度；求入 (或出 )度，須遍歷整個(gè)鄰接表； 在鄰接表上容易找出任一頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn) ； 要判定兩個(gè)頂點(diǎn) 要搜索第 圖的遍歷 圖 的遍歷 (從圖的某一頂點(diǎn)出發(fā)，訪遍圖中的其余頂點(diǎn)， 且每個(gè)頂點(diǎn)僅被訪問一次 。圖 的遍歷算法是各種圖操作的基礎(chǔ) 。 復(fù)雜性： 圖的任意頂點(diǎn)可能和其余的頂點(diǎn)相鄰接，可能在訪問了某個(gè)頂點(diǎn)后，沿某條路徑搜索后又回到原頂點(diǎn)。 解決辦法 ： 在遍歷過程中記下已被訪問過的頂點(diǎn)。設(shè)置一個(gè)輔助向量 n(，其初值為 0，一旦訪問了頂點(diǎn) i為 1或?yàn)樵L問的次序號(hào) 。 圖 的遍歷算法有 深度優(yōu)先搜索算法 和 廣度優(yōu)先搜索算法 。 采用的數(shù)據(jù)結(jié)構(gòu) 是 (正 )鄰接鏈表 。 深度優(yōu)先搜索算法 深度優(yōu)先搜索 (歷類似樹的先序遍歷 ，是 樹的先序遍歷的推廣 。 1 算法思想 設(shè)初始狀態(tài)時(shí)圖中的所有頂點(diǎn)未被訪問，則： 從圖中某個(gè)頂點(diǎn) 訪問 后找到 個(gè)鄰接頂點(diǎn) 從 度優(yōu)先搜索訪問和 接 且 未被訪問 的所有頂點(diǎn)； 轉(zhuǎn) ，直到和 接的所有頂點(diǎn)都被訪問為止 繼續(xù)選取圖中未被訪問頂點(diǎn) (1)，直到圖中所有頂點(diǎn)都被訪問為止。 (a) 無向圖 G v1 v2 v3 v4 b) 0 1 2 3 4 v2 2 1 2 0 0 1 4 3 無向圖的深度優(yōu)先搜索遍歷示例。 某種 深度優(yōu)先搜索算法 有向圖的廣度優(yōu)先搜索遍歷示例 。 上述圖 的 b) G的正鄰接鏈表 1 3 0 1 4 2 3 0 1 2 3 4 2 0 3 1 1 (a) 有向圖 G v1 v2 v3 v4 廣度優(yōu)先搜索算法 構(gòu) 造最小生成樹的算法有許多，基本原則是： 盡可能選取權(quán)值最小的邊，但不能構(gòu)成回路； 選擇 以上的基本原則是基于 設(shè) G=(V， E)是一個(gè)帶權(quán)連通圖， 的一個(gè)非空子集。若 u U ， v (u, v)是 值最小的邊 ， 則必存在一棵包含邊 (u, v)的最小生成樹 。 最小生成樹 普里姆 (法 從連通網(wǎng) N=(U， E)中找最小生成樹 T=(U， 。 1 算法思想 若從頂點(diǎn) U= ； 先找 權(quán)值最小 的邊 (u， v)，其中 u U且 v 且子圖不構(gòu)成環(huán)，則 U= U v， E (u， v) ； 重復(fù) ，直到 U= 則 T=(U，是最小生成樹 。 v1 v3 v2 v4 8 5 7 12 11 3 6 (1) v2 (2) (3) v2 (4) v2 (5) v2 普里姆 (法 克魯斯卡爾 (法 1 算法思想 設(shè) G=(V, E)是具有 T=(U, 其最小生成樹 。 初值： U=V， 。 對(duì) 選取權(quán)值 最小的邊 (若 邊 (入到 則舍棄該邊 (邊 (；否則，將該邊并入到 即 E ( 。 重復(fù) ，直到 v1 v3 v2 v4 8 5 7 12 11 3 6 (1) (2) 3 v5 v4 (5) v2 按 (3) 3 v5 4) 3 v5 拓?fù)渑判?1 定義 拓?fù)渑判?： 由某個(gè)集合上的一個(gè) 偏序 得到該集合上的一個(gè) 全序 的操作。 自反性 ：若 a R，稱集合 是 自反的 。 對(duì)稱