c語言程序設計與項目實踐第18章(已修改)
2025-01-21 01:07 本頁面
【正文】 第 18章 C語言常用算法 ? 本章的學習重點 ◆ 了解起泡排序、選擇排序及合并排序算法 ◆ 掌握快速排序算法 ◆ 掌握折半查找算法 ◆ 了解二叉樹的概念及其簡單操作 什么是算法 算法的程序公式： 程序 = 數(shù)據(jù)結構 + 算法 ? 1．計算機算法 計算機算法主要有兩類：數(shù)值運算算法和非數(shù)值運算算法。 ? 2．算法的程序實現(xiàn) 使用程序實現(xiàn)算法，應做到程序簡潔明了，易讀性強，執(zhí)行效率高。 例如，要實現(xiàn)下面的公式的加和運算： 1+3+5+7+…… +99+100 對于這樣的累加計算，可以使用下面的 C語言程序實現(xiàn)： 01 int loop = 0, sum = 0。 02 for(loop=1。loop100。loop=loop+2) 03 { 04 sum = sum + loop。 05 } 06 sum = sum + 100。 什么是算法 如果利用數(shù)學算法，可以使程序效率提高近 10倍。數(shù)學運算中，可以使用和差算法計算這樣的加和運算，公式為： sum = n*(a1+an)/2 使用 C語言實現(xiàn)的程序為： 01 int sum = 0。 02 sum = 49 * (99 + 1) / 。 03 sum = sum +100。 ? 3．非數(shù)值算法 C語言中最常用的非數(shù)值算法主要包括排序算法和查找算法。在這些算法的理論設計中，有時需要用到某些數(shù)學模型，通常稱為數(shù)據(jù)結構。典型的數(shù)據(jù)結構類型主要有鏈表、二叉樹、圖等。 排序算法 排序，是指將一系列數(shù)據(jù)按照某種規(guī)則按照一定的順序進行排列，以符合實際處理需求的操作過程。 例如，對于一組數(shù)據(jù)，可以按照由大到小的順序排序，也可以按照由小到大的順序排序。對于人員姓名，可以按照首字母前后順序排序，也可以按照姓名長度排序等等。一個合理的排序算法可以使程序執(zhí)行效率提高，程序健壯性增強。 起泡排序 起泡排序也叫冒泡排序，它的一般實現(xiàn)規(guī)則為：首先制定排序規(guī)則，然后，依次兩兩比較待排序的數(shù)據(jù)，若不符合排序規(guī)則，則進行交換，然后依次比較下去，直到全部元素排列有序為止。 例如，有如下一組數(shù)據(jù) {85， 279， 948， 521， 616， 888}，按照從大到小的順序排列，使用起泡法排序，首先執(zhí)行第一趟交換，過程如圖所示。 2 7 96 1 68 8 89 4 85 2 18 58 56 1 68 8 89 4 85 2 12 7 99 4 86 1 68 8 88 55 2 12 7 99 4 86 1 68 8 85 2 18 52 7 99 4 88 58 8 85 2 16 1 62 7 99 4 88 8 88 55 2 16 1 62 7 9第一次交換第三次交換第一趟交換結果第四次交換第五次交換第六次交換 起泡排序 在第一趟數(shù)據(jù)比較的基礎上，繼續(xù)進行第二趟數(shù)據(jù)比較。第二趟數(shù)據(jù)比較共執(zhí)行 4次比較與交換，執(zhí)行完畢后數(shù)據(jù)順序為 {948， 521，616， 888， 279， 85}，次小值 279將被放到倒數(shù)第二的位置，如圖所示。 9 4 88 8 88 55 2 16 1 62 7 9第一次交換第二次交換第三次交換第四次交換2 7 98 8 88 55 2 16 1 69 4 85 2 18 8 88 52 7 96 1 69 4 85 2 18 8 88 56 1 62 7 99 4 85 2 12 7 98 56 1 68 8 89 4 8第二趟交換結果 起泡排序 經(jīng)過五趟數(shù)據(jù)比較與交換后，數(shù)據(jù)順序變?yōu)橛纱蟮叫〉挠行蛐蛄?。從而實現(xiàn)了使用起泡法排序的目的。其一般表達函數(shù)為： 01 void BubbleSort(dataList r[], int n) 02 { 03 int loop1, loop2, temp。 04 for(loop1=1。loop1=n1。loop1++) //外層循環(huán)，控制循環(huán)比較趟數(shù) 05 { 06 for(loop2=n。loop2=loop1+1。loop2) //內(nèi)層循環(huán)，控制比較位置 07 { 08 if(r[loop2] r[loop21]) //判斷是否符合交換規(guī)則 09 { 10 temp=r[loop2]。 11 r[loop2]=r[loop21]。 12 r[loop21]=temp。 13 } 14 } 15 } 16 } 起泡排序 ? 范例 設計一段起泡排序算法的排序程序，將下面幾個國家到 2022年為止打入世界杯決賽圈的次數(shù)，按從大到小排列，相同次數(shù)的隨機排列。國家及進入世界杯決賽圈次數(shù)：法國（ 13），西班牙（ 13），荷蘭（ 9），美國（ 9），德國（ 13），巴西（ 19），英格蘭（ 13），阿根廷（ 15），中國（ 1），澳大利亞（ 3），希臘（ 2），意大利（ 17），喀麥隆（ 6）。 選擇排序 選擇排序的基本思想是：首先制定排序規(guī)則（例如按照從小到大排序原則），排序過程中首先在未排序序列中找到最小值，放在排序序列的起始位置，隨后，逐趟從余下未排序的數(shù)值中逐次尋找最小值，直到整個序列有序為止。 例如，有如下隨機序列 {6,18,45,3,77,88}，將該序列從小到大排序，使用選擇排序算法過程如下： 首先，進行第一趟排序，找出其中最小的數(shù)，如圖所示。 1 87 7 8 84 5361 87 7 8 84 5361 87 7 8 84 5361 87 7 8 84 5631 87 7 8 84 5631 87 734 56 8 8第一
法律信息相關推薦
鄂ICP備17016276號-1