1、數(shù)組應(yīng)用的技巧與方法1第1頁(yè)，共40頁(yè)。附加：計(jì)數(shù)器、累加器、累乘器計(jì)數(shù)器int count;while() count +累加器int s;for() a=; s=s+a;累乘器int s;for() a=; s=s*a;2第2頁(yè)，共40頁(yè)。關(guān)于一維數(shù)組的問(wèn)題一般一維數(shù)組所涉及的主要問(wèn)題有排序插入刪除查找分類(lèi)統(tǒng)計(jì)涉及到一些算法，我們通過(guò)例題介紹一部分具體問(wèn)題的解題算法的思路要靠自己慢慢去體會(huì)3第3頁(yè)，共40頁(yè)。1. 什么是排序？ 將一組雜亂無(wú)章的數(shù)據(jù)按一定的規(guī)律順次排列起來(lái)。 2. 排序的目的是什么？存放在數(shù)據(jù)表中按關(guān)鍵字排序3.排序算法的好壞如何衡量？時(shí)間效率排序速度（即排序所花費(fèi)的全部比

2、較次數(shù)）空間效率占內(nèi)存輔助空間的大小穩(wěn)定性若兩個(gè)記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱(chēng)這種排序算法是穩(wěn)定的。 便于查找！4第4頁(yè)，共40頁(yè)。排序算法插入排序直接插入排序折半插入排序表插入排序希爾排序交換排序冒泡排序快速排序（不穩(wěn)定）選擇排序歸并排序基數(shù)排序5第5頁(yè)，共40頁(yè)。插入排序插入排序的基本思想是： 每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象全部插入為止。簡(jiǎn)言之，邊插入邊排序，保證子序列中隨時(shí)都是排好序的。6第6頁(yè)，共40頁(yè)。直接插入排序新元素插入到哪里？例1：關(guān)鍵字序列T=（13，6，3，31，9，27，5，1

3、1）， 請(qǐng)寫(xiě)出直接插入排序的中間過(guò)程序列?！?3】, 6, 3, 31, 9, 27, 5, 11【6, 13】, 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】 在已形成的有序表中線性查找，并在適當(dāng)位置插入，把原來(lái)位置上的元素向后順移。最簡(jiǎn)單的排序法！7第7頁(yè)，共40頁(yè)。交換排序

4、兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序?yàn)橹?。交換排序的主要算法有： 1) 冒泡排序 2) 快速排序交換排序的基本思想是：8第8頁(yè)，共40頁(yè)。 冒泡排序基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。優(yōu)點(diǎn)：每趟結(jié)束時(shí)，不僅能擠出一個(gè)最大值到最后面位置，還能同時(shí)部分理順其他元素；一旦下趟沒(méi)有交換發(fā)生，還可以提前結(jié)束排序。前提：順序存儲(chǔ)結(jié)構(gòu) 例：關(guān)鍵字序列 T=(21，25，49，25*，16，08），請(qǐng)寫(xiě)出冒泡排序的具體實(shí)現(xiàn)過(guò)程。21，25，49， 25*，16， 0821，25，25*，16， 0

5、8 ， 4921，25， 16， 08 ，25*，4921，16， 08 ，25， 25*，4916，08 ，21， 25， 25*，4908，16， 21， 25， 25*，49初態(tài)：第1趟第2趟第3趟第4趟第5趟9第9頁(yè)，共40頁(yè)。選擇排序算法：首先找到數(shù)據(jù)清單中的最小的數(shù)據(jù)，然后將這個(gè)數(shù)據(jù)同第一個(gè)數(shù)據(jù)交換位置；接下來(lái)找第二小的數(shù)據(jù)，再將其同第二個(gè)數(shù)據(jù)交換位置，以此類(lèi)推。第1次，在數(shù)組a的n個(gè)數(shù)據(jù)中選出其小者（只標(biāo)記其所在位置），若它不在其位置（即其下標(biāo)不等于1）則與第一個(gè)數(shù)據(jù)進(jìn)行交換（只需交換一次），經(jīng)過(guò)本次處理后，總可以使得數(shù)組a的第1個(gè)數(shù)據(jù)為第1小。第2次，在數(shù)組a的后n-1個(gè)數(shù)據(jù)（

6、即出去已經(jīng)選擇的最小者的各數(shù)據(jù)）中，經(jīng)過(guò)類(lèi)似的處理后，可以使得數(shù)組a的第2個(gè)數(shù)據(jù)為第2小。第i次，在數(shù)組a后的n-i+1個(gè)數(shù)據(jù)中，經(jīng)過(guò)類(lèi)似選擇處理后，數(shù)組a的第i個(gè)數(shù)據(jù)為第i小。第n-1次，在數(shù)組后的2個(gè)數(shù)據(jù)中，經(jīng)過(guò)類(lèi)似處理后，總可以使數(shù)組a的第n-1個(gè)數(shù)據(jù)為第n-1小。而這時(shí)候第n個(gè)數(shù)據(jù)是第n小。10第10頁(yè)，共40頁(yè)。查找算法查找之前要求排序，不然無(wú)章可查順序查找按照排好序的順序進(jìn)行查找，比如對(duì)一個(gè)升序排列的數(shù)組中，找到第一個(gè)大于需要查找的數(shù)折半查找（二分查找）11第11頁(yè)，共40頁(yè)。折半查找先給數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將key與正中元素相比，若key小，則縮小至右半

7、部?jī)?nèi)查找；再取其中值比較，每次縮小1/2的范圍，直到查找成功或失敗為止。Low指向待查元素所在區(qū)間的下界high指向待查元素所在區(qū)間的上界mid指向待查元素所在區(qū)間的中間位置 已知如下11個(gè)元素的有序表：（05 13 19 21 37 56 64 75 80 88 92）, 請(qǐng)查找關(guān)鍵字為21 和85的數(shù)據(jù)元素。12第12頁(yè)，共40頁(yè)。 先設(shè)定3個(gè)輔助標(biāo)志: low,high,mid，顯然有：mid= (low+high)/2 運(yùn)算步驟：(1) low =1,high =11 ,mid =6 ，待查范圍是 1,11；(2) 若 ST.elemmid.key key，說(shuō)明keylow ,mid-

8、1， 則令：high =mid1;重算 mid ；(4)若 ST.elem mid .key = key，說(shuō)明查找成功，元素序號(hào)=mid;結(jié)束條件：（1）查找成功 ： ST.elemmid.key = key （2）查找不成功 ： highlow （意即區(qū)間長(zhǎng)度小于0）折半查找13第13頁(yè)，共40頁(yè)。有序插入首先查找要插入的位置，假設(shè)位置為aL之前則：for (i =n+1;i L;i-) ai=ai-114第14頁(yè)，共40頁(yè)。有序刪除比如要?jiǎng)h除ad這個(gè)元素，則for (j = d;j n;j+) aj=aj+115第15頁(yè)，共40頁(yè)。 關(guān)于選擇排序算法：N元數(shù)組a0aN-1由小到大排序：第0

9、步:找到a0aN-1中的最小值元素與a0交換;第1步:找到a1aN-1中的最小值元素與a1交換；第2步:找到a2aN-1中的最小值元素與a2交換；第i步:找到aiaN-1中的最小值元素與ai交換;第N-2步:找到aN-2aN-1中的最小值元素與aN-2交換。算法停止。16第16頁(yè)，共40頁(yè)。程序一int i,j,minj,t; for (i = 0;i N-1;i+) for (j = i + 1;j N-1;j+) if (aj ai) t = ai; ai = aj; aj = t; 17第17頁(yè)，共40頁(yè)。改進(jìn)程序int i,j,minj,t; for (i = 0;i N-1;i+)

10、minj = i; /有什么作用？ for (j = i + 1;j N;j+) if (aj aminj) minj = j; if (minj != i) t = ai; ai = aminj; aminj = t; 18第18頁(yè)，共40頁(yè)。找鞍點(diǎn)的問(wèn)題首先要理清楚思路，再動(dòng)手編程序19第19頁(yè)，共40頁(yè)。for (i=0;i3;i+) max=ai0; for (j=0;jmax)max=aij;maxj=j; /*求出行中最大數(shù)*/ for(k=0,flag1=1;kakj) flag1=0; /*算出該數(shù)是否為列中最小*/ if (flag1=1) printf(n第%d行,第%d列

11、的%d是鞍點(diǎn)n,i,maxj,max); flag2=1; /*打印鞍點(diǎn)*/ if (flag2=0) printf(n矩陣中無(wú)鞍點(diǎn)!n); 20第20頁(yè)，共40頁(yè)。折半查找的問(wèn)題h = 0; r = 14; m = (h + r)/2; while(h=r&x!=am) if (x r) printf(無(wú)此數(shù)); else printf(%d,m); 21第21頁(yè)，共40頁(yè)。將一個(gè)數(shù)組逆序轉(zhuǎn)換例如1，2，3，4，5,變?yōu)?，4，3，2，1算法分析：用第一個(gè)與最后一個(gè)交換。這是ai,則前面已有i個(gè)元素，與它交換的元素ak應(yīng)該滿(mǎn)足與ak后面也有i個(gè)元素，則這個(gè)元素的下 標(biāo)k為：n-1-i即下標(biāo)i

12、要與下標(biāo)n-i-1交換22第22頁(yè)，共40頁(yè)。將一個(gè)數(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);23第23頁(yè)，共40頁(yè)。關(guān)于二維數(shù)組的問(wèn)題（雙下標(biāo)的應(yīng)用）涉及到矩陣的問(wèn)題，一般使用二維數(shù)組加以解決下面舉幾個(gè)稍微復(fù)雜一點(diǎn)的例子，也是某

13、些考試（比如高級(jí)程序員）經(jīng)?？嫉降碾y題蛇行矩陣問(wèn)題魔方陣問(wèn)題矩陣旋轉(zhuǎn)問(wèn)題24第24頁(yè)，共40頁(yè)。蛇行方陣問(wèn)題輸入：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 116 8 12 157 13 14 1625第25頁(yè)，共40頁(yè)。蛇行矩陣將自然數(shù)1,2,N

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

15、naji-jn i-naji-ji-n n27第27頁(yè)，共40頁(yè)。上三角（包括對(duì)角線）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第28頁(yè)，共40頁(yè)。下三角（不含對(duì)角線）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第29頁(yè)，共40頁(yè)。

16、螺旋方陣問(wèn)題1 2 3 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第30頁(yè)，共40頁(yè)。從a00開(kāi)始，按照?qǐng)D所示的從外層到內(nèi)

17、層分別為，上，右，下，左，每進(jìn)一層，一行或一列的元素少2個(gè)，其變化規(guī)律是：31第31頁(yè)，共40頁(yè)。上行下行左側(cè)右側(cè)順時(shí)針行in-in-i i+1i n-i-1列i n-i-1 n-i i+1in-i逆時(shí)針行in-ii n-i-1n-i i+1列n-i i+1i n-i-1in-i上行右側(cè)下行左側(cè)32第32頁(yè)，共40頁(yè)。 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;

18、j-) /左 aji=k; k+; if (n % 2 = 0) /最后一個(gè)，中間 an/2n/2=k; 33第33頁(yè)，共40頁(yè)。方陣旋轉(zhuǎn)問(wèn)題順時(shí)針旋轉(zhuǎn)90度可以將n+1階矩陣分為(n+1)/2層每層中可將元素分為n-2i組，每組4個(gè)元素，例如圖，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)分析每一個(gè)元素，設(shè)任意一個(gè)為(aij)，則替換該元素的下標(biāo)axy其中有如下規(guī)律:x=n-j,y=i,aij=an-ji34第34頁(yè)，共40頁(yè)。for (i = 0;i = (n - 1) / 2;i+) for(j = i;j = (n - i - 1);j+) temp=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第35頁(yè)，共40頁(yè)。魔方陣魔方陣是以元素為自然數(shù)1,2,N*N方陣。每個(gè)元素的值均不等且每行每列以及主副對(duì)角線各N個(gè)元素的值相等。其