01數(shù)據(jù)結(jié)構(gòu)實(shí)用概念專題講座.doc

1、01-數(shù)據(jù)構(gòu)造實(shí)用概念專題講座數(shù)據(jù)構(gòu)造根本概念專題講座 數(shù)據(jù)構(gòu)造實(shí)用概念 疑惑 1、我學(xué)完了C語言，可是如今感覺還是寫不出代碼。 2、為什么會(huì)有各種各樣的程序存在？ 3、程序的本質(zhì)是什么？ 程序是為了詳細(xì)問題而存在的 程序需要圍繞問題的解決進(jìn)展設(shè)計(jì) 同一個(gè)問題可以有多種解決方案 如何追求程序的“性價(jià)比”？ 是否有可量化的方法判別程序的好壞？ 數(shù)據(jù)構(gòu)造起 計(jì)算機(jī)從解決數(shù)值計(jì)算問題到解決生活中的問題 現(xiàn)實(shí)生活中的問題涉及不同個(gè)體間的復(fù)雜聯(lián)絡(luò) 需要在計(jì)算機(jī)程序中描繪生活中個(gè)體間的聯(lián)絡(luò) 數(shù)據(jù)構(gòu)造主要研究非數(shù)值計(jì)算程序問題中的操作對(duì)象以及它們之間的關(guān)系 不是研究復(fù)雜的算法 數(shù)據(jù)構(gòu)造中的根本概念 數(shù)據(jù) 程

2、序的操作對(duì)象，用于描繪客觀事物 數(shù)據(jù)的特點(diǎn)： 可以輸入到計(jì)算機(jī) 可以被計(jì)算機(jī)程序處理 數(shù)據(jù)是一個(gè)抽象的概念，將其進(jìn)展分類后得到程序設(shè)計(jì)語言中的類型。如：int，float，char等等 數(shù)據(jù)元素：組成數(shù)據(jù)的根本單位 數(shù)據(jù)項(xiàng)：一個(gè)數(shù)據(jù)元素由假設(shè)干數(shù)據(jù)項(xiàng)組成 數(shù)據(jù)對(duì)象 性質(zhì)一樣的數(shù)據(jù)元素的集合 /王保明，提醒你，來自構(gòu)造體課堂代碼 /聲明一個(gè)構(gòu)造體類型 struct _MyTeacher /一種數(shù)據(jù)類型 char name32; char tile32; int age; char addr128; ; int main21 struct _MyTeacher t1; /數(shù)據(jù)元素 struct _

3、MyTeacher tArray30; /數(shù)據(jù)對(duì)象 memset(&t1, 0, sizeof(t1); strcpy(, “name“); /數(shù)據(jù)項(xiàng) strcpy(t1.addr, “addr“); /數(shù)據(jù)項(xiàng) strcpy(t1.tile, “addr“); /數(shù)據(jù)項(xiàng) t1.age = 1; 數(shù)據(jù)元素之間不是獨(dú)立的，存在特定的關(guān)系，這些關(guān)系即構(gòu)造 數(shù)據(jù)構(gòu)造指數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的關(guān)系 如：數(shù)組中各個(gè)元素之間存在固定的線性關(guān)系 編寫一個(gè)“好”的程序之前，必須分析p 待處理問題中各個(gè)對(duì)象的特性，以及對(duì)象之間的關(guān)系。 根本概念總結(jié)： 數(shù)據(jù)的邏輯構(gòu)造 指數(shù)據(jù)元素之間的邏輯關(guān)系

4、。即從邏輯關(guān)系上描繪數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。邏輯構(gòu)造可細(xì)分為4類： 數(shù)據(jù)的物理構(gòu)造 數(shù)據(jù)的運(yùn)算 算法 算法概念 算法是特定問題求解步驟的描繪 在計(jì)算機(jī)中表現(xiàn)為指令的有限序列 算法是獨(dú)立存在的一種解決問題的方法和思想。 對(duì)于算法而言，語言并不重要，重要的是思想。 算法和數(shù)據(jù)構(gòu)造區(qū)別 數(shù)據(jù)構(gòu)造只是靜態(tài)的描繪了數(shù)據(jù)元素之間的關(guān)系 高效的程序需要在數(shù)據(jù)構(gòu)造的根底上設(shè)計(jì)和選擇算法 =è程序=數(shù)據(jù)構(gòu)造+算法 總結(jié)： 算法是為理解決實(shí)際問題而設(shè)計(jì)的 數(shù)據(jù)構(gòu)造是算法需要處理的問題載體 數(shù)據(jù)構(gòu)造與算法相輔相成 算法特性 輸入 算法具有0個(gè)或多個(gè)輸入 輸出 算法至少有1個(gè)或多個(gè)輸出

5、有窮性 算法在有限的步驟之后會(huì)自動(dòng)完畢而不會(huì)無限循環(huán) 確定性 算法中的每一步都有確定的含義，不會(huì)出現(xiàn)二義性 可行性 算法的每一步都是可行的 算法效率的度量 1、事后統(tǒng)計(jì)法 比擬不同算法對(duì)同一組輸入數(shù)據(jù)的運(yùn)行處理時(shí)間 缺陷 為了獲得不同算法的運(yùn)行時(shí)間必須編寫相應(yīng)程序 運(yùn)行時(shí)間嚴(yán)重依賴硬件以及運(yùn)行時(shí)的環(huán)境因素 算法的測試數(shù)據(jù)的選取相當(dāng)困難 事后統(tǒng)計(jì)法雖然直觀，但是施行困難且缺陷多 算法效率的度量 事前分析p 估算 根據(jù)統(tǒng)計(jì)的方法對(duì)算法效率進(jìn)展估算 影響算法效率的主要因素 算法采用的策略和方法 問題的輸入規(guī)模 編譯器所產(chǎn)生的代碼 計(jì)算機(jī)執(zhí)行速度 long sum1(int n) long ret =

6、 0; int* array = (int*)malloc(n * sizeof(int); int i = 0; for(i=0; i<n; i+) arrayi = i + 1; for(i=0; i<n; i+) ret += arrayi; free(array); return ret; long sum2(int n) long ret = 0; int i = 0; for(i=1; i<=n; i+) ret += i; return ret; long sum3(int n) long ret = 0; if( n > 0 )

7、ret = (1 + n) * n / 2; return ret; int main printf(“%dn“, sum1(100); printf(“%dn“, sum2(100); printf(“%dn“, sum3(100); return 0; int func(int a, int len) int i = 0; int j = 0; int s = 0; for(i=0; i<len; i+) n for(j=0; j<len; j+) n s += i*j; /n*n return s; /n*n 注意1：判斷一個(gè)算法的效率時(shí)，往往只需要關(guān)注操作數(shù)

8、量的最高次項(xiàng)，其它次要項(xiàng)和常數(shù)項(xiàng)可以忽略。 注意2：在沒有特殊說明時(shí)，我們所分析p 的算法的時(shí)間復(fù)雜度都是指最壞時(shí)間復(fù)雜度。 2、大O表示法 算法效率嚴(yán)重依賴于操作(Operation)數(shù)量 在判斷時(shí)首先關(guān)注操作數(shù)量的最高次項(xiàng) 操作數(shù)量的估算可以作為時(shí)間復(fù)雜度的估算 O(5) = O(1) O(2n + 1) = O(2n) = O(n) O(n2+ n + 1) = O(n2) O(3n3+1) = O(3n3) = O(n3) 常見時(shí)間復(fù)雜度 關(guān)系 3、算法的空間復(fù)雜度 算法的空間復(fù)雜度通過計(jì)算算法的存儲(chǔ)空間實(shí)現(xiàn) S(n) = O(f(n) 其中，n為問題規(guī)模，f(n)為在問題規(guī)模為nn時(shí)

9、所占用存儲(chǔ)空間的函數(shù) 大O表示法同樣適用于算法的空間復(fù)雜度 當(dāng)算法執(zhí)行時(shí)所需要的空間是常數(shù)時(shí)，空間復(fù)雜度為O(1) 空間與時(shí)間的策略 多數(shù)情況下，算法執(zhí)行時(shí)所用的時(shí)間更令人關(guān)注 假如有必要，可以通過增加空間復(fù)雜度來降低時(shí)間復(fù)雜度 同理，也可以通過增加時(shí)間復(fù)雜度來降低空間復(fù)雜度 練習(xí)1：分析p sum1 sum2 sum3函數(shù)的空間復(fù)雜度 O(4n+12) O(8)=O(1) O(4)=O(1) 總結(jié)：實(shí)現(xiàn)算法時(shí)，需要分析p 詳細(xì)問題，對(duì)執(zhí)行時(shí)間和空間的要求。 練習(xí)2：時(shí)間換空間 /* 問題： 666 在一個(gè)由自然數(shù)1-1000中某些數(shù)字所組成的數(shù)組中，每個(gè)數(shù)字可能出現(xiàn)零次或者屢次。 設(shè)計(jì)一個(gè)算法，找出出現(xiàn)次數(shù)最多的數(shù)字。 */ 方法1： 排序，然后找出出現(xiàn)次數(shù)最多的數(shù)字 方法2： void search(int a, int len) int sp1000 = 0; int i = 0; int max = 0; for(i=0; i<len; i+) int index = ai - 1; spindex+; for(i=0; i<1000; i+) if( max < spi ) max = spi; for(i=0; i<1000; i