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