计算机系
第一部分 算法与数据结构课程实验概述 一．实验目的
《算法与数据结构》是计算机专业的主干课程和必修课程之一，其目的是让大家学习、分析和研究数据对象特征，掌握数据组织方法和计算机的表示方法，以便选择合适的数据逻辑结构和存储结构，设计相应的运算操作，把现实世界中的问题转化为计算机内部的表示与处理的方法，要求掌握算法的时间、空间复杂度分析基本技术，培养良好的程序设计风格，掌握进行复杂程序设计的技能。在计算机科学领域，尤其是在系统软件和应用软件的设计和应用中要用到各种数据结构，因此，掌握数据结构对提高软件设计和程序编制水平有很大的帮助。
二．实验要求 2.1实验步骤
设计步骤的规范不但可以培养学生科学的工作方法和作风，而且还能有效地减少错误，提高工作效率。因此必须严格执行良好的实验步骤规范（包括上机操作规范）。本课程实验的基本步骤是： 2.1.1问题分析
充分地分析和理解问题本身，明确问题要求做什么。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如；输入、输出数据的类型、值的范围以及形式等。同时为调试程序准备好测试数据，包含合法的输入数据和非法形式输入的数据。
2.1.2设计和编码
设计即是对问题描述中涉及的操作对象定义相应的数据类型，定义主程序模块和各抽象数据类型；定义相应的存储结构并写出各过程和函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试。
编码即把详细设计的结果进一步求精为程序设计语言程序，写出源程序。对程序中的疑问应作出记号，以便上机时注意解决。每个明确的功能模块程序一般不超过60行，程序的每一行不得超过60个字符，否则要进一步划分。
2.1.3上机前程序静态检查
上机前程序静态检查可有效提高调试效率，减少上机调试程序时的无谓错误。
静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑。把程序中的明显错误事先排除。
2.1.4上机调试程序
上机实验时要带上《C语言》教材、《数据结构》教材、《数据结构上机实验指导书》，调试最好分模块进行，自底向下，即先调试低层过程或函数。调试过程中应多动手确定疑点，通过修改程序来证明。
调试正确后，认真整理源程序及其注释，写出或打印出带有完整注释的且格式良好的源程序清单和结果。
2.1.5完成上机实验报告
2.2实验报告格式
《算法与数据结构》
实验报告
题目：
班级： 组号： 姓名： 学号： 姓名： 学号： 姓名： 学号： 姓名： 学号： 姓名： 学号： 姓名： 学号： 姓名： 学号： 姓名： 学号： 姓名： 学号： 姓名： 学号：
华东理工大学 信息学院计算机系 2012年5月
1． 需求分析
以无歧义的陈述说明程序设计的任务，强调程序要做什么。明确规定： （1）．输入的形式和输入值的范围； （2） 输出的形式 （3） 程序所能达到的功能
（4） 测试数据：包括正确的输入及其输出结果，含有错误的输入及其输出结果。 2． 系统设计
1． 说明本程序中用到的所有抽象数据类型的定义；
2． 主程序的流程以及各程序模块之间的层次调用关系，画出函数的调用关
系图。
3． 列出各个功能模块的主要功能及输入输出参数。 3．调试分析 内容包括：
（1）．调试过程中遇到的问题是如何解决的及对设计与实现的回顾讨论与分析。
（2） 算法的时间复杂度分析（包括基本操作和其他算法）和改进设想； （3） 经验与体会等。 4．测试结果
列出你的测试结果，包括输入与输出，这里的测试数据应完整和严格，可用需求分析中的测试数据。 5、用户手册
说明如何使用你编写的程序，详细列出每一步操作步骤。 6、附录
即带注释的源程序清单和结果。除原有注释外再加一些必要的注释和断
言(关键语句或函数功能的注释)。 对填空和改错题还要写出正确答案，如果题目规定了测试数据，则结果要包含这些测试数据和运行输出，当然还可以含其它测试数据及其运行输出。
2.4考核及评分办法
上机实验成绩根据上机考勤、调试情况、实验报告评分，分为五级制：优、良、中、及格、不及格。
第二部分 上机实验内容 序 号 实验名称 内容提要 实 验 类 型 实验时每组人数 数 1 线性表，栈，队列 1．设计实现一个一元稀疏多项式计算器 设计 2. 表达式求值 ·用二叉树来表示代数表达式 ·求二叉树中从根结点到叶子节点的路径 8 4-5 2 树和二叉树 综合 8 4-5 3 图 图的存储与遍历 验证 4 4-5 4 排序与查找 ·内排序方法的比较 ·二叉排序树 验证 4 4-5
实验一 线 性 表，栈和队列
一、 实验目的
1． 了解线性表，栈和队列等线性结构的特性，以便灵活应用。 2． 熟练掌握线性表，栈和队列的各种操作和应用
二、实验内容
1．分别用线性链表和队列设计实现一个一元稀疏多项式计算器
[问题描述]
设计一个一元稀疏多项式简单计算器。 [基本要求]
1. 用带表头结点的单链表存储多项式，多项式的项数存放在头结点中。 2. 用链式队列存储多项式。多项式的项数存放在队列头结点中。 一元稀疏多项式简单计算器的基本功能是： （1） 输入并建立多项式；
（2） 输出多项式，输出形式为整数序列：n,c1,e1, c2,e2,,,,,,, cn,en,其中n是
多项式的项数，ci,ei,分别是第i项的系数和指数，序列按指数降序排序；
（3） 多项式a和b相加，建立多项式a+b；如果用单链表存储多项式，
则用a存储多项式（a+b）。如果用队列存储多项式，则需为多项式（a+b）另外创建一个队列。
（4） 多项式a和b相减，建立多项式a-b；如果用单链表存储多项式，则
用a存储多项式（a+b）。如果用队列存储多项式，则需为多项式（a+b）另外创建一个队列。
（5） 计算多项式在x处的值。
[测试数据] （1）（2x+5x8-3.1x11）+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)
(2) (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9-x+12x-3) (3) (1+x+x2+x3+x4+x5)+(-x3-x4)=(x5+x2+x+1)
(4) (x+x3)+(-x-x3)=0
(5) (x+x2+x3)+0=( x3+ x2+ x)
2．算术表达式求值：设计一个程序，演示用算符优先法对算术表达式求值的过程。
【问题描述：】
设计一个算术表达式计算器。 [基本要求]
以字符序列的形式从终端输入语法正确的、不含变量，带括号的中缀整数表达式。利用下表给出的算符优先关系，应用运算符栈、运算数栈实现对算术四则混合运算表达式的求值。
算符优先关系表（θ1、θ2是相邻算符，θ1在左，θ2在右）
表达式中任何相邻运算符 1、2 的优先关系有：
1 < 2：1的优先级 低于 2 1 = 2：1的优先级 等于 2 1 > 2：1的优先级 高于 2 [测试数据]
3×（7-2）/（32-17）× （23+45）
实验二 树和二叉树
一、 实验目的
1. 掌握二叉树，二叉树排序数的概念及存储方法。 2. 掌握二叉树的遍历算法。
3. 熟练掌握编写实现树的各种运算的算法。
二、实验内容
1. 用二叉树表示代数表达式并输出代数表达式的前缀式和后缀式
[要求及提示]： 编写一个程序，用二叉树来表示代数表达式，树的每个结点包括一个运算符，代数表达式由输入得到（其中只包含+，-，*，/和用一个字母表示的数且没有错误，并且按照先乘除后加减的原则），试编写程序输出表达式的前缀式和后缀式。 [实验数据]：
自己给出一个并附在实验报告中
2. 求二叉树中从根结点到叶子节点的路径 [要求及提示]
对于1中的代数表达式二叉树，分别用递归和非递归的方法编写程序完成如下功能：
1． 输出所有的叶子结点的数据项值。 2． 输出所有从叶子节点到根结点的路径
实验三 图
一、 实验目的 1.熟悉图的各种存储方法。
2.掌握遍历图的递归和非递归的算法。 3.理解图的有关算法。
二、 实验内容
1．实现图的邻接矩阵和邻接表存储
[要求及提示]
对于下图所示的有向图G，编写一个程序完成如下功能： 1． 建立G的邻接表存储结构 2． 输出下图的拓扑排序序列
3． 编写一个程序输出从顶点0开始的深度优先遍历序列（递归算法）和广
度优先遍历序列（非递归算法）。
实验数据
自己选择一个无圈图。
实验三 查找和排序
一、 实验目的
1. 掌握顺序查找，二分法查找，分块查找的算法。 2．掌握各种排序算法及其性能的比较
二、实验内容
1．编写一个程序输出在顺序表{13，22，35，43，54，68，71，82，98，1005}中采用顺序方法和折半方法查找某个关键字的过程。
2．编写一个程序实现直接插入排序过程，并输出{94，28，57，66，35，84，63，42，71，10}的排序过程
3．编写一个程序实现快速排序算法，并输出{94，28，57，66，35，84，63，42，71，10}的排序过程。
