數(shù)據(jù)結(jié)構(gòu)北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Page數(shù)據(jù)結(jié)構(gòu)袁武yuan

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)袁武袁武北京理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院軟件研究所軟件研究所北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 2教學(xué)目的教學(xué)目的n掌握常用的基本數(shù)據(jù)結(jié)構(gòu)的掌握常用的基本數(shù)據(jù)結(jié)構(gòu)的ADT及其應(yīng)用及其應(yīng)用n學(xué)會(huì)合理地組織數(shù)據(jù)學(xué)會(huì)合理地組織數(shù)據(jù), 有效地表有效地表示數(shù)據(jù)示數(shù)據(jù), 有效地處理數(shù)據(jù)有效地處理數(shù)據(jù)n基本掌握算法的設(shè)計(jì)分析技術(shù)基本掌握算法的設(shè)計(jì)分析技術(shù)n提高程序設(shè)計(jì)的質(zhì)量提高程序設(shè)計(jì)的質(zhì)量北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 3教學(xué)要求教學(xué)要求n平時(shí)作業(yè)和上機(jī)實(shí)驗(yàn)平時(shí)作業(yè)和上機(jī)實(shí)驗(yàn)

2、30n期末閉卷筆試期末閉卷筆試 70北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 4誠(chéng)信誠(chéng)信n端正學(xué)習(xí)態(tài)度、調(diào)動(dòng)學(xué)習(xí)興趣端正學(xué)習(xí)態(tài)度、調(diào)動(dòng)學(xué)習(xí)興趣n提倡討論，但嚴(yán)禁抄襲提倡討論，但嚴(yán)禁抄襲n可以討論思路，請(qǐng)同學(xué)看算法的邏輯問題可以討論思路，請(qǐng)同學(xué)看算法的邏輯問題和效率問題。和效率問題。n但要親自動(dòng)手實(shí)現(xiàn)。但要親自動(dòng)手實(shí)現(xiàn)。n發(fā)現(xiàn)抄襲，則抄襲者和被抄襲者本次發(fā)現(xiàn)抄襲，則抄襲者和被抄襲者本次作業(yè)或上機(jī)題計(jì)作業(yè)或上機(jī)題計(jì)0分。以后的作業(yè)題會(huì)分。以后的作業(yè)題會(huì)得到重點(diǎn)檢查。得到重點(diǎn)檢查。北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 5按時(shí)提交

3、作業(yè)，嚴(yán)禁抄襲按時(shí)提交作業(yè)，嚴(yán)禁抄襲n作業(yè)和上機(jī)實(shí)驗(yàn)都必須在指定的期限內(nèi)完成并作業(yè)和上機(jī)實(shí)驗(yàn)都必須在指定的期限內(nèi)完成并提交提交n當(dāng)周完成四選一的練習(xí)題當(dāng)周完成四選一的練習(xí)題n上機(jī)實(shí)驗(yàn)：每次三道題，二周完成上機(jī)實(shí)驗(yàn)：每次三道題，二周完成北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 6網(wǎng)絡(luò)教室地址網(wǎng)絡(luò)教室地址http:/ Page 7教材教材n嚴(yán)蔚敏嚴(yán)蔚敏,吳偉民編吳偉民編.數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（C語言版）語言版）M.北京北京:清華大清華大學(xué)出版社學(xué)出版社,1997年年4月月. 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 8教學(xué)參考書教學(xué)參

4、考書(續(xù)續(xù))n美美Mark Allen Weiss.陳越改編陳越改編.Data Structures and Algorithm Analysis in C(Second Edition)M.北京北京:人民郵電出版人民郵電出版社社,2005.n田魯懷田魯懷.數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)M.北京北京:電子工業(yè)出版電子工業(yè)出版社社,2006.n美美Ellis Horowitz等等.李建中等譯李建中等譯.數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（C語言版）語言版）M.北京北京:機(jī)械工業(yè)出版機(jī)械工業(yè)出版社社,2006. n 嚴(yán)蔚敏，嚴(yán)蔚敏，數(shù)據(jù)結(jié)構(gòu)題集數(shù)據(jù)結(jié)構(gòu)題集，清華大學(xué)出版，清華大學(xué)出版社社北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工

5、學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 9教學(xué)參考書教學(xué)參考書(續(xù)續(xù))nDonald E. Knuth, The Art of Computer Programming, Addison Wesley. Vol. 1， Vol 3. 國(guó)防工業(yè)出版社影印。（蘇運(yùn)霖譯）國(guó)防工業(yè)出版社影印。（蘇運(yùn)霖譯）nThomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, MIT Press. 高高等教育出版社影印。等教育出版社影印。nWilliam Ford，Data Stru

6、cture with C+，清華大學(xué)出版社，清華大學(xué)出版社北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 10第一章第一章 概論概論n1.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)n1.2 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)n1.3 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型n1.4 算法的特性及分類算法的特性及分類n1.5 算法的效率度量算法的效率度量n1.6 數(shù)據(jù)結(jié)構(gòu)的選擇和評(píng)價(jià)數(shù)據(jù)結(jié)構(gòu)的選擇和評(píng)價(jià)北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 111.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)n計(jì)算機(jī)軟件與理論學(xué)科的計(jì)算機(jī)軟件與理論學(xué)科的專業(yè)基礎(chǔ)專業(yè)基

7、礎(chǔ)課程課程 n后續(xù)專業(yè)課程學(xué)習(xí)的后續(xù)專業(yè)課程學(xué)習(xí)的必要必要知識(shí)與技能準(zhǔn)備知識(shí)與技能準(zhǔn)備 n編譯技術(shù)要使用棧、散列表及語法樹編譯技術(shù)要使用棧、散列表及語法樹 n操作系統(tǒng)中用隊(duì)列、存儲(chǔ)管理表及目錄樹操作系統(tǒng)中用隊(duì)列、存儲(chǔ)管理表及目錄樹 n數(shù)據(jù)庫系統(tǒng)運(yùn)用線性表、多鏈表、及索引樹數(shù)據(jù)庫系統(tǒng)運(yùn)用線性表、多鏈表、及索引樹 netc.n增強(qiáng)學(xué)生增強(qiáng)學(xué)生求解復(fù)雜問題求解復(fù)雜問題的能力的能力 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 121.2 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)(data structure) n數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)n數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)n數(shù)據(jù)的運(yùn)算

8、數(shù)據(jù)的運(yùn)算 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 131.2.1 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) n反映了我們對(duì)數(shù)據(jù)含義的解釋反映了我們對(duì)數(shù)據(jù)含義的解釋n數(shù)據(jù)的邏輯結(jié)構(gòu)可以用數(shù)據(jù)的邏輯結(jié)構(gòu)可以用一組數(shù)據(jù)一組數(shù)據(jù)（表示為結(jié)點(diǎn)集合（表示為結(jié)點(diǎn)集合K），以及這些數(shù)據(jù)之間的），以及這些數(shù)據(jù)之間的一組二元關(guān)系一組二元關(guān)系（關(guān)系集合（關(guān)系集合R）來表示：來表示：( K ，R )nK是由是由有限個(gè)有限個(gè)結(jié)點(diǎn)組成的集合，每一個(gè)結(jié)點(diǎn)都代表一個(gè)數(shù)據(jù)結(jié)點(diǎn)組成的集合，每一個(gè)結(jié)點(diǎn)都代表一個(gè)數(shù)據(jù)或一組有明確結(jié)構(gòu)的數(shù)據(jù)或一組有明確結(jié)構(gòu)的數(shù)據(jù)n而關(guān)系集而關(guān)系集R是定義在集合是定義在集合K上

9、的一組關(guān)系，其中每個(gè)關(guān)系上的一組關(guān)系，其中每個(gè)關(guān)系(relation) r（rR）都是）都是KK上的二元關(guān)系上的二元關(guān)系，用它描述結(jié)，用它描述結(jié)點(diǎn)數(shù)據(jù)之間的邏輯關(guān)系點(diǎn)數(shù)據(jù)之間的邏輯關(guān)系 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 14數(shù)據(jù)的邏輯結(jié)構(gòu)（示例）數(shù)據(jù)的邏輯結(jié)構(gòu)（示例） n家族人員家族人員n把每個(gè)成員個(gè)體的屬性描述作為數(shù)據(jù)結(jié)點(diǎn)，而全部人員組成把每個(gè)成員個(gè)體的屬性描述作為數(shù)據(jù)結(jié)點(diǎn)，而全部人員組成結(jié)點(diǎn)集結(jié)點(diǎn)集Kn家族的各類親屬關(guān)系就是一組關(guān)系家族的各類親屬關(guān)系就是一組關(guān)系R, 其中如母系血緣關(guān)系其中如母系血緣關(guān)系r、遠(yuǎn)親關(guān)系遠(yuǎn)親關(guān)系r*、和非血緣的親情關(guān)系、

10、和非血緣的親情關(guān)系r等等，每一個(gè)關(guān)系要給等等，每一個(gè)關(guān)系要給出具體人員的關(guān)系元組出具體人員的關(guān)系元組n例如：母子關(guān)系（王愛蓮，張選）例如：母子關(guān)系（王愛蓮，張選） 兄弟關(guān)系（張選，張立）兄弟關(guān)系（張選，張立） 妯娌關(guān)系妯娌關(guān)系 （王愛蓮，李美英）（王愛蓮，李美英）北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 15結(jié)點(diǎn)的類型結(jié)點(diǎn)的類型 n基本數(shù)據(jù)類型基本數(shù)據(jù)類型n整數(shù)類型整數(shù)類型(integer)：該類型規(guī)定了所能表示的整數(shù)范圍，：該類型規(guī)定了所能表示的整數(shù)范圍，在計(jì)算機(jī)中一般使用在計(jì)算機(jī)中一般使用1個(gè)字節(jié)個(gè)字節(jié)到到4個(gè)字節(jié)個(gè)字節(jié)來存儲(chǔ)整數(shù)來存儲(chǔ)整數(shù)n實(shí)數(shù)類型實(shí)數(shù)類

11、型(real)：計(jì)算機(jī)的浮點(diǎn)數(shù)據(jù)類型所能表示的數(shù)值范：計(jì)算機(jī)的浮點(diǎn)數(shù)據(jù)類型所能表示的數(shù)值范圍和精度是圍和精度是有限有限的。的。 機(jī)器一般使用機(jī)器一般使用4個(gè)字節(jié)個(gè)字節(jié)到到8個(gè)字節(jié)個(gè)字節(jié)來存來存儲(chǔ)浮點(diǎn)數(shù)儲(chǔ)浮點(diǎn)數(shù)n布爾類型布爾類型(boolean)：取值為：取值為真真(true)和假和假(false)，在，在C+語言中一般使用整數(shù)語言中一般使用整數(shù)0表示表示false，用非，用非0表示真表示真 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 16結(jié)點(diǎn)的類型結(jié)點(diǎn)的類型 n基本數(shù)據(jù)類型基本數(shù)據(jù)類型n字符類型字符類型(char)：用：用單個(gè)字節(jié)單個(gè)字節(jié)（8bit，最高位，最高

12、位bit為為0）表示）表示ASCII字符集中的字符。字符集中的字符。n漢字符號(hào)需要使用漢字符號(hào)需要使用2個(gè)字節(jié)個(gè)字節(jié)（每個(gè)字節(jié)的最高位（每個(gè)字節(jié)的最高位bit為為1）的編碼，單個(gè)字節(jié)對(duì)于漢字是沒有獨(dú)立含義的。的編碼，單個(gè)字節(jié)對(duì)于漢字是沒有獨(dú)立含義的。北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 17結(jié)點(diǎn)的類型結(jié)點(diǎn)的類型n在在C中把雙字節(jié)表示中文符號(hào)的字節(jié)類型稱中把雙字節(jié)表示中文符號(hào)的字節(jié)類型稱為為w_char類型（類型（wide character）。）。n目前國(guó)際上已經(jīng)采用了統(tǒng)一的擴(kuò)展字符集合標(biāo)準(zhǔn)目前國(guó)際上已經(jīng)采用了統(tǒng)一的擴(kuò)展字符集合標(biāo)準(zhǔn)UNICODE，這一標(biāo)準(zhǔn)

13、允許英、日、韓、阿拉伯，這一標(biāo)準(zhǔn)允許英、日、韓、阿拉伯語等文字的混合文字處理語等文字的混合文字處理北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 18結(jié)點(diǎn)的類型結(jié)點(diǎn)的類型 n基本數(shù)據(jù)類型基本數(shù)據(jù)類型n指針類型指針類型(pointer)：用于表示機(jī)器內(nèi)存地址，指：用于表示機(jī)器內(nèi)存地址，指針表示指向某一內(nèi)存單元的地址。針表示指向某一內(nèi)存單元的地址。n由于機(jī)器的指令系統(tǒng)一般采用由于機(jī)器的指令系統(tǒng)一般采用32 bit或或64bit的地址長(zhǎng)度，的地址長(zhǎng)度，所以指針類型也相應(yīng)地用所以指針類型也相應(yīng)地用4個(gè)字節(jié)個(gè)字節(jié)或或8個(gè)字節(jié)個(gè)字節(jié)來表示一個(gè)來表示一個(gè)指針。指針。北京大理工學(xué)計(jì)

14、算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 19n指針值的存儲(chǔ)和指針值的運(yùn)算方式，在形式上與指針值的存儲(chǔ)和指針值的運(yùn)算方式，在形式上與正整數(shù)相似。正整數(shù)相似。n但指針的運(yùn)算一般僅限于兩個(gè)指針地址的比較，但指針的運(yùn)算一般僅限于兩個(gè)指針地址的比較，加減，或?qū)σ粋€(gè)指針增減一個(gè)整數(shù)量等加減，或?qū)σ粋€(gè)指針增減一個(gè)整數(shù)量等北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 20結(jié)點(diǎn)的類型結(jié)點(diǎn)的類型 n復(fù)合數(shù)據(jù)類型復(fù)合數(shù)據(jù)類型n復(fù)合類型是由基本數(shù)據(jù)類型組合而成的數(shù)據(jù)結(jié)構(gòu)類型。例如：復(fù)合類型是由基本數(shù)據(jù)類型組合而成的數(shù)據(jù)結(jié)構(gòu)類型。例如：在程序語言中常用的數(shù)組類型，結(jié)構(gòu)

15、（記錄）類型等皆屬?gòu)?fù)在程序語言中常用的數(shù)組類型，結(jié)構(gòu)（記錄）類型等皆屬?gòu)?fù)合數(shù)據(jù)類型合數(shù)據(jù)類型n復(fù)合數(shù)據(jù)類型本身，又可以復(fù)合數(shù)據(jù)類型本身，又可以參與定義參與定義結(jié)構(gòu)更為復(fù)雜的結(jié)點(diǎn)類結(jié)構(gòu)更為復(fù)雜的結(jié)點(diǎn)類型。型。n結(jié)點(diǎn)的類型不限于基本數(shù)據(jù)類型，可以根據(jù)應(yīng)用的需要來靈結(jié)點(diǎn)的類型不限于基本數(shù)據(jù)類型，可以根據(jù)應(yīng)用的需要來靈活定義活定義 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 21結(jié)構(gòu)的分類結(jié)構(gòu)的分類 n討論邏輯結(jié)構(gòu)（討論邏輯結(jié)構(gòu)（K,R）的分類，一般把討論重點(diǎn)放在）的分類，一般把討論重點(diǎn)放在關(guān)系集關(guān)系集R上。用上。用R的性質(zhì)來刻劃數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，并對(duì)的性質(zhì)來刻劃數(shù)據(jù)結(jié)構(gòu)

16、的特點(diǎn)，并對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行分類數(shù)據(jù)結(jié)構(gòu)進(jìn)行分類 n線性結(jié)構(gòu)（線性結(jié)構(gòu)（linear structure）n樹型結(jié)構(gòu)（樹型結(jié)構(gòu)（tree structure） n圖結(jié)構(gòu)（圖結(jié)構(gòu)（graph structure）北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 22線性結(jié)構(gòu)線性結(jié)構(gòu)n這種結(jié)構(gòu)在程序設(shè)計(jì)中這種結(jié)構(gòu)在程序設(shè)計(jì)中應(yīng)用最多應(yīng)用最多。n它的關(guān)系它的關(guān)系r 是一種是一種線性關(guān)系線性關(guān)系，或稱為，或稱為前后關(guān)系前后關(guān)系，有時(shí)也稱為有時(shí)也稱為大小關(guān)系大小關(guān)系。關(guān)系。關(guān)系r是是有向有向的，且滿足的，且滿足全全序性序性和和單索性單索性等約束條件等約束條件n全序性是指，線性結(jié)構(gòu)的

17、全部結(jié)點(diǎn)兩兩皆可以比較前后（關(guān)全序性是指，線性結(jié)構(gòu)的全部結(jié)點(diǎn)兩兩皆可以比較前后（關(guān)系系r）n單索性是指，每一個(gè)結(jié)點(diǎn)單索性是指，每一個(gè)結(jié)點(diǎn)x都存在唯一的一個(gè)直接后繼結(jié)點(diǎn)都存在唯一的一個(gè)直接后繼結(jié)點(diǎn)y。如果其他結(jié)點(diǎn)。如果其他結(jié)點(diǎn)z在在y之前，則這個(gè)之前，則這個(gè)z也一定在也一定在x之前，不會(huì)之前，不會(huì)在在x，y之間之間 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 23樹型結(jié)構(gòu)樹型結(jié)構(gòu) n樹型結(jié)構(gòu)簡(jiǎn)稱樹結(jié)構(gòu)，或稱為層次結(jié)構(gòu)。其關(guān)系樹型結(jié)構(gòu)簡(jiǎn)稱樹結(jié)構(gòu)，或稱為層次結(jié)構(gòu)。其關(guān)系r稱為層次關(guān)系，稱為層次關(guān)系，或稱或稱父子關(guān)系父子關(guān)系、上下級(jí)關(guān)系上下級(jí)關(guān)系等等n每一個(gè)結(jié)點(diǎn)可以有每

18、一個(gè)結(jié)點(diǎn)可以有多于一個(gè)的多于一個(gè)的直接下級(jí)直接下級(jí)，但是它只能有，但是它只能有唯唯一的一的直接上級(jí)直接上級(jí)。樹型結(jié)構(gòu)的最高層次的結(jié)點(diǎn)稱為。樹型結(jié)構(gòu)的最高層次的結(jié)點(diǎn)稱為根（根（root）結(jié)點(diǎn)結(jié)點(diǎn)。只有它。只有它沒有父結(jié)點(diǎn)沒有父結(jié)點(diǎn)n從數(shù)學(xué)上看，樹型結(jié)構(gòu)和圖結(jié)構(gòu)的基本區(qū)別就是從數(shù)學(xué)上看，樹型結(jié)構(gòu)和圖結(jié)構(gòu)的基本區(qū)別就是“每個(gè)結(jié)點(diǎn)是每個(gè)結(jié)點(diǎn)是否否僅僅從屬一個(gè)直接上級(jí)僅僅從屬一個(gè)直接上級(jí)”。而線性結(jié)構(gòu)和樹型結(jié)構(gòu)的基本區(qū)。而線性結(jié)構(gòu)和樹型結(jié)構(gòu)的基本區(qū)別是別是“每個(gè)結(jié)點(diǎn)是否每個(gè)結(jié)點(diǎn)是否僅僅有一個(gè)直接后繼僅僅有一個(gè)直接后繼”。n樹型結(jié)構(gòu)存在著很多變種，如二叉樹結(jié)構(gòu)，堆結(jié)構(gòu)等，它們都樹型結(jié)構(gòu)存在著很多變種，如二

19、叉樹結(jié)構(gòu)，堆結(jié)構(gòu)等，它們都有著各自獨(dú)特的有效應(yīng)用有著各自獨(dú)特的有效應(yīng)用北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 24圖結(jié)構(gòu)圖結(jié)構(gòu) n圖結(jié)構(gòu)有時(shí)稱為結(jié)點(diǎn)互聯(lián)的圖結(jié)構(gòu)有時(shí)稱為結(jié)點(diǎn)互聯(lián)的網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)，因特網(wǎng)的網(wǎng)頁，因特網(wǎng)的網(wǎng)頁鏈接關(guān)系就是一個(gè)非常復(fù)雜的圖結(jié)構(gòu)鏈接關(guān)系就是一個(gè)非常復(fù)雜的圖結(jié)構(gòu)n對(duì)于圖結(jié)構(gòu)的關(guān)系對(duì)于圖結(jié)構(gòu)的關(guān)系r沒有加任何約束。這樣也就無法象沒有加任何約束。這樣也就無法象線性結(jié)構(gòu)及樹結(jié)構(gòu)那樣，利用關(guān)系線性結(jié)構(gòu)及樹結(jié)構(gòu)那樣，利用關(guān)系r的約束來設(shè)計(jì)圖結(jié)的約束來設(shè)計(jì)圖結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)構(gòu)的存儲(chǔ)結(jié)構(gòu)n在日常應(yīng)用中圖結(jié)構(gòu)往往只是層次結(jié)構(gòu)的一種擴(kuò)展在日常應(yīng)用中圖結(jié)構(gòu)

20、往往只是層次結(jié)構(gòu)的一種擴(kuò)展允許結(jié)點(diǎn)具有多個(gè)允許結(jié)點(diǎn)具有多個(gè)直接上級(jí)結(jié)點(diǎn)直接上級(jí)結(jié)點(diǎn)，關(guān)系，關(guān)系r表現(xiàn)表現(xiàn)為樹型結(jié)構(gòu)約束的放松為樹型結(jié)構(gòu)約束的放松 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 25結(jié)點(diǎn)和結(jié)構(gòu)結(jié)點(diǎn)和結(jié)構(gòu) n對(duì)于數(shù)據(jù)結(jié)構(gòu)（對(duì)于數(shù)據(jù)結(jié)構(gòu)（K,R），結(jié)點(diǎn)數(shù)據(jù)類型不限于基本數(shù)），結(jié)點(diǎn)數(shù)據(jù)類型不限于基本數(shù)據(jù)類型，可以根據(jù)應(yīng)用需要來靈活設(shè)計(jì)結(jié)點(diǎn)的數(shù)據(jù)類據(jù)類型，可以根據(jù)應(yīng)用需要來靈活設(shè)計(jì)結(jié)點(diǎn)的數(shù)據(jù)類型型n可以認(rèn)為數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)是一層一層地進(jìn)行的可以認(rèn)為數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)是一層一層地進(jìn)行的n先明確先明確數(shù)據(jù)結(jié)點(diǎn)數(shù)據(jù)結(jié)點(diǎn)，及其，及其主要關(guān)系主要關(guān)系r n在分析關(guān)系在分析關(guān)

21、系r的同時(shí)，也要分析其數(shù)據(jù)結(jié)點(diǎn)的的同時(shí)，也要分析其數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù)類型數(shù)據(jù)類型n如果數(shù)據(jù)結(jié)點(diǎn)的邏輯結(jié)構(gòu)比較復(fù)雜，那么把它作為下一個(gè)層如果數(shù)據(jù)結(jié)點(diǎn)的邏輯結(jié)構(gòu)比較復(fù)雜，那么把它作為下一個(gè)層次，再分析下一層次的邏輯結(jié)構(gòu)次，再分析下一層次的邏輯結(jié)構(gòu)n這是一種這是一種自頂向下自頂向下的分析設(shè)計(jì)方法的分析設(shè)計(jì)方法 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 261.2.2 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)n計(jì)算機(jī)的主存儲(chǔ)器的特性計(jì)算機(jī)的主存儲(chǔ)器的特性n其存儲(chǔ)空間提供了一種具有其存儲(chǔ)空間提供了一種具有非負(fù)整數(shù)非負(fù)整數(shù)地址編地址編碼的，碼的，相鄰單元相鄰單元的集合，其基本的存儲(chǔ)單元的

22、集合，其基本的存儲(chǔ)單元是是字節(jié)字節(jié)n計(jì)算機(jī)的指令具有計(jì)算機(jī)的指令具有按地址隨機(jī)訪問按地址隨機(jī)訪問存儲(chǔ)空間存儲(chǔ)空間內(nèi)任意單元的能力，訪問不同地址所需的訪內(nèi)任意單元的能力，訪問不同地址所需的訪問時(shí)間基本相同問時(shí)間基本相同 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 271.2.2 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)n用數(shù)學(xué)上的映射來表示，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是建立一種用數(shù)學(xué)上的映射來表示，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是建立一種映射，對(duì)于數(shù)據(jù)邏輯結(jié)構(gòu)（映射，對(duì)于數(shù)據(jù)邏輯結(jié)構(gòu)（ K , r ）,其中其中rRn對(duì)它的結(jié)點(diǎn)集合對(duì)它的結(jié)點(diǎn)集合K建立一個(gè)從建立一個(gè)從K到存儲(chǔ)器到存儲(chǔ)器M的單元的映射：的單

23、元的映射：KM，對(duì)于每一個(gè)結(jié)點(diǎn)，對(duì)于每一個(gè)結(jié)點(diǎn)jK都對(duì)應(yīng)一個(gè)都對(duì)應(yīng)一個(gè)唯一唯一的的連續(xù)存儲(chǔ)連續(xù)存儲(chǔ)區(qū)區(qū)域域cM。n每一個(gè)關(guān)系元組（每一個(gè)關(guān)系元組（j1 ,j2）r（其中（其中j1, j2K是結(jié)點(diǎn)），亦是結(jié)點(diǎn)），亦即即j1, j2的邏輯后繼關(guān)系應(yīng)映射為存儲(chǔ)單元的地址順序關(guān)系的邏輯后繼關(guān)系應(yīng)映射為存儲(chǔ)單元的地址順序關(guān)系（或指針的地址指向關(guān)系）。（或指針的地址指向關(guān)系）。n四種基本存儲(chǔ)映射方法：順序、鏈接、索引、散列四種基本存儲(chǔ)映射方法：順序、鏈接、索引、散列北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 28順序（順序（sequential）的方法）的方法 n用一塊無空

24、隙的存儲(chǔ)區(qū)域存儲(chǔ)數(shù)據(jù)稱為用一塊無空隙的存儲(chǔ)區(qū)域存儲(chǔ)數(shù)據(jù)稱為順序順序存儲(chǔ)存儲(chǔ)n順序存儲(chǔ)把一組結(jié)點(diǎn)存儲(chǔ)在按順序存儲(chǔ)把一組結(jié)點(diǎn)存儲(chǔ)在按地址相鄰地址相鄰的順的順序存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯后繼關(guān)系用存序存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯后繼關(guān)系用存儲(chǔ)單元的自然順序關(guān)系來表達(dá)儲(chǔ)單元的自然順序關(guān)系來表達(dá) n順序存儲(chǔ)法為使用整數(shù)編碼來訪問數(shù)據(jù)結(jié)點(diǎn)順序存儲(chǔ)法為使用整數(shù)編碼來訪問數(shù)據(jù)結(jié)點(diǎn)提供了便利提供了便利 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 29順序（順序（sequential）的方法）的方法 n順序存儲(chǔ)結(jié)構(gòu)稱為順序存儲(chǔ)結(jié)構(gòu)稱為緊湊存儲(chǔ)結(jié)構(gòu)緊湊存儲(chǔ)結(jié)構(gòu)，其緊湊性是指它，其緊湊性是指

25、它的存儲(chǔ)空間除了存儲(chǔ)有用數(shù)據(jù)外，沒有用于存儲(chǔ)其的存儲(chǔ)空間除了存儲(chǔ)有用數(shù)據(jù)外，沒有用于存儲(chǔ)其他附加的信息他附加的信息n緊湊性可以用緊湊性可以用存儲(chǔ)密度存儲(chǔ)密度來度量：它是一個(gè)存儲(chǔ)來度量：它是一個(gè)存儲(chǔ)結(jié)構(gòu)所存儲(chǔ)的結(jié)構(gòu)所存儲(chǔ)的有用數(shù)據(jù)有用數(shù)據(jù)和該結(jié)構(gòu)（包括附加信和該結(jié)構(gòu)（包括附加信息）整個(gè)存儲(chǔ)空間大小之比。息）整個(gè)存儲(chǔ)空間大小之比。n有時(shí)為了有時(shí)為了用空間換取時(shí)間用空間換取時(shí)間，在存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)，在存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)一些附加信息還是很必要的。譬如用于提高算法的一些附加信息還是很必要的。譬如用于提高算法的執(zhí)行速度，或者讓算法實(shí)現(xiàn)更為簡(jiǎn)便等執(zhí)行速度，或者讓算法實(shí)現(xiàn)更為簡(jiǎn)便等 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

26、北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 30順序（順序（sequential）的方法）的方法 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 31鏈接（鏈接（linked）的方法）的方法 n利用指針，在結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)中附加指針字段稱為利用指針，在結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)中附加指針字段稱為鏈接法鏈接法。兩個(gè)結(jié)點(diǎn)的邏輯后繼關(guān)系可以用指針的指。兩個(gè)結(jié)點(diǎn)的邏輯后繼關(guān)系可以用指針的指向來表達(dá)向來表達(dá)n任意的邏輯關(guān)系任意的邏輯關(guān)系r，也可以使用這種指針地址來表達(dá)。，也可以使用這種指針地址來表達(dá)。一般的做法是將數(shù)據(jù)結(jié)點(diǎn)分為兩部分一般的做法是將數(shù)據(jù)結(jié)點(diǎn)分為兩部分:n一部分存放結(jié)點(diǎn)本身的數(shù)

27、據(jù)，稱為一部分存放結(jié)點(diǎn)本身的數(shù)據(jù)，稱為數(shù)據(jù)字段數(shù)據(jù)字段n另一部分存放指針，稱另一部分存放指針，稱指針字段指針字段，鏈接到某個(gè)后繼結(jié)點(diǎn)，鏈接到某個(gè)后繼結(jié)點(diǎn)，指向它的存儲(chǔ)單元的開始地址。多個(gè)相關(guān)結(jié)點(diǎn)的依次鏈接指向它的存儲(chǔ)單元的開始地址。多個(gè)相關(guān)結(jié)點(diǎn)的依次鏈接就會(huì)形成就會(huì)形成鏈索鏈索北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 32鏈接（鏈接（linked）的方法）的方法 n對(duì)于經(jīng)常增刪結(jié)點(diǎn)的復(fù)雜數(shù)據(jù)結(jié)構(gòu)，順序存儲(chǔ)往往會(huì)對(duì)于經(jīng)常增刪結(jié)點(diǎn)的復(fù)雜數(shù)據(jù)結(jié)構(gòu)，順序存儲(chǔ)往往會(huì)遇到困難，鏈接方法結(jié)合遇到困難，鏈接方法結(jié)合new動(dòng)態(tài)存儲(chǔ)為這些復(fù)雜問動(dòng)態(tài)存儲(chǔ)為這些復(fù)雜問題提供了解決方法

28、題提供了解決方法n它也有缺陷：它也有缺陷：n為了訪問結(jié)點(diǎn)集為了訪問結(jié)點(diǎn)集K中某個(gè)結(jié)點(diǎn)，必須用該結(jié)點(diǎn)的存儲(chǔ)指針中某個(gè)結(jié)點(diǎn)，必須用該結(jié)點(diǎn)的存儲(chǔ)指針n當(dāng)不知道結(jié)點(diǎn)指針時(shí)，為了在結(jié)點(diǎn)集當(dāng)不知道結(jié)點(diǎn)指針時(shí)，為了在結(jié)點(diǎn)集K中尋找某個(gè)符合條件中尋找某個(gè)符合條件的結(jié)點(diǎn)，就要沿著鏈接結(jié)點(diǎn)的鏈索，一個(gè)個(gè)結(jié)點(diǎn)比較搜索。的結(jié)點(diǎn)，就要沿著鏈接結(jié)點(diǎn)的鏈索，一個(gè)個(gè)結(jié)點(diǎn)比較搜索。所需花費(fèi)的時(shí)間是較大的所需花費(fèi)的時(shí)間是較大的 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 33鏈接（鏈接（linked）的方法）的方法 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 34索

29、引（索引（indexing）的方法）的方法 n索引法是順序存儲(chǔ)法的一種推廣，它也使用整數(shù)編碼來訪問數(shù)索引法是順序存儲(chǔ)法的一種推廣，它也使用整數(shù)編碼來訪問數(shù)據(jù)結(jié)點(diǎn)位置據(jù)結(jié)點(diǎn)位置n索引方法是要建造一個(gè)由整數(shù)域索引方法是要建造一個(gè)由整數(shù)域Z映射到存儲(chǔ)地址域映射到存儲(chǔ)地址域D的函數(shù)的函數(shù)Y：ZD，把，把結(jié)點(diǎn)的整數(shù)索引值結(jié)點(diǎn)的整數(shù)索引值 zZ映射到映射到結(jié)點(diǎn)的存儲(chǔ)地址結(jié)點(diǎn)的存儲(chǔ)地址 dD 。它稱為。它稱為索引函數(shù)索引函數(shù)，一般而言它并不象數(shù)組那樣，是簡(jiǎn)，一般而言它并不象數(shù)組那樣，是簡(jiǎn)單的線性函數(shù)。單的線性函數(shù)。n當(dāng)數(shù)據(jù)結(jié)點(diǎn)長(zhǎng)度不等的情況下，索引函數(shù)就無法用線性表達(dá)式當(dāng)數(shù)據(jù)結(jié)點(diǎn)長(zhǎng)度不等的情況下，索引函數(shù)就

30、無法用線性表達(dá)式給出給出北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 35索引（索引（indexing）的方法）的方法n為了構(gòu)造任意的索引函數(shù)，可以為索引函數(shù)提供附加為了構(gòu)造任意的索引函數(shù)，可以為索引函數(shù)提供附加的存儲(chǔ)空間，稱為的存儲(chǔ)空間，稱為索引表索引表Sn索引表中每一元素是指向數(shù)據(jù)結(jié)點(diǎn)的指針。因?yàn)樗饕饕碇忻恳辉厥侵赶驍?shù)據(jù)結(jié)點(diǎn)的指針。因?yàn)樗饕肀鞸由等長(zhǎng)元素（指針）組成，所以可以進(jìn)行線性的由等長(zhǎng)元素（指針）組成，所以可以進(jìn)行線性的索引計(jì)算：索引計(jì)算： 始址始址(元素元素Si) 始址始址(元素元素S0) i （指針尺寸）（指針尺寸）n通過上述公式，由索引號(hào)通

31、過上述公式，由索引號(hào)i可以計(jì)算出索引表中的單可以計(jì)算出索引表中的單元元Si的始址，再通過讀出的始址，再通過讀出Si元素的內(nèi)容（是指元素的內(nèi)容（是指針），訪問真正需要訪問的數(shù)據(jù)結(jié)點(diǎn)針），訪問真正需要訪問的數(shù)據(jù)結(jié)點(diǎn)北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 36索引（索引（indexing）的方法）的方法n索引方法也付出了存儲(chǔ)開銷，其數(shù)據(jù)結(jié)點(diǎn)要附索引方法也付出了存儲(chǔ)開銷，其數(shù)據(jù)結(jié)點(diǎn)要附加用于指針的存儲(chǔ)空間。加用于指針的存儲(chǔ)空間。n索引方法在程序設(shè)計(jì)中是一種經(jīng)常使用的方法，索引方法在程序設(shè)計(jì)中是一種經(jīng)常使用的方法，其主要原因是對(duì)于非順序的存儲(chǔ)結(jié)構(gòu)來說，使其主要原因是對(duì)

32、于非順序的存儲(chǔ)結(jié)構(gòu)來說，使用索引表是快速地由整數(shù)索引值找到其對(duì)應(yīng)數(shù)用索引表是快速地由整數(shù)索引值找到其對(duì)應(yīng)數(shù)據(jù)結(jié)點(diǎn)的據(jù)結(jié)點(diǎn)的唯一唯一方法方法北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 37索引（索引（indexing）的方法）的方法北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 38散列（散列（hashing）的方法）的方法 n散列方法是索引方法的一種延伸和擴(kuò)展散列方法是索引方法的一種延伸和擴(kuò)展n利用一種稱為利用一種稱為散列函數(shù)散列函數(shù)(hash functions)進(jìn)行索引值的計(jì)算，然后通過索引表求出結(jié)點(diǎn)的進(jìn)行索引值的計(jì)算，然后通過索

33、引表求出結(jié)點(diǎn)的指針地址指針地址n散列函數(shù)是將字符串散列函數(shù)是將字符串s映射到非負(fù)整數(shù)映射到非負(fù)整數(shù)z的一類函的一類函數(shù)數(shù)h: S Z ， 對(duì)任意的對(duì)任意的 s S，散列函數(shù)，散列函數(shù) h(s)=z，z Z北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 39散列（散列（hashing）的方法）的方法 n散列函數(shù)散列函數(shù)h(s)除了它取非負(fù)整數(shù)值外，除了它取非負(fù)整數(shù)值外，關(guān)鍵的問題：關(guān)鍵的問題：n恰當(dāng)?shù)剡x擇散列函數(shù)恰當(dāng)?shù)剡x擇散列函數(shù)n如何建造散列表如何建造散列表n在構(gòu)建散列表的中間解決在構(gòu)建散列表的中間解決碰撞碰撞的辦的辦法法 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工

34、學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 40抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(abstract data structure) n抽象數(shù)據(jù)類型是描述數(shù)據(jù)結(jié)構(gòu)的一種理論工具抽象數(shù)據(jù)類型是描述數(shù)據(jù)結(jié)構(gòu)的一種理論工具n特點(diǎn)是把數(shù)據(jù)結(jié)構(gòu)作為獨(dú)立于應(yīng)用程序的一種抽象特點(diǎn)是把數(shù)據(jù)結(jié)構(gòu)作為獨(dú)立于應(yīng)用程序的一種抽象代數(shù)結(jié)構(gòu)來描述代數(shù)結(jié)構(gòu)來描述n因此在很大程度上可以使人們獨(dú)立于程序的實(shí)現(xiàn)細(xì)因此在很大程度上可以使人們獨(dú)立于程序的實(shí)現(xiàn)細(xì)節(jié)來理解數(shù)據(jù)結(jié)構(gòu)的主要性質(zhì)和約束條件節(jié)來理解數(shù)據(jù)結(jié)構(gòu)的主要性質(zhì)和約束條件北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 41抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(abstruct

35、data structure) n抽象數(shù)據(jù)類型不同于具體的數(shù)據(jù)結(jié)構(gòu)，前者所描述的是抽象數(shù)據(jù)類型不同于具體的數(shù)據(jù)結(jié)構(gòu)，前者所描述的是一種模板以及模板的結(jié)構(gòu)和性質(zhì)。而模板的類型參數(shù)一種模板以及模板的結(jié)構(gòu)和性質(zhì)。而模板的類型參數(shù)T（元素的數(shù)據(jù)類型）必須用具體的數(shù)據(jù)類型所代入，才（元素的數(shù)據(jù)類型）必須用具體的數(shù)據(jù)類型所代入，才能成為具體的數(shù)據(jù)類型能成為具體的數(shù)據(jù)類型n抽象數(shù)據(jù)類型是把數(shù)據(jù)結(jié)構(gòu)作為獨(dú)立于應(yīng)用程序的一種抽象數(shù)據(jù)類型是把數(shù)據(jù)結(jié)構(gòu)作為獨(dú)立于應(yīng)用程序的一種抽象抽象，目的是使人們能夠獨(dú)立于程序的實(shí)現(xiàn)細(xì)節(jié)來理解，目的是使人們能夠獨(dú)立于程序的實(shí)現(xiàn)細(xì)節(jié)來理解數(shù)據(jù)結(jié)構(gòu)的特性數(shù)據(jù)結(jié)構(gòu)的特性 北京大理工學(xué)計(jì)算

36、機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 42抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(abstruct data structure) n抽象數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)結(jié)構(gòu) n的取值空間的取值空間n的關(guān)系集合的關(guān)系集合n的運(yùn)算集的運(yùn)算集 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 43抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(abstruct data structure) n的取值空間：給出該數(shù)據(jù)結(jié)構(gòu)的所有可能取值的集合。為此的取值空間：給出該數(shù)據(jù)結(jié)構(gòu)的所有可能取值的集合。為此需要準(zhǔn)確地給出該數(shù)據(jù)結(jié)構(gòu)需要準(zhǔn)確地給出該數(shù)據(jù)結(jié)構(gòu) 的組成元素的取值類型的組成元素的取值類型 n 的取值空間

37、大小取決于它的元素類型的取值空間大小取決于它的元素類型T。具體的數(shù)據(jù)結(jié)構(gòu)是。具體的數(shù)據(jù)結(jié)構(gòu)是 和和T聯(lián)合確定的聯(lián)合確定的 n對(duì)于取值空間，進(jìn)一步說明它的大小是否可以動(dòng)態(tài)改變是很重要對(duì)于取值空間，進(jìn)一步說明它的大小是否可以動(dòng)態(tài)改變是很重要的的 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 44抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(abstruct data structure) n的運(yùn)算集：一般使用函數(shù)來定義運(yùn)算，參與運(yùn)算的的運(yùn)算集：一般使用函數(shù)來定義運(yùn)算，參與運(yùn)算的對(duì)象成為函數(shù)的輸入?yún)?shù)，運(yùn)算結(jié)果是函數(shù)值對(duì)象成為函數(shù)的輸入?yún)?shù)，運(yùn)算結(jié)果是函數(shù)值n為適合不同應(yīng)用領(lǐng)域以及它的元素

38、類型為適合不同應(yīng)用領(lǐng)域以及它的元素類型T的不同，同一的不同，同一個(gè)結(jié)構(gòu)的含義會(huì)有所不同，也就需要適當(dāng)?shù)靥砑右恍﹤€(gè)結(jié)構(gòu)的含義會(huì)有所不同，也就需要適當(dāng)?shù)靥砑右恍┬碌倪\(yùn)算種類新的運(yùn)算種類n運(yùn)算集的選擇也會(huì)受到該數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方案的影響運(yùn)算集的選擇也會(huì)受到該數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方案的影響北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 45抽象數(shù)據(jù)類型描述抽象數(shù)據(jù)類型描述ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象的定義數(shù)據(jù)對(duì)象的定義數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義數(shù)據(jù)關(guān)系的定義基本操作：基本操作：基本操作的定義基本操作的定義 ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)

39、類型名北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 46抽象數(shù)據(jù)類型描述抽象數(shù)據(jù)類型描述(續(xù)續(xù))基本操作名（參數(shù)表）基本操作名（參數(shù)表） 初始條件：初始條件： 操作結(jié)果：操作結(jié)果：賦值參數(shù)賦值參數(shù): 只為操作提供輸入值。只為操作提供輸入值。引用參數(shù)：以引用參數(shù)：以&打頭，除可提供輸入值之外，還將返回操作結(jié)果。打頭，除可提供輸入值之外，還將返回操作結(jié)果。初始條件：描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若初始條件：描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。操作結(jié)果：說

40、明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返操作結(jié)果：說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果?；氐慕Y(jié)果。北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 47ADT示例：復(fù)數(shù)定義示例：復(fù)數(shù)定義 ADT Complex 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象： De1,e2e1,e2RealSet 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 | e1是復(fù)數(shù)的實(shí)數(shù)部分是復(fù)數(shù)的實(shí)數(shù)部分, | e2 是復(fù)數(shù)的虛數(shù)部分是復(fù)數(shù)的虛數(shù)部分 基本操作：基本操作： InitComplex( &Z, v1, v2 ) 操作結(jié)果：構(gòu)造復(fù)數(shù)操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)其實(shí)部和虛部

41、分別被賦以參數(shù)v1和和v2的值。的值。 DestroyComplex( &Z) 操作結(jié)果：復(fù)數(shù)操作結(jié)果：復(fù)數(shù)Z被銷毀。被銷毀。 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 48ADT示例：復(fù)數(shù)定義（續(xù)）示例：復(fù)數(shù)定義（續(xù)） GetReal( Z, &realPart ) 初始條件：復(fù)數(shù)已存在。初始條件：復(fù)數(shù)已存在。操作結(jié)果：用操作結(jié)果：用realPart返回復(fù)數(shù)返回復(fù)數(shù)Z的實(shí)部值。的實(shí)部值。GetImag( Z, &ImagPart )初始條件：復(fù)數(shù)已存在。初始條件：復(fù)數(shù)已存在。操作結(jié)果：用操作結(jié)果：用ImagPart返回復(fù)數(shù)返回復(fù)數(shù)Z的

42、虛部值。的虛部值。Add( z1,z2, &sum ) 初始條件：初始條件：z1,z2是復(fù)數(shù)是復(fù)數(shù)。操作結(jié)果：用操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)返回兩個(gè)復(fù)數(shù)z1,z2的和值。的和值。 ADT Complex北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 49北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 501.4 算法及其特性算法及其特性n算法算法(algorithms)是為了求解問題而給出的是為了求解問題而給出的指令序列指令序列n程序程序是算法的一種實(shí)現(xiàn)，計(jì)算機(jī)按照程序逐步是算法的一種實(shí)現(xiàn)，計(jì)算機(jī)按照程序逐步執(zhí)行算法，實(shí)現(xiàn)對(duì)問題

43、的求解執(zhí)行算法，實(shí)現(xiàn)對(duì)問題的求解 n一個(gè)一個(gè)求解問題求解問題通常用該問題的輸入數(shù)據(jù)類型和通常用該問題的輸入數(shù)據(jù)類型和該問題所要求解的結(jié)果（算法的輸出數(shù)據(jù)）所該問題所要求解的結(jié)果（算法的輸出數(shù)據(jù)）所應(yīng)遵循的性質(zhì)來描述應(yīng)遵循的性質(zhì)來描述 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 511.4.1 算法及其特性算法及其特性n 算法應(yīng)該具有如下性質(zhì)算法應(yīng)該具有如下性質(zhì):n一定的通用性。一定的通用性。n對(duì)于那些符合輸入類型的任意輸入數(shù)據(jù)，都能根據(jù)算法進(jìn)行問題求對(duì)于那些符合輸入類型的任意輸入數(shù)據(jù)，都能根據(jù)算法進(jìn)行問題求解，并保證計(jì)算結(jié)果的正確性解，并保證計(jì)算結(jié)果的正確性n算

44、法的有效性。算法的有效性。n算法是有限條指令組成的指令序列，其中每一條指令都必須是能夠算法是有限條指令組成的指令序列，其中每一條指令都必須是能夠被確切執(zhí)行的，被人或機(jī)器所執(zhí)行。指令的類型應(yīng)該明確規(guī)定，僅被確切執(zhí)行的，被人或機(jī)器所執(zhí)行。指令的類型應(yīng)該明確規(guī)定，僅限于若干明確無誤的指令動(dòng)作，是一個(gè)有限的指令集限于若干明確無誤的指令動(dòng)作，是一個(gè)有限的指令集 。其結(jié)果應(yīng)具。其結(jié)果應(yīng)具有確定的數(shù)據(jù)類型，是能夠預(yù)期的有確定的數(shù)據(jù)類型，是能夠預(yù)期的北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 521.4.1 算法及其特性算法及其特性n算法的確定性。算法的確定性。n算法每執(zhí)行一步

45、之后，關(guān)于它的下一步，應(yīng)該有明確的指示。下一算法每執(zhí)行一步之后，關(guān)于它的下一步，應(yīng)該有明確的指示。下一步動(dòng)作可以是條件判斷、分支指令、或順序執(zhí)行一條指令、或者指步動(dòng)作可以是條件判斷、分支指令、或順序執(zhí)行一條指令、或者指示整個(gè)算法的結(jié)束等。算法的確定性要保證每一步之后都有關(guān)于下示整個(gè)算法的結(jié)束等。算法的確定性要保證每一步之后都有關(guān)于下一步動(dòng)作的指令，不能缺乏下一步指令（被鎖住）或僅僅含有模糊一步動(dòng)作的指令，不能缺乏下一步指令（被鎖?。┗騼H僅含有模糊不清的指令不清的指令n 算法的有窮性。算法的有窮性。n算法的執(zhí)行必須在有限步內(nèi)結(jié)束。換句話說，算法不能含有死循環(huán)算法的執(zhí)行必須在有限步內(nèi)結(jié)束。換句話說

46、，算法不能含有死循環(huán) 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 531.4.2 計(jì)算復(fù)雜性和算法的效率計(jì)算復(fù)雜性和算法的效率n根據(jù)計(jì)算理論根據(jù)計(jì)算理論(theory of computation)，存在著一，存在著一類問題雖然能夠被準(zhǔn)確定義，但卻不存在能夠解決該類問題雖然能夠被準(zhǔn)確定義，但卻不存在能夠解決該問題的算法。稱為問題的算法。稱為不可解問題不可解問題n計(jì)算復(fù)雜性理論計(jì)算復(fù)雜性理論(computational complexity theory)指出，理論上存在一大類難解問題，它們雖指出，理論上存在一大類難解問題，它們雖然存在著求解算法，但是在算法的計(jì)算

47、時(shí)間上，都是然存在著求解算法，但是在算法的計(jì)算時(shí)間上，都是組合爆炸型組合爆炸型的求解算法的求解算法北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 541.4.2 計(jì)算復(fù)雜性和算法的效率計(jì)算復(fù)雜性和算法的效率n所謂組合爆炸型，是指隨著問題的規(guī)模所謂組合爆炸型，是指隨著問題的規(guī)模n的增大，算的增大，算法的時(shí)間開銷不能約束在法的時(shí)間開銷不能約束在n的的k階多項(xiàng)式數(shù)量范圍內(nèi)。階多項(xiàng)式數(shù)量范圍內(nèi)。（其中（其中k是任意不依賴于是任意不依賴于n的常數(shù)）的常數(shù)） n根據(jù)計(jì)算復(fù)雜性理論，根據(jù)計(jì)算復(fù)雜性理論，難解問題難解問題的定義就是它的求解的定義就是它的求解算法均無法在多項(xiàng)式時(shí)間算法

48、均無法在多項(xiàng)式時(shí)間nk數(shù)量級(jí)內(nèi)解決（其中數(shù)量級(jí)內(nèi)解決（其中k是是任意正整數(shù)）。比較常見的難解問題有：圖論中的求任意正整數(shù)）。比較常見的難解問題有：圖論中的求最優(yōu)巡游路徑問題，判定命題邏輯公式是否為恒真等最優(yōu)巡游路徑問題，判定命題邏輯公式是否為恒真等北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 551.5 算法的執(zhí)行效率及其度量算法的執(zhí)行效率及其度量n解決同一個(gè)問題總是存在著多種算法，而算解決同一個(gè)問題總是存在著多種算法，而算法設(shè)計(jì)者在所法設(shè)計(jì)者在所花費(fèi)的時(shí)間花費(fèi)的時(shí)間和所和所使用的空間使用的空間資資源往往要兩者之間采取折中，采用某種以空源往往要兩者之間采取折中，采

49、用某種以空間資源換取時(shí)間資源的策略間資源換取時(shí)間資源的策略n算法設(shè)計(jì)者可以通過算法分析，判斷所提出算法設(shè)計(jì)者可以通過算法分析，判斷所提出的算法是否現(xiàn)實(shí)，設(shè)計(jì)出更好的算法的算法是否現(xiàn)實(shí)，設(shè)計(jì)出更好的算法 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 561.5.1算法的漸進(jìn)分析算法的漸進(jìn)分析(asymptotic analysis) n算法的漸進(jìn)分析，簡(jiǎn)稱算法的漸進(jìn)分析，簡(jiǎn)稱算法分析算法分析。算法在計(jì)算機(jī)。算法在計(jì)算機(jī)上實(shí)際執(zhí)行時(shí)，需要消耗時(shí)間資源（歸結(jié)為上實(shí)際執(zhí)行時(shí)，需要消耗時(shí)間資源（歸結(jié)為CPU執(zhí)行指令的總數(shù)），和使用空間資源（歸結(jié)為所執(zhí)行指令的總數(shù)），和使用空

50、間資源（歸結(jié)為所需占用的存儲(chǔ)單元數(shù)量，字節(jié)數(shù)）。需占用的存儲(chǔ)單元數(shù)量，字節(jié)數(shù)）。n由于算法分析和它所求解的問題規(guī)模直接有關(guān)，由于算法分析和它所求解的問題規(guī)模直接有關(guān)，因此通常將因此通常將問題規(guī)模問題規(guī)模n作為一個(gè)參照量，求算法的作為一個(gè)參照量，求算法的時(shí)空開銷和時(shí)空開銷和n的關(guān)系。的關(guān)系。 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 571.5.1算法的漸進(jìn)分析算法的漸進(jìn)分析(asymptotic analysis) n算法的漸進(jìn)分析就是要估計(jì)，當(dāng)數(shù)據(jù)規(guī)模算法的漸進(jìn)分析就是要估計(jì)，當(dāng)數(shù)據(jù)規(guī)模n逐逐步增大時(shí)，資源開銷步增大時(shí)，資源開銷T(n)的增長(zhǎng)趨勢(shì)。的增長(zhǎng)趨勢(shì)

51、。n從數(shù)量級(jí)大小的比較來考慮，當(dāng)從數(shù)量級(jí)大小的比較來考慮，當(dāng)n增大到一定增大到一定值以后，資源開銷的計(jì)算公式中影響最大的就值以后，資源開銷的計(jì)算公式中影響最大的就是是n的冪次最高的項(xiàng)，其他的常數(shù)項(xiàng)和低冪次的冪次最高的項(xiàng)，其他的常數(shù)項(xiàng)和低冪次項(xiàng)都是可以忽略的。項(xiàng)都是可以忽略的。 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 581.5.1算法的漸進(jìn)分析算法的漸進(jìn)分析(asymptotic analysis) n算法的漸進(jìn)分析就是要得到一個(gè)大算法的漸進(jìn)分析就是要得到一個(gè)大O漸進(jìn)表達(dá)式，簡(jiǎn)寫為：漸進(jìn)表達(dá)式，簡(jiǎn)寫為：rate n T(n) O( F(n) )n其中其中O是

52、數(shù)學(xué)分析常用符號(hào)是數(shù)學(xué)分析常用符號(hào)大大O，而而 F(n)是自變量為是自變量為n的某個(gè)具體的整的某個(gè)具體的整函數(shù)表達(dá)式，例如函數(shù)表達(dá)式，例如F(n)n2北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 59算法的漸進(jìn)分析示例算法的漸進(jìn)分析示例矩陣求和（矩陣求和（matrix_addition ）void matrix_addition(double *M1, double *M2, int k)/ 矩陣矩陣M1,M2求和，即兩兩元素求和，結(jié)果存回求和，即兩兩元素求和，結(jié)果存回M1/ kk是矩陣的規(guī)模是矩陣的規(guī)模 for (int i=0 ; ik; i+) for (i

53、nt j=0 ; jk; j+) /對(duì)應(yīng)位置的矩陣元素相加對(duì)應(yīng)位置的矩陣元素相加 M1ij = M1ij +M2ij ;北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 60算法的漸進(jìn)分析示例算法的漸進(jìn)分析示例矩陣求和（矩陣求和（matrix_addition ）n此問題的規(guī)模由輸入數(shù)據(jù)規(guī)模決定，主要是浮點(diǎn)矩陣此問題的規(guī)模由輸入數(shù)據(jù)規(guī)模決定，主要是浮點(diǎn)矩陣M1, M2的尺寸的尺寸n2*k2 n在漸進(jìn)分析時(shí)，通常我們把浮點(diǎn)運(yùn)算和數(shù)組元素的讀寫在漸進(jìn)分析時(shí)，通常我們把浮點(diǎn)運(yùn)算和數(shù)組元素的讀寫操作的執(zhí)行時(shí)間都看作在同一個(gè)數(shù)量級(jí)內(nèi)，忽略其執(zhí)行操作的執(zhí)行時(shí)間都看作在同一個(gè)數(shù)量級(jí)

54、內(nèi)，忽略其執(zhí)行時(shí)間的細(xì)微差別時(shí)間的細(xì)微差別n為了求出一個(gè)漸進(jìn)估計(jì)的代數(shù)公式，若令為了求出一個(gè)漸進(jìn)估計(jì)的代數(shù)公式，若令r是單個(gè)指令是單個(gè)指令執(zhí)行時(shí)間，那么對(duì)于矩陣加法程序，由于循環(huán)體每執(zhí)行執(zhí)行時(shí)間，那么對(duì)于矩陣加法程序，由于循環(huán)體每執(zhí)行一次，需要一次，需要p r時(shí)間，其中時(shí)間，其中p是一個(gè)常數(shù)倍數(shù)是一個(gè)常數(shù)倍數(shù) 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 61算法的漸進(jìn)分析示例算法的漸進(jìn)分析示例矩陣求和（矩陣求和（matrix_addition ）n考慮到兩重嵌套的考慮到兩重嵌套的for循環(huán)，一共執(zhí)行循環(huán)，一共執(zhí)行kk遍，因此，遍，因此，這個(gè)程序的時(shí)間開銷的漸進(jìn)估

55、計(jì)式可以寫為這個(gè)程序的時(shí)間開銷的漸進(jìn)估計(jì)式可以寫為T(n) p r nC。其中。其中C是一個(gè)不隨是一個(gè)不隨n而變化的常數(shù)，代表那些而變化的常數(shù)，代表那些在進(jìn)入循環(huán)體前后計(jì)算機(jī)所作的輔助操作時(shí)間在進(jìn)入循環(huán)體前后計(jì)算機(jī)所作的輔助操作時(shí)間n由此看出，矩陣加法的時(shí)間開銷是和問題規(guī)模由此看出，矩陣加法的時(shí)間開銷是和問題規(guī)模n成正比成正比的，或稱該算法（的時(shí)間開銷）是線性增長(zhǎng)率的。簡(jiǎn)寫的，或稱該算法（的時(shí)間開銷）是線性增長(zhǎng)率的。簡(jiǎn)寫為為rate n T(n) O(n )，即，即F(n)=n北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 621.5.1算法的漸進(jìn)分析算法的漸進(jìn)分析

56、(asymptotic analysis) n用于漸進(jìn)分析的常見的用于漸進(jìn)分析的常見的F(n)還有以下若干種還有以下若干種 ：nF(n) = 1, 常數(shù)函數(shù)，不依賴于常數(shù)函數(shù)，不依賴于nnF(n) = log n, 對(duì)數(shù)函數(shù)，它比線性函數(shù)對(duì)數(shù)函數(shù)，它比線性函數(shù)n增長(zhǎng)慢增長(zhǎng)慢nF(n) = n， 線性增長(zhǎng)，隨著問題規(guī)模線性增長(zhǎng)，隨著問題規(guī)模n而增長(zhǎng)而增長(zhǎng) 例如，例如，rate n（n個(gè)個(gè)a相加）相加） = rate n （n a） = O(n)nF(n) = n2，二階增長(zhǎng)，二階增長(zhǎng) 例如，例如，rate n i=1.n j=i.n ( a ) = O(n2)， 這是因?yàn)檫@是因?yàn)?i=1.n（a

57、 ( ni )）（）（a (n (n-1)/2)北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 631.5.1算法的漸進(jìn)分析算法的漸進(jìn)分析(asymptotic analysis) n用于漸進(jìn)分析的常見的用于漸進(jìn)分析的常見的F(n)還有以下若干種還有以下若干種 ：nF(n)= n log(n)，其增長(zhǎng)率的階數(shù)低于二階，但高于，其增長(zhǎng)率的階數(shù)低于二階，但高于一階線性。例如，一階線性。例如， rate n i=1.log n j=i.n ( a ) O( n log(n) )n F(n)= an 指數(shù)增長(zhǎng)，隨問題規(guī)模指數(shù)增長(zhǎng)，隨問題規(guī)模n而增長(zhǎng)極快而增長(zhǎng)極快 這種指數(shù)型

58、的漸進(jìn)函數(shù)往往由遞歸定義的函數(shù)產(chǎn)生。例這種指數(shù)型的漸進(jìn)函數(shù)往往由遞歸定義的函數(shù)產(chǎn)生。例 如函數(shù)如函數(shù)H(n)，令，令H(1)=1, 且且H(n)=2 H(n-1), 那么那么通過遞推可以計(jì)算出通過遞推可以計(jì)算出H(n) = 2(n-1)北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 641.5.2最壞、最好、和平均情況最壞、最好、和平均情況n在具體進(jìn)行算法增長(zhǎng)率估計(jì)時(shí)，往往會(huì)由于算法中在具體進(jìn)行算法增長(zhǎng)率估計(jì)時(shí)，往往會(huì)由于算法中的條件分支而遇到困難。的條件分支而遇到困難。n由于算法實(shí)際執(zhí)行的操作往往依賴于分支條件的走由于算法實(shí)際執(zhí)行的操作往往依賴于分支條件的走向，而

59、輸入數(shù)據(jù)的取值又影響這些分支走向，因此向，而輸入數(shù)據(jù)的取值又影響這些分支走向，因此很多算法都無法得出獨(dú)立于輸入數(shù)據(jù)的漸進(jìn)估計(jì)。很多算法都無法得出獨(dú)立于輸入數(shù)據(jù)的漸進(jìn)估計(jì)。n針對(duì)這一情況，提出了最壞情況估計(jì)、平均情況估針對(duì)這一情況，提出了最壞情況估計(jì)、平均情況估計(jì)、和計(jì)、和Theta（ 希塔）估計(jì)等三種方法希塔）估計(jì)等三種方法 北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 651.5.2示例示例求矩陣求矩陣M中絕對(duì)值最大的元素中絕對(duì)值最大的元素 double abs_biggest(double *M, int k) /求矩陣求矩陣M中絕對(duì)值最大的元素，中絕對(duì)值最大

60、的元素，kk是矩陣的規(guī)模是矩陣的規(guī)模 double current_big = 0;/臨時(shí)存儲(chǔ)單元，初始化為臨時(shí)存儲(chǔ)單元，初始化為0 for (int i=0 ; ik; i+) for (int j=0 ; j current_big) current_big = temp; / current_big存儲(chǔ)當(dāng)前最大者存儲(chǔ)當(dāng)前最大者 return current_big; /函數(shù)值返回函數(shù)值返回北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院北京大理工學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 Page 661.5.2示例示例求矩陣求矩陣M中絕對(duì)值最大的元素中絕對(duì)值最大的元素 n輸入?yún)?shù)為浮點(diǎn)矩陣輸入?yún)?shù)為浮點(diǎn)矩陣M，它的大小是影響算法時(shí)空開銷，它的大小是影響算法時(shí)空開銷