數(shù)據(jù)結構課件：緒論

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

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

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

例如，描述學生情況的數(shù)據(jù)可包括學生的學號、姓名、性別、年齡等。學生的學號、姓名、性別、年齡等數(shù)據(jù)就構成學生情況描述的數(shù)據(jù)項；學號、姓名、性別、年齡等數(shù)據(jù)項的一組數(shù)據(jù)就構成學生情況描述的一個數(shù)據(jù)元素。表1-1是一個有三個數(shù)據(jù)元素數(shù)值的學生情況表。

表1-1學生情況表在數(shù)據(jù)結構課程中，關于數(shù)據(jù)元素、數(shù)據(jù)項的描述都使用某種高級程序設計語言語法格式，高級程序設計語言要求在定義數(shù)據(jù)元素時必須指定每個數(shù)據(jù)項所屬的數(shù)據(jù)類型。本書采用C語言語法格式。學生情況數(shù)據(jù)元素的數(shù)據(jù)類型的C語言格式定義為：

structStudent

{

charnumber［8］;

charname［10］;

charsex［3］;

intage;

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

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

typedefstructStudent

{

charnumber［8］;

charname［10］;

charsex［3］;

intage;

}StudentType;

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

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

上述學生情況數(shù)據(jù)元素的數(shù)據(jù)類型定義為StudentType，即給出了具體的數(shù)據(jù)類型定義。但是，像數(shù)學一樣，數(shù)據(jù)結構課程討論的數(shù)據(jù)元素也可以是抽象數(shù)據(jù)元素，我們把沒有具體數(shù)據(jù)類型定義的數(shù)據(jù)元素稱作抽象數(shù)據(jù)元素。當討論抽象數(shù)據(jù)元素時，我們用符號DataType表示該抽象數(shù)據(jù)元素的數(shù)據(jù)類型。當軟件設計問題具體確定時，抽象數(shù)據(jù)元素的數(shù)據(jù)類型將被具體的數(shù)據(jù)類型取代。例如，當該抽象線性表的數(shù)據(jù)元素類型具體確定為表1-1的數(shù)據(jù)元素類型時，可通過重新定義抽象數(shù)據(jù)元素類型為StudentType，來具體確定該抽象數(shù)據(jù)元素的數(shù)據(jù)類型。具體的定義語句格式為：

typedefStudentTypeDataType;

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

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

圖1-1基本的數(shù)據(jù)邏輯結構形式

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

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

圖1-2基本存儲結構形式

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

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

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

類型是一組值的集合。

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

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

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

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

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

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

1.3.1算法

算法是描述求解問題方法的操作步驟集合。

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

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

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

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

{

inti;

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

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

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

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

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

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

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;

}

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

算法應滿足以下性質：

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

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

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

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

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

應用程序通常是通過調用函數(shù)(即算法)來完成的。程序和算法的惟一區(qū)別是程序允許無限循環(huán)，而算法不允許無限循環(huán)。構成無限循環(huán)的一組語句可以是：while(1)/*循環(huán)條件永真*/

{

……/*任意語句序列*/

}1.3.2算法設計的目標算法設計應滿足以下五條目標：

(1)正確性：算法應確切地滿足具體問題的需求，這是算法設計的基本目標。

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

(3)健壯性：當輸入非法數(shù)據(jù)時算法要能做出適當?shù)奶幚?，而不應產生不可預料的結果。

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

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

算法的執(zhí)行時間需通過根據(jù)該算法編制的程序在計算機上運行時所消耗的時間來度量。度量一個程序在計算機上的執(zhí)行時間通常有如下兩種方法：

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

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

①書寫算法的程序設計語言；

②編譯產生的機器語言代碼質量；

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

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

在這4個因素中，前3個都與具體的機器有關，我們在分析算法的時間效率時應拋開具體的機器，僅考慮算法本身的因素。因此，事前分析方法主要分析算法的時間效率與算法所處理的數(shù)據(jù)個數(shù)n的函數(shù)關系。這種方法在實際中比較常用。

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

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

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

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

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

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

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

{

c［i］［j］＝0;/*基本語句1*/

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

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

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

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

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

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

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

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

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

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;

}

}

}

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

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

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

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

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

{

intj;

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

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

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

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

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

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

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

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

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

＝277.8/24＝11.6(天)

表1-2多項式增長和指數(shù)增長的比較

算法設計是軟件設計的基礎，也是初學者最感頭痛的問題，本節(jié)將討論算法設計問題。讀者要熟練掌握算法設計技術，必須要做大量的算法設計習題和上機實踐習題。

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

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

{

函數(shù)體

}

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

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

設計算法設計如下：intMax1(intx1，intx2)

{

if(x1>＝x2)returnx1;

elsereturnx2;

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

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

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

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

{

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;

}

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

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

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

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

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

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