《數(shù)據(jù)結(jié)構(gòu)JAVA語(yǔ)言版》課件 第1章緒論

數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE——Java描述1.1數(shù)據(jù)結(jié)構(gòu)的地位1.2基本概念和術(shù)語(yǔ)

1.2.1基本概念1.數(shù)據(jù)（data）：是對(duì)客觀事物的符號(hào)表示，所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的總稱。2.數(shù)據(jù)元素（dataelement）：數(shù)據(jù)元素是表示現(xiàn)實(shí)世界中一個(gè)實(shí)體的一組數(shù)據(jù)，是數(shù)據(jù)結(jié)構(gòu)的基本組成單位。一個(gè)數(shù)據(jù)元素可由一個(gè)或若干個(gè)數(shù)據(jù)項(xiàng)（dataItem）組成。3.數(shù)據(jù)對(duì)象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合。4.數(shù)據(jù)結(jié)構(gòu)（Data_Structure）相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。1.2.2數(shù)據(jù)結(jié)構(gòu)的種類1、集合結(jié)構(gòu)。在集合結(jié)構(gòu)中，數(shù)據(jù)元素間的關(guān)系除了“屬于同一個(gè)集合”外，別無(wú)任何關(guān)系。

1.2.2數(shù)據(jù)結(jié)構(gòu)的種類2、線性結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系。

1.2.2數(shù)據(jù)結(jié)構(gòu)的種類3、樹型結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。1.2.2數(shù)據(jù)結(jié)構(gòu)的種類4、圖形結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系，圖形結(jié)構(gòu)也稱作網(wǎng)狀結(jié)構(gòu)。1.2.3數(shù)據(jù)結(jié)構(gòu)的數(shù)學(xué)定義數(shù)據(jù)結(jié)構(gòu)的數(shù)學(xué)定義為：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組：

Data-Structure=(D，S)其中：D是數(shù)據(jù)元素的集合，S是數(shù)據(jù)元素之間關(guān)系的集合。例:復(fù)數(shù)a+bi的數(shù)據(jù)結(jié)構(gòu)定義如下：

Complex=(C，R)其中，D部分用C表示，C是含兩個(gè)實(shí)數(shù)的集合﹛a，b﹜；S部分用R表示，R={〈a，b〉}，〈a，b〉表示a和b存在一種有序關(guān)系，a表示復(fù)數(shù)的實(shí)部，b表示復(fù)數(shù)的虛部，二者不能互換。1.2.4數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

本課程是在高級(jí)語(yǔ)言Java的層次上討論數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中內(nèi)存中的存儲(chǔ)，主要研究的是數(shù)據(jù)元素以及它們之間的關(guān)系在Java虛擬處理器中的表示，可以稱為虛擬存儲(chǔ)結(jié)構(gòu)。1、數(shù)據(jù)元素的表示單個(gè)數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)元素可以利用java語(yǔ)言固有的基本數(shù)據(jù)類型（8種）來(lái)表示。

例如：復(fù)數(shù)數(shù)據(jù)結(jié)構(gòu)Complex=(C，R)中的C=﹛a，b﹜，數(shù)據(jù)元素a和b是實(shí)數(shù)，可用Java語(yǔ)言中的固有的雙精度浮點(diǎn)型double表示。多個(gè)數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)元素可以利用Java語(yǔ)言中的自己定義的類表示。例如：學(xué)生實(shí)體的數(shù)據(jù)元素可由學(xué)號(hào)、姓名、所在系、性別、出生日期、入學(xué)成績(jī)等數(shù)據(jù)項(xiàng)組成，在Java語(yǔ)言中用自己定義的類表示如下：classStudent{

StringNO;//String位于java.lang子類庫(kù)中

StringName;

StringDepartment;

charSex;

DateBirthDate;//Date位于java.util子類庫(kù)中

doubleScore;}1.2.4數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)2數(shù)據(jù)元素之間關(guān)系的表示數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)內(nèi)存中有兩種不同的表示方法：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。順序存儲(chǔ)是把數(shù)據(jù)元素按一定的規(guī)則存放在一組編號(hào)連續(xù)的存儲(chǔ)單元中，通過(guò)元素在內(nèi)存中的存儲(chǔ)位置來(lái)體現(xiàn)數(shù)據(jù)元素之間的邏輯關(guān)系，邏輯上相鄰的數(shù)據(jù)元素在內(nèi)存中的存儲(chǔ)位置也相鄰。abcd

例如：線性數(shù)據(jù)結(jié)構(gòu)（‘a(chǎn)’，‘b’，‘c’，‘d’）的順序存儲(chǔ)就是把數(shù)據(jù)元素‘a(chǎn)’、‘b’、‘c’、‘d’放在一組編號(hào)連續(xù)的存儲(chǔ)單元（1個(gè)存儲(chǔ)單元即1個(gè)字節(jié)）中，通過(guò)元素的存儲(chǔ)地址是否相鄰來(lái)表示數(shù)據(jù)元素在邏輯上是否相鄰。存儲(chǔ)單元編號(hào)存儲(chǔ)內(nèi)容

…0030a0032b0034c0036d

…在高級(jí)語(yǔ)言Java的層次上討論時(shí)，線性數(shù)據(jù)結(jié)構(gòu)（‘a(chǎn)’，‘b’，‘c’，‘d’）的數(shù)據(jù)元素是char型，每個(gè)數(shù)據(jù)元素在占用2個(gè)字節(jié)的內(nèi)存空間。。在Java語(yǔ)言中，存儲(chǔ)單元的編號(hào)對(duì)用戶透明，在Java虛擬處理器中線性數(shù)據(jù)結(jié)構(gòu)的順序存儲(chǔ)就是線性數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素依次存放到一維數(shù)組中，因?yàn)镴ava語(yǔ)言中一維數(shù)組占用的就是一組編號(hào)連續(xù)的內(nèi)存單元。1.2.4數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)2數(shù)據(jù)元素之間關(guān)系的表示鏈?zhǔn)酱鎯?chǔ)：鏈?zhǔn)酱鎯?chǔ)時(shí)數(shù)據(jù)元素不必存放在一組編號(hào)連續(xù)的存儲(chǔ)單元中，把數(shù)據(jù)元素后附加一個(gè)地址域，通過(guò)指示相鄰元素的存儲(chǔ)地址來(lái)體現(xiàn)數(shù)據(jù)元素的邏輯關(guān)系，邏輯上相鄰的數(shù)據(jù)元素物理存儲(chǔ)位置不一定相鄰。線性數(shù)據(jù)結(jié)構(gòu)（‘a(chǎn)’，‘b’，‘c’，‘d’）的鏈?zhǔn)酱鎯?chǔ)是在把數(shù)據(jù)元素后面加一個(gè)地址域，通過(guò)指示相鄰元素的存儲(chǔ)地址來(lái)體現(xiàn)數(shù)據(jù)元素的邏輯關(guān)系，邏輯上相鄰的數(shù)據(jù)元素物理存儲(chǔ)位置上不一定相鄰。abcd

存儲(chǔ)單元編號(hào)存儲(chǔ)內(nèi)容

…0100b01020120……0120c01220160……0144a01460100……0160d0162NULL

…h(huán)eadd^cba前面已經(jīng)提及，在Java語(yǔ)言中，存儲(chǔ)單元的編號(hào)對(duì)用戶透明，在Java虛擬處理器中，把相鄰元素的存儲(chǔ)地址抽象為引用，在存儲(chǔ)結(jié)構(gòu)圖中用箭頭表示，整個(gè)存儲(chǔ)結(jié)構(gòu)像一條鏈條，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也是由此命名。1.2.5抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型：數(shù)據(jù)的邏輯結(jié)構(gòu)及定義在該邏輯結(jié)構(gòu)上的一組操作。

ADT={D,S,P}為什麼還要研究操作呢？因?yàn)獒槍?duì)不同的數(shù)據(jù)元素集合，定義于其上的操作也不一樣。以Java語(yǔ)言中的int,boolean數(shù)據(jù)類型為例：int數(shù)據(jù)類型，其數(shù)據(jù)元素集是-231～231-1區(qū)間的整數(shù)，定義在其上的操作是為加、減、乘、除和取模等算術(shù)運(yùn)算和大于、不等于、等于、小于等關(guān)系運(yùn)算。boolean數(shù)據(jù)類型，其數(shù)據(jù)元素集是{true，false}，定義在其上的操作是與、或、非等邏輯運(yùn)算。在后面的章節(jié)中，每研究一種數(shù)據(jù)結(jié)構(gòu)，都是從抽象數(shù)據(jù)類型開始，即先研究邏輯結(jié)構(gòu)及定義于其上的操作，邏輯結(jié)構(gòu)嚴(yán)格來(lái)說(shuō)屬于離散數(shù)學(xué)課程的學(xué)習(xí)內(nèi)容。1.2.5抽象數(shù)據(jù)類型對(duì)于使用數(shù)據(jù)類型的用戶而言，引入“數(shù)據(jù)類型”，實(shí)現(xiàn)了信息的隱蔽，即將一切用戶不必了解的細(xì)節(jié)都封裝在類型中。例如，Java編程用戶使用int數(shù)據(jù)類型時(shí)，既不需要了解int型整數(shù)在計(jì)算機(jī)的內(nèi)部是如何表示的，也不需要知道其操作是如何實(shí)現(xiàn)的，這些由Java語(yǔ)言的推出者關(guān)注實(shí)現(xiàn)。就int數(shù)據(jù)類型的“加”操作而言，Java編程用戶只需關(guān)注“加”的功能及它的數(shù)學(xué)意義，不必去關(guān)注其硬件的“位”操作如何進(jìn)行。

抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念，抽象的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。另外抽象數(shù)據(jù)類型的范疇更廣，它不再局限于各高級(jí)語(yǔ)言處理器中已定義并實(shí)現(xiàn)的數(shù)據(jù)類型，還包括用戶開發(fā)軟件系統(tǒng)時(shí)自己定義的數(shù)據(jù)類型。

為了提高軟件的復(fù)用率，在近代程序設(shè)計(jì)方法學(xué)中指出，一個(gè)軟件系統(tǒng)的框架應(yīng)建立在數(shù)據(jù)之上，而不是建立在操作之上。在構(gòu)成軟件系統(tǒng)的每個(gè)相對(duì)獨(dú)立的模塊上，定義一組數(shù)據(jù)和施于這組數(shù)據(jù)上的一組操作，并在模塊內(nèi)部給出這些數(shù)據(jù)的表示及操作的細(xì)節(jié)，而在模塊外部使用的只是抽象的操作。顯然，所定義的數(shù)據(jù)類型的抽象層次越高，含有該數(shù)據(jù)類型的軟件模塊的復(fù)用度也越高。1.3數(shù)學(xué)預(yù)備知識(shí)1.3.1集合1、集合的概念

集合是由一些確定的、彼此不同的成員或者元素構(gòu)成的一個(gè)整體。成員的個(gè)數(shù)稱為集合的基數(shù)。如果某集合的成員都屬于該集合，那麼某集合叫做該集合的子集

沒(méi)有元素的集合稱為空集，記作Φ。3是R的成員，記為：3∈R，6不是R的成員，記為：6?R。{3，4}是R的子集。2、集合的表示法

窮舉法：S＝{2，4，6，8，10}；

描述法：S＝{x|x是偶數(shù)，且0≤x≤10}。3、集合的特性確定性：任何一個(gè)對(duì)象都能被確切地判斷是集合中的元素或不是；互異性：集合中的元素不能重復(fù)；無(wú)序性：集合中元素與順序無(wú)關(guān)。

1.3.2常用的數(shù)學(xué)術(shù)語(yǔ)計(jì)量單位(Unit)：字節(jié)縮寫為“B”，位縮寫為“b”，千字節(jié)縮寫為“KB”，百萬(wàn)字節(jié)縮寫為縮寫為“MB”，十億字節(jié)縮寫為縮寫為“GB”，萬(wàn)億字節(jié)縮寫為“TB”，。階乘函數(shù)(FactorialFunction)：階乘函數(shù)n!是指從1到n之間所有整數(shù)的連乘，其中n為大于0的整數(shù)。因此，5!=1?2?3?4?5=120。特別地，0!=1。取下整和取上整(FloorandCeiling)：實(shí)數(shù)x的取下整函數(shù)(Floor)，返回不超過(guò)x的最大整數(shù)，例如Floor（5.5)=5；實(shí)數(shù)x的取上整函數(shù)(Ceiling)，返回不小于x的最小整數(shù)，Ceiling（

5.5)=6

。取模操作符（Modulus）：取模函數(shù)返回整除后的余數(shù),有時(shí)稱為求余，記為%,例如:5%3=2。1.3.3對(duì)數(shù)一般地，如果a(a＞0，a≠1)的b次冪等于N，就是ab=N，那么數(shù)b叫做以a為底N的對(duì)數(shù)，記作logaN=b，其中a叫做對(duì)數(shù)的底數(shù)，N叫做真數(shù)。

負(fù)數(shù)和零沒(méi)有對(duì)數(shù)。1.3.4遞歸如果一個(gè)算法直接調(diào)用自己或間接地調(diào)用自己，就稱這個(gè)算法是遞歸的(Recursive)。根據(jù)調(diào)用方式的不同，它分為直接遞歸和間接遞歸。直接遞歸調(diào)用就是在函數(shù)a（或過(guò)程）中直接引用（調(diào)用）函數(shù)a本身。間接遞歸調(diào)用就是在函數(shù)a（或過(guò)程）中調(diào)用另外一個(gè)函數(shù)b，而該函數(shù)b又引用（調(diào)用）了函數(shù)a。

1.3.4遞歸一個(gè)遞歸算法必須有兩個(gè)部分：初始部分(Basecase)和遞歸部分。初始情況只處理可以直接解決而不需要再次遞歸調(diào)用的簡(jiǎn)單輸入。遞歸部分包含對(duì)算法的一次或多次遞歸調(diào)用，每一次的調(diào)用參數(shù)都在某種程度上比原始調(diào)用參數(shù)更接近初始情況。

函數(shù)的遞歸調(diào)用可以理解為：通過(guò)一系列的自身調(diào)用，達(dá)到某一終止條件后，在按照調(diào)用路線逐步返回。遞歸是程序設(shè)計(jì)中強(qiáng)有力的工具，有很多數(shù)學(xué)函數(shù)時(shí)遞歸定義的。階乘函數(shù)，對(duì)n!作如下定義：

階乘函數(shù)的java語(yǔ)言實(shí)現(xiàn)如下：

public

static

double

fun(intn){

if(n=0)

return1;

else

return

fun(n-1)*n;}1.4算法和算法分析1.4.1算法1、定義算法（Algorithm）是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個(gè)或多個(gè)操作。算法的描述工具有自然語(yǔ)言、框圖、PAD圖、偽碼、程序設(shè)計(jì)語(yǔ)言等等。在Java程序設(shè)計(jì)語(yǔ)言中，算法一般用類的一個(gè)方法進(jìn)行描述，方法體內(nèi)的一條條語(yǔ)句就是對(duì)問(wèn)題求解步驟的一種描述。

1.4算法和算法分析1.4.1算法2、特性輸入

有輸入輸出有輸出(處理結(jié)果)確定性每步定義都是確切、無(wú)歧義的有窮性算法應(yīng)在執(zhí)行有窮步后結(jié)束有效性每一條運(yùn)算能有效的執(zhí)行

（1）有輸入。算法有一個(gè)或多個(gè)輸入數(shù)據(jù)，輸入數(shù)據(jù)是算法的加工對(duì)象，是數(shù)據(jù)原材料。

在Java程序設(shè)計(jì)語(yǔ)言中，算法表現(xiàn)為類的方法，算法的輸入可以通過(guò)方法的形式參數(shù)接受，也可以在方法體內(nèi)由變量賦值語(yǔ)句指定，還可以在方法體內(nèi)通過(guò)輸入語(yǔ)句從鍵盤、外存等外部設(shè)備接受，算法的輸入數(shù)據(jù)亦可由方法所在類的成員變量的值提供。

例如求階乘的算法有一個(gè)輸入數(shù)據(jù)，通過(guò)方法的形式參數(shù)接受，如下所示：

staticdoublefact(intn){ doubles=1; for(inti=1;i<=n;i++){ s=s*i; } returns;

}算法也可以有兩個(gè)或多個(gè)輸入數(shù)據(jù)，例如求最大公約數(shù)的算法有兩個(gè)輸入數(shù)據(jù)，需要輸入兩個(gè)整數(shù)的值。

求兩個(gè)非負(fù)整數(shù)數(shù)a和b（要求a>b）的最大公約數(shù)可以使用輾轉(zhuǎn)相除法，算法用自然語(yǔ)言描述為：

①a除以b得到的余數(shù)為c（0<=c<b）；

②若c=0則算法結(jié)束，b為最大公約數(shù)。否則轉(zhuǎn)③；

③a=b，b=c，轉(zhuǎn)①；

static

int

gys1(int

a,int

b)//最大公約數(shù)

{

int

temp=0;

if(a<b){temp=a;a=b;b=temp;}

int

c=a%b;

while(c!=0){

a=b;

b=c;

c=a%b;}

return

b;}

輾轉(zhuǎn)相除法算法用Java語(yǔ)言描述如下，算法的兩個(gè)輸入數(shù)據(jù)均通過(guò)方法的形式參數(shù)接受：在Java語(yǔ)言中，輾轉(zhuǎn)相除算法的兩個(gè)輸入數(shù)據(jù)也可以在方法體內(nèi)通過(guò)輸入語(yǔ)句從外設(shè)鍵盤接受，如下所示：static

int

gys2()//最大公約數(shù)

{Scannerreader=newScanner(System.in);System.out.print("請(qǐng)輸入第一個(gè)數(shù)：");inta=reader.nextInt();System.out.print("請(qǐng)輸入第二個(gè)數(shù)：");intb=reader.nextInt();

int

temp=0;

if(a<b){temp=a;a=b;b=temp;}

int

c=a%b;

while(c!=0){

a=b;

b=c;

c=a%b;}

return

b;}

（2）有輸出。

算法有一個(gè)或多個(gè)輸出數(shù)據(jù)，輸出數(shù)據(jù)是一組與輸入有確定關(guān)系的值，是算法對(duì)輸入數(shù)據(jù)進(jìn)行加工后得到的結(jié)果數(shù)據(jù)，這種確定關(guān)系即為算法的功能。上面例子中，階乘、最大公約數(shù)就是算法的輸出。

在Java程序設(shè)計(jì)語(yǔ)言中，算法的輸出一般通過(guò)方法體內(nèi)的return語(yǔ)句返回，如上面兩個(gè)例子；還可以把結(jié)果數(shù)據(jù)輸出到屏幕、打印機(jī)、外存等外部設(shè)備，也可以傳到網(wǎng)絡(luò)，還可以表現(xiàn)為方法所在類中成員變量值的改變。例如輾轉(zhuǎn)相除法求最大公約數(shù)可以把結(jié)果數(shù)據(jù)輸出到屏幕，如下所示：staticvoidgys3()//最大公約數(shù)

{Scannerreader=newScanner(System.in);System.out.print("請(qǐng)輸入第一個(gè)數(shù)：");inta=reader.nextInt();System.out.print("請(qǐng)輸入第二個(gè)數(shù)：");intb=reader.nextInt();

int

temp=0;

if(a<b){temp=a;a=b;b=temp;}

int

c=a%b;

while(c!=0){

a=b;

b=c;

c=a%b;}

System.out.print("最大公約數(shù)為："+b);}

（3）確定性。每步定義都是確切、無(wú)歧義的，而不是含糊的，模棱兩可的。并且在任何條件下，算法只有惟一的一條執(zhí)行路徑，即對(duì)于相同的輸入只能得到相同的輸出。

在Java程序設(shè)計(jì)語(yǔ)言中，算法的操作步驟通過(guò)語(yǔ)句描述，所寫語(yǔ)句必須符合語(yǔ)法規(guī)定，不符合確定性要求的語(yǔ)句編譯不會(huì)通過(guò)，算法的確定性檢驗(yàn)主要由編譯器協(xié)助完成。（4）有窮性。對(duì)于任意一組合法的輸入值，算法在執(zhí)行有窮步驟后一定能結(jié)束。即算法的操作步驟為有限個(gè)，且每步都能在有限時(shí)間內(nèi)完成。

在Java程序設(shè)計(jì)語(yǔ)言中，死循環(huán)的算法是不符合設(shè)計(jì)要求的。事實(shí)上，“有窮性”是指合理的范圍內(nèi)，計(jì)算機(jī)執(zhí)行100年才結(jié)束的算法，雖然是有窮的，但超過(guò)了合理的限度，也是不可行的。（5）有效性。算法每一步能有效的執(zhí)行，并能得到確定的結(jié)果。例如，在除法中，除數(shù)不為0才能被有效執(zhí)行，除數(shù)為0是不能被有效執(zhí)行的。

在Java程序設(shè)計(jì)語(yǔ)言中，不能被有效執(zhí)行的語(yǔ)句會(huì)中止執(zhí)行，并產(chǎn)生異常對(duì)象。1.4.2算法設(shè)計(jì)的要求

對(duì)于一個(gè)特定的問(wèn)題，采用的數(shù)據(jù)結(jié)構(gòu)不同，其設(shè)計(jì)的算法一般也不同，即使在同一種數(shù)據(jù)結(jié)構(gòu)下，也可以采用不同的算法。那么，解決實(shí)際問(wèn)題時(shí)，選擇哪一種算法比較合適，以及如何對(duì)現(xiàn)有的算法進(jìn)行改進(jìn)，從而設(shè)計(jì)出更優(yōu)質(zhì)的算法，這就是算法設(shè)計(jì)要求的問(wèn)題。評(píng)價(jià)一個(gè)算法優(yōu)劣的主要標(biāo)準(zhǔn)如下：

正確性可讀性健壯性時(shí)間效率與空間效率

1、正確性（correctness）

算法的正確性指的是對(duì)合法正確的輸入能夠獲取正確的輸出。比如求階乘的算法，對(duì)于合法正確的輸入數(shù)據(jù)4，算法能夠輸出正確的結(jié)果24。

對(duì)于程序設(shè)計(jì)語(yǔ)言描述的算法，“正確”大體分為以下四個(gè)層次：

（1）不含語(yǔ)法錯(cuò)誤，編譯通過(guò)。

（2）幾組輸入數(shù)據(jù)能輸出正確的結(jié)果數(shù)據(jù)。

（3）精心選擇的幾組典型、苛刻、刁難性數(shù)據(jù)能得出正確的結(jié)果數(shù)據(jù)。

（4）一切合法輸入均能輸出正確的結(jié)果數(shù)據(jù)。

顯然，達(dá)到第四層次意義下的正確是極為困難的，一切合法輸入數(shù)據(jù)量大得驚人，逐一測(cè)試的方法是不現(xiàn)實(shí)的。對(duì)大型軟件需要進(jìn)行專業(yè)測(cè)試，一般情況下，通常以第三層次意義的正確性作為軟件驗(yàn)收標(biāo)準(zhǔn)1.4.2算法設(shè)計(jì)的要求

2、可讀性（readbility）算法的可讀性指的是算法的表達(dá)思路清晰，簡(jiǎn)潔明了，易于理解。對(duì)于程序設(shè)計(jì)語(yǔ)言描述的算法，為了提高可讀性，通常做法加注釋。1.4.2算法設(shè)計(jì)的要求3、健壯性（robustness）又稱魯棒性，是robust音譯,也稱容錯(cuò)性。當(dāng)用戶輸入不合法時(shí)，例如用戶輸入錯(cuò)誤時(shí)，能夠反饋給用戶相應(yīng)的提示信息，而不是終止程序的執(zhí)行，或顯示調(diào)試時(shí)出現(xiàn)的一些錯(cuò)誤信息。1.4.2算法設(shè)計(jì)的要求4、時(shí)間效率與空間效率要求算法執(zhí)行時(shí)間越短，算法的時(shí)間效率越高，算法執(zhí)行時(shí)占用的內(nèi)存空間越少，算法的空間效率越高。下面兩小節(jié)就要來(lái)講述怎樣度量算法的效率。1.4.2算法設(shè)計(jì)的要求1.4.3算法時(shí)間效率的度量1、算法的執(zhí)行時(shí)間算法時(shí)間效率可以利用算法執(zhí)行時(shí)間進(jìn)行度量，算法執(zhí)行時(shí)間就是依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行所消耗的時(shí)間。兩個(gè)缺陷：

1）必須首先運(yùn)行依據(jù)算法編制的程序

2）所得時(shí)間的統(tǒng)計(jì)量依賴于計(jì)算機(jī)硬件、軟件的因素，容易掩蓋算法本身的優(yōu)劣。分析算法時(shí)間效率時(shí)，必須撇開這些與算法無(wú)關(guān)的軟硬件因素。通常的做法是：從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。稱之為：2、漸進(jìn)時(shí)間復(fù)雜度

被稱作問(wèn)題的基本操作的原操作多數(shù)情況下是最深層循環(huán)內(nèi)語(yǔ)句的原操作，它的執(zhí)行次數(shù)和包含它的語(yǔ)句頻度相同，語(yǔ)句的頻度指的是該語(yǔ)句重復(fù)執(zhí)行的次數(shù)。

例題1求階乘的算法把乘法操作看作基本操作，乘法操作包含在下面畫橫線的語(yǔ)句中，基本操作重復(fù)執(zhí)行了多少次？staticdoublefact(intn){ doubles=1; for(inti=1;i<=n;i++){

s=s*i; } returns;}

乘法操作執(zhí)行了n次。該算法的時(shí)間復(fù)雜度記為O(n)基本操作執(zhí)行次數(shù)與n成正比的即an+b均記為O(n)基本操作執(zhí)行次數(shù)與n2成正比的即cn2+an+b均記為O(n2)（重點(diǎn)關(guān)注增長(zhǎng)最快的項(xiàng)）在一些常用的項(xiàng)中到底哪個(gè)項(xiàng)增長(zhǎng)快呢？有下面的不等式成立：c<log2n<n<nlog2n<n2<n3<2n<3n<n!例題2：求n行n列矩陣所有元素之和的算法可以把加法操作看作基本操作，加法操作包含在下面劃?rùn)M線的語(yǔ)句中，請(qǐng)分析該算法的時(shí)間復(fù)雜度。

基本操作執(zhí)行n2+n次，該算法的時(shí)間復(fù)雜度記為O(n2)

staticfloatexample(float[][]x,intn){ float[]sum=newfloat[n]; floattotalsum=0.0f; for(inti=0;i<n;i++){//x[][]中各行數(shù)據(jù)累加和

for(intj=0;j<n;j++)

sum[i]=sum[i]+x[i][j]; } for(inti=0;i<n;i++)//各行數(shù)據(jù)匯總相加

totalsum=totalsum+sum[i]; returntotalsum;

}有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問(wèn)題的輸入數(shù)據(jù)集不同而不同。比如冒泡排序法，此算法的功能是對(duì)輸入數(shù)據(jù)序列進(jìn)行排序，算法執(zhí)行完畢后，序列中數(shù)據(jù)元素依次遞增。排序過(guò)程如下所示：冒泡排序的過(guò)程：假設(shè)輸入數(shù)據(jù)序列中元素個(gè)數(shù)是n，首先比較第一個(gè)和第二個(gè)數(shù)據(jù)，將其中較小的數(shù)據(jù)放到第一個(gè)位置，較大的放到第二個(gè)位置；然后比較第二個(gè)和第三個(gè)數(shù)據(jù)，仍將較大的放到后一個(gè)位置。依此類推，直到比較第n-1和第n個(gè)數(shù)據(jù)。這樣，就將待排序序列中的最大的一個(gè)放到了第n個(gè)位置（一趟排序冒出一個(gè)泡來(lái)），這個(gè)過(guò)程稱為第一趟排序。對(duì)前n-1個(gè)數(shù)據(jù)重復(fù)這個(gè)過(guò)程（不用考慮第n個(gè)位置數(shù)據(jù)，因?yàn)樗呀?jīng)是最大的了），又將次大的數(shù)據(jù)放到了第n-1個(gè)位置。第三趟排序選出第三大的數(shù)據(jù)，放到倒數(shù)第三個(gè)位置。重復(fù)這個(gè)過(guò)程，直到數(shù)據(jù)依次遞增為止（共n-1趟）。[初態(tài)]：4682405267312173對(duì)此輸入數(shù)據(jù)序列進(jìn)行冒泡排序：冒泡排序法示例：[初態(tài)]：4682405267312173第1趟：4640526731217382第2趟：4046523121677382第3趟：4046312152677382第4趟：4031214652677382第5趟：3121404652677382第6趟：2131404652677382第7趟：2131404652677382java語(yǔ)言源碼

static

voidbubble_sort(int[]a,int

n) {

for(int

i=n-1;i>0;i--)

for(int

j=0;j<i;++j)

if(a[j]>a[j+1])

{int

temp=a[j];a[j]=a[j+1];a[j+1]=temp;} }冒泡排序法中把數(shù)據(jù)交換操作看作基本操作，數(shù)據(jù)交換操作包含在上面畫橫線的語(yǔ)句中，設(shè)輸入數(shù)據(jù)序列中數(shù)據(jù)元素個(gè)數(shù)是n，則冒泡排序法中基本操作重復(fù)執(zhí)行的次數(shù)隨輸入數(shù)據(jù)狀態(tài)的不同而不同。最壞的情況：當(dāng)初始狀態(tài)完全逆序，即數(shù)據(jù)元素遞減有序，需要進(jìn)行多少次數(shù)據(jù)交換？（此例中數(shù)據(jù)元素個(gè)數(shù)n=8）

[初態(tài)]：82736752464031

21第1趟：736752464031

21

82

n-1第2趟：6752464031

2173

82n-2第3趟：5246403121677382n-3第4趟：4640312152677382.第5趟：4031214652677382.第6趟：31214046526773822第7趟：21314046526773821第1趟需要進(jìn)行n-1次數(shù)據(jù)交換，第2趟需要進(jìn)行n-2次數(shù)據(jù)交換，依此類推...，第n-1要進(jìn)行需要進(jìn)行1次數(shù)據(jù)交換，數(shù)據(jù)交換操作重復(fù)進(jìn)行的總次數(shù)=(n-1)+(n-2)+…+2+1=n(n-1)/2。

[初態(tài)]：2131404652677382次數(shù)第1趟：21314046526773820第2趟：21314046526773820第3趟：21314046526773820第4趟：21314046526773820第5趟：21314046526773820第6趟：21314046526773820第7趟：21314046526773820最好的情況：當(dāng)初始狀態(tài)已經(jīng)遞增有序時(shí)，第1趟不需要進(jìn)行數(shù)據(jù)交換，第2趟不需要進(jìn)行數(shù)據(jù)交換，依此類推...，第n-1趟也不需要進(jìn)行次數(shù)據(jù)交換，如下所示：（此例中數(shù)據(jù)元素個(gè)數(shù)n=8）

計(jì)算時(shí)間復(fù)雜度以最壞情況為準(zhǔn)，為O(n2)。當(dāng)某一趟排序沒(méi)有數(shù)據(jù)交換時(shí)，表明數(shù)據(jù)元素已經(jīng)按遞增有序，接下來(lái)的排序過(guò)程可以不必進(jìn)行，但此算法依就會(huì)進(jìn)行完n-1排序過(guò)程才終止。怎樣解決此問(wèn)題？具體做法是：設(shè)置一個(gè)變量change=true，用它來(lái)記錄一趟排序過(guò)程中是否有數(shù)據(jù)交換。在每趟排序之前置change的值為false，每當(dāng)產(chǎn)生交換數(shù)據(jù)，change的值就改為true。每趟排序之后，判斷change的值，若為true，則繼續(xù)下一趟排序；若為false，表明這一趟沒(méi)有交換任何數(shù)據(jù)，排序已經(jīng)完成。

改進(jìn)算法中，如果輸入數(shù)據(jù)集的初始狀態(tài)已經(jīng)呈現(xiàn)遞增有序，形如21、31、40、46、52、67、73、82，則if分支下的語(yǔ)句無(wú)執(zhí)行的機(jī)會(huì)，chang