资源描述
数组操作,（1） 选择排序法 （2）冒泡排序法 （3）比较排序法,（1）顺序查找法 （2）折半查找法,（1）数组元素插入 （2）数组元素删除,（1）选择排序第17、26套的填空题,简单选择排序: 从1到n 选出关键值最（大）小的记录，交换到第一个位置上，然后从2到n选 出键值最（大）小的记录，交换到第 二个位置上，.,i=0,初态,数组下标 0 1 2 3 4,k!=i,交换,判断ajak?,用选择法对数组 int a5= 54,71,58,29,31 进行升序排序,k=j,29 71 58 54 31,29 71 58 54 31,29 71 58 54 31,29 71 58 54 31,k!=i,交换,29 31 58 54 71,判断ajak?,k=j,k=j,k=j,判断ajak?,“选择排序法” （由小到大排序） 选择法(递增) 基本思想： (1) 从n个数的序列中选出最小的数，与第1个数交换位置； (2) 除第1个数外，其余n-1个数再按(1)的方法选出次小的数，与第2个数交换位置; (3) 重复(1)n-1遍，最后构成递增序列。 实现方法：采用双重循环（循环的嵌套） 外循环为i：控制排序趟数 内循环为j：第i趟排序过程中的下标变量,“选择”排序法的结构形式：,for(i=0;iaj) k=j; if(k!=i) t=ai;ai=ak;ak=t; ,#include #include “stdlib.h“ void main() const int N = 10; int i,j,k,t,aN; for(i = 0;i aj) k = j; if(k != i) t = ak; ak = ai; ai = t; for(i = 0;iN;i+) printf(“%5d“,ai); printf(“n“); ,第二种：“冒泡法”（由小到大排序） 基本思想： (1)从第一个元素开始，对数组中两两相邻的元素比较，将值较小的元素放在前面，值较大的元素放在后面，一轮比较完毕，最大的数存放在aN-1中； (2)然后对a0到aN-2的N-1个数进行同（1）的操作，次最大数放入aN-2元素内，完成第二趟排序；依次类推，进行N-1趟排序后，所有数均有序。 实现方法：采用双重循环（循环的嵌套）,（2）冒泡排序,交换排序：俩俩比较待排序记录的键值，若逆序，则交换， 直到全部满足为止,交 换 排 序“ 冒泡”排序法 特点：逐个对数组中每相邻二数进行比较，若条件满 足，则互相交换，否则保持原位置不变。,千万要注意！ 若有n个数据，需要进行i=n-1轮比较 。每轮中比较的次数为j=n-i+1 次。,排序过程：（设数据存于A数组中，n个数据，按递增 次序排序） A0与A1比较 A0A(1) 不换，否则对调 A1与A2比较 A1A2 不换，否则对调 ： An-2与An-1比较 An-2An-1 不换，否则对调,冒泡法排序,用冒泡法对10个数排序(由小到大)。,4 8 2 7 5 9,2 4 8 5 7 9,2 4 5 8 7 9,2 4 5 7 8 9,2 4 5 7 8 9,2 4 5 7 8 9,冒泡排序的结构形式（递增）,for(i=0;iaj+1)t=aj; aj=aj+1; aj+1=t;,for(i= 1 ; iaj+1) t=aj;aj=aj+1;aj+1=t;,关键代码：,14,for(i= 0 ; iaj+1) t=aj;aj=aj+1;aj+1=t;,#include #define N 6 void main( ) int i,j,t,aN; printf(“input N numbers:n“); for (i=0;iaj+1)t=aj; aj=aj+1; aj+1=t; for (i=0;iN;i+) printf(“%5d,“,ai); printf(“n“); ,冒泡程序,第三种：比较排序（上机19、52套编程题）,for(i= 0 ; iaj) t=ai;ai=aj;aj=t;,注意ai与aj比较,补充知识一：查找,查找的方法很多。 如：顺序查找、二分法查找等等。,1、顺序查找： 最简单的查找方法，基本思想是利用循环顺序扫描整个数组，依次将每个元素与待查找值比较，直至找到或找不到。,对于无序数组，顺序查找是唯一可行的办法 对大批量数据用顺序查找占机器时间较多。,int Search(long a , int n, long x) int i; for (i=0; in; i+) if (ai = x) return (i); return (-1); ,2、二分法查找/折半查找：,二分法查找的条件：,必须是有序数列，即数组中的各元素已按数值大小按递增或递减次序排列！,查找过程： (1) 将数列对分，找出中间数据 (2) 用此数据与要查的数据比较 (3) 数值相等则结束查询，否则确定要查的数据所在区间，逐步缩小查找范围，每次将数列区间缩小一半，直到找到或找不到为止。,( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),折半查找（二分法查找）,( 08, 14, 23, 37, 46, 55, 68, 79, 91 ),下标 0 1 2 3 4 5 6 7 8,折半查找,1，5，6，9，11，17，25，34，38，41,下界low,上界up,中值mid,共有10个已排好序的数据：查找9。,int BinSearch(long a,int n,long x) int low, high, mid; low = 0; high = n - 1; while (low amid) low = mid + 1; else if(x amid)high = mid - 1; else return (mid); return(-1); ,折半查找程序,#include main( ) int up=9, low=0, mid, found=0, find; int a10=1, 5, 6, 9, 11, 17, 25, 34, 38, 41; scanf(%d , ,补充知识二：数组元素的插入、删除,1、插入数据 在有序数组中插入数据后，数组仍然有序。 要求数组有足够的空间。,前提：被操作数组已经是有序数组，操作前后不改变数组的有序性,插入过程： (1) 确定数据插入位置 (2) 从最后一个元素开始逐个后移，直到将第i个位置腾出。 (ai+1=ai) (3) 将数据插入到指定下标元素位置中,插入运算,ai-1,a1,a0,alength,ai+1,ai,x,x,2、删除数据 在有序的数组中删除数据后，数组仍然有序。,删除过程： (1) 确定数据删除位置i (2)从第i1个位置开始逐个向前移动原数组元素，(ai=ai+1),下面介绍引用一维数组元素的三种方式。 1.下标方式 形式： 数组名下标 , 如ai 2. 地址方式 形式： *（地址）,如*(a+i)等价ai 3. 指针方式 形式： *指针变量名 如: int a10,*p； p=,一维数组与指针,1数组就是连续存放的若干元素的集合。 2数组名就是指向数组第一个元素的首地址（指针） 如 int a10,*p；则p=a等价于p= 4数组元素下标在内部实现时，统一按“基地址位移”的方式处理。即：a，a1，ai；,表示数组的地址可用：p+i，a+i 表示数组的内容可用：ai ， *(p+i) ， *(a+i),注意：虽然a与p都可以指示地址，但a是指首地址，p是变量（可以指首地址，也可以指其他地址）,
展开阅读全文