數(shù)組應(yīng)用的技巧與方法-展示頁
2024-11-05 15:46本頁面
【正文】 下趟沒有交換發(fā)生，還可以提前結(jié)束排序。 21， 25， 49， 25*， 16， 08 21， 25， 25*， 16， 08 ， 49 21， 25， 16， 08 ， 25*， 49 21， 16， 08 ， 25， 25*， 49 16， 08 ， 21， 25， 25*， 49 08， 16， 21， 25， 25*， 49 初態(tài)： 第 1趟 第 2趟 第 3趟 第 4趟 第 5趟 12 冒泡排序法關(guān)鍵程序 ? int i,j,minj,t。i N1。j N1。 a[i] = a[j]。 } } 13 選擇排序（快速排序） ? 算法：首先找到數(shù)據(jù)清單中的最小的數(shù)據(jù)，然后將這個數(shù)據(jù)同第一個數(shù)據(jù)交換位置；接下來找第二小的數(shù)據(jù)，再將其同第二個數(shù)據(jù)交換位置，以此類推。 ? 第 2次，在數(shù)組 a的后 n1個數(shù)據(jù)（即出去已經(jīng)選擇的最小者的各數(shù)據(jù)）中，經(jīng)過類似的處理后，可以使得數(shù)組 a的第 2個數(shù)據(jù)為第 2小。 ? 第 n1次，在數(shù)組后的 2個數(shù)據(jù)中，經(jīng)過類似處理后，總可以使數(shù)組a的第 n1個數(shù)據(jù)為第 n1小。 14 關(guān)于選擇排序 ? 算法： N元數(shù)組 a[0]~a[N1]由小到大排序： 第 0步 :找到 a[0]~a[N1]中的最小值元素與 a[0]交換 。 … 第 N2步 :找到 a[N2]~a[N1]中的最小值元素與 a[N2]交換。 15 選擇排序法程序 ? int i,j,minj,t。i N1。 //有什么作用？ for (j = i + 1。j++) if (a[j] a[minj]) minj = j。 a[i] = a[minj]。 } } 減少了數(shù)據(jù)交換的次數(shù)！ 16 查找算法 ? 查找之前要求排序，不然無章可查 ? 順序查找 ? 按照排好序的順序進行查找，比如對一個升序排列的數(shù)組中，找到第一個大于需要查找的數(shù) ? 折半查找（二分查找） 17 折半查找（二分查找） 先給數(shù)據(jù)排序 （例如按升序排好），形成有序表 ，然后再將 key與正中元素相比，若 key小，則縮小至右半部內(nèi)查找；再取其中值比較，每次縮小 1/2的范圍，直到查找成功或失敗為止。 18 ① 先設(shè)定 3個輔助標(biāo)志 : low,high,mid， 顯然有： mid= ?(low+high)/2? ② 運算步驟 ： （ key為要查找的值 ） (1) low =1,high =11 ,mid =6 ，待查范圍是 [1,11]； (2) 若 elem[mid] key，說明 key?[ mid+1,high] ， 則令： low =mid+1。重算 mid ； (4)若 elem[ mid ] = key，說明查找成功，元素序號 =mid。 //置當(dāng)前查找區(qū)間上、下界的初值 while(low=high) //當(dāng)前查找區(qū)間 R[low..high]非空 { mid=low+((highlow)/2)。 //查找成功返回 if(R[mid]Key) high=mid1。 //繼續(xù)在 R[mid+1..high]中查找 } return 1。i3。 ? for (j=0。j++){ ? if (a[i][j]max){ ? max=a[i][j]。 /*求出行中最大數(shù) */ ? } ? } ? for(k=0,flag1=1。amp。k++){ ? if (maxa[k][j]) ? flag1=0。 ? flag2=1。 ? } 22 將一個數(shù)組逆序轉(zhuǎn)換 例如 1， 2， 3， 4， 5,變?yōu)?5， 4， 3， 2， 1 ? 算法分析：用第一個與最后一個交換。 printf(\n original array:\n)。 iN。a[i])。 iN/2。 a[i] = a[Ni1]。 } printf(\n sorted array:\n)。 iN。 } 24 關(guān)于二維數(shù)組的問題 （雙下標(biāo)的應(yīng)用） ? 涉及到矩陣的問題，一般使用二維數(shù)組加以解決 ? 下面舉幾個稍微復(fù)雜一點的例子，也是某些考試（比如高級程序員）經(jīng)?？嫉降碾y題 ? 蛇行矩陣問題 ? 魔方陣問題 ? 矩陣旋轉(zhuǎn)問題 25 蛇行方陣問題 輸入： N=4 N=7 輸出： 1 3 4 10 1 3 4 10 11 21 22 2 5 9 11 2 5 9 12 20 23 34 6 8 12 15 6 8 13 19 24 33 35 7 13 14 16 7 14 18 25 32 36 43 15 17 26 31 37 42 44 16 27 30 38 41 45 48 28 29 39 40 46 47 49 1 3 4 10 2 5 9 11 6 8 12 15 7 13 14 16 26 蛇行矩陣 ? 將自然數(shù) 1,2,… ,N*N,逐個順序插入方陣中適當(dāng)?shù)奈恢?，這個過程沿斜列進行。同時方陣又可分為上三角與下三角（含對角線）每一斜列上元素個數(shù)為 i+1個；下三角每一斜列上元素個數(shù)為 2ni+1個。 66656463626160565554535251504645444342414036353433323130
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1