C++數(shù)據(jù)結(jié)構(gòu)整理

1、數(shù)據(jù)結(jié)構(gòu)整理作者：李逸凡參考書目：數(shù)據(jù)結(jié)構(gòu)( c+語言描述) 作者：朱戰(zhàn)力第一章 緒論1、基本術(shù)語(1) 數(shù)據(jù)：人們利用文字符號(hào)、數(shù)字符號(hào)以及其他規(guī)定的符號(hào)對現(xiàn)實(shí)世界的事物及其活動(dòng) 所做的抽象描述。(2) 數(shù)據(jù)元素：表示一個(gè)事物的一組數(shù)據(jù)。(3) 數(shù)據(jù)項(xiàng)：構(gòu)成數(shù)據(jù)元素的數(shù)據(jù)。(4) 抽象數(shù)據(jù)元素：沒有實(shí)際含義的數(shù)據(jù)元素。(5) 抽象數(shù)據(jù)類型：沒有確切定義的數(shù)據(jù)類型。(6) 數(shù)據(jù)的 邏輯結(jié)構(gòu) ：數(shù)據(jù)元素之間的相互聯(lián)系方式。分為三種：線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu) 。(7) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)方式。(8) 數(shù)據(jù)的操作：對一種數(shù)據(jù)類型的數(shù)據(jù)進(jìn)行的某種處理。一般從抽象和具體兩個(gè)方面去

2、討論。(9) 數(shù)據(jù)的 操作集合 ：對一種數(shù)據(jù)類型的數(shù)據(jù)進(jìn)行的 所有操作 。(10) 類型 是一 組值的集合。(11) 數(shù)據(jù)類型 是指一個(gè)類型和定義在這個(gè)類型上的操作集合。(12) 抽象數(shù)據(jù)類型 是指一個(gè) 邏輯概念上(用戶自定義) 的類型和這個(gè)類型上的操作集合。(13) 構(gòu)成抽象數(shù)據(jù)類型的三個(gè)要素為： _數(shù)據(jù)對象 _、 _數(shù)據(jù)關(guān)系、 _基本操作2、 算法及其時(shí)間復(fù)雜度1)2) 算法滿足以下性質(zhì)(1) 輸入性：具有 0 個(gè)或若干個(gè)輸入量；(2)輸出性：至少產(chǎn)生一個(gè)輸出或一個(gè)有意義的操作；(3) 有限性 ：執(zhí)行語句的序列是有限的；(4) 確定性 ：每一條語句的含義明確，無二義性(5)可執(zhí)行性：每一條

3、語句都應(yīng)在有限的時(shí)間內(nèi)完成。3) 算法設(shè)計(jì)應(yīng)該滿足的目標(biāo)：(1)正確性(2)可讀性(3)健壯性(4)高時(shí)間效率(5)高空間效率4) 計(jì)算時(shí)間復(fù)雜度 p27注意：時(shí)間復(fù)雜度的計(jì)算分為最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度，要注意題目在問哪一 種時(shí)間復(fù)雜度。5) 以下六種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的 其關(guān)系為： O(1)<O(logn)<O(n)<O(nlogn) <O(n2)<O(n3) 指數(shù)時(shí)間的關(guān)系為： O( 2n )<O(n!)<O( n n )6) 空間復(fù)雜度 :算法所需存儲(chǔ)空間的度量， 記作 S(n)=O(f(n)其中 n 為問題的規(guī)模 (或大小 )

4、7) 算法的存儲(chǔ)量：1輸入數(shù)據(jù)所占空間2程序本身所占空間3輔助變量所占空間 若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。第一章 線性表1、順序表類(1) 程序?qū)嵗?class SeqListprotected:DataType *list; int maxSize; int size;public:SeqList(int max=0); SeqList(void); int Size(void) const;void Insert(const DataType& item,int i);DataType Delete(const int i);DataType G

5、etData(int i) const; ;(2)順序表算法的優(yōu)缺點(diǎn)/ 數(shù)組/ 最大元素個(gè)數(shù)/ 當(dāng)前元素個(gè)數(shù)/ 構(gòu)造函數(shù)/ 析構(gòu)函數(shù)/ 取當(dāng)前數(shù)據(jù)元素個(gè)數(shù)/ 插入/ 刪除/ 取數(shù)據(jù)元素(1) 主要優(yōu)點(diǎn)是算法簡單，空間單元利用率高；(2) 主要缺點(diǎn)是需要預(yù)先確定數(shù)據(jù)元素的最大個(gè)數(shù)，插入和刪除時(shí)需要移動(dòng)較多的數(shù)據(jù)元 素。2、單鏈表類(1) 單鏈表算法的主要優(yōu)缺點(diǎn)(1) 主要優(yōu)點(diǎn)是不需要預(yù)先確定數(shù)據(jù)元素的最大個(gè)數(shù)，插入和刪除操作不需要移動(dòng)數(shù)據(jù)元 素(2) 主要缺點(diǎn)是每個(gè)結(jié)點(diǎn)中要有一個(gè)指針域，因此空間單元利用率不高。而且單鏈表操作 的算法也較復(fù)雜。3、循環(huán)鏈表(1) 循環(huán)單鏈表是單鏈表的另一種形式，

6、其結(jié)構(gòu)特點(diǎn)是鏈表中最后一個(gè)結(jié)點(diǎn)的指針域指向 整個(gè)鏈表的第一個(gè)結(jié)點(diǎn)， 從而使鏈表形成一個(gè)環(huán)。 它的優(yōu)點(diǎn)是從鏈尾到鏈頭比較方便。 循環(huán) 單鏈表也有帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)兩種結(jié)構(gòu)。4、雙向鏈表(1) 雙向鏈表是每個(gè)結(jié)點(diǎn)除后繼指針域外還有一個(gè)前驅(qū)指針域，它有帶頭結(jié)點(diǎn)和不帶頭結(jié) 點(diǎn)，循環(huán)和非循環(huán)結(jié)構(gòu)，雙向鏈表是解決查找前驅(qū)結(jié)點(diǎn)問題的有效途徑。(2) 循環(huán)雙向鏈表5、靜態(tài)鏈表( 1)在數(shù)組中增加一個(gè) (或兩個(gè) )指針域用來存放下一個(gè) (或上一個(gè) )數(shù)據(jù)元素在數(shù)組中的下 標(biāo)，從而構(gòu)成用數(shù)組構(gòu)造的單鏈表。 因?yàn)閿?shù)組內(nèi)存空間的申請方式是靜態(tài)的， 所以稱為靜態(tài) 鏈表，增加的指針稱做 仿真指針 。結(jié)構(gòu)如下：第二章 對

7、棧和隊(duì)列一、堆棧1、基本概念：( 1) 定義 :限定只能在 固定一端 進(jìn)行插入和刪除操作的線性表。特點(diǎn)：后進(jìn)先出。( 2) 允許進(jìn)行插入和刪除操作的一端稱為棧頂，另一端稱為棧底。(3) 操作集合：(1)Initiate(S) 初始化堆棧 S (2)Push(S,x)入棧 (3)Pop(S,d)出棧 (4)GetTop(S) 取棧頂數(shù)據(jù)元素(5)NotEmpty(S)= 堆棧 S非空否（4）標(biāo)識(shí)當(dāng)前棧頂位置的變量稱為棧頂指示器。2、運(yùn)算符問題 p72二、隊(duì)列1、隊(duì)列中允許進(jìn)行插入操作的是隊(duì)頭，允許進(jìn)行刪除操作的一端是隊(duì)尾。2、假溢出 順序隊(duì)列因多次入隊(duì)列和出隊(duì)列操作后出現(xiàn)的有存儲(chǔ)空間但不能進(jìn)行入

8、隊(duì)列操作的溢出。如何解決順序隊(duì)列的假溢出問題？ 可采取四種方法：1）采用循環(huán)隊(duì)列；2）按最大可能的進(jìn)隊(duì)操作次數(shù)設(shè)置順序隊(duì)列的最大元素個(gè)數(shù)；3）修改出隊(duì)算法，使每次出隊(duì)列后都把隊(duì)列中剩余數(shù)據(jù)元素向隊(duì)頭方向移動(dòng)一個(gè)位置；4）修改入隊(duì)算法，增加判斷條件，當(dāng)假溢出時(shí)，把隊(duì)列中的數(shù)據(jù)元素向?qū)︻^移動(dòng)， 然后方完成入隊(duì)操作。3、順序循環(huán)隊(duì)列中判斷隊(duì)滿隊(duì)空的方法（5）順序循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿判斷問題 新問題：在循環(huán)隊(duì)列中，空隊(duì)特征是 front=rear ；隊(duì)滿時(shí)也會(huì)有 front=rear ；判決條件將 出現(xiàn)二義性！解決方案有三： 使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù) （即隊(duì)列長度）； 常用方法 判隊(duì)滿： co

9、unt>0 && rear=front判隊(duì)空： count=0 加設(shè)標(biāo)志位，出隊(duì)時(shí)置 ,入隊(duì)時(shí)置 ,則可識(shí)別當(dāng)前 front=rear 屬于何種情況 判隊(duì)滿： tag=1 && rear=front判隊(duì)空： tag=0 && rear=front 少用一個(gè)存儲(chǔ)單元判隊(duì)滿： front= （rear+1）%MaxQueueSize判隊(duì)空： rear=front第三章串1、串的基本概念1）串長串中字符的個(gè)數(shù)（ n0）2）空串串中字符的個(gè)數(shù)為 0 時(shí)稱為空串3）空白串 由一個(gè)或多個(gè)空格符組成的串4）子串串 S中任意個(gè)連續(xù)的字符序列叫 S的子串 ;

10、 S叫主串5）子串位置 子串的第一個(gè)字符在主串中的序號(hào)。6）串相等 串長度相等，且對應(yīng)位置上字符相等。（即兩個(gè)串中的字符序列一一對應(yīng)相 等。）7）空串和空白串區(qū)別： 空串（Null String）是指長度為零的串； 空白串（Blank String）,是指包含一個(gè)或多個(gè)空白字符 '（空格鍵）的字符串 .8）“a”串 ，長度為的串。（它不僅要存儲(chǔ)字符 ，a'還要存儲(chǔ)該串的長度數(shù)據(jù)） a'字符 a。（只存儲(chǔ)字符a'）2、串的抽象數(shù)據(jù)集合：(1)數(shù)據(jù)集合：串的數(shù)據(jù)集合可以表示為字符序列s0,s1, ,s-n1，每個(gè)數(shù)據(jù)元素的數(shù)據(jù)類型為字符類型。(2) 操作集合：(1)

11、初始化串Initiate(S)(2)賦值A(chǔ)ssign(S,T)(3)求串長度Length(S) 不包括最后 0 的真實(shí)長度(4)比較Compare(S,T)(5)插入Insert(S,pos,T) pos 是從 0 開始算(6)刪除Delete(S,pos,len)(7)取子串SubString(S,pos,len)(8)查找子串Search(S,start,T)(9)替換子串Replace(S,start,T,V)3、C+用字符數(shù)組存儲(chǔ)串4、第四章 數(shù)組1、數(shù)組和線性表的比較 相同之處是它們都是若干個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1,a2,.,a0-1 構(gòu)成的 有限序列 。不同之處是：( 1

12、)數(shù)組要求其元素占用一塊 地址連續(xù)的內(nèi)存單元空間 ，而線性表無此要求； ( 2)線性表的元素是 邏輯意義上不可再分的元素 ，而數(shù)組中的每個(gè)元素還可以是一 個(gè)數(shù)組；(3) 數(shù)組的操作主要是向某個(gè)下標(biāo)的數(shù)組元素中存數(shù)據(jù)和取某個(gè)下標(biāo)的數(shù)組元素， 這和線性表的插入、刪除操作不同。2、特殊矩陣(1) 對稱矩陣：假設(shè)以一維數(shù)組 va 作為 n 階對稱矩陣 A 的壓縮存儲(chǔ)單元， k 為一維數(shù)組 v 的下標(biāo)序號(hào)， aij為n階對稱矩陣 A中 i行 j列的數(shù)據(jù)元素 (其中 1i,j )n， 其數(shù)學(xué)映射 關(guān)系為：（2）下三角矩陣： 假設(shè)以一維數(shù)組 sa作為 n 階下三角矩陣 A的壓縮存儲(chǔ)單元， k為一維數(shù) 組 v

13、a 的下標(biāo)序號(hào)， aij 為 n 階下三角矩陣 A 中 i 行 j 列的數(shù)據(jù)元素 （其中 1 i,j n ），其 數(shù)學(xué)映射關(guān)系為：3、稀疏矩陣（1） 概念1）稀疏矩陣 矩陣中非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素個(gè)數(shù)。2）稠密矩陣 一個(gè)不稀疏的矩陣。3）稀疏矩陣壓縮存儲(chǔ)方法 只存儲(chǔ)稀疏矩陣中的非零元素， 實(shí)現(xiàn)方法是 :將每個(gè)非零元素用一個(gè)三元組 （ i，j，aij） 來表示，則每個(gè)稀疏矩陣可用一個(gè)三元組線性表來表示。（2）稀疏矩陣的三元組鏈表（1）三元組鏈表 用鏈表存儲(chǔ)的三元組線性表。（2）行指針數(shù)組結(jié)構(gòu)的三元組鏈表 把每行非零元素三元組組織成一個(gè)單鏈表， 再設(shè)計(jì)一個(gè)指針類型的數(shù)組存儲(chǔ)所有單鏈表 的頭

14、指針。（3）三元組十字鏈表 把非零元素三元組按行和按列組織成單鏈表，這樣稀疏矩陣中的每個(gè)非零元素三元組 結(jié)點(diǎn)都將既勾鏈在行單鏈表上，又勾鏈在列單鏈表上，形成十字形狀。第七章1、樹二叉樹是一顆有序樹2、樹的結(jié)點(diǎn)之間的 邏輯關(guān)系 主要有雙親 -孩子關(guān)系，兄弟關(guān)系。因此，從結(jié)點(diǎn)之間的邏輯 關(guān)系分， 樹的 存儲(chǔ)結(jié)構(gòu) 主要有：雙親表示法、孩子表示法、 雙親孩子表示法和孩子兄弟表示 法四種組合。二叉樹1、基本特征 : 每個(gè)結(jié)點(diǎn)最多只有兩棵子樹(不存在度大于 2 的結(jié)點(diǎn))； 左子樹和右子樹次序不能顛倒。所以下面是兩棵不同的樹2、二叉樹的特殊性質(zhì)(1)具有 n個(gè)結(jié)點(diǎn)的完全二叉樹的深度 k為不超過 log2(n

15、+1)-1 的最大整數(shù)。 (注意第一層 的深度為 0)(2) 對于一棵有 n 個(gè)結(jié)點(diǎn)的完全二叉樹，按照從上至下和從左至右的順序?qū)λ薪Y(jié)點(diǎn)從 0 開始順序編號(hào) ,則對于序號(hào)為 i 的結(jié)點(diǎn) (0in),有：(1) 如果 i>0，則其雙親是結(jié)點(diǎn) (i-1)/2 (“ / ”表示整除) ；如果 i=0，則結(jié)點(diǎn) I是根結(jié)點(diǎn)，無 雙親。(2)如果 2i+1<n ，其左孩子是結(jié)點(diǎn) 2i+1；如果 2i+1n，則結(jié)點(diǎn) i 無左孩子。(3) 如果 2i2<n，其右孩子是結(jié)點(diǎn) 2i2；如果 2i2n，則結(jié)點(diǎn) i無右孩子。3、二叉樹的存儲(chǔ)結(jié)構(gòu)主要有三種：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和仿真指針存儲(chǔ)結(jié)構(gòu)

16、。 （1）二叉樹的順序存儲(chǔ)結(jié)構(gòu)完全二叉樹的結(jié)點(diǎn)可按從上至下和從左至右的次序存儲(chǔ)在一維數(shù)組中， 其結(jié)點(diǎn)之間的 關(guān)系可由公式計(jì)算得到，這就是二叉樹的順序存儲(chǔ)結(jié)構(gòu)。（2）二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用指針建立二叉樹中結(jié)點(diǎn)之間的關(guān)系。二叉樹最常用的的鏈 式存儲(chǔ)結(jié)構(gòu)是二叉鏈。 二叉鏈存儲(chǔ)結(jié)構(gòu)的每個(gè)結(jié)點(diǎn)包含三個(gè)域， 分別是數(shù)據(jù)域 data 、左孩子 指針域 leftChild 和右孩子指針域 rightChild 。（3）二叉樹的 仿真指針 存儲(chǔ)結(jié)構(gòu)是用數(shù)組存儲(chǔ)二叉樹中的結(jié)點(diǎn)，數(shù)組中每個(gè)結(jié)點(diǎn)除數(shù)據(jù)元 素域外，再增加仿真指針域用于仿真常規(guī)指針建立二叉樹中結(jié)點(diǎn)之間的關(guān)系。三、以節(jié)點(diǎn)類為基礎(chǔ)的二叉樹設(shè)計(jì)1. 二叉樹的

17、遍歷（具體實(shí)現(xiàn)見 169 面，必考）（1） 前序遍歷（ DLR）遞歸算法為： 若二叉樹為空則算法結(jié)束；否則： （ 1）訪問根結(jié)點(diǎn)；（ 2）前序遍歷根結(jié)點(diǎn)的左子樹；（ 3）前序遍歷根結(jié)點(diǎn)的右子樹。（2） 中序遍歷（ LDR）遞歸算法為： 若二叉樹為空則算法結(jié)束；否則： （ 1）中序遍歷根結(jié)點(diǎn)的左子樹； （ 2）訪問根結(jié)點(diǎn)； （ 3）中序遍歷根結(jié)點(diǎn)的右子樹。（3）后序遍歷（ LRD）遞歸算法為：若二叉樹為空則算法結(jié)束；否則：( 1)后序遍歷根結(jié)點(diǎn)的左子樹；( 2)后序遍歷根結(jié)點(diǎn)的右子樹；( 3)訪問根結(jié)點(diǎn)。2. 二叉樹的層序遍歷 二叉樹的層序遍歷算法如下：( 1)初始化設(shè)置一個(gè)隊(duì)列；( 2)把根結(jié)

18、點(diǎn)指針入隊(duì)列；( 3)當(dāng)隊(duì)列非空時(shí)，循環(huán)執(zhí)行步驟( 3.a)到步驟( 3.c)；( 3.a)出隊(duì)列取得一個(gè)結(jié)點(diǎn)指針，訪問該結(jié)點(diǎn)；( 3.b )若該結(jié)點(diǎn)的左子樹非空，則將該結(jié)點(diǎn)的左子樹指針入隊(duì)列；( 3.c )若該結(jié)點(diǎn)的右子樹非空，則將該結(jié)點(diǎn)的右子樹指針入隊(duì)列；( 4)結(jié)束。 具體實(shí)現(xiàn) template<class T> void LevelOrder(BiTreeNode<T>*&t,void (*visit)(T item)LinQueue<BiTreeNode<T>*> q;(考試中寫成 queue<BiTreeNode>

19、 q ) BiTreeNode<T> *p;q.Append(t);while(q.NotEmpty()p=q.Delete();visit(p->data); if(p->left()!=NULL) q.Append(p->left();if(p->right()!=NULL) q.Append(p->right();3. 二叉樹的撤銷操作4. 二叉樹的查找5. 二叉樹的非遞歸遍歷(必考) template<class T>void NotRecurPreOrder(BiTreeNode<T>*&t,void (*vi

20、sit)(T item) stack<BiTreeNode<T>*> stack; BiTreeNode<T> *p;stack.Push(t); while(stack.NotEmpty()p = stack.Pop();visit(p->data);if(p->right() != NULL)stack.Push(p->right();if(p->left() != NULL)stack.Push(p->left();6. 判斷二叉樹是否為完全二叉樹(必考) template<class T> bool IsCo

21、mplete(BiTreeNode<T>*& t) queue<BiTreeNode<T>*> q;BiTreeNode<T> *p;q.push(t); while(p=q.pop()!=NULL) q.push(p->left(); q.push(p->right();while(!q.empty()p=q.pop();if(p!=NULL) return false;return true;7. 線索二叉樹 （1）定義：當(dāng)某結(jié)點(diǎn)的左指針為空時(shí)，令該指針指向按某種方法遍歷二叉樹時(shí)得到的該結(jié) 點(diǎn)的前驅(qū)結(jié)點(diǎn)； 當(dāng)某結(jié)點(diǎn)的右指針

22、為空時(shí)， 令該指針指向按某種方法遍歷二叉樹時(shí)得到的該 結(jié)點(diǎn)的后繼結(jié)點(diǎn)。2）3)四、哈夫曼樹1. 定義：(1) 從 A結(jié)點(diǎn)到 B結(jié)點(diǎn)所經(jīng)過的分支序列叫做從 A結(jié)點(diǎn)到 B結(jié)點(diǎn)的 路徑 ；(2) 從 A結(jié)點(diǎn)到 B結(jié)點(diǎn)所經(jīng)過的分支個(gè)數(shù)叫做從 A結(jié)點(diǎn)到 B結(jié)點(diǎn)的 路徑長度 ；(3) 從二叉樹的根結(jié)點(diǎn)到二叉樹中所有葉結(jié)點(diǎn)的路徑長度之和稱作 該二叉樹的路徑長度(4) 設(shè)二叉樹有 n 個(gè)帶權(quán)值的葉結(jié)點(diǎn)，定義從二叉樹的根結(jié)點(diǎn)到二叉樹中所有葉結(jié)點(diǎn)的路徑 長度與相應(yīng)葉結(jié)點(diǎn)權(quán)值的乘積之和稱作該二叉樹的 帶權(quán)路徑長度( WPL)nWP w i li其中， wi 為第 i 個(gè)葉結(jié)點(diǎn)的權(quán)值L， = li 為從根結(jié)點(diǎn)到第 i

23、 個(gè)葉結(jié)點(diǎn)的路徑長度。2. 哈夫曼編碼3. 哈夫曼編碼的軟件設(shè)計(jì)1) 結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)2)3) 樹轉(zhuǎn)換為二叉樹的方法是： 樹中所有相同雙親結(jié)點(diǎn)的兄弟結(jié)點(diǎn)之間加一條連線。 對樹中不是雙親結(jié)點(diǎn)第一個(gè)孩子的結(jié)點(diǎn)， 只保留新添加的該結(jié)點(diǎn)與左兄弟結(jié)點(diǎn)之間的 連線，刪去該結(jié)點(diǎn)與雙親結(jié)點(diǎn)之間的連線。 整理所有保留的和添加的連線， 使每個(gè)結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)連線位于左孩子指針位置，使每個(gè)結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)連線位于右孩子指針位置。第八章 圖一、圖的基本概念和定義：1、 圖是由頂點(diǎn)集合及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)。圖G 的定義是：G =（ V，E）2、頂點(diǎn)和邊：圖中的結(jié)點(diǎn)稱作頂點(diǎn)，圖中的第 i個(gè)頂點(diǎn)記做

24、vi。兩個(gè)頂點(diǎn) vi和 vj相關(guān)聯(lián)稱 作頂點(diǎn) vi 和 vj 之間有一條邊，圖中的第 k 條邊記做 ek，ek =（ vi,vj ）或 vi,vj。3、有向圖和無向圖：在有向圖中，頂點(diǎn)對 x ,y 是有序的，頂點(diǎn)對 x,y稱為從頂點(diǎn) x 到頂點(diǎn) y 的一條有向邊，有向圖中的邊也稱作弧 ；在無向圖中，頂點(diǎn)對（ x,y）是無序的，頂點(diǎn)對（ x,y）稱為與頂點(diǎn) x 和頂點(diǎn) y 相關(guān)聯(lián)的一條邊。4、完全圖：在有 n 個(gè)頂點(diǎn)的無向圖中，若有 n（n-1）/2 條邊，即任意兩個(gè)頂點(diǎn)之間有且只有 一條邊，則稱此圖為無向完全圖；在有 n 個(gè)頂點(diǎn)的有向圖中，若有 n（n-1） 條邊，即任意兩個(gè) 頂點(diǎn)之間有且只有

25、方向相反的兩條邊，則稱此圖為有向完全圖。5、鄰接頂點(diǎn) ：在無向圖 G中，若（ u,v）是 E（G）中的一條邊，則稱 u和 v互為鄰接頂點(diǎn)， 并稱邊（ u,v）依附于頂點(diǎn) u 和 v；在有向圖 G 中，若 u,v 是 E（G）中的一條邊，則稱頂點(diǎn) u 鄰接到頂點(diǎn) v，頂點(diǎn) v鄰接自頂點(diǎn) u，并稱邊 u,v和頂點(diǎn) u 和頂點(diǎn) v相關(guān)聯(lián)。6、頂點(diǎn)的度：頂點(diǎn) v 的度是與它相關(guān)聯(lián)的邊的條數(shù)，記作TD（v）。7、路徑：在圖 G=（V,E）中，若從頂點(diǎn) vi 出發(fā)有一組邊使可到達(dá)頂點(diǎn) vj，則稱頂點(diǎn) vi 到頂點(diǎn) vj 的頂點(diǎn)序列為從頂點(diǎn) vi 到頂點(diǎn) vj 的路徑。8、權(quán)：有些圖的邊附帶有數(shù)據(jù)信息，這些

26、附帶的數(shù)據(jù)信息稱為權(quán)。帶權(quán)的圖也稱作網(wǎng)絡(luò)或 網(wǎng)。9、路徑長度：對于 不帶權(quán) 的圖，一條路徑的路徑長度是指該路徑上的 邊的條數(shù) ；對于帶權(quán) 的圖，一條路徑的路徑長度是指 該路徑上各個(gè)邊權(quán)值的總和 。10、子圖：設(shè)有圖 G1=V1,E1和圖 G2=V2,E2，若 V2V1 且 E2E1，則稱圖 G2 是圖 G1 的子 圖。11、連通圖和強(qiáng)連通圖：在無向圖中，若從頂點(diǎn)vi 到頂點(diǎn) vj 有路徑，則稱頂點(diǎn) vi 和頂點(diǎn) vj是連通的。如果圖中任意一對頂點(diǎn)都是連通的，則稱該圖是連通圖。圖中的無向圖 a 和 b 都是連通圖。12、在有向圖中，若對于任意一對頂點(diǎn) vi 和頂點(diǎn) vj（ vi ）vj都存在路徑

27、，則稱圖 G 是強(qiáng)連 通圖。圖中的有向圖 d 是強(qiáng)連通圖，強(qiáng)連通圖指的是任意一對頂點(diǎn)之間都是聯(lián)通的。13、生成樹：一個(gè)連通圖的最小連通子圖稱作該圖的生成樹。有n 個(gè)頂點(diǎn)的連通圖的生成樹有 n 個(gè)頂點(diǎn)和 n-1 條邊。14、簡單路徑和回路： 若路徑上各頂點(diǎn) v1,v2, ,v互m,不重復(fù)， 則稱這樣的路徑為簡單路徑； 若路徑上第一個(gè)頂點(diǎn) v1 與最后一個(gè)頂點(diǎn) vm 重合，則稱這樣的路徑為回路或環(huán) 。二、圖的存儲(chǔ)結(jié)構(gòu)1、 圖的存儲(chǔ)結(jié)構(gòu)主要有 鄰接矩陣 和鄰接表 兩種。2、 鄰接表：數(shù)組的 data 域存儲(chǔ)圖的頂點(diǎn)信息， sorce 域存儲(chǔ)該頂點(diǎn)在數(shù)組中的下標(biāo)序號(hào)， adj 域?yàn)樵擁旤c(diǎn)的鄰接頂點(diǎn)單鏈

28、表的頭指針。第 i 行單鏈表中的 dest 域存儲(chǔ)所有起始頂點(diǎn)為 vi 的鄰接頂點(diǎn) vj 在數(shù)組中的下標(biāo)序號(hào)， next 域?yàn)閱捂湵碇邢乱粋€(gè)鄰接頂點(diǎn)的指針域。如果 是帶權(quán)圖，單鏈表中需再增加 cost 域，用來存儲(chǔ)邊 <vi,vj>的權(quán)值 wij 。三、圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷1、 圖的深度優(yōu)先遍歷算法 鄰接矩陣存儲(chǔ)結(jié)構(gòu)圖類的深度優(yōu)先遍歷成員函數(shù)如下： void AdjMWGraph:DepthFirstSearch(const int v, int visited, void Visit(VerT item)/連通圖 G以 v為初始頂點(diǎn)序號(hào)、訪問操作為 Visit()的深度

29、優(yōu)先遍歷/ 數(shù)組 visited 標(biāo)記了相應(yīng)頂點(diǎn)是否已訪問過， 0 表示未訪問， 1 表示已訪問 Visit(GetValue(v);/ 訪問該頂點(diǎn)visitedv = 1;/ 置已訪問標(biāo)記int w = GetFirstNeighbor(v);/ 取第一個(gè)鄰接頂點(diǎn)while(w != -1)/ 當(dāng)鄰接頂點(diǎn)存在時(shí)循環(huán)if(! visitedw)DepthFirstSearch(w, visited, Visit);/ 遞歸w = GetNextNeighbor(v, w); / 取下一個(gè)鄰接頂點(diǎn)2、 非聯(lián)通圖的深度優(yōu)先遍歷算法void AdjMWGraph:DepthFirstSearch(v

30、oid Visit(VerT item)/ 非連通圖 G 訪問操作為 Visit()的深度優(yōu)先遍歷int *visited = new intNumOfVertices();for(int i = 0; i < NumOfVertices(); i+)visitedi = 0; / 初始化訪問標(biāo)記for(i = 0; i < NumOfVertices(); i+)if(! visitedi)DepthFirstSearch(i, visited, Visit); / 深度優(yōu)先遍歷delete visited;3、圖的廣度優(yōu)先算法 見課本 p210四、最小生成樹1、 一個(gè)有 n 個(gè)

31、頂點(diǎn)的連通圖的生成樹是原圖的極小連通子圖，它包含原圖中的所有n 個(gè)頂點(diǎn)，并且有保持圖連通的最少的邊。2、 普里姆算法時(shí)間復(fù)雜度 O（ n2）3、克魯斯卡爾算法時(shí)間復(fù)雜度： O（e loge）五、最短路徑1、迪克斯特 拉 算法時(shí)間復(fù)雜度 O( n2)第九章 排序一、定義： 排序是對數(shù)據(jù)元素序列建立某種有序排列的過程,是把一個(gè)數(shù)據(jù)元素序列整理成按關(guān)鍵字遞增(或遞減)排列的過程。 關(guān)鍵字 是要排序的數(shù)據(jù)元素集合中的一個(gè)域， 排序是以關(guān)鍵字為基準(zhǔn)進(jìn)行的 。 主關(guān)鍵字 :數(shù)據(jù)元素值不同時(shí) 該關(guān)鍵字的值也一定不同 ，是 能夠惟一區(qū)分各個(gè)不同數(shù)據(jù) 元素的關(guān)鍵字 ;不滿足主關(guān)鍵字定義的關(guān)鍵字稱為 次關(guān)鍵字 。

32、 內(nèi)部排序 是把待排數(shù)據(jù)元素 全部調(diào)入內(nèi)存 中進(jìn)行的排序。 外部排序 是因數(shù)量太大， 把 數(shù)據(jù)元素分批導(dǎo)入內(nèi)存 ，排好序后再分批導(dǎo)出到磁盤和磁帶 外存介質(zhì)上的排序方法。二、比較排序算法優(yōu)劣的標(biāo)準(zhǔn) :(1) 時(shí)間復(fù)雜度 :它主要是分析記錄關(guān)鍵字的 比較次數(shù) 和記錄的 移動(dòng)次數(shù)， 在大多數(shù)的排序 之中，最理想的狀態(tài)是把它對映成 一顆二叉樹 ，這樣，把 n 個(gè)數(shù)據(jù)元素均排列有序的最好時(shí) 間復(fù)雜度就是 O( nlog 2n )(2) 空間復(fù)雜度 :算法中使用的 內(nèi)存輔助空間 的多少，大多數(shù)的排序算法的空間復(fù)雜度是 O(1)(3) 穩(wěn)定性:若兩個(gè)記錄 A和B的關(guān)鍵字 值相等，但排序后 A、B的先后次序保

33、持不變 ，則 稱這種排序算法是穩(wěn)定的三、插入排序1、直接插入排序(1) 算法分析：(1)時(shí)間效率： 因?yàn)樵谧顗那闆r下，所有元素的比較次數(shù)總和為(0 1 n-1)2O( n 2 )。其他情況下也要考慮移動(dòng)元素的次數(shù)。 在最好的情況下時(shí)間復(fù)雜度為 O(n)故時(shí)間復(fù)雜度為 O(n)到 O(n2 )之間(2) 空間效率：僅占用 1 個(gè)緩沖單元 O(1)(3) 算法的穩(wěn)定性： 穩(wěn)定2、希爾排序(1) 基本思想： 原始數(shù)據(jù)元素集合越接近有序， 直接插入算法的效率越高，這個(gè)是希爾排 序算法成立的基礎(chǔ)四、選擇排序1、直接選擇排序（1）基本思想是： 從待排序的數(shù)據(jù)元素集合中選取關(guān)鍵字 最小 的數(shù)據(jù)元素并將它與原

34、始數(shù) 據(jù)元素集合中的 第一個(gè) 數(shù)據(jù)元素交換位置； 然后從不包括第一個(gè)位置上數(shù)據(jù)元素的集合中選 取關(guān)鍵字最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第二個(gè)數(shù)據(jù)元素交換位置； 如此重 復(fù)，直到數(shù)據(jù)元素集合中只剩一個(gè)數(shù)據(jù)元素為止。（2）算法分析時(shí)間效率：空間效率：O(n2)O(1)雖移動(dòng)次數(shù)較少，但比較次數(shù)仍多。沒有附加單元（僅用到 1 個(gè) temp）算法的穩(wěn)定性：不穩(wěn)定2、堆排序（1） 基本思想 :把待排序的數(shù)據(jù)元素集合構(gòu)成一個(gè)完全二叉樹結(jié)構(gòu)，則每次選擇出一個(gè)最大（或最?。┑臄?shù)據(jù)元素只需比較完全二叉樹的高度次，即log 2n 次，則排序算法的時(shí)間復(fù)雜度就是 O（ nlog 2n）。（2）堆分為最大堆

35、和最小堆兩種。（3）性質(zhì)： 最大堆的 根結(jié)點(diǎn)是堆中值最大 的數(shù)據(jù)元素，最小堆的 根結(jié)點(diǎn) 是堆中 值最小 的數(shù)據(jù)元 素，我們稱堆的根結(jié)點(diǎn)元素為堆頂元素。 對于最大堆， 從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)的路徑上， 數(shù)據(jù)元素組成的序列都是遞減有序 的； 對于最小堆， 從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)的路徑上， 數(shù)據(jù)元素組成的序列都是遞增有序 的。時(shí)間效率： O(nlog2n)。因?yàn)檎麄€(gè)排序過程中需要調(diào)用n-1 次堆頂點(diǎn)的調(diào)整，而每次堆排序算法本身耗時(shí)為 log2n；空間效率： O(1)。僅在第二個(gè) for 循環(huán)中交換記錄時(shí)用到一個(gè)臨時(shí)變量temp。穩(wěn)定性： 不穩(wěn)定。優(yōu)點(diǎn)：對小文件效果不明顯，但對大文件有效。五、交換排序1、

36、冒泡排序(1)2時(shí)間效率： O（ n ） 考慮最壞情況空間效率： O（1 ） 只在交換時(shí)用到一個(gè)緩沖單元穩(wěn) 定 性： 穩(wěn)定 25和25*在排序前后的次序未改變2、快速排序六、歸并排序七、基數(shù)排序第十章 查找一、 查找的基本概念1. 查找 :查詢關(guān)鍵字是否在 （數(shù)據(jù)元素集合）表中的過程。也稱作檢索。2. 主關(guān)鍵字 :能夠 唯一區(qū)分各個(gè)不同數(shù)據(jù)元素的關(guān)鍵字3. 次關(guān)鍵字 :通常不能唯一區(qū)分各個(gè)不同數(shù)據(jù)元素的關(guān)鍵字4. 查找成功 :在數(shù)據(jù)元素集合中找到了要查找的數(shù)據(jù)元素5. 查找不成功 :在數(shù)據(jù)元素集合中沒有找到要查找的數(shù)據(jù)元素6. 靜態(tài)查找 : 只查找，不改變數(shù)據(jù)元素集合內(nèi)的數(shù)據(jù)元素7. 動(dòng)態(tài)查找

37、 : 既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素8. 靜態(tài)查找表 :靜態(tài)查找時(shí)構(gòu)造的存儲(chǔ)結(jié)構(gòu)9. 動(dòng)態(tài)查找表 :動(dòng)態(tài)查找時(shí)構(gòu)造的存儲(chǔ)結(jié)構(gòu)10. 平均查找長度 :查找過程所需進(jìn)行的 關(guān)鍵字比較次數(shù)的平均值 ,是衡量查找算法效率的最主要標(biāo)準(zhǔn) ,其數(shù)學(xué)定義為：靜態(tài)查找表1、 靜態(tài)查找表主要有三種結(jié)構(gòu)：順序表、有序順序表、索引順序表2、順序表n n 1ASL 失敗Pi C i1n ni 1 i 1 n3、有序順序表（1）順序查找2）二分查找4、索引順序表3)相關(guān)術(shù)語 (1) 主表：要在其上建立索引表的順序表。(2) 完全索引表 : 和主表項(xiàng)完全相同 ，但只包含索引關(guān)鍵字和該數(shù)據(jù)元素在主表中位置信息 的索引表(3) 二級(jí)索引表 : 當(dāng)主表中的數(shù)據(jù)元素個(gè)數(shù)非常龐大時(shí)，按照建立索引表的同樣方法對索引 表再建立的索引表。二級(jí)以上的 索引結(jié)構(gòu)稱作多級(jí)索引結(jié)構(gòu)(4) 等長索引表 : 索引表中的每個(gè)索引項(xiàng)對應(yīng)主表中的數(shù)據(jù)元素個(gè)數(shù)相等 ;反之稱為 不等長索引表 。不等長索引表中的索引長度可隨著動(dòng)態(tài)插入和動(dòng)態(tài)