數(shù)據(jù)結(jié)構(gòu)課程PPT第1章緒論

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)教材教材: : 數(shù)據(jù)結(jié)構(gòu)教程（第數(shù)據(jù)結(jié)構(gòu)教程（第4版）版） 李春葆等，李春葆等， 清華大學(xué)出版社清華大學(xué)出版社 2012年年 （另配套學(xué)習(xí)指導(dǎo)和上機(jī)指導(dǎo)兩書(shū)，作為參考）（另配套學(xué)習(xí)指導(dǎo)和上機(jī)指導(dǎo)兩書(shū)，作為參考）參考書(shū)參考書(shū): : 1.1.數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）嚴(yán)蔚敏，吳偉民語(yǔ)言版）嚴(yán)蔚敏，吳偉民 清華大學(xué)出版社清華大學(xué)出版社 1997 2.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅc數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC+描述）殷人昆等描述）殷人昆等 清華大學(xué)清華大學(xué)出版社出版社 1999C語(yǔ)言語(yǔ)言 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 軟件工程軟件工程掌握基本編掌握基本編程方法程方法掌握數(shù)據(jù)組掌握數(shù)據(jù)組織和數(shù)據(jù)處織

2、和數(shù)據(jù)處理的方法理的方法掌握大型軟掌握大型軟件開(kāi)發(fā)方法件開(kāi)發(fā)方法學(xué)習(xí)識(shí)字學(xué)習(xí)識(shí)字學(xué)習(xí)寫(xiě)作文學(xué)習(xí)寫(xiě)作文學(xué)習(xí)寫(xiě)小說(shuō)學(xué)習(xí)寫(xiě)小說(shuō)基本要求課程關(guān)系與語(yǔ)文學(xué)習(xí)過(guò)程類比動(dòng)手能力（上機(jī)）前期課程前期課程數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)基礎(chǔ)計(jì)算機(jī)基礎(chǔ)C語(yǔ)言語(yǔ)言離散數(shù)學(xué)離散數(shù)學(xué)后期課程后期課程操作系統(tǒng)操作系統(tǒng)編譯原理編譯原理數(shù)據(jù)庫(kù)原理數(shù)據(jù)庫(kù)原理軟件工程軟件工程承上承上啟下啟下計(jì)算機(jī)科學(xué)課程體系（偏軟）計(jì)算機(jī)科學(xué)課程體系（偏軟）學(xué)習(xí)和講授方法學(xué)習(xí)和講授方法l 演譯法演譯法先學(xué)習(xí)先學(xué)習(xí)/ /講授理論知識(shí)，用知識(shí)解決問(wèn)題。講授理論知識(shí)，用知識(shí)解決問(wèn)題。l 歸納法歸納法先解決具體問(wèn)題，由此歸納出解決問(wèn)題的理論知先解決具體問(wèn)題，由此

3、歸納出解決問(wèn)題的理論知識(shí)。識(shí)。只有歸納法才能產(chǎn)生新的知識(shí)！只有歸納法才能產(chǎn)生新的知識(shí)！編寫(xiě)程序編寫(xiě)程序1編寫(xiě)程序編寫(xiě)程序2編寫(xiě)程序編寫(xiě)程序n.具有編程的基本能力具有編程的基本能力用計(jì)算機(jī)求解問(wèn)題的基本思路用計(jì)算機(jī)求解問(wèn)題的基本思路講授課時(shí)：講授課時(shí)：72上機(jī)課時(shí)：上機(jī)課時(shí)：36評(píng)分方式：評(píng)分方式：平時(shí)：平時(shí)：10上機(jī)：上機(jī)：10，作業(yè)：作業(yè)：10期末考試：期末考試：70授課安排授課安排第第1章章 緒論緒論 1.2 算法及其描述算法及其描述 1.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)1.3 算法分析算法分析 本章小結(jié)本章小結(jié)1.4 數(shù)據(jù)結(jié)構(gòu)算法程序數(shù)據(jù)結(jié)構(gòu)算法程序 數(shù)據(jù)：數(shù)據(jù)：是所有能被輸入到計(jì)算機(jī)中

4、是所有能被輸入到計(jì)算機(jī)中, ,且能被計(jì)算機(jī)處理的且能被計(jì)算機(jī)處理的符號(hào)的集合。它是計(jì)算機(jī)操作的對(duì)象的總稱符號(hào)的集合。它是計(jì)算機(jī)操作的對(duì)象的總稱, ,也是計(jì)算機(jī)也是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。處理的信息的某種特定的符號(hào)表示形式。數(shù)據(jù)元素：數(shù)據(jù)元素：是數(shù)據(jù)是數(shù)據(jù)( (集合集合) )中的一個(gè)中的一個(gè)“個(gè)體個(gè)體”, ,是數(shù)據(jù)的基是數(shù)據(jù)的基本單位。本單位。 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：是具有相同性質(zhì)的若干個(gè)數(shù)據(jù)元素的集合。是具有相同性質(zhì)的若干個(gè)數(shù)據(jù)元素的集合。 1.1.1 數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)的定義1.1 1.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu) 例如，例如，200402班為一個(gè)學(xué)生數(shù)據(jù)對(duì)象，其中的

5、班為一個(gè)學(xué)生數(shù)據(jù)對(duì)象，其中的“張三張三”是一個(gè)數(shù)據(jù)元素。是一個(gè)數(shù)據(jù)元素。 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：是指數(shù)據(jù)以及數(shù)據(jù)元素相互之間的聯(lián)系?？梢钥词侵笖?shù)據(jù)以及數(shù)據(jù)元素相互之間的聯(lián)系?？梢钥醋魇窍嗷ブg存在著某種特定關(guān)系的數(shù)據(jù)元素的集合。作是相互之間存在著某種特定關(guān)系的數(shù)據(jù)元素的集合。 因此，可時(shí)把數(shù)據(jù)結(jié)構(gòu)看成是因此，可時(shí)把數(shù)據(jù)結(jié)構(gòu)看成是帶結(jié)構(gòu)帶結(jié)構(gòu)的的數(shù)據(jù)元素的集合數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)包括如下幾個(gè)方面：數(shù)據(jù)結(jié)構(gòu)包括如下幾個(gè)方面： 數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)。數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式，即數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式，

6、即數(shù)據(jù)的數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)，也稱為數(shù)據(jù)的，也稱為數(shù)據(jù)的物理結(jié)構(gòu)物理結(jié)構(gòu)。施加在該數(shù)據(jù)上的操作，即數(shù)據(jù)的施加在該數(shù)據(jù)上的操作，即數(shù)據(jù)的運(yùn)算運(yùn)算。 例例1.1 有一個(gè)學(xué)生表如表有一個(gè)學(xué)生表如表1.1所示。這個(gè)表中的數(shù)據(jù)元所示。這個(gè)表中的數(shù)據(jù)元素是學(xué)生記錄，每個(gè)數(shù)據(jù)元素由四個(gè)數(shù)據(jù)項(xiàng)（即學(xué)號(hào)、素是學(xué)生記錄，每個(gè)數(shù)據(jù)元素由四個(gè)數(shù)據(jù)項(xiàng)（即學(xué)號(hào)、姓別、性別和班號(hào)）組成。姓別、性別和班號(hào)）組成。邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)運(yùn)算實(shí)現(xiàn)運(yùn)算實(shí)現(xiàn)學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別班號(hào)班號(hào)1張斌張斌男男99018劉麗劉麗女女990234李英李英女女990120陳華陳華男男990212王奇王奇男男990126董強(qiáng)董強(qiáng)男男9

7、9025王萍王萍女女9901表表1.1 學(xué)生表學(xué)生表 邏輯結(jié)構(gòu)表示邏輯結(jié)構(gòu)表示1（1）邏輯結(jié)構(gòu)）邏輯結(jié)構(gòu) 該表中的記錄順序反映了數(shù)據(jù)元素之間的邏輯關(guān)系該表中的記錄順序反映了數(shù)據(jù)元素之間的邏輯關(guān)系, ,為為線性線性關(guān)系關(guān)系。用學(xué)號(hào)標(biāo)識(shí)每個(gè)學(xué)生記錄，這種邏輯關(guān)系可以表示為：。用學(xué)號(hào)標(biāo)識(shí)每個(gè)學(xué)生記錄，這種邏輯關(guān)系可以表示為： , 其中尖括號(hào)其中尖括號(hào)“”表示元素表示元素ai和和ai+1之間是相鄰的，即之間是相鄰的，即ai在在ai+1之前，之前，ai+1在在ai之后。之后。邏輯結(jié)構(gòu)表示邏輯結(jié)構(gòu)表示2 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式就是數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式就是存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)。 邏輯結(jié)構(gòu)邏輯結(jié)

8、構(gòu)存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)映射映射映射應(yīng)滿足兩個(gè)條件：映射應(yīng)滿足兩個(gè)條件： 存儲(chǔ)元素存儲(chǔ)元素 存儲(chǔ)關(guān)系存儲(chǔ)關(guān)系存放學(xué)生表的結(jié)構(gòu)體數(shù)組存放學(xué)生表的結(jié)構(gòu)體數(shù)組Stud定義為：定義為： struct int no; /存儲(chǔ)學(xué)號(hào)存儲(chǔ)學(xué)號(hào) char name8; /存儲(chǔ)姓名存儲(chǔ)姓名 char sex2; /存儲(chǔ)性別存儲(chǔ)性別 char class4; /存儲(chǔ)班號(hào)存儲(chǔ)班號(hào) Stud7=1,“張斌張斌”,“男男”,“9901”, 5,王萍王萍,女女,9901;C/C+語(yǔ)言中，通常采用結(jié)構(gòu)體數(shù)組和鏈表兩種方式實(shí)現(xiàn)語(yǔ)言中，通常采用結(jié)構(gòu)體數(shù)組和鏈表兩種方式實(shí)現(xiàn)其存儲(chǔ)結(jié)構(gòu)。其存儲(chǔ)結(jié)構(gòu)。（2）存儲(chǔ)結(jié)構(gòu)）存儲(chǔ)結(jié)構(gòu) 結(jié)構(gòu)體數(shù)組結(jié)構(gòu)

9、體數(shù)組Stud各元素在內(nèi)存中順序存放，即第各元素在內(nèi)存中順序存放，即第i（1i6）個(gè)學(xué)生對(duì)應(yīng)的元素個(gè)學(xué)生對(duì)應(yīng)的元素Studi存放在第存放在第i+1個(gè)學(xué)生對(duì)應(yīng)的元素個(gè)學(xué)生對(duì)應(yīng)的元素Studi+1之前，之前，Studi+1正好在正好在Studi之后。之后。9901女女王萍王萍59901男男張斌張斌1 1Stud0Stud6Stud數(shù)組起始地址數(shù)組起始地址存儲(chǔ)結(jié)構(gòu)表示存儲(chǔ)結(jié)構(gòu)表示1存放學(xué)生表的鏈表的節(jié)點(diǎn)類型存放學(xué)生表的鏈表的節(jié)點(diǎn)類型StudType聲明為：聲明為：typedef struct studnode int no; /存儲(chǔ)學(xué)號(hào)存儲(chǔ)學(xué)號(hào) char name8; /存儲(chǔ)姓名存儲(chǔ)姓名 char

10、sex2; /存儲(chǔ)性別存儲(chǔ)性別 char class4; /存儲(chǔ)班號(hào)存儲(chǔ)班號(hào) struct studnode *next;/存儲(chǔ)指向下一個(gè)學(xué)生的指針存儲(chǔ)指向下一個(gè)學(xué)生的指針 StudType；鏈表首節(jié)點(diǎn)地址鏈表首節(jié)點(diǎn)地址head1張斌張斌男男 99018劉麗劉麗女女 990234李英李英女女 990120陳華陳華男男 990212王奇王奇男男 990126董強(qiáng)董強(qiáng)男男 99025王萍王萍女女 9901 學(xué)生表構(gòu)成的鏈表如右學(xué)生表構(gòu)成的鏈表如右圖所示。其中的圖所示。其中的head為第為第一個(gè)數(shù)據(jù)元素的指針。一個(gè)數(shù)據(jù)元素的指針。 學(xué)生表構(gòu)成的鏈表學(xué)生表構(gòu)成的鏈表存儲(chǔ)結(jié)構(gòu)表示存儲(chǔ)結(jié)構(gòu)表示2對(duì)于對(duì)于“

11、學(xué)生表學(xué)生表”這種數(shù)據(jù)結(jié)構(gòu)，可以進(jìn)行一系列的運(yùn)算：這種數(shù)據(jù)結(jié)構(gòu)，可以進(jìn)行一系列的運(yùn)算：（3）運(yùn)算實(shí)現(xiàn)）運(yùn)算實(shí)現(xiàn)增加一個(gè)學(xué)生記錄；增加一個(gè)學(xué)生記錄；刪除一個(gè)學(xué)生記錄；刪除一個(gè)學(xué)生記錄；查找性別為查找性別為“女女”的學(xué)生記錄；的學(xué)生記錄；查找班號(hào)為查找班號(hào)為“9902”的學(xué)生記錄；的學(xué)生記錄； 例如，查找學(xué)號(hào)為例如，查找學(xué)號(hào)為20的學(xué)生的姓名：的學(xué)生的姓名： 對(duì)于對(duì)于Stud數(shù)組：從數(shù)組：從Stud0開(kāi)始比較，開(kāi)始比較，Stud0.no不等于不等于20，再與再與Stud1.no比較，比較，直到，直到Stud3.no等于等于20，返回，返回S。 9902男男陳華陳華209901男男

12、張斌張斌1Stud0Stud3i3運(yùn)算的實(shí)現(xiàn)過(guò)程運(yùn)算的實(shí)現(xiàn)過(guò)程1對(duì)于對(duì)于head為首節(jié)點(diǎn)指針的為首節(jié)點(diǎn)指針的鏈表：鏈表：從從p=head所指節(jié)點(diǎn)開(kāi)始比較，所指節(jié)點(diǎn)開(kāi)始比較，p- -no不等于不等于20，從它的，從它的next得得到下一個(gè)節(jié)點(diǎn)的地址，再與下到下一個(gè)節(jié)點(diǎn)的地址，再與下一個(gè)節(jié)點(diǎn)的一個(gè)節(jié)點(diǎn)的no域比較，域比較，直，直到某節(jié)點(diǎn)的到某節(jié)點(diǎn)的no域等于域等于20，返回，返回其其p- -name域。域。head1張斌張斌男男 99018劉麗劉麗女女 990234李英李英女女 990120陳華陳華男男 990212王奇王奇男男 990126董強(qiáng)董強(qiáng)男男 99025王萍王萍女女 9901p運(yùn)算的實(shí)

13、現(xiàn)過(guò)程運(yùn)算的實(shí)現(xiàn)過(guò)程2結(jié)論：結(jié)論： 同一邏輯結(jié)構(gòu)可以對(duì)應(yīng)多種存儲(chǔ)結(jié)構(gòu)。同一邏輯結(jié)構(gòu)可以對(duì)應(yīng)多種存儲(chǔ)結(jié)構(gòu)。 同樣的運(yùn)算，在不同的存儲(chǔ)結(jié)構(gòu)中，其實(shí)現(xiàn)過(guò)程是不同同樣的運(yùn)算，在不同的存儲(chǔ)結(jié)構(gòu)中，其實(shí)現(xiàn)過(guò)程是不同的。的。思考題：思考題：數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)有什么不同？數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)有什么不同？ 為了更確切地描述一種數(shù)據(jù)結(jié)構(gòu)，通常采用二元組表為了更確切地描述一種數(shù)據(jù)結(jié)構(gòu)，通常采用二元組表示：示： B=(D,R) 其中，其中，B是一種數(shù)據(jù)結(jié)構(gòu)，它由數(shù)據(jù)元素的集合是一種數(shù)據(jù)結(jié)構(gòu)，它由數(shù)據(jù)元素的集合D和和D上二元關(guān)系的集合上二元關(guān)系的集合R所組成。其中：所組成。其中： D=di| 1in,n0 R

14、=rj | 1jm,m0 邏輯結(jié)構(gòu)的描述或表示：邏輯結(jié)構(gòu)的描述或表示：一種通用的邏輯結(jié)構(gòu)表示方法一種通用的邏輯結(jié)構(gòu)表示方法di表示集合表示集合D中的第中的第i個(gè)節(jié)點(diǎn)或數(shù)據(jù)元素。個(gè)節(jié)點(diǎn)或數(shù)據(jù)元素。n為為D中節(jié)點(diǎn)的個(gè)數(shù)，特別地，若中節(jié)點(diǎn)的個(gè)數(shù)，特別地，若n=0，則，則D是一個(gè)空集，是一個(gè)空集，因而因而B(niǎo)也就無(wú)結(jié)構(gòu)可言，有時(shí)也可以認(rèn)為它具有任一結(jié)構(gòu)。也就無(wú)結(jié)構(gòu)可言，有時(shí)也可以認(rèn)為它具有任一結(jié)構(gòu)。rj表示集合表示集合R中的第中的第j個(gè)關(guān)系，每個(gè)關(guān)系用序偶表示。個(gè)關(guān)系，每個(gè)關(guān)系用序偶表示。m為為R中關(guān)系的個(gè)數(shù)中關(guān)系的個(gè)數(shù),特別地，若特別地，若m=0，則，則R是一個(gè)空集，是一個(gè)空集，表明集合表明集合D中的

15、元素間不存在任何關(guān)系，彼此是獨(dú)立的。中的元素間不存在任何關(guān)系，彼此是獨(dú)立的。其中：其中：序偶序偶（x,yD） x為第一元素，為第一元素，y為第二元素。為第二元素。x為為y的的前驅(qū)元素前驅(qū)元素。y為為x的的后繼元素后繼元素。若某個(gè)節(jié)點(diǎn)沒(méi)有前驅(qū)元素，則稱該節(jié)點(diǎn)為若某個(gè)節(jié)點(diǎn)沒(méi)有前驅(qū)元素，則稱該節(jié)點(diǎn)為開(kāi)始元素開(kāi)始元素；若某個(gè)節(jié)點(diǎn)沒(méi)有后繼元素，則稱該節(jié)點(diǎn)為若某個(gè)節(jié)點(diǎn)沒(méi)有后繼元素，則稱該節(jié)點(diǎn)為終端元素終端元素。 說(shuō)明：說(shuō)明：表示有向關(guān)系，表示有向關(guān)系，(x,y)表示無(wú)向關(guān)系。表示無(wú)向關(guān)系。采用離散數(shù)學(xué)的表示方法。采用離散數(shù)學(xué)的表示方法。每個(gè)關(guān)系的用序偶表示：每個(gè)關(guān)系的用序偶表示：區(qū)號(hào)區(qū)號(hào)城市名城市名說(shuō)明說(shuō)

16、明010Beijing首都首都021Shanghai直轄市直轄市027Wuhan湖北省省會(huì)湖北省省會(huì)029Xian陜西省省會(huì)陜西省省會(huì)025Nanjing江蘇省省會(huì)江蘇省省會(huì)City=(D,R)D=010,021,027,029,025R=rr=,區(qū)號(hào)為關(guān)鍵字區(qū)號(hào)為關(guān)鍵字例如，有一個(gè)如下表所示的城市表，假設(shè)城市名是唯一的，例如，有一個(gè)如下表所示的城市表，假設(shè)城市名是唯一的，給出其邏輯結(jié)構(gòu)的二元組表示。給出其邏輯結(jié)構(gòu)的二元組表示。城市表城市表City中共有中共有5個(gè)記錄，其邏輯結(jié)構(gòu)的二元組表示如下：個(gè)記錄，其邏輯結(jié)構(gòu)的二元組表示如下：又例如，有如下數(shù)據(jù)即一個(gè)矩陣：又例如，有如下數(shù)據(jù)即一個(gè)矩陣：

17、119105471281362 對(duì)應(yīng)的二元組表示為對(duì)應(yīng)的二元組表示為B=(D,R)，其中：，其中： D=2,6,3,1,8,12,7,4,5,10,9,11 R=r1,r2 其中，其中，r1表示行關(guān)系，表示行關(guān)系，r2表示列關(guān)系表示列關(guān)系 r1=, , r2=, , 一個(gè)二維數(shù)組一個(gè)二維數(shù)組 可以可以利用圖形形象地表示邏輯結(jié)構(gòu)利用圖形形象地表示邏輯結(jié)構(gòu)。 例如，上述例如，上述“學(xué)生表學(xué)生表”數(shù)據(jù)結(jié)構(gòu)用下圖的圖形表示。數(shù)據(jù)結(jié)構(gòu)用下圖的圖形表示。學(xué)生表數(shù)據(jù)結(jié)構(gòu)圖示學(xué)生表數(shù)據(jù)結(jié)構(gòu)圖（1）線性結(jié)構(gòu)）線性結(jié)構(gòu) 節(jié)點(diǎn)之間關(guān)系：一對(duì)一。節(jié)點(diǎn)之間關(guān)系：一對(duì)一。 特點(diǎn)：特點(diǎn)：開(kāi)始節(jié)點(diǎn)和

18、終端節(jié)點(diǎn)都是唯一的開(kāi)始節(jié)點(diǎn)和終端節(jié)點(diǎn)都是唯一的, ,除了開(kāi)始節(jié)點(diǎn)和終除了開(kāi)始節(jié)點(diǎn)和終端節(jié)點(diǎn)以外端節(jié)點(diǎn)以外, ,其余節(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)節(jié)點(diǎn)其余節(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)節(jié)點(diǎn), ,有且僅有一個(gè)有且僅有一個(gè)后繼節(jié)點(diǎn)。線性表就是典型的線性結(jié)構(gòu)。后繼節(jié)點(diǎn)。線性表就是典型的線性結(jié)構(gòu)。1.1.2 邏輯結(jié)構(gòu)類型邏輯結(jié)構(gòu)類型 （2）樹(shù)形結(jié)構(gòu)）樹(shù)形結(jié)構(gòu) 節(jié)點(diǎn)之間關(guān)系：一對(duì)多。節(jié)點(diǎn)之間關(guān)系：一對(duì)多。 特點(diǎn)：特點(diǎn)：開(kāi)始節(jié)點(diǎn)唯一，終端節(jié)點(diǎn)不唯一。除終端節(jié)開(kāi)始節(jié)點(diǎn)唯一，終端節(jié)點(diǎn)不唯一。除終端節(jié)點(diǎn)以外，每個(gè)節(jié)點(diǎn)有一個(gè)或多個(gè)后續(xù)節(jié)點(diǎn)；除開(kāi)始節(jié)點(diǎn)以外，每個(gè)節(jié)點(diǎn)有一個(gè)或多個(gè)后續(xù)節(jié)點(diǎn)；除開(kāi)始節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)有且僅有一個(gè)前驅(qū)節(jié)點(diǎn)。點(diǎn)

19、外，每個(gè)節(jié)點(diǎn)有且僅有一個(gè)前驅(qū)節(jié)點(diǎn)。 （3）圖形結(jié)構(gòu)）圖形結(jié)構(gòu) 節(jié)點(diǎn)之間關(guān)系：多對(duì)多。節(jié)點(diǎn)之間關(guān)系：多對(duì)多。 特點(diǎn)：特點(diǎn)：沒(méi)有開(kāi)始節(jié)點(diǎn)和終端節(jié)點(diǎn)，所有節(jié)點(diǎn)都可沒(méi)有開(kāi)始節(jié)點(diǎn)和終端節(jié)點(diǎn)，所有節(jié)點(diǎn)都可能有多個(gè)前驅(qū)節(jié)點(diǎn)和多個(gè)后繼節(jié)點(diǎn)。能有多個(gè)前驅(qū)節(jié)點(diǎn)和多個(gè)后繼節(jié)點(diǎn)。1.1.3 存儲(chǔ)結(jié)構(gòu)類型存儲(chǔ)結(jié)構(gòu)類型（2）鏈?zhǔn)酱鎯?chǔ)方法）鏈?zhǔn)酱鎯?chǔ)方法 （3）索引存儲(chǔ)方法）索引存儲(chǔ)方法 （4） 散列（哈希）存儲(chǔ)方法散列（哈希）存儲(chǔ)方法 （1）順序存儲(chǔ)方法）順序存儲(chǔ)方法 前面通過(guò)示例已介紹前面通過(guò)示例已介紹第第9 9章介紹章介紹 （1）數(shù)據(jù)類型）數(shù)據(jù)類型 高級(jí)程序語(yǔ)言中高級(jí)程序語(yǔ)言中,一般須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或一般

20、須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式表達(dá)式,明確說(shuō)明它們所屬的數(shù)據(jù)類型。不同類型的變量明確說(shuō)明它們所屬的數(shù)據(jù)類型。不同類型的變量,其所其所能取的值的范圍不同能取的值的范圍不同,所能進(jìn)行的操作不同。所能進(jìn)行的操作不同。 數(shù)據(jù)類型數(shù)據(jù)類型是一個(gè)值的集合和定義在此集合上的一組操作是一個(gè)值的集合和定義在此集合上的一組操作的總稱。的總稱。1.1.4 數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型 如如C/C+中的中的int就是整型數(shù)據(jù)類型。它是所有整數(shù)的集合就是整型數(shù)據(jù)類型。它是所有整數(shù)的集合（在（在16位計(jì)算機(jī)中為位計(jì)算機(jī)中為3276832767的全體整數(shù)）和相關(guān)的整的全體整數(shù)）和相關(guān)的整數(shù)運(yùn)算（如、等）。數(shù)

21、運(yùn)算（如、等）。int i=2,j=5,k;k=i+j;.因?yàn)橐驗(yàn)閕、j和和k都屬于都屬于int，而，而int提提供了各種運(yùn)算，所以可以進(jìn)行相供了各種運(yùn)算，所以可以進(jìn)行相應(yīng)運(yùn)算。應(yīng)運(yùn)算。int i=9999999999;i*; （2）抽象數(shù)據(jù)類型）抽象數(shù)據(jù)類型 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（Abstract Data Type簡(jiǎn)寫(xiě)為簡(jiǎn)寫(xiě)為ADT）指的是）指的是用戶進(jìn)行軟件系統(tǒng)設(shè)計(jì)時(shí)從問(wèn)題的數(shù)學(xué)模型中抽象出來(lái)的邏用戶進(jìn)行軟件系統(tǒng)設(shè)計(jì)時(shí)從問(wèn)題的數(shù)學(xué)模型中抽象出來(lái)的邏輯數(shù)據(jù)結(jié)構(gòu)和邏輯數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算，而不考慮計(jì)算機(jī)的具輯數(shù)據(jù)結(jié)構(gòu)和邏輯數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算，而不考慮計(jì)算機(jī)的具體存儲(chǔ)結(jié)構(gòu)和運(yùn)算的具體實(shí)現(xiàn)算法。體

22、存儲(chǔ)結(jié)構(gòu)和運(yùn)算的具體實(shí)現(xiàn)算法。 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型=邏輯結(jié)構(gòu)抽象運(yùn)算邏輯結(jié)構(gòu)抽象運(yùn)算 抽象數(shù)據(jù)類型實(shí)質(zhì)上就是描述一個(gè)求解問(wèn)題本身（與計(jì)算抽象數(shù)據(jù)類型實(shí)質(zhì)上就是描述一個(gè)求解問(wèn)題本身（與計(jì)算機(jī)無(wú)關(guān)），計(jì)算機(jī)人員就是在理解問(wèn)題基礎(chǔ)上實(shí)現(xiàn)用計(jì)算機(jī)機(jī)無(wú)關(guān)），計(jì)算機(jī)人員就是在理解問(wèn)題基礎(chǔ)上實(shí)現(xiàn)用計(jì)算機(jī)求解問(wèn)題的過(guò)程。求解問(wèn)題的過(guò)程。例如，抽象數(shù)據(jù)類型復(fù)數(shù)的定義：例如，抽象數(shù)據(jù)類型復(fù)數(shù)的定義：ADT Complex 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象： D=e1,e2 | e1,e2均為實(shí)數(shù)均為實(shí)數(shù)數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R= | e1是復(fù)數(shù)的實(shí)數(shù)部分，是復(fù)數(shù)的實(shí)數(shù)部分，e2 是復(fù)數(shù)的是復(fù)數(shù)的 虛數(shù)部分虛數(shù)部分 復(fù)數(shù)形

23、式：復(fù)數(shù)形式：e1+e2i或或（e1，e2）基本操作：基本操作： AssignComplex(&z,v1,v2)：構(gòu)造復(fù)數(shù)：構(gòu)造復(fù)數(shù)Z。 DestroyComplex(&z)：復(fù)數(shù)：復(fù)數(shù)z被銷毀。被銷毀。 GetReal(z,&real)：返回復(fù)數(shù)：返回復(fù)數(shù)z的實(shí)部值。的實(shí)部值。 GetImag(z,&Imag)：返回復(fù)數(shù)：返回復(fù)數(shù)z的虛部值。的虛部值。 Add(z1,z2,&sum)：返回兩個(gè)復(fù)數(shù)：返回兩個(gè)復(fù)數(shù)z1、z2的和。的和。 ADT Complex運(yùn)算功能描述運(yùn)算功能描述思考題：思考題：數(shù)據(jù)類型和抽象數(shù)據(jù)類型有什么不同？數(shù)據(jù)類型和抽象數(shù)據(jù)類型有

24、什么不同？1.2.1 什么是算法什么是算法 數(shù)據(jù)元素之間的關(guān)系有邏輯關(guān)系和物理關(guān)系，對(duì)應(yīng)的操數(shù)據(jù)元素之間的關(guān)系有邏輯關(guān)系和物理關(guān)系，對(duì)應(yīng)的操作有作有邏輯結(jié)構(gòu)上的操作功能邏輯結(jié)構(gòu)上的操作功能和和具體存儲(chǔ)結(jié)構(gòu)上的操作實(shí)現(xiàn)具體存儲(chǔ)結(jié)構(gòu)上的操作實(shí)現(xiàn)。 通常把具體存儲(chǔ)結(jié)構(gòu)上的操作實(shí)現(xiàn)步驟或過(guò)程稱為算法。通常把具體存儲(chǔ)結(jié)構(gòu)上的操作實(shí)現(xiàn)步驟或過(guò)程稱為算法。屬屬ADT的一部分的一部分算法實(shí)現(xiàn)算法實(shí)現(xiàn)1.2 算法及其描述算法及其描述 算法的五個(gè)重要的特性算法的五個(gè)重要的特性 （1） 有窮性：在有窮步之后結(jié)束。有窮性：在有窮步之后結(jié)束。（2） 確定性：無(wú)二義性。確定性：無(wú)二義性。 （3） 可行性：可通過(guò)基本運(yùn)算有

25、限次執(zhí)行來(lái)實(shí)現(xiàn)?？尚行裕嚎赏ㄟ^(guò)基本運(yùn)算有限次執(zhí)行來(lái)實(shí)現(xiàn)。（4） 有輸入有輸入 （5） 有輸出有輸出 表示存在數(shù)據(jù)處理表示存在數(shù)據(jù)處理例如，考慮下列兩段描述：例如，考慮下列兩段描述：（1）描述一）描述一void exam1() int n2; while (n%20) nn+2; printf(%dn,n);華中科大考研題華中科大考研題 （2） 描述二描述二void exam2() int x,y; y=0; x=5/y; printf(“%d,%dn”,x,y); 這兩段描述均不能滿足算法的特征，試問(wèn)它們違反了這兩段描述均不能滿足算法的特征，試問(wèn)它們違反了哪些特征？哪些特征？ 解：解：（1）算

26、法是一個(gè)死循環(huán)，違反了算法的有窮性）算法是一個(gè)死循環(huán)，違反了算法的有窮性特征。特征。 （2）算法包含除零錯(cuò)誤，違反了算法的可行性特征）算法包含除零錯(cuò)誤，違反了算法的可行性特征。思考題：思考題：算法和程序有什么不同？算法和程序有什么不同？ 1.2.2 算法描述算法描述 本書(shū)中采用本書(shū)中采用C/C+語(yǔ)言描述算法。語(yǔ)言描述算法。 說(shuō)明：說(shuō)明：C+語(yǔ)言中提供了一種語(yǔ)言中提供了一種引用引用運(yùn)算符運(yùn)算符“&”，引用，引用是個(gè)別名，當(dāng)建立引用時(shí)，程序用另一個(gè)已定義的變量是個(gè)別名，當(dāng)建立引用時(shí)，程序用另一個(gè)已定義的變量或?qū)ο螅繕?biāo)）的名字初始化它，從那時(shí)起，引用作為或?qū)ο螅繕?biāo)）的名字初始化它，從那時(shí)

27、起，引用作為目標(biāo)的別名而使用，對(duì)引用的改動(dòng)實(shí)際就是對(duì)目標(biāo)的改目標(biāo)的別名而使用，對(duì)引用的改動(dòng)實(shí)際就是對(duì)目標(biāo)的改動(dòng)。動(dòng)。 注意：注意：Turbo C不支持引用類型，不支持引用類型，VC+、Dev C+支支持引用類型。持引用類型。 編寫(xiě)一個(gè)函數(shù)編寫(xiě)一個(gè)函數(shù)swap1(x,y)，當(dāng)執(zhí)行語(yǔ)句，當(dāng)執(zhí)行語(yǔ)句swap1(a,b)時(shí)，交時(shí)，交換換a和和b的值。的值。 void swap1(int x,int y) int tmp; tmp=x;x=y;y=tmp; 注意：注意：a和和b的值不會(huì)發(fā)生了交換。的值不會(huì)發(fā)生了交換。 為此，采用指針的方式來(lái)回傳形參的值，需將上述函數(shù)為此，采用指針的方式來(lái)回傳形參的值，需

28、將上述函數(shù)改為：改為： void swap2(int *x,int *y) int tmp; tmp=*x;/將將x的值放在的值放在tmp中中 *x=*y; /將將x所指的值改為所指的值改為*y *y=tmp； /將將y所指的值改為所指的值改為tmp 上述函數(shù)的調(diào)用改為上述函數(shù)的調(diào)用改為swap2(&a,&b)，顯然遠(yuǎn)不如采用引，顯然遠(yuǎn)不如采用引用方式簡(jiǎn)潔。所以本書(shū)后面很多算法都采用引用形參。用方式簡(jiǎn)潔。所以本書(shū)后面很多算法都采用引用形參?！耙靡谩钡母拍畹母拍罾纾豪纾?int a=4; /a為普通的整型變量為普通的整型變量 int &b=a; /b是是a的引用變

29、量的引用變量 這里說(shuō)明這里說(shuō)明b變量是變量變量是變量a的引用，的引用，b也等于也等于4，之后這兩，之后這兩個(gè)變量同步改變。當(dāng)個(gè)變量同步改變。當(dāng)a改變時(shí)改變時(shí)b也同步改變，同樣，當(dāng)也同步改變，同樣，當(dāng)b改改變時(shí)變時(shí)a也同步改變。也同步改變。void main() int a=2; int &b=a; printf(a=%d,b=%dn,a,b); /輸出：輸出：a=2,b=2 b+; printf(a=%d,b=%dn,a,b); /輸出：輸出：a=3,b=3 a+; printf(a=%d,b=%dn,a,b); /輸出：輸出：a=4,b=4 引用常用于函數(shù)形參中，采用引用型形參時(shí)，在

30、函數(shù)調(diào)用引用常用于函數(shù)形參中，采用引用型形參時(shí)，在函數(shù)調(diào)用時(shí)將形參的改變回傳給實(shí)參，例如，有如下函數(shù)（其中的形參時(shí)將形參的改變回傳給實(shí)參，例如，有如下函數(shù)（其中的形參均為引用型形參）：均為引用型形參）： void swap(int &x,int &y) /形參前的形參前的“&”符號(hào)不是指針運(yùn)算符符號(hào)不是指針運(yùn)算符 int tmp=x; x=y;y=tmp 當(dāng)用執(zhí)行語(yǔ)句當(dāng)用執(zhí)行語(yǔ)句swap(a,b)時(shí)，時(shí)，a和和b的值發(fā)生了交換。的值發(fā)生了交換。void fun1(int n) int m=2; fun2(m); printf(“%dn”,m);void fun2(int

31、 x) x+; printf(“%dn”,x);實(shí)參實(shí)參普通形參普通形參fun1(m)fun2(x)實(shí)參到形參單向?qū)崊⒌叫螀蜗蛑祩鬟f值傳遞普通的參數(shù)傳遞普通的參數(shù)傳遞void fun1(int n) int m=2; fun2(m); printf(“%dn”,m);void fun2(int &x) x+; printf(“%dn”,x);實(shí)參實(shí)參引用型形參引用型形參fun1(m)fun2(x)實(shí)參到形參單向?qū)崊⒌叫螀蜗蛑祩鬟f值傳遞引用類型的參數(shù)傳遞引用類型的參數(shù)傳遞形參回傳給實(shí)參，實(shí)參和形參回傳給實(shí)參，實(shí)參和形參可步發(fā)生改變形參可步發(fā)生改變 例例1.3 編寫(xiě)一個(gè)算法編寫(xiě)一個(gè)算法

32、, 讀入三個(gè)整數(shù)讀入三個(gè)整數(shù)x、y和和z的值，要求從大的值，要求從大到小輸出這三個(gè)數(shù)。到小輸出這三個(gè)數(shù)。 解：解：依次輸入依次輸入x、y和和z這三個(gè)整數(shù)，通過(guò)比較交換后，使得這三個(gè)整數(shù)，通過(guò)比較交換后，使得xyz，然后輸出，然后輸出x、y和和z。 在算法中應(yīng)考慮對(duì)這三個(gè)元素作盡可能少的比較和移動(dòng)，在算法中應(yīng)考慮對(duì)這三個(gè)元素作盡可能少的比較和移動(dòng)，如下述算法在最壞的情況下只需進(jìn)行如下述算法在最壞的情況下只需進(jìn)行3次比較和次比較和7次移動(dòng)。次移動(dòng)。用用C/C+描述算法示例描述算法示例void Descending() printf(輸入輸入x,y,z); scanf(%d,%d,%d,&x

33、,&y,&z); if (x=y if (yz if (x=temp) y=temp； else y=x;x=temp; printf(%d,%d,%dn,x,y,z); 1.3 算法分析算法分析 1.3.2 算法時(shí)間復(fù)雜度分析算法時(shí)間復(fù)雜度分析 1.3.3 算法空間復(fù)雜度分析算法空間復(fù)雜度分析 1.3.1 算法設(shè)計(jì)的目標(biāo)算法設(shè)計(jì)的目標(biāo)1.3.1 算法設(shè)計(jì)的目標(biāo)算法設(shè)計(jì)的目標(biāo)算法設(shè)計(jì)應(yīng)滿足以下幾條目標(biāo)：算法設(shè)計(jì)應(yīng)滿足以下幾條目標(biāo)：（1）正確性）正確性 要求算法能夠正確地執(zhí)行預(yù)先規(guī)定的功能和要求算法能夠正確地執(zhí)行預(yù)先規(guī)定的功能和性能要求。這是最重要也是最基本的標(biāo)準(zhǔn)。性能要求。這是

34、最重要也是最基本的標(biāo)準(zhǔn)。（2）可使用性）可使用性 要求算法能夠很方便地使用。這個(gè)特性也要求算法能夠很方便地使用。這個(gè)特性也叫做用戶友好性。叫做用戶友好性。（3）可讀性）可讀性 算法應(yīng)該易于人的理解，也就是可讀性好。算法應(yīng)該易于人的理解，也就是可讀性好。為了達(dá)到這個(gè)要求，算法的邏輯必須是清晰的、簡(jiǎn)單的為了達(dá)到這個(gè)要求，算法的邏輯必須是清晰的、簡(jiǎn)單的和結(jié)構(gòu)化的。和結(jié)構(gòu)化的。（4）健壯性）健壯性 要求算法具有很好的容錯(cuò)性，即提供異常處要求算法具有很好的容錯(cuò)性，即提供異常處理，能夠?qū)Σ缓侠淼臄?shù)據(jù)進(jìn)行檢查。不經(jīng)常出現(xiàn)異常中理，能夠?qū)Σ缓侠淼臄?shù)據(jù)進(jìn)行檢查。不經(jīng)常出現(xiàn)異常中斷或死機(jī)現(xiàn)象。斷或死機(jī)現(xiàn)象。（5）

35、高效率與低存儲(chǔ)量需求）高效率與低存儲(chǔ)量需求 通常算法的效率主要指算法通常算法的效率主要指算法的執(zhí)行時(shí)間。對(duì)于同一個(gè)問(wèn)題如果有多種算法可以求解，的執(zhí)行時(shí)間。對(duì)于同一個(gè)問(wèn)題如果有多種算法可以求解，執(zhí)行時(shí)間短的算法效率高。算法存儲(chǔ)量指的是算法執(zhí)行執(zhí)行時(shí)間短的算法效率高。算法存儲(chǔ)量指的是算法執(zhí)行過(guò)程中所需的最大存儲(chǔ)空間。效率和低存儲(chǔ)量這兩者都過(guò)程中所需的最大存儲(chǔ)空間。效率和低存儲(chǔ)量這兩者都與問(wèn)題的規(guī)模有關(guān)。與問(wèn)題的規(guī)模有關(guān)。 一個(gè)算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)三種）和一個(gè)算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)三種）和原操作（指固有數(shù)據(jù)類型的操作，如原操作（指固有數(shù)據(jù)類型的操作，如n+等）構(gòu)成的，則等）

36、構(gòu)成的，則算法時(shí)間取決于兩者的綜合效果。算法時(shí)間取決于兩者的綜合效果。1.3.2 算法時(shí)間復(fù)雜度分析算法時(shí)間復(fù)雜度分析 控制語(yǔ)句控制語(yǔ)句1原操作原操作控制語(yǔ)句控制語(yǔ)句n原操作原操作一個(gè)算法的構(gòu)成一個(gè)算法的構(gòu)成例如：例如：void fun(int a,int n) int i; for (i=0;in;i+) ai=2*i; for (i=0;in;i+) printf(“%d “,ai); printf(“n”);算法描述的語(yǔ)言不同算法描述的語(yǔ)言不同算法執(zhí)行的環(huán)境不同算法執(zhí)行的環(huán)境不同其他因素其他因素所以不能用絕對(duì)執(zhí)行時(shí)間進(jìn)行比較。所以不能用絕對(duì)執(zhí)行時(shí)間進(jìn)行比較。同一問(wèn)題可以采用多種算法實(shí)現(xiàn)。

37、如何比較同一問(wèn)題可以采用多種算法實(shí)現(xiàn)。如何比較算法執(zhí)行效率？算法執(zhí)行效率？ 為了便于比較同一問(wèn)題的不同算法，通常從算法中為了便于比較同一問(wèn)題的不同算法，通常從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是基本運(yùn)算的選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是基本運(yùn)算的原操作原操作（以下將基本運(yùn)算的原操作簡(jiǎn)稱為（以下將基本運(yùn)算的原操作簡(jiǎn)稱為基本運(yùn)算基本運(yùn)算）。）。 算法執(zhí)行時(shí)間大致為基本運(yùn)算所需的時(shí)間與其運(yùn)算次算法執(zhí)行時(shí)間大致為基本運(yùn)算所需的時(shí)間與其運(yùn)算次數(shù)（也稱為數(shù)（也稱為頻度頻度）的乘積。）的乘積。 被視為算法基本運(yùn)算的一般是最深層循環(huán)內(nèi)的語(yǔ)句。被視為算法基本運(yùn)算的一般是最深層循環(huán)內(nèi)的語(yǔ)句。 在一個(gè)算法中在一個(gè)算法

38、中, ,進(jìn)行基本運(yùn)算的次數(shù)越少進(jìn)行基本運(yùn)算的次數(shù)越少, ,其運(yùn)行時(shí)間也就其運(yùn)行時(shí)間也就相對(duì)地越少；基本運(yùn)算次數(shù)越多相對(duì)地越少；基本運(yùn)算次數(shù)越多, ,其運(yùn)行時(shí)間也就相對(duì)地越多。其運(yùn)行時(shí)間也就相對(duì)地越多。 所以所以, ,通常把算法中包含基本運(yùn)算次數(shù)的多少稱為算法的通常把算法中包含基本運(yùn)算次數(shù)的多少稱為算法的時(shí)間復(fù)雜度，也就是說(shuō)，一個(gè)算法的時(shí)間復(fù)雜度是指該算法的時(shí)間復(fù)雜度，也就是說(shuō)，一個(gè)算法的時(shí)間復(fù)雜度是指該算法的基本運(yùn)算次數(shù)基本運(yùn)算次數(shù)。 算法中基本運(yùn)算次數(shù)算法中基本運(yùn)算次數(shù)T(n)是問(wèn)題規(guī)模是問(wèn)題規(guī)模n的某個(gè)函數(shù)的某個(gè)函數(shù)f(n)，記作，記作： T(n)=O(f(n) 記號(hào)記號(hào)“O”讀作讀作“大

39、大O”，它表示隨問(wèn)題規(guī)模，它表示隨問(wèn)題規(guī)模n的增大算法的增大算法執(zhí)行時(shí)間的增長(zhǎng)率和執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同。的增長(zhǎng)率相同?！癘”的形式定義為：的形式定義為： 若若f(n)是正整數(shù)是正整數(shù)n的一個(gè)函數(shù)，則的一個(gè)函數(shù)，則T(n)=O(f(n)表示存在一表示存在一個(gè)正的常數(shù)個(gè)正的常數(shù)M，使得當(dāng)，使得當(dāng)nn0時(shí)都滿足：時(shí)都滿足： |T(n)|M|f(n)| 也就是只求出也就是只求出T(n)的最高階，忽略其低階項(xiàng)和的最高階，忽略其低階項(xiàng)和常系數(shù)，這樣既可簡(jiǎn)化常系數(shù)，這樣既可簡(jiǎn)化T(n)的計(jì)算，又能比較客觀的計(jì)算，又能比較客觀地反映出當(dāng)?shù)胤从吵霎?dāng)n很大時(shí)算法的時(shí)間性能。很大時(shí)算法的時(shí)間性能。

40、 例如，例如，T(n)=3n2-5n+10000=O(n2)本質(zhì)上講，是一種最高本質(zhì)上講，是一種最高數(shù)量級(jí)的比較數(shù)量級(jí)的比較一個(gè)沒(méi)有循環(huán)的算法的基本運(yùn)算次數(shù)與問(wèn)題規(guī)模一個(gè)沒(méi)有循環(huán)的算法的基本運(yùn)算次數(shù)與問(wèn)題規(guī)模n無(wú)關(guān)，記作無(wú)關(guān)，記作O(1)，也稱作常數(shù)階。，也稱作常數(shù)階。一個(gè)只有一重循環(huán)的算法的基本運(yùn)算次數(shù)與問(wèn)題規(guī)模一個(gè)只有一重循環(huán)的算法的基本運(yùn)算次數(shù)與問(wèn)題規(guī)模n的增長(zhǎng)的增長(zhǎng)呈線性增大關(guān)系，記作呈線性增大關(guān)系，記作O(n)，也稱線性階。，也稱線性階。其余常用的還有平方階其余常用的還有平方階O(n2)、立方階、立方階O(n3)、對(duì)數(shù)階、對(duì)數(shù)階O(log2n)、指數(shù)階指數(shù)階O(2n)等。等。 各種不

41、同數(shù)量級(jí)對(duì)應(yīng)的值存在著如下關(guān)系：各種不同數(shù)量級(jí)對(duì)應(yīng)的值存在著如下關(guān)系： O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)O(n!)思考題：思考題：為什么要進(jìn)行算法的時(shí)間復(fù)雜度分析？為什么要進(jìn)行算法的時(shí)間復(fù)雜度分析？ 例例1.4 求兩個(gè)求兩個(gè)n階方陣的相加階方陣的相加C=A+B的算法如下的算法如下,分分析其時(shí)間復(fù)雜度。析其時(shí)間復(fù)雜度。 #define MAX 20 /定義最大的方階定義最大的方階 void matrixadd(int n,int AMAXMAX, int BMAXMAX,int CMAXMAX) int i,j; for (i=0;in;i+)fo

42、r (j=0;jn;j+) Cij=Aij+Bij; 該 算 法 中 的 基 本 運(yùn) 算 是 兩 重 循 環(huán) 中 最 深 層 的 語(yǔ) 句該 算 法 中 的 基 本 運(yùn) 算 是 兩 重 循 環(huán) 中 最 深 層 的 語(yǔ) 句Cij=Aij+Bij，分析它的頻度，即：，分析它的頻度，即： T(n)= =O(n2) 102101010*11ninininjnnnnn例例1.5 分析以下算法的時(shí)間復(fù)雜度。分析以下算法的時(shí)間復(fù)雜度。int fun(int n) int i,j,k,s; s=0; for (i=0;i=n;i+) for (j=0;j=i;j+) for (k=0;k=j;k+) s+; r

43、eturn(s);基本語(yǔ)句或基本操作基本語(yǔ)句或基本操作 解：解：該算法的基本操作是語(yǔ)句該算法的基本操作是語(yǔ)句s+，其頻度：，其頻度： T(n)= =O(n3)則該算法的時(shí)間復(fù)雜度為則該算法的時(shí)間復(fù)雜度為O(n3)。 niijjk0001例例1.6 分析以下算法的時(shí)間復(fù)雜度分析以下算法的時(shí)間復(fù)雜度。void func(int n) int i=0,s=0; while (sn) i+; s=s+i; 基本語(yǔ)句基本語(yǔ)句 解：解：對(duì)于對(duì)于while循環(huán)語(yǔ)句，設(shè)執(zhí)行的次數(shù)為循環(huán)語(yǔ)句，設(shè)執(zhí)行的次數(shù)為m，i從從0開(kāi)始遞增開(kāi)始遞增1，直到，直到m為止，有：為止，有： s=0+1+2+(m-1)=m(m-1)

44、/2， 并滿足并滿足s=m(m-1)/2n，則有，則有m 。 T(n)=O( ) 所以，該算法的時(shí)間復(fù)雜度為所以，該算法的時(shí)間復(fù)雜度為O( )。 nnn 例例1.7 有如下算法：有如下算法： void fun(int a,int n,int k) /數(shù)組數(shù)組a共有共有n個(gè)元素個(gè)元素 int i;if (k=n-1) for (i=0;in;i+) /n次次 printf(%dn,ai);else for (i=k;in;i+)/n-k次次ai=ai+i*i; fun(a,n,k+1); 調(diào)用上述算法的語(yǔ)句為調(diào)用上述算法的語(yǔ)句為fun(a,n,0)，求其時(shí)間復(fù)雜度。，求其時(shí)間復(fù)雜度。 解：解：設(shè)

45、設(shè)fun(a,n,0)的時(shí)間復(fù)雜度為的時(shí)間復(fù)雜度為T(mén)(n)，則，則fun(a,n,k)的執(zhí)的執(zhí)行時(shí)間為行時(shí)間為T(mén)1(n,k)，由，由fun()算法可知：算法可知： T1(n,k)=n 當(dāng)當(dāng)k=n-1時(shí)時(shí) T1(n,k)= (n-k)+T1(n,k+1) 其他情況其他情況 則則 T(n)=T1(n,0)=n+T1(n,1)=n+(n-1)+T1(n,2)=n+(n-1)+2+T1(n,n-1)=n+(n-1)+ +2+n=O(n2) 所以調(diào)用所以調(diào)用fun(a,n,0)的時(shí)間復(fù)雜度為的時(shí)間復(fù)雜度為O(n2)。 空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間

46、臨時(shí)占用的存儲(chǔ)空間大小的量度，一般也作為問(wèn)題規(guī)模大小的量度，一般也作為問(wèn)題規(guī)模n的函數(shù)，以數(shù)量級(jí)形式給出的函數(shù)，以數(shù)量級(jí)形式給出,記作：記作： S(n) = O(g(n) 若所需額外空間相對(duì)于輸入數(shù)據(jù)量來(lái)說(shuō)是常數(shù)，則稱此算法若所需額外空間相對(duì)于輸入數(shù)據(jù)量來(lái)說(shuō)是常數(shù)，則稱此算法為為原地工作原地工作。若所需存儲(chǔ)量依賴于特定的輸入，則通常按最壞。若所需存儲(chǔ)量依賴于特定的輸入，則通常按最壞情況考慮。情況考慮。1.3.3 算法空間復(fù)雜度分析算法空間復(fù)雜度分析 例例1.8 分析例分析例1.4和例和例1.5的空間復(fù)雜度。的空間復(fù)雜度。 解：解：由于這兩個(gè)算法中臨時(shí)變量的個(gè)數(shù)與問(wèn)題規(guī)模由于這兩個(gè)算法中臨時(shí)變量

47、的個(gè)數(shù)與問(wèn)題規(guī)模n無(wú)關(guān)，所以空間復(fù)雜度均為無(wú)關(guān)，所以空間復(fù)雜度均為O(1)。1.4 數(shù)據(jù)結(jié)構(gòu)算法程序數(shù)據(jù)結(jié)構(gòu)算法程序 數(shù)據(jù)結(jié)構(gòu)算法程序數(shù)據(jù)結(jié)構(gòu)算法程序的作者：的作者：N.Wirth（1934年），瑞士計(jì)算機(jī)科學(xué)家，年），瑞士計(jì)算機(jī)科學(xué)家，1960年獲加利福尼亞大學(xué)伯克利分校博士學(xué)位。曾任年獲加利福尼亞大學(xué)伯克利分校博士學(xué)位。曾任斯坦福大學(xué)、蘇黎世聯(lián)邦理工學(xué)院教授。發(fā)明多斯坦福大學(xué)、蘇黎世聯(lián)邦理工學(xué)院教授。發(fā)明多種計(jì)算機(jī)語(yǔ)言（包括種計(jì)算機(jī)語(yǔ)言（包括Pascal、Modula和和Oberon等），并為軟件工程領(lǐng)域作出過(guò)開(kāi)拓性的貢獻(xiàn)。等），并為軟件工程領(lǐng)域作出過(guò)開(kāi)拓性的貢獻(xiàn)。于于1980年獲得計(jì)算機(jī)

48、科學(xué)界最高獎(jiǎng)年獲得計(jì)算機(jī)科學(xué)界最高獎(jiǎng)圖靈獎(jiǎng)圖靈獎(jiǎng)（/wiki/Turing_Award）。）。C#語(yǔ)言創(chuàng)始人：語(yǔ)言創(chuàng)始人：Anders Hejlsberg（安德斯，海斯博（安德斯，海斯博格）格）Wirth的學(xué)生：的學(xué)生：數(shù)據(jù)結(jié)構(gòu)領(lǐng)域做出突出貢獻(xiàn)的計(jì)算機(jī)科學(xué)家：數(shù)據(jù)結(jié)構(gòu)領(lǐng)域做出突出貢獻(xiàn)的計(jì)算機(jī)科學(xué)家：Donald Knuth（1938年），算法和程序設(shè)年），算法和程序設(shè)計(jì)技術(shù)的先驅(qū)者，計(jì)算機(jī)排版系統(tǒng)計(jì)技術(shù)的先驅(qū)者，計(jì)算機(jī)排版系統(tǒng)TEX和和METAFONT的發(fā)明者，他因這些成就和大量的發(fā)明者，他因這些成就和大量創(chuàng)造性的影響深遠(yuǎn)的著作（創(chuàng)造性的影響深遠(yuǎn)的著

49、作（19部書(shū)和部書(shū)和160篇論篇論文）而譽(yù)滿全球。作為斯坦福大學(xué)計(jì)算機(jī)程文）而譽(yù)滿全球。作為斯坦福大學(xué)計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)的榮譽(yù)退休教授，序設(shè)計(jì)藝術(shù)的榮譽(yù)退休教授，他當(dāng)前正全神他當(dāng)前正全神貫注于完成其關(guān)于計(jì)算機(jī)科學(xué)的史詩(shī)性的七貫注于完成其關(guān)于計(jì)算機(jī)科學(xué)的史詩(shī)性的七卷集。卷集。這一偉大工程在這一偉大工程在1962年他還是加利福年他還是加利福尼亞理工學(xué)院的研究生時(shí)就開(kāi)始了。他于尼亞理工學(xué)院的研究生時(shí)就開(kāi)始了。他于1974年獲得計(jì)算機(jī)科學(xué)界最高獎(jiǎng)年獲得計(jì)算機(jī)科學(xué)界最高獎(jiǎng)圖靈獎(jiǎng)圖靈獎(jiǎng)。C.A.R.Hoare（1934年），英國(guó)計(jì)算機(jī)科學(xué)年），英國(guó)計(jì)算機(jī)科學(xué)家，畢業(yè)于牛津大學(xué)，他最重要的工作包括：家，畢業(yè)

50、于牛津大學(xué)，他最重要的工作包括：快速排序算法快速排序算法，Hoare邏輯，形式語(yǔ)言通信時(shí)邏輯，形式語(yǔ)言通信時(shí)序進(jìn)程（序進(jìn)程（CSP）等。于）等。于1980年獲得計(jì)算機(jī)科年獲得計(jì)算機(jī)科學(xué)界最高獎(jiǎng)學(xué)界最高獎(jiǎng)圖靈獎(jiǎng)圖靈獎(jiǎng)。1.4.1 程序和數(shù)據(jù)結(jié)構(gòu)程序和數(shù)據(jù)結(jié)構(gòu)沃思沃思指出：程序就是在數(shù)據(jù)的某些特定的表示方法指出：程序就是在數(shù)據(jù)的某些特定的表示方法和結(jié)構(gòu)的基礎(chǔ)上，對(duì)抽象算法的具體表述，所以說(shuō)程序和結(jié)構(gòu)的基礎(chǔ)上，對(duì)抽象算法的具體表述，所以說(shuō)程序離不開(kāi)數(shù)據(jù)結(jié)構(gòu)。離不開(kāi)數(shù)據(jù)結(jié)構(gòu)。1.4.2 算法和程序算法和程序由程序設(shè)計(jì)語(yǔ)言描述的算法就是計(jì)算機(jī)程序。對(duì)一個(gè)由程序設(shè)計(jì)語(yǔ)言描述的算法就是計(jì)算機(jī)程序。對(duì)一個(gè)求解

51、問(wèn)題而言，算法就是解題的方法，沒(méi)有算法，程求解問(wèn)題而言，算法就是解題的方法，沒(méi)有算法，程序就成了無(wú)本之末，無(wú)源之水。序就成了無(wú)本之末，無(wú)源之水。有了算法，將它表示成程序是不困難的。算法是程序有了算法，將它表示成程序是不困難的。算法是程序的核心。算法在程序設(shè)計(jì)，也可以說(shuō)軟件開(kāi)發(fā)，甚至的核心。算法在程序設(shè)計(jì)，也可以說(shuō)軟件開(kāi)發(fā)，甚至可以說(shuō)在整個(gè)計(jì)算機(jī)科學(xué)中的地位都是極其重要的?？梢哉f(shuō)在整個(gè)計(jì)算機(jī)科學(xué)中的地位都是極其重要的。1.4.3 算法和數(shù)據(jù)結(jié)構(gòu)算法和數(shù)據(jù)結(jié)構(gòu)求解的問(wèn)題可以通過(guò)抽象數(shù)據(jù)類型描述，它由數(shù)據(jù)的邏求解的問(wèn)題可以通過(guò)抽象數(shù)據(jù)類型描述，它由數(shù)據(jù)的邏輯結(jié)構(gòu)和抽象運(yùn)算兩部分組成。輯結(jié)構(gòu)和抽象運(yùn)算

52、兩部分組成。一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以映射成多種存儲(chǔ)結(jié)構(gòu)，抽象運(yùn)一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以映射成多種存儲(chǔ)結(jié)構(gòu)，抽象運(yùn)算在不同的存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)可以對(duì)應(yīng)多種算法，在同一算在不同的存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)可以對(duì)應(yīng)多種算法，在同一種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)也可能有多種算法，通過(guò)算法的時(shí)間種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)也可能有多種算法，通過(guò)算法的時(shí)間復(fù)雜度和空間復(fù)雜度等分析，可以得到好的算法。復(fù)雜度和空間復(fù)雜度等分析，可以得到好的算法。 好算法與以下因素有關(guān)：好算法與以下因素有關(guān)：算法的正確性、可讀性和可維護(hù)性等。算法的正確性、可讀性和可維護(hù)性等。算法的時(shí)間和空間復(fù)雜度。算法的時(shí)間和空間復(fù)雜度。存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)能力存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)能力。如果存儲(chǔ)結(jié)構(gòu)

53、存儲(chǔ)能力強(qiáng)、存儲(chǔ)。如果存儲(chǔ)結(jié)構(gòu)存儲(chǔ)能力強(qiáng)、存儲(chǔ)信息多，算法將會(huì)較好設(shè)計(jì)。反之對(duì)于過(guò)于簡(jiǎn)單的存儲(chǔ)信息多，算法將會(huì)較好設(shè)計(jì)。反之對(duì)于過(guò)于簡(jiǎn)單的存儲(chǔ)結(jié)構(gòu)，可能就要設(shè)計(jì)一套比較復(fù)雜的算法。在這一點(diǎn)上，結(jié)構(gòu)，可能就要設(shè)計(jì)一套比較復(fù)雜的算法。在這一點(diǎn)上，經(jīng)常體現(xiàn)時(shí)間與空間的矛盾，往往存儲(chǔ)能力是與所使用經(jīng)常體現(xiàn)時(shí)間與空間的矛盾，往往存儲(chǔ)能力是與所使用的空間大小成正比的。的空間大小成正比的。存儲(chǔ)結(jié)構(gòu)應(yīng)與所選擇的算法相適應(yīng)。存儲(chǔ)結(jié)構(gòu)應(yīng)與所選擇的算法相適應(yīng)。存儲(chǔ)結(jié)構(gòu)是實(shí)現(xiàn)算存儲(chǔ)結(jié)構(gòu)是實(shí)現(xiàn)算法的基礎(chǔ)，也會(huì)影響算法的設(shè)計(jì)，其選擇要充分考慮算法的基礎(chǔ)，也會(huì)影響算法的設(shè)計(jì)，其選擇要充分考慮算法的各種操作，應(yīng)與算法的操作相

54、適應(yīng)。法的各種操作，應(yīng)與算法的操作相適應(yīng)。數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)會(huì)影響算法的好壞，因此在選擇存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)會(huì)影響算法的好壞，因此在選擇存儲(chǔ)結(jié)構(gòu)時(shí)，也要考慮其對(duì)算法的影響。存儲(chǔ)結(jié)構(gòu)對(duì)算法的影響主時(shí)，也要考慮其對(duì)算法的影響。存儲(chǔ)結(jié)構(gòu)對(duì)算法的影響主要在兩方面：要在兩方面：?jiǎn)栴}描述問(wèn)題描述：有若干學(xué)生數(shù)據(jù)（學(xué)生數(shù)小于：有若干學(xué)生數(shù)據(jù)（學(xué)生數(shù)小于50），），每個(gè)學(xué)生數(shù)據(jù)包含學(xué)號(hào)（每個(gè)學(xué)生學(xué)號(hào)是唯一的，每個(gè)學(xué)生數(shù)據(jù)包含學(xué)號(hào)（每個(gè)學(xué)生學(xué)號(hào)是唯一的，但學(xué)生記錄不一定按學(xué)號(hào)順序存放）、姓名、班但學(xué)生記錄不一定按學(xué)號(hào)順序存放）、姓名、班號(hào)和若干門(mén)課程成績(jī)（每個(gè)學(xué)生所選課程數(shù)目可號(hào)和若干門(mén)課程成績(jī)（每個(gè)學(xué)生所選課程數(shù)目可能不等，但最多不超過(guò)能不等，但最多不超過(guò)6門(mén)）。門(mén)）。要求要求：設(shè)計(jì)一個(gè)程序輸出每個(gè)學(xué)生的學(xué)號(hào)、姓名：設(shè)計(jì)一個(gè)程序輸出每個(gè)學(xué)生的學(xué)號(hào)、姓名和平均分以及每門(mén)課程（課程編號(hào)從和平均分以及每門(mén)課程（課