数据结构与算法实验报告册

- 欢迎下载 河南工程学院河南工程学院 理学院学院理学院学院 实验报告 （数据结构与算法） 学学 期期: : 课课 程程: : 专专 业业: : 班班 级级: : 学学 号号: : 姓姓 名名: : 指导教师指导教师: : - 欢迎下载 目目 录录 实验一实验一 线性表线性表 1（顺序表及单链表的合并）（顺序表及单链表的合并）.1 实验二实验二 线性表线性表 2（循环链表实现约瑟夫环）（循环链表实现约瑟夫环）.1 实验三实验三 栈和队列的应用（表达式求值和杨辉三角）栈和队列的应用（表达式求值和杨辉三角） .1 实验四实验四 赫夫曼编码赫夫曼编码 实验五实验五 最小生成树最小生成树.1 实验六实验六 排序算法排序算法 - 欢迎下载 实验一实验一 线性表线性表 1 一、实验学时：一、实验学时： 2 学时学时 二、实验目的二、实验目的 1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系。在计算机中 表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。 2.熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储 结构上的实现。 三、实验内容三、实验内容 1. 编写程序，实现顺序表的合并。 2. 编写程序，实现单链表的合并。 四、主要仪器设备及耗材四、主要仪器设备及耗材 硬件：计算机一台 软件：VC+ 6.0，MSDN2003 或者以上版本 五、算法设计五、算法设计 1. 顺序表合并的基本思想 程序流程图： 2. 单链表合并的基本思想 程序流程图 六、程序清单六、程序清单 - 欢迎下载 七、实现结果七、实现结果 - 欢迎下载 八、实验体会或对改进实验的建议八、实验体会或对改进实验的建议 - 欢迎下载 实验二实验二 线性表线性表 2 一、实验学时：一、实验学时： 2 学时学时 二、实验目的二、实验目的 1.了解双向循环链表的逻辑结构特性，理解与单链表的区别与联系。 2.熟练掌握双向循环链表的存储结构以及基本操作。 三、实验内容三、实验内容 编写程序，采用循环链表实现约瑟夫环。 设有编号为 1，2，n 的 n(n0)个人围成一个圈，从第 1 个人开始报 数，报到 m 时停止报数，报 m 的人出圈，再从他的下一个人起重新报数，报到 m 时停止报数，报 m 的出圈，如此下去，直到所有人全部出圈为止。当 任意给定 n 和 m 后，设计算法求 n 个人出圈的次序。 四、主要仪器设备及耗材四、主要仪器设备及耗材 硬件：计算机一台 软件：VC+ 6.0，MSDN2003 或者以上版本 五、算法设计五、算法设计 约瑟夫环实现的基本思想 程序流程图： 六、程序清单六、程序清单 - 欢迎下载 七、实现结果七、实现结果 - 欢迎下载 八、实验体会或对改进实验的建议八、实验体会或对改进实验的建议 - 欢迎下载 实验三实验三 栈和队列的应用栈和队列的应用 一、实验学时：一、实验学时： 2 学时学时 二、实验目的二、实验目的 1.掌握栈的存储结构、基本算法，尤其是入栈和出栈操作。 2、理解队列的含义，掌握队列的存储结构以及入队、出队操作。 三、实验内容三、实验内容 1. 编写程序，采用栈的结构实现表达式求值。 2. 编写程序，采用队列的结构实现杨辉三角。 四、主要仪器设备及耗材四、主要仪器设备及耗材 硬件：计算机一台 软件：VC+ 6.0，MSDN2003 或者以上版本 五、算法设计五、算法设计 1. 表达式求值的基本思想 程序流程图： 2. 实现杨辉三角的基本思想 程序流程图 六、程序清单六、程序清单 - 欢迎下载 七、实现结果七、实现结果 - 欢迎下载 八、实验体会或对改进实验的建议八、实验体会或对改进实验的建议 - 欢迎下载 实验四实验四 赫夫曼编码赫夫曼编码 一、实验学时：一、实验学时： 2 学时学时 二、实验目的二、实验目的 1、掌握赫夫曼树和赫夫曼编码的存储表示，实现赫夫曼编码。 2、理解二叉树的存储结构和实现算法。 三、实验内容三、实验内容 在传送电文时，总希望总长极尽可能地短，如果对每个字符设计长度不等 的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的 总长便可减少。为了不造成多种译法，采用前缀编码，即任一个字符的编码都 不是另一个字符的编码的前缀,寻找该前缀编码的过程即为赫夫曼编码的过程。 测试数据：已知某系统在通信联络中只可能出现 8 种字符，其概率分别为 0.05,0.29,0.07,0.08,0.14，0.23,0.03,0.11，试设计赫夫曼编码。 四、主要仪器设备及耗材四、主要仪器设备及耗材 硬件：计算机一台 软件：VC+ 6.0，MSDN2003 或者以上版本 五、算法设计五、算法设计 1. 构造赫夫曼树的