大學(xué)計(jì)算機(jī)基礎(chǔ)算法

1、 大學(xué)計(jì)算機(jī)基礎(chǔ) 第8章 數(shù)據(jù)結(jié)構(gòu)與算法 程序是什么？ 程序=數(shù)據(jù)結(jié)構(gòu)+算法！ 大連民族學(xué)院計(jì)算機(jī)學(xué)院 趙丕錫教授例：某校對100個學(xué)生進(jìn)行獎勵，學(xué)生信息存在磁盤文件“file.dat”中，條件是其三門成績?nèi)吭?0分以上才能進(jìn)行獎勵，打印出被獎勵學(xué)生的學(xué)號。以C語言為例，程序代碼如下：#include Void main() struct stu /*數(shù)據(jù)類型*/ 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); /* 從文件中讀取數(shù)據(jù)*/ for(j=0;j3;j+) if(ai.scorej=3) /* 如果符合條件，輸出其學(xué)號*/ printf(“num:%d”,ai.num); Fclose(fp); 由此可見，程序包括：對數(shù)據(jù)的描述，在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式。 對操作的描述，即對數(shù)據(jù)的操作處理步驟大學(xué)計(jì)算機(jī)基礎(chǔ) 主講人：趙丕錫教授 第8章 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)（data structure） ： 對數(shù)據(jù)的描述。即在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式。算法（algorithm）： 對操作的描述。即

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

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

5、Ii=i+1輸出sum的值N-S圖方式大學(xué)計(jì)算機(jī)基礎(chǔ) 主講人：趙丕錫教授四、偽代碼描述： sum=1+2+3+n的算法 就是用文字和符號的方式來描述算法。在實(shí)際應(yīng)用中，人們往往用接近于某種程序語言的代碼形式作為偽代碼。這樣可以方便編程。 偽代碼方式Input n sum=0 i=1 for i=1 to n do sum=sum+i print sumend大學(xué)計(jì)算機(jī)基礎(chǔ) 主講人：趙丕錫教授五、計(jì)算機(jī)語言描述：程序用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);大學(xué)計(jì)算機(jī)基礎(chǔ) 主講人：趙丕錫教授一、算法的5個基本特征 1、可行性 2、確定性 3、有窮性 4、有零個或多個輸入 5、有一個或多個輸出二、算法的2個基本要素 1、對數(shù)據(jù)的運(yùn)算和操作 2、算法的控制結(jié)構(gòu)。大學(xué)計(jì)算機(jī)基礎(chǔ) 主講人：趙丕錫教授 算法的基本要素之一：對數(shù)據(jù)的運(yùn)算和操作 在計(jì)算機(jī)系統(tǒng)中，基本的運(yùn)算和操作有以下四類： 算術(shù)運(yùn)算：主要包括加、減、乘、除等運(yùn)算。 邏輯運(yùn)算：主要包括“邏輯與”、“邏輯或”、“邏輯非” 等運(yùn)算。 關(guān)系運(yùn)算：主要包括“大于”、“大于或等于”、“小于”、 “小于或等于”、“等于”、“不等于”等運(yùn)算。 數(shù)據(jù)傳輸：主要包括賦

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

8、解決列舉量為無限的問題。 3、遞推 遞推是指從已知的初始條件出發(fā)，逐步推出所要求的結(jié)果。大學(xué)計(jì)算機(jī)基礎(chǔ) 主講人：趙丕錫教授4、遞歸 在解決某些復(fù)雜問題時，為了降低問題的復(fù)雜程度（如問題的規(guī)模等），可以將問題逐層分解，最后歸結(jié)為一些最簡單的問題。例8.2 有5個人坐在一起，問第5個人多少歲?他說比第4個人大2歲。問第4個人的歲數(shù)，他說比第3個人大2歲。問第3個人，又說比第2個人大2歲。問第2個人，說比第1個人大2歲。最后問第1個人，他說是10歲。請問第5個人多大？ 大學(xué)計(jì)算機(jī)基礎(chǔ) 主講人：趙丕錫教授 用遞歸方法求解，遞歸過程如下： 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大學(xué)計(jì)算機(jī)基礎(chǔ) 主講人：趙丕錫教授5、減半遞推技術(shù) “減半”是指將問題的規(guī)模減半，而問題的性質(zhì)不變； “遞推”是指重復(fù)“減半”的過程。 例8.3 設(shè)方程f（x）=0在區(qū)間 a，b上有實(shí)根，且f（a）與f（b） 符號相反，即f（a）f（b）0。利用二分法求該方程在區(qū)間 a，b上的一個實(shí)根。 用二分法求方程實(shí)根的減半遞推過程如下： 首先計(jì)算區(qū)間的中點(diǎn)c=（a+b）/2，然后計(jì)算函數(shù)在中點(diǎn)c的值f（c），并判斷f （c）是否為0。若f（c）=0，則說明c就是所求的根，求解過程結(jié)束；如果f （c）0，則根據(jù)以下原則將原區(qū)間減半：

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

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

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

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

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

15、方法查找；若x大于中間元素的值，則在線性表的后半部分以相同的方法查找。這個過程一直進(jìn)行到查找成功或子表長度為0（說明線性表中沒有這個元素）為止?？梢钥闯?，當(dāng)有序的線性表為順序存儲時才能采用二分查找?？梢宰C明，對于長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次，順序查找需要比較n次?？梢姡植檎业男室软樞虿檎腋叩枚?。大學(xué)計(jì)算機(jī)基礎(chǔ) 主講人：趙丕錫教授8.7.3 交換類排序法1冒泡排序法冒泡排序法是一種最簡單的交換類排序方法，它是通過相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序的。冒泡排序法的操作過程如下：首先，從表頭開始往后掃描線性表，在掃描過程中依次比較相鄰兩元素的大小，若

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

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

18、區(qū)交換排序法。快速排序法的基本思想如下： 從線性表中任意選取一個元素（通常選第一個元素），設(shè)為T，將線性表中小于T的元素移到T的前面，而大于T的元素移到T的后面，結(jié)果就將線性表分成了兩部分（稱為兩個子表），T處于分界線的位置處，這個過程稱為線性表的分割。通過對線性表的一次分割，就以T為分界線，將線性表分成了前后兩個子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。 如果對分割后的各子表再按上述原則進(jìn)行分割，并且，這種分割過程可以一直做下去，直到所有子表為空為止，此時的線性表就變成了有序表。大學(xué)計(jì)算機(jī)基礎(chǔ) 主講人：趙丕錫教授設(shè)當(dāng)前要排序的線性表的下界為low，上界為hig

19、h，則分割操作的步驟如下：（1）設(shè)兩個指針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）反復(fù)進(jìn)行（2）和（3）兩步操作，直到i和j指向同一個元素，即i=j時，分割結(jié)束。i所指向的元素就是T應(yīng)該放置的位置。大學(xué)計(jì)算機(jī)基礎(chǔ) 主講人：趙丕錫教授下面舉例說明快速排序法。設(shè)線性表為（33 18 22 88 38 14

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

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

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

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