數(shù)據(jù)結(jié)構(gòu)最新考研知識點(diǎn),完全貼合大綱講解

1、數(shù)據(jù)結(jié)構(gòu)知識點(diǎn)基本概念1.數(shù)據(jù) 能被計(jì)算機(jī)識別、存儲和加工處理的信息的載體。2. 數(shù)據(jù)元素?cái)?shù)據(jù)的基本單位，可由若干個(gè)數(shù)據(jù)項(xiàng)組成。例如，一 本書的書目信息為一個(gè)數(shù)據(jù)元素，而書目信息的每一 項(xiàng)（如書名，作者名等）為一個(gè)數(shù)據(jù)項(xiàng)。3. 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。它包括三 個(gè)要素：數(shù)據(jù)的邏輯結(jié)構(gòu)（數(shù)據(jù)之間的邏輯關(guān)系） 、 數(shù)據(jù)的存儲結(jié)構(gòu)（數(shù)據(jù)在計(jì)算機(jī)中的存儲方式）和數(shù) 據(jù)的運(yùn)算。4. 數(shù)據(jù)的邏輯結(jié)構(gòu)線性結(jié)構(gòu)：若結(jié)構(gòu)是非空集，則有且僅有一個(gè)開始 結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè) 直接前趨和一個(gè)直接后繼。 棧、隊(duì)列等都是線性結(jié)構(gòu)。非線性結(jié)構(gòu)：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直

2、接 后繼。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性 結(jié)構(gòu)。5. 數(shù)據(jù)的存儲結(jié)構(gòu)順序存儲 借助數(shù)據(jù)在連續(xù)的存儲空間中的相對位置表示元素 關(guān)系,通常用數(shù)組描述。鏈接存儲 借助數(shù)據(jù)元素的存儲地址的指針表示元素關(guān)系。索引存儲 儲存結(jié)點(diǎn)信息的同時(shí)，建立附加索引表， 。索引表由 若干索引項(xiàng)組成。索引項(xiàng)的一般形式是： （關(guān)鍵字、 地 址）。有稠密索引和稀疏索引。散列存儲 按結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出存儲地址第一章 棧、隊(duì)列和數(shù)組 一、棧和隊(duì)列的基本概念1. 棧(Stack) 1.1 概念 棧是僅在表的一端進(jìn)行插入和刪除運(yùn)算的線性表， 又稱棧為 LIFO 表(Last In First Out) 。棧的修改是按

3、后進(jìn)先出的原則進(jìn)行的。稱插入、刪除這一端為棧頂，另一端稱為棧底。表 中無元素時(shí)為空棧。通常棧有順序棧和鏈棧兩種存儲 結(jié)構(gòu)。1.2 棧的基本運(yùn)算 構(gòu)造空棧： InitStack(S) 判?？?: StackEmpty(S) 判棧滿： StackFull(S) 進(jìn)棧： Push(S,x) 退棧： Pop(S) 取棧頂元素： StackTop(S)2 隊(duì)列 (Queue)2.1 概念隊(duì)列是一種運(yùn)算受限的線性表，又稱作 FIFO 表 (First In First Out) ，插入在表的一端進(jìn)行，而刪除在 表的另一端進(jìn)行，隊(duì)列的操作原則是先進(jìn)先出的。 允許刪除的一端稱為隊(duì)頭 (front) ，允許插入

4、的一端 稱為隊(duì)尾 (rear) , 隊(duì)列也有順序存儲和鏈?zhǔn)酱鎯煞N存 儲結(jié)構(gòu)。2.2 隊(duì)列的基本運(yùn)算置空隊(duì)： InitQueue(Q)判隊(duì)空： QueueEmpty(Q)判隊(duì)滿： QueueFull(Q)入隊(duì)： EnQueue(Q,x)出隊(duì)： DeQueue(Q)取隊(duì)頭元素： QueueFront(Q)二、棧和隊(duì)列的順序存儲結(jié)構(gòu)1.棧的順序存儲結(jié)構(gòu)1.1概念開辟一組地址連續(xù)的存儲單元，依次存放自棧底到 棧頂?shù)臄?shù)據(jù)元素。設(shè)top指針指示棧頂元素的當(dāng)前位置。當(dāng)棧滿時(shí)，做進(jìn)棧運(yùn)算必定產(chǎn)生空間溢出，稱“上 溢”。 當(dāng)棧空時(shí)，做退棧運(yùn)算必定產(chǎn)生空間溢出，稱 “下溢”。上溢是一種錯(cuò)誤應(yīng)設(shè)法避免，下溢常用作

5、 程序控制轉(zhuǎn)移的條件。1.2基本運(yùn)算新元素入棧頂時(shí)：先入棧 , 再移指針 top=top+1 刪除元素時(shí)：先移指針 top=top-1,后刪棧頂元素 3 棧的長度： top-base2. 隊(duì)列的順序存儲結(jié)構(gòu)2.1 概念用一組地址連續(xù)的存儲單元依次存放從隊(duì)頭到隊(duì)尾的元素。 設(shè)隊(duì)頭指針為 front，指向隊(duì)頭元素隊(duì)尾指針為 rear，指向隊(duì)尾元素的下一個(gè)位。當(dāng) front=rear=0 ，表示空隊(duì)列。順序隊(duì)列中存在“假上溢”現(xiàn)象，由于入隊(duì)和出隊(duì) 操作使頭尾指針只增不減導(dǎo)致被刪元素的空間無法 利用，隊(duì)尾指針超過向量空間的上界而不能入隊(duì)。3 將隊(duì)列的頭、尾相連形成一個(gè)環(huán)，構(gòu)成循環(huán)隊(duì)列。并引 入數(shù)學(xué)中的

6、模運(yùn)算計(jì)算隊(duì)頭和隊(duì)尾指針。2.2基本運(yùn)算入隊(duì)操作：Q.baseQ.rear=x;Q.rear=(Q.rear+1)%MAXQSIZE;出隊(duì)操作： x=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;、棧和隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)1.棧的鏈?zhǔn)酱鎯Y(jié)構(gòu) 1.1 概念采用鏈?zhǔn)酱鎯Y(jié)構(gòu)稱鏈棧，并由其棧頂指針惟一確設(shè) ls為棧頂指針，棧 =(a1,a2,an)，a1 為棧底元素， an 為棧頂元素。1.2基本運(yùn)算建棧。Void initstack(linkstack *s) s-top=NULL;判?？铡nt stackempty (linkstack *s)retur

7、n s-top=NULL;3 進(jìn)棧。Void push(linkstack *s,datatype x)stacknode *p=(stacknode *)malloc(sizeof(stacknode); p-data=x;p-next=s-top;s-top=p;退棧。Datatype pop(linksatck *s)datatype x;stacknode *p=s-top;if(stackempty(s)error( “stack underflow” );x=p-data;s-top=p-next;free(p);return x;5 取棧頂元素。Datatype stacktop

8、(linkstack *s)if(stackempty(s)error( “stack is empty”);return s-top-data;2.隊(duì)的鏈?zhǔn)酱鎯Y(jié)構(gòu)2.1 概念 用鏈表示的隊(duì)列簡稱為鏈隊(duì)列。設(shè)兩個(gè)指針 front、 rear 分別指示隊(duì)頭和隊(duì)尾。為了鏈隊(duì)列的操作方便， 增加一個(gè)頭結(jié)點(diǎn)， front 指向頭結(jié)點(diǎn)， rear 指向隊(duì)尾元 素。如圖所示：2.2基本運(yùn)算建空隊(duì)Void initqueue(linkqueue *q)q-front=q-rear=NULL;判隊(duì)空。Int queueempty(linkqueue *q)return q-front=NULL&q-rear

9、=NULL;3 入隊(duì)。Void enqueue(linkqueue *q,datatype x)queuenode *p=(queuenode *)malloc(sizeof(queuenode); p-data=x; p-next=NULL; if(queueempty(q)q-front=q-rear=p;elseq-rear-next=p;q-rear=p;出隊(duì)。Datatype dequeue(linkqueue *q)datatype x;queuenode *p;if(queueempty(q)error( “queue is underflow”); p=q-front;x=p-

10、data;q-front=p-next;if(q-rear=p) q-rear=NULL; free(p);return x;5 取隊(duì)頭元素。Datatype queuefront(linkqueue *q) if(queueempty(q)error( “queue is empty”);return q-front-data;第二章 樹與二叉樹一、樹的基本概念1.樹是 n 個(gè)結(jié)點(diǎn)的有限集合，非空時(shí)必須滿足：只有 一個(gè)稱為根的結(jié)點(diǎn)；其余結(jié)點(diǎn)形成 m 個(gè)不相交的子 集，并稱根的子樹。2.樹的表示方法： 樹形表示法； 嵌套集合表示法； 3 凹入表表示法；廣義表表示法；3. 一個(gè)結(jié)點(diǎn)擁有的子樹數(shù)稱

11、為該結(jié)點(diǎn)的度；一棵樹的 度是指樹中結(jié)點(diǎn)最大的度數(shù)。4. 度為零的結(jié)點(diǎn)稱葉子或終端結(jié)點(diǎn)；度不為零的結(jié)點(diǎn) 稱分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)5. 根結(jié)點(diǎn)稱開始結(jié)點(diǎn)，根結(jié)點(diǎn)外的分支結(jié)點(diǎn)稱內(nèi)部結(jié) 點(diǎn)；6. 樹中某結(jié)點(diǎn)的子樹根稱該結(jié)點(diǎn)的孩子；該結(jié)點(diǎn)稱為 孩子的雙親；7.樹中存在一個(gè)結(jié)點(diǎn)序列 K1，K2， Kn，使 Ki 為 Ki+1 的雙親，則稱該結(jié)點(diǎn)序列為 K1 到 Kn 的路徑或 道路；8.樹中結(jié)點(diǎn) K 到 Ks 間存在一條路徑，則稱 K 是 Ks 的祖先， Ks 是 K 的子孫；9. 結(jié)點(diǎn)的層數(shù)從根算起，若根的層數(shù)為1，則其余結(jié)點(diǎn)層數(shù)是其雙親結(jié)點(diǎn)層數(shù)加 1；雙親在同一層的結(jié)點(diǎn)互為堂兄弟；樹中結(jié)點(diǎn)最大層數(shù)稱為樹

12、的高度或深 度；10. 樹中每個(gè)結(jié)點(diǎn)的各個(gè)子樹從左到右有次序的稱有 序樹，否則稱無序樹；11. 森林是 m 棵互不相交的樹的集合。二、二叉樹1. 二叉樹的定義及其主要特性1.1定義 樹中每個(gè)結(jié)點(diǎn)至多有兩棵子樹，且子樹有序。滿二叉樹是一棵深度為 k，結(jié)點(diǎn)數(shù)為 2k-1 的二叉樹； 3 完全二叉樹是至多在最下兩層上結(jié)點(diǎn)的度數(shù)可以 小于 2，并且最下層的結(jié)點(diǎn)集中在該層最左的位置的 二叉樹。1.2 二叉樹的五種基本形態(tài)1.3 二叉樹的主要特性二叉樹第 i 層上的結(jié)點(diǎn)數(shù)最多為 2i-1；深度為 k 的二叉樹至多有 2k-1 個(gè)結(jié)點(diǎn)；3 在任意二叉樹中， 葉子數(shù)為 n0，度為 2 的結(jié)點(diǎn)數(shù)為 n2，則 n

13、0=n2+1；1.4 滿二叉樹與完全二叉樹滿二叉樹深度為 k，且有 2k-1個(gè)結(jié)點(diǎn)。（對滿二叉樹中的結(jié)點(diǎn)約 定編號：自根起，從上到下，從左到右） 完全二叉樹 僅允許最下層右側(cè)分支不滿，若按從上到下，從左到 右為樹中結(jié)點(diǎn)編號，則與滿二叉樹相同。二者關(guān)系： 滿二叉樹是完全二叉樹。 完全二叉樹不一定是滿二叉樹1.5完全二叉樹性質(zhì) n個(gè)結(jié)點(diǎn)，深度為 K的完全二叉樹，其 K= log2N+1 對一棵 n個(gè)結(jié)點(diǎn)深度為 K 的完全二叉樹上的結(jié)點(diǎn)按 層次編碼（從第一層到第 K 層，從左到右），則樹中編 號為i的結(jié)點(diǎn) （1=i1時(shí)， i的雙親是 i/2 ； c: 當(dāng)2in時(shí)，i是葉點(diǎn)（無左孩子） ；當(dāng)2in時(shí)，

14、 i結(jié)點(diǎn)無右孩子；當(dāng) 2i+11 則雙親結(jié)點(diǎn)是 i/2 取整； 左孩子是 2i, 右孩子是 2i+1；（要小于 n） 3 i（n/2 取整）的結(jié)點(diǎn)是葉子； 奇數(shù)沒有右兄弟，左兄弟是 i-1 ；偶數(shù)沒有左兄弟， 右兄弟是 i+1。但順序存儲結(jié)構(gòu)適用于完全二叉樹 特點(diǎn)： 即不浪費(fèi)空間，又可以快速確定其結(jié)點(diǎn)的位置；對已 知的結(jié)點(diǎn) i，其左孩子為 2i，右孩子為 2i+1，雙親為 i/22.2 鏈?zhǔn)酱鎯Y(jié)構(gòu) 鏈表中每個(gè)結(jié)點(diǎn)至少含有三個(gè)域：數(shù)據(jù)域、左指針域 和右指針域。3. 二叉樹的遍歷根據(jù)訪問結(jié)點(diǎn)的次序不同可分為：先序遍歷 （ 前序 遍歷或先根遍歷 ） ，中序遍歷 （或中根遍歷 ）、后序遍 歷（ 或后

15、根遍歷 ） 。遍歷線索二叉樹。時(shí)間復(fù)雜度為 O（n）。先序：先訪問根結(jié)點(diǎn)，然后訪問左子樹，再訪問右子樹中序：先訪問左子樹，然后訪問根結(jié)點(diǎn)，再訪問右 子樹。后序：先訪問左子樹，然后訪問右子樹，再訪問根 結(jié)點(diǎn)。4. 線索二叉樹的基本概念和構(gòu)造4.1 概念利用二叉鏈表中的 n+1個(gè)空指針域存放指向某種遍歷 次序下的前趨和后繼結(jié)點(diǎn)的指針，這種指針稱線索。 加線索的二叉鏈表稱線索鏈表。相應(yīng)二叉樹稱線索二 叉樹。4.2 構(gòu)造、樹和森林1. 樹的存儲結(jié)構(gòu)雙親表示法（順序存儲結(jié)構(gòu)）：開辟一組連續(xù)空間 存儲樹的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示雙親結(jié)點(diǎn)的 雙親域。孩子表示法（鏈?zhǔn)酱鎯Y(jié)構(gòu)）：A.按樹的度設(shè)結(jié)點(diǎn)指針域。

16、B.按結(jié)點(diǎn)的度設(shè)結(jié)點(diǎn)指針域C.按孩子結(jié)點(diǎn)排成線性表3 孩子兄弟表示法（二叉樹表示法）：在這種表示法 中，樹中每個(gè)結(jié)點(diǎn)有三個(gè)域。數(shù)據(jù)域：存放結(jié)點(diǎn)數(shù)據(jù)左指針域：指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn) 右指針域：指向該結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)2. 森林與二叉樹的轉(zhuǎn)換二叉樹和樹都可以用二叉鏈表作為其存儲結(jié)構(gòu)。因 此，以二叉鏈表作為中間介，可以導(dǎo)出樹與二叉樹之 間存在對應(yīng)關(guān)系。一棵樹與惟一的一棵二叉樹一一對 應(yīng)。2.1 樹轉(zhuǎn)換成二叉樹保持雙親和第一個(gè)孩子連線，其他連線去掉； 兄弟之間連線；3 使右兄弟結(jié)點(diǎn)成為右孩子， 使第一個(gè)孩子成為左孩 子。2.2 森林轉(zhuǎn)換為二叉樹將每棵樹轉(zhuǎn)化為二叉樹；將各棵二叉樹的根相連；3 使二叉樹

17、的根成為右孩子。2.3 二叉樹轉(zhuǎn)換成森林若某結(jié)點(diǎn)是其父結(jié)點(diǎn)的左孩子，則把該結(jié)點(diǎn)的右孩 子、右孩子的右孩子、 ，都與該結(jié)點(diǎn)的父結(jié) 點(diǎn)用線線連；去掉樹中所有父結(jié)點(diǎn)到其右孩子的連線，生成森 林。3. 樹和森林的遍歷3.1 樹的遍歷先根遍歷 先訪問樹根，再依次先根遍歷根的每棵子樹。后根遍歷 先依次后根遍歷根的每棵子樹，再訪問樹根。二叉樹（續(xù)上例）先序：ABCEFD 中牙:BEFCDA結(jié)論: 樹的先根遍歷相當(dāng)于其轉(zhuǎn)化的二叉樹的先序遍歷: 樹的后根遍歷相當(dāng)于其轉(zhuǎn)化的二叉樹的中序遍歷;3.2 森林的遍歷 先序（ 先根 ） 遍歷森林中序（后根）遍歷森林例:先根:ABCDEFGHJIK （二叉樹的先序） 后根:

18、BADEFCJHKIG （二叉樹的中廟）森林轉(zhuǎn)化的二叉樹:四、樹與二叉樹的應(yīng)用1. 概念：樹的路徑長度是從樹根到每一結(jié)點(diǎn)的路徑長度之 和。將樹中的結(jié)點(diǎn)賦予實(shí)數(shù)稱為結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑是該結(jié)點(diǎn)的路徑長度與權(quán)的乘積。 樹的帶權(quán)路徑長度又稱樹的代價(jià)，是所有葉子的帶權(quán) 路徑長度之和。帶權(quán)路徑長度最小的二叉樹稱最優(yōu)二 叉樹（ 哈夫曼樹 ）。3 具有2n-1 個(gè)結(jié)點(diǎn)其中有 n個(gè)葉子，并且沒有度為 1 的分支結(jié)點(diǎn)的樹稱為嚴(yán)格二叉樹。對字符集編碼時(shí)，要求字符集中任一字符的編碼都 不是其它字符的編碼前綴，這種編碼稱前綴碼。5 字符出現(xiàn)頻度與碼長乘積之和稱文件總長； 字符出 現(xiàn)概率與碼長乘積之和稱平均碼長；6

19、 使文件總長或平均碼長最小的前綴碼稱最優(yōu)前綴碼利用哈夫曼樹求最優(yōu)前綴碼，左為 0，右為 1。編碼 平均碼長最??；沒有葉子是其它葉子的祖先，不可能 出現(xiàn)重復(fù)前綴。2. 哈夫曼樹構(gòu)造算法 )根據(jù)給定的 n個(gè)權(quán)值 w1,w2, ,wn 構(gòu)成 n棵二叉樹 的集合F=T1,T2, ,Tn ，其中每棵二叉樹 Ti 中只有 一個(gè)帶權(quán)為 wi 的根結(jié)點(diǎn)，其左右子樹為空。在 F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子 樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的 權(quán)值為左右子樹上根結(jié)點(diǎn)的權(quán)值之和。3 在F中刪除這兩棵樹， 同時(shí)將新得到的二叉樹加入 F 中。 重復(fù)和 3 ，直到 F只含一棵樹為止。 這棵樹便是

20、哈夫曼樹。3. 前綴碼給定一個(gè)碼的集合序列，若沒有一個(gè)序列是另一個(gè)序列的前綴，則稱這個(gè)集合中的碼為前綴碼。例：000, 00b Ob 10, 11詢細(xì)刈乂容易翻譯。0, I, 10, 11不是前綴碼 特點(diǎn)：前綴碼是碼長不等的編碼，既可以縮短報(bào)文的長度第四章 圖一、圖的基本概念1. 圖：圖 G 是由頂點(diǎn)集 V 和邊集 E 組成，頂點(diǎn)集是有 窮非空集，邊集是有窮集；2. G 中每條邊都有方向稱有向圖；有向邊稱?。贿叺?始點(diǎn)稱弧尾；邊的終點(diǎn)稱弧頭； G 中每條邊都沒有方 向的稱無向圖。3. 頂點(diǎn) n 與邊數(shù) e 的關(guān)系：無向圖的邊數(shù) e 介于 0n(n-1)/2 之間，有 n(n-1)/2 條邊的稱

21、無向完全圖； 有向圖的邊數(shù) e 介于 0n(n-1)之間，有 n(n-1)條邊的 稱有向完全圖；4. 無向圖中頂點(diǎn)的度是關(guān)聯(lián)與頂點(diǎn)的邊數(shù)；有向圖中 頂點(diǎn)的度是入度與出度的和。所有圖均滿足：所有頂點(diǎn)的度數(shù)和的一半為邊數(shù)。5. 圖 G(V，E)，如 V是 V 的子集， E是 E 的子集， 且 E中關(guān)聯(lián)的頂點(diǎn)均在 V中，則 G (V ,E是)G 的子 圖。6. 在有向圖中，從頂點(diǎn)出發(fā)都有路徑到達(dá)其它頂點(diǎn)的 圖稱有根圖；7. 在無向圖中，任意兩個(gè)頂點(diǎn)都有路徑連通稱連通圖； 極大連通子圖稱連通分量；8. 在有向圖中，任意順序兩個(gè)頂點(diǎn)都有路徑連通稱強(qiáng)連通圖；極大連通子圖稱強(qiáng)連通分量；9. 將圖中每條邊賦上

22、權(quán)，則稱帶權(quán)圖為網(wǎng)絡(luò)二、圖的存儲及基本操作1. 鄰接矩陣表示法用一維數(shù)組存儲圖中頂點(diǎn)的信息； 用矩陣（二維數(shù)組）表示圖中各頂點(diǎn)之間的相鄰關(guān)系2. 鄰接表法構(gòu)造方法： 與同一頂點(diǎn)鄰接的所有鄰接點(diǎn)構(gòu)成一個(gè)單鏈表，用表 結(jié)點(diǎn)描述； 各鏈表設(shè)置表頭結(jié)點(diǎn)，由頭結(jié)點(diǎn)描述； 各表頭結(jié)點(diǎn)構(gòu)成一個(gè)順序表。3. 鄰接矩陣表示法與鄰接表表示法的比較鄰接矩陣是唯一的，鄰接表不唯一；存儲稀疏圖用鄰接表，存儲稠密圖用鄰接矩陣；3 求無向圖頂點(diǎn)的度都容易， 求有向圖頂點(diǎn)的度鄰接 矩陣較方便；判斷是否是圖中的邊，鄰接矩陣容易，鄰接表最壞 時(shí)間為 O(n) ；5 求邊數(shù) e，鄰接矩陣耗時(shí)為 O(n2)，與 e 無關(guān)，鄰 接表的

23、耗時(shí)為 O(e+n)；三、圖的遍歷1. 深度優(yōu)先搜索( DFS)搜索策略：訪問當(dāng)前頂點(diǎn) vi ，尋找與 vi 相鄰且未被訪問頂點(diǎn)vj ，若存在，將其作為當(dāng)前點(diǎn)，訪問，并重復(fù)上述搜 尋過程。否則(所有鄰接點(diǎn)都被訪問過)，退回一步，尋找 與前一個(gè)頂點(diǎn)相鄰的未被訪問頂點(diǎn)，訪問，并重復(fù)上 述過程。若上述過程無法訪問圖中的所有頂點(diǎn)，則另選一個(gè) 新頂點(diǎn)重新開始。深度優(yōu)先搜索是一種縱向搜索的過程。2. 廣度優(yōu)先搜索( BFS)訪問出發(fā)點(diǎn) v0，依次訪問 v0的各個(gè)未曾訪問過的鄰 接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)重復(fù)上述過程。若上述過程無法訪問圖中的所有頂點(diǎn)，則另選一個(gè) 新頂點(diǎn)重新開始。廣度優(yōu)先搜索是一種橫向搜

24、索的過程。 使用隊(duì)列結(jié)構(gòu)。四、圖的基本應(yīng)用1. 概念將沒有回路的連通圖定義為樹稱自由樹。 生成樹：連通圖 G 的一個(gè)子圖若是一棵包含 G 中 所有頂點(diǎn)的樹，該子圖稱生成樹。有 DFS 生成樹和 BFS 生成樹， BFS 生成樹的高度最小。非連通圖生成 的是森林。3 最小生成樹：連通網(wǎng) G=(V,E)，邊是帶權(quán)的，因而 G 的生成樹的各邊也是帶權(quán)的。將生成樹的各邊的權(quán) 值總和稱為生成樹的權(quán)，并把權(quán)最小的生成樹稱為 G 的最小生成樹。例：用Prim算法求最小生成樹連通圖如下所示：例：用克魯斯卡爾算法求最小生成樹 連通圖如下所示:2.最短路徑 路徑的開始頂點(diǎn)稱源點(diǎn)，路徑的最后一個(gè)頂點(diǎn)稱終 點(diǎn)。3.

25、拓?fù)渑判?.1 概念A(yù)OV 網(wǎng)：頂點(diǎn)表示活動， 弧表示活動間的優(yōu)先關(guān)系 的有向圖。在無回路的 AOV 網(wǎng)中，所有的活動可以排成一個(gè) 線性序列，使得每個(gè)活動的所有前驅(qū)活動都排在該活 動的前邊，稱此序列為拓?fù)湫蛄?，?AOV 網(wǎng)構(gòu)成拓 撲序列的過程稱為拓?fù)渑判颉?.2 拓?fù)渑判蛩惴ㄋ枷脒x擇有向圖中入度為 0 的頂點(diǎn)輸出，并從圖中刪去 該點(diǎn)相鄰??；重復(fù)上述操作，直到圖中全部頂點(diǎn)均被輸出或圖中 已不存在入度為 0 的頂點(diǎn)（有回路）。第五章 動態(tài)查找一、平衡二叉樹 （AVL 樹）1.基本概念查找的同時(shí)對表做修改操作 （如插入或刪除 ） 則相應(yīng) 的表稱之為動態(tài)查找表，否則稱之為靜態(tài)查找表。 衡量一個(gè)查找算

26、法次序優(yōu)劣的標(biāo)準(zhǔn)是在查找過程 中對關(guān)鍵字需要執(zhí)行的平均比較次數(shù) （即平均查找長 度 ASL）.3 平衡二叉樹 （AVL 樹），或?yàn)榭諛?,或?yàn)槿缦滦再|(zhì)的二 叉排序樹 :左右子樹深度之差的絕對值不超過1;左右子樹仍然為平衡二叉樹 .平衡因子 BF=左子樹深度右子樹深度 . 平衡二叉樹每個(gè)結(jié)點(diǎn)的平衡因子只能是 1，0，-1。若其絕對值超過 1，則該二叉排序樹就是不平衡的。如圖所示為平衡樹和非平衡樹示意圖：2.平衡二叉樹的算法思想 若向平衡二叉樹中插入一個(gè)新結(jié)點(diǎn)后破壞了平衡 二叉樹的平衡性。首先要找出插入新結(jié)點(diǎn)后失去平衡 的最小子樹根結(jié)點(diǎn)的指針。然后再調(diào)整這個(gè)子樹中有 關(guān)結(jié)點(diǎn)之間的鏈接關(guān)系，使之成為

27、新的平衡子樹。當(dāng) 失去平衡的最小子樹被調(diào)整為平衡子樹后，原有其他 所有不平衡子樹無需調(diào)整，整個(gè)二叉排序樹就又成為 一棵平衡二叉樹。失去平衡的最小子樹是指以離插入結(jié)點(diǎn)最近，且平 衡因子絕對值大于 1 的結(jié)點(diǎn)作為根的子樹。假設(shè)用 A 表示失去平衡的最小子樹的根結(jié)點(diǎn)，則調(diào)整該子樹的 操作可歸納為下列四種情況。2.1 LL 型平衡旋轉(zhuǎn)法由于在 A 的左孩子 B 的左子樹上插入結(jié)點(diǎn) F，使 A 的平衡因子由 1增至 2 而失去平衡。故需進(jìn)行一次順 時(shí)針旋轉(zhuǎn)操作。 即將 A 的左孩子 B 向右上旋轉(zhuǎn)代替 A 作為根結(jié)點(diǎn)， A 向右下旋轉(zhuǎn)成為 B 的右子樹的根結(jié) 點(diǎn)。而原來 B 的右子樹則變成 A 的左子樹

28、。2.2 RR 型平衡旋轉(zhuǎn)法由于在 A 的右孩子 C 的右子樹上插入結(jié)點(diǎn) F，使 A 的平衡因子由 -1 減至-2 而失去平衡。 故需進(jìn)行一次逆 時(shí)針旋轉(zhuǎn)操作。即將 A 的右孩子 C 向左上旋轉(zhuǎn)代替 A 作為根結(jié)點(diǎn)，A 向左下旋轉(zhuǎn)成為 C 的左子樹的根結(jié)點(diǎn)。 而原來 C 的左子樹則變成 A 的右子樹。2.3 LR 型平衡旋轉(zhuǎn)法由于在 A 的左孩子 B 的右子數(shù)上插入結(jié)點(diǎn) F，使 A 的平衡因子由 1 增至 2 而失去平衡。故需進(jìn)行兩次旋 轉(zhuǎn)操作（先逆時(shí)針，后順時(shí)針） 。即先將 A 結(jié)點(diǎn)的左 孩子 B 的右子樹的根結(jié)點(diǎn) D 向左上旋轉(zhuǎn)提升到 B 結(jié)點(diǎn)的位置，然后再把該 D 結(jié)點(diǎn)向右上旋轉(zhuǎn)提升到

29、A 結(jié) 點(diǎn)的位置。即先使之成為 LL 型，再按 LL 型處理。如圖中所示，即先將圓圈部分先調(diào)整為平衡樹，然后 將其以根結(jié)點(diǎn)接到 A 的左子樹上，此時(shí)成為 LL 型， 再按 LL 型處理成平衡型。2.4 RL 型平衡旋轉(zhuǎn)法由于在 A 的右孩子 C 的左子樹上插入結(jié)點(diǎn) F，使 A 的平衡因子由 -1 減至-2 而失去平衡。 故需進(jìn)行兩次旋 轉(zhuǎn)操作（先順時(shí)針，后逆時(shí)針） ，即先將 A 結(jié)點(diǎn)的右 孩子 C 的左子樹的根結(jié)點(diǎn) D 向右上旋轉(zhuǎn)提升到 C 結(jié) 點(diǎn)的位置，然后再把該 D 結(jié)點(diǎn)向左上旋轉(zhuǎn)提升到 A 結(jié) 點(diǎn)的位置。即先使之成為 RR 型，再按 RR 型處理。二、B 樹及其基本操作、 B+樹的基本概

30、念1.B 樹的概念2. B 樹的基本操作2.1 檢索2.2 插入2.3 刪除、散列（ Hash）表二、解決沖突的方法1、開放定址法：當(dāng)沖突發(fā)生時(shí)，使用某種方法在Hash表中形成-個(gè)探査序列，然 后沿著此探查序列逐個(gè)單元地查找，直到找到給定關(guān)鍵字或碰到一個(gè) 開放的地址(即地址單元為空)為止。插入?yún)迹号龅介_放的地址，則將待査關(guān)鍵字插入。查找時(shí)：碰到開放的地址，則說明查找失敗。仃八線性探測再散列di = (d+i) mod mi二 1, 2,m-1m為Hash表表長d為沖突產(chǎn)生時(shí)的Hash地址通過i取值的線性變化構(gòu)造探查序列特點(diǎn)：線性(2)二次探測再散列:2i-i = (d + i2) mod md

31、2i = (d - i2) mod ml=i=(m-l)/2特點(diǎn)：將同義詞來回散列在第一次產(chǎn)生沖突時(shí)的Hash地址的兩端探測序列是跳躍似的減少堆積(二次聚集)的發(fā)生缺點(diǎn)：不易探測到整個(gè)Hash表空間(3)偽隨機(jī)探測再散列di 二(d + Ri) mod mm為Hash表長d為沖突產(chǎn)生時(shí)的Hash地址Ri： Rl, R2, . , Rm-1是一個(gè)偽隨機(jī)數(shù)序列2、再哈希法當(dāng)沖突產(chǎn)生時(shí)，通過再計(jì)算另一個(gè)哈希函數(shù)地址解決沖突。即為 構(gòu)造不同的哈希函數(shù)。di = RHi(K)i=l, 2,.，k其中：RHi (K)豐RHj (K)，即RHi均是不同的Hash函數(shù)。優(yōu)點(diǎn)：不易產(chǎn)生堆積或聚集。缺點(diǎn)：計(jì)算量大

32、。3、鏈地址法將所有關(guān)鍵字為同義詞的記錄存儲在同一單鏈表中。假設(shè)Hash函數(shù)產(chǎn)生的哈希地址在區(qū)間0曠1上，則將Hash表定義 為一個(gè)由m個(gè)頭指針組成的指針數(shù)組chainllashm,凡Hash地址為i 的記錄都插入到以數(shù)組元素chainllashEi為頭指針的鏈表中，并保持 同義詞在同一線性鏈表中按關(guān)鍵字有序。優(yōu)缺點(diǎn)優(yōu)點(diǎn)：不會產(chǎn)生堆積；空間是動態(tài)申請的，適用于造表前無法確 定表長的情況。缺點(diǎn)：空間開銷大。三、哈希表的算法分析哈希表的裝填因子_表中填入的記錄數(shù)_ n_a哈希表的長度一 ma體現(xiàn)哈希表的裝滿程度哈希表的查找效率的決定因素哈希函數(shù)解決沖突的方法哈希表的裝填因子假設(shè)Hash函數(shù)均勻的前

33、提下，不同的解決沖突的方法得到的Hash 表的ASL不同，且不是表中關(guān)鍵字個(gè)數(shù)n的函數(shù)，而是裝填因子a的函 數(shù)。如下表所示：解決沖突的方法平均査找長度ASL成功查找不成功查找線性探測法(l+l/(l-a)/2(1+1/(1 -a)2)/2二次探測、隨機(jī)探測 、再哈希法-ln(l-a)/a1/(1-a)鏈地址法1+ a /2a + exp(-a )ASLot越小，發(fā)生沖突的可能性越小。a越大，發(fā)生沖突的可能性越大。因此只要a選擇合適，不管n多大，哈希表的平均查找長度就會限 定在一個(gè)范圍之內(nèi)。第六章 排序一、希爾排序( Shell Sort) 又稱縮小增量排序，是直接插入排序的改進(jìn)。 基本思想：將

34、待排記錄序列按增量 dh 值分成若干 子表進(jìn)行直接插入排序；然后縮小增量值，再分割， 再排序，直至整個(gè)序列“基本有序”時(shí)，再對整個(gè)序 列做一次直接插入排序。實(shí)現(xiàn)過程：將直接插入排序的間隔變?yōu)?d。 d 的取 值要注意：最后一次必為 1；避免 d 值互為倍數(shù)； 關(guān)鍵字比較次數(shù)最大為 n1.25；記錄移動次數(shù)最大為 1.6n1.25；算法的平均時(shí)間是 O(n1.25)；是一種就地的不 穩(wěn)定的排序。二、快速排序 基本思想：每趟讓待排表中的第一元素作支點(diǎn)，排 序后入終位 k，將原表一分為二，使得 r1rk-1 中 元素小于等于 rk ，而 rk+1rn中元素都大于等于 rk ，遞歸進(jìn)行，直到表長為 1 時(shí)，排序結(jié)束。 實(shí)現(xiàn)過程：將第一個(gè)值作為基準(zhǔn)， 設(shè)置 i,j 指針交替