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

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

一、數(shù)組于簡(jiǎn)單排序...............................................................1

二、棧與隊(duì)列....................................................................4

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

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

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

六、高級(jí)排序...................................................................25

七、二叉樹(shù).....................................................................25

八、紅一黑樹(shù)...................................................................26

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

十、帶權(quán)圖.....................................................................40

一、數(shù)組于簡(jiǎn)單排序

數(shù)組

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

被定義為任何類型，可以是一維或多維。數(shù)組中的一個(gè)特別要素是通過(guò)下標(biāo)來(lái)訪

問(wèn)它。數(shù)組提供了一種將有聯(lián)系的信息分組的便利方法。

一維數(shù)組

一維數(shù)組(one-dimensionalarray)實(shí)質(zhì)上是相同類型變量列表。要?jiǎng)?chuàng)建一

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

typevar-name[];

獲得一個(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ù)組的初始化(arrayinitializer)就是包括在花括號(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)(在這方面，

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

多維數(shù)組

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

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

有一些微妙的差別。定義多維數(shù)組變量要將每個(gè)維數(shù)放在它們各自的方括號(hào)中。

例如，下面語(yǔ)句定義了一個(gè)名為twoD的二維數(shù)組變量。

inttwoD[][]=newint⑷⑸；

簡(jiǎn)單排序

簡(jiǎn)單排序中包括了：冒泡排序、選擇排序、插入排序；

L冒泡排序的思想：

假設(shè)有N個(gè)數(shù)據(jù)需要排序，則從第0個(gè)數(shù)開(kāi)始，依次比較第0和第1個(gè)數(shù)據(jù)，

如果第。個(gè)大于第1個(gè)則兩者交換，否則什么動(dòng)作都不做，繼續(xù)比較第1個(gè)第2

個(gè)…，這樣依次類推，直至所有數(shù)據(jù)都“冒泡”到數(shù)據(jù)頂上。

冒泡排序的的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);

}

}

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

條件被稱為算法的不變性，如果不變性不為真了，則標(biāo)記出錯(cuò)了；

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

2.選擇排序的思想：

假設(shè)有N條數(shù)據(jù)，則暫且標(biāo)記第0個(gè)數(shù)據(jù)為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代碼：

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；選擇排序與冒泡排序比

較，比較次數(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的值，則后移，直到遇到第一個(gè)比temp

小的值，在其下一個(gè)位置插入；

插入排序的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,復(fù)制N*N/4；插入排序在隨機(jī)數(shù)的

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

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

二、棧與隊(duì)列

1、棧的定義

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

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

(2)當(dāng)表中沒(méi)有元素時(shí)稱為空棧。

(3)棧為后進(jìn)先出(LastInFirstOut)的線性表，簡(jiǎn)稱為L(zhǎng)IFO表。

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

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

要到最后才能刪除。

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

alo

2、棧的基本運(yùn)算

(1)InitStack(S)

構(gòu)造一個(gè)空棧So

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

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

(6)StackTop(S)

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

隊(duì)列的定義及基本運(yùn)算

1、定義

隊(duì)列（Queue）是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的運(yùn)算

受限的線性表

出隊(duì)--2…

r

隊(duì)頭隊(duì)尾

隊(duì)列示意圖

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

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

（3）當(dāng)隊(duì)列中沒(méi)有元素時(shí)稱為空隊(duì)列。

（4）隊(duì)列亦稱作先進(jìn)先出（FirstInFirstOut）的線性表，簡(jiǎn)稱為FIFO

表。

隊(duì)列的修改是依先進(jìn)先出的原則進(jìn)行的。新來(lái)的成員總是加入隊(duì)尾（即

不允許“加塞”），每次離開(kāi)的成員總是隊(duì)列頭上的（不允許中途離隊(duì)），即當(dāng)前

〃最老的〃成員離隊(duì)。

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

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

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非滿，則將元素x插入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)的引用

單鏈表

用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。

以元素(數(shù)據(jù)元素的映象)

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

=結(jié)點(diǎn)

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

以“結(jié)點(diǎn)的序列”表示線性表

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

單鏈表是一種順序存取的結(jié)構(gòu)，為找第i個(gè)數(shù)據(jù)元素，必須先找到第i-1個(gè)數(shù)

據(jù)元素。

因此，查找第i個(gè)數(shù)據(jù)元素的基本操作為：移動(dòng)指針，比較j和i

1、鏈接存儲(chǔ)方法

鏈接方式存儲(chǔ)的線性表簡(jiǎn)稱為鏈表(LinkedList)?

鏈表的具體存儲(chǔ)表示為：

①用一組任意的存儲(chǔ)單元來(lái)存放線性表的結(jié)點(diǎn)(這組存儲(chǔ)單元既可以是連續(xù)的，

也可以是不連續(xù)的)

②鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏

輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址(或位置)信

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

注意：

鏈?zhǔn)酱鎯?chǔ)是最常用的存儲(chǔ)方式之一，它不僅可用來(lái)表示線性表，而且可用來(lái)表示

各種非線性的數(shù)據(jù)結(jié)構(gòu)。

2、鏈表的結(jié)點(diǎn)結(jié)構(gòu)

|data|next|

data域--存放結(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è)鏈域的鏈表稱為單鏈表(SingleLinkedList),

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

3、頭指針head和終端結(jié)點(diǎn)指針域的表示

單鏈表中每個(gè)結(jié)點(diǎn)的存儲(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)榭?，即NULLo

4、單鏈表的一般圖示法

由于我們常常只注重結(jié)點(diǎn)間的邏輯順序，不關(guān)心每個(gè)結(jié)點(diǎn)的實(shí)際位置，可以用箭

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

以表示為下圖形式。

5、單鏈表類型描述

typedefcharDataType;〃假設(shè)結(jié)點(diǎn)的數(shù)據(jù)域類型為字符

typedefstructnode{〃結(jié)點(diǎn)類型定義

DataTypedata;〃結(jié)點(diǎn)的數(shù)據(jù)域

structnode*next;〃結(jié)點(diǎn)的指針域

JListNode

typedefListNode*LinkList;

ListNode*p;

LinkListhead;

注意：

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

上更明確)

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

③ListNode類型的指針變量p表示它是指向某一結(jié)點(diǎn)的指針

6、指針變量和結(jié)點(diǎn)變量

|指針變量|結(jié)點(diǎn)變量|

定義|在變量說(shuō)明部分顯式定義|在程序執(zhí)行時(shí)，通過(guò)標(biāo)準(zhǔn)|

||函數(shù)malloc生成|

取值|非空時(shí)，存放某類型結(jié)點(diǎn)|實(shí)際存放結(jié)點(diǎn)各域內(nèi)容|

|的地址||

操作方式|通過(guò)指針變量名訪問(wèn)|通過(guò)指針生成、訪問(wèn)和釋放|

①生成結(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)變量*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)，然后修改其指向后繼的指針。

雙端鏈表

雙端鏈表與傳統(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è)雙端鏈表的例子。

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

)

)

為了簡(jiǎn)單起見(jiàn)，在這個(gè)程序中，把每個(gè)鏈結(jié)點(diǎn)中的數(shù)據(jù)字段個(gè)數(shù)從兩個(gè)壓縮到一個(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(),這個(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)，那么多表頭

刪除也是一種特殊情況：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ù)

組的地方是插入的速度，另外鏈表可以擴(kuò)展到全部有效的使用內(nèi)存，而數(shù)組只能局限

于一個(gè)固定的大小中。但是，有序鏈表實(shí)現(xiàn)起來(lái)比有序數(shù)組更困難一些。

后而將看到一個(gè)有序鏈表的應(yīng)用：為數(shù)據(jù)排序。有序鏈表也可以用于實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，

盡管堆是更常用的實(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)的Next字段指

向下一個(gè)鏈結(jié)點(diǎn)，然后把前一個(gè)鏈結(jié)點(diǎn)的Next字段改為指向新的鏈結(jié)點(diǎn)。然而，需

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

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;

)

在鏈表上移動(dòng)時(shí)，需要用一個(gè)previous引用，這樣才能把前一個(gè)鏈結(jié)點(diǎn)的Next字段

指向新的鏈結(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é)

點(diǎn)。否則current處在鏈表中部或結(jié)尾，就使previous的next字段指向新的鏈結(jié)點(diǎn)。

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

II值，則新鏈結(jié)點(diǎn)的Next字段也本應(yīng)該設(shè)為這個(gè)值(Null)。

下面是有序鏈表的程序

SortedList.java程序?qū)崿F(xiàn)了一個(gè)SortedList類，它擁有insert()^remove。和display

List()方法。只有insert。方法與無(wú)序鏈表中的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的兩個(gè)鏈結(jié)點(diǎn)。然后再插入三個(gè)鏈結(jié)點(diǎn)，分別

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

處理了特殊情況。最后刪除了一個(gè)鏈結(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)*/

typedefstructDuLNode

(

ElemTypedata;

structDuLNode*prior,*next;

}DuLNode,*DuLinkList;

/*帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表的基本操作(14個(gè))*/

voidlnitList(DuLinkList*L)

{/*產(chǎn)生空的雙向循環(huán)鏈表L7

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

if(*L)

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

else

exit(OVERFLOW);

)

voidDestroyList(DuLinkList*L)

{/*操作結(jié)果：銷毀雙向循環(huán)鏈表L*/

DuLinkListq,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;

)

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

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

DuLinkListq,p=L->next;/*p指向第一個(gè)結(jié)點(diǎn)*1

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

{

q=p->next;

free(p);

p=q;

)

L->next=L->prior=L;/*頭結(jié)點(diǎn)的兩個(gè)指針域均指向自身*/

}

StatusListEmpty(DuLinkListL)

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

返回FALSE*/

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

returnTRUE;

else

returnFALSE;

)

intListLength(DuLinkListL)

{/*初始條件：L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù)7

inti=0;

DuLinkListp=L->next;/*p指向第一個(gè)結(jié)點(diǎn)*/

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

(

i++；

p=p->next;

)

returni;

)

StatusGetElem(DuLinkListL,inti,ElemType*e)

{/*當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給e并返回OK,否則返回ERROR7

intj=1;/*j為計(jì)數(shù)器*/

DuLinkListp=L->next;/*p指向第一個(gè)結(jié)點(diǎn)*/

while(p!=L&&jnext;

j++；

)

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

returnERROR;

*e=p->data;/*取第i個(gè)元素*/

returnOK;

)

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

Type))

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

/*操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare。的數(shù)據(jù)元素的位序。7

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

inti=0;

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

while(p!=L)

(

i++；

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

returni;

p=p->next;

)

return0;

)

StatusPriorElem(DuLinkListL,ElemTypecur_e,ElemType*pre_e)

{/*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它的

前驅(qū)，*/

/*否則操作失敗，pre_e無(wú)定義*/

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

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

(

if(p->data==cur_e)

(

*pre_e=p->prior->data;

returnTRUE;

)

p=p->next;

)

returnFALSE;

)

StatusNextElem(DuLinkListL,ElemTypecur_e,ElemType*next_e)

{I*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回

它的后繼，*/

/*否則操作失敗，next_e無(wú)定義*/

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

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

{

if(p->prior->data==cur_e)

(

*next_e=p->data;

returnTRUE;

)

p=p->next;

)

returnFALSE;

)

DuLinkListGetElemP(DuLinkListL,inti)/*另加*/

{/*在雙向鏈表L中返回第i個(gè)元素的地址。i為0,返回頭結(jié)點(diǎn)的地址。若第i

個(gè)元素不存在，*/

/*返回NULL*/

intj;

DuLinkListp=L;I*p指向頭結(jié)點(diǎn)*/

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

returnNULL;

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

p=p->next;

returnp;

)

StatusListlnsert(DuLinkListL,inti,ElemTypee)

{/*在帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表L中第i個(gè)位置之前插入元素e,i的合法值為

伍區(qū)表長(zhǎng)+1*/

/*改進(jìn)算法2.18,否則無(wú)法在第表長(zhǎng)+1個(gè)結(jié)點(diǎn)之前插入元素*/

DuLinkListp,s;

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

returnERROR;

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

if(!p)/*p=NULL,即第i個(gè)元素的前驅(qū)不存在(設(shè)頭結(jié)點(diǎn)為第1個(gè)元素的前驅(qū))*/

returnERROR;

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

if(ls)

returnOVERFLOW;

s->data=e;

s->prior=p;/*在第i-1個(gè)元素之后插入*/

s->next=p->next;

p->next->prior=s;

p->next=s;

returnOK;

)

StatusListDelete(DuLinkListL,inti.ElemType*e)

{/*刪除帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表L的第i個(gè)元素，i的合法值為1WV表長(zhǎng)*/

DuLinkListp;

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

returnERROR;

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

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

returnERROR;

*e=p->data;

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

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

free(p);

returnOK;

)

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

{r由雙鏈循環(huán)線性表L的頭結(jié)點(diǎn)出發(fā)，正序?qū)γ總€(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit。*

/

DuLinkListp=L->next;/*p指向頭結(jié)點(diǎn)*/

while(p!=L)

(

visit(p->data);

p=p->next;

}

printf(”\n");

)

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

{/*由雙鏈循環(huán)線性表L的頭結(jié)點(diǎn)出發(fā)，逆序?qū)γ總€(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit。。

另加*/

DuLinkListp=L->prior;/*p指向尾結(jié)點(diǎn)*/

while(p!=L)

visit(p->data);

p=p->prior;

)

printf("\n");

)

迭代器

迭代器是一種對(duì)象，它能夠用來(lái)遍歷STL容器中的部分或全部元素，每個(gè)迭代器對(duì)

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

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

能力，它可以把抽象容器和通用算法有機(jī)的統(tǒng)一起來(lái)。

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

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

復(fù)雜數(shù)據(jù)結(jié)構(gòu)的能力。其下層運(yùn)行機(jī)制取決于其所遍歷的數(shù)據(jù)結(jié)構(gòu)。因此，每一種容

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

于內(nèi)部。因此各種迭代器的接口相同，型別卻不同。這直接導(dǎo)出了泛型程序設(shè)計(jì)的概

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

功能

迭代器使開(kāi)發(fā)人員能夠在類或結(jié)構(gòu)中支持foreach迭代，而不必整個(gè)實(shí)現(xiàn)lEnumerab

Ie或者lEnumerator接口。只需提供一個(gè)迭代器，即可遍歷類中的數(shù)據(jù)結(jié)構(gòu)。當(dāng)編譯

器檢測(cè)到迭代器時(shí)，將自動(dòng)生成lEnumerable接口或者lEnumerator接口的Current,

MoveNext和Dispose方法。

特點(diǎn)

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

2.迭代器可用作方法、運(yùn)算符或get訪問(wèn)器的代碼體；

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

4.可以在類中實(shí)現(xiàn)多個(gè)迭代器，每個(gè)迭代器都必須像任何類成員一樣有惟一的名

稱，并且可以在foreach語(yǔ)句中被客戶端代碼調(diào)用；

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

6.迭代器是產(chǎn)生值的有序序列的一個(gè)語(yǔ)句塊，不同于有一個(gè)或多個(gè)yield語(yǔ)句存

在的常規(guī)語(yǔ)句塊；

7.迭代器不是一種成員，它只是實(shí)現(xiàn)函數(shù)成員的方式，理解這一點(diǎn)是很重要的，

一個(gè)通過(guò)迭代器實(shí)現(xiàn)的成員，可以被其他可能或不可能通過(guò)迭代器實(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)中的基本形式是：Publicvoidmothed(intn){〃當(dāng)滿足某條件時(shí)：

Mothed(n-1)；

)

遞歸二分查找

Java二分查找實(shí)現(xiàn)，歡迎大家提出交流意見(jiàn).

/**

*名稱:BinarySearch

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

*說(shuō)明：

*1、要求所查找的數(shù)組已有序,并且其中元素已實(shí)現(xiàn)ComparablevT>接口,如

Integer、String等.

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

*

*本程序僅供編程學(xué)習(xí)參考

★

*@autho匚Winty

*@date:2008-8-11

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

*/

classBinarySearch<TextendsComparable<T?{

privateT[]data;〃要排序的數(shù)據(jù)

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