《数据结构适用教程ch08课件》由会员分享，可在线阅读，更多相关《数据结构适用教程ch08课件（29页珍藏版）》请在金锄头文库上搜索。
1、第第8 8章章 课程实习指导课程实习指导算法书写规范算法书写规范实习步骤规范实习步骤规范实习报告范例实习报告范例加密算法实例加密算法实例18.1.1 8.1.1 算法书写规范算法书写规范1 1 算法说明算法说明 算法说明以注释的形式写在程序首部，说明算法说明以注释的形式写在程序首部，说明算法的功能，说明各参数的含义和使用的方算法的功能，说明各参数的含义和使用的方法，说明使用一个函数需要的入口参数，还法，说明使用一个函数需要的入口参数，还有函数调用后返回的出口参数。有函数调用后返回的出口参数。 很多人都依赖算法说明和注解。不好的算法很多人都依赖算法说明和注解。不好的算法说明不仅不利于他人理解，还
2、可能引起说明不仅不利于他人理解，还可能引起误导误导。22.2.注释与断言注释与断言 注释是很重要的帮助理解算法的手段，注释是很重要的帮助理解算法的手段，但不必要为每句语句都加上注解。但不必要为每句语句都加上注解。 当阅读算法时遇到不明之处时，当阅读算法时遇到不明之处时，切中要切中要害的注解害的注解能大大减少理解算法的时间，能大大减少理解算法的时间，同时也利于程序的排错同时也利于程序的排错。 算法书写规范算法书写规范3算法书写规范算法书写规范3.3.输入和输出输入和输出 算法的输入和输出可以通过几种途径实算法的输入和输出可以通过几种途径实现。一般最多的是通过现。一般最多的是通过函数的参数表函数的
3、参数表进进行传递，行传递， 一种不太好的方法是用一种不太好的方法是用全局变量或者用全局变量或者用公共的存储区交换数据公共的存储区交换数据。这种共享式的。这种共享式的交换容易引起岐义和不可控制性，应该交换容易引起岐义和不可控制性，应该尽量少用。尽量少用。 4算法书写规范算法书写规范4.4.语句选用的算法结构语句选用的算法结构算法结构不应该过份追求算法的新奇和算法结构不应该过份追求算法的新奇和花哨，花哨，, ,简明清晰的程序结构和可靠的程简明清晰的程序结构和可靠的程序功能序功能是我们需要的目标。是我们需要的目标。要要避免大段代码避免大段代码（远大于一页）的直接（远大于一页）的直接出现，一般将一页左
4、右的代码分成一个出现，一般将一页左右的代码分成一个模块（函数），控制模块规模，并用函模块（函数），控制模块规模，并用函数原型来说明算法的行为。数原型来说明算法的行为。 5算法书写规范算法书写规范5.5.基本运算基本运算在算法设计过程中，会发现教材上有很在算法设计过程中，会发现教材上有很多现成的算法可以使用，但我们在学习多现成的算法可以使用，但我们在学习过程中希望读者不要直接利用这些现成过程中希望读者不要直接利用这些现成的产品。如果算法工作量很大，非用不的产品。如果算法工作量很大，非用不可，那必须将所有基本运算写成具体函可，那必须将所有基本运算写成具体函数过程加以实现。数过程加以实现。 6算法书
5、写规范算法书写规范(1)1)建议用建议用图图说明算法。说明算法。(2)(2)建议在算法书写完毕后，用建议在算法书写完毕后，用边界条件边界条件的输入参数值的输入参数值验证一下算法能否正确执验证一下算法能否正确执行。行。 (3)(3)编写代码时，养成编写代码时，养成良好的编码习惯良好的编码习惯。 7算法书写规范算法书写规范“匈牙利记法匈牙利记法”的变量名的变量名在这种记法中，变量具有一个描述性名在这种记法中，变量具有一个描述性名字，如字，如CountCount、UserNameUserName，并以大写字母并以大写字母开始。如果变量由多个单词组成，则每开始。如果变量由多个单词组成，则每个单词词头需
6、大写，个单词词头需大写，在描述性名称前，在描述性名称前，需加上表示变量类型的字母需加上表示变量类型的字母 . .8前缀前缀前缀前缀变量类型变量类型变量类型变量类型注释注释注释注释A A A AArrayArrayArrayArray数组数组数组数组B B B BBooleanBooleanBooleanBoolean布尔布尔布尔布尔D D D DDoubleDoubleDoubleDouble双精度双精度双精度双精度H H H HHandleHandleHandleHandle句柄（句柄（句柄（句柄（windowswindowswindowswindows用）用）用）用）I I I IInte
7、gerIntegerIntegerInteger整数整数整数整数L L L LLongLongLongLong长型长型长型长型LpfnLpfnLpfnLpfnLong pointer to functionLong pointer to functionLong pointer to functionLong pointer to function指向函数的长指针指向函数的长指针指向函数的长指针指向函数的长指针m_m_m_m_Member variableMember variableMember variableMember variable成员变量成员变量成员变量成员变量N N N NIn
8、tegerIntegerIntegerInteger整数整数整数整数P P P PPointer to Pointer to Pointer to Pointer to 指针指针指针指针S S S SStringStringStringString串串串串SzSzSzSzZero terminnated stringZero terminnated stringZero terminnated stringZero terminnated string以以以以零零零零0000结结结结尾尾尾尾的的的的串串串串U U U UUnsigned integerUnsigned integerUnsig
9、ned integerUnsigned integer无符号整数无符号整数无符号整数无符号整数表8-1-1变量的匈牙利记法9 8.1.2 8.1.2实习步骤规范实习步骤规范 1.1.问题分析与系统结构设计问题分析与系统结构设计 软件工程的理论表明，解决一个问题的软件工程的理论表明，解决一个问题的核心在核心在于了解问题本身于了解问题本身 设计算法前，首先弄清要求设计算法前，首先弄清要求做什么做什么而不是怎么而不是怎么做做 第二步是按照以数据结构为中心的原则划分模第二步是按照以数据结构为中心的原则划分模块，先定义所需要的数据结构，然后定义在它块，先定义所需要的数据结构，然后定义在它上面能进行的操作
10、。上面能进行的操作。最后最后再进行具体编码。再进行具体编码。 10 8.1.2 8.1.2实习步骤规范实习步骤规范 2 2 详细设计和编码详细设计和编码写出程序的框架，用伪码和接口描述算写出程序的框架，用伪码和接口描述算法，对需求分析做进一步细化。法，对需求分析做进一步细化。通过较通过较高层次的设计能使流程清晰，而不陷入高层次的设计能使流程清晰，而不陷入具体算法之中。具体算法之中。详细设计和编码是对详详细设计和编码是对详细设计结果的进一步求精。细设计结果的进一步求精。最后用某种高级语言，比如最后用某种高级语言，比如C C语言或者语言或者C+C+语言表达出来。语言表达出来。 118.1.28.1
11、.2实习步骤规范实习步骤规范 3.3.上机准备和静态检查上机准备和静态检查( (以以C C语言为例语言为例) )掌握掌握C C语言的基本语法语言的基本语法 掌握掌握C C语言的调试方法语言的调试方法 上机准备的重点应该放在上机准备的重点应该放在程序的语义方程序的语义方面面 128.1.28.1.2实习步骤规范实习步骤规范 静态检查，主要有两种途径，静态检查，主要有两种途径，一是用一一是用一组测试数据手工执行程序组测试数据手工执行程序( (或分模块进行或分模块进行) )；二是通过阅读或给别人讲解自己的程；二是通过阅读或给别人讲解自己的程序来全面理解程序逻辑，序来全面理解程序逻辑，动态检查，即调试
12、程序。一般要在静态动态检查，即调试程序。一般要在静态检查无误后，才检查无误后，才上机调试上机调试。138.1.28.1.2实习步骤规范实习步骤规范 错误是关联的，错误是关联的，一个错误会引起其它多一个错误会引起其它多个错误。个错误。所以当改正一个错误点时，可所以当改正一个错误点时，可能消除多个编译错误。当某个错误看来能消除多个编译错误。当某个错误看来无法改正的时候，可以先试着改正下一无法改正的时候，可以先试着改正下一个错。个错。 上机调试时最好上机调试时最好分块进行分块进行，自底向上，自底向上，即先调试低层函数。必要时可以另写一即先调试低层函数。必要时可以另写一个调用驱动程序。个调用驱动程序。
13、 148.1.28.1.2实习步骤规范实习步骤规范 4 4 整理实习报告的内容整理实习报告的内容(1)(1)需求和规格说明需求和规格说明 (2)(2)设计：设计：(3)(3)调试报告调试报告 (4)(4)附录附录 158.1.28.1.2实习步骤规范实习步骤规范 6.6.实验报告的要求实验报告的要求(1)(1)各种文档资料要在程序开发过程中逐各种文档资料要在程序开发过程中逐渐形成，而渐形成，而不能最后再写不能最后再写( (但可以最后誊但可以最后誊清清) )。(2)(2)各种文档资料要用公文纸或稿纸书写，各种文档资料要用公文纸或稿纸书写，也可以打印，不得写在程序清单上。也可以打印，不得写在程序清
14、单上。 168.2 8.2 实习报告范例实习报告范例 求出一个不带变量的表达式的值。求出一个不带变量的表达式的值。 问题描述问题描述 用用一一个个算算法法，将将一一个个合合法法的的表表达达式式，如如10*3-10*3-(4+5)/12(4+5)/12转转化化成成计计算算机机能能执执行行的的命命令令或或者者直直接接计计算算出出结结果果。本本次次设设计计的的算算法法是是递递归归下下降降语语法法分分析析程程序序，还还有有对对复复杂杂数数值值表表达达式式求求值值所所必必须须的的全全部部支支持持函函数数。主主要要任任务务是是：输输入入一一个个串串，判断它是否合法，并将其结果算出。判断它是否合法，并将其结
15、果算出。178.2 8.2 实习报告范例实习报告范例 基本要求基本要求 根据输入的字符串，判断其是否是合法根据输入的字符串，判断其是否是合法的表达式。如果不是，给出出错信息。的表达式。如果不是，给出出错信息。否则计算表达式结果并显示在屏幕上。否则计算表达式结果并显示在屏幕上。算法要求体现算符优先级，比如先乘除算法要求体现算符优先级，比如先乘除后加减，先次方再乘除，括号提升优先后加减，先次方再乘除，括号提升优先级等级等 188.2 8.2 实习报告范例实习报告范例1 1 需求和规格说明需求和规格说明虽虽然然表表达达式式可可由由所所有有类类型型的的字字符符串串构构成成，但但是是这这里里只只研研究究
16、一一种种类类型型：即即数数值值型型表表达达式式。假假定定数值型表达式可由下列元素组成：数值型表达式可由下列元素组成：数字数字运算符运算符+ +、 - -、 * *、 / /、 、 % % 括号括号其其中中“”“”表表示示指指数数，“%”“%”表表示示求求余余数数。所所有有这这些些项项都都遵遵守守代代数数规规则则。每每个个运运算算符符优优先先级级见见书本书本. .198.2 8.2 实习报告范例实习报告范例2 2 设计设计（1 1）设计思想）设计思想 1 1 分解表达式。分解表达式。在设计对表达式求值的语法分析程序之在设计对表达式求值的语法分析程序之前，先要得到表达式的每一部份，前，先要得到表达
17、式的每一部份， 表达式里的每个合乎语法的部份叫一个表达式里的每个合乎语法的部份叫一个tokentoken。所以返回下一个表达式中元素的所以返回下一个表达式中元素的函数称为函数称为get_tokenget_token。 208.2 8.2 实习报告范例实习报告范例2 2 表达式语法分析表达式语法分析表表达达式式的的求求值值有有多多种种方方法法，比比如如算算符符优优先先文文法法。本本例例中中，将将表表达达式式认认为为是是作作用用于于自自身身的的递递归归的的数数据据结结构构。例例如如假假使使表表达达式式中中算算符符只只有有 + +、 - -、 * *、 / /和括号，则它可以用以下规则定义：和括号，
18、则它可以用以下规则定义：表达式表达式 - - 项项+项项 - -项项 项项 - - 因子因子*因子因子 / /因子因子 因子因子 - - 变量，数，或者变量，数，或者( (表达式表达式) )218.2 8.2 实习报告范例实习报告范例（2 2）设计表示法设计表示法1 1本本程程序序采采用用了了多多个个函函数数。其其中中相相继继调调用用get_expget_exp，level2,level3,level4,level5,level6 level2,level3,level4,level5,level6 处处 理理不不同同优优先先级级的的运运算算，优优先先级级低低的的 + +和和- -算算符符放放
19、在在较较高高层层的的level2level2中中，* *和和/ /放放在在level3level3中中，这这样样，调调用用的的时时候候先先由由level2level2调调用用level3level3，level3level3先先执执行行放放在在其其函函数数体体内内的的 * *、/ /处处理理程程序序，等等处处理理完完成成，再再返返回回level2level2处处理理加加减减，这这样算符的优先级就得以体现。样算符的优先级就得以体现。228.2 8.2 实习报告范例实习报告范例2 2 接口函数功能和说明接口函数功能和说明( (略略) )3 3 调试报告调试报告在调试中要特别注意在分析过程中在调试中
20、要特别注意在分析过程中各个函数的各个函数的调用顺序和调用方法，因为这个顺序隐含了优调用顺序和调用方法，因为这个顺序隐含了优先级。先级。还要注意参数在传递过程中的变化。比还要注意参数在传递过程中的变化。比如参数如参数resultresult一级一级返回并被计算的过程。一级一级返回并被计算的过程。调试遇到的语法问题可能有：调试遇到的语法问题可能有：漏了分号漏了分号关关键字拼写错误键字拼写错误函数参数类型不匹配函数参数类型不匹配花括号花括号不匹配等。具体调试过程因人而异。不匹配等。具体调试过程因人而异。程序代码略程序代码略, ,见书本见书本. . 238.3 8.3 加密算法实例加密算法实例在在实实
21、现现算算法法之之前前有有两两个个术术语语应应当当熟熟悉悉：明明文文( (plaintext)plaintext)和和密密文文( (cipherext)cipherext)。明明文文是是能能读读懂懂的的文文本本；密密文文是是编编了了码码的的文本形式。文本形式。本本节节算算法法用用来来加加密密和和解解密密文文本本文文件件。程程序序有有code( code( ) )和和decode( decode( ) )两两个个函函数数：函函数数decode( decode( ) )用用于于解解码码，是是生生成成密密文文的的codecode( )( )函数的反过程。函数的反过程。248.3 8.3 加密算法实例加
22、密算法实例天天书书是是一一条条缠缠绕绕在在一一个个园园柱柱体体上上的的布布条条，信信息息纵向地写在布条上。纵向地写在布条上。解解码码的的过过程程是是将将布布条条解解开开传传送送给给信信息息的的接接收收者者，接接收收者者有有一一个个同同样样大大小小的的园园柱柱体体就就可可以以读读懂懂密密码。码。从从理理论论上上讲讲，没没有有这这个个园园柱柱体体就就不不可可能能读读懂懂布布条条，因因为为字字母母顺顺序序已已经经打打乱乱。实实际际上上这这个个方方法法还还有有些些漏漏洞洞，因因为为可可以以用用许许多多不不同同大大小小的的园园柱柱体去尝试，直到尝试成功。体去尝试，直到尝试成功。258.3 8.3 加密算
23、法实例加密算法实例将将信信息息以以一一种种方方式式存存入入数数组组，以以另另一一种种不不同同的的方方式式读读出出，可可以以建建立立一一个个计计算算机机化的化的“天书天书”。例如，以下联合。例如，以下联合union message union message char s100; char s100; char s2 20 5; char s2 20 5; skytale; skytale;268.3 8.3 加密算法实例加密算法实例如果你把信息如果你把信息meet me at sunsetmeet me at sunset存存入入数数组组skytale.sskytale.s，但但将将它它看看作
24、作一一个个二二维数组维数组skytale.s2skytale.s2，其形式将如下。其形式将如下。27M ME EE Et tM ME Ea at tS SU Un ns sE ET T0 00 00 00 00 00 00 00 0288.3 8.3 加密算法实例加密算法实例如果你按列读出数组如果你按列读出数组，信息就变成，信息就变成 mm.e.eest.e.u.tan.ts.mm.e.eest.e.u.tan.ts.这这里里的的“.”“.”点点号号说说明明了了填填充充的的空空格格。要要解解密密信信息息，按按列列填填入入到到skytale.s2skytale.s2，那那么么数数组组skytale.sskytale.s就就能能按按正正常常次次序序显显示示。由由于于信信息息以以空空00结结束束，skytale.sskytale.s数数组组可可作作为为一一个个字字符符串串显显示示。天天书书密密码码程程序序使使用用这这种种方方法法加加密密和和解密信息。解密信息。具体代码从略具体代码从略29
