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

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

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

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

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

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

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

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

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

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

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

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

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