第一章數(shù)據(jù)結(jié)構(gòu)概論

1、數(shù)據(jù)結(jié)構(gòu)(C語言版) Data Structure授課教師：孫曉芳授課教師：孫曉芳聯(lián)系方式：聯(lián)系方式：教材：教材： 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 高等教育出版社高等教育出版社 陳越陳越參考資料：參考資料：數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)與實(shí)驗(yàn)指導(dǎo)，陳越著，高等教育出版社數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)與實(shí)驗(yàn)指導(dǎo)，陳越著，高等教育出版社學(xué)時(shí)：學(xué)時(shí)：3636學(xué)時(shí)課堂學(xué)時(shí)課堂課程安排課程要求成績(jī)構(gòu)成及比例成績(jī)構(gòu)成及比例總評(píng)成績(jī)=平時(shí)總成績(jī)（40%）+期末考試成績(jī)60%其中平時(shí)成績(jī)包括考勤（占總分的10%）、作業(yè)（占總分的20%）、小測(cè)驗(yàn)（占總分的10%）取消考試資格情況取消考試資格情況缺課累計(jì)13學(xué)時(shí)及以上者取消考試資格；無故曠課8學(xué)時(shí)者取消考試資格

2、；抄襲他人作業(yè)、未完成作業(yè)次數(shù)較多的取消考試資格。 引子引子 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 算法算法 應(yīng)用實(shí)例應(yīng)用實(shí)例為什么要學(xué)數(shù)據(jù)結(jié)構(gòu)？ “數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)、軟件工程專業(yè)甚至于是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)、軟件工程專業(yè)甚至于其它電氣信息類專業(yè)的重要專業(yè)基礎(chǔ)課程。它所討論的知識(shí)內(nèi)容和提其它電氣信息類專業(yè)的重要專業(yè)基礎(chǔ)課程。它所討論的知識(shí)內(nèi)容和提倡的技術(shù)方法，無論對(duì)進(jìn)一步學(xué)習(xí)計(jì)算機(jī)領(lǐng)域的其它課程，還是對(duì)從倡的技術(shù)方法，無論對(duì)進(jìn)一步學(xué)習(xí)計(jì)算機(jī)領(lǐng)域的其它課程，還是對(duì)從事大型信息工程的開發(fā)，都是重要而必備的基礎(chǔ)。事大型信息工程的開發(fā)，都是重要而必備的基礎(chǔ)。 程序設(shè)計(jì)解決問題往往有多種方法，且不同

3、方法之間的效率可程序設(shè)計(jì)解決問題往往有多種方法，且不同方法之間的效率可能相差甚遠(yuǎn)。程序的時(shí)間和空間效率，不僅跟數(shù)據(jù)的組織方式有關(guān)，能相差甚遠(yuǎn)。程序的時(shí)間和空間效率，不僅跟數(shù)據(jù)的組織方式有關(guān)，也跟處理流程的巧妙程度有關(guān)。本課程將介紹并探討有關(guān)數(shù)據(jù)組織、也跟處理流程的巧妙程度有關(guān)。本課程將介紹并探討有關(guān)數(shù)據(jù)組織、算法設(shè)計(jì)、時(shí)間和空間效率的概念和通用分析方法，幫助學(xué)生學(xué)會(huì)數(shù)算法設(shè)計(jì)、時(shí)間和空間效率的概念和通用分析方法，幫助學(xué)生學(xué)會(huì)數(shù)據(jù)的組織方法和一些典型算法的實(shí)現(xiàn)，能夠針對(duì)問題的應(yīng)用背景分析，據(jù)的組織方法和一些典型算法的實(shí)現(xiàn)，能夠針對(duì)問題的應(yīng)用背景分析，選擇合適的數(shù)據(jù)結(jié)構(gòu)，從而培養(yǎng)高級(jí)程序設(shè)計(jì)技能。

4、選擇合適的數(shù)據(jù)結(jié)構(gòu)，從而培養(yǎng)高級(jí)程序設(shè)計(jì)技能。1 引子引子第第1章章 概論概論 為什么要學(xué)數(shù)據(jù)結(jié)構(gòu)？考研課程考研課程計(jì)算機(jī)等級(jí)考試課程計(jì)算機(jī)等級(jí)考試課程程序員考試課程程序員考試課程編程基礎(chǔ)編程基礎(chǔ) N.N.沃思（沃思（Niklaus Wirth)Niklaus Wirth)教授提出：教授提出： 程序=算法+數(shù)據(jù)結(jié)構(gòu)實(shí)際應(yīng)用需求實(shí)際應(yīng)用需求 數(shù)值計(jì)算數(shù)值計(jì)算非數(shù)值計(jì)算非數(shù)值計(jì)算1 引子引子第第1章章 概論概論 第第1章章 概論概論 【定義定義】“數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)中數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)中存儲(chǔ)、組織數(shù)據(jù)存儲(chǔ)、組織數(shù)據(jù)的方式。的方式。精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來最優(yōu)效率的算法最優(yōu)效

5、率的算法。”1/251 引子引子例例1.1 該該如何擺放書如何擺放書，才能讓讀者很方便地找到你手里這本，才能讓讀者很方便地找到你手里這本數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)？什么是數(shù)據(jù)結(jié)構(gòu)？第第1章章 概論概論 【分析分析】2/251 引子引子方法方法1 隨便放隨便放-任何時(shí)候有新書進(jìn)來，哪里有空就把書插到哪里。任何時(shí)候有新書進(jìn)來，哪里有空就把書插到哪里。方法方法2 按照書名的按照書名的字母順序字母順序排放。排放。方法方法3 把書架把書架劃分成幾塊區(qū)域劃分成幾塊區(qū)域，每塊區(qū)域指定擺放某種類別的圖書；，每塊區(qū)域指定擺放某種類別的圖書；在每種類別內(nèi)，按照書名的拼音字母順序排放。在每種類別內(nèi)，按照書名的拼音字母順序排

6、放。 查找效率極低！查找效率極低！ 有時(shí)插入新書很困難！有時(shí)插入新書很困難！ 可能造成空間的浪費(fèi)！可能造成空間的浪費(fèi)！查找效率查找效率 跟數(shù)據(jù)的組織方式有關(guān)！跟數(shù)據(jù)的組織方式有關(guān)！第第1章章 概論概論 1 引子引子例例1.2 ：寫程序?qū)崿F(xiàn)一個(gè)函數(shù)：寫程序?qū)崿F(xiàn)一個(gè)函數(shù)PrintN，使得傳入一個(gè)正，使得傳入一個(gè)正整數(shù)為整數(shù)為N的參數(shù)后，能順序的參數(shù)后，能順序打印從打印從1到到N的全部正整數(shù)。的全部正整數(shù)。 void PrintN ( int N ) int i; for ( i=1; i=N; i+ ) printf(“%dn”, i ); return; void PrintN ( int N

7、) if ( !N ) return; PrintN( N 1 ); printf(“%dn”, N ); return; 3/25運(yùn)行效率運(yùn)行效率 跟空間的利用效率有關(guān)！跟空間的利用效率有關(guān)！第第1章章 概論概論 1 引子引子例例1.3 多項(xiàng)式的標(biāo)準(zhǔn)表達(dá)式可以寫為：多項(xiàng)式的標(biāo)準(zhǔn)表達(dá)式可以寫為： f(x) = a0 + a1x + a2x2 + + anxn現(xiàn)給定一個(gè)多項(xiàng)式的階數(shù)現(xiàn)給定一個(gè)多項(xiàng)式的階數(shù) n，并將全體系數(shù)存放在數(shù)組，并將全體系數(shù)存放在數(shù)組 a 里。請(qǐng)寫程序計(jì)算這個(gè)多項(xiàng)式在里。請(qǐng)寫程序計(jì)算這個(gè)多項(xiàng)式在給定點(diǎn)給定點(diǎn) x 處的值處的值。方法方法1 計(jì)算多項(xiàng)式函數(shù)值的計(jì)算多項(xiàng)式函數(shù)值的直

8、接法直接法 double f( int n, double a, double x ) /* 計(jì)算階數(shù)為計(jì)算階數(shù)為n，系數(shù)為，系數(shù)為a0.an的多項(xiàng)式在的多項(xiàng)式在x點(diǎn)的值點(diǎn)的值 */int i;double p = a0;for ( i=1; i0; i-)p = ai-1 + x*p;return p;4/25#include #include clock_t start, stop; /* clock_t是是clock()函數(shù)返回的變量類型函數(shù)返回的變量類型 */double duration; /* 記錄被測(cè)函數(shù)運(yùn)行時(shí)間，以秒為單位記錄被測(cè)函數(shù)運(yùn)行時(shí)間，以秒為單位 */int main

9、() /* 不在測(cè)試范圍內(nèi)的準(zhǔn)備工作寫在不在測(cè)試范圍內(nèi)的準(zhǔn)備工作寫在clock()調(diào)用之前調(diào)用之前*/ start = clock(); /* 開始計(jì)時(shí)開始計(jì)時(shí) */ function(); /* 把被測(cè)函數(shù)加在這里把被測(cè)函數(shù)加在這里 */ stop = clock(); /* 停止計(jì)時(shí)停止計(jì)時(shí) */ duration = (double)(stop - start)/CLK_TCK;/* 計(jì)算運(yùn)行時(shí)間計(jì)算運(yùn)行時(shí)間 */ /* 其他不在測(cè)試范圍的處理寫在后面，例如輸出其他不在測(cè)試范圍的處理寫在后面，例如輸出duration的值的值 */ return 0; 第第1章章 概論概論 1 引子引子5

10、/25代碼代碼1.6 測(cè)試函數(shù)測(cè)試函數(shù)function()的的運(yùn)行時(shí)間運(yùn)行時(shí)間秦九韶算法的計(jì)算速度明顯比秦九韶算法的計(jì)算速度明顯比直接法直接法快了一個(gè)數(shù)量級(jí)快了一個(gè)數(shù)量級(jí)！為什么會(huì)這樣？為什么會(huì)這樣？ 即使解決一個(gè)非常簡(jiǎn)單的問題，往往也有即使解決一個(gè)非常簡(jiǎn)單的問題，往往也有多種方法多種方法，且不同方法之間的且不同方法之間的效率可能相差甚遠(yuǎn)效率可能相差甚遠(yuǎn) 解決問題方法的解決問題方法的效率效率 跟數(shù)據(jù)的跟數(shù)據(jù)的組織方式組織方式有關(guān)（如例有關(guān)（如例1.1） 跟跟空間的利用效率空間的利用效率有關(guān)（如例有關(guān)（如例1.2） 跟跟算法的巧妙算法的巧妙程度有關(guān)（如例程度有關(guān)（如例1.3）第第1章章 概論概論

11、 1 引子引子6/25第第1章章 概論概論 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象： 計(jì)算機(jī)要處理的事物，通常計(jì)算機(jī)要處理的事物，通常是是性質(zhì)相同性質(zhì)相同的數(shù)據(jù)元素的集的數(shù)據(jù)元素的集合。合。如例如例1中中“圖書圖書” 。2.1 術(shù)語定義術(shù)語定義 操作操作：處理事物的動(dòng)作集合，如例處理事物的動(dòng)作集合，如例1中的中的“查找查找”和和“插入插入”，例例2的函數(shù)的函數(shù)“求值求值”等。等。 算法算法： 操作的實(shí)現(xiàn)方法，如例操作的實(shí)現(xiàn)方法，如例1的按字母序排放的的按字母序排放的“查找查找”和和“插入插入”、例、例2的的“直接法直接法”和和“秦九韶法秦九韶法”等；等； 通常一個(gè)算法用一個(gè)通常一個(gè)算法用一個(gè)函數(shù)函數(shù)來實(shí)現(xiàn)來實(shí)現(xiàn)。7

12、/25數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)： 數(shù)據(jù)對(duì)象在計(jì)算機(jī)中的數(shù)據(jù)對(duì)象在計(jì)算機(jī)中的組織方式組織方式 定義在數(shù)據(jù)對(duì)象之上的操作定義在數(shù)據(jù)對(duì)象之上的操作 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)：數(shù)據(jù)元素間抽象化的相互數(shù)據(jù)元素間抽象化的相互關(guān)系關(guān)系。與數(shù)據(jù)的存儲(chǔ)。與數(shù)據(jù)的存儲(chǔ)無關(guān)，獨(dú)立于計(jì)算機(jī)，它是從具體問題抽象出來的數(shù)學(xué)模型。無關(guān)，獨(dú)立于計(jì)算機(jī)，它是從具體問題抽象出來的數(shù)學(xué)模型。分為分為“集合集合”、“線性線性”、“樹樹”和和“圖圖”。例。例1中按方中按方法法1來處理，就是把圖書集看成是線性的結(jié)構(gòu)；按方法來處理，就是把圖書集看成是線性的結(jié)構(gòu)；按方法3來處理，就是把圖書集看成是樹型的結(jié)構(gòu)。來處理，就是把圖書集看成是樹型的結(jié)構(gòu)。 物理結(jié)構(gòu)

13、物理結(jié)構(gòu)：數(shù)據(jù)對(duì)象信息在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)組織關(guān)：數(shù)據(jù)對(duì)象信息在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)組織關(guān)系，它依賴于計(jì)算機(jī)語言。一般分為系，它依賴于計(jì)算機(jī)語言。一般分為“順序存儲(chǔ)順序存儲(chǔ)”和和“鏈鏈?zhǔn)酱鎯?chǔ)式存儲(chǔ)”。（索引存儲(chǔ)，散列存儲(chǔ)）。（索引存儲(chǔ)，散列存儲(chǔ)）數(shù)據(jù)對(duì)象在計(jì)算機(jī)中的組織方式：數(shù)據(jù)對(duì)象在計(jì)算機(jī)中的組織方式：邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)。第第1章章 概論概論 2.1 術(shù)語定義術(shù)語定義數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)（物理）結(jié)構(gòu)存儲(chǔ)（物理）結(jié)構(gòu)數(shù)據(jù)運(yùn)算數(shù)據(jù)運(yùn)算線性結(jié)構(gòu)（線性表、棧、隊(duì)列、串、數(shù)組等）線性結(jié)構(gòu)（線性表、棧、隊(duì)列、串、數(shù)組等）非線性結(jié)構(gòu)非線性結(jié)構(gòu)順序結(jié)構(gòu)順序結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)插

14、入插入刪除刪除查找查找排序排序修改修改樹結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)圖結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)就是數(shù)據(jù)元素之間的邏輯關(guān)系?？杀硎緸椋簲?shù)據(jù)的邏輯結(jié)構(gòu)就是數(shù)據(jù)元素之間的邏輯關(guān)系?？杀硎緸椋?Data_Structure =(DData_Structure =(D，R)R)其中，其中，D D是組成數(shù)據(jù)的數(shù)據(jù)元素的有限集合，是組成數(shù)據(jù)的數(shù)據(jù)元素的有限集合，R R是數(shù)據(jù)元素之間的關(guān)系集合。是數(shù)據(jù)元素之間的關(guān)系集合。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，數(shù)據(jù)結(jié)構(gòu)可分為線性數(shù)據(jù)結(jié)構(gòu)和非線根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，數(shù)據(jù)結(jié)構(gòu)可分為線性數(shù)據(jù)結(jié)構(gòu)和非線性數(shù)據(jù)結(jié)構(gòu)。性數(shù)據(jù)結(jié)構(gòu)。（1 1）線性結(jié)構(gòu)的邏輯特征是除第一個(gè)結(jié)點(diǎn)和

15、最后一個(gè)結(jié)點(diǎn)外，其他所有結(jié)）線性結(jié)構(gòu)的邏輯特征是除第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)都有且只有一個(gè)直接前趨和一個(gè)直接后繼結(jié)點(diǎn)。點(diǎn)都有且只有一個(gè)直接前趨和一個(gè)直接后繼結(jié)點(diǎn)。（2 2）非線性結(jié)構(gòu)的邏輯特征是一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。）非線性結(jié)構(gòu)的邏輯特征是一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是面向應(yīng)用問題的，是從用戶角度看到的數(shù)據(jù)的結(jié)數(shù)據(jù)的邏輯結(jié)構(gòu)是面向應(yīng)用問題的，是從用戶角度看到的數(shù)據(jù)的結(jié)構(gòu)。數(shù)據(jù)必須在計(jì)算機(jī)內(nèi)存儲(chǔ)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)構(gòu)。數(shù)據(jù)必須在計(jì)算機(jī)內(nèi)存儲(chǔ)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(storage (storage structure)structure)是

16、研究數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系如何在計(jì)算機(jī)中是研究數(shù)據(jù)元素和數(shù)據(jù)元素之間的關(guān)系如何在計(jì)算機(jī)中表示，是邏輯數(shù)據(jù)的存儲(chǔ)映像，它是面向計(jì)算機(jī)的。表示，是邏輯數(shù)據(jù)的存儲(chǔ)映像，它是面向計(jì)算機(jī)的。實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)到計(jì)算機(jī)存儲(chǔ)器的映像有多種不同的方式。通實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)到計(jì)算機(jī)存儲(chǔ)器的映像有多種不同的方式。通常，數(shù)據(jù)在存儲(chǔ)器中的存儲(chǔ)有兩種基本的映像方法。常，數(shù)據(jù)在存儲(chǔ)器中的存儲(chǔ)有兩種基本的映像方法。（1 1）順序存儲(chǔ)結(jié)構(gòu)（）順序存儲(chǔ)結(jié)構(gòu)（Sequential Storage StructureSequential Storage Structure）：把邏輯上）：把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的

17、存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)，它主要用于線性數(shù)據(jù)結(jié)構(gòu)，非線性的數(shù)據(jù)結(jié)構(gòu)也可以通過某種線性化它主要用于線性數(shù)據(jù)結(jié)構(gòu)，非線性的數(shù)據(jù)結(jié)構(gòu)也可以通過某種線性化的方法來實(shí)現(xiàn)順序存儲(chǔ)。的方法來實(shí)現(xiàn)順序存儲(chǔ)。（2 2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（Linked Storage StructureLinked Storage Structure）：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)把邏輯上相鄰的兩個(gè)元素存放在物理上不一定相鄰的存儲(chǔ)單元

18、中，結(jié)把邏輯上相鄰的兩個(gè)元素存放在物理上不一定相鄰的存儲(chǔ)單元中，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)就點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)就是將存放每個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)分為兩部分：一部分存放數(shù)據(jù)元素是將存放每個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)分為兩部分：一部分存放數(shù)據(jù)元素( (稱稱為數(shù)據(jù)域?yàn)閿?shù)據(jù)域) )；另一部分存放指示存儲(chǔ)地址的指針；另一部分存放指示存儲(chǔ)地址的指針( (稱為指針域稱為指針域) )，借助，借助指針表示數(shù)據(jù)元素之間的關(guān)系。指針表示數(shù)據(jù)元素之間的關(guān)系。例：復(fù)數(shù)74i 的兩種存儲(chǔ)方式： （1）地址 內(nèi)容 （2）地址 內(nèi)容7403200322707020320

19、032207024 數(shù)據(jù)結(jié)構(gòu)定義：數(shù)據(jù)結(jié)構(gòu)定義： 按某種按某種邏輯關(guān)系邏輯關(guān)系組織起來的一批數(shù)據(jù)（或稱帶結(jié)構(gòu)的數(shù)據(jù)元素的集合）應(yīng)用計(jì)算機(jī)語言并按一定的存儲(chǔ)表示按一定的存儲(chǔ)表示 方式方式把它們存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，并在其上定義了一個(gè)運(yùn)在其上定義了一個(gè)運(yùn)算的集合算的集合。定義定義2-是相互之間存在相互之間存在一種或多種特定關(guān)系一種或多種特定關(guān)系的數(shù)據(jù)元素的數(shù)據(jù)元素的集合。的集合。第第1章章 概論概論 數(shù)據(jù)類型：數(shù)據(jù)類型： 數(shù)據(jù)對(duì)象的類型確定了其數(shù)據(jù)對(duì)象的類型確定了其“操作集操作集”和和“數(shù)據(jù)定義域數(shù)據(jù)定義域”。比如：整型，字符型等。比如：整型，字符型等。2.2 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 抽象數(shù)據(jù)

20、類型（抽象數(shù)據(jù)類型（Abstract Data Type ，簡(jiǎn)稱簡(jiǎn)稱ADT） ： 由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型數(shù)據(jù)模型。它由基本的數(shù)據(jù)類型構(gòu)成，并包括一一組相關(guān)組相關(guān)的服務(wù)（或稱操作操作）。8/25 ADT的形式化定義是三元組：的形式化定義是三元組：ADT=(D，S，P)其中：其中：D是是數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象，S是是D上的上的關(guān)系集關(guān)系集，P是對(duì)是對(duì)D的的基本操基本操作集作集。第第1章章 概論概論 例例1.4“矩陣矩陣”的抽象數(shù)據(jù)類型定義的抽象數(shù)據(jù)類型定義2.2 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型類型名稱類型名稱：Matrix數(shù)據(jù)對(duì)象集：數(shù)據(jù)對(duì)象集：一個(gè)一個(gè)M N的矩陣的矩陣 A。操作集操作集：對(duì)

21、于任意矩陣：對(duì)于任意矩陣A、B、C Matrix，以及正整數(shù)，以及正整數(shù)i、j、M、N，以下僅列出幾項(xiàng)有代表性的操作。以下僅列出幾項(xiàng)有代表性的操作。1）Matrix Create( int M, int N )：返回一個(gè)返回一個(gè)M N的空矩陣；的空矩陣；2） int GetMaxRow( Matrix A )：返回矩陣：返回矩陣A的總行數(shù)；的總行數(shù)；3）int GetMaxCol( Matrix A )：返回矩陣：返回矩陣A的總列數(shù)；的總列數(shù)；4）ElementType GetEntry( Matrix A, int i, int j )：返回矩陣：返回矩陣A的第的第i行、行、第第j列的元素；

22、列的元素；5）Matrix Add( Matrix A, Matrix B )：如果：如果A和和B的行、列數(shù)一致，則的行、列數(shù)一致，則返回矩陣返回矩陣C=A+B，否則返回錯(cuò)誤標(biāo)志；，否則返回錯(cuò)誤標(biāo)志；6） Matrix Multiply( Matrix A, Matrix B )：如果：如果A的列數(shù)等于的列數(shù)等于B的行數(shù)，的行數(shù)，則返回矩陣則返回矩陣C = AB，否則返回錯(cuò)誤標(biāo)志；，否則返回錯(cuò)誤標(biāo)志；7）9/25第第1章章 概論概論 2.2 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型“抽象抽象”描述數(shù)據(jù)對(duì)象時(shí)，并描述數(shù)據(jù)對(duì)象時(shí)，并不規(guī)定不規(guī)定其中其中數(shù)據(jù)元素的類型數(shù)據(jù)元素的類型對(duì)數(shù)據(jù)對(duì)象的描述對(duì)數(shù)據(jù)對(duì)象的描述不

23、依賴不依賴其在計(jì)算機(jī)中的其在計(jì)算機(jī)中的存儲(chǔ)方法存儲(chǔ)方法描述操作時(shí)，只描述操作要實(shí)現(xiàn)的功能，描述操作時(shí)，只描述操作要實(shí)現(xiàn)的功能，并不涉及并不涉及具體實(shí)現(xiàn)方法具體實(shí)現(xiàn)方法【定義定義】一個(gè)一個(gè)算法算法是解決某一類問題的步驟的描述。是解決某一類問題的步驟的描述。一般一般而言，算法應(yīng)該符合以下五項(xiàng)要求：而言，算法應(yīng)該符合以下五項(xiàng)要求：(1) 輸入輸入：它接受一些輸入（有些情況下不需要輸入）；它接受一些輸入（有些情況下不需要輸入）；(2) 輸出輸出：至少產(chǎn)生一個(gè)輸出；至少產(chǎn)生一個(gè)輸出；(3) 確定性確定性：算法的每一步必須有充分明確的含義，不可以有歧義；算法的每一步必須有充分明確的含義，不可以有歧義；(4

24、) 有限性有限性：算法是一個(gè)有限指令集，并一定在有限步驟之后終止；算法是一個(gè)有限指令集，并一定在有限步驟之后終止；(5) 可行性可行性：算法的每一步必須在計(jì)算機(jī)能處理的范圍之內(nèi)算法的每一步必須在計(jì)算機(jī)能處理的范圍之內(nèi)第第1章章 概論概論 3.1 算法定義算法定義 另外，另外，算法的描述算法的描述可以不依賴于任何一種計(jì)算機(jī)語言以及具體的可以不依賴于任何一種計(jì)算機(jī)語言以及具體的實(shí)現(xiàn)手段。可以用實(shí)現(xiàn)手段。可以用自然語言、流程圖自然語言、流程圖等方法來描述。等方法來描述。 但是，用某一種計(jì)算機(jī)語言進(jìn)行但是，用某一種計(jì)算機(jī)語言進(jìn)行偽碼描述偽碼描述往往使算法容易被理解，往往使算法容易被理解，本書即采用本書

25、即采用C語言的部分語法作為描述算法的工具。語言的部分語法作為描述算法的工具。10/25例例 選擇法排序選擇法排序：把：把n個(gè)整數(shù)排序成從小到大。個(gè)整數(shù)排序成從小到大。思想：從余下的未排序的部分整數(shù)中，挑選最小整數(shù)放在前思想：從余下的未排序的部分整數(shù)中，挑選最小整數(shù)放在前面已排序部分的后面面已排序部分的后面.如何進(jìn)行排序如何進(jìn)行排序? 哪里哪里?void SelectionSort ( int List, int N ) /* 將將N個(gè)整數(shù)個(gè)整數(shù)List0.ListN-1進(jìn)行非遞減排序進(jìn)行非遞減排序 */ for ( i = 0; i N; i + ) MinPosition = ScanFor

26、Min( List, i, N1 ); /* 從從Listi到到ListN1中找最小元，并將其位置賦給中找最小元，并將其位置賦給MinPosition */ Swap( Listi, ListMinPosition ); /* 將未排序部分的最小元換到有序部分的最后位置將未排序部分的最小元換到有序部分的最后位置 */ 選擇排序選擇排序 = 找最小整數(shù)找最小整數(shù) + 交換至合適位置交換至合適位置.第第1章章 概論概論 3.1 算法例子算法例子11/25第第1章章 概論概論 3.2 算法復(fù)雜度算法復(fù)雜度 什么是什么是“好好”的算法？的算法？12/25算法設(shè)計(jì)的基本要求（評(píng)價(jià)指標(biāo)）算法設(shè)計(jì)的基本要求

27、（評(píng)價(jià)指標(biāo)）u正確性u(píng)可讀性u(píng)健壯性u(píng)效率和低存儲(chǔ)量需求常用時(shí)間復(fù)雜度來衡量常用時(shí)間復(fù)雜度來衡量常用空間復(fù)雜度來衡量常用空間復(fù)雜度來衡量度量程序的執(zhí)行時(shí)間的方法1事后統(tǒng)計(jì)，指的是通過計(jì)事后統(tǒng)計(jì)，指的是通過計(jì)算機(jī)內(nèi)部計(jì)算時(shí)間，并進(jìn)算機(jī)內(nèi)部計(jì)算時(shí)間，并進(jìn)行分析行分析。2事前分析估算，主要事前分析估算，主要指的指的是在分析時(shí)間復(fù)雜度等因是在分析時(shí)間復(fù)雜度等因素基礎(chǔ)上進(jìn)行研究。素基礎(chǔ)上進(jìn)行研究。 第第1章章 概論概論 3.2 算法復(fù)雜度算法復(fù)雜度 時(shí)間復(fù)雜度時(shí)間復(fù)雜度 T(n) 根據(jù)算法寫成的根據(jù)算法寫成的程序在執(zhí)行時(shí)耗費(fèi)時(shí)間的長(zhǎng)程序在執(zhí)行時(shí)耗費(fèi)時(shí)間的長(zhǎng)度度。這個(gè)長(zhǎng)度往往也與輸入數(shù)據(jù)的規(guī)模。這個(gè)長(zhǎng)度往

28、往也與輸入數(shù)據(jù)的規(guī)模 有關(guān)。時(shí)間復(fù)雜度過高的低有關(guān)。時(shí)間復(fù)雜度過高的低效算法可能導(dǎo)致我們?cè)谟猩甓嫉炔坏竭\(yùn)行結(jié)果。效算法可能導(dǎo)致我們?cè)谟猩甓嫉炔坏竭\(yùn)行結(jié)果。12/25 T(n)-常用程序中常用程序中最深層循環(huán)內(nèi)最深層循環(huán)內(nèi)的語句的原操作的的語句的原操作的執(zhí)行頻度執(zhí)行頻度(重重復(fù)執(zhí)行的次數(shù)復(fù)執(zhí)行的次數(shù))來表示來表示.第第1章章 概論概論 3.2 算法復(fù)雜度算法復(fù)雜度12/25（1）定義（算法執(zhí)行時(shí)間的增長(zhǎng)率）定義（算法執(zhí)行時(shí)間的增長(zhǎng)率） T(n)=o(f(n)（2）說明）說明 f( n)是基本操作（包括語句）的重復(fù)執(zhí)行的次數(shù)是基本操作（包括語句）的重復(fù)執(zhí)行的次數(shù) o( )為漸進(jìn)符號(hào)為漸進(jìn)符

29、號(hào) （3）計(jì)算方法）計(jì)算方法 T(n)由嵌套最深層語句的（頻度）執(zhí)行次數(shù)決定由嵌套最深層語句的（頻度）執(zhí)行次數(shù)決定 例如：分析以下程序段的時(shí)間復(fù)雜度例如：分析以下程序段的時(shí)間復(fù)雜度 i=1; For (i=1;i=2n;i+) i=i+2; 分析：語句的頻度是分析：語句的頻度是1 1，語句，語句2 2的頻度是的頻度是f(n)=2nf(n)=2n 所以該程序段的時(shí)間復(fù)雜度T(n)=O(n)T(n)=O(n)01234567891001020304050602nn2n log nnlog nfn第第1章章 概論概論 3.3 復(fù)雜度的漸進(jìn)表示法復(fù)雜度的漸進(jìn)表示法18/25補(bǔ)充說明：時(shí)間復(fù)雜度T(n)

30、按數(shù)量級(jí)遞增順序如下通常，把算法在執(zhí)行時(shí)所需的輔助空間的大小作為分析算法空間復(fù)雜通常，把算法在執(zhí)行時(shí)所需的輔助空間的大小作為分析算法空間復(fù)雜度的依據(jù)。度的依據(jù)?？臻g復(fù)雜度空間復(fù)雜度S(n)S(n)（1 1）定義（算法所需存儲(chǔ)空間的度量）定義（算法所需存儲(chǔ)空間的度量） S(n)=o(f(n) S(n)=o(f(n)常見的幾種空間復(fù)雜度有：常見的幾種空間復(fù)雜度有：O(1)O(1)，O(n)O(n)，O(nO(n2 2) )，O(nO(n3 3) )等。等。（2 2）說明）說明算法本身所占用的存儲(chǔ)空間算法本身所占用的存儲(chǔ)空間算法的輸入、輸出數(shù)據(jù)所占用的存儲(chǔ)空間算法的輸入、輸出數(shù)據(jù)所占用的存儲(chǔ)空間算法

31、運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間算法運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間 例例1.51.5下面算法實(shí)現(xiàn)求一個(gè)數(shù)組元素的累加和，計(jì)算該算法的時(shí)間下面算法實(shí)現(xiàn)求一個(gè)數(shù)組元素的累加和，計(jì)算該算法的時(shí)間復(fù)雜度。復(fù)雜度。int sum(int list,int n)int sum(int list,int n) / /* * 執(zhí)行次數(shù)執(zhí)行次數(shù) * */ /int sum=0.0; int sum=0.0; for (int i=0; in; i+ ) for (int i=0; in; i+ ) / /* * =n+1 =n+1 * */ /sum += listi; sum += listi; / /* * =n =n * */ /return sum; return sum; / /* * =1 =1 * */ / 時(shí)間復(fù)雜度為：時(shí)間復(fù)雜度為：(n+1)+n+1=2n+2(n+1)+n+1=2n+2，記為：，記為： O(n) O(n) 例例1.61.6下面過程實(shí)現(xiàn)兩矩陣乘法，計(jì)算該過程的時(shí)間復(fù)雜度。下面過程實(shí)現(xiàn)兩矩陣乘法，計(jì)算該過程的時(shí)間復(fù)雜度。 / /* *執(zhí)行次數(shù)執(zhí)行次數(shù)* */ /for(i=0; in; i+)for(i=0; in; i+) / /* * =n+1 =n+1 * */ / for(j=0; jn; j+) for(j=0; jn; j+) /