【培训】数组应用的技巧与方法ppt课件

1、数组运用的技巧与方法1附加：计数器、累加器、累乘器计数器int count;while() count +累加器int s;for() a=; s=s+a;累乘器int s;for() a=; s=s*a;2关于一维数组的问题普通一维数组所涉及的主要问题有排序插入删除查找分类统计涉及到一些算法，我们经过例题引见一部分详细问题的解题算法的思绪要靠本人渐渐去领会31. 什么是排序？ 将一组杂乱无章的数据按一定的规律依次陈列起来。 2. 排序的目的是什么？存放在数据表中按关键字排序3.排序算法的好坏如何衡量？时间效率排序速度即排序所破费的全部比较次数空间效率占内存辅助空间的大小稳定性假设两个记录A和

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

3、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交换排序 两两比较待排序记录的关键码，假设发生逆序即陈列顺序与排序后的次序正好相反，那么交换之，直到一切记录都排好序为止。交换排序的主要算法有：

4、 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， 2

5、5， 25*，49初态：第1趟第2趟第3趟第4趟第5趟9选择排序算法：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。第1次，在数组a的n个数据中选出其小者只标志其所在位置，假设它不在其位置即其下标不等于1那么与第一个数据进展交换只需交换一次，经过本次处置后，总可以使得数组a的第1个数据为第1小。第2次，在数组a的后n-1个数据即出去曾经选择的最小者的各数据中，经过类似的处置后，可以使得数组a的第2个数据为第2小。第i次，在数组a后的n-i+1个数据中，经过类似选择处置后，数组a的第i个数据为第i小。第n-1次，在

6、数组后的2个数据中，经过类似处置后，总可以使数组a的第n-1个数据为第n-1小。而这时候第n个数据是第n小。10查找算法查找之前要求排序，不然无章可查顺序查找按照排好序的顺序进展查找，比如对一个升序陈列的数组中，找到第一个大于需求查找的数折半查找二分查找11折半查找先给数据排序例如按升序排好，构成有序表，然后再将key与正中元素相比，假设key小，那么减少至右半部内查找；再取其中值比较，每次减少1/2的范围，直到查找胜利或失败为止。Low指向待查元素所在区间的下界high指向待查元素所在区间的上界mid指向待查元素所在区间的中间位置 知如下11个元素的有序表：05 13 19 21 37 56

7、 64 75 80 88 92, 请查找关键字为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 意即区间长度小于

8、0折半查找13有序插入首先查找要插入的位置，假设位置为aL之前那么：for (i =n+1;i L;i-) ai=ai-114有序删除比如要删除ad这个元素，那么for (j = d;j n;j+) aj=aj+115 关于选择排序算法：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程序一int i,j,minj,t; for (i

9、= 0;i N-1;i+) for (j = i + 1;j N-1;j+) if (aj ai) t = ai; ai = aj; aj = t; 17改良程序int 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找鞍点的问题首先要理清楚思绪，再动手编程序19for (i=0;i3;i+) max=ai0; for (j=0;jmax)max=aij

10、;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); 20折半查找的问题h = 0; r = 14; m = (h + r)/2; while(h=r&x!=am) if (x r) printf(无此数); else printf(%d,m); 21将一个数组逆序转换例如1，2，3，4，5,变为5，4，3，2，1

11、算法分析：用第一个与最后一个交换。这是ai,那么前面已有i个元素，与它交换的元素ak应该满足与ak后面也有i个元素，那么这个元素的下 标k为：n-1-i即下标i要与下标n-i-1交换22将一个数组逆序转换程序#define N 5main() int aN=9,6,5,4,1,i,temp;printf(n original array:n);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

12、);23关于二维数组的问题双下标的运用涉及到矩阵的问题，普通运用二维数组加以处理下面举几个略微复杂一点的例子，也是某些考试比如高级程序员经常考到的难题蛇行矩阵问题魔方阵问题矩阵旋转问题24蛇行方阵问题输入：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 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 493 4 102 5 9

13、116 8 12 157 13 14 1625蛇行矩阵将自然数1,2,N*N,逐个顺序插入方阵中适当的位置，这个过程沿斜列进展。将斜列编号为0,1,2,2n以i表记,n=N-1，从图中看出在一斜列上各元素的下标是相等的，且等于斜列号i。同时方阵又可分为上三角与下三角含对角线每一斜列上元素个数为i+1个；下三角每一斜列上元素个数为2n-i+1个。在斜列上安排数可以使自右上向左下或自左下向右上两种方式进展，元素可以表示为ai-jj或者aji-j的方式。26蛇行方阵的排数方法左下向右右上向左下标变量下标j的变化下标变量下标j的变化上三角ai-jj0 iai-jji 0aji-ji 0aji-j0 i

14、下三角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+; 3 4 102 5 9 116 8 12 157 13 14 1628下三角不含对角线for (i = n + 1;i = (2 * n);i+) if (i %2 = 1) for (j = i - n;j =i- n;j-) ai-jj = k; k+; 3 4 102 5 9 116 8 12 157 13 14 1629螺旋方阵问题1 2 3

15、4 5 6 724 25 26 27 28 29 823 40 41 42 43 30 922 39 48 49 44 31 1021 38 47 46 45 32 1120 37 36 35 34 33 1219 18 17 16 15 14 13 1 24 23 22 21 20 192 25 40 39 38 37 183 26 49 48 47 36 174 27 42 49 46 35 165 28 43 44 45 34 156 29 30 31 32 33 147 8 9 10 11 12 13 30从a00开场，按照图所示的从外层到内层分别为，上，右，下，左，每进一层，一行或一

16、列的元素少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) /最后一个，中间

17、an/2n/2=k; 33方阵旋转问题顺时针旋转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,a45,a52,a21)分析每一个元素，设恣意一个为(aij)，那么交换该元素的下标axy其中有如下规律:x=n-j,y=i,aij=an-ji34for (i = 0;i = (n - 1) / 2;i+) for(j = i;j = (n - i - 1);j+) temp=

18、aij; aij=an-ji; an-ji=an-in-j; an-in-j=ajn-i; ajn-i=temp; 交换元素下标也就是等式右边的部分规律x=n-j,y=i35魔方阵魔方阵是以元素为自然数1,2,N*N方阵。每个元素的值均不等且每行每列以及主副对角线各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(