第10讲-复合数据结构——数组与结构

1、第十讲：复合数据结构数组与结构北京大学 信息科学技术学院2013年12月#include int main()int a, b;int e;scanf(%d, &a);scanf(%d, &b);if(a b)e = a;a = b;b = e; printf(%d %dn, a, b); return 0;#include int main()int a, b, c;int e;scanf(%d, &a);scanf(%d, &b);scanf(%d, &c);if(a b)e = a;a = b;b = e;if(b c)e = b;b = c;c = e;if(a b)e = a;a =

2、 b;b = e;printf(%d %d %dn, a, b, c); return 0;如果要求：1. 接收用户输入的10个数字2. 输出的10个数字按照 从小到大 的顺序排列难道需要这样定义10个变量吗？int a, b, c, d, e, f, g, h, i, j;有没有一种 更简便的方式，可以一次定义一组变量？内容题要 复合数据结构 数组 结构数组数组 是 什么？数组 是 一组变量数组 是 一组 具有编号 的 变量如何声明 一个数组int sz10; 数组的类型数组名数组中变量的数目必须是一个常量数组 中 变量 的 编号int sz10; 数组中变量的编号 从 0 开始； 到 数组

3、的长度1 结束0 1 2 3 4 5 6 7 8 9如何访问 数组 中 的 变量int sz10;sz0 = 1;sz1 = 3;sz2 = 7;sz8 = 16;sz9 = 12; sz2; 数组名变量编号数组变量赋值 的 一种特殊方式 声明时赋值int sz5 =12, 3, 7, 28, -2; #include int main()int sz10;int i;for( ; ; ) ;for(i = 0; i 10; i+)printf(%d , szi);return 0;程序填空；要求：1.接收用户输入的10个数字2.存放在数组sz中#include int main()int s

4、z10;int i;for( i=0 ; i 10 ; i+)scanf(%d, &(szi);for(i = 0; i 10; i+)printf(%d , szi);return 0;数组 的 遍历通过 循环结构正向 遍历int szLEN; for(int i = 0; i = 0; i-) szi 通过遍历 实现 对 数组变量 的 控制台赋值int szLEN; for(int i = 0; i LEN; i+)scanf(“%d”, &(szi);通过遍历 实现 对 数组变量 的 控制台输出int szLEN; for(int i = 0; i LEN; i+)printf(“%dn

5、”, szi);数组 的 应用示例当程序要处理一组类型相同、含义类似的数据时，应该使用数组游戏：过年抽奖 一个村庄，有128个村民 村长对村民说： 今年村里出现了财政盈余M元； M是20003000之间的一个整数 准备通过抽奖的方式把钱发给村民 游戏规则如下： 每个村民上报一个在20003000元之间的整数 如果有人上报的数字和M相等，就把钱发给这些人 如果只有一个村民猜对，就把M元钱全部发给他 如果有多个人村民猜对，就把M元钱平均分配给这些村民村长邀请我们编写一个程序， 实现村里财政盈余的自动分配编程的基本思路 定义一个数组 存放所有村民上报的数据 定义一个数组 存放获奖者的编号（幸运者数组

6、） 定义一个整数 存放获奖者人数 对村民从0开始编号（最后一个编号是127） 村民按照编号顺序上报数字；程序将村民上报的数字存放在对应编号的数组变量中。 遍历村民上报的数字，若上报数字与幸运数相等，则 将村民编号添加到幸运者数组中； 并将获奖者人数加1 最后，打印出获奖者编号和获得的奖金数额#define LUCKY_M 2345#define LUCKY_M 2345 /财政盈余财政盈余#define POPULATION 128 #define POPULATION 128 /村民数量村民数量int main( )int main( ) int peoplePOPULATION; int

7、peoplePOPULATION; /记录所有村民上报数字的数组记录所有村民上报数字的数组 int luckyPeoplePOPULATION;int luckyPeoplePOPULATION; /幸运者数组，记录获奖者编号幸运者数组，记录获奖者编号 int nLucky=0; int nLucky=0; /获奖者人数获奖者人数 int i; int i; /循环变量循环变量 for (i=0; iPOPULATION; i+) for (i=0; iPOPULATION; i+) scanf(“%d”, scanf(“%d”, &(peoplei)&(peoplei); ); /读入村民报

8、的数字，数组下标就是村民的编号读入村民报的数字，数组下标就是村民的编号 for (i=0; iPOPULATION; i+) for (i=0; iPOPULATION; i+) if ( peoplei = LUCKY_M ) if ( peoplei = LUCKY_M ) luckyPeoplenLucky = i; luckyPeoplenLucky = i; nLucky +; nLucky +; /输出获奖者编号及所获奖金数额输出获奖者编号及所获奖金数额 for (i=0; inLucky; i+) for (i=0; inLucky; i+) printf(%d %dn, luc

9、kyPeoplei, LUCKY_M / nLucky); printf(%d %dn, luckyPeoplei, LUCKY_M / nLucky); return 0; return 0; 回顾排序：冒泡排序回顾排序：冒泡排序int i, k, e, szLEN;for(i = 0; i LEN; i+)scanf(“%d”, &(szi);for(k = 1 ; k = LEN ; k+)for(i = 0; i szi+1)e = szi+1;szi+1 = szi;szi = e;#define LEN 10结构 结构的结构的概念概念 通常，一个学生的个人信息，包括：学号、姓名、性

10、别、年龄、各门功课的成绩等数据，这些数据都与一个学生相关联，类型各不相同。如果将这些数据定义为各独立的简单变量：n Number、Name、Sex、Age、Course1、Course2、 这样就难以反映它们之间的内在联系。应该把它们组织成一个组合项，把它们当作一个有机的整体。这个组合项就是结构（结构（Structure）25结构类型及其定义 把多个紧密关联的变量（分量分量）顺序组织在一起，定义成一个新的复合数据类型结构类型结构类型 定义一个结构类型定义一个结构类型struct 结构类型名结构类型名 类型类型1 分量名分量名1; 类型类型2 分量名分量名2; .; 结构分量的类型可以相同，也可

11、不同 同一个结构内的分量名不可相同26struct point float x; float y;结构类型变量的定义 结构类型只是定义了一种新的数据类型一种新的数据类型 系统并不为这个新类型分配内存空间。 可以使用新的结构类型来声明变量结构类型变量。 结构类型变量结构类型变量定义的两种形式： 用已定义的结构定义变量，例如：struct point point1;struct point point2; 定义结构的同时定义结构类型的变量，例如：struct city float x, y; int population; city1, city2; 系统会为结构类型变量分配内存空间系统会为结构类

12、型变量分配内存空间27结构类型变量中分量的访问 结构类型变量的值由其各个分量构成 对分量的访问一般通过“变量名变量名.分量名分量名”完成 结构赋值及访问的例子：float dx, dy;struct point float x, y; p1, p2, points2;p1.x = p1.y = 3.5f;p2.x = p2.y = 1.5f;dx = p1.x - p2.x;dy = p1.y - p2.y;28结构变量本身可以作为一个整体来使用结构变量本身可以作为一个整体来使用points0 = p1; points1 = p2;29结构类型中的分量 结构类型中分量的类型可以是任何类型 基本

13、数据类型的分量struct point float x, y; 其他类型的分量：结构类型、数组类型 分量的类型不能是未定义的结构类型 分量的类型不能是正在定义的结构类型struct city char name32; struct city city1;x;struct city struct point float x, y; location; int population; char name32;city1;struct city struct point location; int population; char name32;city1; (city1.location).x30

14、结构变量的内存布局 结构中各分量在内存中顺序存放struct square struct point int x, 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结构变量所占内存的大小 结构变量所占内存的大小并不完全等于于各分量所占字节数的总和struct char_frequency char c; int frequency;sizeof(strcut char_frequency)通常为通常为8，

15、而非，而非5这是编译器在编译时的一个特殊要求。这是编译器在编译时的一个特殊要求。31结构应用示例（1）救援 洪水淹没了很多房子，只有屋顶还是安全的。被困的人们都爬上了屋顶。现在救生船每次都从大本营出发，到各屋顶救人，救了人之后将人送回大本营。 救生船每次从大本营出发，以速度50米/分钟时向下一个屋顶，达到一个屋顶后，救下其上的所有人，每人上船1分钟，船原路返回，达到大本营，每人下船0.5分钟。 假设大本营与任意一个屋顶的连线不穿过其它屋顶。 输入：第一行是屋顶数n，其后n行，每行是每个屋顶的坐标和人数 输出：第一行是所有人都到达大本营并登陆所用的时间，其后n行，每行是每个屋顶的坐标和人数323

16、3NiiiipspeedyxtotalTime122)5 . 01 (2(图中原点是大本营，每个点代表屋顶，每个屋顶由其位置坐标和其上的人数表示。34#include #include #include #define MAX_ROOF_NUM 1000#define SPEED 50.0#define UP 1.0#define DOWN 0.5int main() int roof_num; / 屋顶数屋顶数. scanf(%d, &roof_num); / 输入屋顶数输入屋顶数. struct roof float x, y; / 屋顶坐标屋顶坐标. int p; / 屋顶上的人数屋顶上

17、的人数. rfsMAX_ROOF_NUM; double totalTime = 0; / 救援总时间救援总时间. int i; / 循环控制变量循环控制变量. /用循环处理每一个屋顶，输入屋顶位置及人数数用循环处理每一个屋顶，输入屋顶位置及人数数. for (i=0; iroof_num; i+)35 /用循环处理每一个屋顶，输入屋顶位置及人数用循环处理每一个屋顶，输入屋顶位置及人数. for (i=0; iroof_num; i+ scanf(%f%f%d,&(rfsi.x), &(rfsi.y), &(rfsi.p); / 用循环处理每一个屋顶，计算救援时间用循环处理每一个屋顶，计算救援

18、时间 . for (i=0; iroof_num; i+) / 首先计算从大本营到屋顶的双程航行时间，并累加到总救援时间中首先计算从大本营到屋顶的双程航行时间，并累加到总救援时间中 . totalTime += 2 * sqrt(rfsi.x*rfsi.x + rfsi.y*rfsi.y) / SPEED; / 然后计算被求人员上船和下船所耗费的总时间，并累加到总救援时间中然后计算被求人员上船和下船所耗费的总时间，并累加到总救援时间中 . totalTime += rfsi.p * (UP + DOWN); / 打印出救援总时间打印出救援总时间. printf(Total Time is: %

19、.2lfn, totalTime); / 依次打印出各屋顶的位置及人数依次打印出各屋顶的位置及人数. for (i=0; iroof_num; i+) printf(Roof ID: %d %.2f %.2f %dn, i+1, rfsi.x, rfsi.y, rfsi.p); return 0;36结构应用示例（2）学生成绩统计n定义一个结构，包含学生的所有信息。struct student int number; char name8; char sex; int age; float course8; ;struct student class1160;37单个变量、数组和结构 数组和结

20、构：多个变量的集合多个变量的集合 数组 通过数组可定义大量类型相同类型相同的变量 数组元素通过“变量变量下标下标”形式访问 静态数组的大小（数组元素的个数）是预先确定的，即数组定义中数组个数必须是整数常量 结构 结构把一组密切相关的变量（类型可以不同）密切相关的变量（类型可以不同）组织成一个整体 结构的分量通过变量变量. 分量分量形式访问单个变量、数组和结构38n更加复杂的数据定义更加复杂的数据定义n结构中的数组结构中的数组n结构中的结构结构中的结构n结构数组结构数组复杂结构示例：教师、学生、班级struct teacher_s / 教师结构教师结构 char name32; / 姓名姓名 c

21、har title16; / 职称职称 int age; / 年龄年龄;struct student_s / 学生结构学生结构 char name32; / 姓名姓名 char sex; / 性别性别 int age; / 年龄年龄;struct class_s / 班级结构班级结构 struct teacher_s teacher; / 教师教师 struct student_s students180; / 所有学生所有学生 int student_num; / 学生人数学生人数;习题习题1.接收从控制台输出的两个整数 （假设是两个正整数）2.输出这两个数的最大公约数#include in

22、t main() int a, 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(%dn, b); return 0;1.接收从控制台输出的一组整数 （假设输入n n个整数，n n = 100 = 100）2.按输入相反的顺序输出这组整数#include #define MAX 100int main() int aMAX, i, j, n, t; scanf(%d, &n); for (i = 0

23、; i n; i+) scanf(%d, &ai); for (i = 0, j = n-1; i j; i+, j-) t = ai; ai = aj; aj = t; for (i = 0; i n; i+) printf(%dn, ai); return 0;#include #define MAX 100int main() int aMAX, i, j, n, t; scanf(%d, &n); for (i = 0; i n; i+) scanf(%d, &ai); for (i = 0, j = n-1; i j; i+, j-) t = ai; ai = aj; aj = t; for (i = 0; i n; i+) printf(%dn, ai); return 0;1.接收从控制台输出的一组整数 （假设输入n n个整数，n n = 100 = 100）2.将数组中后m m个数移动到数组头部3.要求不能使用辅助数组#include #define MAX 100int main() int aMAX, i, j, m, n, t; scanf(%d%d, &n, &m); for (i = 0; i n; i+) scanf(%d, &ai); for (j = 0; j 0; i-) ai = ai-1; a0 = t; for (i = 0; i n;