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

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

3、提供運行邊界檢查)。多維數(shù)組在Java中，多維數(shù)組(multidimensionalarrays)實際上是數(shù)組的數(shù)組。你可能期望，這些數(shù)組形式上和行動上和一般的多維數(shù)組一樣。然而，你將看到，有一些微妙的差別。定義多維數(shù)組變量要將每個維數(shù)放在它們各自的方括號中。例如，下面語句定義了一個名為twoD的二維數(shù)組變量。inttwoD=newint45;簡單排序簡單排序中包括了：冒泡排序、選擇排序、插入排序；1 .冒泡排序的思想：假設(shè)有N個數(shù)據(jù)需要排序，則從第0個數(shù)開始，依次比較第0和第1個數(shù)據(jù)，如果第0個大于第1個則兩者交換，否則什么動作都不做，繼續(xù)比較第1個第2個，這樣依次類推，直至所有數(shù)據(jù)都“冒泡

4、”到數(shù)據(jù)頂上。冒泡排序的的java代碼：PublicvoidbubbleSort()intin,out;for(out=nElems-1;out>0;out-)for(in=0;in<out;in+)If(ain>ain+1)Swap(in,in+1);算法的不變性：許多算法中，有些條件在算法執(zhí)行過程中始終是不變的。這些條件被稱為算法的不變性，如果不變性不為真了，則標(biāo)記出錯了；冒泡排序的效率O(N*N),比較N*N/2,交換N*N/4;2 .選擇排序的思想：假設(shè)有N條數(shù)據(jù)，則暫且標(biāo)記第0個數(shù)據(jù)為MIN(最小)，使用OUT標(biāo)記最左邊未排序的數(shù)據(jù)，然后使用IN標(biāo)記第1個數(shù)據(jù)，依次

5、與MIN進(jìn)行比較，如果比MIN小，則將該數(shù)據(jù)標(biāo)記為MIN,當(dāng)?shù)谝惠啽容^完后，最終的MIN與OUT標(biāo)記數(shù)據(jù)交換，依次類推；選擇排序的java代碼：PublicvoidselectSort()(Intin,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;選擇排序與冒泡排序比較，比較次數(shù)沒有明顯改變，但交換次數(shù)明顯減少了很多；3 .插入排序的思想：插入排序是在部

6、分?jǐn)?shù)據(jù)有序的情況下，使用OUT標(biāo)記第一個無序的數(shù)據(jù)，將其提取保存到一個中間變量temp中去，使用IN標(biāo)記空位置，依次比較temp中的值與IN-1的值，如果IN-值大于temp的值，則后移，直到遇到第一個比temp小的值，在其下一個位置插入；插入排序的java代碼：PublicvoidInsertionSort()Intin,out;For(out=1;out<nElems;out+)Longtemp=aoutIn=out;While(in>0&&ain-1>temp)(Ain=ain-1;-in;Ain=temp;插入排序的效率：O(N*N),比較N*N/4,

7、復(fù)制N*N/4;插入排序在隨機(jī)數(shù)的情況下，比冒泡快一倍，比選擇稍快；在基本有序的數(shù)組中，插入排序幾乎只需要O(N);在逆序情況下，并不比冒泡快；二、棧與隊列1、棧的定義棧(Stack)是限制僅在表的一端進(jìn)行插入和刪除運算的線性表。(1)通常稱插入、刪除的這一端為棧頂(Top),另一端稱為棧底(Bottom)。(2)當(dāng)表中沒有元素時稱為空棧。(3)棧為后進(jìn)先出(LastInFirstOut)的線性表，簡稱為LIFO表。棧的修改是按后進(jìn)先出的原則進(jìn)行。每次刪除(退棧)的總是當(dāng)前棧中"最新”的元素，即最后插入(進(jìn)棧)的元素，而最先插入的是被放在棧的底部，要到最后才能刪除。進(jìn)棧【示例】元素是

8、以al,a2,an的順序進(jìn)棧，退棧的次序卻是an,an-1，a1o2、棧的基本運算(DInitStack(S)構(gòu)造一個空棧S。(2)StackEmpty(S)判棧空。若S為空棧，則返回TRUE否則返回FALSE(3)StackFull(S)判棧滿。若S為滿棧，則返回TRUE否則返回FALSE該運算只適用于棧的順序存儲結(jié)構(gòu)。(4)Push(S,x)進(jìn)棧。若棧S不滿，則將元素x插入S的棧頂。(5)Pop(S)退棧。若棧S非空，則將S的棧頂元素刪去，并返回該元素。(6)StackTop(S)取棧頂元素。若棧S非空，則返回棧頂元素，但不改變棧的狀態(tài)。隊列的定義及基本運算1、定義隊列(Queue是只允許

9、在一端進(jìn)行插入，而在另一端進(jìn)行刪除的運算受限的線性表出隊V-LL社2,*a.一人隊隊頭隊尾隊列示意圖(1)允許刪除的一端稱為隊頭(Front)o(2)允許插入的一端稱為隊尾(Rear)。(3)當(dāng)隊列中沒有元素時稱為空隊列。(4)隊列亦稱作先進(jìn)先出(FirstInFirstOut)的線性表，簡稱為FIFO表。隊列的修改是依先進(jìn)先出的原則進(jìn)行的。新來的成員總是加入隊尾(即不允許“加塞")，每次離開的成員總是隊列頭上的(不允許中途離隊)，即當(dāng)前"最老的”成員離隊。【例】在隊列中依次加入元素ai,a2,an之后，ai是隊頭元素，an是隊尾元素。退出隊列的次序只能是ai,a2,ano

10、2、隊列的基本邏輯運算(1) InitQueue(Q置空隊。構(gòu)造一個空隊列Q(2) QueueEmpty(Q)判隊空。若隊列Q為空，則返回真值，否則返回假值。(3) QueueFull(Q)判隊滿。若隊列Q為滿，則返回真值，否則返回假值。注意：此操作只適用于隊列的順序存儲結(jié)構(gòu)。(4) EnQueue(Q,x)若隊列Q非滿，則將元素x插入Q的隊尾。此操作簡稱入隊。(5) DeQueue(Q)若隊列Q非空，則刪去Q的隊頭元素，并返回該元素。此操作簡稱出隊(6) QueueFront(Q)若隊列Q非空，則返回隊頭元素，但不改變隊列Q的狀態(tài)。二、鏈表1.鏈結(jié)點在鏈表中，每個數(shù)據(jù)項都被包含在點“中，一個

11、點是某個類的對象，這個類可認(rèn)叫做LINK。因為一個鏈表中有許多類似的鏈結(jié)點，所以有必要用一個不同于鏈表的類來表達(dá)鏈結(jié)點。每個LINK對象中都包含一個對下一個點引用的字段(通常叫做next)但是本身的對象中有一個字段指向?qū)Φ谝粋€鏈結(jié)點的引用單鏈表用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。以元素(數(shù)據(jù)元素白映象)+指針(指示后繼元素存儲位置)=結(jié)點(表示數(shù)據(jù)元素或數(shù)據(jù)元素白映象)以結(jié)點的序列”表示線性表稱作線性鏈表(單鏈表)單鏈表是一種順序存取的結(jié)構(gòu)，為找第i個數(shù)據(jù)元素，必須先找到第i-1個數(shù)據(jù)元素。因此，查找第i個數(shù)據(jù)元素的基本操作為：移動指針，比較j和i1、鏈接存儲方法鏈接方式存儲的線性

12、表簡稱為鏈表(LinkedList)。鏈表的具體存儲表示為：(這組存儲單元既可以是連續(xù)的,用一組任意的存儲單元來存放線性表的結(jié)點也可以是不連續(xù)的)鏈表中結(jié)點的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還必須存儲指示其后繼結(jié)點的地址(或位置)信息(稱為指針(pointer)或鏈(link)注意：鏈?zhǔn)酱鎯κ亲畛Ｓ玫拇鎯Ψ绞街唬粌H可用來表示線性表，而且可用來表示各種非線性的數(shù)據(jù)結(jié)構(gòu)。2、鏈表的結(jié)點結(jié)構(gòu)Indatanext1data域-存放結(jié)點值的數(shù)據(jù)域next域-存放結(jié)點的直接后繼的地址(位置)的指針域(鏈域)注意：鏈表通過每個結(jié)點的鏈域?qū)⒕€性表的n

13、個結(jié)點按其邏輯順序鏈接在一起的。每個結(jié)點只有一個鏈域的鏈表稱為單鏈表(SingleLinkedList)。【例】線性表(bat,cat,eat,fat,hat,jat,lat,mat)的單鏈表示如示意圖3、頭指針head和終端結(jié)點指針域的表示單鏈表中每個結(jié)點的存儲地址是存放在其前趨結(jié)點next域中，而開始結(jié)點無前趨，故應(yīng)設(shè)頭指針head指向開始結(jié)點。注意：鏈表由頭指針唯一確定，單鏈表可以用頭指針的名字來命名。【例】頭指針名是head的鏈表可稱為表head。終端結(jié)點無后繼，故終端結(jié)點的指針域為空，即NULL。4、單鏈表的一般圖示法由于我們常常只注重結(jié)點間的邏輯順序，不關(guān)心每個結(jié)點的實際位置，可以

14、用箭頭來表示鏈域中的指針，線性表(bat,cat,fat,hat,jat,lat,mat)的單鏈表就可以表示為下圖形式。5、單鏈表類型描述typedefcharDataType;假設(shè)結(jié)點的數(shù)據(jù)域類型為字符typedefstructnode結(jié)點類型定義DataTypedata;結(jié)點的數(shù)據(jù)域structnode*next;結(jié)點的指針域ListNodetypedefListNode*LinkList;ListNode*p;LinkListhead;注意：*LinkList和ListNode是不同名字的同一個指針類型(命名的不同是為了概念上更明確)*LinkList類型的指針變量head表示它是單鏈表

15、的頭指針ListNode類型的指針變量p表示它是指向某一結(jié)點的指針6、指針變量和結(jié)點變量I指針變量I結(jié)點變量I111定義I在變量說明部分顯式定義I在程序執(zhí)行時，通過標(biāo)準(zhǔn)I1函數(shù)malloc生成I111取值I非空時，存放某類型結(jié)點I實際存放結(jié)點各域內(nèi)容I的地址II111操作方式I通過指針變量名訪問I通過指針生成、訪問和釋放生成結(jié)點變量的標(biāo)準(zhǔn)函數(shù)p=(ListNode*)malloc(sizeof(ListNode);/函數(shù)malloc分配一個類型為ListNode的結(jié)點變量的空間，并將其首地址放入指針變量p中釋放結(jié)點變量空間的標(biāo)準(zhǔn)函數(shù)free(p);/釋放p所指的結(jié)點變量空間結(jié)點分量的訪問利用結(jié)

16、點變量的名字*p訪問結(jié)點分量方法一：(*p).data和(*p).next方法二：p->data和p->next指針變量p和結(jié)點變量*p的關(guān)系指針變量p的值一一結(jié)點地址結(jié)點變量*p的值結(jié)點內(nèi)容(*p).data的值p指針?biāo)附Y(jié)點的data域的值(*p).next的值*p后繼結(jié)點的地址*(*p).next)*p后繼結(jié)點注意：若指針變量p的值為空(NULL),則它不指向任何結(jié)點。此時，若通過*p來訪問結(jié)點就意味著訪問一個不存在的變量，從而引起程序的錯誤。有關(guān)指針類型的意義和說明方式的詳細(xì)解釋可見，在鏈表中插入結(jié)點只需要修改指針。但同時，若要在第i個結(jié)點之前插入元素，修改的是第i-1個結(jié)

17、點的指針。因此，在單鏈表中第i個結(jié)點之前進(jìn)行插入的基本操作為：找到線性表中第i-1個結(jié)點，然后修改其指向后繼的指針。雙端鏈表雙端鏈表與傳統(tǒng)的鏈表非常相似，但是它有一個新增的特性：即對最后一個鏈結(jié)點的引用，就像對第一個鏈結(jié)點的引用一樣。對最后一個鏈結(jié)點的引用允許像在表頭一樣，在表尾直接插入一個鏈結(jié)點。當(dāng)然，仍然可以在普通的單鏈表的表尾插入一個鏈結(jié)點，方法是遍歷整個鏈表直到到達(dá)表尾，但是這種方法效率很低。對最后一個鏈結(jié)點的引用允許像在表頭一樣，在表尾直接插入一個鏈結(jié)點。當(dāng)然，仍然可以在普通的單鏈表的表尾插入一個鏈結(jié)點，方法是遍歷整個鏈表直到到達(dá)表尾，但是這種方法效率很低。像訪問表頭一樣訪問表尾的特

18、性，使雙端鏈表更適合于一些普通鏈表不方便操作的場合，隊列的實現(xiàn)就是這樣一個情況。下面是一個雙端鏈表的例子。classLink3publiclongdData;publicLink3next;/publicLink3(longd)dData=d;/publicvoiddisplayLink()System.out.print(dData+"");/classFirstLastListprivateLink3first;privateLink3last;/publicFirstLastList()first=null;last=null;/publicbooleanisEmpt

19、y()returnfirst=null;/publicvoidinsertFirst(longdd)Link3newLink=newLink3(dd);if(isEmpty()last=newLink;newLink.next=first;first=newLink;)/publicvoidinsertLast(longdd)Link3newLink=newLink3(dd);if(isEmpty()first=newLink;elselast.next=newLink;last=newLink;)/publiclongdeleteFirst()longtemp=first.dData;if(

20、first.next=null)last=null;first=first.next;returntemp;)/publicvoiddisplayList()System.out.print("List(first->last):");Link3current=first;while(current!=null)current.displayLink();current=current.next;)System.out.println("");)/publicclassFirstLastApppublicstaticvoidmain(Stringa

21、rgs)FirstLastListtheList=newFirstLastList();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é)點中的數(shù)據(jù)字段個

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

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

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

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

26、oidinsert(longLinknewLink=newLinkprevious=null;Linkcurrent=first;While(current!=nullPrevious=current;key)Link(key);&&key>current.dData)Current=current.next;If(previous=null)First=newLink;ElsePrevious.next=newLink;newLink.next=current;在鏈表上移動時，需要用一個previous引用，這樣才能把前一個鏈結(jié)點的Next字段指向新的鏈結(jié)點。創(chuàng)建新鏈結(jié)

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

28、revious的next字段指向新的鏈結(jié)點。不論哪種情況、者B讓新鏈結(jié)點的Next字段指向current。如果在表尾，current為Null值，則新鏈結(jié)點的Next字段也本應(yīng)該設(shè)為這個值(Null)。下面是有序鏈表的程序SortedList.java程序?qū)崿F(xiàn)了一個SortedList類，它擁有insert()、remove()和displayList()方法。只有insert()方法與無序鏈表中的insert()方法不同。package有序鏈表；classLinkpubliclongdData;publicLinknext;publicLink(longdd)dData=dd;/public

29、voiddisplayLink()System.out.print(dData+"");/classSortedListprivateLinkfirst;/publicSortedList()first=null;/publicbooleanisEmpty()return(first=null);/publicvoidinsert(longkey)LinknewLink=newLink(key);Linkprevious=null;Linkcurrent=first;while(current!=null&&key>current.dData)prev

30、ious=current;current=current.next;)if(previous=null)first=newLink;elseprevious.next=newLink;newLink.next=current;)/publicLinkremove()Linktemp=first;first=first.next;returntemp;)/publicvoiddisplayList()System.out.print("List(first->last):");Linkcurrent=first;while(current!=null)current.d

31、isplayLink();current=current.next;)System.out.println("");)publicclassSortedLinkApppublicstaticvoidmain(Stringargs)SortedListtheSortedList=newSortedList();theSortedList.insert(20);theSortedList.insert(40);theSortedList.displayList();theSortedList.insert(10);theSortedList.insert(30);theSort

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

33、雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。一般我們都構(gòu)造雙向循環(huán)鏈表。/*線性表的雙向鏈表存儲結(jié)構(gòu)*/typedefstructDuLNode(ElemTypedata;structDuLNode*prior,*next;DuLNode,*DuLinkList;/*帶頭結(jié)點的雙向循環(huán)鏈表的基本操作(14個)*/voidInitList(DuLinkList*L)/*產(chǎn)生空的雙向循環(huán)鏈表L*/*L=(DuLinkList)malloc(sizeof(DuLNode);if(*L)(*L)->next=(*L)->prior=*L;elseexit(OVE

34、RFLOW);voidDestroyList(DuLinkList*L)/*操作結(jié)果：銷毀雙向循環(huán)鏈表L*/DuLinkListq,p=(*L)->next;/*p指向第一個結(jié)點*/while(p!=*L)/*p沒到表頭*/q=p->next;free(p);p=q;free(*L);*L=NULL;voidClearList(DuLinkListL)/*不改變L*/*初始條件：L已存在。操作結(jié)果：將L重置為空表*/DuLinkListq,p=L->next;/*p指向第一個結(jié)點*/while(p!=L)/*p沒到表頭*/q=p->next;free(p);p=q;L-

35、>next=L->prior=L;/*頭結(jié)點的兩個指針域均指向自身*/StatusListEmpty(DuLinkListL)/*初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE,否則返回FALSE*/if(L->next=L&&L->prior=L)returnTRUE;elsereturnFALSE;intListLength(DuLinkListL)/*初始條件：L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù)*/inti=0;DuLinkListp=L->next;/*p指向第一個結(jié)點*/while(p!=L)/*p沒到表頭*/i+;

36、p=p->next;returni;StatusGetElem(DuLinkListL,inti,ElemType*e)/*當(dāng)?shù)趇個元素存在時，其值賦給e并返回OK,否則返回ERROR*/intj=1;/*j為計數(shù)器*/DuLinkListp=L->next;/*p指向第一個結(jié)點*/while(p!=L&&jnext;j+;if(p=L|j>i)/*第i個元素不存在*/returnERROR;*e=p->data;/*取第i個元素*/returnOK;)intLocateElem(DuLinkListL,ElemTypee,Status(*compare

37、)(ElemType,ElemType)/*初始條件：L已存在，compare()是數(shù)據(jù)元素判定函數(shù)*/*操作結(jié)果：返回L中第1個與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序。*/*若這樣的數(shù)據(jù)元素不存在，則返回值為0*/inti=0;DuLinkListp=L->next;/*p指向第1個元素*/while(p!=L)i+;if(compare(p->data,e)/*找到這樣的數(shù)據(jù)元素*/returni;p=p->next;return0;StatusPriorElem(DuLinkListL,ElemTypecur_e,ElemType/*操作結(jié)果：若前驅(qū)，*/*否則

38、操作失敗，cur_e是L的數(shù)據(jù)元素，且不是第一個，則用pre_e無定義*/DuLinkListwhile(p!=L)p=L->next->next;/*p沒到表頭/*p指向第2個元素*/*/*pre_e)pre_e返回它的if(p->data=cur_e)*pre_e=p->prior->data;returnTRUE;p=p->next;returnFALSE;StatusNextElem(DuLinkList/*操作結(jié)果：若cur_e是LL,ElemTypecur_e,ElemType的數(shù)據(jù)元素，且不是最后一個，則用*next_e)nexte返回它的后繼

39、，*/*否則操作失敗，next_e無定義*/DuLinkListp=L->next->next;/*p指向第2個元素*/while(p!=L)/*p沒到表頭*/(if(p->prior->data=cur_e)(*next_e=p->data;returnTRUE;p=p->next;returnFALSE;DuLinkListGetElemP(DuLinkListL,inti)/*另加*/*在雙向鏈表L中返回第i個元素的地址。i為0,返回頭結(jié)點的地址。若第個元素不存在，*/*返回NULL*/intj;DuLinkListp=L;/*p指向頭結(jié)點*/if(i

40、<0|i>ListLength(L)/*i值不合法*/returnNULL;for(j=1;j<=i;j+)p=p->next;returnp;StatusListInsert(DuLinkListL,inti,ElemTypee)/*在帶頭結(jié)點的雙鏈循環(huán)線性表L中第i個位置之前插入元素e,i的合法值為1wi表長+1*/*改進(jìn)算法2.18,否則無法在第表長+1個結(jié)點之前插入元素*/DuLinkListp,s;if(i<1|i>ListLength(L)+1)/*i值不合法*/returnERROR;p=GetElemP(L,i-1);/*在L中確定第i個元素

41、前驅(qū)的位置指針p*/if(!p)/*p=NULL,即第i個元素的前驅(qū)不存在(設(shè)頭結(jié)點為第1個元素的前驅(qū))*/returnERROR;s=(DuLinkList)malloc(sizeof(DuLNode);if(!s)returnOVERFLOW;s->data=e;*/s->prior=p;/*在第i-1個元素之后插入s->next=p->next;p->next->prior=s;p->next=s;returnOK;)StatusListDelete(DuLinkListL,inti,ElemType*e)/*刪除帶頭結(jié)點的雙鏈循環(huán)線性表L的第i

42、個元素，i的合法值為1Wi表長*/DuLinkListp;if(i<1)/*i值不合法*/returnERROR;p=GetElemP(L,i);/*在L中確定第i個元素的位置指針p*/if(!p)/*p=NULL,即第i個元素不存在*/returnERROR;*e=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);returnOK;)voidListTraverse(DuLinkListL,void(*visit)(ElemType)/*由雙鏈循環(huán)線性表L的頭結(jié)點出發(fā)，

43、正序?qū)γ總€數(shù)據(jù)元素調(diào)用函數(shù)visit()*/DuLinkListp=L->next;/*p指向頭結(jié)點*/while(p!=L)visit(p->data);p=p->next;)printf("n");)voidListTraverseBack(DuLinkListL,void(*visit)(ElemType)/*由雙鏈循環(huán)線性表L的頭結(jié)點出發(fā)，逆序?qū)γ總€數(shù)據(jù)元素調(diào)用函數(shù)visit()。另加*/DuLinkListp=L->prior;/*p指向尾Z吉點*/while(p!=L)visit(p->data);p=p->prior;)pr

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

45、每一種容器都將其迭代器以嵌套的方式定義于內(nèi)部。因此各種迭代器的接口相同，型別卻不同。這直接導(dǎo)出了泛型程序設(shè)計的概念：所有操作行為都使用相同接口，雖然它們的型別不同。功能迭代器使開發(fā)人員能夠在類或結(jié)構(gòu)中支持foreach迭代，而不必整個實現(xiàn)IEnumerable或者IEnumerator接口。只需提供一個迭代器，即可遍歷類中的數(shù)據(jù)結(jié)構(gòu)。當(dāng)編譯器檢測到迭代器時，將自動生成Enumerable接口或者IEnumerator接口的Current,MoveNext和Dispose方法。特點1 .迭代器是可以返回相同類型值的有序序列的一段代碼；2 .迭代器可用作方法、運算符或get訪問器的代碼體；3 .迭

46、代器代碼使用yieldreturn語句依次返回每個元素，yieldbreak將終止迭代；4 .可以在類中實現(xiàn)多個迭代器，每個迭代器都必須像任何類成員一樣有惟一的名稱，并且可以在foreach語句中被客戶端代碼調(diào)用；5 .迭代器的返回類型必須為IEnumerable和IEnumerator中的任意一種；6 .迭代器是產(chǎn)生值的有序序列的一個語句塊，不同于有一個或多個yield語句存在的常規(guī)語句塊；7 .迭代器不是一種成員，它只是實現(xiàn)函數(shù)成員的方式，理解這一點是很重要的，一個通過迭代器實現(xiàn)的成員，可以被其他可能或不可能通過迭代器實現(xiàn)的成員覆蓋和重載；8 .迭代器塊在C#語法中不是獨特的元素，它們在幾

47、個方面受到限制，并且主要作用在函數(shù)成員聲明的語義上，它們在語法上只是語句塊而已；四、遞歸遞歸是函數(shù)調(diào)用自身的一種特殊的編程技術(shù)，其應(yīng)用主要在以下幾個方面:在java當(dāng)中的基本形式是:遞歸二分查找Java二分查找實現(xiàn)/*名稱：BinarySearchPublicvoidmothed(intn)/當(dāng)滿足某條件時：Mothed(n-1);)，歡迎大家提出交流意見.* 功能：實現(xiàn)了折半查找(二分查找)的遞歸和非遞歸算法.* 說明：* 1、要求所查找的數(shù)組已有序，并且其中元素已實現(xiàn)Comparable<T>接口，如Integer、String等.* 2、非遞歸查找使用search();,遞歸

48、查找使用searchRecursively();*本程序僅供編程學(xué)習(xí)參考*author：Winty*date:2008-8-11*email：emailwintys/email*/classBinarySearch<TextendsComparable<T>>privateT口data;/要排序的數(shù)據(jù)publicBinarySearch(Tdata)this.data=data;)publicintsearch(Tkey)intlow;inthigh;intmid;if(data=null)return-1;low=0;high=data.length-1;2;&quo

49、t;+mid+"midvalue:"+datamid);/while(low<=high)mid=(low+high)/System.out.println("midif(pareTo(datamid)<0)high=mid-1;elseif(pareTo(datamid)>0)low=mid+1;elseif(pareTo(datamid)=0)returnmid;return-1;privateintdoSearchRecursively(intlow,inthigh,Tkey)intmid;intresult;if(low<=high

50、)mid=(low+high)/2;result=pareTo(datamid);+"midvalue:"+datamid);/,mid-1,key);+1,high,key);System.out.println("mid"+midif(result<0)returndoSearchRecursively(lowelseif(result>0)returndoSearchRecursively(midelseif(result=0)returnmid;return-1;publicintsearchRecursively(Tkey)if(d

51、ata=null)return-1;returndoSearchRecursively(0,data.length-1,key);Integer口datapublicstaticvoidmain(Stringargs)1,4,5,8,15,33,48,77,96;BinarySearch<Integer>/System.out.println("KeybinSearch=newBinarySearch<Integer>(data);index:"+binSearch.search(33);System.out.println("Keyind

52、ex:"+binSearch.searchRecursively(3);/String口dataStr="A","C","F","J","L","N","T"BinarySearch<String>binSearch=newBinarySearch<String>(dataStr);/System.out.println("Keyindex:"+binSearch.search("A"

53、;);遞歸排序其實在數(shù)組的全排序中完全可以使用更加易懂簡便的寫法一一for循環(huán)，但是通過for循環(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á)到較好的效果(遞歸的

54、時候排除所有不可能的萬案)消除遞歸消除遞歸的基本思路是用棧來模擬系統(tǒng)的函數(shù)調(diào)用從而消除遞歸。基本上要做一下三件事：傳遞參數(shù)(包括返回地址)并轉(zhuǎn)到函數(shù)入口；獲得參數(shù)并處理參數(shù)；根據(jù)傳入的返回地址返回五、哈希表一般的線性表、樹中，記錄在結(jié)構(gòu)中的相對位置是隨機(jī)的即和記錄的關(guān)鍵字之間不存在確定的關(guān)系，在結(jié)構(gòu)中查找記錄時需進(jìn)行一系列和關(guān)鍵字的比較。這一類查找方法建立在比較”的基礎(chǔ)上，查找的效率與比較次數(shù)密切相關(guān)。理想的情況是能直接找到需要的記錄，因此必須在記錄的存儲位置和它的關(guān)鍵字之間建立一確定的對應(yīng)關(guān)系f,使每個關(guān)鍵字和結(jié)構(gòu)中一個唯一的存儲位置相對應(yīng)。因而查找時，只需根據(jù)這個對應(yīng)關(guān)系f找到給定值K的像

55、f（K）。若結(jié)構(gòu)中存在關(guān)鍵字和K相等的記錄，則必定在f（K）的存儲位置上，由此不需要進(jìn)行比較便可直接取得所查記錄。在此，稱這個對應(yīng)關(guān)系f為哈希函數(shù)，按這個思想建立的表為哈希表（又稱為雜湊法或散列表）。哈希表不可避免沖突（collision）現(xiàn)象：對不同的關(guān)鍵字可能得到同一哈希地址即keylwkey2,而f（key1）=f（key2）。具有相同函數(shù)值的關(guān)鍵字對該哈希函數(shù)來說稱為同義詞（synonym）。因此，在建造哈希表時不僅要設(shè)定一個好的哈希函數(shù)，而且要設(shè)定一種處理沖突的方法。可如下描述哈希表：根據(jù)設(shè)定的哈希函數(shù)H（key）和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個有限的、地址連續(xù)的地址集（區(qū)間）上并以關(guān)鍵字在地址集中的象”作為相應(yīng)記錄在表中的存儲位置，這種表被稱為哈希表。六、高級排序下周提供。七、二叉樹1 .二叉樹？答：二叉樹是一種樹型結(jié)構(gòu)，它的特點是每個結(jié)點至多只有二棵子樹（即二叉樹中不存在度大于2的結(jié)點），并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。.二叉樹的基本形態(tài)：（1）空二叉樹；（2）只有一個根結(jié)點的二叉樹；（3）右子樹為空的二叉樹；4）左子樹為空的二叉樹；（5）完全二叉樹。二叉樹的存儲結(jié)構(gòu)包括：1 .順序存儲結(jié)構(gòu)連續(xù)