c語(yǔ)言程序設(shè)計(jì)與項(xiàng)目實(shí)踐第18章(編輯修改稿)
2025-02-05 01:07 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 應(yīng)的操作。查找的算法很多，常用的查找算法是順序查找算法和折半查找算法。 順序查找算法 順序查找的基本思想是：從元素序列開(kāi)始位置，逐個(gè)比較序列中的元素與被查找關(guān)鍵元素，若序列中某元素與關(guān)鍵元素相等，則查找成功，否則，繼續(xù)查找直到找到對(duì)應(yīng)元素。若直到最后一個(gè)序列元素仍未找到，則該序列中沒(méi)有與關(guān)鍵元素相匹配的數(shù)據(jù)，查找失敗。 例如，有數(shù)組 array[10]={101, 80, 96, 11458, , 495, 6174, 705, 56, }，要在該數(shù)組中查找關(guān)鍵元素 key=56，并返回其數(shù)組下標(biāo)位置。則可以定義遍歷變量 i，然后順次遍歷數(shù)組元素，直到找到該元素值為止。查找循環(huán)代碼如下： 01 for(i=0。 i10。 i++) //遍歷待查找數(shù)組 02 { 03 if(array[i]= =key) //關(guān)鍵參數(shù)比較與判斷 04 { 05 break。 06 } 07 } 08 if(10 = =i) //判斷是否查找成功，若部成功，打印信息 09 { 10 printf(“查找失敗，未找到對(duì)應(yīng)元素 \n”)。 11 } 12 else //查找成功分支 13 { 14 printf(“找到對(duì)應(yīng)元素，下標(biāo)為： %d\n”, i)。 15 } 順序查找算法 ? 范例 數(shù)組 MobileCustom[7][12]中保存著一周內(nèi)某地區(qū)從早 6點(diǎn)到晚 6點(diǎn)之間移動(dòng)話務(wù)接入量，每 1小時(shí)統(tǒng)計(jì)一次，使用順序查找算法，找出話務(wù)量為 2022次的日期及時(shí)段信息。 折半查找算法 折半查找的基本思想為：首先，將待查找的有序序列中間位置元素與要查找的關(guān)鍵元素比較，如果兩者相等，則查找成功，否則，利用中間位置的記錄將序列分成前、后兩個(gè)子序列，若中間位置元素大于要查找的關(guān)鍵元素，則進(jìn)一步查找前一子序列，否則進(jìn)一步查找后一子序列。 [ 9 8 5 1 1 4 0 1 1 0 5 2 1 9 9 1 9 9 3 1 0 2 4 2 0 1 0 2 0 4 8 ]l o w k e y = 2 0 1 0第 一 趟 比 較 ， l o w 將 移 到 m i d + 1 的 位 置h i g hm i d[ 9 8 5 1 1 4 0 1 1 0 5 2 1 9 9 1 9 9 3 1 0 2 4 2 0 1 0 2 0 4 8 ]l o w k e y = 2 0 1 0h i g hm i d[ 9 8 5 1 1 4 0 1 1 0 5 2 1 9 9 1 9 9 3 1 0 2 4 2 0 1 0 2 0 4 8 ]l o wm i d = = k e y = 2 0 1 0h i g hm i d第 二 趟 比 較 ， l o w 將 移 到 m i d + 1 的 位 置第 三 趟 比 較 ， 找 到 所 查 元 素 例如，有如下有序序列array[10]={985， 114， 0，110， 521， 991， 993， 1024，2022， 2048}，要查找關(guān)鍵元素 2022，則首先需要定位序列的中間位置，然后進(jìn)一步判斷是否需要進(jìn)行下一步查找，如圖所示為折半查找過(guò)程。 折半查找算法 折半查找的一般表達(dá)函數(shù)如下： 01 int BinarySearch(int InputTable[N], int KeyParameter) 02 { 03 int low=0, high=N1,mid=0。 04 while(lowhigh) //判斷是否查找結(jié)束 05 { 06 mid=(low+high)/2。 //選擇中間位置 07 if(KeyParameter= = InputTable[mid]) //判斷是否查找到所需元素 08 { 09 return mid。 //返回查找到的位置 10 } 11 else if(InputTable[mid]KeyParameter) //判斷當(dāng)前位置大于或小于要查找元素 12 { 13 high = mid1。 //移動(dòng)高位下標(biāo) 14 } 15 else 16 { 17 low = mid+1。 //移動(dòng)低位下標(biāo) 18 } 19 } 20 printf(“未查找到要查找的元素，查找失敗 \n”)。 21 } 二叉樹(shù) 二叉樹(shù)是數(shù)據(jù)結(jié)構(gòu)的典型代表之一，它是一類非常重要的非線性數(shù)據(jù)結(jié)構(gòu)。二叉樹(shù)在數(shù)據(jù)庫(kù)系統(tǒng)和計(jì)算機(jī)語(yǔ)法結(jié)構(gòu)設(shè)計(jì)中應(yīng)用廣泛，此外，數(shù)據(jù)序列的排序和查找也廣泛應(yīng)用二叉樹(shù)結(jié)構(gòu)設(shè)計(jì)。由于二叉樹(shù)常被用于數(shù)據(jù)查找，因此，二叉樹(shù)又被稱為二叉查找樹(shù)和二叉堆。 二叉樹(shù)的結(jié)構(gòu) ? 1．樹(shù)的定義 樹(shù)形結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)中一種的數(shù)據(jù)結(jié)構(gòu)，它是由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限集合。每個(gè)結(jié)點(diǎn)表示實(shí)際應(yīng)用中的一個(gè)數(shù)據(jù)元素。對(duì)于任何一個(gè)包含 n個(gè)結(jié)點(diǎn)的非空樹(shù)，都有如下特點(diǎn)： 1）有且僅有一個(gè)稱為根的結(jié)點(diǎn)（ root） 2）若 n1，則剩余結(jié)點(diǎn)被可以被分成 m個(gè)互不相交的集合 TreeTree Tree …… Treem，這些集合被稱為子樹(shù)（ SubTree）。如圖所示為一個(gè)典型的樹(shù)形結(jié)構(gòu)。 AB C DEF GHI J K L NM 二叉樹(shù)的結(jié)構(gòu) ? 2．二叉樹(shù)的定義 二叉樹(shù)是一種特殊的樹(shù)形結(jié)構(gòu)，其特點(diǎn)是每個(gè)結(jié)點(diǎn)至多有兩個(gè)子樹(shù)，即每個(gè)結(jié)點(diǎn)中最多有兩個(gè)孩子結(jié)點(diǎn)，并且二叉樹(shù)的結(jié)點(diǎn)有左右之分，也就是說(shuō)，二叉樹(shù)是有序的。如圖所示為幾種不同的二叉樹(shù)結(jié)構(gòu)。 AB CABABABCD E FG( a ) ( b ) ( c ) ( d )( a )右 子 樹(shù) 為 空 的 二 叉 樹(shù)( b )三 個(gè) 結(jié) 點(diǎn) 的 滿 二 叉 樹(shù)( c )七 個(gè) 結(jié) 點(diǎn) 的 滿 二 叉 樹(shù)( d )左 子 樹(shù) 為 空 的 二 叉 樹(shù) C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的二叉樹(shù) ? 1．二叉樹(shù)結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu) 二叉樹(shù)結(jié)點(diǎn)至少需要三個(gè)向其他結(jié)點(diǎn)的索引才能滿足整個(gè)二叉樹(shù)的結(jié)構(gòu)。如圖所示為一個(gè)即有雙親結(jié)點(diǎn)又有孩子結(jié)點(diǎn)的二叉樹(shù)結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)索引示意圖。 指 向 雙 親 結(jié) 點(diǎn)指向左孩子結(jié)點(diǎn)指向右孩子結(jié)點(diǎn)數(shù) 據(jù) 域
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1