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

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

2、樹和圖等數(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é)點信息的同時，建立附加索引表，。索引表由若干索引項組成。索引項的一般形式是：(關(guān)鍵字、地址)。有稠密索引和稀疏索引。散列存儲按結(jié)點的關(guān)鍵字直接計算出存儲地址第一章 棧、隊列和數(shù)組一、棧和隊列的基本概念1.棧(Stack)1.1概念棧是僅在表的一端進行插入和刪除運算的線性表，又稱棧為LIFO表(Last In First Out)。棧的修改是按后進先出的原則進行的。稱插入、刪除這一端為棧頂，另一端稱為棧底。表

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

4、Queue(Q)判隊空：QueueEmpty(Q)判隊滿：QueueFull(Q)入隊：EnQueue(Q,x)出隊：DeQueue(Q)取隊頭元素：QueueFront(Q)二、棧和隊列的順序存儲結(jié)構(gòu)1.棧的順序存儲結(jié)構(gòu)1.1概念開辟一組地址連續(xù)的存儲單元，依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。設top指針指示棧頂元素的當前位置。當棧滿時，做進棧運算必定產(chǎn)生空間溢出，稱“上溢”。 當?？諘r，做退棧運算必定產(chǎn)生空間溢出，稱“下溢”。上溢是一種錯誤應設法避免，下溢常用作程序控制轉(zhuǎn)移的條件。1.2基本運算新元素入棧頂時：先入棧, 再移指針top=top+1刪除元素時：先移指針top=top-1,后刪棧頂

5、元素棧的長度：top-base2.隊列的順序存儲結(jié)構(gòu)2.1概念用一組地址連續(xù)的存儲單元依次存放從隊頭到隊尾的元素。設隊頭指針為front，指向隊頭元素。隊尾指針為rear，指向隊尾元素的下一個位。當front=rear=0，表示空隊列。順序隊列中存在“假上溢”現(xiàn)象，由于入隊和出隊操作使頭尾指針只增不減導致被刪元素的空間無法利用，隊尾指針超過向量空間的上界而不能入隊。將隊列的頭、尾相連形成一個環(huán)，構(gòu)成循環(huán)隊列。并引入數(shù)學中的模運算計算隊頭和隊尾指針。2.2基本運算入隊操作：Q.baseQ.rear=x;Q.rear=(Q.rear+1)%MAXQSIZE;出隊操作：x=Q.baseQ.front

6、;Q.front=(Q.front+1)%MAXQSIZE;三、棧和隊列的鏈式存儲結(jié)構(gòu)1.棧的鏈式存儲結(jié)構(gòu)1.1概念采用鏈式存儲結(jié)構(gòu)稱鏈棧，并由其棧頂指針惟一確定。設ls為棧頂指針，棧=(a1,a2,an)，a1為棧底元素，an為棧頂元素。1.2基本運算建棧。Void initstack(linkstack *s) s->top=NULL;判?？铡nt stackempty (linkstack *s) return s->top=NULL;進棧。Void push(linkstack *s,datatype x) stacknode *p=(sta

7、cknode *)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

8、x;取棧頂元素。Datatype stacktop(linkstack *s) if(stackempty(s)  error(“stack is empty”); return s->top->data;2.隊的鏈式存儲結(jié)構(gòu)2.1概念 用鏈表示的隊列簡稱為鏈隊列。設兩個指針front、rear分別指示隊頭和隊尾。為了鏈隊列的操作方便，增加一個頭結(jié)點，front指向頭結(jié)點，rear指向隊尾元素。如圖所示：2.2基本運算建空隊Void initqueue(linkqueue *q) q->front=q->rear=NUL

9、L;判隊空。Int queueempty(linkqueue *q) return q->front=NULL&&q->rear=NULL;入隊。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; else  q->

10、rear->next=p;  q->rear=p;  出隊。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); retu

11、rn x;取隊頭元素。Datatype queuefront(linkqueue *q) if(queueempty(q)  error(“queue is empty”); return q->front->data;第二章 樹與二叉樹一、樹的基本概念1.樹是n個結(jié)點的有限集合，非空時必須滿足：只有一個稱為根的結(jié)點；其余結(jié)點形成m個不相交的子集，并稱根的子樹。2.樹的表示方法：樹形表示法；嵌套集合表示法；凹入表表示法；廣義表表示法；3.一個結(jié)點擁有的子樹數(shù)稱為該結(jié)點的度；一棵樹的度是指樹中結(jié)點最大的度數(shù)。4.度為零的結(jié)點稱葉子或終端結(jié)點；度不為零的結(jié)

12、點稱分支結(jié)點或非終端結(jié)點5.根結(jié)點稱開始結(jié)點，根結(jié)點外的分支結(jié)點稱內(nèi)部結(jié)點；6.樹中某結(jié)點的子樹根稱該結(jié)點的孩子；該結(jié)點稱為孩子的雙親；7.樹中存在一個結(jié)點序列K1，K2，Kn，使Ki為Ki+1的雙親，則稱該結(jié)點序列為K1到Kn的路徑或道路；8.樹中結(jié)點K到Ks間存在一條路徑，則稱K是Ks的祖先，Ks是K的子孫；9.結(jié)點的層數(shù)從根算起，若根的層數(shù)為1，則其余結(jié)點層數(shù)是其雙親結(jié)點層數(shù)加1；雙親在同一層的結(jié)點互為堂兄弟；樹中結(jié)點最大層數(shù)稱為樹的高度或深度；10.樹中每個結(jié)點的各個子樹從左到右有次序的稱有序樹，否則稱無序樹；11.森林是m棵互不相交的樹的集合。二、二叉樹1. 二叉樹的定義及其主要特性

13、 1.1定義樹中每個結(jié)點至多有兩棵子樹，且子樹有序。滿二叉樹是一棵深度為k，結(jié)點數(shù)為2k-1的二叉樹；完全二叉樹是至多在最下兩層上結(jié)點的度數(shù)可以小于2，并且最下層的結(jié)點集中在該層最左的位置的二叉樹。1.2二叉樹的五種基本形態(tài)1.3二叉樹的主要特性二叉樹第i層上的結(jié)點數(shù)最多為2i-1；深度為k的二叉樹至多有2k-1個結(jié)點；在任意二叉樹中，葉子數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1；1.4滿二叉樹與完全二叉樹 滿二叉樹深度為k，且有2k-1個結(jié)點。（對滿二叉樹中的結(jié)點約定編號：自根起，從上到下，從左到右）完全二叉樹僅允許最下層右側(cè)分支不滿，若按從上到下，從左到右為樹中結(jié)點編號，則與滿二叉

14、樹相同。二者關(guān)系：滿二叉樹是完全二叉樹。完全二叉樹不一定是滿二叉樹。1.5完全二叉樹性質(zhì)n個結(jié)點，深度為K的完全二叉樹，其K= log2N+1對一棵n個結(jié)點深度為K的完全二叉樹上的結(jié)點按層次編碼（從第一層到第K層，從左到右），則樹中編號為i的結(jié)點(1<=i<=n)有：a: 當i=1時，此點是根；b: 當i>1時，i的雙親是 i/2 ；c: 當2i>n時，i是葉點（無左孩子）；當2i<=n時，2i是i的左孩子；d: 當2i+1>n時，i結(jié)點無右孩子；當2i+1<=n時，2i+1是i的右孩子。2.二叉樹的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)2.1順序存儲結(jié)構(gòu)用一維數(shù)

15、組A作為二叉樹的存儲結(jié)構(gòu)，Ai表示編號為i的結(jié)點。各個結(jié)點編號間的關(guān)系：i=1是根結(jié)點；i>1則雙親結(jié)點是i/2取整；左孩子是2i, 右孩子是2i+1；（要小于n）i>（n/2取整）的結(jié)點是葉子；奇數(shù)沒有右兄弟，左兄弟是i-1；偶數(shù)沒有左兄弟，右兄弟是i+1。但順序存儲結(jié)構(gòu)適用于完全二叉樹。特點：即不浪費空間，又可以快速確定其結(jié)點的位置；對已知的結(jié)點 i，其左孩子為2i，右孩子為2i+1，雙親為 i/2。2.2鏈式存儲結(jié)構(gòu)鏈表中每個結(jié)點至少含有三個域：數(shù)據(jù)域、左指針域和右指針域。t3. 二叉樹的遍歷 根據(jù)訪問結(jié)點的次序不同可分為：先序遍歷(前序遍歷或先根遍歷)，中序遍歷(或中根遍歷

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

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

18、成森林若某結(jié)點是其父結(jié)點的左孩子，則把該結(jié)點的右孩子、右孩子的右孩子、 ，都與該結(jié)點的父結(jié)點用線線連；去掉樹中所有父結(jié)點到其右孩子的連線，生成森林。 3.樹和森林的遍歷3.1樹的遍歷先根遍歷先訪問樹根，再依次先根遍歷根的每棵子樹。后根遍歷先依次后根遍歷根的每棵子樹，再訪問樹根。3.2森林的遍歷 先序(先根)遍歷森林中序(后根)遍歷森林四、樹與二叉樹的應用1.概念：樹的路徑長度是從樹根到每一結(jié)點的路徑長度之和。將樹中的結(jié)點賦予實數(shù)稱為結(jié)點的權(quán)。結(jié)點的帶權(quán)路徑是該結(jié)點的路徑長度與權(quán)的乘積。樹的帶權(quán)路徑長度又稱樹的代價，是所有葉子的帶權(quán)路徑長度之和。帶權(quán)路徑長度最小的二叉樹稱最優(yōu)二叉樹（哈夫曼樹）。

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

20、構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為左右子樹上根結(jié)點的權(quán)值之和。在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中。 重復和，直到F只含一棵樹為止。這棵樹便是哈夫曼樹。3. 前綴碼給定一個碼的集合序列，若沒有一個序列是另一個序列的前綴，則稱這個集合中的碼為前綴碼。 第四章 圖一、圖的基本概念1.圖：圖G是由頂點集V和邊集E組成，頂點集是有窮非空集，邊集是有窮集；2.G中每條邊都有方向稱有向圖；有向邊稱弧；邊的始點稱弧尾；邊的終點稱弧頭；G中每條邊都沒有方向的稱無向圖。3.頂點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.無向圖中頂點的度是關(guān)聯(lián)與頂點的邊數(shù)；有向圖中頂點的度是入度與出度的和。所有圖均滿足：所有頂點的度數(shù)和的一半為邊數(shù)。5.圖G（V，E），如V是V的子集，E是E的子集，且E中關(guān)聯(lián)的頂點均在V中，則G(V,E)是G的子圖。6.在有向圖中，從頂點出發(fā)都有路徑到達其它頂點的圖稱有根圖；7.在無向圖中，任意兩個頂點都有路徑連通稱連通圖；極大連通子圖稱連通分量；8.在有向圖中，任意順序兩個頂點都有路徑連通稱強連通圖；極大連通子圖稱強連通分量；9.將圖中每條邊賦上權(quán)，則稱帶權(quán)圖為網(wǎng)絡。二、圖的存儲及基本操作1. 鄰接矩陣表示法用一維數(shù)組存儲圖中

22、頂點的信息；用矩陣（二維數(shù)組）表示圖中各頂點之間的相鄰關(guān)系。2. 鄰接表法構(gòu)造方法：與同一頂點鄰接的所有鄰接點構(gòu)成一個單鏈表，用表結(jié)點描述；各鏈表設置表頭結(jié)點，由頭結(jié)點描述；各表頭結(jié)點構(gòu)成一個順序表。3.鄰接矩陣表示法與鄰接表表示法的比較鄰接矩陣是唯一的，鄰接表不唯一；存儲稀疏圖用鄰接表，存儲稠密圖用鄰接矩陣；求無向圖頂點的度都容易，求有向圖頂點的度鄰接矩陣較方便；判斷是否是圖中的邊，鄰接矩陣容易，鄰接表最壞時間為O(n)；求邊數(shù)e，鄰接矩陣耗時為O(n2)，與e無關(guān)，鄰接表的耗時為O(e+n)；三、圖的遍歷1. 深度優(yōu)先搜索（DFS）搜索策略： 訪問當前頂點vi，尋找與vi相鄰且未被訪問頂點

23、vj，若存在，將其作為當前點，訪問，并重復上述搜尋過程。 否則（所有鄰接點都被訪問過），退回一步，尋找與前一個頂點相鄰的未被訪問頂點，訪問，并重復上述過程。 若上述過程無法訪問圖中的所有頂點，則另選一個新頂點重新開始。 深度優(yōu)先搜索是一種縱向搜索的過程。2. 廣度優(yōu)先搜索（BFS） 訪問出發(fā)點v0，依次訪問v0的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發(fā)重復上述過程。 若上述過程無法訪問圖中的所有頂點，則另選一個新頂點重新開始。 廣度優(yōu)先搜索是一種橫向搜索的過程。 使用隊列結(jié)構(gòu)。四、圖的基本應用1.概念將沒有回路的連通圖定義為樹稱自由樹。生成樹：連通圖G的一個子圖若是一棵包含G中所有頂點

24、的樹，該子圖稱生成樹。有DFS生成樹和BFS生成樹，BFS生成樹的高度最小。非連通圖生成的是森林。最小生成樹：連通網(wǎng)G=(V,E)，邊是帶權(quán)的，因而G的生成樹的各邊也是帶權(quán)的。將生成樹的各邊的權(quán)值總和稱為生成樹的權(quán)，并把權(quán)最小的生成樹稱為G的最小生成樹。2. 最短路徑路徑的開始頂點稱源點，路徑的最后一個頂點稱終點。3. 拓撲排序3.1概念 AOV網(wǎng)：頂點表示活動，弧表示活動間的優(yōu)先關(guān)系的有向圖。 在無回路的AOV網(wǎng)中，所有的活動可以排成一個線性序列，使得每個活動的所有前驅(qū)活動都排在該活動的前邊，稱此序列為拓撲序列，由AOV網(wǎng)構(gòu)成拓撲序列的過程稱為拓撲排序。3.2拓撲排序算法思想 選擇有向圖中入

25、度為0的頂點輸出，并從圖中刪去該點相鄰?。?重復上述操作，直到圖中全部頂點均被輸出或圖中已不存在入度為0的頂點（有回路）。第五章 動態(tài)查找一、平衡二叉樹(AVL樹)1.基本概念查找的同時對表做修改操作(如插入或刪除)則相應的表稱之為動態(tài)查找表，否則稱之為靜態(tài)查找表。衡量一個查找算法次序優(yōu)劣的標準是在查找過程中對關(guān)鍵字需要執(zhí)行的平均比較次數(shù)(即平均查找長度ASL).平衡二叉樹(AVL樹)，或為空樹,或為如下性質(zhì)的二叉排序樹:左右子樹深度之差的絕對值不超過1;左右子樹仍然為平衡二叉樹. 平衡因子BF=左子樹深度右子樹深度. 平衡二叉樹每個結(jié)點的平衡因子只能是1，0，-1。若其絕對值超過1，則該二叉

26、排序樹就是不平衡的。如圖所示為平衡樹和非平衡樹示意圖：2.平衡二叉樹的算法思想 若向平衡二叉樹中插入一個新結(jié)點后破壞了平衡二叉樹的平衡性。首先要找出插入新結(jié)點后失去平衡的最小子樹根結(jié)點的指針。然后再調(diào)整這個子樹中有關(guān)結(jié)點之間的鏈接關(guān)系，使之成為新的平衡子樹。當失去平衡的最小子樹被調(diào)整為平衡子樹后，原有其他所有不平衡子樹無需調(diào)整，整個二叉排序樹就又成為一棵平衡二叉樹。 失去平衡的最小子樹是指以離插入結(jié)點最近，且平衡因子絕對值大于1的結(jié)點作為根的子樹。假設用A表示失去平衡的最小子樹的根結(jié)點，則調(diào)整該子樹的操作可歸納為下列四種情況。2.1 LL型平衡旋轉(zhuǎn)法 由于在A的左孩子B的左子樹上插入結(jié)點F，使

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

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

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