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 ）實質(zhì)上是相同類型變量列表。要創(chuàng)建一個數(shù)組，你必須首先定義數(shù)組變量所需的類型。通用的一維數(shù)組的聲明格式是：type var-name ; 獲得一個數(shù)組需要2步。第一

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

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

4、2個，這樣依次類推，直至所有數(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í)行過程中始終是不變的。這些條件被稱 為算法的不變性，如果不變性不為真了，則標(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)

5、記最左邊未排序的數(shù)據(jù)，然后使用IN標(biāo)記第1個數(shù)據(jù)，依次與MIN進行比較，如果比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； 選擇排序與冒泡排序比較，比較次數(shù)沒有明顯改變

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

7、ain-1; - -in;Ain=temp;插入排序的效率：O（N*N）, 比較N*N/4，復(fù)制N*N/4；插入排序在隨機數(shù)的情況下，比冒泡快一倍，比選擇稍快；在基本有序的數(shù)組中，插入排序幾乎只需要O（N）；在逆序情況下，并不比冒泡快；二、棧與隊列1、棧的定義    棧（Stack）是限制僅在表的一端進行插入和刪除運算的線性表。(1)通常稱插入、刪除的這一端為棧頂（Top），另一端稱為棧底（Bottom）。(2)當(dāng)表中沒有元素時稱為空棧。(3)棧為后進先出（Last In First Out）的線性表，簡稱為LIFO表。    棧的修

8、改是按后進先出的原則進行。每次刪除（退棧）的總是當(dāng)前棧中"最新"的元素，即最后插入（進棧）的元素，而最先插入的是被放在棧的底部，要到最后才能刪除。        【示例】元素是以a1，a2，an的順序進棧，退棧的次序卻是an，an-1，a1。2、棧的基本運算（1）InitStack（S）    構(gòu)造一個空棧S。（2）StackEmpty（S）    判?？?。若S為空棧，則返回TRUE，否則返回FALSE。（3）StackFull（S） 

9、   判棧滿。若S為滿棧，則返回TRUE，否則返回FALSE。注意： 該運算只適用于棧的順序存儲結(jié)構(gòu)。（4）Push（S，x）    進棧。若棧S不滿，則將元素x插入S的棧頂。（5）Pop（S）    退棧。若棧S非空，則將S的棧頂元素刪去，并返回該元素。（6）StackTop（S）    取棧頂元素。若棧S非空，則返回棧頂元素，但不改變棧的狀態(tài)。隊列的定義及基本運算1、定義    隊列（Queue）是只允許在一端進行插入，而在另一端進行刪除的運算受限的線

10、性表       （1）允許刪除的一端稱為隊頭（Front）。（2）允許插入的一端稱為隊尾（Rear）。（3）當(dāng)隊列中沒有元素時稱為空隊列。（4）隊列亦稱作先進先出（First In First Out）的線性表，簡稱為FIFO表。    隊列的修改是依先進先出的原則進行的。新來的成員總是加入隊尾（即不允許"加塞"），每次離開的成員總是隊列頭上的（不允許中途離隊），即當(dāng)前"最老的"成員離隊?！纠吭陉犃兄幸来渭尤朐豠1，a2，an之后，a1是隊頭元素，an是隊尾元

11、素。退出隊列的次序只能是a1，a2，an。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）

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

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

14、須存儲指示其后繼結(jié)點的地址（或位置）信息（稱為指針（pointer）或鏈(link)）注意：鏈?zhǔn)酱鎯κ亲畛Ｓ玫拇鎯Ψ绞街?，它不僅可用來表示線性表，而且可用來表示各種非線性的數(shù)據(jù)結(jié)構(gòu)。2、鏈表的結(jié)點結(jié)構(gòu)datanext data域-存放結(jié)點值的數(shù)據(jù)域next域-存放結(jié)點的直接后繼的地址（位置）的指針域（鏈域）注意：鏈表通過每個結(jié)點的鏈域?qū)⒕€性表的n個結(jié)點按其邏輯順序鏈接在一起的。每個結(jié)點只有一個鏈域的鏈表稱為單鏈表（Single Linked List）?！纠烤€性表（bat，cat，eat，fat，hat，jat，lat，mat）的單鏈表示如示意圖3、頭指針head和終端結(jié)點指針域的表示單鏈

15、表中每個結(jié)點的存儲地址是存放在其前趨結(jié)點next域中，而開始結(jié)點無前趨，故應(yīng)設(shè)頭指針head指向開始結(jié)點。注意：鏈表由頭指針唯一確定，單鏈表可以用頭指針的名字來命名?！纠款^指針名是head的鏈表可稱為表head。終端結(jié)點無后繼，故終端結(jié)點的指針域為空，即NULL。4、單鏈表的一般圖示法由于我們常常只注重結(jié)點間的邏輯順序，不關(guān)心每個結(jié)點的實際位置，可以用箭頭來表示鏈域中的指針，線性表（bat，cat，fat，hat，jat，lat，mat）的單鏈表就可以表示為下圖形式。5、單鏈表類型描述typedef char DataType; /假設(shè)結(jié)點的數(shù)據(jù)域類型為字符typedef struct no

16、de /結(jié)點類型定義DataType data; /結(jié)點的數(shù)據(jù)域struct node *next;/結(jié)點的指針域ListNodetypedef ListNode *LinkList;ListNode *p;LinkList head;注意：*LinkList和ListNode是不同名字的同一個指針類型（命名的不同是為了概念上更明確）*LinkList類型的指針變量head表示它是單鏈表的頭指針ListNode類型的指針變量p表示它是指向某一結(jié)點的指針6、指針變量和結(jié)點變量 指針變量結(jié)點變量 定義 在變量說明部分顯式定義 在程序執(zhí)行時，通過標(biāo)準(zhǔn) 函數(shù)malloc生成 取值 非空時，存放某類型結(jié)

17、點 實際存放結(jié)點各域內(nè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é)點變量的名字*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é)點的

18、data域的值(*p).next的值*p后繼結(jié)點的地址*(*p).next)*p后繼結(jié)點注意： 若指針變量p的值為空（NULL），則它不指向任何結(jié)點。此時，若通過*p來訪問結(jié)點就意味著訪問一個不存在的變量，從而引起程序的錯誤。 有關(guān)指針類型的意義和說明方式的詳細(xì)解釋可見，在鏈表中插入結(jié)點只需要修改指針。但同時，若要在第 i 個結(jié)點之前插入元素，修改的是第 i-1 個結(jié)點的指針。因此，在單鏈表中第 i 個結(jié)點之前進行插入的基本操作為:找到線性表中第i-1個結(jié)點，然后修改其指向后繼的指針。雙端鏈表雙端鏈表與傳統(tǒng)的鏈表非常相似，但是它有一個新增的特性：即對最后一個鏈結(jié)點的引用，就像對第一個鏈結(jié)點的引

19、用一樣。對最后一個鏈結(jié)點的引用允許像在表頭一樣，在表尾直接插入一個鏈結(jié)點。當(dāng)然，仍然可以在普通的單鏈表的表尾插入一個鏈結(jié)點，方法是遍歷整個鏈表直到到達表尾，但是這種方法效率很低。對最后一個鏈結(jié)點的引用允許像在表頭一樣，在表尾直接插入一個鏈結(jié)點。當(dāng)然，仍然可以在普通的單鏈表的表尾插入一個鏈結(jié)點，方法是遍歷整個鏈表直到到達表尾，但是這種方法效率很低。像訪問表頭一樣訪問表尾的特性，使雙端鏈表更適合于一些普通鏈表不方便操作的場合，隊列的實現(xiàn)就是這樣一個情況。下面是一個雙端鏈表的例子。class Link3 public long dData; public Link3 next; /. public

20、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(long dd) Link3 newLink=n

21、ew 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) last=null; first=first

22、.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) FirstLastLi

23、st 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é)點中的數(shù)據(jù)字段個數(shù)從

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

25、個方法在表尾插入一個新的鏈結(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é)點，那么多表頭刪除也是一種特殊情況：last必須被賦

26、值為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ù)組的地方是插入的速度，另外鏈表可以擴展到

27、全部有效的使用內(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é)點有可以插在表頭，或者插在表尾。看一下這段代碼：Public void i

28、nsert(long key)Link newLink=new Link(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;在鏈表上移動時，需要用一個previous引用，這樣才能把前一個鏈結(jié)點的Next字段指向新的鏈結(jié)點。創(chuàng)建

29、新鏈結(jié)點后，把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é)尾，

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

31、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(long key)Link newLink=new Link(key);Link previous=null;Link current=first;while(current!=null &am

32、p;& key>current.dData)previous=current;current=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 cu

33、rrent=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);theSortedList.displayList();theSorte

34、dList.insert(10);theSortedList.insert(30);theSortedList.insert(50);theSortedList.displayList();theSortedList.remove();theSortedList.displayList();System.exit(0);在Main()方法中，插入值為20和40的兩個鏈結(jié)點。然后再插入三個鏈結(jié)點，分別是10、30和50。這三個值分別插在表頭、表中和表尾。這說明insert()方法正確地處理了特殊情況。最后刪除了一個鏈結(jié)點，表現(xiàn)出刪除操作總是從表頭進行。每一步變化后，都顯示整個鏈表。雙向鏈表雙向鏈

35、表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。一般我們都構(gòu)造雙向循環(huán)鏈表。/* 線性表的雙向鏈表存儲結(jié)構(gòu) */typedef struct DuLNodeElemType data;struct DuLNode *prior,*next;DuLNode,*DuLinkList;/*帶頭結(jié)點的雙向循環(huán)鏈表的基本操作(14個) */void InitList(DuLinkList *L) /* 產(chǎn)生空的雙向循環(huán)鏈表L */*L=(DuLinkList)malloc(sizeof

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

37、inkList q,p=L->next; /* p指向第一個結(jié)點 */while(p!=L) /* p沒到表頭 */q=p->next;free(p);p=q;L->next=L->prior=L; /* 頭結(jié)點的兩個指針域均指向自身 */Status ListEmpty(DuLinkList L) /* 初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE */if(L->next=L&&L->prior=L)return TRUE;elsereturn FALSE;int ListLength(DuLinkL

38、ist L) /* 初始條件：L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù) */int i=0;DuLinkList p=L->next; /* p指向第一個結(jié)點 */while(p!=L) /* p沒到表頭 */i+;p=p->next;return i;Status GetElem(DuLinkList L,int i,ElemType *e) /* 當(dāng)?shù)趇個元素存在時，其值賦給e并返回OK，否則返回ERROR */int j=1; /* j為計數(shù)器 */DuLinkList p=L->next; /* p指向第一個結(jié)點 */while(p!=L&&jnext

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

40、 */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ù)據(jù)元素，且不是第一個，則用pre_e返回它的前驅(qū)， */* 否則操作失敗，pre_e無定義 */DuLinkList p=L->next->next; /* p指向第2個元素 */while(p!=L) /* p沒到表頭 */if(p->data

41、=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ù)元素，且不是最后一個，則用next_e返回它的后繼， */* 否則操作失敗，next_e無定義 */DuLinkList p=L->next->next; /* p指向第2個元素 */while(p!=L) /* p沒到表頭 */if(p->prior->data=c

42、ur_e)*next_e=p->data;return TRUE;p=p->next;return FALSE;DuLinkList GetElemP(DuLinkList L,int i) /* 另加 */ /* 在雙向鏈表L中返回第i個元素的地址。i為0，返回頭結(jié)點的地址。若第i個元素不存在，*/* 返回NULL */int j;DuLinkList p=L; /* p指向頭結(jié)點 */if(i<0|i>ListLength(L) /* i值不合法 */return NULL;for(j=1;j<=i;j+)p=p->next;return p;Statu

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

44、DuLinkList)malloc(sizeof(DuLNode);if(!s)return OVERFLOW;s->data=e;s->prior=p; /* 在第i-1個元素之后插入 */s->next=p->next;p->next->prior=s;p->next=s;return OK;Status ListDelete(DuLinkList L,int i,ElemType *e) /* 刪除帶頭結(jié)點的雙鏈循環(huán)線性表L的第i個元素，i的合法值為1i表長 */DuLinkList p;if(i<1) /* i值不合法 */return

45、ERROR;p=GetElemP(L,i); /* 在L中確定第i個元素的位置指針p */if(!p) /* p=NULL,即第i個元素不存在 */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é)點出發(fā)，正序?qū)γ總€數(shù)據(jù)元素調(diào)用函數(shù)visit() */DuLinkList p=L->n

46、ext; /* p指向頭結(jié)點 */while(p!=L)visit(p->data);p=p->next;printf("n");void ListTraverseBack(DuLinkList L,void(*visit)(ElemType) /* 由雙鏈循環(huán)線性表L的頭結(jié)點出發(fā)，逆序?qū)γ總€數(shù)據(jù)元素調(diào)用函數(shù)visit()。另加 */DuLinkList p=L->prior; /* p指向尾結(jié)點 */while(p!=L)visit(p->data);p=p->prior;printf("n");迭代器迭代器是一種對象，它

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

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

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

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

51、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ù)  &#

52、160; public BinarySearch(T data)        this.data = data;        public int search(T key)        int low;        int high;  &

53、#160;     int mid;        if(data = null)            return -1;        low = 0;        high = d

54、ata.length - 1;        while(low <= high)            mid = (low + high) / 2;            System.out.println("mid " + mid + "

55、; mid value:" + datamid);/                        if(pareTo(datamid) < 0)                hig

56、h = mid - 1;            else if(pareTo(datamid) > 0)                low = mid + 1;            els

57、e if(pareTo(datamid) = 0)                return mid;                            

58、return -1;        private int doSearchRecursively(int low , int high , T key)        int mid;        int result;        if(low <= high)&#

59、160;           mid = (low + high) / 2;            result = pareTo(datamid);            System.out.println("mid " +

60、mid + " mid value:" + datamid);/                        if(result < 0)                return doSearchRecursively(low , mid - 1 , key);