编程的技巧与常见问题--READ.ppt

1、数据结构习题课 编程技巧与常见问题关于函数n特殊情况与边界情况n指针n内存管理n代码，从“头”说起n常见错误及解决方法n编程经验n推荐书目n关于作业关于函数n为什么要写函数？q实现一个逻辑意义上的独立功能n清晰、完整、独立q减少重复代码n代码重复3次以上应该写成函数n例子：有理数格式化打印输出n好的函数具有的特性q通用性：可以用于解决不同问题q独立性：不依赖于上下文代码n例子：有理数格式化打印输出（输出函数的两种形式）关于函数n选择合适的参数和返回值q形参与实参n形参：函数在声明或定义时，所写出的参数定义n实参：实际调用时，传给函数的实际参数q传值参数和传址参数（值参与变参）n传值参数：q只将

2、实参的值传入函数，函数中的操作不会影响实参本身n传址参数：q将实参本身地址传入函数，函数中的操作会影响实参关于函数n选择合适的参数和返回值q传值参数和传址参数（值参与变参）npascal:qprocedure proc1(m:integer;var n:integer);nVisual Basicqsub sub1(byval m as integer,n as integer)qdefault:byrefncqvoid func1(int m,int*pn);q调用：func1(m,&n);nc+qvoid func1(int m,int&n);关于函数n选择合适的参数和返回值q向函数内传递

3、的数据n传值参数（或全局变量）q函数传出或改变的数据n返回值、传址参数（或全局变量）n单个数据对象：返回值n多个数据对象：传址参数返回值（状态值等）q尽量不要使用全局变量n逻辑不清楚，容易被其他操作误改变n特殊情况：过程模型的状态变量编程技巧与常见问题n关于函数特殊情况与边界情况n指针n内存管理n代码，从“头”说起n常见错误及解决方法n编程经验n推荐书目n关于作业特殊情况与边界情况n在各种问题中普遍存在q解决问题时需要预见q特殊情况与边界情况的处理n特殊处理n给出提示信息q多做测试n测试数据考虑边界情况和特殊情况n本门课程的作业：不必故意使用错误数据来测试特殊情况与边界情况n常见边界情况q数值

4、n0q做除数时：给出错误信息q多项式的项系数为0：消去q多项式的项指数为0：6x0 6，n1q多项式系数、指数为1：1x1 xn负数q判断大小特殊情况与边界情况n常见边界情况q指针nNULLq做操作前，先判断指针是否等于NULLn第一个q无头节点时，增加或删除第一个节点q（例子：约瑟夫环问题，m=1）n最后一个：q无头节点时，删除最后一个节点q循环链表，删除最后一个节点特殊情况与边界情况n常见边界情况q字符串n字符串结尾，0n空串q文件结尾nfeof(FILE*file)编程技巧与常见问题n关于函数n特殊情况与边界情况指针n内存管理n代码，从“头”说起n常见错误及解决方法n编程经验n推荐书目n

5、关于作业指针n指针本身是一个变量q指针变量的值是一个内存地址q区分：指针变量本身和指针指向的空间nchar*pc;nmalloc与freeqpc=(char*)malloc(sizeof(char);n先分配空间：malloc(sizeof(char)n再把空间地址赋值给pc：pc=(char*)qfree释放的是指针指向的空间pc=(char*)malloc(sizeof(char);free(pc);/pc仍然指向该内存pc=NULL;/杜绝“野指针”0 x0012ff78:pc0 x00430130e0 x00430130指针n分配空间的管理qmalloc分配的空间，系统不管，自己负责v

6、oid test()int*pn=(int*)malloc(sizeof(int);q函数结束后，pn本身作为局部变量被销毁，但为pn分配的空间不会被销毁，成为“无主之地”q在函数结束之前“接管”为pn分配的空间nmake_node函数指针char c,*pc;int*pn;c=a;pc=&c;c=b;*pc=c;pc=(char*)malloc(sizeof(char);*pc=d;free(pc);pn=(int*)malloc(sizeof(int);pc=(char*)malloc(sizeof(char)*2);*pc=e;/pc0=e;*(pc+1)=f;/pc1=f;free(p

7、c);pc=NULL;0 x0012ff7c:c0 x0012ff78:pc0 x00430160a0 x0012ff7cdbec0 x004301600 x00430130f0 x0012ff74:pn0 x004301600 x004301300 x00000000编程技巧与常见问题n关于函数n特殊情况与边界情况n指针内存管理n代码，从“头”说起n常见错误及解决方法n编程经验n推荐书目n关于作业内存管理n内存分配方式q从静态存储区域分配。内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量，static 变量。q在栈上创建。在执行函数时，函数内局部变量的存储单

8、元都可以在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。q从堆上分配，亦称动态内存分配。程序在运行的时候用malloc 或new 申请任意多少的内存，程序员自己负责在何时用free 或delete 释放内存。动态内存的生存期由我们决定使用非常灵活但问题也最多。内存管理n常见的内存错误及其对策q编译器不能自动发现这些错误，通常是在程序运行时才能捕捉到。q内存分配未成功，却使用了它。n指针p 是函数的参数，函数的入口assert(p!=NULL)检查n用malloc 或new 来申请内存，if(p=NULL)或if(p!=N

9、ULL)检查q内存分配虽然成功，但是尚未初始化就引用它。n误以为内存的缺省初值全为零，导致引用初值错误，例如数组。q内存分配成功并且已经初始化，但操作越过了内存的边界。n循环次数搞错导致数组操作越界，数组下标“多1”或“少1”内存管理n常见的内存错误及其对策q忘记了释放内存，造成内存泄露。n每被调用一次就丢失一块内存，刚开始时系统的内存充足你看不到错误，终有一次程序突然死掉，系统出现提示：内存耗尽。n动态内存的申请与释放必须配对，程序中malloc 与free 的使用次数一定要相同。q释放了内存却继续使用它。n函数的return 注意不要返回指向栈内存的指针或者引用，因为该内存在函数体结束时被

10、自动销毁。n使用free 或delete 释放了内存后，没有将指针设置为NULL，导致产生野指针。内存管理nmalloc/free 和new/deleteqmalloc与free 是C+/C 语言的标准库函数，malloc与free 不能执行构造函数与析构函数。qnew与delete 是C+的运算符，它们都可用于申请动态内存和释放内存。new:一个能完成动态内存分配和初始化工作的运算符；delete:一个能完成清理与释放内存工作的运算符。qfree 释放new 创建的动态对象？无法执行析构函数，可能出错。qdelete 释放malloc 申请的动态内存？可读性差。qnew/delete 必须配

11、对使用，malloc/free 也一样。class Objpublic:Obj(void)cout “Initialization”endl;Obj(void)cout “Destroy”endl;void Initialize(void)cout “Initialization”endl;void Destroy(void)cout “Destroy”Initialize();/初始化/a-Destroy();/清除工作free(a);/释放内存void UseNewDelete(void)Obj*a=new Obj;/申请动态内存并且初始化/delete a;/清除并且释放内存内存管理nm

12、alloc/free 的使用要点q函数malloc 的原型如下nvoid*malloc(size_t size);q用malloc 申请一块长度为length 的整数类型的内存程序如下nint*p=(int*)malloc(sizeof(int)*length);qmalloc 返回值的类型是void*，所以在调用malloc 时要显式地进行类型转换，将void*转换成所需要的指针类型。qmalloc 函数本身并不识别要申请的内存是什么类型，它只关心内存的总字节数。q函数free 的原型如下nvoid free(void*memblock);nfree(p)后，p指向垃圾内存区域，如果不设置p

13、=NULL,会让人误以为p是合法的指针，引用它就会出错。n如果p!=NULL,再次运行free(p)会导致程序运行出错。内存管理nnew/delete 的使用要点q比较nint*p1=(int*)malloc(sizeof(int)*length);nint*p2=new intlength;qnew 内置了sizeof、类型转换和类型安全检查功能。对于非内部数据类型的对象而言，new 在创建动态对象的同时完成了初始化工作。qObj*objects=new Obj100;/创建100 个动态对象qdelete objects;/正确的用法qdelete objects;/错误的用法q后者相当于

14、delete objects0，漏掉了另外99 个对象。内存管理n指针消亡了，并不表示它所指的内存会被自动释放。n内存被释放了，并不表示指针会消亡或者成了NULL 指针。n杜绝“野指针”q“野指针”不是NULL 指针，而是指向垃圾内存的指针。q用if语句可以容易的判断NULL指针，但是对“野指针”不起作用，很危险n“野指针”的成因q指针变量没有被初始化。所以要么将指针设置为NULL，要么让它指向合法的内存。q指针p 被free 或者delete 之后没有置为NULL，让人误以为p 是个合法的指针。q指针操作超越了变量的作用范围。如在指针所指向的内存变量的作用范围之外使用该指针访问该内存。编程技

15、巧与常见问题n关于函数n特殊情况与边界情况n指针n内存管理代码，从“头”说起n常见错误及解决方法n编程经验n推荐书目n关于作业代码，从“头”说起关于头文件n从代码到程序q编辑q编译（Compile）ncpp文件obj文件n每个cpp文件单独编译，编译时引入头文件n匹配：函数声明函数调用q连接n把所有的obj文件连接为可执行文件n匹配：函数调用函数实现q运行代码，从“头”说起关于头文件n头文件的作用q公用定义n类型、常量、数据结构等q实现代码文件拆分n文件拆分：增加代码复用性，减少重复编译n函数声明：实现与调用的桥梁q隐藏源代码n可以只给出函数头和二进制代码，不提供源代码n全局变量qextern

16、声明代码关于可读性与健壮性n好的程序风格，减少出错机会q缩进与对齐q顾名思义的标识符命名q符合正常逻辑nd=c-0;好d=c-48;不好nif(coefficient!=0)好if(coefficient)不好q注释与空行q尽量使用引用调用n考虑特殊情况与边界情况q参见编程技巧及常见问题讲稿编程技巧与常见问题n关于函数n特殊情况与边界情况n指针n内存管理n代码，从“头”说起常见错误及解决方法n编程经验n推荐书目n关于作业常见错误及解决方法n编译错误q认真看错误信息n连接错误q没有定义n项目中是否包含了函数实现的文件？q重复定义n引用了cpp文件？q类型不一致n是否包含了正确的头文件？注意#if

17、ndef,#define,#undef的用法q做到：声明、实现、调用三者一致常见错误及解决方法n运行错误与逻辑错误q运行错误（出错退出或死循环）主要看指针q跟踪：由粗到细原则n先确定大概位置（F10，Step Over）n再进入细部（F11，Step Into）nCtrl+F10，Run to Cursor；F9，Breakpointq看variables，自己加watchq看程序运行是否如自己设想n莫名其妙地改变q有没有把=写成=?q仔细查有没有数据越界（编译器不会查）常见错误及解决方法n无法一眼看出的错误qsyntax error:missing before*n类型是否正确定义n前面函数

18、的、是否匹配q already has a bodyn是否引用了cpp文件？qunresolved external symbol n函数声明、调用与实现是否一致，尤其是有类型重定义的时候qunresolved external symbol _WinMain16nproject类型错误，应该是Win32 Console Application编程技巧与常见问题n关于函数n特殊情况与边界情况n指针n内存管理n代码，从“头”说起n常见错误及解决方法编程经验n推荐书目n关于作业编程经验n利用基本功能实现高级功能q例子：多项式计算n已有加法、数值乘法q用其实现减法、乘法n更进一步：q用多项式规范化，

19、实现加法n加入调试代码q输出中间结果n使用断言q使用Assert宏断言进行安全检查，仅在Debug版本起作用的宏，用于检查“不应该”发生的情况，如在使用指针之前调用assert(p!=NULL)n在函数的入口处，使用断言检查参数的有效性n使用断言对函数中的假定进行检查n由简单到复杂编程技巧与常见问题n关于函数n特殊情况与边界情况n指针n内存管理n代码，从“头”说起n常见错误及解决方法n编程经验推荐书目n关于作业推荐书目n高质量C+/C编程指南，林锐q课程主页“补充材料”一栏有下载编程技巧与常见问题n关于函数n特殊情况与边界情况n指针n内存管理n代码，从“头”说起n常见错误及解决方法n编程经验n

20、推荐书目关于作业关于作业n作业请按照要求完成q建立正确的project，能够直接打开运行。q使用作业说明中给出的输入输出文件格式。q减轻助教工作量，谢谢。n作业请独立完成q使用了老师给出的代码，或者其他参考书上的代码，请在readme_me.txt文件中说明。q同学之间讨论请限制在思路和算法级别，不要直接或间接使用别人的代码。关于作业n作业满分分值列表q16题；520分；共195分n作业给分原则q结果的有效性,正确性（黑箱测试，边界值等）q代码的组织，模块化，可读性（注释）q文件组织（头文件的使用等）q文件输入、输出q选做部分可加分(非满分的情况下)q其它作业要求有理数计算n考察要点：ADT的

21、思想n函数q逻辑意义上的独立功能n清晰、完整、独立q减少重复代码n代码重复3次以上应该写成函数n例子：有理数格式化打印输出q通用性：可以用于解决不同问题q独立性：不依赖于上下文代码n例子：有理数格式化打印输出（输出函数的两种形式）约瑟夫环n考察要点：链表的操作（建立、初始化、插入、删除等）是否在功能独立、完善的的函数中实现n链表初始化（动态分配结点，动态添加链表结点）；合理性、正确性n内存管理；结点分配、引用及释放n指针使用，指针参数、返回（程序运行异常通常与指针操作不当有关）n边界情况，删除尾结点后初始化（分配结点、插入）|遍历链表|删除结点（内存释放）多项式计算n考察要点：链表的操作n链表的遍历、比较及改变结点位置（删除及插入），按幂级数排序，合并幂次相同的项（直接连接两个链表，此步可完成“加”）n“加”：遍历结点插入 结点系数更改（系数为零时，删除结点n“减”：“加”上负系数的多项式n“乘”：幂次相加，系数相乘 插入结点（可在此时一并完成合并同类项及排序）魔王语言解释n考察要点：栈和队列的基本操作n需要考虑的规则q有多个括号时q括号中有大写字母时q增加的规则，可变规则数n括号的展开q漏了最后一个q括号展开的顺序反了谢谢大家