計(jì)算機(jī)導(dǎo)論課件：算法與數(shù)據(jù)結(jié)構(gòu)

4.1算法4.2數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)4.1算法4.1.1算法描述一個(gè)問題可以有多種求解方法，一個(gè)求解方法可以有多種描述形式。如果在人與人之間交流，可以采用自然語言、示例、圖、表、公式等描述形式；如果在人與計(jì)算機(jī)之間交流，則只能采用程序設(shè)計(jì)語言，因此程序也稱為程序設(shè)計(jì)語言描述的算法。下面，通過一個(gè)例子介紹不同的算法描述形式。例4-1求解兩個(gè)正整數(shù)的最大公約數(shù)。針對(duì)這個(gè)問題，給出兩種求解方法：窮舉法和輾轉(zhuǎn)相除法，每種方法給出三種描述形式：自然語言形式、流程圖形式和程序設(shè)計(jì)語言(C語言)形式。1．窮舉法(1)窮舉法的自然語言形式如下：①令S為兩個(gè)正整數(shù)M、N中的較小者；②令R1為M除以S的余數(shù)，R2為N除以S的余數(shù)；③若R1與R2同時(shí)等于0，則S就是兩個(gè)正整數(shù)的最大公約數(shù)，否則令S為S減1，返回②繼續(xù)。窮舉法的流程圖形式如圖4-1所示。(2)窮舉法的程序設(shè)計(jì)語言形式如下：intgreatest_common_divisor(intm,intn){ints,r1,r2;if(m>n)s=n;elses=m;r1=m%s;r2=n%s;while(r1!=0||r2!=0){s=s-1;r1=m%s;r2=n%s;}return(s);}2．輾轉(zhuǎn)相除法(1)輾轉(zhuǎn)相除法的自然語言形式如下：①令M為兩個(gè)正整數(shù)中的較大者，N為較小者；②令R為M除以N的余數(shù)；③若R等于0，則N就是兩個(gè)正整數(shù)的最大公約數(shù)；否則令M為N，N為R，返回②繼續(xù)。(2)輾轉(zhuǎn)相除法的程序設(shè)計(jì)語言形式如下：intgreatest_common_divisor(intm,intn){intr;if(m<n){r=m;m=n;n=r;}r=m%n;while(r!=0)

{m=n;n=r;r=m%n;}return(n);}輾轉(zhuǎn)相除法的流程圖形式如圖4-2所示。4.1.2算法分析前面提到，一個(gè)問題可以有多個(gè)求解算法，究竟哪個(gè)算法好呢？這就是算法分析的任務(wù)。算法分析，也稱為算法復(fù)雜性分析，是對(duì)運(yùn)行算法所消耗的資源進(jìn)行分析。算法消耗的資源越多，算法復(fù)雜性就越高。資源可以分為時(shí)間資源(運(yùn)行時(shí)間)和空間資源(內(nèi)存空間)，因此，算法復(fù)雜性分析也分為時(shí)間復(fù)雜性分析和空間復(fù)雜性分析。例4-2直觀分析例4-1給出的兩個(gè)算法——窮舉法和輾轉(zhuǎn)相除法。窮舉法和輾轉(zhuǎn)相除法的算法分析如表4-1所示。如果選擇變量數(shù)目作為空間度量，則窮舉法需要5個(gè)變量M、N、S、R1、R2，輾轉(zhuǎn)相除法需要3個(gè)變量M、N、R，輾轉(zhuǎn)相除法優(yōu)于窮舉法。如果選擇循環(huán)語句執(zhí)行次數(shù)作為時(shí)間度量，則當(dāng)M?=?30，N?=?15時(shí)，窮舉法和輾轉(zhuǎn)相除法都是0次循環(huán)，而當(dāng)M?=?30，N?=?16時(shí)，窮舉法是14次循環(huán)，輾轉(zhuǎn)相除法是2次循環(huán)?？梢钥吹?，不同的M和N，同一算法的循環(huán)次數(shù)也不同，因此，時(shí)間復(fù)雜性有最好情況、最壞情況、平均情況三種。從平均情況來看，輾轉(zhuǎn)相除法優(yōu)于窮舉法。事實(shí)上，當(dāng)進(jìn)行算法復(fù)雜性分析時(shí)，不可能也沒必要如例4-2一樣，針對(duì)特定輸入分析算法的變量數(shù)目和基本語句執(zhí)行次數(shù)，而是分析隨著問題規(guī)模的增長，復(fù)雜性增長的量級(jí)。例如，算法的時(shí)間復(fù)雜性與算法本身、問題規(guī)模n相關(guān)，當(dāng)算法確定時(shí)，算法的時(shí)間復(fù)雜性就是n的函數(shù)T(n)，并且通常采用漸進(jìn)上界O(f(n))表達(dá)其時(shí)間復(fù)雜性增長的量級(jí)。如果算法的時(shí)間復(fù)雜性過高，則該算法可能是理論可計(jì)算，而實(shí)際不可計(jì)算。例如，時(shí)間復(fù)雜性為O(2n)的算法，隨著問題規(guī)模n的增加，運(yùn)行時(shí)間呈指數(shù)增加，算法就是理論可計(jì)算而實(shí)際不可計(jì)算。4.1.3算法設(shè)計(jì)1.分治與遞歸計(jì)算機(jī)求解問題所需時(shí)間一般都與問題規(guī)模相關(guān)，問題規(guī)模越小，所需時(shí)間越少，也較容易處理。分治是將一個(gè)難以直接解決的規(guī)模較大的原問題分解成一系列規(guī)模較小的子問題，分別求解各個(gè)子問題，再合并子問題的解得到原問題的解。分治是算法設(shè)計(jì)的基本策略，包括三個(gè)步驟：(1)分解：將原問題分解成一系列子問題。(2)求解：求解各個(gè)子問題。(3)合并：合并子問題的解得到原問題的解。在算法設(shè)計(jì)中，遞歸與分治就像孿生兄弟，密切相關(guān)。遞歸是指函數(shù)(或過程)直接調(diào)用自己或通過一系列調(diào)用語句間接調(diào)用自己。通常，遞歸用于解決結(jié)構(gòu)自相似問題，即構(gòu)成原問題的子問題與原問題在結(jié)構(gòu)上相似，可以采用類似方法求解。遞歸是描述問題和解決問題的基本方法，包括兩個(gè)要素：(1)邊界條件：確定遞歸何時(shí)終止，也稱為遞歸出口。(2)遞歸模式：確定原問題如何分解為子問題，也稱為遞歸體。例4-3求解n!。方法一：n!可以展開為n!?=?n*(n-1)?*?(n-2)*…*3*2*1，可以采用循環(huán)求解，流程圖如圖4-3所示，程序如下：intfactorial(intn){intp,m;p=1;m=1;while(m<=n){p=p*m;m=m+1;}return(p);}方法二：n!?也可以寫成遞歸形式，即遞歸體：n!?=?n*(n-1)!，遞歸出口：1!=1，可以采用遞歸求解，求解過程如圖4-4所示，程序如下：intfactorial(intn){intp;if(n==1)p=1;elsep=n*factorial(n-1);return(p);}2.動(dòng)態(tài)規(guī)劃當(dāng)采用分治與遞歸設(shè)計(jì)算法時(shí)，原問題的一系列子問題最好相互獨(dú)立，否則會(huì)因?yàn)橹貜?fù)求解公共子問題而導(dǎo)致效率低下。如果子問題相互重疊，通?？梢圆捎脛?dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃對(duì)每個(gè)子問題只求解一次并將解保存在表格中，當(dāng)需要再次求解該子問題時(shí)，通過查表獲得其解，從而避免重復(fù)求解公共子問題。例4-4計(jì)算2階Fibonacci序列的第n項(xiàng)，公式如下：方法一：上述公式本身就是遞歸描述，即遞歸體：fn?=?fn-1?+?fn-2，遞歸出口：f0?=?0，f1?=?1。遞歸求解過程中的子問題如圖4-5所示，程序如下：intfibonacci(intn){intp;if(n==0)p=0;if(n==1)p=1;if(n>=2)p=fibonacci(n-1)+fibonacci(n-2);return(p);}從圖4-5可以看到，在f5的遞歸計(jì)算中，有許多子問題被重復(fù)計(jì)算，如f3被重復(fù)計(jì)算了2次，f2被重復(fù)計(jì)算了3次。隨著n的增加，這個(gè)現(xiàn)象更加突顯，嚴(yán)重影響計(jì)算效率。方法二：采用動(dòng)態(tài)規(guī)劃，即顛倒計(jì)算方向，將自頂而下計(jì)算變?yōu)樽缘锥嫌?jì)算，對(duì)每個(gè)子問題僅計(jì)算一次并將解保存在表格中，當(dāng)需要再次計(jì)算該子問題時(shí)，通過查表獲得其解，從而避免重復(fù)求解公共子問題，程序如下：intfibonacci(intn){intp,f[100],i;if(n==0)p=0;if(n==1)p=1;if(n>=2){f[0]=0;f[1]=1;for(i=2;i<=n;i++)f[i]=f[i-1]+f[i-2];p=f[n];}return(p);}動(dòng)態(tài)規(guī)劃求解過程中的表格如表4-2所示。4.2數(shù)據(jù)結(jié)構(gòu)4.2.1基本概念數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。所謂數(shù)據(jù)元素是在程序中作為一個(gè)整體進(jìn)行考慮和處理的數(shù)據(jù)的基本單位，可由若干個(gè)數(shù)據(jù)項(xiàng)組成。例4-5如圖4-6所示，在職工管理中，一個(gè)職工的信息就是一個(gè)數(shù)據(jù)元素，可由職工號(hào)、姓名、性別、出生年月等數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容包括：(1)數(shù)據(jù)的邏輯結(jié)構(gòu)：研究數(shù)據(jù)元素之間的邏輯關(guān)系。(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：研究數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)中的表示與存儲(chǔ)。(3)基本操作的算法：研究當(dāng)某種邏輯結(jié)構(gòu)采用某種存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)時(shí)，基本操作的算法及復(fù)雜性。數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容如圖4-7所示。邏輯結(jié)構(gòu)可以分為線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)可以分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。例4-6在職工管理中，n個(gè)職工的信息是n個(gè)數(shù)據(jù)元素，它們的邏輯結(jié)構(gòu)可以看做線性結(jié)構(gòu)中的線性表，即數(shù)據(jù)元素之間的邏輯關(guān)系是線性關(guān)系，而且可以在任一位置刪除或者插入一個(gè)數(shù)據(jù)元素，如圖4-8所示。線性表的順序存儲(chǔ)結(jié)構(gòu)可以采用C語言中的數(shù)組實(shí)現(xiàn)，一個(gè)數(shù)組元素存儲(chǔ)一個(gè)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯相鄰采用數(shù)組元素之間的物理相鄰表示，順序存儲(chǔ)結(jié)構(gòu)如圖4-9所示。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可以采用C語言中的指針實(shí)現(xiàn)，如圖4-10所示，一個(gè)結(jié)點(diǎn)存儲(chǔ)一個(gè)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯相鄰采用結(jié)點(diǎn)之間的指針表示。4.2.2線性結(jié)構(gòu)線性結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系是線性關(guān)系(一對(duì)一關(guān)系)。第一個(gè)數(shù)據(jù)元素沒有前驅(qū)，只有唯一后繼，最后一個(gè)數(shù)據(jù)元素沒有后繼，只有唯一前驅(qū)，其它數(shù)據(jù)元素有唯一前驅(qū)和唯一后繼。如圖4-12所示，圓圈表示數(shù)據(jù)元素，線表示數(shù)據(jù)元素之間的關(guān)系。根據(jù)線性結(jié)構(gòu)中數(shù)據(jù)元素的操作限制，線性結(jié)構(gòu)分為以下幾個(gè)：(1)線性表：允許在任一位置進(jìn)行插入和刪除操作。(2)堆棧：只允許在一端進(jìn)行插入和刪除操作。這一端稱為棧頂，另一端稱為棧底，如圖4-13所示。堆棧的特點(diǎn)是先進(jìn)棧的數(shù)據(jù)元素后出棧，稱為先進(jìn)后出(FirstInLastOut，F(xiàn)ILO)。(3)隊(duì)列：只允許在一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作。插入一端稱為隊(duì)尾，刪除一端稱為隊(duì)頭，如圖4-14所示。隊(duì)列的特點(diǎn)是先進(jìn)隊(duì)的數(shù)據(jù)元素先出隊(duì)，稱為先進(jìn)先出(FirstInFirstOut，F(xiàn)IFO)。4.2.3樹結(jié)構(gòu)樹結(jié)構(gòu)是一種非常重要的數(shù)據(jù)結(jié)構(gòu)。樹的遞歸定義為：沒有結(jié)點(diǎn)(數(shù)據(jù)元素)的樹稱為空樹。在非空樹中，有且僅有一個(gè)結(jié)點(diǎn)稱為根結(jié)點(diǎn)，其余結(jié)點(diǎn)可分為若干互不相交的集合，每個(gè)集合又是一棵樹，稱為根結(jié)點(diǎn)的子樹。結(jié)點(diǎn)的子樹數(shù)目稱為結(jié)點(diǎn)的度。除根結(jié)點(diǎn)外，度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)，度不為0的結(jié)點(diǎn)稱為內(nèi)部結(jié)點(diǎn)。結(jié)點(diǎn)的子樹根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)，相應(yīng)地，該結(jié)點(diǎn)稱為子樹根結(jié)點(diǎn)的父結(jié)點(diǎn)。根結(jié)點(diǎn)沒有父結(jié)點(diǎn)，可以有若干子結(jié)點(diǎn)；葉結(jié)點(diǎn)沒有子結(jié)點(diǎn)，只有唯一父結(jié)點(diǎn)；內(nèi)部結(jié)點(diǎn)只有唯一父結(jié)點(diǎn)，可以有若干子結(jié)點(diǎn)。因此，樹結(jié)構(gòu)是指數(shù)據(jù)元素(結(jié)點(diǎn))之間的邏輯關(guān)系是一對(duì)多關(guān)系(分支)，一個(gè)父結(jié)點(diǎn)可以有若干子結(jié)點(diǎn)，一個(gè)子結(jié)點(diǎn)只有唯一父結(jié)點(diǎn)，如圖4-15所示。二叉樹是一種應(yīng)用廣泛的特殊的樹結(jié)構(gòu)，它的遞歸定義是：沒有結(jié)點(diǎn)(數(shù)據(jù)元素)的二叉樹稱為空樹。在非空二叉樹中，有且僅有一個(gè)結(jié)點(diǎn)稱為根結(jié)點(diǎn)，其余結(jié)點(diǎn)可分為兩個(gè)互不相交的集合，每個(gè)集合又是一棵二叉樹，分別稱為根結(jié)點(diǎn)的左子樹和右子樹。二叉樹的特點(diǎn)是任意結(jié)點(diǎn)至多有二個(gè)子結(jié)點(diǎn)，子結(jié)點(diǎn)有左右之分，如圖4-16所示。二叉排序樹又是一種用于查找的特殊的二叉樹，它的特點(diǎn)是：對(duì)于任意結(jié)點(diǎn)，若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的值；若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的值，如圖4-17所示。4.2.4圖結(jié)構(gòu)圖結(jié)構(gòu)是比樹結(jié)構(gòu)更復(fù)雜的一種數(shù)據(jù)結(jié)構(gòu)。如圖4-18所示，在圖結(jié)構(gòu)中，數(shù)據(jù)元素(頂點(diǎn))之間的邏輯關(guān)系是多對(duì)多關(guān)系(邊)。根據(jù)邊是否有方向，可將圖分為有向圖(如圖4-18(a)所示)和無向圖(如圖4-18(b)所示)。在無向圖