數(shù)據(jù)結(jié)構(gòu)地球信息科學(xué)與技術(shù)系

1、數(shù)據(jù)結(jié)構(gòu)梁音地球信息科學(xué)與技術(shù)系地球物理與空間信息學(xué)院緒 論一、教材及相應(yīng)的參考書二、為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？三、什么是數(shù)據(jù)結(jié)構(gòu)？四、什么是算法？五、算法的設(shè)計(jì)要求六、算法的分析一、教材及參考書教材：嚴(yán)蔚敏、吳偉民編著，數(shù)據(jù)結(jié)構(gòu)(C語言版)，清華大學(xué)出版社。參考書：Donald E. Knuth，The Arts of Computer Programming (Volume I、II、and III) ，Addison Wesley。Donald E. Knuth是當(dāng)今計(jì)算機(jī)業(yè)界的大牛，圖靈獎(jiǎng)得主。他所寫的這七卷著作是當(dāng)今算法分析領(lǐng)域最權(quán)威的著作。一、教材及參考書Thomas H. Corme

2、n、 Charles E. Leiserson、 Ronald L. Rivest、Clifford Stein，Introduction to Algorithms，The MIT Press。1996年版只有前面的三位作者。2002年版的增加了一位作者(Clifford Stein)。一、教材及參考書Mark Allen Weiss, Data Structure and Algorithm Analysis in C (Second Edition), Addison Wesley。二、為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)產(chǎn)業(yè)的飛速發(fā)展，應(yīng)用領(lǐng)域的迅速擴(kuò)展。突破傳統(tǒng)的數(shù)值計(jì)算，處理的對(duì)象更多的涉及

3、到字符、表格和圖像等非數(shù)值元素。數(shù)據(jù)結(jié)構(gòu)是前人在思考問題時(shí)想出的解決方法。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)可以提高程序設(shè)計(jì)的水平。三、什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的組織形式。相互之間存在的一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。集合線性結(jié)構(gòu)樹狀結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)四、什么是算法對(duì)特定問題求解步驟的一種描述。指令的有限序列。算法的五個(gè)重要特性：有窮性確定性可行性輸入輸出五、算法的設(shè)計(jì)要求正確性：算法應(yīng)當(dāng)滿足具體問題的需求可讀性：算法主要是為了人的閱讀與交流健壯性：當(dāng)輸入數(shù)據(jù)非法時(shí)，算法應(yīng)能適當(dāng)?shù)淖鞒龇磻?yīng)或進(jìn)行處理效率與低存儲(chǔ)量需求：效率指的是算法的執(zhí)行時(shí)間；存儲(chǔ)量需求指算法執(zhí)行過程中所需要的最大存儲(chǔ)空間六、算法的分析6.1算法效率的度量

4、1)事后統(tǒng)計(jì)的方法：利用計(jì)算機(jī)的內(nèi)部計(jì)時(shí)功能，精確統(tǒng)計(jì)算法執(zhí)行的時(shí)間到毫秒級(jí)。不足：必須先運(yùn)行依據(jù)算法編制的程序統(tǒng)計(jì)的結(jié)果依賴于計(jì)算機(jī)的硬軟件環(huán)境六、算法的分析6.1算法效率的度量2) 事前分析估計(jì)的方法：從算法中選取一種對(duì)于所研究的問題來說是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。這樣就避免了與計(jì)算機(jī)硬軟件有關(guān)的諸因素對(duì)算法執(zhí)行時(shí)間度量上的不準(zhǔn)確六、算法的分析語句的頻度：指的是該語句重復(fù)執(zhí)行的次數(shù)(a) x+; a = 0;(b) for (i=1;i=n;i+) x+; s+=x;(c) for (j=1;j=n;j+) for(k=1;k=n0時(shí)，總有|T(n)|

5、 1時(shí)，f(x) g(x)六、算法的分析算法的漸進(jìn)時(shí)間復(fù)雜度：對(duì)于1，n，n2，n3，2n，3n，nn。1 = O(n)，n = O(n2)， n2 = O(n3)，n3 = O(2n)， 2n = O(3n)， 3n = O(nn)。O(1)O(n)O(n2)O(n3)O(2n)O(3n) 1時(shí)，f (x) 0.5g(x)，所以， f (x) = ( g(x)。表示f (x) g(x)為下界。如果當(dāng)x 1時(shí)， g(x) f(x) 2g(x)。則，f(x) = (g(x) 表示f(x)的變化可以始終限制在某個(gè)以a*g(x)為上界，以b*g(x)為下界的條帶內(nèi)。六、算法的分析六、算法的分析當(dāng)n比較小時(shí)， (logn)并不一定就比 (2n)變化快，這時(shí)的常數(shù)系數(shù)將起到一定作用。但是當(dāng)n很大時(shí)，對(duì)于同一個(gè)問題而言，時(shí)間復(fù)雜度為 (logn)的算法其效率要高于時(shí)間復(fù)雜度為 (2