《算法与数据结构》实验报告.doc

《《算法与数据结构》实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《算法与数据结构》实验报告学院专业姓名学号实验1：约瑟夫环问题（3学时）[问题描述]将编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。[实验目的]（1）掌握线性表的顺序存储结构和循环顺序存储结构。[实验内容及要求]（1）构造数据结构。（2）对线性表进行初始化。[测试数据]输入一组n，m值时，程序输出出列顺序。[思考]（1）你采用的存储结构是

2、顺序表还是循环顺序表？哪个比较合适？（2）当存储结构为循环链表时，如何修改你的程序？并考虑两种存储结构的优缺点。《算法与数据结构》实验报告学院专业姓名学号实验2：ADTList（线性表）（6学时）[问题描述]线性表是典型的线性结构，实现ADTList，并在此基础上实现两个集合的交运算或并运算。[实验目的]（1）掌握线性表的链表存储结构。（2）掌握在单链表上基本操作的实现。（3）在掌握单链表的基本操作上进行综合题的实现。[实验内容及要求]（1）要求用带头结点的单链表存储两个集合中的元素和最终的结果。（2）集合的元素限定为十进制数，程序应对出现重复的数据进行

3、过滤，即链表中没有重复数据。（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)，请你提出一种时间复杂度更少的算法思想，并分析时间复杂度是多少？《算法与数据结构》实验报告学院专业姓名学号实验3：利用栈将中缀表达式转

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

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

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

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

8、。（2）掌握使用队列实现某些问题。[实验内容及要求]要求打印形式为1112113