C++程序设计教程第4章-数组与结构体.ppt

,第4章 数组和结构体,数组是有序数据的集合。数组中的每一个元素都属于同一个数据类型，用一个统一的数组名和下标来唯一地确定数组中的元素。4.1.1 数组的定义 格式：类型说明符 数组名常量表达式 例如：int a10；int z34；float b20；数组元素为：a0、a1、a2、a9 b0、b1、b2、b19 ai与某个简单变量是一样的。C+中没有动态数组。例如：int n=10;int an;/是错误的,4.1 数组,4.1.2 数组元素的引用 数组在内存中是连续存放的。对于数组也必须先定义后使用。并且C+规定只能逐个引用数组元素而不能一次引用整个数组。一维数组中数组元素的引用方式为：数组名下标下标可以是整型常量或整型表达式。例如：a0、a2*3、ai+5。二维数组的元素的引用方式为:数组名下标下标下标可以是整型表达式。如a23、a3-12*2-1。但不要写成a2，3。,注意事项：1、同一数组中的元素必须具有相同的数据类型，而且这组数据在内存中将占据一段连续的存储单元,2、数组名命名规则和变量名相同，遵循标识符命名规则。,3、常量表达式表示元素的个数，即数组长度。,4、常量表达式中可以包括常量和符号常量，不能包含变量。（int an;-不对）5、数组第一个元素的下标为0。,例4-1 从键盘输入10个整数，将它们逆序输出。#include int main()int i,a10;for(i=0;iai;for(i=9;i=0;i-)coutai;coutendl;return 0;,例4-2 用数组构造Fibnacci序列的前20个数。#include int main()int i,fib20;fib0=1;fib1=1;for(i=2;i=19;i+)fibi=fibi-1+fibi-2;for(i=0;i=19;i+)coutfibi“;coutendl;return 0;,关键,4.1.3 数组的初始化 在定义数组时可以对其进行初始化。1一维数组的初始化（1）全部赋初值 int a10=0，1，2，3，4，5，6，7，8，9；（2）部分赋初值 int a10=0，1，2，3，4；/后5个元素值为0（3）赋初值时省略数组大小 int a5=0，1，2，3，4；int a=0，1，2，3，4；/两个语句等价 初始化给出的元素个数不能超过数组的长度。例如：int a5=0，1，2，3，4，5；就是错误的。,2二维数组的初始化（1）全部赋初值 int a34=1，2，3，4，5，6，7，8，9，10，11，12；int a34=1，2，3，4，5，6，7，8，9，10，11，12；（2）部分赋初值 int a34=1，2，3；int a34=1，0，2，0，0，3；,（3）赋初值省略第一维的大小 int a 4=1，2，3，4，5，6，7，8，9，10，11，12；等价于：int a34=1，2，3，4，5，6，7，8，9，10，11，12；在定义时也可以只对部分元素赋初值而省略第一维的大小，但应分行赋初值。如 int a 4=0，1，1，0，1；这样的写法，能通知编译系统，数组共有3行。数组各元素为：,例4-3 将一个3*4矩阵转置后输出。例如矩阵 转置后成为矩阵#include int main()int i,j,b43;int a34=1,2,3,4,1,2,3,4,1,2,3,4;coutBefore convertingendl;,for(i=0;i3;i+)for(j=0;j4;j+)cout.width(3);coutaij;coutendl;for(i=0;i3;i+)for(j=0;j4;j+)bji=aij;coutAfter convertingendl;for(i=0;i4;i+)for(j=0;j3;j+)cout.width(3);coutbij;coutendl;return 0;,cout.width(3);/设置宽度为3，不足用空格填充,是左边补空格。,4.1.4 数组的应用1.数组的简单应用例4-4 编写程序找出1000以内所有的完数。所谓完数就是该数等于它的所有因子之和。如6=1+2+3。#include int main()int n,m,i,j,a20;for(n=2;n=1000;n+)m=n;j=0;for(i=1;in;i+)if(n%i=0)aj=i;j=j+1;m=m-i;if(m=0)coutn是一个完数，它的因子是;for(i=0;ij;i+)coutai,;coutendl;return 0;,/aj中存的是因数,例4-5 有3*4的整数数组，编写程序，求出最大的那个元素的值以及其所在的行列号。#include int main()int a34=1,2,3,4,5,6,7,8,9,0,10,11;int i,j,row,col,max;max=a00;row=0;col=0;for(i=0;imax)max=aij;row=i;col=j;coutMax=max;coutRow=row;coutCol=colendl;return 0;,修改版：#include int main()/int a34=1,2,3,4,5,6,7,8,9,0,10,11;int a34;int i,j,row,col,max;for(i=0;iaij;max=a00;row=0;col=0;for(i=0;imax)max=aij;row=i;col=j;coutMax=max;coutRow=row;coutCol=colendl;return 0;,输入：1 2 3 4 5 6 7 8 9 0 10 11输出：Max=11 Row=2 Col=3,例4-6 Josephus 问题 分析：Josephus 问题是说，一群小孩围成一圈，任意假定一个数m，从第1个小孩起，顺时针方向数，每数到第m个小孩时，该小孩便离开。小孩不断离开，圈子不断缩小。最后，剩下的一个小孩便是胜利者。编写程序，顺序打印离开的小孩及最后的胜利者。,#include#define NUM 10/定义小孩个数int main()int m;/每次数m个小孩，便让小孩离开 int aNUM;/小孩数组 int i,j,k,s;/数组下标变量i,数数记数变量j,/离开小孩记数变量k,游戏标志变量s for(i=0;im;/输入数小孩的间隔数到m k=1;/游戏开始 i=-1;s=1;/设数组下标初值（下一个值0即第一个开数小孩 的下标)和标志s初值,while(s)/剩下的小孩多于一个 j=0;/设置开始记数初值 while(jm)/数m个小孩 i=(i+1)%NUM;/对下标加1求模 if(ai!=0)j+;/如果该元素的小孩在圈中，则数数有效 if(k=NUM)/表示圈中只有一个小孩了，因为k初值是1 s=0;else coutai,;/输出本次离开的小孩的编号 ai=0;/标识小孩已离开 k+;/准备处理圈中下一个小孩 coutendl;cout第 ai 号小孩获胜！;return 0;,理解,2 利用数组进行排序例4-7 用直接选择排序方法将输入的n个整数按从小到大的顺序排列输出。思路：直接选择排序是一种比较简单的排序方法，它的排序过程为：先从待排序的所有记录中选出关键字最小的记录，把它与原始序列中的第一个记录交换位置；然后再从去掉了关键字最小的记录的剩余记录中选出关键字最小的记录，把它与原始序列中第二个记录交换位置；依次类推，直至所有的记录成为有序序列。,#include int main()int a10,i,j,k,temp,n=10;for(i=0;iai;for(i=0;in-1;i+)k=i;for(j=i+1;jn;j+)if(ajak)k=j;if(k!=i)temp=ai;ai=ak;ak=temp;,coutAfter sortingendl;for(i=0;in;i+)cout ai;cout endl;return 0;,找剩余的数中最小的那个数,并把其下标存入k中,例4-8 用冒泡排序方法将输入的n个整数按从小到大的顺序排列输出。思路：冒泡排序的排序过程为：先将第1个记录和第2个记录进行比较，若为逆序，则交换之；接着比较第2个记录和第3个记录；依次类推，直至第n-1个记录和第n个记录进行比较、交换为止，我们称这样的过程为一趟冒泡排序。如此经过一趟排序，关键字最大的记录被安置到最后一个记录的位置上。然后，对前n-1个记录进行同样的操作，使具有次大关键字的记录被安置到第n-1个记录的位置上。重复以上过程，直到没有记录需要交换为止。,/用i表示比较的趟次，则i：19/用j表示比较的两个对象的前一个的下标，/即aj与aj+1比较j：0 9-i#include int main()int a10,i,j,temp,n=10;for(i=0;iai;for(i=1;iaj+1)temp=aj;aj=aj+1;aj+1=temp;,coutAfter sorting“endl;for(i=0;in;i+)cout ai;cout endl;return 0;,3 字符串应用 在C+中，字符串常量是用一对双引号括起来的字符序列。它在内存中的存放形式是：按串中字符的排列次序顺序存放，每个字符占一个字节，并在末尾添加0作为结束标记。在C+的基本数据类型变量中没有字符串变量。将字符串变量作为字符数组来处理。字符数组中的一个元素存放一个字符。可以用字符串常量来使字符数组初始化。例如 char c=“I am a boy”；或 char c“I am a boy”；数组c的长度不是10，而是11。因此，上面的初始化与下面的初始化等价。char c=I，a，m,，a，b，o，y，0；而不与下面的等价：char c=I，a，m，a，b，o，y；,对字符串进行处理，可以使用系统的字符串处理函数gets、puts、strcat、strcpy、strcmp、strlen等。使用这些函数之前，首先要将头文件stdio.h（包含函数gets、puts）、string.h包括到源程序中。（1）gets gets的作用是从终端输入一个字符串到字符数组，并且得到一个函数值。该函数值是字符数组的起始地址。函数原型为：char*gets（char*buffer）；用cin也可以输入字符串，但输入的字符串中不能有空格。,（2）puts puts的作用是将一个字符串（以0结束的字符序列）输出到终端。函数原型为：int puts（const char*string）；（3）strcatstrcat是STRing CATenate（字符串连接）的缩写。函数原型为：char*strcat（char*strDestination，const char*strSource）；其作用是连接两个字符数组中的字符串，把字符串strSource接到字符串strDestination的后面，结果放在字符数组strDestination中，函数的返回值为字符数组strDestination 的地址。,（4）strlen strlen是STRing LENgth（字符串长度）的缩写，它是测试字符串长度的函数。函数的返回值为字符串中的实际长度，不包括0在内。函数原型为：int strlen（const char*string）；（5）strcpy strcpy是STRing CoPY（字符串复制）的缩写，它是“字符串复制函数”。函数原型为：char*strcpy（char*strDestination，const char*strSource）；其作用是将字符串strSource复制到字符数组strDestination中去，函数的返回值为字符数组strDestination 的地址。,（6）strcmp strcmp是STRing CoMPare（字符串比较）的缩写。函数原型为：int strcmp（const char*string1，const char*string2）；作用是比较字符串string1和字符串string2。字符串比较的规则是对两个字符串自左至右逐个字符相比（按ASCII码值大小比较），直到出现不同的字符或遇到0为止。如全部字符相同，则认为相等；若出现不相同的字符，则以第一个不相同的字符的比较结果为准。比较的结果由函数值带回。如果字符串string1字符串string2，函数值为0。如果字符串string1 字符串string2，函数值为一个正整数。如果字符串string1 字符串string2，函数值为一个负整数。,ASCII的比较：09AZaz：记住几个常见字母的ASCII码大小：“A”为65；“a”为97；“0”为48；,例4-9 输入三个字符串，将它们按从小到大的顺序排列输出。#include#include int main()char c380,temp80;int i,j;for(i=0;i0)strcpy(temp,ci);strcpy(ci,cj);strcpy(cj,temp);for(i=0;i3;i+)puts(ci);return 0;,输入3个字符串对3个字符串进行排序两个字符串相交换输出3个字符串,直接选择排序,4利用数组构造魔方阵和杨辉三角形等例4-10 打印奇数阶魔方阵。-自学 n 阶魔方阵是指由1到n2（n为奇数）个自然数构成的n*n方阵，它的每一行、每一列和对角线的各元素之和均相等，3阶魔方阵如下所示。n 阶魔方阵的构造方法为：首先把1放到顶行的正中间，然后把后继数按顺序放置在右上斜的对角线上，并作如下修改：（1）当到达顶行时，下一个数放到底行，好象它在顶行的上面；（2）当到达最右端列时，下一个数放在最左端列，好象它紧靠在右端列的右方；（3）当到达的位置已经填好数时，或到达右上角的位置时，下一个数就放在刚填写数的位置的正下方。,#include#define ROW 20 int main()int aROWROW,row,col,num,n;coutn;for(row=0;rown;row+)for(col=0;coln;col+)arowcol=0;row=0;col=n/2;num=1;arowcol=num;while(numn*n)num+;if(row=0,else row-;col+;if(row0)row=n-1;if(col=n)col=0;if(arowcol!=0)row+=2;col-;arowcol=num;for(row=0;rown;row+)for(col=0;coln;col+)cout.width(4);coutarowcol;coutendl;return 0;,例4-11 试编写一个程序生成杨辉三角形的前10行，并把它打印出来。杨辉三角形图案如下：1 1 1 1 2 1 1 3 3 1解法1：用一个二维数组 y1010 来保存杨辉三角形每一行的值。杨辉三角形第row行可以由第row1行来生成。例如：,由上表知：当row4时，y40=1，y41=y30+y31，y42=y31+y32，y43=y32+y33，y44=y33+y34 一般的，对于第row（09）行，该行有row1个元素，yrow0=1,第col（1row)个元素为：yrowcol=yrow-1col-1+yrow-1col。,#include int main()int y1010=1,row,col;/赋初值的结果是y00=1,其他的均是0 for(row=1;row10;row+)yrow0=1;for(col=1;col=row;col+)yrowcol=yrow-1col+yrow-1col-1;for(row=0;row10;row+)for(col=0;col=row;col+)coutyrowcol;coutendl;return 0;,此循环仅执行这一句,解法2：用一个一维数组 y10 来保存杨辉三角形某一行的值。杨辉三角形第row行可以由第row1行来生成。-自学例如：,由上表知：当row4时，y4=y4+y3，y3=y3+y2，y2=y2+y1，y1=y1+y0，y0=1 一般的，对于第row（09）行，该行有row1个元素，第col（row1)个元素为：ycol=ycol+ycol-1，y0=1,#include int main()int y10=1,row,col;cout=1;col-)ycol=ycol+ycol-1;for(col=0;col=row;col+)coutycol;coutendl;return 0;,功能？,习题4-5 打印蛇型矩阵 6 7 9 2 5 8 1 3 4#include int main()int aNN=0;int i,j,k,m,n;/定义元素下标变量i,j;元素值变量k;/层次变量m;层内元素记数变量n i=N-1;/初始元素（左下角元素）的行标 j=0;/初始元素（左下角元素）的列标 k=1;/初始元素（左下角元素）的值 m=1;/设置层次初值,while(m=N)/生成下三角，当层次在主对角下（含主对角）aij=k;/放置每层第一个元素 for(n=2;n=m;n+)/放置本层其他元素 k=k+1;/生成下一个元素值 if(m%2!=0)/如果本层是奇数层 i=i-1;j=j-1;/生成下一个元素的放置位置（左上斜）else/否则本层是偶数层 i=i+1;j=j+1;/生成下一个元素的放置位置（右下斜）aij=k;/放置本层下一个元素 if(m%2!=0)/如果本层是奇数层 i=i-1;/则下一层首元素的位置垂直向上 else/否则本层是偶数层 j=j+1;/则下一层首元素的位置平行向右 k=k+1;/确定下一个要放的数 m=m+1;/层次推进到下一层/下三角构造完毕 if(N%2=0)/如果矩阵是偶数阶 i=N-2;j=N-1;/则上三角首元素的位置在倒数第二行最右列 else/否则矩阵是奇数阶 i=0;j=1;/则上三角首元素的位置在第一行第二列 m=N-1;/设置生成上三角的层次初值,while(m=1)/生成上三角，当层次在主对角上（不含主对角）aij=k;/放置每层第一个元素 for(n=2;n=m;n+)/放置本层其他元素 k=k+1;/生成下一个元素值 if(m%2!=0)/如果本层是奇数层 i=i-1;j=j-1;/生成下一个元素的放置位置（左上斜）else/否则本层是偶数层 i=i+1;j=j+1;/生成下一个元素的放置位置（右下斜）aij=k;/放置本层下一个元素 if(m%2!=0)/如果本层是奇数层 j=j+1;/则下一层首元素的位置平行向右 else/否则本层是偶数层 i=i-1;/则下一层首元素的位置垂直向上 k=k+1;/确定下一个要放的数 m=m-1;/层次推进到下一层/上三角构造完毕 for(i=0;iN;i+)/输出构造好的矩阵 for(j=0;jN;j+)cout.width(3);coutaij;coutendl;coutendl;return 0;,1结构体概述 所谓结构体就是其他高级语言中的记录，是一种构造数据类型。在程序设计中，有时需要将不同类型的数据组合成一个有机的整体，以便于引用。这些组合在一个整体中的数据是互相联系的。例如，一个学生的学号、姓名、性别、年龄等项，这些项都与某一学生相联系。如果将学号（num）、姓名（name）、性别（sex）、年龄（age）分别定义为互相独立的简单变量，难以反映它们之间的内在联系。应当把它们组织成一个组合项，在一个组合项中包含若干个类型不同（当然也可以相同）的数据项。C+允许用户自己指定这样一种数据类型，它称为结构体（structure）。,4.2 结构体,2定义结构体 格式：struct 结构体名 成员表列；例如，学生情况结构体可以定义为：struct Student int num；char name20；char sex；int age；注意不要忽略最后的分号。,结构体中的成员还可以是一个结构体类型的变量。例如：struct Student1 int num；char name20；char sex；Date birthday；,struct Date int year；int month；int day；,3定义结构体变量 结构体类型的定义只是指定了一个结构体类型，它相当于一个模型，但其中并无具体数据，系统对之也不分配实际内存单元。为了能在程序中使用结构体类型的数据，应当定义结构体类型的变量，并在其中存放具体的数据。定义结构体类型变量的方法为：结构体名 结构体变量名例如：方法一：定义结构体的同时定义其变量。struct Student int num；char name20；char sex；int age；st1,st2；/st1在内存中占29（4+20+1+4）个字节。,结构体变量的初始化：结构体变量可以在定义时指定初始值。例如：Student stu1=1001,“LiSi”，M，22；Student1 stu2=1001,“LiSi”，M，1998,09,10；/Student1的定义见前一个slice但是不能：Student stu1;stu1=1001,“LiSi”，M，22;,方法二：先定义结构体，然后定义其变量 struct Student int num；char name20；char sex；int age；Student st3，st4；,4结构体变量的引用 引用结构体变量中成员的方式为：结构体变量名.成员名例如：stu2=stu1;/结构体变量可以整体引用来赋值。stu1.num=1002；strcpy(stu1.name,“ZhangSan”);stu1.birthday.year=1988;stu1.birthday.month+;coutstu1.num“”stu1.name“”stu1.sex“”;cout stu1.birthday.year“stu1.birthday.month;cout“stu1.birthday.dayendl;注意：1、coutstu1;是错误的,因为结构体变量不能整体输出2、“”是成员(分量)运算符，它在所有的运算符中优先级最高，将stud1.num作为一个整体来看待。,例4-13 输入一个学生的姓名和4门功课的成绩，求出其平均成绩#include int main()struct Studentchar name10;int score4;float average;int i,sum;Student stu;coutstu.name;coutstu.scorei;sum=0;for(i=0;i4;i+)sum+=stu.scorei;stu.average=(float)sum/4.0;cout stu.name 的平均成绩为 stu.average endl;return 0;,运行情况：请输入学生姓名：gs请输入 4 门功课的成绩:90 80 90 80 gs的平均成绩为85,5结构体数组 数组中每个元素为结构体。例如：Student st1，st2；Student stu10；定义了一个数组stu，它的10个元素均为Student类型数据。若输入10个学生的信息，程序段如下：for(int i=0;istui.num;cinstui.name;cinstui.sex;cinstui.age;,例4-14 用结构体数组初始化建立学生信息，然后通过学号查询学生的基本信息。#include int main()struct Dateint year;int month;int day;,定义结构体,struct Studentint num;char name20;char sex;Date birthday;Student stu4=1001,Zhangsan,M,1984,10,12,1002,Lisi,F,1982,7,8,1003,Wangwu,M,1978,9,19,1004,Zhaoliu,M,1985,12,5;int i,number;coutnumber;,结构体类型,for(i=0;i4;i+)if(number=stui.num)break;if(i4)cout 学号为 number 的学生信息如下：;coutendl;cout姓名：stui.name;cout 性别：;if(stui.sex=M)cout男;else cout女;cout 出生日期：stui.birthday.year.;coutstui.birthday.month.stui.birthday.dayendl;elsecout 学号为 number 的学生不存在。endl;return 0;,结构体输出,