數(shù)據(jù)結(jié)構(gòu)第一章緒論

數(shù)據(jù)結(jié)構(gòu)新疆大學(xué)軟件學(xué)院孫華

電話-mail:xj_sh@163.com2015-2016學(xué)年第一學(xué)期

使用教材：嚴(yán)蔚敏吳偉民編著，數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)出版社參考書：1、曹桂琴編著，數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，大連理工大學(xué)出版社。2、晉良穎編，數(shù)據(jù)結(jié)構(gòu)，人民郵電出版社3、BrunoR.Preiss，數(shù)據(jù)結(jié)構(gòu)與算法，電子工業(yè)出版社使用教材及參考書課程教學(xué)目的在計(jì)算機(jī)及其應(yīng)用的各個(gè)領(lǐng)域中，都會(huì)用到各種各樣的數(shù)據(jù)結(jié)構(gòu)，通過本課程使學(xué)生學(xué)會(huì)分析和研究計(jì)算機(jī)加工對(duì)象的特性，選擇合適的數(shù)據(jù)結(jié)構(gòu)和存儲(chǔ)表示，以及編制相應(yīng)的實(shí)現(xiàn)算法．課程教學(xué)基本要求:本課程介紹各種最常用的數(shù)據(jù)結(jié)構(gòu)，闡述各種數(shù)據(jù)結(jié)構(gòu)內(nèi)涵的邏輯關(guān)系，討論它們?cè)谟?jì)算機(jī)中的存儲(chǔ)表示，以及在這些數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算和實(shí)際的執(zhí)行算法，并對(duì)算法的效率進(jìn)行簡(jiǎn)要的分析和討論。數(shù)據(jù)結(jié)構(gòu)的研究不僅涉及到計(jì)算機(jī)硬件（特別是編碼理論、存儲(chǔ)裝置和存取方法）的研究范圍，而且和計(jì)算機(jī)軟件的研究有著密切的關(guān)系，無論是編譯程序還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲(chǔ)器中的分配問題。在研究信息檢索時(shí)也必須考慮如何組織數(shù)據(jù)，以便查找和存取數(shù)據(jù)元素更為方便。課程介紹數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。程序＝算法＋數(shù)據(jù)結(jié)構(gòu)目前在我國(guó)，《數(shù)據(jù)結(jié)構(gòu)》已經(jīng)不僅僅是計(jì)算機(jī)專業(yè)的教學(xué)計(jì)劃中的核心課程之一，而且是其它非計(jì)算機(jī)專業(yè)的主要選修課程之一。通過對(duì)這門課程的學(xué)習(xí)可增強(qiáng)選擇合適的數(shù)據(jù)結(jié)構(gòu)與編寫高效的程序的能力。課程介紹教學(xué)安排及考試講課學(xué)時(shí)：50學(xué)時(shí)上機(jī)時(shí)間：4次（共8學(xué)時(shí)）考試成績(jī)計(jì)算：平時(shí)成績(jī)（考勤、作業(yè)及上機(jī)）30分考試（70分）

目錄第1章緒論第2章線性表第3章棧和隊(duì)列第4章串第5章數(shù)組和廣義表第6章樹和二叉樹第7章圖第8章查找第9章內(nèi)部排序第10章文件計(jì)算機(jī)的應(yīng)用已不再局限于科學(xué)計(jì)算，而更多地用于控制、管理及數(shù)據(jù)處理等非數(shù)值計(jì)算的處理工作。與此對(duì)應(yīng)，計(jì)算機(jī)加工處理的對(duì)象由純粹的數(shù)值發(fā)展到字符、表格和圖像等各種具有一定結(jié)構(gòu)的數(shù)據(jù)。為了編寫出一個(gè)“好”的程序，必須分析待處理的對(duì)象的特征以及各對(duì)象之間存在的關(guān)系，這就是“數(shù)據(jù)結(jié)構(gòu)”這門學(xué)科形成和發(fā)展的背景。第一章緒論第一章緒論用計(jì)算機(jī)解決一個(gè)具體問題時(shí)，大致需要經(jīng)多下列幾個(gè)步驟：首先要從具體問題抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法，最后編出程序、進(jìn)行測(cè)試、調(diào)整直至得到最終解答。尋求數(shù)學(xué)模型的實(shí)質(zhì)是分析問題，從中提取操作的對(duì)象，并找出這些操作對(duì)象之間含有的關(guān)系，然后用數(shù)學(xué)的語言加以描述。然而，更多的非數(shù)值問題無法用數(shù)學(xué)方程描述。什么是數(shù)據(jù)結(jié)構(gòu)呢？先看以下幾個(gè)例子。1.1什么是數(shù)據(jù)結(jié)構(gòu)書目文件按書名按作者名按分類號(hào)索引表線性表例1書目自動(dòng)檢索系統(tǒng)登錄號(hào)：書名：作者名：分類號(hào)：出版單位：出版時(shí)間：價(jià)格：書目卡片樹……..……..…...…...…...…...例2人機(jī)對(duì)奕問題對(duì)于一個(gè)多叉路口，設(shè)計(jì)一個(gè)交通信號(hào)燈的管理系統(tǒng)。首先需要分析一下所有車輛的行駛路線的沖突問題。這個(gè)問題可以歸結(jié)為對(duì)車輛的可能行駛方向作某種分組，對(duì)分組的要求是使任一個(gè)組中各個(gè)方向行駛的車輛可以同時(shí)安全行駛而不發(fā)生碰撞。CEDAB例3多叉路口交通燈管理問題可通行方向ABACADBABCBDDADBDCEAEBECEDCEDAB例3多叉路口交通燈管理問題有些通行方向顯然不能同時(shí)進(jìn)行，相應(yīng)的結(jié)點(diǎn)間畫一條連線。ABACADBABCBDDADBDCEAEBECED圖1.2交叉路口的圖示模型CEDAB圖把圖1.2中的結(jié)點(diǎn)進(jìn)行分組，使得有結(jié)點(diǎn)相連的結(jié)點(diǎn)不在同一個(gè)組里。

地圖著色問題如果把上圖中的一個(gè)結(jié)點(diǎn)理解為一個(gè)國(guó)家，結(jié)點(diǎn)之間的連線看作兩國(guó)有共同邊界，上述問題就變成著名的“著色問題”：即求出最少要幾種顏色可將圖中所有國(guó)家著色，使得任意兩個(gè)相鄰的國(guó)家顏色都不相同。通過上面的分析，我們就獲得了該交通管系統(tǒng)的數(shù)學(xué)模型。下面就可以著手進(jìn)行算法的設(shè)計(jì)。例3多叉路口交通燈管理問題算法設(shè)計(jì)2.“貪心法”

while有結(jié)點(diǎn)未著色；{選擇一種新顏色；

在未著色的結(jié)點(diǎn)中,給盡可能多的彼此結(jié)點(diǎn)之間沒有邊點(diǎn)著色；}1.對(duì)n個(gè)結(jié)點(diǎn)，逐個(gè)測(cè)試其所有組合；例3多叉路口交通燈管理問題ABACADBABCBDDADBDCEAEBECED圖1.2交叉路口的圖示模型圖ABACADBABCBDDADBDCEAEBECEDCEDAB著色結(jié)果把上面方法應(yīng)用于圖1.2，得到下面的分組：

綠色：AB,AC,AD,BA,DC,ED

藍(lán)色：BC,BD,EA

紅色：DA,DB

白色：EB,EC例3多叉路口交通燈管理問題描述非數(shù)值計(jì)算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)它們之間相互關(guān)系，并對(duì)這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算，而且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。第一章緒論數(shù)據(jù)(Data):是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。對(duì)計(jì)算機(jī)科學(xué)而言，數(shù)據(jù)的含義極為廣泛，如圖像、聲音等都可以通過編碼而歸之于數(shù)據(jù)的范疇。數(shù)據(jù)元素(DataElement):是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。例如，例1－2中的“樹”中的一個(gè)棋盤格局，例1－3中的“圖”中的一個(gè)園圈都被稱為一個(gè)數(shù)據(jù)元素。1.2基本概念和術(shù)語一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。例如，例1－1中一本書的書目信息為一個(gè)數(shù)據(jù)元素，而書目信息中的每一項(xiàng)（如書名、作者名等）為一個(gè)數(shù)據(jù)項(xiàng)。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)對(duì)象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如，整數(shù)數(shù)據(jù)對(duì)象是集合N＝{0，±1，±2，…}，字母字符數(shù)據(jù)對(duì)象是集合C＝{A，B，C，…}。數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。1.2基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)主要指邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。通常分為四類基本結(jié)構(gòu)：一、集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。二、線性結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。三、樹型結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。四、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。1.2基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組：

Data-Structure=(D，S)其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。例復(fù)數(shù)的數(shù)據(jù)結(jié)構(gòu)定義如下：Complex=(C，R)其中：C是含兩個(gè)實(shí)數(shù)的集合﹛C1，C2﹜，分別表示復(fù)數(shù)的實(shí)部和虛部。R={P}，P是定義在集合上的一種關(guān)系{〈C1，C2〉}。1.2基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱為存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中有兩種不同的表示方法：

順序表示和非順序表示由此得出兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu):用數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放地址的指針，用此指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。1.2基本概念和術(shù)語元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲(chǔ)1536元素21400元素11346元素3∧元素41345h存儲(chǔ)地址

存儲(chǔ)內(nèi)容

指針1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

鏈?zhǔn)酱鎯?chǔ)

h

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等

線性結(jié)構(gòu)

非線性結(jié)構(gòu)

順序存儲(chǔ)

鏈?zhǔn)酱鎯?chǔ)線性表?xiàng)ｊ?duì)樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：1.2基本概念和術(shù)語數(shù)據(jù)類型：數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集范圍上的一組操作的總稱。例如，C語言中的整型變量，其值集為某個(gè)區(qū)間上的整數(shù)，定義在其上的操作為：加、減、乘、除和取模等算術(shù)運(yùn)算。按“值”的不同特性，高級(jí)程序語言中的數(shù)據(jù)類型可分為：一類是非結(jié)構(gòu)的原子類型。原子類型的值是不可分解的。如：C語言中的基本類型（整型、實(shí)型、字符型和枚舉類型）、指針類型和空類型。另一類是結(jié)構(gòu)類型。結(jié)構(gòu)類型的值是由若干成分按某種結(jié)構(gòu)組成的。例如數(shù)組的值由若干分量組成。每個(gè)分量可以是整數(shù)，也可以是數(shù)組等。1.2基本概念和術(shù)語抽象數(shù)據(jù)類型：一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部的使用。抽象數(shù)據(jù)類型實(shí)際上就是對(duì)該數(shù)據(jù)結(jié)構(gòu)的定義。因?yàn)樗x了一個(gè)數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)上的一組算法。和數(shù)據(jù)結(jié)構(gòu)的形式定義相對(duì)應(yīng)，抽象數(shù)據(jù)類型可用三元組描述如下：（Ｄ，Ｓ，Ｐ）D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。1.2基本概念和術(shù)語本書采用以下格式定義抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的定義：

ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象的定義>

數(shù)據(jù)關(guān)系：<數(shù)據(jù)邏輯關(guān)系的定義>

基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名基本操作的定義格式為：

基本操作名（參數(shù)表）

初始條件：<初始條件描述>

操作結(jié)果：<操作結(jié)果描述>1.2基本概念和術(shù)語抽象數(shù)據(jù)類型三元組的定義：ADTTriplet{數(shù)據(jù)對(duì)象：D={e1,e2,e3|e1,e2,e3ElemSet}數(shù)據(jù)關(guān)系：R1={<e1,e2>,<e2,e3>}基本操作：InitTriplet(&T,v1,v2,v3)操作結(jié)果：構(gòu)造了三元組T，元素e1,e2和e3分別賦以參數(shù)v1,v2和v3的值。}ADTTriplet1.2基本概念和術(shù)語ADTTriplet{數(shù)據(jù)對(duì)象：D={e1,e2,e3|e1,e2,e3ElemSet}數(shù)據(jù)關(guān)系：R1={<e1,e2>,<e2,e3>}基本操作：Get(T，i，&e)初始條件：三元組T已存在，1i3操作結(jié)果：用e返回T的第i元的值。}ADTTriplet1.2基本概念和術(shù)語抽象數(shù)據(jù)類型可通過固有數(shù)據(jù)類型來表示和實(shí)現(xiàn)，即利用處理器中已存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實(shí)現(xiàn)的操作來組合新的操作。由于本書在高級(jí)程序設(shè)計(jì)語言的虛擬層次上討論抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)，并且討論的數(shù)據(jù)結(jié)構(gòu)及其算法主要是面向讀者，故采用介于偽碼和C語言之間的類C語言作為描述工具，有時(shí)也用偽碼描述一些只含抽象操作的抽象算法。這使得數(shù)據(jù)結(jié)構(gòu)和算法的描述和討論簡(jiǎn)明清晰，不拘泥于C語言的細(xì)節(jié)，又能容易轉(zhuǎn)換成C或者C＋＋程序。1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)本書采用的類C語言精選了C語言的一個(gè)核心子集，同時(shí)作了若干擴(kuò)充，增強(qiáng)了語言的描述功能。以下對(duì)其作簡(jiǎn)要說明。（1）預(yù)定義常量和類型

//函數(shù)結(jié)果狀態(tài)代碼#defineTRUE1#defineFLASE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼

TypedefintStatus;1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)（2）數(shù)據(jù)結(jié)構(gòu)的表示用類型定義（typedef）描述。數(shù)據(jù)元素類型約定為Elemtype，由用戶在使用該數(shù)據(jù)類型時(shí)定義。（3）基本操作的算法都用以下形式的函數(shù)描述：函數(shù)類型

函數(shù)名（函數(shù)參數(shù)表）{//算法說明語句序列}//函數(shù)名

1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)（4）賦值語句有簡(jiǎn)單賦值變量名=表達(dá)式；串值賦值變量名1=變量名2=……=表達(dá)式成組賦值（變量名1，。。。，）=（表達(dá)式1，）交換賦值變量名變量名條件賦值變量名=條件表達(dá)式？表達(dá)式T：表達(dá)式F1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)（5）選擇語句有條件語句1if（表達(dá)式）語句；條件語句2if（表達(dá)式）語句；Else語句開關(guān)語句1switch(表達(dá)式){case值1：語句序列1；break;Default:語句序列n+1;}開關(guān)語句2switch{case條件1：語句序列1；break;Default:語句序列n+1;}1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)（6）循環(huán)語句有For語句for（賦初值表達(dá)式；條件；修改表達(dá)式序列）語句；While語句while（條件）語句；do-while語句do{語句序列}while（條件）；1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)（7）結(jié)束語句函數(shù)結(jié)束語句return表達(dá)式；return；Case結(jié)束語句break;異常結(jié)束語句exit(異常代碼)（8）輸入和輸出語句輸入語句scanf([格式串]，變量1，變量n)；輸出語句printf([格式串]，表達(dá)式1，表達(dá)式2)；1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)（9）注釋單行注釋//文字序列（10）基本函數(shù)有求最大值max(表達(dá)式1，表達(dá)式n）求最小值min(表達(dá)式1，表達(dá)式n）求絕對(duì)值abs(表達(dá)式)求不足整數(shù)值floor（表達(dá)式）判定行結(jié)束eoln（文件變量）或eoln1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)（11）邏輯運(yùn)算約定與運(yùn)算&&:對(duì)于A&&B,當(dāng)A的值為0時(shí),不再對(duì)B求值。或運(yùn)算||：對(duì)于A||B,當(dāng)A的值為非0時(shí),不再對(duì)B求值。1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)例題：抽象數(shù)據(jù)類型Triplet的表示和實(shí)現(xiàn)//--------采用動(dòng)態(tài)分配的順序存儲(chǔ)結(jié)構(gòu)----------------TypedefElemType*Triplet://--------基本操作的函數(shù)原形說明----------------//initTriplet分配三個(gè)元素存儲(chǔ)空間StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3）；//操作結(jié)果：構(gòu)造了三元組T，元素e1，e2和e3分別賦以參數(shù)v1，v2和v3的值。1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)StatusDestroyTriplet(Triplet&T）；//操作結(jié)果：三元組T被消除。StatusGet(Triplet&T，inti，ElemType&e）；//初始條件：三元組T已存在，1i3。

//操作結(jié)果：用e返回T的第i元的值。1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)//--------基本操作的實(shí)現(xiàn)----------------StatusGet(Triplet&T，inti，ElemType&e）{//1i3,用e返回T的第i元的值。

If(i<1||i>3)returnERROR;e=T[i-1]；

returnOK;}//Get}ADTTriplet1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)算法是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，每一條指令表示一個(gè)或多個(gè)操作。算法有五個(gè)特性：1.4算法和算法分析（1）有窮性一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。（2）確定性算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個(gè)入口和一個(gè)出口。（3）可行性一個(gè)算法是可行的。即算法描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。（4）輸入一個(gè)算法有零個(gè)或多個(gè)輸入。（5）輸出一個(gè)算法有一個(gè)或多個(gè)輸出。評(píng)價(jià)一個(gè)好的算法有以下幾個(gè)標(biāo)準(zhǔn):（1）正確性（2）可讀性算法應(yīng)該好讀。（3）健狀性算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對(duì)其作出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出結(jié)果。（4）效率與存儲(chǔ)量需求效率是指算法執(zhí)行的時(shí)間；存儲(chǔ)量需求指算法執(zhí)行過程中所需要的最大存儲(chǔ)空間。2、算法設(shè)計(jì)的要求程序不含語法錯(cuò)誤。程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果。程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果。程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明的結(jié)果。正確性（算法應(yīng)滿足具體問題的需求）算法執(zhí)行時(shí)間需要通過依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間度量。度量一個(gè)程序的執(zhí)行時(shí)間通常有兩種方法。事后統(tǒng)計(jì)的方法

一是必須先運(yùn)行依據(jù)算法編制的程序二是所得時(shí)間的統(tǒng)計(jì)量依賴于計(jì)算機(jī)的硬件、軟件等環(huán)境因素求出該算法的一個(gè)時(shí)間界限函數(shù)事前分析估算的方法

依據(jù)的算法選用何種策、問題的規(guī)模、書寫的語言、編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量、機(jī)器執(zhí)行指令的速度。所以，人們常常采用事前分析估算的方法。3、算法效率的度量使用絕對(duì)的時(shí)間單位衡量算法的效率是不合適的。撇開這些與計(jì)算機(jī)硬件軟件有關(guān)的因素，可以認(rèn)為一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量表示），或者說，它是問題規(guī)模的函數(shù)。一個(gè)算法是由控制結(jié)構(gòu)（順序分支和循環(huán)三種）和原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成的，則算法時(shí)間取決于兩者的綜合效果。為了便于比較同一問題的不同算法，通常的做法是，從算法中選取一種對(duì)于研究問題（或算法類型）來說是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度。3、算法效率的度量一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)，算法的時(shí)間度量記作T(n)=O(f(n))它表示隨著問題規(guī)模n的增加，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱作算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。3、算法效率的度量顯然，被稱作問題的基本操作的原操作應(yīng)是其重復(fù)執(zhí)行次數(shù)和算法的執(zhí)行時(shí)間成正比的原操作，多數(shù)情況下它是最深層循環(huán)內(nèi)的語句中的原操作，它的執(zhí)行次數(shù)和包含它的語句的頻度相同。語句的頻度是指的是該語句重復(fù)執(zhí)行的次數(shù)。例２{++x;s=0;}將x自增看成是基本操作，則語句頻度為１，即時(shí)間復(fù)雜度為Ｏ(1)。如果將s=0也看成是基本操作，則語句頻度為２，其時(shí)間復(fù)雜度仍為Ｏ(1)，即常量階。3、算法效率的度量例３、for(i=1;i<=n;++i){++x;s+=x;}語句頻度為：2n

其時(shí)間復(fù)雜度為：O(n)即時(shí)間復(fù)雜度為線性階。例４、for(i=1;i<=n;++i)

for(j=1;j<=n;++j){++x;s+=x;}語句頻度為：2n2時(shí)間復(fù)雜度為：O(n2)即時(shí)間復(fù)雜度為平方階。3、算法效率的度量定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一個(gè)m次多項(xiàng)式，則A(n)=O(nm)。證略。例５for(i=2;i<=n;++I)for(j=2;j<=i-1;++j){++x;a[i，j]=x;}語句頻度為：1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2-3n+2時(shí)間復(fù)雜度為O(n2),

即此算法的時(shí)間復(fù)雜度為平方階。3、算法效率的度量for(i=1;i<=n;++