1、Java數(shù)據(jù)結(jié)構(gòu)和算法一、數(shù)組于簡(jiǎn)單排序 i二、棧與隊(duì)列 4三、鏈表 7四、遞歸 22五、哈希表 25六、高級(jí)排序 25七、二叉樹 25八、紅一黑樹 26九、堆 36十、帶權(quán)圖 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ì)上是相同類型變量歹U表。要?jiǎng)?chuàng)建一 個(gè)數(shù)組，你必須首先定義數(shù)組變量所需的類型。通用的一維數(shù)組的聲明格式是：type var-name;

2、獲得一個(gè)數(shù)組需要2步。第一步，你必須定義變量所需的類型。第二步，你 必須使用運(yùn)算符new來(lái)為數(shù)組所要存儲(chǔ)的數(shù)據(jù)分配內(nèi)存，并把它們分配給數(shù)組 變量。這樣Java中的數(shù)組被動(dòng)態(tài)地分配。如果動(dòng)態(tài)分配的概念對(duì)你陌生，別擔(dān) 心，它將在本書的后面詳細(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)(在這

3、方面，Java與C/C+從根本上不同，C/C+不提供運(yùn)行邊界檢查)多維數(shù)組在Java中，多維數(shù)組(multidimensional arrays )實(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)作

4、都不做，繼續(xù)比較第 1個(gè)第2 個(gè)，,這樣依次類推，直至所有數(shù)據(jù)都“冒泡”到數(shù)據(jù)頂上。冒泡排序的的java代碼：Public void bubbleSort()int in，out;for(out=nElems-1;out>0;out-)for(in=0;in<out;in+)If(ain>ain+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ù)為

5、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ù)交換，依次類推；選擇排序的java代碼：Public void selectSort()(Int in,out,min;For(out=0;out<nElems-1;out+)(Min=out;For(in=out+1;in<nElems;in+)If(ain<amin)Min=in;Swap(out,min);選擇排序的效率：O (N*N)，比較N*N/2，交換<N;選擇排

6、序與冒泡排序比 較，比較次數(shù)沒(méi)有明顯改變，但交換次數(shù)明顯減少了很多；3. 插入排序的思想：插入排序是在部分?jǐn)?shù)據(jù)有序的情況下，使用OUT標(biāo)記第一個(gè)無(wú)序的數(shù)據(jù)，將其提取保存到一個(gè)中間變量temp中去，使用IN標(biāo)記空位置，依次比較temp中 的值與IN-1的值，如果IN-值大于temp的值，貝U后移，直到遇到第一個(gè)比temp 小的值，在其下一個(gè)位置插入；插入排序的java代碼：Public void InsertionSort()Int in,out;For(out=1;out<nElems;out+)Long temp=aoutIn=out;While(in>0&& a

7、in-1>temp)(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) 通常稱插入、刪除的這一端為 棧頂(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)行。

8、每次刪除( 退棧)的總是當(dāng)前棧中" 最新”的元素，即最后插入(進(jìn)棧)的元素，而最先插入的是被放在棧的底部， 要到最后才能刪除。進(jìn)棧【示例】元素是以al, a2, , , an的順序進(jìn)棧，退棧的次序卻是an, an-1 ,al。2、棧的基本運(yùn)算(1) InitStack (S)構(gòu)造一個(gè)空棧S。(2) StackEmpty (S)判棧空。若S為空棧，則返回TRUE否則返回FALSE(3) StackFull (S)判棧滿。若S為滿棧，則返回TRUE否則返回FALSE注意：該運(yùn)算只適用丁棧的順序存儲(chǔ)結(jié)構(gòu)。(4) Push (S, x)進(jìn)棧。若棧S不滿，則將元素x插入S的棧頂。(5) Pop

9、 (S)退棧。若棧S非空，則將S的棧頂元素刪去，并返回該元素。(6) StackTop (S)取棧頂元素。若棧S非空，則返回棧頂元素，但不改變棧的狀態(tài)隊(duì)列的定義及基本運(yùn)算1、定義隊(duì)列(Queue是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的運(yùn)算受 限的線性表出亂 甲 御 珀 入隊(duì)隊(duì)頭隊(duì)尾隊(duì)列示點(diǎn):圖(1) 允許刪除的一端稱為 隊(duì)頭(Front )。(2) 允許插入的一端稱為隊(duì)尾(Rear)。(3) 當(dāng)隊(duì)列中沒(méi)有元素時(shí)稱為 空隊(duì)列。(4) 隊(duì)列亦稱作先進(jìn)先出(First In First Out )的線性表，簡(jiǎn)稱為FIFO 表0隊(duì)列的修改是依先進(jìn)先出的原則進(jìn)行的。 新來(lái)的成員總是加入隊(duì)尾(即不 允

10、許”加塞”)，每次離開(kāi)的成員總是隊(duì)列頭上的(不允許中途離隊(duì))，即當(dāng)前 " 最老的”成員離隊(duì)。【例】在隊(duì)列中依次加入元素 ai, a2, , , an之后，ai是隊(duì)頭元素，an是隊(duì)尾 元素。退出隊(duì)列的次序只能是 ai, 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) EnQueue (Q, x)若隊(duì)列Q非滿，貝U將元素x插入

11、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)。二、鏈表1. 鏈結(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)的引用單鏈表數(shù)據(jù)元素i個(gè)數(shù)據(jù)元素，必須先找到第 i-1個(gè)數(shù)用一組地址任意的存儲(chǔ)單元存放線性表

12、中的以元素(數(shù)據(jù)元素的映象 )+指針(指示后繼元素存儲(chǔ)位置 )=結(jié)點(diǎn)(表示數(shù)據(jù)元素或 數(shù)據(jù)元素的映象 )以結(jié)點(diǎn)的序列”表示線性表稱作線性鏈表(單鏈表)單鏈表是一種順序存取的結(jié)構(gòu)，為找第 據(jù)元素。因此，查找第 i個(gè)數(shù)據(jù)元素的基本操作為：移動(dòng)指針，比較j和i1、鏈接存儲(chǔ)方法鏈接方式存儲(chǔ)的線性表簡(jiǎn)稱為鏈表( Linked List )。鏈表的具體存儲(chǔ)表示為：(這組存儲(chǔ)單元既可以是連續(xù)的, 用一組任意的存儲(chǔ)單元來(lái)存放線性表的結(jié)點(diǎn) 也可以是不連續(xù)的) 鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏 輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址(或位置)信 息(稱為指

13、針(pointer )或鏈(link)注意：鏈?zhǔn)酱鎯?chǔ)是最常用的存儲(chǔ)方式之一，它不僅可用來(lái)表示線性表，而且可用來(lái)表示 各種非線性的數(shù)據(jù)結(jié)構(gòu)。2、鏈表的結(jié)點(diǎn)結(jié)構(gòu)data nextdata域-存放結(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 , jat, lat , mat)的單鏈表示如示意圖3、頭指針 head和終端結(jié)點(diǎn)指針域的表示單鏈表中每個(gè)結(jié)點(diǎn)的

14、存儲(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 DataType;/假設(shè)結(jié)點(diǎn)的數(shù)據(jù)域類型為字符typedef struct no

15、de 結(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)變量11111指針變量 1結(jié)點(diǎn)變量LJ11定義1在變量說(shuō)明部分顯式定義函數(shù)malloc生成1111在程序執(zhí)行時(shí)，通過(guò)標(biāo)

16、準(zhǔn)1111取值1非空時(shí)，存放某類型結(jié)點(diǎn)11實(shí)際存放結(jié)點(diǎn)各域內(nèi)容1的地址111111操作方式1通過(guò)指針變量名訪1可1111通過(guò)指針生成、訪問(wèn)和釋放11 生成結(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)

17、變量*p的關(guān)系指針變量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)，然后修改其指向后繼的指針。雙端鏈

18、表雙端鏈表與傳統(tǒng)的鏈表非常相似，但是它有一個(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

19、 Link3(public long dData;public Link3 next;/public Link3(long d)(dData=d;/public void displayLink()System.out.print(dData+" ");/class FirstLastListprivateLink3 first;privateLink3 last;/public FirstLastList()first=null;last=null;/public boolean isEmpty()return first=null;/public void insert

20、First(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;elselast.next=newLink;last=newLink;/public long deleteFirst()(long temp=first.dData;if(first.next=null)last=null

21、;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) ( Firs

22、tLastList theList=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è)壓

23、縮到一個(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

24、(),這個(gè)方法在表尾插入一個(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)，那么多表頭刪除也是一

25、種特殊情況：last必須被賦值為null值。不幸的是，用雙端鏈表也不能有助于刪除最后一個(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ù) 組的地方

26、是插入的速度，另外鏈表可以擴(kuò)展到全部有效的使用內(nèi)存，而數(shù)組只能局限 于一個(gè)固定的大小中。但是，有序鏈表實(shí)現(xiàn)起來(lái)比有序數(shù)組更困難一些。為數(shù)據(jù)排序。有序鏈表也可以用于實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列,后而將看到一個(gè)有序鏈表的應(yīng)用：盡管堆是更常用的實(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)的向下一個(gè)鏈結(jié)點(diǎn)，然后把前一個(gè)鏈結(jié)點(diǎn)的Next字段改為指向新的鏈結(jié)點(diǎn)。要考慮一些特殊情況：鏈結(jié)點(diǎn)有可以插在表頭，或者插在表尾。看一下這段代碼：Next字段

27、指然而，需Public void insert(longkey)Link newLink=newLink(key);Link previous=null;Link current=first;While(current!=null&& key>current.dData)Previous=current;Current=current.next;If(previous=null)First=newLink;ElsePrevious.next=newLink;newLink.next=current;Next字段在鏈表上移動(dòng)時(shí)，需要用一個(gè)previous引用，這樣才能把前一

28、個(gè)鏈結(jié)點(diǎn)的指向新的鏈結(jié)點(diǎn)。創(chuàng)建新鏈結(jié)點(diǎn)后，把 current變量設(shè)為first ,準(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é)

29、點(diǎn)。否則current處在鏈表中部或結(jié)尾，就使previous的next字段指向新的鏈結(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；

30、public Link(long dd)dData=dd；/public void displayLink()System.out.print(dData+" ")；/ class SortedListprivate Link first；/public SortedList()first=null；/public boolean isEmpty()return (first=null)；/public void insert(longkey)Link newLink=newLink(key)；Link previous=null；Link current=first；wh

31、ile(current!=null && key>current.dData)previous=current；current=current.next； if(previous=null) first=newLink; else previous.next=newLink; newLink.next=current;/public Link remove() Link temp=first; first=first.next; return temp;/public void displayList()System.out.print("List (first

32、->last): "); Link current=first; while(current!=null) current.displayLink(); current=current.next;System.out.println("");public class SortedLinkApp public static void main(String args) SortedList theSortedList=new SortedList(); theSortedList.insert(20);theSortedList.insert(40); the

33、SortedList.displayList(); theSortedList.insert(10); theSortedList.insert(30); theSortedList.insert(50); theSortedList.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è)鏈

34、結(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)和后繼結(jié)點(diǎn)。一般我們都構(gòu)造雙向循環(huán)鏈表。/*線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)*/typedef struct DuLNode(ElemType data;struct DuLNode *prior,*next;DuLNode,*DuLinkList;/*帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表的基本操作(14個(gè))*/void InitList(DuLinkList *L)( /*產(chǎn)

35、生空的雙向循環(huán)鏈表 L */*L=(DuLinkList)malloc(sizeof(DuLNode);if(*L)(*L)->next=(*L)->prior=*L;elseexit(OVERFLOW);void DestroyList(DuLinkList *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)

36、/* 不改變 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; /*頭結(jié)點(diǎn)的兩個(gè)指針域均指向自身*/Status ListEmpty(DuLinkList L)( /*初始條件：線性表 L已存在。操作結(jié)果：若 L為空表，則返回TRUE ,否則返回 FALSE */if(L->next=L&&L->prior=L)r

37、eturn 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;Status GetElem(DuLinkList L,int i,ElemType *e)( /*當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給e并返回OK,否則返回ERROR */int j=1; /* j為計(jì)數(shù)器*/DuLinkList p=

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

39、 */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;Status PriorElem(DuLinkListreturn 0;L,ElemType cur_e,ElemType *pre_e) /*操作結(jié)果：若 cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用 pre_e返回它的前驅(qū)，*/*否則操作失敗,pre_e無(wú)定義 */DuLinkList p=L->next->next; /* p 指向第

40、 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返回它的后繼，*/*否則操作失敗，next_e無(wú)定義 */DuLinkList p=L->next->next; /* p 指向第 2 個(gè)元素 */w

41、hile(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)的地址。若第 個(gè)元素不存在，*/* 返回 NULL */int j;DuLinkList p=L; /* p 指向頭結(jié)點(diǎn) */if(i<0|i>ListLength(L) /* i 值不合法*/return

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

43、=NULL,即第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的合法值為

44、1v i表長(zhǎng)*/DuLinkList p;if(i<1) /* i值不合法*/return ERROR;p=GetElemP(L,i); /*在L中確定第i個(gè)元素的位置指針p */if(!p) /* p=NULL,即第i個(gè)元素不存在*/return ERROR;*e=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);return OK;void ListTraverse(DuLinkList L,void(*visit)(ElemType)( /*由雙鏈循環(huán)線性表L的頭結(jié)

45、點(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的頭結(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);

46、p=p->prior;printf("n");迭代器迭代器是一種對(duì)象，它能夠用來(lái)遍歷STL容器中的部分或全部元素，每個(gè)迭代器對(duì)象代表容器中的確定的地址。迭代器修改了常規(guī)指針的接口，所謂迭代器是一種概念 上的抽象：那些行為上象迭代器的東西都可以叫做迭代器。然而迭代器有很多不同的 能力，它可以把抽象容器和通用算法有機(jī)的統(tǒng)一起來(lái)。迭代器提供一些基本操作符：*、+、=、！=、=。這些操作和C/C+"操作array元素”時(shí)的指針接口一致。不同之處在于，迭代器是個(gè)所謂的smart pointers ,具有遍歷復(fù)雜數(shù)據(jù)結(jié)構(gòu)的能力。其下層運(yùn)行機(jī)制取決于其所遍歷的數(shù)據(jù)結(jié)構(gòu)。因

47、此，每一種容 器型別都必須提供自己的迭代器。事實(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 接口或者IEnumerator 接口的Current ,MoveNext 和 Dispose 方法。特點(diǎn)1. 迭代器是可以返回相同類型值的有序序列的一段

48、代碼；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. 迭代器不是一種成員，它只是實(shí)現(xiàn)函數(shù)成員的方式，理解這一點(diǎn)是很重要的，一個(gè)通過(guò)迭代器實(shí)現(xiàn)的成員，可以被其他可能或不可能通過(guò)迭

49、代器實(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)中的基本形式是:遞歸二分查找Java二分查找實(shí)現(xiàn)/*名稱:BinarySearchPublic void mothed (int n) (/ 當(dāng)滿足某條件時(shí)： Mothed (n-1);，歡迎大家提出交流意見(jiàn).*功能：實(shí)現(xiàn)了折半查找(二分查找)的遞歸和非遞歸算法.*說(shuō)明：* 1、要求所查找的數(shù)組已有序，并且其中元素已實(shí)現(xiàn)Comparable<T&

50、gt; 接口，如Integer、String 等.* 2、非遞歸查找使用search();,遞歸查找使用searchRecursively();*本程序僅供編程學(xué)習(xí)參考*author:Winty*date:2008-8-11*email: emailwintys/email*/class BinarySearch<T extends Comparable<T>> ( private T data;/要排序的數(shù)據(jù)public BinarySearch(T data)(this.data = data;public int search(T key)( int low;in

51、t high;int mid;if(data = null) return -1;low = 0;high = data.length - 1;while(low <= high)mid = (low + high) / 2;+ datamid);/System.out.println("mid " + mid + " mid value:if(pareTo(datamid)< 0)high = mid - 1;elseif(pareTo(datamid)> 0)low = mid + 1;elseif(pareTo(datamid)= 0)re

52、turn mid;return -1;private intint mid;int result;doSearchRecursively(intlow, int highif(low<=mid = resulthigh)(low + high) / 2;= pareTo(datamid);System.out.println("mid" + mid +if(result< 0)" mid valuereturnelsedoSearchRecursively(low if(result > 0), mid - 1returnelsereturndo

53、SearchRecursively(mid if(result = 0) mid;+ 1 , highT key)+ datamid);/key);key);return -1;public int searchRecursively(T key)(if(data =null)return -1;return doSearchRecursively(0 , data.length - 1 , key); public static void main(StringInteger data = (1BinarySearch<Integer>/System.out.println(&q

54、uot;Key,4,5 ,8binSearchargs)(,15 ,33 ,48 ,77 ,96;new BinarySearch<Integer>(data);index:" + binSearch.search(33) );System.out.println("Keyindex:" + binSearch.searchRecursively(3);/String dataStr = ("A" ,"C” ,"F" ,"J" ,"L" ,"N" ,"T"/BinarySearch<String> binSearch = new BinarySearch<String>(dataSt r);/System.out.println("Key index:" + binSearch.search("A") ); 遞歸排序其實(shí)在數(shù)組的全排序中完全可以使用更加易懂簡(jiǎn)便的寫法一一for循環(huán)，但是通過(guò)for循環(huán)編寫數(shù)組全排序需要有一個(gè)先決條件知道