顺序表链表KMP实验报告 本文关键词：表链，顺序，实验，报告，KMP
顺序表链表KMP实验报告 本文简介：附件（四）深圳大学实验报告课程名称：数据结构实验与课程设计实验项目名称：顺序表、链表、堆栈队列、串KMP算法学院：专业：指导教师：报告人：学号：班级：实验时间：实验报告提交时间：教务处制一、实验目的与完成说明：1.简单介绍本实验的主要目的2.说明你自己在本次实验中完成了第几项要求（必填）DS实验01
顺序表链表KMP实验报告 本文内容：
附件（四）
深
圳
大
学
实
验
报
告
课程名称：
数据结构实验与课程设计
实验项目名称：
顺序表、链表、堆栈队列、串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(ListNodeLa,ListNodeLb)
要求：
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次方，表示为x^3（完成）
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种客户，类型为A/B/C，大厅分别设置了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.125
19
/
2
=
9
…
10.125
2
=
0.25
…
0
9
/
2
=
4
…
10.25
2
=
0.5
…
0
4
/
2
=
2
…
0
0.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表示要转换的数制，1data;
p->data=q->data;
q->data=temp;
return
ok;
}
3.
Problem
C:
DS单链表--合并
过程基本与线性表合并相同。不同的是需要调整指针。
4.
Problem
D:
DS线性表--多项式相加
线性表实现：
建立两个数组分别存储系数和指数。
多项式相加的操作过程基本与合并相似。先比较指数，若指数较小就插在最左边，若指数相等则相加再插入。一条多项式插完后另一条多项式剩余系数指数插在右边。
链表实现：
Status
MakeNode(Link分配一个结点
Status
CreatPolyn(polynomai
将结点插入多项式中。插入过程中比较指数大小按由小到大的顺序插在相应的位置里，如果有相同指数的则系数相加（系数可为正负），若系数为0则调用删除函数删除该结点。
Status
AddPolyn(polynomai
多项式相加。比线性表要简单，直接把Pa，Pb里的系数跟指数创建一个结点放入多项式Pc中即可，相加直接在加入的时候完成。
DS实验03--堆栈与队列
1.
Problem
A:
DS堆栈--逆序输出（STL栈使用）
建立一个栈，将数值push()进栈后用top()返回值并pop()弹出值逆向输出。
2.
Problem
B:
DS线性表综合练习--队列之银行排队
建立两个队列，一个为，另一个为，用于存储时间和字符，在一个个用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。
从起点开始如果右边能走优先往右。直到右边不能走了就往下，如果右边和下边都不能走就pop（），同时刚刚的坐标上直接标记无法通行（1），然后判断下边能不能走。坐标轴到达了右下角即成功，如果最后pop（）到栈内没有元素了的话就说明没有路径。
DS实验04--串应用KMP算法
1.
Problem
A:
DS串应用--KMP算法
next[j]：
①
：第一为0的作用是让子串向右移动一格，此时i会变。
②
：1的作用是子串换成第一个字符再进行比较，此时i不会变。
③
：j取next[j]的时候i不变。
④
：如果一直没有匹配到，j一直为1，next[j]一直为0。如果有匹配到j就会大于1；
⑤
：子串有j个字符，则next中用到的只有前j个。
⑥
：next[j]大于0时候表示调用第next[j]个位置的字符与mainstr[i]匹配。
三．实验程序或内容：
1.
针对每一项实验要求，给出编写的代码，
2.
可以粘贴全部代码，或者可以只粘贴重要的代码（为了节省纸张），但代码必须完整，至少是完整的函数。
3.
代码符合以下要求，评分更高：
a.
排版整齐，可读性高
b.
代码有注释，越详细越清晰越好
DS实验01--顺序表
1.
Problem
A:
DS顺序表--类实现
#include
using
namespace
std;
#define
ok
0
#define
error
-1
//顺序表类定义
class
SeqList
{
private:
intlist;
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
int[maxsize];
}
//析构函数
SeqList::~SeqList()
{
delete[]list;
}
//返回长度
int
SeqList::list_size()
{
return
size;
}
//插入函数
int
SeqList::list_insert(int
i,int
item)
{
if(i>size+1||ii-1;j--)
{
list[j]=list[j-1];
}
list[j]=item;
size++;
return
ok;
}
//删除函数
int
SeqList::list_del(int
i)
{
if(i>size||isize)return
error;
return
list[i-1];
}
//输出函数
void
SeqList::list_display()
{
int
j;
for(j=0;j>n;
for(i=0;i>NUM;
L.list_insert(i+1,NUM);
}
cout>position>>NUM;
if(L.list_insert(position,NUM)==-1)cout>position>>NUM;
if(L.list_insert(position,NUM)==-1)cout>position;
if(L.list_del(position)==-1)cout>position;
if(L.list_del(position)==-1)cout>position;
if(L.list_get(position)==-1)cout>position;
if(L.list_get(position)==-1)cout
using
namespace
std;
#define
ok
0
#define
error
-1
//顺序表类定义
class
SeqList
{
private:
intlist;
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
int[maxsize];
}
//析构函数
SeqList::~SeqList()
{
delete[]list;
}
//返回长度
int
SeqList::list_size()
{
return
size;
}
//插入函数
int
SeqList::list_insert(int
i,int
item)
{
if(i>size+1||ii-1;j--)
{
list[j]=list[j-1];
}
list[j]=item;
size++;
return
ok;
}
//删除函数
int
SeqList::list_del(int
i)
{
if(i>size||isize)return
error;
return
list[i-1];
}
//输出函数
void
SeqList::list_display()
{
int
j;
for(j=0;j>n;
for(j=0;j>NUM;
L.list_insert(j+1,NUM);
}
cout>i>>k;
for(j=0;j>NUM;
L.list_insert(i++,NUM);
}
cout>i>>k;
for(j=0;j
using
namespace
std;
#define
ok
0
#define
error
-1
//顺序表类定义
class
SeqList
{
private:
intlist;
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
int[maxsize];
}
//析构函数
SeqList::~SeqList()
{
delete[]list;
}
//返回长度
int
SeqList::list_size()
{
return
size;
}
//插入函数
int
SeqList::list_insert(int
i,int
item)
{
if(i>size+1||ii-1;j--)
{
list[j]=list[j-1];
}
list[j]=item;
size++;
return
ok;
}
//删除函数
int
SeqList::list_del(int
i)
{
if(i>size||isize)return
error;
return
list[i-1];
}
//输出函数
void
SeqList::list_display()
{
int
j;
for(j=0;j>n;
for(j=0;j>NUM;
L1.list_insert(j+1,NUM);
}
cin>>m;
for(j=0;j>NUM;
L2.list_insert(j+1,NUM);
}
int
i=1;
j=1;
int
k=1;
//排列Start
while(iL2.list_get(j))
{
L3.list_insert(k++,L2.list_get(j));
j++;
continue;
}
if(L1.list_get(i)
using
namespace
std;
#define
ok
1
#define
error
-1;
class
ListNode
{
public:
int
data;
ListNodenext;
ListNode(){next=NULL;}
};
class
LinkList
{
public:
ListNodehead;
int
len;
LinkList();
~LinkList();
ListNodeLL_index(int
i);
int
LL_get(int
i);
int
LL_insert(int
i,int
item);
int
LL_del(int
i);
void
LL_display();
};
LinkList::LinkList()
{
head=
new
ListNode();
len=0;
}
LinkList::~LinkList()
{
ListNodep,*q;
p=head;
while(p!=NULL)
{
q=p;
p=p->next;
delete
q;
}
len=0;
head=NULL;
}
void
LinkList::LL_display()
{
ListNodep;
p=head->next;
while(p)
{
coutdatanext;
}
coutlen)return
NULL;;
ListNodep;
p=head->next;
while(p->next
}
return
p;
}
int
LinkList::LL_get(int
i)
{
if(ilen)return
error;
ListNodep=NULL;
p=head->next;
while(p->next
}
return
p->data;
}
int
LinkList::LL_insert(int
i,int
item)
{
if(ilen+1)return
error;
ListNodep;
p=new
ListNode();
p->data=item;
if(i==1)
{
ListNodepE;
pE=head->next;
head->next=p;
p->next=pE;
len++;
return
ok;
}
if(i==len+1)
{
ListNodepE;
pE=head->next;
while(pE->next)
{
pE=pE->next;
}
pE->next=p;
len++;
return
ok;
}
else
{
ListNodepE,*pN;
pE=head->next;
pN=pE;
while(pE->next
pE=pE->next;
}
pN->next=p;
p->next=pE;
len++;
}
return
ok;
}
int
LinkList::LL_del(int
i)
{
if(ilen)return
error;
ListNodepE;
if(i==1)
{
pE=head->next->next;
head->next=pE;
len--;
return
ok;
}
else
{
ListNodepN;
pE=head->next;
while(pE->next
pE=pE->next;
}
pE=pE->next;