數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)(第三版)第九章數(shù)據(jù)結(jié)構(gòu)總結(jié).ppt

1、數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ) 課程回顧與總結(jié),第一章 緒論,A數(shù)據(jù)結(jié)構(gòu)研究對象 信息 數(shù)據(jù) 數(shù)據(jù)元素 數(shù)據(jù)項 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)對象 數(shù)據(jù)類型,B數(shù)據(jù)結(jié)構(gòu) 邏輯結(jié)構(gòu) 存儲結(jié)構(gòu)（物理結(jié)構(gòu)） 數(shù)據(jù)結(jié)構(gòu)分類,C數(shù)據(jù)結(jié)構(gòu)發(fā)展概況,D抽象數(shù)據(jù)型(ADT) 數(shù)據(jù)型、數(shù)據(jù)結(jié)構(gòu)與抽象數(shù)據(jù)型 抽象數(shù)據(jù)型的規(guī)格描述（語法、語義） 抽象數(shù)據(jù)型的實現(xiàn) 抽象數(shù)據(jù)型的優(yōu)點 多層次抽象技術(shù),E算法 什么叫算法？ 算法的特征 “好”的算法的評價標(biāo)準(zhǔn) 對算法的正確性的要求 算法的描述 類語言 F算法分析 算法的時間特性 時間復(fù)雜度T(n) 空間復(fù)雜度S(n),第二章 線性表,A線性表的概念 什么叫線性表 抽象數(shù)據(jù)型線性表,B線性表的實現(xiàn) 靜

2、態(tài)數(shù)據(jù)結(jié)構(gòu) 動態(tài)數(shù)據(jù)結(jié)構(gòu) 順序存儲（數(shù)組實現(xiàn)） 鏈?zhǔn)酱鎯Γㄖ羔槪?游標(biāo)（靜態(tài)鏈表）,C線性鏈表 表頭結(jié)點 單向鏈表 雙向鏈表 單向循環(huán)鏈表 雙向循環(huán)鏈表,D限定性數(shù)據(jù)結(jié)構(gòu)： 棧 & 隊列,E棧 棧的概念 ADT棧 棧的存儲結(jié)構(gòu) 棧的應(yīng)用: 棧與遞歸 迷宮求解 表達式轉(zhuǎn)換與求值,F隊列 隊列的概念 ADT隊列 隊列的存儲結(jié)構(gòu) 循環(huán)隊列,G線性表的應(yīng)用： 多項式的表示 多項式相加運算,H串 串的基本概念 ADT串 串的存儲結(jié)構(gòu) 存儲密度,I 數(shù)組 數(shù)組的概念 ADT數(shù)組 數(shù)組的存儲結(jié)構(gòu) 數(shù)組的壓縮存儲：特殊矩陣、對角或帶狀矩陣、稀疏矩陣,J廣義表 基本概念 廣義表的存儲結(jié)構(gòu),第二章 樹與二元樹,A

3、樹的基本術(shù)語 樹 子樹 結(jié)點 分支 度 路 葉子 非終結(jié)（端）結(jié)點 終結(jié)（端）結(jié)點 兒子 父親 兄弟 堂兄弟 祖先 子孫結(jié)點； 層 高度（深度） 結(jié)點的順序 層序 有序樹 無序樹 森林,B二元樹 二元樹的定義，ADT二元樹，滿二元樹，完全二元樹 二元樹的遍歷：先序遍歷、中序遍歷和后序遍歷，層序遍歷 二元樹遍歷的非遞歸算法（先序、中序和后序） 二元樹的性質(zhì)：（15） 二元樹的存儲結(jié)構(gòu)：順序存儲、鏈?zhǔn)酱鎯Γǘ骀湵恚?線索二元樹：基本概念，先序、中序與后序線索 求線索二元樹的（先序、中序、后序）前驅(qū)與后繼結(jié)點 線索二元樹的遍歷 線索二元樹中插入、刪除結(jié)點的討論,D樹 ADT樹 樹的存儲結(jié)構(gòu)：雙親表

4、示法，孩子表示法（鄰接表），樹的左右鏈表示 樹與二元樹的轉(zhuǎn)換，森林與二元樹的轉(zhuǎn)換 樹的遍歷：先序、中序和后序遍歷樹,E樹的應(yīng)用 用樹表示集合、判定樹、哈夫曼樹及其應(yīng)用、最優(yōu)編碼,C二元樹的相似與等價，二元樹的復(fù)制算法,第四章 圖以及與圖有關(guān)的算法,A圖的基本概念 圖的定義 ADT圖 有向圖 無向圖 弧 邊 頂點 鄰接點 相鄰 依附 環(huán)路 權(quán) 子圖 帶標(biāo)號的圖（網(wǎng)） 路徑 簡單路徑 連通圖 強連通圖 連通分量 強連通分量 完全圖 稀疏圖 稠密圖 度 入度 出度 生成樹,B圖的表示（存儲結(jié)構(gòu)）： 鄰接矩陣 鄰接表,C圖的遍歷（搜索）算法： 先深搜索（DFS） 先廣搜索（BFS）,D圖與樹的關(guān)系 生

5、成樹 先深生成森林 先廣生成森林 樹邊與回退邊 開放樹 最小生成樹及其算法（MST性質(zhì)、Prim、Kruskal算法）,E無向圖的雙連通性 關(guān)結(jié)點 雙連通圖 雙連通分量,F有向圖的搜索 生成樹 生成森林 如何區(qū)別樹邊、向前邊、回退邊和 橫邊,G強連通性：強連通分量，歸約圖 ，圖的中心點的概念及求解方法,H拓?fù)浞诸?有向無環(huán)圖及其應(yīng)用 拓?fù)浞诸?拓?fù)浞诸愃惴?I 關(guān)鍵路徑 事件 活動 AOE網(wǎng) AOV網(wǎng) 路徑長度 關(guān)鍵活動 關(guān)鍵路徑 AOE網(wǎng)： (1)完成整個工程至少需要多少時間？ (2)哪些活動是影響工程進度的關(guān)鍵活動？ 關(guān)鍵路徑算法中的關(guān)鍵變量： 事件 Vj 的最早可能發(fā)生時間 VE(j)；

6、 活動 ai 的最早可能開始時間 E(k)； 事件 Vk 的最遲發(fā)生時間 VL(k)； 活動 ai 的最遲允許開始時間 L(i)； 時間余量 L(i)-E(i)。,J最短路徑問題 單源最短路徑：Dijkstra算法 任意頂點間的最短路徑：Floyd算法、Warshall算法,B線性查找 C折半查找：條件 D分快查找 E二元查找樹：什么叫二元查找樹、插入結(jié)點、刪除結(jié)點、查找結(jié)點 E散列法：哈稀函數(shù) 沖突 哈希表的長度 哈希函數(shù)：直接定址法 質(zhì)數(shù)除余法 平方取中法 折疊法 數(shù)字分析法 隨機法 處理沖突：開放定址法（線性探測、二次探測） 再散列法 鏈地址法 建立公共溢出區(qū),第五章 查找,A基本概念

7、查找（檢索） 查找表 關(guān)鍵字 靜態(tài)查找 動態(tài)查找 平均查找長度,裝填因子標(biāo)志著哈希表的 裝滿程度，越小，發(fā)生沖 突的可能性越小，反之，發(fā) 生沖突的可能性越大。,G成功查找平均查找長度：ASLs 查找到散列表中已存在結(jié)點的平均比較次數(shù)。 H失敗查找平均查找長度：ASLu 查找失敗，但找到插入位置的平均比較次數(shù)。,C簡單的分類算法： 氣泡排序 插入排序 冒泡（選擇）排序 O(n2) DShell分類：縮小增量法 E快速分類: 快速分類的遞歸算法與非遞歸算法 F歸并分類 G堆 分 類：堆的概念 整理堆的算法 H基數(shù)分類（多關(guān)鍵字）,第六章 內(nèi)部排序（分類）,A排序（分類） 排序 內(nèi)部排序 外部排序

8、穩(wěn)定與不穩(wěn)定的排序方法,B影響分類性能的因素： 比較關(guān)鍵字的次數(shù)當(dāng)關(guān)鍵字是字符串時，是主要因素； 交換記錄位置和移動記錄的次數(shù)當(dāng)記錄很大時，是主要因素。,各種排序的比較,分析： (1) 平均時間性能； (2) 當(dāng)序列“基本有序”時，簡單排序中的插入排序最佳； (3) 基數(shù)排序適用于n值很大而關(guān)鍵字較小的序列； (4) 穩(wěn)定性以基數(shù)排序為最佳；,第七章 外部排序（分類）,B磁盤文件的歸并分類 (1) 多路歸并減少歸并遍數(shù) (2) 并行操作的緩沖區(qū)處理使輸入、輸出和CPU處理盡可能重疊 (3) 初始?xì)w并段的生成 m個初始段進行 2 路歸并，需要 log2m 遍歸并； 一般地，m 個初始段，采用k路

9、歸并，需要 logkm 遍歸并。顯然，k越大， 歸并遍數(shù)越少，可提高歸并的效率。 在 k 路歸并時，從 k個關(guān)鍵字中選擇最小記錄時，要比較K-1次。若記 錄總數(shù)為n，每遍要比較的次數(shù)為：n*(k-1) log2m/log2k 選擇樹或敗者樹，k路歸并時間 O(n log2m) ，與k無關(guān)。,A歸并方法：首先將文件中的數(shù)據(jù)輸入到內(nèi)存，采用內(nèi)部分類方法進行分類 （歸并段），然后將有序段寫回外存；對多歸并段（已有序） 進 行多遍合并（歸并），最后形成一個有序序列。,C磁帶文件的歸并分類：k 路平衡歸并分類。,第八章 文件,A文件及文件操作 文件的概念 關(guān)鍵字 主關(guān)鍵字 次關(guān)鍵字 文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu) 文件的操作：Insert Delete Modify Retrieve 檢索方式：實時 or 成批 更新方式：實時 or 成批 查詢方式：Q1:簡單查詢，Q2:范圍查詢，Q3:函數(shù)查詢，Q4:布爾查詢,B文件的組織 順序方式，索引方式，散列方式，鏈接方式，倒排方式,復(fù)習(xí)時注意幾個問題,知識的連貫性：認(rèn)真讀書、尊重教材、要注意參考其它教材,注意基本概念：名詞的理解、問題的研究對象,算法：（1）遍歷算法（線性表、樹與二元樹、圖）； （2）（結(jié)點）插入與刪除算法（線性表、線索二元樹、二元排序樹）； （3）注意圖中解決同一個問題的不同算法之間的區(qū)別； （4