C语言高级编程结构与习题课课件

1、第十八讲 C语言高级编程 结构与习题课北京大学信息学院第1页，共32页。2 结构的概念 通常，一个学生的个人信息，包括：学号、姓名、性别、年龄、各门功课的成绩等数据，这些数据都与一个学生相关联，类型各不相同。如果将这些数据定义为各独立的简单变量： Number、Name、Sex、Age、Course1、Course2、这样就难以反映它们之间的内在联系。应该把它们组织成一个组合项，把它们当作一个有机的整体。这个组合项就是结构（Structure）第2页，共32页。3结构类型及其定义把多个紧密关联的变量（分量）顺序组织在一起，定义成一个新的复合数据类型结构类型定义一个结构类型struct 结构类型

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

3、;系统会为结构类型变量分配内存空间第4页，共32页。5结构类型变量中分量的访问结构类型变量的值由其各个分量构成对分量的访问一般通过“变量名.分量名”完成结构赋值及访问的例子：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;结构变量本身可以作为一个整体来使用points0 = p1; points1 = p2;第5页，共32页。6结构类型中的分量结构类型中分量的类型可以是任何类型基本数据类型的分

4、量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).x第6页，共32页。7结

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

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

7、大本营，每个点代表屋顶，每个屋顶由其位置坐标和其上的人数表示。第10页，共32页。11程序示例：succor.cpp第11页，共32页。12结构应用示例（2）学生成绩统计定义一个结构，包含学生的所有信息。struct student int number; char name8; char sex; int age; float course8; ;struct student class1160;第12页，共32页。13单个变量、数组和结构数组和结构：多个变量的集合数组通过数组可定义大量类型相同的变量数组元素通过“变量下标”形式访问静态数组的大小（数组元素的个数）是预先确定的，即数组定义中数

8、组个数必须是整数常量结构结构把一组密切相关的变量（类型可以不同）组织成一个整体结构的分量通过变量. 分量形式访问第13页，共32页。int a;char str100;scanf(“%d”, &a);gets(str);字符串与数值从控制台输入字符串：scanf()：不能带空格gets()：可以有空格在一个程序中，尽量只使用一种输入函数。当既要输入有空格的字符串，又要输入数值时，应避免使用以下方式：14那该怎么办呢？第14页，共32页。字符串与数值在输入数值时也使用gets()，得到表示数值的字符串，再将该字符串转换成数值。int atoi(char *str)：将字符串转换成整数double

9、 atof(char *str)：将字符串转换成浮点数15#include 第15页，共32页。字符串与数值16#include #include #include int main()char s100;double x;int i;gets(s); /* Test of atof */x = atof( s );printf( atof test: ASCII string: %s float: %lfn, s, x );gets(s); /* Test of atoi */i = atoi( s );printf( atoi test: ASCII string: %s integer:

10、 %dn, s, i );return 0;第16页，共32页。小明的药物动力学名词词典17第17页，共32页。小明的药物动力学名词词典回顾排序：排序的基本思想18对数组 int szLEN进行排序，可以分为 LEN 个步骤进行。 第 k 步：把第 k 大的数放在变量 szLEN-k 中；（K=1, 2, 3, 4, , LEN-1, LEN）第18页，共32页。小明的药物动力学名词词典回顾排序：冒泡排序19int e;for(int k = 1 ; k = LEN ; k+)for(int i = 0; i szi+1)e = szi+1;szi+1 = szi;szi = e;第19页，共

11、32页。小明的药物动力学名词词典数据表示：字符串数组char word100100;字符串大小比较：strcmp(str1, str2)strcmp(wordi, wordi+1) 0字符串内容的交换：strcpy(str1, str2)char temp100;strcpy(temp, wordi); strcpy(wordi, wordi+1);strcpy(wordi+1, temp);20第20页，共32页。21#include #include int main()int n, k, i;char word100100, temp100; /字符串数组scanf(%d, &n);fo

12、r(i=0; in; i+) /输入字符串scanf(%s, wordi);for(k=1; k=n; k+) /排序for(i=0; i0 ) /字符串大小比较strcpy(temp, wordi); /字符串交换strcpy(wordi, wordi+1);strcpy(wordi+1, temp);for(i=0;in;i+) /输出字符串printf(%sn,wordi);return 0;第21页，共32页。22大整数的加法问题描述 请编写一个程序帮助统计局完成以下计算任务：从键盘输入两个正整数m和n（根据统计需要，m和n最多可以是200位十进制正整数），计算m和n的和，并打印输出。

13、第22页，共32页。23大整数的加法计算 83856 + 129476解决输入的问题：利用字符数组接收输入；为了进行计算：把字符数组转换成整数数组，每个元素 与字符数组中的每个字符相对应；转换过程中可以顺便更换一下摆放顺序，以便符合我们平时的竖式计算习惯；按照规则进行计算，用数组元素操作每一位（注意进位）；把操作结果按照“先高位再低位”的顺序输出出来；838561294768385612947665838674921233312213332第23页，共32页。24#define MAX_LEN 201#include int main()int an1MAX_LEN = 0, an2MAX_L

14、EN = 0; int sumMAX_LEN = 0;char seLine1MAX_LEN, seLine2MAX_LEN;printf(please input two integers:n);gets(seLine1);gets(seLine2);int nLen1 = strlen(seLine1);int nLen2 = strlen(seLine2);使用strlen()函数： 获得字符串的长度！第24页，共32页。25int i, j; /将输入的两个字符数组变成整数数组，并倒置for (i = nLen1-1, j=0; i=0; i-, j+)an1j = seLine1i

15、- 0; for (i = nLen2-1, j=0; i=0; i-, j+)an2j = seLine2i - 0; 838560129476065838000006749210000字符数组整数数组第25页，共32页。int carry = 0; /进位值for (i = 0; i = 10) sumi -= 10; carry = 1; else carry = 0;i = MAX_LEN -1;while(sumi=0) /找到第一个不为0的位 i-; for(;i = 0; i-) /假设总和不为0！printf(%d, sumi); /输出每一位数printf(n);return

16、 0;65838000006749210000233312000021333226carry第26页，共32页。算法的效率素数问题判断一个数是否素数27int isPrimeNumber(int p)int i, half, isPrime1;if ( p % 2 = 0 ) if ( p = 2 ) return isPrime; isPrime = 0;return isPrime;half = p - 1;for( i = 3; i = half; i = i+2 ) if( p % i = 0 ) isPrime = 0;break;return isPrime;half = p /

17、2; half = sqrt(p);第27页，共32页。算法的效率素数问题验证哥德巴赫猜想28int GoldbachConjecture(int n) / 验证偶数n满足哥德巴赫猜想int half = n/2; / 求出半数n/2待用int i, result = 0, isPrime1, isPrime2;for( i = 3; i 2int i; / 循环变量int isPrime; / 临时变量 printf(“The primes less than %d are 2”, n);for( i = 3; i 2int number=1; /小于n的素数的个数int primes100

18、; /用于存放素数int i, j; /循环变量primes0 = 2; /2是第一个素数printf(“The primes less than %d are 2”, n);for( i = 3; i = n; i = i + 2 ) /判断i是否被它之前的素数整除for(j=0; primesj*primesji ) /如果i不能被它之前的素数整除，则它也是素数primesnumber = i;number+;printf(“,%d, i);一个效率更高的算法：如果一个数不是素数那么它一定是若干个小于它的素数的乘积，并且它小于在它之前的那个最大素数的平方。问题：修改这个函数，求第n个素数？求小于n的所有素数第30页，共32页。31int nthPrime(int n)int number=1; /小于n的素数的个数int *primes = (int *)malloc(sizeof(int)*n); /用于存放素数int i, j; / 循环变量primes0 = 2; /2是第一