第8章 数组算法

《第8章 数组算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、内容提要数据分类数据排序：交换法、选择法、冒泡法、插入法数据检索：顺序查找、二分法查找（折半查找）矩阵的常用算法第8章数组算法数据分类一、数据分类缺点：程序冗长、占机时多常用数据分类的方法利用if语句利用switch语句例：随机输入一组数据，数据在1~4之间，输入结束统计出各类数据的个数。分析问题给出算法一：1、输入数据到x2、判断该数据属于那类，分别记数4、分别输出a、b、c、d的值3、反复执行1、2步骤直到数据输完为1记入a中为2记入b中为3记入c中为4记入d中利用if、switch语句编程方法一：（用基本数据类型）main(){inti,

2、n,x,a=0,b=0,c=0,d=0,e=0;scanf(“%d”,&n);for(i=1;i<=n;i++){scanf(“%d”,&x);switch(x){case1:a+=1;break;case2:b+=1;break;case3:c+=1;break;case4:d+=1;break;default:e+=1;}}printf(“1的个数为：%d”,a);printf(“2的个数为：%d”,b);printf(“3的个数为：%d”,c);printf(“4的个数为：%d”,d);printf(“其他个数为：%d”,e);}数组的引

3、入，利用下标为分类（分档）问题提供了一种巧妙的方法，使程序明显简化。利用if、switch语句分析问题给出算法二：（用数组）2、输入数据到x3、判断该数据属于那类，分别记数5、分别输出a[0]~a[4]的值4、反复执行2、3步骤直到输入结束a[1]中记1的个数1、设定一个数组a存放统计结果inta[5]a[4]中记4的个数a[3]中记3的个数a[2]中记2的个数a[x]+=1main(){inta[5]={0,0,0,0,0},x=1,i=0;while(x){scanf("%d",&x);if(x<=4&&x>=1){a[x]=a[x]+1;

4、}else……}for(i=0;i<5;i++)printf("a[%d]=%d",i,a[i]);}编程方法二：（用数组）数据排序又称为排队问题。所谓排序就是对一个数值大小不规则的数列按从小到大（从大到小）的顺序重新组成一个新的数列。内部排序:交换~、选择~、冒泡~、插入~等排序的分类外部排序数据排序常用的排序算法1：交换法排序（比较法排序、选择法排序）算法思想：（以升序为例）举例原始数据：8，6，9，2，3要求：升序S[0]……S[n-1]存放n个无序数，将其升序重新排列。1.第一趟比较，结束后S[0]存放最小的数。S[0]与S[1]比

5、较，若S[0]>S[1]则做交换；S[0]与S[2]比较，S[0]>S[2]则做交换；……2.第二趟比较，结束后S[1]存放第二小的数。S[1]与S[2]比较，若S[1]>S[2]则做交换；S[1]与S[2]比较，S[1]>S[2]）则做交换；……3.第n-1趟比较，S[n-2]与S[n-1]比较，S[n-2]存放小的，S[n-1]存放大的（也是n个数中最大数）。经过n-1趟比较后，n个数按从小到大的顺序排列。第一趟比较：8692368923689232896328963第一趟结束，找到最小值2第二趟比较：第二趟结束，找到第二小值3289632

6、69832896323986第三趟结果：23698第四趟结果：23689算法表示：(n为数组元素个数,升序为“>”)for(i=0;isort[j]){temp=sort[i];sort[i]=sort[j];sort[j]=temp;}/*交换*交换法排序算法交换法排序for(i=0;iscore[i])"交换成绩score[j]和score[

7、i]"，"交换学号num[j]和num[i]"；}}例：教材P205例6.3#include#defineARR_SIZE40main(){floatscore[ARR_SIZE],temp1;intn,i,j;longnum[ARR_SIZE],temp2;printf("Pleaseentertotalnumber:");scanf("%d",&n);/*从键盘输入学生人数n*/printf("Pleaseenterthenumberandscore:");for(i=0;i

8、学生的学号和成绩*/{scanf("%ld%f",&num[i],&score[i]);}/*用交换法按成绩由高到低对学生成绩及学重新排序*/for(