北京大学计算概论课件第10讲-复合数据结构-数组与结构

第十讲：复合数据结构

——数组与结构北京大学

信息科学技术学院2013年11月内容题要复合数据结构数组结构常见问题与错误常见问题编译错误运行调试数组数组

是

什么？数组

是

一组变量数组

是

一组

具有编号

的

变量如何声明

一个数组intsz[10];

数组的类型数组名数组中变量的数目必须是一个常量数组

中

变量

的

编号intsz[10];

数组中变量的编号

从

0

开始；

到

数组的长度－1

结束0123456789如何访问

数组

中

的

变量intsz[10];sz[0]

=1;sz[1]=3;sz[2]=7;…sz[8]=16;sz[9]=12;

…sz[2]…;

数组名变量编号数组变量赋值

的

一种特殊方式声明时赋值intsz[5]=｛12,3,7,28,-2｝;

#include<stdio.h>intmain(){

intsz[10]; inti;

for(

;

;

){

; } for(i=0;i<10;i++){ printf("%d",sz[i]); } return0;}程序填空；要求：1.接收用户输入的10个数字2.存放在数组sz中#include<stdio.h>intmain(){

intsz[10]; inti;

for(i=0;i<10;i++){ scanf("%d",&(sz[i]));

}

for(i=0;i<10;i++){ printf("%d",sz[i]); } return0;}数组

的

遍历通过

循环结构正向

遍历intsz[LEN];

for(inti=0;i<LEN;i++){

…sz[i]…

}反向

遍历intsz[LEN];

for(inti=LEN-1;i

>=0;i--){

…sz[i]…

}通过遍历

实现

对

数组变量

的

控制台赋值intsz[LEN];

for(inti=0;i<LEN;i++){

scanf(“%d”,&(sz[i])); }通过遍历

实现

对

数组变量

的

控制台输出intsz[LEN];

for(inti=0;i<LEN;i++){

printf(“%d\n”,sz[i]); }数组

的

应用示例当程序要处理

一组类型相同、含义类似的数据时，

应该使用数组游戏：过年抽奖一个村庄，有128个村民村长对村民说：今年村里出现了财政盈余M元；M是2000－3000之间的一个整数准备通过抽奖的方式把钱发给村民游戏规则如下：每个村民上报一个在2000－3000元之间的整数如果有人上报的数字和M相等，就把钱发给这些人如果只有一个村民猜对，就把M元钱全部发给他如果有多个人村民猜对，就把M元钱平均分配给这些村民村长邀请我们编写一个程序，

实现村里财政盈余的自动分配编程的基本思路定义一个数组

存放所有村民上报的数据定义一个数组

存放获奖者的编号（幸运者数组）定义一个整数

存放获奖者人数对村民从0开始编号（最后一个编号是127）村民按照编号顺序上报数字；程序将村民上报的数字存放在对应编号的数组变量中。遍历村民上报的数字，若上报数字与幸运数相等，则将村民编号添加到幸运者数组中；并将获奖者人数加1最后，打印出获奖者编号和获得的奖金数额#defineLUCKY_M2345

//财政盈余#definePOPULATION128 //村民数量intmain(){intpeople[POPULATION];//记录所有村民上报数字的数组

intluckyPeople[POPULATION];

//幸运者数组，记录获奖者编号intnLucky=0;//获奖者人数inti;//循环变量for(i=0;i<POPULATION;i++){scanf(“%d”,&(people[i]));//读入村民报的数字，数组下标就是村民的编号

}for(i=0;i<POPULATION;i++){if(people[i]==LUCKY_M){luckyPeople[nLucky]=i;nLucky++;}}

//输出获奖者编号及所获奖金数额for(i=0;i<nLucky;i++){printf("%d%d\n",luckyPeople[i],LUCKY_M/nLucky);}return0;}结构

结构的概念

通常，一个学生的个人信息，包括：学号、姓名、性别、年龄、各门功课的成绩等数据，这些数据都与一个学生相关联，类型各不相同。如果将这些数据定义为各独立的简单变量：

Number、Name、Sex、Age、Course1、Course2、…这样就难以反映它们之间的内在联系。应该把它们组织成一个组合项，把它们当作一个有机的整体。 ——这个组合项就是结构（Structure）21结构类型及其定义把多个紧密关联的变量（分量）顺序组织在一起，定义成一个新的复合数据类型——结构类型定义一个结构类型struct结构类型名{

类型1分量名1;

类型2分量名2;......};结构分量的类型可以相同，也可不同同一个结构内的分量名不可相同22structpoint{floatx;floaty;};结构类型变量的定义结构类型只是定义了一种新的数据类型系统并不为这个新类型分配内存空间。可以使用新的结构类型来声明变量——结构类型变量。结构类型变量定义的两种形式：用已定义的结构定义变量，例如：

structpointpoint1;

structpointpoint2;定义结构的同时定义结构类型的变量，例如：

structcity{floatx,y;intpopulation;}city1,city2;系统会为结构类型变量分配内存空间23结构类型变量中分量的访问结构类型变量的值由其各个分量构成对分量的访问一般通过“变量名.分量名”完成结构赋值及访问的例子：floatdx,dy;structpoint{floatx,y;}p1,p2,points[2];p1.x=p1.y=3.5f;p2.x=p2.y=1.5f;dx=p1.x-p2.x;dy=p1.y-p2.y;24结构变量本身可以作为一个整体来使用points[0]=p1;

points[1]=p2;25结构类型中的分量结构类型中分量的类型可以是任何类型基本数据类型的分量structpoint{floatx,y;};其他类型的分量：结构类型、数组类型分量的类型不能是未定义的结构类型分量的类型不能是正在定义的结构类型structcity{charname[32];

structcitycity1;}x;structcity{

structpoint{floatx,y;}location;intpopulation;

charname[32];}city1;structcity{

structpointlocation;intpopulation;charname[32];}city1;(city1.location).x26结构变量的内存布局结构中各分量在内存中顺序存放structsquare{structpoint{intx,y;}p1,p2;}sq1;sq1.p1.x=10;sq1.p1.y=20;sq1.p2.x=100;sq1.p2.y=200;主存储器sq1.p1.x1020100200**sq1.p1.ysq1.p2.xsq1.p2.y结构变量所占内存的大小结构变量所占内存的大小并不完全等于于各分量所占字节数的总和structchar_frequency{charc;intfrequency;};sizeof(strcutchar_frequency)通常为8，而非5这是编译器在编译时的一个特殊要求。27结构应用示例（1）救援洪水淹没了很多房子，只有屋顶还是安全的。被困的人们都爬上了屋顶。现在救生船每次都从大本营出发，到各屋顶救人，救了人之后将人送回大本营。救生船每次从大本营出发，以速度50米/分钟时向下一个屋顶，达到一个屋顶后，救下其上的所有人，每人上船1分钟，船原路返回，达到大本营，每人下船0.5分钟。假设大本营与任意一个屋顶的连线不穿过其它屋顶。输入：第一行是屋顶数n，其后n行，每行是每个屋顶的坐标和人数输出：第一行是所有人都到达大本营并登陆所用的时间，其后n行，每行是每个屋顶的坐标和人数2829图中原点是大本营，每个点代表屋顶，每个屋顶由其位置坐标和其上的人数表示。30#include<stdio.h>#include<math.h>#include<malloc.h>#defineMAX_ROOF_NUM1000#defineSPEED50.0#defineUP1.0#defineDOWN0.5intmain(){

introof_num;//屋顶数.scanf("%d",&roof_num);//输入屋顶数.structroof{

floatx,y;//屋顶坐标.

intp;//屋顶上的人数.}rfs[MAX_ROOF_NUM];

doubletotalTime=0;//救援总时间.

inti;//循环控制变量.

//用循环处理每一个屋顶，输入屋顶位置及人数数.for(i=0;i<roof_num;i++){31

//用循环处理每一个屋顶，输入屋顶位置及人数.

for(i=0;i<roof_num;i++{{scanf("%f%f%d",&(rfs[i].x),&(rfs[i].y),&(rfs[i].p));}

//用循环处理每一个屋顶，计算救援时间.

for(i=0;i<roof_num;i++){

//首先计算从大本营到屋顶的双程航行时间，并累加到总救援时间中.totalTime+=2*sqrt(rfs[i].x*rfs[i].x+rfs[i].y*rfs[i].y)/SPEED;

//然后计算被求人员上船和下船所耗费的总时间，并累加到总救援时间中.totalTime+=rfs[i].p*(UP+DOWN);}//打印出救援总时间.printf("TotalTimeis:%.2lf\n",totalTime);

//依次打印出各屋顶的位置及人数.

for(i=0;i<roof_num;i++){printf("RoofID:%d%.2f%.2f%d\n",i+1,rfs[i].x,rfs[i].y,rfs[i].p);}return0;}32结构应用示例（2）学生成绩统计定义一个结构，包含学生的所有信息。structstudent{intnumber;charname[8];charsex;intage;floatcourse[8];};structstudentclass1[160];33单个变量、数组和结构数组和结构：多个变量的集合数组通过数组可定义大量类型相同的变量数组元素通过“变量[下标]”形式访问静态数组的大小（数组元素的个数）是预先确定的，即数组定义中数组个数必须是整数常量结构结构把一组密切相关的变量（类型可以不同）组织成一个整体结构的分量通过"变量.分量"形式访问单个变量、数组和结构34更加复杂的数据定义结构中的数组结构中的结构结构数组复杂结构示例：教师、学生、班级structteacher_s{//教师结构

charname[32];//姓名

chartitle[16];//职称

intage;//年龄};structstudent_s{//学生结构

charname[32];//姓名

charsex;//性别

intage;//年龄};structclass_s{//班级结构

structteacher_steacher;//教师

structstudent_sstudents[180];//所有学生

intstudent_num;//学生人数};上机中的

问题

和

错误上机编写程序

的

基本流程第一步：按照题目要求，

在VC中编写、调试程序第二步：把调试成功的程序

提交到编程网格中问题：为什么

在VC的一个项目里面，

只能有一个main函数？VC的一个项目代表了一个C程序一个C程序只能具有一个main函数VC的一个项目里只能有一个main函数问题：为什么

main函数需要返回一个int值？

int

main(

)｛

return

0;

｝用于表示：在程序运行过程中是否发生了错误返回值为0，表示：没有发生错误在这们课程涉及的程序中，返回值固定为

0

！错误:include语句前没有

#

include<stdio.h>

intmain()｛

return0;｝#include<stdio.h>

intmain()｛

return0;｝✕✓关于关系运算表达式inta,b,c;……if(a>b>c){ ……}……✕inta,b,c;……If((a>b)&&(b>c){ ……}……✓分支结构中

的花括号…if(a>b){

print(“%d”,a); print(“%d”,b);}………if(a>b)

print(“%d”,a); print(“%d”,b);…………if(a>b){

print(“%d”,a);}print(“%d”,b);……=≠在任何情况下，scanf函数调用中都

不要出现

\n

……

scanf(“…\n…”,……);

……✕程序

的

书写风格intmain(){intresult;intnum;inti=1;while(i<=10){scanf(“%d”,&num);

if(i==1){result=num;}else{

if(num>result){

result=num;

}}i++;}printf(“%d\n”,result);return0;｝intmain(){ intresult; intnum; inti=1; while(i<=10){

scanf(“%d”,&num);

if(i==1){

result=num;

}else{

if(num>result){

result=num;

} }

i++; } printf(“%d\n”,result); return0;｝程序

的

书写风格风格1：每一行

最多

只写

一条语句……e=a;a=b;b=e;…………e=a;a=b;b=e;……程序

的

书写风格风格2：同一层次的语句

具有

相同的缩进 #include<stdio.h> intmain(){ inta,b,e; scanf(“%d%d”,&a,&b); if(a>b)｛ e=a; a=b; b=e; ｝ printf(“%d%d\n”,a,b); return0; }缩进1缩进2缩进3程序

的

书写风格if…else…语句

的

书写风格

if(a>b){ a+=b; printf(“a>b”);

}else{ b+=a; printf(“a<=b”);

}程序

的

书写风格while语句

的

书写风格 while(i<100){ sum+=i; i++; }程序

的

书写风格for语句

的

书写风格

for(inti=0;i<100;i++){ if(i%2==0){ continue; } sum+=i;

}程序

的

书写风格风格3：成对地

输入

左右花括号while(i<100)while(i<100)while(i<100){ sum+=i; i++;}while(i<100){

sum+=i; i++;}while(i<100){ sum+=i; i++;while(i<100){}step1step2step3step1step2step3编译出现错误时，

请从第一个错误开始分析！程序的调试语法错误：编译(组建)错误不要惊慌，编译结果输出窗口已经为你指明了程序的出错行及错误原因，可以据此来修改程序错误。改错时，应从出错信息中的第一条开始，用鼠标双击该条信息，程序源文件窗口就将定位到出错行。很多时候，程序编译后会出很多错误，但很可能是由第一个错误衍生而来的，改完第一个错误后，再编译时其他错误就不再出现了。所以，应该每修改完一个错误后就编译一次。二、关于程序的错误修改及调试{这里少了一个“{”。双击第一行，定位错误及了解错误原因！这里的一堆错误，都是由于上面少了一个“{”引起的！程序调试！程序运行不正确，怎么办？运行结果错：程序跟踪调试由于程序算法及其他原因，执行结果不正确，这时从源程序表面上就很难发现错误。跟踪调试：可以手动一步一步执行程序语句，在每条语句执行后，可以查看相关变量的值，以判断和预期结果是否相符；也可以了解程序的执行顺序，看它是否和预期的程序流程相符。断点设定：在跟踪调试前，还需要确定一下程序可能从哪里出错，设置一个断点，让程序在此停止自动运行，由我们手动一步一步发出程序执行命令。如果不能确定程序是从哪里出错，则可以将断点设置在程序的第一条语句处。程序的调试设置程序断点跟踪方式执行程序查看变量值当前程序执行停留在此行程序手动执行进入函数一步一步执行从函数中执行出来执行到光标所在行课堂参与

——请一个同学上来调试下面程序的问题所在//有一分数序列:2/1,3/2,5/3,8/5,13/8,21/13,...求出这个数列的前n项之和。#include<stdio.h>intmain(){ inta,b,e,m,n,i,j; doublesum=0.0; a=1; b=2; scanf("%d",&m); for(j=0;j<m;j++){ scanf("%d",&n); for(i=0;i<n;i++){ sum+=b/a; e=a; a=b; b=e+b; } printf("%.3lf\n",sum); } return0;}课堂练习练习1：接收用户输入的3个数字,输出其中的最小值程序输入3个数字程序输出3个数字中的最小值课堂参与请一位同学上台,编写上述程序课堂参与练习2：判断一个整数能否被7整除程序输入一个整数程序输出如果这个整数能被7整除，输出字符串true;否则，输出字符串false;请一位同学上台,编写上述程序练习3：判断一个整数的某个数位上是否存在数字7问题描述给定一个4位整数，判断这个数字的个位数、十位数、百位数和千位数这4个数字中是否存在数字7程序输入一个4位整数程序输出如果某个数位上的数字是7，输出字符串true否则，输出字符串false课堂参与请一位同学上台,编写上述程序练习4：判断某一年是否是闰年程序输入一个表示年份的整数（如，2012）程序输出如果这个年份是闰年，程序输出true;否则，程序输出false;闰年的充分必要条件是：“年份能被400整除”或者“年份能被4整除，但不能被100整除”课堂参与请一位同学上台,编写上述程序接收从控制台输出的两个整数（假设是两个正整数）输出这两个数的最大公约数练习5：求两个正整数的最大公约数#include<stdio.h>intmain(){

inta,b,t;scanf("%d%d",&a,&b);

//a和b的最大共数也是b和a%b的最大公约数t=a%b;

while(t!=0){a=b;b=t;t=a%b;}printf("%d\n",b);

return0;}接收从控制台输出的一组整数

（假设输入n个整数，n<=100）按输入相反的顺序输出这组整数练习6：逆序排列数组中的元素#include<stdio.h>#defineMAX100intmain(){

inta[MAX],i,j,n,t;scanf("%d",&n);

for(i=0;i<n;i++){scanf("%d",&a[i]);}for(i=0,j=n-1;i<j;i++,j--){t=a[i];a[i]=a[j];a[j]=t;}

for(i=0;i<n;i++){printf("%d\n",a[i]);

}

return0;}#include<stdio.h>#defineMAX100intmain(){

inta[MAX],i,j,n,t;scanf("%d",&n);

for(i=0;i<n;i++){scanf("%d",&a[i]);}

for(i=0,j=n-1;i<j;i++,j--){t=a[i];a[i]=a[j];a[j]=t;}

for(i=0;i<n;i++){printf("%d\n",a[i]);

}

return0;}接收从控制台输出的一组整数

（假设输入n个整数，n<=100）将数组中后m个数移动到数组头部要求不能使用辅助数组练习7：循环右移数组中的元素#include<stdio.h>#defineMAX100intmain(){

inta[MAX],i,j,m,n,t;scanf("%d%d",&n,&m);

for(i=0;i<n;i++){