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

1、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)第一章 緒論一、 基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)線性結(jié)構(gòu)、非線性結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、散列存儲(chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)類型、抽象數(shù)據(jù)類型。算法、語句的頻度、算法的時(shí)間復(fù)雜度、算法的漸進(jìn)復(fù)雜度空間復(fù)雜度二、 數(shù)據(jù)結(jié)構(gòu)概念：數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。數(shù)據(jù)的運(yùn)算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，是通過算法來描述的。數(shù)據(jù)運(yùn)算的實(shí)現(xiàn)依賴于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)分類方法：按數(shù)據(jù)元素間的邏輯關(guān)系分類：集合、線性、樹狀、圖狀或網(wǎng)狀按元素間的邏輯關(guān)系和施加的運(yùn)算分類（抽象數(shù)據(jù)類型）： 線性表、棧、隊(duì)列、串、數(shù)據(jù)、廣義表 樹、二叉樹、圖 查找

2、表 文件三、 算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度T(n):算法的時(shí)間消耗算法的時(shí)間消耗：所有語句的執(zhí)行次數(shù)（頻度）之和算法的漸進(jìn)時(shí)間復(fù)雜度（簡稱時(shí)間復(fù)雜度）：當(dāng)n->時(shí)，T(n)的數(shù)量級(jí)。即為T(n)中階最高的那一項(xiàng)，是算法中頻度最大的語句頻度。空間復(fù)雜度：除數(shù)據(jù)集合所需的空間外，為實(shí)現(xiàn)運(yùn)算所需的輔助空間的數(shù)量（級(jí)）。第二章 線性表一、線性表的邏輯特征數(shù)據(jù)元素在線性表中的相對(duì)位置是線性的，可以用一個(gè)連續(xù)的整數(shù)編碼來標(biāo)識(shí)，即數(shù)據(jù)元素在線性表中的位置只依賴于它們自己的序號(hào)，與數(shù)據(jù)元素的具體內(nèi)容無關(guān)。 二、對(duì)線性表的基本操作1、 初始化操作2、 求線性表的長度3、 取表中第i個(gè)元素:若1iLEN

3、GTH(L)，則函數(shù)值為給定線性表中第i個(gè)元素，否則為元素NULL。4、 定位函數(shù):返回元素x的位序。5、 INSERT（L，i,b）:前插函數(shù)。在第i 個(gè)元素前插入數(shù)據(jù)元素b。6、 DELETE（L，i）:刪除第i個(gè)數(shù)據(jù)元素。7、 刪除指針p指定的結(jié)點(diǎn)。三、線性表的順序存儲(chǔ)結(jié)構(gòu)（向量結(jié)構(gòu)）用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的元素。 特點(diǎn)：1、邏輯上相鄰的數(shù)據(jù)元素ai和ai+1的存儲(chǔ)位置也相鄰。即以數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系。 loc(ai)=loc(a1)+(i-1)*L loc(a1)是第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置，通常稱為線性表的起始地址或基地址。

4、 2、只要確定了存儲(chǔ)線性表的起始地址，就直接確定了線性表中任一數(shù)據(jù)元素的存儲(chǔ)位置，并且通過該公式實(shí)現(xiàn)對(duì)線性表元素的隨機(jī)存取（訪問）。 線性表順序存儲(chǔ)結(jié)構(gòu)的C描述線性表順序存儲(chǔ)結(jié)構(gòu)的操作1、定位操作：定位平均比較次數(shù)為(i)/n=(n+1)/2，算法的時(shí)間復(fù)雜度為O(n)。 不成功，則要比較n+1。2、 INSERT(v,i,b):前插操作，在第i個(gè)數(shù)據(jù)元素之前插入一個(gè)元素b。所需移動(dòng)元素次數(shù)的期望值（平均次數(shù)）為： Eis=pi(n-i+1)=(n(n+1)/2)/(n+1)=n/2 (i=1,2,n+1) 即：算法的時(shí)間復(fù)雜度為O(n).3、刪除運(yùn)算：在長度為n的線性表中刪除第i個(gè)元素。刪除

5、第i個(gè)元素移動(dòng)次數(shù)為n-i平均移動(dòng)次數(shù)為Ede=(n-i)/n=(n-1)/2 (i=1,2,.,n)刪除運(yùn)算的時(shí)間復(fù)雜度為O(n)缺點(diǎn)：插入刪除操作可能要移動(dòng)大量元素。四、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)：用一組任意的存儲(chǔ)單元存放線性表的數(shù)據(jù)元素（存儲(chǔ)單元可以不連續(xù)）。 數(shù)據(jù)元素間的邏輯關(guān)系表示：存儲(chǔ)一個(gè)指示其直接后繼的信息。 用獨(dú)立結(jié)點(diǎn)來存儲(chǔ)數(shù)據(jù)元素的信息和指示數(shù)據(jù)元素間的邏輯關(guān)系。 實(shí)現(xiàn)的C語言描述單鏈表的特點(diǎn) 1、頭指針：指示線性鏈表中第一個(gè)結(jié)點(diǎn)。 2、最后一個(gè)結(jié)點(diǎn)無后繼，其指針域設(shè)為“空”（NIL），表示鏈表到此結(jié)束。 3、結(jié)點(diǎn)指針域：把內(nèi)存中可能不連續(xù)的數(shù)據(jù)元素順序組成一個(gè)線性表。 4、要

6、訪問任一元素，必須從頭指針出發(fā)尋找，是順序訪問結(jié)構(gòu)。5、增設(shè)一個(gè)頭結(jié)點(diǎn)，作為線性表的第一個(gè)結(jié)點(diǎn)，可以簡化插入、刪除算法。線性鏈表的運(yùn)算1、在相鄰元素a和b之間插入一個(gè)值為x的數(shù)據(jù)元素的基本操作步驟：生成一個(gè)數(shù)據(jù)域值為x的結(jié)點(diǎn)s;使x結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)b: s->next=p->next;修改a結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)x:p->next=s;2、在第i個(gè)元素前插入一個(gè)元素x的步驟：生成一個(gè)數(shù)據(jù)域值為x的結(jié)點(diǎn)s;查找第i-1個(gè)接點(diǎn)p使x結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)p的后繼接點(diǎn): s->next=p->next;使p結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)s:p->next=s; 3、刪除第i

7、個(gè)結(jié)點(diǎn)。 實(shí)現(xiàn)：修改前驅(qū)結(jié)點(diǎn)(第i-1結(jié)點(diǎn))的指針域使其指向第i+1個(gè)結(jié)點(diǎn)。 插入和刪除運(yùn)算的關(guān)鍵：尋找前驅(qū)結(jié)點(diǎn)。在兩種運(yùn)算中，WHILE循環(huán)平均比較次數(shù)： (i)/(n+1)=(n+1)/2 （I=1,2,n+1）循環(huán)體的執(zhí)行次數(shù): (（i-1）/(n+1)=n/2 時(shí)間復(fù)雜度為(n)。 采用線性鏈表的優(yōu)點(diǎn)： 有效利用存儲(chǔ)資源，提高程序運(yùn)行的可靠性。有多少數(shù)據(jù)元素，才申請(qǐng)多少相應(yīng)的存儲(chǔ)空間。不使用的單元可歸還給系統(tǒng)。存儲(chǔ)密度 插入和刪除，不需移動(dòng)元素。3、循環(huán)鏈表 使最后一個(gè)結(jié)點(diǎn)的指針域又指向第一個(gè)結(jié)點(diǎn)或頭結(jié)點(diǎn)。這樣的線性鏈表就叫循環(huán)鏈表。特點(diǎn)：從任一結(jié)點(diǎn)出發(fā)，可以訪問表中所有其它結(jié)點(diǎn)。 為

8、了使得空表和非空表的運(yùn)算統(tǒng)一，設(shè)置一個(gè)表頭結(jié)點(diǎn)。它的值域或?yàn)榭? 用指向表尾結(jié)點(diǎn)的指針來表示循環(huán)鏈表的優(yōu)點(diǎn)4、雙向循環(huán)鏈表雙向鏈表：每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)指向直接前驅(qū)，一個(gè)指向直接后繼。雙向循環(huán)鏈表：在雙向鏈表中，若第一個(gè)結(jié)點(diǎn)（后頭結(jié)點(diǎn)）的前向指針指向最后一個(gè)結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的后向指針指向第一個(gè)結(jié)點(diǎn)（或頭結(jié)點(diǎn)），則就是雙向循環(huán)鏈表。雙向循環(huán)鏈表結(jié)點(diǎn)的插入：在P結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)S雙向循環(huán)鏈表結(jié)點(diǎn)的刪除 第三章 棧和隊(duì)列一、棧（stack）1、棧的定義：限定僅在表的一端進(jìn)行插入和刪除操作的線性結(jié)構(gòu)。 棧頂（top）： 允許進(jìn)行插入和刪除操作的一端。 2、棧的特點(diǎn)：后進(jìn)先出（或先進(jìn)后出）：L

9、ast In First OutLIFO3、棧的基本操作 INISTACK(s):初始化棧。設(shè)定一個(gè)空棧。EMPTY(S):判棧空函數(shù)。?？諘r(shí)返回真，否則返回假。PUSH（S，x）：入棧操作函數(shù)。在棧頂插入元素x。POP（S,&e）：出棧函數(shù)。若棧不空，返回棧頂元素值，并從棧中刪除該元素，否則返回空元素NULL。GETTOP（S,&e）：取棧頂元素函數(shù)。若棧不空，返回棧頂元素值，否則返回空元素NULL。4、棧的順序存儲(chǔ)表示及其實(shí)現(xiàn)用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。實(shí)現(xiàn)的C描述棧的初始化進(jìn)棧操作出棧操作 棧的“下溢”極其意義。5、棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 鏈表頭指針

10、用Top表示。 棧空時(shí)：Top=NIL 入棧：每當(dāng)一個(gè)元素進(jìn)棧時(shí)，申請(qǐng)一個(gè)新結(jié)點(diǎn)，插入到表頭。 出棧：每當(dāng)一個(gè)元素出棧時(shí)，從表頭釋放一個(gè)結(jié)點(diǎn)。 判斷進(jìn)棧、出棧序列的正確性 二、隊(duì)列（Queue）定義：隊(duì)列是一種先進(jìn)先出的線性表（結(jié)構(gòu)）。 特點(diǎn)：插入運(yùn)算在表的一端進(jìn)行。刪除運(yùn)算在表的另一端進(jìn)行。 隊(duì)頭：允許刪除的一端，用front表示。 隊(duì)尾：允許插入的一端，用rear表示。 3、隊(duì)列的基本操作INIQUEUE（Q）：初始化隊(duì)列，設(shè)置一個(gè)空隊(duì)列。EMPTY（Q）：判隊(duì)列空函數(shù)。隊(duì)列空，返回true,否則返回false。ENQUEUE（Q）：入隊(duì)操作，在隊(duì)列尾部插入一個(gè)元素。DEQUEUE（Q）：

11、出隊(duì)操作，若隊(duì)不空，出隊(duì)頭元素，并返回該元素值，否則返回NULL。4、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)-鏈隊(duì)列 C語言描述 頭指針-指向刪除的一端 尾指針-指向插入的一端 隊(duì)空時(shí)： 頭、尾指針為NULL,或都指向頭結(jié)點(diǎn)。 出隊(duì)操作要判斷尾指針的正確性5、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) 假上溢。 假上溢的原因是：頭指針和尾指針的值總是不斷增加，已使用過的存儲(chǔ)單元無法再使用。 解決假上溢的方法：循環(huán)隊(duì)列解決隊(duì)空隊(duì)滿都有頭尾指針相等問題： 1、一個(gè)標(biāo)志字段區(qū)分隊(duì)空隊(duì)滿 2、少用一個(gè)元素空間，個(gè)元素單元最多只存放個(gè)元素，且： front=rear -隊(duì)空 （rear+1）%m=front -隊(duì)滿3、長度記數(shù)器要能夠區(qū)分線性表、

12、棧、隊(duì)列的異同第四章 串一、串及其操作1、串的邏輯結(jié)構(gòu)定義：串（字符串）：是由個(gè)或多個(gè)字符組成的有限序列。 串的長度，空串，空格串、子串，主串、主串、字符在串中的位置、子串在串中的位置。2、串的基本操作判斷相等、求串長、聯(lián)接、串復(fù)制、求子串、串的模式匹配二、 串的存儲(chǔ)結(jié)構(gòu) 1、靜態(tài)存儲(chǔ)分配：分配一組連續(xù)的存儲(chǔ)單元存放串的字符序列。C語言可描述 2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)-動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)-塊鏈存儲(chǔ)結(jié)構(gòu) 存儲(chǔ)密度=串值所占存儲(chǔ)位/實(shí)際分配的存儲(chǔ)位3、堆分配與存儲(chǔ)映像第五章 數(shù)組和廣義表一、 數(shù)組的邏輯結(jié)構(gòu)特點(diǎn) 數(shù)組元素個(gè)數(shù)一個(gè)元素都受n個(gè)關(guān)系的約束,每個(gè)關(guān)系都是線性關(guān)系。每個(gè)數(shù)組元素屬于同一數(shù)據(jù)類型。每個(gè)數(shù)組

13、元素對(duì)應(yīng)于一組下標(biāo)，每個(gè)下標(biāo)有由一對(duì)界偶（ci,di）限定其范圍。數(shù)組的兩個(gè)定義1、一個(gè) n維數(shù)組被定義為一個(gè)線性表，其元素是一個(gè) n-1維數(shù)組。2、一個(gè) n維數(shù)組的數(shù)據(jù)元素受n個(gè)關(guān)系的約束，且每個(gè)關(guān)系都是線性的。二、對(duì)數(shù)組的操作： 給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素。 給定一組下標(biāo)，修改相應(yīng)數(shù)據(jù)中的某一個(gè)或幾個(gè)數(shù)據(jù)項(xiàng)的值。三、數(shù)組的順序存儲(chǔ)結(jié)構(gòu) 二維數(shù)組的兩種分配方式： 行主分配：先分配第一行的元素，以后每一行的元素緊跟其上一行的后面進(jìn)行分配。列主分配：先分配第一列的元素，以后每一列的元素緊跟其前一列的后面進(jìn)行分配。計(jì)算數(shù)組元素地址的公式 對(duì)于二維以上數(shù)組：行主分配為低下標(biāo)優(yōu)先。列主分配為高下

14、標(biāo)優(yōu)先：總是前面的下標(biāo)從小變到大，后面的下標(biāo)在增值。計(jì)算數(shù)組元素地址的公式四、矩陣的壓縮存儲(chǔ)1、 特殊矩陣：對(duì)稱矩陣、對(duì)角矩陣的壓縮存儲(chǔ)及其與一維數(shù)組下標(biāo)的對(duì)應(yīng)關(guān)系。2、 稀疏矩陣：三元組表三元組順序表。五、廣義表 1、特點(diǎn)：ai 可以單個(gè)元素，也可以是廣義表。 2、表頭、表尾的概念取列表表頭操作取列表表尾操作第六章 樹和二叉樹 一、樹（Tree）的定義、 遞歸定義-樹的固有特性 在任意一棵非空樹中：有一個(gè)特定的稱為根（root）的結(jié)點(diǎn)。當(dāng)n>1時(shí)，其余結(jié)點(diǎn)分為（>0）個(gè)互不相交的子集,每個(gè)集合本身又是一棵樹，并且稱為根的子樹、 非遞歸定義-從樹的結(jié)點(diǎn)間的直接關(guān)系看 在任意一棵非空

15、樹中：有且僅有一個(gè)沒有前驅(qū)的結(jié)點(diǎn)-根。當(dāng)n>1時(shí)，其余結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)。所有結(jié)點(diǎn)都可以有個(gè)或多個(gè)后繼。3、樹的基本術(shù)語: 樹的結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向子樹的分支(關(guān)系的表示)。 結(jié)點(diǎn)的度、樹葉、非葉結(jié)點(diǎn)、樹的度、結(jié)點(diǎn)的孩子、雙親結(jié)點(diǎn)的層次、樹的深度、有序樹、森林二、二叉樹（binery tree）1、二叉樹的定義：由一個(gè)根結(jié)點(diǎn)加上兩個(gè)互不相交的被稱為該根的左右兩個(gè)子樹組成。 2、二叉樹的特點(diǎn)：結(jié)點(diǎn)的度最大為（但不一定有度為2的結(jié)點(diǎn)）；子樹有左右之分，不能顛倒。3、二叉樹的五種形態(tài)4、二叉樹的特性第層的結(jié)點(diǎn)數(shù)最大為i-1；深度為的二叉樹的結(jié)點(diǎn)總數(shù)最大為k-1； 02+1；滿

16、二叉樹、完全二叉樹具有個(gè)結(jié)點(diǎn)的完全二叉樹深度為 (int)(log2n)+1具有個(gè)結(jié)點(diǎn)的完全二叉樹，對(duì)任一結(jié)點(diǎn)，1<=i<=n 有： i=1 根結(jié)點(diǎn)，無雙親 i>1 其雙親結(jié)點(diǎn)為 int(i/2) (PARENTi) 2i>n 結(jié)點(diǎn)i無左孩。否則結(jié)點(diǎn)i的左孩lchildi=2i 2i+1>n 結(jié)點(diǎn)i無右孩。否則結(jié)點(diǎn)i的右孩rchildi=2i+1 5、二叉樹的存儲(chǔ)結(jié)構(gòu) 、順序表示法 ：k 、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：二叉鏈表存儲(chǔ)結(jié)構(gòu)：（標(biāo)準(zhǔn)形式的存儲(chǔ)結(jié)構(gòu)）結(jié)點(diǎn)結(jié)構(gòu) 空指針個(gè)數(shù)三、遍歷二叉樹 1、遍歷二叉樹：指以一定的次序訪問二叉樹的每個(gè)結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)僅訪問一次。 DLR-前

17、序遍歷 先根遍歷 先序遍歷 LDR-中序遍歷 中根遍歷 LRD-后序遍歷 后根遍歷知道前序和中序，或知道中序和后序序列，構(gòu)造其二叉樹。通過某種遍歷方式：求二叉樹的深度、求葉結(jié)點(diǎn)數(shù)、求左右子樹的深度等 2、線索二叉樹 在中序遍歷過程中建立中序線索樹算法在中序線索二叉樹中求結(jié)點(diǎn)的前驅(qū)和后繼在中序線索二叉樹中刪除一個(gè)結(jié)點(diǎn)的算法。四、 樹和森林1、樹的二叉樹表示 2、由樹轉(zhuǎn)換成二叉樹有兩個(gè)特點(diǎn)： 根結(jié)點(diǎn)沒有右子樹。 轉(zhuǎn)換生成的二叉樹中各結(jié)點(diǎn)的右孩子是原樹中該結(jié)點(diǎn)的兄弟。3、森林轉(zhuǎn)換成二叉樹4、二叉樹轉(zhuǎn)換成森林5、樹的先根遍歷何后根遍歷及其與對(duì)應(yīng)二叉樹遍歷的關(guān)系，樹的層次遍歷五、哈夫曼樹及其應(yīng)用1、哈夫

18、曼樹-最優(yōu)二叉樹 路徑、路徑長度、樹的路徑長度、結(jié)點(diǎn)的帶權(quán)路徑長度、樹的帶權(quán)路徑長度哈夫曼樹；哈夫曼算法哈夫曼編碼第七章 圖一、基本概念1、圖的定義 （，）。2、概念：有向圖、無圖、無向完全圖、有向完全圖、稀疏圖、稠密圖、網(wǎng)、子圖。鄰接、頂點(diǎn)的度、頂點(diǎn)的入度、頂點(diǎn)的出度、圖的頂點(diǎn)的度與邊的關(guān)系；路徑、路徑長度、簡單路徑、回路、簡單回路 連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量、生成樹、連通圖的生成樹二、圖的存儲(chǔ)結(jié)構(gòu)1、鄰接矩陣表示法圖的順序存儲(chǔ)結(jié)構(gòu)用一個(gè)一維數(shù)組存儲(chǔ)數(shù)據(jù)元素（頂點(diǎn)）的信息。用一個(gè)二維數(shù)組來存儲(chǔ)數(shù)據(jù)元素之間的相鄰關(guān)系（邊或弧）的信息。鄰接矩陣表示的特點(diǎn)：無向圖的鄰接矩陣是對(duì)稱的。2

19、、鄰接表(adjacency list)表示法-圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 無向圖：個(gè)結(jié)點(diǎn)，條邊，個(gè)表頭結(jié)點(diǎn)，表結(jié)點(diǎn)。每個(gè)鏈表表結(jié)點(diǎn)的個(gè)數(shù)就是對(duì)應(yīng)頂點(diǎn)的度。 有向圖：表結(jié)點(diǎn)數(shù)等于邊數(shù)。 每個(gè)鏈表表結(jié)點(diǎn)的個(gè)數(shù)就是對(duì)應(yīng)頂點(diǎn)的出度。 若要求頂點(diǎn)的入度，必須對(duì)鄰接鏈表進(jìn)行掃描統(tǒng)計(jì)。 逆鄰接表：對(duì)每個(gè)頂點(diǎn)Vi建立一個(gè)以Vi為頭的弧的鏈表。 三、圖的遍歷1、圖的遍歷定義2、深度優(yōu)先搜索法-縱向優(yōu)先搜索法 圖的深度優(yōu)先搜索算法. 算法時(shí)間復(fù)雜度分析： 鄰接矩陣：對(duì)每個(gè)頂點(diǎn)，都要查遍所有的鄰接點(diǎn)，時(shí)間復(fù)雜度為O(n2)。 鄰接表：查找鄰接點(diǎn)的時(shí)間復(fù)雜度為O(e),整個(gè)算法的時(shí)間復(fù)雜度為O(n+e)。 3、廣度優(yōu)先搜索法

20、-橫向優(yōu)先搜索 圖的廣度優(yōu)先搜索算法.四、圖的連通性1、連通圖的生成樹：是連通圖的極小連通子圖，它包含圖中所有頂點(diǎn)，但只有構(gòu)成n個(gè)頂點(diǎn)的一棵樹的n-1條邊。深度優(yōu)先搜索樹、廣度優(yōu)先搜索樹。廣度優(yōu)先搜索樹的深度不大于深度優(yōu)先搜索樹生成森林。2、最小生成樹 邊賦以權(quán)值的圖稱為網(wǎng)或帶權(quán)圖。 最小生成樹 MST性質(zhì)。普里姆（Prim）算法：克魯斯卡爾(Kruskl)算法： 五、拓?fù)渑判?有向無環(huán)圖DAG圖拓?fù)溆行蛐蛄?、拓?fù)渑判蛲負(fù)渑判蚍椒?、最短路徑從某個(gè)源點(diǎn)到其余個(gè)頂點(diǎn)的最短路徑：迪杰斯特拉（Dijkstra）算法：按路徑長度遞增的次序產(chǎn)生最短路徑。第九章 查找查找表、靜態(tài)查找表、動(dòng)態(tài)查找表。關(guān)鍵字

21、查找：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字值等于給定值的數(shù)據(jù)元素或記錄（在列表中的位置）的過程。一、順序表的查找 哨兵元素。 查找操作的性能分析： 空間復(fù)雜度：O(1)，增加了一個(gè)元素的輔助空間。 時(shí)間復(fù)雜度：成功查找所需平均次數(shù)為： （）n(n+1)/(2n)=（n+1）/2 若八哨兵放在n+1的位置，算法如何實(shí)現(xiàn)。 二、有序表的查找折半查找有序表。元素按關(guān)鍵字非遞減（或非遞增）順序排列。查找方法：折半查找-二叉判定樹。優(yōu)點(diǎn)：效率高。不適合經(jīng)常的插入和刪除元素的表。折半查找條件：元素關(guān)鍵字非遞減有序，順序存儲(chǔ)結(jié)構(gòu) 三、索引順序查找-分塊查找分塊查找方法：將表中元素均勻地分成塊，塊間按

22、大小排序，塊內(nèi)可以不排序索引表中關(guān)鍵字按從小到大排序。各塊內(nèi)記錄可以按或不按關(guān)鍵字排序。 查找過程：第一步：根據(jù)給定值在索引表中進(jìn)行順序或折半查找。第二步：在塊中進(jìn)行順序查找。 查找效率：平均查找長度塊的最佳長度：sqrt()，平均查找長度sqrt(n)+1四、二叉排序樹特點(diǎn)：所有左子樹的結(jié)點(diǎn)值都小于根結(jié)點(diǎn)，所有右子樹的結(jié)點(diǎn)值都大于根結(jié)點(diǎn) 二叉排序樹的構(gòu)造方法； 對(duì)二叉排序樹按中序遍歷輸出每個(gè)結(jié)點(diǎn)的值，就得到了從小到大的排列順序。在二叉排序樹上插入結(jié)點(diǎn)的三個(gè)特點(diǎn)：無需遍歷樹，只需從根結(jié)點(diǎn)出發(fā)，走一條從根到葉結(jié)點(diǎn)的路徑。每次插入的新結(jié)點(diǎn)都是二叉排序樹的葉結(jié)點(diǎn)。這樣，在二叉排序樹上插入結(jié)點(diǎn)不必移動(dòng)

23、其它結(jié)點(diǎn)。二叉排序樹的構(gòu)造依賴于數(shù)據(jù)元素的插入次序，即同一組數(shù)，插入次序不同，構(gòu)造出的二叉排序樹也不同。五、B_樹B_樹的定義n個(gè)結(jié)點(diǎn)的B_樹的深度B_樹數(shù)據(jù)插入和刪除的基本要點(diǎn)六、哈希法查找（hashing search）-散列地址編碼法哈希函數(shù)哈希函數(shù)是一個(gè)壓縮函數(shù)?？赡軐?dǎo)致不同關(guān)鍵字值映射到同一散列地址的情況。 同義詞哈希函數(shù)構(gòu)造的基本方法 直接定址法 數(shù)字分析法 平方取中法 折疊法與移位法除留余數(shù)法模除取余法解決沖突的常用方法 開放定址法：線性探測再散列鏈地址法哈希表的查找及其分析查找過程中需與給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)取決于下面三種因素： 哈希函數(shù)：哈希函數(shù)的好壞首先影響沖突的頻繁程度。 處理沖突方法：對(duì)同一組關(guān)鍵字，哈希函數(shù)相同，則不同的沖突處理方法得到不同的哈希表，其平均查找程度也不相同。 哈希表的裝填因子：相同的哈希函數(shù)和相同的沖突處理方法，填滿程度不同，發(fā)生沖突的多少不同。裝滿程度用裝填因子表示：=表中填入的記錄數(shù)/哈希表的長度越小，產(chǎn)生沖突的可能性就越小。第十章 內(nèi)部排序-分類一、基本概念1、排序：將記錄關(guān)鍵字無序的序列調(diào)整為一個(gè)