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

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

《顺序表链表KMP实验报告.docx》由会员分享，可在线阅读，更多相关《顺序表链表KMP实验报告.docx（104页珍藏版）》请在冰点文库上搜索。

顺序表链表KMP实验报告

附件（四）

深圳大学实验报告

课程名称：

数据结构实验与课程设计

实验项目名称：

顺序表、链表、堆栈队列、串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（int pa,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.125

19/2=9…10.125*2=0.25…0

9/2=4…10.25*2=0.5…0

4/2=2…00.5*2=1…1

2/2=1…0

1/2=0…1

（2）所以整数部分转为10011，小数部分转为0.001，合起来为10011.001

（3）提示整数部分可用堆栈，小数部分可用队列实现

（4）注意：

必须按照上述方法来实现数制转换，其他方法0分

要求：

Input

第一行输入一个t，表示下面将有t组测试数据。

（完成）

接下来每行包含两个参数n和k，n表示要转换的数值，可能是非整数；k表示要转换的数制，1

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

每行输出一个表达式的计算结果，计算结果用浮点数（含4位小数）的格式表示（完成）

8.ProblemH:

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

逐个输出迷宫的路径（完成）

如果迷宫不存在路径，则输出nopath并回车（完成）

如果迷宫存在路径，将路径中每个方格的x和y坐标输出，从起点到终点，每输出四个方格就换行，最终以单词END结尾（完成）

DS实验04--串应用KMP算法

1.ProblemA:

DS串应用--KMP算法

目的：

（1）学习KMP算法，给出主串和模式串，求模式串在主串的位置

要求：

Input

第一个输入t，表示有t个实例（完成）

第二行输入第1个实例的主串，第三行输入第1个实例的模式串（完成）

以此类推

Output

第一行输出第1个实例的模式串的next值（完成）

第二行输出第1个实例的匹配位置，位置从1开始计算，如果匹配成功输出位置，匹配失败输出0（完成）

以此类推

二、主要思路与方法：

1.对于本次实验，说明你认为最重要的函数、算法或知识点，并谈谈你对它们的理解

DS实验01--顺序表

1.ProblemA:

DS顺序表--类实现

函数：

list_insert（inti,intitem）;插入函数

一维数组需要把插入点后的数据往后推一格再给插入点赋值。

所耗时间比链表久。

list_del（inti）删除函数

将删除点后点数据前推一格覆盖删除点。

所耗时间比链表久。

list_get（inti）返回指定值函数

比链表快。

2.ProblemB:

DS顺序表--连续操作

同ProblemA:

DS顺序表--类实现。

使用for循环以及插入函数。

3.ProblemC:

DS顺序表--合并操作

合并操作：

两个线性表，分别读取数字，比较两数字大小，小的先插入第三个线性表，一直读到其中一个线性表到底跳出循环，将另一条线性表里剩余的数字全都插在第三个线性表后。

DS实验02--链表

1.ProblemA:

DS单链表--类实现

函数：

LL_insert（inti,intitem）;插入函数。

调整指针指向即可插入。

比顺序表快。

LL_get（inti）;返回值函数。

遍历到指定结点后输出。

比顺序表慢。

LL_del（inti）;删除函数。

调整指针指向，释放结点或放置另一条链表中回收利用。

2.ProblemB:

DS单链表--结点交换

改变指针进行交换：

改变数值进行交换：

intLinkList:

:

swap（ListNode*p,ListNode*q）

{

if（p==head||q==head||!

p||!

q）returnerror;

inttemp;

temp=p->data;

p->data=q->data;

q->data=temp;

returnok;

}

3.ProblemC:

DS单链表--合并

过程基本与线性表合并相同。

不同的是需要调整指针。

4.ProblemD:

DS线性表--多项式相加

线性表实现：

建立两个数组分别存储系数和指数。

多项式相加的操作过程基本与合并相似。

先比较指数，若指数较小就插在最左边，若指数相等则相加再插入。

一条多项式插完后另一条多项式剩余系数指数插在右边。

链表实现：

StatusMakeNode（Link&p,ElemTypee,ElemTypee1）;分配一个结点

StatusCreatPolyn（polynomai&P,Link&p）;将结点插入多项式中。

插入过程中比较指数大小按由小到大的顺序插在相应的位置里，如果有相同指数的则系数相加（系数可为正负），若系数为0则调用删除函数删除该结点。

StatusAddPolyn（polynomai&Pa,polynomai&Pb,polynomai&Pc）;

多项式相加。

比线性表要简单，直接把Pa，Pb里的系数跟指数创建一个结点放入多项式Pc中即可，相加直接在加入的时候完成。

DS实验03--堆栈与队列

1.ProblemA:

DS堆栈--逆序输出（STL栈使用）

建立一个栈，将数值push（）进栈后用top（）返回值并pop（）弹出值逆向输出。

2.ProblemB:

DS线性表综合练习--队列之银行排队

建立两个队列，一个为，另一个为，用于存储时间和字符，在一个个用front（）取值并用pop（）弹出，用判断语句进行平均数求值。

3.ProblemC:

DS堆栈--行编辑

建立两个栈，用其中一个栈存储string数组的每一个字符。

先判断是否为#号且有多少个#号，若没有#号则push（）字符进第二个栈，有多少个#号就pop（）多少个。

全程判断栈是否为空。

最后判断第二个栈是否为空，不为空就输出字符串，为空就输出NULL。

4.ProblemD:

DS线性表综合练习--数制转换

Push数值与进制数的余数进栈然后逆向输出。

Push数值与2的倍数取整进栈然后逆向输出。

5.ProblemE:

DS堆栈--括号匹配

若栈为空时下一个就是右括号直接括号不匹配。

若是左括号则进栈。

一直进左括号知道有右括号出现。

若右括号与top（）匹配则pop（）。

若括号匹配则栈为空。

6.ProblemF:

DS线性表综合练习--组队列

建立队列数组，同组的元素进入同一个队列中。

7.ProblemG:

DS堆栈--表达式计算

使用OPTR栈存储运算符，使用OPND栈存储数字。

OPTR先PUSH入#号，输入表达式时最后一位为#号，在c==OPTR.top（）==’#’的时候结束表达式计算。

读入字符的过程中不断有运算符和数字进栈，直到两个运算符遭遇的时候，判断栈内top（）运算符与c内运算符的优先级，即表达式中前一个运算符与后一个运算符的优先级。

如果是小于，则直接让c进OPTR栈，再读入下一个字符；

如果是大于，则OPTR弹出一个运算符，OPND弹出两个数字进行计算求值重新放回OPND栈；

如果是等于则OPTR出栈消除括号。

只有左括号和右括号以及两个#号的优先级为等于号。

而右括号出现的时候左括号以后的运算符都已计算并变成数字进入了OPND栈，所以右括号出现时候OPTR.pop（）弹出的必然是左括号。

最后OPND会剩下最后一个数字即结果。

函数：

Strcat（char[],char）在字符串后面加字符。

8.ProblemH:

DS堆栈--迷宫求解

建立一个类CPOS，对象分别是xp,yp作为坐标。

建立存储类型为类的栈stack。

从起点开始如果右边能走优先往右。

直到右边不能走了就往下，如果右边和下边都不能走就pop（），同时刚刚的坐标上直接标记无法通行

（1），然后判断下边能不能走。

坐标轴到达了右下角即成功，如果最后pop（）到栈内没有元素了的话就说明没有路径。

DS实验04--串应用KMP算法

1.ProblemA:

DS串应用--KMP算法

next[j]：

1：

第一为0的作用是让子串向右移动一格，此时i会变。

2：

1的作用是子串换成第一个字符再进行比较，此时i不会变。

3：

j取next[j]的时候i不变。

4：

如果一直没有匹配到，j一直为1，next[j]一直为0。

如果有匹配到j就会大于1；

5：

子串有j个字符，则next中用到的只有前j个。

6：

next[j]大于0时候表示调用第next[j]个位置的字符与mainstr[i]匹配。

三．实验程序或内容：

1.针对每一项实验要求，给出编写的代码，

2.可以粘贴全部代码，或者可以只粘贴重要的代码（为了节省纸X），但代码必须完整，至少是完整的函数。

3.代码符合以下要求，评分更高：

a.排版整齐，可读性高

b.代码有注释，越详细越清晰越好

DS实验01--顺序表

1.ProblemA:

DS顺序表--类实现

#include

usingnamespacestd;

#defineok0

#defineerror-1

//顺序表类定义

classSeqList

{

private:

int*list;

intmaxsize;

intsize;

public:

SeqList（）;

~SeqList（）;

intlist_size（）;

intlist_insert（inti,intitem）;

intlist_del（inti）;

intlist_get（inti）;

voidlist_display（）;

};

//构造函数

SeqList:

:

SeqList（）

{

maxsize=1000;

size=0;

list=newint[maxsize];

}

//析构函数

SeqList:

:

~SeqList（）

{

delete[]list;

}

//返回长度

intSeqList:

:

list_size（）

{

returnsize;

}

//插入函数

intSeqList:

:

list_insert（inti,intitem）

{

if（i>size+1||i<0||size==maxsize）returnerror;

if（i==size+1）

{

list[i-1]=item;

size++;

returnok;

}

intj;

for（j=size;j>i-1;j--）

{

list[j]=list[j-1];

}

list[j]=ite