第一章緒論

通過這一章的學(xué)習(xí)，使讀者全面了解數(shù)據(jù)結(jié)構(gòu)的定義、研究內(nèi)容以及這門課程的知識體系，從而為后面章節(jié)的學(xué)習(xí)打下基礎(chǔ)。

數(shù)據(jù)結(jié)構(gòu)的定義；算法描述的工具；算法性能的評價；難重點(diǎn)：教學(xué)目標(biāo)：一、數(shù)據(jù)結(jié)構(gòu)起源于程序設(shè)計1946年第一臺計算機(jī)問世，主要用于軍事和科學(xué)研究方面的科學(xué)計算，人們把計算機(jī)理解為數(shù)值計算的工具，使用計算機(jī)的目的主要是處理數(shù)值計算問題。

抽象數(shù)學(xué)模型

設(shè)計算法

編制程序,上機(jī)調(diào)試用計算機(jī)解決一個具體問題的步驟：分析問題

提取操作對象

對象之間關(guān)系

數(shù)學(xué)的語言描述尋求數(shù)學(xué)模型：1.1數(shù)據(jù)結(jié)構(gòu)的起源

隨著計算機(jī)科學(xué)與技術(shù)的不斷發(fā)展，計算機(jī)的應(yīng)用領(lǐng)域已不再局限于科學(xué)計算，而更多地應(yīng)用于控制、管理等非數(shù)值處理領(lǐng)域。

與此相應(yīng)，計算機(jī)處理的數(shù)據(jù)也由純粹的數(shù)值發(fā)展到字符、表格、圖形、圖象、聲音等具有一定結(jié)構(gòu)的數(shù)據(jù)，處理的數(shù)據(jù)量也越來越大，這就給程序設(shè)計帶來一個問題：應(yīng)如何組織待處理的數(shù)據(jù)以及數(shù)據(jù)之間的關(guān)系（結(jié)構(gòu)）。

1968年克努思教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計算機(jī)程序設(shè)計藝術(shù)》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。隨后，相繼出現(xiàn)了用Pascal、Java、C、C++、C#等語言編寫的數(shù)據(jù)結(jié)構(gòu)方面的書。70年代初，數(shù)據(jù)結(jié)構(gòu)作為一門獨(dú)立的課程開始進(jìn)入大學(xué)課堂。二、數(shù)據(jù)結(jié)構(gòu)隨著程序設(shè)計的發(fā)展而發(fā)展

程序設(shè)計經(jīng)歷了三個階段：無結(jié)構(gòu)階段、結(jié)構(gòu)化階段和面向?qū)ο箅A段，相應(yīng)地，數(shù)據(jù)結(jié)構(gòu)的發(fā)展也經(jīng)歷了三個階段：40~60年代60~80年代始于80年代初⑴無結(jié)構(gòu)階段。

40~60年代，計算機(jī)的應(yīng)用主要針對科學(xué)計算，程序設(shè)計技術(shù)以機(jī)器語言/匯編語言為主，程序處理的數(shù)據(jù)是純粹的數(shù)值，數(shù)據(jù)之間的關(guān)系主要是數(shù)學(xué)公式或數(shù)學(xué)模型。這一階段，在人類的自然語言與計算機(jī)編程語言之間存在著巨大的鴻溝，程序設(shè)計屬于面向計算機(jī)的程序設(shè)計，設(shè)計人員關(guān)注的重心是使程序盡可能地被計算機(jī)接受并按指令正確執(zhí)行，至于程序能否讓人理解并不重要。⑵結(jié)構(gòu)化階段。

60~80年代，計算機(jī)開始廣泛應(yīng)用于非數(shù)值處理領(lǐng)域，數(shù)據(jù)表示成為程序設(shè)計的重要問題，人們認(rèn)識到程序設(shè)計規(guī)范化的重要性，提出了程序結(jié)構(gòu)模塊化，并開始注意數(shù)據(jù)表示與操作的結(jié)構(gòu)化。數(shù)據(jù)結(jié)構(gòu)及抽象數(shù)據(jù)類型就是在這種情況下形成的。數(shù)據(jù)結(jié)構(gòu)概念的引入，對程序設(shè)計的規(guī)范化起到了重大作用。圖靈獎獲得者沃思給出了一個著名的公式：

數(shù)據(jù)結(jié)構(gòu)+算法=程序從這個公式可以看到，數(shù)據(jù)結(jié)構(gòu)和算法是構(gòu)成程序的兩個重要的組成部分，一個軟件系統(tǒng)通常是以一個或幾個關(guān)鍵數(shù)據(jù)結(jié)構(gòu)為核心而組織的。隨著軟件系統(tǒng)的規(guī)模越來越大、復(fù)雜性不斷增加，人們不得不對結(jié)構(gòu)化技術(shù)重新評價。由于軟件系統(tǒng)的實(shí)現(xiàn)依賴于關(guān)鍵數(shù)據(jù)結(jié)構(gòu)，如果這些關(guān)鍵數(shù)據(jù)結(jié)構(gòu)的一個或幾個有所改變，則涉及到整個系統(tǒng)，甚至導(dǎo)致整個系統(tǒng)徹底崩潰。⑶面向?qū)ο箅A段。面向?qū)ο蠹夹g(shù)（首先是面向?qū)ο蟪绦蛟O(shè)計）始于80年代初，是目前最流行的程序設(shè)計技術(shù)。由于對象（類）將密切相關(guān)的屬性（數(shù)據(jù)）和方法（操作）定義為一個整體，從而實(shí)現(xiàn)了封裝和信息隱藏。使用類時，無需了解其內(nèi)部的實(shí)現(xiàn)細(xì)節(jié)，一旦數(shù)據(jù)（結(jié)構(gòu)）修改了，只需修改類內(nèi)部的局部代碼，軟件系統(tǒng)的其余部分無需修改。數(shù)據(jù)結(jié)構(gòu)主要強(qiáng)調(diào)兩個方面的內(nèi)容：①數(shù)據(jù)之間的關(guān)系；②針對這些關(guān)系的基本操作。三、數(shù)據(jù)結(jié)構(gòu)的發(fā)展并未終結(jié)

值得注意的是，數(shù)據(jù)結(jié)構(gòu)的發(fā)展并未終結(jié)。一方面，數(shù)據(jù)結(jié)構(gòu)將繼續(xù)隨著程序設(shè)計的發(fā)展而發(fā)展；另一方面，面向各專門領(lǐng)域的數(shù)據(jù)結(jié)構(gòu)得到研究和發(fā)展，各種實(shí)用的高級數(shù)據(jù)結(jié)構(gòu)被研究出來，各種空間數(shù)據(jù)結(jié)構(gòu)也在探索中?！皵?shù)據(jù)結(jié)構(gòu)”在計算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課，是介于數(shù)學(xué)、計算機(jī)硬件和計算機(jī)軟件三者之間的一門核心課程，其內(nèi)容不僅是一般程序設(shè)計(特別是非數(shù)值性程序設(shè)計)的基礎(chǔ)，而且是設(shè)計和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序的重要基礎(chǔ)。

1.2什么是數(shù)據(jù)結(jié)構(gòu)

描述客觀事物的符號，是信息的載體，它是能夠被計算機(jī)識別、存儲和加工處理的對象。

數(shù)據(jù)是人們利用文字符號、數(shù)字符號以及其他規(guī)定的符號對現(xiàn)實(shí)世界的事物及其活動所做的描述。數(shù)據(jù)不僅僅包括整型、實(shí)型等數(shù)值類型，還可以是文字、表格、圖像、聲音等非數(shù)值類型。比如，我們現(xiàn)在離不開的“百度”，其中有網(wǎng)頁、音樂、圖片、視頻等分類，音樂就是音頻數(shù)據(jù)，圖片是圖像數(shù)據(jù)，網(wǎng)頁則包括數(shù)值、文字、圖片等多種數(shù)據(jù)?？傊?，我們這里所說的數(shù)據(jù)，其實(shí)就是具備以下兩個條件的符號：①可以輸入到計算機(jī)；②能被計算機(jī)程序處理。1.數(shù)據(jù)2.數(shù)據(jù)元素

一個數(shù)據(jù)元素是由用來描述一個特定事物的名稱、數(shù)量、特征、性質(zhì)的一組相關(guān)信息組成的，在計算機(jī)中通常把數(shù)據(jù)元素作為一個整體進(jìn)行考慮和處理。

多數(shù)情況下，一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(xiàng)組成，有時也把數(shù)據(jù)項(xiàng)稱為數(shù)據(jù)元素的域、字段、關(guān)鍵字。具有獨(dú)立含義的最小單位3.數(shù)據(jù)項(xiàng)學(xué)號姓名性別專業(yè)年級……130102彭鳳姣女信息與計算科學(xué)13級……130103李麗女軟件工程13級……130104張漢濤男信息與計算科學(xué)13級……130105何穎文女計算機(jī)應(yīng)用13級……130106高媛女計算機(jī)應(yīng)用13級……………………例如，一所學(xué)校對學(xué)生的信息管理，其中管理對象就是學(xué)生數(shù)據(jù)。其數(shù)據(jù)元素就是一個學(xué)生的信息；每一個學(xué)生的所有信息形成了一個數(shù)據(jù)元素，通?？梢苑Q為一個學(xué)生記錄。學(xué)生的學(xué)號、姓名、性別、專業(yè)等就是其數(shù)據(jù)項(xiàng)(或稱字段)。數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位，但是在討論問題時，數(shù)據(jù)元素才是數(shù)據(jù)結(jié)構(gòu)中建立數(shù)學(xué)模型的著眼點(diǎn)。

我們把具有相同性質(zhì)的數(shù)據(jù)元素的集合稱為數(shù)據(jù)對象，它是數(shù)據(jù)的一個子集。例如，

(1)字母字符數(shù)據(jù)對象的集合C?=?{'A','B',…,'Z'}，它是字符數(shù)據(jù)的一個子集；

(2)偶數(shù)數(shù)據(jù)對象的集合N?=?{0,±2,±4,…}是整數(shù)數(shù)據(jù)的子集；

(3)學(xué)生表中的學(xué)生信息是學(xué)生數(shù)據(jù)的子集。在具體問題中，數(shù)據(jù)元素都具有相同的性質(zhì)(元素值不一定相等)，且屬于同一數(shù)據(jù)對象(數(shù)據(jù)元素類)。數(shù)據(jù)元素是數(shù)據(jù)對象的一個實(shí)例。4.數(shù)據(jù)對象數(shù)據(jù)結(jié)構(gòu)——是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)兩要素：一個是數(shù)據(jù)元素的集合，另一個是關(guān)系的集合。5.數(shù)據(jù)結(jié)構(gòu)

討論數(shù)據(jù)結(jié)構(gòu)的目的是為了在計算機(jī)中實(shí)現(xiàn)其所需的各種操作。數(shù)據(jù)結(jié)構(gòu)的操作與其具體問題要求有關(guān)。基本的操作主要有以下幾種：

插入、刪除、修改、查找、排序根據(jù)插入、刪除、修改、查找、排序等操作的特性，所有的操作可以分為兩大類：一類是加工型操作，其操作改變了結(jié)構(gòu)的值；另一類是引用型操作，其操作不改變結(jié)構(gòu)的值。數(shù)據(jù)結(jié)構(gòu)包含三部分：數(shù)據(jù)、數(shù)據(jù)之間的關(guān)系及在數(shù)據(jù)集合上的一組操作。

數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中的操作對象、對象之間的關(guān)系以及在此之上的一系列操作的學(xué)科。

數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)有兩個要素：

數(shù)據(jù)元素集合、關(guān)系的集合。在形式上，邏輯結(jié)構(gòu)通常可以采用一個二元組來表示：1.3邏輯結(jié)構(gòu)與物理結(jié)構(gòu)1.邏輯結(jié)構(gòu)Data_Structure=(D，R)

其中，D是數(shù)據(jù)元素的有限集，

R是D上關(guān)系的有限集。

邏輯結(jié)構(gòu)是面向問題的，而物理結(jié)構(gòu)是面向計算機(jī)的，其基本目標(biāo)就是將數(shù)據(jù)及其關(guān)系存儲到計算機(jī)的內(nèi)存中。根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通常有下列四類基本的結(jié)構(gòu)：

集合結(jié)構(gòu)：元素屬于或不屬于同一個集合線性結(jié)構(gòu)：元素之間存在著一對一的關(guān)系。樹形結(jié)構(gòu)：元素之間存在著一對多的關(guān)系。圖狀結(jié)構(gòu)：元素之間存在著多對多的關(guān)系。

集合線形表樹圖

物理結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的存儲形式，是邏輯結(jié)構(gòu)在計算機(jī)中的實(shí)現(xiàn)，包括數(shù)據(jù)元素的存儲及元素之間關(guān)系的組織。數(shù)據(jù)的存儲結(jié)構(gòu)要能正確反映數(shù)據(jù)元素之間的邏輯關(guān)系。如何存儲數(shù)據(jù)元素之間的關(guān)系，是實(shí)現(xiàn)物理結(jié)構(gòu)的重點(diǎn)和難點(diǎn)。數(shù)據(jù)元素的存儲結(jié)構(gòu)形式有兩種：順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)2.存儲結(jié)構(gòu)（又稱物理結(jié)構(gòu)）

順序存儲結(jié)構(gòu)是把數(shù)據(jù)元素存放在地址連續(xù)的存儲單元中，其數(shù)據(jù)元素之間的邏輯關(guān)系和物理位置一致。

（a1,a2,a3,……,an）順序存儲結(jié)構(gòu)

鏈?zhǔn)酱鎯Y(jié)構(gòu)是把數(shù)據(jù)元素存放在任意的存儲單元中，這組存儲單元可以連續(xù)也可以不連續(xù)。其數(shù)據(jù)元素之間的物理位置不能反映其邏輯關(guān)系，用指針來反映數(shù)據(jù)元素之間的邏輯關(guān)系。鏈?zhǔn)酱鎯Y(jié)構(gòu)例如，百家姓的部分姓氏表(zhao,qian,sun,li,zhou,wu,zheng,wang)，是一個線性結(jié)構(gòu)，用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲，數(shù)據(jù)類型是指一個值的集合和定義在這個值集上的一組操作的總稱。1.4抽象數(shù)據(jù)類型1、數(shù)據(jù)類型

數(shù)據(jù)類型決定了數(shù)據(jù)占內(nèi)存的字節(jié)數(shù)、數(shù)據(jù)的取值范圍、可進(jìn)行的操作。例如，C語言中

inta,b;規(guī)定了變量a、b在內(nèi)存中所占的字節(jié)數(shù)、取值范圍以及施加于a、b上的運(yùn)算。在使用int類型時，既不需要了解在計算機(jī)內(nèi)部是如何表示的，也不需要知道其操作如何實(shí)現(xiàn)。如a?+?b，設(shè)計者僅僅關(guān)注其“數(shù)學(xué)上求和”的抽象特征。我們可以將數(shù)據(jù)類型進(jìn)一步抽象，即抽象數(shù)據(jù)類型。

抽象數(shù)據(jù)類型(AbstractDataType，ADT)是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。

是將“數(shù)據(jù)”、“結(jié)構(gòu)”、“處理操作”封裝在一起而形成的復(fù)合體。抽象數(shù)據(jù)類型實(shí)際上就是對數(shù)據(jù)結(jié)構(gòu)的邏輯定義。例如，將與有序表有關(guān)的數(shù)據(jù)和處理操作封裝成一個ADT，包含數(shù)據(jù)元素及其關(guān)系，操作有初始建表、插入、刪除、查找，其描述如下：ADTOrdList//OrdList為抽象數(shù)據(jù)類型的名字

{數(shù)據(jù)對象：D?=?{ai|ai∈ElemSet,i=1,2,…,n,n≥0}//ElemSet為數(shù)據(jù)元素集合數(shù)據(jù)關(guān)系：R?=?{<ai-1,ai>|ai-1,ai∈D,i=2,…,n}

基本操作：

InitList(&L) //構(gòu)造一個空的有序表LListLength(L) //輸出L中數(shù)據(jù)元素個數(shù)

LocateElem(L,e) //在表L中查找與給定值e相等的元素

ListInsert(&L,i,e) //在表L中第i個位置之前插入新的數(shù)據(jù)元素eListDelete(*L,i,*e) //刪除表L的第i個數(shù)據(jù)元素

}ADTOrdList2、抽象數(shù)據(jù)類型

實(shí)現(xiàn)ADT的方法有三種：封裝法、分散法、半封裝法。

封裝法：數(shù)據(jù)及其操作封裝成一個整體，比如C++?中的類。分散法：將數(shù)據(jù)和處理數(shù)據(jù)的函數(shù)各自分開。無法從程序的物理結(jié)構(gòu)(即代碼的物理次序)上區(qū)分哪些數(shù)據(jù)和函數(shù)屬于哪個ADT。例如，用一個數(shù)組elem[?]存儲棧中的元素，再用一個整型變量top表示棧頂位置，其操作用一個一個的函數(shù)實(shí)現(xiàn)。

datatypeelem[MAXSIZE];inttop;

半封裝法：將數(shù)據(jù)和為處理數(shù)據(jù)需要而定義的相關(guān)變量封裝在一起形成一個結(jié)構(gòu)，有關(guān)處理函數(shù)定義在結(jié)構(gòu)之外。這種方法僅做到了對數(shù)據(jù)存儲結(jié)構(gòu)的封裝，其特點(diǎn)介于封裝法和分散法之間。例如，實(shí)現(xiàn)棧的抽象數(shù)據(jù)類型時，我們把存儲棧中元素的數(shù)組elem[]?和棧頂位置變量top封裝在一起，其操作函數(shù)實(shí)現(xiàn)如下：

#defineMAXSIZE<最大元素數(shù)>typedefstruct{datatypeelem[MAXSIZE];inttop;}SeqStack3、抽象數(shù)據(jù)類型的實(shí)現(xiàn)方法

用C語言編寫程序計算1?+?2?+?3?+?4?+?…?+?100，大家都會寫出這樣一段代碼：

main(){inti,sum=0,n=100;

for(i=1;i<n;i++)sum=sum+i;printf(″%d″,sum);

}這是最簡單的一個計算機(jī)程序，它就是一種算法。這個算法效率怎樣呢?實(shí)際上對于這個問題，據(jù)說高斯在上小學(xué)時就給出了一個高效算法：

sum?=1?+??2??+??3??+…+100sum?=?100+?99?+?98?+…+12*sum=?101?+?101?+?101?+…+?101

共100個所以sum=5050。1.5算法程序如下：

main(){inti,sum=0,n=100;

sum=(1+100)*100/2;printf(″%d″,sum);

}(1)有窮性：有限步驟之內(nèi)完成,不能形成無窮循環(huán)。(2)確定性：每一個步驟必須有確定含義,無二義性。(3)可行性：操作可通過已實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次完成。(4)輸入：有多個或0個輸入。(5)輸出：至少有一個或多個輸出。

算法是對特定問題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個或多個操作。算法的特性1.5.1算法的基本概念

算法的含義與程序十分相似，但又有區(qū)別。一個程序不一定滿足有窮性。例如操作系統(tǒng)，只要整個系統(tǒng)不遭破壞，它將永遠(yuǎn)不會停止，即使沒有作業(yè)需要處理，它仍處于動態(tài)等待中，因此操作系統(tǒng)不是一個算法。另一方面，程序中的指令必須是機(jī)器可執(zhí)行的，而算法中的指令則無此限制。算法代表了對問題的求解過程，而程序則是算法在計算機(jī)上的特定的實(shí)現(xiàn)。一個算法若用程序設(shè)計語言來描述，則它就是一個程序。算法與數(shù)據(jù)結(jié)構(gòu)是相輔相成的。解決某一特定類型問題的算法可以選定不同的數(shù)據(jù)結(jié)構(gòu)，而且選擇恰當(dāng)與否直接影響算法的效率；反之，一種數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣由各種算法的執(zhí)行效果來體現(xiàn)。算法與程序算法要求：正確、可讀、健壯、高效率低存儲

(1)正確。

算法“正確”的含義大體上可分為四個層次：一是所設(shè)計的程序沒有語法錯誤；二是所設(shè)計的程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；三是所設(shè)計的程序?qū)τ诰倪x擇的典型、苛刻而且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得到滿足要求的結(jié)果；四是所設(shè)計的程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足要求的結(jié)果。對于這四層含義，其中達(dá)到第四層含義下的正確是極其困難的。一般情況下，以達(dá)到第三層含義的正確性作為衡量一個程序是否正確的標(biāo)準(zhǔn)。例如，要求n個數(shù)的最大值問題，算法如下：

max:=0;for(i=1;i<=n;i++)

{scanf(″%f″,&x);

if(x>max)max=x;

}

此算法無語法錯誤，請考慮，如果輸入的數(shù)全為負(fù)數(shù)時，會產(chǎn)生什么結(jié)果?其正確性達(dá)到了第幾層。算法要求：正確、可讀、健壯、高效率低存儲

(2)可讀。算法首先應(yīng)該便于人們理解和相互交流，其次才是機(jī)器可執(zhí)行。所以一個算法應(yīng)當(dāng)思路清晰，層次分明，簡單明了，易讀易懂。

(3)健壯。作為一個好的算法，當(dāng)輸入不合法數(shù)據(jù)時，應(yīng)能適當(dāng)?shù)刈龀稣_反應(yīng)或進(jìn)行相應(yīng)的處理，而不至于產(chǎn)生一些莫名其妙的輸出結(jié)果。

(4)高效率低存儲。算法效率通常指算法的執(zhí)行時間。對于同一個問題如果有多個算法可以解決，執(zhí)行時間短的算法其效率高。所謂存儲量的要求，是指算法在執(zhí)行過程中所需要的最大存儲空間。這兩者都與問題規(guī)模有關(guān)。1.5.2算法的性能評價

算法的時間復(fù)雜度與空間復(fù)雜度

1.算法效率的度量方法算法的效率，大都指算法的執(zhí)行時間。其度量方法有兩種：一種方法叫做事后統(tǒng)計法，一種是事前分析估算法。事后統(tǒng)計法：通過設(shè)計好的測試程序和數(shù)據(jù)，利用計算機(jī)計時器對不同算法編制的程序的運(yùn)行時間進(jìn)行比較，從而確定算法效率的高低。這種方法顯然有很大的缺陷：

(1)必須依據(jù)算法編制好程序，這通常需要花費(fèi)大量的時間和精力，如果編制出來之后發(fā)現(xiàn)有很大缺陷，就會前功盡棄。

(2)時間的比較依賴于計算機(jī)硬件和軟件的環(huán)境因素，有時會遮蓋算法本身的優(yōu)劣。

(3)算法的測試數(shù)據(jù)設(shè)計困難，并且程序運(yùn)行時間往往還與測試數(shù)據(jù)規(guī)模有很大關(guān)系，效率高的算法在小規(guī)模的測試數(shù)據(jù)面前往往得不到體現(xiàn)。比如，10個數(shù)字的排序，不管用什么算法，差異幾乎為零。而如果有一百萬個隨機(jī)數(shù)字排序，那不同的算法差異就非常大。那么我們?yōu)榱吮容^算法，到底用多少數(shù)據(jù)來測試，這是很難判斷的問題。事前分析估算法：在計算機(jī)程序編制前，依據(jù)統(tǒng)計方法對算法進(jìn)行估算。經(jīng)過分析發(fā)現(xiàn)，一個用高級程序設(shè)計語言編寫的程序在計算機(jī)上運(yùn)行時所消耗的時間取決于下列因素：

(1)算法采用的策略、方法；

(2)編譯產(chǎn)生的代碼質(zhì)量；

(3)問題的輸入規(guī)模；

(4)機(jī)器執(zhí)行指令的速度。上述第(1)條當(dāng)然是算法好壞的根本，第(2)條是要系統(tǒng)軟件來支持，第(4)條要看硬件性能。如果拋開與計算機(jī)相關(guān)的軟、硬件因素，一個特定算法的運(yùn)行工作量的大小就只依賴于問題的規(guī)模(通常用正整數(shù)n表示)，或者說它是問題規(guī)模的函數(shù)。所謂問題的規(guī)模，就是指輸入量的大小。一個算法是由一條條指令構(gòu)成的，算法的指令通常稱為語句。所以，算法的執(zhí)行時間和算法中所有語句執(zhí)行次數(shù)的總和成正比。再來看看我們上節(jié)舉的例子，求1?+?2?+?3?+?4?+?…?+?100。用第一種方法：

main(){inti,sum=0,n=100; /*執(zhí)行1次*/for(i=1;i<=n;i++) /*執(zhí)行n+1次*/sum=sum+i; /*執(zhí)行n次*/printf(″%d″,sum); /*執(zhí)行1次*/}用第二種方法：

main(){inti,sum=0,n=100; /*執(zhí)行1次*/sum=(1+100)*100/2; /*執(zhí)行1次*/printf(″%d″,sum); /*執(zhí)行1次*/}那么，第一種算法執(zhí)行時間為1

+

(n

+

1)

+

n

+

1

=

2n

+

3而第二種算法執(zhí)行時間是1

+

1

+

1

=

3

事實(shí)上兩種算法的第一句和最后一句是一樣的，我們關(guān)注的代碼其實(shí)是中間的那部分，我們把循環(huán)看做一個整體，忽略頭尾循環(huán)判斷的開銷，那么這兩個算法其實(shí)就是n和1的差距。算法好壞顯而易見了

兩個n×n階矩陣相乘的算法。1for(i=0;i<n;i++) /*執(zhí)行n+1次*/2for(j=0;j<n;j++) /*執(zhí)行n*(n+1)次*/3{c[i][j]=0; /*執(zhí)行n2次*/4for(k=0;k<n;k++) /*執(zhí)行n2*(n+1)次*/5c[i][j]=c[i][j]+a[i][k]*b[k][j]; /*執(zhí)行n3次*/6}

上述算法中語句的總的執(zhí)行次數(shù)為2n3?+?3n2?+?2n?+?1。顯然，算法執(zhí)行時間與語句的執(zhí)行次數(shù)成正比，我們可以用語句的執(zhí)行次數(shù)來描述算法的執(zhí)行時間?？梢钥闯?，算法的執(zhí)行時間是問題規(guī)模n的函數(shù)f(n)，n就是給定的問題規(guī)模。2.算法時間復(fù)雜度算法:控制結(jié)構(gòu)(順序、分支、循環(huán))+原操作算法執(zhí)行時間取決于兩者的綜合效果。

以原操作重復(fù)執(zhí)行的次數(shù)作為算法的時間度量。

一般情況下，算法中原操作重復(fù)執(zhí)行的次數(shù)是規(guī)模n的某個函數(shù)T(n)。引入漸進(jìn)時間復(fù)雜度在數(shù)量上估計一個算法的執(zhí)行時間算法中語句的執(zhí)行次數(shù)T(n)，它是關(guān)于問題規(guī)模n的函數(shù)，進(jìn)而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級(orderofmagnitude)。記作：

T(n)?=?O(f(n))

表示隨問題規(guī)模n的增大，算法的執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。表1.12n2、3n?+?1、2n2?+?3n?+?1的增長率次數(shù)算法A(2n2)算法B(3n?+?1)算法C(2n2?+?3n?+?1)n?=?1246n?=?28715n?=?1020031231n?=?10020?00030120?301n?=?10002?000?00030012?003?001n?=?10?000200?000?00030?001200?030?001n?=?100?00020?000?000?000300?00120?000?300?001n?=?1000?0002?000?000?000?0003?000?0012?000?003?000?001從表1.1的數(shù)據(jù)變化可以清楚地看到，當(dāng)n值越來越大時，3n?+?1的增長和2n2相差甚遠(yuǎn)，最終幾乎可以忽略不計。也就是說，隨著n的增大，2n2趨近于2n2?+?3n?+?1。結(jié)論：如果得出了基本操作執(zhí)行的次數(shù)的函數(shù)f(n)，判斷一個算法效率時，函數(shù)f(n)中的常數(shù)和其他次要項(xiàng)常?？梢院雎?，關(guān)注最高階的項(xiàng)即可。下面給出推導(dǎo)大O方法。第一步，找到原操作的執(zhí)行次數(shù)。第二步，用常數(shù)1取代運(yùn)行時間中的所有加法常數(shù)。第三步，在修改后的執(zhí)行次數(shù)中，只保留最高階項(xiàng)。第四步，如果最高階項(xiàng)存在與這個項(xiàng)相乘的常數(shù)，則去掉這個常數(shù)。這樣就可得到大O階。

(1)順序結(jié)構(gòu)的時間復(fù)雜度。

inti,sum=0,n=100; /*執(zhí)行1次*/sum=(1+100)*100/2; /*執(zhí)行1次*/printf(″%d″,sum); /*執(zhí)行1次*/這個算法的運(yùn)行次數(shù)為f(n)?=?3。順序結(jié)構(gòu)、分支結(jié)構(gòu)的程序，不管代碼有多少行，執(zhí)行次數(shù)不會隨著n的變化而發(fā)生變化，它與問題規(guī)模n的大小無關(guān)，執(zhí)行次數(shù)是恒定的，我們用O(1)來表示其時間復(fù)雜度。通常稱之為常量階。(2)單循環(huán)結(jié)構(gòu)的時間復(fù)雜度。

for(i=1;i<n;i++) /*執(zhí)行n+1次*/sum=sum+i; /*原操作執(zhí)行n次*/其時間復(fù)雜度為O(n)，我們稱之為線性階。(3)多重循環(huán)結(jié)構(gòu)的時間復(fù)雜度。

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

/*執(zhí)行n+1次*/for(j=1;j<=n;j++) /*執(zhí)行n+1次*/x=x+1; /*原操作執(zhí)行n2次*/其時間復(fù)雜度為O(n2)，我們稱之為平方階。如果是三重循環(huán)，其時間復(fù)雜度為O(n3)，我們稱之為立方階，以此類推。當(dāng)i

=

0時，內(nèi)循環(huán)執(zhí)行了n次，當(dāng)i

=

1時，內(nèi)循環(huán)執(zhí)行了n-1次……當(dāng)i

=

n-1時，執(zhí)行1次。所以總的執(zhí)行次數(shù)為n

+

(n-1)

+

(n-2)

+

…

+

1

=

n(n+1)/2

=

n2/2

+

n/2。用推導(dǎo)大O階的方法，第一，n2/2

+

n/2沒有加數(shù)常數(shù)，可以不予考慮；第二，保留最高項(xiàng)n2/2；第三，去掉這個項(xiàng)相乘的常數(shù)，最終得到n2，所以，這段代碼的時間復(fù)雜度為O(n2)。

inti,j;for(i=0;i<n;i++)for(j=i;j<n;j++)

x=x+1;/*原操作*/(4)下面代碼時間復(fù)雜度又是多少?

intc=1;

while(c<n)

c=c*2;/*原操作*/

由于每次c乘以2之后，就離n更近，也就是說，多少個2相乘后大于n，才會退出循環(huán)。由2x

=

n得到x

=

lb

n?？梢缘贸?，循環(huán)的執(zhí)行次數(shù)為lb

n，時間復(fù)雜度為O(lb

n)。我們稱之為對數(shù)階。(5)遞歸程序的時間復(fù)雜度的分析。

intBinrec(intn)

{ifn=1

return1;

else

returnBinrec(n/2)+1;/*原操作*/

}用A(n)表示所做的加法次數(shù)，建立遞推關(guān)系如下:設(shè)n?=?2k，當(dāng)k?>?0時，A(2k)?=?A(2k-1)?+?1?=?[A(2k-2)?+?1]?+?1?=?A(2k-2)?+?2=?…?=?A(2k-i)?+?i?=?…?=?A(2k-k)?+?k?=?k

因?yàn)閚?=?2k，所以k?=?lb?n。因此A(n)?=?lb?n。其時間復(fù)雜度為

O(lb?n)

我們稱之為對數(shù)階。常用的時間復(fù)雜度：常量階O(1)、線性階O(n)、平方階O(n2)、對數(shù)階O(lb?n)。此外，算法還能呈現(xiàn)的時間復(fù)雜度有二維階O(n?lb?n)、立方階O(n3)、指數(shù)階O(2n)、階乘階O(n!)等，數(shù)據(jù)結(jié)構(gòu)中常用的時間復(fù)雜度關(guān)系如下：O(1)?<?O(lb?n)?<?O(n)?<?O(n?lb?n)?<?O(n2)?<?O(n3)?<?O(2n)?<?O(n!)?<?O(nn)常見的T(n)隨著問題規(guī)模n不斷增大時的變化情況。3.算法的最優(yōu)、最差與平均時間復(fù)雜度

算法的效率不僅依賴于問題的規(guī)模，還與問題的初始輸入數(shù)據(jù)集有關(guān)。例如，在數(shù)組a[1..n]?中查找值為k的元素，若找到，則輸出位置i(1≤i≤n)；否則輸出0。算法描述如下：

i=n;

while(i>0)&&(a[i]!=k)

i=i-1;printf(″%d″,i);while循環(huán)的執(zhí)行次數(shù)不僅與問題規(guī)模有關(guān)，還與k和數(shù)組a中各分量的取值有關(guān)。最壞情況下，即數(shù)組a中不含值為k的元素，while循環(huán)執(zhí)行n次；最好情況下，即數(shù)組中值為k的元素為a[n]，while循環(huán)執(zhí)行1次；平均情況下，while循環(huán)執(zhí)行(n+1)/2次，時間復(fù)雜度為線性階。

最優(yōu)時間復(fù)雜度是指在輸入規(guī)模為n時，算法在最優(yōu)情況下的時間復(fù)雜度。最差時間復(fù)雜度是指在輸入規(guī)模為n時，算法在最差情況下的時間復(fù)雜度。最差情況的運(yùn)行時間是一種保證，那就是運(yùn)行時間將不會再壞了。平均時間復(fù)雜度是指在“典型”或“隨機(jī)”輸入的情況下，算法具有的時間復(fù)雜度。平均時間復(fù)雜度是從概率的角度進(jìn)行分析的，研究它的直接方法就是將規(guī)模為n的實(shí)例劃分為幾種類型，需要得到或者假設(shè)各種輸入類型的概率分布，以便推導(dǎo)出基本操作的平均執(zhí)行次數(shù)。但是，這個方案的技術(shù)實(shí)現(xiàn)一般都不簡單，而且在各種特定的情況下，它所包含的概率假設(shè)也往往很難驗(yàn)證。

本書中如不作特殊說明，所討論的各種算法的時間復(fù)雜度均指最壞情況下的時間復(fù)雜度。4.空間復(fù)雜度123…n-2n-1na[1]a[2]a[3]…a[n-2]a[n-1]a[n]

類似于算法的時間復(fù)雜度，采用空間復(fù)雜度作為算法所需存儲空間的量度，記作：S(n)?=?O(f(n))其中n為問題的規(guī)模。在存儲空間使用方面，對于處理同一問題的不同算法，其對存儲空間的需求有較大的差異。例如：將存放在一維數(shù)組a中的n個整數(shù)反向存放，即原始數(shù)組a為反向存放后數(shù)組a為123…n-2n-1na[n]a[n-1]a[n-2]…a[3]a[2]a[1]

對于這一問題，可以用一組工作單元，即設(shè)置一個數(shù)組b[1..n]算法實(shí)現(xiàn)：

for(i=1;i<=n;i++)b[n-i+1]=a[i];for(i=1;i<=n;i++)a[i]=b[i];但也可以只使用一個工作單元temp，算法如下：

for(i=1;i<=n/2;i++){temp=a[i];a[i]=a[n-i+1];a[n-i+1]=temp;}顯然，采用后一種算法比前一種算法所需的存儲空間要節(jié)省得多。

一個程序的空間復(fù)雜度是指程序運(yùn)行從開始到結(jié)束所需的存儲量。程序的一次運(yùn)行是針對所求解的問題的某一特定實(shí)例而言的。程序運(yùn)行所需的存儲空間包括以下兩部分：

(1)固定部分。這部分空間與所處理數(shù)據(jù)的大小和個數(shù)無關(guān)，或者稱與問題的實(shí)例的特征無關(guān)。主要包括程序代碼、常量、簡單變量、定長成分的結(jié)構(gòu)變量所占的空間。

(2)可變部分。這部分空間大小與算法在某次執(zhí)行中處理的特定數(shù)據(jù)的大小和規(guī)模有關(guān)。例如，100個數(shù)據(jù)元素的排序算法與1000個數(shù)據(jù)元素的排序算法所需的存儲空間顯然是不同的。

1.5.3算法描述

常用的算法描述方法有如下幾種：

(1)使用自然語言。

(2)使用流程圖。

(3)使用某種程序設(shè)計語言。

(4)使用類程序設(shè)計語言。本書采用類C語言作為算法描述工具，類C語言是一種偽碼語言。1.“數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計”課程的地位是計算機(jī)專業(yè)中的一門專業(yè)基礎(chǔ)必修課,是一門理論與實(shí)踐相結(jié)合的課程。它是程序設(shè)計(特別是非數(shù)值計算的程序設(shè)計)的基礎(chǔ)，也是設(shè)計和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。因此，“數(shù)據(jù)結(jié)構(gòu)”是數(shù)學(xué)、計算機(jī)硬件、計算機(jī)軟件三者之間的一門核心課程，是提高學(xué)生軟件設(shè)計水平的一門關(guān)鍵課程。該課程多年來一直是計算機(jī)相關(guān)專業(yè)研究生考試必考專業(yè)課之一，是反映學(xué)生數(shù)據(jù)抽象能力、編程能力的重要體現(xiàn)。1.6“數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計”課程的地位及主要內(nèi)容2.“數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計”課程的主要內(nèi)容名稱特點(diǎn)存儲結(jié)構(gòu)線性表數(shù)據(jù)元素之間的關(guān)系是一對一順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)棧插入操作和刪除操作位置在線性表的一端進(jìn)行，具有先進(jìn)后出的特點(diǎn)順序棧、鏈棧隊列插入操作在線性表的一端、刪除操作在線性表的另一端進(jìn)行，具有后進(jìn)先出的特點(diǎn)順序隊列、鏈隊列、循環(huán)隊列串

數(shù)據(jù)元素是字符的線性表，操作對象是數(shù)據(jù)元素的序列順序串、塊鏈結(jié)構(gòu)、堆存儲串?dāng)?shù)組線性表的推廣，數(shù)據(jù)元素可以是一個表，如二維數(shù)組、三維數(shù)組……

以行為主序或者以列為主序的順序存儲。特殊矩陣的壓縮存儲；稀疏矩陣的三元組表存儲、十字鏈表存儲廣義表

線性表的推廣，數(shù)據(jù)元素可以是一個表，也可以是一個元素

廣義表鏈?zhǔn)酱鎯?/p>