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

1、1,数组应用的技巧与方法,2,附加：计数器、累加器、累乘器,计数器intcount;while()count+累加器ints;for()a=;s=s+a;,累乘器ints;for()a=;s=s*a;,3,关于一维数组的问题,一般一维数组所涉及的主要问题有排序插入删除查找分类统计涉及到一些算法，我们通过例题介绍一部分具体问题的解题算法的思路要靠自己慢慢去体会,4,1.什么是排序？将一组杂乱无章的数据按一定的规律顺次排列起来。,2.排序的目的是什么？,存放在数据表中,按关键字排序,3.排序算法的好坏如何衡量？时间效率排序速度（即排序所花费的全部比较次数）空间效率占内存辅助空间的大小稳定性若两个记

2、录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。,便于查找！,5,排序算法,插入排序直接插入排序折半插入排序表插入排序希尔排序交换排序冒泡排序快速排序（不稳定）选择排序归并排序基数排序,6,插入排序,插入排序的基本思想是：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。,简言之，边插入边排序，保证子序列中随时都是排好序的。,7,直接插入排序,新元素插入到哪里？,例1：关键字序列T=（13，6，3，31，9，27，5，11），请写出直接插入排序的中间过程序列。,【13】,6,3,31,9,27,5,11

3、【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,冒泡

4、排序,基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。前提：顺序存储结构,例：关键字序列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趟,10,选择排序,算法：首先找

5、到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。第1次，在数组a的n个数据中选出其小者（只标记其所在位置），若它不在其位置（即其下标不等于1）则与第一个数据进行交换（只需交换一次），经过本次处理后，总可以使得数组a的第1个数据为第1小。第2次，在数组a的后n-1个数据（即出去已经选择的最小者的各数据）中，经过类似的处理后，可以使得数组a的第2个数据为第2小。第i次，在数组a后的n-i+1个数据中，经过类似选择处理后，数组a的第i个数据为第i小。第n-1次，在数组后的2个数据中，经过类似处理后，总可以使数组a的第n-1个数

6、据为第n-1小。而这时候第n个数据是第n小。,11,查找算法,查找之前要求排序，不然无章可查顺序查找按照排好序的顺序进行查找，比如对一个升序排列的数组中，找到第一个大于需要查找的数折半查找（二分查找）,12,折半查找,先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。,Low指向待查元素所在区间的下界,high指向待查元素所在区间的上界,mid指向待查元素所在区间的中间位置,已知如下11个元素的有序表：（0513192137566475808892）,请查找关键字为21和85

7、的数据元素。,13,先设定3个辅助标志:low,high,mid，显然有：mid=(low+high)/2运算步骤：(1)low=1,high=11,mid=6，待查范围是1,11；(2)若ST.elemmid.keykey，说明keylow,mid-1，则令：high=mid1;重算mid；(4)若ST.elemmid.key=key，说明查找成功，元素序号=mid;结束条件：（1）查找成功：ST.elemmid.key=key（2）查找不成功：highlow（意即区间长度小于0）,折半查找,14,有序插入,首先查找要插入的位置，假设位置为aL之前则：for(i=n+1;iL;i-)ai=a

8、i-1,15,有序删除,比如要删除ad这个元素，则for(j=d;jn;j+)aj=aj+1,16,关于选择排序,算法：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交换。算法停止。,17,程序一,inti,j,minj,t;for(i=0;iN-1;i+)for(j=i+1;jN-1;j+)if(ajai)t=ai;ai=aj;aj=t;,18,改进程

9、序,inti,j,minj,t;for(i=0;iN-1;i+)minj=i;/有什么作用？for(j=i+1;jN;j+)if(ajaminj)minj=j;if(minj!=i)t=ai;ai=aminj;aminj=t;,19,找鞍点的问题,首先要理清楚思路，再动手编程序,20,for(i=0;imax)max=aij;maxj=j;/*求出行中最大数*/for(k=0,flag1=1;kakj)flag1=0;/*算出该数是否为列中最小*/if(flag1=1)printf(n第%d行,第%d列的%d是鞍点n,i,maxj,max);flag2=1;/*打印鞍点*/if(flag2=0

10、)printf(n矩阵中无鞍点!n);,21,折半查找的问题,h=0;r=14;m=(h+r)/2;while(hr)printf(无此数);elseprintf(%d,m);,22,将一个数组逆序转换例如1，2，3，4，5,变为5，4，3，2，1,算法分析：用第一个与最后一个交换。,这是ai,则前面已有i个元素，与它交换的元素ak应该满足与ak后面也有i个元素，则这个元素的下标k为：n-1-i即下标i要与下标n-i-1交换,23,将一个数组逆序转换程序,#defineN5main()intaN=9,6,5,4,1,i,temp;printf(noriginalarray:n);for(i=0

11、;iN;i+)printf(%4d,ai);for(i=0;iN/2;i+)temp=ai;ai=aN-i-1;aN-i-1=temp;printf(nsortedarray:n);for(i=0;i=i+1;j-)/左aji=k;k+;if(n%2=0)/最后一个，中间an/2n/2=k;,34,方阵旋转问题,顺时针旋转90度可以将n+1阶矩阵分为(n+1)/2层每层中可将元素分为n-2i组，每组4个元素，例如图，i标记为1的层（从外向内数的第二层），其中含n-2*i=4组：(a11,a15,a55,a51)、(a12,a25,a54,a41)、(a13,a35,a53,a31)、(a14,

12、a45,a52,a21)分析每一个元素，设任意一个为(aij)，则替换该元素的下标axy其中有如下规律:x=n-j,y=i,aij=an-ji,35,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;替换元素下标（也就是等式右边的部分）规律x=n-j,y=i,36,魔方阵,魔方阵是以元素为自然数1,2,N*N方阵。每个元素的值均不等且每行每列以及主副对角线各N个元素的值相等。其算法为：第一个元素的位置在第一行正中新的位置应该处于最近插入位置的右上方，但如果右上方的位置超出方阵上边界，则新的位置应该取列的最下一个位置。超出右边界则取行的最左的一个位置。若最近的插入的元素为n的整数倍，则选下面一行同列上的位置为新的位置。,37,#includestdio.h#defineMAXSIZE15intmagicMAXSIZEMAXSIZE;intcur_i=0,cur_j;main()intcount,size=0,i,j;while(size%2)=0)/输入阶数，只接受奇数printf(nentersquqresize(ODD)number:);scanf