數(shù)據(jù)結(jié)構(gòu) A數(shù)據(jù)結(jié)構(gòu)總結(jié)學(xué)習(xí)課件

《數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)》課程回顧與總結(jié)第一章緒論A數(shù)據(jù)結(jié)構(gòu)研究對(duì)象信息數(shù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)對(duì)象數(shù)據(jù)類型B數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(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ù)型的實(shí)現(xiàn)抽象數(shù)據(jù)型的優(yōu)點(diǎn)多層次抽象技術(shù)E算法什么叫算法？算法的特征“好”的算法的評(píng)價(jià)標(biāo)準(zhǔn)對(duì)算法的正確性的要求算法的描述類語言F算法分析算法的時(shí)間特性時(shí)間復(fù)雜度T(n)空間復(fù)雜度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)①M(fèi)AKENULL(S)②TOP(S)③POP(S)④PUSH(x,S)⑤EMPTY(S)①M(fèi)AKENULL(Q)②FRONT(Q)③ENQUEUE(x,Q)④DEQUEUE(Q)⑤EMPTY(Q)①EMPTY(BT);②ISEMPTY(BT);③CREATEBT(V,LT,RT);④LCHILD(BT);⑤RCHILD(BT);⑥D(zhuǎn)ATA(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（）；建立一個(gè)空數(shù)組②RETRIEVE（array，index）；返回第index個(gè)元素③

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

。性質(zhì)3：對(duì)任意的非空二叉樹T

，如果葉結(jié)點(diǎn)的個(gè)數(shù)為n0，而其度為2

的結(jié)點(diǎn)數(shù)為n2，則：n0=n2+1

。性質(zhì)4：具有n

個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1。性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的二叉樹的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)i有：

⑴如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無雙親；如果i＞1，則其雙親結(jié)點(diǎn)是i/2；

⑵如果2i＞n，則結(jié)點(diǎn)i無左孩子結(jié)點(diǎn)，否則其左孩子結(jié)點(diǎn)是2i；

⑶如果2i+1＞n，則結(jié)點(diǎn)i無右孩子結(jié)點(diǎn)，否則其右孩子結(jié)點(diǎn)是2i+1。D樹

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

AOE網(wǎng)AOV網(wǎng)事件活動(dòng)路徑長(zhǎng)度關(guān)鍵活動(dòng)關(guān)鍵路徑

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

(2)哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵活動(dòng)？關(guān)鍵路徑算法中的關(guān)鍵變量：①事件Vj

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

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

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

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

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

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

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

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

(3)初始?xì)w并段的生成

m個(gè)初始段進(jìn)行2路歸并，需要log2m

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

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

在k

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

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