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

1、數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)基本概念1. 數(shù)據(jù)能被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息的載體。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ù)的存儲(chǔ)結(jié)構(gòu)（數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式）和數(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è)直接前趨和直接后繼。數(shù)組、廣義表、

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

3、中無(wú)元素時(shí)為空棧。通常棧有順序棧和鏈棧兩種存儲(chǔ)結(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)，允許插入的一端稱為隊(duì)尾(rear) ,隊(duì)列也有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)結(jié)構(gòu)。2.2隊(duì)列的基本運(yùn)算 置空隊(duì)：Init

4、Queue(Q)判隊(duì)空：QueueEmpty(Q)判隊(duì)滿：QueueFull(Q)入隊(duì)：EnQueue(Q,x)出隊(duì)：DeQueue(Q)取隊(duì)頭元素：QueueFront(Q)二、棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)1.棧的順序存儲(chǔ)結(jié)構(gòu)1.1概念開辟一組地址連續(xù)的存儲(chǔ)單元，依次存放自棧底到棧頂?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è)法避免，下溢常用作程序控制轉(zhuǎn)移的條件。1.2基本運(yùn)算新元素入棧頂時(shí)：先入棧, 再移指針top=top+1刪除元素時(shí)：先移指針top=top-1,后刪棧頂

5、元素棧的長(zhǎng)度：top-base2.隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)2.1概念用一組地址連續(xù)的存儲(chǔ)單元依次存放從隊(duì)頭到隊(duì)尾的元素。設(shè)隊(duì)頭指針為front，指向隊(duì)頭元素。隊(duì)尾指針為rear，指向隊(duì)尾元素的下一個(gè)位。當(dāng)front=rear=0，表示空隊(duì)列。順序隊(duì)列中存在“假上溢”現(xiàn)象，由于入隊(duì)和出隊(duì)操作使頭尾指針只增不減導(dǎo)致被刪元素的空間無(wú)法利用，隊(duì)尾指針超過(guò)向量空間的上界而不能入隊(duì)。將隊(duì)列的頭、尾相連形成一個(gè)環(huán)，構(gòu)成循環(huán)隊(duì)列。并引入數(shù)學(xué)中的模運(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

6、;Q.front=(Q.front+1)%MAXQSIZE;三、棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1.棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1.1概念采用鏈?zhǔn)酱鎯?chǔ)結(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)return s-top=NULL;進(jìn)棧。Void push(linkstack *s,datatype x)stacknode *p=(stacknode *)malloc(sizeof(sta

7、cknode);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;取棧頂元素。Datatype stacktop(linkstack *s)if(stackempty(s) error(“stack is empty”);return s-top-data;2.隊(duì)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.1概念用鏈表示的隊(duì)列簡(jiǎn)稱為鏈

8、隊(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=NULL;入隊(duì)。Void enqueue(linkqueue *q,datatype x)queuenode *p=(queuenode *)malloc(sizeof(queuenode);p-data=x;p-ne

9、xt=NULL;if(queueempty(q) q-front=q-rear=p;else q-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-data;q-front=p-next;if(q-rear=p) q-rear=NULL;free(p);return x;取隊(duì)頭元素。Datatype queuefront(linkqueue *q)if(queueemp

10、ty(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.一個(gè)結(jié)點(diǎn)擁有的子樹數(shù)稱為該結(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)序列K

11、1，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ù)稱為樹的高度或深度；10.樹中每個(gè)結(jié)點(diǎn)的各個(gè)子樹從左到右有次序的稱有序樹，否則稱無(wú)序樹；11.森林是m棵互不相交的樹的集合。二、二叉樹1. 二叉樹的定義及其主要特性 1.1定義樹中每個(gè)結(jié)點(diǎn)至多有兩棵子樹，且子樹有序。滿二叉樹是一棵深度為k，結(jié)點(diǎn)數(shù)為2k-1的二叉樹；完全二叉樹是至多在最下兩層上結(jié)點(diǎn)的度數(shù)可以小于2，并且最下層

12、的結(jié)點(diǎn)集中在該層最左的位置的二叉樹。1.2二叉樹的五種基本形態(tài)1.3二叉樹的主要特性二叉樹第i層上的結(jié)點(diǎn)數(shù)最多為2i-1；深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)；在任意二叉樹中，葉子數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1；1.4滿二叉樹與完全二叉樹 滿二叉樹深度為k，且有2k-1個(gè)結(jié)點(diǎn)。（對(duì)滿二叉樹中的結(jié)點(diǎn)約定編號(hào)：自根起，從上到下，從左到右）完全二叉樹僅允許最下層右側(cè)分支不滿，若按從上到下，從左到右為樹中結(jié)點(diǎn)編號(hào)，則與滿二叉樹相同。二者關(guān)系：滿二叉樹是完全二叉樹。完全二叉樹不一定是滿二叉樹。1.5完全二叉樹性質(zhì)n個(gè)結(jié)點(diǎn)，深度為K的完全二叉樹，其K= log2N+1對(duì)一棵n個(gè)結(jié)點(diǎn)深度為

13、K的完全二叉樹上的結(jié)點(diǎn)按層次編碼（從第一層到第K層，從左到右），則樹中編號(hào)為i的結(jié)點(diǎn)(1=i1時(shí)，i的雙親是 i/2 ；c: 當(dāng)2in時(shí)，i是葉點(diǎn)（無(wú)左孩子）；當(dāng)2in時(shí)，i結(jié)點(diǎn)無(wú)右孩子；當(dāng)2i+11則雙親結(jié)點(diǎn)是i/2取整；左孩子是2i, 右孩子是2i+1；（要小于n）i（n/2取整）的結(jié)點(diǎn)是葉子；奇數(shù)沒有右兄弟，左兄弟是i-1；偶數(shù)沒有左兄弟，右兄弟是i+1。但順序存儲(chǔ)結(jié)構(gòu)適用于完全二叉樹。特點(diǎn)：即不浪費(fèi)空間，又可以快速確定其結(jié)點(diǎn)的位置；對(duì)已知的結(jié)點(diǎn) i，其左孩子為2i，右孩子為2i+1，雙親為 i/2。2.2鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈表中每個(gè)結(jié)點(diǎn)至少含有三個(gè)域：數(shù)據(jù)域、左指針域和右指針域。t3. 二叉

14、樹的遍歷 根據(jù)訪問結(jié)點(diǎn)的次序不同可分為：先序遍歷(前序遍歷或先根遍歷)，中序遍歷(或中根遍歷)、后序遍歷(或后根遍歷)。遍歷線索二叉樹。時(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. 樹的存儲(chǔ)結(jié)構(gòu)雙親表示法（順序存儲(chǔ)結(jié)構(gòu)）：開辟一組連續(xù)空間存儲(chǔ)樹的結(jié)點(diǎn)，每

15、個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示雙親結(jié)點(diǎn)的雙親域。孩子表示法（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）：A.按樹的度設(shè)結(jié)點(diǎn)指針域。B.按結(jié)點(diǎn)的度設(shè)結(jié)點(diǎn)指針域C.按孩子結(jié)點(diǎn)排成線性表孩子兄弟表示法（二叉樹表示法）：在這種表示法中，樹中每個(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)換二叉樹和樹都可以用二叉鏈表作為其存儲(chǔ)結(jié)構(gòu)。因此，以二叉鏈表作為中間介，可以導(dǎo)出樹與二叉樹之間存在對(duì)應(yīng)關(guān)系。一棵樹與惟一的一棵二叉樹一一對(duì)應(yīng)。2.1樹轉(zhuǎn)換成二叉樹保持雙親和第一個(gè)孩子連線，其他連線去掉；兄弟之間連線；使右兄弟結(jié)點(diǎn)成為右孩子，使第一個(gè)孩子成為左孩子。2.2森林轉(zhuǎn)換

16、為二叉樹將每棵樹轉(zhuǎn)化為二叉樹；將各棵二叉樹的根相連；使二叉樹的根成為右孩子。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樹的遍歷先根遍歷先訪問樹根，再依次先根遍歷根的每棵子樹。后根遍歷先依次后根遍歷根的每棵子樹，再訪問樹根。3.2森林的遍歷 先序(先根)遍歷森林中序(后根)遍歷森林四、樹與二叉樹的應(yīng)用1.概念：樹的路徑長(zhǎng)度是從樹根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。將樹中的結(jié)點(diǎn)賦予實(shí)數(shù)稱為結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑是該結(jié)點(diǎn)的路徑長(zhǎng)度與權(quán)的乘積。樹的帶權(quán)路徑長(zhǎng)度又

17、稱樹的代價(jià)，是所有葉子的帶權(quán)路徑長(zhǎng)度之和。帶權(quán)路徑長(zhǎng)度最小的二叉樹稱最優(yōu)二叉樹（哈夫曼樹）。具有2n-1個(gè)結(jié)點(diǎn)其中有n個(gè)葉子，并且沒有度為1的分支結(jié)點(diǎn)的樹稱為嚴(yán)格二叉樹。對(duì)字符集編碼時(shí)，要求字符集中任一字符的編碼都不是其它字符的編碼前綴，這種編碼稱前綴碼。字符出現(xiàn)頻度與碼長(zhǎng)乘積之和稱文件總長(zhǎng)；字符出現(xiàn)概率與碼長(zhǎng)乘積之和稱平均碼長(zhǎng)；使文件總長(zhǎng)或平均碼長(zhǎng)最小的前綴碼稱最優(yōu)前綴碼利用哈夫曼樹求最優(yōu)前綴碼，左為0，右為1。編碼平均碼長(zhǎng)最??；沒有葉子是其它葉子的祖先，不可能出現(xiàn)重復(fù)前綴。2. 哈夫曼樹構(gòu)造算法)根據(jù)給定的n個(gè)權(quán)值w1,w2,wn構(gòu)成n棵二叉樹的集合F=T1,T2,Tn，其中每棵二叉樹Ti

18、中只有一個(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)值之和。在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入F中。 重復(fù)和，直到F只含一棵樹為止。這棵樹便是哈夫曼樹。3. 前綴碼給定一個(gè)碼的集合序列，若沒有一個(gè)序列是另一個(gè)序列的前綴，則稱這個(gè)集合中的碼為前綴碼。 第四章 圖一、圖的基本概念1.圖：圖G是由頂點(diǎn)集V和邊集E組成，頂點(diǎn)集是有窮非空集，邊集是有窮集；2.G中每條邊都有方向稱有向圖；有向邊稱?。贿叺氖键c(diǎn)稱弧尾；邊的終點(diǎn)稱弧頭；G中每條邊都沒有方向的稱無(wú)向圖。3.頂點(diǎn)n與邊數(shù)e的關(guān)系

19、：無(wú)向圖的邊數(shù)e介于0n(n-1)/2之間，有n(n-1)/2條邊的稱無(wú)向完全圖；有向圖的邊數(shù)e介于0n(n-1)之間，有n(n-1)條邊的稱有向完全圖；4.無(wú)向圖中頂點(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.在無(wú)向圖中，任意兩個(gè)頂點(diǎn)都有路徑連通稱連通圖；極大連通子圖稱連通分量；8.在有向圖中，任意順序兩個(gè)頂點(diǎn)都有路徑連通稱強(qiáng)連通圖；極大連通子圖稱強(qiáng)連通分量；9.將圖中

20、每條邊賦上權(quán)，則稱帶權(quán)圖為網(wǎng)絡(luò)。二、圖的存儲(chǔ)及基本操作1. 鄰接矩陣表示法用一維數(shù)組存儲(chǔ)圖中頂點(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.鄰接矩陣表示法與鄰接表表示法的比較鄰接矩陣是唯一的，鄰接表不唯一；存儲(chǔ)稀疏圖用鄰接表，存儲(chǔ)稠密圖用鄰接矩陣；求無(wú)向圖頂點(diǎn)的度都容易，求有向圖頂點(diǎn)的度鄰接矩陣較方便；判斷是否是圖中的邊，鄰接矩陣容易，鄰接表最壞時(shí)間為O(n)；求邊數(shù)e，鄰接矩陣耗時(shí)為O(n2)，與e無(wú)關(guān)，鄰接表的耗時(shí)為O(e+n)；三、圖

21、的遍歷1. 深度優(yōu)先搜索（DFS）搜索策略： 訪問當(dāng)前頂點(diǎn)vi，尋找與vi相鄰且未被訪問頂點(diǎn)vj，若存在，將其作為當(dāng)前點(diǎn)，訪問，并重復(fù)上述搜尋過(guò)程。 否則（所有鄰接點(diǎn)都被訪問過(guò)），退回一步，尋找與前一個(gè)頂點(diǎn)相鄰的未被訪問頂點(diǎn)，訪問，并重復(fù)上述過(guò)程。 若上述過(guò)程無(wú)法訪問圖中的所有頂點(diǎn)，則另選一個(gè)新頂點(diǎn)重新開始。 深度優(yōu)先搜索是一種縱向搜索的過(guò)程。2. 廣度優(yōu)先搜索（BFS） 訪問出發(fā)點(diǎn)v0，依次訪問v0的各個(gè)未曾訪問過(guò)的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)重復(fù)上述過(guò)程。 若上述過(guò)程無(wú)法訪問圖中的所有頂點(diǎn)，則另選一個(gè)新頂點(diǎn)重新開始。 廣度優(yōu)先搜索是一種橫向搜索的過(guò)程。 使用隊(duì)列結(jié)構(gòu)。四、圖的基本應(yīng)用1

22、.概念將沒有回路的連通圖定義為樹稱自由樹。生成樹：連通圖G的一個(gè)子圖若是一棵包含G中所有頂點(diǎn)的樹，該子圖稱生成樹。有DFS生成樹和BFS生成樹，BFS生成樹的高度最小。非連通圖生成的是森林。最小生成樹：連通網(wǎng)G=(V,E)，邊是帶權(quán)的，因而G的生成樹的各邊也是帶權(quán)的。將生成樹的各邊的權(quán)值總和稱為生成樹的權(quán)，并把權(quán)最小的生成樹稱為G的最小生成樹。2. 最短路徑路徑的開始頂點(diǎn)稱源點(diǎn)，路徑的最后一個(gè)頂點(diǎn)稱終點(diǎn)。3. 拓?fù)渑判?.1概念 AOV網(wǎng)：頂點(diǎn)表示活動(dòng)，弧表示活動(dòng)間的優(yōu)先關(guān)系的有向圖。 在無(wú)回路的AOV網(wǎng)中，所有的活動(dòng)可以排成一個(gè)線性序列，使得每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前邊，稱此序列

23、為拓?fù)湫蛄?，由AOV網(wǎng)構(gòu)成拓?fù)湫蛄械倪^(guò)程稱為拓?fù)渑判颉?.2拓?fù)渑判蛩惴ㄋ枷?選擇有向圖中入度為0的頂點(diǎn)輸出，并從圖中刪去該點(diǎn)相鄰??； 重復(fù)上述操作，直到圖中全部頂點(diǎn)均被輸出或圖中已不存在入度為0的頂點(diǎn)（有回路）。第五章 動(dòng)態(tài)查找一、平衡二叉樹(AVL樹)1.基本概念查找的同時(shí)對(duì)表做修改操作(如插入或刪除)則相應(yīng)的表稱之為動(dòng)態(tài)查找表，否則稱之為靜態(tài)查找表。衡量一個(gè)查找算法次序優(yōu)劣的標(biāo)準(zhǔn)是在查找過(guò)程中對(duì)關(guān)鍵字需要執(zhí)行的平均比較次數(shù)(即平均查找長(zhǎng)度ASL).平衡二叉樹(AVL樹)，或?yàn)榭諛?或?yàn)槿缦滦再|(zhì)的二叉排序樹:左右子樹深度之差的絕對(duì)值不超過(guò)1;左右子樹仍然為平衡二叉樹. 平衡因子BF=左子樹

24、深度右子樹深度. 平衡二叉樹每個(gè)結(jié)點(diǎn)的平衡因子只能是1，0，-1。若其絕對(duì)值超過(guò)1，則該二叉排序樹就是不平衡的。如圖所示為平衡樹和非平衡樹示意圖：2.平衡二叉樹的算法思想 若向平衡二叉樹中插入一個(gè)新結(jié)點(diǎn)后破壞了平衡二叉樹的平衡性。首先要找出插入新結(jié)點(diǎn)后失去平衡的最小子樹根結(jié)點(diǎn)的指針。然后再調(diào)整這個(gè)子樹中有關(guān)結(jié)點(diǎn)之間的鏈接關(guān)系，使之成為新的平衡子樹。當(dāng)失去平衡的最小子樹被調(diào)整為平衡子樹后，原有其他所有不平衡子樹無(wú)需調(diào)整，整個(gè)二叉排序樹就又成為一棵平衡二叉樹。 失去平衡的最小子樹是指以離插入結(jié)點(diǎn)最近，且平衡因子絕對(duì)值大于1的結(jié)點(diǎn)作為根的子樹。假設(shè)用A表示失去平衡的最小子樹的根結(jié)點(diǎn)，則調(diào)整該子樹的操

25、作可歸納為下列四種情況。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)。而原來(lái)B的右子樹則變成A的左子樹。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)。而原來(lái)C的左子樹則變成A的右子樹。2.3 LR型平衡旋轉(zhuǎn)法 由于在A的左孩子B的右子數(shù)上插入結(jié)點(diǎn)F，使A的平衡因子

26、由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)提升到A結(jié)點(diǎn)的位置。即先使之成為L(zhǎng)L型，再按LL型處理。 如圖中所示，即先將圓圈部分先調(diào)整為平衡樹，然后將其以根結(jié)點(diǎn)接到A的左子樹上，此時(shí)成為L(zhǎng)L型，再按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)的位置

27、。即先使之成為RR型，再按RR型處理。二、B樹及其基本操作、B+樹的基本概念1.B樹的概念2. B樹的基本操作2.1檢索2.2插入2.3刪除三、散列（Hash）表第六章 排序一、希爾排序（Shell Sort） 又稱縮小增量排序，是直接插入排序的改進(jìn)。 基本思想：將待排記錄序列按增量dh值分成若干子表進(jìn)行直接插入排序；然后縮小增量值，再分割，再排序，直至整個(gè)序列“基本有序”時(shí)，再對(duì)整個(gè)序列做一次直接插入排序。 實(shí)現(xiàn)過(guò)程：將直接插入排序的間隔變?yōu)閐。d的取值要注意：最后一次必為1；避免d值互為倍數(shù)；關(guān)鍵字比較次數(shù)最大為n1.25；記錄移動(dòng)次數(shù)最大為1.6n1.25；算法的平均時(shí)間是O(n1.25)；是一種就地的不穩(wěn)定的排序。二、快速排序 基本思想：每趟讓待排表中的第一元素作支點(diǎn)，排序后入終位k，將原表一分為二，使得r1rk-1中元素小于等于rk，而rk+1rn中元素都大于等于rk，遞歸進(jìn)行，直到表長(zhǎng)為1時(shí)，排序結(jié)束。 實(shí)現(xiàn)過(guò)程：將第一個(gè)值作為基準(zhǔn)，設(shè)置i,j指針交替從兩頭與基準(zhǔn)比較，有交換后,交換j，i。i=j時(shí)確定基準(zhǔn)，并以其為界限將序列分為兩段。重復(fù)以上步驟。 算法的最好時(shí)間是O(nlog2n)；最壞時(shí)間是O(n2)；平均時(shí)間是O(nlog2n)；輔助空間為O(log2n)；是一種不穩(wěn)定排