大連交通大學軟件學院數(shù)據(jù)結(jié)構(gòu)-復(fù)習資料-考試題PPT課件

1 數(shù)據(jù)結(jié)構(gòu) 教材李春葆數(shù)據(jù)結(jié)構(gòu)教程清華大學出版社嚴蔚敏數(shù)據(jù)結(jié)構(gòu)清華大學出版社參考書李春葆數(shù)據(jù)結(jié)構(gòu)習題與解析 第2版或第3版 清華大學出版社 2 概述模塊1 線性表模塊2 樹型結(jié)構(gòu)模塊3 圖型結(jié)構(gòu)模塊4 其他 3 1 數(shù)據(jù)結(jié)構(gòu)的定義 數(shù)據(jù) 數(shù)據(jù)元素 數(shù)據(jù)項 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)以及相互之間的聯(lián)系 或關(guān)系 包括 1 數(shù)據(jù)的邏輯結(jié)構(gòu) 2 數(shù)據(jù)的存儲結(jié)構(gòu) 物理結(jié)構(gòu) 3 施加在該數(shù)據(jù)上的運算 概述 4 數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù) 它與數(shù)據(jù)的存儲無關(guān) 是獨立于計算機的 數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn) 亦稱為映象 它是依賴于計算機語言的 數(shù)據(jù)的運算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的 每種邏輯結(jié)構(gòu)都有一組相應(yīng)的運算 但運算的實現(xiàn)與數(shù)據(jù)的存儲結(jié)構(gòu)有關(guān) 程序 數(shù)據(jù)結(jié)構(gòu) 算法 概述 5 1 線性結(jié)構(gòu) 2 樹形結(jié)構(gòu) 3 圖形結(jié)構(gòu) 概述 邏輯結(jié)構(gòu)主要有三大類 6 存儲結(jié)構(gòu)分為如下四種 1 順序存儲方法 2 鏈式存儲方法 3 索引存儲方法 4 散列存儲方法 概述 7 2 算法 算法是對特定問題求解步驟的一種描述 它是指令的有限序列 概述 8 算法的五個重要的特性 1 有窮性 2 確定性 3 可行性 4 有輸入 5 有輸出 概述 9 算法的時間復(fù)雜度 是指其基本運算在算法中重復(fù)執(zhí)行的次數(shù) 算法中基本運算次數(shù)T n 是問題規(guī)模n的某個函數(shù)f n 記作 T n O f n 記號 O 讀作 大O 它表示隨問題規(guī)模n的增大算法執(zhí)行時間的增長率和f n 的增長率相同 概述 10 例分析以下程序段的時間復(fù)雜度 i 1 while i n i i 2 解 上述算法中基本操作是語句i i 2 設(shè)其頻度為T n 則有 2T n n即T n log2n O log2n 所以 該程序段的時間復(fù)雜度為O log2n 11 算法空間復(fù)雜度 是對一個算法在運行過程中臨時占用的存儲空間大小的量度 對于空間復(fù)雜度為O 1 的算法稱為原地工作或就地工作算法 概述 12 遞歸定義 3 算法設(shè)計方法 遞歸 在定義一個算法時出現(xiàn)調(diào)用本算法的成分 稱之為遞歸 概述 13 遞歸模型 由遞歸出口和遞歸體組成 例如 求二叉樹所有結(jié)點個數(shù) f b 0b NULLf b f b lchild f b rchild 1b NULL 概述 14 遞歸算法設(shè)計 對原問題f s 進行分析 假設(shè)出合理的 較小問題 f s 假設(shè)f s 是可解的 在此基礎(chǔ)上確定f s 的解 即給出f s 與f s 之間的關(guān)系 確定一個特定情況 如f 1 或f 0 的解 由此作為遞歸出口 概述 15 b b rchild b lchild 假設(shè)出合理的 較小問題 假設(shè)左右子樹的結(jié)點個數(shù)可求 求出f s 與f s 之間的關(guān)系 f b f b lchild f b rchild 1 確定遞歸出口 f NULL 0 概述 16 intf BTNode b if b NULL return 0 elsereturn f b lchild f b rchild 1 求解算法 概述 17 例設(shè)計求f n 1 2 n的遞歸算法解 f n 為前n項之和 則f n 1 1 2 n 1 假設(shè)f n 1 可求 則f n f n 1 n 所以 f n 1當n 1f n f n 1 n當n 1對應(yīng)的遞歸算法如下 18 intf intn if n 1 return 1 elsereturn f n 1 n 19 1 一般線性表線性表 具有相同特性的數(shù)據(jù)元素的一個有限序列 不是集合 模塊1 線性結(jié)構(gòu) 邏輯結(jié)構(gòu) 20 1 順序表 typedefstruct ElemTypeelem MaxSize 存放順序表元素 intlength 存放順序表的長度 SqList 存儲結(jié)構(gòu)之一 模塊1 線性結(jié)構(gòu) 21 順序表基本運算的實現(xiàn) 插入數(shù)據(jù)元素算法 元素移動的次數(shù)不僅與表長n有關(guān) 插入一個元素時所需移動元素的平均次數(shù)n 2 平均時間復(fù)雜度為O n 模塊1 線性結(jié)構(gòu) 22 刪除數(shù)據(jù)元素算法 元素移動的次數(shù)也與表長n有關(guān) 刪除一個元素時所需移動元素的平均次數(shù)為 n 1 2 刪除算法的平均時間復(fù)雜度為O n 模塊1 線性結(jié)構(gòu) 23 2 鏈表 定義單鏈表結(jié)點類型 typedefstructLNode ElemTypedata structLNode next 指向后繼結(jié)點 LinkList 存儲結(jié)構(gòu)之二 模塊1 線性結(jié)構(gòu) 24 定義雙鏈表結(jié)點類型 typedefstructDNode ElemTypedata structDNode prior 指向前驅(qū)結(jié)點 structDNode next 指向后繼結(jié)點 DLinkList 模塊1 線性結(jié)構(gòu) 25 單鏈表基本運算的實現(xiàn) 重點 1 頭插法建表和尾插法建表算法 它是很多算法設(shè)計的基礎(chǔ) 2 查找 插入和刪除操作 模塊1 線性結(jié)構(gòu) 26 頭插法建表該方法從一個空表開始 讀取字符數(shù)組a中的字符 生成新結(jié)點 將讀取的數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中 然后將新結(jié)點插入到當前鏈表的表頭上 直到結(jié)束為止 采用頭插法建表的算法如下 模塊1 線性結(jié)構(gòu) 27 voidCreateListF LinkList 模塊1 線性結(jié)構(gòu) 28 i 0 i 1 i 2 i 3 head 采用頭插法建立單鏈表的過程 head head head head 第1步 建頭結(jié)點 第2步 i 0 新建a結(jié)點 插入到頭結(jié)點之后 第3步 i 1 新建d結(jié)點 插入到頭結(jié)點之后 第4步 i 2 新建c結(jié)點 插入到頭結(jié)點之后 第5步 i 3 新建b結(jié)點 插入到頭結(jié)點之后 29 尾插法建表頭插法建立鏈表雖然算法簡單 但生成的鏈表中結(jié)點的次序和原數(shù)組元素的順序相反 若希望兩者次序一致 可采用尾插法建立 該方法是將新結(jié)點插到當前鏈表的表尾上 為此必須增加一個尾指針r 使其始終指向當前鏈表的尾結(jié)點 采用尾插法建表的算法如下 模塊1 線性結(jié)構(gòu) 30 voidCreateListR LinkList 終端結(jié)點next域置為NULL 31 i 0 i 1 i 2 i 3 head 頭結(jié)點 采用尾插法建立單鏈表的過程 模塊1 線性結(jié)構(gòu) 32 例設(shè)C a1 b1 a2 b2 an bn 為一線性表 采用帶頭結(jié)點的hc單鏈表存放 編寫一個算法 將其拆分為兩個線性表 使得 A a1 a2 an B b1 b2 bn 模塊1 線性結(jié)構(gòu) 33 解 設(shè)拆分后的兩個線性表都用帶頭結(jié)點的單鏈表存放 先建立兩個頭結(jié)點 ha和 hb 它們用于存放拆分后的線性表A和B ra和rb分別指向這兩個單鏈表的表尾 用p指針掃描單鏈表hc 將當前結(jié)點 p鏈到ha未尾 p沿next域下移一個結(jié)點 若不為空 則當前結(jié)點 p鏈到hb未尾 p沿next域下移一個結(jié)點 如此這樣 直到p為空 最后將兩個尾結(jié)點的next域置空 對應(yīng)算法如下 模塊1 線性結(jié)構(gòu) 34 voidfun LinkList hc LinkList rb始終指向hb的末尾結(jié)點 模塊1 線性結(jié)構(gòu) 35 while p NULL ra next p ra p 將 p鏈到ha單鏈表未尾 p p next rb next p rb p 將 p鏈到hb單鏈表未尾 p p next ra next rb next NULL 兩個尾結(jié)點的next域置空 模塊1 線性結(jié)構(gòu) 36 例已知線性表元素遞增有序 并以帶頭結(jié)點的單鏈表作存儲結(jié)構(gòu) 設(shè)計一個高效算法 刪除表中所有值大于mink且小于maxk的元素 若表中存在這樣的元素 并分析所寫算法的時間復(fù)雜度 模塊1 線性結(jié)構(gòu) 37 解 先在單鏈表中找到其data值則好大于mink的結(jié)點 p 其前驅(qū)結(jié)點為 pre 繼續(xù)沿next鏈查找其值大于maxk的結(jié)點 在這個過程中刪除 p結(jié)點 算法如下 voiddelnode SNode h ElemTypemaxk ElemTypemink SNode p pre if maxk mink pre h p pre next 模塊1 線性結(jié)構(gòu) 38 while p NULL 模塊1 線性結(jié)構(gòu) 39 雙鏈表基本運算的實現(xiàn) 重點 插入和刪除結(jié)點的算法 模塊1 線性結(jié)構(gòu) 40 循環(huán)鏈表基本運算的實現(xiàn) 重點 判斷最后一個結(jié)點 模塊1 線性結(jié)構(gòu) 41 例某線性表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除第一個結(jié)點 故采用存儲方式最節(jié)省運算時間 A 單鏈表B 僅有頭結(jié)點的單循環(huán)鏈表C 雙鏈表D 僅有尾指針的單循環(huán)鏈表 模塊1 線性結(jié)構(gòu) 42 例設(shè)計一個算法在單鏈表中查找元素值為e的結(jié)點序號的算法LocateElem L e 思路 在單鏈表L中從頭開始找第1個值域與e相等的結(jié)點 若存在這樣的結(jié)點 則返回位置 否則返回0 intLocateElem LinkList L ElemTypee LinkList p L next intn 1 while p NULL 43 解 本題答案為D 在有尾指針r的單循環(huán)鏈表中在最后一個結(jié)點之后插入結(jié)點 s的操作是 s next r next r next s r s 刪除第一個結(jié)點的操作是 p r next r next p next free p 其時間復(fù)雜度均為O 1 模塊1 線性結(jié)構(gòu) 44 2 棧 1 棧的定義棧是一種先進后出表棧的基本運算 進棧 出棧 邏輯結(jié)構(gòu) 模塊1 線性結(jié)構(gòu) 45 例已知一個棧的進棧序列是1 2 3 n 其輸出序列是p1 p2 pn 若p1 n 則pi的值 A i B n i C n i 1 D 不確定 答 當p1 n時 輸出序列必是n n 1 3 2 1 則有 p2 n 1 p3 n 2 pn 1推斷出pi n i 1 所以本題答案為C 46 例設(shè)n個元素進棧序列是1 2 3 n 其輸出序列是p1 p2 pn 若p1 3 則p2的值 A 一定是2 B 一定是1 C 不可能是1 D 以上都不對 答 當p1 3時 說明1 2 3先進棧 立即出棧3 然后可能出棧 即為2 也可能4或后面的元素進棧 再出棧 因此 p2可能是2 也可能是4 n 但一定不能是1 所以本題答案為C 模塊1 線性結(jié)構(gòu) 47 2 順序棧 typedefstruct ElemTypeelem MaxSize inttop 棧指針 SqStack 存儲結(jié)構(gòu)之一 模塊1 線性結(jié)構(gòu) 48 ?？諚l件 s top 1棧滿條件 s top MaxSize 1進棧 top s data s top e 出棧 e s data s top s top 順序棧的4要素 模塊1 線性結(jié)構(gòu) 49 3 鏈棧 typedefstructlinknode ElemTypedata 數(shù)據(jù)域 structlinknode next 指針域 LiStack 存儲結(jié)構(gòu)之二 模塊1 線性結(jié)構(gòu) 50 帶頭結(jié)點的單鏈表來實現(xiàn) 也可不帶頭結(jié)點 ?？諚l件 s next NULL棧滿條件 模塊1 線性結(jié)構(gòu) 51 3 隊列 1 隊列的定義隊列是一種先進先出表 隊列的基本運算 進隊 出隊 邏輯結(jié)構(gòu) 模塊1 線性結(jié)構(gòu) 52 2 順序隊 typedefstruct ElemTypeelem MaxSize intfront rear 隊首和隊尾指針 SqQueue 存儲結(jié)構(gòu)之一 模塊1 線性結(jié)構(gòu) 53 隊空 q front q rear隊滿 q rear 1 MaxSize q front進隊 q rear q rear 1 MaxSize q data q rear e 出隊 q front q front 1 MaxSize e q data q front 環(huán)形隊列的4要素 模塊1 線性結(jié)構(gòu) 54 3 鏈隊 structqnode 數(shù)據(jù)結(jié)點 ElemTypedata structqnode next QNode typedefstruct 頭結(jié)點 QNode front QNode rear LiQueue 存儲結(jié)構(gòu)之二 模塊1 線性結(jié)構(gòu) 55 2 順序串 3 鏈串 4 串的模式匹配算法 不作要求 4 串 1 串的定義串 子串 串相等 空串 空格串 模塊1 線性結(jié)構(gòu) 56 5 數(shù)組和稀疏矩陣 1 數(shù)組的定義相同類型數(shù)據(jù)元素 有限序列 模塊1 線性結(jié)構(gòu) 57 2 數(shù)組的存儲結(jié)構(gòu) 以行序為主序 LOC ai j LOC ac1 c2 i c1 d2 c2 1 j c2 k 以列序為主序LOC ai j LOC ac1 c2 j c2 d1 c1 1 i c1 k 以數(shù)組A c1 d1 c2 d2 為例 模塊1 線性結(jié)構(gòu) 58 3 特殊矩陣的壓縮存儲 對稱矩陣若一個n階方陣A n n 中的元素滿足ai j aj i 0 i j n 1 則稱其為n階對稱矩陣 A 0 n 1 0 n 1 B 0 n n 1 2 模塊1 線性結(jié)構(gòu) 59 三角矩陣 采用類似的壓縮方法 模塊1 線性結(jié)構(gòu) 60 4 稀疏矩陣 存儲結(jié)構(gòu) 三元組表示 十字鏈表表示各種表示的基本思路 非零元素遠小于元素總數(shù) 模塊1 線性結(jié)構(gòu) 61 一個廣義表中所含元素的個數(shù)稱為它的長度 6 廣義表 GL a a a b c d 長度為4 模塊1 線性結(jié)構(gòu) 62 一個廣義表中括號嵌套的最大次數(shù)為它的深度 GL a a a b c d 深度為2 模塊1 線性結(jié)構(gòu) 63 表的第一個元素a1為廣義表GL的表頭 其余部分 a2 ai ai 1 an 為GL的表尾 GL a a a b c d 表頭為a 表尾為 a a b c d 模塊1 線性結(jié)構(gòu) 64 模塊2 樹形結(jié)構(gòu) 1 樹的定義遞歸定義適合于表示層次結(jié)構(gòu)的數(shù)據(jù) 1 樹 65 2 樹的表示法 邏輯表示方法 樹形表示法 文氏圖表示法 凹入表示法 括號表示法 模塊2 樹形結(jié)構(gòu) 66 3 樹的遍歷 先根遍歷算法 后根遍歷算法 模塊2 樹形結(jié)構(gòu) 67 4 樹和二叉樹的相互轉(zhuǎn)換 樹 二叉樹 二叉樹 樹 模塊2 樹形結(jié)構(gòu) 68 2 二叉樹 1 二叉樹的定義根 左子樹 右子樹完全二叉樹 滿二叉樹的定義 模塊2 樹形結(jié)構(gòu) 69 性質(zhì)1非空二叉樹上葉結(jié)點數(shù)等于雙分支結(jié)點數(shù)加1 即n0 n2 1 性質(zhì)2非空二叉樹上第i層上至多有2i 1個結(jié)點 i 1 2 二叉樹性質(zhì) 模塊2 樹形結(jié)構(gòu) 70 性質(zhì)3高度為h的二叉樹至多有2h 1個結(jié)點 h 1 性質(zhì)4完全二叉樹的性質(zhì) 性質(zhì)5具有n個 n 0 結(jié)點的完全二叉樹的高度為 log2n 1 或 log2n 1 2 二叉樹性質(zhì) 模塊2 樹形結(jié)構(gòu) 71 例將一棵有99個結(jié)點的完全二叉樹從根這一層開始 每一層從左到右依次對結(jié)點進行編號 根結(jié)點的編號為1 則編號為49的結(jié)點的右孩子編號為 A 98B 99C 50D 不存在 答 D 模塊2 樹形結(jié)構(gòu) 72 例深度為5的二叉樹至多有個結(jié)點 A 16B 32C 31D 10 答 相同滿度時滿二叉樹結(jié)點最多 h 5的滿二叉樹結(jié)點個數(shù) 25 1 31 C 模塊2 樹形結(jié)構(gòu) 73 3 二叉樹存儲結(jié)構(gòu) 二叉樹的順序存儲結(jié)構(gòu) 模塊2 樹形結(jié)構(gòu) A B C D E F 74 i 2i 2i 1 左孩子 右孩子 75 二叉鏈存儲結(jié)構(gòu)typedefstructnode ElemTypedata 數(shù)據(jù)元素 structnode lchild 指向左孩子 structnode rchild 指向右孩子 BTNode 76 A B C 左孩子 右孩子 77 4 二叉樹的遍歷 先序遍歷 中序遍歷 后序遍歷 層次遍歷 模塊2 樹形結(jié)構(gòu) 78 例假設(shè)二叉樹采用二叉鏈存儲結(jié)構(gòu)存儲 試設(shè)計一個算法 輸出一棵給定二叉樹的所有葉子結(jié)點 解 輸出一棵二叉樹的所有葉子結(jié)點的遞歸模型f 如下 f b 不做任何事件若b NULLf b 輸出 b結(jié)點的data域若 b為葉子結(jié)點f b f b lchild f b rchild 其他情況 模塊2 樹形結(jié)構(gòu) 79 voidDispLeaf BTNode b if b NULL if b lchild NULL 模塊2 樹形結(jié)構(gòu) 先序遍歷思想 80 例試設(shè)計判斷兩棵二叉樹是否相似的算法 所謂二叉樹t1和t2是相似的指的是t1和t2都是空的二叉樹 或者t1和t2的根結(jié)點是相似的 t1的左子樹和t2的左子樹是相似的且t1的右子樹與t2的右子樹是相似的 模塊2 樹形結(jié)構(gòu) 81 解本題的遞歸模型如下 true若t1 t2 NULLf t1 t2 false若t1 t2之一為NULL 另一不為NULLf t1 lchild t2 lchild f t1 rchild t2 rchild 其他情況對應(yīng)的算法如下 模塊2 樹形結(jié)構(gòu) 82 intlike BTNode b1 BTNode b2 intlike1 like2 if b1 NULL 模塊2 樹形結(jié)構(gòu) 后序遍歷思想 83 例設(shè)計一個算法求二叉樹的所有結(jié)點個數(shù) 解 對應(yīng)的算法如下 intnodenum BTNode bt if bt NULL return nodenum bt lchild nodenum bt lchild 1 elsereturn 0 模塊2 樹形結(jié)構(gòu) 后序遍歷思想 84 例設(shè)計一個算法釋放一棵二叉樹bt的所有結(jié)點 解 算法如下 voidrelease BSTNode 模塊2 樹形結(jié)構(gòu) 后序遍歷思想 85 5 線索二叉樹 共有2n n 1 n 1個空鏈域 線索化 模塊2 樹形結(jié)構(gòu) 線索化與某種遍歷方式有關(guān) 86 3 哈夫曼樹 1 哈夫曼樹的定義 WPL最小 沒有單分支結(jié)點即n1 0 模塊2 樹形結(jié)構(gòu) 87 2 哈夫曼樹的構(gòu)造過程 3 哈夫曼編碼的構(gòu)造過程 模塊2 樹形結(jié)構(gòu) 88 頂點的度 入度和出度 完全圖 子圖 路徑和路徑長度 連通 連通圖和連通分量 強連通圖和強連通分量 權(quán)和網(wǎng) 模塊3 圖形結(jié)構(gòu) 1 圖的基本概念 89 2 圖的存儲結(jié)構(gòu) 鄰接矩陣存儲方法 掌握兩種存儲方法的優(yōu)缺點 同一種功能在不同存儲結(jié)構(gòu)上的實現(xiàn)算法 鄰接表存儲方法 模塊3 圖形結(jié)構(gòu) 90 3 圖的遍歷 深度優(yōu)先搜索遍歷 離初始點越遠越優(yōu)先訪問 訪問序列 1 2 3 4 5 6 7 模塊3 圖形結(jié)構(gòu) 91 voidDFS ALGraph G intv ArcNode p Visited v 1 置已訪問標記 printf d v 輸出被訪問頂點的編號 p G adjlist v firstarc while p NULL if visited p adjvex 0 DFS G p adjvex p p nextarc 模塊3 圖形結(jié)構(gòu) 92 廣度優(yōu)先搜索遍歷 離初始點越近越優(yōu)先訪問 訪問序列 1 2 6 7 3 5 4 模塊3 圖形結(jié)構(gòu) 93 voidBFS ALGraph G intv ArcNode p intqueue MAXV front 0 rear 0 intvisited MAXV intw i for i 0 in i visited i 0 printf 2d v visited v 1 置已訪問標記 rear rear 1 MAXV queue rear v v進隊 模塊3 圖形結(jié)構(gòu) 94 while front rear 若隊列不空時循環(huán) front front 1 MAXV w queue front 出隊并賦給w p G adjlist w firstarc while p NULL if visited p adjvex 0 printf 2d p adjvex visited p adjvex 1 rear rear 1 MAXV queue rear p adjvex p p nextarc 模塊3 圖形結(jié)構(gòu) 95 例試以鄰接表為存儲結(jié)構(gòu) 分別寫出基于DFS和BPS遍歷的算法來判別頂點i和頂點j i j 之間是否有路徑 解 先置全局變量visited 為0 然后從頂點i開始進行某種遍歷 遍歷之后 若visited j 0 說明頂點i與頂點j之間沒有路徑 否則說明它們之間存在路徑 模塊3 圖形結(jié)構(gòu) 96 基于DFS遍歷的算法如下 intvisited MaxVertexNum intDFSTrave ALGraph G inti intj intk for k 0 kn k visited k 0 DFS G i 從頂點i開始進行深度優(yōu)先遍歷if visited j 0 return0 elsereturn1 模塊3 圖形結(jié)構(gòu) 97 基于BFS遍歷的算法如下 intvisited MaxVertexNum intDFSTrave ALGraph G inti intj intk for k 0 kn k visited k 0 BFS G i 從頂點i