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

1数组应用的技巧与方法2附加：计数器、累加器、累乘器计数器intcount;while(…){…count++}累加器ints;for(…){…a=…;s=s+a;}累乘器ints;for(…){…a=…;s=s*a;}3关于一维数组的问题一般一维数组所涉及的主要问题有排序插入删除查找分类统计涉及到一些算法，我们通过例题介绍一部分具体问题的解题算法的思路要靠自己慢慢去体会41.什么是排序？将一组杂乱无章的数据按一定的规律顺次排列起来。2.排序的目的是什么？存放在数据表中按关键字排序3.排序算法的好坏如何衡量？•时间效率——排序速度（即排序所花费的全部比较次数）•空间效率——占内存辅助空间的大小•稳定性——若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。——便于查找！5排序算法插入排序直接插入排序折半插入排序表插入排序希尔排序交换排序冒泡排序快速排序（不稳定）选择排序归并排序基数排序6插入排序插入排序的基本思想是：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。简言之，边插入边排序，保证子序列中随时都是排好序的。7直接插入排序新元素插入到哪里？例1：关键字序列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】在已形成的有序表中线性查找，并在适当位置插入，把原来位置上的元素向后顺移。最简单的排序法！8交换排序两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序为止。交换排序的主要算法有：1)冒泡排序2)快速排序交换排序的基本思想是：9冒泡排序基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。前提：顺序存储结构例：关键字序列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，25，25*，49初态：第1趟第2趟第3趟第4趟第5趟10选择排序算法：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。第1次，在数组a的n个数据中选出其小者（只标记其所在位置），若它不在其位置（即其下标不等于1）则与第一个数据进行交换（只需交换一次），经过本次处理后，总可以使得数组a的第1个数据为第1小。第2次，在数组a的后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小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。Low指向待查元素所在区间的下界high指向待查元素所在区间的上界mid指向待查元素所在区间的中间位置已知如下11个元素的有序表：（0513192137566475808892）,请查找关键字为21和85的数据元素。13①先设定3个辅助标志:low,high,mid，显然有：mid=(low+high)/2②运算步骤：(1)low=1,high=11,mid=6，待查范围是[1,11]；(2)若ST.elem[mid].keykey，说明key[mid+1,high]，则令：low=mid+1;重算mid＝(low+high)/2；.(3)若ST.elem[mid].keykey，说明key[low,mid-1]，则令：high=mid–1;重算mid；(4)若ST.elem[mid].key=key，说明查找成功，元素序号=mid;结束条件：（1）查找成功：ST.elem[mid].key=key（2）查找不成功：high≤low（意即区间长度小于0）折半查找14有序插入首先查找要插入的位置，假设位置为a[L]之前则：for(i=n+1;iL;i--)a[i]=a[i-1]15有序删除比如要删除a[d]这个元素，则for(j=d;jn;j++)a[j]=a[j+1]16关于选择排序算法：N元数组a[0]~a[N-1]由小到大排序：第0步:找到a[0]~a[N-1]中的最小值元素与a[0]交换;第1步:找到a[1]~a[N-1]中的最小值元素与a[1]交换；第2步:找到a[2]~a[N-1]中的最小值元素与a[2]交换；…第i步:找到a[i]~a[N-1]中的最小值元素与a[i]交换;…第N-2步:找到a[N-2]~a[N-1]中的最小值元素与a[N-2]交换。算法停止。17程序一inti,j,minj,t;for(i=0;iN-1;i++){for(j=i+1;jN-1;j++)if(a[j]a[i]){t=a[i];a[i]=a[j];a[j]=t;}}18改进程序inti,j,minj,t;for(i=0;iN-1;i++){minj=i;//有什么作用？for(j=i+1;jN;j++)if(a[j]a[minj])minj=j;if(minj!=i){t=a[i];a[i]=a[minj];a[minj]=t;}}19找鞍点的问题首先要理清楚思路，再动手编程序20for(i=0;i3;i++){max=a[i][0];for(j=0;j3;j++){if(a[i][j]max){max=a[i][j];maxj=j;/*求出行中最大数*/}}for(k=0,flag1=1;k3&&flag1;k++){if(maxa[k][j])flag1=0;/*算出该数是否为列中最小*/}if(flag1==1){printf(\n第%d行,第%d列的%d是鞍点\n,i,maxj,max);flag2=1;/*打印鞍点*/}if(flag2==0)printf(\n矩阵中无鞍点!\n);}21折半查找的问题h=0;r=14;m=(h+r)/2;while(h=r&&x!=a[m]){if(xa[m]){r=m-1;m=(h+r)/2;}else{h=m+1;m=(h+r)/2;}}if(hr)printf(无此数);elseprintf(%d,m);22将一个数组逆序转换例如1，2，3，4，5,变为5，4，3，2，1算法分析：用第一个与最后一个交换。这是a[i],则前面已有i个元素，与它交换的元素a[k]应该满足与a[k]后面也有i个元素，则这个元素的下标k为：n-1-i即下标i要与下标n-i-1交换23将一个数组逆序转换程序#defineN5main(){inta[N]={9,6,5,4,1},i,temp;printf(\noriginalarray:\n);for(i=0;iN;i++)printf(%4d,a[i]);for(i=0;iN/2;i++){temp=a[i];a[i]=a[N-i-1];a[N-i-1]=temp;}printf(\nsortedarray:\n);for(i=0;iN;i++)printf(%4d,a[i]);}24关于二维数组的问题（双下标的应用）涉及到矩阵的问题，一般使用二维数组加以解决下面举几个稍微复杂一点的例子，也是某些考试（比如高级程序员）经常考到的难题蛇行矩阵问题魔方阵问题矩阵旋转问题25蛇行方阵问题输入：N=4N=7输出：13410134101121222591125912202334681215681319243335713141671418253236431517263137424416273038414548282939404647491341025911681215713141626蛇行矩阵将自然数1,2,…,N*N,逐个顺序插入方阵中适当的位置，这个过程沿斜列进行。将斜列编号为0,1,2,…,2n（以i表记,n=N-1），从图中看出在一斜列上各元素的下标是相等的，且等于斜列号i。同时方阵又可分为上三角与下三角（含对角线）每一斜列上元素个数为i+1个；下三角每一斜列上元素个数为2n-i+1个。在斜列上安排数可以使自右上向左下或自左下向右上两种方式进行，元素可以表示为a[i-j][j]或者a[j][i-j]的形式。66656463626160565554535251504645444342414036353433323130262524232221201615141312111006050403020100aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa斜列号012345678910111227蛇行方阵的排数方法左下向右右上向左下标变量下标j的变化下标变量下标j的变化上三角a[i-j][j]0ia[i-j][j]i0a[j][i-j]i0a[j][i-j]0i下三角a[i-j][j]i-nna[i-j][j]ni-na[j][i-j]ni-na[j][i-j]i-nn28上三角（包括对角线）for(i=0;i=n;i++){if(i%2==1){for(j=0;j=i;j++){a[i-j][j]=k;k++;}}else{for(j=i;j=0;j--){a[i-j][j]=k;k++;}}}aaaaaaaaaaaa504132302321141210050301斜列号135aaaaaaaaaaaaaaaa60514240333124222015131106040200斜列号02461341025911681215713141629下三角（不含对角线）for(i=n+1;i=(2*n);i++){if(i%2==1){for(j=i-n;j=n;j++){a[i-j][j]=k;k++;}}else{for(j=n;j=i-n;j--){a[i-j][j]=k;k++;}}}aaaaaaaaaaaa6563615654524543363425167911666462555346443526aaaaaaaaa810121341025911681215713141630螺旋方阵问题123456724252627282982340414243309223948494431102138474645321120373635343312191817161514131242322212019225403938371832649484736174274249463516528434445341562930313233147891011121331从a00开始，按照图所示的从外层到内层分别