《数组应用的技巧与方法.ppt》由会员分享，可在线阅读，更多相关《数组应用的技巧与方法.ppt（39页珍藏版）》请在三一文库上搜索。
1、1,数组应用的技巧与方法,桂林电子科技大学 周信东,2,常用算法：计数器、累加器、累乘器,计数器 int count=0; while () count + 累加器 int s=0; for () a=; s=s+a; ,累乘器 int s=1; for () a=; s=s*a; ,3,关于一维数组的问题,一般一维数组所涉及的主要问题有 排序 插入 删除 查找 分类统计 涉及到一些算法，我们通过例题介绍一部分 具体问题的解题算法的思路要靠自己慢慢去体会,4,1. 什么是排序？ 将一组杂乱无章的数据按一定的规律顺次排列起来。,2. 排序的目的是什么？,存放在数据表中,按关键字排序,3.排序算法
2、的好坏如何衡量？ 时间效率排序速度（即排序所花费的全部比较次数） 空间效率占内存辅助空间的大小 稳定性若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。,便于查找,5,常见排序算法,插入排序 直接插入排序 折半插入排序 表插入排序 希尔排序 交换排序 冒泡排序 快速排序（不稳定） 选择排序 归并排序 基数排序,6,插入排序,插入排序的基本思想是： 每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。,简言之，边插入边排序，保证子序列中随时都是排好序的。,7,直接插入排序,新元素插入到哪里？,例1：关
3、键字序列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】,在已形成的有序表中线性查找，并在适当位置插入，把原来位
4、置上的元素向后顺移。,最简单的排序法！,8,有序插入,首先查找要插入的位置，假设位置为aL之前 则： for (i =n+1;i L;i-) ai=ai-1,9,有序删除,比如要删除ad这个元素， 则 for (j = d;j n;j+) aj=aj+1,10,交换排序,两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序为止。,交换排序的主要算法有： 1) 冒泡排序 2) 快速排序,交换排序的基本思想是：,11,冒泡排序,基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。 优点：每趟结束时，不仅能挤出一个最大
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趟,12,冒泡排序法关键程序,int i,j,minj,t; for (i = 0;i N-1
6、;i+) for (j = i + 1;j N-1;j+) if (aj ai) t = ai; ai = aj; aj = t; ,13,选择排序（快速排序）,算法：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。 第1次，在数组a的n个数据中选出其小者（只标记其所在位置），若它不在其位置（即其下标不等于1）则与第一个数据进行交换（只需交换一次），经过本次处理后，总可以使得数组a的第1个数据为第1小。 第2次，在数组a的后n-1个数据（即出去已经选择的最小者的各数据）中，经过类似的处理后，可以使得数组a的第2个数
7、据为第2小。 第i次，在数组a后的n-i+1个数据中，经过类似选择处理后，数组a的第i个数据为第i小。 第n-1次，在数组后的2个数据中，经过类似处理后，总可以使数组a的第n-1个数据为第n-1小。而这时候第n个数据是第n小。,14,关于选择排序,算法：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交换。 算法停止。,15,选择排序法程序,in
8、t 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; ,减少了数据交换的次数！,16,查找算法,查找之前要求排序，不然无章可查 顺序查找 按照排好序的顺序进行查找，比如对一个升序排列的数组中，找到第一个大于需要查找的数 折半查找（二分查找）,17,折半查找（二分查找）,先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小
9、至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。,Low指向待查元素所在区间的下界,high指向待查元素所在区间的上界,mid指向待查元素所在区间的中间位置,已知如下11个元素的有序表： （05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21 和85的数据元素。,18, 先设定3个辅助标志: low,high,mid， 显然有：mid= (low+high)/2 运算步骤：（key为要查找的值） (1) low =1,high =11 ,mid =6 ，待查范围是 1,11； (2) 若 elemmid key，说明keylow
10、 ,mid-1， 则令：high =mid1;重算 mid ； (4)若 elem mid = key，说明查找成功，元素序号=mid; 结束条件：（1）查找成功 ： elemmid = key （2）查找不成功 ： highlow （意即区间长度小于0）,折半查找,19,折半查找法程序,int BinSearch(int R, int n, int Key) /功能：在有序表R0n-1中进行折半查找 /返回值：查找成功时返回数组下标，否则返回-1 int low=0,high=n-1,mid; /置当前查找区间上、下界的初值 while(lowKey) high=mid-1; /继续在Rlo
11、wmid-1中查找 else low=mid+1; /继续在Rmid+1high中查找 return -1; /当lowhigh时表示查找区间为空，查找失败 ,20,首先要理清楚思路，再动手编程序,找鞍点的问题,21,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) printf(“n矩阵中无鞍点!
12、n“); ,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,将一个数组逆序转换程序,#define N 5 main() int aN=9,6,5,4,1,i,temp; printf(“n original array:n“); for(i=0; iN; i+) printf(“%4d“, ,24,关于二维数组的问题（双下标的应用）,涉及到矩阵的问题，一般使用二维数组加以解决
13、下面举几个稍微复杂一点的例子，也是某些考试（比如高级程序员）经常考到的难题 蛇行矩阵问题 魔方阵问题 矩阵旋转问题,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 30 38 41 45 48 28 29 39 40 46 47 49,3 4 10 2 5 9 11 6 8 12 15 7 13 14 16,26,蛇
14、行矩阵,将自然数1,2,N*N,逐个顺序插入方阵中适当的位置，这个过程沿斜列进行。将斜列编号为0,1,2,2n（以i表记,n=N-1），从图中看出在一斜列上各元素的下标是相等的，且等于斜列号i。同时方阵又可分为上三角与下三角（含对角线）每一斜列上元素个数为i+1个；下三角每一斜列上元素个数为2n-i+1个。在斜列上安排数可以使自右上向左下或自左下向右上两种方式进行，元素可以表示为ai-jj或者aji-j的形式。,27,蛇行方阵的排数方法,28,上三角（包括对角线）,for (i=0; i=0; j-) ai-jj = k; k+; ,3 4 10 2 5 9 11 6 8 12 15 7 13
15、 14 16,29,下三角（不含对角线）,for (i=n+1; i=i-n; j-) ai-jj = k; k+; ,3 4 10 2 5 9 11 6 8 12 15 7 13 14 16,30,螺旋方阵问题,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 13,1 24 23 22 21 20 19 2 25 40 39 38 37 18 3 26 49 48 47 3
16、6 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 13,31,从a00开始，按照图所示的从外层到内层分别为：上、右、下、左，每进一层，一行或一列的元素少2个，其变化规律是：,32,上行,右侧,下行,左侧,33,k=1; for ( i=0; i=i+1; j-) /下 an-ij=k+; for ( j=n-i; j=i+1; j-) /左 aji=k+; if (n%2 = 0) /最后一个，中间 an/2n/2=k;,34,方阵旋转问题,顺时针旋转90度 可以将n+1阶矩阵分为(n
17、+1)/2层 每层中可将元素分为n-2i组，每组4个元素，例如图，i标记为1的层（从外向内数的第二层），其中含n-2*i=4组： (a11,a15,a55,a51)、(a12,a25,a54,a41)、(a13,a35,a53,a31)、(a14,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=aj
18、n-i; ajn-i=temp; 替换元素下标（也就是等式右边的部分）规律 x=n-j,y=i,36,魔方阵,魔方阵是以元素为自然数1,2,N*N方阵。每个元素的值均不等且每行每列以及主副对角线各N个元素的值相等。 其算法为： 第一个元素的位置在第一行正中 新的位置应该处于最近插入位置的右上方，但如果右上方的位置超出方阵上边界，则新的位置应该取列的最下一个位置。超出右边界则取行的最左的一个位置。 若最近的插入的元素为n的整数倍，则选下面一行同列上的位置为新的位置。,37,#include “stdio.h“ #define MAXSIZE 15 int magicMAXSIZEMAXSIZE;
19、 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“,魔方阵参考程序,38,for(count=1; count size-1) /如果列越界 cur_j -= size; /end count for (i=0; isize; i+) printf(“n“); for (j=0; jsize; j+) printf(“%3d“,magicij); ,39,结束语,“纸上谈兵”学不出程序设计本领；只有大量上机、编程、调试，才能掌握。 学好程序设计语言的唯一途径是上机。 你的编程能力和你在机器上投入的时间成正比。,