方白羽吉林大学
数据结构实验报告
班级： 姓名： 学号：
姓名 实验项目 实验性质 学号 第一次上机 □演示性实验□验证性实验 ?操作性实验□综合性实验 实验地点 计算机楼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-
