数据结构上机实验指导书

《数据结构上机实验指导书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机系第一部分算法与数据结构课程实验概述一．实验目的《算法与数据结构》是计算机专业的主干课程和必修课程之一，其目的是让大家学习、分析和研究数据对象特征，掌握数据组织方法和计算机的表示方法，以便选择合适的数据逻辑结构和存储结构，设计相应的运算操作，把现实世界中的问题转化为计算机内部的表示与处理的方法，要求掌握算法的时间、空间复杂度分析基本技术，培养良好的程序设计风格，掌握进行复杂程序设计的技能。在计算机科学领域，尤其是在系统软件和应用软件的设计和应用中要用到各种数据结构，因此，掌握数据结构对提高软件设计和程序编制水平有很大的帮助。二．实验

2、要求2.1实验步骤设计步骤的规范不但可以培养学生科学的工作方法和作风，而且还能有效地减少错误，提高工作效率。因此必须严格执行良好的实验步骤规范（包括上机操作规范）。本课程实验的基本步骤是：2.1.1问题分析充分地分析和理解问题本身，明确问题要求做什么。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如；输入、输出数据的类型、值的范围以及形式等。同时为调试程序准备好测试数据，包含合法的输入数据和非法形式输入的数据。2.1.2设计和编码设计即是对问题描述中涉及的操作对象定义相应的数据类型，定义主程序模块和各抽象

3、数据类型；定义相应的存储结构并写出各过程和函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试。编码即把详细设计的结果进一步求精为程序设计语言程序，写出源程序。对程序中的疑问应作出记号，以便上机时注意解决。每个明确的功能模块程序一般不超过60行，程序的每一行不得超过60个字符，否则要进一步划分。2.1.3上机前程序静态检查上机前程序静态检查可有效提高调试效率，减少上机调试程序时的无谓错误。静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑。把程序中

4、的明显错误事先排除。2.1.4上机调试程序上机实验时要带上《C语言》教材、《数据结构》教材、《数据结构上机实验指导书》，调试最好分模块进行，自底向下，即先调试低层过程或函数。调试过程中应多动手确定疑点，通过修改程序来证明。调试正确后，认真整理源程序及其注释，写出或打印出带有完整注释的且格式良好的源程序清单和结果。2.1.5完成上机实验报告2.2实验报告格式《算法与数据结构》实验报告题目：班级：组号：姓名：学号：姓名：学号：姓名：学号：姓名：学号：姓名：学号：姓名：学号：姓名：学号：姓名：学号：姓名：学号：姓名：学号：华东理工大学信息学院计

5、算机系2012年5月1．需求分析以无歧义的陈述说明程序设计的任务，强调程序要做什么。明确规定：（1）．输入的形式和输入值的范围；（2）输出的形式（3）程序所能达到的功能（4）测试数据：包括正确的输入及其输出结果，含有错误的输入及其输出结果。2．系统设计1．说明本程序中用到的所有抽象数据类型的定义；2．主程序的流程以及各程序模块之间的层次调用关系，画出函数的调用关系图。3．列出各个功能模块的主要功能及输入输出参数。3．调试分析内容包括：（1）．调试过程中遇到的问题是如何解决的及对设计与实现的回顾讨论与分析。（2）算法的时间复杂度分析（包括基

6、本操作和其他算法）和改进设想；（3）经验与体会等。4．测试结果列出你的测试结果，包括输入与输出，这里的测试数据应完整和严格，可用需求分析中的测试数据。5、用户手册说明如何使用你编写的程序，详细列出每一步操作步骤。6、附录即带注释的源程序清单和结果。除原有注释外再加一些必要的注释和断言(关键语句或函数功能的注释)。对填空和改错题还要写出正确答案，如果题目规定了测试数据，则结果要包含这些测试数据和运行输出，当然还可以含其它测试数据及其运行输出。2.4考核及评分办法上机实验成绩根据上机考勤、调试情况、实验报告评分，分为五级制：优、良、中、及格、

7、不及格。第二部分上机实验内容序号实验名称内容提要实验类型实验时数每组人数1线性表，栈，队列1．设计实现一个一元稀疏多项式计算器2.表达式求值设计84-52树和二叉树·用二叉树来表示代数表达式·求二叉树中从根结点到叶子节点的路径综合84-53图图的存储与遍历验证44-54排序与查找·内排序方法的比较·二叉排序树验证44-5实验一线性表，栈和队列一、实验目的1．了解线性表，栈和队列等线性结构的特性，以便灵活应用。2．熟练掌握线性表，栈和队列的各种操作和应用二、实验内容1．分别用线性链表和队列设计实现一个一元稀疏多项式计算器[问题描述]设计一个

8、一元稀疏多项式简单计算器。[基本要求]1.用带表头结点的单链表存储多项式，多项式的项数存放在头结点中。2.用链式队列存储多项式。多项式的项数存放在队列头结点中。一元稀疏多项式简单计算器的基本功