搜索
附件（四）深圳大学实验报告课程名称：数据结构实验与课程设计实验项目名称：顺序表、链表、堆栈队列、串KMP算法学院：专业：指导教师：报告人：学号：班级：实验时间：实验报告提交时间：教务处制一、实验目的与完成说明：1.简单介绍本实验的主要目的2.说明你自己在本次实验中完成了第几项要求（必填）DS实验01--顺序表1.ProblemA:DS顺序表--类实现目的：(1)实现顺序表的用C++语言和类实现顺序表(2)属性包括：数组、实际长度、最大长度（设定为1000）(3)操作包括：创建、插入、删除、查找要求：Input第1行先输入n表示有n个数据，即n是实际长度；接着输入n个数据（完成）第2行输入要插入的位置和新数据（完成）第3行输入要插入的位置和新数据（完成）第4行输入要删除的位置（完成）第5行输入要删除的位置（完成）第6行输入要查找的位置（完成）第7行输入要查找的位置（完成）Output第1行输出创建后的顺序表内容，包括顺序表实际长度和数据（完成）每成功执行一次操作（插入或删除），输出执行后的顺序表内容（完成）每成功执行一次查找，输出查找到的数据（完成）如果执行操作失败（包括插入、删除、查找等失败），输出字符串error，不必输出顺序表内容（完成）2.ProblemB:DS顺序表--连续操作目的：(1)建立顺序表的类，属性包括：数组、实际长度、最大长度（设定为1000）(2)实现连续多个插入，即从位置i开始插入多个数据(3)实现连续多个删除，即从位置i开始删除多个数据要求：Input第1行先输入n表示有n个数据，即n是实际长度；接着输入n个数据（完成）第2行先输入i表示插入开始的位置，再输入k表示有k个插入数据，接着输入k个数据（完成）第3行先输入i表示删除开始的位置，再输入k表示要删除k个数据（完成）Output顺序表内容包括顺序表的实际长度和数据，数据之间用空格隔开（完成）第1行输出创建后的顺序表内容（完成）第2行输出执行连续插入后的顺序表内容（完成）第3行输出执行连续删除后的顺序表内容（完成）3.ProblemC:DS顺序表--合并操作目的：(1)建立顺序表的类，属性包括：数组、实际长度、最大长度（设定为1000）(2)已知两个递增序列，把两个序列的数据合并到顺序表中，(3)并使得顺序表的数据递增有序。要求：Input第1行先输入n表示有n个数据，接着输入n个数据，表示第1个序列，要求数据递增互不等（完成）第2行先输入m表示有m个数据，接着输入m个数据，表示第2个序列，要求数据递增互不等（完成）Output顺序表内容包括顺序表的实际长度和数据，数据之间用空格隔开（完成）第1行输出创建后的顺序表内容（完成）DS实验02--链表1.ProblemA:DS单链表--类实现目的：(1)用C++语言和类实现单链表，含头结点(2)属性包括：data数据域、next指针域(3)操作包括：插入、删除、查找(4)注意：单链表不是数组，所以位置从1开始对应首结点，头结点不放数据要求：Input第1行先输入n表示有n个数据，接着输入n个数据（完成）第2行输入要插入的位置和新数据（完成）第3行输入要插入的位置和新数据（完成）第4行输入要删除的位置（完成）第5行输入要删除的位置（完成）第6行输入要查找的位置（完成）第7行输入要查找的位置（完成）Output数据之间用空格隔开，（完成）第1行输出创建后的单链表的数据（完成）每成功执行一次操作（插入或删除），输出执行后的单链表数据（完成）每成功执行一次查找，输出查找到的数据（完成）如果执行操作失败（包括插入、删除、查找等失败），输出字符串error，不必输出单链表（完成）2.ProblemB:DS单链表--结点交换目的：(1)用C++实现含头结点的单链表，然后实现单链表的两个结点交换位置。(2)注意不能简单交换两个结点包含数据，必须通过修改指针来实现两个结点的位置交换(3)交换函数定义可以参考：(4)swap（intpa,intpb)//pa和pb表示两个结点在单链表的位置序号(5)swap(ListNode*p,ListNode*q)//p和q表示指向两个结点的指针要求：Input第1行先输入n表示有n个数据，接着输入n个数据（完成）第2行输入要交换的两个结点位置（完成）第3行输入要交换的两个结点位置（完成）Output第一行输出单链表创建后的所有数据，数据之间用空格隔开（完成）第二行输出执行第1次交换操作后的单链表数据，数据之间用空格隔开（完成）第三行输出执行第2次交换操作后的单链表数据，数据之间用空格隔开（完成）如果发现输入位置不合法，输出字符串error，不必输出单链表（完成）3.ProblemC:DS单链表--合并目的：(1)假定两个单链表是递增有序，定义并实现以下函数，完成两个单链表的合并，继续保持递增有序(2)intLL_merge(ListNode*La,ListNode*Lb)要求：Input第1行先输入n表示有n个数据，接着输入n个数据（完成）第2行先输入m表示有M个数据，接着输入m个数据（完成）Output输出合并后的单链表数据，数据之间用空格隔开（完成）4.ProblemD:DS线性表--多项式相加目的：(1)对于一元多项式p(x)=p0+p1x+p2x2+…+pnxn，每个项都有系数和指数两部分，例如p2x2的系数为p2,指数为2(2)编程实现两个多项式的相加例如5+x+2x2+3x3，-5-x+6x2+4x4，两者相加结果：8x2+3x3+4x4(3)其中系数5和-5都是x的0次方的系数，相加后为0，所以不显示。x的1次方同理不显示。(4)可用顺序表或单链表实现要求：Input第1行：输入t表示有t组测试数据（完成）第2行：输入n表示有第1组的第1个多项式包含n个项（完成）第3行：输入第一项的系数和指数，以此类推输入n行（完成）接着输入m表示第1组的第2个多项式包含m项（完成）同理输入第2个多项式的m个项的系数和指数（完成）参考上面输入第2组数据，以此类推输入t组（完成）假设所有数据都是整数（完成）Output对于每1组数据，先用两行输出两个原来的多项式，再用一行输出运算结果，不必考虑结果全为0的情况（完成）输出格式参考样本数据，格式要求包括：1.如果指数或系数是负数，用小括号括起来（完成）2.如果系数为0，则该项不用输出（完成）3.如果指数不为0，则用符号^表示，例如x的3次方，表示为x^3（完成）4.多项式的每个项之间用符号+连接，每个+两边加1个空格隔开（完成）DS实验03--堆栈与队列1.ProblemA:DS堆栈--逆序输出（STL栈使用）目的：(1)C++中已经自带堆栈对象stack，无需编写堆栈操作的具体实现代码。(2)本题目主要帮助大家熟悉stack对象的使用，然后实现字符串的逆序输出(3)输入一个字符串，按字符按输入顺序压入堆栈，然后根据堆栈后进先出的特点，做逆序输出要求：Input第一行输入t，表示有t个测试实例（完成）第二起，每一行输入一个字符串，注意字符串不要包含空格（完成）Output每行逆序输出每一个字符串（完成）2.ProblemB:DS线性表综合练习--队列之银行排队目的：(1)在银行营业大厅共服务3种客户，类型为A\B\C，大厅分别设置了3个窗口分别服务三种客户，即每个窗口只服务一种客户。现有一批客户来银行办理业务，每个客户都有类型和办理业务时间。每个窗口按照客户到来的顺序进行服务。要求：Input第一行输入先输入n表示客户数量（完成）第二行输入每个客户的类型，数据之间用用空格隔开（完成）第三行输入每个客户的办理时间，数据之间用用空格隔开（完成）Output第一行输出A类客户的平均办理时间（完成）第二行输出B类客户的平均办理时间（完成）第三行输出C类客户的平均办理时间（完成）3.ProblemC:DS堆栈--行编辑目的：(1)使用C++的STL堆栈对象，编写程序实现行编辑功能。行编辑功能是：当输入#字符，则执行退格操作；如果无字符可退就不操作，不会报错(2)本程序默认不会显示#字符，所以连续输入多个#表示连续执行多次退格操作(3)每输入一行字符打回车则表示字符串结束(4)注意：必须使用堆栈实现，而且结果必须是正序输出要求：Input第一行输入一个整数t，表示有t行字符串要输入（完成）第二行起输入一行字符串，共输入t行（完成）Output每行输出最终处理后的结果，如果一行输入的字符串经过处理后没有字符输出，则直接输出NULL（完成）4.ProblemD:DS线性表综合练习--数制转换目的：(1)对于任意十进制数转换为k进制，包括整数部分和小数部分转换。整数部分采用除k求余法，小数部分采用乘k取整法例如x=19.125，求2进制转换整数部分19，小数部分0.12519/2=9…10.125*2=0.25…09/2=4…10.25*2=0.5…04/2=2…00.5*2=1…12/2=1…01/2=0…1(2)所以整数部分转为10011，小数部分转为0.001，合起来为10011.001(3)提示整数部分可用堆栈，小数部分可用队列实现(4)注意：必须按照上述方法来实现数制转换，其他方法0分要求：Input第一行输入一个t，表示下面将有t组测试数据。（完成）接下来每行包含两个参数n和k，n表示要转换的数值，可能是非整数；k表示要转换的数制，1k=16（完成）Output对于每一组测试数据，每行输出转换后的结果，结果精度到小数点后3位（完成）5.ProblemE:DS堆栈--括号匹配目的：(1)处理表达式过程中需要对括号匹配进行检验，括号匹配包括三种：“(”和“)”，“[”和“]”，“{”和“}”。例如表达式中包含括号如下：()[()([])]{}123456789101112(2)从上例可以看出第1和第2个括号匹配，第3和第10个括号匹配，4和5匹配，6和9匹配，7和8匹配，11和12匹配。从中可以看到括号嵌套的的情况是比较复杂的，使用堆栈可以很方便的处理这种括号匹配检验，可以遵循以下规则：1、当接收第1个左括号，表示新的一组匹配检查开始；随后如果连续接收到左括号，则不断进堆栈。2、当接受第1个右括号，则和最新进栈的左括号进行匹配，表示嵌套中1组括号已经匹配消除3、若到最后，括号不能完全匹配，则说明输入的表达式有错(3)建议使用C++自带的stack对象来实现要求：Input第一行输入一个t，表示下面将有t组测试数据。接下来的t行的每行输入一个表达式，表达式只考虑英文半角状态输入，无需考虑中文全角输入（完成）Output对于每一行的表达式，检查括号是否匹配，匹配则输入ok，不匹配则输出error（完成）6.ProblemF:DS线性表综合练习--组队列目的：(1)组队列是队列结构中一种常见的队列结构，在很多地方有着广泛应用。组队列是是指队列内的元素分组聚集在一起。组队列包含两种命令：1、ENQUEUE，表示当有新的元素进入队列，首先会检索是否有同一组的元素已经存在，如果有，则新元素排在同组的最后，如果没有则插入队列末尾。2、DEQUEUE，表示队列头元素出队3、STOP，停止操作(2)建议使用C++自带的队列对象queue，编程更方便要求：Input第1行输入一个t(t=10)，表示1个队列中有多少个组（完成）第2行输入一个第1组的元素个数和数值第3行输入一个第2组的元素个数和数值，（完成但不严谨）以此类推输入完n组之后，开始输入多个操作命令(200)，例如输入ENQUEUE100，表示把元素100插入队列（完成）最后输入STOP，表示输入命令结束（完成）Output经过命令操作后队列的最终结果（完成）7.ProblemG:DS堆栈--表达式计算目的：(1)计算一个表达式的运算结果(2)使用C++自带stack堆栈对象来实现(3)参考课本的伪代码，把伪代码改造成可运行的代码要求：Input第一个输入t，表示有t个实例（完成）第二行起，每行输入一个表达式，每个表达式末尾带#表示结束（完成）输入t行Output每行输出一个表达式的计