數(shù)組應(yīng)用的技巧與方法課件

數(shù)組應(yīng)用的技巧與方法1

數(shù)組應(yīng)用的技巧與方法1附加：計數(shù)器、累加器、累乘器計數(shù)器intcount;while(…){…count++}累加器ints;for(…){…a=…;s=s+a;}累乘器ints;for(…){…a=…;s=s*a;}2附加：計數(shù)器、累加器、累乘器計數(shù)器累乘器2關(guān)于一維數(shù)組的問題一般一維數(shù)組所涉及的主要問題有排序插入刪除查找分類統(tǒng)計涉及到一些算法，我們通過例題介紹一部分具體問題的解題算法的思路要靠自己慢慢去體會3關(guān)于一維數(shù)組的問題一般一維數(shù)組所涉及的主要問題有31.什么是排序？將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。

2.排序的目的是什么？存放在數(shù)據(jù)表中按關(guān)鍵字排序3.排序算法的好壞如何衡量？時間效率——排序速度（即排序所花費的全部比較次數(shù)）空間效率——占內(nèi)存輔助空間的大小穩(wěn)定性——若兩個記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。

——便于查找！41.什么是排序？2.排序的目的是什么？存放在數(shù)據(jù)表中按關(guān)排序算法插入排序直接插入排序折半插入排序表插入排序希爾排序交換排序冒泡排序快速排序（不穩(wěn)定）選擇排序歸并排序基數(shù)排序5排序算法插入排序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,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)位置插入，把原來位置上的元素向后順移。最簡單的排序法！7直接插入排序新元素插入到哪里？例1：關(guān)鍵字序列T=（13，6交換排序兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序為止。交換排序的主要算法有：

1)冒泡排序

2)快速排序交換排序的基本思想是：8交換排序

冒泡排序基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。優(yōu)點：每趟結(jié)束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結(jié)束排序。前提：順序存儲結(jié)構(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，

25，

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)記其所在位置），若它不在其位置（即其下標(biāo)不等于1）則與第一個數(shù)據(jù)進(jìn)行交換（只需交換一次），經(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次，在數(shù)組后的2個數(shù)據(jù)中，經(jīng)過類似處理后，總可以使數(shù)組a的第n-1個數(shù)據(jù)為第n-1小。而這時候第n個數(shù)據(jù)是第n小。10選擇排序算法：首先找到數(shù)據(jù)清單中的最小的數(shù)據(jù)，然后將這個數(shù)據(jù)查找算法查找之前要求排序，不然無章可查順序查找按照排好序的順序進(jìn)行查找，比如對一個升序排列的數(shù)組中，找到第一個大于需要查找的數(shù)折半查找（二分查找）11查找算法查找之前要求排序，不然無章可查11折半查找先給數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將key與正中元素相比，若key小，則縮小至右半部內(nèi)查找；再取其中值比較，每次縮小1/2的范圍，直到查找成功或失敗為止。Low指向待查元素所在區(qū)間的下界high指向待查元素所在區(qū)間的上界mid指向待查元素所在區(qū)間的中間位置已知如下11個元素的有序表：

（0513192137566475808892）,請查找關(guān)鍵字為21

和85的數(shù)據(jù)元素。12折半查找Low指向待查元素所在區(qū)間的下界high指向待查元素①先設(shè)定3個輔助標(biāo)志:

low,high,mid，顯然有：mid=(low+high)/2②運算步驟：(1)low=1,high=11,mid=6，待查范圍是[1,11]；(2)若ST.elem[mid].key<key，說明key[mid+1,high]，則令：low=mid+1;重算mid＝(low+high)/2；.(3)若ST.elem[mid].key>

key，說明key[low,mid-1]，則令：high=mid–1;重算mid；(4)若ST.elem[mid].key=key，說明查找成功，元素序號=mid;結(jié)束條件：（1）查找成功：ST.elem[mid].key=key

（2）查找不成功：high≤low

（意即區(qū)間長度小于0）折半查找13①先設(shè)定3個輔助標(biāo)志:low,high,mid，折半查找有序插入首先查找要插入的位置，假設(shè)位置為a[L]之前則： for(i=n+1;i>L;i--)a[i]=a[i-1]14有序插入首先查找要插入的位置，假設(shè)位置為a[L]之前14有序刪除比如要刪除a[d]這個元素，則for(j=d;j<n;j++)a[j]=a[j+1]15有序刪除比如要刪除a[d]這個元素，15關(guān)于選擇排序算法：N元數(shù)組a[0]~a[N-1]由小到大排序：

第0步:找到a[0]~a[N-1]中的最小值元素與a[0]交換;

第1步:找到a[1]~a[N-1]中的最小值元素與a[1]交換；

第2步:找到a[2]~a[N-1]中的最小值元素與a[2]交換；

…

第i步:找到a[i]~a[N-1]中的最小值元素與a[i]交換;

…

第N-2步:找到a[N-2]~a[N-1]中的最小值元素與a[N-2]交換。

算法停止。16關(guān)于選擇排序算法：N元數(shù)組a[0]~a[N-1]由小到大排程序一inti,j,minj,t;

for(i=0;i<N-1;i++){

for(j=i+1;j<N-1;j++)

if(a[j]<a[i]){

t=a[i];

a[i]=a[j];

a[j]=t;

}

}

17程序一inti,j,minj,t;

for(i改進(jìn)程序inti,j,minj,t;

for(i=0;i<N-1;i++){

minj=i;

//有什么作用？

for(j=i+1;j<N;j++)

if(a[j]<a[minj])

minj=j;

if(minj!=i){

t=a[i];

a[i]=a[minj];

a[minj]=t;

}

}

18改進(jìn)程序inti,j,minj,t;

for(i找鞍點的問題首先要理清楚思路，再動手編程序19找鞍點的問題首先要理清楚思路，再動手編程序19for(i=0;i<3;i++){max=a[i][0];for(j=0;j<3;j++){if(a[i][j]>max){ max=a[i][j]; maxj=j;/*求出行中最大數(shù)*/ }}for(k=0,flag1=1;k<3&&flag1;k++){if(max>a[k][j]) flag1=0;/*算出該數(shù)是否為列中最小*/}if(flag1==1){printf("\n第%d行,第%d列的%d是鞍點\n",i,maxj,max);flag2=1;/*打印鞍點*/}if(flag2==0)printf("\n矩陣中無鞍點!\n");}20for(i=0;i<3;i++){20折半查找的問題h=0;r=14;m=(h+r)/2;while(h<=r&&x!=a[m]){if(x<a[m]){r=m-1;m=(h+r)/2;}else{h=m+1;m=(h+r)/2;}}if(h>r)printf("無此數(shù)");elseprintf("%d",m);21折半查找的問題h=0;21將一個數(shù)組逆序轉(zhuǎn)換

例如1，2，3，4，5,變?yōu)?，4，3，2，1算法分析：用第一個與最后一個交換。這是a[i],則前面已有i個元素，與它交換的元素a[k]應(yīng)該滿足與a[k]后面也有i個元素，則這個元素的下標(biāo)k為：n-1-i即下標(biāo)i要與下標(biāo)n-i-1交換22將一個數(shù)組逆序轉(zhuǎn)換

例如1，2，3，4，5,變?yōu)?，4，3，將一個數(shù)組逆序轉(zhuǎn)換程序#defineN5main(){inta[N]={9,6,5,4,1},i,temp;

printf("\noriginalarray:\n");

for(i=0;i<N;i++)

printf("%4d",a[i]);

for(i=0;i<N/2;i++)

{ temp=a[i];

a[i]=a[N-i-1]; a[N-i-1]=temp;

}printf("\nsortedarray:\n");for(i=0;i<N;i++)

printf("%4d",a[i]);}23將一個數(shù)組逆序轉(zhuǎn)換程序#defineN523關(guān)于二維數(shù)組的問題（雙下標(biāo)的應(yīng)用）涉及到矩陣的問題，一般使用二維數(shù)組加以解決下面舉幾個稍微復(fù)雜一點的例子，也是某些考試（比如高級程序員）經(jīng)常考到的難題蛇行矩陣問題魔方陣問題矩陣旋轉(zhuǎn)問題24關(guān)于二維數(shù)組的問題（雙下標(biāo)的應(yīng)用）涉及到矩陣的問題，一般使用蛇行方陣問題輸入：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

49341025911681215713141625蛇行方陣問題輸入：N=4

蛇行矩陣將自然數(shù)1,2,…,N*N,逐個順序插入方陣中適當(dāng)?shù)奈恢?，這個過程沿斜列進(jìn)行。將斜列編號為0,1,2,…,2n（以i表記,n=N-1），從圖中看出在一斜列上各元素的下標(biāo)是相等的，且等于斜列號i。同時方陣又可分為上三角與下三角（含對角線）每一斜列上元素個數(shù)為i+1個；下三角每一斜列上元素個數(shù)為2n-i+1個。在斜列上安排數(shù)可以使自右上向左下或自左下向右上兩種方式進(jìn)行，元素可以表示為a[i-j][j]或者a[j][i-j]的形式。26蛇行矩陣將自然數(shù)1,2,…,N*N,逐個順序插入方陣中適當(dāng)?shù)纳咝蟹疥嚨呐艛?shù)方法左下向右右上向左下標(biāo)變量下標(biāo)j的變化下標(biāo)變量下標(biāo)j的變化上三角a[i-j][j]0ia[i-j][j]i0a[j][i-j]i0a[j][i-j]0i下三角a[i-j][j]i-nna[i-j][j]ni-na[j][i-j]ni-na[j][i-j]i-nn27蛇行方陣的排數(shù)方法左下向右右上向左下標(biāo)變量下標(biāo)j的變化下標(biāo)變上三角（包括對角線）for(i=0;i<=n;i++){if(i%2==1){for(j=0;j<=i;j++){a[i-j][j]=k;k++;}}else{for(j=i;j>=0;j--){a[i-j][j]=k;k++;}}}341025911681215713141628上三角（包括對角線）for(i=0;i<=n;i+下三角（不含對角線）for(i=n+1;i<=(2*n);i++){if(i%2==1){for(j=i-n;j<=n;j++){a[i-j][j]=k;k++;}}else{for(j=n;j>=i-n;j--){a[i-j][j]=k;k++;}}}341025911681215713141629下三角（不含對角線）for(i=n+1;i<=螺旋方陣問題12345672425262728298234041424330922394849443110213847464532112037363534331219181716151413

12423222120192254039383718326494847361742742494635165284344453415629303132331478910111213

30螺旋方陣問題1234從a00開始，按照圖所示的從外層到內(nèi)層分別為，上，右，下，左，每進(jìn)一層，一行或一列的元素少2個，其變化規(guī)律是：31從a00開始，按照圖所示的從外層到內(nèi)層分別為，上，右，下，左上行下行左側(cè)右側(cè)順時針行in-in-ii+1in-i-1列in-i-1n-ii+1in-i逆時針行in-iin-i-1n-ii+1列n-ii+1in-i-1in-i上行右側(cè)下行左側(cè)32上行下行左側(cè)右側(cè)順時針行in-in-ii+1i

k=1;for(i=0;i<=(n-1)/2;i++){for(j=i;j<=(n-i-1);j++){//上

a[i][j]=k;k++;}for(j=i;j<=(n-i-1);j++){//右

a[j][n-i]=k;k++;}for(j=n-i;j>=i+1;j--){//下

a[n-i][j]=k;k++;}for(j=n-i;j>=i+1;j--){//左

a[j][i]=k;k++;}}if(n%2==0){//最后一個，中間

a[n/2][n/2]=k;}33k=1;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)a[x][y]其中有如下規(guī)律:x=n-j,y=i,a[i][j]=a[n-j][i]34方陣旋轉(zhuǎn)問題順時針旋轉(zhuǎn)90度34for(i=0;i<=(n-1)/2;i++){for(j=i;j<=(n-i-1);j++){temp=a[i][j];a[i][j]=a[n-j][i];a[n-j][i]=a[n-i][n-j];a[n-i][n-j]=a[j][n-i];a[j][n-i]=temp;}}替換元素下標(biāo)（也就是等式右邊的部分）規(guī)律x=n-j,y=i35for(i=0;i<=(n-1)/2;i+魔方陣魔方陣是以元素為自然數(shù)1,2,…N*N方陣。每個元素的值均不等且每行每列以及主副對角線各N個元素的值相等。其算法為：第一個元素的位置在第一行正中新的位置應(yīng)該處于最近插入位置的右上方，但如果右上方的位置超出方陣上邊界，則新的位置應(yīng)該取列的最下一個位置。超出右邊界則取行的最左的一個位置。若最近的插入的元素為n的整數(shù)倍，則選下面一行同列上的位置為新的位置。36魔方陣魔方陣是以元素為自然數(shù)1,2,…N*N方陣。每個元素的#include"stdio.h"#defineMAXSIZE15intmagic[MAXSIZE][MAXSIZE];intcur_i=0,cur_j;main(){intcount,size=0,i,j;while((size%2)==0){//輸入階數(shù)，只接受奇數(shù)

printf("\nentersquqresize(ODD)number:");scanf("%d",&size);}cur_j=(size-1)/2;37#include"stdio.h"37for(count=1;count<=size*size;count++){magic[cur_i][cur_j]=count;//第一個元素放在正中if((count%size==0)){//最近的插入的元素為n的整數(shù)倍，下面一行，同列為新的位置

cur_i=cur_i+1;continue;}cur_i=cur_i-1;cur_j=cur_j+1;//下一個到右上角

if(cur_i==-1)//如果行越界

cur_i+=size;elseif(cur_j>size-1)//如果列越界

cur_j-=size;}//endcountfor(i=0;i<size;i++){printf("\n");for(j=0;j<size;j++)printf("%3d",magic[i][j]);}}38for(count=1;count<=size*結(jié)束語“紙上談兵”學(xué)不出程序設(shè)計本領(lǐng)；只有大量上機(jī)、編程、調(diào)試，才能掌握。學(xué)好程序設(shè)計語言的唯一途徑是上機(jī)。你的編程能力和你在機(jī)器上投入的時間成正比。39結(jié)束語“紙上談兵”學(xué)不出程序設(shè)計本領(lǐng)；只有大量上機(jī)、編程、調(diào)

數(shù)組應(yīng)用的技巧與方法40

數(shù)組應(yīng)用的技巧與方法1附加：計數(shù)器、累加器、累乘器計數(shù)器intcount;while(…){…count++}累加器ints;for(…){…a=…;s=s+a;}累乘器ints;for(…){…a=…;s=s*a;}41附加：計數(shù)器、累加器、累乘器計數(shù)器累乘器2關(guān)于一維數(shù)組的問題一般一維數(shù)組所涉及的主要問題有排序插入刪除查找分類統(tǒng)計涉及到一些算法，我們通過例題介紹一部分具體問題的解題算法的思路要靠自己慢慢去體會42關(guān)于一維數(shù)組的問題一般一維數(shù)組所涉及的主要問題有31.什么是排序？將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。

2.排序的目的是什么？存放在數(shù)據(jù)表中按關(guān)鍵字排序3.排序算法的好壞如何衡量？時間效率——排序速度（即排序所花費的全部比較次數(shù)）空間效率——占內(nèi)存輔助空間的大小穩(wěn)定性——若兩個記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。

——便于查找！431.什么是排序？2.排序的目的是什么？存放在數(shù)據(jù)表中按關(guān)排序算法插入排序直接插入排序折半插入排序表插入排序希爾排序交換排序冒泡排序快速排序（不穩(wěn)定）選擇排序歸并排序基數(shù)排序44排序算法插入排序5插入排序插入排序的基本思想是：每步將一個待排序的對象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對象的適當(dāng)位置上，直到對象全部插入為止。簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。45插入排序插入排序的基本思想是：簡言之，邊插入邊排序，保證子序直接插入排序新元素插入到哪里？例1：關(guān)鍵字序列T=（13，6，3，31，9，27，5，11），請寫出直接插入排序的中間過程序列。【13】,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)位置插入，把原來位置上的元素向后順移。最簡單的排序法！46直接插入排序新元素插入到哪里？例1：關(guān)鍵字序列T=（13，6交換排序兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序為止。交換排序的主要算法有：

1)冒泡排序

2)快速排序交換排序的基本思想是：47交換排序

冒泡排序基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。優(yōu)點：每趟結(jié)束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結(jié)束排序。前提：順序存儲結(jié)構(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，

25，

25*，49初態(tài)：第1趟第2趟第3趟第4趟第5趟48冒泡排序基本思路：每趟不斷將記錄兩兩比較，并按“前小后大選擇排序算法：首先找到數(shù)據(jù)清單中的最小的數(shù)據(jù)，然后將這個數(shù)據(jù)同第一個數(shù)據(jù)交換位置；接下來找第二小的數(shù)據(jù)，再將其同第二個數(shù)據(jù)交換位置，以此類推。第1次，在數(shù)組a的n個數(shù)據(jù)中選出其小者（只標(biāo)記其所在位置），若它不在其位置（即其下標(biāo)不等于1）則與第一個數(shù)據(jù)進(jìn)行交換（只需交換一次），經(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次，在數(shù)組后的2個數(shù)據(jù)中，經(jīng)過類似處理后，總可以使數(shù)組a的第n-1個數(shù)據(jù)為第n-1小。而這時候第n個數(shù)據(jù)是第n小。49選擇排序算法：首先找到數(shù)據(jù)清單中的最小的數(shù)據(jù)，然后將這個數(shù)據(jù)查找算法查找之前要求排序，不然無章可查順序查找按照排好序的順序進(jìn)行查找，比如對一個升序排列的數(shù)組中，找到第一個大于需要查找的數(shù)折半查找（二分查找）50查找算法查找之前要求排序，不然無章可查11折半查找先給數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將key與正中元素相比，若key小，則縮小至右半部內(nèi)查找；再取其中值比較，每次縮小1/2的范圍，直到查找成功或失敗為止。Low指向待查元素所在區(qū)間的下界high指向待查元素所在區(qū)間的上界mid指向待查元素所在區(qū)間的中間位置已知如下11個元素的有序表：

（0513192137566475808892）,請查找關(guān)鍵字為21

和85的數(shù)據(jù)元素。51折半查找Low指向待查元素所在區(qū)間的下界high指向待查元素①先設(shè)定3個輔助標(biāo)志:

low,high,mid，顯然有：mid=(low+high)/2②運算步驟：(1)low=1,high=11,mid=6，待查范圍是[1,11]；(2)若ST.elem[mid].key<key，說明key[mid+1,high]，則令：low=mid+1;重算mid＝(low+high)/2；.(3)若ST.elem[mid].key>

key，說明key[low,mid-1]，則令：high=mid–1;重算mid；(4)若ST.elem[mid].key=key，說明查找成功，元素序號=mid;結(jié)束條件：（1）查找成功：ST.elem[mid].key=key

（2）查找不成功：high≤low

（意即區(qū)間長度小于0）折半查找52①先設(shè)定3個輔助標(biāo)志:low,high,mid，折半查找有序插入首先查找要插入的位置，假設(shè)位置為a[L]之前則： for(i=n+1;i>L;i--)a[i]=a[i-1]53有序插入首先查找要插入的位置，假設(shè)位置為a[L]之前14有序刪除比如要刪除a[d]這個元素，則for(j=d;j<n;j++)a[j]=a[j+1]54有序刪除比如要刪除a[d]這個元素，15關(guān)于選擇排序算法：N元數(shù)組a[0]~a[N-1]由小到大排序：

第0步:找到a[0]~a[N-1]中的最小值元素與a[0]交換;

第1步:找到a[1]~a[N-1]中的最小值元素與a[1]交換；

第2步:找到a[2]~a[N-1]中的最小值元素與a[2]交換；

…

第i步:找到a[i]~a[N-1]中的最小值元素與a[i]交換;

…

第N-2步:找到a[N-2]~a[N-1]中的最小值元素與a[N-2]交換。

算法停止。55關(guān)于選擇排序算法：N元數(shù)組a[0]~a[N-1]由小到大排程序一inti,j,minj,t;

for(i=0;i<N-1;i++){

for(j=i+1;j<N-1;j++)

if(a[j]<a[i]){

t=a[i];

a[i]=a[j];

a[j]=t;

}

}

56程序一inti,j,minj,t;

for(i改進(jìn)程序inti,j,minj,t;

for(i=0;i<N-1;i++){

minj=i;

//有什么作用？

for(j=i+1;j<N;j++)

if(a[j]<a[minj])

minj=j;

if(minj!=i){

t=a[i];

a[i]=a[minj];

a[minj]=t;

}

}

57改進(jìn)程序inti,j,minj,t;

for(i找鞍點的問題首先要理清楚思路，再動手編程序58找鞍點的問題首先要理清楚思路，再動手編程序19for(i=0;i<3;i++){max=a[i][0];for(j=0;j<3;j++){if(a[i][j]>max){ max=a[i][j]; maxj=j;/*求出行中最大數(shù)*/ }}for(k=0,flag1=1;k<3&&flag1;k++){if(max>a[k][j]) flag1=0;/*算出該數(shù)是否為列中最小*/}if(flag1==1){printf("\n第%d行,第%d列的%d是鞍點\n",i,maxj,max);flag2=1;/*打印鞍點*/}if(flag2==0)printf("\n矩陣中無鞍點!\n");}59for(i=0;i<3;i++){20折半查找的問題h=0;r=14;m=(h+r)/2;while(h<=r&&x!=a[m]){if(x<a[m]){r=m-1;m=(h+r)/2;}else{h=m+1;m=(h+r)/2;}}if(h>r)printf("無此數(shù)");elseprintf("%d",m);60折半查找的問題h=0;21將一個數(shù)組逆序轉(zhuǎn)換

例如1，2，3，4，5,變?yōu)?，4，3，2，1算法分析：用第一個與最后一個交換。這是a[i],則前面已有i個元素，與它交換的元素a[k]應(yīng)該滿足與a[k]后面也有i個元素，則這個元素的下標(biāo)k為：n-1-i即下標(biāo)i要與下標(biāo)n-i-1交換61將一個數(shù)組逆序轉(zhuǎn)換

例如1，2，3，4，5,變?yōu)?，4，3，將一個數(shù)組逆序轉(zhuǎn)換程序#defineN5main(){inta[N]={9,6,5,4,1},i,temp;

printf("\noriginalarray:\n");

for(i=0;i<N;i++)

printf("%4d",a[i]);

for(i=0;i<N/2;i++)

{ temp=a[i];

a[i]=a[N-i-1]; a[N-i-1]=temp;

}printf("\nsortedarray:\n");for(i=0;i<N;i++)

printf("%4d",a[i]);}62將一個數(shù)組逆序轉(zhuǎn)換程序#defineN523關(guān)于二維數(shù)組的問題（雙下標(biāo)的應(yīng)用）涉及到矩陣的問題，一般使用二維數(shù)組加以解決下面舉幾個稍微復(fù)雜一點的例子，也是某些考試（比如高級程序員）經(jīng)常考到的難題蛇行矩陣問題魔方陣問題矩陣旋轉(zhuǎn)問題63關(guān)于二維數(shù)組的問題（雙下標(biāo)的應(yīng)用）涉及到矩陣的問題，一般使用蛇行方陣問題輸入：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

49341025911681215713141664蛇行方陣問題輸入：N=4

蛇行矩陣將自然數(shù)1,2,…,N*N,逐個順序插入方陣中適當(dāng)?shù)奈恢茫@個過程沿斜列進(jìn)行。將斜列編號為0,1,2,…,2n（以i表記,n=N-1），從圖中看出在一斜列上各元素的下標(biāo)是相等的，且等于斜列號i。同時方陣又可分為上三角與下三角（含對角線）每一斜列上元素個數(shù)為i+1個；下三角每一斜列上元素個數(shù)為2n-i+1個。在斜列上安排數(shù)可以使自右上向左下或自左下向右上兩種方式進(jìn)行，元素可以表示為a[i-j][j]或者a[j][i-j]的形式。65蛇行矩陣將自然數(shù)1,2,…,N*N,逐個順序插入方陣中適當(dāng)?shù)纳咝蟹疥嚨呐艛?shù)方法左下向右右上向左下標(biāo)變量下標(biāo)j的變化下標(biāo)變量下標(biāo)j的變化上三角a[i-j][j]0ia[i-j][j]i0a[j][i-j]i0a[j][i-j]0i下三角a[i-j][j]i-nna[i-j][j]ni-na[j][i-j]ni-na[j][i-j]i-nn66蛇行方陣的排數(shù)方法左下向右右上向左下標(biāo)變量下標(biāo)j的變化下標(biāo)變上三角（包括對角線）for(i=0;i<=n;i++){if(i%2==1){for(j=0;j<=i;j++){a[i-j][j]=k;k++;}}else{for(j=i;j>=0;j--){a[i-j][j]=k;k++;}}}341025911681215713141667上三角（包括對角線）for(i=0;i<=n;i+下三角（不含對角線）for(i=n+1;i<=(2*n);i++){if(i%2==1){for(j=i-n;j<=n;j++){a[i-j][j]=k;k++;}}else{for(j=n;j>=i-n;j--){a[i-j][j]=k;k++;}}}341025911681215713141668下三角（不含對角線）for(i=n+1;i<=螺旋方陣問題12345672425262728298234041424330922394849443110213847464532112037363534331219181716151413

12423222120192254039383718326494847361742742494635165284344453415629303132331478910111213

69螺旋方陣問題1234從a00開始，按照圖所示的從外層到內(nèi)層分別為，上，右，下，左，每進(jìn)一層，一行或一列的元素少2個，其變化規(guī)律是：70從a00開始，按照圖所示的從外層到內(nèi)層分別為，上，右，下，左上行下行左側(cè)右側(cè)順時針行in-in-ii+1in-i-1列in-i-1n-ii+1in-i逆時針行in-iin-i-1n-ii+1列n-ii+1in-i-1in-i上行右側(cè)下行左側(cè)71上行下行左側(cè)右側(cè)順時針行in-in-ii+1i

k=1;for(i=0;i<=(n-1)/2;i++){for(j=i;j<=(