Java數(shù)據(jù)結(jié)構(gòu)和算法

1、Java數(shù)據(jù)結(jié)構(gòu)和算法一、數(shù)組于簡單排序1二、棧與隊列4三、鏈表7四、遞歸22五、哈希表25六、高級排序25七、二叉樹25八、紅一黑樹26九、堆36十、帶權(quán)圖39一、數(shù)組于簡單排序數(shù)組數(shù)組(array)是相同類熨變最的集合，可以使用共同的名字引用它。數(shù)組可 被定義為任何類型，可以是一維或多維。數(shù)組中的一個特別耍素是通過下標(biāo)來訪 問它。數(shù)組提供了一種將冇聯(lián)系的信息分組的便利方法。一維數(shù)組一維數(shù)組(one-dimensional array )實(shí)質(zhì)上是相同類型變量列表。耍創(chuàng)建一 個數(shù)組，你必須首先定義數(shù)組變帚所需的類熨。通用的一維數(shù)組的聲明格式是:type var-name;獲得一個數(shù)組需耍2步。

2、第一步，你必須定義變暈所需的類型。第二步，你 必須使用運(yùn)算符new來為數(shù)組所雯存儲的數(shù)據(jù)分配內(nèi)存，并把它們分配給數(shù)組 變址。這樣Java中的數(shù)組被動態(tài)地分配。如果動態(tài)分配的概念對你陌生，別擔(dān) 心，它將在木書的后而詳細(xì)討論。數(shù)組的初始化(array initializer )就是包括在花括號Z內(nèi)用逗號分開的表達(dá) 式的列表。逗號分開了數(shù)組元素的值。Java會門動地分配一個足夠大的空間來 保存你指定的初始化元素的個數(shù)，而不必使用運(yùn)算符newoJava嚴(yán)格地檢査以保證你不會總外地公存儲或引用在數(shù)組范圉以外的值。 Java的運(yùn)行系統(tǒng)會檢査以確保所有的數(shù)組下標(biāo)都在正確的范F科以內(nèi)(在這方面,Java與C/

3、C+從根木上不同，C/C+不提供運(yùn)行邊界檢查)。多維數(shù)組在Java中,多維數(shù)組(multidimensional arrays )實(shí)際上是數(shù)組的數(shù)組。你 可能期璽，這些數(shù)組形式上和行動上和一般的多維數(shù)紐一樣。然而，你將看到, 有一些微妙的差別。定義多維數(shù)組變量要將每個維數(shù)放在它們各I的方括號中。 例如，下而語句定義了一個名為twoD的二維數(shù)組變鼠。int twoD = new int；簡單排序簡單排序中包括了：冒泡排序、選擇排序、插入排序；1. 冒泡排序的思想：假設(shè)有N個數(shù)據(jù)需要排序，則從第0個數(shù)開始，依次比較第0和第1個數(shù)據(jù), 如果笫0個大丁笫1個則兩者交換，否則什么動作都不做，繼續(xù)比較笫1

4、個第2 個，這樣依次類推，H至所有數(shù)據(jù)都“冒泡”到數(shù)據(jù)頂上。冒泡排序的的java代碼：Public void bubbleSort()int in,out;for(out=nElems-l;out>0;out)for(i n=O;i nv out;in+)lf(ain>ain+l)Swap(in,in+1);算法的不變性：許多算法中，有些條件在算法執(zhí)行過程中始終是不變的。這些 條件被稱為算法的不變性，如果不變性不為真了，則標(biāo)記出錯門冒泡排序的效率0 (N#N),比較N*N/2,交換N*N/4；2. 選擇排序的思想：假設(shè)有N條數(shù)據(jù)，則暫且標(biāo)記第0個數(shù)據(jù)為MIN (最小)，使用OUT標(biāo)

5、記最左 邊未排序的數(shù)據(jù)，然后使用IN標(biāo)記第1個數(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-l;out+)Min=out;For(in=out+l;i n<n Elems;in+)lf(ain<amin)Min=in;Swapjoumin);選擇排序的效率：0 (NN),比較N*N/2,交換VN；選擇排序與冒泡排序比 較，比較次數(shù)沒有明顯改變，但交

6、換次數(shù)明顯減少了很多；3. 插入排序的思想:插入排序是在部分?jǐn)?shù)據(jù)有序的悄況下，使用OUT標(biāo)記第一個無序的數(shù)據(jù)，將 其提取保存到一個屮間變暈temp小去，使用IN標(biāo)記空位置，依次比較temp屮 的值與INJ的值,如果IN值大T temp的值，則后移,直到遇到第一個比temp 小的值，在其下一個位置插入；插入排序的java代碼：Public void lnsertionSort()Int in,out;For(out=l;out vn Elems;out+)Long temp=aoutln=out;While(in>0&& ain-l>temp)Ain=ain-1;-i

7、n;Ain=temp;插入排序的效率:O(N*N),比較N*N/4,復(fù)制N*N/4；插入排序在隨機(jī)數(shù)的 情況下，比冒泡快一倍，比選擇稍快：在基本有序的數(shù)組屮，插入排序兒乎只需 要0 (N)；在逆序悄況下，并不比冒泡快；二、棧與隊列1、棧的定義棧(Stack)是限制僅在表的一端進(jìn)行插入和刪除運(yùn)算的線性表。(1) 通常稱插入、刪除的這一端為棧頂(Top),另一端稱為棧底(Bottom)。(2) 當(dāng)表中沒有元索時稱為空棧:(3) 棧為后進(jìn)先出(Last In First Out)的線性表,簡稱為UFO表。棧的修改是按后進(jìn)先出的原則進(jìn)行。每次刪除(退棧)的總是當(dāng)前棧中" 最新"的元

8、素，即最后插入(進(jìn)棧)的元素，而最先插入的是被放在棧的底部， 農(nóng)到最后才能刪除。出棧棧頂棧底棧示意圖【示例】元素是以al, a2, , an的順序進(jìn)棧，退棧的次序卻是an, an-1, ,31 o2、棧的基本運(yùn)算(1) InitStack (S)構(gòu)造一個空棧S。(2) StackEmpty (S)判?？?。若S為空棧，則返回TRUE,否則返回FALSEo(3) StaukFull (S)判棧滿。若S為滿棧,則返回TRUE,否則返回FALSEo注意：該運(yùn)算只適用丁棧的順序存儲結(jié)構(gòu)。(4) Push (S» x)進(jìn)棧。若棧S不滿，則將元素x插入S的棧頂。(5) Pop (S)退棧。若棧S非

9、空，則將S的棧頂元素刪去，并返回該元素。(6) StackTop (S)取棧頂元素。若棧S非空，則返冋棧頂元素，但不改變棧的狀態(tài)。隊列的定義及基本運(yùn)算1、定義隊列（Queue）是只允許在一端進(jìn)行插入，而任另一端進(jìn)行刪除的運(yùn)算受入隊限的線杵表ai 82隊頭隊甩隊列示怠圖（1）允許刪除的一端稱為隊頭（Front） o（2）允許插入的一端稱為隊尾（Rear）。（3）當(dāng)隊列中沒有元索時稱為空隊列。（4）隊列亦稱作先進(jìn)先出（First In First Out）的線性表，簡稱為FIFO 表。隊列的修改是依先進(jìn)先出的原則進(jìn)行的。新來的成員總是加入隊尾（即不 允許"加塞"，每次離開的成員

10、總是隊列頭上的（不允許中途離隊），即當(dāng)前" 最老的"成員離隊。【例】在隊列中依次加入元素a” a:,，a=之后，內(nèi)是隊頭元素，a=是隊尾 元素。退出隊列的次序只能是a“ a：,念。2、隊列的基本邏輯運(yùn)算（1）InitQueue （Q）置空隊。構(gòu)造一個空隊列Q。（2）QueueEmpty （Q）判隊空。若隊列Q為空，則返回真值，否則返回假值。（3）QueueFull （Q）判隊滿。若隊列Q為滿，則返回真值，否則返回假值。注意：此操作只適用J：隊列的順序存儲結(jié)構(gòu)。（4）EnQueue （Q, x）若隊列Q非滿，則將元素x插入Q的隊尾。此操作簡稱入隊。（5）DeQueue （Q）

11、若隊列Q非空，則刪公Q的隊頭元素，并返回該元素。此操作簡稱出隊:（6）QueueFront （Q）若隊列Q非空，則返回隊頭元素，但不改變隊列Q的狀態(tài)。三、鏈表1. 鏈結(jié)點(diǎn)在鏈表中，每個數(shù)據(jù)項都被包含在'點(diǎn)“中，一個點(diǎn)是某個類的對象，這個類可認(rèn)叫做 UNKo因為一個鏈表屮仔許命類似的鏈結(jié)點(diǎn)，所以有必耍用一個不同鏈表的類來表達(dá) 鏈結(jié)點(diǎn)。每個LINK對象中都包含一個對下個點(diǎn)引用的字段（通常叫做next）但是本 身的対彖中有一個字段指向?qū)Φ谝粋€鏈結(jié)點(diǎn)的引用單鏈表用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)尤素。以元素（數(shù)據(jù)元素的映彖）+指針（指示后繼元素存儲位置）二結(jié)點(diǎn)（表示數(shù)據(jù)元索或數(shù)據(jù)元素的

12、映彖）以“結(jié)點(diǎn)的序列”表示線性表稱作線性鏈表（單鏈表）一單鏈表是一種順序存取的結(jié)構(gòu)，為找第i個數(shù)據(jù)尤素，必須先找到第i-1個數(shù) 據(jù)元素。因此，弈找第i個數(shù)據(jù)元素的基木操作為：移動指針，比較j和i1、鏈接存儲方法鏈接方式存儲的線性表簡稱為鏈表（Linked List）。鏈表的具體存儲表示為： 用一組任意的存儲單元來存放線性表的結(jié)點(diǎn)（這組存儲單尤既可以是連續(xù)的， 也可以是不連續(xù)的） 鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏 輯關(guān)系，在存儲每個結(jié)點(diǎn)值的同時，還必須存儲指示Jt后繼結(jié)點(diǎn)的地址(或位置)信 息(稱為指針(pointer)或鏈(link)注意：鏈?zhǔn)酱鎯κ亲畛Ｓ玫拇?/p>

13、儲方式之一，它不僅可用來表示線性表，而且可用來表示 齊種非線性的數(shù)據(jù)結(jié)構(gòu)。2、鏈表的結(jié)點(diǎn)結(jié)構(gòu)| data| next|data域存放結(jié)點(diǎn)侑的數(shù)據(jù)域next域療放結(jié)點(diǎn)的直接后繼的地址(位置)的指針域(鏈域)注意： 鏈衷通過每個結(jié)點(diǎn)的鏈域?qū)⒕€性農(nóng)的n個結(jié)點(diǎn)按其邏輯順序鏈接在一起的。 每個結(jié)點(diǎn)只冇一個鏈域的鏈衷稱為單鏈表(Single Linked List)?！纠烤€性表(bat, cat, eat, fat, hat, jat, lat, mat)的單鏈表示如示意圖3、頭指針head和終端結(jié)點(diǎn)指針域的表示唯鏈表中每個結(jié)點(diǎn)的存儲地址是存放在It前趨結(jié)點(diǎn)next域中，而開始結(jié)點(diǎn)無前 趨，故應(yīng)設(shè)頭指針

14、head向開始結(jié)點(diǎn)。注意：鏈衷由頭指針唯一確定，單鏈衷可以用頭指什的名字來命名?！纠款^指針名是head的鏈表可稱為表head。終端結(jié)點(diǎn)無后繼，故終端結(jié)點(diǎn)的指針域為空，即NULLo4、單鏈衷的一般圖示法由我們常常只注HL纟占點(diǎn)間的邏輯順序，不關(guān)心毎個結(jié)點(diǎn)的實(shí)際位迓，可以用箭 頭來表示鏈域中的指針,線性表(bat, cat, fat, hat, jat, lat, mat)的單鏈表就可 以表示為下圖形式。5、單鏈衷類型描述typedef char DataType; 假設(shè)結(jié)點(diǎn)的數(shù)據(jù)域類型為字符typedef struct node 結(jié)點(diǎn)類型定義DataType data; 結(jié)點(diǎn)的數(shù)據(jù)域struc

15、t node *next;/結(jié)點(diǎn)的指針域JListNodetypedef ListNode *LinkList;ListNode *p;LinkList head;注意： PnkList和ListNode是不同名字的同一個指針類型(命名的不同是為了概念 上更明確) LinkList類型的指針變量head表示它是單鏈表的頭指針 ListNode類醴的指針變就p表示它是指向某一結(jié)點(diǎn)的拆針6、指針變量和結(jié)點(diǎn)變量|指針變最|結(jié)點(diǎn)變帚|IJIII1IIII1 1|定義|在變屆說明部分顯式定義|在程序執(zhí)行時，通過標(biāo)準(zhǔn)| | | |函數(shù)malloc生成|1-J1 1II1 11 1II|取值|非空時，存放某

16、類型結(jié)點(diǎn)|實(shí)際存放結(jié)點(diǎn)各域內(nèi)容| | |的地址| |I-JIIIIIIIIII|操作方式|通過指針變屆名訪問|通過指針生成、訪問和釋放 生成結(jié)點(diǎn)變鼠的標(biāo)準(zhǔn)函數(shù)p=( ListNode *)malloc(sizeof(ListNode)；函數(shù)malloc分配一個類型為ListNode的結(jié)點(diǎn)變量的空間,并將其首地址放入指 針變量p中 釋放結(jié)點(diǎn)變起空間的標(biāo)準(zhǔn)函數(shù)free(p)； 釋放p所指的結(jié)點(diǎn)變量空間 結(jié)點(diǎn)分量的訪問利用結(jié)點(diǎn)變屆的乳字S訪問結(jié)點(diǎn)分吊力法一：(*p).data 和Cp).next方法二：p- > data 和 p > next 指針變屜P和結(jié)點(diǎn)變吊"P的關(guān)系指針

17、變鼠p的值一結(jié)點(diǎn)地址結(jié)點(diǎn)變m!：*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)。此時，若通過S 來訪問結(jié)點(diǎn)就意味著訪問一個不存在的變鼠，從而引起程序的錯謀。 仃關(guān)指針類型的意義和說明方式的詳細(xì)斛釋可見，在鏈表中插入結(jié)點(diǎn)只需要修改折針。但同時，若耍在第i個結(jié)點(diǎn)之前插 入元素，修改的是第i-1個結(jié)點(diǎn)的指針。因此，在單鏈表屮第i個結(jié)點(diǎn)之前進(jìn)行插入的甚本操作為：找到線性表中第PI個結(jié)點(diǎn)，然后修改其指向后繼的指針。雙端鏈表雙端鏈表與傳統(tǒng)的鏈衣II巾

18、相似，但是它有一個新增的特性：即對垠后一個鏈結(jié)點(diǎn)的 引用，就像對第一個鏈結(jié)點(diǎn)的引用一樣。對彊后一個鏈結(jié)點(diǎn)的引用允許像在衷頭-樣，在表尾直接插入一個鏈結(jié)點(diǎn)。當(dāng)然，仍 然可以在普通的單鏈衣的表尾插入-個鏈結(jié)點(diǎn)，方法足遍歷整個鏈衷直到到達(dá)農(nóng)足, 但是這種方法效率很低。對彊后一個鏈結(jié)點(diǎn)的引用允許像在表頭-樣，在表尾直接插入一個鏈結(jié)點(diǎn)。當(dāng)然，仍 然可以在普通的單鏈農(nóng)的衣尾插入一個鏈結(jié)點(diǎn)，方法足遍歷整個鏈衷12到到達(dá)農(nóng)足, 但是這種方法效率很低。像訪問農(nóng)頭樣訪問農(nóng)尾的特性，使雙端謎農(nóng)更適合 些普通謎農(nóng)不方便操作的場 介，隊列的實(shí)現(xiàn)就是這樣一個情況。卜面是一個雙端鏈表的例子。class Link3publi

19、c long dData;public Link3 next;IIpublic Link3(long d)dData=d;IIpublic void displayLink()System out print(dData+M M);/class FirstLastListprivate Link3 first;private Link3 last;IIpublic FirstLastList()first 二 n ull;last=null;public boolean isEmpty() return first二二null;IIIIpublic void insertFirst(long

20、dd)Link3 newLink=new Link3(dd); if(isEmpty() last 二 n ewLink;newLink.next 二 first;first 二 newLink;/public void insertLast(long dd)Link3 newLink=new Link3(dd); if(isEmpty() first二newLink;elselast.next 二 newLi nk;last 二n ewLink;/public long deleteFirst() long temp二first dData; if(first.next=二 null) la

21、st 二 n ull;first 二 first, next; return temp;/public void displayList()System.out.print("List (first->last):");Link3 current二first; while(curre nt!二 n ull) curre nt.displayLi nk(); current=curre nt. next;System.out.println(,IR);lllllllllllllllllllllllllllllllllllll public class FirstLast

22、App public static void main(String args) FirstLastList 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.di

23、splayList();為了簡單起見，在這個程序中，把每個徒結(jié)點(diǎn)中的數(shù)據(jù)字段個數(shù)從兩個壓縮到一個。 這更容易顯示鏈結(jié)點(diǎn)的內(nèi)容。(記住，在一個正式的程序中，可能會冇非常多的數(shù)據(jù) 字段，或者對另外一個對彖的引用，那個對彖也包含很多數(shù)據(jù)字段。)這個程序在表頭和衷用各插入三個鏈點(diǎn)，顯示插入后的鏈表。然后刪除頭兩個鏈結(jié)點(diǎn), 再次顯示。注意在表頭巫復(fù)插入操作會顛倒鏈結(jié)點(diǎn)進(jìn)入的順序，而在表用的重復(fù)插入則保持鏈結(jié) 點(diǎn)進(jìn)入的順序。雙端鏈表類叫做FirstLastList.它有兩個項,first和last. 一個指向鏈表中的第一個 鏈結(jié)點(diǎn)，另一個指向最后一個鏈結(jié)點(diǎn)。如果鏈衷中只有一個鏈結(jié)點(diǎn)，first利last就

24、都 指向它,如呆沒有鏈結(jié)點(diǎn),兩者都為Null ffLo這個類右一個新的方法insertLastO,這個方法在衷用插入一個新的鏈結(jié)點(diǎn)。這個過 程首先改變last.next,使其指向新生成的鏈結(jié)點(diǎn),然后改變last,使其指向新的鏈結(jié) 點(diǎn)。插入和刪除方法和普通鍛表的相應(yīng)部分類似。然而，兩個插入方法都要考世一種特殊 情況,即插入前鏈表是空的。如果isEmpty()是真,那么insertFirst()必須把last指向 新的鏈結(jié)點(diǎn),insertLastO也必須把first指向新的鏈結(jié)點(diǎn)。如果用insertFirst()方法實(shí)現(xiàn)在表頭插入,first就指向新的鏈結(jié)點(diǎn)，用insertLastO方 法實(shí)現(xiàn)在衷

25、疋插入，last就指向新的鏈結(jié)點(diǎn)。如果鏈衷只仃一個鏈結(jié)點(diǎn)，那么多衷頭 刪除也是-種特殊情況:last必須被賦值為null值。不幸的是，用雙端鏈農(nóng)也不能仃助J刪除厳后一個鏈結(jié)點(diǎn)，因為沒仃一個引用指向倒 數(shù)笫二個鏈結(jié)點(diǎn)。如來最后個鏈結(jié)點(diǎn)被刪除，倒數(shù)第二個鏈結(jié)點(diǎn)的Next字段應(yīng)該 變成Null值。為了方便的刪除址后一個鏈結(jié)點(diǎn)，需要一個雙向鏈表。(當(dāng)然，也可以 遍歷整個鏈表找到最后一個鏈結(jié)點(diǎn)，但是那樣做效率不是很高。)有序鏈表在有序鏈表中,數(shù)據(jù)是按照關(guān)鍵值有序排列的。有序鏈表的刪除常常是只限FJM除在 鏈表頭部的最小鏈結(jié)點(diǎn)。不過，有時也用Find()方法和Delete()方法在整個鏈表中搜 索某一特定

26、點(diǎn)。一般，在犬多數(shù)需要使用有序數(shù)組的場合也可以便用有序鏈表。有序鏈表優(yōu)于有序數(shù) 組的地方是插入的速度,另外鏈表可以擴(kuò)展到全部有效的使用內(nèi)存，而數(shù)組只能局限 一個固定的人小中。但是，有序鏈表實(shí)現(xiàn)起來比有序數(shù)組更困難一些。后而將看到一個有序鏈表的應(yīng)用：為數(shù)據(jù)排序。有序鏈表也可以用實(shí)現(xiàn)優(yōu)先級隊列, 盡管堆是更常用的實(shí)現(xiàn)方法。在勺序鏈表中插入一個數(shù)據(jù)項的Java代碼為了在一個令用鏈表中插入數(shù)據(jù)項，算法必須首先捜索懺表，苴到找到合適的位置: 它恰好在第一個比它人的數(shù)據(jù)項的前向。當(dāng)算法找到了耍插入的位置，用通常的方式插入數(shù)據(jù)項：把新鏈結(jié)點(diǎn)的Next字段指 向卜一個鏈結(jié)點(diǎn)，然后把前一個鏈結(jié)點(diǎn)的Next字段改

27、為指向新的鏈結(jié)點(diǎn)。然而，需 要考慮一些特殊情況：鍛結(jié)點(diǎn)令可以插在表頭，或者插在表尾?？匆徊愤@段代碼： Public void insert(long key)Link newLink=new Link(key);Link previous=null;Link current二first;While(current!=null && key>current.dData)Previous=curre nt;Current=current.next;lf(provious=null)First=newLink;ElsePrevious.next=newLink;n ewLink

28、.next=curre nt;在鏈表上移動時，需要用一個previous引用，這樣才能把前一個鏈結(jié)點(diǎn)的Next字段 指向新的鏈結(jié)點(diǎn)。創(chuàng)建新鏈結(jié)點(diǎn)后，把current變杲設(shè)為first,準(zhǔn)備搜索止確的插入 點(diǎn)。這時也把previous設(shè)為Null值,這步操作很重要，因為后面要用這個Null值判 斷是否仍在表頭。While循環(huán)和以前用來搜索插入點(diǎn)的代碼類似，但是冇一個附加的條件。如果當(dāng)前檢 件的鏈結(jié)點(diǎn)的關(guān)鍵值不再小待插入的鏈結(jié)點(diǎn)的關(guān)鍵值，則循環(huán)結(jié)束：這是最常見的 情況，即新關(guān)鍵值插在徒表中部的某個地方。然而，如果current為Null值，while循環(huán)也會停止。這種情況發(fā)生在表尾，或者鏈 表為空

29、時。如果current在表頭或者鏈表為空,previous將為Null值;所以讓first指向新的鏈結(jié) 點(diǎn)。否則current處在鏈衣中部或結(jié)尼，就使previous的next字段扌旨向新的鏈結(jié)點(diǎn)。 不論哪種情況、都讓新鏈結(jié)點(diǎn)的Next字段指向currento如眾在表尼，current為Nu II值，則新鏈結(jié)點(diǎn)的Next字段也本應(yīng)該設(shè)為這個值(Null) o下面是有序鏈表的程序SortedList.java 程序?qū)崿F(xiàn)了一個 SortedList 類,它擁有 insert。、remove()和 display List()方法。只有insert()方法與無序鏈表中的insert()方濃不同。pa

30、ckage有序鏈表;class Linkpublic long dData;public Link next;public Link(long dd)dData=dd;/public void displayLink()System.out.print(dData+M n);llllllllllllllllllllllllllllllllllllllllclass SortedListprivate Link first;/public SortedList()first 二 null;/public boolean isEmpty()return (first二二null);/public

31、void insert(long key)Link newLink=new Link(key);Link previous二null;Link current二first;while(current!二null && key>current.dData)prcvious=curront;current=current. next;if(previous=null) first二newLink;elseprevious.next=newLink; newLink. next 二 current;/public Link remove()Link temp二first;fir

32、st 二 first.next; return temp;/public void displayList()System.out.printC'List (first->last):");Link current=first; while(current!=nu ll) current.displayLi nk(); current 二 current, next;System.out.println(MM);public class SortedLinkApp public static void main(String args) SortedList theSo

33、rtedList二new SortedList(); theSortedList.insert(20);theSortedList. insert(40); theSortedList.displayList();theSortedList. insert( 10);theSortedList.i nsert(30);theSortedList.! nset(50); theSortedList.displayList(); theSortedList.remove();theSortedList.displayList();System.exit(0);在Main()方法中，插入值為20和4

34、0的兩個鏈結(jié)點(diǎn)。然后再插入三個鏈結(jié)點(diǎn)，分別 是10、30和50。這三個值分別插在表頭、表中和表尼。這說明insert()方法正確地 處理了特殊情況。最厲刪除了一個鏈結(jié)點(diǎn)，表現(xiàn)出刪除操作總是從表頭進(jìn)行。每一步 變化后，都顯示整個鏈表。雙向鏈表雙向鏈表也叫雙鏈表,是鏈表的一種，它的每個數(shù)據(jù)結(jié)點(diǎn)中都有兩個指針,分別指向 直接后繼和直接前驅(qū)。所以,從雙向鏈表中的任意一個結(jié)點(diǎn)開始,都可以很方便地訪 問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。一般我們都構(gòu)造雙向循壞鏈表。/*線性表的雙向儺表存儲結(jié)構(gòu)Ttypedef struct DuLNodeElemType data;struct DuLNode *priorf*nex

35、t;DuLNode,*DuLinkList;廠帶頭結(jié)點(diǎn)的雙向循壞鏈表的基本操作(14個)*/void lnitList(DuLinkList *L) P產(chǎn)生空的雙向循環(huán)鏈表L */*L=(DuLinkList)malloc(sizeof(DuLNode);(*L)->next=(*L)->prior=*L;elsecxit(OVERFLOW);void DestroyList(DuLinkList *L) r操作結(jié)果：銷毀雙向循環(huán)鏈表L /DuLinkList q,p=(*L)->next; /* p 指向第一個結(jié)點(diǎn) */while(pl=*L) /* p 沒到表頭/q=p-

36、>next;free(p);P=q；free(-L);*L=NULL;void ClearList(DuLinkList L) /* 不改變 L 7 /*初始條件：L已存在。操作結(jié)果：將L亜置為空表7DuLinkList q,p=L->next; /* p 指向第一個結(jié)點(diǎn) T while(p!=L) /* p 沒到表頭 */q=p->next;free(p);P 二 q；L->next=L->prior=L; /*頭結(jié)點(diǎn)的兩個指針域均指向自身*/Status ListEmpty(DuLinkList L) /*初始條件：線性表Li2存在。操作結(jié)果：弟L為空衷，則返

37、回TRUE,否則 返回 FALSE */if(L->next=L&&L->prior=L)return TRUE;elsereturn FALSE;int ListLength(DuLinkList L) /*初始條件：L已存在。操作結(jié)果：返回L中數(shù)據(jù)兀索個數(shù)7int i=0;DuLinkList p=L->next; /* p 指向第一個結(jié)點(diǎn) */while(p!=L) / p 沒到表頭 Ti+;p=p->n ext;return i;Status GetElem(DuLinkList L.int i.ElemType *e) P當(dāng)?shù)趇個元素存在時，其

38、值賦給e并返回OK,否則返回ERROR */ int j=1; /* j為計數(shù)器TDuLinkList p=L->next; /* p 指向第一個結(jié)點(diǎn) Twhile(p!=L&&jnext;j+；if(p=L|j>i) /*第i個元索不存在Treturn ERROR;*e=p->data; /* 取第 i 個元素 */return OK;int LocateElem(DuLinkList L.EIemType e,Status(*compare)(ElemType,Elem Type) /*初始條件：L已存在，compare()是數(shù)據(jù)元素判定函數(shù)TP操作結(jié)果：

39、返回L中第1個與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序。*/*若這樣的數(shù)據(jù)元素不存在，則返回值為0 */int i=0;DuLinkList p=L->next; /* p 指向第 1 個元素 Twhile(p!=L)i+；if(compare(p->data,e) /*找到這樣的數(shù)據(jù)元素*/return i;p=p->next;return 0;Status PriorElem(DuLinkList L.EIemType cur_e,ElemType *pre_e) /*操作結(jié)果：Zf cur_e是L的數(shù)據(jù)元素，JI不是第一個，則用pre_e返回它的 前驅(qū)，7/否則操

40、作失敗，pe_e無定義TDuLinkList p=L->next->next; /* p 指向第 2 個元素 */while(p!=L) r p 沒到農(nóng)頭 Tif(p->data=cur_e)*pre_e=p->prior->data;return TRUEp=p->n ext;return FALSE;Status NextElem(DuLinkList L.EIemType cur_e,ElemType *next_e) /*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，£1不是址后一個，則用next_e返回 它的后繼，T/*否則操作失敗，next_e

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

42、p 指向頭結(jié)點(diǎn) */ if(i<O|i>ListLength(L) /* i ffi不合法 */ return NULL;forG=1;j<=i;j+)p=p->next;return p;Status Listlnsert(DuLinkList L,int i.ElemType e) /*在帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表L中第i個位置Z前插入尤素e, i的介法值為 1<i<3< 長+1 */*改進(jìn)算法2J&否則無法在第表長+ 1個結(jié)點(diǎn)Z前插入元素TDuLinkList p.s;if(i<1|i>ListLength(L)+1)廣 i 值

43、不合法 */return ERROR;p=GetElemP(L,i-1); /*在L中確定第i個元素前驅(qū)的位置指針p */if(!p) P p二NULL,即第i個九索的前驅(qū)不存在(設(shè)頭結(jié)點(diǎn)為笫1個尤索的前驅(qū))7 return ERROR;s=(DuLinkList)malloc (sizeof(DuLNode);if(!s)return OVERFLOW;s->data=e;s->prior=p; /*在第/個元素之后插入*/s>n ext=p >next;p>n ext->prior=s;p>n ext=s;return OK;Status List

44、Delete(DuLinkList L,int i.ElemType *e) /*刪除帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表L的第i個元素，i的合法值為農(nóng)長/DuLinkList p;if(i<1)廣i值不合法7return ERROR;p=GetElemP(L,i); /在L中確定第i個元素的位置指針p /if(!p) r P二NULL,即第i個元素不存在Treturn ERROR;*e=p->data;p >prior>next 二 p>n ext;p>n ext->prior 二 p >pior;free(p);return OK;void ListTr

45、averse(DuLinkList L,void(*visit)(ElemType) /*由雙鏈循環(huán)線性衷L的頭結(jié)點(diǎn)出發(fā)，正序?qū)γ總€數(shù)據(jù)尤索調(diào)用函數(shù)visit() */DuLinkList p=L->next; /* p 指向頭結(jié)點(diǎn) */while(p!=L)visit(p->data);p=p->n ext;printf("n");void ListTraverseBack(DuLinkList L,void(*visit)(ElemType) /*宙雙鏈循環(huán)線性農(nóng)L的頭結(jié)點(diǎn)出發(fā)，逆序?qū)γ總€數(shù)據(jù)尤索調(diào)用函數(shù)visit()o 另加*/DuLinkList

46、p=L->prior; /* p 指向尾結(jié)點(diǎn) */whilo(p!=L)visit(p->data); p=p->prior; printf("n");迭代器迭代器是一種對彖，它能夠用來遍歷STL容器中的部分或全部元索，每個迭代器對 象代表容器中的確定的地址。迭代器修改了常規(guī)指針的接口,所謂迭代器是一種概念 上的抽象:那些行為上彖迭代器的東西都可以叫做迭代器。然而迭代器有很多不同的 能力，它可以把抽彖容器和通用算法有機(jī)的統(tǒng)一起來。迭代器提供一些基本操作符：*、+、=二、！二、=o這些操作和C/C+"操作array元 索”時的指針接1丨一致。不同Z

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

48、erator接11的Current, MoveNext 和 Dispose 方広。特點(diǎn)1.迭代器是可以返冋相同類空值的有序序列的一段代碼；2迭代器可用作方法、運(yùn)算符或get訪問器的代碼體；3. 迭代器代碼使用yield return語句依次返回每個元素,yield break將終止迭代：4可以在類中實(shí)現(xiàn)多個迭代器，每個迭代器都必須像任何類成員一樣冇惟一的名 稱，并且可以在foreach語句中被客戶端代碼調(diào)用：5. 迭代器的返回類型必須為（Enumerable和lEnumerator 'I1的任意一種;6. 迭代器是產(chǎn)生值的有序序列的一個語句塊，不同冇一個 或多個yield語句存 在的常

49、規(guī)語句塊；7. 迭代器不是一種成員，它只是實(shí)現(xiàn)怖數(shù)成員的方式，理解這一點(diǎn)是很覓要的， 一個通過迭代器實(shí)現(xiàn)的成員，可以被梵他可能或不可能通過迭代器實(shí)現(xiàn)的成員廈盂和 重載；8. 迭代器塊在C#語法屮不是獨(dú)特的尤素，它們在兒個方而受到限制，并且主耍 作用在函數(shù)成員聲明的語義上，它們在語法上只是語句塊而己；I、遞歸遞歸是函數(shù)調(diào)用自身的一種特殊的編程技術(shù)，其應(yīng)用主要在以卜兒個方面：階乘在java為中的某木形式是：Public void mothed (int n) /半滿足某條件時：Mothed (n-1 )：遞歸二分查找Java二分先找實(shí)現(xiàn)，歡迎人家提出交流意見./*名稱:BinarySearch.功

50、能:實(shí)現(xiàn)了折半査找(二分査找)的遞歸和非遞歸算法.r兌明：* 1、要求所資找的數(shù)組已有序,并且其中元素己實(shí)現(xiàn)Comparable<T>接丨I,如 Integer、String 等.* 2、非遞歸査找使用search();,遞歸査找便用searchRecursively();"本程序僅供編程學(xué)習(xí)參考*author: Wintywdate:2000-8-11*email: emailwintys/email/class BinarySearch<T extends Comparable<T>> private T data;/要排序的數(shù)據(jù)public

51、BinarySearch(T data)this.data = data;public int search(T key)int low;int high;int mid;if(data 二二 null)return -1;low = 0;high = dataength 1;while(low <= high)mid = (low + high) / 2;System.out.println(Mmid M + mid + M mid value:11 + datamid);/if(pareTo(datamid) < 0)high = mid - 1;else if(pareTo(

52、datamid) > 0)low = mid + 1;else if(pareTo(datamid) = 0)return mid;returnprivate int doSearchRecursively(int low , int high r T key)int mid;int result;if(low <= high)mid = (low + high) / 2;result = pareTo(datamid):System.out.printlnC'mid " + mid + " mid value:" + datamid);/if

53、(result < 0)return doSearchRecursively(low f mid 1 t key);else if(result > 0)return doSearchRecursively(mid + 1 , high , key);else if(result = 0)return mid;return -1;public int searchRecursively(T key)if(data =null)returnreturn doSearchRecursively(0 , dataength 1 , key);public static void main

54、(String args)lnteger data = 1 ,4 ,5 ,8 ,15 ,33 ,48 ,77 ,96;BinarySearch<lnteger> binSearch = new BinarySearch<lnteger>(data); /System.out.pri ntln ("Key in dex:H + bin Search.search(33);System.out.println(wKey index，+ binSearch.searchRecursively(3);/String dataStr = "A”，”C”，“F”

55、，”J" ,"L"，”N” ,T;/BinarySearch<String> binSearch 二 new BinarySearch<String>(dataSt 0；/System.out.println("Key index:" + binSearch.search("A");遞歸排序氏實(shí)在數(shù)組的全排序屮完全可以使用更加易懂簡便的寫広for循環(huán)，但是通過 fo循環(huán)編寫數(shù)組全排序盂要冇一個先決條件一知道數(shù)組全排序的個數(shù)，因為有 n個數(shù)據(jù)全排序就需要寫n個恢套for循環(huán)。因此在寫全排序時一般使用遞歸方 法。這就是我的第一個關(guān)于遞歸排序的見解遞歸排序可以無需已知排序數(shù)組 的長度,即排序個數(shù)!其二,不管是使用遞歸進(jìn)行數(shù)組排序還是使用for循環(huán)進(jìn)行數(shù)組的排序,它們都 是本質(zhì)都是使用枚舉，因此可以得出這樣一個結(jié)論:枚舉可以確保找出每一種可能 的排序規(guī)則！其三，枚舉是列出所有的方法并找出符合耍求的算法，因此其算法效率一定比較 的低，需要対其進(jìn)行優(yōu)化，才能達(dá)到較好的效果(遞歸的時候排除所有不町能的 方案)消除遞歸消除遞歸的基本思路是用棧來模擬系統(tǒng)的函數(shù)調(diào)用從而消除遞歸?；旧弦鲆徊啡拢簜鬟f參數(shù)(池括返回地址)并轉(zhuǎn)到兩數(shù)入