顺序表链表KMP算法数据结构报告.docx
《顺序表链表KMP算法数据结构报告.docx》由会员分享，可在线阅读，更多相关《顺序表链表KMP算法数据结构报告.docx（33页珍藏版）》请在冰点文库上搜索。
顺序表链表KMP算法数据结构报告
需求分析-------------------------------------------------P3
概要设计-------------------------------------------------P4
详细设计-------------------------------------------------P9
调试分析-------------------------------------------------P11
测试结果-------------------------------------------------P11
课程设计总结---------------------------------------------P15
参考文献-------------------------------------------------P16
附录------------------------------------------------------P16
一：
需求分析：
顺序表的插入、删除、合并等操作：
涉及顺序表的创建、插入、删除、查找、合并、显示等。
采用数组作为顺序表的结构，定义一个MAXSIZE作为数组的最大长度。
从键盘接收用户输入的基本数据类型（这里以char为例，也可以是int等其他类型）为例演示方便，系统自带一个已经含有元素的顺序表。
然后接收用户输入指令进行相应的操作。
插入演示时，要求用户输入插入的字符串和要插入的位置；删除演示时要求用户输入要删除的长度和起始位置；合并操作演示时，要求用户输入一个字符串用来建立新的顺序表，然后两个顺序表合并并输出新的顺序表。
链表的查找、删除、计数、输出等功能以及有序链表的合并：
涉及链表的创建、删除、查找、合并、显示等。
需要动态分配内存，用指针连接各节点。
先自定义一个ListNode节点用户存储数据和指针。
为了演示方便，系统依然自带了一个创建好并且含有若干元素的链表，用户可以在此基础上进行操作。
查找操作时，要求用户输入查找的字符，然后输出查找结果；插入操作时，要求用户输入要插入的字符以及要插入的位置；删除演示时要求用户输入要删除的长度和起始位置；合并操作演示时，要求用户输入一个字符串用来建立新的链表，然后两个顺序表合并并输出新的顺序表。
串的模式匹配：
为了演示方便，系统依然自带了一个创建好并且含有若干元素的主串，然后接受用户输入的模式串。
求出该模式串的next[]和nextval[]，再由此验证模式串在主串中的匹配情况。
二：
概要设计：
本程序中用到的所有抽象数据类型的定义如下。
1、顺序表
ADTSqList
{
数据对象：
D={ai|ai∈ElemSet,i=1,2,…,n,n>=0}
数据关系：
R1={|ai-1,ai∈D,i=2,…,n}
基本操作：
InitList_Sq（&L）
操作结果：
构造一个空的顺序表。
Create_Sq（&L）
初始条件：
空顺序表L已经构造。
操作结果：
在L中存放数据元素，创建顺序表L。
ListInsert_Sq&L,I,e）
初始条件：
顺序表L存在，并且1<=i<=ListLength（L）+1。
操作结果：
在L中的第i个位置之前插入新的数据元素e，L的表长加1。
Show_Sq（L）
初始条件：
存在非空顺序表L。
操作结果：
输出显示顺序表L。
MergeList_Sq（La,Lb,&Lc）
初始条件：
存在顺序表La,Lb，Lc。
操作结果：
把LaLb合并为Lc。
DeSameElem_Sq（&L）
初始条件：
存在非空顺序表L。
操作结果：
剔除L中的相同元素。
Sort_Sq（&L）
初始条件：
存在非空顺序表L。
操作结果：
//对顺序表L按非递减顺序排序。
ListDelete_Sq（&L,i）
初始条件：
存在顺序表L非空，1<=i<=ListLength（L）。
操作结果：
在顺序表L中删除第i个元素，并用显示其值e
}ADTSqList
2、链表
ADTLinkList
{
数据对象：
D={ai|ai∈ElemSet,i=1,2,…,n,n>=0}
数据关系：
R1={|ai-1,ai∈D,i=2,…,n}
基本操作：
InitList_L（&L）
操作结果：
构造一个空的链表
CreateList_f（void）
初始条件：
存在空的链表L。
操作结果：
头插入法实现链表的创建,并且返回头结点给L。
CreateList_r（void）
初始条件：
存在空的链表L。
操作结果：
尾插入法实现链表的创建,并且返回头结点给L。
LocateElem_L（L,&e）
初始条件：
存在空的链表L。
操作结果：
查询L第一个与e相等的数据元素，若存在，则返回它的位序，否则返回0。
NumberElem_L（L）
初始条件：
存在链表L。
操作结果：
计算并返回L数据元素的个数。
Show_L（L）
初始条件：
存在非空链表L。
操作结果：
输出显示链表L。
ListDelete_L（&L,i）
初始条件：
存在链表L非空，1<=i<=ListLength（L）。
操作结果：
在顺序链表L中删除第i个元素，返回其值。
DeSameElem_L（&L）
初始条件：
存在非空顺序表L。
操作结果：
剔除L中的相同元素。
MergeList_L（La,Lb,&Lc）
初始条件：
存在链表La,Lb，Lc。
操作结果：
把La，Lb合并为Lc。
SortList_L（&L）
初始条件：
存在非空链表L。
操作结果：
将L按非递减顺序排序。
ListInsert（&L,i,e）
初始条件：
链表L存在非空，并且1<=i<=ListLength（L）+1。
操作结果：
在L中的第i个位置之前插入新的数据元素e。
}ADTLinkList
3、串
ADTHString
{
数据对象：
D={ai|ai∈CharacterSet,i=1,2,…,n,n>=0}
数据关系：
R1={|ai-1,ai∈D,i=2,…,n}
基本操作：
InitStr（&S）
操作结果：
构造一个空串
CreateStr（&S,ch）
初始条件：
ch是字符串常量。
串S已经构造。
操作结果：
生成一个其值等于ch的串S。
ShowStr（S）
初始条件：
存在非空串S。
操作结果：
输出显示串S。
Index_KMP（S,T,pos,nextval[]）
初始条件：
串S和T存在，T是非空串，1<=pos<=SteLength（L）,nextval是next修正值。
操作结果：
若主串S中存在和串T相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；若不则函数值为0。
get_next（S,next[]）
初始条件：
串S存在且非空。
操作结果：
求串S的next值。
get_nextval（S,nextval[]）
初始条件：
串T存在且非非空。
操作结果：
求串S的nextval值。
}ADTHString
三：
详细设计
#defineMAXSIZE100
typedefstructnode
{
chardata;//数据域
structnode*next;//指针域
}ListNode;//ListNode数据结构的定义
voidPrintMenu（）;//打印菜单
voidDemo1（）;//演示一
voidDemo1Menu（）;//演示一的目录
intmyinsert（char*s,char*t,intpos）;//插入
intmydelete（char*s,intlen,intpos）;//删除
intmycombine（char*t1,char*t2,char*s）;//合并
intmycut（char*s,char*temp,intlen,intpos）;//顺序表切割
voidDemo2（）;//演示二
voidDemo2Menu（）;//演示二的菜单
ListNode*CreateList（）;//只创建一个空链表，返回表头
voidInsert（ListNode*head,chardata,intpos）;//插入一个元素
voidAppend（ListNode*head,chardata）;//尾部追加一个元素
intSearch（ListNode*head,chardata）;//某个元素是否在链表中,返回所在位置index
voidDeleteByValue（ListNode*head,chardata）;//依据元素值删除元素
voidDeleteByPos（ListNode*head,intpos）;//依据元素索引删除元素
intListLen（ListNode*head）;//求链表长度
voidDisplayList（ListNode*head）;//打印链表
voidListCombine（ListNode*heada,ListNode*headb）;
//合并链表,返回合并后的链表的表头
voidDemo3（）;//演示三
intindex_KMP（char*s,char*t,intpos,int*next）;//模式匹配算法
voidget_next（char*t,int*next）;//获取next[j]数组的函数声明
voidget_nextval（char*t,int*nextal）;//获取nextval[j]数组的函数声明
intmain（）
{
……
……
return0;
}
四：
调试分析
调试过程中对菜单处理很难，要做到程序健壮，就要对用户的错误输入进行处理，但是控制台应用程序要做到这一点很困难，一开始我是用char来接受用户输入的菜单指令，调试发现系统会见回车键和空格键当成字符输入。
后来决定用int来接受，当然这里也会有不太好的地方。
所以还是应该使用图形应用程序比较好。
五：
测试结果
程序启动后主界面
顺序表演示界面
顺序表插入演示
顺序表删除演示
链表查找演示
链表插入演示
链表合并演示
串的模式匹配演示
六：
课程设计总结
本次课程设计持续两周。
通过这次的课程设计，让我无论是知识上还是能力上，都有所进步。
一向惯于独立思考的自己学会了积极的同同学、朋友交流，取长补短，共同进步。
提升了实践能力，编程能力。
编写程序是件细心活,稍不留神就会出错,这就必须要求我们对待事情要认真!
在编写程序的过程中,错误不断出现,不同的类型（如少写了一个符号,写错了字母,用错了函数等等）层出不穷,这考验我们待事细心,耐心,能不能坚持到底,不能半途而废。
通过这次的课程设计，我对《数据结构》课程的认识进一步加深。
决定在暑假的时候把数据结构演示系统二，数据结构演示系统三完成。
让自己对编程能力，算法分析设计能力有更大的进步。
数据结构演示系统一，还有一些可以改进的地方，如，退出系统时，提示用户是否保存数据，增加文件读写功能，以及操作界面美化。
七：
参考文献
[1]严蔚敏，吴伟民编著，数据结构（C语言版），北京；清华大学出版社，2005
[2]严蔚敏，陈文博编著，数据结构及应用算法教程，北京；清华大学出版社，2006
[3]谭浩强.C语言程序设计（第二版）.北京:
清华大学出版社,2007.10
八：
附录（带注释的源程序）
#include
#include
#include
#defineMAXSIZE100
typedefstructnode
{
chardata;
structnode*next;
}ListNode;
voidPrintMenu（）;//打印菜单
voidDemo1（）;//演示一
voidDemo1Menu（）;
intmyinsert（char*s,char*t,intpos）;
intmydelete（char*s,intlen,intpos）;
intmycombine（char*t1,char*t2,char*s）;
intmycut（char*s,char*temp,intlen,intpos）;//顺序表切割
voidDemo2（）;//演示二
voidDemo2Menu（）;
ListNode*CreateList（）;//只创建一个空链表，返回表头
voidInsert（ListNode*head,chardata,intpos）;//插入一个元素
voidAppend（ListNode*head,chardata）;//尾部追加一个元素
intSearch（ListNode*head,chardata）;//某个元素是否在链表中,返回所在位置index
voidDeleteByValue（ListNode*head,chardata）;//依据元素值删除元素
voidDeleteByPos（ListNode*head,intpos）;//依据元素索引删除元素
intListLen（ListNode*head）;//求链表长度
voidDisplayList（ListNode*head）;//打印链表
voidListCombine（ListNode*heada,ListNode*headb）;//合并链表,返回合并后的链表的表头
voidDemo3（）;//演示三
intindex_KMP（char*s,char*t,intpos,int*next）;
voidget_next（char*t,int*next）;//获取next[j]数组的函数声明
voidget_nextval（char*t,int*nextal）;//获取nextval[j]数组的函数声明
intmain（）
{
intselect;
while
（1）
{
PrintMenu（）;
scanf（"%d",&select）;
switch（select）
{
case1:
Demo1（）;break;
case2:
Demo2（）;break;
case3:
Demo3（）;break;
case4:
exit（0）;break;
default:
printf（"输入有误，请重新输入！
"）;break;
}
system（"pause"）;//每次循环后停一下，输出提示信息，等待用户
}
system（"pause"）;
return0;
}
//打印菜单
voidPrintMenu（）
{
system（"cls"）;
printf（"\t\t\t\t主菜单\n\n"）;
printf（"\t\t\t1.顺序表的插入、删除、合并操作\n\n"）;
printf（"\t\t\t2.链表的查找、删除、计数、输出以及合并\n\n"）;
printf（"\t\t\t3.串的模式匹配、next、nextval\n\n"）;
printf（"\t\t\t4.退出\n\n"）;
printf（"\t\t请选择一项:
"）;
}
//演示一
voidDemo1（）
{
charDemoString[MAXSIZE]="abcdefgVERYCSU";//演示用原字符串
charOtherDemoS[MAXSIZE];
charS2Gether[MAXSIZE];
intselect;//选择的菜单项
charInsertString[20];//插入的字符串
intlen;//要删除的字符串长度
intpos;//在原字符串中的位置
while
（1）
{
system（"cls"）;
Demo1Menu（）;
scanf（"%d",&select）;
switch（select）
{
case1:
{
system（"cls"）;
printf（"这是演示用字符串:
%s\n\n",DemoString）;
printf（"请输入要插入的字符串，20字节以内:
"）;
scanf（"%s",InsertString）;
printf（"\n\n要将字符串插入原字符串哪个位置？
请输入正确的索引值:
"）;
scanf（"%d",&pos）;
myinsert（DemoString,InsertString,pos）;
printf（"\n\n插入操作后的字符串:
%s\n\n",DemoString）;
}break;
case2:
{
system（"cls"）;
printf（"这是演示用字符串:
%s\n\n",DemoString）;
printf（"要删除的字符串原字符串哪个位置？
请输入正确的索引值:
"）;
scanf（"%d",&pos）;
printf（"\n\n请输入要删除的字符串长度:
"）;
scanf（"%d",&len）;
mydelete（DemoString,len,pos）;
printf（"\n\n插入操作后的字符串:
%s\n\n",DemoString）;
}
break;
case3:
{
system（"cls"）;
printf（"这是演示用字符串:
%s\n\n",DemoString）;
printf（"请输入一个字符串，用于演示合并:
"）;
scanf（"%s",OtherDemoS）;
mycombine（DemoString,OtherDemoS,S2Gether）;
printf（"你输入的是:
%s",S2Gether）;
}
break;
case4:
return;break;//回到上一级菜单，return就可以了
default:
printf（"输入有误，请重新输入！
"）;break;
}
system（"pause"）;
}
}
voidDemo1Menu（）
{
printf（"\t\t\t1.插入演示\n\n"）;
printf（"\t\t\t2.删除演示\n\n"）;
printf（"\t\t\t3.合并演示\n\n"）;
printf（"\t\t\t4.回到上一级菜单\n\n"）;
printf（"\t\t请选择一项:
"）;
}
intmycut（char*s,char*temp,intlen,intpos）
{
if（checkcut（s,temp,len,pos）==0）
{
temp[0]='\0';
return0;
}
inti=0;
for（i=0;i{
temp[i]=s[pos+i];
}
temp[len]='\0';
}
//切割检查
intcheckcut（char*s,char*temp,intlen,intpos）
{
if（len+pos>strlen（s）||pos<0）return0;//>strlen（s）,not>=
elsereturn1;
}
intmyinsert（char*s,char*t,intpos）
{
chartemp1[MAXSIZE];
chartemp2[MAXSIZE];
intstate=checkInsert（s,t,pos）;
if（state==0）
{
printf（"操作未能成功！
\n"）;
return0;
}
if（state==1）mycombine（s,t,s）;
if（state==2）
{
mycut（s,temp1,pos,0）;
mycut（s,temp2,strlen（s）-pos,pos）;
mycombine（temp1,t,temp1）;
mycombine（temp1,temp2,s）;
}
}
//插入检查
intcheckInsert（char*s,char*t,intpos）//无法用char作为返回值类型吗？
{
intis=strlen（s）;
intit=strlen（t）;
if（pos<0||is+it>MAXSIZE||pos>MAXSIZE）return0;//error
if（pos>is）return1;//append
if（pos}
//合并
intmycombine（char*t1,char*t2,char*s）
{
if（checkCombine（t1,t2,s）==0）
{
printf（"操作未能成功！
\n"）;
return0;
}
intm=strlen（t1）;
intn=strlen（t2）;
inti;
for（i=0;i{
s[i]=t1[i];
}
for（i=0;i{
s[m+i]=t2[i];
}
s[m+n]='\0';
}
intcheckCombine（char*t1,char*t2,char*s）
{
intm=strlen（t1）;
intn=strlen（t2）;
if（m+n>=MAXSIZE）return0;
elsereturn1;
}
intmydelete（char*s,intlen,intpos）
{
chartemp1[MAXSIZE];
chartemp2[MAXSIZE];
if（checkDelete（s,len,pos）==0）
{
printf（"len或pos参数错误！
\n"）;
return0;
}
mycut（s,temp1,pos,0）;
mycut（s,temp2,strlen（s）-pos-len,pos+len）;
mycombine（temp1,temp2,s）;
}
intcheckDelete（char*s,intlen,intpos）
{
if（len<=0||strlen（s）strlen（s））return0;
elsereturn1;
}
//演示二,链表的查找、删除、计数、输出以及合并
voidDemo2（）
{
intselect;//选择的菜单项
intlen;//要删除的字符串长度
intpos;//在原字符串中的位置
charSearc
升级会员 