数据结构适用教程ch08课件.ppt

1、123注释是很重要的帮助理解算法的手段，注释是很重要的帮助理解算法的手段，但不必要为每句语句都加上注解。但不必要为每句语句都加上注解。当阅读算法时遇到不明之处时，当阅读算法时遇到不明之处时，切中要切中要害的注解害的注解能大大减少理解算法的时间，能大大减少理解算法的时间，同时也利于程序的排错同时也利于程序的排错。43.3.输入和输出输入和输出 54.4.语句选用的算法结构语句选用的算法结构算法结构不应该过份追求算法的新奇和算法结构不应该过份追求算法的新奇和花哨，花哨，,简明清晰的程序结构和可靠的程简明清晰的程序结构和可靠的程序功能序功能是我们需要的目标。是我们需要的目标。要要避免大段代码避免大段

2、代码（远大于一页）的直接（远大于一页）的直接出现，一般将一页左右的代码分成一个出现，一般将一页左右的代码分成一个模块（函数），控制模块规模，并用函模块（函数），控制模块规模，并用函数原型来说明算法的行为。数原型来说明算法的行为。65.5.基本运算基本运算在算法设计过程中，会发现教材上有很在算法设计过程中，会发现教材上有很多现成的算法可以使用，但我们在学习多现成的算法可以使用，但我们在学习过程中希望读者不要直接利用这些现成过程中希望读者不要直接利用这些现成的产品。如果算法工作量很大，非用不的产品。如果算法工作量很大，非用不可，那必须将所有基本运算写成具体函可，那必须将所有基本运算写成具体函数过程

3、加以实现。数过程加以实现。7(1)1)建议用建议用图图说明算法。说明算法。(2)(2)建议在算法书写完毕后，用建议在算法书写完毕后，用边界条件边界条件的输入参数值的输入参数值验证一下算法能否正确执验证一下算法能否正确执行。行。(3)(3)编写代码时，养成编写代码时，养成良好的编码习惯良好的编码习惯。8“匈牙利记法匈牙利记法”的变量名的变量名在这种记法中，变量具有一个描述性名在这种记法中，变量具有一个描述性名字，如字，如CountCount、UserNameUserName，并以大写字母，并以大写字母开始。如果变量由多个单词组成，则每开始。如果变量由多个单词组成，则每个单词词头需大写，个单词词头

4、需大写，在描述性名称前，在描述性名称前，需加上表示变量类型的字母需加上表示变量类型的字母 .9表8-1-1变量的匈牙利记法101.1.问题分析与系统结构设计问题分析与系统结构设计 软件工程的理论表明，解决一个问题的软件工程的理论表明，解决一个问题的核心在核心在于了解问题本身于了解问题本身 设计算法前，首先弄清要求设计算法前，首先弄清要求做什么做什么而不是怎么而不是怎么做做 第二步是按照以数据结构为中心的原则划分模第二步是按照以数据结构为中心的原则划分模块，先定义所需要的数据结构，然后定义在它块，先定义所需要的数据结构，然后定义在它上面能进行的操作。上面能进行的操作。最后最后再进行具体编码。再进

5、行具体编码。112 2 详细设计和编码详细设计和编码写出程序的框架，用伪码和接口描述算写出程序的框架，用伪码和接口描述算法，对需求分析做进一步细化。法，对需求分析做进一步细化。通过较通过较高层次的设计能使流程清晰，而不陷入高层次的设计能使流程清晰，而不陷入具体算法之中。具体算法之中。详细设计和编码是对详详细设计和编码是对详细设计结果的进一步求精。细设计结果的进一步求精。最后用某种高级语言，比如最后用某种高级语言，比如C C语言或者语言或者C+C+语言表达出来。语言表达出来。123.3.上机准备和静态检查上机准备和静态检查(以以C C语言为例语言为例)掌握掌握C C语言的基本语法语言的基本语法

6、掌握掌握C C语言的调试方法语言的调试方法 上机准备的重点应该放在上机准备的重点应该放在程序的语义方程序的语义方面面 13 静态检查，主要有两种途径，静态检查，主要有两种途径，一是用一一是用一组测试数据手工执行程序组测试数据手工执行程序(或分模块进或分模块进行行)；二是通过阅读或给别人讲解自己的；二是通过阅读或给别人讲解自己的程序来全面理解程序逻辑，程序来全面理解程序逻辑，动态检查，即调试程序。一般要在静态动态检查，即调试程序。一般要在静态检查无误后，才检查无误后，才上机调试上机调试。14错误是关联的，错误是关联的，一个错误会引起其它多一个错误会引起其它多个错误。个错误。所以当改正一个错误点时

7、，可所以当改正一个错误点时，可能消除多个编译错误。当某个错误看来能消除多个编译错误。当某个错误看来无法改正的时候，可以先试着改正下一无法改正的时候，可以先试着改正下一个错。个错。上机调试时最好上机调试时最好分块进行分块进行，自底向上，自底向上，即先调试低层函数。必要时可以另写一即先调试低层函数。必要时可以另写一个调用驱动程序。个调用驱动程序。154 4 整理实习报告的内容整理实习报告的内容(1)(1)需求和规格说明需求和规格说明 (2)(2)设计：设计：(3)(3)调试报告调试报告 (4)(4)附录附录 166.6.实验报告的要求实验报告的要求(1)(1)各种文档资料要在程序开发过程中逐各种文

8、档资料要在程序开发过程中逐渐形成，而渐形成，而不能最后再写不能最后再写(但可以最后誊但可以最后誊清清)。(2)(2)各种文档资料要用公文纸或稿纸书写，各种文档资料要用公文纸或稿纸书写，也可以打印，不得写在程序清单上。也可以打印，不得写在程序清单上。178.2 8.2 实习报告范例实习报告范例 求出一个不带变量的表达式的值。求出一个不带变量的表达式的值。问题描述问题描述 用一个算法，将一个合法的表达式，如用一个算法，将一个合法的表达式，如1010*3-3-(4+5)/12(4+5)/12转化成计算机能执行的命令或者直接转化成计算机能执行的命令或者直接计算出结果。本次设计的算法是递归下降语法计算出

9、结果。本次设计的算法是递归下降语法分析程序，还有对复杂数值表达式求值所必须分析程序，还有对复杂数值表达式求值所必须的全部支持函数。主要任务是：输入一个串，的全部支持函数。主要任务是：输入一个串，判断它是否合法，并将其结果算出。判断它是否合法，并将其结果算出。188.2 8.2 实习报告范例实习报告范例 基本要求基本要求 根据输入的字符串，判断其是否是合法根据输入的字符串，判断其是否是合法的表达式。如果不是，给出出错信息。的表达式。如果不是，给出出错信息。否则计算表达式结果并显示在屏幕上。否则计算表达式结果并显示在屏幕上。算法要求体现算符优先级，比如先乘除算法要求体现算符优先级，比如先乘除后加减

10、，先次方再乘除，括号提升优先后加减，先次方再乘除，括号提升优先级等级等 198.2 8.2 实习报告范例实习报告范例1 1 需求和规格说明需求和规格说明 虽然表达式可由所有类型的字符串构成，但虽然表达式可由所有类型的字符串构成，但是这里只研究一种类型：即数值型表达式。假是这里只研究一种类型：即数值型表达式。假定数值型表达式可由下列元素组成：定数值型表达式可由下列元素组成：数字数字运算符运算符+、-、*、/、%括号括号其中其中“”表示指数，表示指数，“%”%”表示求余数。所有表示求余数。所有这些项都遵守代数规则。每个运算符优先级见这些项都遵守代数规则。每个运算符优先级见书本书本.208.2 8.

11、2 实习报告范例实习报告范例2 2 设计设计（1 1）设计思想）设计思想 1 1 分解表达式。分解表达式。在设计对表达式求值的语法分析程序之在设计对表达式求值的语法分析程序之前，先要得到表达式的每一部份，前，先要得到表达式的每一部份，表达式里的每个合乎语法的部份叫一个表达式里的每个合乎语法的部份叫一个tokentoken。所以返回下一个表达式中元素的。所以返回下一个表达式中元素的函数称为函数称为get_tokenget_token。218.2 8.2 实习报告范例实习报告范例2 2 表达式语法分析表达式语法分析表达式的求值有多种方法，比如算符优先文法。表达式的求值有多种方法，比如算符优先文法。

12、本例中，将表达式认为是作用于自身的递归的本例中，将表达式认为是作用于自身的递归的数据结构。例如假使表达式中算符只有数据结构。例如假使表达式中算符只有 +、-、*、/和括号，则它可以用以下规则定义：和括号，则它可以用以下规则定义：表达式表达式 -项项+项项-项项 项项 -因子因子*因子因子/因子因子 因子因子 -变量，数，或者变量，数，或者(表达式表达式)228.2 8.2 实习报告范例实习报告范例（2 2）设计表示法）设计表示法1 1本程序采用了多个函数。其中相继调用本程序采用了多个函数。其中相继调用get_expget_exp，level2,level3,level4,level5,leve

13、l6 level2,level3,level4,level5,level6 处理处理不同优先级的运算，优先级低的不同优先级的运算，优先级低的 +和和-算符放算符放在较高层的在较高层的level2level2中，中，*和和/放在放在level3level3中，这中，这样，调用的时候先由样，调用的时候先由level2level2调用调用level3level3，level3level3先执行放在其函数体内的先执行放在其函数体内的 *、/处理程处理程序，等处理完成，再返回序，等处理完成，再返回level2level2处理加减，这处理加减，这样算符的优先级就得以体现。样算符的优先级就得以体现。238.

14、2 8.2 实习报告范例实习报告范例2 2 接口函数功能和说明接口函数功能和说明(略略)3 3 调试报告调试报告在调试中要特别注意在分析过程中在调试中要特别注意在分析过程中各个函数的各个函数的调用顺序和调用方法，因为这个顺序隐含了优调用顺序和调用方法，因为这个顺序隐含了优先级。先级。还要注意参数在传递过程中的变化。比还要注意参数在传递过程中的变化。比如参数如参数resultresult一级一级返回并被计算的过程。一级一级返回并被计算的过程。调试遇到的语法问题可能有：调试遇到的语法问题可能有：漏了分号漏了分号关关键字拼写错误键字拼写错误函数参数类型不匹配函数参数类型不匹配花括号花括号不匹配等。具

15、体调试过程因人而异。不匹配等。具体调试过程因人而异。程序代码略程序代码略,见书本见书本.248.3 8.3 加密算法实例加密算法实例在实现算法之前有两个术语应当熟悉：在实现算法之前有两个术语应当熟悉：明文明文(plaintext)(plaintext)和密文和密文(cipherext)(cipherext)。明文是能读懂的文本；密文是编了码的明文是能读懂的文本；密文是编了码的文本形式。文本形式。本节算法用来加密和解密文本文件。程本节算法用来加密和解密文本文件。程序有序有code()code()和和decode()decode()两个函数两个函数：函：函数数decode()decode()用于解

16、码，是生成密文的用于解码，是生成密文的code()code()函数的反过程。函数的反过程。258.3 8.3 加密算法实例加密算法实例天书是一条缠绕在一个园柱体上的布条，信息天书是一条缠绕在一个园柱体上的布条，信息纵向地写在布条上。纵向地写在布条上。解码的过程是将布条解开传送给信息的接收者，解码的过程是将布条解开传送给信息的接收者，接收者有一个同样大小的园柱体就可以读懂密接收者有一个同样大小的园柱体就可以读懂密码。码。从理论上讲，没有这个园柱体就不可能读懂布从理论上讲，没有这个园柱体就不可能读懂布条，因为字母顺序已经打乱。实际上这个方法条，因为字母顺序已经打乱。实际上这个方法还有些漏洞，因为可

17、以用许多不同大小的园柱还有些漏洞，因为可以用许多不同大小的园柱体去尝试，直到尝试成功。体去尝试，直到尝试成功。268.3 8.3 加密算法实例加密算法实例将信息以一种方式存入数组，以另一种将信息以一种方式存入数组，以另一种不同的方式读出，可以建立一个计算机不同的方式读出，可以建立一个计算机化的化的“天书天书”。例如，以下联合。例如，以下联合union message union message char s100;char s100;char s2 20 5;char s2 20 5;skytale;skytale;278.3 8.3 加密算法实例加密算法实例如果你把信息如果你把信息meet

18、me at sunsetmeet me at sunset存入数组存入数组skytale.sskytale.s，但将它看作一个二，但将它看作一个二维数组维数组skytale.s2skytale.s2，其形式将如下。，其形式将如下。28298.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数组可作为一个字数组可作为一个字符串显示。天书密码程序使用这种方法加密和符串显示。天书密码程序使用这种方法加密和解密信息。解密信息。具体代码从略具体代码从略