數(shù)據(jù)結(jié)構(gòu)1-緒論-青島學(xué)院

1、數(shù)據(jù)結(jié)構(gòu)第一章 緒論中國(guó)海洋大學(xué)青島學(xué)院 孫月江Telmail:1.1 什么是數(shù)據(jù)結(jié)構(gòu)1.2 基本概念和術(shù)語(yǔ)1.4 算法和算法分析1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)主要內(nèi)容（4學(xué)時(shí)）：為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)不是教你怎樣才能編程，而是教你怎樣才能編好程;數(shù)據(jù)結(jié)構(gòu)就是教你怎樣用最精簡(jiǎn)的語(yǔ)言，利用最少的資源（包括時(shí)間和空間）編寫出最優(yōu)秀最合理的程序。 數(shù)據(jù)結(jié)構(gòu)存在的意義就是使程序最優(yōu)化。數(shù)據(jù)結(jié)構(gòu)就是編程的思維，編程的靈魂，算法的精髓所在，沒有了數(shù)據(jù)結(jié)構(gòu)，程序就好像一個(gè)空核，是低效率的。 如果把程序看成一輛汽車，那么程序語(yǔ)言就構(gòu)成了這輛車的車身和輪胎。而算法則是這輛車的

2、核心發(fā)動(dòng)機(jī)。這輛車跑得是快是慢，關(guān)鍵就在于發(fā)動(dòng)機(jī)的好壞（當(dāng)然輪胎太爛了也不行），而數(shù)據(jù)結(jié)構(gòu)就是用來改造發(fā)動(dòng)機(jī)的?？梢赃@么說，數(shù)據(jù)結(jié)構(gòu)并不是一門語(yǔ)言，它是一種思想，一種方法，一種思維方式。它并不受語(yǔ)言的限制 。1.1 什么是數(shù)據(jù)結(jié)構(gòu)CS是一門研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。這里面涉及到兩個(gè)問題：信息的表示 ：學(xué)生信息、視頻、圖片等的表示信息的處理：查找、刪除、修改、壓縮、排序等信息的表示和組織直接關(guān)系到處理信息的程序的效率。隨著計(jì)算機(jī)的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，為了編寫出一個(gè)“好”的程序，必須分析待處理的對(duì)象的特征及各對(duì)象

3、之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。一般來講，用計(jì)算機(jī)解決一個(gè)具體問題時(shí)，大致需要下列幾個(gè)步驟：首先從具體問題抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型：分析問題，從中提取操作的對(duì)象，并找出這些對(duì)象之間的關(guān)系，然后用數(shù)學(xué)語(yǔ)言加以描述。然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法最后編出程序、進(jìn)行測(cè)試、調(diào)整直至得到最終答案。 1.1 什么是數(shù)據(jù)結(jié)構(gòu)問題：比如黃蓉遇上神算子瑛姑，給她出的三道題目中有一題是這樣的:今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？也就是說，有一個(gè)未知數(shù)，這個(gè)數(shù)除以三余二，除以五余三，除以七余二，問這個(gè)數(shù)是多少？數(shù)學(xué)模型：線性方程組算法：解方程組編程實(shí)現(xiàn)public

4、 class hr public static void main(String args) for(int x=0;x100;x+) if(x % 3 = 2)&(x % 5 = 3)&(x % 7 = 2) System.out.println(這個(gè)數(shù)字是：); System.out.println(x); 例1-1圖書館的書目檢索系統(tǒng)自動(dòng)化問題001高等數(shù)學(xué)樊映川S01002理論力學(xué)羅遠(yuǎn)祥L(zhǎng)01003高等數(shù)學(xué)華羅庚S01004線性代數(shù)欒汝書S02.高等數(shù)學(xué)001，003理論力學(xué)002,線性代數(shù)004,L002,S001,003,樊映川001,華羅庚003,欒汝書004,圖1.1 圖書目錄

5、文件示例 由這四張表構(gòu)成的文件便是書目自動(dòng)檢索的數(shù)學(xué)模型，計(jì)算機(jī)的主要操作便是按照某個(gè)特定要求對(duì)書目文件進(jìn)行查詢。在這類文檔管理的數(shù)學(xué)模型中，計(jì)算機(jī)處理的對(duì)象之間通常存在著的是一種最簡(jiǎn)單的線性關(guān)系，這類數(shù)學(xué)模型可稱為線性的數(shù)據(jù)結(jié)構(gòu)?！皩W(xué)生”表格9補(bǔ)充：電話號(hào)碼查詢系統(tǒng)設(shè)有一個(gè)電話號(hào)碼薄，它記錄了N個(gè)人的名字和其相應(yīng)的電話號(hào)碼，假定按如下形式安排： (a1，b1)(a2，b2)(an，bn)其中ai，bi(i=1，2n) 分別表示某人的名字和對(duì)應(yīng)的電話號(hào)碼。要求設(shè)計(jì)一個(gè)算法，當(dāng)給定任何一個(gè)人的名字時(shí)，該算法能夠打印出此人的電話號(hào)碼，如果該電話簿中根本就沒有這個(gè)人，則該算法也能夠報(bào)告沒有這個(gè)人的標(biāo)

6、志。上述的問題是一種數(shù)據(jù)結(jié)構(gòu)問題?？蓪⒚趾蛯?duì)應(yīng)的電話號(hào)碼設(shè)計(jì)成：二維數(shù)組、表結(jié)構(gòu)、向量。例1-2 計(jì)算機(jī)和人對(duì)弈算法：?對(duì)弈的規(guī)則和策略棋盤及棋盤的格局(樹)模型：?圖1.2UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖12算法：?通路之間相互矛盾的關(guān)系各種圖模型：?圖1.3例1-3 多叉路口交通燈的管理問題例：鋪設(shè)城市的煤氣管道算法：?模型：?如何規(guī)劃使得總投資花費(fèi)最少？圖概括地說： 數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型(非數(shù)值計(jì)算)及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)”的學(xué)科?；蛘哒f， 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)的發(fā)展歷

7、史1968年美國(guó)唐歐克努特Donald E.Knuth教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系從20世紀(jì)70年代中期到80年代初，各種版本的數(shù)據(jù)結(jié)構(gòu)著作就相繼出現(xiàn)。未來發(fā)展的兩個(gè)方向： （1）面向各專門領(lǐng)域中特殊問題的數(shù)據(jù)結(jié)構(gòu)：多維圖形數(shù)據(jù)結(jié)構(gòu)等 （2）抽象數(shù)據(jù)類型的觀點(diǎn)來討論數(shù)據(jù)結(jié)構(gòu)。The Art of Computer Programming: 1. Fundamental Algorithms; 2. Seminumerical Algorithms; 3. Sorting and Searching；三卷中文名為基本算法、半數(shù)值算法及排序與查找。本書內(nèi)容博大精深，作者因?yàn)槿頃@得美國(guó)計(jì)算機(jī)協(xié)會(huì)

8、1974年圖靈獎(jiǎng)(該獎(jiǎng)被國(guó)際公認(rèn)為計(jì)算機(jī)科學(xué)領(lǐng)域的最高獎(jiǎng)項(xiàng))。對(duì)于Knuth教授來說，衡量一個(gè)計(jì)算機(jī)程序是否完整的標(biāo)準(zhǔn)不僅僅在于它是否能夠運(yùn)行，他認(rèn)為一個(gè)計(jì)算機(jī)程序應(yīng)該是雅致的、甚至可以說是美的。計(jì)算機(jī)程序設(shè)計(jì)應(yīng)該是一門藝術(shù)，一個(gè)算法應(yīng)該像一段音樂，而一個(gè)好的程序應(yīng)該如一部文學(xué)作品一般。如果你認(rèn)為你是一名真正優(yōu)秀的程序員讀Knuth的計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)，如果你能讀懂整套書的話，請(qǐng)給我發(fā)一份你的簡(jiǎn)歷。 Bill Gates一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)類型三、抽象數(shù)據(jù)類型1.2 基本概念和術(shù)語(yǔ)一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu) 所有能輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù):是計(jì)算機(jī)操作的對(duì)象的總稱。

9、是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。數(shù)據(jù)可以分為兩類：數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù) 數(shù)據(jù)項(xiàng)： 是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。數(shù)據(jù)元素可以是數(shù)據(jù)項(xiàng)的集合。例如：描述一個(gè)運(yùn)動(dòng)員的數(shù)據(jù)元素可以是稱之為組合項(xiàng)姓名俱樂部名稱出生日期參加日期職務(wù)業(yè)績(jī)年月日數(shù)據(jù)元素： 是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”，是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如，整數(shù)數(shù)據(jù)對(duì)象是集合N=0，1，-1，2，-2，字母字符數(shù)據(jù)對(duì)象是集合C=A，B，Z。數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 例，在2行3列的二維數(shù)組a1,

10、 a2, a3, a4, a5, a6 中六個(gè)元素之間存在兩個(gè)關(guān)系:行的次序關(guān)系:列的次序關(guān)系:row = ,col = , a1 a3 a5 a2 a4 a6 a1 a2 a3a4 a5 a6 再例，在一維數(shù)組 a1, a2, a3, a4, a5, a6 的數(shù)據(jù)元素之間存在如下的次序關(guān)系:| i=1, 2, 3, 4, 5，6 或者說，數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。 可見，不同的“關(guān)系”構(gòu)成不同的“結(jié)構(gòu)”。注意：數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對(duì)象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對(duì)象，而且要描述數(shù)據(jù)對(duì)象各元素之間的相互關(guān)系。數(shù)據(jù)結(jié)構(gòu)主要指邏輯結(jié)構(gòu)和物理結(jié)構(gòu)數(shù)據(jù)之間的

11、相互關(guān)系稱為邏輯結(jié)構(gòu)。通常分為四類基本結(jié)構(gòu)：集合 結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無(wú)其它關(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)系。 25數(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。26例1-4 設(shè)有一個(gè)數(shù)據(jù)結(jié)構(gòu)的形式

12、定義可表示為DS=(D,S),其中D=a1,a2,a3,a4,a5,S=,，則它的邏輯結(jié)構(gòu)用圖描述見圖1.4 。 線性表的邏輯結(jié)構(gòu)描述a1a2a3a4a5例1-5 設(shè)一個(gè)數(shù)據(jù)結(jié)構(gòu)的形式定義為DS=(D,S),其中D=a,b,c,d,e,f,g,h,S=,則它的邏輯結(jié)構(gòu)用圖描述見圖1.5。例 1-6 設(shè)一個(gè)數(shù)據(jù)結(jié)構(gòu)的形式定義為DS=(D,S),其中D=1,2,3,4,而S=(1,2),(1,3),(1,4),(2,3),(2,4),(3,4), 則它的邏輯結(jié)構(gòu)用圖描述見圖1.6。存儲(chǔ)結(jié)構(gòu)（Storge Structure):數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(或稱映象）稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，又稱為物理結(jié)構(gòu)。

13、數(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)系。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象“數(shù)據(jù)元素”的映象 ？“關(guān)系”的映象 ？數(shù)據(jù)元素的映象方法：例：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2關(guān)系的映象方法：（表示x, y的方法）順序映象以相對(duì)的存儲(chǔ)位置

14、表示后繼關(guān)系。 例如:令 y 的存儲(chǔ)位置和 x 的存儲(chǔ)位置之間差一個(gè)常量 C。而 C 是一個(gè)隱含值，整個(gè)存儲(chǔ)結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息。 x y鏈?zhǔn)接诚?以附加信息(指針)表示后繼關(guān)系。需要用一個(gè)和 x 在一起的附加信息指示 y 的存儲(chǔ)位置。 y x 在不同的編程環(huán)境中，存儲(chǔ)結(jié)構(gòu)可有不同的描述方法。 當(dāng)用高級(jí)程序設(shè)計(jì)語(yǔ)言進(jìn)行編程時(shí)，通?？捎酶呒?jí)編程語(yǔ)言中提供的數(shù)據(jù)類型描述之。例如: 以三個(gè)帶有次序關(guān)系的整數(shù)表示一個(gè)長(zhǎng)整數(shù)時(shí)，可利用 C 語(yǔ)言中提供的整數(shù)數(shù)組類型。 typedef int Long_int 3定義長(zhǎng)整數(shù)為:二、數(shù)據(jù)類型在用高級(jí)程序語(yǔ)言編寫的程序中，必須對(duì)程序中出現(xiàn)的每個(gè)變量、常

15、量或表達(dá)式，明確說明它們所屬的數(shù)據(jù)類型。C語(yǔ)言的數(shù)據(jù)類型：基本類型和構(gòu)造類型基本類型：整型、浮點(diǎn)型、字符型構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義數(shù)據(jù)類型:是一個(gè)值的集合和定義在此集合上的一組操作的總稱。不同類型的變量，其所能取的值的范圍不同，所能進(jìn)行的操作不同。使用數(shù)據(jù)類型可以實(shí)現(xiàn)信息隱蔽，即將用戶不必了解的細(xì)節(jié)都封裝在類型中。三、抽象數(shù)據(jù)類型(Abstract Data Type 簡(jiǎn)稱ADT) 是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。抽象數(shù)據(jù)類型的描述方法：抽象數(shù)據(jù)類型可用（D，S，P）三元組表示。D 是數(shù)據(jù)對(duì)象；S 是 D 上的關(guān)系集；P 是對(duì) D 的基本操作集。 數(shù)據(jù)

16、類型與抽象數(shù)據(jù)類型的區(qū)別？數(shù)據(jù)類型：是一個(gè)值的集合和定義在該值上的一組操作的總稱。抽象數(shù)據(jù)類型：由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。它由基本的數(shù)據(jù)類型構(gòu)成，并包括一組相關(guān)的服務(wù)（或稱操作）與數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念，但其特征是使用與實(shí)現(xiàn)分離，實(shí)行封裝和信息隱蔽（獨(dú)立于計(jì)算機(jī)）。例如：各種高級(jí)程序設(shè)計(jì)語(yǔ)言中都擁有“整數(shù)”類型，盡管它們?cè)诓煌幚砥魃蠈?shí)現(xiàn)的方法不同，但對(duì)程序員而言是“相同的”，因?yàn)樗鼈兊臄?shù)學(xué)特性相同。抽象數(shù)據(jù)類型的范疇更廣，不再局限于各處理器已定義和實(shí)現(xiàn)的數(shù)據(jù)類型，還包括用戶根據(jù)需要自定義的數(shù)據(jù)類型。抽象數(shù)據(jù)類型的分類原子類型：變量的值是不可分解得。較少，已有的固有類型足以滿足

17、需要。特殊情況下，也需要定義新的原子類型。固定聚合類型：其值由確定數(shù)目的成分按某種結(jié)構(gòu)組成。例如：復(fù)數(shù)，分?jǐn)?shù)可變聚合類型：構(gòu)成的類型值的成分?jǐn)?shù)目不確定。例如：有序整數(shù)序列，其中序列的長(zhǎng)度是可變的。后兩種統(tǒng)稱為：結(jié)構(gòu)類型ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義 基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名其中基本操作的定義格式為:基本操作名（參數(shù)表） 初始條件：初始條件描述 操作結(jié)果：操作結(jié)果描述 ADT常用定義格式賦值參數(shù) 只為操作提供輸入值。引用參數(shù) 以&打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件 描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若

18、不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。操作結(jié)果 說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。ADT Triplet 數(shù)據(jù)對(duì)象：D= e1,e2,e3|e1,e2,e3ElemSet (定義了關(guān)系運(yùn)算的某個(gè)集合) 數(shù)據(jù)關(guān)系：R1=, 基本操作： InitTriplet( &T,v1,v2,v3) 操作結(jié)果：構(gòu)造了三元組T，元素e1,e2和e3分別被賦以參數(shù) v1，v2 和 v3 的值。 DestroyTriplet( &T) 操作結(jié)果：三元組T被銷毀。 Get(T,i,&e) 初始條件：三元組已存在，i=3. 操作結(jié)果：用e返回的第i元的值例1-6 抽象

19、數(shù)據(jù)類型三元組的定義： Put(&T,i,e) 初始條件：三元組已存在，i 操作結(jié)果：改變的第i元的值為eIsAscending(T) 初始條件：三元組已存在 操作結(jié)果：如果的個(gè)元素按升序排列，則返回，否則返回IsDescending(T) 初始條件：三元組已存在 操作結(jié)果：如果的個(gè)元素按降序排列，則返回，否則返回Max(T,&e) 初始條件：三元組已存在 操作結(jié)果：用e返回的個(gè)元素中的最大值A(chǔ)DTTriplet例如，定義抽象數(shù)據(jù)類型“復(fù)數(shù)” 數(shù)據(jù)對(duì)象： De1,e2e1,e2RealSet 數(shù)據(jù)關(guān)系： R1 | e1是復(fù)數(shù)的實(shí)數(shù)部分, | e2 是復(fù)數(shù)的虛數(shù)部分 ADT Complex 基本

20、操作：AssignComplex( &Z, v1, v2 ) 操作結(jié)果：構(gòu)造復(fù)數(shù) Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。DestroyComplex( &Z) 操作結(jié)果：復(fù)數(shù)Z被銷毀。 GetReal( Z, &realPart ) 初始條件：復(fù)數(shù)已存在。 操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。 GetImag( Z, &ImagPart )初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。Add( z1,z2, &sum )初始條件：z1, z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1, z2 的和值。 ADT Complex多形數(shù)據(jù)類型是指其值的成分

21、不確定的數(shù)據(jù)類型。例如，例1-6中定義的抽象數(shù)據(jù)類型Triplet，其元素e1、e2和e3可以是整數(shù)或字符或字符串，甚至更復(fù)雜的由多種成分構(gòu)成。然而，元素之間的關(guān)系相同，基本操作也相同，從抽象數(shù)據(jù)類型的角度看，具有相同的數(shù)學(xué)抽象特性，故稱之為多形數(shù)據(jù)類型。1.3 抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)。以下對(duì)類C語(yǔ)言的描述作簡(jiǎn)要說明。（1）預(yù)定義常量和類型/函數(shù)結(jié)果狀態(tài)代碼#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#defin

22、e OVERFLOW -2Typedef int Status; /Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼（2）數(shù)據(jù)結(jié)構(gòu)的表示（存儲(chǔ)結(jié)構(gòu)）用類型定義（typedef)描述。數(shù)據(jù)元素類型約定為ElemType,由用戶在使用該數(shù)據(jù)類型時(shí)自行定義。（注意define與typedef的區(qū)別）函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表） / 算法說明 語(yǔ)句序列 / 函數(shù)名除了函數(shù)的參數(shù)需要說明類型外，算法中使用的輔助變量可以不作變量說明，必要時(shí)對(duì)其作用給予注釋。一般而言，a、b、c、d、e等用作數(shù)據(jù)元素名，i、j、k、l、m、n等用作整形變量名，p、q、r等用作指針變量名。當(dāng)函數(shù)返回值為函數(shù)結(jié)果狀態(tài)代碼時(shí)，

23、函數(shù)定義為Status類型。為了便于算法描述，除了值調(diào)用方式外，增添了C+語(yǔ)言的引用調(diào)用的參數(shù)傳遞方式。在形參表中，以&打頭的參數(shù)即為引用參數(shù)。（3）基本操作的算法都用以下形式的函數(shù)描述：簡(jiǎn)單賦值 變量名=表達(dá)式；串聯(lián)賦值 變量名 1=變量名2=變量名k=表達(dá)式；成組賦值 （變量名1，變量名k）=（表達(dá)式1， ，表達(dá)式k）； 結(jié)構(gòu)名=結(jié)構(gòu)名； 結(jié)構(gòu)名=（值1，值k）； 變量名 =表達(dá)式； 變量名起始下標(biāo).終止下標(biāo)=變量名起始下標(biāo).終止下標(biāo)；交換賦值 變量名 變量名；條件賦值 變量名=條件表達(dá)式？表達(dá)式T：表達(dá)式F；（4）賦值語(yǔ)名有條件語(yǔ)句1 if (表達(dá)式) 語(yǔ)句；條件語(yǔ)句2 if (表達(dá)式)

24、 語(yǔ)句； else 語(yǔ)句；開關(guān)語(yǔ)句1 switch （表達(dá)式） case值1: 語(yǔ)句序列1；break; case 值n：語(yǔ)句序列n;break ; default; 語(yǔ)句序列n+1； 開關(guān)語(yǔ)句2 switch case 條件1：語(yǔ)句序列1;break; case 條件n：語(yǔ)句序列n;break ; default:語(yǔ)句序列n+1； （5）選擇語(yǔ)句有for語(yǔ)句 for（賦初值表達(dá)式序列；條件；修改表達(dá)式序列）語(yǔ)句；while語(yǔ)句 while（條件）語(yǔ)句； do-while語(yǔ)句 do 語(yǔ)句序列； while（條件）；（7）結(jié)束語(yǔ)句有函數(shù)結(jié)束語(yǔ)句 return 表達(dá)式； return; case結(jié)

25、束語(yǔ)句 break;異常結(jié)束語(yǔ)句 exit（異常代碼）；（6）循環(huán)語(yǔ)句有（8）輸入和輸出語(yǔ)句有輸入語(yǔ)句 scanf（格式串，變量1，變量n）；輸出語(yǔ)句 printf （格式串，表達(dá)式1，表達(dá)式n）；通常省略格式串。（9）注釋單行注釋 / 文字序列（10）基本函數(shù)有求最大值 max（表達(dá)式1，表達(dá)式n)求最小值 min（表達(dá)式1，表達(dá)式n） 求絕對(duì)值 abs（表達(dá)式）求不足整數(shù)值 floor（表達(dá)式）求進(jìn)位整數(shù)值 ceil （表達(dá)式）判定文件結(jié)束 eof（文件變量）或eof判定行結(jié)束 eoln（文件變量）或eoln(11)邏輯運(yùn)算約定 與運(yùn)算&：對(duì)于A&B，當(dāng)A的值為0時(shí)，不再對(duì)B求值。 或運(yùn)算

26、|：對(duì)于A|B，當(dāng)A的值為非0時(shí)，不再對(duì)B求值。例1-8 抽象數(shù)據(jù)類型Triplet的表示和實(shí)現(xiàn)。 /- - - - 采用動(dòng)態(tài)分配的順序存儲(chǔ)結(jié)構(gòu)- - - - - typedef ElemType *Triplet; / 由InitTriplet分配3個(gè)元素存儲(chǔ)空間/- - - - 基本操作的函數(shù)原型說明- - - - - Status InitTriplet (Triplet &T, ElemType v1, ElemType v2, ElemType v3); /操作結(jié)果：構(gòu)造了三元組，元素e1,e2和e3分別被賦以參數(shù) v1，v2 和 v3 的值。 Status DestroyTripl

27、et ( Triplet &T); /操作結(jié)果：三元組T被銷毀。Status Get ( Triplet T , int i , ElemType &e); /初始條件：三元組已存在，=i=3. /操作結(jié)果：用e返回的第i元的值Status Put (Triplet &T , int i , ElemType e); /初始條件：三元組已存在，=i= /操作結(jié)果：改變的第i元的值為e Status IsAscending (Triplet T); / 初始條件：三元組已存在 / 操作結(jié)果：如果的個(gè)元素按升序排列，則返回，否則返回Status IsDescending (Triplet T);

28、/ 初始條件：三元組已存在 / 操作結(jié)果：如果的個(gè)元素按降序排列，則返回，否則返回Status Max (Triplet T, ElemType &e) / 初始條件：三元組已存在/ 操作結(jié)果：用e返回的個(gè)元素中的最大值Status Min (Triplet T, ElemType &e) / 初始條件：三元組已存在 / 操作結(jié)果：用e返回的個(gè)元素中的最小值/- - - - 基本操作的函數(shù)原型說明- - - - -Status InitTriplet (Triplet &T, ElemType v1, ElemType v2, ElemType v3) /構(gòu)造了三元組，依次置T的三個(gè)元素的初值

29、 v1，v2 和 v3 T=(ElemType *) malloc(3 *sizeof (ElemType ); /分配三個(gè)元素的存儲(chǔ)空間 if (!T) exit ( OVERFLOW ) ; /分配存儲(chǔ)空間失敗 T0=v1; T1=v2; T2=v3; return OK; / InitTriplet Status DestroyTriplet ( Triplet &T) /銷毀三元組T。 free ( T ); T = NULL; return OK; / InitTripletStatus Get ( Triplet T , int i , ElemType &e) /1=i=3,用e

30、返回的第i元的值 if ( i3 ) return ERROR; e = Ti-1; return OK; / GetStatus Put (Triplet &T , int i , ElemType e) /1=i=3,置的第i元的值為e if ( i3 ) return ERROR; Ti-1 = e; return OK; / PutStatus IsAscending (Triplet T) / 如果的個(gè)元素按升序排列，則返回，否則返回 return ( T0 =T1)& T1 =T1)& T1 =T2); / IsDescendingStatus Max (Triplet T, El

31、emType &e) / 用e返回的個(gè)元素中的最大值e = ( T0 =T1)?( T0 =T2)? T0 :T2):(T1 =T2)? T1 :T2);return OK; / MaxStatus Min (Triplet T, ElemType &e) / 用e返回的個(gè)元素中的最小值e = ( T0 =T1)?( T0 =T2)? T0 :T2):(T1 =T2)? T1 :T2);return OK; / Min 算法是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。一個(gè)算法必須滿足以下五個(gè)重要特性：1有窮性 2確定性 3可行性4有輸入 5有輸出1.4

32、.1 算法1.4 算法和算法分析 1有窮性 對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成。 2確定性 對(duì)于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑，不允許有二義性。 例如下面這句話：張三對(duì)李四講，他的兒子考上了大學(xué)。 確切含義？ 3可行性 算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。 4有輸入 一個(gè)算法有零個(gè)或多個(gè)的輸入，這些輸入取自于某個(gè)特定的對(duì)象的集合。 5有輸出 它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行

33、信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。1.4.2 算法設(shè)計(jì)的要求 設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1正確性2. 可讀性3健壯性4高效率與低存儲(chǔ)量需求1正確性 首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)格說明”方式給出的需求。 其次，對(duì)算法是否“正確”的理解可以有以下四個(gè)層次：a程序中不含語(yǔ)法錯(cuò)誤； b程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； c程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； d程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果； 通常以第 c 層意義的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。2. 可讀性 算法主要是為了人的閱讀與交流，其次才

34、是為計(jì)算機(jī)執(zhí)行，因此算法應(yīng)該易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試。3健壯性 當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。4高效率與低存儲(chǔ)量需求 通常，效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過程中所需的最大存儲(chǔ)空間，兩者都與問題的規(guī)模有關(guān)。1.4.3 算法效率的度量 通常有兩種衡量算法效率的方法: 事后統(tǒng)計(jì)法事前分析估算法缺點(diǎn)：1必須執(zhí)行程序 2其它因素掩蓋算法本質(zhì) 一個(gè)用高級(jí)語(yǔ)言編寫的程序在計(jì)算機(jī)上運(yùn)行時(shí)所

35、消耗時(shí)間取決于下列因素：1算法選用的策略2問題的規(guī)模3編寫程序的語(yǔ)言4編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5計(jì)算機(jī)執(zhí)行指令的速度一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來的，必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能也沒有必要對(duì)每個(gè)算法都上機(jī)測(cè)試，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱為語(yǔ)句頻度或時(shí)間頻度。記為T(n)。 撇開與計(jì)算機(jī)硬件、軟件有關(guān)的因素，可以認(rèn)為一個(gè)特定算法 “運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模

36、的函數(shù)。 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模 n 的某個(gè)函數(shù)f(n)，算法的時(shí)間度量記作 T(n) = O(f(n) 它表示隨著問題規(guī)模 n 的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和 f(n) 的增長(zhǎng)率相同，稱作算法的(漸近)時(shí)間復(fù)雜度（Asymptotic Time Complexity）。算法 = 控制結(jié)構(gòu) + 原操作 （固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)間 =原操作(i)的執(zhí)行次數(shù)原操作(i)的執(zhí)行時(shí)間 算法的執(zhí)行時(shí)間與 原操作執(zhí)行次數(shù)之和成正比 如何估算算法的時(shí)間復(fù)雜度？ 從算法中選取一種對(duì)于所研究的問題來說是 基本操作 的原操作，以該基本操作 在算法中重復(fù)執(zhí)行的次數(shù) 作為算法運(yùn)行

37、時(shí)間的衡量準(zhǔn)則。(c) for(j=1;j=n;+j) for(k=1;k=n;+k) +x;s+=x; 語(yǔ)句頻度： n2 T(n)=O(n2) 平方階+x;s=0; 語(yǔ)句頻度：1 T(n)=O(1) 常量階(b) for(i=1;i=n;+i) +x;s+=x; 語(yǔ)句頻度：n T(n)=O(n) 線性階例：兩個(gè)矩陣相乘void mult(int a, int b, int& c ) / 以二維數(shù)組存儲(chǔ)矩陣元素，c 為 /a 和 b 的乘積 for (i=1; i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1; k=n; +k) ci,j += ai

38、,k*bk,j; /for /mult基本操作: 乘法操作時(shí)間復(fù)雜度: O(n3)選擇執(zhí)行次數(shù)最多增長(zhǎng)最快的一個(gè)原操作，一般是最內(nèi)層的循環(huán)例1 求下列算法段的語(yǔ)句頻度f(wàn)or(i=1; i=n; i+)for(j =1; j =i ; j+)x=x+1;分析：該算法為一個(gè)二重循環(huán)，執(zhí)行次數(shù)為內(nèi)、外循環(huán)次數(shù)相乘，但內(nèi)循環(huán)次數(shù)不固定，與外循環(huán)有關(guān)，因些，時(shí)間頻度T(n)=1+2+3+n= 例1.2 分析以下程序段的時(shí)間復(fù)雜度f(wàn)or (i=1;in;i+) y=y+1; for (j=0; j=(2*n); j+)x+; /* 1 * /* 2 * /分析：語(yǔ)句的頻度指的是該語(yǔ)句重復(fù)執(zhí)行的次數(shù)。一個(gè)算法中所有語(yǔ)句的頻度之和構(gòu)成了該算法的運(yùn)行時(shí)間。語(yǔ)句1的頻度是：n-1語(yǔ)句2的頻度是：則該程序段的時(shí)間復(fù)雜度：T(n)=例1.3 分析以下程序段的時(shí)間復(fù)雜度i=1;while (i=n) i=i*2語(yǔ)句1的頻度是：1設(shè)語(yǔ)句2的頻度是f(n)，則有：即 取最大值,則該程序段的時(shí)間復(fù)雜度為：/* 1 * /* 2 * /例1.4x=1;for (i=1;i=n;i+) for (j=1;j=i;j+) for