C语言程序设计进阶.ppt

1、C语言程序设计进阶,2005-01-02,尹宝林：C语言程序设计,2,程序调试的基本过程,观察和记录错误的现象 分析错误的原因 修改程序 观察和记录修改后的效果,2005-01-02,尹宝林：C语言程序设计,3,程序调试的要点,确认错误的现象 确定性/可重现 非确定性/不可重现 确认发生错误的条件 引起错误的操作命令和顺序 引起错误的数据 逐步缩小可能产生故障的范围 确认发生错误的语句和相关变量的值,2005-01-02,尹宝林：C语言程序设计,4,程序调试的基本方法,故障定位 确定程序执行的过程 判断程序出错的位置 在关键点打印出必要的信息 程序跟踪 设置断点 观察变量的内容 增加必要的中间

2、变量和调试语句,2005-01-02,尹宝林：C语言程序设计,5,程序调试的基本方法(续),缩小故障的规模 发现引起故障的最小操作序列 构造引起故障的最小数据 缩小程序的存储空间分配 缩小故障原因搜索的范围 了解程序的基本执行过程 分析可能的原因 使用系统分析的方法,2005-01-02,尹宝林：C语言程序设计,6,程序调试的基本方法(续),排除法 基本思想 缩小问题的查找范围 确定问题发生的区间 对问题的位置进行初步分析 搜索问题可能发生的位置 屏蔽程序的某些部分 屏蔽后观察错误是否仍存在 屏蔽的方法：注释,2005-01-02,尹宝林：C语言程序设计,7,程序调试的基本方法(续),跟踪法

3、从出错功能的顶层函数出发 逐级向下检查 调用函数所传递的参数和返回值 变量内容的变化 回溯法 从表现出错误的最后一个函数开始 逐级向上检查函数所传递的参数及中间变量,2005-01-02,尹宝林：C语言程序设计,8,错误确认,错误现象的准确描述 对复杂程序和复杂错误应排除不相干的内容 使错误可以重现 最小的操作序列和最小的数据集 发现错误现象出现的条件和规律 纪录 图表 统计特性,2005-01-02,尹宝林：C语言程序设计,9,错误定位,充分的测试数据 对程序结构的理解和掌握 分析、判断和验证 可能故障点的调试信息输出 缩小查找范围 显示执行路径和可达位置 对半区间查找（二分法）/黄金分割法

4、,2005-01-02,尹宝林：C语言程序设计,10,程序调试的例,动态内存分配及释放 int * alloc_2d(int n,int m); void main() int n, m, *ang, i; scanf(%d%d, /为什么这个地方有错误? /为什么Debug状态下出错？,int * alloc_2d(int n，int m) int i,j; int *p = malloc(n * sizeof(int *); if (p = NULL) fprintf(stderr, error: out of memory!n); return NULL; for (i = 0; i m

5、; i+) pi = malloc(m * sizeof(int); if (pi = NULL) fprintf(stderr, error: out of memory!n); for (j=0; j i; j+) free(pj); free(p); return NULL; return p; ,2005-01-02,尹宝林：C语言程序设计,12,程序调试的例（续）,确认故障现象 选择程序运行参数 有分辨度 便于观察 设置断点 在关键位置设置：内存的分配和释放点 观察程序在断点处的状态 内存的分配和释放时的地址,2005-01-02,尹宝林：C语言程序设计,13,程序调试的例（续）,选

6、择程序运行参数 m和n应该不同 m和n应该较小 确认在选择的参数下问题存在 实际选择参数：5，8,2005-01-02,尹宝林：C语言程序设计,14,程序调试的例（续）,观察程序在断点处的状态 记录分配和释放时的地址 注意程序执行的过程 观察结果 对行空间的分配执行了8次,2005-01-02,尹宝林：C语言程序设计,15,程序调试的例（续）,查找故障原因 阅读相关的代码 for (i = 0; i m; i+) pi = malloc(m * sizeof(int); 修改及确认 在Debug和Release状态下差异的原因,讲义中的代码 void *alloc_2d(int item_si

7、ze, int m, int n) void *p = malloc(m * sizeof(void *); if (p = NULL) fprintf(stderr, Out of memory!n); return NULL; for (i = 0; i m; i+) pi = malloc(n * item_size); if (pi = NULL) for (j = 0; j i; j+) free(pj); free(p); fprintf(stderr, Out of memory!n); return NULL; return p; ,2005-01-02,尹宝林：C语言程序设计

8、,17,期中测验题目讨论,第一组题目 实数格式识别real 求倒数 - reciproc 词频统计 - frequency 第二组题目 球的排放 - ball 字符串排序 - sortstr 后缀表达式求值 - express,2005-01-02,尹宝林：C语言程序设计,18,对题目的分析,考核内容 题目给出的条件及含义 问题的切入点和基本算法 注意要点 实现细节 测试数据,2005-01-02,尹宝林：C语言程序设计,19,实数格式识别real,实数书写格式分一般格式和科学格式： 一般格式= 科学格式= 各项之间无分隔符。描述中由括起的内容说明该项的属性， 括起的内容为可选的属性。例如，+

9、2、-1.56为一般格式的实数，而6.2E-2、-9E8为科学格式的实数。 分析数的书写是否正确，以及书写方式。,2005-01-02,尹宝林：C语言程序设计,20,实数格式识别（续）,考核要点 基本程序设计 字符串的处理 可能的方法 状态机（FA） 字符串分析,参考程序 void deal_real(char *s)/ 入口函数 char *p; p = strchr(s, E); if (p != NULL) *p = 0; if (is_real(s) ,int pure_digit(char *s) if (strlen(s) = 0 | !isdigit(*s) return 0;

10、for (; *s != 0 ,2005-01-02,尹宝林：C语言程序设计,23,求倒数 - reciproc,求 1/a，其中 2= a = 10000 输入文件有两行，包含两个正整数，分别代表正整数a和所要保留的小数位数( 500) 输出文件内容为所求的小数部分，只打印小数部分，小数部分不输出尾部的0,2005-01-02,尹宝林：C语言程序设计,24,求倒数（续）,考核要点 高精度除法 字符串的处理 可能的方法 除法的基本算法 多种实现方法 除、减,short resMAX_LEN; void gen_res(int a, int prec) int i, count, remain

11、= 1; for (count = 0, count prec, count+) remain *= 10; rescount = remain / a; remain -= rescount * a; if(remain = 0) /余数为0，结束运算 break; ,2005-01-02,尹宝林：C语言程序设计,26,球的排放 - ball,在一条直线上有N个连续的位置,每个位置可以放一个球,或者为空,但是不能有M个球连续放在一起,对于给定的M,N,求出球可以放置的方案总数 输入文件只有一行,包含2个正整数N,M 1 N = 50 , 2 = M =5,2005-01-02,尹宝林：C语言

12、程序设计,27,球的排放（续）,考核要点 基本编程 递归 注意要点 基本边界条件 递归调用和计算,2005-01-02,尹宝林：C语言程序设计,28,球的排放（续）,基本边界条件 N M,2005-01-02,尹宝林：C语言程序设计,29,球的排放（续）,递归调用和计算 设有N个位置,不能有M个球连续放在一起的排列数量为:pos_num(N, M) 当有N+1个位置时，可能的排列数： 2 * pos_num(N, M) pos_num(N M, M) (N, M) (N + 1, M) (N + 1, M),int pos_num(int m, int n) if( m n) return (

13、int) pow(2, n); else if(m = n) return (int) pow(2, n) - 1; else return (int)( 2 * pos_num(n - 1) pos_num(n m - 1); ,2005-01-02,尹宝林：C语言程序设计,31,字符串排序 - sortstr,从标准输入中读取字符串，将字符串排序以后输出到标准输出。 每个字符串的长度不超过4000 字符串数量小于10万 整体的输入数据量小于10M 按ASCII码从小到大排序,2005-01-02,尹宝林：C语言程序设计,32,字符串排序（续）,考核要点 动态内存分配 指针数组 注意要点 不

14、宜静态分配存储空间 4 * 103 * 105 = 400M 总数据小于10M 直接对数据排序效率低，实现复杂,char *rowsROW_NUM; / 使用固定大小的指针数组 int index; int mycmp(const char *s1, const char *s2) return strcmp(*s1, *s2); void sortstr(FILE *fp) char bufMAX_LEN; int i, n; for (index = 0; fgets(buf, MAX_LEN - 1, fp) != NULL; index+) n = strlen(buf); rowsi

15、ndex = malloc(n + 1); strcpy(rowsindex, buf); qsort(rows, index, sizeof(char *), mycmp); for (i = 0; i index; i+) fputs(rowsi, stdout); free(rowsi); ,char *rows;/ 动态分配指针数组 int row_num = ROW_INC; void sortstr(FILE *fp) char bufMAX_LEN; int i, n; rows = malloc(sizeof(char *) * row_num); for (index = 0

16、; fgets(buf, MAX_LEN - 1, fp) != NULL; index+) if (row_num = index) / 扩展指针数组的大小 row_num += ROW_INC; rows = realloc(rows, sizeof(char *) * row_num); n = strlen(buf); rowsindex = malloc(n + 1); strcpy(rowsindex, buf); qsort(rows, index, sizeof(char *), mycmp); for (i = 0; i index; i+) fputs(rowsi, std

17、out); free(rowsi); ,2005-01-02,尹宝林：C语言程序设计,35,后缀表达式求值 - express,给出包含变量的后缀表达式以及变量的赋值表，求表达式的值。 输入文件的第一行是一个后缀表达式。运算对象是数值或变量，允许的操作符包括四则运算符+、*、/和三角函数sin和cos。 输入文件的后N行为N个不同的变量赋值表，每个赋值表的形式为:。 例： abda sin bfd cos * cccc + abda:90 bfd:60 cccc:1 abda:30 bfd:60 cccc:1.5,2005-01-02,尹宝林：C语言程序设计,36,后缀表达式求值（续）,考核要

18、点 栈的表示和操作 字符串的处理 数据的读入和分析 程序结构 读入表达式 分析赋值表 表达式的分析和栈式计算,#define push(v) stacksp+ = v #define pop()stack-sp typedef struct char nameMAX_LEN; double val; var_t; double stackMAX_STACK; char expressionBUFSIZ; var_t varsMAX_VARS; int var_num, sp; char *get_item(char *p, char *buf) while (*p != 0 ,void eva

19、l_expr(char *s) char bufBUFSIZ, *p = s, *q; var_num = sp = 0; while (*p != 0) / 变量赋值表的分析和处理 p = get_item(p, buf); if (strlen(buf) 3) break; q = strchr(buf, :); *q = 0; strcpy(varsvar_, buf); sscanf(q + 1, %lf, / 表达式的处理 ,void calculate(char *s) char bufBUFSIZ, *p = s; double u, v; while (*p !

20、= 0) p = get_item(p, buf); if (strlen(buf) 1) break; if (sscanf(buf, “%lf”, ,v = pop(); u = pop(); switch (buf0) case +: push(u + v); break; case -: push(u - v); break; case *: push(u * v); break; case /: if (fabs(v) ESP) fprintf(stderr, “Error: Divided by 0!n); exit(1); push(u / v); break; default:

21、 fprintf(stderr, “Error: Unknown word!n); exit(2); output(stack0); ,int is_var(char *s, double *v) int i; for (i = 0; i var_num; i+) if (strcmp(s, ) = 0) *v = varsi.val; return 1; return 0; ,2005-01-02,尹宝林：C语言程序设计,42,词频统计 - frequency,统计正文文件中指定英文单词出现的次数的和。 仅首字母大写的词应与首字母非大写的词视为同一个词,其余大小写不一致的

22、词应视为不同的词。名词复数、第三人称单数等单词变形应视为不同于单词原形的词。单词内的符号连字符“-”、缩写符“”不计入标点符号之列，单词后的缩写符“.”如U.S.中的两个后缩写符，则计入标点符号之列。 输入文件分为两部分。第一部分是一个由英文单词、数字和标点、以及空格符和换行符组成的正文串，由连续3个换行符结束。第二部分包含若干行，每行的形式如下： + 每行中单词的个数小于等于100，单词与之间由0个或多个空格符分隔。特殊单词_PUNCT_表示正文中所有标点符号。,2005-01-02,尹宝林：C语言程序设计,43,词频统计（续）,考核要点 数据结构和指针 排序 字符串的处理 可能的数据结构

23、二叉树 结构数组,2005-01-02,尹宝林：C语言程序设计,44,词频统计（续）,可能的算法 生成每个词的出现次数表 根据要求累加 文件顺序扫描 根据要求生成指定词的出现次数表 缓存待处理的正文 或 首先扫描指定词，然后再读入正文,2005-01-02,尹宝林：C语言程序设计,45,生成每个词的出现次数表,线性表的检索和插入 效率和实现的复杂度 二叉树的检索和插入 实现的复杂度 线性表的插入、排序和压缩 线性表的插入、排序+结构(指针)数组 实现较简单,typedef struct char *w; int num; word_info_t; char word_listMAX_WORDS

24、MAX_LEN; int word_num, word_count, punct_count; word_info_t word_infoMAX_WORDS; void freq(FILE *fp) char sBUFSIZ; word_num = word_count = punct_count = 0; gen_wordinfo(fp); while (fgets(s, BUFSIZ - 1, fp) != NULL) if (s0 = n | s0 = r) continue; deal_text(s); ,int mycmp(const void *key, const void *elem) ret