1、Java數(shù)據(jù)結(jié)構(gòu)和算法 TOC o 1-1 h z u HYPERLINK l _Toc232568994 一、數(shù)組于簡(jiǎn)單排序 PAGEREF _Toc232568994 h 1 HYPERLINK l _Toc232568995 二、棧與隊(duì)列 PAGEREF _Toc232568995 h 4 HYPERLINK l _Toc232568996 三、鏈表 PAGEREF _Toc232568996 h 7 HYPERLINK l _Toc232568997 四、遞歸 PAGEREF _Toc232568997 h 22 HYPERLINK l _Toc232568998 五、哈希表 PAGE

2、REF _Toc232568998 h 25 HYPERLINK l _Toc232568999 六、高級(jí)排序 PAGEREF _Toc232568999 h 25 HYPERLINK l _Toc232569000 七、二叉樹(shù) PAGEREF _Toc232569000 h 25 HYPERLINK l _Toc232569001 八、紅黑樹(shù) PAGEREF _Toc232569001 h 26 HYPERLINK l _Toc232569002 九、堆 PAGEREF _Toc232569002 h 36 HYPERLINK l _Toc232569003 十、帶權(quán)圖 PAGEREF _T

3、oc232569003 h 39一、數(shù)組于簡(jiǎn)單排序數(shù)組數(shù)組（array）是相同類型變量的集合，可以使用共同的名字引用它。數(shù)組可被定義為任何類型，可以是一維或多維。數(shù)組中的一個(gè)特別要素是通過(guò)下標(biāo)來(lái)訪問(wèn)它。數(shù)組提供了一種將有聯(lián)系的信息分組的便利方法。一維數(shù)組一維數(shù)組（one-dimensional array ）實(shí)質(zhì)上是相同類型變量列表。要?jiǎng)?chuàng)建一個(gè)數(shù)組，你必須首先定義數(shù)組變量所需的類型。通用的一維數(shù)組的聲明格式是：type var-name ; 獲得一個(gè)數(shù)組需要2步。第一步，你必須定義變量所需的類型。第二步，你必須使用運(yùn)算符new來(lái)為數(shù)組所要存儲(chǔ)的數(shù)據(jù)分配內(nèi)存，并把它們分配給數(shù)組變量。這樣Java

4、 中的數(shù)組被動(dòng)態(tài)地分配。如果動(dòng)態(tài)分配的概念對(duì)你陌生，別擔(dān)心，它將在本書(shū)的后面詳細(xì)討論。數(shù)組的初始化（array initializer ）就是包括在花括號(hào)之內(nèi)用逗號(hào)分開(kāi)的表達(dá)式的列表。逗號(hào)分開(kāi)了數(shù)組元素的值。Java 會(huì)自動(dòng)地分配一個(gè)足夠大的空間來(lái)保存你指定的初始化元素的個(gè)數(shù)，而不必使用運(yùn)算符new。Java 嚴(yán)格地檢查以保證你不會(huì)意外地去存儲(chǔ)或引用在數(shù)組范圍以外的值。Java 的運(yùn)行系統(tǒng)會(huì)檢查以確保所有的數(shù)組下標(biāo)都在正確的范圍以內(nèi)（在這方面，Java 與C/C+ 從根本上不同，C/C+ 不提供運(yùn)行邊界檢查）。多維數(shù)組在Java 中，多維數(shù)組（multidimensional arrays ）

5、實(shí)際上是數(shù)組的數(shù)組。你可能期望，這些數(shù)組形式上和行動(dòng)上和一般的多維數(shù)組一樣。然而，你將看到，有一些微妙的差別。定義多維數(shù)組變量要將每個(gè)維數(shù)放在它們各自的方括號(hào)中。例如，下面語(yǔ)句定義了一個(gè)名為twoD 的二維數(shù)組變量。int twoD = new int45; 簡(jiǎn)單排序簡(jiǎn)單排序中包括了：冒泡排序、選擇排序、插入排序；1.冒泡排序的思想：假設(shè)有N個(gè)數(shù)據(jù)需要排序，則從第0個(gè)數(shù)開(kāi)始，依次比較第0和第1個(gè)數(shù)據(jù)，如果第0個(gè)大于第1個(gè)則兩者交換，否則什么動(dòng)作都不做，繼續(xù)比較第1個(gè)第2個(gè)，這樣依次類推，直至所有數(shù)據(jù)都“冒泡”到數(shù)據(jù)頂上。冒泡排序的的java代碼：Public void bubbleSort()

6、int in,out;for(out=nElems-1;out0;out-) for(in=0;inain+1) Swap(in,in+1);算法的不變性：許多算法中，有些條件在算法執(zhí)行過(guò)程中始終是不變的。這些條件被稱 為算法的不變性，如果不變性不為真了，則標(biāo)記出錯(cuò)了；冒泡排序的效率O（N*N），比較N*N/2，交換N*N/4；2. 選擇排序的思想：假設(shè)有N條數(shù)據(jù)，則暫且標(biāo)記第0個(gè)數(shù)據(jù)為MIN（最小），使用OUT標(biāo)記最左邊未排序的數(shù)據(jù)，然后使用IN標(biāo)記第1個(gè)數(shù)據(jù)，依次與MIN進(jìn)行比較，如果比MIN小，則將該數(shù)據(jù)標(biāo)記為MIN，當(dāng)?shù)谝惠啽容^完后，最終的MIN與OUT標(biāo)記數(shù)據(jù)交換，依次類推；選擇排序

7、的java代碼：Public void selectSort()Int in,out,min;For(out=0;outnElems-1;out+) Min=out;For(in=out+1;innElems;in+) If(ainamin) Min=in;Swap(out,min);選擇排序的效率：O（N*N），比較N*N/2，交換N； 選擇排序與冒泡排序比較，比較次數(shù)沒(méi)有明顯改變，但交換次數(shù)明顯減少了很多；3. 插入排序的思想：插入排序是在部分?jǐn)?shù)據(jù)有序的情況下，使用OUT標(biāo)記第一個(gè)無(wú)序的數(shù)據(jù)，將其提取保存到一個(gè)中間變量temp中去，使用IN標(biāo)記空位置，依次比較temp中的值與IN-1的值，

8、如果IN-值大于temp的值，則后移，直到遇到第一個(gè)比temp小的值，在其下一個(gè)位置插入；插入排序的java代碼：Public void InsertionSort() Int in,out; For(out=1;out0& ain-1temp) Ain=ain-1; - -in;Ain=temp;插入排序的效率：O（N*N）, 比較N*N/4，復(fù)制N*N/4；插入排序在隨機(jī)數(shù)的情況下，比冒泡快一倍，比選擇稍快；在基本有序的數(shù)組中，插入排序幾乎只需要O（N）；在逆序情況下，并不比冒泡快；二、棧與隊(duì)列1、棧的定義 棧（Stack）是限制僅在表的一端進(jìn)行插入和刪除運(yùn)算的線性表。(1)通常稱插入、刪

9、除的這一端為棧頂（Top），另一端稱為棧底（Bottom）。(2)當(dāng)表中沒(méi)有元素時(shí)稱為空棧。(3)棧為后進(jìn)先出（Last In First Out）的線性表，簡(jiǎn)稱為L(zhǎng)IFO表。 棧的修改是按后進(jìn)先出的原則進(jìn)行。每次刪除（退棧）的總是當(dāng)前棧中最新的元素，即最后插入（進(jìn)棧）的元素，而最先插入的是被放在棧的底部，要到最后才能刪除。 【示例】元素是以a1，a2，an的順序進(jìn)棧，退棧的次序卻是an，an-1，a1。2、棧的基本運(yùn)算（1）InitStack（S） 構(gòu)造一個(gè)空棧S。（2）StackEmpty（S） 判棧空。若S為空棧，則返回TRUE，否則返回FALSE。（3）StackFull（S） 判棧滿

10、。若S為滿棧，則返回TRUE，否則返回FALSE。注意： 該運(yùn)算只適用于棧的順序存儲(chǔ)結(jié)構(gòu)。（4）Push（S，x） 進(jìn)棧。若棧S不滿，則將元素x插入S的棧頂。（5）Pop（S） 退棧。若棧S非空，則將S的棧頂元素刪去，并返回該元素。（6）StackTop（S） 取棧頂元素。若棧S非空，則返回棧頂元素，但不改變棧的狀態(tài)。隊(duì)列的定義及基本運(yùn)算1、定義 隊(duì)列（Queue）是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的運(yùn)算受限的線性表 （1）允許刪除的一端稱為隊(duì)頭（Front）。（2）允許插入的一端稱為隊(duì)尾（Rear）。（3）當(dāng)隊(duì)列中沒(méi)有元素時(shí)稱為空隊(duì)列。（4）隊(duì)列亦稱作先進(jìn)先出（First In Fi

11、rst Out）的線性表，簡(jiǎn)稱為FIFO表。 隊(duì)列的修改是依先進(jìn)先出的原則進(jìn)行的。新來(lái)的成員總是加入隊(duì)尾（即不允許加塞），每次離開(kāi)的成員總是隊(duì)列頭上的（不允許中途離隊(duì)），即當(dāng)前最老的成員離隊(duì)。【例】在隊(duì)列中依次加入元素a1，a2，an之后，a1是隊(duì)頭元素，an是隊(duì)尾元素。退出隊(duì)列的次序只能是a1，a2，an。2、隊(duì)列的基本邏輯運(yùn)算（1）InitQueue（Q） 置空隊(duì)。構(gòu)造一個(gè)空隊(duì)列Q。（2）QueueEmpty（Q） 判隊(duì)空。若隊(duì)列Q為空，則返回真值，否則返回假值。（3） QueueFull（Q） 判隊(duì)滿。若隊(duì)列Q為滿，則返回真值，否則返回假值。 注意：此操作只適用于隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)。（4

12、） EnQueue（Q，x） 若隊(duì)列Q非滿，則將元素x插入Q的隊(duì)尾。此操作簡(jiǎn)稱入隊(duì)。（5） DeQueue（Q） 若隊(duì)列Q非空，則刪去Q的隊(duì)頭元素，并返回該元素。此操作簡(jiǎn)稱出隊(duì)。（6） QueueFront（Q） 若隊(duì)列Q非空，則返回隊(duì)頭元素，但不改變隊(duì)列Q的狀態(tài)。 三、鏈表鏈結(jié)點(diǎn)在鏈表中，每個(gè)數(shù)據(jù)項(xiàng)都被包含在點(diǎn)“中，一個(gè)點(diǎn)是某個(gè)類的對(duì)象，這個(gè)類可認(rèn)叫做LINK。因?yàn)橐粋€(gè)鏈表中有許多類似的鏈結(jié)點(diǎn)，所以有必要用一個(gè)不同于鏈表的類來(lái)表達(dá)鏈結(jié)點(diǎn)。每個(gè)LINK對(duì)象中都包含一個(gè)對(duì)下一個(gè)點(diǎn)引用的字段（通常叫做next）但是本身的對(duì)象中有一個(gè)字段指向?qū)Φ谝粋€(gè)鏈結(jié)點(diǎn)的引用單鏈表用一組地址任意的存儲(chǔ)單元存放線性

13、表中的 HYPERLINK /view/38785.htm t _blank 數(shù)據(jù)元素。以元素(數(shù)據(jù)元素的映象) + 指針(指示后繼元素存儲(chǔ)位置)= 結(jié)點(diǎn)(表示數(shù)據(jù)元素 或 數(shù)據(jù)元素的映象)以“結(jié)點(diǎn)的序列”表示線性表 稱作線性鏈表（單鏈表）單鏈表是一種順序存取的結(jié)構(gòu)，為找第 i 個(gè)數(shù)據(jù)元素，必須先找到第 i-1 個(gè)數(shù)據(jù)元素。因此，查找第 i 個(gè)數(shù)據(jù)元素的基本操作為：移動(dòng)指針，比較 j 和 i 1、鏈接存儲(chǔ)方法鏈接方式存儲(chǔ)的線性表簡(jiǎn)稱為鏈表（Linked List）。鏈表的具體存儲(chǔ)表示為： 用一組任意的存儲(chǔ)單元來(lái)存放線性表的結(jié)點(diǎn)（這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的） 鏈表中結(jié)點(diǎn)的邏輯次

14、序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址（或位置）信息（稱為指針（pointer）或鏈(link)）注意：鏈?zhǔn)酱鎯?chǔ)是最常用的存儲(chǔ)方式之一，它不僅可用來(lái)表示線性表，而且可用來(lái)表示各種非線性的數(shù)據(jù)結(jié)構(gòu)。2、鏈表的結(jié)點(diǎn)結(jié)構(gòu)datanext data域-存放結(jié)點(diǎn)值的數(shù)據(jù)域next域-存放結(jié)點(diǎn)的直接后繼的地址（位置）的指針域（鏈域）注意：鏈表通過(guò)每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯順序鏈接在一起的。每個(gè)結(jié)點(diǎn)只有一個(gè)鏈域的鏈表稱為單鏈表（Single Linked List）。【例】線性表（bat，cat，eat，fat，hat，j

15、at，lat，mat）的單鏈表示如示意圖3、頭指針head和終端結(jié)點(diǎn)指針域的表示單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其前趨結(jié)點(diǎn)next域中，而開(kāi)始結(jié)點(diǎn)無(wú)前趨，故應(yīng)設(shè)頭指針head指向開(kāi)始結(jié)點(diǎn)。注意：鏈表由頭指針唯一確定，單鏈表可以用頭指針的名字來(lái)命名。【例】頭指針名是head的鏈表可稱為表head。終端結(jié)點(diǎn)無(wú)后繼，故終端結(jié)點(diǎn)的指針域?yàn)榭眨碞ULL。4、單鏈表的一般圖示法由于我們常常只注重結(jié)點(diǎn)間的邏輯順序，不關(guān)心每個(gè)結(jié)點(diǎn)的實(shí)際位置，可以用箭頭來(lái)表示鏈域中的指針，線性表（bat，cat，fat，hat，jat，lat，mat）的單鏈表就可以表示為下圖形式。5、單鏈表類型描述typedef char

16、 DataType; /假設(shè)結(jié)點(diǎn)的數(shù)據(jù)域類型為字符typedef struct node /結(jié)點(diǎn)類型定義DataType data; /結(jié)點(diǎn)的數(shù)據(jù)域struct node *next;/結(jié)點(diǎn)的指針域ListNodetypedef ListNode *LinkList;ListNode *p;LinkList head;注意：*LinkList和ListNode是不同名字的同一個(gè)指針類型（命名的不同是為了概念上更明確）*LinkList類型的指針變量head表示它是單鏈表的頭指針ListNode類型的指針變量p表示它是指向某一結(jié)點(diǎn)的指針6、指針變量和結(jié)點(diǎn)變量 指針變量結(jié)點(diǎn)變量 定義 在變量說(shuō)明部

17、分顯式定義 在程序執(zhí)行時(shí)，通過(guò)標(biāo)準(zhǔn) 函數(shù)malloc生成 取值 非空時(shí)，存放某類型結(jié)點(diǎn) 實(shí)際存放結(jié)點(diǎn)各域內(nèi)容 的地址 操作方式 通過(guò)指針變量名訪問(wèn) 通過(guò)指針生成、訪問(wèn)和釋放 生成結(jié)點(diǎn)變量的標(biāo)準(zhǔn)函數(shù)p=( ListNode *)malloc(sizeof(ListNode)；/函數(shù)malloc分配一個(gè)類型為L(zhǎng)istNode的結(jié)點(diǎn)變量的空間,并將其首地址放入指針變量p中釋放結(jié)點(diǎn)變量空間的標(biāo)準(zhǔn)函數(shù) free(p)；/釋放p所指的結(jié)點(diǎn)變量空間結(jié)點(diǎn)分量的訪問(wèn) 利用結(jié)點(diǎn)變量的名字*p訪問(wèn)結(jié)點(diǎn)分量方法一：(*p).data和(*p).next方法二：p-data和p-next指針變量p和結(jié)點(diǎn)變量*p的關(guān)系

18、指針變量p的值結(jié)點(diǎn)地址結(jié)點(diǎn)變量*p的值結(jié)點(diǎn)內(nèi)容(*p).data的值p指針?biāo)附Y(jié)點(diǎn)的data域的值(*p).next的值*p后繼結(jié)點(diǎn)的地址*(*p).next)*p后繼結(jié)點(diǎn)注意： 若指針變量p的值為空（NULL），則它不指向任何結(jié)點(diǎn)。此時(shí)，若通過(guò)*p來(lái)訪問(wèn)結(jié)點(diǎn)就意味著訪問(wèn)一個(gè)不存在的變量，從而引起程序的錯(cuò)誤。 有關(guān)指針類型的意義和說(shuō)明方式的詳細(xì)解釋可見(jiàn)，在鏈表中插入結(jié)點(diǎn)只需要修改指針。但同時(shí)，若要在第 i 個(gè)結(jié)點(diǎn)之前插入元素，修改的是第 i-1 個(gè)結(jié)點(diǎn)的指針。因此，在單鏈表中第 i 個(gè)結(jié)點(diǎn)之前進(jìn)行插入的基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，然后修改其指向后繼的指針。雙端鏈表雙端鏈表與傳統(tǒng)的鏈

19、表非常相似，但是它有一個(gè)新增的特性：即對(duì)最后一個(gè)鏈結(jié)點(diǎn)的引用，就像對(duì)第一個(gè)鏈結(jié)點(diǎn)的引用一樣。對(duì)最后一個(gè)鏈結(jié)點(diǎn)的引用允許像在表頭一樣，在表尾直接插入一個(gè)鏈結(jié)點(diǎn)。當(dāng)然，仍然可以在普通的單鏈表的表尾插入一個(gè)鏈結(jié)點(diǎn)，方法是遍歷整個(gè)鏈表直到到達(dá)表尾，但是這種方法效率很低。對(duì)最后一個(gè)鏈結(jié)點(diǎn)的引用允許像在表頭一樣，在表尾直接插入一個(gè)鏈結(jié)點(diǎn)。當(dāng)然，仍然可以在普通的單鏈表的表尾插入一個(gè)鏈結(jié)點(diǎn)，方法是遍歷整個(gè)鏈表直到到達(dá)表尾，但是這種方法效率很低。像訪問(wèn)表頭一樣訪問(wèn)表尾的特性，使雙端鏈表更適合于一些普通鏈表不方便操作的場(chǎng)合，隊(duì)列的實(shí)現(xiàn)就是這樣一個(gè)情況。下面是一個(gè)雙端鏈表的例子。class Link3 public

20、 long dData; public Link3 next; / public Link3(long d) dData=d; / public void displayLink() System.out.print(dData+ ); /class FirstLastList private Link3 first; private Link3 last; / public FirstLastList() first=null; last=null; / public boolean isEmpty() return first=null; / public void insertFirst

21、(long dd) Link3 newLink=new Link3(dd); if(isEmpty() last=newLink; newLink.next=first; first=newLink; / public void insertLast(long dd) Link3 newLink=new Link3(dd); if(isEmpty() first=newLink; else last.next=newLink; last=newLink; / public long deleteFirst() long temp=first.dData; if(first.next=null)

22、 last=null; first=first.next; return temp; / public void displayList() System.out.print(List (first-last): ); Link3 current=first; while(current!=null) current.displayLink(); current=current.next; System.out.println(); /public class FirstLastApp public static void main(String args) FirstLastList the

23、List=new FirstLastList(); theList.insertFirst(22); theList.insertFirst(44); theList.insertFirst(66); theList.insertLast(11); theList.insertLast(33); theList.insertLast(55); theList.displayList(); theList.deleteFirst(); theList.deleteFirst(); theList.displayList(); 為了簡(jiǎn)單起見(jiàn)，在這個(gè)程序中，把每個(gè)鏈結(jié)點(diǎn)中的數(shù)據(jù)字段個(gè)數(shù)從兩個(gè)壓縮到一

24、個(gè)。這更容易顯示鏈結(jié)點(diǎn)的內(nèi)容。（記住，在一個(gè)正式的程序中，可能會(huì)有非常多的數(shù)據(jù)字段，或者對(duì)另外一個(gè)對(duì)象的引用，那個(gè)對(duì)象也包含很多數(shù)據(jù)字段。）這個(gè)程序在表頭和表尾各插入三個(gè)鏈點(diǎn)，顯示插入后的鏈表。然后刪除頭兩個(gè)鏈結(jié)點(diǎn)，再次顯示。注意在表頭重復(fù)插入操作會(huì)顛倒鏈結(jié)點(diǎn)進(jìn)入的順序，而在表尾的重復(fù)插入則保持鏈結(jié)點(diǎn)進(jìn)入的順序。雙端鏈表類叫做FirstLastList。它有兩個(gè)項(xiàng)，first和last，一個(gè)指向鏈表中的第一個(gè)鏈結(jié)點(diǎn)，另一個(gè)指向最后一個(gè)鏈結(jié)點(diǎn)。如果鏈表中只有一個(gè)鏈結(jié)點(diǎn)，first和last就都指向它，如果沒(méi)有鏈結(jié)點(diǎn)，兩者都為Null值。這個(gè)類有一個(gè)新的方法insertLast()，這個(gè)方法在表尾

25、插入一個(gè)新的鏈結(jié)點(diǎn)。這個(gè)過(guò)程首先改變last.next，使其指向新生成的鏈結(jié)點(diǎn)，然后改變last，使其指向新的鏈結(jié)點(diǎn)。插入和刪除方法和普通鏈表的相應(yīng)部分類似。然而，兩個(gè)插入方法都要考慮一種特殊情況，即插入前鏈表是空的。如果isEmpty()是真，那么insertFirst()必須把last指向新的鏈結(jié)點(diǎn)，insertLast()也必須把first指向新的鏈結(jié)點(diǎn)。如果用insertFirst()方法實(shí)現(xiàn)在表頭插入，first就指向新的鏈結(jié)點(diǎn)，用insertLast()方法實(shí)現(xiàn)在表尾插入，last就指向新的鏈結(jié)點(diǎn)。如果鏈表只有一個(gè)鏈結(jié)點(diǎn)，那么多表頭刪除也是一種特殊情況：last必須被賦值為null

26、值。不幸的是，用雙端鏈表也不能有助于刪除最后一個(gè)鏈結(jié)點(diǎn)，因?yàn)闆](méi)有一個(gè)引用指向倒數(shù)第二個(gè)鏈結(jié)點(diǎn)。如果最后一個(gè)鏈結(jié)點(diǎn)被刪除，倒數(shù)第二個(gè)鏈結(jié)點(diǎn)的Next字段應(yīng)該變成Null值。為了方便的刪除最后一個(gè)鏈結(jié)點(diǎn)，需要一個(gè)雙向鏈表。（當(dāng)然，也可以遍歷整個(gè)鏈表找到最后一個(gè)鏈結(jié)點(diǎn)，但是那樣做效率不是很高。）有序鏈表在有序鏈表中，數(shù)據(jù)是按照關(guān)鍵值有序排列的。有序鏈表的刪除常常是只限于刪除在鏈表頭部的最小鏈結(jié)點(diǎn)。不過(guò)，有時(shí)也用Find()方法和Delete()方法在整個(gè)鏈表中搜索某一特定點(diǎn)。一般，在大多數(shù)需要使用有序數(shù)組的場(chǎng)合也可以使用有序鏈表。有序鏈表優(yōu)于有序數(shù)組的地方是插入的速度，另外鏈表可以擴(kuò)展到全部有效的使

27、用內(nèi)存，而數(shù)組只能局限于一個(gè)固定的大小中。但是，有序鏈表實(shí)現(xiàn)起來(lái)比有序數(shù)組更困難一些。后而將看到一個(gè)有序鏈表的應(yīng)用：為數(shù)據(jù)排序。有序鏈表也可以用于實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，盡管堆是更常用的實(shí)現(xiàn)方法。在有序鏈表中插入一個(gè)數(shù)據(jù)項(xiàng)的Java代碼為了在一個(gè)有序鏈表中插入數(shù)據(jù)項(xiàng)，算法必須首先搜索鏈表，直到找到合適的位置：它恰好在第一個(gè)比它大的數(shù)據(jù)項(xiàng)的前面。當(dāng)算法找到了要插入的位置，用通常的方式插入數(shù)據(jù)項(xiàng)：把新鏈結(jié)點(diǎn)的Next字段指向下一個(gè)鏈結(jié)點(diǎn)，然后把前一個(gè)鏈結(jié)點(diǎn)的Next字段改為指向新的鏈結(jié)點(diǎn)。然而，需要考慮一些特殊情況：鏈結(jié)點(diǎn)有可以插在表頭，或者插在表尾。看一下這段代碼：Public void insert(

28、long key)Link newLink=new Link(key);Link previous=null;Link current=first;While(current!=null & keycurrent.dData)Previous=current;Current=current.next;If(previous=null)First=newLink;ElsePrevious.next=newLink;newLink.next=current;在鏈表上移動(dòng)時(shí)，需要用一個(gè)previous引用，這樣才能把前一個(gè)鏈結(jié)點(diǎn)的Next字段指向新的鏈結(jié)點(diǎn)。創(chuàng)建新鏈結(jié)點(diǎn)后，把current變量設(shè)為f

29、irst，準(zhǔn)備搜索正確的插入點(diǎn)。這時(shí)也把previous設(shè)為Null值，這步操作很重要，因?yàn)楹竺嬉眠@個(gè)Null值判斷是否仍在表頭。While循環(huán)和以前用來(lái)搜索插入點(diǎn)的代碼類似，但是有一個(gè)附加的條件。如果當(dāng)前檢查的鏈結(jié)點(diǎn)的關(guān)鍵值不再小于待插入的鏈結(jié)點(diǎn)的關(guān)鍵值，則循環(huán)結(jié)束；這是最常見(jiàn)的情況，即新關(guān)鍵值插在鏈表中部的某個(gè)地方。然而，如果current為Null值，while循環(huán)也會(huì)停止。這種情況發(fā)生在表尾，或者鏈表為空時(shí)。如果current在表頭或者鏈表為空，previous將為Null值；所以讓first指向新的鏈結(jié)點(diǎn)。否則current處在鏈表中部或結(jié)尾，就使previous的next字段指向

30、新的鏈結(jié)點(diǎn)。不論哪種情況、都讓新鏈結(jié)點(diǎn)的Next字段指向current。如果在表尾，current為Null值，則新鏈結(jié)點(diǎn)的Next字段也本應(yīng)該設(shè)為這個(gè)值（Null）。下面是有序鏈表的程序SortedList.java程序?qū)崿F(xiàn)了一個(gè)SortedList類，它擁有insert()、remove()和displayList()方法。只有insert()方法與無(wú)序鏈表中的insert()方法不同。package 有序鏈表;class Linkpublic long dData;public Link next;public Link(long dd)dData=dd;/public void dis

31、playLink()System.out.print(dData+ );/class SortedListprivate Link first;/public SortedList()first=null;/public boolean isEmpty()return (first=null);/public void insert(long key)Link newLink=new Link(key);Link previous=null;Link current=first;while(current!=null & keycurrent.dData)previous=current;cu

32、rrent=current.next;if(previous=null)first=newLink;elseprevious.next=newLink;newLink.next=current;/public Link remove()Link temp=first;first=first.next;return temp;/public void displayList()System.out.print(List (first-last): );Link current=first;while(current!=null)current.displayLink();current=curr

33、ent.next;System.out.println();public class SortedLinkApp public static void main(String args) SortedList theSortedList=new SortedList();theSortedList.insert(20);theSortedList.insert(40);theSortedList.displayList();theSortedList.insert(10);theSortedList.insert(30);theSortedList.insert(50);theSortedLi

34、st.displayList();theSortedList.remove();theSortedList.displayList();System.exit(0);在Main()方法中，插入值為20和40的兩個(gè)鏈結(jié)點(diǎn)。然后再插入三個(gè)鏈結(jié)點(diǎn)，分別是10、30和50。這三個(gè)值分別插在表頭、表中和表尾。這說(shuō)明insert()方法正確地處理了特殊情況。最后刪除了一個(gè)鏈結(jié)點(diǎn)，表現(xiàn)出刪除操作總是從表頭進(jìn)行。每一步變化后，都顯示整個(gè)鏈表。雙向鏈表雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開(kāi)始，都可以很方便地訪問(wèn)它的前驅(qū)結(jié)點(diǎn)

35、和后繼結(jié)點(diǎn)。一般我們都構(gòu)造雙向循環(huán)鏈表。/* 線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu) */typedef struct DuLNodeElemType data;struct DuLNode *prior,*next;DuLNode,*DuLinkList;/*帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表的基本操作(14個(gè)) */void InitList(DuLinkList *L) /* 產(chǎn)生空的雙向循環(huán)鏈表L */*L=(DuLinkList)malloc(sizeof(DuLNode);if(*L)(*L)-next=(*L)-prior=*L;elseexit(OVERFLOW);void DestroyList(Du

36、LinkList *L) /* 操作結(jié)果：銷毀雙向循環(huán)鏈表L */DuLinkList q,p=(*L)-next; /* p指向第一個(gè)結(jié)點(diǎn) */while(p!=*L) /* p沒(méi)到表頭 */q=p-next;free(p);p=q;free(*L);*L=NULL;void ClearList(DuLinkList L) /* 不改變L */ /* 初始條件：L已存在。操作結(jié)果：將L重置為空表 */DuLinkList q,p=L-next; /* p指向第一個(gè)結(jié)點(diǎn) */while(p!=L) /* p沒(méi)到表頭 */q=p-next;free(p);p=q;L-next=L-prior=L

37、; /* 頭結(jié)點(diǎn)的兩個(gè)指針域均指向自身 */Status ListEmpty(DuLinkList L) /* 初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE */if(L-next=L&L-prior=L)return TRUE;elsereturn FALSE;int ListLength(DuLinkList L) /* 初始條件：L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù) */int i=0;DuLinkList p=L-next; /* p指向第一個(gè)結(jié)點(diǎn) */while(p!=L) /* p沒(méi)到表頭 */i+;p=p-next;return i;St

38、atus GetElem(DuLinkList L,int i,ElemType *e) /* 當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給e并返回OK，否則返回ERROR */int j=1; /* j為計(jì)數(shù)器 */DuLinkList p=L-next; /* p指向第一個(gè)結(jié)點(diǎn) */while(p!=L&jnext;j+;if(p=L|ji) /* 第i個(gè)元素不存在 */return ERROR;*e=p-data; /* 取第i個(gè)元素 */return OK;int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType

39、) /* 初始條件：L已存在，compare()是數(shù)據(jù)元素判定函數(shù) */* 操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序。 */* 若這樣的數(shù)據(jù)元素不存在，則返回值為0 */int i=0;DuLinkList p=L-next; /* p指向第1個(gè)元素 */while(p!=L)i+;if(compare(p-data,e) /* 找到這樣的數(shù)據(jù)元素 */return i;p=p-next;return 0;Status PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e) /* 操作結(jié)果：若cur_e是L的數(shù)

40、據(jù)元素，且不是第一個(gè)，則用pre_e返回它的前驅(qū)， */* 否則操作失敗，pre_e無(wú)定義 */DuLinkList p=L-next-next; /* p指向第2個(gè)元素 */while(p!=L) /* p沒(méi)到表頭 */if(p-data=cur_e)*pre_e=p-prior-data;return TRUE;p=p-next;return FALSE;Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e) /* 操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼， */* 否則操作失敗，

41、next_e無(wú)定義 */DuLinkList p=L-next-next; /* p指向第2個(gè)元素 */while(p!=L) /* p沒(méi)到表頭 */if(p-prior-data=cur_e)*next_e=p-data;return TRUE;p=p-next;return FALSE;DuLinkList GetElemP(DuLinkList L,int i) /* 另加 */ /* 在雙向鏈表L中返回第i個(gè)元素的地址。i為0，返回頭結(jié)點(diǎn)的地址。若第i個(gè)元素不存在，*/* 返回NULL */int j;DuLinkList p=L; /* p指向頭結(jié)點(diǎn) */if(iListLength

42、(L) /* i值不合法 */return NULL;for(j=1;jnext;return p;Status ListInsert(DuLinkList L,int i,ElemType e) /* 在帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表L中第i個(gè)位置之前插入元素e，i的合法值為1i表長(zhǎng)+1 */* 改進(jìn)算法2.18，否則無(wú)法在第表長(zhǎng)+1個(gè)結(jié)點(diǎn)之前插入元素 */DuLinkList p,s;if(iListLength(L)+1) /* i值不合法 */return ERROR;p=GetElemP(L,i-1); /* 在L中確定第i個(gè)元素前驅(qū)的位置指針p */if(!p) /* p=NULL,即第

43、i個(gè)元素的前驅(qū)不存在(設(shè)頭結(jié)點(diǎn)為第1個(gè)元素的前驅(qū)) */return ERROR;s=(DuLinkList)malloc(sizeof(DuLNode);if(!s)return OVERFLOW;s-data=e;s-prior=p; /* 在第i-1個(gè)元素之后插入 */s-next=p-next;p-next-prior=s;p-next=s;return OK;Status ListDelete(DuLinkList L,int i,ElemType *e) /* 刪除帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表L的第i個(gè)元素，i的合法值為1i表長(zhǎng) */DuLinkList p;if(idata;p-pr

44、ior-next=p-next;p-next-prior=p-prior;free(p);return OK;void ListTraverse(DuLinkList L,void(*visit)(ElemType) /* 由雙鏈循環(huán)線性表L的頭結(jié)點(diǎn)出發(fā)，正序?qū)γ總€(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit() */DuLinkList p=L-next; /* p指向頭結(jié)點(diǎn) */while(p!=L)visit(p-data);p=p-next;printf(n);void ListTraverseBack(DuLinkList L,void(*visit)(ElemType) /* 由雙鏈循環(huán)線性表L的頭

45、結(jié)點(diǎn)出發(fā)，逆序?qū)γ總€(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit()。另加 */DuLinkList p=L-prior; /* p指向尾結(jié)點(diǎn) */while(p!=L)visit(p-data);p=p-prior;printf(n);迭代器迭代器是一種對(duì)象，它能夠用來(lái)遍歷STL容器中的部分或全部元素，每個(gè)迭代器對(duì)象代表容器中的確定的地址。迭代器修改了常規(guī)指針的接口，所謂迭代器是一種概念上的抽象：那些行為上象迭代器的東西都可以叫做迭代器。然而迭代器有很多不同的能力，它可以把抽象容器和通用算法有機(jī)的統(tǒng)一起來(lái)。迭代器提供一些基本操作符：*、+、=、！=、=。這些操作和C/C+“操作array元素”時(shí)的指針接口一致

46、。不同之處在于，迭代器是個(gè)所謂的smart pointers，具有遍歷復(fù)雜數(shù)據(jù)結(jié)構(gòu)的能力。其下層運(yùn)行機(jī)制取決于其所遍歷的數(shù)據(jù)結(jié)構(gòu)。因此，每一種容器型別都必須提供自己的迭代器。事實(shí)上每一種容器都將其迭代器以嵌套的方式定義于內(nèi)部。因此各種迭代器的接口相同，型別卻不同。這直接導(dǎo)出了泛型程序設(shè)計(jì)的概念：所有操作行為都使用相同接口，雖然它們的型別不同。 功能迭代器使開(kāi)發(fā)人員能夠在類或結(jié)構(gòu)中支持foreach迭代，而不必整個(gè)實(shí)現(xiàn)IEnumerable或者IEnumerator接口。只需提供一個(gè)迭代器，即可遍歷類中的數(shù)據(jù)結(jié)構(gòu)。當(dāng)編譯器檢測(cè)到迭代器時(shí)，將自動(dòng)生成IEnumerable接口或者IEnumerat

47、or接口的Current，MoveNext和Dispose方法。 特點(diǎn)1.迭代器是可以返回相同類型值的有序序列的一段代碼； 2.迭代器可用作方法、運(yùn)算符或get訪問(wèn)器的代碼體； 3.迭代器代碼使用yield return語(yǔ)句依次返回每個(gè)元素，yield break將終止迭代；4.可以在類中實(shí)現(xiàn)多個(gè)迭代器，每個(gè)迭代器都必須像任何類成員一樣有惟一的名稱，并且可以在foreach語(yǔ)句中被客戶端代碼調(diào)用； 5.迭代器的返回類型必須為IEnumerable和IEnumerator中的任意一種；6.迭代器是產(chǎn)生值的有序序列的一個(gè)語(yǔ)句塊，不同于有一個(gè) 或多個(gè)yield語(yǔ)句存在的常規(guī)語(yǔ)句塊； 7.迭代器不是一

48、種成員，它只是實(shí)現(xiàn)函數(shù)成員的方式，理解這一點(diǎn)是很重要的，一個(gè)通過(guò)迭代器實(shí)現(xiàn)的成員，可以被其他可能或不可能通過(guò)迭代器實(shí)現(xiàn)的成員覆蓋和重載； 8.迭代器塊在C#語(yǔ)法中不是獨(dú)特的元素，它們?cè)趲讉€(gè)方面受到限制，并且主要作用在函數(shù)成員聲明的語(yǔ)義上，它們?cè)谡Z(yǔ)法上只是語(yǔ)句塊而已； 四、遞歸遞歸是函數(shù)調(diào)用自身的一種特殊的編程技術(shù)，其應(yīng)用主要在以下幾個(gè)方面：階乘在java當(dāng)中的基本形式是：Public void mothed（int n）/當(dāng)滿足某條件時(shí)： Mothed（n-1）；遞歸二分查找Java二分查找實(shí)現(xiàn),歡迎大家提出交流意見(jiàn)./*名稱:BinarySearch*功能:實(shí)現(xiàn)了折半查找(二分查找)的遞歸和

49、非遞歸算法.*說(shuō)明:* 1、要求所查找的數(shù)組已有序,并且其中元素已實(shí)現(xiàn)Comparable接口,如Integer、String等.*2、非遞歸查找使用search();,遞歸查找使用searchRecursively();*本程序僅供編程學(xué)習(xí)參考*author: Winty*date: 2008-8-11*email:emailwintys/email*/class BinarySearchT extends Comparable private Tdata;/要排序的數(shù)據(jù)public BinarySearch(T data)this.data = data;public int search

50、(T key)int low;int high;int mid;if(data = null)return -1;low = 0;high = data.length - 1;while(low = high)mid = (low + high) / 2;System.out.println(mid + mid + mid value: + datamid);/if(pareTo(datamid) 0)low = mid + 1;else if(pareTo(datamid) = 0)return mid;return -1;private int doSearchRecursively(in

51、t low , int high , T key)int mid;int result;if(low = high)mid = (low + high) / 2;result = pareTo(datamid);System.out.println(mid + mid + mid value: + datamid);/if(result 0)return doSearchRecursively(mid + 1 , high , key);else if(result = 0)return mid;return -1;public int searchRecursively(T key)if(d

52、ata =null)return -1;return doSearchRecursively(0 , data.length - 1 , key);public static void main(String args)Integer data = 1 ,4 ,5 ,8 ,15 ,33 ,48 ,77 ,96;BinarySearch binSearch = new BinarySearch(data);/System.out.println(Key index: + binSearch.search(33) );System.out.println(Key index: + binSearc

53、h.searchRecursively(3) );/String dataStr = A ,C ,F ,J ,L ,N ,T;/BinarySearch binSearch = new BinarySearch(dataStr);/System.out.println(Key index: + binSearch.search(A) );遞歸排序其實(shí)在數(shù)組的全排序中完全可以使用更加易懂簡(jiǎn)便的寫法for循環(huán)，但是通過(guò)for循環(huán)編寫數(shù)組全排序需要有一個(gè)先決條件知道數(shù)組全排序的個(gè)數(shù)，因?yàn)橛衝個(gè)數(shù)據(jù)全排序就需要寫n個(gè)嵌套for循環(huán)。因此在寫全排序時(shí)一般使用遞歸方法。這就是我的第一個(gè)關(guān)于遞歸排序的見(jiàn)解遞

54、歸排序可以無(wú)需已知排序數(shù)組的長(zhǎng)度，即排序個(gè)數(shù)！ 其二，不管是使用遞歸進(jìn)行數(shù)組排序還是使用for循環(huán)進(jìn)行數(shù)組的排序，它們都是本質(zhì)都是使用枚舉，因此可以得出這樣一個(gè)結(jié)論:枚舉可以確保找出每一種可能的排序規(guī)則！其三，枚舉是列出所有的方法并找出符合要求的算法，因此其算法效率一定比較的低，需要對(duì)其進(jìn)行優(yōu)化，才能達(dá)到較好的效果（遞歸的時(shí)候排除所有不可能的方案）消除遞歸消除遞歸的基本思路是用棧來(lái)模擬系統(tǒng)的函數(shù)調(diào)用從而消除遞歸。基本上要做一下三件事：傳遞參數(shù)（包括返回地址）并轉(zhuǎn)到函數(shù)入口；獲得參數(shù)并處理參數(shù)；根據(jù)傳入的返回地址返回五、哈希表一般的線性表、樹(shù)中，記錄在結(jié)構(gòu)中的相對(duì)位置是隨機(jī)的即和記錄的關(guān)鍵字之間

55、不存在確定的關(guān)系，在結(jié)構(gòu)中查找記錄時(shí)需進(jìn)行一系列和關(guān)鍵字的比較。這一類查找方法建立在“比較”的基礎(chǔ)上，查找的效率與比較次數(shù)密切相關(guān)。理想的情況是能直接找到需要的記錄，因此必須在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一確定的對(duì)應(yīng)關(guān)系f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。因而查找時(shí)，只需根據(jù)這個(gè)對(duì)應(yīng)關(guān)系f找到給定值K的像f(K)。若結(jié)構(gòu)中存在關(guān)鍵字和K相等的記錄，則必定在f(K)的存儲(chǔ)位置上，由此不需要進(jìn)行比較便可直接取得所查記錄。在此，稱這個(gè)對(duì)應(yīng)關(guān)系f為哈希函數(shù)，按這個(gè)思想建立的表為哈希表（又稱為雜湊法或散列表）。哈希表不可避免沖突(collision)現(xiàn)象：對(duì)不同的關(guān)鍵字可能得到同一哈

56、希地址 即key1key2，而f(key1)=f(key2)。具有相同函數(shù)值的關(guān)鍵字對(duì)該哈希函數(shù)來(lái)說(shuō)稱為同義詞(synonym)。 因此，在建造哈希表時(shí)不僅要設(shè)定一個(gè)好的哈希函數(shù)，而且要設(shè)定一種處理沖突的方法。可如下描述哈希表：根據(jù)設(shè)定的哈希函數(shù)H(key)和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個(gè)有限的、地址連續(xù)的地址集(區(qū)間)上并以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲(chǔ)位置，這種表被稱為哈希表。六、高級(jí)排序下周提供。七、二叉樹(shù)二叉樹(shù)？答：二叉樹(shù)是一種樹(shù)型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹(shù)（即二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)),并且,二叉樹(shù)的子樹(shù)有左右之分,其次序不能任意顛

57、倒。.二叉樹(shù)的基本形態(tài)：(1)空二叉樹(shù)；(2)只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)；(3)右子樹(shù)為空的二叉樹(shù)；4)左子樹(shù)為空的二叉樹(shù)；(5)完全二叉樹(shù)。二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 包括：1.順序存儲(chǔ)結(jié)構(gòu) 連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹(shù)的數(shù)據(jù)元素。例如圖 6.4(b)的完全二叉樹(shù) , 可以向量 (一維數(shù)組 ) bt(1:6)作它的存儲(chǔ)結(jié)構(gòu)，將二叉樹(shù)中編號(hào)為 i的結(jié)點(diǎn)的數(shù)據(jù)元素存放在分量 bti中 ,如圖 6.6(a) 所示。但這種順序存儲(chǔ)結(jié)構(gòu)僅適合于完全二叉樹(shù) ,而一般二叉樹(shù)也按這種形式來(lái)存儲(chǔ) ,這將造成存 貯浪費(fèi)。如和圖 6.4(c)的二叉樹(shù)相應(yīng)的存儲(chǔ)結(jié)構(gòu)圖 6.6(b)所示，圖中以 “0”表示不存在此結(jié)點(diǎn) . 2. 鏈?zhǔn)?/p>

58、存儲(chǔ)結(jié)構(gòu) 由二叉樹(shù)的定義得知二叉樹(shù)的結(jié)點(diǎn)由一個(gè)數(shù)據(jù)元素和分別指向左右子樹(shù)的兩個(gè)分支構(gòu)成 ,則表 示二叉樹(shù)的鏈表中的結(jié)點(diǎn)至少包含三個(gè)域 :數(shù)據(jù)域和左右指針域 ,如圖 (b)所示。有時(shí) ,為了便于找 到結(jié)點(diǎn)的雙親 ,則還可在結(jié)點(diǎn)結(jié)構(gòu)中增加一個(gè)指向其雙親受的指針域，如圖 6.7(c)所示。 遍歷二叉樹(shù)： 遍歷二叉樹(shù) (traversing binary tree)的問(wèn)題， 即如何按某條搜索路徑巡訪樹(shù)中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次。 其中常見(jiàn)的有三種情況：分別稱之為先 (根 )序遍歷，中 (根 )序遍歷和后 (根 )序遍歷。 （1）前序遍歷 前序遍歷運(yùn)算：即先訪問(wèn)根結(jié)點(diǎn)，再前序

59、遍歷左子樹(shù)，最后再前序遍歷右子樹(shù)。前序遍歷運(yùn)算訪問(wèn)二叉樹(shù)各結(jié)點(diǎn)是以根、左、右的順序進(jìn)行訪問(wèn)的（2）中序遍歷 中序遍歷運(yùn)算：即先中前序遍歷左子樹(shù)，然后再訪問(wèn)根結(jié)點(diǎn)，最后再中序遍歷右子樹(shù)。中序遍歷運(yùn)算訪問(wèn)二叉樹(shù)各結(jié)點(diǎn)是以左、根、右的順序進(jìn)行訪問(wèn)的（3）后序遍歷 后序遍歷運(yùn)算：即先后序遍歷左子樹(shù)，然后再后序遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。后序遍歷運(yùn)算訪問(wèn)二叉樹(shù)各結(jié)點(diǎn)是以左、右、根的順序進(jìn)行訪問(wèn)的八、紅黑樹(shù)概念紅黑樹(shù)是一種自平衡二叉查找樹(shù)，是在計(jì)算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)，典型的用途是實(shí)現(xiàn)關(guān)聯(lián)數(shù)組。它是在1972年由Rudolf Bayer發(fā)明的，他稱之為對(duì)稱二叉B樹(shù)，它現(xiàn)代的名字是在 Leo J. G

60、uibas 和 Robert Sedgewick 于1978年寫的一篇論文中獲得的。它是復(fù)雜的，但它的操作有著良好的最壞情況運(yùn)行時(shí)間，并且在實(shí)踐中是高效的: 它可以在O(log n)時(shí)間內(nèi)做查找，插入和刪除，這里的n 是樹(shù)中元素的數(shù)目。紅黑樹(shù)是一種很有意思的平衡檢索樹(shù)。它的統(tǒng)計(jì)性能要好于平衡二叉樹(shù)(有些書(shū)籍根據(jù)作者姓名，Adelson-Velskii和Landis，將其稱為AVL-樹(shù))，因此，紅黑樹(shù)在很多地方都有應(yīng)用。在C+ STL中，很多部分(目前包括set, multiset, map, multimap)應(yīng)用了紅黑樹(shù)的變體(SGI STL中的紅黑樹(shù)有一些變化，這些修改提供了更好的性能，以