附件（四）深 圳 大 学 实 验 报 告 课程名称： 数据结构实验与课程设计 实验项目名称： 顺序表、链表、堆栈队列、串KMP算法 学院： 专业： 指导教师： 报告人： 学号： 班级： 实验时间： 实验报告提交时间： 教务处制一、 实验目的与完成说明：1. 简单介绍本实验的主要目的2. 说明你自己在本次实验中完成了第几项要求（必填）DS实验01-顺序表1. Problem A: DS顺序表-类实现目的： (1)实现顺序表的用C+语言和类实现顺序表(2)属性包括：数组、实际长度、最大长度（设定为1000）(3)操作包括：创建、插入、删除、查找要求：Input第1行先输入n表示有n个数据，即n是实际长度；接着输入n个数据（完成）第2行输入要插入的位置和新数据（完成）第3行输入要插入的位置和新数据（完成）第4行输入要删除的位置（完成）第5行输入要删除的位置（完成）第6行输入要查找的位置（完成）第7行输入要查找的位置（完成）Output第1行输出创建后的顺序表内容，包括顺序表实际长度和数据（完成）每成功执行一次操作（插入或删除），输出执行后的顺序表内容（完成）每成功执行一次查找，输出查找到的数据（完成）如果执行操作失败（包括插入、删除、查找等失败），输出字符串error，不必输出顺序表内容（完成）2. Problem B: 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. Problem C: DS顺序表-合并操作目的： (1)建立顺序表的类，属性包括：数组、实际长度、最大长度（设定为1000）(2)已知两个递增序列，把两个序列的数据合并到顺序表中，(3)并使得顺序表的数据递增有序。要求：Input第1行先输入n表示有n个数据，接着输入n个数据，表示第1个序列，要求数据递增互不等（完成）第2行先输入m表示有m个数据，接着输入m个数据，表示第2个序列，要求数据递增互不等（完成）Output顺序表内容包括顺序表的实际长度和数据，数据之间用空格隔开（完成）第1行输出创建后的顺序表内容（完成）DS实验02-链表1. Problem A: DS单链表-类实现目的：(1)用C+语言和类实现单链表，含头结点(2)属性包括：data数据域、next指针域(3)操作包括：插入、删除、查找(4)注意：单链表不是数组，所以位置从1开始对应首结点，头结点不放数据要求：Input第1行先输入n表示有n个数据，接着输入n个数据（完成）第2行输入要插入的位置和新数据（完成）第3行输入要插入的位置和新数据（完成）第4行输入要删除的位置（完成）第5行输入要删除的位置（完成）第6行输入要查找的位置（完成）第7行输入要查找的位置（完成）Output数据之间用空格隔开，（完成）第1行输出创建后的单链表的数据（完成）每成功执行一次操作（插入或删除），输出执行后的单链表数据（完成）每成功执行一次查找，输出查找到的数据（完成）如果执行操作失败（包括插入、删除、查找等失败），输出字符串error，不必输出单链表（完成）2. Problem B: DS单链表-结点交换目的：(1)用C+实现含头结点的单链表，然后实现单链表的两个结点交换位置。(2)注意不能简单交换两个结点包含数据，必须通过修改指针来实现两个结点的位置交换(3)交换函数定义可以参考：(4)swap（int pa, int pb) /pa和pb表示两个结点在单链表的位置序号(5)swap (ListNode * p, ListNode * q) /p和q表示指向两个结点的指针要求：Input第1行先输入n表示有n个数据，接着输入n个数据（完成）第2行输入要交换的两个结点位置（完成）第3行输入要交换的两个结点位置（完成）Output第一行输出单链表创建后的所有数据，数据之间用空格隔开（完成）第二行输出执行第1次交换操作后的单链表数据，数据之间用空格隔开（完成）第三行输出执行第2次交换操作后的单链表数据，数据之间用空格隔开（完成）如果发现输入位置不合法，输出字符串error，不必输出单链表（完成）3. Problem C: DS单链表-合并目的：(1)假定两个单链表是递增有序，定义并实现以下函数，完成两个单链表的合并，继续保持递增有序(2)int LL_merge(ListNode *La, ListNode *Lb)要求：Input第1行先输入n表示有n个数据，接着输入n个数据（完成）第2行先输入m表示有M个数据，接着输入m个数据（完成）Output输出合并后的单链表数据，数据之间用空格隔开（完成）4. Problem D: 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次方，表示为x3（完成）4.多项式的每个项之间用符号+连接，每个+两边加1个空格隔开（完成）DS实验03-堆栈与队列1. Problem A: DS堆栈-逆序输出（STL栈使用）目的：(1)C+中已经自带堆栈对象stack，无需编写堆栈操作的具体实现代码。(2)本题目主要帮助大家熟悉stack对象的使用，然后实现字符串的逆序输出(3)输入一个字符串，按字符按输入顺序压入堆栈，然后根据堆栈后进先出的特点，做逆序输出要求：Input第一行输入t，表示有t个测试实例（完成）第二起，每一行输入一个字符串，注意字符串不要包含空格（完成）Output每行逆序输出每一个字符串（完成）2. Problem B: DS线性表综合练习-队列之银行排队目的：(1)在银行营业大厅共服务3种客户，类型为ABC，大厅分别设置了3个窗口分别服务三种客户，即每个窗口只服务一种客户。现有一批客户来银行办理业务，每个客户都有类型和办理业务时间。每个窗口按照客户到来的顺序进行服务。要求：Input第一行输入先输入n表示客户数量（完成）第二行输入每个客户的类型，数据之间用用空格隔开（完成）第三行输入每个客户的办理时间，数据之间用用空格隔开（完成）Output第一行输出A类客户的平均办理时间（完成）第二行输出B类客户的平均办理时间（完成）第三行输出C类客户的平均办理时间（完成）3. Problem C: DS堆栈-行编辑目的：(1)使用C+的STL堆栈对象，编写程序实现行编辑功能。行编辑功能是：当输入#字符，则执行退格操作；如果无字符可退就不操作，不会报错(2)本程序默认不会显示#字符，所以连续输入多个#表示连续执行多次退格操作(3)每输入一行字符打回车则表示字符串结束(4)注意：必须使用堆栈实现，而且结果必须是正序输出要求：Input第一行输入一个整数t，表示有t行字符串要输入（完成）第二行起输入一行字符串，共输入t行（完成）Output每行输出最终处理后的结果，如果一行输入的字符串经过处理后没有字符输出，则直接输出NULL（完成）4. Problem D: 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 0 0.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. Problem E: DS堆栈-括号匹配目的：(1)处理表达式过程中需要对括号匹配进行检验，括号匹配包括三种：“(”和“)”，“”和“”，“”和“”。例如表达式中包含括号如下：()()()123456789101112(2)从上例可以看出第1和第2个括号匹配，第3和第10个括号匹配，4和5匹配，6和9匹配，7和8匹配，11和12