顺序表链表KMP实验报告hdze.docx

附件（四）深 圳 大 学 实 验 报 告 课程名称： 数据结构实验与课程设计 实验项目名称： 顺序表、链表、堆栈队列、串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表示要转换的数制，1<k<=16（完成）Output对于每一组测试数据，每行输出转换后的结果，结果精度到小数点后3位（完成）5. Problem E: 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. Problem F: DS线性表综合练习-组队列目的：(1)组队列是队列结构中一种常见的队列结构，在很多地方有着广泛应用。组队列是是指队列内的元素分组聚集在一起。组队列包含两种命令：1、 ENQUEUE，表示当有新的元素进入队列，首先会检索是否有同一组的元素已经存在，如果有，则新元素排在同组的最后，如果没有则插入队列末尾。2、 DEQUEUE，表示队列头元素出队3、 STOP，停止操作(2)建议使用C+自带的队列对象queue，编程更方便要求：Input第1行输入一个t(t<=10)，表示1个队列中有多少个组（完成）第2行输入一个第1组的元素个数和数值第3行输入一个第2组的元素个数和数值，（完成但不严谨）以此类推输入完n组之后，开始输入多个操作命令(<200)，例如输入ENQUEUE 100，表示把元素100插入队列（完成）最后输入STOP，表示输入命令结束（完成）Output经过命令操作后队列的最终结果（完成）7. Problem G: DS堆栈-表达式计算目的：(1)计算一个表达式的运算结果(2)使用C+自带stack堆栈对象来实现(3)参考课本的伪代码，把伪代码改造成可运行的代码要求：Input第一个输入t，表示有t个实例（完成）第二行起，每行输入一个表达式，每个表达式末尾带#表示结束（完成）输入t行Output每行输出一个表达式的计算结果，计算结果用浮点数（含4位小数）的格式表示（完成）8. Problem H: DS堆栈-迷宫求解目的：(1)给出一个N*N的迷宫矩阵示意图，从起点0,0出发，寻找路径到达终点N-1, N-1。(2)要求使用堆栈对象来实现，具体算法参考课本3.2.4节51页。要求：Input第一行输入t，表示有t个迷宫（完成）第二行输入n，表示第一个迷宫有n行n列（完成）第三行起，输入迷宫每一行的每个方格的状态，0表示可通过，1表示不可通过输入n行（完成）以此类推输入下一个迷宫Output逐个输出迷宫的路径（完成）如果迷宫不存在路径，则输出no path并回车（完成）如果迷宫存在路径，将路径中每个方格的x和y坐标输出，从起点到终点，每输出四个方格就换行，最终以单词END结尾（完成）DS实验04-串应用KMP算法1. Problem A: DS串应用-KMP算法目的：(1) 学习KMP算法，给出主串和模式串，求模式串在主串的位置要求：Input第一个输入t，表示有t个实例（完成）第二行输入第1个实例的主串，第三行输入第1个实例的模式串（完成）以此类推Output第一行输出第1个实例的模式串的next值（完成）第二行输出第1个实例的匹配位置，位置从1开始计算，如果匹配成功输出位置，匹配失败输出0（完成）以此类推二、主要思路与方法：1. 对于本次实验，说明你认为最重要的函数、算法或知识点，并谈谈你对它们的理解DS实验01-顺序表1. Problem A: DS顺序表-类实现函数：list_insert(int i,int item);插入函数一维数组需要把插入点后的数据往后推一格再给插入点赋值。所耗时间比链表久。list_del(int i)删除函数将删除点后点数据前推一格覆盖删除点。所耗时间比链表久。list_get(int i)返回指定值函数比链表快。2. Problem B: DS顺序表-连续操作同Problem A: DS顺序表-类实现。使用for循环以及插入函数。3. Problem C: DS顺序表-合并操作合并操作：两个线性表，分别读取数字，比较两数字大小，小的先插入第三个线性表，一直读到其中一个线性表到底跳出循环，将另一条线性表里剩余的数字全都插在第三个线性表后。DS实验02-链表1. Problem A: DS单链表-类实现函数：LL_insert(int i,int item);插入函数。调整指针指向即可插入。比顺序表快。LL_get(int i);返回值函数。遍历到指定结点后输出。比顺序表慢。LL_del(int i);删除函数。调整指针指向，释放结点或放置另一条链表中回收利用。2. Problem B: DS单链表-结点交换改变指针进行交换：a_pNexb_pNexaa_pPrebb_pPrea_pNexaa_pPreb_pNexbb_pPre改变数值进行交换：int LinkList:swap(ListNode *p,ListNode *q) if(p=head|q=head|!p|!q)return error; int temp;temp=p->data;p->data=q->data;q->data=temp; return ok; 3. Problem C: DS单链表-合并 过程基本与线性表合并相同。不同的是需要调整指针。4. Problem D: DS线性表-多项式相加线性表实现： 建立两个数组分别存储系数和指数。多项式相加的操作过程基本与合并相似。先比较指数，若指数较小就插在最左边，若指数相等则相加再插入。一条多项式插完后另一条多项式剩余系数指数插在右边。链表实现：Status MakeNode(Link& p,ElemType e,ElemType e1);分配一个结点Status CreatPolyn(polynomai &P,Link& p);将结点插入多项式中。插入过程中比较指数大小按由小到大的顺序插在相应的位置里，如果有相同指数的则系数相加（系数可为正负），若系数为0则调用删除函数删除该结点。Status AddPolyn(polynomai &Pa,polynomai &Pb,polynomai &Pc);多项式相加。比线性表要简单，直接把Pa，Pb里的系数跟指数创建一个结点放入多项式Pc中即可，相加直接在加入的时候完成。DS实验03-堆栈与队列1. Problem A: DS堆栈-逆序输出（STL栈使用）建立一个栈，将数值push()进栈后用top()返回值并pop()弹出值逆向输出。2. Problem B: DS线性表综合练习-队列之银行排队建立两个队列，一个为<int>，另一个为<char>，用于存储时间和字符，在一个个用front()取值并用pop()弹出，用判断语句进行平均数求值。3. Problem C: DS堆栈-行编辑建立两个栈，用其中一个栈存储string数组的每一个字符。先判断是否为#号且有多少个#号，若没有#号则push()字符进第二个栈，有多少个#号就pop()多少个。全程判断栈是否为空。最后判断第二个栈是否为空，不为空就输出字符串，为空就输出NULL。4. Problem D: DS线性表综合练习-数制转换Push数值与进制数的余数进栈然后逆向输出。Push数值与2的倍数取整进栈然后逆向输出。5. Problem E: DS堆栈-括号匹配若栈为空时下一个就是右括号直接括号不匹配。若是左括号则进栈。一直进左括号知道有右括号出现。若右括号与top()匹配则pop()。若括号匹配则栈为空。6. Problem F: DS线性表综合练习-组队列建立队列数组，同组的元素进入同一个队列中。7. Problem G: DS堆栈-表达式计算使用OPTR栈存储运算符，使用OPND栈存储数字。OPTR先PUSH入#号，输入表达式时最后一位为#号，在c= =OPTR.top()= =#的时候结束表达式计算。读入字符的过程中不断有运算符和数字进栈，直到两个运算符遭遇的时候，判断栈内top()运算符与c内运算符的优先级，即表达式中前一个运算符与后一个运算符的优先级。如果是小于，则直接让c进OPTR栈，再读入下一个字符；如果是大于，则OPTR弹出一个运算符，OPND弹出两个数字进行计算求值重新放回OPND栈；如果是等于则OPTR出栈消除括号。只有左括号和右括号以及两个#号的优先级为等于号。而右括号出现的时候左括号以后的运算符都已计算并变成数字进入了OPND栈，所以右括号出现时候OPTR.pop()弹出的必然是左括号。最后OPND会剩下最后一个数字即结果。函数： Strcat(char,char)在字符串后面加字符。8. Problem H: DS堆栈-迷宫求解建立一个类CPOS，对象分别是xp,yp作为坐标。建立存储类型为类的栈stack<CPOS>。从起点开始如果右边能走优先往右。直到右边不能走了就往下，如果右边和下边都不能走就pop（），同时刚刚的坐标上直接标记无法通行（1），然后判断下边能不能走。坐标轴到达了右下角即成功，如果最后pop（）到栈内没有元素了的话就说明没有路径。DS实验04-串应用KMP算法1. Problem A: DS串应用-KMP算法nextj： ：第一为0的作用是让子串向右移动一格，此时i会变。 ：1的作用是子串换成第一个字符再进行比较，此时i不会变。 ：j取nextj的时候i不变。 ：如果一直没有匹配到，j一直为1，nextj一直为0。如果有匹配到j就会大于1； ：子串有j个字符，则next中用到的只有前j个。 ：nextj大于0时候表示调用第nextj个位置的字符与mainstri匹配。三实验程序或内容：1. 针对每一项实验要求，给出编写的代码，2. 可以粘贴全部代码，或者可以只粘贴重要的代码（为了节省纸张），但代码必须完整，至少是完整的函数。3. 代码符合以下要求，评分更高：a. 排版整齐，可读性高b. 代码有注释，越详细越清晰越好DS实验01-顺序表1. Problem A: DS顺序表-类实现#include<iostream> using namespace std; #define ok 0 #define error -1 /顺序表类定义 class SeqList private: int *list; int maxsize; int size; public: SeqList(); SeqList(); int list_size(); int list_insert(int i,int item); int list_del(int i); int list_get(int i); void list_display(); ; /构造函数SeqList:SeqList() maxsize=1000; size=0; list=new intmaxsize; /析构函数SeqList:SeqList() deletelist; /返回长度int SeqList:list_size() return size; /插入函数int SeqList:list_insert(int i,int item) if(i>size+1|i<0|size=maxsize)return error; if(i=size+1) listi-1=item; size+; return ok; int j; for(j=size;j>i-1;j-) listj=listj-1; listj=item; size+; return ok; /删除函数int SeqList:list_del(int i) if(i>size|i<0|size=0)return error; int j; for(j=i-1;j<size-1;j+) listj=listj+1; size-; return ok; /返回值函数int SeqList:list_get(int i) if(i<=0|i>size)return error; return listi-1; /输出函数void SeqList:list_display() int j; for(j=0;j<size;j+) cout<<listj<<" " cout<<endl; int main() int n,i,NUM,position; SeqList L; /第1行先输入n表示有n个数据，即n是实际长度；接着输入n个数据 cin>>n; for(i=0;i<n;i+) cin>>NUM; L.list_insert(i+1,NUM); cout<<L.list_size()<<" " L.list_display(); /第2行输入要插入的位置和新数据 cin>>position>>NUM; if(L.list_insert(position,NUM)=-1)cout<<"error"<<endl; else cout<<L.list_size()<<" " L.list_display(); /第3行输入要插入的位置和新数据 cin>>position>>NUM; if(L.list_insert(position,NUM)=-1)cout<<"error"<<endl; else cout<<L.list_size()<<" " L.list_display(); /第4行输入要删除的位置 cin>>position; if(L.list_del(position)=-1)cout<<"error"<<endl; else cout<<L.list_size()<<" " L.list_display(); /第5行输入要删除的位置 cin>>position; if(L.list_del(position)=-1)cout<<"error"<<endl; else cout<<L.list_size()<<" " L.list_display(); /第6行输入要查找的位置 cin>>position; if(L.list_get(position)=-1)cout<<"error"<<endl; else cout<<L.list_get(position)<<endl; /第7行输入要查找的位置 cin>>position; if(L.list_get(position)=-1)cout<<"error"<<endl; else cout<<L.list_get(position)<<endl; return 0; 2.Problem B: DS顺序表-连续操作#include<iostream> using namespace std; #define ok 0 #define error -1 /顺序表类定义 class SeqList private: int *list; int maxsize; int size; public: SeqList(); SeqList(); int list_size(); int list_insert(int i,int item); int list_del(int i); int list_get(int i); void list_display(); ; /构造函数SeqList:SeqList() maxsize=1000; size=0; list=new intmaxsize; /析构函数SeqList:SeqList() deletelist; /返回长度int SeqList:list_size() return size; /插入函数int SeqList:list_insert(int i,int item) if(i>size+1|i<0|size=maxsize)return error; if(i=size+1) listi-1=item; size+; return ok; int j; for(j=size;j>i-1;j-) listj=listj-1; listj=item; size+; return ok; /删除函数int SeqList:list_del(int i) if(i>size|i<0|size=0)return error; int j; for(j=i-1;j<size-1;j+) listj=listj+1; size-; return ok; /返回值函数int SeqList:list_get(int i) if(i<=0|i>size)return error; return listi-1; /输出函数void SeqList:list_display() int j; for(j=0;j<size;j+) cout<<listj<<" " cout<<endl; int main() int n,i,NUM,k,j; SeqList L; /第1行先输入n表示有n个数据，即n是实际长度；接着输入n个数据 cin>>n; for(j=0;j<n;j+) cin>>NUM; L.list_insert(j+1,NUM); cout<<L.list_size()<<" " L.list_display(); /第2行先输入i表示插入开始的位置，再输入k表示有k个插入数据，接着输入k个数据 cin>>i>>k; for(j=0;j<k;j+) cin>>NUM; L.list_insert(i+,NUM); cout<<L.list_size()<<" " L.list_display(); /第3行先输入i表示删除开始的位置，再输入k表示要删除k个数据 cin>>i>>k; for(j=0;j<k;j+) L.list_del(i); cout<<L.list_size()<<" " L.list_display(); return 0; 3. Problem C: DS顺序表-合并操作#include<iostream> using namespace std; #define ok 0 #define error -1 /顺序表类定义 class SeqList private: int *list; int maxsize; int size; public: SeqList(); SeqList(); int list_size(); int list_insert(int i,int item); int list_del(int i); int list_get(int i); void list_display(); ; /构造函数SeqList:SeqList() maxsize=1000