《贵州大学数据结构实验任务指导书(实验报告版)》由会员分享，可在线阅读，更多相关《贵州大学数据结构实验任务指导书(实验报告版)（14页珍藏版）》请在金锄头文库上搜索。
1、贵州大学计算机科学与技术学院贵州大学计算机科学与技术学院 计算机科学与技术系上机实验报告计算机科学与技术系上机实验报告 课程名称：数据结构班级：计科 121实验日期：日期 姓名：学号：指导教师：程欣宇 实验序号：一实验成绩： 一、实验名称 线性表及其应用 二、实验目的及要求 1、熟悉链表的创建，链表结点查找、插入和删除； 2、理解链表用于存储线性表的优势和劣势； 3、掌握利用链表存储一元多项式的数据结构，及其运算操作。 三、实验环境 Visual C+ 四、实验内容 1、输入并建立多项式； 2、输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,.,cn,en, 其中 n 是多项式的项
2、数，ci 和 ei 分别是第 I 项的系数和指数，序列按 照指数降序排列； 3、多项式 a 和 b 相加，建立多项式 a+b； 4、多项式 a 和 b 相减，建立多项式 a-b。 五、算法描述及实验步骤 使用链表存储一元多项式c1 X e1+ c2 Xe2+ cn Xen 如下图所示： 如何实现这种线性链表表示的多项式的加法运算？ 根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的 项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一 元多项式中所有指数不相同的项，则分别复抄到“和”多项式中去。 实验步骤： 1、 2、 3、 头结点c1e1c2e2cnen 六、
3、调试过程及实验结果 详细记录程序在调试过程中出现的问题及解决方法。 记录程序执行的结果。 七、总结 对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。 八、附录 源程序（核心代码）清单或使用说明书，可另附纸 贵州大学计算机科学与技术学院贵州大学计算机科学与技术学院 计算机科学与技术系上机实验报告计算机科学与技术系上机实验报告 课程名称：数据结构班级：计科 121实验日期：日期 姓名：学号：指导教师：程欣宇 实验序号：二实验成绩： 一、实验名称 栈及其应用 二、实验目的及要求 1、熟悉栈的原理和实现方式； 2、理解使用栈消除函数递归调用的原理； 3、掌握后缀表达式计算的方法。 三、实验
4、环境 Visual C+ 四、实验内容 1、栈实现阶乘函数； 2、栈实现后缀表达式的计算。 五、算法描述及实验步骤 函数调用栈的结构如下： 第 n 层调用 （当前函数局部变量空间） 第 n-1 层调用 （当前函数的主调函数变量空间） 第 1 层调用 主函数局部变量空间 函数调用的栈空间 返 回 返 回 返 回 调 用 调 用 调 用 调 用 返 回 使用栈消去递归的算法框架如下： 初始化栈； 将完整问题参数压栈； while(栈非空) 取出栈顶元素所描述的问题 如果可以直接解决，则直接解决 否则分解为子问题压栈 后缀表达式是运算符在运算数之后的一种表达式存储的数据结构，不需要比 较运算符优先级
5、别， 只需要每次读到运算数时压栈， 读到运算符时将运算数出栈， 将结果压栈即可。最后的运算结果存放在栈底。 实验步骤 1、 2、 3、 六、调试过程及实验结果 详细记录程序在调试过程中出现的问题及解决方法。 记录程序执行的结果。 七、总结 对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。 八、附录 源程序（核心代码）清单或使用说明书，可另附纸 贵州大学计算机科学与技术学院贵州大学计算机科学与技术学院 计算机科学与技术系上机实验报告计算机科学与技术系上机实验报告 课程名称：数据结构班级：计科 121实验日期：日期 姓名：学号：指导教师：程欣宇 实验序号：三实验成绩： 一、实验名称 队
6、列及其应用 二、实验目的及要求 1、熟悉队列的原理和实现方式； 2、理解使用队列进行搜索的原理； 3、掌握使用队列进行搜索的程序设计方法。 三、实验环境 Visual C+ 四、实验内容 1、使用队列实现教科书 P50 页说描述的迷宫问题。 五、算法描述及实验步骤 使用队列进行搜索的算法框架如下： 初始化队列； 将搜索的出发点入队； while(队列非空) 取出队首元素所描述的位置； 如果到达搜索目标，则完成搜索，推出循环； 否则将该位置可以扩展搜索的位置入队待搜索。 实验步骤 1、 2、 3、 六、调试过程及实验结果 详细记录程序在调试过程中出现的问题及解决方法。 记录程序执行的结果。 七、
7、总结 对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。 八、附录 源程序（核心代码）清单或使用说明书，可另附纸 贵州大学计算机科学与技术学院贵州大学计算机科学与技术学院 计算机科学与技术系上机实验报告计算机科学与技术系上机实验报告 课程名称：数据结构班级：计科 121实验日期：日期 姓名：学号：指导教师：程欣宇 实验序号：四实验成绩： 一、实验名称 串及其应用 二、实验目的及要求 1、熟悉串的基本操作方法 2、掌握文本模式匹配算法。 三、实验环境 Visual C+ 四、实验内容 1、输入以回车作为结束符的一串字符作为主串； 2、求主串中指定的单个字符出现的次数和位置； 3、求主串
8、中指定子串出现的次数和位置； 4、求主串中指定单词出现的次数和位置,注意单词与子串的区别。 五、算法描述及实验步骤 算法描述： 1、统计指定单个字符出现的次数和位置，只需遍历主串的每一个字符即可。 2、求指定子串出现的位置，可以采用逐位置滑动的匹配方法和 KMP 快速匹 配算法。 3、求指定单词出现的位置，关键是考虑单词和子串的不同，即：单词首尾 要么是空格要么是主串的首尾，所以在匹配到子串后，作此检查即可。另外，也 可以考虑采用在主串和单词首尾加入空格的方法，进行子串搜索。 实验步骤 1、 2、 3、 六、调试过程及实验结果 详细记录程序在调试过程中出现的问题及解决方法。 记录程序执行的结果
9、。 七、总结 对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。 八、附录 源程序（核心代码）清单或使用说明书，可另附纸 贵州大学计算机科学与技术学院贵州大学计算机科学与技术学院 计算机科学与技术系上机实验报告计算机科学与技术系上机实验报告 课程名称：数据结构班级：计科 121实验日期：日期 姓名：学号：指导教师：程欣宇 实验序号：五实验成绩： 一、实验名称 稀疏矩阵和多维数组的实现 二、实验目的及要求 1、熟悉三元组方式存储稀疏矩阵的原理和算法； 2、掌握多维数组的存储空间分配和访问算法。 三、实验环境 Visual C+ 四、实验内容 1、封装一个稀疏矩阵类。要求内部使用三元组顺
10、序表表示。 要求实现如下成员函数： a、按三元组数组构造 b、矩阵加法 c、矩阵转置 d、矩阵乘法 不要求实现性能最优化算法，不要求使用运算符重载，要求构造测试用例。 2、封装一个三维数组类 class Array3D 内部使用一维数组存储数据。 提供构造函数 提供访问每一维长度的方法 int getLength(int dim) 提供读取任意一元素的方法 ElemType get(int i,int j,int k) 提供写入取任意一元素的方法 void set(int i,int j,int k,ElemType value) 五、算法描述及实验步骤 三元组方式存储稀疏数组： 1、表示稀疏
11、矩阵的一个非零元素可以使用一个三元组：行号、列号、元素 值。 2、使用 n 个三元元组表示一个稀疏矩阵，需要定义一个三元组的数组，数 组大小等于 n+1，其中第一个三元组存储数组的最大行列号。 多维数组的实现算法： 1、传入三维数组各位大小：n,m,p，动态申请内存空间，size=n*m*p； 2、访问元素需要传入下标数组：i,j,k，其对应存储空间为： Loc(i,j,k)=i*p*m+j*p+k 实验步骤 1、 2、 3、 六、调试过程及实验结果 详细记录程序在调试过程中出现的问题及解决方法。 记录程序执行的结果。 七、总结 对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。 八
12、、附录 源程序（核心代码）清单或使用说明书，可另附纸 贵州大学计算机科学与技术学院贵州大学计算机科学与技术学院 计算机科学与技术系上机实验报告计算机科学与技术系上机实验报告 课程名称：数据结构班级：计科 121实验日期：日期 姓名：学号：指导教师：程欣宇 实验序号：六实验成绩： 一、实验名称 哈夫曼编码/译码器 二、实验目的及要求 1、掌握二叉树的存储方法； 2、掌握 Huffman 二叉树的构造、编码和译码算法； 三、实验环境 Visual C+ 四、实验内容 1、生成编码二叉树 输入为字符集和词频，输出为哈夫曼二叉树。 字符集和词频如下： 字 符 空 格 ABCDEFGHIJKLM 频 度
13、 1866413223210321154757153220 字 符 NOPQRSTUVWXYZ 词 频 5763151485180238181161 2、编码器设计 输入为二叉树和要编码的内容，输出为编码结果 3、译码器设计 输入为二叉树和要解码的内容，输出为译码内容 五、算法描述及实验步骤 哈夫曼二叉树在创建过程中，最初为 n 个独立的叶子结点， 的叶子结点就是要编码的字符，数量为 n，最初为 创建可以使用一个= 实验步骤 1、 2、 3、 六、调试过程及实验结果 详细记录程序在调试过程中出现的问题及解决方法。 记录程序执行的结果。 七、总结 对上机实践结果进行分析，问题回答，上机的心得体会
14、及改进意见。 八、附录 源程序（核心代码）清单或使用说明书，可另附纸 贵州大学计算机科学与技术学院贵州大学计算机科学与技术学院 计算机科学与技术系上机实验报告计算机科学与技术系上机实验报告 课程名称：数据结构班级：计科 121实验日期：日期 姓名：学号：指导教师：程欣宇 实验序号：七实验成绩： 一、实验名称 图及其应用 二、实验目的及要求 1、熟悉图的两种常用存储形式：邻接矩阵、邻接表； 2、熟悉图的遍历算法； 3、熟悉出度、入度的求法； 4、掌握拓扑排序算法； 5、掌握关键路径求法。 三、实验环境 Visual C+ 四、实验内容 1、定义出图有向图和无向图两种数据类型； 2、实现有向图的邻
15、接矩阵和邻接表； 3、实现无向图的邻接矩阵和邻接表。 4、编写图的关键路径算法 五、算法描述及实验步骤 邻接矩阵是使用一个二维数组存储图的方式，其元素 cij记录顶点 Vi 和顶 点 Vj 的关联情况。 邻接链表使用一个顶点数组存储顶点信息，顶点数组中每条记录指向一条弧 链表，第 i 条链表纪录了所有从顶点 Vi 出去的弧的信息。 拓扑排序是讲一个偏序关系确定为一个全序关系的过程，其算法是使用一个 栈纪录当前入度为 0 的顶点，然后每次选择栈顶元素出栈和作相应调整，最后得 到的出栈顺序就是拓扑序。 在求关键路径中需要用到拓扑排序方式求得每个顶点的最早开始时间，对于 活动结束状态来说，然后规定整
16、个工程不能超过其最早开始时间，然后倒推得到 每个活动的最晚开始时间。最早开始时间等于最晚开始时间的活动就是关键活 动，由此得到关键路径。 实验步骤 1、输入顶点数量 n； 2、输入边的数量 m； 3、依次输入（一共 m 次）图的各边的顶点编号和权值：，同时修改 邻接矩阵的 aij或邻接链表的 ai； 4、按图的存储结构输出图（输出邻接矩阵或邻接链表） 。 5、建立图的邻接表 6、按拓扑排序的顺序，求出 ve、vl 数组 7、通过 ve、vl 求出 ee、el 8、通过 ee 和 el 求出关键活动 六、调试过程及实验结果 详细记录程序在调试过程中出现的问题及解决方法。 记录程序执行的结果。 七、总结 对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。 八、附录 源程序（核心代码）清单或使用说明书，可另附纸
