《【培训课件】数组应用的技巧与方法》由会员分享，可在线阅读，更多相关《【培训课件】数组应用的技巧与方法（39页珍藏版）》请在金锄头文库上搜索。
1、数组应用的技巧与方法 1附加：计数器、累加器、累乘器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.排序算法的好坏如何衡量？ 时间效率排序速度（即
2、排序所花费的全部比较次数） 空间效率占内存辅助空间的大小 稳定性若两个记录A和B的关键字值相等，但排序后A、 B的先后次序保持不变，则称这种排序算法是稳定的。便于查找！4排序算法l插入排序l直接插入排序l折半插入排序l表插入排序l希尔排序l交换排序l冒泡排序l快速排序（不稳定）l选择排序l归并排序l基数排序5插入排序插入排序的基本思想是：插入排序的基本思想是：每步将一个待排序的对象，按其关键码大小，插入每步将一个待排序的对象，按其关键码大小，插入 到前面已经排好序的一组对象的适当位置上，直到对到前面已经排好序的一组对象的适当位置上，直到对 象全部插入为止。象全部插入为止。简言之，边插入边排序，
3、保证子序列中随时都是排好序的。简言之，边插入边排序，保证子序列中随时都是排好序的。6直接插入排序新元素插入到哪里？例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】
4、, 11 【3, 5, 6, 9, 11，13，27, 31】 在已形成的有序表中线性查找，并在 适当位置插入，把原来位置上的元素向后顺移。最简单的排序法！最简单的排序法！7交换排序两两比较待排序记录的关键两两比较待排序记录的关键 码，如果发生逆序（即排列顺序与排序后的次序正好码，如果发生逆序（即排列顺序与排序后的次序正好 相反），则交换之，直到所有记录都排好序为止。相反），则交换之，直到所有记录都排好序为止。交换排序的主要算法有：1) 冒泡排序2) 快速排序交换排序的基本思想是：交换排序的基本思想是：8冒泡排序冒泡排序基本思路：每趟不断将记录两两比较，并按“前小后大”（ 或“前大后小”）规则
5、交换。优点：每趟结束时，不仅能挤出一个最大值到最后面位置 ，还能同时部分理顺其他元素；一旦下趟没有交换 发生，还可以提前结束排序。 前提：顺序存储结构 例：关键字序列 T=(21，25，49，25*，16，08），请写出 冒泡排序的具体实现过程。 21，25，49， 25*，16， 08 21，25，25*，16， 08 ， 49 21，25， 16， 08 ，25*，49 21，16， 08 ，25， 25*，49 16，08 ，21， 25， 25*，49 08，16， 21， 25， 25*，49初态： 第1趟 第2趟 第3趟 第4趟 第5趟9选择排序l算法：首先找到数据清单中的最小的数
6、据，然后将这个数据同第一 个数据交换位置；接下来找第二小的数据，再将其同第二个数据交 换位置，以此类推。l第1次，在数组a的n个数据中选出其小者（只标记其所在位置），若 它不在其位置（即其下标不等于1）则与第一个数据进行交换（只需 交换一次），经过本次处理后，总可以使得数组a的第1个数据为第1 小。l第2次，在数组a的后n-1个数据（即出去已经选择的最小者的各数据 ）中，经过类似的处理后，可以使得数组a的第2个数据为第2小。l第i次，在数组a后的n-i+1个数据中，经过类似选择处理后，数组a 的第i个数据为第i小。l第n-1次，在数组后的2个数据中，经过类似处理后，总可以使数组a 的第n-1个
7、数据为第n-1小。而这时候第n个数据是第n小。10查找算法l查找之前要求排序，不然无章可查l顺序查找l按照排好序的顺序进行查找，比如对 一个升序排列的数组中，找到第一个 大于需要查找的数l折半查找（二分查找）11折半查找先给数据排序（例如按升序排好），形成 有序表，然后再将key与正中元素相比 ，若key小，则缩小至右半部内查找； 再取其中值比较，每次缩小1/2的范围 ，直到查找成功或失败为止。Low指向待查元素 所在区间的下界high指向待查元素所 在区间的上界mid指向待查元素所在 区间的中间位置已知如下11个元素的有序表： （05 13 19 21 37 56 64 75 80 88 9
8、2）, 请查找关键字为21和85的数据元素。12 先设定3个辅助标志: low,high,mid， 显然有：mid= (low+high)/2 运算步骤： (1) low =1,high =11 ,mid =6 ，待查范围是 1,11； (2) 若 ST.elemmid.key key，说明keylow ,mid-1，则令：high =mid1;重算 mid ； (4)若 ST.elem mid .key = key，说明查找成功，元素序号=mid; 结束条件：（1）查找成功 ： ST.elemmid.key = key（2）查找不成功 ： highlow （意即区间长度小于0）折半查找13有
9、序插入l首先查找要插入的位置，假设位置为aL之前l则： for (i =n+1;i L;i-)ai=ai-114有序删除l比如要删除ad这个元素，则 for (j = d;j max)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
10、= 0;r = 14; m = (h + r)/2; while(h r) printf(“无此数“); else printf(“%d“,m); 21将一个数组逆序转换 例如1，2，3，4，5,变为5，4，3，2，1l算法分析：用第一个与最后一个交换。这是ai,则前面已有i个元素，与它交换的元素ak应该 满足与ak后面也有i个元素，则这个元素的下 标k为：n- 1-i即下标i要与下标n-i-1交换22将一个数组逆序转换程序l#define N 5lmain()l int aN=9,6,5,4,1,i,temp;l printf(“n original array:n“);l for(i=0;
11、i=0;j-) ai-jj = k;k+; 13 4 102 5 9 116 8 12 157 13 14 1628下三角（不含对角线）for (i = n + 1;i =i- n;j-) ai-jj = k;k+; 13 4 102 5 9 116 8 12 157 13 14 1629螺旋方阵问题1 2 3 4 5 6 7 24 25 26 27 28 29 8 23 40 41 42 43 30 9 22 39 48 49 44 31 10 21 38 47 46 45 32 11 20 37 36 35 34 33 12 19 18 17 16 15 14 131 24 23 22 2
12、1 20 19 2 25 40 39 38 37 18 3 26 49 48 47 36 17 4 27 42 49 46 35 16 5 28 43 44 45 34 15 6 29 30 31 32 33 14 7 8 9 10 11 12 1330l从a00开始，按照图 所示的从外层到内层 分别为，上，右，下 ，左，每进一层，一 行或一列的元素少2 个，其变化规律是：31上行下行左侧右侧 顺时 针行in-in-i i+1 i 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
13、k=1;for (i = 0;i = 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顺时针旋转90度l可以将n+1阶矩阵分为(n+1)/2层l每层中可将元素分为n-2i组，每组4 个元素，例如图，i标记为1的层（从 外向内数的第二层），其中含n- 2*i=4组：l(a11,a15,a55,a51)、 (a12,a25,a54,a41)、 (a13,a35,a53,a31)、 (a14,a45,a52,a21)l分析每一个元素，设任意一个为 (aij)，则替换该元素的下标axy 其中有如下规律:lx=n-j,y=i,aij=an-ji34for (i = 0;i size-1) /如果列越界cur_j -= size;/end countfor (i = 0;i size;i+) printf(“n“);for (j = 0;j size;j+)printf(“%3d“,magicij); 38结束语l“纸上谈兵”学不出程序设计本领； 只有大量上机、编程、调试，才能 掌握。l学好程序设计语言的唯一途径是上 机。l你的编程能力和你在机器上投入的 时间成正比。39
