數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)

1、第 1 章 緒 論 數(shù)據(jù)結(jié)構(gòu)基本概念1. 數(shù)據(jù)： 在計算機科學(xué)中是指所有能輸入到計算機中并能被計算機程序識別和處理的符號集合。2. 數(shù)據(jù)元素： 是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。 構(gòu)成數(shù)據(jù)元素的不可分割的最小單位稱為數(shù)據(jù)項。3. 數(shù)據(jù)對象： 是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。4. 數(shù)據(jù)結(jié)構(gòu)：是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。按照視點的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)。存儲結(jié)構(gòu)要存儲兩方面的內(nèi)容： 數(shù)據(jù)元素； 數(shù)據(jù)元素之間的邏輯關(guān)系。根據(jù)數(shù)據(jù)元素之間邏輯關(guān)系的不同，數(shù)據(jù)結(jié)構(gòu)分為四類： 集合 線性結(jié)構(gòu) 樹結(jié)構(gòu) 圖結(jié)構(gòu)會畫四種基本

2、數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)圖數(shù)據(jù)的存儲結(jié)構(gòu)又稱為物理結(jié)構(gòu)有兩種存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)的基本思想是：用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系是由元素的存儲位置來表示的。鏈接存儲結(jié)構(gòu)的基本思想是：用一組任意的存儲單元存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系是用指針來表示的。 算法及算法分析什么是算法通俗地講，算法是解決問題的方法；嚴格地說，算法是對特定問題求解步驟的一種描述，是指令的有限序列。算法必須滿足下列五個重要特性： 輸入： 輸出： 有窮性： 確定性： 可行性： 算法的描述方法常用的描述算法的方法常用的描述算法的方法有自然語言、流程圖、程序設(shè)計語言和偽代碼等。算法分析1度量算法效率的方

3、法一種方法是事后統(tǒng)計的方法，先將算法實現(xiàn)，然后輸入適當?shù)臄?shù)據(jù)運行，測算其時間和空間開銷。其缺點： 編寫程序?qū)崿F(xiàn)算法將花費較多的時間和精力； 所得實驗結(jié)果依賴于計算機的軟硬件等環(huán)境因素，有時容易掩蓋算法本身的優(yōu)劣。 另一種是事前分析估算的方法漸進復(fù)雜度，它是對算法所消耗資源的一種估算方法。2算法的時間復(fù)雜度問題規(guī)模問題規(guī)模是指輸入量的多少。運行算法所需要的時間T是問題規(guī)模n的函數(shù)?；菊Z句是執(zhí)行次數(shù)與整個算法的執(zhí)行次數(shù)成正比的語句。這種衡量效率的方法得出的不是時間量，而是一種增長趨勢的度量。即當只考察問題規(guī)模充分大時，算法中基本語句的執(zhí)行次數(shù)在漸近意義下的階，稱作算法的漸進時間復(fù)雜度，簡稱時間復(fù)

4、雜度，通常用大O（讀作“大歐”）記號表示。定義1-1 若存在兩個正的常數(shù)c和n0，對于任意nn0，都有T(n)c×f(n)，則稱T(n)=O(f(n)（或稱算法在O(f(n)中）。大O記號的含義:3最好、最壞和平均情況4算法的空間復(fù)雜度算法的空間復(fù)雜度是指在算法的執(zhí)行過程中，需要的輔助空間數(shù)量。輔助空間是除算法本身和輸入輸出數(shù)據(jù)所占據(jù)的空間外，算法臨時開辟的存儲空間。通常記作：S(n)=O(f(n)，其中，n為問題規(guī)模，分析方法與算法的時間復(fù)雜度類似。5. 算法分析舉例定理1-1 若A(n)=amnm +am-1nm-1 +a1n+a0是一個m次多項式，則A(n)=O(n m)。第

5、2 章 線 性 表 線性表的定義 線性表的順序存儲結(jié)構(gòu)及實現(xiàn)設(shè)順序表的每個元素占用c個存儲單元，則第i個元素的存儲地址為：LOC(ai)= LOC(a1)(i1)×c線性表的順序存儲結(jié)構(gòu)順序表順序表的實現(xiàn)建一個空的順序表順序表插入算法。順序表刪除算法。順序表查找算法 按位查找 按值查找 查找算法的時間復(fù)雜度。線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)線性表的鏈接存儲結(jié)構(gòu)單鏈表線性表的鏈接存儲結(jié)構(gòu)單鏈表的實現(xiàn)在單鏈表上按位查找 單鏈表的插入算法。插入算法的時間復(fù)雜度。單鏈表的構(gòu)造：即生成一個有n個結(jié)點的單鏈表。有兩種方法：頭插法和尾插法。 頭插法算法 尾插法算法刪除算法。 順序表和單鏈表的比較循環(huán)鏈表

6、雙鏈表雙鏈表的性質(zhì)第 3 章 棧、隊列棧的定義棧是限定僅在表尾進行插入和刪除操作的線性表。允許插入和刪除的一端稱為棧頂，另一端稱為棧底，不含任何數(shù)據(jù)元素的棧稱為空棧。 棧的順序存儲結(jié)構(gòu)及實現(xiàn) 棧的順序存儲結(jié)構(gòu)順序棧棧的順序存儲結(jié)構(gòu)稱為順序棧。 順序棧的實現(xiàn)順序棧入棧算法Push 順序棧出棧算法Pop在棧i中插入元素x的算法在棧i中刪除棧頂元素的算法棧的鏈接存儲結(jié)構(gòu)及實現(xiàn)1. 棧的鏈接存儲結(jié)構(gòu)鏈棧鏈棧的示意圖鏈棧中是否需要頭結(jié)點？為什么？2. 鏈棧的實現(xiàn)鏈棧的插入算法鏈棧的刪除算法 順序棧和鏈棧的比較 隊列的定義， 隊列的順序存儲結(jié)構(gòu)及實現(xiàn)1. 隊列的順序存儲結(jié)構(gòu)循環(huán)隊列隊列的假溢出及其解決循環(huán)

7、隊列2. 循環(huán)隊列的實現(xiàn)循環(huán)隊列的入隊算法，循環(huán)隊列的出隊算法隊列的鏈接存儲結(jié)構(gòu)及實現(xiàn)隊列的鏈接存儲結(jié)構(gòu)鏈隊列隊列的鏈接存儲結(jié)構(gòu)稱為鏈隊列。鏈隊列的實現(xiàn)創(chuàng)建鏈隊列的算法。入隊算法。 出隊算法循環(huán)隊列和鏈隊列的比較第4章 數(shù)組、串和廣義表數(shù)組的定義數(shù)組的特點數(shù)組的基本操作 存?。航o定一組下標，讀出對應(yīng)的數(shù)組元素； 修改：給定一組下標，存儲或修改與其相對應(yīng)的數(shù)組元素。存取和修改操作本質(zhì)上只對應(yīng)一種操作尋址數(shù)組的存儲結(jié)構(gòu)與尋址一維數(shù)組設(shè)一維數(shù)組的下標的范圍為閉區(qū)間l，h，每個數(shù)組元素占用 c 個存儲單元，則其任一元素 ai 的存儲地址可由下式確定： Loc(ai)Loc(al)(il)×c

8、 二Loc(aij)Loc(al1l2)(il1)×(h2l21)(jl2)×c維數(shù)組按行優(yōu)先存儲的尋址特殊矩陣和稀疏矩陣串和廣義表的定義第 5 章 樹和二叉樹樹的定義和基本術(shù)語1. 樹的定義2. 樹的基本術(shù)語結(jié)點的度、樹的度 葉子結(jié)點、分支結(jié)點孩子結(jié)點、雙親結(jié)點、兄弟結(jié)點路徑、路徑長度祖先、子孫結(jié)點的層數(shù)、樹的深度（高度）層序編號有序樹、無序樹森林 樹的遍歷操作1. 前序遍歷2. 后序遍歷3. 層序遍歷 樹的存儲結(jié)構(gòu)雙親表示法 孩子表示法 多重鏈表表示法 孩子鏈表表示法雙親孩子表示法孩子兄弟表示法 二叉樹的定義二叉樹具有五種基本形態(tài)： 空二叉樹； 只有一個根結(jié)點； 根結(jié)點

9、只有左子樹； 根結(jié)點只有右子樹； 根結(jié)點既有左子樹又有右子樹。會畫二叉樹的五種基本形態(tài)：幾種特殊的二叉樹： 斜樹 滿二叉樹 完全二叉樹 二叉樹的基本性質(zhì)性質(zhì)1 二叉樹的第i層上最多有2i-1個結(jié)點（i1）。 性質(zhì)2 在一棵深度為k的二叉樹中，最多有2k-1個結(jié)點，最少有k個結(jié)點。性質(zhì)3 在一棵二叉樹中，如果葉子結(jié)點的個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，則n0n21。 性質(zhì)4 具有n個結(jié)點的完全二叉樹的深度為。性質(zhì)5 對一棵具有n個結(jié)點的完全二叉樹中的結(jié)點從1開始按層序編號，則對于任意的編號為i（1in）的結(jié)點（簡稱為結(jié)點i），有： 如果i1，則結(jié)點i的雙親的編號為；否則結(jié)點i是根結(jié)點，無雙親；

10、 如果2in，則結(jié)點i的左孩子的編號為2i；否則結(jié)點i無左孩子； 如果2i1n，則結(jié)點i的右孩子的編號為2i1；否則結(jié)點i無右孩子。 不同組合根結(jié)點DD的左子樹LD的右子樹R前序LRD中序LDR后序LRD 二叉樹的遍歷操作二叉樹的組成：1. 前序遍歷2. 中序遍歷3. 后序遍歷4. 層序遍歷任意一棵二叉樹的遍歷序列都是唯一的。由二叉樹的前序遍歷序列和中序遍歷序列，唯一確定這棵二叉樹；由二叉樹的后序序列和中序序列也可唯一確定一棵二叉樹，但是，如果只知道二叉樹的前序序列和后序序列，則不能唯一地確定一棵二叉樹。 二叉樹的存儲結(jié)構(gòu)及實現(xiàn)1 順序存儲結(jié)構(gòu)2 二叉鏈表·前序遍歷的遞歸算法二叉樹前

11、序遍歷遞歸算法PreOrder前序遍歷的非遞歸算法二叉樹的前序遍歷非遞歸算法PreOrder·中序遍歷的遞歸算法： ·中序遍歷的非遞歸算法： ·后序遍歷的遞歸算法 二叉樹的建立算法 線索鏈表為什么要建立線索鏈表？基本概念：線索：線索二叉樹：線索鏈表：·線索鏈表的結(jié)點結(jié)構(gòu)為：前序線索鏈表中序線索鏈表后序線索鏈表。1中序線索鏈表的建立算法2在中序線索鏈表上查找結(jié)點p的后繼結(jié)點算法3在中序線索鏈表上查找結(jié)點p的前趨結(jié)點算法樹、森林與二叉樹的轉(zhuǎn)換1樹轉(zhuǎn)換為二叉樹將一棵樹轉(zhuǎn)換為二叉樹的方法是：2森林轉(zhuǎn)換為二叉樹將一個森林轉(zhuǎn)換為二叉樹的方法是： 哈夫曼樹及哈夫曼編碼

12、1. 哈夫曼樹葉子結(jié)點的權(quán)值二叉樹的帶權(quán)路徑長度哈夫曼樹哈夫曼算法的基本思想是：2. 哈夫曼編碼·等長編碼：·不等長編碼：·前綴編碼：第 6 章 圖 圖的定義和基本術(shù)語 在圖中，常常將數(shù)據(jù)元素稱為頂點，將頂點之間的關(guān)系用邊來表示。1. 圖的定義2. 圖的基本術(shù)語簡單圖鄰接、依附無向完全圖、有向完全圖稠密圖、稀疏圖頂點的度、入度、出度權(quán)、網(wǎng)路徑、路徑長度、回路簡單路徑、簡單回路子圖連通圖、連通分量強連通圖、強連通分量生成樹、生成森林圖的遍歷操作1. 深度優(yōu)先遍歷 2. 廣度優(yōu)先遍歷 圖的存儲結(jié)構(gòu)及實現(xiàn)6.2.1 鄰接矩陣1. 存儲方法： 建立一個無向圖的鄰接矩陣存儲的算法 2. 深度優(yōu)先遍歷5. 廣度優(yōu)先遍歷 鄰接表·存儲方法：vertexfirstedge adjvex next頂點表結(jié)點 邊表結(jié)點·結(jié)點結(jié)構(gòu)： 建立一個有向圖的鄰接表存儲的算法2. 深度優(yōu)先遍歷3. 廣度優(yōu)先遍歷算法 圖的連通性 生成樹生成樹可以在圖的遍歷過程中得到。 最小生成樹1. MST性質(zhì)2. Prim算法Prim算法的基本思想。 3. 克魯斯卡爾（Kruskal）算法 Kruskal算法的基本思想： 最短路徑1. 單