数据结构课程设计-字符串操作

《数据结构课程设计-字符串操作》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称《数据结构》课题名称字符串操作专业计算机科学与技术班级学号姓名联系方式指导教师2011年12月25日目录一、问题描述………………………………………………………1二、基本要求………………………………………………………1三、测试数据………………………………………………………1四、算法思想………………………………………………………11、注释………………………………………………….………12、模式匹配……………………………………………………..13、KMP算法……………

2、……………………………….………24、文本文件单词的检索与计数……………………………………2五、模块划分………………………………………….……………31、串的模式匹配…………………………………….…………32、字符串的加密与解密…………………………..……………43、文本文件单词的计数和检索……………………….…………4六、数据结构………………………………………………………4七、源程序（格式调整，添加注释）……………………………5八、测试情况………………………………………………………12九、参考文献……………………

3、…………………………………13十、总结……………………………………………………………14一、问题描述字符串是一种常见的数据类型，在现实生活中有着广泛的应用。本次课程设计需要选择合适的结构完成字符串的建立，实现串的基本操作，编写三种模式匹配算法和字符串的加密与解密算法，并利用它们实现字符串的应用:包括文本文件对单词的检索和计数。二、基本要求程序要求选择合适的存储结构，并实现以下功能：1.完成串的基本操作，如：串的赋值，比较，连接，插入，删除；2.实现串的模式匹配，包括：穷举法，BF算法和KMP算法；3.字符串的应用：

4、字符串的加密与解密；文本文件单词的计数；文本文件单词的检索；三、测试数据1.对模式匹配(穷举法，KMP算法和BF算法)的测试：如：在“asdsfhasdasd”中找从第3个下标开始匹配的模式串“asd”。2.对加密与解密的测试：如：对串“afhbs537hsj/sjdh”加密，再将加密后的串还原。3.对文本文件单词的计数和检索的测试：如创建一个文本文件，在其中对单词“me”进行计数并且检索其所处行、列。四、算法思想1、用结构体SString记录字符串信息，其中ch代表字符串，length代表字符串长度。2、模式匹配

5、：1）穷举法的Index（S,T,pos）：从位置开始通过SubString截取S中T长度的字符串，并与T通过StrCompare进行比较，若找到则返回位置；否则继续。若没找到，返回-1。2）BF算法：IndexBF(S,T,pos)主串S从pos位置开始，模式串T从0位置开始，从目标串s=“s0s2…sn-1"的第一个字符开始和模式串t=“t0t2…tm-1"中的第一个字符比较,若相等,则继续逐个比较后续字符；否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。依次类推,若从模式串s的i位置字符开始

6、,每个字符依次和目标串t中的对应字符相等,则匹配成功,该算法返回i；否则,匹配失败,函数返回-1。3、KMP算法：该算法较BF算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。定义next[j]函数，表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。max{k

7、0

8、则next[j+1]=?①若pk=pj，则有“p0…pk-1pk”=“pj-k…pj-1pj”（0

9、两部分，存储在两个字符中。2)Decrypt算法：对字符串中的单个字符c的二进制形式进行操作，通过左移和与位运算等两个字符还原累加，得到原字符。4、文本文件单词的检索与计数；1）建立文件的实现思路是：(1)定义一个串变量；(2)定义文本文件；(3)输入文件名，打开该文件；(4)循环读入文本行，写入文本文件，其过程如下：while(不是文件输入结束){读入一文