没有合适的资源?快使用搜索试试~ 我知道了~
毕业论文设计--数据结构课程设计报告.doc
0 下载量 186 浏览量
2023-06-28
02:12:26
上传
评论
收藏 1.81MB DOC 举报
温馨提示
试读
68页
毕业论文设计--数据结构课程设计报告.doc
资源推荐
资源详情
资源评论
数据结构课程设计
学院名称: 计算机工程学院
专 业: 信息管理与信息系统
班 级:
姓 名:
2015 年 1 月 7 日
目录
一、数据结构课程设计报告要求...............................................................................1
二、第一类题目...........................................................................................................2
2.1 问题陈述...............................................................................................2
2.2.程序代码................................................................................................2
2.3.运行结果................................................................................................4
2.4.设计体会与总结....................................................................................4
三、第二类题目...........................................................................................................4
3.1.问题陈述................................................................................................4
3.2.需求分析................................................................................................5
3.3.概要设计................................................................................................5
3.4.详细设计................................................................................................6
3.5.程序代码................................................................................................7
3.6.运行结果与测试..................................................................................18
3.7.设计体会与总结..................................................................................19
四、第三类题目.........................................................................................................20
4.1.问题陈述..............................................................................................20
4.2.需求分析............................................................................................20
4.3.概要设计............................................................................................20
4.4.详细设计............................................................................................21
4.5.程序代码............................................................................................40
4.6.运行结果与测试................................................................................58
4.7.设计体会与总结................................................................................65
五、课设总结.............................................................................................................65
六、参考文献.............................................................................................................66
0
《数据结构课程设计》报告要求
一、第一类题目(宋体,四号,加粗)
1.问题陈述(宋体,小四,单倍行距)
2.程序代码
3.运行结果
4.设计体会与总结
二、第二类题目(宋体,四号,加粗)
1.问题陈述(宋体,小四,单倍行距)
2.需求分析
3.概要设计
4.详细设计
5.程序代码
6.运行结果与测试
7.设计体会与总结
三、第三类题目(宋体,四号,加粗)
1.问题陈述(宋体,小四,单倍行距)
2.需求分析
3.概要设计
4.详细设计
5.程序代码
6.运行结果与测试
7.设计体会与总结
四、要求
1.标题为字体黑体,小三,居中
2.小标题为宋体,四号,加粗
3.正文要求为宋体,小四,单倍行距
4.每个段落缩进 2 个汉字(4 个空格)
5.每个人报告书不得雷同,尤其第二类与第三类题目,发现雷同者一律按
不及格论处。
6.相关内容可以参考《数据结构课程设计》指导书,但不得抄袭相关内容。
1
一、第一类题目(宋体,四号,加粗)
1.问题陈述(宋体,小四,单倍行距)
串的模式匹配:
字符串模式匹配算法是入侵检测系统中的一种重要算法。通过对算法 KMP
分析,该算法通过每次匹配失败时特殊位置上字符的启发来获得字符串向
后移动的可能距离,这个距离由定义的一个统一函数求出,取其中的最大
值作为字符串向后移动的实际距离。实验结果表明,该算法能减少模式匹
配中字符的比较次数和尝试次数,提高模式匹配的效率。
2.程序代码
#include"stdio.h"
#include"string.h"
typedef char DataType;
void GetNext(DataType *t,int *next,int tlength)//求模式串 t 的 next
函数值并存入数组 next
{
int i=1,j=0; //定义整型变量 i,j
next[1]=0; //初始化存
放部分匹配数组的 next 的第一项为-1
while(i<tlength) //当 i 小于字
符串的长度时,执行循环
{
if(j==0||t[i]==t[j]) //如果 j 刚开始
循环或者 i 和 j 表示的字符相同时
{
++i;++j; //i 和 j 都自增,即增加到 next 中 i 位置
的后一位,而 j 的增加也表示与 i 表示的字符相符的个数加 1
if(t[i]!=t[j]) //如果此时模式串中的 i 和 j 位置的字符不
等
next[i]=j; //将 j 的值赋给 next 数组,便于直接比较目标
串 s 与 t 在 next[j]处的值
else //如果模式串中的 i 和 j 位置的字符仍然相等
next[i]=next[j]; //将 j 的 next 中的值赋给 i 所在位置的值,
这样能够保证后面比较目标串和字串时,直接比较 t 在 next[j]处的值,
而不需要比较 t 在 j 处的值
}
else //如果 i 和 j
对应的字符不相同
j=next[j]; //继续后续比较
}
}
int IndexKmp(DataType *s,DataType *t,int pos,int tlength,int
slength,int *next)//利用模式串 t 的 next 函数求 t 在主串 s 中第 pos 个
字符之后的位置
2
{
int i=pos,j=1; //定义整型变
量 i,j
while(i<=slength&&j<=tlength) //当 i 和 j 都
未到达字符串末端时
{
if(j==0||s[i]==t[j]) //如果 j 刚开
始比较或者模式串和目标串对应的字符相等时
{
++i;++j; //i 和 j 均往后
移动,比较后续字符
}
else
j=next[j]; //否则,保持 i
不变,将 j 右滑动到下一个部分匹配位置
}
if(j>tlength) //如果 j 的大
小都大于 t(模式串)的长度,说明能够找到匹配的位置
return i-tlength; //返回此时 i
的值减去 t(模式串)的长度得到 t 在对应的 s 前方还有几个字符,即为它
们的匹配位置
else
return 0; //否则,即为
找不到匹配,返回 0
}
int main(int argc,char *argv[])
{
int locate,tlength,slength; //定义整型变
量表示它们的匹配和两个字符串的长度
int next[256]; //定义存放它
们部分匹配数值的数组
DataType s[256],t[256]; //定义字符数
组 s,t
printf("请输入第一个串(母串):");
slength=strlen(gets(s+1)); //目标串长度
printf("请输入第二个串(母串):");
tlength=strlen(gets(t+1)); //模式串长度
GetNext(t,next,tlength); //求部分匹配
数组 next
locate=IndexKmp(s,t,0,tlength,slength,next); //求出它们的
具体匹配位置
printf("匹配位置:%d\n",locate);
return 0;
}
剩余67页未读,继续阅读
资源评论
yyyyyyhhh222
- 粉丝: 412
- 资源: 6万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功