數據結構與算法基礎(第三版)第九章數據結構總結.ppt

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

2、態(tài)數據結構 動態(tài)數據結構 順序存儲（數組實現） 鏈式存儲（指針） 游標（靜態(tài)鏈表）,C線性鏈表 表頭結點 單向鏈表 雙向鏈表 單向循環(huán)鏈表 雙向循環(huán)鏈表,D限定性數據結構： 棧 & 隊列,E棧 棧的概念 ADT棧 棧的存儲結構 棧的應用: 棧與遞歸 迷宮求解 表達式轉換與求值,F隊列 隊列的概念 ADT隊列 隊列的存儲結構 循環(huán)隊列,G線性表的應用： 多項式的表示 多項式相加運算,H串 串的基本概念 ADT串 串的存儲結構 存儲密度,I 數組 數組的概念 ADT數組 數組的存儲結構 數組的壓縮存儲：特殊矩陣、對角或帶狀矩陣、稀疏矩陣,J廣義表 基本概念 廣義表的存儲結構,第二章 樹與二元樹,A

3、樹的基本術語 樹 子樹 結點 分支 度 路 葉子 非終結（端）結點 終結（端）結點 兒子 父親 兄弟 堂兄弟 祖先 子孫結點； 層 高度（深度） 結點的順序 層序 有序樹 無序樹 森林,B二元樹 二元樹的定義，ADT二元樹，滿二元樹，完全二元樹 二元樹的遍歷：先序遍歷、中序遍歷和后序遍歷，層序遍歷 二元樹遍歷的非遞歸算法（先序、中序和后序） 二元樹的性質：（15） 二元樹的存儲結構：順序存儲、鏈式存儲（二叉鏈表） 線索二元樹：基本概念，先序、中序與后序線索 求線索二元樹的（先序、中序、后序）前驅與后繼結點 線索二元樹的遍歷 線索二元樹中插入、刪除結點的討論,D樹 ADT樹 樹的存儲結構：雙親表

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

5、成樹 先深生成森林 先廣生成森林 樹邊與回退邊 開放樹 最小生成樹及其算法（MST性質、Prim、Kruskal算法）,E無向圖的雙連通性 關結點 雙連通圖 雙連通分量,F有向圖的搜索 生成樹 生成森林 如何區(qū)別樹邊、向前邊、回退邊和 橫邊,G強連通性：強連通分量，歸約圖 ，圖的中心點的概念及求解方法,H拓撲分類 有向無環(huán)圖及其應用 拓撲分類 拓撲分類算法,I 關鍵路徑 事件 活動 AOE網 AOV網 路徑長度 關鍵活動 關鍵路徑 AOE網： (1)完成整個工程至少需要多少時間？ (2)哪些活動是影響工程進度的關鍵活動？ 關鍵路徑算法中的關鍵變量： 事件 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二元查找樹：什么叫二元查找樹、插入結點、刪除結點、查找結點 E散列法：哈稀函數 沖突 哈希表的長度 哈希函數：直接定址法 質數除余法 平方取中法 折疊法 數字分析法 隨機法 處理沖突：開放定址法（線性探測、二次探測） 再散列法 鏈地址法 建立公共溢出區(qū),第五章 查找,A基本概念

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

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

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