数据结构适用教程ch08课件

第8章课程实习指导算法书写规范实习步骤规范实习报告范例加密算法实例1第8章课程实习指导算法书写规范18.1.1算法书写规范1算法说明算法说明以注释的形式写在程序首部，说明算法的功能，说明各参数的含义和使用的方法，说明使用一个函数需要的入口参数，还有函数调用后返回的出口参数。很多人都依赖算法说明和注解。不好的算法说明不仅不利于他人理解，还可能引起误导。28.1.1算法书写规范1算法说明22.注释与断言注释是很重要的帮助理解算法的手段，但不必要为每句语句都加上注解。当阅读算法时遇到不明之处时，切中要害的注解能大大减少理解算法的时间，同时也利于程序的排错。算法书写规范32.注释与断言算法书写规范3算法书写规范3.输入和输出

算法的输入和输出可以通过几种途径实现。一般最多的是通过函数的参数表进行传递，一种不太好的方法是用全局变量或者用公共的存储区交换数据。这种共享式的交换容易引起岐义和不可控制性，应该尽量少用。

4算法书写规范3.输入和输出4算法书写规范4.语句选用的算法结构算法结构不应该过份追求算法的新奇和花哨，,简明清晰的程序结构和可靠的程序功能是我们需要的目标。要避免大段代码（远大于一页）的直接出现，一般将一页左右的代码分成一个模块（函数），控制模块规模，并用函数原型来说明算法的行为。

5算法书写规范4.语句选用的算法结构5算法书写规范5.基本运算在算法设计过程中，会发现教材上有很多现成的算法可以使用，但我们在学习过程中希望读者不要直接利用这些现成的产品。如果算法工作量很大，非用不可，那必须将所有基本运算写成具体函数过程加以实现。

6算法书写规范5.基本运算6算法书写规范(1)建议用图说明算法。(2)建议在算法书写完毕后，用边界条件的输入参数值验证一下算法能否正确执行。(3)编写代码时，养成良好的编码习惯。

7算法书写规范(1)建议用图说明算法。7算法书写规范“匈牙利记法”的变量名在这种记法中，变量具有一个描述性名字，如Count、UserName，并以大写字母开始。如果变量由多个单词组成，则每个单词词头需大写，在描述性名称前，需加上表示变量类型的字母.8算法书写规范“匈牙利记法”的变量名8前缀变量类型注释AArray数组BBoolean布尔DDouble双精度HHandle句柄（windows用）IInteger整数LLong长型LpfnLongpointertofunction指向函数的长指针m_Membervariable成员变量NInteger整数PPointerto指针SString串SzZeroterminnatedstring以零’\0’结尾的串UUnsignedinteger无符号整数表8-1-1变量的匈牙利记法9前缀变量类型注释AArray数组BBoolean布尔DDou8.1.2实习步骤规范1.问题分析与系统结构设计软件工程的理论表明，解决一个问题的核心在于了解问题本身设计算法前，首先弄清要求做什么而不是怎么做第二步是按照以数据结构为中心的原则划分模块，先定义所需要的数据结构，然后定义在它上面能进行的操作。最后再进行具体编码。108.1.2实习步骤规范1.问题分析与系统结构设计108.1.2实习步骤规范2详细设计和编码写出程序的框架，用伪码和接口描述算法，对需求分析做进一步细化。通过较高层次的设计能使流程清晰，而不陷入具体算法之中。详细设计和编码是对详细设计结果的进一步求精。最后用某种高级语言，比如C语言或者C++语言表达出来。118.1.2实习步骤规范2详细设计和编码118.1.2实习步骤规范3.上机准备和静态检查(以C语言为例)掌握C语言的基本语法掌握C语言的调试方法上机准备的重点应该放在程序的语义方面128.1.2实习步骤规范3.上机准备和静态检查(以C语言为例8.1.2实习步骤规范

静态检查，主要有两种途径，一是用一组测试数据手工执行程序(或分模块进行)；二是通过阅读或给别人讲解自己的程序来全面理解程序逻辑，动态检查，即调试程序。一般要在静态检查无误后，才上机调试。138.1.2实习步骤规范

静态检查，主要有两种途径，一是用一8.1.2实习步骤规范错误是关联的，一个错误会引起其它多个错误。所以当改正一个错误点时，可能消除多个编译错误。当某个错误看来无法改正的时候，可以先试着改正下一个错。上机调试时最好分块进行，自底向上，即先调试低层函数。必要时可以另写一个调用驱动程序。148.1.2实习步骤规范错误是关联的，一个错误会引起其它多个8.1.2实习步骤规范4整理实习报告的内容(1)需求和规格说明(2)设计：(3)调试报告(4)附录158.1.2实习步骤规范4整理实习报告的内容158.1.2实习步骤规范6.实验报告的要求(1)各种文档资料要在程序开发过程中逐渐形成，而不能最后再写(但可以最后誊清)。(2)各种文档资料要用公文纸或稿纸书写，也可以打印，不得写在程序清单上。168.1.2实习步骤规范6.实验报告的要求168.2实习报告范例求出一个不带变量的表达式的值。[问题描述]用一个算法，将一个合法的表达式，如10*3-(4+5)/12转化成计算机能执行的命令或者直接计算出结果。本次设计的算法是递归下降语法分析程序，还有对复杂数值表达式求值所必须的全部支持函数。主要任务是：输入一个串，判断它是否合法，并将其结果算出。178.2实习报告范例求出一个不带变量的表达式的值。178.2实习报告范例[基本要求]根据输入的字符串，判断其是否是合法的表达式。如果不是，给出出错信息。否则计算表达式结果并显示在屏幕上。算法要求体现算符优先级，比如先乘除后加减，先次方再乘除，括号提升优先级等188.2实习报告范例[基本要求]188.2实习报告范例1需求和规格说明

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

（1）设计思想1分解表达式。在设计对表达式求值的语法分析程序之前，先要得到表达式的每一部份，表达式里的每个合乎语法的部份叫一个token。所以返回下一个表达式中元素的函数称为get_token。208.2实习报告范例2设计

208.2实习报告范例2表达式语法分析表达式的求值有多种方法，比如算符优先文法。本例中，将表达式认为是作用于自身的递归的数据结构。例如假使表达式中算符只有+、-、*、/和括号，则它可以用以下规则定义：表达式->项[+项][-项]项->因子[*因子][/因子]因子->变量，数，或者(表达式)218.2实习报告范例2表达式语法分析218.2实习报告范例（2）设计表示法1本程序采用了多个函数。其中相继调用get_exp，level2,level3,level4,level5,level6处理不同优先级的运算，优先级低的+和-算符放在较高层的level2中，*和/放在level3中，这样，调用的时候先由level2调用level3，level3先执行放在其函数体内的*、/处理程序，等处理完成，再返回level2处理加减，这样算符的优先级就得以体现。228.2实习报告范例（2）设计表示法228.2实习报告范例2接口函数功能和说明(略)3调试报告在调试中要特别注意在分析过程中各个函数的调用顺序和调用方法，因为这个顺序隐含了优先级。还要注意参数在传递过程中的变化。比如参数result一级一级返回并被计算的过程。调试遇到的语法问题可能有：①漏了分号②关键字拼写错误③函数参数类型不匹配④花括号不匹配等。具体调试过程因人而异。程序代码略,见书本.238.2实习报告范例2接口函数功能和说明(略)238.3加密算法实例在实现算法之前有两个术语应当熟悉：明文(plaintext)和密文(cipherext)。明文是能读懂的文本；密文是编了码的文本形式。本节算法用来加密和解密文本文件。程序有code()和decode()两个函数：函数decode()用于解码，是生成密文的code()函数的反过程。248.3加密算法实例在实现算法之前有两个术语应当熟悉：明文(8.3加密算法实例天书是一条缠绕在一个园柱体上的布条，信息纵向地写在布条上。解码的过程是将布条解开传送给信息的接收者，接收者有一个同样大小的园柱体就可以读懂密码。从理论上讲，没有这个园柱体就不可能读懂布条，因为字母顺序已经打乱。实际上这个方法还有些漏洞，因为可以用许多不同大小的园柱体去尝试，直到尝试成功。258.3加密算法实例天书是一条缠绕在一个园柱体上的布条，信息8.3加密算法实例将信息以一种方式存入数组，以另一种不同的方式读出，可以建立一个计算机化的“天书”。例如，以下联合unionmessage{chars[100];chars2[20][5];}skytale;268.3加密算法实例将信息以一种方式存入数组，以另一种不同的8.3加密算法实例如果你把信息meetmeatsunset存入数组skytale.s，但将它看作一个二维数组skytale.s2，其形式将如下。278.3加密算法实例如果你把信息27MEEt

ME

at

SUnsET0000000028MEEt

ME

at

SUnsET00000000288.3加密算法实例如果你按列读出数组，信息就变成

mm.e...eest...e.u...tan...ts...这里的“.”点号说明了填充的空格。要解密信息，按列填入到skytale.s2，那么数组skytale.s就能按正常次序显示。由于信息以空’\0’结束，skytale.s数组可作为一个字符串显示。天书密码程序使用这种方法加密和解密信息。具体代码从略298.3加密算法实例如果你按列读出数组，信息就变成29第8章课程实习指导算法书写规范实习步骤规范实习报告范例加密算法实例30第8章课程实习指导算法书写规范18.1.1算法书写规范1算法说明算法说明以注释的形式写在程序首部，说明算法的功能，说明各参数的含义和使用的方法，说明使用一个函数需要的入口参数，还有函数调用后返回的出口参数。很多人都依赖算法说明和注解。不好的算法说明不仅不利于他人理解，还可能引起误导。318.1.1算法书写规范1算法说明22.注释与断言注释是很重要的帮助理解算法的手段，但不必要为每句语句都加上注解。当阅读算法时遇到不明之处时，切中要害的注解能大大减少理解算法的时间，同时也利于程序的排错。算法书写规范322.注释与断言算法书写规范3算法书写规范3.输入和输出

算法的输入和输出可以通过几种途径实现。一般最多的是通过函数的参数表进行传递，一种不太好的方法是用全局变量或者用公共的存储区交换数据。这种共享式的交换容易引起岐义和不可控制性，应该尽量少用。

33算法书写规范3.输入和输出4算法书写规范4.语句选用的算法结构算法结构不应该过份追求算法的新奇和花哨，,简明清晰的程序结构和可靠的程序功能是我们需要的目标。要避免大段代码（远大于一页）的直接出现，一般将一页左右的代码分成一个模块（函数），控制模块规模，并用函数原型来说明算法的行为。

34算法书写规范4.语句选用的算法结构5算法书写规范5.基本运算在算法设计过程中，会发现教材上有很多现成的算法可以使用，但我们在学习过程中希望读者不要直接利用这些现成的产品。如果算法工作量很大，非用不可，那必须将所有基本运算写成具体函数过程加以实现。

35算法书写规范5.基本运算6算法书写规范(1)建议用图说明算法。(2)建议在算法书写完毕后，用边界条件的输入参数值验证一下算法能否正确执行。(3)编写代码时，养成良好的编码习惯。

36算法书写规范(1)建议用图说明算法。7算法书写规范“匈牙利记法”的变量名在这种记法中，变量具有一个描述性名字，如Count、UserName，并以大写字母开始。如果变量由多个单词组成，则每个单词词头需大写，在描述性名称前，需加上表示变量类型的字母.37算法书写规范“匈牙利记法”的变量名8前缀变量类型注释AArray数组BBoolean布尔DDouble双精度HHandle句柄（windows用）IInteger整数LLong长型LpfnLongpointertofunction指向函数的长指针m_Membervariable成员变量NInteger整数PPointerto指针SString串SzZeroterminnatedstring以零’\0’结尾的串UUnsignedinteger无符号整数表8-1-1变量的匈牙利记法38前缀变量类型注释AArray数组BBoolean布尔DDou8.1.2实习步骤规范1.问题分析与系统结构设计软件工程的理论表明，解决一个问题的核心在于了解问题本身设计算法前，首先弄清要求做什么而不是怎么做第二步是按照以数据结构为中心的原则划分模块，先定义所需要的数据结构，然后定义在它上面能进行的操作。最后再进行具体编码。398.1.2实习步骤规范1.问题分析与系统结构设计108.1.2实习步骤规范2详细设计和编码写出程序的框架，用伪码和接口描述算法，对需求分析做进一步细化。通过较高层次的设计能使流程清晰，而不陷入具体算法之中。详细设计和编码是对详细设计结果的进一步求精。最后用某种高级语言，比如C语言或者C++语言表达出来。408.1.2实习步骤规范2详细设计和编码118.1.2实习步骤规范3.上机准备和静态检查(以C语言为例)掌握C语言的基本语法掌握C语言的调试方法上机准备的重点应该放在程序的语义方面418.1.2实习步骤规范3.上机准备和静态检查(以C语言为例8.1.2实习步骤规范

静态检查，主要有两种途径，一是用一组测试数据手工执行程序(或分模块进行)；二是通过阅读或给别人讲解自己的程序来全面理解程序逻辑，动态检查，即调试程序。一般要在静态检查无误后，才上机调试。428.1.2实习步骤规范

静态检查，主要有两种途径，一是用一8.1.2实习步骤规范错误是关联的，一个错误会引起其它多个错误。所以当改正一个错误点时，可能消除多个编译错误。当某个错误看来无法改正的时候，可以先试着改正下一个错。上机调试时最好分块进行，自底向上，即先调试低层函数。必要时可以另写一个调用驱动程序。438.1.2实习步骤规范错误是关联的，一个错误会引起其它多个8.1.2实习步骤规范4整理实习报告的内容(1)需求和规格说明(2)设计：(3)调试报告(4)附录448.1.2实习步骤规范4整理实习报告的内容158.1.2实习步骤规范6.实验报告的要求(1)各种文档资料要在程序开发过程中逐渐形成，而不能最后再写(但可以最后誊清)。(2)各种文档资料要用公文纸或稿纸书写，也可以打印，不得写在程序清单上。458.1.2实习步骤规范6.实验报告的要求168.2实习报告范例求出一个不带变量的表达式的值。[问题描述]用一个算法，将一个合法的表达式，如10*3-(4+5)/12转化成计算机能执行的命令或者直接计算出结果。本次设计的算法是递归下降语法分析程序，还有对复杂数值表达式求值所必须的全部支持函数。主要任务是：输入一个串，判断它是否合法，并将其结果算出。468.2实习报告范例求出一个不带变量的表达式的值。178.2实习报告范例[基本要求]根据输入的字符串，判断其是否是合法的表达式。如果不是，给出出错信息。否则计算表达式结果并显示在屏幕上。算法要求体现算符优先级，比如先乘除后加减，先次方再乘除，括号提升优先级等478.2实习报告范例[基本要求]188.2实习报告范例1需求和规格说明

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

（1）设计思想1分解表达式。在设计对表达式求值的语法分析程序之前，先要得到表达式的每一部份，表达式里的每个合乎语法的部份叫一个token。所以返回下一个表达式中元素的函数称为get_token。498.2实习报告范例2设计

208.2实习报告范例2表达式语法分析表达式的求值有多种方法，比如算符优先文法。本例中，将表达式认为是作用于自身的递归的数据结构。例如假使表达式中算符只有+、-、*、/和括号，则它可以用以下规则定义：表达式->项[+项][-项]项->因子[*因子][/因子]因子->变量，数，或者(表达式)508.2实习报告范例2表达式语法分析218.2实习报告范例（2）设计表示法1本程序采用了多个函数。其中相继调用get_exp，level2,level3,level4,level5,level6处理不同优先级的运算，优先级低的+和-算符放在较高层的level2中，*和/放在level3中，这样，调用的时候先由level2调用level3，level3先执行放在其函数体内的*、/处理程序，等处理完成，再返回level2处理加减，这样算符的优先级就得以体现。518.2实习报告范例（2）设计表示法228.2实习报告范例2接口函数功能和说明(略)3调试报告在调试中要特别注意在分析过程中各个函数的调用顺序和调用方法，因为这个顺序隐含了优先级。还要注意参数在传递过程中的变化。比如参数result一级一级返回并被计算的过程。调试遇到的语法问题可能有：①漏了分号②关键字拼写错误③函数参数类型不匹配④花括号不匹配等。具体调试过程因人而异。程序代码略,见书本.528.2实习报告范例2接口函数功能和说明(略)238.3加密算法实例在实现算法之前有两个术语应当熟悉：明文(plaintext)和密文(