程序的设计基础一

1

6

数据组织与处理(1)

—数组2数组的概念、定义和初始化筛法的解题思路冒泡排序的思路二维数组学习目标3数组：定义、初始化、操作与应用筛法：do_while循环、while循环、求质数排序：冒泡排序的算法二维数组：定义、初始化、应用内容要点4

6.1数组5

中秋佳节，有贵客来到草原，主人要从羊群中选一只肥羊宴请宾客，当然要选最重者。这样就要记录每只羊的重量，如果有成千上万只羊，不可能用一般变量来记录。可以用带有下标的变量，也就是这里要讲的数组。问题：哪只羊最重？ 我们先看例子：用键盘输入10只羊的重量存放到一个名为sheep的数组中6//************************************//*程序名：6_1.cpp（数组示例）*//*作者：wuwh*//*编制时间：2002年9月20日*//*主要功能：找出最重的羊*//************************************#include<iostream> //预编译命令#include<memory> //预编译命令usingnamespacestd;intmain() //主函数{

floatsheep[10]; //数组，有10个浮点类型元素，

//用于存10只羊每一只的重量

memset(sheep,0,sizeof(sheep));//初始化数组元素为0

floatbigsheep=0.0; //浮点类型变量，存放最肥羊的重量

inti=0,bigsheepNo=0; //整型变量，i用于计数循环，

//bigsheepNo用于记录最肥羊的号7

for(i=0;i<10;i=i+1) //计数循环

{ //循环，开始

cout<<"请输入羊的重量sheep["<<i<<"]=";//提示用

cin>>sheep[i]; //输入第i只羊的重量

if(bigsheep<sheep[i]) //如果第i只羊比当前最肥羊大

{ bigsheep=sheep[i]; //让第i只羊为当前最肥羊

bigsheepNo=i; //纪录第i只羊的编号

} } //循环结束 //输出最肥羊的重量

cout<<"最肥羊的重量为"<<bigsheep<<endl;//输出该羊的编号

cout<<"最肥羊的编号为"<<bigsheepNo<<endl;

return0;}8程序框图9

类型说明符 数组名[常量表达式]例： floatsheep[10]; inta2001[1000];说明1.数组名的第一个字符应为英文字母；2.用方括号将常量表达式括起；3.常量表达式定义了数组元素的个数；数组的定义104.数组下标从0开始。如果定义5个元素，是从第0个元素至第4个元素；

例如 inta[5]定义了5个数组元素如下：

a[0],a[1],a[2],a[3],a[4]

这是5个带下标的变量，这5个变量的类型是相同的

115.常量表达式中不允许包含变量例如 intn; n=5; inta[n]; 不合法！因为n是变量，不是常量12#defineN100//宏定义，N为常数100#defineM200//宏定义，M为常数200inta[N];//定义有100个元素的整型数组alongb[N+M];//定义有300个元素的长整型数组bdoubleg[M+6];//定义有206个元素的双精度实

//型数组g以上定义是合法的#defineN100为命令行，不是语句，程序在编译时遇到N就用100替换。在命令行中定义的符号名N，也被称为符号常量N。13

第一种方法直接在定义时初始化 例如

inta[5]={3,5,4,1,2};

a[0]=3;a[1]=5;a[2]=4;a[3]=1;a[4]=2;数组初始化14

第二种方法使用memset函数 格式为

memset(数组名,初始化值,sizeof(数组名)) 举例：

memset(sheep,0,sizeof(sheep));

含义是将名为sheep的数组中的全部元素均初始化为0。更深一层是说让系统为sheep[10]所分配的内存单元从sheep[0]为标志的地址单元到该数组的全部地址单元都赋以0。调用此库函数需要加入头文件<memory.h>。151.#include<iostream>usingnamespacestd; intmain() { inta[4]; //声明项 cout<<a[0]<<endl; cout<<a[1]<<endl; cout<<a[2]<<endl; cout<<a[3]<<endl;return0; }2.其他不变，改变声明项为

inta[4]={0,1,2,3};请自己上机做7个实验163.其他不变，改变声明项为

inta[4]={3,8};4.其他不变，改变声明项为

inta[4]={2,4,6,8,10};5.其他不变，改变声明项为

inta[4]={2,4,6,d};6.其他不变，改变声明项为

intd;

inta[4]={2,4,6,d};7.其他不变，改变声明项为

intn=4; inta[n]={0,1,2,3};17讨论问题使用筛法求100以内的所有素数18

6.2筛法19思路想象将100个数看作沙子和小石头子，让小石头子权称素数；让沙子当作非素数。弄一个筛子，只要将沙子筛走，剩下的就是素数了。非素数一定是2、3、4……

的倍数。使用数组，让下标就是100以内的数，让数组元素的值作为筛去与否的标志。比如筛去以后让元素值为1。20方法的依据：

1至100这些自然数可以分为三类：单位数：仅有一个数1。素数：是这样一个数，它大于1，且只有1和它自身这样两个正因数。合数：除了1和自身以外，还有其他正因数。

1不是素数，除1以外的自然数，当然只有素数与合数。筛法实际上是筛去合数，留下素数。 21为了提高筛法效率，注意到： 令n为合数（这里是100），c为n的最小正因数，

据初等数论，只要找到c就可以确认n为合数，将其筛去。

一定注意：要进行“筛”的1—100的数字是与数组prime[101]的下标相对应的，而每个数组元素的取值只有2个：是0或1，分别代表（标志）与下标相对应的数字是素数或不是素数。22程序框图如下：请同学来分析左边程序的结构从而了解算法的设计思路为程序代码的实现创造条件23上述框图很清晰地描述了筛法的思路：1.第一块是一个计数型的循环语句，功能是将prime数组清零。

prime[c]=0; c=2,3,…,1002.第二块是正因数d初始化为d=2。3.第三块是循环筛数。这里用了一个dowhile

语句，属于一种直到型循环

24举例求π的近似值25例.求π的近似值

用变量pi表示π的值。

令 表示括号中的每个项当最后一项的绝对值小于等于时，忽略掉以后的项26//************************************//*程序名：5_2.cpp*//*作者：wuwh*//*编制时间：2002年9月20日*//*主要功能：求pi的近似值*//************************************#include<iostream>#include<cmath>usingnamespacestd;intmain() //主函数{ intsum=0; //整型变量，总项数

floatpi=0.0,a=1.0,b=1.0,c=1.0; //浮点变量，a为分母，b为分子，c为b除以a

27

do //直到型循环 { //循环体，开始 pi=pi+c; //累加每一项 sum=sum+1; a=a+2.0f;//计算每一项的分母；强制将2.0转换成float型 b=-b;//分子变正负号

c=b/a; //计算每一项 } //循环体结束 while(fabs(c)>1e-6);//当c的绝对值大于10的-6次方时，继续 //执行循环体，否则退出

pi=4.0f*pi; //得到最终结果；将4.0作为float类型 cout<<“pi=”<<pi<<endl; //输出pi值 cout<<“sum=”<<sum<<endl; //输出总项数

return0;}28do //直到型循环 { //循环体，开始

pi=pi+c; //累加每一项

sum=sum+1;

a=a+2.0f; //计算每一项的分母

b=-b; //分子变正负号

c=b/a; //计算每一项} //循环体结束

while(fabs(c)>1e-6);29运行结果

pi=3.14159，sum=500000答：会构成死循环，即无休止地执行循环体请实验：1.将b定义为int型看看执行结果并分析为什么2.将1e-6变为1e-7或1e-4看看结果提问：这种循环当表达式的值永远为真时，会如何？30举例求两个整数的最小公倍数31分析：假定有x,y且x>y，设最小公倍数为z1.z一定会>=x2.z=kx,k=1,2,…3.z一定会被y整除用两个最简单的数试一下就可以找到算法.比如x=5,y=3.32第一步z=x//x=5 5%3!=0//z%y不能整除第二步z=z+x 10%3!=0//z%y

不能整除第三步z=z+x 15%3==0//z%y

能整除找到了z，15就是5和3的最小公倍数33//************************************//*程序名：5_3.cpp*//*作者：wuwh*//*编制时间：2002年9月20日*//*主要功能：求两个数的最小公倍数*//************************************#include<iostream>#include<cmath>usingnamespacestd;intmain() //主函数{ intx=0,y=0,z=0,w=0;//整型变量

cout<<“请输入两个整数，用空格隔开：”;//提示信息 cin>>x; //键盘输入整数x cin>>y; //键盘输入整数y if(x<y) //让x表示两者中的大数

{ w=x;x=y;y=w;//“倒油瓶”方法 } z=x; //将一个大数赋给z while(z%y!=0) //当z不能被y整除时，就让z累加x {z=z+x;} cout<<“最小公倍数为”<<z<<endl; //输出最小公倍数

return0;}34cout<<“请输入两个整数，用空格隔开：”;//提示信息 cin>>x; //键盘输入整数x cin>>y; //键盘输入整数y if(x<y) //让x表示两者中的大数

{ w=x;x=y;y=w; }35

z=x; //将一个大数赋给z//当z不能被y整除时，就让z累加xwhile(z%y!=0) {z=z+x;}cout<<"最小公倍数为"<<z<<endl; 36 请同学们去比较三种循环的异同之处

1.for循环（计数型循环） 2.当型循环（while循环）3.直到型循环（dowhile循环）上机将筛出素数的程序完成自学与比较37排序问题38

6.3冒泡排序法

39

a183249下标123456

希望排成：

a984321下标12345640

冒泡排序法问题：

将几个数从大到小排序并输出414243从表中可以看出最小的一个数第一遍扫描就交换到a[6]中。如果将a[1]视为水底，a[6]视为水面：最轻的(最小的)一个数1最先浮到水面，交换到a[6];次轻的2第二遍扫描交换到a[5]；再轻的3第三遍扫描交换到a[4]； …依此类推，有6个数，前5个数到位需5遍扫描，第6个最重的数自然落在a[1]中。因此，6个数只需5遍扫描，令扫描编数为J，J=n-1,n=6。冒泡排序算法分析：44再看在每遍扫描中，相邻两数组元素的比较次数。当j=1时，i=1,2,…,n-j。n=6时，比较5次之后a[6]中有一个最小数到达，这时a[6]不必再参与比较了。因此在第二遍搜索时，j=2,i=1,2,…,n-j，即i=1,2,3,4。比较4次之后次小的一个数到达了a[5]。这时a[5]不必再参与比较了。因此，j=3时，i=1,2,3；j=4时，i=1,2；j=5时，i=1.理出上述规律后，程序就不难编了45inti=0,j=0,p=0,a[7];//整型变量memset(a,0,sizeof(a)); //数组初始化for(i=1;i<=6;i++) //键入6个数{ cout<<"请输入待排序的数a["

<<i<<"]=“; //提示

cin>>a[i]; //输入整数}46为了表述方便，定义以下3个变量：n——待排序的数的个数，这里n=6

j——扫描遍数，j=1,2,…,n-1

i——第j遍扫描待比较元素的下标，i=1,2,…,n-j冒泡排序算法设计：47采用两重计数型循环：步骤1：将待排序的数据放入数组中；步骤2：置j为1；步骤3：让i从1到n-j，比较a[i]与a[i+1]， 如果a[i]>=a[i+1]，位置不动； 如果a[i]<a[i+1]，位置交换，

步骤4：让j=j+1；只要j!=n返回步骤3

,当j==n时执行步骤5步骤5：输出排序结果48//************************************//*程序名：5_4.cpp*//*作者：wuwh*//*编制时间：2002年9月22日*//*主要功能：冒泡排序*//************************************#include<iostream> //预编译命令#include<memory> //预编译命令usingnamespacestd;intmain() //主函数{ inti=0,j=0,p=0,a[7]; //整型变量 memset(a,0,sizeof(a)); //整型数组初始化

for(i=1;i<=6;i++) //键入6个数，放入a数组中 { cout<<"请输入待排序的数a["<<i<<"]="; //提示

cin>>a[i]; //用键盘输入整数赋给a[i] } for(j=1;j<=5;j++) //冒泡排序，外层循环 for(i=1;i<=6-j;i++) //内层循环 if(a[i]<a[i+1]) //如果a[i]<a[i+1] { p=a[i]; //让a[i]与a[i+1]交换 a[i]=a[i+1]; a[i+1]=p; } for(i=1;i<=6;i++) //输出排序结果

cout<<a[i]<<endl; //输出a[i]return0;}49//************************************//*程序名：5_4.cpp