數(shù)據(jù)結(jié)構(gòu)課件：緒論

緒論1.1數(shù)據(jù)結(jié)構(gòu)的基本概念1.2抽象數(shù)據(jù)類型和軟件構(gòu)造方法1.3算法和算法的時(shí)間復(fù)雜度1.4算法設(shè)計(jì)1.5算法書寫規(guī)范1.6本課程內(nèi)容概述計(jì)算機(jī)是對(duì)各種各樣的數(shù)據(jù)進(jìn)行處理的機(jī)器。要對(duì)數(shù)據(jù)進(jìn)行處理，首先就要對(duì)數(shù)據(jù)進(jìn)行組織。因此，在計(jì)算機(jī)中如何有效地組織數(shù)據(jù)和處理數(shù)據(jù)就是計(jì)算機(jī)科學(xué)的基本研究?jī)?nèi)容，也是繼續(xù)深入學(xué)習(xí)后續(xù)課程的基礎(chǔ)。本章主要對(duì)數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)中將遇到的基本概念做概括性的敘述，這些內(nèi)容將貫穿于數(shù)據(jù)結(jié)構(gòu)課程的整個(gè)學(xué)習(xí)過(guò)程中。其中，1.1節(jié)概述了數(shù)據(jù)結(jié)構(gòu)的基本概念；1.2節(jié)討論了抽象數(shù)據(jù)類型和軟件構(gòu)造方法；1.3節(jié)給出了算法的定義和算法效率的數(shù)學(xué)定義；算法設(shè)計(jì)一直是初學(xué)者最感頭痛的內(nèi)容，1.4節(jié)通過(guò)實(shí)際例子討論了算法設(shè)計(jì)要考慮的問(wèn)題；數(shù)據(jù)結(jié)構(gòu)課程的任務(wù)之一是訓(xùn)練學(xué)生的軟件設(shè)計(jì)能力，并要求軟件設(shè)計(jì)按規(guī)范進(jìn)行，1.5節(jié)給出的算法書寫規(guī)范有助于培養(yǎng)學(xué)生這方面的能力。

數(shù)據(jù)是人們利用文字符號(hào)、數(shù)字符號(hào)以及其他規(guī)定的符號(hào)對(duì)現(xiàn)實(shí)世界的事物及其活動(dòng)所做的抽象描述。

例如，今天天氣最高溫度為4°C，最低溫度為-4°C，就是關(guān)于今天天氣情況的描述數(shù)據(jù)。又例如，班上甲同學(xué)姓名叫張三，乙同學(xué)姓名叫李四，就是關(guān)于班上同學(xué)姓名的描述數(shù)據(jù)。1.1數(shù)據(jù)結(jié)構(gòu)的基本概念表示一個(gè)事物的一組數(shù)據(jù)稱作一個(gè)數(shù)據(jù)元素；構(gòu)成數(shù)據(jù)元素的數(shù)據(jù)稱作該數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。

例如，描述學(xué)生情況的數(shù)據(jù)可包括學(xué)生的學(xué)號(hào)、姓名、性別、年齡等。學(xué)生的學(xué)號(hào)、姓名、性別、年齡等數(shù)據(jù)就構(gòu)成學(xué)生情況描述的數(shù)據(jù)項(xiàng)；學(xué)號(hào)、姓名、性別、年齡等數(shù)據(jù)項(xiàng)的一組數(shù)據(jù)就構(gòu)成學(xué)生情況描述的一個(gè)數(shù)據(jù)元素。表1-1是一個(gè)有三個(gè)數(shù)據(jù)元素?cái)?shù)值的學(xué)生情況表。

表1-1學(xué)生情況表在數(shù)據(jù)結(jié)構(gòu)課程中，關(guān)于數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)的描述都使用某種高級(jí)程序設(shè)計(jì)語(yǔ)言語(yǔ)法格式，高級(jí)程序設(shè)計(jì)語(yǔ)言要求在定義數(shù)據(jù)元素時(shí)必須指定每個(gè)數(shù)據(jù)項(xiàng)所屬的數(shù)據(jù)類型。本書采用C語(yǔ)言語(yǔ)法格式。學(xué)生情況數(shù)據(jù)元素的數(shù)據(jù)類型的C語(yǔ)言格式定義為：

structStudent

{

charnumber［8］;

charname［10］;

charsex［3］;

intage;

};由于漢字“男”、“女”需占兩個(gè)字符，一個(gè)以上的字符序列稱為字符串，在C語(yǔ)言中，字符串還有一個(gè)結(jié)束標(biāo)記，所以sex域應(yīng)定義為長(zhǎng)度為3的字符數(shù)組。關(guān)于字符串的定義見(jiàn)4.1節(jié)。

通過(guò)C語(yǔ)言程序設(shè)計(jì)課程的學(xué)習(xí)我們知道，可以利用已定義的基本數(shù)據(jù)類型定義新的數(shù)據(jù)類型。通過(guò)上述定義，structStudent就可像C語(yǔ)言中已定義的數(shù)據(jù)類型char、int、float等一樣，用于定義新的描述學(xué)生情況的數(shù)據(jù)類型。為使用簡(jiǎn)便起見(jiàn)，我們還可以把上述定義改寫為：

typedefstructStudent

{

charnumber［8］;

charname［10］;

charsex［3］;

intage;

}StudentType;

typedef是關(guān)鍵字，上述定義表示StudentType和structStudent同名。定義后，我們可以用StudentType定義新的描述學(xué)生情況的數(shù)據(jù)類型。例如，像下面這樣定義后就表示變量a和b所屬的數(shù)據(jù)類型為StudentType：

StudentTypea，b;此時(shí)，表示變量a的name數(shù)據(jù)項(xiàng)的語(yǔ)法是，表示變量b的age數(shù)據(jù)項(xiàng)的語(yǔ)法是b.age。沒(méi)有定義具體數(shù)據(jù)類型的數(shù)據(jù)元素稱作抽象數(shù)據(jù)元素。

上述學(xué)生情況數(shù)據(jù)元素的數(shù)據(jù)類型定義為StudentType，即給出了具體的數(shù)據(jù)類型定義。但是，像數(shù)學(xué)一樣，數(shù)據(jù)結(jié)構(gòu)課程討論的數(shù)據(jù)元素也可以是抽象數(shù)據(jù)元素，我們把沒(méi)有具體數(shù)據(jù)類型定義的數(shù)據(jù)元素稱作抽象數(shù)據(jù)元素。當(dāng)討論抽象數(shù)據(jù)元素時(shí)，我們用符號(hào)DataType表示該抽象數(shù)據(jù)元素的數(shù)據(jù)類型。當(dāng)軟件設(shè)計(jì)問(wèn)題具體確定時(shí)，抽象數(shù)據(jù)元素的數(shù)據(jù)類型將被具體的數(shù)據(jù)類型取代。例如，當(dāng)該抽象線性表的數(shù)據(jù)元素類型具體確定為表1-1的數(shù)據(jù)元素類型時(shí)，可通過(guò)重新定義抽象數(shù)據(jù)元素類型為StudentType，來(lái)具體確定該抽象數(shù)據(jù)元素的數(shù)據(jù)類型。具體的定義語(yǔ)句格式為：

typedefStudentTypeDataType;

數(shù)據(jù)元素之間的相互聯(lián)系方式稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。按照數(shù)據(jù)元素之間的相互聯(lián)系方式，數(shù)據(jù)的邏輯結(jié)構(gòu)可分為線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)。線性結(jié)構(gòu)是指除第一個(gè)和最后一個(gè)數(shù)據(jù)元素外每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素和一個(gè)后繼數(shù)據(jù)元素。表1-1中的數(shù)據(jù)元素就是一個(gè)線性結(jié)構(gòu)的數(shù)據(jù)元素。線性結(jié)構(gòu)也可表示為圖1-1(a)。由于線性結(jié)構(gòu)的數(shù)據(jù)元素呈現(xiàn)為線性序列，所以有些教科書把線性結(jié)構(gòu)稱為線性序列，或簡(jiǎn)稱序列。樹結(jié)構(gòu)是指除根結(jié)點(diǎn)外每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素和若干個(gè)后繼數(shù)據(jù)元素，其典型例子如圖1-1(b)所示，其中，數(shù)據(jù)元素A有兩個(gè)后繼數(shù)據(jù)元素，分別為B和C。

圖結(jié)構(gòu)是指每個(gè)數(shù)據(jù)元素可有若干個(gè)前驅(qū)數(shù)據(jù)元素和若干個(gè)后繼數(shù)據(jù)元素，其典型例子如圖1-1(c)所示，其中，數(shù)據(jù)元素E有兩個(gè)前驅(qū)數(shù)據(jù)元素，分別為B和C。

圖1-1基本的數(shù)據(jù)邏輯結(jié)構(gòu)形式

(a)線性結(jié)構(gòu)；(b)樹結(jié)構(gòu)；(c)圖結(jié)構(gòu)任何需要計(jì)算機(jī)進(jìn)行管理和處理的數(shù)據(jù)元素都必須首先按某種方式存儲(chǔ)在計(jì)算機(jī)中。數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)方式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，也稱為數(shù)據(jù)的物理結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)應(yīng)能正確地表示出數(shù)據(jù)元素間的邏輯關(guān)系。

數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的基本形式有兩種：一種是順序存儲(chǔ)結(jié)構(gòu)，另一種是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)是把數(shù)據(jù)元素存儲(chǔ)在一塊連續(xù)地址空間的內(nèi)存中，其特點(diǎn)是邏輯上相鄰的數(shù)據(jù)元素在物理上也相鄰，數(shù)據(jù)間的邏輯關(guān)系表現(xiàn)在數(shù)據(jù)元素的存儲(chǔ)位置關(guān)系上。當(dāng)采用高級(jí)程序設(shè)計(jì)語(yǔ)言表示時(shí)，實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)的方法是使用數(shù)組。圖1-2(a)是線性結(jié)構(gòu)數(shù)據(jù)元素a0，a1，…，an-1順序存儲(chǔ)結(jié)構(gòu)的基本形式。指針是指向物理存儲(chǔ)單元地址的變量。我們把由數(shù)據(jù)元素域和指針域組成的一個(gè)結(jié)構(gòu)體稱為一個(gè)結(jié)點(diǎn)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指使用指針把相互直接關(guān)聯(lián)的結(jié)點(diǎn)(即直接前驅(qū)結(jié)點(diǎn)或直接后繼結(jié)點(diǎn))鏈接起來(lái)，其特點(diǎn)是邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰，數(shù)據(jù)間的邏輯關(guān)系表現(xiàn)在結(jié)點(diǎn)的鏈接關(guān)系上。圖1-2(b)是線性結(jié)構(gòu)數(shù)據(jù)元素a0，a1，…，an-1鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的基本形式。

圖1-2基本存儲(chǔ)結(jié)構(gòu)形式

(a)順序存儲(chǔ)結(jié)構(gòu)；(b)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是兩種最基本、最常用的存儲(chǔ)結(jié)構(gòu)。除此之外，還有仿真指針(也稱作靜態(tài)數(shù)組)和間接地址存儲(chǔ)結(jié)構(gòu)。仿真指針和間接地址存儲(chǔ)結(jié)構(gòu)實(shí)際上分別是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的某種形式的結(jié)合。

對(duì)一種數(shù)據(jù)類型的數(shù)據(jù)進(jìn)行的某種處理稱作數(shù)據(jù)的操作，對(duì)一種數(shù)據(jù)類型的數(shù)據(jù)的所有操作稱作數(shù)據(jù)的操作集合。數(shù)據(jù)的操作有兩個(gè)方面的含義：在邏輯結(jié)構(gòu)意義下，數(shù)據(jù)的操作主要討論該種數(shù)據(jù)類型數(shù)據(jù)應(yīng)實(shí)現(xiàn)的操作功能；在存儲(chǔ)結(jié)構(gòu)意義下，數(shù)據(jù)的操作主要討論操作的具體實(shí)現(xiàn)算法。例如，若某軟件要對(duì)表1-1所示的學(xué)生情況表進(jìn)行處理，在邏輯結(jié)構(gòu)意義下，對(duì)學(xué)生情況表可能進(jìn)行的操作有：插入一條數(shù)據(jù)元素，刪除一條數(shù)據(jù)元素，列出所有數(shù)據(jù)元素的值，等等。若采用圖1-2(a)所示的順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)元素，就要考慮在這種存儲(chǔ)結(jié)構(gòu)下插入、刪除一條數(shù)據(jù)元素，以及列出所有數(shù)據(jù)元素的值等操作的具體實(shí)現(xiàn)算法；若采用圖1-2(b)所示的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)元素，就要考慮在這種存儲(chǔ)結(jié)構(gòu)下插入、刪除一條數(shù)據(jù)元素，以及列出所有數(shù)據(jù)元素的值等操作的具體實(shí)現(xiàn)算法。顯然，對(duì)于邏輯結(jié)構(gòu)意義下的插入一條數(shù)據(jù)元素操作，其存儲(chǔ)結(jié)構(gòu)不同，操作的具體實(shí)現(xiàn)算法將不同。

數(shù)據(jù)結(jié)構(gòu)課程主要討論表、堆棧、隊(duì)列、串、數(shù)組、樹、二叉樹、圖等典型的常用數(shù)據(jù)結(jié)構(gòu)，在討論這些典型的常用數(shù)據(jù)結(jié)構(gòu)時(shí)，主要從它們的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)操作三個(gè)方面進(jìn)行分析討論。例如，我們?cè)诘?章討論線性表時(shí)，2.1節(jié)將討論線性表的抽象數(shù)據(jù)類型(即線性表的邏輯結(jié)構(gòu)和邏輯結(jié)構(gòu)意義下的操作功能)，2.2節(jié)將討論線性表的順序存儲(chǔ)結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)下各基本操作的具體實(shí)現(xiàn)算法，2.3節(jié)將討論線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下各基本操作的具體實(shí)現(xiàn)算法。其他各章中對(duì)堆棧、隊(duì)列、串、數(shù)組、樹、二叉樹、圖等討論的章節(jié)安排次序和第2章類同。

類型是一組值的集合。

例如，整數(shù)類型就是具體計(jì)算機(jī)所允許表示的整數(shù)數(shù)值的集合，通常整數(shù)類型的范圍是-32767~32768。又例如，布爾類型就是數(shù)值true和false組成的集合。

數(shù)據(jù)類型是指一個(gè)類型和定義在這個(gè)類型上的操作的集合。1.2抽象數(shù)據(jù)類型和軟件構(gòu)造方法例如，當(dāng)我們說(shuō)計(jì)算機(jī)中的整數(shù)數(shù)據(jù)類型時(shí)，它就不僅指計(jì)算機(jī)所允許表示的整數(shù)數(shù)值的集合，而且指能對(duì)這個(gè)整數(shù)類型進(jìn)行的加(＋)、減(-)、乘(*)、除(/)和求模(%)操作。

在本課程中，通常把在已有的數(shù)據(jù)類型基礎(chǔ)上設(shè)計(jì)新的數(shù)據(jù)類型的過(guò)程稱作數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，在這里，數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型含義相同。

抽象數(shù)據(jù)類型(AbstractDataType，縮寫為ADT)是指一個(gè)邏輯概念上的類型和這個(gè)類型上的操作集合。

數(shù)據(jù)結(jié)構(gòu)課程主要討論的表、堆棧、隊(duì)列、串、數(shù)組、樹、二叉樹、圖等典型的常用數(shù)據(jù)結(jié)構(gòu)，就是一個(gè)個(gè)不同的抽象數(shù)據(jù)類型。

在蓋樓時(shí)，如果我們用磚、水泥、沙子來(lái)蓋，則不僅建造周期長(zhǎng)，而且樓不可能蓋得很高(否則將不安全)；如果我們用水泥預(yù)制板，則不僅建造周期短(因水泥預(yù)制板有專門的公司按規(guī)范的規(guī)格提供)，樓能蓋很高，而且所建造的高樓能保證安全。從數(shù)學(xué)的觀點(diǎn)看，水泥預(yù)制板使高樓的接縫數(shù)量大大減少，從而大大降低了高樓建造的復(fù)雜度。抽象數(shù)據(jù)類型是大型軟件構(gòu)造的模塊化方法。和安全、快速、方便地建造高樓方法類同，大型軟件的設(shè)計(jì)也采用模塊化方法。典型的常用抽象數(shù)據(jù)類型，如表、堆棧、隊(duì)列、串、數(shù)組、樹、二叉樹、圖等就是我們?cè)O(shè)計(jì)大型軟件時(shí)要使用的水泥預(yù)制板，我們用這些已由專門公司設(shè)計(jì)好的抽象數(shù)據(jù)類型，就可以安全、快速、方便地設(shè)計(jì)功能復(fù)雜的大型軟件。抽象數(shù)據(jù)類型定義是軟件設(shè)計(jì)的中間環(huán)節(jié)。一方面，根據(jù)給出的抽象數(shù)據(jù)類型定義，負(fù)責(zé)設(shè)計(jì)這些抽象數(shù)據(jù)類型的專門公司(或?qū)ｉT設(shè)計(jì)人員)設(shè)計(jì)該抽象數(shù)據(jù)類型的具體存儲(chǔ)結(jié)構(gòu)以及在具體存儲(chǔ)結(jié)構(gòu)下各操作的具體實(shí)現(xiàn)算法；另一方面，利用已設(shè)計(jì)實(shí)現(xiàn)的抽象數(shù)據(jù)類型模塊，負(fù)責(zé)設(shè)計(jì)大型軟件的專門公司(或?qū)ｉT設(shè)計(jì)人員)可以安全、快速、方便地完成該大型軟件系統(tǒng)設(shè)計(jì)，方法和建造高樓的方法類同。水泥預(yù)制板規(guī)格的設(shè)計(jì)是高樓建造的中間環(huán)節(jié)。一方面，根據(jù)給出的水泥預(yù)制板規(guī)格，負(fù)責(zé)提供水泥預(yù)制板的專門公司制造水泥預(yù)制板；另一方面，根據(jù)給出的水泥預(yù)制板規(guī)格，高樓的設(shè)計(jì)人員和建造人員可以安全、快速、方便地完成高樓的設(shè)計(jì)和建造。

1.3.1算法

算法是描述求解問(wèn)題方法的操作步驟集合。

算法要用某種語(yǔ)言來(lái)描述。描述算法的語(yǔ)言主要有三種形式：文字形式、偽碼形式、程序設(shè)計(jì)語(yǔ)言形式。文字形式是用中文或英文這樣的文字來(lái)描述算法。偽碼形式是用一種仿程序設(shè)計(jì)語(yǔ)言的語(yǔ)言(因這樣的語(yǔ)言不是真正的程序設(shè)計(jì)語(yǔ)言，所以稱為偽碼)來(lái)描述算法。1.3算法和算法的時(shí)間復(fù)雜度程序設(shè)計(jì)語(yǔ)言形式是用某種程序設(shè)計(jì)語(yǔ)言來(lái)描述算法。用程序設(shè)計(jì)語(yǔ)言描述算法的優(yōu)點(diǎn)是，這樣的算法不需修改，直接作為程序語(yǔ)句鍵入計(jì)算機(jī)后，計(jì)算機(jī)能調(diào)用和運(yùn)行。(本書采用C語(yǔ)言描述算法。)

設(shè)計(jì)一個(gè)把存儲(chǔ)在數(shù)組中的n個(gè)抽象數(shù)據(jù)元素a0，a1，…，an-1逆置的算法，即要求逆置后的數(shù)組中的數(shù)據(jù)元素序列為an-1，…，a1，a0，并要求原數(shù)組中的數(shù)據(jù)元素值不能被改變。

設(shè)計(jì)這是一個(gè)算法設(shè)計(jì)問(wèn)題。該算法要求一個(gè)表示元素個(gè)數(shù)的輸入?yún)?shù)n，一個(gè)表示原數(shù)組的輸入?yún)?shù)a和一個(gè)表示逆置后的數(shù)組的輸出參數(shù)b(關(guān)于輸入?yún)?shù)和輸出參數(shù)的詳細(xì)討論見(jiàn)1.4節(jié))。算法設(shè)計(jì)如下：

voidReverse(intn，DataTypea［］，DataTypeb［］)

{

inti;

for(i＝0;i<n;i＋＋)/*為數(shù)組b的n個(gè)元素賦值*/

b［i］＝a［n-1-i］;

}該算法的實(shí)現(xiàn)方法圖示見(jiàn)圖1-3。

圖1-3例1-1算法實(shí)現(xiàn)方法圖示設(shè)計(jì)一個(gè)把存儲(chǔ)在數(shù)組中的n個(gè)抽象數(shù)據(jù)元素a0，a1，…，an-1就地逆置的算法，即要求逆置后數(shù)組中數(shù)據(jù)元素序列為an-1，…，a1，a0，并要求原數(shù)組中的數(shù)據(jù)元素值被改變。

設(shè)計(jì)這是一個(gè)不同于例1-1的算法設(shè)計(jì)問(wèn)題。該算法要求一個(gè)表示元素個(gè)數(shù)的輸入?yún)?shù)n，一個(gè)表示原數(shù)組的輸入?yún)?shù)a和一個(gè)表示逆置后的數(shù)組的輸出參數(shù)b。由于要求原數(shù)組中的數(shù)據(jù)元素值被改變，所以輸出參數(shù)b必須和輸入?yún)?shù)a相同，因此這兩個(gè)參數(shù)應(yīng)設(shè)計(jì)為一個(gè)參數(shù)，其參數(shù)類型設(shè)計(jì)為輸入輸出混合型參數(shù)。

圖1-4例1-2算法實(shí)現(xiàn)方法圖示算法設(shè)計(jì)如下：

voidReverse(intn，DataTypea［］)

{

inti，m＝n/2;

DataTypetemp;

for(i＝0;i<m;i＋＋)

{

temp＝a［i］;

a［i］＝a［n-1-i］;

a［n-1-i］＝temp;

}

}該算法的實(shí)現(xiàn)方法圖示見(jiàn)圖1-4。

算法應(yīng)滿足以下性質(zhì)：

(1)輸入性：具有零個(gè)或若干個(gè)輸入量；

(2)輸出性：至少產(chǎn)生一個(gè)輸出或執(zhí)行一個(gè)有意義的操作；

(3)有限性：執(zhí)行語(yǔ)句的序列是有限的；

(4)確定性：每一條語(yǔ)句的含義明確，無(wú)二義性；

(5)可執(zhí)行性：每一條語(yǔ)句都應(yīng)在有限的時(shí)間內(nèi)完成。由于高級(jí)程序設(shè)計(jì)語(yǔ)言都規(guī)范了語(yǔ)句格式，不允許出現(xiàn)二義性語(yǔ)句，因此用高級(jí)程序設(shè)計(jì)語(yǔ)言設(shè)計(jì)的算法中只要沒(méi)有無(wú)限循環(huán)就必然滿足算法的有限性、確定性和可執(zhí)行性的性質(zhì)。

應(yīng)用程序通常是通過(guò)調(diào)用函數(shù)(即算法)來(lái)完成的。程序和算法的惟一區(qū)別是程序允許無(wú)限循環(huán)，而算法不允許無(wú)限循環(huán)。構(gòu)成無(wú)限循環(huán)的一組語(yǔ)句可以是：while(1)/*循環(huán)條件永真*/

{

……/*任意語(yǔ)句序列*/

}1.3.2算法設(shè)計(jì)的目標(biāo)算法設(shè)計(jì)應(yīng)滿足以下五條目標(biāo)：

(1)正確性：算法應(yīng)確切地滿足具體問(wèn)題的需求，這是算法設(shè)計(jì)的基本目標(biāo)。

(2)可讀性：算法的可讀性有利于人們對(duì)算法的理解，這既有利于程序的調(diào)試和維護(hù)，也有利于算法的交流和移植。算法的可讀性主要體現(xiàn)在兩方面：一是類名、對(duì)象名、方法名等命名要見(jiàn)名知意；二是要有足夠多的注釋。

(3)健壯性：當(dāng)輸入非法數(shù)據(jù)時(shí)算法要能做出適當(dāng)?shù)奶幚恚粦?yīng)產(chǎn)生不可預(yù)料的結(jié)果。

(4)高時(shí)間效率：算法的時(shí)間效率是指算法的執(zhí)行時(shí)間。對(duì)于同一個(gè)問(wèn)題如果有多個(gè)算法可供選擇，應(yīng)盡可能選擇執(zhí)行時(shí)間短的算法。執(zhí)行時(shí)間短的算法稱作高時(shí)間效率的算法。

(5)高空間效率：算法在執(zhí)行時(shí)一般要求額外的內(nèi)存空間。對(duì)于同一個(gè)問(wèn)題如果有多個(gè)算法可供選擇，應(yīng)盡可能選擇內(nèi)存要求低的算法。內(nèi)存要求低的算法稱作高空間效率的算法。算法的高時(shí)間效率目標(biāo)和高空間效率目標(biāo)通常是矛盾的。如有些問(wèn)題若采用較多的內(nèi)存空間可使時(shí)間效率提高，若采用較少的內(nèi)存空間則使時(shí)間效率降低。在目前計(jì)算機(jī)硬件價(jià)格快速下降的趨勢(shì)下，算法的時(shí)間效率應(yīng)首先被考慮。1.3.3算法時(shí)間效率的度量

算法的執(zhí)行時(shí)間需通過(guò)根據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間來(lái)度量。度量一個(gè)程序在計(jì)算機(jī)上的執(zhí)行時(shí)間通常有如下兩種方法：

(1)事后統(tǒng)計(jì)方法。計(jì)算機(jī)內(nèi)部均設(shè)有計(jì)時(shí)功能，可設(shè)計(jì)一組或若干組測(cè)試數(shù)據(jù)，然后分別運(yùn)行根據(jù)不同的算法編制的程序，并比較這些程序的實(shí)際運(yùn)行時(shí)間，從而確定算法效率的優(yōu)劣。但這種方法有兩個(gè)缺陷：一是必須運(yùn)行依據(jù)算法編制的程序，而這通常是比較麻煩的；二是有些算法的測(cè)試數(shù)據(jù)設(shè)計(jì)困難，因?yàn)椴煌乃惴▽?duì)不同的測(cè)試數(shù)據(jù)反應(yīng)不同，要設(shè)計(jì)出能客觀、全面地反映算法效率的測(cè)試數(shù)據(jù)有時(shí)很困難。

(2)事前分析方法：用數(shù)學(xué)方法直接對(duì)算法的效率進(jìn)行分析。因這種分析方法是在計(jì)算機(jī)實(shí)際運(yùn)行根據(jù)該算法編制的程序前進(jìn)行的，所以稱作事前分析方法。根據(jù)算法編制的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間與下列因素有關(guān)：

①書寫算法的程序設(shè)計(jì)語(yǔ)言；

②編譯產(chǎn)生的機(jī)器語(yǔ)言代碼質(zhì)量；

③機(jī)器執(zhí)行指令的速度；

④問(wèn)題的規(guī)模，即算法的時(shí)間效率與算法所處理的數(shù)據(jù)個(gè)數(shù)n的函數(shù)關(guān)系。

在這4個(gè)因素中，前3個(gè)都與具體的機(jī)器有關(guān)，我們?cè)诜治鏊惴ǖ臅r(shí)間效率時(shí)應(yīng)拋開(kāi)具體的機(jī)器，僅考慮算法本身的因素。因此，事前分析方法主要分析算法的時(shí)間效率與算法所處理的數(shù)據(jù)個(gè)數(shù)n的函數(shù)關(guān)系。這種方法在實(shí)際中比較常用。

算法的時(shí)間效率是算法所處理的數(shù)據(jù)個(gè)數(shù)n的函數(shù)，它也稱作算法的時(shí)間復(fù)雜度。

算法的時(shí)間復(fù)雜度分析通常采用O(f(n))表示法(O(f(n))讀做大O的f(n))。

定義T(n)＝O(f(n))當(dāng)且僅當(dāng)存在正常數(shù)c和n0，對(duì)所有的n(n≥n0)滿足T(n)≤c*f(n)。

通俗地說(shuō)，O(f(n))給出了函數(shù)f(n)的上界。由于上述定義中對(duì)所有的n(n≥n0)條件，只要n比較大一般均成立，而我們考慮的算法的時(shí)間復(fù)雜度也主要是針對(duì)數(shù)據(jù)個(gè)數(shù)n相當(dāng)大時(shí)的情況，所以在具體分析一個(gè)算法的時(shí)間復(fù)雜度T(n)時(shí)一般不考慮n為一個(gè)較小的數(shù)時(shí)T(n)≤c*f(n)不成立的情況。

令函數(shù)T(n)為算法的時(shí)間復(fù)雜度，其中n為算法處理的數(shù)據(jù)個(gè)數(shù)，則T(n)＝O(f(n))表示算法的時(shí)間復(fù)雜度隨數(shù)據(jù)個(gè)數(shù)n的增長(zhǎng)率和函數(shù)f(n)的增長(zhǎng)率相同，或者說(shuō)兩者具有相同的數(shù)量級(jí)。當(dāng)算法的時(shí)間復(fù)雜度T(n)和數(shù)據(jù)個(gè)數(shù)n無(wú)關(guān)系時(shí)，T(n)≤c*1，所以此時(shí)算法的時(shí)間復(fù)雜度T(n)＝O(1)；當(dāng)算法的時(shí)間復(fù)雜度T(n)和數(shù)據(jù)個(gè)數(shù)n為線性關(guān)系時(shí)，T(n)≤c*n，所以此時(shí)算法的時(shí)間復(fù)雜度T(n)＝O(n)；當(dāng)算法的時(shí)間復(fù)雜度T(n)和數(shù)據(jù)個(gè)數(shù)n為平方關(guān)系時(shí)，T(n)≤c*n2，所以此時(shí)算法的時(shí)間復(fù)雜度T(n)＝O(n2)；依此類推，還有O(n3)、O(lbn)、O(2n)等等?？梢?jiàn)，分析一個(gè)算法中基本語(yǔ)句的執(zhí)行次數(shù)和數(shù)據(jù)個(gè)數(shù)n的函數(shù)關(guān)系就可求出該算法的時(shí)間復(fù)雜度。

下面的4個(gè)例題是算法的時(shí)間復(fù)雜度分析的4種典型情況。設(shè)數(shù)組a和b在前邊部分已賦值，求如下兩個(gè)n階矩陣相乘運(yùn)算程序段的時(shí)間復(fù)雜度。for(i＝0;i<n;i＋＋)

for(j＝0;j<n;j＋＋)

{

c［i］［j］＝0;/*基本語(yǔ)句1*/

for(k＝0;k<n;k＋＋)

c［i］［j］＝c［i］［j］＋a［i］［k］*b［k］［j］;/*基本語(yǔ)句2*/

}解設(shè)基本語(yǔ)句的執(zhí)行次數(shù)為f(n)，有

f(n)＝n2＋n3因程序段的時(shí)間復(fù)雜度T(n)＝f(n)＝n2＋n3≤c*n3＝O(n3)，其中c為常數(shù)，所以該程序段的時(shí)間復(fù)雜度為O(n3)。

設(shè)n為如下程序段處理的數(shù)據(jù)個(gè)數(shù)，求如下程序段的時(shí)間復(fù)雜度。for(i＝1;i<＝n;i＝2*i)

printf("i＝%d＼n"，i);/*基本語(yǔ)句*/

解設(shè)基本語(yǔ)句的執(zhí)行次數(shù)為f(n)，有2f(n)≤n，即有f(n)≤lbn。因程序段的時(shí)間復(fù)雜度T(n)＝f(n)≤lbn≤c*lbn＝O(lbn)，其中c＝1，所以該程序段的時(shí)間復(fù)雜度為O(lbn)。

在很多情況下，算法中數(shù)據(jù)元素的取值情況不同，算法的時(shí)間復(fù)雜度也會(huì)不同。此時(shí)算法的時(shí)間復(fù)雜度應(yīng)是數(shù)據(jù)元素最壞情況下取值的時(shí)間復(fù)雜度或數(shù)據(jù)元素等概率取值情況下的平均(或稱期望)時(shí)間復(fù)雜度。

下面的算法是用冒泡排序法對(duì)數(shù)組a中的n個(gè)整數(shù)類型的數(shù)據(jù)元素(a［0］～a［n-1］)進(jìn)行從小到大排序的算法，求該算法的時(shí)間復(fù)雜度。

voidBubbleSort(inta［］，intn)

{

inti，j，flag＝1;

inttemp;

for(i＝1;i<n&&flag＝＝1;i＋＋)

{

flag＝0;

for(j＝0;j<n-i;j＋＋)

{

if(a［j］>a［j＋1］)

{

flag＝1;

temp＝a［j］;

a［j］＝a［j＋1］;

a［j＋1］＝temp;

}

}

}

}解這個(gè)算法的時(shí)間復(fù)雜度隨待排序數(shù)據(jù)的不同而不同。若某次排序過(guò)程中沒(méi)有任何兩個(gè)數(shù)組元素交換位置，則表明數(shù)組元素已排序完畢，此時(shí)算法將因標(biāo)記flag＝0不滿足循環(huán)條件而結(jié)束。但是，在最壞情況下，每次排序過(guò)程中都至少有兩個(gè)數(shù)組元素交換位置，因此，應(yīng)按最壞情況計(jì)算該算法的時(shí)間復(fù)雜度。

設(shè)基本語(yǔ)句的執(zhí)行次數(shù)為f(n)，最壞情況下有

f(n)≈n＋4*n2/2因算法的最壞時(shí)間復(fù)雜度T(n)＝f(n)≈n＋2*n2≤c*n2＝O(n2)，其中c為常數(shù)，所以該算法的最壞時(shí)間復(fù)雜度為O(n2)。

下面的算法是在一個(gè)有n個(gè)數(shù)據(jù)元素的數(shù)組a中刪除第i個(gè)位置的數(shù)組元素，要求當(dāng)刪除成功時(shí)數(shù)組元素個(gè)數(shù)減1，求該算法的時(shí)間復(fù)雜度。其中，數(shù)組下標(biāo)從0至n-1。

intDelete(inta［］，int*n，inti)

{

intj;

if(i<0||i>*n)return0;/*刪除位置錯(cuò)誤，失敗返回*/

for(j＝i＋1;j<*n;j＋＋)a［j-1］＝a［j］;/*順次移位填補(bǔ)*/

(*n)--;/*數(shù)組元素個(gè)數(shù)減1*/

return1;/*刪除成功返回*/

}解這個(gè)算法的時(shí)間復(fù)雜度隨刪除數(shù)據(jù)的位置不同而不同。當(dāng)刪除最后一個(gè)位置的數(shù)組元素時(shí)有i＝n-1，j＝i＋1＝n，此時(shí)因不需移位填補(bǔ)而循環(huán)次數(shù)為0;當(dāng)刪除倒數(shù)最后一個(gè)位置的數(shù)組元素時(shí)有i＝n-2，j＝i＋1＝n-1，此時(shí)因只需移位填補(bǔ)一次而循環(huán)次數(shù)為1;依此類推，當(dāng)刪除第一個(gè)位置的數(shù)組元素時(shí)有i＝0，j＝i＋1＝1，此時(shí)因需移位填補(bǔ)n-1次而循環(huán)次數(shù)為n-1。此時(shí)算法的時(shí)間復(fù)雜度應(yīng)是刪除數(shù)據(jù)的位置等概率取值情況下的平均時(shí)間復(fù)雜度。假設(shè)刪除任何位置上的數(shù)據(jù)元素都是等概率的(一般情況下均可做等概率假設(shè))，設(shè)Pi為刪除第i個(gè)位置上數(shù)據(jù)元素的概率，則有Pi＝1/n，設(shè)E為刪除數(shù)組元素的平均次數(shù)，則有

因該算法的平均時(shí)間復(fù)雜度T(n)＝E≤(n＋1)/2≤c*n＝O(n)，其中c為常數(shù)，所以該算法的平均時(shí)間復(fù)雜度為O(n)。

算法的時(shí)間復(fù)雜度是衡量一個(gè)算法好壞的重要指標(biāo)。一般來(lái)說(shuō)，具有多項(xiàng)式時(shí)間復(fù)雜度的算法是可接受、可實(shí)際使用的算法；具有指數(shù)時(shí)間復(fù)雜度的算法是只有當(dāng)n足夠小時(shí)才可使用的算法。表1-2給出了多項(xiàng)式增長(zhǎng)和指數(shù)增長(zhǎng)的比較。從表1-2中可以看出，當(dāng)n＝50時(shí)，多項(xiàng)式函數(shù)n3＝125000，而指數(shù)函數(shù)2n＝1.0×1015，n!＝3.0×1064，nn＝8.9×1084。通常，當(dāng)基本語(yǔ)句的計(jì)算次數(shù)超過(guò)1.0×1015時(shí)，該算法的計(jì)算機(jī)執(zhí)行時(shí)間就無(wú)法接受。我們可以計(jì)算如下，設(shè)計(jì)算機(jī)每秒可執(zhí)行1億(1.0×109)條基本語(yǔ)句，則執(zhí)行一個(gè)需1.0×1015次基本操作的算法需要的時(shí)間為

T＝1.0×1015/1.0×109＝1.0×106(秒)

＝1.0×106/3600＝277.8(小時(shí))

＝277.8/24＝11.6(天)

表1-2多項(xiàng)式增長(zhǎng)和指數(shù)增長(zhǎng)的比較

算法設(shè)計(jì)是軟件設(shè)計(jì)的基礎(chǔ)，也是初學(xué)者最感頭痛的問(wèn)題，本節(jié)將討論算法設(shè)計(jì)問(wèn)題。讀者要熟練掌握算法設(shè)計(jì)技術(shù)，必須要做大量的算法設(shè)計(jì)習(xí)題和上機(jī)實(shí)踐習(xí)題。

用C語(yǔ)言描述算法應(yīng)使用函數(shù)，C語(yǔ)言函數(shù)的一般形式如下：

1.4算法設(shè)計(jì)數(shù)據(jù)類型函數(shù)名(數(shù)據(jù)類型參數(shù)1，數(shù)據(jù)類型參數(shù)2，…，數(shù)據(jù)類型參數(shù)n)

{

函數(shù)體

}

因此，算法設(shè)計(jì)主要包括函數(shù)名設(shè)計(jì)、參數(shù)設(shè)計(jì)和函數(shù)體設(shè)計(jì)三部分。函數(shù)名設(shè)計(jì)包括函數(shù)名的用途和數(shù)據(jù)類型設(shè)計(jì)；參數(shù)設(shè)計(jì)包括參數(shù)的用途、參數(shù)類型和參數(shù)的數(shù)據(jù)類型設(shè)計(jì)；函數(shù)體設(shè)計(jì)是實(shí)現(xiàn)算法的語(yǔ)句序列的設(shè)計(jì)。算法的參數(shù)類型可分為輸入型參數(shù)、輸出型參數(shù)和輸入輸出混合型參數(shù)。例1-7是一個(gè)輸入型參數(shù)的例子，例1-8是一個(gè)輸出型參數(shù)的例子。

設(shè)計(jì)一個(gè)從兩個(gè)整數(shù)類型數(shù)據(jù)中得到較大數(shù)值的算法。

設(shè)計(jì)算法設(shè)計(jì)如下：intMax1(intx1，intx2)

{

if(x1>＝x2)returnx1;

elsereturnx2;

}在上述算法的設(shè)計(jì)中，函數(shù)名具有整數(shù)類型的返回值，用于返回得到的較大數(shù)值；兩個(gè)參數(shù)均為輸入?yún)?shù)(即值參)，參數(shù)的類型均為整數(shù)類型。

設(shè)計(jì)一個(gè)從三個(gè)整數(shù)類型數(shù)據(jù)中得到最大數(shù)值和次大數(shù)值的算法。設(shè)計(jì)分析：算法要有三個(gè)輸入?yún)?shù)，分別表示三個(gè)整數(shù)類型數(shù)據(jù)；由于算法要帶回兩個(gè)返回值，而函數(shù)名只能帶回一個(gè)返回值，因此必須設(shè)計(jì)兩個(gè)輸出參數(shù)(即變參)，用于帶回算法的兩個(gè)結(jié)果值，其類型為整數(shù)類型的指針類型。C語(yǔ)言中輸出參數(shù)是使用某種數(shù)據(jù)類型的指針類型，這里輸出參數(shù)即為整數(shù)類型的指針類型。

算法設(shè)計(jì)如下：voidMax2(intx1，intx2，intx3，int*y1，int*y2)

/*輸出參數(shù)y1和y2設(shè)計(jì)為指針類型*/

{

if(x1>＝x2&&x1>＝x3)

{

*y1＝x1;

if(x2>＝x3)*y2＝x2;

else*y2＝x3;

}

if(x1>＝x2&&x1<x3)

{

*y1＝x3;

if(x1>＝x2)*y2＝x1;

else*y2＝x2;

}

if(x1<x2&&x2>＝x3)

{

*y1＝x2;

if(x1>＝x3)*y2＝x1;

else*y2＝x3;

}

if(x1<x2&&x2<x3)

{

*y1＝x3;

if(x1>＝x2)*y2＝x1;

else*y2＝x2;

}

}一個(gè)測(cè)試主函數(shù)如下：＃include<stdio.h>

voidmain(void)

{

intv1＝5，v2＝9，v3＝7，f1，f2;

Max2(v1，v2，v3，&f1，&f2);/*&f1表示f1的地址，為指針類型*/

printf("f1＝%df2＝%d＼n"，f1，f2);

}主函數(shù)中實(shí)際輸入?yún)?shù)v1和算法中形式輸入?yún)?shù)x1的代換過(guò)程如圖1-5(a)和圖1-5(b)所示，實(shí)際輸入?yún)?shù)v2、v3和算法中形式輸入?yún)?shù)x2、x3的代換過(guò)程類同。此例中，形式參數(shù)x1中的值在函數(shù)體中未發(fā)生變化，如果x1中的值在函數(shù)體中發(fā)生變化，如x1變?yōu)?，主函數(shù)中實(shí)際參數(shù)v1的值也不會(huì)變化，v1將繼續(xù)保持為5。

圖1-5輸入?yún)?shù)的代換過(guò)程

(a)初始狀態(tài)；(b)結(jié)束狀態(tài)主函數(shù)中實(shí)際輸出參數(shù)f1和算法中形式輸出參數(shù)y1的代換過(guò)程如圖1-6(a)和圖1-6(b)所示，實(shí)際輸出參數(shù)f2和算法中形式輸出參數(shù)y2的代換過(guò)程類同。

圖1-6輸出參數(shù)的代換過(guò)程

(a)初始狀態(tài)；(b)結(jié)束狀態(tài)若函數(shù)的某個(gè)參數(shù)在函數(shù)的執(zhí)行過(guò)程中要發(fā)生改變，如既要作為輸入型參數(shù)向函數(shù)提供操作數(shù)據(jù)，又要作為輸出型參數(shù)帶回函數(shù)操作所改變的結(jié)果值，則這個(gè)參數(shù)是輸入輸出混合型參數(shù)。輸入輸出混合型參數(shù)應(yīng)按輸出型參數(shù)的設(shè)計(jì)方法設(shè)計(jì)，即將輸入輸出混合型參數(shù)設(shè)計(jì)成指針類型。

為了提高形式參數(shù)和實(shí)際參數(shù)結(jié)合的空間效率，實(shí)際的函數(shù)設(shè)計(jì)中有時(shí)也把輸入方式的參數(shù)設(shè)計(jì)成輸出方式的參