大學計算機基礎算法

1、 大學計算機基礎 第8章 數據結構與算法 程序是什么？ 程序=數據結構+算法！ 大連民族學院計算機學院 趙丕錫教授例：某校對100個學生進行獎勵，學生信息存在磁盤文件“file.dat”中，條件是其三門成績全部在90分以上才能進行獎勵，打印出被獎勵學生的學號。以C語言為例，程序代碼如下：#include Void main() struct stu /*數據類型*/ int num; float score3; a100; /* 定義變量*/FILE *fp； Int I,j; fp=fopen(“file.dat”,”r”); /* 打開文件file.dat*/ for(i=0;i100;i

2、+) Fread(&ai,sizeof(struct stu),1,fp); /* 從文件中讀取數據*/ for(j=0;j3;j+) if(ai.scorej=3) /* 如果符合條件，輸出其學號*/ printf(“num:%d”,ai.num); Fclose(fp); 由此可見，程序包括：對數據的描述，在程序中要指定數據的類型和數據的組織形式。 對操作的描述，即對數據的操作處理步驟大學計算機基礎 主講人：趙丕錫教授 第8章 數據結構與算法數據結構（data structure） ： 對數據的描述。即在程序中要指定數據的類型和數據的組織形式。算法（algorithm）： 對操作的描述。即

3、對數據的操作處理步驟。程序：就是用計算機語言表示的數據結構和算法。程序設計：用計算機語言編寫程序的過程。兩個基本步驟： 1、設計數據結構和算法。 2、用一種計算機語言表示出來。 因此，數據結構與算法是程序設計的基礎。 大學計算機基礎 主講人：趙丕錫教授8.1 算 法 8.1.1 算法的基本概念 算法（algorithm）： 對操作的描述。即對數據的操作處理步驟。 算法的表示方法： 自然語言、流程圖、N-S流程圖、偽代碼、計算機語言大學計算機基礎 主講人：趙丕錫教授案例：計算sum=1+2+3+n的算法一、用自然語言描述1、輸入n，即數據個數；2、設置累加器sum，初始制為0；設置計數器i，初始

4、值為1。3、當i小于或等于n時，做累加，即將sum與i相加，其和再放入sum中。計數器i取下一個數，即i等于i+1，直到i大于n時終止。4、輸出累加和sum。大學計算機基礎 主講人：趙丕錫教授二、流程圖描述：sum=1+2+3+n的算法開始輸入nSum=0i=1i=nSum=sum+Iii+1輸出sum結束否是大學計算機基礎 主講人：趙丕錫教授三、N-S圖描述： sum=1+2+3+n的算法 N-S圖是美國學者I.Nassi和B.Shneiderman在1973年提出的一種流程圖，其主要特點是不帶有流程線，整個算法完全寫在一個大的矩形框中。當i=n時，做輸入nSum=0，i=1Sum=sum+

5、Ii=i+1輸出sum的值N-S圖方式大學計算機基礎 主講人：趙丕錫教授四、偽代碼描述： sum=1+2+3+n的算法 就是用文字和符號的方式來描述算法。在實際應用中，人們往往用接近于某種程序語言的代碼形式作為偽代碼。這樣可以方便編程。 偽代碼方式Input n sum=0 i=1 for i=1 to n do sum=sum+i print sumend大學計算機基礎 主講人：趙丕錫教授五、計算機語言描述：程序用C語言描述sum=1+2+3+n的算法Main() int n; int sum=0,i=1; scanf(“%d”,&n); for(i=1;i=n;i+) sum=sum+i;

6、 printf(“sum=%dn”,sum);大學計算機基礎 主講人：趙丕錫教授一、算法的5個基本特征 1、可行性 2、確定性 3、有窮性 4、有零個或多個輸入 5、有一個或多個輸出二、算法的2個基本要素 1、對數據的運算和操作 2、算法的控制結構。大學計算機基礎 主講人：趙丕錫教授 算法的基本要素之一：對數據的運算和操作 在計算機系統(tǒng)中，基本的運算和操作有以下四類： 算術運算：主要包括加、減、乘、除等運算。 邏輯運算：主要包括“邏輯與”、“邏輯或”、“邏輯非” 等運算。 關系運算：主要包括“大于”、“大于或等于”、“小于”、 “小于或等于”、“等于”、“不等于”等運算。 數據傳輸：主要包括賦

7、值、輸入、輸出等操作。算法流程圖例子大學計算機基礎 主講人：趙丕錫教授 算法的基本要素之二：算法的控制結構 控制結構-算法中各種操作步驟之間的執(zhí)行順序。 順序結構選擇結構循環(huán)結構三種基本控制結構算法流程圖例子大學計算機基礎 主講人：趙丕錫教授三、算法設計的基本方法 六種：列舉法、歸納法、遞推、 遞歸、減半遞推技術、回溯法。 1、列舉法 列舉法就是根據所要解決的問題，把所有可 能的情況都一一列舉出來，并用問題中給定的條 件來檢驗哪些是需要的，哪些是不需要的。大學計算機基礎 主講人：趙丕錫教授2、歸納法 歸納法的基本思想是通過列舉少量的特殊情況，經過分析，最后找出一般的關系。 可以看出，歸納法可以

8、解決列舉量為無限的問題。 3、遞推 遞推是指從已知的初始條件出發(fā)，逐步推出所要求的結果。大學計算機基礎 主講人：趙丕錫教授4、遞歸 在解決某些復雜問題時，為了降低問題的復雜程度（如問題的規(guī)模等），可以將問題逐層分解，最后歸結為一些最簡單的問題。例8.2 有5個人坐在一起，問第5個人多少歲?他說比第4個人大2歲。問第4個人的歲數，他說比第3個人大2歲。問第3個人，又說比第2個人大2歲。問第2個人，說比第1個人大2歲。最后問第1個人，他說是10歲。請問第5個人多大？ 大學計算機基礎 主講人：趙丕錫教授 用遞歸方法求解，遞歸過程如下： age（5）age（4）十2 age（4）=age（3）十2 a

9、ge（3）age（2）十2 age（2）age（1）十2 age（l）10大學計算機基礎 主講人：趙丕錫教授5、減半遞推技術 “減半”是指將問題的規(guī)模減半，而問題的性質不變； “遞推”是指重復“減半”的過程。 例8.3 設方程f（x）=0在區(qū)間 a，b上有實根，且f（a）與f（b） 符號相反，即f（a）f（b）0。利用二分法求該方程在區(qū)間 a，b上的一個實根。 用二分法求方程實根的減半遞推過程如下： 首先計算區(qū)間的中點c=（a+b）/2，然后計算函數在中點c的值f（c），并判斷f （c）是否為0。若f（c）=0，則說明c就是所求的根，求解過程結束；如果f （c）0，則根據以下原則將原區(qū)間減半：

10、 大學計算機基礎 主講人：趙丕錫教授 若f（a）f（c）0，則取原區(qū)間的前半部分，； 若f（b）f（c）1，則其父結點編號為i/2。（2）如果2in，則結點i無左子結點（結點i為葉子結點）；否則，其左子結點是結點2i。（3）如果2i+1n，則結點i無右子結點；否則，其右子結點是結點2i+1。根據完全二叉樹的這個性質，如果按從上到下、從左到右順序存儲完全二叉樹的各結點，則很容易確定每一個結點的父結點、左子結點和右子結點的位置。 大學計算機基礎 主講人：趙丕錫教授8.6.3 二叉樹的存儲結構二叉樹通常采用鏈式存儲結構。用于存儲二叉樹中各元素的存儲結點由兩部分組成：數據域與指針域。大學計算機基礎 主

11、講人：趙丕錫教授由于在二叉樹的存儲結構中每個存儲結點有兩個指針域，因此，二叉樹的鏈式存儲結構也稱為二叉鏈表。圖8.30表示二叉鏈表的存儲示意圖。大學計算機基礎 主講人：趙丕錫教授8.6.4 二叉樹的遍歷遍歷是二叉樹的重要運算。二叉樹的遍歷是指按一定的次序訪問二叉樹中的每一個結點，使每個結點被訪問一次且只被訪問一次。在遍歷二叉樹的過程中，一般先遍歷左子樹，然后再遍歷右子樹。在先左后右的原則下，根據訪問根結點的次序，二叉樹的遍歷可以分為三種：前序遍歷、中序遍歷、后序遍歷。下面分別介紹這三種遍歷的方法，并用D、L、R分別表示“訪問根結點”、“遍歷根結點的左子樹”和“遍歷根結點的右子樹”。大學計算機基

12、礎 主講人：趙丕錫教授1前序遍歷（DLR）前序遍歷是指首先訪問根結點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先訪問根結點，然后遍歷左子樹，最后遍歷右子樹例如，對圖8.31中的二叉樹進行前序遍歷，則遍歷的結果為ABDGCEHIF。大學計算機基礎 主講人：趙丕錫教授2中序遍歷（LDR）中序遍歷是指首先遍歷左子樹，然后訪問根結點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。例如，對圖8.31中的二叉樹進行中序遍歷，則遍歷結果為DGBAHEICF。大學計算機基礎 主講人：趙丕錫教授3后序遍歷（LRD）后序遍歷是指首先遍歷左子樹，然

13、后遍歷右子樹，最后訪問根結點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結點。例如，對圖8.31中的二叉樹進行后序遍歷，則遍歷結果為GDBHIEFCA。大學計算機基礎 主講人：趙丕錫教授考題（2005_4）1.某二叉樹中度為2的結點有18個，則該二叉樹中有_1_個葉子結點。答案：19大學計算機基礎 主講人：趙丕錫教授考題（2005_4）（4）一棵二叉樹第六層（根結點為第一層）的結點數最多為_個。答案：32大學計算機基礎 主講人：趙丕錫教授8.7 查找與排序技術8.7.1 順序查找順序查找又稱為順序搜索。順序查找一般是指在線性表中查找指定的元素，基本方法如下：從線性表

14、的第一個元素開始，依次將線性表中的元素與被查找元素進行比較，若相等則表示找到（即查找成功）；若線性表中所有的元素都與被查元素進行了比較，但都不相等，則表示線性表中沒有要查找的元素（即查找失?。?。大學計算機基礎 主講人：趙丕錫教授8.7.2 二分法查找二分法查找只適用于順序存儲的有序表，即要求線性表中的元素按元素值的大小排列（遞減排列或遞增排列）。假設有序線性表是按元素值遞增排列的，并設表的長度為n，被查元素為x，則二分法查找過程如下：大學計算機基礎 主講人：趙丕錫教授將x與線性表的中間元素進行比較：若中間元素的值等于x，則說明查成功，查找結束；若x小于中間元素的值，則在線性表的前半部分以相同的

15、方法查找；若x大于中間元素的值，則在線性表的后半部分以相同的方法查找。這個過程一直進行到查找成功或子表長度為0（說明線性表中沒有這個元素）為止?？梢钥闯?，當有序的線性表為順序存儲時才能采用二分查找。可以證明，對于長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次，順序查找需要比較n次。可見，二分查找的效率要比順序查找高得多。大學計算機基礎 主講人：趙丕錫教授8.7.3 交換類排序法1冒泡排序法冒泡排序法是一種最簡單的交換類排序方法，它是通過相鄰數據元素的交換逐步將線性表變成有序的。冒泡排序法的操作過程如下：首先，從表頭開始往后掃描線性表，在掃描過程中依次比較相鄰兩元素的大小，若

16、前面的元素大于后面的元素，則將它們互換，稱之為消去了一個逆序。顯然，在掃描過程中，不斷地將兩相鄰元素中的大者往后移動，最后就將線性表中的最大者換到了表的最后。大學計算機基礎 主講人：趙丕錫教授然后，按相反的方向掃描剩下的線性表，在掃描過程中依次比較相鄰兩個元素的大小，若后面的元素小于前面的元素，則將它們互換，這樣就又消去了一個逆序。顯然，在掃描過程中，不斷地將兩相鄰元素中的小者往前移動，最后就將剩下的線性表中的最小者換到了表的最前面。此時，線性表的第一個元素就是最小者，最后一個元素就是最大者。對剩下的元素構成的線性表重復上述過程，直到剩下的元素為空或者在掃描過程中沒有交換任何元素，此時，線性表

17、變?yōu)橛行?。大學計算機基礎 主講人：趙丕錫教授 圖8.32是冒泡排序法的示意圖。圖中有下劃線的元素表示掃描過程中的第一個和最后一個元素的位置。 從冒泡排序法的操作過程可以看出，對長度為n的線性表，在最壞的情況下需要進行（n-1）+（n-2）+2+1=n（n-1）/2次比較。原序列628131957第1遍（從前往后）261318579（從后往前）126135879第2遍（從前往后）121356789（從后往前）112356789第3遍（從前往后）112356789最后結果1123567898.32冒泡排序示意圖大學計算機基礎 主講人：趙丕錫教授2快速排序法 快速排序法是對冒泡排序法的改進，又叫作分

18、區(qū)交換排序法?？焖倥判蚍ǖ幕舅枷肴缦拢?從線性表中任意選取一個元素（通常選第一個元素），設為T，將線性表中小于T的元素移到T的前面，而大于T的元素移到T的后面，結果就將線性表分成了兩部分（稱為兩個子表），T處于分界線的位置處，這個過程稱為線性表的分割。通過對線性表的一次分割，就以T為分界線，將線性表分成了前后兩個子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。 如果對分割后的各子表再按上述原則進行分割，并且，這種分割過程可以一直做下去，直到所有子表為空為止，此時的線性表就變成了有序表。大學計算機基礎 主講人：趙丕錫教授設當前要排序的線性表的下界為low，上界為hig

19、h，則分割操作的步驟如下：（1）設兩個指針i和j分別指向線性表的第一個元素和最后一個元素，即P（i）=low；P（j）=high，并將第一個元素保存在T中。（2）用T與j指向的元素比較，若TP（j），則讓j指向前一個元素，再比較；否則將P（j）和P（i）互換位置。（3）用T與i指向的元素比較，若TP（i），則讓i指向后一個元素，再比較；否則將P（j）和P（i）互換位置。（4）反復進行（2）和（3）兩步操作，直到i和j指向同一個元素，即i=j時，分割結束。i所指向的元素就是T應該放置的位置。大學計算機基礎 主講人：趙丕錫教授下面舉例說明快速排序法。設線性表為（33 18 22 88 38 14

20、55 13 47），若選第一個元素33為T，則第一次排序過程如圖8.33（a）所示。大學計算機基礎 主講人：趙丕錫教授對線性表進行完一次快速排序后，用同樣的方法對分割后的子表進行快速排序，直到各個子表的長度為1為止。排序過程如圖8.33（b）所示。大學計算機基礎 主講人：趙丕錫教授8.7.3 插入類排序法1簡單插入排序法 簡單插入排序法也叫直接插入排序法。插入排序是指將無序序列中的各元素依次插入到已經有序的線性表中。 圖8.34給出了插入排序的示意圖。圖中方括號 中為已排好序的元素。大學計算機基礎 主講人：趙丕錫教授 在簡單插入排序法中，每一次比較后最多移掉一個逆序，因此，這種排序方法的效率與

21、冒泡排序法相同。在最壞情況下，簡單插入排序需要n（n-1）/2次比較。大學計算機基礎 主講人：趙丕錫教授2希爾排序法 希爾排序法（Shell Sort）又稱縮小增量排序法，它對簡單插入排序做了較大的改進。 其方法如下： 將整個無序序列分割成若干小的子序列分別進行簡單插入排序。 子序列的分割方法如下： 使相隔某個增量h的元素構成一個子序列。在排序過程中，逐次減小這個增量，最后當h減到1時，進行一次簡單插入排序，排序就完成。 增量序列一般取hk=n/2k （k=l，2，log2n），其中n為待排序序列的長度。大學計算機基礎 主講人：趙丕錫教授圖8.35為希爾排序法的示意圖。大學計算機基礎 主講人：

22、趙丕錫教授8.7.4 選擇類排序法1簡單選擇排序法 簡單選擇排序法也叫直接選擇排序法，是一種比較簡單的排序方法，其排序過程如下： 掃描整個線性表，從中選出最小的元素，將它與表中的第一個元素交換；然后對剩下的子表采用同樣的方法，直到子表只有一個元素為止。大學計算機基礎 主講人：趙丕錫教授2堆排序法 堆排序法是在簡單排序法的基礎上借助于完全二叉樹結構而形成的一種排序方法。 首先介紹堆的定義： 具有n個元素的序列（h1，h2，hn），當且僅當滿足 （i=1，2，n/2） 時稱之為堆。 為了方便，我們稱滿足前者條件的堆為大根堆，而稱滿足后面條件的堆為小根堆。下面只討論大根堆。大學計算機基礎 主講人：趙

23、丕錫教授 由堆的定義可知，堆頂元素（即第一個元素）必為最大項。 在實際應用中，可用一維數組H（1：n）來存儲堆序列中的元素，并且可用完全二叉樹來表示堆的結構。 例如，序列（98，82，54，35，46，29，21）是一個堆，它所對應的完全二叉樹如圖8.37所示。 大學計算機基礎 主講人：趙丕錫教授 在用完全二叉樹表示堆時，樹中所有非葉子結點值均不小于其左、右子樹的根結點值，因此，堆頂（完全二叉樹的根結點）元素必為序列的n個元素中的最大項。 下面討論調整建堆的問題：我們用一維數組H（1：n）表示一棵具有n個結點的完全二叉樹。在這個完全二叉樹中，假設結點H（m）的左右子樹都是堆，現在要將以H（m）為根結點的子樹也調整為堆。大學計算機基礎 主講人：趙丕錫教授 例如，假設圖8.38 （a）是一棵完全二叉樹。 在這棵二叉樹中，根結點46的左、右子樹都是堆?，F在為了將整個子樹調整為堆，首先將根結點46與其左、右子樹的根結點值進行比較，這時由于左子樹根結點89大于右子樹根結點43，且它又大于根結點46， 圖8.38（a） 大學計算機基礎 主講人：趙丕錫教授 根據堆的定義，應將元素46與89交換，如圖8.38（b）所示。經過這一次交換后，破壞了原來左子樹的堆結構，需要對左子樹再進行調整，將元素75