c語言程序設(shè)計與項目實踐第18章(完整版)

　　

【正文】 近 10倍。第 18章 C語言常用算法 ? 本章的學(xué)習(xí)重點 ◆ 了解起泡排序、選擇排序及合并排序算法 ◆ 掌握快速排序算法 ◆ 掌握折半查找算法 ◆ 了解二叉樹的概念及其簡單操作 什么是算法 算法的程序公式： 程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法 ? 1．計算機算法 計算機算法主要有兩類：數(shù)值運算算法和非數(shù)值運算算法。數(shù)學(xué)運算中，可以使用和差算法計算這樣的加和運算，公式為： sum = n*(a1+an)/2 使用 C語言實現(xiàn)的程序為： 01 int sum = 0。對于人員姓名，可以按照首字母前后順序排序，也可以按照姓名長度排序等等。其一般表達函數(shù)為： 01 void BubbleSort(dataList r[], int n) 02 { 03 int loop1, loop2, temp。 13 } 14 } 15 } 16 } 起泡排序 ? 范例 設(shè)計一段起泡排序算法的排序程序，將下面幾個國家到 2022年為止打入世界杯決賽圈的次數(shù)，按從大到小排列，相同次數(shù)的隨機排列。loop1=len1。最簡單的合并是將兩個有序數(shù)組合并成一個有序數(shù)組。 07 MergeSort(array, firstIndex, midIndex)。所謂查找，就是要在一組數(shù)據(jù)中找出某個特定的元素，若找到，則執(zhí)行某種預(yù)定的動作，若未找到，則輸出提示信息，并執(zhí)行相應(yīng)的操作。 i++) //遍歷待查找數(shù)組 02 { 03 if(array[i]= =key) //關(guān)鍵參數(shù)比較與判斷 04 { 05 break。 //選擇中間位置 07 if(KeyParameter= = InputTable[mid]) //判斷是否查找到所需元素 08 { 09 return mid。每個結(jié)點表示實際應(yīng)用中的一個數(shù)據(jù)元素。 P a r e n t F i e l d D a t a F i e l d L e f t C h i l d R i g h t C h i l d 可以使用結(jié)構(gòu)體定義上述二叉樹結(jié)點，定義格式如下： 01 struct TreeNode 02 { 03 struct TreeNode *parent。 上述代碼定義了一個 TreeNode類型的結(jié)構(gòu)體數(shù)組 BinTree，用于構(gòu)建含有 100個結(jié)點的二叉樹。 07 } 08 else 09 { 10 printf(“二叉樹不為空 \n”)。 //訪問根結(jié)點 11 preOrderTreversingTree(InBinTreeleftchild)。//中序遍歷左子樹 11 printf( %d, InBinTreedata)。 //后序遍歷左子樹 11 LastOrderTreversingTree (InBinTreerightchild)。 09 } 10 else 11 { 12 if(InBinTreedata == Indata) 13 { 14 return InBinTree。 07 pNodeleftchild=NULL。當二叉樹根結(jié)點為要刪除的結(jié)點且左子樹為空時，直接刪除根結(jié)點，將右子樹作為保留二叉樹。 ? 2．技術(shù)應(yīng)用 將兩個有序數(shù)組進行合并，按照有序數(shù)組合并的基本思想，第一次比較結(jié)果如圖所示，圖中 i為數(shù)組 array1的元素指示下標， j為數(shù)組array2的元素指示下標， k為數(shù)組 arrayMerge的元素指示下標。 進行第二次比較之后，將 array1中的值 3插入數(shù)組 arrayMerge中，下標 i和 k分別將指向下一個元素。當二叉樹僅有一個結(jié)點且為要刪除的結(jié)點時，刪除該結(jié)點，并結(jié)束。 09 InBinTree=pNode。 //返回查找到的結(jié)點 21 } 22 if(pTree = SearchBinTree(InBinTreerightchild, Indata)) //遍歷右子樹 23 { 24 return pTree。//訪問根結(jié)點 13 } 14 return。 //中序遍歷右子樹 13 } 14 return。//先序遍歷右子樹 13 } 14 return。 12 } 13 } 二叉樹的簡單操作 二叉樹的遍歷分為先序遍歷、中序遍歷和后序遍歷三種。 pBinTree = (struct TreeNode *)malloc(100*sizeof(struct TreeNode))。 //數(shù)據(jù)域 05 struct TreeNode *leftchild。如圖所示為一個典型的樹形結(jié)構(gòu)。 //移動高位下標 14 } 15 else 16 { 17 low = mid+1。 11 } 12 else //查找成功分支 13 { 14 printf(“找到對應(yīng)元素，下標為： %d\n”, i)。 順序查找算法 順序查找的基本思想是：從元素序列開始位置，逐個比較序列中的元素與被查找關(guān)鍵元素，若序列中某元素與關(guān)鍵元素相等，則查找成功，否則，繼續(xù)查找直到找到對應(yīng)元素。 09 arrayMergeFun(array, firstIndex, midIndex, lastIndex)。 ? 1．兩個數(shù)組合并排序 將兩個有序數(shù)組 Array1和 Array2進行排序并放到另一個數(shù)組ArrayMerge的基本思想為： 首先，在 Array1和 Array2數(shù)組中各取第一個元素進行比較，將小的元素放入數(shù)組 ArrayMerge； 然后，取較小的元素所在數(shù)組的下一個元素與另一數(shù)組中上次比較后較大的元素比較，重復(fù)上述比較過程，直到某個數(shù)組被先排完； 最后，將另一個數(shù)組中剩余元素拷貝到數(shù)組 ArrayMerge。loop2len。 選擇排序 選擇排序的基本思想是：首先制定排序規(guī)則（例如按照從小到大排序原則），排序過程中首先在未排序序列中找到最小值，放在排序序列的起始位置，隨后，逐趟從余下未排序的數(shù)值中逐次尋找最小值，直到