基于選擇排序方法的類(lèi)模板設(shè)計(jì)與實(shí)現(xiàn)c課程設(shè)計(jì)(編輯修改稿)
2025-06-09 23:42 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 行內(nèi)部聲明，函數(shù)體在類(lèi)體外定義 類(lèi)的實(shí)現(xiàn)//簡(jiǎn)單選擇排序template class Typevoid SortType::SelectSort(Type ar[]) { int i,j。 Type t。 for(i=1。ilen。i++) for(j=i+1。j=len。j++) if(array[i]array[j]) {t=array[i]。array[i]=array[j]。array[j]=t。}}5template class Typevoid SortType::tree_select_sort(Type arr[],int n) //樹(shù)形選擇排序{Type tree[M]。 // 樹(shù) int baseSize。 // 當(dāng) n 是 2 的冪次時(shí),baseSize 是 n, 當(dāng) n 不是時(shí),baseSize 是大于 n 的最小的 2 的冪次 // 就是構(gòu)造成滿二叉樹(shù)的最下層的大小，即葉子數(shù) int i。Type max。 // 最大值 int maxIndex。 // 最大數(shù)的下標(biāo) int treeSize。 // 最終這棵樹(shù)會(huì)達(dá)到的大小 baseSize = 1。while (baseSize n){ baseSize *= 2。}treeSize = baseSize * 2 1。//滿二叉樹(shù)的所有結(jié)點(diǎn)個(gè)數(shù)等于葉子數(shù)的 2 倍減一for (i = 0。i n。i++) // 從數(shù)組的后面部分開(kāi)始填充, 不使用 tree[0]{ tree[treeSize i] = arr[i]。}for (。i baseSize。i++) // 用 MIN_VALUE 填充 tree,直到一共有 baseSize個(gè){ tree[treeSize i] = MIN_VALUE。}// 構(gòu)造一棵樹(shù) for (i = treeSize。i 1。i = 2)6{// 以 arr[i]和 arr[i + 1]為子結(jié)點(diǎn)的數(shù)的根是 arr[i]和 arr[i + 1]中的較大者 tree[i / 2] = (tree[i] tree[i 1] ? tree[i] : tree[i 1])。}n = n 1。 //此時(shí)的 n 表示當(dāng)前 tree[1]應(yīng)該放到 arr 中的位置 // 不斷把樹(shù)中值為最大值的結(jié)點(diǎn)移走,直到 n 的值為1 while (n != 1){ max = tree[1]。 arr[n] = max。 maxIndex = treeSize。// 在葉子上找到最大值對(duì)應(yīng)的下標(biāo) while (tree[maxIndex] != max) { maxIndex。 } tree[maxIndex] = MIN_VALUE。 // 沿著葉子上的結(jié)點(diǎn)到根的路徑更新 while (maxIndex 1) // 當(dāng)結(jié)點(diǎn)還有父結(jié)點(diǎn)時(shí) { if (maxIndex % 2 == 0) // 如果值為最大值的結(jié)點(diǎn)是左子結(jié)點(diǎn) { // 用子結(jié)點(diǎn)中較大值代替父結(jié)點(diǎn) tree[maxIndex / 2] = (tree[maxIndex] tree[maxIndex + 1] ? tree[maxIndex] : tree[maxIndex + 1])。} else // 如果不是左子結(jié)點(diǎn) {7 // 用子結(jié)點(diǎn)中較大值代替父結(jié)點(diǎn) tree[maxIndex / 2] = (tree[maxIndex] tree[maxIndex 1] ? tree[maxIndex] : tree[maxIndex 1])。} maxIndex /= 2。 // 繼續(xù)處理父結(jié)點(diǎn) }}}template class Typevoid SortType::AdjustTree(Type ar[],int k,int n) //調(diào)整堆{ int i,j。 i=k。 j=2*i。 //arrau[j]是 array[i]的左孩子 Type temp=array[i]。 while(j=n) {if(jnamp。amp。array[j]array[j+1]) //若有孩子較大，把 j 指向右孩子 j=j+1。 if(temparray[j]) { array[i]=array[j]。 //array[j]調(diào)整到雙親結(jié)點(diǎn) i=j。 j=2*i。 } else break。 } array[i]=temp。}template class Type8void SortType::HeapSort(Type ar[]) //堆排序{ int i。 Type t。 for(i=len/2。i=1。i) //循環(huán)建立初始堆 AdjustTree(array,i,len)。 for(i=len。i=2。i) //進(jìn)行 n1 次循環(huán)，完成堆排序 {t=array[i]。 array[i]=array[1]。 array[1]=t。 AdjustTree(array,1,i1)。 }}templateclass Typevoid SortType::write() //輸入數(shù)組{int i,l。printf(請(qǐng)輸入數(shù)組長(zhǎng)度:)。scanf(%d,amp。l)。len=l。printf(請(qǐng)輸入數(shù)組元素:\n)。for(i=1。i=l。i++)cinarray[i]。}templateclass Typevoid SortType::print() //輸出數(shù)組{int i。 printf(排序后的數(shù)組為:\n)。 for(i=1。i=l
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1