数据结构与算法实验报告

1、数据结构与算法实验报告编制老师 袁宇丽 审定 何文孝（适用于计算机科学学院2022级本科同学）专业:班级： 级 班学号:姓名:2022至2022学年其次学期计算机科学学院试验总结及意见:试验评价（老师）:试验名称：线性表的应用指导老师：余文春试验日期：2022年 月 日 试验地点：北503 成果：试验目的：1、把握线性表及其挨次存储与链式存储结构的概念。2、把握两种存储方式的基本运算、实现方法和技术。3、敏捷应用线性表进行程序设计，解决实际问题。试验内容：约瑟夫(Joseph)问题的一种描述是：编号为1, 2,，n的n个 人按顺时针方向围坐一圈，一开头任选一个正整数作为报数上限值m, 从第一个

2、人开头按顺时针方向自1开头挨次报数，报到m时停止报数。 报m的人出列，从他在顺时针方向上的下一个人开头重新从1报数， 同样报到m的人出列，如此下去，直至全部人全部出列为止。采用循 环链表为存储结构模拟此过程，根据出列的挨次输出依次出列人的编 号。基本要求：1、写出完成试验内容的试验方法和源代码。2、写出试验数据及运行结果。3、写出在试验过程中所遇到的问题及解决方法。试验总结及意见:试验评价（老师）:试验名称：栈及队列的应用指导老师：余文春试验日期：2022年 月 日 试验地点：北503 成果：试验目的：1、把握队列及其存储结构的概念。2、把握栈、队列的基本运算、实现方法和技术。3、能用栈、队列

3、的学问和操作技术设计有肯定难度的程序。试验内容：1、假设算术表达式仅由加(+)、减(-)、乘(*)、除()运算符组 成，编写一个借助堆栈把中缀表达式转换为后缀表达式的函数，为使 问题简化，可不考虑中缀表达式不正确的状况。2、假设在周末舞会上，男士们和女士们进入舞厅时，各自排成 一队。跳舞开头时，依次从男队和女队的队头上各出一人配成舞伴。 若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞 曲。现要求写一算法模拟上述舞伴配对问题。基本要求：1、写出完成试验内容的试验方法和源代码。2、写出试验数据及运行结果。3、写出在试验过程中所遇到的问题及解决方法。试验总结及意见:试验评价（老师）:试验

4、名称：二叉树的建立与遍历算法指导老师：余文春试验日期：2022年 月 日 试验地点：北503成果：试验目的：1、把握二叉树的定义。2、二叉树的链式存储结构及在链式存储结构中三种遍历（前序, 中序，后序）操作的实现及应用。试验内容：1、编写程序，建立一棵二叉树（以链表存储），对该二叉树进行 遍历并输出该二叉树的前序，中序，后序遍历序列。要求前序、中序 遍历用非递归方法，后序遍历用递归方法完成。2、编写程序，建立一棵二叉树（以链表存储），实现二叉树左右 子树的交换。3、统计二叉树中叶子结点个数。（要求用非递归算法完成） 基本要求：1、写出完成试验内容的试验方法和源代码。2、写出试验数据及运行结果。

5、3、写出在试验过程中所遇到的问题及解决方法。试验总结及意见:试验评价（老师）:试验名称：查找及排序算法指导老师：余文春试验日期：2022年 月 日 试验地点：北503 成果：试验目的：1、把握基本查找和排序技术的原理及其实现方法。2、对于不同的要求，能选择比较合理的查找、排序算法，得到 初步的算法分析的训练，提高算法设计的力量。试验内容：定义一最大长度为20的结构体数组（可以在结构体中只定义关 键字域），从键盘输入结构体数组各元素的关键字值，以输入-9999 为结束，对该数组中的元素按关键字非递减的挨次进行排序，分别用 冒泡排序，非递归的快速排序，递归的快速排序方法完成，再用折半 查找方法对已

6、经有序的结构体数组进行操作，输入一待查纪录关键 字，若查找胜利输出“success”，查找不胜利则输出“unsuccess，以 上各功能模块均用函数实现。设计相应算法并分析各排序方法的效 率。该程序运行状况举例说明：运行主界面如下图所示：提示用户输入相应选项，键入数字1则 进行待排序数据值的输入；键入数字2进行冒泡排序；键入数字3进 行递归的快速排序；键入数字4则进行递归的快速排序；键入数字5 则进行折半（二分）查找；键入数字。程序结束并退出。基本要求：1、写出完成试验内容的试验方法和源代码。2、写出试验数据及运行结果。3、写出在试验过程中所遇到的问题及解决方法:|主菜单如下:select 1:输入待排序元素值select 2:直接插入排序select 3:直接