《專升本計算機(jī)導(dǎo)論》PPT課件.ppt

《《專升本計算機(jī)導(dǎo)論》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《專升本計算機(jī)導(dǎo)論》PPT課件.ppt（47頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、1,,知識點： 練習(xí)題： 模擬題：,2,本課程的主要研究內(nèi)容 什么是數(shù)據(jù)結(jié)構(gòu) 算法及其復(fù)雜性的概念 算法的表達(dá)與數(shù)據(jù)表示 抽象數(shù)據(jù)類型,第一章 引論,3,數(shù)據(jù)結(jié)構(gòu)的主要研究內(nèi)容,問題,,,建模,求精,數(shù)學(xué)模型,實現(xiàn),4,數(shù)據(jù)（data）,數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機(jī)中，被計算機(jī)程序識別和處理的符號的集合。 數(shù)值性數(shù)據(jù) 非數(shù)值性數(shù)據(jù),5,數(shù)據(jù)元素 (data element),數(shù)據(jù)的基本單位。在計算機(jī)程序中常作為一個整體進(jìn)行考慮和處理。 一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項(Data Item)組成。數(shù)據(jù)項是具有獨立含義的最小標(biāo)識單位。 數(shù)據(jù)元素又稱為元素、結(jié)點、記

2、錄。,6,數(shù)據(jù)對象 (data object),數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。 整數(shù)數(shù)據(jù)對象 N = 0, 1, 2, 學(xué)生數(shù)據(jù)對象,7,什么是數(shù)據(jù)結(jié)構(gòu),定義: 指某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關(guān)系。記為： Data_Structure = D, R 其中，D 是某一數(shù)據(jù)對象，R 是該對象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。,8,數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的存在(組織)形式,數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)； 數(shù)據(jù)元素及其關(guān)系在計算機(jī)存儲內(nèi)的表示，即數(shù)據(jù)的存儲(機(jī)內(nèi))表示； 數(shù)據(jù)的運算，即對數(shù)據(jù)元素施加的操作。,9,數(shù)據(jù)的邏輯結(jié)構(gòu),數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述

3、數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)； 數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)據(jù)模型； 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容無關(guān)； 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對存儲位置無關(guān)。,10,數(shù)據(jù)的邏輯結(jié)構(gòu)分類,線性結(jié)構(gòu) 線性表 非線性結(jié)構(gòu) 多維數(shù)組 廣義表 樹 圖（或網(wǎng)絡(luò)）,11,,,,,,,,,,,,,,,,,,,,,,,,,,,,線性結(jié)構(gòu),樹形結(jié)構(gòu),樹 二叉樹 二叉搜索樹,,,,,,,,,,,,,,,14,13,12,11,2,3,4,5,6,7,8,9,10,,,,,,,,,,,,,,,,,,,,,,,3,1,5,8,7,10,11,9,9,8,7,4,5,6,6,2,3,13,1,,,,

4、,,,,,,bin,dev,etc,lib,user,1,12,,,,,,,,,,,,堆結(jié)構(gòu),“最大”堆 “最小”堆,,12,,,,,,3,5,4,8,,,,7,11,10,2,,,,9,1,6,,,,,,,,,,,,,,,,,,4,,,,,,,10,12,11,5,1,2,3,6,9,8,7,13,,,,,圖結(jié)構(gòu) 網(wǎng)絡(luò)結(jié)構(gòu),,1,,,,,,,,,,,,2,5,6,4,3,,,,,,1,,,,,,,,,,,2,5,4,3,,6,11,33,18,14,6,6,5,16,19,21,14,數(shù)據(jù)的存儲結(jié)構(gòu),數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機(jī)語言的實現(xiàn)； 數(shù)據(jù)的存儲結(jié)構(gòu)依賴于計算機(jī)語言。 順序存

5、儲表示 鏈接存儲表示 索引存儲表示 散列存儲表示,,15,算法的概念,算法的定義：由若干條指令組成的一個有窮序列，這些指令為解決某一特定任務(wù)規(guī)定了一個運算序列 特性： 輸入 有0個或多個輸入 輸出 有一個或多個輸出(處理結(jié)果) 確定性 每步定義都是確切、無歧義的 有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束,16,程序與算法的區(qū)別,程序可以不滿足有窮性。,17,算法的性能標(biāo)準(zhǔn),正確性：要求算法能夠正確地執(zhí)行預(yù)先規(guī)定的功能和性能要求。這是最重要的標(biāo)準(zhǔn)，這要求算法的編寫者對問題有正確的理解，并正確地、無歧義地描述和利用某種編程語言正確地實現(xiàn)對算法的要求。 可使用性：要求算法能夠方便的使用。這個特性也叫用戶友好

6、性。為了便于用戶使用，要求該算法具有良好的界面，完備的用戶文檔。因此，算法的設(shè)計必須符合抽象數(shù)據(jù)類型和模塊化的要求，最好所有的輸入和輸出數(shù)據(jù)都通過參數(shù)表顯式地傳遞，少用變量或全局變量，每個算法只完成一個功能。,18,算法的性能標(biāo)準(zhǔn),可讀性：算法應(yīng)當(dāng)是可讀的。這是理解、測試和修改算法的需要。為了達(dá)到這一要求，算法的邏輯必須是清晰的、簡單的和結(jié)構(gòu)化的。所有的變量名、函數(shù)名的命名必須有實際含義、讓人見名知義。在算法中必須加入注釋，簡要說明算法的功能、輸入與輸出參數(shù)的使用規(guī)則、重要數(shù)據(jù)的作用、算法中各程序段完成的功能等。 效率：算法的效率是指算法執(zhí)行時計算機(jī)資源的消耗。,19,算法的性能標(biāo)準(zhǔn),健壯性：

7、要求在算法中加入對輸入?yún)?shù)、打開文件、讀文件記錄、子程序調(diào)用狀態(tài)進(jìn)行自動檢錯、報錯并通過與用戶對話來糾錯的功能，也叫容錯性或例外處理。一個完整的算法必須具有健壯性，能夠?qū)Σ缓侠淼臄?shù)據(jù)進(jìn)行檢查。,20,算法復(fù)雜性的概念,算法的復(fù)雜性：是運行算法所需要的計算機(jī)資源的量。 時間復(fù)雜性：需要的時間資源的量。 空間復(fù)雜性：需要的空間資源的量。 算法復(fù)雜性分析的目的是評價算法的效率，對算法的設(shè)計或選用具有重要的指導(dǎo)義意和實用價值。,21,算法復(fù)雜性的度量,度量算法復(fù)雜性的量應(yīng)能集中反映算法的效率, 而從運行該算法的實際計算機(jī)中抽象出來。即這個量只依賴算法要解決問題的規(guī)模和算法的輸入函數(shù)。 設(shè)：n - 問題

8、規(guī)模; I - 輸入函數(shù) C -算法復(fù)雜性, 應(yīng)表示為C(n, I)。 T(n, I) 時間復(fù)雜性 S(n,I) 空間復(fù)雜性,22,算法復(fù)雜性的度量,根據(jù)T(n, I) 的概念， 它是表示算法在一臺抽象的計算機(jī)上運行所需的時間。 設(shè)抽象的計算機(jī)所提供的元運算有k種，分別記為O1，O2，,Ok。又設(shè)執(zhí)行一次元運算所需的時間為t1，t2，,tk。對于給定的算法A，用到的元運算Oi的次數(shù)為ei, i=1,2, ,k。 則ei是n和I的函數(shù)，即ei= ei （n,I)。,T(n, I) =,23,算法復(fù)雜性的度量,Tmin(n, I) =,最好情況下的時間復(fù)雜性,min T (n, I)

9、 I Dn,=,=T(n,I*),24,算法復(fù)雜性的度量,Tmax(n, I) =,最壞情況下的時間復(fù)雜性,max T (n, I) I Dn,=,=T(n,I),,,25,算法復(fù)雜性的度量,Tavg(n, I) =,平均情況下的時間復(fù)雜性,=,,I Dn,Dn是規(guī)模為n的合法輸入的集合。,26,算法復(fù)雜性的度量(事例),例: 設(shè)變量a、b、c、d中各含一個整數(shù)。求a、b、c中的最大值與d的乘積。,算法max1: void max1(int a, b, c, d) int x; a*=d; b*=d; c*=d; if (ab) x=a; else x=b;

10、 if (cx) x=c; printf(“%dn”,x) ,算法max2: void max2(int a, b, c, d) int x; if (ab) x=a; else x=b; if (cx) x=c; x*=d; printf(“%dn”,x) ,27,算法復(fù)雜性的度量(事例),設(shè)輸入為：a=1、b=2、c=3、d=4。兩個算法在給定輸入條件下的計算量,若以賦值語句為標(biāo)準(zhǔn)操作，算法max1和max2在輸入（3，2，1，4）下的計算量為4和2。最壞情況下的時間復(fù)雜性分別為5和3。,28,算法復(fù)雜性的度量(事例),例

11、（算法復(fù)雜性是問題規(guī)模的函數(shù)）：矩陣乘法,void matrimlt(int Ann, Bnn, Cnn) /* 求n階矩陣A，B的乘積C*/ for (i=0;i

12、，則稱,是T（n）當(dāng)n 時的漸近性態(tài)，或稱,是算法A當(dāng)n 時的漸近復(fù)雜性,30,算法復(fù)雜性的漸近性態(tài),如當(dāng)T（n）=3n2+4nlogn+7時，,T（n）-,,T（n）,=0,的一個答案是3n2,4nlogn+7,,3n2+4nlogn+7,=,為了簡化分析，我們假設(shè)算法中用到的所有不同的元運算各執(zhí)行一次所需的時間都是一個單位時間。,只要考慮當(dāng)問題規(guī)模充分大時，算法復(fù)雜性在漸近意義下的階。,31,算法復(fù)雜性的漸近性態(tài),設(shè)： f(n)和g(n)是定義在正數(shù)集上的正函數(shù)。 如果存在正的常數(shù)c和自然數(shù)n0，使得當(dāng)n n0時有f(n) cg(n)，則稱函數(shù)f(n)當(dāng)n充分大時上有界，且g(n)是它的一

13、個上界，記為f(n)=O(g(n))。這時還說f(n)的階不高于g(n)的階。 例子： 1、 因為當(dāng)n1時，有3n 4n，則 有 3n=O(n)。 2、因為當(dāng)n1時，有n+1024 1025n，則 有 n+1024 =O(n)。,32,算法復(fù)雜性的漸近性態(tài),例子： 3、 因為當(dāng)n10時，有2n2+11n-10 3n2 ，則 有 2n2+11n-10 =O(n2)。 4、因為當(dāng)n1時，有n2 n3，則 有 n2=O(n3)。 5、反例： n3 O(n2)。因為若不然，則存在正的常數(shù)c和自然數(shù)n0，使得當(dāng)n n0有n3 cn2, 即

14、n c。顯然， 當(dāng)取n=max(n0, c+1 )時，不等式n3 cn2不成立，故n3 O(n2)。,33,算法復(fù)雜性的漸近性態(tài),按符號O的定義，有以下運算規(guī)則： 1. O(f)+O(g)=O(max(f, g)); 2. O(f)+O(g)=O(f+ g); 3. O(f) O(g)=O(fg); 4. 如果g(n)=O(f(n)), O(f)+O(g)=O(f); 5. O(cf(n))=O(f(n)), 其中c是一個正的常數(shù)； 6. f= O(f),34,算法復(fù)雜性的漸近性態(tài),規(guī)則1的證明： 設(shè)F(n)= O(f),按符號O的定義，則存在正的常數(shù)c1和自然數(shù)n1，使得當(dāng)n n1時有F(n

15、) c1 f(n)。再設(shè)G(n)= O(g), 則存在正的常數(shù)c2和自然數(shù)n2，使得當(dāng)n n2時有G(n) c2 g(n)。 令c3=max(c1, c2), n3=max(n1, n2), h(n)=max(f, g), 對于所有的n n3 , 有 G(n) c2g(n) c2 h(n) c3 h(n),35,算法復(fù)雜性的漸近性態(tài),O(f)+O(g)=F(n)+G(n) c3 h(n)+ c3 h(n)=2 c3 h(n) =O(h)=O(max(f, g)),,36,算法復(fù)雜性的漸近性態(tài),符號 : 如果存在正的常數(shù)c和自然數(shù)n0，使得當(dāng)n n0時有f(n) cg(n)，則

16、稱函數(shù)f(n)當(dāng)n充分大時下有界，且g(n)是它的一個下界，記為f(n)= (g(n))。這時還說f(n)的階不低于g(n)的階。,上界的階越低, 算法復(fù)雜評估的越準(zhǔn)確; 下界的階越高算法復(fù)雜評估的越準(zhǔn)確 。,37,算法復(fù)雜性的漸近性態(tài),問題的下界或某類算法的下界 : 對于一個問題和任意給定的充分大的規(guī)模n，下界在該問題的所有算法或某類算法的復(fù)雜性中取值，這時得到的下界稱之為：問題的下界或某類算法的下界 。 常與O配合以證明某問題的一個特定算法是該問題的最優(yōu)算法或該問題的某算法類中的最優(yōu)算法。,38,算法復(fù)雜性的漸近性態(tài),符號 ：定義f(n)= (g(n))當(dāng)且僅當(dāng)f(n)=O(g(n))且f

17、(n)= (g(n))。這時f(n)與g(n)同階。,如果對于任意給定的0，都存在正整數(shù)n0，使得當(dāng)n n0時有f(n) /g(n)< ,稱函數(shù)f(n)當(dāng)n充分大時的階比g(n)低, 記為f(n)=o(g(n)) 例: 4nlogn+7=o(3n2+ 4nlogn+7),39,構(gòu)造數(shù)據(jù)類型由基本數(shù)據(jù)類型或構(gòu)造數(shù)據(jù)類型組合而成。 構(gòu)造數(shù)據(jù)類型由不同成分類型構(gòu)成。 基本數(shù)據(jù)類型可以看作是計算機(jī)中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過它是從編程者的角度來使用的。 數(shù)據(jù)類型是模板，必須定義屬于某種數(shù)據(jù)類型的變量，才能參加運算。,40,抽象數(shù)據(jù)類型 (ADTs: Abstract Data Ty

18、pes),為什么要引入抽象數(shù)據(jù)類型 按照頂向下逐步求精的原則, 在探索運算步驟時,首先應(yīng)考慮算法的頂層運算步驟, 然后再考慮底層運算步驟. 頂層運算步驟: 指定義在數(shù)據(jù)模型上的運算步驟; 底層運算步驟:頂層抽象的運算的具體實現(xiàn). 包括數(shù)據(jù)模型的具體表示和定義在該數(shù)據(jù)模型上的運算的具體實現(xiàn).,數(shù)據(jù)類型與抽象數(shù)據(jù)類型,41,抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types),為什么要引入抽象數(shù)據(jù)類型 為了將頂層算法與底層算法隔開, 使二者在設(shè)計時不會相互牽制, 相互影響, 必須對二者的接口進(jìn)行一次抽象.讓底層只通過這個接口為頂層服務(wù), 頂層也只通過這個接口調(diào)用底層的運算. 這個接

19、口就是抽象數(shù)據(jù)類型.,42,抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types),由數(shù)據(jù)模型及定義在該數(shù)據(jù)模型上的一組相關(guān)的運算構(gòu)成. 抽象數(shù)據(jù)類型的特征是使用于實現(xiàn)分離, 實行封裝與信息隱蔽. 數(shù)據(jù)模型及定義在該數(shù)據(jù)模型上的運算存在密不可分的聯(lián)系.一方面,數(shù)據(jù)模型上的運算依賴于數(shù)據(jù)模型的具體表示;另一方面,數(shù)據(jù)模型的具體表示反過來又依賴于數(shù)據(jù)模型上的運算;,43,抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types),定義抽象數(shù)據(jù)類型 就是約定抽象數(shù)據(jù)類型的名字, 同時, 約定在該類型上定義的各個運算的名字, 明確各個運算的參數(shù), 以及運算的功能.,44,抽象數(shù)

20、據(jù)類型 (ADTs: Abstract Data Types),定義抽象數(shù)據(jù)類型 , 算法底層的設(shè)計任務(wù)為: 1. 對于每一個抽象數(shù)據(jù)類型 賦予其具體的構(gòu)造數(shù)據(jù)類型, 即給每一個抽象數(shù)據(jù)類型 賦予其具體的數(shù)據(jù)結(jié)構(gòu); 2. 對每個運算賦予其具體的運算內(nèi)容, 即賦予其具體的函數(shù). 算法底層的設(shè)計就是數(shù)據(jù)結(jié)構(gòu)的設(shè)計和函數(shù)的設(shè)計,45,抽象數(shù)據(jù)類型,,,,,,,,,,,,,查找 登錄 刪除 修改,,,,,,,,,,,,,,,符 號 表,,,,,46,自然數(shù)的抽象數(shù)據(jù)類型定義,ADT NaturalNumber is objects: 一個整數(shù)的有序子集合,它開始于0, 結(jié)束于機(jī)器能表示的最大整數(shù)(M

21、axInt)。 Function: 對于所有的 x, y NaturalNumber; False, True Boolean, +、-、<、==、=等都是可用的服務(wù)。 Zero( ) : NaturalNumber 返回自然數(shù)0,,47,IsZero(x) : if (x==0) 返回True Boolean else 返回False Add (x, y) : if (x+y<=MaxInt)返回 x+y NaturalNumber else 返回MaxInt Subtract (x, y) : if (x < y) 返回 0 NaturalNumber else 返回 x - y Equal (x, y) : if (x==y) 返回True Boolean else 返回 False Successor (x) : if (x==MaxInt) 返回 x NaturalNumber else 返回 x+1 end NaturalNumber,,