数据结构上机试验报告

吉林大学

数据结构实验报告

班级： 姓名： 学号：

姓名 实验项目 实验性质 学号 第一次上机 □演示性实验□验证性实验 ?操作性实验□综合性实验 实验地点 计算机楼A108 机器编号 2017年11月24日 时 指导教师 江丽 实验时间 分 一、实验目的及要求 题目1： 线性表、堆栈、队列相关算法的实验验证 [实验目的] 验证单链表及其上的基本操作。 [实验内容及要求] 1、 定义单链表类、链式栈类、顺序队列类。 2、 实验验证如下算法的正确性、各种功能及指标： 1）单链表插入操作：分别在当前结点后、表头、表尾插入值为x的结点； 2）单链表删除操作：分别删除表头结点、表尾结点和当前结点的后继结点； 3）查找操作：查找值为x的元素在单链表中出现的位置（是链表中的第几个元素）； 4）压栈和弹栈操作； 5）出队和入队操作（顺序存储） 3、 为便于观察程序的运行结果，设计的输出函数能在输出设备上以图形或表格或其它直观的形式输出计算结果。例如可将链表输出成如下形式： [1]?[2] ?[3] ?[4] ?[5] 4、 测试程序时，对所有输入变量取遍各种有代表性的值。 5、 为了增强程序的可读性，程序中要有适当的注释。 题目2（选做题）：应用单链表实现一元多项式及其相加。 [实验目的] 应用单链表解决实际应用问题。 实验内容及要求： 1、 使用自己已定义的单链表类。 2、 编写程序实现一元多项式的输入、输出和加法运算。 3、 为便于观察程序的运行结果，设计的输出函数能在输出设备上以图形或表格或其它直观的形式输出计算结果。 4、 为程序制定测试方案，对所有输入变量取遍各种有代表性的值。 5、 为了增强程序的可读性，程序中要有适当的注释。 二、实验设备、软件 PC，windows 10 Professional，VS2015 三、实验过程（算法设计、代码编写、程序调试、测试数据设计、测试、报告撰写） 基本数据结构选择及算法设计： 单链表类的使用，队列类的使用，栈类的使用。 1、单链表类 先定义结点类，包括数据类型定义和指向下一个节点的指针，同时定义指针p，其中p为头指针，为了让p在程序结束后时刻指回头指针，定义函数getHeadPoint（）。 构造函数设置表头指针为空。 析构函数用于清空链表，释放内存。 append（int element）函数为从尾部添加结点并保存数据element。 addasFirst(int element)函数为从头部添加结点并保存element。 addAfter(int element ,int location)函数从指定位置将元素生成节点添加链表，如 从链表第 location == 2个元素后，添加 element == 23 remove(int element)删除指定元素值大小的所有结点，判断是否存在。 printAll（）打印所有链表元素值 2、栈 实现较为简单，操作函数仅有两个，所以自己增加了难度使用类模板 结点类： 在结点中我加入了函数，使程序压栈更加快捷。StackNode(T Data, StackNode* p) p指向下一个指针。 栈类： 构造函数 Stack（）：top（NULL）{}；定义顶部节点为空。 析构函数~释放内存。 Push(const T & item)，压栈。调用结点类的构造函数。 Pop（），判断栈内是否还有元素，弹栈。 Clear（），手动清空，类似析构函数。 IsEmpty（），判断头指针是否为空。 3、队列 有了前两次的调试，第三次应用很顺利，使用类模板。队列定义结点类和定义类 结点构造函数为next为空。 队列类： 其中定义头指针first和尾指针rear。 构造函数定义顶部节点为空。 析构函数~释放内存。 Push（）判断添加的结点是否为第一个，第一个单独添加。 Pop()判断删除的节点是否为最后一个，最后一个输出出队失败。 4、多项式 使用单链表代码 ，将链表结点改为多项式结点，数据存放分别为指数和系数，改造完成后重新编写多项式创建代码。插入部分大多沿用链表中的算法，在此仅对加法作出解释。 AP1.[判断空] IF pa = NULL AND pb = NULL RETURN. AP2.[加法] IFpa->expn < pb->expnTHEN((s = pa AND pc->next = pa.) IFpa->expn > pb->expnTHEN(s = pb AND pc->next = pb.) ELSE( IF pa->coef + pb->coef != 0THEN tc->next = new node) AP3.[未扫描完的余下结点复制并链接到pc单链表之后] IF pa != NULL THEN p<-pa ELSE p-next = new node RETURN pc. 代码编写（仅填写关键代码）： 单链表部分： //逐个添加链表元素， 尾部添加 void append(intelement); //从首部添加链表元素 void addasFirst(intelement); //从指定位置将元素生成节点添加链表，如 从链表第 location == 2个元素后，添加 element == 23 void addAfter(intelement, intlocation); //删除指定链表元素值大小的所有结点 void remove(intelement); //返回表头指针 node * getHeadPoint(); //打印所有链表元素值 void printAll(); 栈部分： T Pop() void Push(constT&item) void Clear(void) int IsEmpty(void) const 队列部分： void initSqueue(Squeue *); void emptySqueue(Squeue *); void fullSqueue(Squeue *); void Insqueue(Squeue *, int); void Outsqueue(Squeue *, int *); void PrintSqueue(Squeue *); 多项式部分关键代码： void InitList(PolyNode *&L) //初始化多项式单链表，生成一个头结点 void InsertNode(PolyNode *&L, floatc, inte, inti) //在多项式链表的第i个位置插入结点 void print(PolyNode *L) //打印多项式 void CreateList(PolyNode *&L, floatC[], intE[], intn) //创建多项式单链表 PolyNode *AddPoly(PolyNode *L1, PolyNode *L2) //一元多项式相加 程序调试过程记录： 1、从结尾添加结点，忘记了返回头指针，导致接下来的程序不能运行。 2、删除结点时，对于重复结点欠考虑，导致了很严重的问题。包括：删不了头，删不了两个头，当两个重复节点相邻时，只能删除一个，都是逻辑问题。在第一次运行时均没有发现。后来单独写了删除头结点的代码并判断，删除重复节点后直接执行下按一次循环（continue），解决了这些问题。 3、发现只有逻辑删除没有物理删除，又在加入了delete。 4.多项式创建出现问题，重新调整类的结构，定义了不同的数组。 测试数据设计：

单链表： 创建链表，用头、尾、选择插入各个方法依次插入并输出检测。 删除时，删除：不存在的一个数，头，双头，中间，双中间，尾，双尾。（双意思是重复的数据） 充分考虑到这些问题。依次测试。 栈： 测试压栈 。 弹栈。 弹空栈。 队列： 测试入队。 出队。 出空队. 多项式： 测试多项式的创建和加法 测试结果记录： 单链表： 栈： 队列： 多项式： 实验过程总结（对所作程序进行分析、评价运行效果，总结遇到的问题和解决办法）： 删除结点时，在尾节点删除会经常遇到指针空导致程序崩溃。现在在对尾结点进行操作的时候，多了保护指针。 姓名 实验项目 胡锐 学号 54160317 第二次上机 □演示性实验□验证性实验 实验性质 ?操作性实验□综合性实验 实验地点 计算机楼A108 机器编号 2017年 12 月 1 日 时 指导教师 江丽 实验时间 分 一、实验目的及要求 题目1：二叉树相关算法的实验验证 1）从文件创建一棵二叉树， 2）先根、中根、后根遍历二叉树； 3）在二叉树中搜索给定结点的父结点； 4）搜索二叉树中符合数据域条件的结点； 5）从二叉树中删除给定结点及其左右子树。 题目2（选作）：森林的遍历算法的实验验证 1）创建森林； 2）森林的先根遍历的递归和迭代算法； 3）森林的后根遍历的递归和迭代算法； 4）森林的层次遍历算法。 二、实验设备、软件 PC，windows 10 Professional，VS2015 三、实验过程（算法设计、代码编写、程序调试、测试数据设计、测试、报告撰写） 基本数据结构选择及算法设计： 1、在二叉树中搜索给定节点的父节点 Father1.[t=NULL?] IF t =NULL THEN (q <-NULL. RETURN.) Father2.[t为所求？] IF Left(t) = p OR Right(t) = p THEN(q<-t.RETURN.) Father3.[递归] Father(Left(t),p. qL) IF qL!=NULL THEN(q <-qL.RETURN.) ELSE Father(Right(t),p. qR.RETURN.) 2、搜索二叉树中符合数据域条件的节点（递归） 3、从二叉树中删除给定结点及其左右子树 DST1.[t=NULL?] IF t =NULL THEN ( RETURN.) IFData（t）= item THEN (q <-t. RETURN.) DST2.[t=root?] IF t=rootTHEN(Del（t）.root<- NULL. RETURN) Find(Right(t),item. p) RETURN. DST3.[找t的父节点q] p<-t.Father(root.p. q) DST4.[修改q的指针域] IFLeft（q）= p THEN Left（q）q =NULL. IFRight（q）= p THEN Right（q）q =NULL. DST5.[删除p及其子树] Del（p）. 3、删除结点p及其左右子树 （递归） 5、先根遍历算法（递归） 6、中根遍历算法（递归） 7、后根遍历算法（递归） 8、创建二叉树 CBT1.[读数据] ifstream fin(\); CBT2.[p=stop?] IF p=stopTHEN(t =NULL. RETURN t.) CBT3.[构造左子树] CBT(Left(t)). CBT4.[构造右子树] CBT(Right(t)). 代码编写（仅填写关键代码）： ? 题目1 //先根遍历并输出以节点t为根节点的子树 void PreOrder(BinTreeNode *t) //中根遍历并输出以节点t为根节点的子树 void InOrder(BinTreeNode *t) //后根遍历并输出以节点t为根节点的子树 void PostOrder(BinTreeNode *t) BinTreeNode*BinTree::Create() //找到父节点 BinTreeNode * Father(BinTreeNode *t, BinTreeNode *p) //寻找结点 BinTreeNode *Find(BinTreeNode *t, constT&item) ? 题目2

程序调试过程记录： 1、文件输入出错。 输入值为12453.然而过程中跳过了第一个数，意识到是指针出了问题。以下是错误代码和运行结果，其中第一位1并未输入到数组s中。 while ((fin.get())!= EOF) {fin >> s[i];i++;} 更改了操作顺序，使用了do while。 更改后： do{fin >> s[i]; i++; }while ((fin.get()) != EOF) 测试成功 测试数据设计： 构建一棵二叉树如图所示： 构建好之后先根中根后根遍历输出。 中间两个地址是先取某一个点的地址，然后寻找他孩子节点的父节点，测试父节点寻找函数，地址相同证明寻找正确。 删除2及其子树后，二叉树仅剩下13，输出正确。 测试结果记录： 实验过程总结（对所作程序进行分析、评价运行效果，总结遇到的问题和解决办法）： 题目1： 程序运行比较稳定，功能基本实现。 题目2： 功能基本实现。 遇到的问题及解决办法见调试经过记录。 姓名 实验项目 胡锐 学号 54160317 第三次上机 □演示性实验□验证性实验 实验性质 ?操作性实验□综合性实验 实验地点 计算机楼A108 机器编号 2017年 12 月 1 日 时 指导教师 江丽 实验时间 分 一、实验目的及要求 题目1：邻接矩阵存储的图及相关算法的实验验证 实验验证如下算法的正确性、各种功能及指标： 1）创建一个邻接矩阵存储的图； 2）返回图中指定边的权值； 3）查找图中某顶点的所有邻接顶点； 4）图的深度优先遍历； 题目2 邻接表存储的图相关算法的实验验证 1）创建一个邻接表存储的图； 2）返回图中指定边的权值； 3）插入操作：向图中插入一个顶点，插入一条边； 4）删除操作：从图中删除一个顶点，删除一条边； 6）图的广度优先遍历； 7）基于迪杰斯特拉算法求最短路径。【选做题】 二、实验设备、软件 PC，windows 10 Professional，VS2015 三、实验过程（算法设计、代码编写、程序调试、测试数据设计、测试、报告撰写） 基本数据结构选择及算法设计： 题一、 图形结构，链式栈结构。 深度优先遍历中采用一个堆栈S来存储访问过程，使用迭代算法。当顶点进栈后，visited【v】置1，初始时，其实顶点v0入栈，其对应的迭代过程如下： （1）检测栈是否为空。若空，结束。 （2）栈中弹出一个顶点v，访问v （3）将v未被访问的邻接顶点压入栈，并置1 （4）执行（1） 题二、 图形结构，队列结构。 广度优先遍历中采用一个队列来存储访问过程，使用迭代算法。当顶点出队后，visited【v】置1，初始时，其实顶点v0入队，其对应的迭代过程如下： （1）检测队列是否为空，空，结束 （2）初始化后入队第一个元素 （3）从队中弹出一个结点，访问 （4）执行（1） 代码编写（仅填写关键代码）： ? 题目1 int GetNextNeighbor(constintv1, constintv2) int GetWeight(constint&v1, constint&v2) int GetFirstNeighbor(constintv) void DFS_self(constintv ) ? 题目2 //权重 //得到第一个 int getweight(constint&v1, constint&v2); int getfirstneighbor(constintv); int getnextneighbor(constintv1, constintv2);//查找图中某顶点的所有邻接顶点 void insterVertex(constint&v); //添加顶点 void insterEdge(constintv1, constintv2, intweight);//添加边 void deleteVertex(constint&v); //删除顶点 //删除边 //删除边 //广度优先 void deleteEdge(constintv1, constintv2); void deleteEdge1(constintv1, constintv2); void BFS(constints); void DShortestPath(constintv); void print(); //最短路径问题 //输出图 程序调试过程记录： 1、大多按照书上内容调试，整体过程程序均可以运行，析构函数运行时会出现指针置空，编译器会调整好，不影响程序运行 测试数据设计： 一、构建一个图： 然后测试11,01,03,之间的权值为 0,1,1.并且以3为起点遍历为3201，结果正常。 二、构建一个图： 结果记录： 实验一： 实验二：

本文来源：https://www.bwwdw.com/article/zlh8.html