《數(shù)據(jù)結(jié)構(gòu)JAVA語(yǔ)言版》課件 孫愛(ài)香 第1-3章 緒論、線(xiàn)性表、棧和隊(duì)列

數(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)的總稱(chēng)。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)的種類(lèi)1、集合結(jié)構(gòu)。在集合結(jié)構(gòu)中，數(shù)據(jù)元素間的關(guān)系除了“屬于同一個(gè)集合”外，別無(wú)任何關(guān)系。

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

1.2.2數(shù)據(jù)結(jié)構(gòu)的種類(lèi)3、樹(shù)型結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。1.2.2數(shù)據(jù)結(jié)構(gòu)的種類(lèi)4、圖形結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系，圖形結(jié)構(gòu)也稱(chēng)作網(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ēng)為虛擬存儲(chǔ)結(jié)構(gòu)。1、數(shù)據(jù)元素的表示單個(gè)數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)元素可以利用java語(yǔ)言固有的基本數(shù)據(jù)類(lèi)型（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ǔ)言中的自己定義的類(lèi)表示。例如：學(xué)生實(shí)體的數(shù)據(jù)元素可由學(xué)號(hào)、姓名、所在系、性別、出生日期、入學(xué)成績(jī)等數(shù)據(jù)項(xiàng)組成，在Java語(yǔ)言中用自己定義的類(lèi)表示如下：classStudent{

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

StringName;

StringDepartment;

charSex;

DateBirthDate;//Date位于java.util子類(lèi)庫(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

例如：線(xiàn)性數(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í)，線(xiàn)性數(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ì)用戶(hù)透明，在Java虛擬處理器中線(xiàn)性數(shù)據(jù)結(jié)構(gòu)的順序存儲(chǔ)就是線(xiàn)性數(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ǔ)位置不一定相鄰。線(xiàn)性數(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ì)用戶(hù)透明，在Java虛擬處理器中，把相鄰元素的存儲(chǔ)地址抽象為引用，在存儲(chǔ)結(jié)構(gòu)圖中用箭頭表示，整個(gè)存儲(chǔ)結(jié)構(gòu)像一條鏈條，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也是由此命名。1.2.5抽象數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型：數(shù)據(jù)的邏輯結(jié)構(gòu)及定義在該邏輯結(jié)構(gòu)上的一組操作。

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

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

為了提高軟件的復(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ù)類(lèi)型的抽象層次越高，含有該數(shù)據(jù)類(lèi)型的軟件模塊的復(fù)用度也越高。1.3數(shù)學(xué)預(yù)備知識(shí)1.3.1集合1、集合的概念

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

沒(méi)有元素的集合稱(chēng)為空集，記作Φ。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é)縮寫(xiě)為“B”，位縮寫(xiě)為“b”，千字節(jié)縮寫(xiě)為“KB”，百萬(wàn)字節(jié)縮寫(xiě)為縮寫(xiě)為“MB”，十億字節(jié)縮寫(xiě)為縮寫(xiě)為“GB”，萬(wàn)億字節(jié)縮寫(xiě)為“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í)稱(chēng)為求余，記為%,例如: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)用自己，就稱(chēng)這個(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)用路線(xiàn)逐步返回。遞歸是程序設(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ǔ)言中，算法一般用類(lèi)的一個(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)為類(lèi)的方法，算法的輸入可以通過(guò)方法的形式參數(shù)接受，也可以在方法體內(nèi)由變量賦值語(yǔ)句指定，還可以在方法體內(nèi)通過(guò)輸入語(yǔ)句從鍵盤(pán)、外存等外部設(shè)備接受，算法的輸入數(shù)據(jù)亦可由方法所在類(lèi)的成員變量的值提供。

例如求階乘的算法有一個(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è)鍵盤(pán)接受，如下所示：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)為方法所在類(lèi)中成員變量值的改變。例如輾轉(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ǔ)句描述，所寫(xiě)語(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)行專(zhuā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）又稱(chēng)魯棒性，是robust音譯,也稱(chēng)容錯(cuò)性。當(dāng)用戶(hù)輸入不合法時(shí)，例如用戶(hù)輸入錯(cuò)誤時(shí)，能夠反饋給用戶(hù)相應(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ì)量依賴(lài)于計(jì)算機(jī)硬件、軟件的因素，容易掩蓋算法本身的優(yōu)劣。分析算法時(shí)間效率時(shí)，必須撇開(kāi)這些與算法無(wú)關(guān)的軟硬件因素。通常的做法是：從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。稱(chēng)之為：2、漸進(jìn)時(shí)間復(fù)雜度

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

例題1求階乘的算法把乘法操作看作基本操作，乘法操作包含在下面畫(huà)橫線(xiàn)的語(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線(xiàn)的語(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è)位置。依此類(lèi)推，直到比較第n-1和第n個(gè)數(shù)據(jù)。這樣，就將待排序序列中的最大的一個(gè)放到了第n個(gè)位置（一趟排序冒出一個(gè)泡來(lái)），這個(gè)過(guò)程稱(chēng)為第一趟排序。對(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ù)交換操作包含在上面畫(huà)橫線(xiàn)的語(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ù)交換，依此類(lèi)推...，第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ù)交換，依此類(lèi)推...，第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ì)，change的值無(wú)法改變?yōu)閠rue，始終保持false，內(nèi)層循環(huán)語(yǔ)句執(zhí)行結(jié)束后，i>0&&change邏輯表達(dá)式的運(yùn)算結(jié)果為false，不能再次進(jìn)入外層循環(huán)，排序過(guò)程終止。

static

voidimprove_bubble_sort(int[]a,int

n){

int

i,jtemp;boolean

change=true;

for(i=n-1;i>0&&change;--i)

{

change=false;

for(

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

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

temp=a[j];a[j]=a[j+1];a[j+1]=temp;

change=true;}}}1.4.4算法的空間效率分析算法的空間效率指的是包含算法的程序從運(yùn)行開(kāi)始到結(jié)束所需的存儲(chǔ)空間。執(zhí)行一個(gè)算法所需的存儲(chǔ)空間包括三部分：（1）程序指令占用的存儲(chǔ)空間；（2）輸入數(shù)據(jù)占用的存儲(chǔ)空間；（3）實(shí)現(xiàn)數(shù)據(jù)處理任務(wù)所必須的輔助存儲(chǔ)空間。指令占用存儲(chǔ)空間一般與問(wèn)題規(guī)模n無(wú)關(guān);輸入數(shù)據(jù)占用的存儲(chǔ)空間多數(shù)情況下與算法無(wú)關(guān);重點(diǎn)分析輔助存儲(chǔ)空間與問(wèn)題規(guī)模n的函數(shù)關(guān)系，該函數(shù)記為f（n）。

請(qǐng)分析下面算法的空間復(fù)雜度。

static

voidimprove_bubble_sort(int[]a,int

n){

int

i,jtemp;boolean

change=true;

for(i=n-1;i>0&&change;--i)

{

change=false;

for(

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

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

temp=a[j];a[j]=a[j+1];a[j+1]=temp;

change=true;}}}該冒泡排序算法除了程序指令和輸入數(shù)據(jù)占用的存儲(chǔ)空間，還必須用到i、j、change、temp四個(gè)輔助變量，i、j、temp是int型變量，分別占用4個(gè)字節(jié)的存儲(chǔ)空間，change是boolean型變量，占用2個(gè)字節(jié)的存儲(chǔ)空間，所以該冒泡排序算法輔助變量占用的總存儲(chǔ)空間14個(gè)字節(jié)，即f（n）=14，算法的空間復(fù)雜度記為O(1)，是常量階的。第2章線(xiàn)性表本章主要介紹下列內(nèi)容線(xiàn)性表的類(lèi)型定義線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線(xiàn)性表的應(yīng)用舉例2.1線(xiàn)性表的類(lèi)型定義2.1.1線(xiàn)性表的定義線(xiàn)性表是由n（n≥0）個(gè)類(lèi)型相同的數(shù)據(jù)元素組成的有限序列，通常表示成如下形式：

L=(a1,a2,...,ai-1,ai,ai+1,...,an)

其中，L為線(xiàn)性表名稱(chēng)，習(xí)慣用大寫(xiě)字母書(shū)寫(xiě)；ai為組成該線(xiàn)性表的數(shù)據(jù)元素，習(xí)慣用小寫(xiě)字母書(shū)寫(xiě)。

線(xiàn)性表中數(shù)據(jù)元素的個(gè)數(shù)被稱(chēng)為線(xiàn)性表的長(zhǎng)度，當(dāng)線(xiàn)性表的長(zhǎng)度為0時(shí)，線(xiàn)性表被稱(chēng)為空線(xiàn)性表。

表中相鄰元素之間存在著前后次序關(guān)系，將ai-1稱(chēng)為ai的直接前驅(qū)，將ai＋1稱(chēng)為ai的直接后繼。

線(xiàn)性表舉例：

例如，

線(xiàn)性表LA=(34,89,765,12,90,-34,22)中，

線(xiàn)性表的長(zhǎng)度為7，數(shù)據(jù)元素類(lèi)型均為整型，765是12的直接前驅(qū)，90是12的直接后繼。

線(xiàn)性表LB=(“Hello”,“World”,“China”,“Welcome”)中，

線(xiàn)性表的長(zhǎng)度為4，數(shù)據(jù)元素類(lèi)型均為字符串型，“World”是“China”的直接前驅(qū)，“Welcome”是“China”的直接后繼。L=(a1,a2,...,ai-1,ai,ai+1,...,an)

2.1.2線(xiàn)性表的四個(gè)特點(diǎn)：（1）存在唯一的一個(gè)被稱(chēng)作“第一個(gè)”的數(shù)據(jù)元素。（2）存在唯一的一個(gè)被稱(chēng)作“最后一個(gè)”的數(shù)據(jù)元素。（3）除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)直接前驅(qū)。（4）除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)直接后繼。2.1.3線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型定義

ADT

LIST{

數(shù)據(jù)對(duì)象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：

R＝{<ai-1,ai>|ai-1,ai

∈D,i=2,...,n}

基本操作：}

棧D是n個(gè)數(shù)據(jù)元素的集合，D是ElemSet的子集。ElemSet表示某個(gè)集合，集合中的數(shù)據(jù)元素類(lèi)型相同，例如整數(shù)集、自然數(shù)集等。棧R是數(shù)據(jù)元素之間關(guān)系的集合，<ai-1,ai>表示ai-1和ai之間互為前驅(qū)和后繼的邏輯關(guān)系。

基本操作的定義如下。返回值類(lèi)型

基本操作名（參數(shù)表）初始條件：<初始條件描述>操作結(jié)果：<操作結(jié)果描述>“初始條件”描述了基本操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿(mǎn)足的條件；若不滿(mǎn)足，則操作失敗，并返回相應(yīng)信息。若初始條件為空，即基本操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)不必滿(mǎn)足任何條件，則省略該部分-初始條件：<初始條件描述>?！安僮鹘Y(jié)果”說(shuō)明了基本操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。關(guān)于ADT

LIST中基本操作的幾點(diǎn)附加說(shuō)明：（1）線(xiàn)性表中的數(shù)據(jù)元素類(lèi)型用T表示。（2）線(xiàn)性表基本操作是定義于邏輯結(jié)構(gòu)上的基本操作，是向使用者提供的使用說(shuō)明?；静僮髦挥性诖鎯?chǔ)結(jié)構(gòu)確定之后才能實(shí)現(xiàn)。如果線(xiàn)性表采用的存儲(chǔ)結(jié)構(gòu)不同，線(xiàn)性表基本操作的實(shí)現(xiàn)算法也不相同。（3）線(xiàn)性表基本操作的種類(lèi)和數(shù)量可以根據(jù)實(shí)際需要決定。（4）線(xiàn)性表基本操作名稱(chēng)，形式參數(shù)數(shù)量、名稱(chēng)、類(lèi)型，返回值類(lèi)型由設(shè)計(jì)者決定，使用者根據(jù)設(shè)計(jì)者的設(shè)計(jì)規(guī)則使用基本操作。

基本操作P：（1）intCount()//求長(zhǎng)度操作

操作結(jié)果：返回線(xiàn)性表中所有數(shù)據(jù)元素的個(gè)數(shù)，如果線(xiàn)性表為空，返回0。（2）Clear()//清空

操作結(jié)果：從線(xiàn)性表中清除所有數(shù)據(jù)元素。（3）booleanIsEmpty()//判斷線(xiàn)性表是否為空

操作結(jié)果：判斷線(xiàn)性表當(dāng)前的狀態(tài)，如果線(xiàn)性表為空返回true，否則返回false。

（4）Append(Titem)//附加操作初始條件：線(xiàn)性表未滿(mǎn)。操作結(jié)果：將值為item的新元素添加到表的末尾。（5）Insert(Titem,inti)//插入操作初始條件：線(xiàn)性表未滿(mǎn)且插入位置正確(1≤i≤n+1,n為插入前的表長(zhǎng))。操作結(jié)果：在線(xiàn)性表的第i個(gè)位置上插入一個(gè)值為item的新元素，這樣使得原序號(hào)為i,i+1,…,n的數(shù)據(jù)元素的序號(hào)變?yōu)閕+1,i+2,…,n+1，插入后表長(zhǎng)=原表長(zhǎng)+1。

（6）TDelete(inti)//刪除操作初始條件：線(xiàn)性表不為空且刪除位置正確(1≤i≤n,n為刪除前的表長(zhǎng))。操作結(jié)果：在線(xiàn)性表中刪除序號(hào)為i的數(shù)據(jù)元素，返回刪除后的數(shù)據(jù)元素。刪除后使原序號(hào)為i+1,i+2,…,n的數(shù)據(jù)元素的序號(hào)變?yōu)閕,i+1,…,n-1，刪除后表長(zhǎng)=原表長(zhǎng)-1。（7）TGetElem(inti)//取表元操作初始條件：線(xiàn)性表不為空且所取數(shù)據(jù)元素位置正確（1≤i≤n，n為線(xiàn)性表的表長(zhǎng)）。操作結(jié)果：返回線(xiàn)性表中的第i個(gè)數(shù)據(jù)元素。。（8）intLocate(Tvalue)//按值查找操作

操作結(jié)果：在線(xiàn)性表中查找值為value的數(shù)據(jù)元素，其結(jié)果返回在線(xiàn)性表中首次出現(xiàn)的值為value的數(shù)據(jù)元素的序號(hào)，稱(chēng)為查找成功；否則，在線(xiàn)性表中未找到值為value的數(shù)據(jù)元素，返回一個(gè)特殊值-1表示查找失敗。。interface

IListDS<T>{

int

Count();//求長(zhǎng)度

void

Clear();//清空操作

boolean

IsEmpty();//判斷線(xiàn)性表是否為空

void

Append(Titem);//附加操作

void

Insert(Titem,int

i);//插入操作

TDelete(int

i);//刪除操作

TGetElem(int

i);//取表元

int

Locate(Tvalue);//按值查找}在Java程序設(shè)計(jì)語(yǔ)言中，用接口表示線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型如下。

2.2線(xiàn)性表的順序存儲(chǔ)及操作實(shí)現(xiàn)2.2.1順序存儲(chǔ)線(xiàn)性表的順序存儲(chǔ)是把線(xiàn)性表的數(shù)據(jù)元素放在一組地址連續(xù)的存儲(chǔ)單元中。（在這種存儲(chǔ)方式中，以元素在計(jì)算機(jī)內(nèi)存儲(chǔ)器內(nèi)的物理位置來(lái)體現(xiàn)互為前驅(qū)和后繼的邏輯關(guān)系，線(xiàn)性表中相鄰的元素在內(nèi)存儲(chǔ)器內(nèi)也相鄰）

假設(shè)每個(gè)元素占用l(小寫(xiě)L)個(gè)存儲(chǔ)單元，線(xiàn)性表中第一個(gè)元素的存儲(chǔ)地址LOC(a1)=b，那麼線(xiàn)性表中第i個(gè)元素的存儲(chǔ)地址是多少？我們利用Java語(yǔ)言討論線(xiàn)性表的順序存儲(chǔ)，在Java虛擬處理器中，存儲(chǔ)單元的編號(hào)即存儲(chǔ)地址對(duì)用戶(hù)來(lái)說(shuō)是透明的，不可見(jiàn)的。在java虛擬處理器中我們認(rèn)為線(xiàn)性表的順序存儲(chǔ)是把線(xiàn)性表的數(shù)據(jù)元素放在一維數(shù)組中，(數(shù)組占用的就是一組地址連續(xù)的存儲(chǔ)單元)數(shù)據(jù)元素在數(shù)組中相鄰就表示它們?cè)诰€(xiàn)性表中互為前驅(qū)和后繼。在線(xiàn)性表抽象數(shù)據(jù)類(lèi)型的定義中講過(guò)，定義于邏輯結(jié)構(gòu)上的基本操作只是向外界使用者提供的一個(gè)使用接口，存儲(chǔ)結(jié)構(gòu)確定了之后基本操才能實(shí)現(xiàn)。所以接下來(lái)討論在順序存儲(chǔ)結(jié)構(gòu)下基本操作的實(shí)現(xiàn)，重點(diǎn)分析一下插入和刪除兩種基本操作的實(shí)現(xiàn)算法。ia1a2…an…ai+1

ai

a1a2…ani…ai+1ai

a1a2…ani…ai+1aiitemn+1n+1n+12.2.2順序存儲(chǔ)結(jié)構(gòu)下基本操作分析

1、

在線(xiàn)性表的第i個(gè)位置上插入數(shù)據(jù)元素item？分析插入數(shù)據(jù)元素到線(xiàn)性表（即數(shù)組）的第i個(gè)位置上所需移動(dòng)元素次數(shù)：答：從第i個(gè)數(shù)據(jù)元素到第n個(gè)都需移動(dòng)，共需移動(dòng)n-i+1次？每一個(gè)位置上都有可能插入數(shù)據(jù)元素，平均移動(dòng)次數(shù)是多少？答：第一個(gè)位置上n次，第二個(gè)位置上n-1次，第三個(gè)位置上n-2次，依次類(lèi)推，第n+1個(gè)位置上0次，平均移動(dòng)次數(shù)為：[n+（n-1）+…+1]/n+1=n/2,即：

插入到每個(gè)位置的概率相等的情況下，平均移動(dòng)次數(shù)是n/2，有些情況下插入到每個(gè)位置的概率不一定相等，怎麼算？假設(shè)插入到第一個(gè)位置的概率是1/2，其余位置是1/2n，所需移動(dòng)元素次數(shù)的期望值（平均值）（用到概率中的數(shù)學(xué)期望概念）：ia1a2…an…ai+2ai+1

iia1a2…

…ai+2ai+1

an

a1

a2

……ai+2ai+1ai

an2、

刪除線(xiàn)性表的第i個(gè)數(shù)據(jù)元素分析刪除線(xiàn)性表的第i個(gè)數(shù)據(jù)元素所需移動(dòng)元素次數(shù)答：從第i+1個(gè)數(shù)據(jù)元素到第n個(gè)都需向上移動(dòng)，共需移動(dòng)n-i次每一個(gè)位置上的數(shù)據(jù)元素都有可能被刪除，平均移動(dòng)次數(shù)是多少？答：刪除第一個(gè)數(shù)據(jù)元素需要n-1次，第二個(gè)數(shù)據(jù)元素需要n-2次，第三個(gè)位置上n-3次，依次類(lèi)推，第n個(gè)位置上0次，平均移動(dòng)次數(shù)為：[（n-1）+（n-2）+…+1]/n=（n-1）/2,即：刪除每個(gè)數(shù)據(jù)元素的概率相等的情況下即pi=1/n，平均移動(dòng)次數(shù)是（n-1）/2，有些情況下刪除每個(gè)數(shù)據(jù)元素概率不一定相等，怎麼算？假設(shè)刪除第一個(gè)數(shù)據(jù)元素概率是1/2，其余位置是所需移動(dòng)元素次數(shù)的期望值（平均值）（用到概率中的數(shù)學(xué)期望概念）：2.2.3源碼實(shí)現(xiàn)1、幾點(diǎn)說(shuō)明：

（1）前面定義的線(xiàn)性表接口IListDS<T>interface

IListDS<T>{

intCount();//求長(zhǎng)度

voidClear();//清空操作

boolean

IsEmpty();//判斷線(xiàn)性表是否為空

void

Append(T

item);//附加操作

void

Insert(T

item,int

i);//插入操作

TDelete(int

i);//刪除操作

TGetElem(int

i);//取表元

int

Locate(T

value);//按值查找}（2）順序表類(lèi)SeqList<T>，實(shí)現(xiàn)接口IListDS<T>。順序表類(lèi)SeqList<T>的實(shí)現(xiàn)說(shuō)明如下所示：

public

class

SeqList<T>implements

IListDS<T>

{T[]data;

//數(shù)組，用于存儲(chǔ)順序表中的數(shù)據(jù)元素

int

maxsize;//順序表的容量

int

last;

//指示順序表最后一個(gè)元素的位置

//接口成員方法的實(shí)現(xiàn)；

}關(guān)于屬性成員的幾點(diǎn)說(shuō)明：①Java語(yǔ)言中的數(shù)組在內(nèi)存中占用的存儲(chǔ)空間就是一組地址連續(xù)的存儲(chǔ)單元，所以，在Java虛擬處理器中考慮問(wèn)題時(shí)，認(rèn)為線(xiàn)性表的順序存儲(chǔ)就是把線(xiàn)性表的數(shù)據(jù)元素存放到數(shù)組data中。②maxsize表示容量；容量可以用數(shù)組的length屬性即data.length來(lái)表示，但為了說(shuō)明線(xiàn)性表的最大長(zhǎng)度（容量），增強(qiáng)可讀性，在SeqList<T>類(lèi)中用屬性成員maxsize來(lái)表示。③線(xiàn)性表中的元素由data[0]開(kāi)始依次順序存放，由于線(xiàn)性表中的實(shí)際元素個(gè)數(shù)一般達(dá)不到maxsize，因此，在SeqList<T>類(lèi)中需要一個(gè)屬性成員last表示線(xiàn)性表中最后一個(gè)數(shù)據(jù)元素在數(shù)組中的位置。last的值等于線(xiàn)性表中最后一個(gè)數(shù)據(jù)元素在數(shù)組中的下標(biāo)，0≤last≤maxsize-1，last值為-1時(shí)表示線(xiàn)性表為空。

public

SeqList(int

size){

if

(size

>0){

data

=(T[])new

Object[size];

//建立一個(gè)長(zhǎng)度為size，類(lèi)型為T(mén)的數(shù)組

this.maxsize

=size;

//順序表的容量maxsize

=size

last

=-1;

//最后一個(gè)元素位置last=-1；表示順序表為空。

}else

throw

new

IllegalArgumentException("初始化容量必須大于0");

}（3）順序表類(lèi)SeqList<T>的構(gòu)造方法在Java語(yǔ)言中，一個(gè)基本操作表現(xiàn)為類(lèi)中的一個(gè)方法。SeqList<T>類(lèi)除了實(shí)現(xiàn)接口IListDS<T>中的方法外，還可實(shí)現(xiàn)一些另外的成員方法，實(shí)現(xiàn)更復(fù)雜的操作。2基本操作實(shí)現(xiàn)（1）求長(zhǎng)度

由于數(shù)組是0基數(shù)組，即數(shù)組的最小下標(biāo)為0，所以，長(zhǎng)度就是最后一個(gè)元素在數(shù)組中的下標(biāo)last加1。

求長(zhǎng)度的算法實(shí)現(xiàn)如下：

public

intCount(){

return

last+1;}2、清空操作

清除順序表中的數(shù)據(jù)元素是使順序表為空，此時(shí)，last等于-1。

public

voidClear(){

last=-1;}

3、判斷線(xiàn)性表是否為空如果順序表的last為-1，則順序表為空，返回true，否則返回false。

public

boolean

IsEmpty(){

if(last==-1){

return

true;}

else{

return

false;}}4、判斷順序表是否為滿(mǎn)如果順序表為滿(mǎn)，即last等于maxsize-1，則返回true，否則返回false。

public

boolean

IsFull(){

if(last==maxsize-1)//順序表已滿(mǎn)

{

return

true;}

else{

return

false;}}

5、附加操作

附加操作是在順序表未滿(mǎn)的情況下，在表的末端添加一個(gè)新元素，然后使順序表的last加1。

public

void

Append(T

item){

if(last==maxsize-1)//順序表已滿(mǎn)

{System.out.println("Listisfull");

//輸出順序表已滿(mǎn)信息提示

return;//返回

}

data[++last]=item;//在表的末端添加一個(gè)新元素，使順序表的last加1}

6、插入操作Insert(Titem,inti)

順序表的插入是指在順序表的第i個(gè)位置插入一個(gè)值為item的新元素。

插入后使原表長(zhǎng)為n的表

(a1,a2,…,ai-1,ai,ai+1,…,an)成為表長(zhǎng)為n+1的表

(a1,a2,…,ai-1,item,ai,ai+1,…,an)。i的取值范圍為1≤i≤n+1（n為順序表的表長(zhǎng)=last+1）。i為n+1(即last+2)時(shí)，表示在順序表的末尾插入數(shù)據(jù)元素。

順序表上插入數(shù)據(jù)元素的步驟如下：判斷順序表是否已滿(mǎn)和插入的位置是否正確，表滿(mǎn)或插入的位置不正確不能插入；如果表未滿(mǎn)和插入的位置正確，則將an～ai依次向后移動(dòng)，為新的數(shù)據(jù)元素空出位置。在算法中用循環(huán)來(lái)實(shí)現(xiàn)；將新的數(shù)據(jù)元素插入到空出的第i個(gè)位置上；修改last（相當(dāng)于修改表長(zhǎng)），使它仍指向順序表的最后一個(gè)數(shù)據(jù)元素。

插入操作的算法實(shí)現(xiàn)如下：

public

void

Insert(T

item,int

i){

//判斷順序表是否已滿(mǎn)

if(IsFull()){

System.out.println("Listisfull");

return;}//判斷插入的位置是否正確，//i小于1表示在第1個(gè)位置之前插入，//i大于last+2表示在最后一個(gè)元素后面的第2個(gè)位置插入。

if(i<1||i>last+2){

System.out.println("Positioniserror!");

return;}

//元素移動(dòng)

for(int

j=last;j>=i-1;--j){

data[j+1]=data[j];}

//將新的數(shù)據(jù)元素插入到第i個(gè)位置上

data[i-1]=item;

//修改表長(zhǎng)

++last;}算法的時(shí)間復(fù)雜度分析：順序表上的插入操作，時(shí)間主要消耗在數(shù)據(jù)的移動(dòng)上；在第i個(gè)位置插入一個(gè)元素，從ai到an都要向后移動(dòng)一個(gè)位置，共需要移動(dòng)n-i+1個(gè)元素；i的取值范圍為1≤i≤n+1，當(dāng)i等于1時(shí)，需要移動(dòng)的元素個(gè)數(shù)最多，為n個(gè)；當(dāng)i為n+1時(shí)，不需要移動(dòng)元素。插入操作的時(shí)間復(fù)雜度為O（n）。7、刪除操作順序表的刪除操作是指將表中第i個(gè)數(shù)據(jù)元素從順序表中去掉。刪除后使原表長(zhǎng)為n的表(a1,a2,…,ai-1,ai,ai+1,…,an)變?yōu)楸黹L(zhǎng)為n-1的表(a1,a2,…,ai-1,ai+1,…,an)。i的取值范圍為1≤i≤n。i為n時(shí)，表示刪除末尾的數(shù)據(jù)元素。

順序表上刪除一個(gè)數(shù)據(jù)元素的步驟如下：（1）判斷順序表是否為空和刪除的位置是否正確，表空或刪除的位置不正確不能刪除；

（2）如果表未空和刪除的位置正確，則將ai+1～an依次向前移動(dòng)。在算法中用循環(huán)來(lái)實(shí)現(xiàn)；

（3）修改last（相當(dāng)于修改表長(zhǎng)），使它仍指向順序表的最后一個(gè)元素。

publicTDelete(inti)刪除操作的算法實(shí)現(xiàn)如下：

publicTDelete(int

i){Ttmp;

//判斷表是否為空

if(IsEmpty()){

throw

new

RuntimeException("線(xiàn)性表為空，無(wú)法刪除");}

//判斷刪除的位置是否正確

//i小于1表示刪除第1個(gè)位置之前的元素，

//i大于last+1表示刪除最后一個(gè)元素后面的第1個(gè)位置的元素。

if(i<1||i>last+1){

throw

new

RuntimeException(“無(wú)效的下標(biāo)：”+i);

//拋出異常}

tmp=data[i-1];

//tmp值等于順序表的第i個(gè)數(shù)據(jù)元素data[i-1]

for(int

j=i;j<=last;++j){

data[j-1]=data[j];}//元素移動(dòng)

--last;//修改表長(zhǎng)

return

tmp;//返回tmp值}

算法的時(shí)間復(fù)雜度分析在第i個(gè)位置刪除一個(gè)元素，從ai+1到an都要向前移動(dòng)一個(gè)位置，共需要移動(dòng)n-i個(gè)元素；而i的取值范圍為1≤i≤n；當(dāng)i等于1時(shí)，需要移動(dòng)的元素個(gè)數(shù)最多，為n-1個(gè)；當(dāng)i為n時(shí)，不需要移動(dòng)元素；刪除操作的時(shí)間復(fù)雜度為O(n)。8、取表元TGetElem(inti)取表元運(yùn)算是返回順序表中第i個(gè)數(shù)據(jù)元素。i的取值范圍是1≤i≤last+1步驟如下：判斷表是否為空和位置是否正確返回順序表的第i個(gè)數(shù)據(jù)元素

取表元運(yùn)算的算法實(shí)現(xiàn)如下：順序表取表元運(yùn)算的時(shí)間復(fù)雜度為O（1）。

publicTGetElem(int

i){//判斷表是否為空和位置是否正確

if(IsEmpty()){

throw

new

RuntimeException("線(xiàn)性表為空，無(wú)法刪除"); }

//判斷位置是否正確

//i小于1表示獲取第1個(gè)位置之前的元素，

//i大于last+1表示獲取最后一個(gè)元素后面的第1個(gè)位置的元素。

if(i<1||i>last+1) {

throw

new

RuntimeException("無(wú)效的下標(biāo)："+i);

//返回tmp }

return

data[i-1];//返回順序表的第i個(gè)數(shù)據(jù)元素

}

9、按值查找int

Locate(Tvalue)

順序表中的按值查找是指在表中查找滿(mǎn)足給定值的數(shù)據(jù)元素。從第一個(gè)元素起依次與給定值比較，如果找到，則返回在順序表中首次出現(xiàn)與給定值相等的數(shù)據(jù)元素的序號(hào)，稱(chēng)為查找成功；否則，在順序表中沒(méi)有與給定值匹配的數(shù)據(jù)元素，返回一個(gè)特殊值-1表示查找失敗。

按值查找運(yùn)算的算法實(shí)現(xiàn)如下：

public

int

Locate(T

value){

//順序表為空

if(IsEmpty()){

System.out.println("listisEmpty");

return-1;}

int

i=0;

//循環(huán)處理順序表

for(i=0;i<=last;++i){

//順序表中存在與給定值相等的元素

if(data[i]==value){

break;}}

//順序表中不存在與給定值相等的元素

if(i>last){

return-1;}

return

i;}算法的時(shí)間復(fù)雜度分析順序表中的按值查找的主要運(yùn)算是比較，比較的次數(shù)與給定值在表中的位置和表長(zhǎng)有關(guān)。當(dāng)給定值與第一個(gè)數(shù)據(jù)元素相等時(shí)，比較次數(shù)為1；而當(dāng)給定值與最后一個(gè)元素相等時(shí)，比較次數(shù)為n。平均比較次數(shù)為(n+1)/2，時(shí)間復(fù)雜度為O（n）。10、輸出線(xiàn)性表

2.2.4順序表中的復(fù)雜操作【例2-1】已知順序表L，寫(xiě)一算法將其倒置。(a)

(b)

112336458060406640608045362311

算法思路把第一個(gè)元素與最后一個(gè)元素交換，把第二個(gè)元素與倒數(shù)第二個(gè)元素交換。也就是，把第i個(gè)元素與第n-i+1個(gè)元素交換。（n為線(xiàn)性表中元素的個(gè)數(shù)）i的取值范圍是1到n/2。（包括n/2）public

static

void

ReversSeqList(SeqList<Integer>L)存儲(chǔ)整數(shù)的順序表的倒置的算法實(shí)現(xiàn)如下：

public

static

void

ReversSeqList(SeqList<Integer>L){//順序表數(shù)據(jù)類(lèi)型是int

int

tmp=0;

int

n=L.Count();//n等于線(xiàn)性表的長(zhǎng)度

//以下循環(huán)實(shí)現(xiàn)順序表的倒置

for(int

i=1;i<=n/2;++i){

//數(shù)組下標(biāo)從0開(kāi)始，所以是下標(biāo)i-1的元素與n-i的元素交換

tmp=L.data[i-1];

L.data[i-1]=L.data[n-i];

L.data[n-i]=tmp;}}該算法只是對(duì)順序表中的數(shù)據(jù)元素順序掃描一遍即完成了倒置，所以時(shí)間復(fù)雜度為O(n)。【例2】有數(shù)據(jù)類(lèi)型為整型的順序表La和Lb，其數(shù)據(jù)元素均按從小到大的升序排列，編寫(xiě)一個(gè)算法將它們合并成一個(gè)表Lc，要求Lc中數(shù)據(jù)元素也按升序排列。

算法實(shí)現(xiàn)思路是依次掃描La和Lb的數(shù)據(jù)元素，比較La和Lb當(dāng)前數(shù)據(jù)元素的值，將較小值的數(shù)據(jù)元素賦給Lc，如此直到一個(gè)順序表被掃描完，然后將未完的那個(gè)順序表中余下的數(shù)據(jù)元素賦給Lc即可。Lc的容量要能夠容納La和Lb兩個(gè)表相加的長(zhǎng)度。線(xiàn)性表采用順序存儲(chǔ)方式時(shí),缺點(diǎn)：

1）占用一組編號(hào)連續(xù)的存儲(chǔ)單元。

2）刪除、插入操作需大量移動(dòng)數(shù)據(jù)元素。

為什麼說(shuō)占用一組編號(hào)連續(xù)的存儲(chǔ)單元是缺點(diǎn)？某一時(shí)刻計(jì)算機(jī)內(nèi)存狀態(tài)因?yàn)橛?jì)算機(jī)的內(nèi)存中存在很多零碎的小空間;采用順序存儲(chǔ)方式時(shí),占用一組編號(hào)連續(xù)的存儲(chǔ)單元,這些零碎的小空間得不到充分利用.2.3.1基本概念1、線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)是指用一組任意的存儲(chǔ)單元（可以不連續(xù)）存儲(chǔ)線(xiàn)性表中的數(shù)據(jù)元素。

Le=(‘A’,‘B’,‘C’)數(shù)據(jù)類(lèi)型是字符型，字符型數(shù)據(jù)占用二個(gè)存儲(chǔ)單元，即二個(gè)字節(jié)。

Le的順序存儲(chǔ)結(jié)構(gòu)：線(xiàn)性表的順序存儲(chǔ)是指用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)線(xiàn)性表中的數(shù)據(jù)元素。采用順序存儲(chǔ)方式時(shí)，數(shù)據(jù)的存儲(chǔ)是有規(guī)律的，計(jì)算機(jī)可以通過(guò)數(shù)據(jù)元素自身的地址計(jì)算出它的后繼元素地址，從而找到它的后繼元素。假設(shè)數(shù)據(jù)元素A的存儲(chǔ)地址是L,它的后繼元素的存儲(chǔ)地址是：L+2,L+2地址里面存放著B(niǎo)，表明A的后繼元素就是B數(shù)據(jù)元素B的存儲(chǔ)地址是L+2，它的后繼元素的存儲(chǔ)地址是L+4L+4地址里面存放著C，表明B的后繼元素就是C……B……A……C……864128Le=(‘A’,‘B’,‘C’)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)是用一組任意的存儲(chǔ)單元存放它的數(shù)據(jù)元素，數(shù)據(jù)的存儲(chǔ)毫無(wú)規(guī)律可言，計(jì)算機(jī)通過(guò)數(shù)據(jù)元素自身的地址無(wú)法計(jì)算出它的后繼元素地址，從而無(wú)法找到它的后繼元素是誰(shuí)?！?B……128A……NULLC……864128我們需要在它的后面附加一個(gè)指針(引用)，指向它的后繼元素。查找元素后繼時(shí)，利用指針(引用)提供的后繼元素地址，從而找到它的后繼元素。例如：數(shù)據(jù)元素A，利用指針提供的后繼元素地址128，可以確認(rèn)它的后繼是B。數(shù)據(jù)元素B，利用指針提供的后繼元素地址8，可以確認(rèn)它的后繼是C。講到這兒，同學(xué)們能不能看出鏈?zhǔn)酱鎯?chǔ)的一個(gè)優(yōu)點(diǎn)？

線(xiàn)性表的數(shù)據(jù)元素不必放在地址連續(xù)的存儲(chǔ)單元中，零碎空間能得到充分的利用。

ABCNULL在Java語(yǔ)言中，內(nèi)存單元的編號(hào)8，64，128對(duì)用戶(hù)屏蔽（也就是8，64，128不需要我們知道）,線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可以用如下形式表示：箭頭代表指針(引用)，指向下一個(gè)元素的存儲(chǔ)位置一個(gè)藍(lán)色的方塊稱(chēng)為一個(gè)結(jié)點(diǎn),它包含數(shù)據(jù)和指針（引用）兩部分。2、結(jié)點(diǎn)：數(shù)據(jù)和引用（指針）的組合。上圖中一個(gè)藍(lán)色的方塊就代表一個(gè)結(jié)點(diǎn)。ABCnull3、鏈表：線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。上圖三個(gè)方塊加兩個(gè)箭頭就是一個(gè)鏈表。

數(shù)據(jù)部分命名為data：用來(lái)存放線(xiàn)性表中數(shù)據(jù)元素。引用（指針）部分命名為next：存放下一個(gè)結(jié)點(diǎn)的地址。L=的鏈表（同學(xué)們自畫(huà)）a1a2an∧heada1a2an∧head

a1a2an