本科生《算法与数据结构》实验报告3

《本科生《算法与数据结构》实验报告3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法与数据结构》实验报告学院专业姓名学号实验1：ADTList（线性表）（3学时）[问题描述]线性表是典型的线性结构，实现ADTList，并在此基础上实现两个集合的交运算或并运算。[实验目的]（1）掌握线性表链表存储结构。（2）掌握在单链表上基本操作的实现。（3）在掌握单链表的基本操作上进行综合题的实现。[实验内容及要求]（1）要求用带头结点的单链表存储两个集合中的元素和最终的结果。（2）集合的元素限定为十进制数，程序应对出现重复的数据进行过滤，即链表中没有重复数据。（3）显示两个集合的内容及其运算结果。[测试数据]（1）set1={3,

2、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＝第20页[思考]（1）分析你所设计的算法的时间复杂度？(2)若输入两个集合内的元素是递增的，见测试数据(2)，请你提出一种时间复杂度更少的算法思想，并分析时间复杂度是多少？第20页《算法与数据结构》实验报告学院专业姓名学号实验2：利用栈将中缀表达式转换为后缀表达式并进行计算（3学时）[问题描述]中缀表达式是最普通的一种

3、书写表达式的方式，而后缀表达式不需要用括号来表示，计算机可简化对后缀表达式的计算过程，而该过程又是栈的一个典型应用。[实验目的]（1）深入理解栈的特性。（2）掌握栈结构的构造方法。[实验内容及要求]（1）中缀表达式中只包含＋、－、×、/运算及（和）。（2）可以输入任意中缀表达式,数据为一位整数。（3）显示中缀表达式及转换后的后缀表达式(为清楚起见，要求每输出一个数据用逗号隔开)。（4）对转换后的后缀表达式进行计算。栈的类定义如下：#includeconstintStackSize=50;classStack{char

4、*StackList;inttop;public:Stack(){StackList=newchar[StackSize];top=-1;}第20页boolIsEmpty();boolIsFull();voidPush(charx);charPop();charGetTop();voidpostexpression();};//Stack[测试数据]（1）6＋3*(9-7)-8/2转换后的后缀表达式为：计算结果为：（2）(8-2)/(3-1)*(9-6)转换后的后缀表达式为：计算结果为：[思考]（1）把中缀表达式转化为后缀表达式的好处？第2

5、0页（1）考虑当表达式中数据的位数超过一位时，如何修改你的程序？困难在哪？第20页《算法与数据结构》实验报告学院专业姓名学号实验3：n皇后问题（6学时）[问题描述]在一个n×n的国际象棋棋盘上按照每行顺序摆放棋子，在棋盘上的每一个格中都可以摆放棋子，但任何两个棋子不得在棋盘上的同一行、同一列、同一斜线上出现，利用递归算法解决该问题，并给出该问题的n个棋子的一个合理布局。[实验目的]（1）深入理解栈的特性。（2）掌握使用递归实现某些问题。（3）设计出应用栈解决在实际问题背景下对较复杂问题的递归算法。[实验内容及要求]（1）从棋盘的第一行开始放

6、起。（2）输出最后每个棋子的在棋盘上的坐标(最好以矩阵形式输出)。[测试数据]自定n值。[思考]（1）设计一个递归算法的三要素是什么？第20页（1）考虑用非递归实现该问题，并从中总结递归算法和非递归算法的优、缺点各是什么？（2）通过对递归算法的理解，总结把一个递归算法转换为非递归算法的方法(可查参考书)，并把求n的阶乘的递归算法转换为非递归算法。第20页《算法与数据结构》实验报告学院专业姓名学号实验4：打印二项展开式(a+b)n的系数（3学时）[问题描述]将二项式(a+b)n展开，系数构成著名的杨辉三角形，这是典型的对队列的应用。[实验目的

7、]（1）深入理解队列的特性。（2）掌握使用队列实现某些问题。[实验内容及要求]要求打印形式为11121133114641……………[测试数据]自定n值。[思考]（1）杨辉三角形中系数之间的关系是什么？（2）栈和队列各应用于什么范围？第20页《算法与数据结构》实验报告学院专业姓名学号实验5：实现二叉树的基本操作(6学时)[问题描述]树和二叉树是最常用的非线性结构(树型结构)，其中以二叉树最为常见，本实验题要求实现二叉树的最基本操作，其中遍历二叉树是二叉树各种操作的基础，它分为先序、中序和后序。[实验目的]（1）熟练掌握二叉树的结构特性。（2）

8、掌握二叉树的各种存储结构的特点及实用范围。（3）通过二叉树的基本操作的实现，从而思考一般树的基本操作的实现。（4）熟练掌握各种遍历二叉树的递归和非递归算法。[实验内容及要求]（1