⑴ 演算法有哪些分類
演算法分類編輯演算法可大致分為：
基本演算法、數據結構的演算法、數論與代數演算法、計算幾何的演算法、圖論的演算法、動態規劃以及數值分析、加密演算法、排序演算法、檢索演算法、隨機化演算法、並行演算法，厄米變形模型，隨機森林演算法。
⑵ C語言中基本的幾種演算法有哪些越多越好！就像打擂台演算法'冒泡排序法等等...
排序演算法
冒泡排序
選擇排序
快速排序
高精度運算
存儲方法
加法運算
減法運算
乘法運算
擴大進制數
習題與練習
搜索演算法
枚舉演算法
深度優先搜索
廣度優先搜索
8數碼問題
n皇後問題
搜索演算法習題
枚舉法習題
聰明的打字員
量水問題
染色問題
跳馬問題
算24點
圖論演算法
最小生成樹演算法(Prim演算法)
單源最短路徑演算法(Dijkstra演算法)
任意結點最短路徑演算法(Floyd演算法)
求有向帶權圖的所有環
Bellman-Ford演算法
計算圖的連通性
計算最佳連通分支
計算拓撲序列
圖論演算法習題
網路建設問題
最短變換問題
挖地雷
烏托邦城市
烏托邦交通中心
動態規劃
最短路徑問題
動態規劃概念
騎士游歷問題
最長遞增子序列
合唱隊形
石子合並問題
能量項鏈
0/1背包問題
開心的金明
金明的預算方案
加分二叉樹
字串編輯距離
花瓶插花
凸多邊形三角劃分
快餐店
⑶ 編程語言都有哪些演算法
（一）基本演算法 : 1.枚舉 2.搜索: 深度優先搜索 廣度優先搜索 啟發式搜索 遺傳演算法 （二）數據結構的演算法 （三）數論與代數演算法 （四）計算幾何的演算法：求凸包 （五）圖論 演算法： 1.哈夫曼編碼 2.樹的遍歷 3.最短路徑 演算法 4.最小生成樹 演算法 5.最小樹形圖 6.網路流 演算法 7.匹配演算法 （六）動態規劃 （七）其他： 1.數值分析 2.加密演算法 3.排序 演算法 4.檢索演算法 5.隨機化演算法
希望採納
⑷ 有關匹配和排序的演算法，高手幫幫忙哈
一、插入排序(Insertion Sort)
1. 基本思想：
每次將一個待排序的數據元素，插入到前面已經排好序的數列中的適當位置，使數列依然有序；直到待排序數據元素全部插入完為止。
2. 排序過程：
【示例】：
[初始關鍵字] [49] 38 65 97 76 13 27 49
J=2(38) [38 49] 65 97 76 13 27 49
J=3(65) [38 49 65] 97 76 13 27 49
J=4(97) [38 49 65 97] 76 13 27 49
J=5(76) [38 49 65 76 97] 13 27 49
J=6(13) [13 38 49 65 76 97] 27 49
J=7(27) [13 27 38 49 65 76 97] 49
J=8(49) [13 27 38 49 49 65 76 97]
Procere InsertSort(Var R : FileType);
//對R[1..N]按遞增序進行插入排序, R[0]是監視哨//
Begin
for I := 2 To N Do //依次插入R[2],...,R[n]//
begin
R[0] := R[I]; J := I - 1;
While R[0] < R[J] Do //查找R[I]的插入位置//
begin
R[J+1] := R[J]; //將大於R[I]的元素後移//
J := J - 1
end
R[J + 1] := R[0] ; //插入R[I] //
end
End; //InsertSort //
二、選擇排序
1. 基本思想：
每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數據元素排完。
2. 排序過程：
【示例】：
初始關鍵字 [49 38 65 97 76 13 27 49]
第一趟排序後 13 〔38 65 97 76 49 27 49]
第二趟排序後 13 27 〔65 97 76 49 38 49]
第三趟排序後 13 27 38 [97 76 49 65 49]
第四趟排序後 13 27 38 49 [49 97 65 76]
第五趟排序後 13 27 38 49 49 [97 97 76]
第六趟排序後 13 27 38 49 49 76 [76 97]
第七趟排序後 13 27 38 49 49 76 76 [ 97]
最後排序結果 13 27 38 49 49 76 76 97
Procere SelectSort(Var R : FileType); //對R[1..N]進行直接選擇排序 //
Begin
for I := 1 To N - 1 Do //做N - 1趟選擇排序//
begin
K := I;
For J := I + 1 To N Do //在當前無序區R[I..N]中選最小的元素R[K]//
begin
If R[J] < R[K] Then K := J
end;
If K <>; I Then //交換R[I]和R[K] //
begin Temp := R[I]; R[I] := R[K]; R[K] := Temp; end;
end
End; //SelectSort //
三、冒泡排序(BubbleSort)
1. 基本思想：
兩兩比較待排序數據元素的大小，發現兩個數據元素的次序相反時即進行交換，直到沒有反序的數據元素為止。
2. 排序過程：
設想被排序的數組R〔1..N〕垂直豎立，將每個數據元素看作有重量的氣泡，根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復進行，直至最後任何兩個氣泡都是輕者在上，重者在下為止。
【示例】：
49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97
Procere BubbleSort(Var R : FileType) //從下往上掃描的起泡排序//
Begin
For I := 1 To N-1 Do //做N-1趟排序//
begin
NoSwap := True; //置未排序的標志//
For J := N - 1 DownTo 1 Do //從底部往上掃描//
begin
If R[J+1]< R[J] Then //交換元素//
begin
Temp := R[J+1]; R[J+1 := R[J]; R[J] := Temp;
NoSwap := False
end;
end;
If NoSwap Then Return//本趟排序中未發生交換，則終止演算法//
end
End; //BubbleSort//
四、快速排序（Quick Sort）
1. 基本思想：
在當前無序區R[1..H]中任取一個數據元素作為比較的"基準"(不妨記為X)，用此基準將當前無序區劃分為左右兩個較小的無序區：R[1..I-1]和R[I+1..H]，且左邊的無序子區中數據元素均小於等於基準元素，右邊的無序子區中數據元素均大於等於基準元素，而基準X則位於最終排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，當R[1..I-1]和R[I+1..H]均非空時，分別對它們進行上述的劃分過程，直至所有無序子區中的數據元素均已排序為止。
2. 排序過程：
【示例】：
初始關鍵字 [49 38 65 97 76 13 27 49〕
第一次交換後 〔27 38 65 97 76 13 49 49〕
第二次交換後 〔27 38 49 97 76 13 65 49〕
J向左掃描，位置不變，第三次交換後 〔27 38 13 97 76 49 65 49〕
I向右掃描，位置不變，第四次交換後 〔27 38 13 49 76 97 65 49〕
J向左掃描 〔27 38 13 49 76 97 65 49〕
（一次劃分過程）
初始關鍵字 〔49 38 65 97 76 13 27 49〕
一趟排序之後 〔27 38 13〕 49 〔76 97 65 49〕
二趟排序之後 〔13〕 27 〔38〕 49 〔49 65〕76 〔97〕
三趟排序之後 13 27 38 49 49 〔65〕76 97
最後的排序結果 13 27 38 49 49 65 76 97
各趟排序之後的狀態
Procere Parttion(Var R : FileType; L, H : Integer; Var I : Integer);
//對無序區R[1,H]做劃分，I給以出本次劃分後已被定位的基準元素的位置 //
Begin
I := 1; J := H; X := R[I] ;//初始化，X為基準//
Repeat
While (R[J] >;= X) And (I < J) Do
begin
J := J - 1 //從右向左掃描，查找第1個小於 X的元素//
If I < J Then //已找到R[J] 〈X//
begin
R[I] := R[J]; //相當於交換R[I]和R[J]//
I := I + 1
end;
While (R[I] <= X) And (I < J) Do
I := I + 1 //從左向右掃描，查找第1個大於 X的元素///
end;
If I < J Then //已找到R[I] >; X //
begin R[J] := R[I]; //相當於交換R[I]和R[J]//
J := J - 1
end
Until I = J;
R[I] := X //基準X已被最終定位//
End; //Parttion //
Procere QuickSort(Var R :FileType; S,T: Integer); //對R[S..T]快速排序//
Begin
If S < T Then //當R[S..T]為空或只有一個元素是無需排序//
begin
Partion(R, S, T, I); //對R[S..T]做劃分//
QuickSort(R, S, I-1);//遞歸處理左區間R[S,I-1]//
QuickSort(R, I+1,T);//遞歸處理右區間R[I+1..T] //
end;
End; //QuickSort//
五、堆排序(Heap Sort)
1. 基本思想：
堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。
2. 堆的定義: N個元素的序列K1,K2,K3,...,Kn.稱為堆，當且僅當該序列滿足特性：
Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])
堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉子結點的關鍵字均大於等於其孩子結點的關鍵字。例如序列10,15,56,25,30,70就是一個堆，它對應的完全二叉樹如上圖所示。這種堆中根結點（稱為堆頂）的關鍵字最小，我們把它稱為小根堆。反之，若完全二叉樹中任一非葉子結點的關鍵字均大於等於其孩子的關鍵字，則稱之為大根堆。
3. 排序過程：
堆排序正是利用小根堆（或大根堆）來選取當前無序區中關鍵字小（或最大）的記錄實現排序的。我們不妨利用大根堆來排序。每一趟排序的基本操作是：將當前無序區調整為一個大根堆，選取關鍵字最大的堆頂記錄，將它和無序區中的最後一個記錄交換。這樣，正好和直接選擇排序相反，有序區是在原記錄區的尾部形成並逐步向前擴大到整個記錄區。
【示例】：對關鍵字序列42，13，91，23，24，16，05，88建堆
Procere Sift(Var R :FileType; I, M : Integer);
//在數組R[I..M]中調用R[I]，使得以它為完全二叉樹構成堆。事先已知其左、右子樹(2I+1 <=M時)均是堆//
Begin
X := R[I]; J := 2*I; //若J <=M, R[J]是R[I]的左孩子//
While J <= M Do //若當前被調整結點R[I]有左孩子R[J]//
begin
If (J < M) And R[J].Key < R[J+1].Key Then
J := J + 1 //令J指向關鍵字較大的右孩子//
//J指向R[I]的左、右孩子中關鍵字較大者//
If X.Key < R[J].Key Then //孩子結點關鍵字較大//
begin
R[I] := R[J]; //將R[J]換到雙親位置上//
I := J ; J := 2*I //繼續以R[J]為當前被調整結點往下層調整//
end;
Else
Exit//調整完畢，退出循環//
end
R[I] := X;//將最初被調整的結點放入正確位置//
End;//Sift//
Procere HeapSort(Var R : FileType); //對R[1..N]進行堆排序//
Begin
For I := N Div Downto 1 Do //建立初始堆//
Sift(R, I , N)
For I := N Downto 2 do //進行N-1趟排序//
begin
T := R[1]; R[1] := R[I]; R[I] := T;//將當前堆頂記錄和堆中最後一個記錄交換//
Sift(R, 1, I-1) //將R[1..I-1]重成堆//
end
End; //HeapSort//
六、幾種排序演算法的比較和選擇
1. 選取排序方法需要考慮的因素：
(1) 待排序的元素數目n；
(2) 元素本身信息量的大小；
(3) 關鍵字的結構及其分布情況；
(4) 語言工具的條件，輔助空間的大小等。
2. 小結：
(1) 若n較小(n <= 50)，則可以採用直接插入排序或直接選擇排序。由於直接插入排序所需的記錄移動操作較直接選擇排序多，因而當記錄本身信息量較大時，用直接選擇排序較好。
(2) 若文件的初始狀態已按關鍵字基本有序，則選用直接插入或冒泡排序為宜。
(3) 若n較大，則應採用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸並排序。 快速排序是目前基於比較的內部排序法中被認為是最好的方法。
(4) 在基於比較排序方法中，每次比較兩個關鍵字的大小之後，僅僅出現兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程，由此可以證明：當文件的n個關鍵字隨機分布時，任何藉助於"比較"的排序演算法，至少需要O(nlog2n)的時間。
(5) 當記錄本身信息量較大時，為避免耗費大量時間移動記錄，可以用鏈表作為存儲結構。
⑸ 數據結構與演算法中，樹一般會應用在哪些方面為什麼
數據結構就不多說了，樹以遞歸性質這一對計算機而言最普遍的描述結構簡直貫穿始終。查找樹字典樹四叉樹哪個都是樹的實際應用。除了低維結構不用樹描述（其實一維結構也可以看成是退化後的樹）。
演算法層面，樹基本上到處都是（當然有些時候是隱性的）。計算機執行指令是線性的，程序代碼也是順序的，是個一維結構，一旦需要解決高維問題，利用棧、隊列等一維基礎結構所能做到的只有樹，而樹則可以用來描述高維邏輯，起到了個橋梁作用。
演算法舉例如下。
狀態空間遍歷類：DFS、BFS
決策類：各種自動機（特例還有退化為一位情況的KMP）、貪心、分治、動態規劃（同屬狀態空間遍歷）、匹配
圖與流：尋路（最短路）、生成樹
應用舉例就更多了，例如XML、DOM樹、編譯器中的模式識別和語法樹、JSON數據傳遞、磁碟路徑結構……
樹的普遍取決於它的結構與通常解決問題的演算法的一致性和結構簡單嚴謹：遞歸定義、拓撲有序（無環）、實現簡單。當面臨高維狀態時，其它結構的處理方式幾乎一定不如轉化為樹來的簡單，所以就成為了組織一維實現與高維邏輯中的橋梁。
⑹ 數據結構匹配演算法如何添加成程序
1、演算法有啦一個大致的雛形後，想清楚演算法的流程，然後先將主程序打好，細節先用過程與函數代替。
2、然後再完善細節部分。
3、最後構造一些數據測試。
建議構造3種數據。
第一種隨機生成的大數據，以檢驗程序在平均情況下的時間效率。
第二種是人工構造的奇葩/猥瑣數據，且最好能確定答案，以檢驗其正確性，比如貪心的一些可能的反例。
最後一種是人工構造的特殊數據，比如，在有關樹的題目中，將輸入中的樹退化成一條鏈。
⑺ 程序員必須知道的10個演算法和數據結構有哪些
演算法
圖搜索 （廣度優先、深度優先）深度優先特別重要
排序
動態規劃
匹配演算法和網路流演算法
正則表達式和字元串匹配
數據結構
圖 （樹尤其重要）
Map
堆
棧/隊列
Tries | 字典樹
額外推薦
貪婪演算法
⑻ 求解：圖論中常見的最短路徑演算法有幾種都是什麼
主要是有三種、、
第一種是最直接的貪心dijkstra演算法、、可以利用堆數據結構進行優化、、缺點就是不能求有負權的最短路與判斷負環、、
第二種是bellman-ford演算法、、根據鬆弛操作的性質是可以來判斷負環的、、時間復雜度是O(nm)的、、
第三種是SPFA演算法、、把他單獨拿出來作為一種演算法並不是非常好的、、他的實質應該是上面的bellman-ford演算法的隊列優化時間復雜度更低、O(KE)、K的值約等於2、、
⑼ 平衡二叉樹的各種演算法實現
多值結點平衡二叉樹的結構及演算法研究
1引言
傳統的AV1.樹是一種應用較為廣泛的數據結構，適合」幾組織在內存中的較小索引.它的
每個結l從上存儲有一個關鍵字、一個平衡因子和兩個指針項，山」幾它是一棵接近」幾理想狀態的
平衡二叉樹，所以AV1.樹具有很高的查詢效率.但正如任何事物都具有兩而性一樣，AV1.樹同
樣存在比較嚴重的缺l從，一是存儲效率比較低:真正有用的關鍵字在結l從上所，片的空間比例較
小，而作為輔助信息的平衡因子和指針卻，片據較大的空間;二是額外運算量比較大:當有結l從
被插入或刪除而導致AV1.樹不平衡時，AV1.樹就需要進行調整而保持它的平衡性，山」幾每個
結l從上只有一個關鍵字，所以任何一次的數據插入或刪除都有可能導致AV1.樹的平衡調整，
這種頻繁的調整運算將大大降低AV1.樹的存取效率.為解決以上問題，結合T3樹每個結l從可
以存儲多個關鍵字項的優l側}l，木文提出了多值結l從平衡二叉樹(簡稱MAV1.樹)，它的主要特
點在」幾每個MAV1.樹的結l從都存儲有多個關鍵字項，而其它信息仍與AV1.樹一樣，即一個平
衡因子和兩個指針項.
2 MAV1.樹結構描述
MAV1.樹仍舊是一種平衡二叉樹，它的整體樹型結構和演算法也是建立在傳統的平衡二叉
樹基礎之上的.MAV1.樹的特徵在」幾它的每個結l從都可以存儲多個關鍵字(較理想的取值大約
在20} 50個之間).用C++語言描述的MAV1.樹結l從結構如卜:
struct NodeStruct
int IJ1emsOnNode;
int bf:
struct NodPStruct*lch;ld:
//一結點中項的數目
//平衡因子
//夕.子
struct NodeStruct * rchild:
}lemType }lemsi Max}lem} ;//結點中的項數組
Node T:
在這種結構中.ElemsOnNode反映的是「當前狀態卜」該結l從中關鍵字項的個數.當在此結
點插入一個關鍵字時.FlemsOnNode值加1.當刪除一個關鍵字時.則FlemsOnNode值減1.每個
結l從上可存儲的關鍵字個數介J幾1 } M axElem之間.bf為平衡因r.其作用等同J幾AV1.樹的平
衡因r. MAV1.樹的任一結l從的平衡因r只能取一1 ,0和1.如果一個結l從的平衡因r的絕對
值大」幾1.則這棵樹就失去了平衡.需要做平衡運算保持平衡.lehild和:child分別為指向左右
J"樹根結0的指針.Flems[ i]為結0中第i個關鍵字項.Flems} MaxFlem」是一個按升序排列的
關鍵字數組.具體的MAV1.樹結l從結構如圖1所示.
}lemsOnNode一h『一* leh;ld一
圖1
reh擊3
}lemsi 0}一
樹結點結構
}lemsi Max}lem}
MAVT
MAV1.樹的結構特l從使它比AV1.樹具有更高的存儲效率.在AV1.樹或MAV1.樹中.實際
有用的信急只有關鍵字.1f1! ElemsOnNode ,bf ,lehild和:child都是為了構建樹型結構If1J不得不添
加的輔助信急. MAV1.樹就是通過減小這些輔助信急的比例來獲得較高的存儲效率.山MAV1.
樹結l從的定義可以看出:FlemsOnNode和bf為int型.各，片4個位元組長度.指針型的lchild和
rchild也各，片4個位元組長度.在以上四項信急中.AV1.樹結l從除了沒有ElemsOnNode外.其餘和
MAV1.樹相同.現假設關鍵字長度為24位元組.M axFl二值定為50.則對AV1.樹來說.它的結l從
長度為36位元組.其中輔助信h,長度為12位元組;If}J MAV1.樹的結l從長度是1. 2K位元組.其中輔助
信急長度為16位元組.山此可以看出.MAV1.樹在存儲時.結l從中輔助信急長度，片整個結l從長度
的比例是很小的.它對存儲空間的利用效率比 AV1.樹要高.這一l從對」幾主要而向內存應用的
MAV1.樹來說是非常重要的.
在實際的應用中.當MAV1.樹作為資料庫索引結構時.為進一步節約內存空間.結l從中Fl-
emType的結構可根據實際需要作不同的定義.
( 1)當排序關鍵字較短時.可以直接將資料庫中的關鍵字值拷貝到索引文件中.這樣
MAV1.樹既有較快的運行速度又不會，片用太大的空間.此時ElemType定義如卜
struct IdxRlemStruct
{
int RecPos://金己錄號
KeyType Key://關鍵字
}R1emType;
( 2}當排序關鍵字較長時.如果直接將資料庫中的關鍵字值拷貝到索引文件中會，片據較大
的空間.此時可以採用只存儲關鍵字地址的形式.這樣不管關鍵字有多長.映射到MAV1.樹後
都只，片據一個指針的固定長度.這種以時間換空間的方法比較適合內存容量有限的情況.此時
ElemType定義如卜
struct Tdxl?lemStruct
int RecPos:
char * Key
R1emType;
//記錄號
//關鍵字指釗
3基於MAUI.樹的運算
MAUI.樹的基木運算.包括MAUI.樹的建立、記錄的插入、刪除、修改以及查詢.這些演算法
與基J幾AVI.樹的演算法相似.都建立在一叉查詢和平衡演算法基礎上.
3. 1 MAVI,樹的平衡運算
如果在一棵原木是平衡的MAUI.樹中插入一個新結l從.造成了不平衡.此時必須調整樹的
結構.使之平衡化「21 .MAUI.樹的平衡演算法與AVI.樹的平衡演算法是相同的.但山J幾MAUI.樹的
每個結l從中都存儲有多個關鍵字.所以在關鍵字個數相同的情況卜. MAUI.樹的應用可以大大
減少平衡運算的次數.例如.假設具有n個關鍵字的待插入序列在插入過程中有5%(根據隨
機序列特l從的不同.此數值會有所差異.這里以比較保守的5%為例)的新產生結l從會導致一
叉樹出現不平衡.對AVI.樹來說.山」幾需要為每個關鍵字分配一個結l從.所以在整個插入過程
中做平衡的次數為n * 5%;對J幾MAUI.樹.設MAUI.樹中M axFl二的值被定義為k(k為大J幾1
的正整數少，則平均每k次的數據插入才會有一個新結l從產生，所以在整個插入過程中需做平
衡的次數僅為(nlk) * 5%.即在M axFl二取值為k的情況卜.對」幾相同的待插入關鍵字序列.
在插入過程中MAUI.樹用J幾平衡運算的開銷是AVI.樹的1/ k.
3. 2數據查找
在MAUI.樹上進行查找.是一個從根結l從開始.沿某一個分支逐層向卜進行比較判等的過
程.假設要在MAUI.樹上查找的值為GetKey.查找過程從根結l從開始.如果根指針為NU1.1..則
查找失敗;否則把要查找的值GetKey與根結l從關鍵字數組中的最小項Elems [ 0]進行比較.如
果GetKev小」幾當前結i最小關鍵字.則遞歸查找左r樹;如果GetKey'大」幾Elems [ 0].則將
GetKey'與根結0關鍵字數組中的最大項Fletns} MaxFl二一1]進行比較.如果GetKey'大」幾當前
結l從最大關鍵字.則遞歸查找右r樹;否則.對當前結l從的關鍵字數組進行查找(山」幾是有序序
列.可以採用折半查找以提高效率).如果有與GetKey'相匹配的值.則查找成功.返回成功信
息,7{報告查找到的關鍵字地址.
3. 3數據插入
數據插入是構建MAV1.樹的基礎.設要在MAV1.樹*T上插入一個新的數據兀素GetKev,
其遞歸演算法描述如卜:
(1)若*T為空樹.則申清一新結} ' Elems} MaxElem}.將GetKey'插入到Flems[ 0]的位置.樹
的深度增1.
(2)若*T未滿.則在*T中找到插入位置後將GetKey'插入.JI在插入後保持結l從中的各
關鍵項有序遞增.若己存在與GetKev相同的項.則不進行插入.
(3)如果*T為滿結l從目一GetKey'值介」幾Flems[ 0]和Flems} MaxFlem]之間.則在*T中找到
GetKev的插入位置posit ion.山」幾*T木身就是滿結l從.所以GetKev的插入必然會將原來*T中
的某個數據擠出去JI卜降到r樹中.根據插入位置position的不同.分以卜幾種情況處理:若*
T中存在與C etl} e`'相同的項.則不進行插入;若插入位置在*T結ii的前半部分(即position <
=MaxFlem/ 2).則將Flems[ 1]到Fletns} position」的數據依次左移一位.再把GetKey插入到Elems
} MaxFlem」中position的位置.Ifn原來*T中最左邊項數據將被擠入到*T的左r樹中.考察此
數據的特l從.它必然大」幾*T左r樹中的任一數據項.所以此時不需要作任何的額外運算.直
接將此數據插入到*T左r樹根結i從的最右r孫位置處就可以了(見圖2中插入，}} 11"後「1,>
的位置變化);若插入位置在*T結ii的後半部分(即position> MaxFlem/ 2).則將Fletns} posi-
tion}到Fletns} MaxFl二一2}的數據依次右移一位.再把GetKev插入到*T結0中position的位
置.與前一種情況類似.結l從中最右邊被擠出的項將被插入到*T的右r樹根結l從的最左r孫
的位置(見圖2中插入「25"後" 30"的位置變化).
插入，"}i」插入」zs0
}o i is i }a
s}土 s
圖2
滿結點插入數據的過程
(4)若GetKey的值小」幾T的最小項值.則將GetKey遞歸插入到T的左r樹中.即在遞歸調
用時GetKey值不變Ifn T= T->lehild.
(5)若GetKey的值大」幾T的最大項值.則將GetKey遞歸插入到T的右r樹中.即在遞歸調
用時GetKey值不變Ifn T= T->rehild.
4結束語
山J幾MAV1.樹的結l從中存儲有多個關鍵字值.所以它具有較高的存儲效率;對MAV l樹進
行查找是_分查找和順序查找的結合.其查詢效率只略低」幾AV1.樹.血山」幾MAV1.樹的平衡
運算比AV1.樹要少得多.所以MAV1.樹有很優秀的綜合運算效率.綜上所述.在數據量大、內
存容量相對較小、數據增刪運算比較頻繁的情況卜.用MAV1.樹作為常駐內存的索引結構是一
種理想的選擇.
⑽ 矩陣求樹的最大匹配
你這個難度有點大啊