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