1、数组应用的技巧与方法1第1页，共40页。附加：计数器、累加器、累乘器附加：计数器、累加器、累乘器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;l2第2页，共40页。关于一维数组的问题关于一维数组的问题l一般一维数组所涉及的主要问题有一般一维数组所涉及的主要问题有l排序排序l插入插入l删除删除l查找查找l分类统计分类统计l涉及到一些算法，我们通过例题介绍一部分涉及到一些算法，我们通过例题介绍一部分l具体问题的解题算法的思路要靠自
2、己慢慢去体会具体问题的解题算法的思路要靠自己慢慢去体会3第3页，共40页。1.什么是排序？什么是排序？将一组杂乱无章的将一组杂乱无章的数据数据按一定的按一定的规律规律顺次排列起来。顺次排列起来。2.排序的目的是什么？排序的目的是什么？存放在数据表中存放在数据表中按关键字排序按关键字排序3.3.排序算法的好坏如何衡量？排序算法的好坏如何衡量？时间效率时间效率排序速度（即排序所花费的全部比较次数）排序速度（即排序所花费的全部比较次数）空间效率空间效率占内存辅助空间的大小占内存辅助空间的大小 稳定性稳定性若两个记录若两个记录A A和和B B的关键字值相等，但排序后的关键字值相等，但排序后A A、B
3、B的先的先后次序保持不变，则称这种排序算法是稳定的。后次序保持不变，则称这种排序算法是稳定的。便于查找！便于查找！4第4页，共40页。排序算法排序算法l插入排序插入排序l直接插入排序直接插入排序l折半插入排序折半插入排序l表插入排序表插入排序l希尔排序希尔排序l交换排序交换排序l冒泡排序冒泡排序l快速排序（不稳定）快速排序（不稳定）l选择排序选择排序l归并排序归并排序l基数排序基数排序5第5页，共40页。插入排序插入排序6第6页，共40页。直接插入排序直接插入排序新元素插入到哪里？新元素插入到哪里？例例1 1：关键字序列关键字序列T=（13，6，3，31，9，27，5，11），），请写出直接插
4、入排序的中间过程序列。请写出直接插入排序的中间过程序列。【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】在已形成的在已形成的有序表中有序表中线性查找线性查找，并在适当，并在适当位置插入，把原来位置上的元素向后位置插入，把原来位置上的元素向后顺移顺移。7第7页，共40页。交换排序交换排序交换排序的主要算法有：交换
5、排序的主要算法有：1)冒泡排序冒泡排序 2)快速排序快速排序8第8页，共40页。基本思路：基本思路：每趟不断将记录两两比较，并按每趟不断将记录两两比较，并按“前小后大前小后大”（或（或“前大前大后小后小”）规则交换。）规则交换。优点：优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。以提前结束排序。前提：前提：顺序存储结构顺序存储结构 例：例：关键字序列关键字序列 T=(21，25，49，25*，16，08），请写出冒泡排），请
6、写出冒泡排序的具体实现过程。序的具体实现过程。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初态：初态：第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟9第9页，共40页。选择排序选择排序l算法：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位算法：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。置；接下来找第二小的数据，再将其同
7、第二个数据交换位置，以此类推。l第第1 1次，在数组次，在数组a a的的n n个数据中选出其小者（只标记其所在位置），若它不在个数据中选出其小者（只标记其所在位置），若它不在其位置（即其下标不等于其位置（即其下标不等于1 1）则与第一个数据进行交换（只需交换一次），经过本）则与第一个数据进行交换（只需交换一次），经过本次处理后，总可以使得数组次处理后，总可以使得数组a a的第的第1 1个数据为第个数据为第1 1小。小。l第第2 2次，在数组次，在数组a a的后的后n-1n-1个数据（即出去已经选择的最小者的各数据）中，个数据（即出去已经选择的最小者的各数据）中，经过类似的处理后，可以使得数组经
8、过类似的处理后，可以使得数组a a的第的第2 2个数据为第个数据为第2 2小。小。l第第i i次，在数组次，在数组a a后的后的n-i+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小。小。10第10页，共40页。查找算法查找算法l查找之前要求排序，不然无章可查查找
9、之前要求排序，不然无章可查l顺序查找顺序查找l按照排好序的顺序进行查找，比如对一个按照排好序的顺序进行查找，比如对一个升序排列的数组中，找到第一个大于需要升序排列的数组中，找到第一个大于需要查找的数查找的数l折半查找（二分查找）折半查找（二分查找）11第11页，共40页。折半查找折半查找先给数据排序先给数据排序（例如按升序排好），形成（例如按升序排好），形成有有序表序表，然后再将，然后再将keykey与正中元素相比，若与正中元素相比，若keykey小，则缩小至右半部内查找；再取其中值比小，则缩小至右半部内查找；再取其中值比较，每次缩小较，每次缩小1/21/2的范围，直到查找成功或的范围，直到查
10、找成功或失败为止。失败为止。LowLow指向待查元素所指向待查元素所在区间的下界在区间的下界highhigh指向待查元素所在区指向待查元素所在区间的上界间的上界midmid指向待查元素所在区间的中指向待查元素所在区间的中间位置间位置 已知如下已知如下11个元素的个元素的有序表有序表：（05 13 19 21 37 56 64 75 80 88 92）,请查找关键字为请查找关键字为21 和和85的数据元素。的数据元素。12第12页，共40页。先设定先设定3 3个辅助标志个辅助标志:low,high,midlow,high,mid，显然有：显然有：mid=mid=(low+high)/2(low+
11、high)/2 运算步骤运算步骤：(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，说明，说明keykey low,midlow,mid-1-1，则令：则令：high=mid1high=mid1;重算重算 mid mid；(4)(4)若若 ST.elem mid.key ST.elem mid.key=key=key，说明查找成功，元素序号，说明查找成功，元素序号=mid;=mid;结束条件：结束条件：（1 1）查
12、找成功）查找成功 ：ST.elemmid.key=keyST.elemmid.key=key （2 2）查找不成功）查找不成功 ：highlowhighlow （意即区间长度小于（意即区间长度小于0 0）折半查找折半查找13第13页，共40页。有序插入有序插入l首先查找要插入的位置，假设位置为aL之前l则：for(i=n+1;i L;i-)ai=ai-114第14页，共40页。有序删除有序删除l比如要删除ad这个元素，则for(j=d;j n;j+)aj=aj+115第15页，共40页。关于选择排序关于选择排序l算法：算法：N元数组元数组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第16页，共40页。程序一程序一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
14、;17第17页，共40页。改进程序改进程序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第18页，共40页。找鞍点的问题找鞍点的问题l首先要理首先要理清楚思路，清楚思路，再动手编再动手编程序程序19第19页，共40页。lfor(i=0;i3;i+)l max=ai0;l for(j=0;jmax)lmax=aij;lmaxj=j;/*求出行中最大数*/ll l for(k=0,flag1=1;k
15、akj)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 20第20页，共40页。折半查找的问题折半查找的问题h=0;r=14;m=(h+r)/2;while(h=r&x!=am)if(x r)printf(无此数);else printf(%d,m);21第21页，共40页。将一个数组逆序转换将一个数组逆序转换例如例如1 1，2 2，3 3，4 4，5,5,变为变为5 5，4
16、4，3 3，2 2，1 1l算法分析：用第一个与最后一个交换。算法分析：用第一个与最后一个交换。这是这是ai,ai,则前面已有则前面已有i i个元素，与它交换的元素个元素，与它交换的元素akak应该满足与应该满足与akak后面也有后面也有i i个元素，则这个元素的下个元素，则这个元素的下 标标k k为：为：n-1-in-1-i即下标即下标i i要与下标要与下标n-i-1n-i-1交换交换22第22页，共40页。将一个数组逆序转换程序将一个数组逆序转换程序l#define N 5lmain()l int aN=9,6,5,4,1,i,temp;lprintf(n original array:n
17、);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第23页，共40页。关于二维数组的问题（双下标的应关于二维数组的问题（双下标的应用）用）l涉及到矩阵的问题，一般使用二维数组涉及到矩阵的问题，一般使用二维数组加以解决加以解决l下面举几个稍微复杂一点的例子，也是下面举几个稍微复杂一点的例子，也是某些考试（比如高级程序员）经常考到某些考试（比如高级程序员）经常考到的
18、难题的难题l蛇行矩阵问题蛇行矩阵问题l魔方阵问题魔方阵问题l矩阵旋转问题矩阵旋转问题24第24页，共40页。蛇行方阵问题蛇行方阵问题输入：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 493 4 102 5 9 116 8 12 157 13 14 1625第25页，共40页。
19、蛇行矩阵蛇行矩阵l将自然数将自然数1,2,N1,2,N*N,N,逐个顺序插入逐个顺序插入方阵中适当的位置，这个过程沿斜列进方阵中适当的位置，这个过程沿斜列进行。将斜列编号为行。将斜列编号为0,1,2,2n0,1,2,2n（以（以i i表表记记,n=N-1,n=N-1），从图中看出在一斜列上），从图中看出在一斜列上各元素的下标是相等的，且等于斜各元素的下标是相等的，且等于斜列号列号i i。同时方阵又可分为上三角与下。同时方阵又可分为上三角与下三角（含对角线）每一斜列上元素个数三角（含对角线）每一斜列上元素个数为为i+1i+1个；下三角每一斜列上元素个数个；下三角每一斜列上元素个数为为2n-i+1
20、2n-i+1个。在斜列上安排数可以使个。在斜列上安排数可以使自右上向左下自右上向左下或或自左下向右上自左下向右上两种方式两种方式进行，元素可以表示为进行，元素可以表示为ai-jjai-jj或者或者aji-jaji-j的形式。的形式。26第26页，共40页。蛇行方阵的排数方法蛇行方阵的排数方法左下向右右上向左下标变量下标j的变化下标变量下标j的变化上三角ai-jj0 iai-jji 0aji-ji 0aji-j0 i下三角ai-jji-n nai-jjn i-naji-jn i-naji-ji-n n27第27页，共40页。上三角（包括对角线）上三角（包括对角线）for(i=0;i=n;i+)i
21、f(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页，共40页。下三角（不含对角线）下三角（不含对角线）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页，共40页。螺旋方阵问题螺旋方阵问题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 4
22、5 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页，共40页。l从从a00a00开始，按照图所开始，按照图所示的从外层到内层分示的从外层到内层分别为，上，右，下，别为，上，右，下，左，每进一层，一行左，每进一层，一行或一列的元素少或一列的元素少2 2个，个，其变化规律是：其变化
23、规律是：31第31页，共40页。上行下行左侧右侧顺时针行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上行右侧下行左侧32第32页，共40页。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;33第33页，共40页。方阵旋转问题方阵旋转问题
24、l顺时针旋转顺时针旋转9090度度l可以将可以将n+1n+1阶矩阵分为阶矩阵分为(n+1)/2(n+1)/2层层l每层中可将元素分为每层中可将元素分为n-2in-2i组，每组组，每组4 4个元素，个元素，例如图，例如图，i i标记为标记为1 1的层（从外向内数的第的层（从外向内数的第二层），其中含二层），其中含n-2n-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分析每一个元素，设任意一个为分析每一个元素，设任意一个为(aij)(aij)，则替，则替换该元素的下标换该元素的下标axyaxy其中有如下规律其中有如下规律:lx=n-j,y=i,aij=an-ji34第34页，共40页。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;l替换元素下标（也就是等式右替换元素下标（也就是等式右边的部分）规律边的部分）规律x=n-j,y=i35第35页，共40页。魔方阵魔方阵l魔方阵是以元
26、素为自然数魔方阵是以元素为自然数1,2,N1,2,N*N N方阵。每个元素的值均不方阵。每个元素的值均不等且每行每列以及主副对角线各等且每行每列以及主副对角线各N N个元素的值相等。个元素的值相等。l其算法为：其算法为：l第一个元素的位置在第一行正中第一个元素的位置在第一行正中l新的位置应该处于最近插入位置的右上方，但如果右上方的位新的位置应该处于最近插入位置的右上方，但如果右上方的位置超出方阵上边界，则新的位置应该取列的最下一个位置。超置超出方阵上边界，则新的位置应该取列的最下一个位置。超出右边界则取行的最左的一个位置。出右边界则取行的最左的一个位置。l若最近的插入的元素为若最近的插入的元素
27、为n n的整数倍，则选下面一行同列上的整数倍，则选下面一行同列上的位置为新的位置。的位置为新的位置。36第36页，共40页。#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;37第37页，共40页。for(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);38第38页，共40页。结束语结束语l“纸上谈兵纸上谈兵”学不出程序设计本领；学不出程序设计本领；只有大量上机、编程、调试，才能只有大量上机、编程、调试，才能掌握。掌握。l学好程序设计语言的唯一途径是上学好程序设计语言的唯一途径是上机。机。l你的编程能力和你在机器上投入的时你的编程能力和你在机器上投入的时间成正比。间成正比。39第39页，共40页。演讲完毕，谢谢观看！第40页，共40页。
