《顺序表链表KMP实验报告44871.docx》由会员分享，可在线阅读，更多相关《顺序表链表KMP实验报告44871.docx（148页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、附件（四）深 圳 大 学 实 验 报 告 课课程名称： 数据结结构实验与课课程设计 实实验项目名称称： 顺序表、链链表、堆栈队队列、串KMMP算法 学院： 专专业： 指指导教师： 报报告人： 学号： 班级： 实实验时间： 实实验报告提交交时间： 教务处制一、 实验目的与完成成说明：1. 简单介介绍本实验的的主要目的2. 说明你你自己在本次次实验中完成成了第几项要求（必填）DS实验01-顺序表1. Probblem AA: DS顺顺序表-类类实现目的： (11)实现顺序序表的用C+语言和类类实现顺序表表(2)属性包括括：数组、实实际长度、最最大长度（设设定为10000）(3)操作包括括：创建、插
2、插入、删除、查查找要求：Input第1行先输入nn表示有n个个数据，即nn是实际长度度；接着输入入n个数据（完成）第2行输入要插插入的位置和和新数据（完成）第3行输入要插插入的位置和和新数据（完成）第4行输入要删删除的位置（完成）第5行输入要删删除的位置（完成）第6行输入要查查找的位置（完成）第7行输入要查查找的位置（完成）Output第1行输出创建建后的顺序表表内容，包括括顺序表实际际长度和数据据（完成）每成功执行一次次操作（插入入或删除），输输出执行后的的顺序表内容容（完成）每成功执行一次次查找，输出出查找到的数数据（完成）如果执行操作失失败（包括插插入、删除、查查找等失败），输输出字符串
3、eerror，不不必输出顺序序表内容（完成）2. Probblem BB: DS顺顺序表-连连续操作目的： (1)建立顺序表表的类，属性性包括：数组组、实际长度度、最大长度度（设定为11000）(2)实现连续续多个插入，即即从位置i开开始插入多个个数据(3)实现连续续多个删除，即即从位置i开开始删除多个个数据要求：Input第1行先输入nn表示有n个个数据，即nn是实际长度度；接着输入入n个数据（完成）第2行先输入ii表示插入开开始的位置，再再输入k表示示有k个插入入数据，接着着输入k个数数据（完成）第3行先输入ii表示删除开开始的位置，再再输入k表示示要删除k个个数据（完成）Output顺序
4、表内容包括括顺序表的实实际长度和数数据，数据之之间用空格隔隔开（完成）第1行输出创建建后的顺序表表内容（完成）第2行输出执行行连续插入后后的顺序表内内容（完成）第3行输出执行行连续删除后后的顺序表内内容（完成）3. Probblem CC: DS顺顺序表-合合并操作目的： (1)建立顺序表表的类，属性性包括：数组组、实际长度度、最大长度度（设定为11000）(2)已知两个个递增序列，把把两个序列的的数据合并到到顺序表中，(3)并使得顺顺序表的数据据递增有序。要求：Input第1行先输入nn表示有n个个数据，接着着输入n个数数据，表示第第1个序列，要要求数据递增增互不等（完成）第2行先输入mm表
5、示有m个个数据，接着着输入m个数数据，表示第第2个序列，要要求数据递增增互不等（完成）Output顺序表内容包括括顺序表的实实际长度和数数据，数据之之间用空格隔隔开（完成）第1行输出创建建后的顺序表表内容（完成）DS实验02-链表1. Problemm A: DDS单链表-类实现目的：(1)用C+语言和类实实现单链表，含含头结点(2)属性包括括：dataa数据域、nnext指针针域(3)操作包括括：插入、删删除、查找(4)注意：单单链表不是数数组，所以位位置从1开始始对应首结点点，头结点不不放数据要求：Input第1行先输入nn表示有n个个数据，接着着输入n个数数据（完成）第2行输入要插插入的
6、位置和和新数据（完成）第3行输入要插插入的位置和和新数据（完成）第4行输入要删删除的位置（完成）第5行输入要删删除的位置（完成）第6行输入要查查找的位置（完成）第7行输入要查查找的位置（完成）Output数据之间用空格格隔开，（完成）第1行输出创建建后的单链表表的数据（完成）每成功执行一次次操作（插入入或删除），输输出执行后的的单链表数据据（完成）每成功执行一次次查找，输出出查找到的数数据（完成）如果执行操作失失败（包括插插入、删除、查查找等失败），输输出字符串eerror，不不必输出单链链表（完成）2. Problemm B: DDS单链表-结点交换换目的：(1)用C+实现含头结结点的单链表
7、表，然后实现现单链表的两两个结点交换换位置。(2)注意不能能简单交换两两个结点包含含数据，必须须通过修改指指针来实现两两个结点的位位置交换(3)交换函数数定义可以参参考：(4)swapp（int ppa, innt pb) /ppa和pb表表示两个结点点在单链表的的位置序号(5)swapp (LisstNodee * p, ListtNode * q) /p和和q表示指向向两个结点的的指针要求：Input第1行先输入nn表示有n个个数据，接着着输入n个数数据（完成）第2行输入要交交换的两个结结点位置（完成）第3行输入要交交换的两个结结点位置（完成）Output第一行输出单链链表创建后的的所有数
8、据，数数据之间用空空格隔开（完成）第二行输出执行行第1次交换换操作后的单单链表数据，数数据之间用空空格隔开（完成）第三行输出执行行第2次交换换操作后的单单链表数据，数数据之间用空空格隔开（完成）如果发现输入位位置不合法，输输出字符串eerror，不不必输出单链链表（完成）3. Problemm C: DDS单链表-合并目的：(1)假定两个个单链表是递递增有序，定定义并实现以以下函数，完完成两个单链链表的合并，继继续保持递增增有序(2)int LL_meerge(LListNoode *LLa, LiistNodde *Lbb)要求：Input第1行先输入nn表示有n个个数据，接着着输入n个数数
9、据（完成）第2行先输入mm表示有M个个数据，接着着输入m个数数据（完成）Output输出合并后的单单链表数据，数数据之间用空空格隔开（完成）4. Problemm D: DDS线性表-多项式相相加目的：(1)对于一元元多项式 p(x)=p0+p11x+p2xx2+ +pnxxn ，每每个项都有系系数和指数两两部分，例如如p2x2的的系数为p22,指数为22(2)编程实现现两个多项式式的相加例如5+x+22x2+3xx3，-5-x+6x22+4x4，两两者相加结果果：8x2+3x3+44x4 (3)其中系数数5和-5都都是x的0次次方的系数，相相加后为0，所所以不显示。xx的1次方同同理不显示。
10、(4)可用顺序序表或单链表表实现要求：Input第1行：输入tt表示有t组组测试数据（完成）第2行：输入nn表示有第11组的第1个个多项式包含含n个项（完成）第3行：输入第第一项的系数数和指数，以以此类推输入入n行（完成）接着输入m表示示第1组的第第2个多项式式包含m项（完成）同理输入第2个个多项式的mm个项的系数数和指数（完成）参考上面输入第第2组数据，以以此类推输入入t组（完成）假设所有数据都都是整数（完成）Output对于每1组数据据，先用两行行输出两个原原来的多项式式，再用一行行输出运算结结果，不必考考虑结果全为为0的情况（完成）输出格式参考样样本数据，格格式要求包括括：1.如果指数或
11、或系数是负数数，用小括号号括起来（完成）2.如果系数为为0，则该项项不用输出（完成）3.如果指数不不为0，则用用符号表示示，例如x的的3次方，表表示为x33（完成）4.多项式的每每个项之间用用符号+连接接，每个+两两边加1个空空格隔开（完成）DS实验03-堆栈与队队列1. Problemm A: DDS堆栈-逆序输出（SSTL栈使用用）目的：(1)C+中中已经自带堆堆栈对象sttack，无无需编写堆栈栈操作的具体体实现代码。(2)本题目主主要帮助大家家熟悉staack对象的的使用，然后后实现字符串串的逆序输出出(3)输入一个个字符串，按按字符按输入入顺序压入堆堆栈，然后根根据堆栈后进进先出的特
12、点点，做逆序输输出要求：Input第一行输入t，表表示有t个测测试实例（完成）第二起，每一行行输入一个字字符串，注意意字符串不要要包含空格（完成）Output每行逆序输出每每一个字符串串（完成）2. Problemm B: DDS线性表综综合练习-队列之银行行排队目的：(1)在银行营营业大厅共服服务3种客户，类类型为ABBC，大厅厅分别设置了了3个窗口分别别服务三种客客户，即每个个窗口只服务务一种客户。现现有一批客户户来银行办理理业务，每个个客户都有类类型和办理业业务时间。每每个窗口按照照客户到来的的顺序进行服服务。要求：Input第一行输入先输输入n表示客客户数量（完成）第二行输入每个个客户
13、的类型型，数据之间间用用空格隔隔开（完成）第三行输入每个个客户的办理理时间，数据据之间用用空空格隔开（完成）Output第一行输出A类类客户的平均均办理时间（完成）第二行输出B类类客户的平均均办理时间（完成）第三行输出C类类客户的平均均办理时间（完成）3. Problemm C: DDS堆栈-行编辑目的：(1)使用C+的STLL堆栈对象，编编写程序实现现行编辑功能能。行编辑功功能是：当输输入#字符，则则执行退格操操作；如果无无字符可退就就不操作，不不会报错(2)本程序默默认不会显示示#字符，所所以连续输入入多个#表示示连续执行多多次退格操作作(3)每输入一一行字符打回回车则表示字字符串结束(4
14、)注意：必必须使用堆栈栈实现，而且且结果必须是是正序输出要求：Input第一行输入一个个整数t，表表示有t行字字符串要输入入（完成）第二行起输入一一行字符串，共共输入t行（完完成）Output每行输出最终处处理后的结果果，如果一行行输入的字符符串经过处理理后没有字符符输出，则直直接输出NUULL（完成成）4. Problemm D: DDS线性表综综合练习-数制转换目的：(1)对于任意意十进制数转转换为k进制制，包括整数数部分和小数数部分转换。整整数部分采用用除k求余法法，小数部分分采用乘k取取整法例如xx=19.1125，求22进制转换整数部分19，小数部分0.12519 / 2 = 9 1
15、0.1255 * 2 = 0.225 009 / 2 = 4 10.25 * 2 = 0.5 004 / 2 = 2 0 0.5 * 2 = 1 12 / 2 = 1 01 / 2 = 0 1(2)所以整数数部分转为 100111，小数部分分转为0.0001，合起起来为100011.0001(3)提示整数数部分可用堆堆栈，小数部部分可用队列列实现(4)注意：必必须按照上述述方法来实现现数制转换，其其他方法0分分要求：Input第一行输入一个个t，表示下下面将有t组组测试数据。（完成）接下来每行包含含两个参数nn和k，n表表示要转换的的数值，可能能是非整数；k表示要转转换的数制，11k=116（
16、完成）Output对于每一组测试试数据，每行行输出转换后后的结果，结结果精度到小小数点后3位位（完成）5. Problemm E: DDS堆栈-括号匹配目的：(1)处理表达达式过程中需需要对括号匹匹配进行检验验，括号匹配配包括三种：“(”和“)”，“”和和“”，“”和“”。例例如表达式中中包含括号如如下：()()()1234456789101112(2)从上例可可以看出第11和第2个括括号匹配，第第3和第100个括号匹配配，4和5匹匹配，6和99匹配，7和和8匹配，111和12匹匹配。从中可可以看到括号号嵌套的的情情况是比较复复杂的，使用用堆栈可以很很方便的处理理这种括号匹匹配检验，可可以遵循
17、以下下规则：1、 当接收第第1个左括号号，表示新的的一组匹配检检查开始；随随后如果连续续接收到左括括号，则不断断进堆栈。2、 当接受第第1个右括号号，则和最新新进栈的左括括号进行匹配配，表示嵌套套中1组括号号已经匹配消消除3、 若到最后后，括号不能能完全匹配，则则说明输入的的表达式有错错(3)建议使用用C+自带带的stacck对象来实实现要求：Input第一行输入一个个t，表示下下面将有t组组测试数据。接接下来的t行行的每行输入入一个表达式式，表达式只只考虑英文半半角状态输入入，无需考虑虑中文全角输输入（完成）Output对于每一行的表表达式，检查查括号是否匹匹配，匹配则则输入ok，不不匹配则
18、输出出errorr（完成）6. Problemm F: DDS线性表综综合练习-组队列目的：(1)组队列是是队列结构中中一种常见的的队列结构，在在很多地方有有着广泛应用用。组队列是是是指队列内内的元素分组组聚集在一起起。组队列包包含两种命令令：1、 ENQUUEUE，表表示当有新的的元素进入队队列，首先会会检索是否有有同一组的元元素已经存在在，如果有，则则新元素排在在同组的最后后，如果没有有则插入队列列末尾。2、 DEQUUEUE，表表示队列头元元素出队3、 STOPP，停止操作作(2)建议使用用C+自带带的队列对象象queuee，编程更方方便要求：Input第1行输入一个个t(t=10)，表
19、表示1个队列列中有多少个个组（完成）第2行输入一个个第1组的元元素个数和数数值第3行输输入一个第22组的元素个个数和数值，（完成但不严谨）以此类推输入完完n组之后，开开始输入多个个操作命令(datta;p-datta=q-data;q-datta=temmp; retturn ook; 3. Problemm C: DDS单链表-合并 过程基基本与线性表表合并相同。不不同的是需要要调整指针。4. Problemm D: DDS线性表-多项式相相加线性表实现： 建建立两个数组组分别存储系系数和指数。多项式相加的操操作过程基本本与合并相似似。先比较指指数，若指数数较小就插在在最左边，若若指数相等则
20、则相加再插入入。一条多项项式插完后另另一条多项式式剩余系数指指数插在右边边。链表实现：Status MakeNNode(LLink& p,EleemTypee e,EllemTyppe e1);分配一个个结点Status CreattPolynn(polyynomaii &P,LLink& p);将结结点插入多项项式中。插入入过程中比较较指数大小按由由小到大的顺顺序插在相应应的位置里，如如果有相同指指数的则系数数相加（系数数可为正负），若若系数为0则则调用删除函函数删除该结结点。Status AddPoolyn(ppolynoomai &Pa,poolynommai &PPb,pollynom
21、aai &Pcc);多项式相加。比比线性表要简简单，直接把把Pa，Pbb里的系数跟跟指数创建一一个结点放入入多项式Pcc中即可，相相加直接在加加入的时候完完成。DS实验03-堆栈与队队列1. Problemm A: DDS堆栈-逆序输出（SSTL栈使用用）建立一个栈，将将数值pussh()进栈栈后用topp()返回值值并pop()弹出值逆逆向输出。2. Problemm B: DDS线性表综综合练习-队列之银行行排队建立两个队列，一一个为，另一一个为，用用于存储时间间和字符，在在一个个用ffront()取值并用用pop()弹出，用判判断语句进行行平均数求值值。3. Problemm C: DD
22、S堆栈-行编辑建立两个栈，用用其中一个栈栈存储strring数组组的每一个字字符。先判断断是否为#号号且有多少个个#号，若没没有#号则ppush()字符进第二二个栈，有多多少个#号就就pop()多少个。全全程判断栈是是否为空。最最后判断第二二个栈是否为为空，不为空空就输出字符符串，为空就就输出NULLL。4. Problemm D: DDS线性表综综合练习-数制转换Push数值与与进制数的余余数进栈然后后逆向输出。Push数值与与2的倍数取取整进栈然后后逆向输出。5. Problemm E: DDS堆栈-括号匹配若栈为空时下一一个就是右括括号直接括号号不匹配。若是左括号则进进栈。一直进左括号知
23、知道有右括号号出现。若右括号与toop()匹配配则pop()。若括号匹配则栈栈为空。6. Problemm F: DDS线性表综综合练习-组队列建立队列数组，同同组的元素进进入同一个队队列中。7. Problemm G: DDS堆栈-表达式计算算使用OPTR栈栈存储运算符符，使用OPPND栈存储储数字。OPTR先PUUSH入#号号，输入表达达式时最后一一位为#号，在在c= =OOPTR.ttop()= =#的时候结束束表达式计算算。读入字符的过程程中不断有运运算符和数字字进栈，直到到两个运算符符遭遇的时候候，判断栈内内top()运算符与cc内运算符的的优先级，即即表达式中前前一个运算符符与后一
24、个运运算符的优先先级。如果是小于，则则直接让c进进OPTR栈栈，再读入下下一个字符；如果是大于，则则OPTR弹弹出一个运算算符，OPNND弹出两个个数字进行计计算求值重新新放回OPNND栈；如果是等于则OOPTR出栈栈消除括号。只只有左括号和和右括号以及及两个#号的的优先级为等等于号。而右右括号出现的的时候左括号号以后的运算算符都已计算算并变成数字字进入了OPPND栈，所所以右括号出出现时候OPPTR.poop()弹出出的必然是左左括号。最后OPND会会剩下最后一一个数字即结结果。函数： Strrcat(cchar,charr)在字符串串后面加字符符。8. Problemm H: DDS堆栈-
25、迷宫求解建立一个类CPPOS，对象象分别是xpp,yp作为为坐标。建立立存储类型为为类的栈sttack。从起点开始如果果右边能走优优先往右。直直到右边不能能走了就往下下，如果右边边和下边都不不能走就poop（），同同时刚刚的坐坐标上直接标标记无法通行行（1），然然后判断下边边能不能走。坐坐标轴到达了了右下角即成成功，如果最最后pop（）到到栈内没有元元素了的话就就说明没有路路径。DS实验04-串应用KKMP算法1. Problemm A: DDS串应用-KMP算算法nextj： ：第一为0的作作用是让子串串向右移动一一格，此时ii会变。 ：1的作用是子子串换成第一一个字符再进行比较，此此时i不
26、会变变。 ：j取nexttj的时时候i不变。 ：如果一直没有有匹配到，jj一直为1，nnextjj一直为00。如果有匹匹配到j就会会大于1； ：子串有j个字字符，则neext中用到到的只有前jj个。 ：nextjj大于0时时候表示调用用第nexttj个位位置的字符与与mainsstri匹配。三实验程序或或内容：1. 针对每一一项实验要求求，给出编写写的代码，2. 可以粘贴贴全部代码，或或者可以只粘粘贴重要的代代码（为了节节省纸张），但代码必须须完整，至少少是完整的函函数。3. 代码符合合以下要求，评评分更高：a. 排版整齐齐，可读性高高b. 代码有注注释，越详细细越清晰越好好DS实验01-顺序
27、表1. Probblem AA: DS顺顺序表-类类实现#includde using nnamesppace sstd; #definee ok 00 #definee erroor -1 /顺序表类定定义 class SSeqLisst privatee: intt *lisst; intt maxssize; intt sizee; public: SeqqList(); SeeqListt(); intt listt_sizee(); intt listt_inseert(innt i,intt itemm); intt listt_del(int i); intt listt_get
28、(int i); voiid lisst_dissplay(); ; /构造函数SeqListt:SeqqList() maxxsize=1000; sizze=0; lisst=neww intmaaxsizee; /析构函数SeqListt:SeeqListt() delletelist; /返回长度int SeqqList:listt_sizee() retturn ssize; /插入函数int SeqqList:listt_inseert(innt i,intt itemm) if(isizze+1|ii-1;jj-) listtj=llistjj-1; lisstj=item; s
29、izze+; retturn ook; /删除函数int SeqqList:listt_del(int i) if(isizze|i0|siize=00)retuurn errror; intt j; forr(j=i-1;jssize-11;j+) listtj=llistjj+1; sizze-; retturn ook; /返回值函数数int SeqqList:listt_get(int i) if(isiize)retturn eerror; retturn llistii-1; /输出函数void SeeqListt:lisst_dissplay() intt j; forr(j=0
30、;jsizze;j+) couttlisstj ; couutn; forr(i=0;iNUM; L.liist_innsert(i+1,NNUM); couutL.list_size()possitionnNUMM; if(L.lisst_inssert(ppositiion,NUUM)=-1)couuteerrorenddl; elsse couutL.list_size()possitionnNUMM; if(L.lisst_inssert(ppositiion,NUUM)=-1)couuteerrorenddl; elsse couutL.list_size()possitionn;
31、if(L.lisst_dell(posiition)=-1)couterrrorendl; elsse couutL.list_size()possitionn; if(L.lisst_dell(posiition)=-1)couterrrorendl; elsse couutL.list_size()possitionn; if(L.lisst_gett(posiition)=-1)couterrrorendl; elsee couutL.list_get(ppositiion)possitionn; if(L.lisst_gett(posiition)=-1)couterrrorendl;
32、 elsee couutL.list_get(ppositiion)endl; retturn 00; 2.Probllem B: DS顺序序表-连续续操作#includde using nnamesppace sstd; #definee ok 00 #definee erroor -1 /顺序表类定定义 class SSeqLisst privatee: intt *lisst; intt maxssize; intt sizee; public: SeqqList(); SeeqListt(); intt listt_sizee(); intt listt_inseert(innt i,
33、intt itemm); intt listt_del(int i); intt listt_get(int i); voiid lisst_dissplay(); ; /构造函数SeqListt:SeqqList() maxxsize=1000; sizze=0; lisst=neww intmaaxsizee; /析构函数SeqListt:SeeqListt() delletelist; /返回长度int SeqqList:listt_sizee() retturn ssize; /插入函数int SeqqList:listt_inseert(innt i,intt itemm) if(isizze+1|i0|size=maxssize)rreturnn erroor; if(i=siize+1)