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