本科生《算法与数据结构》实验报告.doc
20页
《算法与数据结构》实验报告学院 专业 姓名 学号 实验1： ADT List（线性表） （3学时）[问题描述]线性表是典型的线性结构，实现ADT List，并在此基础上实现两个集合的交运算或并运算[实验目的]（1）掌握线性表链表存储结构2）掌握在单链表上基本操作的实现3）在掌握单链表的基本操作上进行综合题的实现[实验内容及要求]（1） 要求用带头结点的单链表存储两个集合中的元素和最终的结果2） 集合的元素限定为十进制数，程序应对出现重复的数据进行过滤，即链表中没有重复数据3） 显示两个集合的内容及其运算结果[测试数据]（1） set1={3, 8, 5, 8,11}，set2={22, 6, 8, 3, 15,11,20 } set1∪set2＝set1∩set2＝（2） set1={1, 3, 5, 7}，set2={2, 3, 7, 14, 25,38}set1∪set2＝set1∩set2＝[思考]（1）分析你所设计的算法的时间复杂度？(2) 若输入两个集合内的元素是递增的，见测试数据(2)，请你提出一种时间复杂度更少的算法思想，并分析时间复杂度是多少？《算法与数据结构》实验报告学院 专业 姓名 学号 实验2：利用栈将中缀表达式转换为后缀表达式并进行计算（3学时）[问题描述] 中缀表达式是最普通的一种书写表达式的方式，而后缀表达式不需要用括号来表示，计算机可简化对后缀表达式的计算过程，而该过程又是栈的一个典型应用。
[实验目的] （1） 深入理解栈的特性2） 掌握栈结构的构造方法[实验内容及要求]（1） 中缀表达式中只包含＋、－、×、/ 运算及（ 和 ） （2） 可以输入任意中缀表达式,数据为一位整数3） 显示中缀表达式及转换后的后缀表达式(为清楚起见，要求每输出一个数据用逗号隔开)4） 对转换后的后缀表达式进行计算栈的类定义如下：#include
[实验目的]（1） 深入理解栈的特性2） 掌握使用递归实现某些问题3） 设计出应用栈解决在实际问题背景下对较复杂问题的递归算法[实验内容及要求]（1） 从棋盘的第一行开始放起2） 输出最后每个棋子的在棋盘上的坐标(最好以矩阵形式输出)[测试数据] 自定n值[思考] （1） 设计一个递归算法的三要素是什么？（2） 考虑用非递归实现该问题，并从中总结递归算法和非递归算法的优、缺点各是什么？（3） 通过对递归算法的理解，总结把一个递归算法转换为非递归算法的方法(可查参考书)，并把求n的阶乘的递归算法转换为非递归算法《算法与数据结构》实验报告学院 专业 姓名 学号 实验4：打印二项展开式(a+b)n的系数（3学时）[问题描述]将二项式(a+b)n展开，系数构成著名的杨辉三角形，这是典型的对队列的应用[实验目的]（1）深入理解队列的特性2）掌握使用队列实现某些问题[实验内容及要求]要求打印形式为 1 1 1 2 1 1 3 3 1 1 4 6 4 1 ……………[测试数据] 自定n值。
[思考] （1）杨辉三角形中系数之间的关系是什么？（2）栈和队列各应用于什么范围？《算法与数据结构》实验报告学院 专业 姓名 学号 实验5： 实现二叉树的基本操作 (6学时)[问题描述] 树和二叉树是最常用的非线性结构(树型结构)，其中以二叉树最为常见，本实验题要求实现二叉树的最基本操作，其中遍历二叉树是二叉树各种操作的基础，它分为先序、中序和后序[实验目的]（1） 熟练掌握二叉树的结构特性2） 掌握二叉树的各种存储结构的特点及实用范围3） 通过二叉树的基本操作的实现，从而思考一般树的基本操作的实现4） 熟练掌握各种遍历二叉树的递归和非递归算法[实验内容及要求]（1）创建二叉树：createBTree(…) 所谓创建二叉树是指按照某一种或某两种遍历序列建立起来的二叉树的存储结构 （2）求叶结点的数目：getLeavesNum()（3）画二叉树：drawBTree()（4）输出二叉树的中序遍历序列[测试数据]（1） 以下图所示1或2的形状画出二叉树(不需画线)，从中体会画这两种形状的图的难易程度。
中序遍历序列结果为：（2）自己设定几组序列来验证程序的正确性[思考]（1）若二叉树采用顺序存储，有什么缺点？ （2）根据任意两种遍历序列重建二叉树，然后给出另外一种遍历序列3）在遍历二叉树的算法中，你用的是递归算法？还是非递归算法？若你用的是递归算法，请考虑用非递归算法实现对二叉树的遍历；反之考虑用递归算法实现对二叉树的遍历《算法与数据结构》实验报告学院 专业 姓名 学号 实验6：哈夫曼树的编/译码器系统的设计(6学时)[问题描述]利用哈夫曼编码进行通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本但是，这要求在发送端通过一个编码系统对待传数据进行预先编码；在接受端将传来的数据进行解码（复原）对于可以双向传输的信道，每端都要有一个完整的编/译码系统试为这样的信息收发站写一个哈夫曼的编译码系统 [实验目的] （1） 通过哈夫曼树的定义，掌握构造哈夫曼树的意义2） 掌握构造哈夫曼树的算法思想3） 通过具体构造哈夫曼树，进一步理解构造哈夫曼树编码的意义[实验内容及要求](1) 从终端读入字符集大小为n（即字符的个数），逐一输入n个字符和相应的n个权值（即字符出现的频度），建立哈夫曼树，将它存于文件 hfmtree 中。
并将建立好的哈夫曼树以树或凹入法形式输出;对每个字符进行编码并且输出2) 利用已建好的哈夫曼编码文件 hfmtree ，对键盘输入的正文进行译码输出字符正文，再输出该文的二进制码 [测试数据] 用下表给出的字符集和频度的实际统计数据建立哈夫曼树：字符ABCDEFGHIJKLMN频度641322321032115475715322057字符OPQRSTUVWXYZ空格频度63151485180238181161168并实现以下报文的译码和输出：THIS PROGRAM IS MY FAVORITE[思考](1) 利用哈夫曼编码，为什么能使报文中的电文总长度减少?(2) 为什么利用哈夫曼算法求出的一个字符的编码都不是其它字符编码的前缀？《算法与数据结构》实验报告学院 专业 姓名 学号 实 验7：图的遍历（6学时）[问题描述] 给定一个无向图或有向图，利用深度优先遍历和广度优先遍历对给定图进行遍历[实验目的] （1） 熟悉图的两种常用的存储结构2） 掌握对图的两种遍历方法，即深度优先遍历和广度优先遍历。
3） 进一步掌握利用递归或队列结构进行算法设计方法[实验内容及要求]（1）构造一个具有n个顶点的无向图或有向图2）输出以深度优先遍历和广度优先遍历后的顶点序列[测试数据] 以下图作为测试数据： 输出结果：[思考]（1） 在你所设计的算法中，使用了什么数据结构？（2） 考虑如何把书上给出的递归实现的深度优先遍历算法改为非递归算法？《算法与数据结构》实验报告学院 专业 姓名 学号 实 验8：利用Kruskal算法求无向网的最小生成树（6学时）[问题描述] 如要在n个城市之间建设通信网络，只需架设n-1条线路即可如何以最低的经济代价建设这个通信网，是求一个无向网的最小生成树问题。
