数据结构与算法实习指导书

《数据结构与算法实习指导书》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构与算法实习指导书上海交通大学电院数据结构大平台课程组目录1・关于实习步骤的要求和建议2.上机实习实习一线性结构实习二树和二叉树实习三查找实习四图3・实习报告样例关于实习步骤的要求和建议从以往的教学事先实习的经验来看，在初学阶段执行严格的实习步骤规范（包括上机操作规范），机时利用率会大大提高，有助于养成良好的程序编制风格，培养严谨、科学、高效的工作方式。在以往的教学实践中，经常发现很多学生抱怨说，化了两个小时才找出一个错误，甚至一无所获。他们不明白造成这种情况的原因，正是他们自己。有的学生不屑于按实习步骤规范

2、去做，甚至对于实习步骤的要求和建议看都不看一遍，认为那是浪费时间，这是及其害的。实习步骤规范不但可以培养科学化的工作作风，而且还能有效地避免错误。具体的步骤机规范如下:1.问题分析与系统的结构设计:充分地分析和理解问题本身，弄清要求作什么，限制条件是什么。按照以数据结构为中心的原则划分模块，即定义数据结构及其在这些结构之上的操作，使得对数据结构的存取通过这些操作加以实现。在这个过程中，要综合考虑系统功能。要考虑系统结构清晰、合理、简单并且易于调试。最后写出每个子程序（过程或函数）的规格说明，列出它们之间的调用关系，

3、可以使用调用关系图表示则更加清晰，这样便完成了系统结构设计。2.详细设计和编码详细设计的目的是对子程序（过程或函数）的进一步求精。用IF、WHILE和赋值语句等，以及自然语言写出算法的框架。利用自然语言的目的是避免陷入细节。在编码时，可以对详细设计的结果进一步求精，用高级语言表不出来。程序的每一行最好不超过60个字符。每个子程序（或过程、函数）通常不要太长，以40行为宜。子程序（或过程、函数）包含的程序行数太多，易于造成理解的困难。控制IF、WHILE等语句的连续嵌套的深度应加以控制。程序的目的性必须明确。对每一段

4、程序完成的作用，除非常明显的除外（如：x=x+l;注释为x加1,没有什么意义），都应加以注释。这会对程序的调试提供很多方便。另外，根据情况可以设立若干调试点，即输出若干信息，用于验证和你的设想是否一致。另外，对于输入输出语句，必须对它们的作用加以说明。否则，在调试程序时，无法了解系统需要输入什么，系统输出的又是什么。程序的书写，必须按照一定的规范，如保留字小写时涂黑等等。3.上机准备和静态检查上机准备：•高级语言文本•熟悉机器的用户手册，熟悉常用的命令。•准备调试的工具，考虑调试方案。如果机器上没有现成的调试工具可

5、供利用，可以自己先设计一些以供使用。•静态检查自己用一组数据手动执行程序；或同同学一起阅读自己的程序，以全面地了解该程序的逻辑。4.上机调试程序自底向上，先调试底层模块，再调试上层模块。最后，整个程序进行联调。调试正确后将源程序和运行结果加以列印输出。1.实习报告的整理•需求及规格说明问题描述，求解的问题是什么。•设计：设计思想：存储结构、主要的算法思想。设计表示：子程序（过程或函数）的规格说明，通过调用关系图表示它们之间的调用关系。实现注释：详细设计表示：主要算法的框架。•用户手册：使用说明。•调试报告：问题是如

6、何解决的，讨论与分析、改进设想、经验与体会、时空复杂度等。•附录源程序清单和结果：源程序必须有注释，以及必要的测试数据和运行结果数据。提倡用英文描述。•实验报告要求：在程序开发过程中，逐步形成各种必要的文档及资料。可以写在实验报告纸上，或以电子文档的形式进行书写。2.上机实习•以下的实习题目配合课程的进度，请同学们务必自己完成。为了锻炼自己的应用各种不同的数据结构的能力，尽可能的多作一些题目是非常必要的。在完成各种不同题目的过程中，对各种算法的时、空复杂性的分析，将帮助您在更高的角度解决各种应用问题。•为了减轻同学

7、的负担，我们对同学的实习报告进行了精简。本实习报告中的题目分以下几种类型：1、实习题：必须按照实习报告的规范完成。每个实习的第一题都是实习题，必须编写详细的实习报告。实习报告的书写方法，请参阅本指导书的第3部分：实习报告的样例。2、作业题：同样必须完成。只需交代清楚题目的解法，辅以求解程序和注释，使得别人能够看懂你的算法和程序即可。不必象实习题那样书写完整的实习报告。3、选作题：鼓励同学选作的题目，尤其是学有余力的同学。以下为各次实习作业:实习一线性结构1、（实习题）请写出计算两个以单链接表表示的多项式相乘的程序。

8、2、（作业题）已知两个单链表A和B分别表示两个集合，其元素递增排列。请编写程序求集合A和B的交集C二AcB,要求单链表C按其元素递增排列，并利用原表（即表A和表B）的结点空间存放表C。3、（作业题）假设有二个栈共同使用一块顺序存储的空间，为简单起见可设为共同使用数组inta（200）。它们的栈底分别设在数组的两端，而栈顶指针在进行插入操作时，向中间方向移动。