文档介绍：数据结构课程设计
设计说明书
模式匹配中的KMP算法的实现
学生姓名
学号
1118042026
班级
专升本1101
成绩
指导教师
计算机科学与技术系
2011年 9 月 9 日
课程设计任务书
2011—2012学年第一学期
专业: 计算机科学与技术学号: 1118042026 姓名:
课程设计名称: 数据结构课程设计
设计题目: 模式匹配中的KMP算法的实现
完成期限:自 2011 年 8 月 29 日至 2011 年 9 月 9 日共 2 周
设计内容:
用C/C++编写一个程序实现字符串的查找。要求使用KMP匹配算法,从键盘输入一段文本和待查找文本,若文本中含有待查找文本,则程序能够自动找出待查找文本的位置,若没有则给出提示。
设计要求:
1)问题分析和任务定义:根据设计题目的要求,充分地分析和理解问题,明确问题要求做什么?(而不是怎么做?)限制条件是什么?确定问题的输入数据集合。
2)逻辑设计:对问题描述中涉及的操作对象定义相应的数据类型,并按照以数据结构为中心的原则划分模块,定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明),各个主要模块的算法,并画出模块之间的调用关系图;
3)详细设计:定义相应的存储结构并写出各函数的伪码算法。在这个过程中,要综合考虑系统功能,使得系统结构清晰、合理、简单和易于调试,抽象数据类型的实现尽可能做到数据封装,基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精,写出数据存储结构的类型定义,写出函数形式的算法框架;
4)程序编码:把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言,使程序中逻辑概念清楚;
5)程序调试与测试:采用自底向上,分模块进行,即先调试低层函数。能够熟练掌握调试工具的各种功能,设计测试数据确定疑点,通过修改程序来证实它或绕过它。调试正确后,认真整理源程序及其注释,形成格式和风格良好的源程序清单和结果;
6)结果分析:程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析;
7)编写课程设计报告;
以上要求中前三个阶段的任务完成后,先将设计说明数的草稿交指导老师面审,审查合格后方可进入后续阶段的工作。设计工作结束后,经指导老师验收合格后将设计说明书打印装订,并进行答辩。
指导教师(签字): 教研室主任(签字):
批准日期: 2011年 8月 29 日
摘要
本次课程设计通过使用KMP算法将模式匹配算法进行了简化。,因此人们称它为克努特—莫里斯—普拉特操作(简称为KMP算法)。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。通过使用KMP匹配算法,从键盘输入一段文本和待查找文本,若文本中含有待查找文本,则程序能够自动找出待查找文本的位置,若没有则给出提示。
关键字:KMP算法;模式匹配;待查找文本
目录
1课题描述 1
2问题定义和任务分析 2
3逻辑设计 3
4详细设计 6
5程序编码 7
6程序调试与测试 9
7结果分析 10
8总结 12
参考文献 13
1课题描述
字符串子串在原串中的定位操作通常称为字符串的模式匹配,是各种传处理系统中最重要的操作之一。字符串定位字串的方法比较多,这里实现用KMP算法来实现模式穿的匹配,给出模式串,要求程序求出其Next[j]。KMP匹配算法高效的部分就是此次匹配失败后下次比较开始位置的确定,这样每次平均移动的字符就不止一个,大大减少了循环的次数,而且比较指针没有回调,提高了效率。设计思想:这个算法的关键在于,当某个位置的匹配不成功的时候,,其中next数组中的元素满足这个条件:next[j] = k,表示的是当模式字符串中的第j + 1个发生匹配不成功的情况时,应该从模式字符串的第k + 1个字符开始新的匹配。
2问题定义和任务分析
本课设要求使用KMP匹配算法,从键盘输入一段文本和待查找文本,若文本中含有待查找文本,则程序能够自动找出待查找文本的位置,若没有则给出提示。KMP算法是模式匹配的一种模式匹配算法的升级。其改进在于每当一趟匹配过程中出现字符比较不等时,不需回溯i指针,而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后,继续进行比较。KMP匹配算法高效的部分就是此次匹配失败后下次比较开始位置的确定,这样每次平均移动的字符就不止一个,大大减少了循环的次数,