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

1、數(shù)組應(yīng)用的技巧與方法數(shù)組應(yīng)用的技巧與方法1附加：計(jì)數(shù)器、累加器、累乘器附加：計(jì)數(shù)器、累加器、累乘器l計(jì)數(shù)器計(jì)數(shù)器lint count;lwhile()l l count +ll累加器累加器lint s;lfor() l l a=;l s=s+a;ll累乘器累乘器lint s;lfor() l l a=;l s=s*a;l2關(guān)于一維數(shù)組的問(wèn)題關(guān)于一維數(shù)組的問(wèn)題l一般一維數(shù)組所涉及的主要問(wèn)題有一般一維數(shù)組所涉及的主要問(wèn)題有l(wèi)排序排序l插入插入l刪除刪除l查找查找l分類統(tǒng)計(jì)分類統(tǒng)計(jì)l涉及到一些算法，我們通過(guò)例題介紹一部分涉及到一些算法，我們通過(guò)例題介紹一部分l具體問(wèn)題的解題算法的思路要靠自己慢慢去體

2、具體問(wèn)題的解題算法的思路要靠自己慢慢去體會(huì)會(huì)31. 什么是排序？什么是排序？ 將一組雜亂無(wú)章的將一組雜亂無(wú)章的數(shù)據(jù)數(shù)據(jù)按一定的按一定的規(guī)律規(guī)律順次排列起來(lái)。順次排列起來(lái)。2. 排序的目的是什么？排序的目的是什么？存放在數(shù)據(jù)表中存放在數(shù)據(jù)表中按關(guān)鍵字排序按關(guān)鍵字排序3.3.排序算法的好壞如何衡量？排序算法的好壞如何衡量？ 時(shí)間效率時(shí)間效率排序速度（即排序所花費(fèi)的全部比較次數(shù)）排序速度（即排序所花費(fèi)的全部比較次數(shù)） 空間效率空間效率占內(nèi)存輔助空間的大小占內(nèi)存輔助空間的大小 穩(wěn)定性穩(wěn)定性若兩個(gè)記錄若兩個(gè)記錄A A和和B B的關(guān)鍵字值相等，但排序后的關(guān)鍵字值相等，但排序后A A、B B的先后次序保持不

3、變，則稱這種排序算法是穩(wěn)定的。的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。 便于查找！便于查找！4排序算法排序算法l插入排序插入排序l直接插入排序直接插入排序l折半插入排序折半插入排序l表插入排序表插入排序l希爾排序希爾排序l交換排序交換排序l冒泡排序冒泡排序l快速排序（不穩(wěn)定）快速排序（不穩(wěn)定）l選擇排序選擇排序l歸并排序歸并排序l基數(shù)排序基數(shù)排序5插入排序插入排序6直接插入排序直接插入排序新元素插入到哪里？新元素插入到哪里？例例1 1：關(guān)鍵字序列關(guān)鍵字序列T=（13，6，3，31，9，27，5，11），）， 請(qǐng)寫(xiě)出直接插入排序的中間過(guò)程序列。請(qǐng)寫(xiě)出直接插入排序的中間過(guò)程序列。【13】,

4、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)位置上的元素向后適當(dāng)位置插入，把原來(lái)位置上的元素向后順移順移。7交換排序交換排序交換排序的

5、主要算法有：交換排序的主要算法有： 1) 冒泡排序冒泡排序 2) 快速排序快速排序8 基本思路：基本思路：每趟不斷將記錄兩兩比較，并按每趟不斷將記錄兩兩比較，并按“前小后大前小后大”（或（或“前大后小前大后小”）規(guī)則交換。）規(guī)則交換。優(yōu)點(diǎn)：優(yōu)點(diǎn)：每趟結(jié)束時(shí)，不僅能擠出一個(gè)最大值到最后面位置，每趟結(jié)束時(shí)，不僅能擠出一個(gè)最大值到最后面位置，還能同時(shí)部分理順其他元素；一旦下趟沒(méi)有交換發(fā)還能同時(shí)部分理順其他元素；一旦下趟沒(méi)有交換發(fā)生，還可以提前結(jié)束排序。生，還可以提前結(jié)束排序。前提：前提：順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu) 例：例：關(guān)鍵字序列關(guān)鍵字序列 T=(21，25，49，25*，16，08），請(qǐng)寫(xiě)出），請(qǐng)

6、寫(xiě)出冒泡排序的具體實(shí)現(xiàn)過(guò)程。冒泡排序的具體實(shí)現(xiàn)過(guò)程。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， 25， 25*，49初態(tài)：初態(tài)：第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟9選擇排序選擇排序l算法：首先找到數(shù)據(jù)清單中的最小的數(shù)據(jù)，然后將這個(gè)數(shù)據(jù)同第一算法：首先找到數(shù)據(jù)清單中的最小的數(shù)據(jù)，然后將這個(gè)數(shù)據(jù)同第一個(gè)數(shù)據(jù)交換位置；接下來(lái)找第二小的數(shù)據(jù)，再將其同第二個(gè)數(shù)據(jù)交個(gè)數(shù)據(jù)交換位置；接下來(lái)找第二小的數(shù)據(jù)，再將

7、其同第二個(gè)數(shù)據(jù)交換位置，以此類推。換位置，以此類推。l第第1 1次，在數(shù)組次，在數(shù)組a a的的n n個(gè)數(shù)據(jù)中選出其小者（只標(biāo)記其所在位置），個(gè)數(shù)據(jù)中選出其小者（只標(biāo)記其所在位置），若它不在其位置（即其下標(biāo)不等于若它不在其位置（即其下標(biāo)不等于1 1）則與第一個(gè)數(shù)據(jù)進(jìn)行交換）則與第一個(gè)數(shù)據(jù)進(jìn)行交換（只需交換一次），經(jīng)過(guò)本次處理后，總可以使得數(shù)組（只需交換一次），經(jīng)過(guò)本次處理后，總可以使得數(shù)組a a的第的第1 1個(gè)數(shù)個(gè)數(shù)據(jù)為第據(jù)為第1 1小。小。l第第2 2次，在數(shù)組次，在數(shù)組a a的后的后n-1n-1個(gè)數(shù)據(jù)（即出去已經(jīng)選擇的最小者的各數(shù)個(gè)數(shù)據(jù)（即出去已經(jīng)選擇的最小者的各數(shù)據(jù)）中，經(jīng)過(guò)類似的處理后，

8、可以使得數(shù)組據(jù)）中，經(jīng)過(guò)類似的處理后，可以使得數(shù)組a a的第的第2 2個(gè)數(shù)據(jù)為第個(gè)數(shù)據(jù)為第2 2小。小。l第第i i次，在數(shù)組次，在數(shù)組a a后的后的n-i+1n-i+1個(gè)數(shù)據(jù)中，經(jīng)過(guò)類似選擇處理后，數(shù)組個(gè)數(shù)據(jù)中，經(jīng)過(guò)類似選擇處理后，數(shù)組a a的第的第i i個(gè)數(shù)據(jù)為第個(gè)數(shù)據(jù)為第i i小。小。l第第n-1n-1次，在數(shù)組后的次，在數(shù)組后的2 2個(gè)數(shù)據(jù)中，經(jīng)過(guò)類似處理后，總可以使數(shù)組個(gè)數(shù)據(jù)中，經(jīng)過(guò)類似處理后，總可以使數(shù)組a a的第的第n-1n-1個(gè)數(shù)據(jù)為第個(gè)數(shù)據(jù)為第n-1n-1小。而這時(shí)候第小。而這時(shí)候第n n個(gè)數(shù)據(jù)是第個(gè)數(shù)據(jù)是第n n小。小。10查找算法查找算法l查找之前要求排序，不然無(wú)章可查查

9、找之前要求排序，不然無(wú)章可查l順序查找順序查找l按照排好序的順序進(jìn)行查找，比如對(duì)按照排好序的順序進(jìn)行查找，比如對(duì)一個(gè)升序排列的數(shù)組中，找到第一個(gè)一個(gè)升序排列的數(shù)組中，找到第一個(gè)大于需要查找的數(shù)大于需要查找的數(shù)l折半查找（二分查找）折半查找（二分查找）11折半查找折半查找先給數(shù)據(jù)排序先給數(shù)據(jù)排序（例如按升序排好），形成（例如按升序排好），形成有序表有序表，然后再將，然后再將keykey與正中元素相比，與正中元素相比，若若keykey小，則縮小至右半部?jī)?nèi)查找；再小，則縮小至右半部?jī)?nèi)查找；再取其中值比較，每次縮小取其中值比較，每次縮小1/21/2的范圍，的范圍，直到查找成功或失敗為止。直到查找成功或

10、失敗為止。LowLow指向待查元素指向待查元素所在區(qū)間的下界所在區(qū)間的下界highhigh指向待查元素所指向待查元素所在區(qū)間的上界在區(qū)間的上界midmid指向待查元素所在指向待查元素所在區(qū)間的中間位置區(qū)間的中間位置 已知如下已知如下11個(gè)元素的個(gè)元素的有序表有序表：（05 13 19 21 37 56 64 75 80 88 92）, 請(qǐng)查找關(guān)鍵字為請(qǐng)查找關(guān)鍵字為21 和和85的數(shù)據(jù)元素。的數(shù)據(jù)元素。12 先設(shè)定先設(shè)定3 3個(gè)輔助標(biāo)志個(gè)輔助標(biāo)志: : low,high,midlow,high,mid，顯然有：顯然有：mid= mid= (low+high)/2(low+high)/2 運(yùn)算步驟

11、運(yùn)算步驟：(1) low =1,high =11 ,mid =6 (1) low =1,high =11 ,mid =6 ，待查范圍是，待查范圍是 1,111,11；(2) (2) 若若 ST.elemmid.key ST.elemmid.key key keykey，說(shuō)明，說(shuō)明keykey low ,midlow ,mid-1-1 ， 則令：則令：high =midhigh =mid1 1; ;重算重算 mid mid ；(4)(4)若若 ST.elem mid .key ST.elem mid .key = key= key，說(shuō)明查找成功，元素序號(hào)，說(shuō)明查找成功，元素序號(hào)=mid;=mid

12、;結(jié)束條件：結(jié)束條件：（1 1）查找成功）查找成功 ： ST.elemmid.key = keyST.elemmid.key = key （2 2）查找不成功）查找不成功 ： highlowhighlow （意即區(qū)間長(zhǎng)度小于（意即區(qū)間長(zhǎng)度小于0 0）折半查找折半查找13有序插入有序插入l首先查找要插入的位置，假設(shè)位置為aL之前l(fā)則：for (i =n+1;i L;i-) ai=ai-114有序刪除有序刪除l比如要?jiǎng)h除ad這個(gè)元素，則for (j = d;j n;j+) aj=aj+115 關(guān)于選擇排序關(guān)于選擇排序l算法：算法：N元數(shù)組元數(shù)組a0aN-1由小到大排序：由小到大排序：第第0步步:找

13、到找到a0aN-1中的最小值元素與中的最小值元素與a0交換交換;第第1步步:找到找到a1aN-1中的最小值元素與中的最小值元素與a1交換；交換；第第2步步:找到找到a2aN-1中的最小值元素與中的最小值元素與a2交換；交換；第第i步步:找到找到aiaN-1中的最小值元素與中的最小值元素與ai交換交換;第第N-2步步:找到找到aN-2aN-1中的最小值元素與中的最小值元素與aN-2交換。交換。算法停止。算法停止。16程序一程序一lint 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

14、= aj; aj = t; 17改進(jìn)程序改進(jìn)程序lint 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找鞍點(diǎn)的問(wèn)題找鞍點(diǎn)的問(wèn)題l首先要理首先要理清楚思路，清楚思路，再動(dòng)手編再動(dòng)手編程序程序19lfor (i=0;i3;i+)l max=ai0;l for (j=0;jmax)lmax=aij;lmaxj=j; /*求出行中最大數(shù)*/ll

15、l for(k=0,flag1=1;kakj)l flag1=0; /*算出該數(shù)是否為列中最小*/l l if (flag1=1)l printf(n第%d行,第%d列的%d是鞍點(diǎn)n,i,maxj,max);l flag2=1; /*打印鞍點(diǎn)*/l l if (flag2=0)l printf(n矩陣中無(wú)鞍點(diǎn)!n);l 20折半查找的問(wèn)題折半查找的問(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將一個(gè)數(shù)組逆序轉(zhuǎn)換將一個(gè)數(shù)組逆序轉(zhuǎn)換例如例如1 1，2 2，3 3

16、，4 4，5,5,變?yōu)樽優(yōu)? 5，4 4，3 3，2 2，1 1l算法分析：用第一個(gè)與最后一個(gè)交換。算法分析：用第一個(gè)與最后一個(gè)交換。這是這是ai,ai,則前面已有則前面已有i i個(gè)元素，與它交換的元素個(gè)元素，與它交換的元素akak應(yīng)該應(yīng)該滿足與滿足與akak后面也有后面也有i i個(gè)元素，則這個(gè)元素的下個(gè)元素，則這個(gè)元素的下 標(biāo)標(biāo)k k為：為：n-1-in-1-i即下標(biāo)即下標(biāo)i i要與下標(biāo)要與下標(biāo)n-i-1n-i-1交換交換22將一個(gè)數(shù)組逆序轉(zhuǎn)換程序?qū)⒁粋€(gè)數(shù)組逆序轉(zhuǎn)換程序l#define N 5lmain()l int aN=9,6,5,4,1,i,temp;lprintf(n origina

17、l array:n);lfor(i=0;iN;i+)lprintf(%4d,ai);lfor(i=0;iN/2;i+)ltemp=ai;lai=aN-i-1;aN-i-1=temp;llprintf(n sorted array:n);lfor(i=0;iN;i+)lprintf(%4d,ai);l23關(guān)于二維數(shù)組的問(wèn)題（雙下標(biāo)的應(yīng)關(guān)于二維數(shù)組的問(wèn)題（雙下標(biāo)的應(yīng)用）用）l涉及到矩陣的問(wèn)題，一般使用二維涉及到矩陣的問(wèn)題，一般使用二維數(shù)組加以解決數(shù)組加以解決l下面舉幾個(gè)稍微復(fù)雜一點(diǎn)的例子，下面舉幾個(gè)稍微復(fù)雜一點(diǎn)的例子，也是某些考試（比如高級(jí)程序員）也是某些考試（比如高級(jí)程序員）經(jīng)?？嫉降碾y題經(jīng)?？?/p>

18、到的難題l蛇行矩陣問(wèn)題蛇行矩陣問(wèn)題l魔方陣問(wèn)題魔方陣問(wèn)題l矩陣旋轉(zhuǎn)問(wèn)題矩陣旋轉(zhuǎn)問(wèn)題24蛇行方陣問(wèn)題蛇行方陣問(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 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 4913 4 102 5 9 116 8 12 157 13 14 1625蛇行矩陣蛇行矩陣l將自然數(shù)將自然數(shù)1,2

19、,N1,2,N* *N,N,逐個(gè)順逐個(gè)順序插入方陣中適當(dāng)?shù)奈恢?，這序插入方陣中適當(dāng)?shù)奈恢茫@個(gè)過(guò)程沿斜列進(jìn)行。將斜列編個(gè)過(guò)程沿斜列進(jìn)行。將斜列編號(hào)為號(hào)為0,1,2,2n0,1,2,2n（以（以i i表表記記,n=N-1,n=N-1），從圖中看出在一），從圖中看出在一斜列上各元素的下標(biāo)是相等的，斜列上各元素的下標(biāo)是相等的，且等于斜列號(hào)且等于斜列號(hào)i i。同時(shí)方陣又。同時(shí)方陣又可分為上三角與下三角（含對(duì)可分為上三角與下三角（含對(duì)角線）每一斜列上元素個(gè)數(shù)為角線）每一斜列上元素個(gè)數(shù)為i+1i+1個(gè)；下三角每一斜列上元個(gè)；下三角每一斜列上元素個(gè)數(shù)為素個(gè)數(shù)為2n-i+12n-i+1個(gè)。在斜列上個(gè)。在斜列上

20、安排數(shù)可以使安排數(shù)可以使自右上向左下自右上向左下或或自左下向右上自左下向右上兩種方式進(jìn)行，兩種方式進(jìn)行，元素可以表示為元素可以表示為ai-jjai-jj或或者者aji-jaji-j的形式。的形式。26蛇行方陣的排數(shù)方法蛇行方陣的排數(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-naji-jn i-naji-ji-n n27上三角（包括對(duì)角線）上三角（包括對(duì)角線）for (i = 0;i = n;i+) if (i %2 = 1) for (j = 0;j =0;j-)

21、 ai-jj = k; k+; 13 4 102 5 9 116 8 12 157 13 14 1628下三角（不含對(duì)角線）下三角（不含對(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+; 13 4 102 5 9 116 8 12 157 13 14 1629螺旋方陣問(wèn)題螺旋方陣問(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

22、 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 30l從從a00a00開(kāi)始，按照?qǐng)D開(kāi)始，按照?qǐng)D所示的從外層到內(nèi)層所示的從外層到內(nèi)層分別為，上，右，下，分別為，上，右，下，左，每進(jìn)一層，一行左，每進(jìn)一層，一行或一列的元素少或一列的元素少2 2個(gè)，個(gè)，其變化規(guī)律是：其變化規(guī)律是：31上行下行左側(cè)右側(cè)順時(shí)針行i

23、n-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 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) /最后一個(gè)，中間 an/2n/2=k; 33方陣旋轉(zhuǎn)問(wèn)題方陣旋轉(zhuǎn)問(wèn)題l順時(shí)針

24、旋轉(zhuǎn)順時(shí)針旋轉(zhuǎn)9090度度l可以將可以將n+1n+1階矩陣分為階矩陣分為(n+1)/2(n+1)/2層層l每層中可將元素分為每層中可將元素分為n-2in-2i組，每組組，每組4 4個(gè)元素，例如圖，個(gè)元素，例如圖，i i標(biāo)記為標(biāo)記為1 1的層（從的層（從外向內(nèi)數(shù)的第二層），其中含外向內(nèi)數(shù)的第二層），其中含n-n-2 2* *i=4i=4組：組：l(a11,a15,a55,a51)(a11,a15,a55,a51)、(a12,a25,a54,a41)(a12,a25,a54,a41)、(a13,a35,a53,a31)(a13,a35,a53,a31)、(a14,a45,a52,a21)(a14,

25、a45,a52,a21)l分析每一個(gè)元素，設(shè)任意一個(gè)為分析每一個(gè)元素，設(shè)任意一個(gè)為(aij)(aij)，則替換該元素的下標(biāo)，則替換該元素的下標(biāo)axyaxy其中有如下規(guī)律其中有如下規(guī)律: :lx=n-j,y=i,aij=an-ji34for (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; l替換元素下標(biāo)（也就是等式替換元素下標(biāo)（也就是等式右邊的部分）規(guī)律右邊的部分）規(guī)律x=n-j,y=i35魔方陣魔方陣l魔方陣是以元素為自然數(shù)魔方陣是以元素為自然數(shù)1,2,N1,2,N* *N N方陣。每個(gè)元素的值方陣。每個(gè)