计算概论 第十八讲 C语言高级编程 结构与习题课 北京大学信息学院.

Presentation on theme: "计算概论 第十八讲 C语言高级编程 结构与习题课 北京大学信息学院."— Presentation transcript:

1 计算概论 第十八讲 C语言高级编程 结构与习题课 北京大学信息学院

2 计算概论 结构的概念 通常，一个学生的个人信息，包括：学号、姓名、性别、年龄、各门功课的成绩等数据，这些数据都与一个学生相关联，类型各不相同。如果将这些数据定义为各独立的简单变量： Number、Name、Sex、Age、Course1、Course2、… 这样就难以反映它们之间的内在联系。应该把它们组织成一个组合项，把它们当作一个有机的整体。 ——这个组合项就是结构（Structure）

3 结构类型及其定义 把多个紧密关联的变量（分量）顺序组织在一起，定义成一个新的复合数据类型——结构类型 定义一个结构类型
计算概论 结构类型及其定义 把多个紧密关联的变量（分量）顺序组织在一起，定义成一个新的复合数据类型——结构类型 定义一个结构类型 struct 结构类型名 { 类型1 分量名1; 类型2 分量名2; ...... }; 结构分量的类型可以相同，也可不同 同一个结构内的分量名不可相同 struct point { float x; float y; };

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

5 结构类型变量中分量的访问 points[0] = p1; points[1] = p2; 结构类型变量的值由其各个分量构成
计算概论 结构类型变量中分量的访问 结构类型变量的值由其各个分量构成 对分量的访问一般通过“变量名.分量名”完成 结构赋值及访问的例子： float dx, dy; struct point { float x, 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; 结构变量本身可以作为一个整体来使用 points[0] = p1; points[1] = p2;

6 结构类型中的分量 (city1.location).x 结构类型中分量的类型可以是任何类型 分量的类型不能是未定义的结构类型
计算概论 结构类型中的分量 结构类型中分量的类型可以是任何类型 基本数据类型的分量 struct point{ float x, y; }; 其他类型的分量：结构类型、数组类型 分量的类型不能是未定义的结构类型 分量的类型不能是正在定义的结构类型 struct city { struct point{ float x, y; }location; int population; char name[32]; }city1; struct city{ struct point location; (city1.location).x struct city { char name[32]; struct city city1; }x;

7 结构变量的内存布局 结构中各分量在内存中顺序存放 主存储器 10 sq1.p1.x 20 sq1.p1.y 100 sq1.p2.x 200
计算概论 结构变量的内存布局 结构中各分量在内存中顺序存放 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; 主存储器 10 20 100 200 * sq1.p1.x sq1.p1.y sq1.p2.x sq1.p2.y

8 结构变量所占内存的大小 结构变量所占内存的大小并不完全等于于各分量所占字节数的总和 这是编译器在编译时的一个特殊要求。
计算概论 结构变量所占内存的大小 结构变量所占内存的大小并不完全等于于各分量所占字节数的总和 struct char_frequency { char c; int frequency; }; sizeof(strcut char_frequency)通常为8，而非5 这是编译器在编译时的一个特殊要求。

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

10 计算概论 图中原点是大本营，每个点代表屋顶， 每个屋顶由其位置坐标和其上的人数表示。

11 计算概论 程序示例： succor.cpp

12 结构应用示例（2）学生成绩统计 struct student { int number; char name[8]; char sex;
计算概论 结构应用示例（2）学生成绩统计 定义一个结构，包含学生的所有信息。 struct student { int number; char name[8]; char sex; int age; float course[8]; }; struct student class1[160];

13 单个变量、数组和结构 数组和结构：多个变量的集合 数组 结构 通过数组可定义大量类型相同的变量 数组元素通过“变量[下标]”形式访问
计算概论 单个变量、数组和结构 数组和结构：多个变量的集合 数组 通过数组可定义大量类型相同的变量 数组元素通过“变量[下标]”形式访问 静态数组的大小（数组元素的个数）是预先确定的，即数组定义中数组个数必须是整数常量 结构 结构把一组密切相关的变量（类型可以不同）组织成一个整体 结构的分量通过"变量. 分量"形式访问

14 字符串与数值 那该怎么办呢？ 从控制台输入字符串：
scanf()：不能带空格 gets()：可以有空格 在一个程序中，尽量只使用一种输入函数。当既要输入有空格的字符串，又要输入数值时，应避免使用以下方式： int a; char str[100]; scanf(“%d”, &a); gets(str); 那该怎么办呢？

15 字符串与数值 在输入数值时也使用gets()，得到表示数值的字符串，再将该字符串转换成数值。
int atoi(char *str)：将字符串转换成整数 double atof(char *str)：将字符串转换成浮点数 #include <stdlib.h>

16 字符串与数值 #include <stdio.h> #include <string.h>
#include <stdlib.h> int main() { char s[100]; double x; int i; gets(s); /* Test of atof */ x = atof( s ); printf( "atof test: ASCII string: %s float: %lf\n", s, x ); gets(s); /* Test of atoi */ i = atoi( s ); printf( "atoi test: ASCII string: %s integer: %d\n", s, i ); return 0; } 字符串与数值

17 小明的药物动力学名词词典

18 小明的药物动力学名词词典 （K=1, 2, 3, 4, …, LEN-1, LEN） 回顾排序：排序的基本思想
对数组 int sz[LEN]进行排序， 可以分为 LEN 个步骤进行。 第 k 步：把第 k 大的数放在变量 sz[LEN-k] 中； （K=1, 2, 3, 4, …, LEN-1, LEN）

19 小明的药物动力学名词词典 回顾排序：冒泡排序 int e; for(int k = 1 ; k <= LEN ; k++){
for(int i = 0; i < LEN - k; i++){ if(sz[i] > sz[i+1]){ e = sz[i+1]; sz[i+1] = sz[i]; sz[i] = e; }

20 小明的药物动力学名词词典 数据表示：字符串数组 字符串大小比较：strcmp(str1, str2)
char word[100][100]; 字符串大小比较：strcmp(str1, str2) strcmp(word[i], word[i+1]) > 0 字符串内容的交换：strcpy(str1, str2) char temp[100]; strcpy(temp, word[i]); strcpy(word[i], word[i+1]); strcpy(word[i+1], temp);

21 #include <stdio.h>
#include <string.h> int main() { int n, k, i; char word[100][100], temp[100]; //字符串数组 scanf("%d", &n); for(i=0; i<n; i++){ //输入字符串 scanf("%s", word[i]); } for(k=1; k<=n; k++){ //排序 for(i=0; i<n-k; i++){ if( strcmp(word[i], word[i+1])>0 ){ //字符串大小比较 strcpy(temp, word[i]); //字符串交换 strcpy(word[i], word[i+1]); strcpy(word[i+1], temp); for(i=0;i<n;i++){ //输出字符串 printf("%s\n",word[i]); return 0;

22 大整数的加法 问题描述 请编写一个程序帮助统计局完成以下计算任务：
从键盘输入两个正整数m和n（根据统计需要，m和n最多可以是200位十进制正整数），计算m和n的和，并打印输出。

23 大整数的加法 计算 83856 + 129476 213332 解决输入的问题：利用字符数组接收输入；
为了进行计算：把字符数组转换成整数数组，每个元素 与字符数组中的每个字符相对应； 转换过程中可以顺便更换一下摆放顺序，以便符合我们平时的竖式计算习惯； 按照规则进行计算，用数组元素操作每一位（注意进位）； 把操作结果按照“先高位再低位”的顺序输出出来； 83856 129476 8 3 5 6 6 5 8 3 1 2 9 4 7 6 6 7 4 9 2 1 2 3 1 213332

24 使用strlen()函数： 获得字符串的长度！ int main() { #define MAX_LEN 201
#include <string.h> int main() { int an1[MAX_LEN] = {0}, an2[MAX_LEN] = {0}; int sum[MAX_LEN] = {0}; char seLine1[MAX_LEN], seLine2[MAX_LEN]; printf("please input two integers:\n"); gets(seLine1); gets(seLine2); int nLen1 = strlen(seLine1); int nLen2 = strlen(seLine2); 使用strlen()函数： 获得字符串的长度！

25 //将输入的两个字符数组变成整数数组，并倒置 for (i = nLen1-1, j=0; i>=0; i--, j++){
int i, j; //将输入的两个字符数组变成整数数组，并倒置 for (i = nLen1-1, j=0; i>=0; i--, j++){ an1[j] = seLine1[i] - '0'; } for (i = nLen2-1, j=0; i>=0; i--, j++){ an2[j] = seLine2[i] - '0'; 8 3 5 6 \0 6 5 8 3 1 2 9 4 7 6 \0 6 7 4 9 2 1 字符数组 整数数组

26 int carry = 0; //进位值 for (i = 0; i < MAX_LEN; i++) { sum[i] = an1[i] + an2[i] + carry; if(sum[i] >= 10){ sum[i] -= 10; carry = 1; } else { carry = 0; } i = MAX_LEN -1; while(sum[i]==0) { //找到第一个不为0的位 i--; for(;i >= 0; i--){ //假设总和不为0！ printf("%d", sum[i]); //输出每一位数 printf("\n"); return 0; 6 5 8 3 6 7 4 9 2 1 carry 2 3 1 213332

27 算法的效率——素数问题 判 断 一 个 数 是 否 素 half = sqrt(p); half = p / 2;
int isPrimeNumber(int p) { int i, half, isPrime＝1; if ( p % 2 == 0 ) { if ( p == 2 ) { return isPrime; } isPrime = 0; half = p - 1; for( i = 3; i <= half; i = i+2 ) { if( p % i == 0 ) { break; 判 断 一 个 数 是 否 素 half = sqrt(p); half = p / 2;

28 算法的效率——素数问题 验证哥德巴赫猜想 大于6的偶数能够分解为2个素数的和
int GoldbachConjecture(int n) // 验证偶数n满足哥德巴赫猜想 { int half = n/2; // 求出半数n/2待用 int i, result = 0, isPrime1, isPrime2; for( i = 3; i <= half; i = i + 2 ){ isPrime1 = isPrimeNumber(i); isPrime2 = isPrimeNumber(n-i); if( isPrime1 && isPrime2 ){ printf("%d = %d + %d\n", n, i, n-i); result = 1; break; } return result;

29 算法的效率——素数问题 求小于n的所有素数：简单判断法 void AllPrimes(int n) //假设n>2 {
int i; // 循环变量 int isPrime; // 临时变量 printf(“The primes less than %d are 2”, n); for( i = 3; i <= n; i = i + 2 ) isPrime = isPrimeNumber(i); if( isPrime ) printf(“,%d", i); }

30 求小于n的所有素数 问题：修改这个函数，求第n个素数？
一个效率更高的算法：如果一个数不是素数那么它一定是若干个小于它的素数的乘积，并且它小于在它之前的那个最大素数的平方。 求小于n的所有素数 void AllPrimes(int n) //假设n>2 { int number=1; //小于n的素数的个数 int primes[100]; //用于存放素数 int i, j; //循环变量 primes[0] = 2; //2是第一个素数 printf(“The primes less than %d are 2”, n); for( i = 3; i <= n; i = i + 2 ) { //判断i是否被它之前的素数整除 for(j=0; primes[j]*primes[j]<i; j++) if( i%primes[j]==0 ) break; } if( primes[j]*primes[j]>i ) //如果i不能被它之前的素数整除，则它也是素数 primes[number] = i; number++; printf((“,%d", i); 问题：修改这个函数，求第n个素数？

31 求第n个素数 int nthPrime(int n) { int number=1; //小于n的素数的个数
int *primes = (int *)malloc(sizeof(int)*n); //用于存放素数 int i, j; // 循环变量 primes[0] = 2; //2是第一个素数 if( n==1 ) return 2; for( i = 3; ; i = i + 2 ) { //判断i是否被它之前的素数整除 for(j=0; primes[j]*primes[j]<i; j++) if( i%primes[j]==0 ) break; } if( primes[j]*primes[j]>i ) //如果i不能被它之前的素数整除，则它也是素数 primes[number] = i; number++; if( number == n ){ return i;

32 后续课程安排 今天是最后一次作业，大家辛苦了！ 12月12日讲链表 12月14日讲文件（乐驹），下午上机第一次模拟测试，必须参加。
12月21日总复习，下午上机第二次模拟测试。 12月30日下午2点答疑？（初定）