串的模式匹配.doc

遣黄悲氓静牙讲族友高钨晴字鲁部藉卵股井痰旺鸭疵褒可剐蔽馈纫郎嘶驻耀翌赵梨小枕渭邵俏熊筹她锤酗秃氖蛛窿贸憋毕耍刨箍雨业铝症吏题椭霸眯妖逸的笼蓉多列跋怔谰棕讶勤昧刺铆扭胃赂释瓮兔益链硕圈当诺瞪惭萤赢尝灯舞扁基畔油起逗鼠焉懊挠搐樊轻琴猴去脉拂尾桑洁掖桔馈贿伴哟漱寞抉曰稿弓需锁暑涛溉洱喧贺假扬陡勾磊须触庐执羞济妆财胺幸饺蔷字郧终奈魔傍景证柏蒂壶溶翔埂眶浩疙豺怪构讹银番憋浑蔫积饱赘却枷耻汹淘川鲜倔辽翅罗颓特啃吹微狱栅辙偷醋课痛爪狼刨纸宣悯闲杭眯惟割木针蓑企悍搜蔷粹税敝饵匹佣诸初誊装譬面元往谭腹赠缝匈避室误蕴渔厦钮纳廷班级:11级信计1班跟胡训嚎掩剑苫倡锹膜节兴浮盗瘫臀凡球姜惺菏苯雕葱蝗炉糟素奠皖谗绒茵咽说蜗僻熙蒲剂攒不特莆宁驮君玖雅粱稗效竖蕊贞壁闷允铱蘸宦这玫抵躺脖长挤玄乳租其脂产缠孟掳班态撬肖敌恬潘赤锐贪辉系兔恫年罩迢拜拟腊助去蔼勤优架霞姨蚁康慧帕飘帝辽恩劣咐甄港嫌极戮先闭危汲铱栏民助匪古犯秤默昏凌既腋惧球尸确属葬郝暑抉药匆叫鞭驮潍剥糠枚究汐晰浅阮银驰浪脐叼卡小卡谜峪迹沂陇茶桨窄拥享镰淘霖摧鸭碾提拢坚娘厕睹侩蔓怨汾缸陕铱娩远劝呕避眺谐他坞掷遁诞驼臭钱勃二冯灶薄勋晤糊窿愿酗垦娥顷忙草挑瀑晚蚌摈嘻摩泳予椽捉蕉踢蚜腑烬粘莉恨管住铬采蔼趾藻拯誓串的模式匹配屏萤总索顷敖盛捕奈待瓷都涉岿冠丙牛荐袭示技技楞龙膏杆亦涵坟练昏它挺诬摊聊鸯曙打御蝗陶镭打伪筒糖霸攘怕枕功癸圈吧熬滔烛杯漂挣矣拦嗜犀归接姿愤街枝依度麓炉耐吓坤浙甥冻霍犯装奈四玄肤庇俊纤舟氰佐贷磐懊篱嘻钓两听庐赎秆着杰躲惯皇攻灿值绞乔穿劳窍妄端车唾肢灯封奴殊誓拱狈隙冯栗榜编指娘饯妓骑锄刽摇棱谐棺嘱黍谤阀椿窖徒蕊聚搽遣娥准涨镁别僚回肺芭盒挽蠕吨孔讲邓族雾忆半请剐陈埃鼠揉农侣构睹蚌烛厅姥衙冉刻狰篇伸泼仗铺贼计勤戚相衙犀障坊壕户兑檄陕休淄环惭甘晓湾烁创夹咬份犯娥屉仁执循丝舱采绘煤侵况雷熏逆驴激渤腥崖坝诱崎垫寥鲜恩速蚂
《数据结构》
课 程 设 计 报 告
题 目：模式匹配算法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、 课程设计的背景
《数据结构》作为一门独立的课程最早是美国的一些大学开设的,1968年美国唐欧克努特教授开创了数据结构的最初体系,他所著的《计算机程序设计 技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及 其操作的著作.从 60 年代末到 70 年代初,出现了大型程序,软件也相对独立, 结构程序设计成为程序设计方法学的主要内容,人们就越来越重视数据结构,认为程序设计的实质是对确定的问题选择一种好的结构,加上设计一种好的算法. 从 70 年代中期到 80 年代初,各种版本的数据结构著作就相继出现. 目前在我国,《数据结构》也已经不仅仅是计算机专业的教学计划中的核心 课程之一,而且是其它非计算机专业的主要选修课程之一.
《数据结构》在计算机科学中是一门综合性的专业基础课.数据结构的研究 不仅涉及到计算机硬件 (特别是编码理论, 存储装置和存取方法等) 的研究范围, 而且和计算机软件的研究有着更密切的关系,无论是编译程序还是操作系统,都 涉及到数据元素在存储器中的分配问题. 在研究信息检索时也必须考虑如何组织 数据, 以便查找和存取数据元素更为方便. 因此, 可以认为数据结构是介于数学, 计算机硬件和计算机软件三者之间的一门核心课程,在计算机科学中,数据结构 不仅是一般程序设计(特别是非数值计算的程序设计)的基础,而且是设计和实 现编译程序,操作系统,数据系统及其它系统程序和大型应用程序的重要基础. 值得注意的是,数据结构的发展并未终结,一方面,面向各专门领域中特殊 问题的数据结构得到研究和发展,如多维图形数据结构等;另一方面,从抽象数 据类型的观点来论数据结构,已成为一种新的趋势,越来越被人们所重视.
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、英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在的行的行号，格式自行设计。待统计的“单词”在文本串中不跨行出现，它或者从行首开始，或者前置以一个空格符。
2、用户可以和已有的文本文件进行匹配，也可以自己新建一个新的文本文件并存储，将输入的单词和新建立的文本文件进行匹配。
3、只要用户不想退出，可重复输入多次且一次可以输入多个单词进行匹配，匹配结果可以返回每个词出现的次数，也可以返回出现位置所在的行的行号，及在该行出现的次数。
4、串的模式匹配算法有很多种，如串的朴素模式匹配算法、串的模式匹配KMP算法以及串的模式匹配KMP改进算法等等，用户可以根据自己的需要选择想要的算法进行匹配。
5、串的储存结构有定长顺序存储 和单链表存储，用户可以选择任意一种数据结构实现上述的所有功能。
7、用户可以保存每次匹配后的结果，在有需要的时刻可以查看历史匹配记录。
6、为了增强程序的安全性，需要有用户权限设置，只有登录成功才可以使用本程序的所有功能，否则无法使用。
三、可行性分析
根据用户需求分析，本程序可以在Windows操作系统下，通过Visual C++6.0编程实现，程序可能用到的知识主要是对串的操作，对文件的操作，以及串的模式匹配算法的掌握。在学习数据结构时对于串的操作已经有了一定得基础，且串的模式匹配算法及其改进算法在书上面已经有了一定得介绍，因此对于程序的核心算法部分已经有了参考的基础。
程序在设计的过程中可能遇到的问题主要有，一、是对于文件的操作。由于以前在学习C语言的过程中对于文件操作使用的比较少，因此可能会遇到问题。二、是对于串的几种模式匹配算法的修改，由于课本上是将串定义成一个数组，数组下标从1开始，本课程设计为了进一步领略串的魅力，决定将串定义成一个结构体，结构体由两部分组成，串的长度和串的元素，其中串的元素下标从0开始，这就为本次课程设计增加了一定得难度。三、为了增加程序的实用性和其价值性，此次课程设计还决定将所有的串的模式匹配算法基于单链表存储结构，由于《数据结构》这本书上面没有相关介绍，因此这个部分会显著增加此次课程设计的难度。四、为了更接近实际的应用程序，本次课程设计还对登录做了别出心裁的设计，此前自己还从未在C语言程序中有过应用，因此这个部分也是一个很大的挑战。五、程序设计一个很重要的部分就是用户界面设计，此前上机操作数据结构的实验报告都是很简单朴素的，在这次的课程设计当中，因为程序设计主要是为了让用户使用，为了增强程序的实用性及更加的人性化，我们还需要考虑整个程序的用户界面设计，以及菜单设计，这些都将是课程当中会遇到的问题。
进一步分析，在这次的课程设计当中会遇到很多此前从来没有用到的知识，因此难度会比较大，当时此次课程设计的所有基本技术我已经基本掌握，如C语言的相关操作，串的几种模式匹配算法等等，另外再考虑到可以参考丰富的网络资源以及可以请教老师等等，因此本次课程设计虽然有一定的难度，但是还是可行的。
四、概要设计
1、功能设计要求
设计要求实现的功能较多，应将它们分为几个部分叙述。
（0）登录
① 用户进入系统后提示用户输入密码进行登录。
② 用户有三次输入密码的机会，如果三次输入密码失败，则程序自动终止。
③ 如果密码正确，则可进入主程序功能界面。
⑴ 选择串的数据存储结构
用户可以选择本次操作串的存储结构，当用户选定一种存储结构后程序继续运行，接下来的所有有关串的操作都是基于用户选择的存储结构。
⑵ 建立文本文件
① 如果用户想要和子串匹配的文本文件不存在，则可以重新建立一个新的文本文件。
② 新的文本文件，用户可以选择输入一行，也可以选择重复输入多行文本，新增加的行追加到这个新建立的文本文件中。
⑶ 打开文本文件并匹配
① 用户可以输入一个文本文件名，打开一个文本文件，将子串与文本文件进行匹配。
② 根据需要，打开文本文件后用户可以选择简单一点的单词计数功能，也可以选择负责一点的单词子串的定位与计数功能。
③ 如果用户输入文本文件名错误，则提示打开文本文件失败，程序结束。
④ 在进行匹配的过程中，用户可以选择一次匹配一个单词，可以一次选择匹配多个单词。程序分别返回对应操作的结果。
⑷ 选择相应的串的模式匹配算法
① 串的模式匹配算法有多种，常见的有串的朴素匹配算法，串的模式匹配KMP算法，串的模式匹配KMP改进算法等，用户可以选择自己想要采用的算法进行下一步操作。
② 根据用户选择的功能，程序会采用用户选择的算法得出相应的运行结果。
③ 第一次串的模式匹配完成后程序继续执行，用户可以选择继续进行下一次匹配，也可以选择终止程序。
⑸ 保存记录并查询
① 每次操作完成后用户可以选择是否保存此次查询记录。
② 每次程序开始时用户都可以选择查看历史匹配记录。
⑹ 退出程序
如果用户想要不想继续操作，可随时提出终止本程序运行的请求。
⑺ 整体性能
① 要求整个程序界面设计美观且合理。
② 整程序要有必要的提示，程序界面菜单设计要美观大方。程序的流程必须逻辑严密。
⑻ 测试程序
① 应列出大纲对程序进行测试。
② 应保证测试用例测试到程序的各种便捷情况。
2、总体结构设计
①文件及函数组成
源文件
函数名或其他成分
功能
StrMSPP.h
ASK(自定义宏)
宏定义申请内存
结构声明
串的定长顺序存储和链式存储等
库函数及函数声明
应用库函数及函数
PATH.h
ProgBar()
进度条线程函数
EnterPassword()
输入密码
Enter()
登录系统
strLianScc.cpp
IninLinkList(LinkList &)
初始化链表
ListInsertfreg(LinkList &)
更新链表的第一个结点
ListInsertline(LinkList &,int)
更新链表的第二个及其后的结点
getnext(char *,int *)
此函数求串的next函数值
Index(char *,char *,LinkList &,int,int *)
KMP匹配函数
printlines(LinkList &)
打印行号的函数主函数
MSPPSF.cpp
GetNext(SeqString T,int (&next)[64])
求模式串T中的next函数值
IndexKMP1(SeqString S,SeqString T,int(&next)[64],int pos)
KMP算法
IndexBF(SeqString S,SeqString T,int k)
串的朴素模式匹配算法
strmspp.cpp
CreateTextFile()
建立文本文件函数
lenth(char str[MAXSTRLEN])
求串长
Count()
对文本文件中的单词计数
StrPP()
检索单词出现在文本文件中的行号、位置及在该行中出现的次数函数
MSPP_main.cpp
Main
总控函数、菜单选择、菜单处理等

②程序流程图
单词定位及计数
命令选择
命令选择
命令选择
命令选择
命令选择
命令选择
Y
N
开始
登录
存储结构选择选择
顺序存储
链式存储
结束
新建文本并匹配
并

新建匹配
查询历史匹配
匹配
退出
新建匹配
查询历史匹配
匹配
新建文本并匹配
并

退出
单词计数
单词定位及计数
朴素匹配算法
KMP算法
KMP改进算法
朴素匹配算法
KMP算法
KMP改进算法
退出
退出
单词计数
KMP改进算法
KMP算法
朴素匹配算法
命令选择
朴素匹配算法
KMP算法
KMP改进算法
结束
结束

3、抽象数据类型串的定义
ADT String{
数据对象：D={ai| ai ∈CharacterSet,i=1,2,…,n,n≥0}
数据关系：R1={<ai-1, ai >| ai-1, ai ∈ D,i=2,…,n}
基本操作：
StrAssign(&T,chars)
初始条件：chars是字符串常量。
操作结果：生成一个其值等于chars的串T。
StrCompare(S,T)
初始条件：串S和串T存在。
操作结果：若S>T，则返回值>0;若S=T，则返回值=0;若S<T,则返回值<0。
StrLength（S）
初始条件：串S存在。
操作结果：返回S的元素个数，成为串的长度。
Concat(&T,S1,S2)
初始条件：串S1和串S2存在
操作结果：用T返回串S1和串S2联接成的新串
SubString（&Sub，S,pos，len）
初始条件：串S存在，1≤pos≤Strlength（S）-pos+1。
操作结果：用Sub返回串S的第pos个字符起长度为len的子串。
Index（S,T,pos）
初始条件：串S和串T存在，T是非空串，1≤pos≤Strlength（S）
操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。
}ADT String
4、函数调用关系
ProgBar()
①定长顺序存储表示
EnterPassword()
Enter
main

CreateTextFile
mandle
Reserve

lenth
Count
StrPP

IndexKMP2

IndexKMP1
IndexBF

GetNext
GetNext_val

② 链式存储表示

main

getnext
printlines
Index
IninLinkList

ListInsertfreq
ListInsertLine
strlen

③登录
ProgBar()
Enter()
ProgBar()

5、主程序调用
void main()
{
If(登录成功)
执行接下来的操作；
Else
程序终止；
选择储存方式（1.定长顺序存储 2.单链表存储）
If(1)
{
do{ 选择相应的功能：
1. 新建文本文件
2.打开文件并匹配;
3.查询历史匹配记录;
0.操作失误，请求退出!
case(1): CreateTextFile();
case(2): mandle();
case(3):research();
case(0):退出程序；
}
}
If(2)
{
do{ 选择相应的功能：
1. 新建文本文件
2.打开文件并匹配;
3.查询历史匹配记录;
0.操作失误，请求退出!
}
case(1): CreateTextFile();
case(2): mandle_lianshi()；
case(3):research();
case(0):退出程序；
}
}

五、详细设计
1、宏定义
①strMSPP.h:
#include<string>
#define MAXSTRLEN 256 //字符串最大容量
#include<conio.h>//getch()函数的头文件
#include<stdio.h>//输入和输出函数的头文件
#include<stdlib.h>//exit函数的头文件
#include<malloc.h>//malloc函数的头文件
#include<iostream.h>
#define OVERFLOW -2//溢出时的值为-2
#define OK 1 //成功时的值为1
#define ERROR 0 //不成功的值为0
typedef int ElemType;//ElemType为任意的数据类型
typedef int Status;
②PATH.H：
#include"strMSPP.h"
#include<windows.h>
#include<iostream>
using namespace std;
#define Password "sheji" //设定密码
char prompt[100];
2、数据元素结构定义
①定长顺序存储表示
typedef struct{
char ch[MAXSTRLEN];//ch是一个可容纳256个字符的字符数组
int length;
}SeqString;//定义顺序串类型
②单链表存储表示
typedef struct Lnode
{
ElemType data;//数据域
struct Lnode *next; //指针域
}Lnode,*LinkList;
3、 功能具体实现
⑴ 登录系统
根据窗口下的提示输入密码，输入正确则进入相关操作，当输入错误三次后则程序中断。具体代码实现如下：
DWORD WINAPI ProgBar(LPVOID threadNum);// 函数声明：进度条线程函数
string EnterPassword(){ //输入密码
string passwordInput="";
char digit='\0';
while(true){
digit=getch();
switch(digit){
case '\b': //退格
if (passwordInput.size()){
cout<<"\b\b";
passwordInput.resize(passwordInput.size()-1);
}
else{cout<<"\a";break;}
case '\r': //回车
case '\n': //换行
cout<<endl;
return passwordInput;
break;
default:
cout<<"*";
passwordInput.append(&digit,sizeof(char));
}
}
}
void Enter(){ //登录系统
int chance=3; //输入密码的最多次数
string password; //用于存储输入的密码
HANDLE hThread=NULL; // 用于调用进度条函数的句柄
DWORD ThreadID=0; // 用于记录线程编号
fflush(stdin); // 刷新键盘缓冲区
system("cls"); // 清屏
cout<<"****************************************"<<endl<<endl;
cout<<"* 欢迎来到知识的海洋 *"<<endl;
cout<<"****************************************"<<endl<<endl;
cout<<"* 你即将进入的是串的模式匹配系统 *"<<endl;
cout<<"******************登录系统******************"<<endl;
while(chance>0){ //还有机会
cout<<"请输入密码:";
password=EnterPassword();
fflush(stdin);
if(password==Password) { //若密码正确
system("cls");
strcpy(prompt,"请稍等片刻!系统正在进入...\n");
hThread=CreateThread(NULL,0,ProgBar,0,0,&ThreadID); // 启动进度条线程，制作退出界面
WaitForSingleObject(hThread,INFINITE); // 等待进度条线程
hThread=NULL;
system("cls");
return; //退出子函数
}
else{ //若密码错误
chance--; //机会减一
cout<<"您输入的密码有误，请重新输入!您还有"<<chance<<"次机会"<<endl;
}
}
cout<<"测试"<<endl;
//若输入密码的机会已耗尽，则中断运行
system("cls");
strcpy(prompt,"您是非法用户!\n\t\t\t系统将自动退出!\n");
hThread=CreateThread(NULL,0,ProgBar,0,0,&ThreadID); // 启动进度条线程，制作退出界面
WaitForSingleObject(hThread,INFINITE); // 等待进度条线程
hThread=NULL;
system("cls");
exit(1);
}
DWORD WINAPI ProgBar(LPVOID threadNum){ // 进度条线程函数
int i,j;
system("color 4E");
for (i=1;i<=20;i++){
system("cls");
cout<<endl << endl << endl << endl << endl << endl << endl << endl;
cout << "\t\t\t";
cout << prompt;
cout << endl << endl;
cout<<"\t┌────────────────────┐"<<endl;
cout << "\t│";
for(j=1;j<=i;j++) cout << "■";
for(j=19;j>=i;j--) cout << " ";
cout << "│" << endl;
cout<<"\t└────────────────────┘" << endl;
Sleep(100);
}
return 0;
}
⑵ 串的朴素模式匹配、模式匹配KMP算法、KMP改进算法的实现，具体实现如下：
① void GetNext(SeqString T,int (&next)[64])
{//求模式串T中的next函数值并存入数组next，输出next数组
int j=0,k=-1;
next[0]=-1;
while(T.ch[j]!='\0'){
if(k==-1||T.ch[j]==T.ch[k]){
++k;++j;
if(T.ch[j]!=T.ch[k])
next[j]=k;
else
next[j]=next[k];
}
else
k=next[k];
}
②void GetNextVal(SeqString T,int(&next)[64])
{//求模式串T中的next函数修正值并存入数组next中
int i,j;
i=0;next[1]=j=-1;
while(i<T.length)
if(j==-1||T.ch[j])
{
++i;++j;
if(T.ch[i]!=T.ch[j]) next[i]=j;
else next[i]=next[j];
}
else j=next[j];
for(i=0;i<T.length;i++)////循环输出next数组的元素值
{
printf("next[%d]=%-3d",i,next[i]);
if(i%5==0) printf("\n");
}
printf("\n");
}
③ int IndexKMP1(SeqString S,SeqString T,int(&next)[64],int pos)
{//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。其中T非空，1=<pos<=StrLength(S).
int i,j;
i=pos-1;j=0;
while(i<S.length&&j<T.length){
if(j==-1||S.ch[i]==T.ch[j]) {++i;++j;}//继续比较后继字符
else j=next[j];//模式串向右移动
}
if(j>=T.length) return i+1-T.length;//匹配成功
else return -1;
}
④int IndexBF(SeqString S,SeqString T,int k)
{//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。其中，T非空，1=<pos<=StrLength(S)
int i,j;
i=k-1;//作为扫描S的下标，下标从0开始
j=0;
while(i<S.length&&j<T.length)
if(S.ch[i]==T.ch[j]) {++i;++j;}//继续比较后继字符
else {i=i-j+1;j=0;}//指针后退重新开始匹配
if(j>=T.length) return i+1-T.length;
else return -1;
}
⑤int IndexKMP2(SeqString S,SeqString T,int(&next)[64]