数组应用的技巧与方法_第1页
数组应用的技巧与方法_第2页
数组应用的技巧与方法_第3页
数组应用的技巧与方法_第4页
数组应用的技巧与方法_第5页
已阅读5页,还剩34页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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) /输入

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论