数组应用的技巧与方法课件.ppt

1、1数组应用的技巧与方法数组应用的技巧与方法 2附加：计数器、累加器、累乘器附加：计数器、累加器、累乘器l计数器计数器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;l3关于一维数组的问题关于一维数组的问题l一般一维数组所涉及的主要问题有一般一维数组所涉及的主要问题有l排序排序l插入插入l删除删除l查找查找l分类统计分类统计l涉及到一些算法，我们通过例题介绍一部分涉及到一些算法，我们通过例题介绍一部分l具体问题的解题算法的思路要靠自己慢慢去体具

2、体问题的解题算法的思路要靠自己慢慢去体会会41.什么是排序？什么是排序？将一组杂乱无章的将一组杂乱无章的数据数据按一定的按一定的规律规律顺次排列起来。顺次排列起来。2.排序的目的是什么？排序的目的是什么？存放在数据表中存放在数据表中按按关键字排序关键字排序3.3.排序算法的好坏如何衡量？排序算法的好坏如何衡量？时间效率时间效率排序速度（即排序所花费的全部比较次数）排序速度（即排序所花费的全部比较次数）空间效率空间效率占内存辅助空间的大小占内存辅助空间的大小 稳定性稳定性若两个记录若两个记录A A和和B B的关键字值相等，但排序后的关键字值相等，但排序后A A、B B的先后次序保持不变，则称这种

3、排序算法是稳定的。的先后次序保持不变，则称这种排序算法是稳定的。便于查找！便于查找！5排序算法排序算法l插入排序插入排序l直接插入排序直接插入排序l折半插入排序折半插入排序l表插入排序表插入排序l希尔排序希尔排序l交换排序交换排序l冒泡排序冒泡排序l快速排序（不稳定）快速排序（不稳定）l选择排序选择排序l归并排序归并排序l基数排序基数排序6插入排序插入排序7直接插入排序直接插入排序新元素插入到哪里？新元素插入到哪里？例例1 1：关键字序列关键字序列T=（13，6，3，31，9，27，5，11），），请写出直接插入排序的中间过程序列。请写出直接插入排序的中间过程序列。【13】,6,3,31,9,

4、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】在已形成的在已形成的有序表中有序表中线性查找线性查找，并在，并在适当位置插入，把原来位置上的元素向后适当位置插入，把原来位置上的元素向后顺移顺移。8交换排序交换排序交换排序的主要算法有：交换排序的主要算法有：1)冒泡排序冒泡排序 2)快速排序快速排序9 基本思路：基本思路：每趟不断将记录两两

5、比较，并按每趟不断将记录两两比较，并按“前小后大前小后大”（或（或“前大后小前大后小”）规则交换。）规则交换。优点：优点：每趟结束时，不仅能挤出一个最大值到最后面位置，每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。生，还可以提前结束排序。前提：前提：顺序存储结构顺序存储结构 例：例：关键字序列关键字序列 T=(21，25，49，25*，16，08），），请写出请写出冒泡排序的具体实现过程。冒泡排序的具体实现过程。21，25，49，25*，16，0821，25，25*，16，08，49

6、21，25，16，08，25*，4921，16，08，25，25*，4916，08，21，25，25*，4908，16，21，25，25*，49初态：初态：第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟10选择排序选择排序l算法：首先找到数据清单中的最小的数据，然后将这个数据同第一算法：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。换位置，以此类推。l第第1 1次，在数组次，在数组a a的的n n个数据中选出其小者（只标记其所在位置），个数据中选出其小

7、者（只标记其所在位置），若它不在其位置（即其下标不等于若它不在其位置（即其下标不等于1 1）则与第一个数据进行交换）则与第一个数据进行交换（只需交换一次），经过本次处理后，总可以使得数组（只需交换一次），经过本次处理后，总可以使得数组a a的第的第1 1个数个数据为第据为第1 1小。小。l第第2 2次，在数组次，在数组a a的后的后n-1n-1个数据（即出去已经选择的最小者的各数个数据（即出去已经选择的最小者的各数据）中，经过类似的处理后，可以使得数组据）中，经过类似的处理后，可以使得数组a a的第的第2 2个数据为第个数据为第2 2小。小。l第第i i次，在数组次，在数组a a后的后的n-i

8、+1n-i+1个数据中，经过类似选择处理后，数组个数据中，经过类似选择处理后，数组a a的第的第i i个数据为第个数据为第i i小。小。l第第n-1n-1次，在数组后的次，在数组后的2 2个数据中，经过类似处理后，总可以使数组个数据中，经过类似处理后，总可以使数组a a的第的第n-1n-1个数据为第个数据为第n-1n-1小。而这时候第小。而这时候第n n个数据是第个数据是第n n小。小。11查找算法查找算法l查找之前要求排序，不然无章可查查找之前要求排序，不然无章可查l顺序查找顺序查找l按照排好序的顺序进行查找，比如对按照排好序的顺序进行查找，比如对一个升序排列的数组中，找到第一个一个升序排列

9、的数组中，找到第一个大于需要查找的数大于需要查找的数l折半查找（二分查找）折半查找（二分查找）12折半查找折半查找先给数据排序先给数据排序（例如按升序排好），形成（例如按升序排好），形成有序表有序表，然后再将，然后再将keykey与正中元素相比，与正中元素相比，若若keykey小，则缩小至右半部内查找；再小，则缩小至右半部内查找；再取其中值比较，每次缩小取其中值比较，每次缩小1/21/2的范围，的范围，直到查找成功或失败为止。直到查找成功或失败为止。LowLow指向待查元素指向待查元素所在区间的下界所在区间的下界highhigh指向待查元素所指向待查元素所在区间的上界在区间的上界midmid指

10、向待查元素所在指向待查元素所在区间的中间位置区间的中间位置 已知如下已知如下11个元素的个元素的有序表有序表：（05 13 19 21 37 56 64 75 80 88 92）,请查找关键字为请查找关键字为21 和和85的数据元素。的数据元素。13 先设定先设定3 3个辅助标志个辅助标志:low,high,midlow,high,mid，显然有：显然有：mid=mid=(low+high)/2(low+high)/2 运算步骤运算步骤：(1)low=1,high=11,mid=6(1)low=1,high=11,mid=6，待查范围是待查范围是 1,111,11；(2)(2)若若 ST.el

11、emmid.keyST.elemmid.key key keykey，说明说明keykey low,midlow,mid-1-1，则令：则令：high=mid1high=mid1;重算重算 mid mid；(4)(4)若若 ST.elemST.elem mid.key mid.key=key=key，说明查找成功，元素序号说明查找成功，元素序号=mid;=mid;结束条件：结束条件：（1 1）查找成功）查找成功 ：ST.elemmid.keyST.elemmid.key=key=key （2 2）查找不成功查找不成功 ：highlowhighlow （意即区间长度小于意即区间长度小于0 0）折

12、半查找折半查找14有序插入有序插入l首先查找要插入的位置，假设位置为aL之前l则：for(i=n+1;i L;i-)ai=ai-115有序删除有序删除l比如要删除ad这个元素，则for(j=d;j n;j+)aj=aj+116 关于选择排序关于选择排序l算法：算法：N元数组元数组a0aN-1由小到大排序：由小到大排序：第第0步步:找到找到a0aN-1中的最小值元素与中的最小值元素与a0交换交换;第第1步步:找到找到a1aN-1中的最小值元素与中的最小值元素与a1交换；交换；第第2步步:找到找到a2aN-1中的最小值元素与中的最小值元素与a2交换；交换；第第i步步:找到找到aiaN-1中的最小值

13、元素与中的最小值元素与ai交换交换;第第N-2步步:找到找到aN-2aN-1中的最小值元素与中的最小值元素与aN-2交换。交换。算法停止。算法停止。17程序一程序一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=aj;aj=t;18改进程序改进程序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;19找鞍点的问题找

14、鞍点的问题l首先要理首先要理清楚思路，清楚思路，再动手编再动手编程序程序20lfor(i=0;i3;i+)l max=ai0;l for(j=0;jmax)lmax=aij;lmaxj=j;/*求出行中最大数*/ll l for(k=0,flag1=1;kakj)l flag1=0;/*算出该数是否为列中最小*/l l if(flag1=1)l printf(n第%d行,第%d列的%d是鞍点n,i,maxj,max);l flag2=1;/*打印鞍点*/l l if(flag2=0)l printf(n矩阵中无鞍点!n);l 21折半查找的问题折半查找的问题h=0;r=14;m=(h+r)/2

15、;while(h=r&x!=am)if(x r)printf(无此数);else printf(%d,m);22将一个数组逆序转换将一个数组逆序转换例如例如1 1，2 2，3 3，4 4，5,5,变为变为5 5，4 4，3 3，2 2，1 1l算法分析：用第一个与最后一个交换。算法分析：用第一个与最后一个交换。这是这是aiai,则前面已有则前面已有i i个元素，与它交换的元素个元素，与它交换的元素akak 应该应该满足与满足与akak 后面也有后面也有i i个元素，则这个元素的下个元素，则这个元素的下 标标k k为：为：n-1-in-1-i即下标即下标i i要与下标要与下标n-i-1n-i-1

16、交换交换23将一个数组逆序转换程序将一个数组逆序转换程序l#define N 5lmain()l int aN=9,6,5,4,1,i,temp;lprintf(n original 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);l24关于二维数组的问题（双下标的应关于二维数组的问题（双下标的应用）用）l涉及到矩阵的问题，一般使用二维涉及到矩阵的问题

17、，一般使用二维数组加以解决数组加以解决l下面举几个稍微复杂一点的例子，下面举几个稍微复杂一点的例子，也是某些考试（比如高级程序员）也是某些考试（比如高级程序员）经常考到的难题经常考到的难题l蛇行矩阵问题蛇行矩阵问题l魔方阵问题魔方阵问题l矩阵旋转问题矩阵旋转问题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 3

18、0 38 41 45 48 28 29 39 40 46 47 4913 4 102 5 9 116 8 12 157 13 14 1626蛇行矩阵蛇行矩阵l将自然数将自然数1,2,1,2,N,N*N,N,逐个顺逐个顺序插入方阵中适当的位置，这序插入方阵中适当的位置，这个过程沿斜列进行。将斜列编个过程沿斜列进行。将斜列编号为号为0,1,2,0,1,2,2n,2n（以（以i i表表记记,n=N-1,n=N-1），从图中看出在一），从图中看出在一斜列上各元素的下标是相等的，斜列上各元素的下标是相等的，且等于斜列号且等于斜列号i i。同时方阵又。同时方阵又可分为上三角与下三角（含对可分为上三角与下三

19、角（含对角线）每一斜列上元素个数为角线）每一斜列上元素个数为i+1i+1个；下三角每一斜列上元个；下三角每一斜列上元素个数为素个数为2n-i+12n-i+1个。在斜列上个。在斜列上安排数可以使安排数可以使自右上向左下自右上向左下或或自左下向右上自左下向右上两种方式进行，两种方式进行，元素可以表示为元素可以表示为ai-jjai-jj或或者者aji-jaji-j 的形式。的形式。27蛇行方阵的排数方法蛇行方阵的排数方法左下向右右上向左下标变量下标j的变化下标变量下标j的变化上三角ai-jj0 iai-jji 0aji-ji 0aji-j0 i下三角ai-jji-n nai-jjn i-naji-j

20、n i-naji-ji-n n28上三角（包括对角线）上三角（包括对角线）for(i=0;i=n;i+)if(i%2=1)for(j=0;j=0;j-)ai-jj=k;k+;13 4 102 5 9 116 8 12 157 13 14 1629下三角（不含对角线）下三角（不含对角线）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 1630螺旋方阵问题螺旋方阵问题1 2 3 4 5 6 724 25 26 27 28 29 823 40 41 42 43 30

21、 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 31l从从a00a00开始，按照图开始，按照图所示的从外层到内层所示的从外层到内层分别为，上，右，下，分别为，上，右，下，左，每进一层，一行左，每进一层，一行或一列的元素

22、少或一列的元素少2 2个，个，其变化规律是：其变化规律是：32上行下行左侧右侧顺时针行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上行右侧下行左侧33 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)/最后一个，中间 an/2n/2=k;34方阵旋转问题方阵旋转问题l顺时针

23、旋转顺时针旋转9090度度l可以将可以将n+1n+1阶矩阵分为阶矩阵分为(n+1)/2(n+1)/2层层l每层中可将元素分为每层中可将元素分为n-2in-2i组，每组组，每组4 4个元素，例如图，个元素，例如图，i i标记为标记为1 1的层（从的层（从外向内数的第二层），其中含外向内数的第二层），其中含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,a4

24、5,a52,a21)l分析每一个元素，设任意一个为分析每一个元素，设任意一个为(aijaij)，则替换该元素的下标，则替换该元素的下标axyaxy 其中有如下规律其中有如下规律:lx=n-j,y=i,aij=an-ji35for(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替换元素下标（也就是等式替换元素下标（也就是等式右边的部分）规律右边的部分）规律x=n-j,y=i36魔方阵魔方阵l魔方阵是以元素为自然数魔方阵是以元素为自然数1,2,1,2,

25、N N*N N方阵。每个元素的值方阵。每个元素的值均不等且每行每列以及主副对角线各均不等且每行每列以及主副对角线各N N个元素的值相等。个元素的值相等。l其算法为：其算法为：l第一个元素的位置在第一行正中第一个元素的位置在第一行正中l新的位置应该处于最近插入位置的右上方，但如果右上新的位置应该处于最近插入位置的右上方，但如果右上方的位置超出方阵上边界，则新的位置应该取列的最下方的位置超出方阵上边界，则新的位置应该取列的最下一个位置。超出右边界则取行的最左的一个位置。一个位置。超出右边界则取行的最左的一个位置。l若最近的插入的元素为若最近的插入的元素为n n的整数倍，则选下面一行同列的整数倍，则

26、选下面一行同列上的位置为新的位置。上的位置为新的位置。37#include stdio.h#define MAXSIZE 15int magicMAXSIZEMAXSIZE;int cur_i=0,cur_j;main()int count,size=0,i,j;while(size%2)=0)/输入阶数，只接受奇数 printf(n enter squqre size(ODD)number:);scanf(%d,&size);cur_j=(size-1)/2;38for(count=1;count size-1)/如果列越界如果列越界 cur_j-=size;/end count for(i=0;i size;i+)printf(n);for(j=0;j size;j+)printf(%3d,magicij);39结束语结束语l“纸上谈兵纸上谈兵”学不出程序设计本领；学不出程序设计本领；只有大量上机、编程、调试，才能只有大量上机、编程、调试，才能掌握。掌握。l学好程序设计语言的唯一途径是上学好程序设计语言的唯一途径是上机。机。l你的编程能力和你在机器上投入的你的编程能力和你在机器上投入的时间成正比。时间成正比。