算法與數(shù)據(jù)結(jié)構(gòu)第1章緒論

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)教材教材: : 數(shù)據(jù)結(jié)構(gòu)教程數(shù)據(jù)結(jié)構(gòu)教程(第第3版版) 李春葆等李春葆等 清華大學(xué)出版社清華大學(xué)出版社 2009 (另配套學(xué)習(xí)指導(dǎo)和上機(jī)指導(dǎo)兩書，作為參考）另配套學(xué)習(xí)指導(dǎo)和上機(jī)指導(dǎo)兩書，作為參考）參考書參考書: : 1.1.數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C語言版）嚴(yán)蔚敏，吳偉民語言版）嚴(yán)蔚敏，吳偉民 清華大學(xué)清華大學(xué)出版社出版社 1997 2.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅc數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC+描述）殷人昆等描述）殷人昆等 清華大學(xué)出版社清華大學(xué)出版社 1999輔導(dǎo)教師：輔導(dǎo)教師：7-8劉闖劉闖 134699674479-11洪偉洪語言語言 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)

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

3、歸納法歸納法先解決具體問題，由此歸納出解決問題的理論知先解決具體問題，由此歸納出解決問題的理論知識(shí)識(shí)只有歸納法才能產(chǎn)生新的知識(shí)！只有歸納法才能產(chǎn)生新的知識(shí)！編寫程序編寫程序1編寫程序編寫程序2編寫程序編寫程序n.具有編程的基本能力具有編程的基本能力用計(jì)算機(jī)求解問題的基本思路用計(jì)算機(jī)求解問題的基本思路學(xué)士學(xué)士精通程序設(shè)計(jì)方法精通程序設(shè)計(jì)方法了解開發(fā)環(huán)境了解開發(fā)環(huán)境碩士碩士精通開發(fā)環(huán)境精通開發(fā)環(huán)境具體一定的理論創(chuàng)具體一定的理論創(chuàng)新知識(shí)新知識(shí)博士博士 具有較高的理論具有較高的理論創(chuàng)新知識(shí)創(chuàng)新知識(shí)講授課時(shí)：講授課時(shí)：72上機(jī)課時(shí)：上機(jī)課時(shí)：36評(píng)分方式：評(píng)分方式：平時(shí)：平時(shí)：10上機(jī)：上機(jī)：10，作業(yè)

4、：作業(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)算法程序 1.1.1 數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)的定義1.1.2 邏輯結(jié)構(gòu)類型邏輯結(jié)構(gòu)類型 1.1.3 存儲(chǔ)結(jié)構(gòu)類型存儲(chǔ)結(jié)構(gòu)類型1.1.4 數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型 1.1 1.1 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)數(shù)據(jù)：是所有能被輸入到計(jì)算機(jī)中：是所有能被輸入到計(jì)算機(jī)中, ,且能被計(jì)算機(jī)處理的且能被計(jì)算機(jī)處理的符號(hào)的集合。它是計(jì)算機(jī)操作的對(duì)象的總稱符號(hào)的集合。它是計(jì)算機(jī)操

5、作的對(duì)象的總稱, ,也是計(jì)算機(jī)也是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。處理的信息的某種特定的符號(hào)表示形式。數(shù)據(jù)元素?cái)?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)的定義 例如例如,200402班為一個(gè)學(xué)生班為一個(gè)學(xué)生數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象,而其中的而其中的“張三張三”是一個(gè)數(shù)據(jù)元素是一個(gè)數(shù)據(jù)元素)。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)：是指：是指數(shù)據(jù)數(shù)據(jù)以及數(shù)據(jù)元素相互之間的以及數(shù)據(jù)元素相互之間的聯(lián)系聯(lián)系?？梢钥?。

6、可以看作是相互之間存在著某種特定關(guān)系的數(shù)據(jù)元素的集合。作是相互之間存在著某種特定關(guān)系的數(shù)據(jù)元素的集合。 因此因此,可時(shí)把可時(shí)把數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)看成是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合?？闯墒菐ЫY(jié)構(gòu)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)包括如下幾個(gè)方面：包括如下幾個(gè)方面： 數(shù)據(jù)元素之間的邏輯關(guān)系數(shù)據(jù)元素之間的邏輯關(guān)系,即數(shù)據(jù)的即數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)。 數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式,即數(shù)據(jù)即數(shù)據(jù)的的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu),也稱為數(shù)據(jù)的物理結(jié)構(gòu)。也稱為數(shù)據(jù)的物理結(jié)構(gòu)。 施加在該數(shù)據(jù)上的操作施加在該數(shù)據(jù)上的操作,即數(shù)據(jù)的即數(shù)據(jù)的運(yùn)算運(yùn)算。 例例1.1 有一個(gè)學(xué)生表如

7、表有一個(gè)學(xué)生表如表1.1所示。這個(gè)表中的數(shù)據(jù)元所示。這個(gè)表中的數(shù)據(jù)元素是學(xué)生記錄素是學(xué)生記錄,每個(gè)數(shù)據(jù)元素由四個(gè)數(shù)據(jù)項(xiàng)每個(gè)數(shù)據(jù)元素由四個(gè)數(shù)據(jù)項(xiàng)(即學(xué)號(hào)、姓即學(xué)號(hào)、姓別、性別和班號(hào)別、性別和班號(hào))組成。組成。學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別班號(hào)班號(hào)1張斌張斌男男99018劉麗劉麗女女990234李英李英女女990120陳華陳華男男990212王奇王奇男男990126董強(qiáng)董強(qiáng)男男99025王萍王萍女女9901表表1.1 學(xué)生表學(xué)生表 邏輯結(jié)構(gòu)表示邏輯結(jié)構(gòu)表示1 該表中的記錄順序反映了數(shù)據(jù)元素之間的邏輯關(guān)系該表中的記錄順序反映了數(shù)據(jù)元素之間的邏輯關(guān)系, , 用學(xué)用學(xué)號(hào)標(biāo)識(shí)每個(gè)學(xué)生記錄號(hào)標(biāo)識(shí)每個(gè)學(xué)生記錄, ,

8、這種這種邏輯關(guān)系邏輯關(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é)構(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

9、sex2; /存儲(chǔ)性別存儲(chǔ)性別 char class4; /存儲(chǔ)班號(hào)存儲(chǔ)班號(hào) Stud7=1,“張斌張斌”,“男男”,“9901”, 5,王萍王萍,女女,9901;C/C+語言中，通常采用結(jié)構(gòu)體數(shù)組和鏈表兩種方式實(shí)現(xiàn)語言中，通常采用結(jié)構(gòu)體數(shù)組和鏈表兩種方式實(shí)現(xiàn)其存儲(chǔ)結(jié)構(gòu)。其存儲(chǔ)結(jié)構(gòu)。 結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體數(shù)組Stud各元素在內(nèi)存中順序存放各元素在內(nèi)存中順序存放,即第即第i(1i6)個(gè)個(gè)學(xué)生對(duì)應(yīng)的元素學(xué)生對(duì)應(yīng)的元素Studi存放在第存放在第i+1個(gè)學(xué)生對(duì)應(yīng)的元素個(gè)學(xué)生對(duì)應(yīng)的元素Studi+1之前之前,Studi+1正好在正好在Studi之后。之后。9901女王萍59901男張斌張斌1Stud0Stu

10、d6Stud數(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 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陳華陳華男

11、男 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ì)于“學(xué)生表學(xué)生表”這種數(shù)據(jù)結(jié)構(gòu)這種數(shù)據(jù)結(jié)構(gòu),可以進(jìn)行一系列的運(yùn)算可以進(jìn)行一系列的運(yùn)算,例例如如,增加一個(gè)學(xué)生記錄、刪除一個(gè)學(xué)生記錄、查找性別為增加一個(gè)學(xué)生記錄、刪除一個(gè)學(xué)生記錄、查找性別為“女女”的學(xué)生記錄、查找班號(hào)為的學(xué)生記錄、查找班號(hào)為“9902”的學(xué)生記錄等等。的學(xué)生記錄等等。 運(yùn)算運(yùn)算 例如例如,查找學(xué)號(hào)為查

12、找學(xué)號(hào)為20的學(xué)生的姓名的學(xué)生的姓名： 對(duì)于對(duì)于Stud數(shù)組：從數(shù)組：從Stud0開始比較開始比較,Stud0.no不等于不等于20,再再與與Stud1.no比較比較,直到直到Stud3.no等于等于20,返回返回S。 9902男陳華209901男張斌張斌1Stud0Stud3i3運(yùn)算的實(shí)現(xiàn)過程運(yùn)算的實(shí)現(xiàn)過程1對(duì)于對(duì)于head為首結(jié)點(diǎn)為首結(jié)點(diǎn)指針的鏈表：指針的鏈表：從從p=head所指結(jié)點(diǎn)開所指結(jié)點(diǎn)開始比較始比較,p- -no不等于不等于20,從它的從它的next得到下一個(gè)得到下一個(gè)結(jié)點(diǎn)的地址結(jié)點(diǎn)的地址,再與下一個(gè)再與下一個(gè)結(jié)點(diǎn)的結(jié)點(diǎn)的no域比較域比較,直到直到某結(jié)點(diǎn)的某結(jié)點(diǎn)

13、的no域等于域等于20,返返回其回其p- -name域。域。head1張斌張斌男男 99018劉麗劉麗女女 990234李英李英女女 990120陳華陳華男男 990212王奇王奇男男 990126董強(qiáng)董強(qiáng)男男 99025王萍王萍女女 9901p運(yùn)算的實(shí)現(xiàn)過程運(yùn)算的實(shí)現(xiàn)過程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)算同樣的運(yùn)算,在不同的存儲(chǔ)結(jié)構(gòu)中在不同的存儲(chǔ)結(jié)構(gòu)中,其實(shí)現(xiàn)過程是不同其實(shí)現(xiàn)過程是不同的。的。思考題：思考題：數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)有什么不同？數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)有什么不同？ 為了更確切地描述一種數(shù)據(jù)結(jié)構(gòu)為了更確切地描述一種數(shù)

14、據(jù)結(jié)構(gòu),通常采用通常采用二元組二元組表示：表示： B=(K,R) 其中其中,B是一種數(shù)據(jù)結(jié)構(gòu)是一種數(shù)據(jù)結(jié)構(gòu),它由數(shù)據(jù)元素的集合它由數(shù)據(jù)元素的集合K和和K上上二元關(guān)系的集合二元關(guān)系的集合R所組成。其中：所組成。其中： K=ki| 1in,n0 R=rj| 1jm,m0 邏輯結(jié)構(gòu)的描述或表示：邏輯結(jié)構(gòu)的描述或表示：一種通用的邏輯結(jié)構(gòu)表示方法一種通用的邏輯結(jié)構(gòu)表示方法其中：其中：u ki表示集合表示集合K中的第中的第i個(gè)結(jié)點(diǎn)或數(shù)據(jù)元素。個(gè)結(jié)點(diǎn)或數(shù)據(jù)元素。u n為為K中結(jié)點(diǎn)的個(gè)數(shù)中結(jié)點(diǎn)的個(gè)數(shù),特別地特別地,若若n=0,則則K是一個(gè)空集是一個(gè)空集,因而因而B也就無結(jié)構(gòu)可言也就無結(jié)構(gòu)可言,有時(shí)也可以認(rèn)為它

15、具有任一結(jié)構(gòu)。有時(shí)也可以認(rèn)為它具有任一結(jié)構(gòu)。u rj表示集合表示集合R中的第中的第j個(gè)關(guān)系，每個(gè)關(guān)系用序偶表示。個(gè)關(guān)系，每個(gè)關(guān)系用序偶表示。u m為為R中關(guān)系的個(gè)數(shù)中關(guān)系的個(gè)數(shù),特別地特別地,若若m=0,則則R是一個(gè)空集是一個(gè)空集,表明表明集合集合K中的元結(jié)點(diǎn)間不存在任何關(guān)系中的元結(jié)點(diǎn)間不存在任何關(guān)系,彼此是獨(dú)立的。彼此是獨(dú)立的。 序偶序偶(x,yK) x為第一結(jié)點(diǎn)為第一結(jié)點(diǎn),y為第二結(jié)點(diǎn)。為第二結(jié)點(diǎn)。 x為為y的的直接前驅(qū)結(jié)點(diǎn)直接前驅(qū)結(jié)點(diǎn)(通常簡稱通常簡稱前驅(qū)結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)) y為為x的的直接后繼結(jié)點(diǎn)直接后繼結(jié)點(diǎn)(通常簡稱通常簡稱后繼結(jié)點(diǎn)后繼結(jié)點(diǎn))。 若某個(gè)結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)若某個(gè)結(jié)點(diǎn)沒有前驅(qū)結(jié)

16、點(diǎn),則稱該結(jié)點(diǎn)為則稱該結(jié)點(diǎn)為開始結(jié)點(diǎn)開始結(jié)點(diǎn)；若某個(gè)；若某個(gè)結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)結(jié)點(diǎn)沒有后繼結(jié)點(diǎn),則稱該結(jié)點(diǎn)為則稱該結(jié)點(diǎn)為終端結(jié)點(diǎn)終端結(jié)點(diǎn)。 說明：說明：表示有向關(guān)系，表示有向關(guān)系，(x,y)表示無向關(guān)系。表示無向關(guān)系。采用離散數(shù)學(xué)的表示方法。采用離散數(shù)學(xué)的表示方法。 例如，有一個(gè)如下表所示的城市表，假設(shè)城市名是唯一的，例如，有一個(gè)如下表所示的城市表，假設(shè)城市名是唯一的，給出其邏輯結(jié)構(gòu)的二元組表示。給出其邏輯結(jié)構(gòu)的二元組表示。城市表城市表City中共有中共有5個(gè)記錄，其邏輯結(jié)構(gòu)的二元組表示如下：個(gè)記錄，其邏輯結(jié)構(gòu)的二元組表示如下： City=(D,R)D=Beijing,Shanghai,Wuha

17、n,Xian,NanjingR=r只有一種關(guān)系只有一種關(guān)系r=, 城市名城市名區(qū)號(hào)區(qū)號(hào)說明說明Beijing010首都首都Shanghai021直轄市直轄市Wuhan027湖北省省會(huì)湖北省省會(huì)Xian029陜西省省會(huì)陜西省省會(huì)Nanjing025江蘇省省會(huì)江蘇省省會(huì)又例如又例如, ,有如下數(shù)據(jù)即一個(gè)矩陣：有如下數(shù)據(jù)即一個(gè)矩陣： 119105471281362 對(duì)應(yīng)的二元組表示為對(duì)應(yīng)的二元組表示為B=(K,R),其中：其中： K=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è)二維

18、數(shù)組一個(gè)二維數(shù)組 可以可以利用圖形形象地表示邏輯結(jié)構(gòu)。利用圖形形象地表示邏輯結(jié)構(gòu)。 例如，上述例如，上述“學(xué)生表學(xué)生表”數(shù)據(jù)結(jié)構(gòu)用下圖的圖形表示。數(shù)據(jù)結(jié)構(gòu)用下圖的圖形表示。 k1 k2 k3 k4 k5 k6 k7 學(xué)生表數(shù)據(jù)結(jié)構(gòu)圖示學(xué)生表數(shù)據(jù)結(jié)構(gòu)圖示 (1) 線性結(jié)構(gòu)線性結(jié)構(gòu) 結(jié)點(diǎn)之間關(guān)系：結(jié)點(diǎn)之間關(guān)系：一對(duì)一。一對(duì)一。 特點(diǎn)：特點(diǎn)：開始結(jié)點(diǎn)和終端結(jié)點(diǎn)都是唯一的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)都是唯一的, ,除了開始結(jié)點(diǎn)和終除了開始結(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)。順序表

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

20、繼結(jié)點(diǎn)。(2) 鏈?zhǔn)酱鎯?chǔ)方法鏈?zhǔn)酱鎯?chǔ)方法 (3) 索引存儲(chǔ)方法索引存儲(chǔ)方法 (4) 散列（哈希）存儲(chǔ)方法散列（哈希）存儲(chǔ)方法 1.1.3 存儲(chǔ)結(jié)構(gòu)類型存儲(chǔ)結(jié)構(gòu)類型(1) 順序存儲(chǔ)方法順序存儲(chǔ)方法 前面通過示例已介紹前面通過示例已介紹第第9章介紹章介紹 (1) 數(shù)據(jù)類型數(shù)據(jù)類型 高級(jí)程序語言中高級(jí)程序語言中,一般須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或一般須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式表達(dá)式,明確說明它們所屬的數(shù)據(jù)類型。不同類型的變量明確說明它們所屬的數(shù)據(jù)類型。不同類型的變量,其所其所能取的值的范圍不同能取的值的范圍不同,所能進(jìn)行的操作不同。所能進(jìn)行的操作不同。 數(shù)據(jù)類型數(shù)據(jù)類型是一個(gè)值的集合和

21、定義在此集合上的一組操作是一個(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ù)的全體整數(shù))和相關(guān)的整數(shù)和相關(guān)的整數(shù)運(yùn)算運(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ù)類型

22、抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(Abstract Data Type簡寫為簡寫為ADT)指的是用指的是用戶進(jìn)行軟件系統(tǒng)設(shè)計(jì)時(shí)從問題的數(shù)學(xué)模型中抽象出來的邏輯戶進(jìn)行軟件系統(tǒng)設(shè)計(jì)時(shí)從問題的數(shù)學(xué)模型中抽象出來的邏輯數(shù)據(jù)結(jié)構(gòu)和邏輯數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算數(shù)據(jù)結(jié)構(gòu)和邏輯數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算,而不考慮計(jì)算機(jī)的具體存而不考慮計(jì)算機(jī)的具體存儲(chǔ)結(jié)構(gòu)和運(yùn)算的具體實(shí)現(xiàn)算法。儲(chǔ)結(jié)構(gòu)和運(yùn)算的具體實(shí)現(xiàn)算法。 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型=數(shù)據(jù)元素集合抽象運(yùn)算數(shù)據(jù)元素集合抽象運(yùn)算 抽象數(shù)據(jù)類型實(shí)質(zhì)上就是描述一個(gè)求解問題本身（與計(jì)算抽象數(shù)據(jù)類型實(shí)質(zhì)上就是描述一個(gè)求解問題本身（與計(jì)算機(jī)無關(guān)），計(jì)算機(jī)人員就是在理解問題基礎(chǔ)上實(shí)現(xiàn)用計(jì)算機(jī)機(jī)無關(guān)），計(jì)算

23、機(jī)人員就是在理解問題基礎(chǔ)上實(shí)現(xiàn)用計(jì)算機(jī)求解問題的過程。求解問題的過程。例如例如,抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型復(fù)數(shù)復(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)系： R1=| e1是復(fù)數(shù)的實(shí)數(shù)部分是復(fù)數(shù)的實(shí)數(shù)部分,e2 是復(fù)數(shù)的是復(fù)數(shù)的 虛數(shù)部分虛數(shù)部分 e1e2i（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í)部值。的

24、實(shí)部值。 GetImag(Z,&Imag):返回復(fù)數(shù)返回復(fù)數(shù)Z的虛部值。的虛部值。 Add(z1,z2,&sum):返回兩個(gè)復(fù)數(shù)返回兩個(gè)復(fù)數(shù)z1,z2的和。的和。 ADT Complex思考題：思考題：數(shù)據(jù)類型和抽象數(shù)據(jù)類型有什么不同？數(shù)據(jù)類型和抽象數(shù)據(jù)類型有什么不同？1.2 算法及其描述算法及其描述 1.2.1 什么是算法什么是算法 1.2.2 算法描述算法描述1.2.1 什么是算法什么是算法 數(shù)據(jù)元素之間的關(guān)系有邏輯關(guān)系和物理關(guān)系數(shù)據(jù)元素之間的關(guān)系有邏輯關(guān)系和物理關(guān)系,對(duì)應(yīng)的對(duì)應(yīng)的操作有操作有邏輯結(jié)構(gòu)上的操作功能邏輯結(jié)構(gòu)上的操作功能和和具體存儲(chǔ)結(jié)構(gòu)上的操作實(shí)具體存儲(chǔ)結(jié)構(gòu)上的

25、操作實(shí)現(xiàn)現(xiàn)。 通常把具體存儲(chǔ)結(jié)構(gòu)上的操作通常把具體存儲(chǔ)結(jié)構(gòu)上的操作實(shí)現(xiàn)實(shí)現(xiàn)步驟或過程稱為步驟或過程稱為算算法法。屬屬ADT的一部分的一部分算法算法算法的五個(gè)重要的特性算法的五個(gè)重要的特性 (1) 有窮性有窮性:在有窮步之后結(jié)束。在有窮步之后結(jié)束。(2) 確定性確定性:無二義性。無二義性。 (3) 可行性可行性:可通過基本運(yùn)算有限次執(zhí)行來實(shí)現(xiàn)?？赏ㄟ^基本運(yùn)算有限次執(zhí)行來實(shí)現(xiàn)。(4) 有輸入有輸入 (5) 有輸出有輸出 表示存在數(shù)據(jù)處理表示存在數(shù)據(jù)處理例例 考慮下列兩段描述：考慮下列兩段描述：(1) 描述一描述一void exam1() int n2; while (n%20) nn+2; pri

26、ntf(%dn,n);華中科大考研題華中科大考研題 (2) 描述二描述二void exam2() int x,y; y=0; x=5/y; printf(“%d,%dn”,x,y); 這兩段描述均不能滿足算法的特征這兩段描述均不能滿足算法的特征,試問它們違反了哪試問它們違反了哪些特征？些特征？ 解：解：(1)算法是一個(gè)死循環(huán)算法是一個(gè)死循環(huán),違反了算法的有窮性特征。違反了算法的有窮性特征。 (2)算法包含除零錯(cuò)誤算法包含除零錯(cuò)誤,違反了算法的可行性特征違反了算法的可行性特征。思考題：思考題：算法和程序有什么不同？算法和程序有什么不同？ 1.2.2 算法描述算法描述 本書中采用本書中采用C/C+

27、語言描述算法。語言描述算法。 說明：說明：C+語言中提供了一種語言中提供了一種引用引用運(yùn)算符運(yùn)算符“&”,引用引用是個(gè)別名是個(gè)別名,當(dāng)建立引用時(shí)當(dāng)建立引用時(shí),程序用另一個(gè)已定義的變量或?qū)Τ绦蛴昧硪粋€(gè)已定義的變量或?qū)ο笙?目標(biāo)目標(biāo))的名字初始化它的名字初始化它,從那時(shí)起從那時(shí)起,引用作為目標(biāo)的別名引用作為目標(biāo)的別名而使用而使用,對(duì)引用的改動(dòng)實(shí)際就是對(duì)目標(biāo)的改動(dòng)。對(duì)引用的改動(dòng)實(shí)際就是對(duì)目標(biāo)的改動(dòng)。 注意：注意：Turbo C不支持引用類型，不支持引用類型，VC+支持引用類型。支持引用類型。 編寫一個(gè)函數(shù)編寫一個(gè)函數(shù)swap1(x,y)，當(dāng)執(zhí)行語句，當(dāng)執(zhí)行語句swap1(a,b)時(shí)時(shí),交換交

28、換a和和b的值。的值。 void swap1(int x,int y) int tmp; tmp=x;x=y;y=tmp; 注意：注意：a a和和b b的值不會(huì)發(fā)生了交換。的值不會(huì)發(fā)生了交換。 為此，采用指針的方式來回傳形參的值，需將上述函數(shù)為此，采用指針的方式來回傳形參的值，需將上述函數(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,&am

29、p;b)，顯然遠(yuǎn)不如采用引，顯然遠(yuǎn)不如采用引用方式簡潔。所以本書后面很多算法都采用引用形參。用方式簡潔。所以本書后面很多算法都采用引用形參。引入引入“引用引用”的概念的概念例如：例如： int a=4; /a為普通的整型變量為普通的整型變量 int &b=a; /b是是a的引用變量的引用變量 這里說明這里說明b變量是變量變量是變量a的引用的引用,b也等于也等于4,之后這兩個(gè)之后這兩個(gè)變量同步改變。當(dāng)變量同步改變。當(dāng)a改變時(shí)改變時(shí)b也同步改變，同樣，當(dāng)也同步改變，同樣，當(dāng)b改變改變時(shí)時(shí)a也同步改變。也同步改變。難點(diǎn)難點(diǎn)void main() int a=2; int &b=a;

30、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ù)形參中,采用引用型形參時(shí)采用引用型形參時(shí),在函數(shù)調(diào)用時(shí)將在函數(shù)調(diào)用時(shí)將形參的改變回傳給實(shí)參形參的改變回傳給實(shí)參,例如例如,有如下函數(shù)有如下函數(shù)(其中的形參均為引用其中的形參均為引用型形參型形參)： void swap(int &x,int &y) /形參前的形參前的“&”符號(hào)不是指針運(yùn)算符符

31、號(hào)不是指針運(yùn)算符 int tmp=x; x=y;y=tmp 當(dāng)用執(zhí)行語句當(dāng)用執(zhí)行語句swap(a,b)時(shí)時(shí),a和和b的值發(fā)生了交換。的值發(fā)生了交換。 例例1.3 編寫一個(gè)算法編寫一個(gè)算法, 讀入三個(gè)整數(shù)讀入三個(gè)整數(shù)x,y和和z的值的值,要求從大到小要求從大到小輸出這三個(gè)數(shù)。輸出這三個(gè)數(shù)。 解：依次輸入解：依次輸入x,y和和z這三個(gè)整數(shù)這三個(gè)整數(shù),通過比較交換后通過比較交換后,使得使得xyz,然后輸出然后輸出x,y,z。 在算法中應(yīng)考慮對(duì)這三個(gè)元素作盡可能少的比較和移動(dòng)在算法中應(yīng)考慮對(duì)這三個(gè)元素作盡可能少的比較和移動(dòng),如如下述算法在最壞的情況下只需進(jìn)行下述算法在最壞的情況下只需進(jìn)行3次比較和次比

32、較和7次移動(dòng)。次移動(dòng)。用用C/C+描述算法示例描述算法示例void Descending() printf(輸入輸入x,y,z); scanf(%d,%d,%d,&x,&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.1 算法時(shí)間復(fù)雜度分析算法時(shí)間復(fù)雜度分析 1.3.2 算法空間復(fù)雜度分析算法空間復(fù)雜度分析 一個(gè)算法是由控制結(jié)構(gòu)一個(gè)算法是由控制結(jié)構(gòu)(順序、分支和循環(huán)三種順序、分支和循環(huán)三種)和和原操作原操作(指固有數(shù)據(jù)

33、類型的操作指固有數(shù)據(jù)類型的操作)構(gòu)成的構(gòu)成的,則算法時(shí)間取則算法時(shí)間取決于兩者的綜合效果。決于兩者的綜合效果。1.3.1 算法時(shí)間復(fù)雜度分析算法時(shí)間復(fù)雜度分析 控制語句控制語句1原操作原操作控制語句控制語句n原操作原操作一個(gè)算法的構(gòu)成一個(gè)算法的構(gòu)成 同一問題可以采用多種算法實(shí)現(xiàn)。如何比較算同一問題可以采用多種算法實(shí)現(xiàn)。如何比較算法執(zhí)行效率？法執(zhí)行效率？ 算法描述的語言不同算法描述的語言不同 算法執(zhí)行的環(huán)境不同算法執(zhí)行的環(huán)境不同 其他因素其他因素 所以不能用絕對(duì)執(zhí)行時(shí)間進(jìn)行比較所以不能用絕對(duì)執(zhí)行時(shí)間進(jìn)行比較 為了便于比較同一問題的不同算法為了便于比較同一問題的不同算法,通常從算法中選通常從算法中

34、選取一種對(duì)于所研究的問題來說是基本運(yùn)算的原操作取一種對(duì)于所研究的問題來說是基本運(yùn)算的原操作(以下以下將基本運(yùn)算的原操作簡稱為將基本運(yùn)算的原操作簡稱為基本運(yùn)算基本運(yùn)算)。 算法執(zhí)行時(shí)間大致為基本運(yùn)算所需的時(shí)間與其運(yùn)算次算法執(zhí)行時(shí)間大致為基本運(yùn)算所需的時(shí)間與其運(yùn)算次數(shù)數(shù)(也稱為頻度也稱為頻度)的乘積。的乘積。 被視為算法被視為算法基本運(yùn)算基本運(yùn)算的一般是最深層循環(huán)內(nèi)的語句。的一般是最深層循環(huán)內(nèi)的語句。 在一個(gè)算法中在一個(gè)算法中, ,進(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ì)地越多。其

35、運(yùn)行時(shí)間也就相對(duì)地越多。 所以所以, ,通常把算法中包含基本運(yùn)算次數(shù)的多少稱為算法的通常把算法中包含基本運(yùn)算次數(shù)的多少稱為算法的時(shí)間復(fù)雜度時(shí)間復(fù)雜度, ,也就是說也就是說, ,一個(gè)算法的時(shí)間復(fù)雜度是指該算法的基一個(gè)算法的時(shí)間復(fù)雜度是指該算法的基本運(yùn)算次數(shù)本運(yùn)算次數(shù)。 算法中算法中基本運(yùn)算次數(shù)基本運(yùn)算次數(shù)T(n)是問題規(guī)模是問題規(guī)模n的某個(gè)函數(shù)的某個(gè)函數(shù)f(n),記作記作： T(n)=O(f(n) 記號(hào)記號(hào)“O”讀作讀作“大大O”,它表示隨問題規(guī)模它表示隨問題規(guī)模n的增大算法執(zhí)的增大算法執(zhí)行時(shí)間的增長率和行時(shí)間的增長率和f(n)的增長率相同。的增長率相同?！癘”的形式定義為：的形式定義為： 若若

36、f(n)是正整數(shù)是正整數(shù)n的一個(gè)函數(shù)的一個(gè)函數(shù),則則T(n)=O(f(n)表示存在一個(gè)表示存在一個(gè)正的常數(shù)正的常數(shù)M,使得當(dāng)使得當(dāng)nn0時(shí)都滿足：時(shí)都滿足： |T(n)|M|f(n)| 也就是只求出也就是只求出T(n)的的最高階最高階,忽略其低階項(xiàng)和常忽略其低階項(xiàng)和常系數(shù)系數(shù),這樣既可簡化這樣既可簡化T(n)的計(jì)算的計(jì)算,又能比較客觀地反又能比較客觀地反映出當(dāng)映出當(dāng)n很大時(shí)算法的時(shí)間性能。很大時(shí)算法的時(shí)間性能。 例如例如,T(n)=3n2-5n+10000=O(n2)本質(zhì)上講，是一種本質(zhì)上講，是一種最高數(shù)量級(jí)的比較最高數(shù)量級(jí)的比較 一個(gè)沒有循環(huán)的算法的基本運(yùn)算次數(shù)與問題規(guī)模一個(gè)沒有循環(huán)的算法的

37、基本運(yùn)算次數(shù)與問題規(guī)模n無關(guān)無關(guān),記作記作O(1),也稱作也稱作常數(shù)階常數(shù)階。 一個(gè)只有一重循環(huán)的算法的基本運(yùn)算次數(shù)與問題規(guī)模一個(gè)只有一重循環(huán)的算法的基本運(yùn)算次數(shù)與問題規(guī)模n的增的增長呈線性增大關(guān)系長呈線性增大關(guān)系,記作記作O(n),也稱也稱線性階線性階。 其余常用的還有平方階其余常用的還有平方階O(n2)、立方階、立方階O(n3)、對(duì)數(shù)階、對(duì)數(shù)階O(log2n)、指數(shù)階指數(shù)階O(2n)等。等。 各種不同數(shù)量級(jí)對(duì)應(yīng)的值存在著如下關(guān)系：各種不同數(shù)量級(jí)對(duì)應(yīng)的值存在著如下關(guān)系： O(1)O(log2n)O(n)O(n*log2n)O(n2)O(n3)O(2n)O(n!)思考題：思考題：為什么要進(jìn)行算

38、法的時(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+)for (j=0;jn;j+) Cij=Aij+Bij; 該 算 法 中 的 基 本 運(yùn) 算 是 兩 重 循 環(huán) 中 最 深 層 的 語 句該 算 法 中 的 基 本 運(yùn) 算 是 兩 重 循 環(huán)

39、中 最 深 層 的 語 句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+; return(s);基本語句或基本操作基本語句或基本操作 解：解：該算法的基本操作是語句該算法的基本操作是語句s+,其頻度：其頻度： T(n)= =O(n3)則該算法的時(shí)間復(fù)雜度為則該算法的時(shí)間復(fù)雜

40、度為O(n3)。 niijjk0001例例1.6 分析以下算法的時(shí)間復(fù)雜度。分析以下算法的時(shí)間復(fù)雜度。void func(int n) int i=0,s=0; while (sn) i+; s=s+i; 基本語句基本語句 解：對(duì)于解：對(duì)于while循環(huán)語句，設(shè)執(zhí)行的次數(shù)為循環(huán)語句，設(shè)執(zhí)行的次數(shù)為m，i從從0開始遞增開始遞增1，直到，直到m為止，有：為止，有： s=0+1+2+(m-1)=m(m-1)/2， 并滿足并滿足s=m(m-1)/2n，則有，則有m 。 T(n)=O( ) 所以，該算法的時(shí)間復(fù)雜度為所以，該算法的時(shí)間復(fù)雜度為O( )。 nnn 例例1.7 有如下算法：有如下算法： vo

41、id 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)用上述算法的語句為調(diào)用上述算法的語句為fun(a,n,0)，求其時(shí)間復(fù)雜度。，求其時(shí)間復(fù)雜度。 解：設(shè)解：設(shè)fun(a,n,0)的時(shí)間復(fù)雜度為的時(shí)間復(fù)雜度為T(n),則則fun(a,n,k)的執(zhí)行的執(zhí)行時(shí)間為時(shí)間為T1(n,k)，由，由fun()算法可知：算法可知： T1(n,k)=n 當(dāng)當(dāng)k=n-1

42、時(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ù)雜度空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過程中是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間臨時(shí)占用的存儲(chǔ)空間大小的量度大小的量度,一般也作為問題規(guī)模一般也作為問題規(guī)模n的函數(shù)的函數(shù),以數(shù)量級(jí)形式給出以數(shù)量級(jí)形式給出,記記作：作： S(n) = O(g(n) 若所需若所需額外空間額外空間相

43、對(duì)于輸入數(shù)據(jù)量來說是常數(shù)相對(duì)于輸入數(shù)據(jù)量來說是常數(shù),則稱此算法為則稱此算法為原地工作。若所需存儲(chǔ)量依賴于特定的輸入原地工作。若所需存儲(chǔ)量依賴于特定的輸入,則通常按最壞情況則通常按最壞情況考慮?？紤]。1.3.2 1.3.2 算法空間復(fù)雜度分析算法空間復(fù)雜度分析 例例1.8 分析例分析例1.4和例和例1.5的空間復(fù)雜度。的空間復(fù)雜度。 解：由于這兩個(gè)算法中臨時(shí)變量的個(gè)數(shù)與問題規(guī)模解：由于這兩個(gè)算法中臨時(shí)變量的個(gè)數(shù)與問題規(guī)模n無關(guān)無關(guān),所以空間復(fù)雜度均為所以空間復(fù)雜度均為O(1)。1.4 數(shù)據(jù)結(jié)構(gòu)算法程序數(shù)據(jù)結(jié)構(gòu)算法程序 數(shù)據(jù)結(jié)構(gòu)對(duì)算法的影響主要在兩方面數(shù)據(jù)結(jié)構(gòu)對(duì)算法的影響主要在兩方面 數(shù)據(jù)結(jié)構(gòu)的存

44、儲(chǔ)能力數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)能力數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)能力強(qiáng)、存儲(chǔ)信息多算法將會(huì)較好設(shè)數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)能力強(qiáng)、存儲(chǔ)信息多算法將會(huì)較好設(shè)計(jì)（時(shí)間少），存儲(chǔ)空間大。計(jì)（時(shí)間少），存儲(chǔ)空間大。時(shí)間和空間的平衡時(shí)間和空間的平衡 定義在數(shù)據(jù)結(jié)構(gòu)上的操作定義在數(shù)據(jù)結(jié)構(gòu)上的操作在數(shù)據(jù)結(jié)構(gòu)上定義基本操作算法調(diào)用這些基本操作。在數(shù)據(jù)結(jié)構(gòu)上定義基本操作算法調(diào)用這些基本操作?；静僮髟酵暾静僮髟酵暾?，算法設(shè)計(jì)就越容算法設(shè)計(jì)就越容易易算法算法基本操作基本操作基本算法基本算法應(yīng)用程序應(yīng)用程序應(yīng)用程序是通過應(yīng)用程序是通過調(diào)用基本算法實(shí)調(diào)用基本算法實(shí)現(xiàn)的現(xiàn)的選擇數(shù)據(jù)結(jié)構(gòu)需要考慮的幾個(gè)方面：選擇數(shù)據(jù)結(jié)構(gòu)需要考慮的幾個(gè)方面： 數(shù)據(jù)結(jié)構(gòu)要適應(yīng)問

45、題的狀態(tài)描述。數(shù)據(jù)結(jié)構(gòu)要適應(yīng)問題的狀態(tài)描述。 數(shù)據(jù)結(jié)構(gòu)應(yīng)與所選擇的算法相適應(yīng)。數(shù)據(jù)結(jié)構(gòu)應(yīng)與所選擇的算法相適應(yīng)。 數(shù)據(jù)結(jié)構(gòu)的選擇同時(shí)要兼顧程序設(shè)計(jì)的方便。數(shù)據(jù)結(jié)構(gòu)的選擇同時(shí)要兼顧程序設(shè)計(jì)的方便。 靈活應(yīng)用已有知識(shí)。靈活應(yīng)用已有知識(shí)。問題描述：問題描述：有若干學(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)和若干門課程成績（每個(gè)學(xué)生所選課程數(shù)目可號(hào)和若干門課程成績（每個(gè)學(xué)生所選課程數(shù)目可能不等，但最多不超過能不等，但

46、最多不超過6門）。門）。要求：要求：設(shè)計(jì)一個(gè)程序輸出每個(gè)學(xué)生的學(xué)號(hào)、姓名設(shè)計(jì)一個(gè)程序輸出每個(gè)學(xué)生的學(xué)號(hào)、姓名和平均分以及每門課程（課程編號(hào)從和平均分以及每門課程（課程編號(hào)從16）的平）的平均分。均分。設(shè)計(jì)方案設(shè)計(jì)方案1：將學(xué)生的全部數(shù)據(jù)項(xiàng)放在一個(gè)表中，一將學(xué)生的全部數(shù)據(jù)項(xiàng)放在一個(gè)表中，一個(gè)學(xué)生的全部數(shù)據(jù)對(duì)應(yīng)一條記錄。由于課程最多可選個(gè)學(xué)生的全部數(shù)據(jù)對(duì)應(yīng)一條記錄。由于課程最多可選6門，門，對(duì)應(yīng)的成績項(xiàng)也應(yīng)有對(duì)應(yīng)的成績項(xiàng)也應(yīng)有6個(gè)。對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)如下：個(gè)。對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)如下：struct studint no;/學(xué)號(hào)學(xué)號(hào)char name10;/姓名姓名int bno;/班號(hào)班號(hào)int deg1;/課程課程1分?jǐn)?shù)分?jǐn)?shù)int deg2;/課程課程2分?jǐn)?shù)分?jǐn)?shù)int deg3;/課程課程3分?jǐn)?shù)分?jǐn)?shù)int deg4;/課程課程4分?jǐn)?shù)分?jǐn)?shù)int deg5;/課程課程5分?jǐn)?shù)分?jǐn)?shù)int deg6;/課程課程6分?jǐn)?shù)分?jǐn)?shù);nonamebnodeg1deg2deg3d