數(shù)據(jù)結構 A數(shù)據(jù)結構總結學習課件

《數(shù)據(jù)結構與算法基礎》課程回顧與總結第一章緒論A數(shù)據(jù)結構研究對象信息數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)項數(shù)據(jù)結構數(shù)據(jù)對象數(shù)據(jù)類型B數(shù)據(jù)結構邏輯結構存儲結構（物理結構）數(shù)據(jù)結構分類C數(shù)據(jù)結構發(fā)展概況D抽象數(shù)據(jù)型(ADT)

數(shù)據(jù)型、數(shù)據(jù)結構與抽象數(shù)據(jù)型抽象數(shù)據(jù)型的規(guī)格描述（語法、語義）抽象數(shù)據(jù)型的實現(xiàn)抽象數(shù)據(jù)型的優(yōu)點多層次抽象技術E算法什么叫算法？算法的特征“好”的算法的評價標準對算法的正確性的要求算法的描述類語言F算法分析算法的時間特性時間復雜度T(n)空間復雜度S(n)①INSERT(x,p,L)②LOCATE(x,L)③RETRIEVE(p,L)④DELETE(p,L)⑤PREVIOUS(p,L),NEXT(p,L)⑥MAKENULL(L)⑦FIRST(L)①MAKENULL(S)②TOP(S)③POP(S)④PUSH(x,S)⑤EMPTY(S)①MAKENULL(Q)②FRONT(Q)③ENQUEUE(x,Q)④DEQUEUE(Q)⑤EMPTY(Q)①EMPTY(BT);②ISEMPTY(BT);③CREATEBT(V,LT,RT);④LCHILD(BT);⑤RCHILD(BT);⑥DATA(BT);①NodeNewNode(G,v)②VoidDelNode(G,v)③VoidSetSucc(G,v1,v2)④VoidDelSucc(G,v1,v2)⑤ListofnodeSucc(G,v)⑥LisyofnodePred(G,v)⑦IntIsEdge(G,v1,v2)⑧NodeFirstAdjVex(G,v)⑨NodeNextAdjVex(G,v,w)①stringNULL();②booleanISNULL(S);③VoidIN(S,a);④intLEN(S);⑤VoidCONCAT(S1,S2);⑥stringSUBSTR(S,m,n);⑦booleanINDEX(S,S1);①CREATE（）；建立一個空數(shù)組②RETRIEVE（array，index）；返回第index個元素③

STORE（array，index，value）；在數(shù)組array中，為第index個元素賦值value第二章線性表A線性表的概念什么叫線性表抽象數(shù)據(jù)型線性表B線性表的實現(xiàn)靜態(tài)數(shù)據(jù)結構動態(tài)數(shù)據(jù)結構順序存儲（數(shù)組實現(xiàn)）鏈式存儲（指針）游標（靜態(tài)鏈表）C線性鏈表表頭結點單向鏈表雙向鏈表單向循環(huán)量表雙向循環(huán)鏈表D限定性數(shù)據(jù)結構：棧&隊列E棧棧的概念ADT棧棧的存儲結構棧的應用:棧與遞歸迷宮求解表達式轉換與求值F隊列隊列的概念ADT隊列隊列的存儲結構循環(huán)隊列G線性表的應用：多項式的表示多項式相加運算H串串的基本概念ADT串串的存儲結構存儲密度I數(shù)組數(shù)組的概念ADT數(shù)組數(shù)組的存儲結構數(shù)組的壓縮存儲：特殊矩陣、對角或帶狀矩陣、稀疏矩陣J廣義表基本概念廣義表的存儲結構第三章樹與二叉樹A樹的基本術語樹子樹結點分支度路葉子非終結（端）結點終結（端）結點兒子父親兄弟堂兄弟祖先子孫結點；層高度（深度）結點的順序層序有序樹無序樹森林B二叉樹二叉樹的定義，ADT二叉樹，滿二叉樹，完全二叉樹二叉樹的遍歷：先序遍歷、中序遍歷和后序遍歷，層序遍歷二叉樹遍歷的非遞歸算法（先序、中序和后序）二叉樹的性質：（1～5）二叉樹的存儲結構：順序存儲、鏈式存儲（二叉鏈表）線索二叉樹：基本概念，先序、中序與后序線索求線索二叉樹的（先序、中序、后序）前驅與后繼結點線索二叉樹的遍歷線索二叉樹中插入、刪除結點的討論性質1：在二叉樹中的第i層的結點數(shù)最多為：2i-1。性質2：高度為k的二叉樹其結點總數(shù)最多為2k－1(k≥1)

。性質3：對任意的非空二叉樹T

，如果葉結點的個數(shù)為n0，而其度為2

的結點數(shù)為n2，則：n0=n2+1

。性質4：具有n

個結點的完全二叉樹的深度為log2n+1。性質5：如果對一棵有n個結點的二叉樹的結點按層序編號，則對任一結點i有：

⑴如果i=1，則結點i是二叉樹的根，無雙親；如果i＞1，則其雙親結點是i/2；

⑵如果2i＞n，則結點i無左孩子結點，否則其左孩子結點是2i；

⑶如果2i+1＞n，則結點i無右孩子結點，否則其右孩子結點是2i+1。D樹

ADT樹樹的存儲結構：雙親表示法，孩子表示法（鄰接表），樹的左右鏈表示樹與二叉樹的轉換，森林與二叉樹的轉換樹的遍歷：先序、中序和后序遍歷樹E樹的應用用樹表示集合、判定樹、哈夫曼樹及其應用、最優(yōu)編碼C二叉樹的相似與等價，二叉樹的復制算法第四章圖以及與圖有關的算法A圖的基本概念圖的定義ADT圖有向圖無向圖弧邊頂點鄰接點相鄰依附環(huán)路權子圖帶標號的圖（網(wǎng)）路徑簡單路徑連通圖強連通圖連通分量強連通分量完全圖稀疏圖稠密圖度入度出度生成樹B圖的表示（存儲結構）：鄰接矩陣鄰接表C圖的遍歷（搜索）算法：先深搜索（DFS）先廣搜索（BFS）D圖與樹的關系生成樹先深生成森林先廣生成森林樹邊與回退邊開放樹最小生成樹及其算法（MST性質、Prim、Kruskal算法）E無向圖的雙連通性關結點雙連通圖雙連通分量F有向圖的搜索生成樹生成森林如何區(qū)別樹邊、向前邊、回退邊和橫邊G強連通性：強連通分量，歸約圖，圖的中心點的概念及求解方法H拓撲分類有向無環(huán)圖及其應用拓撲分類拓撲分類算法I關鍵路徑

AOE網(wǎng)AOV網(wǎng)事件活動路徑長度關鍵活動關鍵路徑

AOE網(wǎng)問題：(1)完成整個工程至少需要多少時間？

(2)哪些活動是影響工程進度的關鍵活動？關鍵路徑算法中的關鍵變量：①事件Vj

的最早可能發(fā)生時間VE(j)；②活動ai

的最早可能開始時間E(k)；③事件Vk的最遲發(fā)生時間VL(k)；④活動ai

的最遲允許開始時間L(i)；⑤時間余量L(i)-E(i)。J最短路徑問題單源最短路徑：Dijkstra算法任意頂點間的最短路徑：Floyd算法、Warshall算法B線性查找C折半查找：條件D分快查找EAVL樹FB-樹B+樹G二叉查找樹：什么叫二叉查找樹、插入結點、刪除結點、查找結點H散列法：哈稀函數(shù)沖突哈希表的長度哈希函數(shù)：直接定址法質數(shù)除余法平方取中法折疊法數(shù)字分析法隨機法處理沖突：開放定址法（線性探測、二次探測）再散列法鏈地址法建立公共溢出區(qū)第五章查找A基本概念查找（檢索）查找表關鍵字靜態(tài)查找動態(tài)查找平均查找長度二次探測法再散列法鏈地址法線性探測法查找失?。ú迦胗涗洠┎檎页晒μ幚頉_突方法L幾種處理沖突方法的平均查找長度裝填因子α標志著哈希表的裝滿程度，α越小，發(fā)生沖突的可能性越小，反之，發(fā)生沖突的可能性越大。J成功查找平均查找長度：ASLs

查找到散列表中已存在結點的平均比較次數(shù)。K失敗查找平均查找長度：ASLu

查找失敗，但找到插入位置的平均比較次數(shù)。I裝填因子：α=表中裝入的記錄數(shù)哈希表的長度查找分塊查找折半查找線性查找地址散列法/哈希表檢索平衡二叉樹/AVL樹減小二叉樹的高度，提高查找效率m-路查找樹增加寬度，減小高度，減少讀盤次數(shù)平衡樹B-/B+樹平衡m-路查找樹/BalancedTree二叉查找樹/二叉排序樹/二叉檢索樹動態(tài)查找理解概念掌握結構閱讀算法C簡單的分類算法：氣泡排序插入排序冒泡（選擇）排序

O(n2)DShell分類：縮小增量法E快速分類:快速分類的遞歸算法與非遞歸算法F歸并分類G堆分類：堆的概念整理堆的算法H基數(shù)分類（多關鍵字）第六章內部排序（分類）A排序（分類）排序內部排序外部排序穩(wěn)定與不穩(wěn)定的排序方法B影響分類性能的因素：比較關鍵字的次數(shù)—當關鍵字是字符串時，是主要因素；交換記錄位置和移動記錄的次數(shù)—當記錄很大時，是主要因素。各種排序的比較排序方法平均時間最好情況最壞情況輔助空間穩(wěn)定性簡單排序O(n2)O（n）O(n2)O(1)穩(wěn)定希爾排序O（n1.3）------O(1)不穩(wěn)定快速排序O(n·log2n)O(n·log2n)O(n2)O(1)不穩(wěn)定堆排序O(n·log2n)O(n·log2n)O(n·log2n)O(1)不穩(wěn)定歸并排序O(n·log2n)O(n·log2n)O(n·log2n)O(n)穩(wěn)定基數(shù)排序O(d·(n+r·d))O(d·(n+r·d))O(d·(n+r·d))O(n+r·d)穩(wěn)定分析：(1)平均時間性能；(2)當序列“基本有序”時，簡單排序中的插入排序最佳；(3)基數(shù)排序適用于n值很大而關鍵字較小的序列；(4)穩(wěn)定性以基數(shù)排序為最佳；第七章外部排序（分類）B磁盤文件的歸并分類

(1)多路歸并——減少歸并遍數(shù)

(2)并行操作的緩沖區(qū)處理——使輸入、輸出和CPU處理盡可能重疊

(3)初始歸并段的生成

m個初始段進行2路歸并，需要log2m

遍歸并；一般地，m個初始段，采用k路歸并，需要logkm

遍歸并。顯然，k越大，歸并遍數(shù)越少，可提高歸并的效率。

在k

路歸并時，從k個關鍵字中選擇最小記錄時，要比較K-1次。若記錄總數(shù)為n，每遍要比較的次數(shù)為：n*(k-1)[log2m/log2k]

選擇樹或敗者樹，k路歸并時間O(n·log2m)，與k無關。A歸并方法：首先將文件中的數(shù)據(jù)輸入到內存，采用內部分類方法進行分類（歸并段），然后將有序段寫回外存；對多歸并段（已有序）進行多遍合并（歸并），最后形成一個有序序列。C磁帶文件的歸并分類：k路平衡歸并分類。第八章文件A文件及文件操作文件的概念