数据结构与算法实验报告

数据结构与算法

实 验 报 告

编制教师 袁宇丽 审定 何文孝

（适用于计算机科学学院2012级本科学生）

专业: 班级: 级 班 学号:________________________ 姓名:________________________ 2013至2014学年第二学期

计算机科学学院

实验名称：线性表的应用 指导教师： 余文春 实验日期：2014年 月 日 实验地点：北503 成绩： 实验目的：

1、 掌握线性表及其顺序存储与链式存储结构的概念。 2、 掌握两种存储方式的基本运算、实现方法和技术。 3、 灵活应用线性表进行程序设计，解决实际问题。 实验内容：

约瑟夫(Joseph)问题的一种描述是：编号为1，2，„，n的n个人按顺时针方向围坐一圈，一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，同样报到m的人出列，如此下去，直至所有人全部出列为止。利用循环链表为存储结构模拟此过程，按照出列的顺序输出依次出列人的编号。

基本要求：

1、写出完成实验内容的实验方法和源代码。 2、写出实验数据及运行结果。

3、写出在实验过程中所遇到的问题及解决办法。

实验总结及意见： 实验评价（教师）：

实验名称：栈及队列的应用 指导教师： 余文春

实验日期：2014年 月 日 实验地点：北503 成绩：

实验目的：

1、掌握队列及其存储结构的概念。

2、掌握栈、队列的基本运算、实现方法和技术。

3、能用栈、队列的知识和操作技术设计有一定难度的程序。 实验内容：

1、假设算术表达式仅由加(+)、减(-)、乘(*)、除(\\)运算符组成，编写一个借助堆栈把中缀表达式转换为后缀表达式的函数，为使问题简化，可不考虑中缀表达式不正确的情况。

2、假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。 基本要求：

1、写出完成实验内容的实验方法和源代码。 2、写出实验数据及运行结果。

3、写出在实验过程中所遇到的问题及解决办法。

实验总结及意见： 实验评价（教师）：

实验名称：二叉树的建立与遍历算法 指导教师： 余文春 实验日期：2014年 月 日 实验地点：北503 成绩： 实验目的：

1、掌握二叉树的定义。

2、二叉树的链式存储结构及在链式存储结构中三种遍历（前序，中序，后序）操作的实现及应用。 实验内容：

1、编写程序，建立一棵二叉树（以链表存储），对该二叉树进行遍历并输出该二叉树的前序，中序，后序遍历序列。要求前序、中序遍历用非递归方法，后序遍历用递归方法完成。

2、编写程序，建立一棵二叉树（以链表存储），实现二叉树左右子树的交换。

3、统计二叉树中叶子结点个数。(要求用非递归算法完成) 基本要求：

1、写出完成实验内容的实验方法和源代码。 2、写出实验数据及运行结果。

3、写出在实验过程中所遇到的问题及解决办法。

实验总结及意见： 实验评价（教师）：

实验名称：查找及排序算法 指导教师： 余文春 实验日期：2014年 月 日 实验地点：北503 成绩： 实验目的：

1、掌握基本查找和排序技术的原理及其实现方法。

2、对于不同的要求，能选择比较合理的查找、排序算法，得到初步的算法分析的训练，提高算法设计的能力。 实验内容：

定义一最大长度为20的结构体数组（可以在结构体中只定义关键字域），从键盘输入结构体数组各元素的关键字值，以输入-9999为结束，对该数组中的元素按关键字非递减的顺序进行排序，分别用冒泡排序，非递归的快速排序，递归的快速排序方法完成，再用折半查找方法对已经有序的结构体数组进行操作，输入一待查记录关键字，若查找成功输出“success”,查找不成功则输出“unsuccess”，以上各功能模块均用函数实现。设计相应算法并分析各排序方法的效率。

该程序运行情况举例说明：

运行主界面如下图所示：提示用户输入相应选项，键入数字1则进行待排序数据值的输入；键入数字2进行冒泡排序；键入数字3进行递归的快速排序；键入数字4则进行递归的快速排序；键入数字5则进行折半（二分）查找；键入数字0程序结束并退出。 基本要求：

1、写出完成实验内容的实验方法和源代码。 2、写出实验数据及运行结果。

3、写出在实验过程中所遇到的问题及解决办法。

实验总结及意见： 实验评价（教师）：