kmp数据结构课程设计报告

课程设计(论文)任务书

院 专 业班

一、课程设计(论文)题目 模式匹配算法的应用 二、课程设计(论文)工作自 年 月 日起至 年 月 日止。

三、课程设计(论文) 地点: 四、课程设计(论文)内容要求： 1．课程设计的目的

为了配合《数据结构》课程的教学，使学生能更深刻的领会《数据结构》课程的 重要性，特开设此课程设计；编写一些在特定数据结构上的算法，通过上机调试，更 好的掌握各种数据结构及其特点，培养学生综合运用所学理论知识解决复杂实际问题 的实践能力、研究性学习能力和团队合作能力。

2．课程设计的任务及要求 1）基本要求

（1）课程设计前必须选定课程设计题目，并认真进行需求分析与系统设计； （2）上机调试之前要认真准备实验程序及调试时所需的测试数据；

（3）独立思考，独立完成，严禁抄袭，调试过程要规范，认真记录调试结果； （4）上机结束后认真规范撰写课设报告，对设计进行总结和讨论。

2）课程设计论文编写要求

（1）要按照书稿的规格撰写打印课设论文

（2）论文包括任务书、目录、绪论、正文、总结、参考文献、附录等

（3）正文中要有问题描述、抽象数据类型的定义、数据的存储结构、设计的求解

算法、算法的实现、调试分析与测试结果 （4）课设论文装订按学校的统一要求完成

3）课设考核

从以下几方面来考查： （1）考勤和态度；

（2）任务的难易程度及设计思路；

（3）动手调试能力；

（4）论文撰写的水平、格式的规范性。

4）参考文献

[1] 严蔚敏, 吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社, 2007年. [2] 严蔚敏, 吴伟民. 数据结构题集（C语言版）[M]. 北京：清华大学出版社, 2007年. [3] 谭浩强. C语言程序设计[M]. 北京：清华大学出版社，2006年.

5）课程设计进度安排

内容 天数 地点 构思及收集资料 1 图书馆 程序设计与调试 3 计算机房 撰写论文 1 图书馆

6）任务及具体要求

1)英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必 工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和 出现位置所在的行的行号，格式自行设计。待统计的“单词”在文本串中不跨行出现， 它或者从行首开始，或者前置以一个空格符。 2)模式匹配要基于KMP算法。

学生签名：

2015年01 月05 日

课程设计(论文)评审意见

（1）考勤和态度 ：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ） （2）任务难易及设计思路 ：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ） （3）动手调试能力评价 ：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ） （4）论文撰写水平及规范性评价：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）

评阅人： 职称： 讲师

年 月 日

目 录

1 绪 论 ............................................. 1

1.1模式匹配算法 ............................................ 1

1.1.2普通模式匹配算法 ................................................................................... 1 1.1.3KMP算法的改进思路及意义 ................................................................ 1 1.2编程环境 ................................................ 2

2程序设计 ........................................................................................................................ 2

2.1需求分析 ................................................ 2

2.2概要设计 ............................................... 2

2.2.1 建立和读入文本文件............................................................................... 2 2.2.2 存储结构设计 ........................................................................................... 3

2.3模块设计 ............................................... 3 2.4.子程序及功能设计 ....................................... 3

3详细设计 ....................................................................................................................... 4

3.1 数据类型定义 ........................................... 4 3.2 系统主要子程序详细设计 ................................ 4

4调试分析与结果 ........................................................................................................ 7

4.1 实验数据 ................................................ 7

4.2 程序运行截图 ............................................ 7 4.3 调试过程 ............................................... 10 4.4 待完善部分 ............................................. 10

5课设总结 .......................................................................................................................11 参考文献 ...........................................................................................................................11 附 录 ............................................................................................................................ 12

1 绪 论

1.1模式匹配算法

为了实现通过查询某些词汇在文章中出现的次数及位置来研究文学作品及作者的功能，以及基于KMP算法的要求 ，我设计了名为文学助手的小程序，该程序基于模式匹配算法中的KMP算法，KMP算法是字符串匹配中的一种，KMP算法是一种高效的模式匹配算法，复杂度可以达到O(m+n)，而普通模式匹配算法的复杂度为O(m*n)，与KMP算法相关的还有MonteCarlo随机算法 及改进的LasVegas算法，由于时间有限及课设要求下面只简绍KMP算法与普通算法。

1.1.2普通模式匹配算法

从主串的第一个字符（或者给定的第pos个字符）开始和子串的第一个字符开始比较，若相等，则继续比较后面的字符。若不相等，则从主串本次开始比较的字符的下一个字符开始，与子串的第一个字符进行比较（即主串需要回退到本次比较开始字符的下一字符，模式串回退到首字符，主串与子串都需要回退）。

匹配成功的标志：比较到子串的’\0’

匹配失败的标志：比较到主串的’\0’，且此时子串的比较位不等于’\0’。算法复杂度：O(m*n）

1.1.3KMP算法的改进思路及意义

在普通匹配算法中子串与模式串都需要回溯，但这些回溯不是必要的。因为当某一位发生失配时，可以根据已匹配的结果进行判断。该算法问题可以理解为，当模式串中的第k位与主串的第i位比较时发生不匹配时，需要将模式串向右滑动到哪里继续与主串的第i位进行比较，避免了不必要的主串回溯，减少了模式串回溯的位数，从而使算法复杂度提升到O(m+n）。< …… 此处隐藏：3315字，全部文档内容请下载后查看。喜欢就下载吧 ……