【培訓(xùn)】數(shù)組應(yīng)用的技巧與方法ppt課件

1、數(shù)組運用的技巧與方法1附加：計數(shù)器、累加器、累乘器計數(shù)器int count;while() count +累加器int s;for() a=; s=s+a;累乘器int s;for() a=; s=s*a;2關(guān)于一維數(shù)組的問題普通一維數(shù)組所涉及的主要問題有排序插入刪除查找分類統(tǒng)計涉及到一些算法，我們經(jīng)過例題引見一部分詳細問題的解題算法的思緒要靠本人漸漸去領(lǐng)會31. 什么是排序？ 將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律依次陳列起來。 2. 排序的目的是什么？存放在數(shù)據(jù)表中按關(guān)鍵字排序3.排序算法的好壞如何衡量？時間效率排序速度即排序所破費的全部比較次數(shù)空間效率占內(nèi)存輔助空間的大小穩(wěn)定性假設(shè)兩個記錄A和

2、B的關(guān)鍵字值相等，但排序后A、B的先后次序堅持不變，那么稱這種排序算法是穩(wěn)定的。 便于查找！4排序算法插入排序直接插入排序折半插入排序表插入排序希爾排序交換排序冒泡排序快速排序不穩(wěn)定選擇排序歸并排序基數(shù)排序5插入排序插入排序的根本思想是： 每步將一個待排序的對象，按其關(guān)鍵碼大小，插入到前面曾經(jīng)排好序的一組對象的適當(dāng)位置上，直到對象全部插入為止。簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。6直接插入排序新元素插入到哪里？例1：關(guān)鍵字序列T=13，6，3，31，9，27，5，11， 請寫出直接插入排序的中間過程序列?！?3】, 6, 3, 31, 9, 27, 5, 11【6, 13】,

3、3, 31, 9, 27, 5, 11【3, 6, 13】, 31, 9, 27, 5, 11【3, 6, 13，31】, 9, 27, 5, 11【3, 6, 9, 13，31】, 27, 5, 11【3, 6, 9, 13，27, 31】, 5, 11【3, 5, 6, 9, 13，27, 31】, 11【3, 5, 6, 9, 11，13，27, 31】 在已構(gòu)成的有序表中線性查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。最簡單的排序法！7交換排序 兩兩比較待排序記錄的關(guān)鍵碼，假設(shè)發(fā)生逆序即陳列順序與排序后的次序正好相反，那么交換之，直到一切記錄都排好序為止。交換排序的主要算法有：

4、 1) 冒泡排序 2) 快速排序交換排序的根本思想是：8 冒泡排序根本思緒：每趟不斷將記錄兩兩比較，并按“前小后大或“前大后小規(guī)那么交換。優(yōu)點：每趟終了時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提早終了排序。前提：順序存儲構(gòu)造 例：關(guān)鍵字序列 T=(21，25，49，25*，16，08，請寫出冒泡排序的詳細實現(xiàn)過程。21，25，49， 25*，16， 0821，25，25*，16， 08 ， 4921，25， 16， 08 ，25*，4921，16， 08 ，25， 25*，4916，08 ，21， 25， 25*，4908，16， 21， 2

5、5， 25*，49初態(tài)：第1趟第2趟第3趟第4趟第5趟9選擇排序算法：首先找到數(shù)據(jù)清單中的最小的數(shù)據(jù)，然后將這個數(shù)據(jù)同第一個數(shù)據(jù)交換位置；接下來找第二小的數(shù)據(jù)，再將其同第二個數(shù)據(jù)交換位置，以此類推。第1次，在數(shù)組a的n個數(shù)據(jù)中選出其小者只標(biāo)志其所在位置，假設(shè)它不在其位置即其下標(biāo)不等于1那么與第一個數(shù)據(jù)進展交換只需交換一次，經(jīng)過本次處置后，總可以使得數(shù)組a的第1個數(shù)據(jù)為第1小。第2次，在數(shù)組a的后n-1個數(shù)據(jù)即出去曾經(jīng)選擇的最小者的各數(shù)據(jù)中，經(jīng)過類似的處置后，可以使得數(shù)組a的第2個數(shù)據(jù)為第2小。第i次，在數(shù)組a后的n-i+1個數(shù)據(jù)中，經(jīng)過類似選擇處置后，數(shù)組a的第i個數(shù)據(jù)為第i小。第n-1次，在

6、數(shù)組后的2個數(shù)據(jù)中，經(jīng)過類似處置后，總可以使數(shù)組a的第n-1個數(shù)據(jù)為第n-1小。而這時候第n個數(shù)據(jù)是第n小。10查找算法查找之前要求排序，不然無章可查順序查找按照排好序的順序進展查找，比如對一個升序陳列的數(shù)組中，找到第一個大于需求查找的數(shù)折半查找二分查找11折半查找先給數(shù)據(jù)排序例如按升序排好，構(gòu)成有序表，然后再將key與正中元素相比，假設(shè)key小，那么減少至右半部內(nèi)查找；再取其中值比較，每次減少1/2的范圍，直到查找勝利或失敗為止。Low指向待查元素所在區(qū)間的下界high指向待查元素所在區(qū)間的上界mid指向待查元素所在區(qū)間的中間位置 知如下11個元素的有序表：05 13 19 21 37 56

7、 64 75 80 88 92, 請查找關(guān)鍵字為21 和85的數(shù)據(jù)元素。12 先設(shè)定3個輔助標(biāo)志: low,high,mid，顯然有：mid= (low+high)/2 運算步驟：(1) low =1,high =11 ,mid =6 ，待查范圍是 1,11；(2) 假設(shè) ST.elemmid.key key，闡明keylow ,mid-1， 那么令：high =mid1;重算 mid ；(4)假設(shè) ST.elem mid .key = key，闡明查找勝利，元素序號=mid;終了條件：1查找勝利 ： ST.elemmid.key = key 2查找不勝利 ： highlow 意即區(qū)間長度小于

8、0折半查找13有序插入首先查找要插入的位置，假設(shè)位置為aL之前那么：for (i =n+1;i L;i-) ai=ai-114有序刪除比如要刪除ad這個元素，那么for (j = d;j n;j+) aj=aj+115 關(guān)于選擇排序算法：N元數(shù)組a0aN-1由小到大排序：第0步:找到a0aN-1中的最小值元素與a0交換;第1步:找到a1aN-1中的最小值元素與a1交換；第2步:找到a2aN-1中的最小值元素與a2交換；第i步:找到aiaN-1中的最小值元素與ai交換;第N-2步:找到aN-2aN-1中的最小值元素與aN-2交換。算法停頓。16程序一int i,j,minj,t; for (i

9、= 0;i N-1;i+) for (j = i + 1;j N-1;j+) if (aj ai) t = ai; ai = aj; aj = t; 17改良程序int i,j,minj,t; for (i = 0;i N-1;i+) minj = i; /有什么作用？ for (j = i + 1;j N;j+) if (aj aminj) minj = j; if (minj != i) t = ai; ai = aminj; aminj = t; 18找鞍點的問題首先要理清楚思緒，再動手編程序19for (i=0;i3;i+) max=ai0; for (j=0;jmax)max=aij

10、;maxj=j; /*求出行中最大數(shù)*/ for(k=0,flag1=1;kakj) flag1=0; /*算出該數(shù)能否為列中最小*/ if (flag1=1) printf(n第%d行,第%d列的%d是鞍點n,i,maxj,max); flag2=1; /*打印鞍點*/ if (flag2=0) printf(n矩陣中無鞍點!n); 20折半查找的問題h = 0; r = 14; m = (h + r)/2; while(h=r&x!=am) if (x r) printf(無此數(shù)); else printf(%d,m); 21將一個數(shù)組逆序轉(zhuǎn)換例如1，2，3，4，5,變?yōu)?，4，3，2，1

11、算法分析：用第一個與最后一個交換。這是ai,那么前面已有i個元素，與它交換的元素ak應(yīng)該滿足與ak后面也有i個元素，那么這個元素的下 標(biāo)k為：n-1-i即下標(biāo)i要與下標(biāo)n-i-1交換22將一個數(shù)組逆序轉(zhuǎn)換程序#define N 5main() int aN=9,6,5,4,1,i,temp;printf(n original array:n);for(i=0;iN;i+)printf(%4d,ai);for(i=0;iN/2;i+)temp=ai;ai=aN-i-1;aN-i-1=temp;printf(n sorted array:n);for(i=0;iN;i+)printf(%4d,ai

12、);23關(guān)于二維數(shù)組的問題雙下標(biāo)的運用涉及到矩陣的問題，普通運用二維數(shù)組加以處理下面舉幾個略微復(fù)雜一點的例子，也是某些考試比如高級程序員經(jīng)?？嫉降碾y題蛇行矩陣問題魔方陣問題矩陣旋轉(zhuǎn)問題24蛇行方陣問題輸入：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 1416 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 493 4 102 5 9

13、116 8 12 157 13 14 1625蛇行矩陣將自然數(shù)1,2,N*N,逐個順序插入方陣中適當(dāng)?shù)奈恢?，這個過程沿斜列進展。將斜列編號為0,1,2,2n以i表記,n=N-1，從圖中看出在一斜列上各元素的下標(biāo)是相等的，且等于斜列號i。同時方陣又可分為上三角與下三角含對角線每一斜列上元素個數(shù)為i+1個；下三角每一斜列上元素個數(shù)為2n-i+1個。在斜列上安排數(shù)可以使自右上向左下或自左下向右上兩種方式進展，元素可以表示為ai-jj或者aji-j的方式。26蛇行方陣的排數(shù)方法左下向右右上向左下標(biāo)變量下標(biāo)j的變化下標(biāo)變量下標(biāo)j的變化上三角ai-jj0 iai-jji 0aji-ji 0aji-j0 i

14、下三角ai-jji-n nai-jjn i-naji-jn i-naji-ji-n n27上三角包括對角線for (i = 0;i = n;i+) if (i %2 = 1) for (j = 0;j =0;j-) ai-jj = k; k+; 3 4 102 5 9 116 8 12 157 13 14 1628下三角不含對角線for (i = n + 1;i = (2 * n);i+) if (i %2 = 1) for (j = i - n;j =i- n;j-) ai-jj = k; k+; 3 4 102 5 9 116 8 12 157 13 14 1629螺旋方陣問題1 2 3

15、4 5 6 724 25 26 27 28 29 823 40 41 42 43 30 922 39 48 49 44 31 1021 38 47 46 45 32 1120 37 36 35 34 33 1219 18 17 16 15 14 13 1 24 23 22 21 20 192 25 40 39 38 37 183 26 49 48 47 36 174 27 42 49 46 35 165 28 43 44 45 34 156 29 30 31 32 33 147 8 9 10 11 12 13 30從a00開場，按照圖所示的從外層到內(nèi)層分別為，上，右，下，左，每進一層，一行或一

16、列的元素少2個，其變化規(guī)律是：31上行下行左側(cè)右側(cè)順時針行in-in-i i+1i n-i-1列i n-i-1 n-i i+1in-i逆時針行in-ii n-i-1n-i i+1列n-i i+1i n-i-1in-i上行右側(cè)下行左側(cè)32 k=1; for (i = 0;i = (n - 1)/2;i+) for (j = i;j = (n - i - 1);j+) /上 aij=k; k+; for (j = i;j= i+1 ;j-) /下 an-ij=k; k+; for (j = n-i;j = i+1;j-) /左 aji=k; k+; if (n % 2 = 0) /最后一個，中間

17、an/2n/2=k; 33方陣旋轉(zhuǎn)問題順時針旋轉(zhuǎn)90度可以將n+1階矩陣分為(n+1)/2層每層中可將元素分為n-2i組，每組4個元素，例如圖，i標(biāo)志為1的層從外向內(nèi)數(shù)的第二層，其中含n-2*i=4組：(a11,a15,a55,a51)、(a12,a25,a54,a41)、(a13,a35,a53,a31)、(a14,a45,a52,a21)分析每一個元素，設(shè)恣意一個為(aij)，那么交換該元素的下標(biāo)axy其中有如下規(guī)律:x=n-j,y=i,aij=an-ji34for (i = 0;i = (n - 1) / 2;i+) for(j = i;j = (n - i - 1);j+) temp=

18、aij; aij=an-ji; an-ji=an-in-j; an-in-j=ajn-i; ajn-i=temp; 交換元素下標(biāo)也就是等式右邊的部分規(guī)律x=n-j,y=i35魔方陣魔方陣是以元素為自然數(shù)1,2,N*N方陣。每個元素的值均不等且每行每列以及主副對角線各N個元素的值相等。其算法為：第一個元素的位置在第一行正中新的位置應(yīng)該處于最近插入位置的右上方，但假設(shè)右上方的位置超出方陣上邊境，那么新的位置應(yīng)該取列的最下一個位置。超出右邊境那么取行的最左的一個位置。假設(shè)最近的插入的元素為n的整數(shù)倍，那么選下面一行同列上的位置為新的位置。36#include stdio.h#define MAXSIZE 15int magicMAXSIZEMAXSIZE;int cur_i = 0,cur_j;main() int count,size = 0,i,j; while(size % 2) = 0) /輸入階數(shù)，只接受奇數(shù) printf(