《数组应用的技与方法》由会员分享，可在线阅读，更多相关《数组应用的技与方法（39页珍藏版）》请在金锄头文库上搜索。
1、数组应用的技巧与方法数组应用的技巧与方法桂林电子科技大学桂林电子科技大学周信东周信东1常用算法：计数器、累加器、累乘器常用算法：计数器、累加器、累乘器l计数器计数器int count=0;while () count +l累加器累加器int s=0;for () a=; s=s+a;l累乘器累乘器int s=1;for () a=; s=s*a;2关于一维数组的问题关于一维数组的问题l一般一维数组所涉及的主要问题有一般一维数组所涉及的主要问题有l排序排序l插入插入l删除删除l查找查找l分类统计分类统计l涉及到一些算法，我们通过例题介绍一部分涉及到一些算法，我们通过例题介绍一部分l具体问题的解题
2、算法的思路要靠自己慢慢去具体问题的解题算法的思路要靠自己慢慢去体会体会31. 什么是排序？什么是排序？ 将一组杂乱无章的将一组杂乱无章的数据数据按一定的按一定的规律规律顺次排列起来。顺次排列起来。 2. 排序的目的是什么？排序的目的是什么？存放在数据表中存放在数据表中按按关键字排序关键字排序3.3.排序算法的好坏如何衡量？排序算法的好坏如何衡量？时间效率时间效率排序速度（即排序所花费的全部比较次数）排序速度（即排序所花费的全部比较次数）空间效率空间效率占内存辅助空间的大小占内存辅助空间的大小稳稳定定性性若若两两个个记记录录A A和和B B的的关关键键字字值值相相等等，但但排排序序后后A A、B
3、 B的先后次序保持不变，则称这种排序算法是稳定的。的先后次序保持不变，则称这种排序算法是稳定的。 便于查找便于查找4常见排序算法常见排序算法l插入排序插入排序l直接插入排序直接插入排序l折半插入排序折半插入排序l表插入排序表插入排序l希尔排序希尔排序l交换排序交换排序l冒泡排序冒泡排序l快速排序（不稳定）快速排序（不稳定）l选择排序选择排序l归并排序归并排序l基数排序基数排序5插入排序插入排序插入排序的基本思想是：插入排序的基本思想是：插入排序的基本思想是：插入排序的基本思想是： 每步将一个待排序的对象，按其关键码大小，插入每步将一个待排序的对象，按其关键码大小，插入每步将一个待排序的对象，按
4、其关键码大小，插入每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对到前面已经排好序的一组对象的适当位置上，直到对到前面已经排好序的一组对象的适当位置上，直到对到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。象全部插入为止。象全部插入为止。象全部插入为止。简言之，边插入边排序，保证子序列中随时都是排好序的。简言之，边插入边排序，保证子序列中随时都是排好序的。简言之，边插入边排序，保证子序列中随时都是排好序的。简言之，边插入边排序，保证子序列中随时都是排好序的。6直接插入排序直接插入排序新元素插入到哪里？新元素插入到哪里？例例1 1：关键字序
5、列关键字序列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】 在已形成的在已形成的有序表中
6、有序表中线性查找线性查找，并在，并在适当位置插入，把原来位置上的元素向后适当位置插入，把原来位置上的元素向后顺移顺移。最简单的排序法！最简单的排序法！最简单的排序法！最简单的排序法！7有序插入有序插入l首先查找要插入的位置，假设位置为aL之前l则：for (i =n+1;i L;i-) ai=ai-18有序删除有序删除l比如要删除ad这个元素，则for (j = d;j n;j+) aj=aj+19交换排序交换排序 两两比较待排序记录的关键两两比较待排序记录的关键两两比较待排序记录的关键两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好码，如果发生逆序（即排列顺序与排序后的
7、次序正好码，如果发生逆序（即排列顺序与排序后的次序正好码，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序为止。相反），则交换之，直到所有记录都排好序为止。相反），则交换之，直到所有记录都排好序为止。相反），则交换之，直到所有记录都排好序为止。交换排序的主要算法有：交换排序的主要算法有： 1) 冒泡排序冒泡排序 2) 快速排序快速排序交换排序的基本思想是：交换排序的基本思想是：交换排序的基本思想是：交换排序的基本思想是：10冒泡排序基本思路：基本思路：每趟不断将记录两两比较，并按每趟不断将记录两两比较，并按“前小后大前小后大”（或（或“前大后小前大后小”）规则交
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*，49
9、16，08 ，21， 25， 25*，4908，16， 21， 25， 25*，49初态：初态：第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟11冒泡排序法关键程序冒泡排序法关键程序linti,j,minj,t;for(i=0;iN-1;i+)for(j=i+1;jN-1;j+)if(ajai)t=ai;ai=aj;aj=t;12选择排序（快速排序）选择排序（快速排序）l算法：首先找到数据清单中的最小的数据，然后将这个数据同第一算法：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交个数据交换位置；接下来找第二小的数据，再将其同第
10、二个数据交换位置，以此类推。换位置，以此类推。l第第1 1次，在数组次，在数组a a的的n n个数据中选出其小者（只标记其所在位置），若个数据中选出其小者（只标记其所在位置），若它不在其位置（即其下标不等于它不在其位置（即其下标不等于1 1）则与第一个数据进行交换（只需）则与第一个数据进行交换（只需交换一次），经过本次处理后，总可以使得数组交换一次），经过本次处理后，总可以使得数组a a的第的第1 1个数据为第个数据为第1 1小。小。l第第2 2次，在数组次，在数组a a的后的后n-1n-1个数据（即出去已经选择的最小者的各数据）个数据（即出去已经选择的最小者的各数据）中，经过类似的处理后，可
11、以使得数组中，经过类似的处理后，可以使得数组a a的第的第2 2个数据为第个数据为第2 2小。小。l第第i i次，在数组次，在数组a a后的后的n-i+1n-i+1个数据中，经过类似选择处理后，数组个数据中，经过类似选择处理后，数组a a的第的第i i个数据为第个数据为第i i小。小。l第第n-1n-1次，在数组后的次，在数组后的2 2个数据中，经过类似处理后，总可以使数组个数据中，经过类似处理后，总可以使数组a a的第的第n-1n-1个数据为第个数据为第n-1n-1小。而这时候第小。而这时候第n n个数据是第个数据是第n n小。小。13关于选择排序关于选择排序l算法：算法：N元数组元数组a0
12、aN-1由小到大排序：由小到大排序：第第0步步:找到找到a0aN-1中的最小值元素与中的最小值元素与a0交换交换;第第1步步:找到找到a1aN-1中的最小值元素与中的最小值元素与a1交换；交换；第第2步步:找到找到a2aN-1中的最小值元素与中的最小值元素与a2交换；交换；第第i步步:找到找到aiaN-1中的最小值元素与中的最小值元素与ai交换交换;第第N-2步步:找到找到aN-2aN-1中的最小值元素与中的最小值元素与aN-2交换。交换。算法停止。算法停止。14选择排序法程序选择排序法程序lint i,j,minj,t; for (i = 0;i N-1;i+) minj = i; /有什么
13、作用？有什么作用？ for (j = i + 1;j N;j+) if (aj aminj) minj = j; if (minj != i) t = ai; ai = aminj; aminj = t; 减少了数减少了数据交换的据交换的次数！次数！15查找算法查找算法l查找之前要求排序，不然无章可查查找之前要求排序，不然无章可查l顺序查找顺序查找l按照排好序的顺序进行查找，比如对按照排好序的顺序进行查找，比如对一个升序排列的数组中，找到第一个一个升序排列的数组中，找到第一个大于需要查找的数大于需要查找的数l折半查找（二分查找）折半查找（二分查找）16折半查找（二分查找）折半查找（二分查找）先
14、给数据排序先给数据排序（例如按升序排好），形成（例如按升序排好），形成有序表有序表，然后再将，然后再将keykey与正中元素相比，与正中元素相比，若若keykey小，则缩小至右半部内查找；再小，则缩小至右半部内查找；再取其中值比较，每次缩小取其中值比较，每次缩小1/21/2的范围，的范围，直到查找成功或失败为止。直到查找成功或失败为止。LowLow指向待查元素指向待查元素所在区间的下界所在区间的下界highhigh指向待查元素所指向待查元素所在区间的上界在区间的上界midmid指向待查元素所在指向待查元素所在区间的中间位置区间的中间位置 已知如下已知如下11个元素的个元素的有序表有序表：（05
15、 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为请查找关键字为21 和和85的数据元素。的数据元素。17 先设定先设定3 3个辅助标志个辅助标志: : low,high,midlow,high,mid，显然有：显然有：mid= mid= (low+high)/2(low+high)/2 运算步骤运算步骤：（key为要查找的值为要查找的值）(1) low =1,high =11 ,mid =6 (1) low =1,high =11 ,mid =6 ，待查范围是待查范围是 1,111,11；(2) (2) 若若 elemmidelemmid key keykey，
16、说明说明keykey low ,midlow ,mid-1-1 ， 则令：则令：high =midhigh =mid1 1; ;重算重算 mid mid ；(4)(4)若若 elemelem mid mid = key= key，说明查找成功，元素序号说明查找成功，元素序号=mid;=mid;结束条件：结束条件：（1 1）查找成功）查找成功 ： elemmidelemmid = key = key （2 2）查找不成功查找不成功 ： highlowhighlow （意即区间长度小于意即区间长度小于0 0）折半查找折半查找18折半查找法程序折半查找法程序int BinSearch(int R,
17、int n, int Key)/功能：在有序表功能：在有序表R0.n-1R0.n-1中进行折半查找中进行折半查找/返回值：查找成功时返回数组下标，否则返回返回值：查找成功时返回数组下标，否则返回-1-1 int low=0,high=n-1,mid; /置当前查找区间上、下界的初值置当前查找区间上、下界的初值 while(lowKey) high=mid-1; /继续在继续在Rlow.mid-1Rlow.mid-1中查找中查找 else low=mid+1; /继续在继续在Rmid+1.highRmid+1.high中查找中查找 return -1; /当当lowhighlowhigh时表示查
18、找区间为空，查找失败时表示查找区间为空，查找失败19l首先要理首先要理清楚思路，清楚思路，再动手编再动手编程序程序找鞍点的问题找鞍点的问题20lfor (i=0;i3;i+)l max=ai0;l for (j=0;jmax)lmax=aij;lmaxj=j; /*求出行中最大数*/ll l for(k=0,flag1=1;kakj)l flag1=0; /*算出该数是否为列中最小*/l l if (flag1=1)l printf(n第%d行,第%d列的%d是鞍点n,i,maxj,max);l flag2=1; /*打印鞍点*/l l if (flag2=0)l printf(n矩阵中无鞍点
19、!n);l 21将一个数组逆序转换将一个数组逆序转换例如例如1 1，2 2，3 3，4 4，5,5,变为变为5 5，4 4，3 3，2 2，1 1l算法分析：用第一个与最后一个交换。算法分析：用第一个与最后一个交换。这是这是aiai,则前面已有则前面已有i i个元素，与它交换的元素个元素，与它交换的元素akak 应该满足与应该满足与akak 后面也有后面也有i i个元素，则这个元素的下个元素，则这个元素的下 标标k k为：为：n-1-in-1-i即即: :下标下标i i要与下标要与下标n-i-1n-i-1交换交换22将一个数组逆序转换程序将一个数组逆序转换程序#define N 5main()
20、 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关于二维数组的问题关于二维数组的问题（双下标的应用）（双下标的应用）l涉及到矩阵的问题，一般使用二维数涉及到矩阵的问题，一般使用二维数组加以解决组加以解决l下面举几个稍微复杂一点的例子，也下面举几个
21、稍微复杂一点的例子，也是某些考试（比如高级程序员）经是某些考试（比如高级程序员）经常考到的难题常考到的难题l蛇行矩阵问题蛇行矩阵问题l魔方阵问题魔方阵问题l矩阵旋转问题矩阵旋转问题24蛇行方阵问题蛇行方阵问题输入：N=4N=7输出：13410134101121222591125912202334681215681319243335713141671418253236431517263137424416273038414548282939404647491341025911681215713141625蛇行矩阵蛇行矩阵l将自然数将自然数1,2,1,2,N*N,N*N,逐个顺序逐个顺序插入方阵中适
22、当的位置，这个过插入方阵中适当的位置，这个过程沿斜列进行。将斜列编号为程沿斜列进行。将斜列编号为0,1,2,0,1,2,2n,2n（以（以i i表记表记,n=N-1,n=N-1），），从图中看出在一斜列上各元素的从图中看出在一斜列上各元素的下标是相等的，且等于斜列号下标是相等的，且等于斜列号i i。同时方阵又可分为上三角与下三同时方阵又可分为上三角与下三角（含对角线）每一斜列上元素角（含对角线）每一斜列上元素个数为个数为i+1i+1个；下三角每一斜列个；下三角每一斜列上元素个数为上元素个数为2n-i+12n-i+1个。在斜列个。在斜列上安排数可以使上安排数可以使自右上向左下自右上向左下或或自左
23、下向右上自左下向右上两种方式进行，元两种方式进行，元素可以表示为素可以表示为ai-jjai-jj或者或者aji-jaji-j 的形式。的形式。26蛇行方阵的排数方法蛇行方阵的排数方法左下向右右上向左下标变量下标j的变化下标变量下标j的变化上三角ai-jj0 iai-jji 0aji-ji 0aji-j0 i下三角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+; 13410259116812
24、15713141628下三角（不含对角线）下三角（不含对角线）for (i=n+1; i=(2*n); i+) if (i%2=1) for (j=i-n; j=i-n; j-) ai-jj = k; k+; 1341025911681215713141629螺旋方阵问题螺旋方阵问题12345672425262728298234041424330922394849443110213847464532112037363534331219181716151413124232221201922540393837183264948473617427424946351652843444534156293
25、0313233147891011121330l从从a00a00开始，按照图开始，按照图所示的从外层到内层所示的从外层到内层分别为：上、右、下、分别为：上、右、下、左，每进一层，一行左，每进一层，一行或一列的元素少或一列的元素少2 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+) /上
26、aij=k+; for ( j=i; j=i+1; j-) /下 an-ij=k+; for ( j=n-i; j=i+1; j-) /左 aji=k+; if (n%2 = 0) /最后一个，中间 an/2n/2=k;33方阵旋转问题方阵旋转问题l顺时针旋转顺时针旋转9090度度l可以将可以将n+1n+1阶矩阵分为阶矩阵分为(n+1)/2(n+1)/2层层l每层中可将元素分为每层中可将元素分为n-2in-2i组，每组组，每组4 4个元素，例如图，个元素，例如图，i i标记为标记为1 1的层（从的层（从外向内数的第二层），其中含外向内数的第二层），其中含n-n-2*i=42*i=4组：组： (
27、 (a11,a15,a55,a51)a11,a15,a55,a51)、(a12,a25,a54,a41)(a12,a25,a54,a41)、(a13,a35,a53,a31)(a13,a35,a53,a31)、(a14,a45,a52,a21)(a14,a45,a52,a21)l分析每一个元素，设任意一个为分析每一个元素，设任意一个为( (a aijij) )，则替换该元素的下标，则替换该元素的下标a axyxy其中有如下其中有如下规律规律: : x=n-j,y=i即：即：aij=an-ji34for ( i=0; i=(n-1)/2; i+) for( j=i; j=(n-i-1); j+)
28、 temp=aij; aij=an-ji; an-ji=an-in-j; an-in-j=ajn-i; ajn-i=temp; l替换元素下标（也就是等替换元素下标（也就是等式右边的部分）规律式右边的部分）规律x=n-j,y=i35魔方阵魔方阵l魔方阵是以元素为自然数魔方阵是以元素为自然数1,2,N*N1,2,N*N方阵。每个元素的值方阵。每个元素的值均不等且每行每列以及主副对角线各均不等且每行每列以及主副对角线各N N个元素的值相等。个元素的值相等。l其算法为：其算法为：l第一个元素的位置在第一行正中第一个元素的位置在第一行正中l新的位置应该处于最近插入位置的右上方，但如果右上新的位置应该处
29、于最近插入位置的右上方，但如果右上方的位置超出方阵上边界，则新的位置应该取列的最下方的位置超出方阵上边界，则新的位置应该取列的最下一个位置。超出右边界则取行的最左的一个位置。一个位置。超出右边界则取行的最左的一个位置。l若最近的插入的元素为若最近的插入的元素为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
30、%2) = 0) /输入阶数，只接受奇数输入阶数，只接受奇数 printf(n enter squqre size(ODD) number:); scanf(%d,&size); cur_j = (size-1)/2;魔方阵参考程序魔方阵参考程序37for(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); 38结束语结束语l“纸上谈兵纸上谈兵”学不出程序设计本领；学不出程序设计本领；只有大量上机、编程、调试，才能掌只有大量上机、编程、调试，才能掌握。握。l学好程序设计语言的唯一途径是上机。学好程序设计语言的唯一途径是上机。l你的编程能力和你在机器上投入的时你的编程能力和你在机器上投入的时间成正比。间成正比。39
