《《專(zhuān)升本計(jì)算機(jī)導(dǎo)論》PPT課件.ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《《專(zhuān)升本計(jì)算機(jī)導(dǎo)論》PPT課件.ppt（47頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、1,,知識(shí)點(diǎn)： 練習(xí)題： 模擬題：,2,本課程的主要研究?jī)?nèi)容 什么是數(shù)據(jù)結(jié)構(gòu) 算法及其復(fù)雜性的概念 算法的表達(dá)與數(shù)據(jù)表示 抽象數(shù)據(jù)類(lèi)型,第一章 引論,3,數(shù)據(jù)結(jié)構(gòu)的主要研究?jī)?nèi)容,問(wèn)題,,,建模,求精,數(shù)學(xué)模型,實(shí)現(xiàn),4,數(shù)據(jù)（data）,數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。 數(shù)值性數(shù)據(jù) 非數(shù)值性數(shù)據(jù),5,數(shù)據(jù)元素 (data element),數(shù)據(jù)的基本單位。在計(jì)算機(jī)程序中常作為一個(gè)整體進(jìn)行考慮和處理。 一個(gè)數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng)(Data Item)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。 數(shù)據(jù)元素又稱(chēng)為元素、結(jié)點(diǎn)、記
2、錄。,6,數(shù)據(jù)對(duì)象 (data object),數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。 整數(shù)數(shù)據(jù)對(duì)象 N = 0, 1, 2, 學(xué)生數(shù)據(jù)對(duì)象,7,什么是數(shù)據(jù)結(jié)構(gòu),定義: 指某一數(shù)據(jù)對(duì)象及該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系。記為： Data_Structure = D, R 其中，D 是某一數(shù)據(jù)對(duì)象，R 是該對(duì)象中所有數(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ì)算機(jī)存儲(chǔ)內(nèi)的表示，即數(shù)據(jù)的存儲(chǔ)(機(jī)內(nèi))表示； 數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)元素施加的操作。,9,數(shù)據(jù)的邏輯結(jié)構(gòu),數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述
3、數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)； 數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)據(jù)模型； 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容無(wú)關(guān)； 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對(duì)存儲(chǔ)位置無(wú)關(guān)。,10,數(shù)據(jù)的邏輯結(jié)構(gòu)分類(lèi),線(xiàn)性結(jié)構(gòu) 線(xiàn)性表 非線(xiàn)性結(jié)構(gòu) 多維數(shù)組 廣義表 樹(shù) 圖（或網(wǎng)絡(luò)）,11,,,,,,,,,,,,,,,,,,,,,,,,,,,,線(xiàn)性結(jié)構(gòu),樹(shù)形結(jié)構(gòu),樹(shù) 二叉樹(shù) 二叉搜索樹(shù),,,,,,,,,,,,,,,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ù)的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)； 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)依賴(lài)于計(jì)算機(jī)語(yǔ)言。 順序存
5、儲(chǔ)表示 鏈接存儲(chǔ)表示 索引存儲(chǔ)表示 散列存儲(chǔ)表示,,15,算法的概念,算法的定義：由若干條指令組成的一個(gè)有窮序列，這些指令為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列 特性： 輸入 有0個(gè)或多個(gè)輸入 輸出 有一個(gè)或多個(gè)輸出(處理結(jié)果) 確定性 每步定義都是確切、無(wú)歧義的 有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束,16,程序與算法的區(qū)別,程序可以不滿(mǎn)足有窮性。,17,算法的性能標(biāo)準(zhǔn),正確性：要求算法能夠正確地執(zhí)行預(yù)先規(guī)定的功能和性能要求。這是最重要的標(biāo)準(zhǔn)，這要求算法的編寫(xiě)者對(duì)問(wèn)題有正確的理解，并正確地、無(wú)歧義地描述和利用某種編程語(yǔ)言正確地實(shí)現(xiàn)對(duì)算法的要求。 可使用性：要求算法能夠方便的使用。這個(gè)特性也叫用戶(hù)友好
6、性。為了便于用戶(hù)使用，要求該算法具有良好的界面，完備的用戶(hù)文檔。因此，算法的設(shè)計(jì)必須符合抽象數(shù)據(jù)類(lèi)型和模塊化的要求，最好所有的輸入和輸出數(shù)據(jù)都通過(guò)參數(shù)表顯式地傳遞，少用變量或全局變量，每個(gè)算法只完成一個(gè)功能。,18,算法的性能標(biāo)準(zhǔn),可讀性：算法應(yīng)當(dāng)是可讀的。這是理解、測(cè)試和修改算法的需要。為了達(dá)到這一要求，算法的邏輯必須是清晰的、簡(jiǎn)單的和結(jié)構(gòu)化的。所有的變量名、函數(shù)名的命名必須有實(shí)際含義、讓人見(jiàn)名知義。在算法中必須加入注釋?zhuān)?jiǎn)要說(shuō)明算法的功能、輸入與輸出參數(shù)的使用規(guī)則、重要數(shù)據(jù)的作用、算法中各程序段完成的功能等。 效率：算法的效率是指算法執(zhí)行時(shí)計(jì)算機(jī)資源的消耗。,19,算法的性能標(biāo)準(zhǔn),健壯性：
7、要求在算法中加入對(duì)輸入?yún)?shù)、打開(kāi)文件、讀文件記錄、子程序調(diào)用狀態(tài)進(jìn)行自動(dòng)檢錯(cuò)、報(bào)錯(cuò)并通過(guò)與用戶(hù)對(duì)話(huà)來(lái)糾錯(cuò)的功能，也叫容錯(cuò)性或例外處理。一個(gè)完整的算法必須具有健壯性，能夠?qū)Σ缓侠淼臄?shù)據(jù)進(jìn)行檢查。,20,算法復(fù)雜性的概念,算法的復(fù)雜性：是運(yùn)行算法所需要的計(jì)算機(jī)資源的量。 時(shí)間復(fù)雜性：需要的時(shí)間資源的量。 空間復(fù)雜性：需要的空間資源的量。 算法復(fù)雜性分析的目的是評(píng)價(jià)算法的效率，對(duì)算法的設(shè)計(jì)或選用具有重要的指導(dǎo)義意和實(shí)用價(jià)值。,21,算法復(fù)雜性的度量,度量算法復(fù)雜性的量應(yīng)能集中反映算法的效率, 而從運(yùn)行該算法的實(shí)際計(jì)算機(jī)中抽象出來(lái)。即這個(gè)量只依賴(lài)算法要解決問(wèn)題的規(guī)模和算法的輸入函數(shù)。 設(shè)：n - 問(wèn)題
8、規(guī)模; I - 輸入函數(shù) C -算法復(fù)雜性, 應(yīng)表示為C(n, I)。 T(n, I) 時(shí)間復(fù)雜性 S(n,I) 空間復(fù)雜性,22,算法復(fù)雜性的度量,根據(jù)T(n, I) 的概念， 它是表示算法在一臺(tái)抽象的計(jì)算機(jī)上運(yùn)行所需的時(shí)間。 設(shè)抽象的計(jì)算機(jī)所提供的元運(yùn)算有k種，分別記為O1，O2，,Ok。又設(shè)執(zhí)行一次元運(yùn)算所需的時(shí)間為t1，t2，,tk。對(duì)于給定的算法A，用到的元運(yùn)算Oi的次數(shù)為ei, i=1,2, ,k。 則ei是n和I的函數(shù)，即ei= ei （n,I)。,T(n, I) =,23,算法復(fù)雜性的度量,Tmin(n, I) =,最好情況下的時(shí)間復(fù)雜性,min T (n, I)
9、 I Dn,=,=T(n,I*),24,算法復(fù)雜性的度量,Tmax(n, I) =,最壞情況下的時(shí)間復(fù)雜性,max T (n, I) I Dn,=,=T(n,I),,,25,算法復(fù)雜性的度量,Tavg(n, I) =,平均情況下的時(shí)間復(fù)雜性,=,,I Dn,Dn是規(guī)模為n的合法輸入的集合。,26,算法復(fù)雜性的度量(事例),例: 設(shè)變量a、b、c、d中各含一個(gè)整數(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。兩個(gè)算法在給定輸入條件下的計(jì)算量,若以賦值語(yǔ)句為標(biāo)準(zhǔn)操作，算法max1和max2在輸入（3，2，1，4）下的計(jì)算量為4和2。最壞情況下的時(shí)間復(fù)雜性分別為5和3。,28,算法復(fù)雜性的度量(事例),例
11、（算法復(fù)雜性是問(wèn)題規(guī)模的函數(shù)）：矩陣乘法,void matrimlt(int Ann, Bnn, Cnn) /* 求n階矩陣A，B的乘積C*/ for (i=0;i
12、，則稱(chēng),是T（n）當(dāng)n 時(shí)的漸近性態(tài)，或稱(chēng),是算法A當(dāng)n 時(shí)的漸近復(fù)雜性,30,算法復(fù)雜性的漸近性態(tài),如當(dāng)T（n）=3n2+4nlogn+7時(shí)，,T（n）-,,T（n）,=0,的一個(gè)答案是3n2,4nlogn+7,,3n2+4nlogn+7,=,為了簡(jiǎn)化分析，我們假設(shè)算法中用到的所有不同的元運(yùn)算各執(zhí)行一次所需的時(shí)間都是一個(gè)單位時(shí)間。,只要考慮當(dāng)問(wèn)題規(guī)模充分大時(shí)，算法復(fù)雜性在漸近意義下的階。,31,算法復(fù)雜性的漸近性態(tài),設(shè)： f(n)和g(n)是定義在正數(shù)集上的正函數(shù)。 如果存在正的常數(shù)c和自然數(shù)n0，使得當(dāng)n n0時(shí)有f(n) cg(n)，則稱(chēng)函數(shù)f(n)當(dāng)n充分大時(shí)上有界，且g(n)是它的一
13、個(gè)上界，記為f(n)=O(g(n))。這時(shí)還說(shuō)f(n)的階不高于g(n)的階。 例子： 1、 因?yàn)楫?dāng)n1時(shí)，有3n 4n，則 有 3n=O(n)。 2、因?yàn)楫?dāng)n1時(shí)，有n+1024 1025n，則 有 n+1024 =O(n)。,32,算法復(fù)雜性的漸近性態(tài),例子： 3、 因?yàn)楫?dāng)n10時(shí)，有2n2+11n-10 3n2 ，則 有 2n2+11n-10 =O(n2)。 4、因?yàn)楫?dāng)n1時(shí)，有n2 n3，則 有 n2=O(n3)。 5、反例： n3 O(n2)。因?yàn)槿舨蝗?，則存在正的常數(shù)c和自然數(shù)n0，使得當(dāng)n n0有n3 cn2, 即
14、n c。顯然， 當(dāng)取n=max(n0, c+1 )時(shí)，不等式n3 cn2不成立，故n3 O(n2)。,33,算法復(fù)雜性的漸近性態(tài),按符號(hào)O的定義，有以下運(yùn)算規(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是一個(gè)正的常數(shù)； 6. f= O(f),34,算法復(fù)雜性的漸近性態(tài),規(guī)則1的證明： 設(shè)F(n)= O(f),按符號(hào)O的定義，則存在正的常數(shù)c1和自然數(shù)n1，使得當(dāng)n n1時(shí)有F(n
15、) c1 f(n)。再設(shè)G(n)= O(g), 則存在正的常數(shù)c2和自然數(shù)n2，使得當(dāng)n n2時(shí)有G(n) c2 g(n)。 令c3=max(c1, c2), n3=max(n1, n2), h(n)=max(f, g), 對(duì)于所有的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),符號(hào) : 如果存在正的常數(shù)c和自然數(shù)n0，使得當(dāng)n n0時(shí)有f(n) cg(n)，則
16、稱(chēng)函數(shù)f(n)當(dāng)n充分大時(shí)下有界，且g(n)是它的一個(gè)下界，記為f(n)= (g(n))。這時(shí)還說(shuō)f(n)的階不低于g(n)的階。,上界的階越低, 算法復(fù)雜評(píng)估的越準(zhǔn)確; 下界的階越高算法復(fù)雜評(píng)估的越準(zhǔn)確 。,37,算法復(fù)雜性的漸近性態(tài),問(wèn)題的下界或某類(lèi)算法的下界 : 對(duì)于一個(gè)問(wèn)題和任意給定的充分大的規(guī)模n，下界在該問(wèn)題的所有算法或某類(lèi)算法的復(fù)雜性中取值，這時(shí)得到的下界稱(chēng)之為：?jiǎn)栴}的下界或某類(lèi)算法的下界 。 常與O配合以證明某問(wèn)題的一個(gè)特定算法是該問(wèn)題的最優(yōu)算法或該問(wèn)題的某算法類(lèi)中的最優(yōu)算法。,38,算法復(fù)雜性的漸近性態(tài),符號(hào) ：定義f(n)= (g(n))當(dāng)且僅當(dāng)f(n)=O(g(n))且f
17、(n)= (g(n))。這時(shí)f(n)與g(n)同階。,如果對(duì)于任意給定的0，都存在正整數(shù)n0，使得當(dāng)n n0時(shí)有f(n) /g(n)< ,稱(chēng)函數(shù)f(n)當(dāng)n充分大時(shí)的階比g(n)低, 記為f(n)=o(g(n)) 例: 4nlogn+7=o(3n2+ 4nlogn+7),39,構(gòu)造數(shù)據(jù)類(lèi)型由基本數(shù)據(jù)類(lèi)型或構(gòu)造數(shù)據(jù)類(lèi)型組合而成。 構(gòu)造數(shù)據(jù)類(lèi)型由不同成分類(lèi)型構(gòu)成。 基本數(shù)據(jù)類(lèi)型可以看作是計(jì)算機(jī)中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)類(lèi)型就是數(shù)據(jù)結(jié)構(gòu)，不過(guò)它是從編程者的角度來(lái)使用的。 數(shù)據(jù)類(lèi)型是模板，必須定義屬于某種數(shù)據(jù)類(lèi)型的變量，才能參加運(yùn)算。,40,抽象數(shù)據(jù)類(lèi)型 (ADTs: Abstract Data Ty
18、pes),為什么要引入抽象數(shù)據(jù)類(lèi)型 按照頂向下逐步求精的原則, 在探索運(yùn)算步驟時(shí),首先應(yīng)考慮算法的頂層運(yùn)算步驟, 然后再考慮底層運(yùn)算步驟. 頂層運(yùn)算步驟: 指定義在數(shù)據(jù)模型上的運(yùn)算步驟; 底層運(yùn)算步驟:頂層抽象的運(yùn)算的具體實(shí)現(xiàn). 包括數(shù)據(jù)模型的具體表示和定義在該數(shù)據(jù)模型上的運(yùn)算的具體實(shí)現(xiàn).,數(shù)據(jù)類(lèi)型與抽象數(shù)據(jù)類(lèi)型,41,抽象數(shù)據(jù)類(lèi)型 (ADTs: Abstract Data Types),為什么要引入抽象數(shù)據(jù)類(lèi)型 為了將頂層算法與底層算法隔開(kāi), 使二者在設(shè)計(jì)時(shí)不會(huì)相互牽制, 相互影響, 必須對(duì)二者的接口進(jìn)行一次抽象.讓底層只通過(guò)這個(gè)接口為頂層服務(wù), 頂層也只通過(guò)這個(gè)接口調(diào)用底層的運(yùn)算. 這個(gè)接
19、口就是抽象數(shù)據(jù)類(lèi)型.,42,抽象數(shù)據(jù)類(lèi)型 (ADTs: Abstract Data Types),由數(shù)據(jù)模型及定義在該數(shù)據(jù)模型上的一組相關(guān)的運(yùn)算構(gòu)成. 抽象數(shù)據(jù)類(lèi)型的特征是使用于實(shí)現(xiàn)分離, 實(shí)行封裝與信息隱蔽. 數(shù)據(jù)模型及定義在該數(shù)據(jù)模型上的運(yùn)算存在密不可分的聯(lián)系.一方面,數(shù)據(jù)模型上的運(yùn)算依賴(lài)于數(shù)據(jù)模型的具體表示;另一方面,數(shù)據(jù)模型的具體表示反過(guò)來(lái)又依賴(lài)于數(shù)據(jù)模型上的運(yùn)算;,43,抽象數(shù)據(jù)類(lèi)型 (ADTs: Abstract Data Types),定義抽象數(shù)據(jù)類(lèi)型 就是約定抽象數(shù)據(jù)類(lèi)型的名字, 同時(shí), 約定在該類(lèi)型上定義的各個(gè)運(yùn)算的名字, 明確各個(gè)運(yùn)算的參數(shù), 以及運(yùn)算的功能.,44,抽象數(shù)
20、據(jù)類(lèi)型 (ADTs: Abstract Data Types),定義抽象數(shù)據(jù)類(lèi)型 , 算法底層的設(shè)計(jì)任務(wù)為: 1. 對(duì)于每一個(gè)抽象數(shù)據(jù)類(lèi)型 賦予其具體的構(gòu)造數(shù)據(jù)類(lèi)型, 即給每一個(gè)抽象數(shù)據(jù)類(lèi)型 賦予其具體的數(shù)據(jù)結(jié)構(gòu); 2. 對(duì)每個(gè)運(yùn)算賦予其具體的運(yùn)算內(nèi)容, 即賦予其具體的函數(shù). 算法底層的設(shè)計(jì)就是數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)和函數(shù)的設(shè)計(jì),45,抽象數(shù)據(jù)類(lèi)型,,,,,,,,,,,,,查找 登錄 刪除 修改,,,,,,,,,,,,,,,符 號(hào) 表,,,,,46,自然數(shù)的抽象數(shù)據(jù)類(lèi)型定義,ADT NaturalNumber is objects: 一個(gè)整數(shù)的有序子集合,它開(kāi)始于0, 結(jié)束于機(jī)器能表示的最大整數(shù)(M
21、axInt)。 Function: 對(duì)于所有的 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,,
《專(zhuān)升本計(jì)算機(jī)導(dǎo)論》PPT課件.ppt
