数组应用的技巧与方法

1、1,数组应用的技巧与方法,2,附加：计数器、累加器、累乘器,计数器 int count; while() count + 累加器 int s; for() a=; s=s+a; ,累乘器 int s; 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，1

3、1）， 请写出直接插入排序的中间过程序列。,【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】,在已形成的有序表中线性查找，并在适当位置插入，把原来位置上的元素向后顺移。,最简单的排序法！,8,交换排

4、序,两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序为止。,交换排序的主要算法有： 1) 冒泡排序 2) 快速排序,交换排序的基本思想是：,9,冒泡排序,基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。 优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。 前提：顺序存储结构,例：关键字序列 T=(21，25，49，25*，16，08），请写出冒泡排序的具体实现过程。,21，25，49， 25*，16， 08 21，25，25*，16，

5、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趟,10,选择排序,算法：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。 第1次，在数组a的n个数据中选出其小者（只标记其所在位置），若它不在其位置（即其下标不等于1）则与第一个数据进行交换（只需交换一次），经过本次处理后，总可以使得数组a的第1个数据为第1小。 第2次，在数组a的

6、后n-1个数据（即出去已经选择的最小者的各数据）中，经过类似的处理后，可以使得数组a的第2个数据为第2小。 第i次，在数组a后的n-i+1个数据中，经过类似选择处理后，数组a的第i个数据为第i小。 第n-1次，在数组后的2个数据中，经过类似处理后，总可以使数组a的第n-1个数据为第n-1小。而这时候第n个数据是第n小。,11,查找算法,查找之前要求排序，不然无章可查 顺序查找 按照排好序的顺序进行查找，比如对一个升序排列的数组中，找到第一个大于需要查找的数 折半查找（二分查找）,12,折半查找,先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至右半部

7、内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。,Low指向待查元素所在区间的下界,high指向待查元素所在区间的上界,mid指向待查元素所在区间的中间位置,已知如下11个元素的有序表：（05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21 和85的数据元素。,13, 先设定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，

8、则令：high =mid1;重算 mid ； (4)若 ST.elem mid .key = key，说明查找成功，元素序号=mid; 结束条件：（1）查找成功 ： ST.elemmid.key = key （2）查找不成功 ： highlow （意即区间长度小于0）,折半查找,14,有序插入,首先查找要插入的位置，假设位置为aL之前 则： for (i =n+1;i L;i-) ai=ai-1,15,有序删除,比如要删除ad这个元素， 则 for (j = d;j n;j+) aj=aj+1,16,关于选择排序,算法：N元数组a0aN-1由小到大排序：第0步:找到a0aN-1中的最小值元素与

9、a0交换;第1步:找到a1aN-1中的最小值元素与a1交换；第2步:找到a2aN-1中的最小值元素与a2交换；第i步:找到aiaN-1中的最小值元素与ai交换;第N-2步:找到aN-2aN-1中的最小值元素与aN-2交换。算法停止。,17,程序一,int 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; ,18,改进程序,int i,j,minj,t; for (i = 0;i N-1;i+) minj = i; /有什么作用？ for (j = i + 1

10、;j N;j+) if (aj aminj) 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) printf(n矩阵中无鞍点!n);

11、 ,21,折半查找的问题,h = 0; r = 14; m = (h + r)/2; while(h r) printf(无此数); else printf(%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,将一个数组逆序转换程序,#define N 5 main() int aN=9,6,5,4,1,i,temp; printf(n original array:n);

12、 for(i=0;iN;i+) printf(%4d,ai); for(i=0;iN/2;i+) temp=ai; ai=aN-i-1; aN-i-1=temp; printf(n sorted array:n); for(i=0;iN;i+) printf(%4d,ai); ,24,关于二维数组的问题（双下标的应用）,涉及到矩阵的问题，一般使用二维数组加以解决 下面举几个稍微复杂一点的例子，也是某些考试（比如高级程序员）经常考到的难题 蛇行矩阵问题 魔方阵问题 矩阵旋转问题,25,蛇行方阵问题,输入：N=4 N=7 输出：1 3 4 10 1 3 4 10 11 21 22 2 5 9 11

13、 2 5 9 12 20 23 34 6 8 12 15 6 8 13 19 24 33 35 7 13 1416 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,蛇行矩阵,将自然数1,2,N*N,逐个顺序插入方阵中适当的位置，这个过程沿斜列进行。将斜列编号为0,1,2,2n（以i表记,n=N-1），从图中看出在一斜列上各元素的下标是相等的，且等于斜列号i。同时方阵又可分为上三角与下三角（含对角线）

14、每一斜列上元素个数为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 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

15、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 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 13,31,从a00开始，按照图所示的从外层到内层分别为，上，右，

16、下，左，每进一层，一行或一列的元素少2个，其变化规律是：,32,上行,右侧,下行,左侧,33,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; ,34,方阵旋转问题,顺时针旋转90度 可以将n+1阶矩阵分为(n+1)/2层 每层中可将元素分为n-2i组，每组4个元素，例如图，i标记为1的层（从外向内数的第二层），其中含n-2*i=4组： (a11,a15,a55,a51)、(a12,a25,a54,a41)、

17、(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=ajn-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; int cur_i = 0,cur_j; main() int count,size = 0,i,j; while(size % 2) = 0) /输入