【培训课件】数组应用的技巧与方法(共40张)(PPT 40页)

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

2、较次数）空间效率占内存辅助空间的大小稳定性若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。 便于查找！4第4页，共40页。排序算法插入排序直接插入排序折半插入排序表插入排序希尔排序交换排序冒泡排序快速排序（不稳定）选择排序归并排序基数排序5第5页，共40页。插入排序插入排序的基本思想是： 每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。简言之，边插入边排序，保证子序列中随时都是排好序的。6第6页，共40页。直接插入排序新元素插入到哪里？例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】 在已形成的有序表中线性查找，并在适当位置插入，把原来位置上的元素向后顺移。最简单的排序法！7第7页，共40页。交换排序

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

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

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

7、部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。Low指向待查元素所在区间的下界high指向待查元素所在区间的上界mid指向待查元素所在区间的中间位置 已知如下11个元素的有序表：（05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21 和85的数据元素。12第12页，共40页。 先设定3个辅助标志: low,high,mid，显然有：mid= (low+high)/2 运算步骤：(1) low =1,high =11 ,mid =6 ，待查范围是 1,11；(2) 若 ST.elemmid.key key，说明keylow ,mid-

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

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

10、minj = i; /有什么作用？ for (j = i + 1;j N;j+) if (aj aminj) minj = j; if (minj != i) t = ai; ai = aminj; aminj = t; 18第18页，共40页。找鞍点的问题首先要理清楚思路，再动手编程序19第19页，共40页。for (i=0;i3;i+) max=ai0; for (j=0;jmax)max=aij;maxj=j; /*求出行中最大数*/ for(k=0,flag1=1;kakj) flag1=0; /*算出该数是否为列中最小*/ if (flag1=1) printf(n第%d行,第%d列

11、的%d是鞍点n,i,maxj,max); flag2=1; /*打印鞍点*/ if (flag2=0) printf(n矩阵中无鞍点!n); 20第20页，共40页。折半查找的问题h = 0; r = 14; m = (h + r)/2; while(h=r&x!=am) if (x r) printf(无此数); else printf(%d,m); 21第21页，共40页。将一个数组逆序转换例如1，2，3，4，5,变为5，4，3，2，1算法分析：用第一个与最后一个交换。这是ai,则前面已有i个元素，与它交换的元素ak应该满足与ak后面也有i个元素，则这个元素的下 标k为：n-1-i即下标i

12、要与下标n-i-1交换22第22页，共40页。将一个数组逆序转换程序#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);23第23页，共40页。关于二维数组的问题（双下标的应用）涉及到矩阵的问题，一般使用二维数组加以解决下面举几个稍微复杂一点的例子，也是某

13、些考试（比如高级程序员）经常考到的难题蛇行矩阵问题魔方阵问题矩阵旋转问题24第24页，共40页。蛇行方阵问题输入：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 116 8 12 157 13 14 1625第25页，共40页。蛇行矩阵将自然数1,2,N

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

15、naji-jn i-naji-ji-n n27第27页，共40页。上三角（包括对角线）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第28页，共40页。下三角（不含对角线）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第29页，共40页。

16、螺旋方阵问题1 2 3 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第30页，共40页。从a00开始，按照图所示的从外层到内

17、层分别为，上，右，下，左，每进一层，一行或一列的元素少2个，其变化规律是：31第31页，共40页。上行下行左侧右侧顺时针行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第32页，共40页。 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;

18、j-) /左 aji=k; k+; if (n % 2 = 0) /最后一个，中间 an/2n/2=k; 33第33页，共40页。方阵旋转问题顺时针旋转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-ji34第34页，共40页。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=i35第35页，共40页。魔方阵魔方阵是以元素为自然数1,2,N*N方阵。每个元素的值均不等且每行每列以及主副对角线各N个元素的值相等。其