《数据结构》
课 程 设 计 报 告
题 目：模式匹配算法KMP及其应用
学院（系）： 班 级 ： 学生学号 ： 姓 名 ：
指导教师：
日期：
目录
摘要..........………………...…………………………………………………….1 一、 绪论???????????????????????2
1. 课程设计的背景??????????????????2 2. 课程设计的意义??????????????????3 3. 开发平台及其简介?????????????????3 二、 需求分析?????????????????????3 三、 可行性分析????????????????????5 四、 概要设计
1. 功能设计要求???????????????????5 2. 总体结构设计???????????????????6 3. 抽象数据类型串的定义???????????????9 4. 函数调用关系???????????????????10 5. 主程序调用????????????????????11 五、 详细设计?????????????????????12
1. 宏定义??????????????????????12 2. 数据元素结构定义?????????????????13 3. 功能具体实现???????????????????13 4. 主程序和菜单设计?????????????????29 六、 设计和调试分析??????????????????31 七、 测试结果?????????????????????33 八、 设计心得体会???????????????????37 九、 用户手册?????????????????????37 十、 附录???????????????????????43 十一、参考文献?????????????????????44
摘要
本程序主要是通过获取一个子串，或新建一个新的文本文件，或和已有的文本文件进行匹配，分别利用了串的朴素模式匹配算法、串的模式匹配KMP算法、串的模式匹配改进算法等数据结构中学的知识实现了，在和文本文件中的主串进行匹配后返回子串在文本文件中出现的次数和出现位置所在的行的行号。
本程序除了实现串在定长顺序存储结构下的三种模式匹配算法，还实现了串在单链表存储结构下的模式匹配KMP算法，通过比较了串的不同存储结构下串的模式匹配算法，进一步加强了对串的理解及串的各类模式算法的掌握。
在使用串的定长存储结构时，考虑到书本上实现串的KMP算法时，储存串的数组下标是从1开始，为了进一步理解串，本程序另辟蹊径，特地定义了一个结构体，结构体中用来存储串的数组下标是从0开始，实现了串的模式匹配KMP算法。
本程序容错性强，功能齐全。整个程序设计从用户的角度出发，把用户的需求作为本程序设计的标准，因此菜单设计非常的人性化，且界面设计优美。同时，本程序还对串的模式匹配算法可能的应用作了设想，例如串的模式匹配在串的查找与替换功能中的应用等等。
本程序安全逻辑严密，且安全系数较高，设计了登录功能，如果没有使用权限则无法使用本系统。此外，本程序的菜单设计合理，菜单功能齐全，中间合理的提示可以让用户更好更快的掌握本系统的使用。
关键字：串 匹配 KMP KMP改进 定长顺序存储
1
一、绪论
1、
课程设计的背景
《数据结构》作为一门独立的课程最早是美国的一些大学开设的,1968年美国唐欧克努特教授开创了数据结构的最初体系,他所著的《计算机程序设计 技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及 其操作的著作.从 60 年代末到 70 年代初,出现了大型程序,软件也相对独立, 结构程序设计成为程序设计方法学的主要内容,人们就越来越重视数据结构,认为程序设计的实质是对确定的问题选择一种好的结构,加上设计一种好的算法. 从 70 年代中期到 80 年代初,各种版本的数据结构著作就相继出现. 目前在我国,《数据结构》也已经不仅仅是计算机专业的教学计划中的核心 课程之一,而且是其它非计算机专业的主要选修课程之一.
《数据结构》在计算机科学中是一门综合性的专业基础课.数据结构的研究 不仅涉及到计算机硬件 (特别是编码理论, 存储装置和存取方法等) 的研究范围, 而且和计算机软件的研究有着更密切的关系,无论是编译程序还是操作系统,都 涉及到数据元素在存储器中的分配问题. 在研究信息检索时也必须考虑如何组织 数据, 以便查找和存取数据元素更为方便. 因此, 可以认为数据结构是介于数学, 计算机硬件和计算机软件三者之间的一门核心课程,在计算机科学中,数据结构 不仅是一般程序设计(特别是非数值计算的程序设计)的基础,而且是设计和实 现编译程序,操作系统,数据系统及其它系统程序和大型应用程序的重要基础. 值得注意的是,数据结构的发展并未终结,一方面,面向各专门领域中特殊 问题的数据结构得到研究和发展,如多维图形数据结构等;另一方面,从抽象数 据类型的观点来论数据结构,已成为一种新的趋势,越来越被人们所重视.
2、
课程设计的意义
数据结构是一门实践性很强的学科。良好的系统设计和分析能力的培养需要通过长期、系统的训练(包括理论和实践两方面)才能获得。高等学校的实践教学一般包括课程实验、综合性设计(课程设计)、课外科技活动、社会实践、毕业设计等，基本上可以分为三个层次：第一，是紧扣课堂教学内容，以掌握和巩固课程教学内容为主的课程实验和综合性设计；第二，是以社会体验和科学研究体验为主的社会实践和课外科技活动；第三，是以综合应用专业知识和全面检验专业知识应用能力的毕业设计。课程实践(含课程实验和课程设计)是大学教育中最重要也最基础的实践环节，直接影响后继课程的学习以及后继实践的质量。由于课程设计是以培养学生的系统设计与分析能力为目标，通过团队式合作、研究式分析、工程化设计完成较大型系统或软件的设计题目的，因此课程设计不仅有利于学生巩固、提高和融合所学的专业课程知识，更重的是能够培养学生多方面的能力，如综合设计能力、动手能力、文献检索能力、团队合作能力、工程化能力、研究性学习能力、创新能力等。
数据结构课程是计算机专业最重要的基础课之一，主要研究分析计算机存储、组织数据的方式，使学生学会数据的组织方法和现实世界问题在计算机内部的表示方法，并能针对应用问题，选择合适的数据逻辑结构、存储结构及其算法，掌握解决复杂问题的程序设计方法和技术。选择合适的数据结构更容易设计出更高效运行或存储效率的算法；反之，选择了特定的算法后也需要设计合适的数据结构与之配合，以达到最佳效果。所以，在进行程序设计时必须将数据结构和与之相关的算法结合起来考虑。
2
数据结构课程的学习离不开实践。针对数据结构的程序设计实践不仅可以加深对课程内容的理解，更重要的是可以通过实践进一步掌握程序设计的技能与方法，初步感受软件开发过程的项目管理方法与规范，为更进一步的学习打下基础。
数据结构的课程实践可分一般性的实验和综合性的课程设计。在传统的课程教学中，往往使用一般性的实验作为课程实践的主要内容，即向学生布置直接针对课堂教学内容的小型练习题，由学生独立进行程序设计与上机实现；而综合性的课程设计则更强调知识的整合、问题分析与求解能力以及团队合作能力的培养。因而，课程设计更能培养学生综合运用所学理论知识解决复杂问题的实践能力、研究性学习能力和团队合作能力。 课程设计不仅仅是以实现相应的程序为目标，更重要的是在完成课程设计的过程中逐步培养今后从事软件开发所需要的各种能力与素质。其中很重要的一种能力就是软件文档的写作能力。因此，在课程设计实施中，不仅需要完成程序并进行测试，还需要撰写相应的课程设计报告。课程设计报告不仅是对课程设计的总结，也是对软件文档写作能力的初步训练。
3、
课程设计的开发平台及其简介
在本课程设计，系统开发 平台为visual C++6.0，程序语言是C语言，程序的运行环境是Visual C++6.0。Visual C++6.0一般分为三个版本：学习版、专业版和企业版。不同的版本适合不同类的应用开发。实验中可以使用这个三个版本的任意一种，在本课程设计中，以Visual C++6.0为编程环境。
Microsoft Visual C++6.0是Microsoft公司的Microsoft Visual Studio 6.0工具箱中的一个C++程序开发包。Visual C++包中除C++编译器外，还包括所有的库、例子和为Windows应用程序所需要的文档。自1993年Microsoft公司推出Visual C++1.0后，随着其新版本的不断问世，Visual C++已成为专业程序员进行软件开发的首选工具。Visual C++从最早期的1.0版本，发展到最新的7.0版本，Visual C++已经有了很大的变化，在界面、功能、库支持方面都有许多的增强。最新的7.0版本在编译器、MFC类库、编辑器以及联机帮助系统等方面都比以前的版本做了较大的改进。
虽然微软公司推出了Visual C++.NET（Visual C++7.0），但它的应用的很大的局限性，只适用于Windows 2000，Windows XP和Windows NT4.0。所以实际应用中，更多的是Visual C++6.0为平台。
Visual C++6.0是Microsoft公司推出的目前使用最广泛的基于Windows平台的可视化编程环境。Visual C++6.0是在以往版本不断更新的基础上形成的，由于其功能强大，灵活性好，完全扩展以及强大的Internet支持，因而在各种C++语言开发工具中脱颖而出，成为目前最为流行的C++语言集成开发环境。
Visual C++6.0秉承Visual C++以前版本的优异特性，为用户提供了一套良好的可视化开发环境：主要包括文本编辑器、资源编辑器、工程创建工具、Degugger调试器等等。用户可以在集成开发环境中创建工程、打开工程、建立、打开和编辑文件、编译、链接、运行、调试应用程序。
二、需求分析
1、英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所
3