《C语言-7-常用算法、编程 PPT课件》由会员分享，可在线阅读，更多相关《C语言-7-常用算法、编程 PPT课件（17页珍藏版）》请在金锄头文库上搜索。
1、常用算法、编程,折半查找也称为二分查找 前提：必须是有序（降序或升序）的数列,P153.7.8,查 找-折半查找,折半查找思想,若数列为升序 1.设定三个位置变量t=0,b=9,m 2.m=(t+b)/2 3.待查找的值x与下标为m的数组元素比较， if(x=am) 若为真，则找到。若为假，重新确定查找范围。 若xb中止查找。,int a10,x;,t,b,m,a9,a8,a7,a6,a5,a4,a3,a2,a1,a0,#include main() int a10=3,4,13,15,23,35,54,67,89,94; int t=0, b=9,m,x; scanf(“%d”, ,找到,没
2、找到时，重新更改查找范围,没找到,对已知的一批数, 按从小到大排序(升序）,将相邻两个数进行比较，若顺序不对，实现交换。,算法思想：,冒(起)泡法排序,P134.例7.3,22,50,设有定义：int a6=30,21,50,45,80,22,第一轮比较完成后，将最大的数沉入底，第二轮在剩余的数中再进行相邻两数的比较,第二轮比较完成后，将次大的数沉入底，第三轮在剩余的数中继续进行相邻两数的比较,依次类推,直到实现排序,a0 a1 a2 a3 a4 a5,结论：,for (i=1; iaj+1) t=aj; aj=aj+1; aj+1=t; ,约定：数组元素的下标从0开始，因此，程序可以变动如下
3、：,for (i=0; iaj+1) t=aj; aj=aj+1; aj+1=t; ,#define N 10 #include main( ) int aN = 9,5,15,8,4,13,6,10,17,1,i,j,t; for (i = 0; i a j+1 ) t = a j ; a j = a j+1 ;a j+1 = t; printf ( The Sorted number are:n ); for ( i = 0; i N ; i + + ) printf ( %4d, a i ); ,算法思想：,若有定义： int a10 第1轮，记数组的第1个元素为最小数的位置k,然后与其
4、后的数组元素逐一比较。若找到较小的，就重置k的位置。当所有的数都比较完后，k所在的位置所对应的元素ak就是本轮的最小数。将最小数放置到本轮的首位，即将ak 与第1轮的第1个元素a0交换。,选择法排序,P168.2,对10个数, 按从小到大排序(升序）,第2轮，记数组的第2个元素为最小数的位置k,然后与其后的数组元素逐一比较。若找到较小的，就重置k的位置。当所有的数都比较完后，k所在的位置所对应的元素ak就是本轮的最小数。将最小数放置到本轮的首位，即将ak 与第2轮的第1个元素a1交换。依次类推。,选择法排序就是不断的选择最小（大）元素的过程。,初始： 49 38 65 97 76 13 27
5、,i=0,13,49,13 38 65 97 76 49 27 ,i=1,27,38,13 27 38 49 65 76 97 ,i=2,i=3,i=4,i=5,#define N 8 #include main( ) int a N = 15,8,4,13,6,10,17,1; int k, i, j, t; for ( i = 0 ; i aj ) k = j; /* 若找到更小的，则记录该元素的下标 */ if ( k != i ) t = ak; ak = ai; ai = t; for ( i = 0; i N ; i + ) printf ( %3d, ai ); ,k = i;,
6、k = j;,#define N 8 #include main( ) int a N = 15,8,4,13,6,10,17,1; int i, j, t; for ( i = 0 ; i aj ) t = ai; ai = aj; aj = t; for ( i = 0; i N ; i + ) printf ( %3d, ai ); ,擂台法排序,P153.7.4 已有一个已排好序的数组，要求输入一个数后，按原来排序的规律将它插入数组中,int a11=3,4,13,15,23,35,54,67,89,94,x=25,i;,找到插入的位置 i=5，从数组的最后一个元素开始依次后移一位到插
7、入的位置。,94,89,67,54,35,在ai的位置插入x，即ai=x;,xai (i=0) (找插入的位置）,aj+1=aj;,25,P168.4 已有一个已排好序的数组，要求输入一个数后，按原来排序的规律将它插入数组中,算法思想：,1.找插入的位置。,while (iai) i+;,2.移位。,for(j=9;j=i;j-) aj+1=aj;,3.插入。,ai=x;,算法：插入排序,#include main() int a11=3,4,13,15,23,35,54,67,89,94; int i,j,x; scanf(%d, ,找插入的位置,右移位,插入,已有n个数，现要求输入一个数，查找是否存在，若存在删除该数。否则退出该程序。,int a11=3,4,13,15,23,35,54,67,89,94,98,x=35,i;,98,94,89,67,54,1.查找删除的元素（即当 x=ai时找到）,while (i11 ,2.移位,for(j=i;j10;j+) aj=aj+1;,3.输出,#include main() int a11=3,4,13,15,23,35,54,67,89,94,98; int i,j,x; printf(Input delete x:n); scanf(%d, ,找删除的位置,左移位,输出删除后的数列,
