大學(xué)計算機第四章ppt課件

1、第四章第四章 軟件基礎(chǔ)軟件基礎(chǔ)第2頁計算機二級考試公共基礎(chǔ)知識計算機二級考試公共基礎(chǔ)知識q 基本數(shù)據(jù)結(jié)構(gòu)與算法基本數(shù)據(jù)結(jié)構(gòu)與算法(教材教材4.2節(jié)節(jié))q 程序設(shè)計基礎(chǔ)程序設(shè)計基礎(chǔ)q 軟件工程基礎(chǔ)軟件工程基礎(chǔ)q 數(shù)據(jù)庫設(shè)計基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)(教材第教材第8章自學(xué)章自學(xué))二級考試科目分成二級語言程序設(shè)計二級考試科目分成二級語言程序設(shè)計(C、C、Java、Visual Basic)和二級數(shù)據(jù)庫程序設(shè)計和二級數(shù)據(jù)庫程序設(shè)計(Visual FoxPro、Access)兩類。兩類。公共基礎(chǔ)知識在各科筆試中的比重為公共基礎(chǔ)知識在各科筆試中的比重為30% (教材教材4.1節(jié)自學(xué)節(jié)自學(xué))第3頁 排序技術(shù)排序技術(shù)

2、第4頁 對解題方案準(zhǔn)確而完整的描述稱為算法。對解題方案準(zhǔn)確而完整的描述稱為算法。 程序程序用計算機語言描述的算法用計算機語言描述的算法 流程圖流程圖圖形化的算法圖形化的算法(機械圖機械圖) 算法是程序設(shè)計的核心算法是程序設(shè)計的核心INPUT rS=r*r*3.14PTINT S開場開場輸入輸入R RS=R*R*3.14輸出輸出S S終了終了問題：輸入園的半徑，計算園的面積起止框起止框輸入輸出框輸入輸出框處處置置框框第5頁算法分為兩類：算法分為兩類： 數(shù)值計算算法數(shù)值計算算法 求數(shù)值解求數(shù)值解 特點：少量的輸入、輸出，復(fù)雜的運算特點：少量的輸入、輸出，復(fù)雜的運算 非數(shù)值計算算法非數(shù)值計算算法 數(shù)

3、據(jù)處理數(shù)據(jù)處理 特點：大量的輸入、輸出，簡單的運算特點：大量的輸入、輸出，簡單的運算第6頁算法的兩個要素：算法的兩個要素： 操作 算術(shù)運算 關(guān)系運算 邏輯運算 數(shù)據(jù)傳輸?shù)?頁 算法的基本特征算法的基本特征 是一組嚴(yán)謹(jǐn)?shù)囟x運算順序的規(guī)則，每一個規(guī)則都是有效的，是明確的，此順序?qū)⒃谟邢薜氖且唤M嚴(yán)謹(jǐn)?shù)囟x運算順序的規(guī)則，每一個規(guī)則都是有效的，是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。次數(shù)下終止。n 有窮性有窮性n 確定性確定性n 可行性可行性n 輸入輸入n 輸出輸出算法在執(zhí)行有窮步驟后結(jié)束，且每一步都能在算法在執(zhí)行有窮步驟后結(jié)束，且每一步都能在有限時間內(nèi)完成。有限時間內(nèi)完成。算法中的每一步操作的內(nèi)容和

4、順序必須含義確算法中的每一步操作的內(nèi)容和順序必須含義確切，不能有二義性切，不能有二義性。算法中的每一步操作都必須是可執(zhí)行的，也稱算法中的每一步操作都必須是可執(zhí)行的，也稱之為有效性之為有效性。算法中有零個或多個輸入。這些輸入數(shù)據(jù)應(yīng)在算法中有零個或多個輸入。這些輸入數(shù)據(jù)應(yīng)在算法操作前提供。算法操作前提供。算法的目的是用來解決一個給定的問題，因此，算法的目的是用來解決一個給定的問題，因此，它應(yīng)向人們提供產(chǎn)生的結(jié)果它應(yīng)向人們提供產(chǎn)生的結(jié)果。擁有足夠的情報擁有足夠的情報第8頁第9頁ACB變量變量C是一個是一個臨時工作單元，臨時工作單元，用來保存中間用來保存中間結(jié)果。結(jié)果。C=BB=AA=C高級語言語句實

5、現(xiàn)第一步第一步第二步第二步第三步第三步第10頁 計數(shù)器和累加器計數(shù)器和累加器 進入一個人進入一個人i=100i=i+10iy輸入輸入XSUM=SUM+X輸出輸出SUM0SUMX=0) ABDFECGHIJKMn 根：根：only onen 若若n=0，則稱為空樹；，則稱為空樹；n 否則，當(dāng)否則，當(dāng)n1時，其余結(jié)時，其余結(jié)點被分成點被分成m(m0)個互不相交個互不相交的子集的子集T1，T2，.，Tm，每個子集又是一棵樹。由此每個子集又是一棵樹。由此可以看出，樹的定義是遞歸可以看出，樹的定義是遞歸的。的。n Question：如何辨別根？：如何辨別根？A只有一個只有一個結(jié)點的樹結(jié)點的樹第40頁AB

6、DFECGHIJKMn 結(jié)點的度結(jié)點的度 一個結(jié)點的子樹的個數(shù)；一個結(jié)點的子樹的個數(shù)；n Q：結(jié)點：結(jié)點A、D的度數(shù)？的度數(shù)？( )n 樹的度樹的度 樹中所有結(jié)點度的最大值；樹中所有結(jié)點度的最大值；n Q：右圖中樹的度？：右圖中樹的度？( )n 終端終端(葉子葉子)結(jié)點結(jié)點 度為度為0的結(jié)點；的結(jié)點；n Q：圖中葉子結(jié)點有幾個？：圖中葉子結(jié)點有幾個？( )n 非終端結(jié)點非終端結(jié)點 度不為度不為0的結(jié)點；的結(jié)點；n Q：圖中非終端結(jié)點有幾個？：圖中非終端結(jié)點有幾個？( )3375第41頁ABDFECGHIJKMn 結(jié)點的層次結(jié)點的層次 樹中根結(jié)點的層次為樹中根結(jié)點的層次為1，根結(jié)點，根結(jié)點子樹的

7、根為第子樹的根為第2層，以此類推；層，以此類推；n Q：圖中結(jié)點：圖中結(jié)點F的層次？的層次？n 樹的深度樹的深度 樹中所有結(jié)點層次的最大值；樹中所有結(jié)點層次的最大值； Q：圖中樹的深度？圖中樹的深度？n 有序樹、無序樹有序樹、無序樹 如果樹中每棵子樹從左向右如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹。序樹，否則稱為無序樹。第42頁 定義：二叉樹是一種有序的樹形結(jié)構(gòu)。它與一般定義：二叉樹是一種有序的樹形結(jié)構(gòu)。它與一般樹形結(jié)構(gòu)的區(qū)別是：樹形結(jié)構(gòu)的區(qū)別是： 每個結(jié)點最多有兩棵子樹；每個結(jié)點最多有兩棵子樹； 子樹有左右之

8、分，次序不能任意顛倒。子樹有左右之分，次序不能任意顛倒。 二叉樹的二叉樹的5種基本形態(tài)種基本形態(tài)第43頁【性質(zhì)1】 在二叉樹的第i層上最多有2i-1個結(jié)點(i1)ABCDFEHGI=1 2i-I=1 2i-1=11=1I=2 2i-I=2 2i-1=21=2I=3 2i-I=3 2i-1=41=4第44頁【性質(zhì)2】深度為h的二叉樹最多有2h -1個結(jié)點(h 1)滿二叉樹：如果一個深度為k的二叉樹擁有2K-1個結(jié)點，則將它稱為滿二叉樹。完全二叉樹：有一棵深度為k，具有n個結(jié)點的二叉樹，若將它與一棵同深度的滿二叉樹中的所有結(jié)點按從上到下，從左到右的順序分別進行編號，且該二叉樹中的每個結(jié)點分別與滿二

9、叉樹中編號為1n的結(jié)點位置一一對應(yīng)，則稱這棵二叉樹為完全二叉樹。 第45頁1213 141589 10 114567123滿二叉樹滿二叉樹完全二叉樹完全二叉樹121389 10 114567123 完全二叉樹是滿二叉樹 滿二叉樹也是完全二叉樹葉子結(jié)點只能出現(xiàn)在最后兩層第46頁121389 10 11456123非完全二非完全二叉樹叉樹深度為深度為4的的完全二叉樹完全二叉樹8456712345671239121389 10 114123567第47頁【性質(zhì)3】二叉樹上葉子結(jié)點數(shù)比度為2的結(jié)點數(shù)多1ABCDFEHG度為2的結(jié)點葉子結(jié)點第48頁 N=N0+N1+N2 (1)除根結(jié)點外每個結(jié)點均有一個

10、分除根結(jié)點外每個結(jié)點均有一個分支進入支進入,設(shè)二叉樹中所有進入分設(shè)二叉樹中所有進入分支數(shù)為支數(shù)為M,總結(jié)點數(shù)總結(jié)點數(shù):N=M+1 (2)由于分支是由非葉子結(jié)點射入由于分支是由非葉子結(jié)點射入, 結(jié)點度為結(jié)點度為1射入射入1個分支個分支, 結(jié)點度為結(jié)點度為2射入射入2個分支個分支,故故M=N1+2N2 (3)將將(3)代入代入(2)式有式有N=N1+2N2+1 (4)比較比較(1)式與式與(4)有有N0+N1+N2=N1+2N2+1化簡后得化簡后得N0=N2+1即葉子結(jié)點數(shù)比結(jié)點度為即葉子結(jié)點數(shù)比結(jié)點度為2的結(jié)的結(jié)點數(shù)多點數(shù)多1.ABCDFEHGN0為結(jié)點度為為結(jié)點度為0,即葉子結(jié)點數(shù)即葉子結(jié)點數(shù)

11、 N1為結(jié)點度為為結(jié)點度為1的結(jié)點數(shù)的結(jié)點數(shù)N2為結(jié)點度為為結(jié)點度為2的結(jié)點數(shù)的結(jié)點數(shù)N為樹的總結(jié)點數(shù)為樹的總結(jié)點數(shù)N=N0+N1+N2N=3+2+2=8第49頁【性質(zhì)4】具有n個結(jié)點的完全二叉樹的深度為 log2n+1其中，log2n 的結(jié)果是不大于log2n的最大整數(shù)A BABCABCFE log22 +1=2 log25 +1=3取整的表示取整的表示第50頁u 一棵二叉樹第六層一棵二叉樹第六層(根結(jié)點為第一層根結(jié)點為第一層)的結(jié)點數(shù)最多的結(jié)點數(shù)最多為為 _ 個。個。u 某二叉樹中度為某二叉樹中度為2的結(jié)點有的結(jié)點有18個，則該二叉樹中有個，則該二叉樹中有_ 個葉子結(jié)點。個葉子結(jié)點。 u

12、在深度為在深度為5的完全二叉樹中，度為的完全二叉樹中，度為2的結(jié)點數(shù)最多的結(jié)點數(shù)最多為為 _ 。練習(xí)：練習(xí)：321915分析分析:完全二叉樹的特例完全二叉樹的特例 是滿二叉樹是滿二叉樹,總結(jié)點數(shù)為總結(jié)點數(shù)為 N=25-1=31 N=N0+N1+N2=N0+N2 N=N2+1+N2=2N2+12N2+1=31 故故N2=15 N0=N2+1=? 26-1=?為為0第51頁u 在計算機中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。在計算機中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。LlinkinfoRlink二叉樹的存儲結(jié)點的結(jié)構(gòu)二叉樹的存儲結(jié)點的結(jié)構(gòu)ABDCFGE A G E F B C Dt第52頁u 遍歷指不重復(fù)地訪

13、問二叉樹中的所有結(jié)遍歷指不重復(fù)地訪問二叉樹中的所有結(jié)點。點。u 二叉樹的遍歷的次序與樹型結(jié)構(gòu)上的大二叉樹的遍歷的次序與樹型結(jié)構(gòu)上的大多數(shù)運算有聯(lián)系。多數(shù)運算有聯(lián)系。u(1)先先(前前)序遍歷序遍歷(DLR)u 若二叉樹為空，則結(jié)束遍歷操作；否則若二叉樹為空，則結(jié)束遍歷操作；否則u訪問根結(jié)點；訪問根結(jié)點；u先序遍歷左子樹；先序遍歷左子樹；u先序遍歷右子樹。先序遍歷右子樹。ABCDFEHG第53頁(2)中序遍歷中序遍歷(LDR) 若二叉樹為空，則結(jié)束遍歷操作；否則若二叉樹為空，則結(jié)束遍歷操作；否則中序遍歷左子樹；中序遍歷左子樹；訪問根結(jié)點；訪問根結(jié)點；中序遍歷右子樹。中序遍歷右子樹。(3)后序遍歷

14、后序遍歷(LRD) 若二叉樹為空，則結(jié)束遍歷操作；否則若二叉樹為空，則結(jié)束遍歷操作；否則后序遍歷左子樹；后序遍歷左子樹；后序遍歷右子樹；后序遍歷右子樹；訪問根結(jié)點。訪問根結(jié)點。ABCDFEHG第54頁先序序列：ABDGCEFH中序序列：DGBAECHF后序序列：GDBEHFCAABCFHDEG下圖所示的二叉樹經(jīng)過三種遍歷得到的順序分別為？下圖所示的二叉樹經(jīng)過三種遍歷得到的順序分別為？練習(xí)：練習(xí)：第55頁u 查找是數(shù)據(jù)處理的重要內(nèi)容。查找是數(shù)據(jù)處理的重要內(nèi)容。u 查找指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找指定的元素，查找指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找指定的元素，該元素也稱關(guān)鍵字。該元素也稱關(guān)鍵字。u 若找到

15、了滿足條件的結(jié)點，稱查找成功；否則稱若找到了滿足條件的結(jié)點，稱查找成功；否則稱查找失敗。查找失敗。 u衡量一個查找算法的主要標(biāo)準(zhǔn)是查找過程中對關(guān)鍵衡量一個查找算法的主要標(biāo)準(zhǔn)是查找過程中對關(guān)鍵字進行的平均比較次數(shù)。字進行的平均比較次數(shù)。 u 通常根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，采用不同的查找方法：通常根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，采用不同的查找方法：u 順序查找順序查找u 二分查找二分查找第56頁u 順序查找是線性表中最簡單的查找方法。順序查找是線性表中最簡單的查找方法。u 順序查找的方法：從線性表的第一個元素開始，順序查找的方法：從線性表的第一個元素開始，依次將線性表中的元素與關(guān)鍵字進行比較，若相等，依次將線性表中

16、的元素與關(guān)鍵字進行比較，若相等，則查找成功；若將所有元素都與關(guān)鍵字進行了比較則查找成功；若將所有元素都與關(guān)鍵字進行了比較但不相等，則查找失敗。但不相等，則查找失敗。u 順序查找法的適用場合：順序查找法的適用場合：u 對線性表中元素的排列次序沒有要求；對線性表中元素的排列次序沒有要求；u 對線性表的存儲結(jié)構(gòu)沒有要求，鏈?zhǔn)浇Y(jié)構(gòu)和順序?qū)€性表的存儲結(jié)構(gòu)沒有要求，鏈?zhǔn)浇Y(jié)構(gòu)和順序結(jié)構(gòu)均可。結(jié)構(gòu)均可。u查找不成功的比較次數(shù)為查找不成功的比較次數(shù)為 N第57頁u 二分查找法是一種效率較高的查找方法，但是只適合順序存儲的有序表。查找不成功的比較次數(shù)為LOG2Nu二分查找的方法：首先將關(guān)鍵字與線性表中間位置的結(jié)

17、點比較，相等則查找成功；不相等則根據(jù)比較結(jié)果確定下一步查找應(yīng)在哪個子表中進行；重復(fù)上述過程，直至查找成功或子表長度為0。u 二分查找法的適用場合：u 線性表中的元素按關(guān)鍵字值遞增或遞減的次序排列；u 線性表采用順序存儲結(jié)構(gòu)。第58頁查找總結(jié)查找總結(jié)查找方法查找方法 最壞情況的比較最壞情況的比較次數(shù)次數(shù)使用條件使用條件N線性表中的元素值是無序線性表中的元素值是無序,也也可是有序的可是有序的;線性表中的元素線性表中的元素個數(shù)不多的情況個數(shù)不多的情況.二分查找二分查找log2N線性表中的元素按關(guān)鍵字值線性表中的元素按關(guān)鍵字值遞增或遞減的次序排列；線遞增或遞減的次序排列；線性表中的元素個數(shù)很多的情性表

18、中的元素個數(shù)很多的情況況.第59頁u 排序也是數(shù)據(jù)處理的重要內(nèi)容。u 排序指將一個無序序列整理成按關(guān)鍵字值遞增或遞減排列的有序序列。u 這里討論的排序方法，其排序?qū)ο笠话闶琼樞虼鎯Φ木€性表。 u 根據(jù)排序序列的規(guī)模以及數(shù)據(jù)處理的要求，可以采用不同的排序方法：u 冒泡排序u 選擇排序u 插入排序第60頁u 冒泡排序的方法：冒泡排序的方法：u 掃描整個線性表，逐次對相鄰的兩個元素進行比較，若為逆序，掃描整個線性表，逐次對相鄰的兩個元素進行比較，若為逆序，則交換；第一趟掃描的結(jié)果使最大的元素排到表的最后；則交換；第一趟掃描的結(jié)果使最大的元素排到表的最后；u 除最后一個元素，對剩余的元素重復(fù)上述過程，

19、將次大的數(shù)排到除最后一個元素，對剩余的元素重復(fù)上述過程，將次大的數(shù)排到表的倒數(shù)第二個位置；表的倒數(shù)第二個位置；u 重復(fù)上述過程；重復(fù)上述過程；u 對于長度為對于長度為n的線性表，冒泡排序需要對表掃描的線性表，冒泡排序需要對表掃描n-1遍。遍。u 在最壞的情況下，冒泡排序需要比較在最壞的情況下，冒泡排序需要比較n(n-1)/2次次第61頁冒泡排序的方法冒泡排序的方法u 設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為18，20，15，32，4，25），第一趟冒泡排序后的序列狀態(tài)如圖所示：u 18 20 15 32 4 25u 18 20 15 32 4 25u 18 15 20 32 4 25u 18 15 20 32

20、 4 25u 18 15 20 4 32 25u 18 15 20 4 25 32 最大數(shù)第62頁Q：第二趟冒泡排序后的結(jié)果是什么樣的？達到：第二趟冒泡排序后的結(jié)果是什么樣的？達到了最終的排序目標(biāo)嗎？一共需要多少次能夠最了最終的排序目標(biāo)嗎？一共需要多少次能夠最后成為有序序列？后成為有序序列？Q：你覺得冒泡排序的效率如何？如果是你，你：你覺得冒泡排序的效率如何？如果是你，你會用什么方法來排序？會用什么方法來排序？ 冒泡排序比較簡單，當(dāng)初始序列基本有序時，冒泡排序比較簡單，當(dāng)初始序列基本有序時，冒泡排序有較高的效率，反之效率較低。冒泡排序有較高的效率，反之效率較低。冒泡排序終止條件冒泡排序終止條件

21、: 本趟排序未發(fā)生交換，終止排序算法本趟排序未發(fā)生交換，終止排序算法 第63頁初始初始 第一趟第一趟 第二趟第二趟 第三趟第三趟 第四趟第四趟 第五趟第五趟序列序列 排序后排序后 排序后排序后 排序后排序后 排序后排序后 排序后排序后26 18 18 18 18 918 26 26 26 9 1532 32 32 9 15 1854 47 9 15 2647 9 15 329 15 4715 54設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為26,18,32,54,47,9,15 )第64頁u 選擇排序的方法：選擇排序的方法：u掃描整個線性表，從中找出最小的元素，與第一個元掃描整個線性表，從中找出最小的元素，與第一

22、個元素交換；素交換；u除第一個元素，對剩下的子表采用相同的方法找出次除第一個元素，對剩下的子表采用相同的方法找出次小的數(shù)，與第二個數(shù)交換；小的數(shù)，與第二個數(shù)交換；u重復(fù)上述過程；重復(fù)上述過程；u對于長度為對于長度為n的線性表，選擇排序需要對表掃描的線性表，選擇排序需要對表掃描n-1遍。遍。u在最壞的情況下，選擇排序需要比較在最壞的情況下，選擇排序需要比較n(n-1)/2次次第65頁選擇排序方法：先找出表中關(guān)鍵字最小的元素，將選擇排序方法：先找出表中關(guān)鍵字最小的元素，將其與第一個元素交換，然后在其余元素中找出關(guān)其與第一個元素交換，然后在其余元素中找出關(guān)鍵字最小的元素，將其與第二個元素交換，依次鍵

23、字最小的元素，將其與第二個元素交換，依次類推，最終所有關(guān)鍵字按從小到大排列。類推，最終所有關(guān)鍵字按從小到大排列。例：設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為例：設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為15，14，22，30，37，11），每一趟排序后的序列狀態(tài)如圖所示：），每一趟排序后的序列狀態(tài)如圖所示：第66頁u初態(tài)： 15，14，22，30，37，15，11u第一趟： 11 14，22，30，37，15，15u第二趟： 11，14 22，30，37，15，15u第三趟： 11，14，15 30，37，22，15u第四趟： 11，14，15，15 37，22，30u第五趟： 11，14，15，15，22 37，30u第六趟： 11，14，15，15