1、軟件開發(fā)設(shè)計(jì)與實(shí)踐實(shí)驗(yàn)報(bào)告王逸格計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2016年5月摘要本報(bào)告闡述了軟件開發(fā)與設(shè)計(jì)課程所實(shí)現(xiàn)的各個(gè)程序的功能，介紹了其算法設(shè)計(jì)思路的由來(lái)，并分析了算法的效率，優(yōu)缺點(diǎn)及實(shí)際應(yīng)用的場(chǎng)合。報(bào)告分模塊對(duì)程序進(jìn)行解釋，將重點(diǎn)置于對(duì)新穎設(shè)計(jì)思想的介紹，以及由此思想設(shè)計(jì)出的算法的優(yōu)劣的分析，穿插著個(gè)人設(shè)計(jì)思路的心得體會(huì)以及對(duì)經(jīng)典思路的總結(jié)分析，此外，通過(guò)設(shè)計(jì)程序?qū)崿F(xiàn)了一些算法的實(shí)際應(yīng)用。 1 線性結(jié)構(gòu)41.1 跳表ADT41.1.1 功能介紹41.1.2 算法分析及具體實(shí)現(xiàn)41.1.3運(yùn)用51.1.4 運(yùn)行結(jié)果51.2 KMP算法51.2.1 功能介紹51.2.2 算法分析51.3 優(yōu)先隊(duì)列6

2、1.3.1 程序功能61.3.2 算法分析61.3.3 運(yùn)行結(jié)果71.4 矩陣的優(yōu)化81.4.1 程序的功能81.4.2 算法的分析81.5實(shí)現(xiàn)語(yǔ)言和運(yùn)用環(huán)境92 樹形結(jié)構(gòu)92.1 前序、后序線索二叉樹的實(shí)現(xiàn)及遍歷92.1.1 程序功能92.1.2算法分析92.1.3 實(shí)驗(yàn)結(jié)果112.2 二叉樹與森林之間的轉(zhuǎn)換112.2.1 程序功能112.2.2 算法分析122.2.3 運(yùn)行結(jié)果132.3 K叉哈夫曼樹142.3.1 程序功能142.3.2 算法分析142.3.3 運(yùn)行結(jié)果143 圖結(jié)構(gòu)143.1無(wú)向圖的雙連通性問(wèn)題及有向圖的強(qiáng)連通性143.1.1程序功能143.1.2 無(wú)向圖雙連通性問(wèn)題1

3、53.1.3 有向圖的強(qiáng)連通性163.1.4 運(yùn)行結(jié)果173.2 最小生成樹算法的實(shí)現(xiàn)173.2.1 Prim 算法173.2.2 Kruskal算法183.3 最短路徑的算法優(yōu)化193.3.1 程序功能193.3.2 Dijkstra算法203.3.3 Dijkstra算法的運(yùn)行結(jié)果203.3.4 Floyd 算法203.3.5 Floyd 算法的運(yùn)行結(jié)果234 查找及散列結(jié)構(gòu)234.1 平衡樹234.1.1 程序功能234.1.2 算法分析244.1.3 運(yùn)行結(jié)果264.2散列查找274.2.1 算法的實(shí)現(xiàn)285 排序方法295.1快排的優(yōu)化295.1.1 程序的功能295.1.2算法實(shí)現(xiàn)

4、295.1.3 運(yùn)行結(jié)果305.2 線性排序算法305.2.1 計(jì)數(shù)排序315.2.2 基數(shù)排序315.2.3 桶排序311 線性結(jié)構(gòu)1.1 跳表ADT1.1.1 功能介紹跳表支持插入，刪除，查找，打印等功能，其具體實(shí)現(xiàn)函數(shù)由skip_list *create_skip_list() 創(chuàng)建跳表函數(shù)int Insert(skip_list *list, int value) 插入函數(shù)int DELETENODE(skip_list *list,int value) 刪除函數(shù)int SEARCH(skip_list *list, int value) 查找函數(shù)void PRINT(skip_lis

5、t *list) 打印函數(shù)void freelist(skip_list *list) 清空跳表函數(shù)1.1.2 算法分析及具體實(shí)現(xiàn)跳表是鏈表的一種，只不過(guò)它在鏈表的基礎(chǔ)上增加了跳躍功能，正是這個(gè)跳躍的功能，使得在查找元素時(shí)，跳表能夠提供O(log n)的時(shí)間復(fù)雜度。跳表的核心思想，其實(shí)是一種通過(guò)“空間來(lái)?yè)Q取時(shí)間”的一個(gè)算法，通過(guò)在每個(gè)節(jié)點(diǎn)中增加了向前的指針(即層)，從而提升查找的效率。跳躍列表是按層建造的。底層是一個(gè)普通的有序鏈表。每個(gè)更高層都充當(dāng)下面列表的快速跑道一個(gè)跳表，應(yīng)該具有以下特征：1,一個(gè)跳表應(yīng)該有幾個(gè)層（level）組成；2,跳表的第一層包含所有的元素；3,每一層都是一個(gè)有序的鏈

6、表；4,如果元素x出現(xiàn)在第i層，則所有比i小的層都包含x；5,每個(gè)節(jié)點(diǎn)包含key及其對(duì)應(yīng)的value和一個(gè)指向同一層鏈表的下個(gè)節(jié)點(diǎn)的指針數(shù)組具體實(shí)現(xiàn)過(guò)程：1. 創(chuàng)建跳表：跳表list含level和Node *head，Node含元素的value和*next，對(duì)跳表進(jìn)行初始化。2. 插入：跳表list含level，編寫一個(gè)int randomlevel()函數(shù)，隨機(jī)產(chǎn)生層數(shù)，將元素插入相應(yīng)層數(shù)3. 查找：從高層開始查找，若遇到第一個(gè)比該數(shù)大的數(shù)，則往下走一層，之后向后走，遇到大數(shù)則向下，直到搜索到或遍歷完整個(gè)跳表為止。4. 刪除：查找到該元素的位置，逐層進(jìn)行刪除，若有必要要更新當(dāng)前跳表的層數(shù)。5

7、. 打印跳表：逐層打印。6. 清空跳表：1.1.3運(yùn)用跳表在當(dāng)前熱門的開源項(xiàng)目中也有很多應(yīng)用，比如LevelDB的核心數(shù)據(jù)結(jié)構(gòu)memtable是用跳表實(shí)現(xiàn)的，redis的sorted set數(shù)據(jù)結(jié)構(gòu)也是有跳表實(shí)現(xiàn)的。1.1.4 運(yùn)行結(jié)果隨機(jī)生成20個(gè)100以內(nèi)的隨機(jī)數(shù)進(jìn)行測(cè)試：1.2 KMP算法1.2.1 功能介紹KMP算法是一種改進(jìn)的字符串匹配算法，由D.E.Knuth與V.R.Pratt和J.H.Morris同時(shí)發(fā)現(xiàn)，因此人們稱它為克努特-莫里斯-普拉特操作(簡(jiǎn)稱KMP算法)。KMP算法的關(guān)鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。本程序?qū)崿F(xiàn)的是主串和模

8、式串匹配時(shí)，返回的主串的位置。利用如下函數(shù)實(shí)現(xiàn)：int kmp_find(const string& target, const string& pattern)1.2.2 算法分析覆蓋函數(shù)所表征的是pattern本身的性質(zhì)，可以讓為其表征的是pattern從左開始的所有連續(xù)子串的自我覆蓋程度。，比如對(duì)于序列a0a1.aj-1 aj要找到一個(gè)k,使它滿足a0a1.ak-1ak=aj-kaj-k+1.aj-1aj而沒(méi)有更大的k滿足這個(gè)條件，就是說(shuō)要找到盡可能大k,使pattern前k字符與后k字符相匹配，k要盡可能的大，原因是如果有比較大的k存在，而我們選擇較小的滿足條件的k，那么當(dāng)失配時(shí)，我們

9、就會(huì)使pattern向右移動(dòng)的位置變大，而較少的移動(dòng)位置是存在匹配的，這樣我們就會(huì)把可能匹配的結(jié)果丟失計(jì)算這個(gè)overlay函數(shù)的方法可以采用遞推，可以想象如果對(duì)于pattern的前j個(gè)字符，如果覆蓋函數(shù)值為ka0a1.ak-1ak=aj-kaj-k+1.aj-1aj則對(duì)于pattern的前j+1序列字符，則有如下可能： patternk+1=patternj+1 此時(shí)overlay(j+1)=k+1=overlay(j)+1 patternk+1patternj+1 此時(shí)只能在pattern前k+1個(gè)子符組所的子串中找到相應(yīng)的overlay函數(shù)，h=overlay(k),如果此時(shí)patter

10、nh+1=patternj+1,則overlay(j+1)=h+1否則重復(fù)(2)過(guò)程。1.3 優(yōu)先隊(duì)列1.3.1 程序功能通過(guò)C語(yǔ)言實(shí)現(xiàn)了優(yōu)先隊(duì)列，該程序能實(shí)現(xiàn)插入元素，刪除元素，查找元素等基本功能，其實(shí)現(xiàn)功能的函數(shù)如下：int INITQUEUE(prqueue & L) 初始化隊(duì)列int INSERT(prqueue &L, elementtype e, elementtype f)插入元素void SHEAPCREATE(prqueue &H, int s, int m) 建堆void SHEAPSORT(prqueue &H) 堆排序elementtype SEARCHELE(prqu

11、eue &L) 查找元素elementtype SEARCHWEIGHT(prqueue &L) 查找權(quán)值int DELETE(prqueue &L) 刪除元素int LEFT(prqueue &L) 打印剩余元素1.3.2 算法分析優(yōu)先隊(duì)列：首先它是一個(gè)隊(duì)列，它強(qiáng)調(diào)了“優(yōu)先”二字，它的“優(yōu)先”意指取隊(duì)首元素時(shí)，有一定的選擇性，即根據(jù)元素的屬性選擇某一項(xiàng)值最優(yōu)的出隊(duì)優(yōu)先隊(duì)列的實(shí)現(xiàn)方法有很多，不僅僅可以用堆來(lái)實(shí)現(xiàn)，也可以選擇無(wú)序數(shù)組、無(wú)序鏈表、有序數(shù)組、有序鏈表以及二叉查找樹，還有堆。這些方法在實(shí)現(xiàn)中當(dāng)然也有優(yōu)先級(jí)，下表就是一些方法的實(shí)現(xiàn)基本操作的時(shí)間性能對(duì)比：從這張表里我們可以按照時(shí)間復(fù)雜度這

12、個(gè)優(yōu)先級(jí)來(lái)進(jìn)行一次排序，當(dāng)然，你會(huì)選用最后一種二叉查找樹作為實(shí)現(xiàn)優(yōu)先隊(duì)列的方案，但是實(shí)際上我們采用的是堆。堆，就是一種二叉樹，堆和二叉查找樹是類似的，但是也有些許不同：從形狀來(lái)看，二叉查找樹可以有不同的形狀，而堆只能是完全二叉樹；在時(shí)間性能上，二者并無(wú)明顯的區(qū)別。堆也是有序的，我們一般將其分為大頂堆和小頂堆。小頂堆，顧名思義，就是這個(gè)堆的子結(jié)點(diǎn)的值小于父結(jié)點(diǎn)的值；相反的，大頂堆就是堆的子結(jié)點(diǎn)的值都大于父結(jié)點(diǎn)的值。在實(shí)現(xiàn)的時(shí)候，我們常常使用基于數(shù)組的堆，即堆中的元素保存在一個(gè)數(shù)組中，而這個(gè)數(shù)組元素的保存也是按照一定規(guī)律的：如果父結(jié)點(diǎn)的位置為n，那么，其對(duì)應(yīng)的左右子結(jié)點(diǎn)的位置分別是2n+1和2n+

13、2。也就是說(shuō)，我們?cè)谝曈X(jué)上（如果用畫圖形象化表示堆的話）和本質(zhì)上將堆打扮成兩種東西，這樣既便于理解，也利于實(shí)現(xiàn)，本質(zhì)的實(shí)現(xiàn)是用數(shù)組是因?yàn)榭紤]到數(shù)組的一些性能。本程序?qū)?quán)值最小的元素進(jìn)行操作，建立的是小根堆。1.3.3 運(yùn)行結(jié)果1.4 矩陣的優(yōu)化1.4.1 程序的功能實(shí)現(xiàn)稀疏矩陣的快速轉(zhuǎn)置。稀疏矩陣是指那些多數(shù)元素為0的矩陣，利用稀疏的特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。1.4.2 算法的分析對(duì)于此算法的分析，矩陣的轉(zhuǎn)置很容易實(shí)現(xiàn)，對(duì)于矩陣的優(yōu)化在于采用三元組進(jìn)行存儲(chǔ)，這樣可以節(jié)約空間，三元組的結(jié)構(gòu)中包含元素所處的列數(shù)，行數(shù)，及元素值，以帶行邏輯鏈接信息的三元組順序表表示稀疏矩

14、陣，實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置運(yùn)算。運(yùn)算結(jié)果以非零的元素位置及值輸出。存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)：矩陣定義為：typedef struct juzhen int row; /行 int col; /列 int value; /元素值;struct juzhen aMAX_TERM; /存放矩陣中元素?cái)?shù)值不為零的元素struct juzhen bMAX_TERM; /轉(zhuǎn)置后的矩陣int chushi(struct juzhen aMAX_TERM) /初始化稀疏矩陣void showjuzhen(struct juzhen aMAX_TERM,int count_a) /顯示稀疏矩陣void showjuzhen_2

15、(struct juzhen aMAX_TERM,int count_a) /顯示稀疏矩陣方法二void zhuanzhi_1(struct juzhen aMAX_TERM,struct juzhen bMAX_TERM) /轉(zhuǎn)置矩陣方法一void zhuanhuan_2(struct juzhen aMAX_TERM,struct juzhen bMAX_TERM)采用優(yōu)化的算法進(jìn)行矩陣轉(zhuǎn)置操作。1.5實(shí)現(xiàn)語(yǔ)言和運(yùn)用環(huán)境本程序由C語(yǔ)言實(shí)現(xiàn)，運(yùn)行環(huán)境為Code：Blocks 13.122 樹形結(jié)構(gòu)2.1 前序、后序線索二叉樹的實(shí)現(xiàn)及遍歷2.1.1 程序功能利用先序序列建立先序和后序線索二叉樹

16、，并對(duì)先序和后序二叉樹進(jìn)行先序遍歷和后序遍歷還有中序遍歷；用以下函數(shù)實(shí)現(xiàn)程序功能：void creat() /創(chuàng)建一棵線索二叉樹void las_build(node *p) /建立后續(xù)結(jié)點(diǎn)void las_creat() /建立后續(xù)線索二叉樹node *parent(node *p) /找到雙親（求后序線索二叉樹中結(jié)點(diǎn)的后繼要知道其雙親的信息）void las_show() /后序輸出void mid_show() /中序輸出void printTable() /打印菜單 2.1.2算法分析根據(jù)線索性質(zhì)的不同，線索二叉樹可分為前序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。線索二叉樹，就

17、好像是給排列在不同地方的對(duì)象用一根無(wú)形的繩子穿起來(lái)了，變成了“線形”的，這樣每個(gè)結(jié)點(diǎn)的前驅(qū)和后繼就能直接得到或者容易找到了。線索化的過(guò)程需要用到遍歷算法，一旦線索建立后，在此結(jié)構(gòu)上遍歷就可以不用遞歸、也不用棧了，實(shí)現(xiàn)更加容易了。對(duì)二叉樹線索化，實(shí)際上就是遍歷二叉樹，檢查當(dāng)前結(jié)點(diǎn)的左、右指針是否為空，如果為空，將它們改為指向前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的線索。存儲(chǔ)結(jié)構(gòu)：struct node /結(jié)點(diǎn) char data; int ltag, rtag; int tag;node *lchild, *rchild;ltag=0 時(shí)lchild指向左孩子；ltag=1 時(shí)lchild指向前驅(qū)；rtag = 0

18、 時(shí)rchild指向右孩子；rtag = 1 時(shí)rchild指向后繼；當(dāng)用二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)時(shí)，因?yàn)槊總€(gè)結(jié)點(diǎn)中只有指向其左、右兒子結(jié)點(diǎn)的指針，所以從任一結(jié)點(diǎn)出發(fā)只線索二叉樹能直接找到該結(jié)點(diǎn)的左、右兒子。在一般情況下靠它無(wú)法直接找到該結(jié)點(diǎn)在某種遍歷序下的前驅(qū)和后繼結(jié)點(diǎn)。如果在每個(gè)結(jié)點(diǎn)中增加指向其前驅(qū)和后繼結(jié)點(diǎn)的指針，將降低存儲(chǔ)空間的效率。我們可以證明：在n個(gè)結(jié)點(diǎn)的二叉鏈表中含有n+1個(gè)空指針。利用這些空指針，存放指向結(jié)點(diǎn)在某種遍歷次序下的前驅(qū)和后繼結(jié)點(diǎn)的指針。這種附加的指針?lè)Q為線索，加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹(ThreadedBinaryTree)。對(duì)

19、一棵非線索二叉樹以某種次序遍歷使其變?yōu)橐豢镁€索二叉樹的過(guò)程稱為二叉樹的線索化。由于線索化的實(shí)質(zhì)是將二叉鏈表中的空指針改為指向結(jié)點(diǎn)前驅(qū)或后繼的線索，而一個(gè)結(jié)點(diǎn)的前驅(qū)或后繼結(jié)點(diǎn)的信息只有在遍歷時(shí)才能得到，因此線索化的過(guò)程即為在遍歷過(guò)程中修改空指針的過(guò)程。為了記下遍歷過(guò)程中訪問(wèn)結(jié)點(diǎn)的先后次序，可附設(shè)一個(gè)指針pre始終指向剛剛訪問(wèn)過(guò)的結(jié)點(diǎn)。當(dāng)指針p指向當(dāng)前訪問(wèn)的結(jié)點(diǎn)時(shí)，pre指向它的前驅(qū)。由此也可推知pre所指結(jié)點(diǎn)的后繼為p所指的當(dāng)前結(jié)點(diǎn)。這樣就可在遍歷過(guò)程中將二叉樹線索化。對(duì)于找前驅(qū)和后繼結(jié)點(diǎn)這二種運(yùn)算而言，線索樹優(yōu)于非線索樹。但線索樹也有其缺點(diǎn)。在進(jìn)行插人和刪除操作時(shí)，線索樹比非線索樹的時(shí)間開銷大

20、。原因在于在線索樹中進(jìn)行插人和刪除時(shí)，除了修改相應(yīng)的指針外，還要修改相應(yīng)的線索。構(gòu)建：建立線索二叉樹，或者說(shuō)對(duì)二叉樹線索化，實(shí)質(zhì)上就是遍歷一顆二叉樹。在遍歷過(guò)程中，訪問(wèn)結(jié)點(diǎn)的草所是檢查當(dāng)前的左，右指針域是否為空，將它們改為指向前驅(qū)結(jié)點(diǎn)或后續(xù)結(jié)點(diǎn)的線索。為實(shí)現(xiàn)這一過(guò)程，設(shè)指針pre始終指向剛剛訪問(wèn)的結(jié)點(diǎn)，即若指針p指向當(dāng)前結(jié)點(diǎn)，則pre指向它的前驅(qū)，以便設(shè)線索。另外，在對(duì)一顆二叉樹加線索時(shí)，必須首先申請(qǐng)一個(gè)頭結(jié)點(diǎn)，head = new node;建立頭結(jié)點(diǎn)與二叉樹的跟結(jié)點(diǎn)的指向關(guān)系，對(duì)二叉樹線索化后，還需建立最后一個(gè)結(jié)點(diǎn)與頭結(jié)點(diǎn)之間的線索。遍歷：以中序?yàn)槔?，利用在中序線索二叉樹上需找后續(xù)結(jié)點(diǎn)和前

21、驅(qū)結(jié)點(diǎn)的算法，就可以遍歷到二叉樹的所有結(jié)點(diǎn)，即先找到按某序遍歷的一個(gè)結(jié)點(diǎn)，然后再一次查詢其后續(xù)；或先找到按某序遍歷的最后一個(gè)結(jié)點(diǎn)，然后再一次查詢其前驅(qū)。這樣，既不用棧也不用遞歸就可以訪問(wèn)但二叉樹的所有結(jié)點(diǎn)。 2.1.3 實(shí)驗(yàn)結(jié)果2.2 二叉樹與森林之間的轉(zhuǎn)換2.2.1 程序功能實(shí)現(xiàn)二叉樹轉(zhuǎn)森林和森林轉(zhuǎn)二叉樹，程序由如下函數(shù)實(shí)現(xiàn)：void printT(int u) 后序遍歷二叉樹void rebuildMap(int u, int fa) 還原void buildT(int u) 構(gòu)建二叉樹2.2.2 算法分析二叉樹轉(zhuǎn)換為樹是樹轉(zhuǎn)換為二叉樹的逆過(guò)程。（1）加線。若某結(jié)點(diǎn)X的左孩子結(jié)點(diǎn)存在，則將

22、這個(gè)左孩子的右孩子結(jié)點(diǎn)、右孩子的右孩子結(jié)點(diǎn)、右孩子的右孩子的右孩子結(jié)點(diǎn)，都作為結(jié)點(diǎn)X的孩子。將結(jié)點(diǎn)X與這些右孩子結(jié)點(diǎn)用線連接起來(lái)。（2）去線。刪除原二叉樹中所有結(jié)點(diǎn)與其右孩子結(jié)點(diǎn)的連線。（3）層次調(diào)整:以樹的根節(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)一定角度，使之結(jié)構(gòu)層次分明二叉樹轉(zhuǎn)換為森林假如一棵二叉樹的根節(jié)點(diǎn)有右孩子，則這棵二叉樹能夠轉(zhuǎn)換為森林，否則將轉(zhuǎn)換為一棵樹。（1）從根節(jié)點(diǎn)開始，若右孩子存在，則把與右孩子結(jié)點(diǎn)的連線刪除。再查看分離后的二叉樹，若其根節(jié)點(diǎn)的右孩子存在，則連線刪除。直到所有這些根節(jié)點(diǎn)與右孩子的連線都刪除為止。（2）將每棵分離后的二叉樹轉(zhuǎn)換為樹。樹轉(zhuǎn)換為二叉樹（1）加線。在所有兄弟結(jié)

23、點(diǎn)之間加一條連線。（2）去線。樹中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)的連線，刪除它與其它孩子結(jié)點(diǎn)之間的連線。（3）層次調(diào)整：以樹的根節(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)一定角度，使之結(jié)構(gòu)層次分明。（注意第一個(gè)孩子是結(jié)點(diǎn)的左孩子，兄弟轉(zhuǎn)換過(guò)來(lái)的孩子是結(jié)點(diǎn)的右孩子）森林轉(zhuǎn)換為二叉樹（1）把每棵樹轉(zhuǎn)換為二叉樹。（2）第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹的根結(jié)點(diǎn)的右孩子，用線連接起來(lái)。樹轉(zhuǎn)換為二叉樹（1）加線。在所有兄弟結(jié)點(diǎn)之間加一條連線。（2）去線。樹中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)的連線，刪除它與其它孩子結(jié)點(diǎn)之間的連線。（3）層次調(diào)整：以樹的根節(jié)點(diǎn)為軸

24、心，將整棵樹順時(shí)針旋轉(zhuǎn)一定角度，使之結(jié)構(gòu)層次分明。（注意第一個(gè)孩子是結(jié)點(diǎn)的左孩子，兄弟轉(zhuǎn)換過(guò)來(lái)的孩子是結(jié)點(diǎn)的右孩子）2.2.3 運(yùn)行結(jié)果測(cè)試用例如圖： 11個(gè)節(jié)點(diǎn)8條邊 2 / 1 5 / 3 6 11 / / 4 9 7 10 8 2 5 11 / | / | /1 3 4 6 7 8 10 / 9/*測(cè)試數(shù)據(jù).11 82 12 32 45 66 95 75 811 10*/2.3 動(dòng)態(tài)哈夫曼樹2.3.1 程序功能實(shí)現(xiàn)動(dòng)態(tài)哈夫曼編碼存儲(chǔ)結(jié)構(gòu)：struct Hnodeint c = 0;int weight = 0;Hnode* left = NULL;Hnode* right = NULL;

25、Hnode* parent = NULL;int search(int c,list* l)/查找有無(wú)出現(xiàn)過(guò)void swap(Hnode* a, Hnode* b) /交換權(quán)值相同的元素int maxloc(int c,int loc,list* l)/相同權(quán)值元素編號(hào)小的在前int searchnode(Hnode* node,list* l)void inc(Hnode* node,list* l)/權(quán)值加一之前父節(jié)點(diǎn)也更新void encode(int c,list* l,int time)/讀文件編碼void Huff(int c,list* l,int time)/插入節(jié)點(diǎn)并判斷有

26、誤出現(xiàn)過(guò)void Huff_Compress(list* l,int* time)/讀字符void Huff_Decompress(list* l,int* time)/寫入文件 譯碼2.3.2 算法分析原始的 Huffman 算法給出了一種靜態(tài)的編碼樹構(gòu)造方案，要求在實(shí)際編碼之前統(tǒng)計(jì)被編碼對(duì)象中符號(hào)出現(xiàn)的幾率，并據(jù)此進(jìn)行編碼樹的構(gòu)造。但應(yīng)用此方案時(shí)必須對(duì)輸入符號(hào)流進(jìn)行兩遍掃描，這在許多實(shí)際的應(yīng)用場(chǎng)合是不能接受的。另外，靜態(tài)編碼樹構(gòu)造方案不能對(duì)符號(hào)流的局部統(tǒng)計(jì)規(guī)律變化做出反應(yīng)，因?yàn)樗鼜氖贾两K都使用完全不變的編碼樹。因此，后人提出了動(dòng)態(tài) Huffman 編碼方案。這種方案在不需要事先構(gòu)造 Huf

27、fman 樹，而是隨著編碼的進(jìn)行，逐步構(gòu)造 Huffman 樹。同時(shí)，這種編碼方案對(duì)符號(hào)的統(tǒng)計(jì)也動(dòng)態(tài)進(jìn)行，隨著程序的運(yùn)行，同一個(gè)符號(hào)的編碼可能發(fā)生改變（變得更長(zhǎng)或更短）。這樣就解決了靜態(tài)編碼樹面臨的主要問(wèn)題。（這里隱含了一個(gè)假設(shè)，就是在一個(gè)數(shù)據(jù)塊中，已經(jīng)出現(xiàn)的符號(hào)出現(xiàn)概率越高，則未來(lái)可能出現(xiàn)的概率也越高，這個(gè)假設(shè)在大多數(shù)情況下是成立的。）初始化編碼樹；對(duì)每一個(gè)輸入符號(hào)對(duì)符號(hào)編碼；更新編碼樹；解碼算法與編碼算法類似，當(dāng)編碼方和解碼方都使用相同的初始化狀態(tài)，以及相同的更新編碼樹策略時(shí)，在編碼方輸入的符號(hào)將正確的在解碼方還原。為了實(shí)現(xiàn)動(dòng)態(tài)編碼，我們每處理完一個(gè)元素就要更新它的權(quán)值（加一），并重新建立

28、哈夫曼編碼樹，這樣效率極低，為了提高效率我們每次只更新受影響的那一部分哈夫曼編碼樹結(jié)構(gòu)。編碼初始狀態(tài)只含一個(gè)葉節(jié)點(diǎn)-NYT，權(quán)重為0，當(dāng)有一個(gè)尚未包含在編碼樹的符號(hào)需要被編碼時(shí)，系統(tǒng)就輸出NYT編碼，后面跟著符號(hào)的原始表達(dá)，當(dāng)解出NYT編碼后，就知道其后的內(nèi)容不再是哈夫曼編碼。3 圖結(jié)構(gòu)3.1無(wú)向圖的雙連通性問(wèn)題及有向圖的強(qiáng)連通性3.1.1程序功能實(shí)現(xiàn)判斷無(wú)向圖是否雙連通，若非雙連通則找出其關(guān)節(jié)點(diǎn)，找出有向圖的強(qiáng)連通分量用如下函數(shù)實(shí)現(xiàn)：存儲(chǔ)結(jié)構(gòu)：struct EDGEEDGE* next;int t;void CreateD(EDGE* V) 創(chuàng)建有向圖void Create(EDGE* V)

29、 創(chuàng)建無(wú)向圖void PrintPoint(EDGE* V) 打印關(guān)節(jié)點(diǎn)void dfslow(EDGE* V, int u, int p) 深搜過(guò)程中頂點(diǎn)編號(hào)void Tarjan(EDGE* V, int i) 求強(qiáng)連通分量的Tarjan算法3.1.2 無(wú)向圖雙連通性問(wèn)題討論無(wú)向圖的雙連通性首先要明確一定的概念：關(guān)節(jié)點(diǎn)（割點(diǎn)）: 是圖中一個(gè)頂點(diǎn)v, 如果刪除它以及它關(guān)聯(lián)的邊后，得到的新圖至少包含兩個(gè)連通分支。雙連通圖： 沒(méi)有關(guān)節(jié)點(diǎn)的連通圖。利用深度優(yōu)先搜索dfs 可以求解雙連通分支，因?yàn)閐fs過(guò)程中，必定要經(jīng)過(guò)關(guān)節(jié)點(diǎn)，并生成一棵深度優(yōu)先搜索樹。如果兩個(gè)頂點(diǎn)u,v ，其中u是v的祖先或者v是

30、u的祖先，那么非樹邊(u,v)叫做回退邊。在深搜樹中，所有的非樹邊都是回退邊。 無(wú)向圖的深搜樹是一棵開放樹，如果在其中添加一條回退邊，就會(huì)形成環(huán)，該環(huán)路或擴(kuò)大連通分量的范圍，或者導(dǎo)致新的連通分量產(chǎn)生。通過(guò)這個(gè)過(guò)程，可以發(fā)現(xiàn)一條規(guī)律：當(dāng)v是樹根，如果它有2個(gè)或者更多兒子，那么它是一個(gè)關(guān)節(jié)點(diǎn)。當(dāng)v不是樹根，當(dāng)且僅當(dāng)它有至少一個(gè)兒子w, 且從w出發(fā)，不能通過(guò)w的后代頂點(diǎn)組成的路徑和一條回退邊到底u(yù) 的任意一個(gè)祖先頂點(diǎn)，此時(shí)v 是一個(gè)關(guān)節(jié)點(diǎn)。 其道理很明顯，如果樹根包含多個(gè)兒子，那么把根節(jié)點(diǎn)去掉，整棵樹自然被分成多個(gè)不相干的部分，圖也就斷開了。如果v是非根頂點(diǎn)，如果其子樹中的節(jié)點(diǎn)均沒(méi)有指向v祖先的回邊

31、，那么去掉v以后，將會(huì)把v及其子樹與圖的其他部分分割開來(lái)，v自然是關(guān)節(jié)點(diǎn)。基于這樣的規(guī)律，我們給每個(gè)頂點(diǎn)定義一個(gè)low值，low(u) 表示從u出發(fā)，經(jīng)過(guò)一條其后代組成的路徑和回退邊，所能到達(dá)的最小深度的頂點(diǎn)的編號(hào)。( 如果這個(gè)編號(hào)大于等于u的編號(hào)，就說(shuō)明它的后代無(wú)法到達(dá)比u深度更淺的頂點(diǎn)，即無(wú)法到達(dá)u的祖先，那么u就是個(gè)關(guān)節(jié)點(diǎn)）low(u) = min dfn(u), min low(w) | w是u的兒子, mindfn(w), | (u,w) 是一條回退邊 dfn(u) 是深搜過(guò)程中對(duì)頂點(diǎn)的編號(hào)值。計(jì)算過(guò)程如下：voiddfnlow(intu,intv) node_pointer ptr

32、;intw; dfnu = lowu = num+;for(ptr = graphu; ptr; ptr = ptr-link) w = ptr-vertex;if(dfnw = dfn(u), 那么u就是關(guān)節(jié)點(diǎn)。求解雙連通分量的過(guò)程，可以通過(guò)深搜完成。 在搜索過(guò)程中，如果遇到一個(gè)新的邊，則壓棧，直到找到一個(gè)關(guān)節(jié)點(diǎn)，由于深搜是遞歸的，在找到一個(gè)關(guān)節(jié)點(diǎn)的同時(shí)，必定已經(jīng)訪問(wèn)完了其子孫節(jié)點(diǎn)和其子樹的邊（包括回退邊），而且這些邊都在棧中，此時(shí)彈出棧中的邊直到遇到關(guān)節(jié)點(diǎn)所在的邊即是雙連通分支包括的邊。3.1.3 有向圖的強(qiáng)連通性有向圖的邊都是單向的，因此可達(dá)性不具有傳遞性：u可以到達(dá)v，不見得v到達(dá)u。

33、但如果u和v相互可達(dá)，那么對(duì)于任意其他結(jié)點(diǎn)w來(lái)說(shuō)，w、u之間的可達(dá)性與w、v之間的可達(dá)性相同?！跋嗷タ蛇_(dá)”關(guān)系是一個(gè)等價(jià)關(guān)系，因此可以根據(jù)這個(gè)關(guān)系把所有結(jié)點(diǎn)分成若干集合，同一個(gè)集合內(nèi)的點(diǎn)相互可達(dá)，不同集合內(nèi)的點(diǎn)不相互可達(dá)，每一個(gè)集合稱為有向圖的一個(gè)強(qiáng)連通分量（Strong Connected Component,SCC）。求強(qiáng)連通分量的Tarjan算法 對(duì)于每一個(gè)強(qiáng)連通分量SCC C，在DFS的過(guò)程中，都有一個(gè)最早被發(fā)現(xiàn)的點(diǎn)，設(shè)為x，則由白色路徑定理，在C中的其他點(diǎn)都是x的后代。如果我們能在x訪問(wèn)完成時(shí)立刻輸出C。這樣，就可以在一棵DFS樹中區(qū)分所有SCC了。因此問(wèn)題的關(guān)鍵就是：判斷一個(gè)點(diǎn)是否

34、為SCC中最先發(fā)現(xiàn)的點(diǎn)。如上圖，實(shí)線表示一條邊，虛線表示一條或多條邊。假設(shè)我們正在判斷u是否是某SCC的第一個(gè)被發(fā)現(xiàn)結(jié)點(diǎn)。如果我們從u的兒子出發(fā)可以到達(dá)u的祖先w，顯然u、v、w在同一個(gè)SCC中，因此u不是該SCC中第一個(gè)被發(fā)現(xiàn)的點(diǎn)。如果從v出發(fā)最多只能到達(dá)u，那么u是該SCC的第一個(gè)被發(fā)現(xiàn)的結(jié)點(diǎn)。這樣，問(wèn)題轉(zhuǎn)化為求：一個(gè)點(diǎn)u最遠(yuǎn)能達(dá)到的祖先的d值。注意，這里的“到達(dá)”可以通過(guò)B邊，不能通過(guò)C邊，但前提是只能通過(guò)當(dāng)前的搜索子樹里的有的點(diǎn)（在程序里用棧保存的）而不是其他已經(jīng)找出來(lái)的SCC里的點(diǎn)。 定義lowu為u及其后代能追溯到的最早（最先發(fā)現(xiàn)）祖先點(diǎn)v的時(shí)間戳dfnv（dfnv表示v變灰的時(shí)間

35、，即v最早發(fā)現(xiàn)的時(shí)間） 程序用sta棧保存當(dāng)前SCC中的結(jié)點(diǎn)（注意這些結(jié)點(diǎn)形成一棵子樹，而不一定是一個(gè)鏈）。idx表示時(shí)間戳， scnt為SCC計(jì)數(shù)器，idi表示i所在的SCC編號(hào)，instai表示i是否在棧中。注意限制v必須在棧中，因?yàn)閺腃邊出發(fā)可能到達(dá)已經(jīng)輸出的SCC中。3.1.4 運(yùn)行結(jié)果3.2 最小生成樹算法的實(shí)現(xiàn)3.2.1 Prim 算法MST（Minimum Spanning Tree，最小生成樹）問(wèn)題有兩種通用的解法，Prim算法就是其中之一，它是從點(diǎn)的方面考慮構(gòu)建一顆MST，大致思想是：設(shè)圖G頂點(diǎn)集合為U，首先任意選擇圖G中的一點(diǎn)作為起始點(diǎn)a，將該點(diǎn)加入集合V，再?gòu)募蟄-V中

36、找到另一點(diǎn)b使得點(diǎn)b到V中任意一點(diǎn)的權(quán)值最小，此時(shí)將b點(diǎn)也加入集合V；以此類推，現(xiàn)在的集合V=a，b，再?gòu)募蟄-V中找到另一點(diǎn)c使得點(diǎn)c到V中任意一點(diǎn)的權(quán)值最小，此時(shí)將c點(diǎn)加入集合V，直至所有頂點(diǎn)全部被加入V，此時(shí)就構(gòu)建出了一顆MST。因?yàn)橛蠳個(gè)頂點(diǎn)，所以該MST就有N-1條邊，每一次向集合V中加入一個(gè)點(diǎn)，就意味著找到一條MST的邊。1).輸入：一個(gè)加權(quán)連通圖，其中頂點(diǎn)集合為V，邊集合為E；2).初始化：Vnew= x，其中x為集合V中的任一節(jié)點(diǎn)（起始點(diǎn)），Enew= ,為空；3).重復(fù)下列操作，直到Vnew= V：a.在集合E中選取權(quán)值最小的邊，其中u為集合Vnew中的元素，而v不在Vne

37、w集合當(dāng)中，并且vV（如果存在有多條滿足前述條件即具有相同權(quán)值的邊，則可任意選取其中之一）；b.將v加入集合Vnew中，將邊加入集合Enew中；4).輸出：使用集合Vnew和Enew來(lái)描述所得到的最小生成樹。prim算法適合稠密圖，其時(shí)間復(fù)雜度為O(n2)，其時(shí)間復(fù)雜度與邊得數(shù)目無(wú)關(guān)測(cè)試用例：4個(gè)頂點(diǎn)：1，2，3，4邊權(quán)重12341049100000024081739801641000000017160 3.2.2 Kruskal算法Kruskal算法是一種用來(lái)尋找最小生成樹的算法，用來(lái)解決同樣問(wèn)題的還有Prim算法都是貪婪算法的應(yīng)用。設(shè)有一個(gè)有n個(gè)頂點(diǎn)的連通網(wǎng)N=V,E,最初先構(gòu)造一個(gè)只有n

38、個(gè)頂點(diǎn)，沒(méi)有邊的非連通圖T=V, E,圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。當(dāng)在E中選到一條具有最小權(quán)值的邊時(shí),并查集：把每個(gè)連通分量看成一個(gè)集合，圖的所有連通分量可以用若干個(gè)不相交集合來(lái)表示，如果把x的父結(jié)點(diǎn)保存在px中(如果沒(méi)有父親，px=x)，則有find(int x) return px=x?x:px=find(px);意思是，如果px=x，說(shuō)明x本身就是樹根，因此返回x；否則返回x的父親px所在樹的根結(jié)點(diǎn)。，樹由集合表示，具體形態(tài)不重要，把遍歷過(guò)的結(jié)點(diǎn)都改成樹根的兒子，下次查找就會(huì)快很多了。算法簡(jiǎn)單描述1).記Graph中有v個(gè)頂點(diǎn)，e個(gè)邊2).新建圖Graphnew，Graphnew中擁有

39、原圖中相同的e個(gè)頂點(diǎn)，但沒(méi)有邊3).將原圖Graph中所有e個(gè)邊按權(quán)值從小到大排序4).循環(huán)：從權(quán)值最小的邊開始遍歷每條邊 直至圖Graph中所有的節(jié)點(diǎn)都在同一個(gè)連通分量中if 這條邊連接的兩個(gè)節(jié)點(diǎn)于圖Graphnew中不在同一個(gè)連通分量中添加這條邊到圖Graphnew中kruskal算法的時(shí)間復(fù)雜度為O(eloge)跟邊的數(shù)目有關(guān)，適合稀疏圖。測(cè)試用例：同上輸入為 頂點(diǎn) 終點(diǎn) 權(quán)值 ；3.3 最短路徑的算法優(yōu)化3.3.1 程序功能用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑3.3.2 Dijkstra算法1) 算法思想：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖，把圖中頂點(diǎn)集合V分成兩組，第一組為已求出最

40、短路徑的頂點(diǎn)集合（用S表示，初始時(shí)S中只有一個(gè)源點(diǎn)，以后每求得一條最短路徑 , 就將加入到集合S中，直到全部頂點(diǎn)都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點(diǎn)集合（用U表示），按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過(guò)程中，總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長(zhǎng)度。此外，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離，S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長(zhǎng)度，U中的頂點(diǎn)的距離，是從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。2)算法步驟：a.初始時(shí)，S只包含源點(diǎn)，即Sv，v的距離為0。U包含除v外的其他頂點(diǎn)，即:U=其余頂點(diǎn)

41、，若v與U中頂點(diǎn)u有邊，則正常有權(quán)值，若u不是v的出邊鄰接點(diǎn)，則權(quán)值為。b.從U中選取一個(gè)距離v最小的頂點(diǎn)k，把k，加入S中（該選定的距離就是v到k的最短路徑長(zhǎng)度）。c.以k為新考慮的中間點(diǎn)，修改U中各頂點(diǎn)的距離；若從源點(diǎn)v到頂點(diǎn)u的距離（經(jīng)過(guò)頂點(diǎn)k）比原來(lái)距離（不經(jīng)過(guò)頂點(diǎn)k）短，則修改頂點(diǎn)u的距離值，修改后的距離值的頂點(diǎn)k的距離加上邊上的權(quán)。d.重復(fù)步驟b和c直到所有頂點(diǎn)都包含在S中。3.3.3 Dijkstra算法的運(yùn)行結(jié)果3.3.4 Floyd 算法Floyd-Warshall算法是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問(wèn)題，同時(shí)也被用于計(jì)算有向圖的傳遞閉

42、包。1)算法思想原理：Floyd算法是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃算法。用通俗的語(yǔ)言來(lái)描述的話，首先我們的目標(biāo)是尋找從點(diǎn)i到點(diǎn)j的最短路徑。從動(dòng)態(tài)規(guī)劃的角度看問(wèn)題，我們需要為這個(gè)目標(biāo)重新做一個(gè)詮釋（這個(gè)詮釋正是動(dòng)態(tài)規(guī)劃最富創(chuàng)造力的精華所在） 從任意節(jié)點(diǎn)i到任意節(jié)點(diǎn)j的最短路徑不外乎2種可能，1是直接從i到j(luò)，2是從i經(jīng)過(guò)若干個(gè)節(jié)點(diǎn)k到j(luò)。所以，我們假設(shè)Dis(i,j)為節(jié)點(diǎn)u到節(jié)點(diǎn)v的最短路徑的距離，對(duì)于每一個(gè)節(jié)點(diǎn)k，我們檢查Dis(i,k) + Dis(k,j) Dis(i,j)是否成立，如果成立，證明從i到k再到j(luò)的路徑比i直接到j(luò)的路徑短，我們便設(shè)置Dis(i,j) = Dis(i,k) + Di

43、s(k,j)，這樣一來(lái)，當(dāng)我們遍歷完所有節(jié)點(diǎn)k，Dis(i,j)中記錄的便是i到j(luò)的最短路徑的距離。2).算法描述：a.從任意一條單邊路徑開始。所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒(méi)有邊相連，則權(quán)為無(wú)窮大。 b.對(duì)于每一對(duì)頂點(diǎn) u 和 v，看看是否存在一個(gè)頂點(diǎn) w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。3).Floyd算法過(guò)程矩陣的計(jì)算-十字交叉法方法：兩條線，從左上角開始計(jì)算一直到右下角 如下所示給出矩陣，其中矩陣A是鄰接矩陣，而矩陣Path記錄u,v兩點(diǎn)之間最短路徑所必須經(jīng)過(guò)的點(diǎn)SPFA(Shortest Path Faster Algorithm) 圖的存儲(chǔ)方

44、式為鄰接表是Bellman-Ford算法的一種隊(duì)列實(shí)現(xiàn)，減少了不必要的冗余計(jì)算。算法大致流程是用一個(gè)隊(duì)列來(lái)進(jìn)行維護(hù)。 初始時(shí)將源加入隊(duì)列。 每次從隊(duì)列中取出一個(gè)元素，并對(duì)所有與他相鄰的點(diǎn)進(jìn)行松弛，若某個(gè)相鄰的點(diǎn)松弛成功，則將其入隊(duì)。 直到隊(duì)列為空時(shí)算法結(jié)束。它可以在O(kE)的時(shí)間復(fù)雜度內(nèi)求出源點(diǎn)到其他所有點(diǎn)的最短路徑，可以處理負(fù)邊。SPFA 在形式上和BFS非常類似，不同的是BFS中一個(gè)點(diǎn)出了隊(duì)列就不可能重新進(jìn)入隊(duì)列，但是SPFA中一個(gè)點(diǎn)可能在出隊(duì)列之后再次被放入隊(duì)列，也就是一個(gè)點(diǎn)改進(jìn)過(guò)其它的點(diǎn)之后，過(guò)了一段時(shí)間可能本身被改進(jìn)，于是再次用來(lái)改進(jìn)其它的點(diǎn)，這樣反復(fù)迭代下去。判斷有無(wú)負(fù)環(huán)：如果某

45、個(gè)點(diǎn)進(jìn)入隊(duì)列的次數(shù)超過(guò)V次則存在負(fù)環(huán)（SPFA無(wú)法處理帶負(fù)環(huán)的圖）。SPFA算法有兩個(gè)優(yōu)化算法 SLF 和 LLL：SLF：Small Label First 策略，設(shè)要加入的節(jié)點(diǎn)是j，隊(duì)首元素為i，若dist(j)x則將i插入到隊(duì)尾，查找下一元素，直到找到某一i使得dist(i)left; k2-left=k1-right; k1-right=k2; / 因?yàn)楸容^的是左右孩子的高度，所以求父節(jié)點(diǎn)的高度要加1 k2-Height=Max(Height(k2-left),Height(k2-right) + 1; k1-Height=Max(Height(k1-left),Height(k2-r

46、ight) + 1; return k1;2. 單向左旋平衡處理RR：由于在*a的右子樹根節(jié)點(diǎn)的右子樹上插入節(jié)點(diǎn)，*a的平衡因子由-1變?yōu)?2，致使以*a為根的子樹失去平衡，則需進(jìn)行一次左旋轉(zhuǎn)操作static Position SingleRotateWithRight(Position k1) / RR旋轉(zhuǎn) Position k2; k2=k1-right; k1-right=k2-left; k2-left=k1; /*結(jié)點(diǎn)的位置變了, 要更新結(jié)點(diǎn)的高度值*/ k1-Height=Max(Height(k1-left),Height(k1-right) + 1; k2-Height=Max

47、(Height(k2-left),Height(k2-right) + 1; return k2;3. 雙向旋轉(zhuǎn)（先左后右）平衡處理LR：由于在*a的左子樹根節(jié)點(diǎn)的右子樹上插入節(jié)點(diǎn)，*a的平衡因子由1增至2，致使以*a為根的子樹失去平衡，則需進(jìn)行兩次旋轉(zhuǎn)（先左旋后右旋）操作static Position DoubleRotateLeft(Position k3) / LR旋轉(zhuǎn)逆時(shí)針順時(shí)針 /在 k3 的左孩子，執(zhí)行右側(cè)單旋轉(zhuǎn) k3-left=SingleRotateWithRight(k3-left); / 再對(duì) k3 進(jìn)行 左側(cè)單旋轉(zhuǎn) return SingleRotateWithLeft(k3);4. 雙向旋轉(zhuǎn)（先右后左）平衡處理RL：由于在*a的右子樹根節(jié)點(diǎn)的左子樹上插入節(jié)點(diǎn)，*a的平衡因子由-1變?yōu)?2，致使以*a為根的子樹失去平衡，則需進(jìn)行兩次旋轉(zhuǎn)（先右旋后左旋）操作。static Position DoubleRotateRight(Position k4) / RL旋轉(zhuǎn) /在 k4 的右孩子，執(zhí)行左側(cè)單旋轉(zhuǎn) k4-right = SingleRotateWith