补充3-数组应用讲述.ppt

补充3数组应用的技巧与方法 附加：计数器、累加器、累乘器 计数器 int count; while(…){ … count ++ } 累加器 int s; for(…) { … a=…; s=s+a; } 关于一维数组的问题 一般一维数组所涉及的主要问题有 排序 插入 删除 查找 分类统计 涉及到一些算法，我们通过例题介绍一部分 具体问题的解题算法的思路要靠自己慢慢去体会 排序算法 插入排序 直接插入排序 折半插入排序 表插入排序 希尔排序 交换排序 冒泡排序 快速排序（不稳定） 选择排序 归并排序 基数排序 插入排序 直接插入排序 交换排序 冒泡排序 选择排序 算法：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。 第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小。 查找算法 查找之前要求排序，不然无章可查 顺序查找 按照排好序的顺序进行查找，比如对一个升序排列的数组中，找到第一个大于需要查找的数 折半查找（二分查找） 折半查找 先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。 折半查找 有序插入 首先查找要插入的位置，假设位置为a[L]之前 则： for (i =n+1;i L;i--) a[i]=a[i-1] 有序删除 比如要删除a[d]这个元素， 则 for (j = d;j n;j++) a[j]=a[j+1] 关于选择排序 算法：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]交换。算法停止。 程序一 int i,j,minj,t; ? ?for (i = 0;i N-1;i++) { ? ?? ?for (j = i + 1;j N-1;j++)? ?? ? if (a[j] a[i]) {? ?? ?? ? ?t = a[i];? ?? ?? ? a[i] = a[j];? ?? ?? ? a[j] = t;  ? ?? ? }? ?} 改进程序 int i,j,minj,t; ? ?for (i = 0;i N-1;i++) { ? ?? ?minj = i; //有什么作用？? ?? ?for (j = i + 1;j N;j++)? ?? ?if (a[j] a[minj])? ?? ?? ? minj = j;? ?? ?if (minj != i) {? ?? ?? ?t = a[i];? ?? ?? ?a[i] = a[minj];? ?? ?? ?a[minj] = t; ? ?? ?}? ?} 找鞍点的问题 首先要理清楚思路，再动手编程序 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;