Java數據結構和算法

一、數組于簡單排序...............................................................1

二、棧與隊列....................................................................4

三、鏈表........................................................................7

四、遞歸.......................................................................22

五、哈希表.....................................................................25

六、高級排序...................................................................25

七、二叉樹.....................................................................25

八、紅一黑樹...................................................................26

九、堆.........................................................................36

十、帶權圖.....................................................................40

一、數組于簡單排序

數組

數組(array)是相同類型變量的集合，可以使用共同的名字引用它。數組可

被定義為任何類型，可以是一維或多維。數組中的一個特別要素是通過下標來訪

問它。數組提供了一種將有聯系的信息分組的便利方法。

一維數組

一維數組(one-dimensionalarray)實質上是相同類型變量列表。要創建一

個數組，你必須首先定義數組變量所需的類型。通用的一維數組的聲明格式是：

typevar-name[];

獲得一個數組需要2步。第一步，你必須定義變量所需的類型。第二步，你

必須使用運算符new來為數組所要存儲的數據分配內存，并把它們分配給數組

變量。這樣Java中的數組被動態地分配。如果動態分配的概念對你陌生，別擔

心，它將在本書的后面詳細討論。

數組的初始化(arrayinitializer)就是包括在花括號之內用逗號分開的表達

式的列表。逗號分開了數組元素的值。Java會自動地分配一個足夠大的空間來

保存你指定的初始化元素的個數，而不必使用運算符new。

Java嚴格地檢查以保證你不會意外地去存儲或引用在數組范圍以外的值。

Java的運行系統會檢查以確保所有的數組下標都在正確的范圍以內(在這方面，

Java與C/C++從根本上不同，C/C++不提供運行邊界檢查)。

多維數組

在Java中，多維數組(multidimensionalarrays)實際上是數組的數組。你

可能期望，這些數組形式上和行動上和一般的多維數組一樣。然而，你將看到，

有一些微妙的差別。定義多維數組變量要將每個維數放在它們各自的方括號中。

例如，下面語句定義了一個名為twoD的二維數組變量。

inttwoD[][]=newint⑷⑸；

簡單排序

簡單排序中包括了：冒泡排序、選擇排序、插入排序；

L冒泡排序的思想：

假設有N個數據需要排序，則從第0個數開始，依次比較第0和第1個數據，

如果第。個大于第1個則兩者交換，否則什么動作都不做，繼續比較第1個第2

個…，這樣依次類推，直至所有數據都“冒泡”到數據頂上。

冒泡排序的的java代碼：

PublicvoidbubbleSort()

(

intin,out;

for(out=n日ems-l;out>0;out--)

for(in=0;in<out;in++)

(

lf(a[in]>a[in+l])

Swap(injn+1);

}

}

算法的不變性：許多算法中，有些條件在算法執行過程中始終是不變的。這些

條件被稱為算法的不變性，如果不變性不為真了，則標記出錯了；

冒泡排序的效率0(N*N),比較N*N/2,交換N*N/4；

2.選擇排序的思想：

假設有N條數據，則暫且標記第0個數據為MIN(最小)，使用OUT標記最左

邊未排序的數據，然后使用IN標記第1個數據，依次與MIN進行比較，如果比

MIN小，則將該數據標記為MIN,當第一輪比較完后，最終的MIN與OUT標記

數據交換，依次類推；

選擇排序的java代碼：

PublicvoidselectSort()

(

Intin,out,min;

For(out=0;out<nElems-l;out++)

{

Min=out;

For(in=out+l;in<nElems;in++)

lf(a[in]<a[min])

Min=in;

Swap(out,min);

)

}

選擇排序的效率：0(N*N),比較N*N/2,交換<N；選擇排序與冒泡排序比

較，比較次數沒有明顯改變，但交換次數明顯減少了很多；

3.插入排序的思想：

插入排序是在部分數據有序的情況下，使用OUT標記第一個無序的數據，將

其提取保存到一個中間變量temp中去，使用IN標記空位置，依次比較temp中

的值與IN-1的值，如果IN-值大于temp的值，則后移，直到遇到第一個比temp

小的值，在其下一個位置插入；

插入排序的java代碼：

PublicvoidlnsertionSort()

(

Intin,out;

For(out=l;out<n曰ems;out++)

Longtemp=a[out]

ln=out;

While(in>0&&a[in-l]>temp)

(

A[in]=a[in-1];

--in;

)

A[in]=temp;

}

}

插入排序的效率：0(N*N),比較N*N/4,復制N*N/4；插入排序在隨機數的

情況下，比冒泡快一倍，比選擇稍快；在基本有序的數組中，插入排序幾乎只需

要0(N)；在逆序情況下，并不比冒泡快；

二、棧與隊列

1、棧的定義

棧(Stack)是限制僅在表的一端進行插入和刪除運算的線性表。

(1)通常稱插入、刪除的這一端為棧頂(Top),另一端稱為棧底(Bottom)。

(2)當表中沒有元素時稱為空棧。

(3)棧為后進先出(LastInFirstOut)的線性表，簡稱為LIFO表。

棧的修改是按后進先出的原則進行。每次刪除(退棧)的總是當前棧

中“最新”的元素，即最后插入(進棧)的元素，而最先插入的是被放在棧的底部，

要到最后才能刪除。

【示例】元素是以al,a2,…，an的順序進棧，退棧的次序卻是an,an-1,…,

alo

2、棧的基本運算

(1)InitStack(S)

構造一個空棧So

(2)StackEmpty(S)

判棧空。若S為空棧，則返回TRUE,否則返回FALSE。

(3)StackFull(S)

判棧滿。若S為滿棧，則返回TRUE,否則返回FALSE。

注意：該運算只適用于棧的順序存儲結構。

(4)Push(S,x)

進棧。若棧S不滿，則將元素x插入S的棧頂。

(5)Pop(S)

退棧。若棧S非空，則將S的棧頂元素刪去，并返回該元素。

(6)StackTop(S)

取棧頂元素。若棧S非空，則返回棧頂元素，但不改變棧的狀態。

隊列的定義及基本運算

1、定義

隊列（Queue）是只允許在一端進行插入，而在另一端進行刪除的運算

受限的線性表

出隊--2…

r

隊頭隊尾

隊列示意圖

（1）允許刪除的一端稱為隊頭（Front）。

（2）允許插入的一端稱為隊尾（Rear）。

（3）當隊列中沒有元素時稱為空隊列。

（4）隊列亦稱作先進先出（FirstInFirstOut）的線性表，簡稱為FIFO

表。

隊列的修改是依先進先出的原則進行的。新來的成員總是加入隊尾（即

不允許“加塞”），每次離開的成員總是隊列頭上的（不允許中途離隊），即當前

〃最老的〃成員離隊。

【例】在隊列中依次加入元素a“&,…，a”之后，a是隊頭元素，a”是隊尾

元素。退出隊列的次序只能是a"a”…，a?o

2、隊列的基本邏輯運算

（1）InitQueue（Q）

置空隊。構造一個空隊列Q。

（2）QueueEmpty（Q）

判隊空。若隊列Q為空，則返回真值，否則返回假值。

(3)QueueFull(Q)

判隊滿。若隊列Q為滿，則返回真值，否則返回假值。

注意：此操作只適用于隊列的順序存儲結構。

(4)EnQueue(Q,x)

若隊列Q非滿，則將元素x插入Q的隊尾。此操作簡稱入隊。

(5)DeQueue(Q)

若隊列Q非空，則刪去Q的隊頭元素，并返回該元素。此操作簡稱出

隊。

(6)QueueFront(Q)

若隊列Q非空，則返回隊頭元素，但不改變隊列Q的狀態。

三、鏈表

1.鏈結點

在鏈表中，每個數據項都被包含在‘點''中，一個點是某個類的對象，這個類可認叫做

LINK。因為一個鏈表中有許多類似的鏈結點，所以有必要用一個不同于鏈表的類來表達

鏈結點。每個LINK對象中都包含一個對下一個點引用的字段(通常叫做next)但是本

身的對象中有一個字段指向對第一個鏈結點的引用

單鏈表

用一組地址任意的存儲單元存放線性表中的數據元素。

以元素(數據元素的映象)

+指針(指示后繼元素存儲位置)

=結點

(表示數據元素或數據元素的映象)

以“結點的序列”表示線性表

稱作線性鏈表(單鏈表)——

單鏈表是一種順序存取的結構，為找第i個數據元素，必須先找到第i-1個數

據元素。

因此，查找第i個數據元素的基本操作為：移動指針，比較j和i

1、鏈接存儲方法

鏈接方式存儲的線性表簡稱為鏈表(LinkedList)?

鏈表的具體存儲表示為：

①用一組任意的存儲單元來存放線性表的結點(這組存儲單元既可以是連續的，

也可以是不連續的)

②鏈表中結點的邏輯次序和物理次序不一定相同。為了能正確表示結點間的邏

輯關系，在存儲每個結點值的同時，還必須存儲指示其后繼結點的地址(或位置)信

息(稱為指針(pointer)或鏈(link))

注意：

鏈式存儲是最常用的存儲方式之一，它不僅可用來表示線性表，而且可用來表示

各種非線性的數據結構。

2、鏈表的結點結構

|data|next|

data域--存放結點值的數據域

next域-存放結點的直接后繼的地址(位置)的指針域(鏈域)

注意：

①鏈表通過每個結點的鏈域將線性表的n個結點按其邏輯順序鏈接在一起的。

②每個結點只有一個鏈域的鏈表稱為單鏈表(SingleLinkedList),

【例】線性表(bat,cat,eat,fat.hat,jat.lat,mat)的單鏈表示如示意圖

3、頭指針head和終端結點指針域的表示

單鏈表中每個結點的存儲地址是存放在其前趨結點next域中，而開始結點無前

趨，故應設頭指針head指向開始結點。

注意：

鏈表由頭指針唯一確定，單鏈表可以用頭指針的名字來命名。

【例】頭指針名是head的鏈表可稱為表head。

終端結點無后繼，故終端結點的指針域為空，即NULLo

4、單鏈表的一般圖示法

由于我們常常只注重結點間的邏輯順序，不關心每個結點的實際位置，可以用箭

頭來表示鏈域中的指針，線性表(bat,cat.fat,hat,jat,lat,mat)的單鏈表就可

以表示為下圖形式。

5、單鏈表類型描述

typedefcharDataType;〃假設結點的數據域類型為字符

typedefstructnode{〃結點類型定義

DataTypedata;〃結點的數據域

structnode*next;〃結點的指針域

JListNode

typedefListNode*LinkList;

ListNode*p;

LinkListhead;

注意：

①*LinkList和ListNode是不同名字的同一個指針類型(命名的不同是為了概念

上更明確)

②*LinkList類型的指針變量head表示它是單鏈表的頭指針

③ListNode類型的指針變量p表示它是指向某一結點的指針

6、指針變量和結點變量

|指針變量|結點變量|

定義|在變量說明部分顯式定義|在程序執行時，通過標準|

||函數malloc生成|

取值|非空時，存放某類型結點|實際存放結點各域內容|

|的地址||

操作方式|通過指針變量名訪問|通過指針生成、訪問和釋放|

①生成結點變量的標準函數

p=(ListNode*)malloc(sizeof(ListNode))；

〃函數malloc分配一個類型為ListNode的結點變量的空間,并將其首地址放入指

針變量p中

②釋放結點變量空間的標準函數

free(p)；〃釋放p所指的結點變量空間

③結點分量的訪問

利用結點變量的名字*p訪問結點分量

方法一：(*p).data和(*p).next

方法二：p->data和p->next

④指針變量p和結點變量*p的關系

指針變量P的值——結點地址

結點變量*p的值——結點內容

(*p).data的值----p指針所指結點的data域的值

(*p).next的值----*p后繼結點的地址

*((*p).next)——*p后繼結點

注意：

①若指針變量p的值為空(NULL),則它不指向任何結點。此時，若通過*p

來訪問結點就意味著訪問一個不存在的變量，從而引起程序的錯誤。

②有關指針類型的意義和說明方式的詳細解釋

可見，在鏈表中插入結點只需要修改指針。但同時，若要在第i個結點之前插

入元素，修改的是第i-1個結點的指針。

因此，在單鏈表中第i個結點之前進行插入的基本操作為：

找到線性表中第i-1個結點，然后修改其指向后繼的指針。

雙端鏈表

雙端鏈表與傳統的鏈表非常相似，但是它有一個新增的特性：即對最后一個鏈結點的

引用，就像對第一個鏈結點的引用一樣。

對最后一個鏈結點的引用允許像在表頭一樣，在表尾直接插入一個鏈結點。當然，仍

然可以在普通的單鏈表的表尾插入一個鏈結點，方法是遍歷整個鏈表直到到達表尾，

但是這種方法效率很低。

對最后一個鏈結點的引用允許像在表頭一樣，在表尾直接插入一個鏈結點。當然，仍

然可以在普通的單鏈表的表尾插入一個鏈結點，方法是遍歷整個鏈表直到到達表尾，

但是這種方法效率很低。

像訪問表頭一樣訪問表尾的特性，使雙端鏈表更適合于一些普通鏈表不方便操作的場

合，隊列的實現就是這樣一個情況。

下面是一個雙端鏈表的例子。

classLink3{

publiclongdData;

publicLink3next;

//.............................

publicLink3(longd){

dData=d;

)

//.............................

publicvoiddisplayLink(){

System.out.print(dData+"");

)

)

lllllllllllllllllllllllllllllllllll

classFirstLastList{

privateLink3first;

privateLink3last;

//.............................

publicFirstLastList(){

first=null;

last=null;

}

//..............................

publicbooleanisEmpty(){

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;

else

last.next=newLink;

last=newLink;

)

//................................

publiclongdeleteFirst(){

longtemp=first.dData;

if(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("");

)

lllllllllllllllllllllllllllllllllllll

publicclassFirstLastApp{

publicstaticvoidmain(String[]args){

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();

)

)

為了簡單起見，在這個程序中，把每個鏈結點中的數據字段個數從兩個壓縮到一個。

這更容易顯示鏈結點的內容。(記住，在一個正式的程序中，可能會有非常多的數據

字段，或者對另外一個對象的引用，那個對象也包含很多數據字段。)

這個程序在表頭和表尾各插入三個鏈點，顯示插入后的鏈表。然后刪除頭兩個鏈結點，

再次顯示。

注意在表頭重復插入操作會顛倒鏈結點進入的順序，而在表尾的重復插入則保持鏈結

點進入的順序。

雙端鏈表類叫做FirstLastList。它有兩個項，first和last,一個指向鏈表中的第一個

鏈結點，另一個指向最后一個鏈結點。如果鏈表中只有一個鏈結點，first和last就都

指向它，如果沒有鏈結點，兩者都為Null值。

這個類有一個新的方法insertLast(),這個方法在表尾插入一個新的鏈結點。這個過

程首先改變last.next,使其指向新生成的鏈結點，然后改變last,使其指向新的鏈結

點。

插入和刪除方法和普通鏈表的相應部分類似。然而，兩個插入方法都要考慮一種特殊

情況，即插入前鏈表是空的。如果isEmpty。是真，那么insertFirst()必須把last指向

新的鏈結點，insertLast。也必須把first指向新的鏈結點。

如果用insertFirst。方法實現在表頭插入，first就指向新的鏈結點，用insertLast。方

法實現在表尾插入，last就指向新的鏈結點。如果鏈表只有一個鏈結點，那么多表頭

刪除也是一種特殊情況：last必須被賦值為null值。

不幸的是，用雙端鏈表也不能有助于刪除最后一個鏈結點，因為沒有一個引用指向倒

數第二個鏈結點。如果最后一個鏈結點被刪除，倒數第二個鏈結點的Next字段應該

變成Null值。為了方便的刪除最后一個鏈結點，需要一個雙向鏈表。(當然，也可以

遍歷整個鏈表找到最后一個鏈結點，但是那樣做效率不是很高。)

有序鏈表

在有序鏈表中，數據是按照關鍵值有序排列的。有序鏈表的刪除常常是只限于刪除在

鏈表頭部的最小鏈結點。不過，有時也用Find()方法和Delete。方法在整個鏈表中搜

索某一特定點。

一般，在大多數需要使用有序數組的場合也可以使用有序鏈表。有序鏈表優于有序數

組的地方是插入的速度，另外鏈表可以擴展到全部有效的使用內存，而數組只能局限

于一個固定的大小中。但是，有序鏈表實現起來比有序數組更困難一些。

后而將看到一個有序鏈表的應用：為數據排序。有序鏈表也可以用于實現優先級隊列，

盡管堆是更常用的實現方法。

在有序鏈表中插入一個數據項的Java代碼

為了在一個有序鏈表中插入數據項，算法必須首先搜索鏈表，直到找到合適的位置：

它恰好在第一個比它大的數據項的前面。

當算法找到了要插入的位置，用通常的方式插入數據項：把新鏈結點的Next字段指

向下一個鏈結點，然后把前一個鏈結點的Next字段改為指向新的鏈結點。然而，需

要考慮一些特殊情況：鏈結點有可以插在表頭，或者插在表尾。看一下這段代碼：

Publicvoidinsert(longkey){

LinknewLink=newLink(key);

Linkprevious=null;

Linkcurrent=first;

While(current!=null&&key>current.dData){

Previous=current;

Current=current.next;

)

lf(previous==null)

First=newLink;

Else

Previous.next=newLink;

newLink.next=current;

)

在鏈表上移動時，需要用一個previous引用，這樣才能把前一個鏈結點的Next字段

指向新的鏈結點。創建新鏈結點后，把current變量設為first,準備搜索正確的插入

點。這時也把previous設為Null值，這步操作很重要，因為后面要用這個Null值判

斷是否仍在表頭。

While循環和以前用來搜索插入點的代碼類似，但是有一個附加的條件。如果當前檢

查的鏈結點的關鍵值不再小于待插入的鏈結點的關鍵值，則循環結束；這是最常見的

情況，即新關鍵值插在鏈表中部的某個地方。

然而，如果current為Null值，while循環也會停止。這種情況發生在表尾，或者鏈

表為空時。

如果current在表頭或者鏈表為空，previous將為Null值；所以讓first指向新的鏈結

點。否則current處在鏈表中部或結尾，就使previous的next字段指向新的鏈結點。

不論哪種情況、都讓新鏈結點的Next字段指向current。如果在表尾，current為Nu

II值，則新鏈結點的Next字段也本應該設為這個值(Null)。

下面是有序鏈表的程序

SortedList.java程序實現了一個SortedList類，它擁有insert()^remove。和display

List()方法。只有insert。方法與無序鏈表中的insert。方法不同。

package有序鏈表;

classLink{

publiclongdData;

publicLinknext;

publicLink(longdd){

dData=dd;

)

//................

publicvoiddisplayLink(){

System.out.print(dData+"");

)

)

llllllllllllllllllllllllllllllllllllllll

classSortedList{

privateLinkfirst;

//................

publicSortedList(){

first=null;

)

//................

publicbooleanisEmpty(){

return(first==null);

)

//................

publicvoidinsert(longkey){

LinknewLink=newLink(key);

Linkprevious=null;

Linkcurrent=first;

while(current!=null&&key>current.dData){

previous=current;

current=current.next;

)

if(previous==null)

first=newLink;

else

previous.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.displayLink();

current=current.next;

)

System.out.println(,n,);

)

)

publicclassSortedLinkApp{

publicstaticvoidmain(String[]args){

SortedListtheSortedList=newSortedList();

theSortedList.insert(20);

theSortedList.insert(40);

theSortedList.displayList();

theSortedList.insert(10);

theSortedList.insert(30);

theSortedList.insert(50);

theSortedList.displayList();

theSortedList.remove();

theSortedList.displayList();

System.exit(O);

}

)

在Main。方法中，插入值為20和40的兩個鏈結點。然后再插入三個鏈結點，分別

是10、30和50。這三個值分別插在表頭、表中和表尾。這說明insert。方法正確地

處理了特殊情況。最后刪除了一個鏈結點，表現出刪除操作總是從表頭進行。每一步

變化后，都顯示整個鏈表。

雙向鏈表

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針、分別指向

直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪

問它的前驅結點和后繼結點。一般我們都構造雙向循環鏈表。

/*線性表的雙向鏈表存儲結構*/

typedefstructDuLNode

(

ElemTypedata;

structDuLNode*prior,*next;

}DuLNode,*DuLinkList;

/*帶頭結點的雙向循環鏈表的基本操作(14個)*/

voidlnitList(DuLinkList*L)

{/*產生空的雙向循環鏈表L7

*L=(DuLinkList)malloc(sizeof(DuLNode));

if(*L)

(*L)->next=(*L)->prior=*L;

else

exit(OVERFLOW);

)

voidDestroyList(DuLinkList*L)

{/*操作結果：銷毀雙向循環鏈表L*/

DuLinkListq,p=(*L)->next;/*p指向第一個結點*/

while(p!=*L)/*p沒到表頭*/

(

q=p->next;

free(p);

p=q;

)

free(*L);

*L=NULL;

)

voidClearList(DuLinkListL)/*不改變L*/

{/*初始條件：L已存在。操作結果：將L重置為空表7

DuLinkListq,p=L->next;/*p指向第一個結點*1

while(p!=L)/*p沒到表頭*/

{

q=p->next;

free(p);

p=q;

)

L->next=L->prior=L;/*頭結點的兩個指針域均指向自身*/

}

StatusListEmpty(DuLinkListL)

{/*初始條件：線性表L已存在。操作結果：若L為空表，則返回TRUE,否則

返回FALSE*/

if(L->next==L&&L->prior==L)

returnTRUE;

else

returnFALSE;

)

intListLength(DuLinkListL)

{/*初始條件：L已存在。操作結果：返回L中數據元素個數7

inti=0;

DuLinkListp=L->next;/*p指向第一個結點*/

while(p!=L)/*p沒到表頭*/

(

i++；

p=p->next;

)

returni;

)

StatusGetElem(DuLinkListL,inti,ElemType*e)

{/*當第i個元素存在時，其值賦給e并返回OK,否則返回ERROR7

intj=1;/*j為計數器*/

DuLinkListp=L->next;/*p指向第一個結點*/

while(p!=L&&jnext;

j++；

)

if(p==L||j>i)/*第i個元素不存在*/

returnERROR;

*e=p->data;/*取第i個元素*/

returnOK;

)

intLocateElem(DuLinkListL,ElemTypee,Status(*compare)(ElemType,Elem

Type))

{I*初始條件：L已存在，compare。是數據元素判定函數7

/*操作結果：返回L中第1個與e滿足關系compare。的數據元素的位序。7

/*若這樣的數據元素不存在，則返回值為0*/

inti=0;

DuLinkListp=L->next;/*p指向第1個元素*/

while(p!=L)

(

i++；

if(compare(p->data,e))/*找到這樣的數據元素7

returni;

p=p->next;

)

return0;

)

StatusPriorElem(DuLinkListL,ElemTypecur_e,ElemType*pre_e)

{/*操作結果：若cur_e是L的數據元素，且不是第一個，則用pre_e返回它的

前驅，*/

/*否則操作失敗，pre_e無定義*/

DuLinkListp=L->next->next;/*p指向第2個元素*/

while(p!=L)/*p沒到表頭*/

(

if(p->data==cur_e)

(

*pre_e=p->prior->data;

returnTRUE;

)

p=p->next;

)

returnFALSE;

)

StatusNextElem(DuLinkListL,ElemTypecur_e,ElemType*next_e)

{I*操作結果：若cur_e是L的數據元素，且不是最后一個，則用next_e返回

它的后繼，*/

/*否則操作失敗，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,返回頭結點的地址。若第i

個元素不存在，*/

/*返回NULL*/

intj;

DuLinkListp=L;I*p指向頭結點*/

if(i<O||i>ListLength(L))/*i值不合法*/

returnNULL;

for(j=1;j<=i;j++)

p=p->next;

returnp;

)

StatusListlnsert(DuLinkListL,inti,ElemTypee)

{/*在帶頭結點的雙鏈循環線性表L中第i個位置之前插入元素e,i的合法值為

伍區表長+1*/

/*改進算法2.18,否則無法在第表長+1個結點之前插入元素*/

DuLinkListp,s;

if(i<1||i>ListLength(L)+1)/*i值不合法*/

returnERROR;

p=GetElemP(L,i-1);/*在L中確定第i個元素前驅的位置指針p*/

if(!p)/*p=NULL,即第i個元素的前驅不存在(設頭結點為第1個元素的前驅)*/

returnERROR;

s=(DuLinkList)malloc(sizeof(DuLNode));

if(ls)

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)

{/*刪除帶頭結點的雙鏈循環線性表L的第i個元素，i的合法值為1WV表長*/

DuLinkListp;

if(i<1)/*i值不合法7

returnERROR;

p=GetElemP(L,i);/*在L中確定第i個元素的位置指針p7

if(!p)I*p=NULL,即第i個元素不存在7

returnERROR;

*e=p->data;

p->prior->next=p->next;

p->next->prior=p->prior;

free(p);

returnOK;

)

voidListTraverse(DuLinkListL,void(*visit)(ElemType))

{r由雙鏈循環線性表L的頭結點出發，正序對每個數據元素調用函數visit。*

/

DuLinkListp=L->next;/*p指向頭結點*/

while(p!=L)

(

visit(p->data);

p=p->next;

}

printf(”\n");

)

voidListTraverseBack(DuLinkListL,void(*visit)(ElemType))

{/*由雙鏈循環線性表L的頭結點出發，逆序對每個數據元素調用函數visit。。

另加*/

DuLinkListp=L->prior;/*p指向尾結點*/

while(p!=L)

visit(p->data);

p=p->prior;

)

printf("\n");

)

迭代器

迭代器是一種對象，它能夠用來遍歷STL容器中的部分或全部元素，每個迭代器對

象代表容器中的確定的地址。迭代器修改了常規指針的接口，所謂迭代器是一種概念

上的抽象：那些行為上象迭代器的東西都可以叫做迭代器。然而迭代器有很多不同的

能力，它可以把抽象容器和通用算法有機的統一起來。

迭代器提供一些基本操作符：*、++、==、！=、=。這些操作和C/C++“操作array元

素”時的指針接口一致。不同之處在于，迭代器是個所謂的smartpointers,具有遍歷

復雜數據結構的能力。其下層運行機制取決于其所遍歷的數據結構。因此，每一種容

器型別都必須提供自己的迭代器。事實上每一種容器都將其迭代器以嵌套的方式定義

于內部。因此各種迭代器的接口相同，型別卻不同。這直接導出了泛型程序設計的概

念：所有操作行為都使用相同接口，雖然它們的型別不同。

功能

迭代器使開發人員能夠在類或結構中支持foreach迭代，而不必整個實現lEnumerab

Ie或者lEnumerator接口。只需提供一個迭代器，即可遍歷類中的數據結構。當編譯

器檢測到迭代器時，將自動生成lEnumerable接口或者lEnumerator接口的Current,

MoveNext和Dispose方法。

特點

1.迭代器是可以返回相同類型值的有序序列的一段代碼；

2.迭代器可用作方法、運算符或get訪問器的代碼體；

3.迭代器代碼使用yieldreturn語句依次返回每個元素，yieldbreak將終止迭代；

4.可以在類中實現多個迭代器，每個迭代器都必須像任何類成員一樣有惟一的名

稱，并且可以在foreach語句中被客戶端代碼調用；

5.迭代器的返回類型必須為(Enumerable和lEnumerator中的任意一種;

6.迭代器是產生值的有序序列的一個語句塊，不同于有一個或多個yield語句存

在的常規語句塊；

7.迭代器不是一種成員，它只是實現函數成員的方式，理解這一點是很重要的，

一個通過迭代器實現的成員，可以被其他可能或不可能通過迭代器實現的成員覆蓋和

重載；

8.迭代器塊在C#語法中不是獨特的元素，它們在幾個方面受到限制，并且主要

作用在函數成員聲明的語義上，它們在語法上只是語句塊而已；

四、遞歸

遞歸是函數調用自身的一種特殊的編程技術，其應用主要在以下幾個方面：

階乘

在java當中的基本形式是：Publicvoidmothed(intn){〃當滿足某條件時：

Mothed(n-1)；

)

遞歸二分查找

Java二分查找實現，歡迎大家提出交流意見.

/**

*名稱:BinarySearch

*功能:實現了折半查找(二分查找)的遞歸和非遞歸算法.

*說明：

*1、要求所查找的數組已有序,并且其中元素已實現ComparablevT>接口,如

Integer、String等.

*2、非遞歸查找使用search。;,遞歸查找使用searchRecursively();

*

*本程序僅供編程學習參考

★

*@autho匚Winty

*@date:2008-8-11

*@email:[email]wintys@[/email]

*/

classBinarySearch<TextendsComparable<T?{

privateT[]data;〃要排序的數據

publicBinarySearch(T[]data){

this.data=data;

publicintsearch(Tkey){

intlow;

inthigh;

intmid;

if(data==null)

return-1;

low=0;

high=data.length-1;

while(low<=high){

mid=(low+high)/2;

System.out.println("mid"+mid+"midvalue:"+data[mid]);

///

if(pareTo(data[mid])<0){

high=mid-1;

}elseif(pareTo(data[mid])>0){

low=mid+1;

}elseif(pareTo(data[mid])==0){

returnmid;

}

)

return-1;

)

privateintdoSearchRecursively(intlow,inthigh,Tkey){

intmid;

intresult;

if(low<=high){

mid=(low+high)/2;

result=pareTo(data[mid]);

System.out.printlnC'mid"+mid+"midvalue:"+data[mid]);

///

if(result<0){

returndoSearchRecursively(low,mid-1,key);

}elseif(result>0){

returndoSearchRecursively(mid+1,high,key);

}elseif(result==0){

returnmid;

)

)

return-1;

)

publicintsearchRecursively(Tkey){

if(data==null)return-1;

returndoSearchRecursively(0,data.length-1,key);

)

publicstaticvoidmain(String[]args){

lnteger[]data={1,4,5,8,15,33,48,77,96);

BinarySearch<lnteger>binSearch=newBinarySearch<lnte