《数据结构》实验要求与规范.doc

数据结构实验要求与规范【基本要求】1正确实现所要求的功能，按时提交实验报告。2实验报告内容应依次包括：实验目的；实验内容与要求；数据结构设计；算法设计；测试结果；心得体会。3程序用C语言或C+语言实现。4在包含主函数的程序文件起始处添加包含如下内容的注释：所引用代码和资料的出处、设计本程序时谁在哪些地方帮助过你。5在程序文件起始处添加包含如下内容的注释：文件名称、创建者姓名班级学号、创建时间、最后修改时间、文件中所定义的函数的名称和主要功能、文件中所定义的全局变量的变量名和主要功能、文件中用到的他处定义的全局变量及其出处、与其他文件的依赖关系。6对每个函数添加包含如下内容的注释：函数名称、函数主要功能、函数调用之前的预备条件、函数的输入参数、函数的输出参数、函数的返回值、该函数与其它函数的调用和被调用关系。实验一 顺序表的实现和应用实验目的： 熟悉线性表的定义和基本操作； 掌握线性表的顺序存储结构设计与基本操作的实现。实验内容与要求： 定义线性表的顺序存储表示； 基于所设计的存储结构实现线性表的基本操作； 编写一个主程序对所实现的线性表进行测试； 线性表的应用：设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用线性表L3代表集合C；（选做）设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。实验二 链表的实现和应用实验目的： 掌握线性表的链式存储结构设计与基本操作的实现。实验内容与要求： 定义线性表的链式存储表示； 基于所设计的存储结构实现线性表的基本操作； 编写一个主程序对所实现的线性表进行测试； 线性表的应用：设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用线性表L3代表集合C；（选做）设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。 设计一个一元多项式计算器，要求能够：输入并建立多项式；输出多项式；执行两个多项式相加；执行两个多项式相减；（选做）执行两个多项式相乘。实验三 后缀表达式的计算实验目的： 熟练掌握栈和队列的存储结构设计及基本操作的实现；学会分析实际问题中具有栈特点的数据结构；了解表达式的前缀、中缀、后缀等计算机内表示形式。实验内容与要求： 按常规形式输入算术表达式（例如：输入2*(6-4)+8/4），要求能够： 生成表达式的后缀表示，并输出； 基于表达式的后缀表示，对该表达式求值； 编写一个主程序对表达式求值函数进行测试。实验四 数组的运算实验目的： 掌握稀疏矩阵的压缩存储方法及主要运算的实现。实验内容与要求： 设计一个稀疏矩阵计算器，要求能够：输入并建立稀疏矩阵；输出稀疏矩阵；执行两个矩阵相加；执行两个矩阵相乘；求一个矩阵的转置矩阵；（选做）求一个矩阵的逆矩阵。实验五 二叉树的创建与遍历实验目的： 通过上机实验进一步掌握栈、队列、二叉树的存储结构及基本操作的实现方法。实验内容与要求： 基于二叉链表存储结构实现二叉树的基本运算，要求： 能建立非空二叉树； 实现二叉树的先、中、后序递归遍历算法； 实现二叉树的非递归的先（或中、或后）序遍历算法及层序遍历算法； 记录运行结果并对递归算法和非递归算法的效率加以分析。实验六 二叉树的应用实验目的： 掌握赫夫曼二叉树的建立及赫夫曼编码的生成。实验内容与要求： 根据给定的n个权值生成赫夫曼二叉树，输出赫夫曼编码。实验七 图的创建与遍历实验目的： 通过上机实验进一步掌握图的存储结构及基本操作的实现。实验内容与要求： 分别基于邻接矩阵和邻接表存储结构实现图的基本运算，要求： 能根据输入的顶点、边/弧的信息建立图； 实现图中顶点、边/弧的插入、删除； 实现对该图的深度优先遍历；实现对该图的广度优先遍历。实验八 图的应用实验目的： 掌握图的基本应用的实现。实验内容与要求： 在下列图的应用中选做两项： 求无向连通网的最小生成树； 对有向图进行拓扑排序； 求AOE网的关键路径；求单源点出发的最短路径。实验九 查找方法比较实验目的： 通过上机实验对各种静态、动态查找方法进行比较。实验内容与要求： 实现三种以上静态或动态查找方法，查找表中的数据随机生成； 生成随机数，并执行查找，