vc++程序设计5.ppt

1、数组与基本算法,第四章,一维数组,二维数组,字符数组,C+程序设计上机(6)要求,本章授课内容,4-1 一维数组,一、一维数组数组的定义,二、一维数组数组的存储结构,三、数组元素的引用形式,四、一维数组的初始化,六、一维数组程序设计举例（算法）,五、一维数组的输入和输出,返 回,数组概念的引出,在科学计算和数据处理中，要用到成批数据，这些数据类型相同，且彼此间存在一定的顺序关系 数组可以表现多种逻辑关系的数据形式。,数组 由一组具有同一数据类型 的变量有序集合。,例如： int a10;,数组名,常量表达式,类型说明,一、一维数组的定义,格式 : 数据类型 数组名常量表达式;,int a10;

2、,数组名命名规则同标识符,int n; cinn; int an; .,可以使用宏定义: #include #define N 10 void main() . int aN; . ,常量表达式中不能有变量,下标从0开始,没有a10;,常量表达式的值为元素的个数,二、一维数组的存储结构,a,a9,a8,a7,a1,a0,一个数组的所有元素都是连续存储的,数组元素为: a0,a1,a2.a9,int a10;,所占空间为: 类型空间*元素个数,三、数组元素的引用形式,数组元素的引用: 数组名下标,a0 = a2+a4*2,2,4,0,int a10; a0=2;,一般不能引用整个数组,int a

3、10,b10; a=b;,int a5=1,2,3,4,5;,四、一维数组的初始化,对数组进行初始化,对static数组赋初值,系统为之初始化,若为数值型,则初始化为0,字符型则初始化为0,数据与元素个数相同,可省略个数,int a=1,2,3,4,5;,例如: 输入n个成绩,求平均分(书P69页，例4.2）,#include void main() int sc,n,i; float aver=0.0; cinn; for(i=0;isc; aver+=sc; aver/=n; coutaver; ,int sc50, n, i;,cinsci; aver+=sci; aver/=n; fo

4、r(i=0 ; iaver) coutsc i );,输出高于平均分的成绩,五、一维数组的输入和输出,数组的输入和输出只能逐个对数组元素进行操作（字符数组例外）,输入方法：,int a10,i;,输入第i个数组元素：,cinai;,输入整个数组元素：,for (i=0;iai;,输出方法：,输出第i个数组元素：,coutai;,输出整个数组元素：,for (i=0;i10;i+) coutai;,用一维数组求Fibonacci 数列 (实验书P42页，范例11）,#include void main() int i; static int f20 = 1,1; for(i=2;i20;i+)

5、fi = fi-2 +fi-1; for(i=0;i20;i+) if(i%5 = 0) cout“n”; cout“t”fi; ,六、一维数组程序设计举例,f 0=1 f 1=1 f i= f i-1+f i-2 求其前20项 1,1,2,3,5,8,13.,基本算法1.排序(1)冒泡法排序(书P70页，例4.3）,输入5个数,进行由小到大排序: 9 8 5 4 2,算法：两两比较,大数向后移,找到最大数放在最后,再在剩余的的4个数中进行两两比较,找到最大数,以次类推.最后,小数排在开始,相当于浮起,故称之为:冒泡法,8 5 4 2 9,5 4 2 8,4 2 5,2 4,比较4次 第一轮,

6、比较3次 第二轮,比较2次 第三轮,比较1次 第四轮,9 8 5 4 2,8 9 5 4 2,8 5 9 4 2,8 5 4 9 2,8 5 4 2,5 8 4 2,5 4 8 2,5 4 2,4 2,4 5 2,对 n 个数，则要进行n-1趟扫描，在第 i 趟扫描中要进行 n-i 次比较。,可以推知：,“211”： 两重循环，一次比较，一次互换 n个数要循环比较n-1 轮； 在每轮中aj 与aj+1进行比较互换 (数组元素的下标从0数组长度-1) 第1轮比较：i=0: j= 0.n-2 第2轮比较：i=1: j= 0.n-3 第2轮比较：i=2: j= 0.n-4 第n-2轮比较：i=n-3

7、: j= 01 第n-1轮比较：i=n-2: j= 0,for(i=0;iaj+1) t =aj; aj=aj+1; aj+1=t; ,若为aj与aj-1的比较互换，则j的变化范围为？,0n-1-i,/*排序*/ for (i=0; iaj+1) t =aj; aj=aj+1; aj+1=t; ,#include #define N 10 void main() int i,j,aN,t; for(i=0;iai; for(i=0;iN;i+)/*输出*/ coutai;,/*排序*/ for (i=0;iaj+1) t=aj; aj=aj+1; aj+1=t; for(i=0;iN;i+)

8、/*输出*/ coutai; ,见sort.c,源程序:,(2)选择法排序(实验书P48范例2),特点：比较后不立即互换元素，而是记下其位置并在每一轮比较完毕后和（）互换 首先，比较的元素不同，以降序为例，是当前元素与上次比较後的最大元素进行比较，因此，在进行比较之前，要有一个初始化最大元素的过程 其次，确定完毕的元素的互换是在每一轮完成后进行的，而不是在比较後进行的 再次，互换元素的不同，为（i）和（iMax） :举例 原始数据： 3，5，7，9，4 要求：降序,第一轮比较，初始化设最大元素下标为 k0 3579 k=0 3579 k=1 3579 k=2 3579 k=3 k=3 S(i)

9、 与 S(k)交换的结果: 9573,/*选择排序*/ for (i=0;iak) k=j; /k为最大数的下标 t=ai; ai=ak; /将最大数放到第一个位置 ak=t; ,2.在有序数组中插入一个数后使原数组仍然有序(实验书P47范例1) 例如：3 5 7 12 18， 将b=10插入 步骤： (1)要找到b在数组中的位置 (2)给b让位置 (3)将b放到该位置上,b=10,for(i=0;ib) break;,for(j=4;j=i;j-) aj+1=aj;,ai=b;,12,18,10,3.在有序数组中删除一个数,例如: 3 5 7 10 12 18， 将b=10删除 步骤： (1

10、) 要找到b在数组中的位置 (2) 后面的数组元素依次前移,覆盖该位置上的数组元素即可实现删除,for(i=0;i6;i+) if(ai=b) break;,10,12,18,for(j=i;j5;j+) aj=aj+1;,是对有序数列进行查找的一种高效查找办法，其基本思想是逐步缩小查找范围，采取半分作为分割范围可使比较次数最少. 比较过程:（设数列已做降序排序处理） 设置三个变量,分别代表数组序列 s 的Top,Bottom和Middle位置,其中Middle=(Top+Bottom)/2,进行下列判断,1 3 4 6 8 10 12 15 18 20 25,X = 15,4、查找：,（1）

11、顺序查找,（2）折半查找法：对有序数组,Kjexam3.cpp,4-2 字符数组,二、字符串及字符串结束标志,三、字符数组的输入和输出,四、字符串处理函数,五、字符数组程序应用,一、字符数组的定义,返 回,一、字符数组,用来存放字符数据的数组为字符数组。,char c10；,char c10=I, ,a,m , ,h,a,p,p,y;,若初值个数小于数组长度，剩余元素自动定为空字符,char c12=c, ,p,r,o,g,r,a,m;,int c10；,定义,初始化,二者互相通用,但存储空间不同,二、字符串和字符串结束标志,将字符串作为字符数组来处理,字符串结束标志0:,0作为判断字符串是否

12、结束标志,使用字符串常量初始化,char c =“I am happy”;,char c =“I am happy”;,只要用字符串常量,就会自动加0,故长度为11,*字符串长度为有效字符串的长度(字符个数),三、字符数组的输入和输出,1.整个数组的输入输出,即按数组名输入输出 (仅用于字符数组),输出字符不包括结束符0,cin输入时系统一直读取字符,直到遇“空格”和“回车符(n)”为止。例如： 输入数据 hello world C数组中内容为hello,2.使用cin.get(字符数组名，字符串长度，规定的结束符),字符串长度：可以是小于数组长度的任意值 规定的结束符：可以省略不写，默认为回

13、车键 例如： char s20; 可以使用： cin.get(s,20) / hello w*orld cin.get(s,20,*) / hello w cin.get(s,5); / hell cin.get(s,5,*); / hell cin.get(s,10,*); / hello w 若输入：hello w*orld,3.使用 cin.getline(字符数组名，字符串长度，规定的结束符) 用法同cin.get（），多用于连续给多个数组输入的情况。 如：char s120,s210; cin.get(s1,20); cin.get(s2,10); 则不能实现为s2的输入,返 回,#

14、include void main()char str20; cinstr; /*cin.get(str,20)按回车结束*/ coutstr; ,输入：how do you do,输出：,#include void main() char str = “HellonBejing”; coutstr; ,输出:,Hello Bejing,how,how do you do,四、字符串处理函数,字符串连接函数: strcat(s1,s2); 连接s1和s2两个字符串赋给s1， 并为函数的返回值 字符串拷贝函数: strcpy(s1,s2); 将s2中的字符串赋给s1 字符串比较函数: strcm

15、p(s1,s2) 求字符串长度函数：strlen(s) 函数值为整数(返回字符个数）,返 回,（参数为字符数组名）,#include #include void main() char st130,st240,st370; int l1,l2,l3,a,b,c; cinst1st2;/*INPUT*/ l1=strlen(st1);/*strlen*/ l2=strlen(st2); cout“l1=“l1“t”“l2=“ l2“n”; a=strcmp(st1,st2);/*strcmp*/ couta“ n”;,if (a0) cout”st2“n”; else if (a=0) cout

16、st1“=“st2; else coutst1“st2“n”; strcat(st1,st2); /*strcat*/ coutst1; cout(strcat(st1,st2); strcpy(st3,st2); /*strcpy*/ coutst3; ,字符串函数的使用（参P81例4.10）,Kjexam.cpp,五、字符数组程序应用,字符串的长度,逆序,字符串函数,求字符串长度,扫描数组,只要不是0,计数器就加1,源程序:,#include void main() int i; char s50; cins; for (i=0;i50 ,i,for (i=0; i50,i,i=0,#in

17、clude #include void main() int i, j=0; char c10,t; cinc; int l=strlen(c); for(i=0, j=l-1;ij;i+, j-) t=ci;ci=cj;cj=t; coutc; ,输入: abcd,输出: dcba,将输入的字符串中的字符逆序输出(参P82例4.11),源程序1:,#include “iostream.h” void main() int i,j; char s10, t ; cins; for( i=0 ; i10 ,源程序2:,输入: abcd,输出: dcba,字符串函数,/*STRCAT*/,#inc

18、lude void main() int i , j; char s140,s250; cins1s2; for( i=0; i40 ,s1,s2,s1,/*STRCPY*/ #include void main() char p180,p280; int i; cinp2; for (i=0;p2i!=0;i+) p1i=p2i; p1i=0; cout“p1=“p1“np2=“p2“n”; ,/*STRCMP*/ #include void main() char p180,p280; int i; cinp1p2; for( i=0;p2i!=0,if (p1ip2i) cout”p2

19、“n; else if (p1ip2i) coutp1“p2 “n”; else coutp1“=“p2 “n”; ,4-3 二维数组,一、二维数组的定义,二、二维数组的存储结构,三、二维数组的初始化,四、二维数组元素的引用形式,五、二维数组的输入和输出,六、二维数组程序设计举例,返 回,一、二维数组的定义,格式: 数据类型 数组名常量表达式常量表达式,int b23;,b为23（2行3列）的数组,b0 b1,b,-b00 b01 b02,-b10 b11 b12,二、二维数组的存储结构,int b23；,b10,b11,b12,b00,b01,b02,存放顺序：按行存放，先顺序存放第一行的元

20、素，再存放第二行的元素,b0 b1可以 作为数组名,三、二维数组的初始化,int b23 = 1,2,3,4,5,6;,int b23 = 1,2,3,4,5,6;,int b3 = 1,2,3,4,5,6;,int b; int b=1,2,3,4,5,6; int bnm;,错 !,分行赋值,按数组排列的顺序赋值,若全部都赋初值，第一维长度可省略,四、二维数组元素的引用形式,数组名下标1下标2,b02 = b10+b00-b02;,数组元素可以出现在表达式中，也可以被赋值,引用形式：,注意：下标值在已定义的数组大小的范围内,int a34; . a34=4;,五、二维数组的输入和输出,数组

21、的输入和输出只能逐个对数组元素进行操作（字符数组例外）,int b23,i,j;,C+将二维数组看作一维数组，其每个数组元素又是一个一维数组,10个同学的姓名，按升序排序,#include #include void main() char s1016,t16; int i,j,n=10; for(i=0;isi; for(i=0;in;i+) coutsi; coutn;,for (i=0;i0) strcpy(t,sj); strcpy(sj,sj+1); strcpy(sj+1,t); for (i=0;in;i+) coutsi; ,Kjexam2.cpp,六、二维数组程序设计举例,有

22、一个2*4的矩阵, 编程求出其中的最大值及其所在的行号和列号。,返 回,#include void main() int i,j,max,row,colum; static int a24 = 1,2,3,4,5,6,7,8; max=a00; for(i=0;imax) max=aij; row=i; colum=j; cout“max=“max“row=“row“colum=“colum“n”; ,Kjexam4.cpp,1.求介乘: 数据类型的定义, long或double 2.求累加和: long 3.统计: 统计正数、平均分以上、n个成绩中10090、8980、7970、6960、60的人数；输入字符串中字母d、单词的个数：设置一个计数变量k：初始化为1，每遇到一次将其加1：k+;,基本算法,小结,存放累加和的变量：初始化为0或第一项，再循环加每一项； 循环控制：前n项之和已知循环次数，可设置一个循环变量如i来控制；加到某一项或累加和满足一定条件。例： 1+2+.+n 与 1+3+5+7+.和 2+4+6