字符串操作(算法与数据结构课程设计)

字符串操作

一、问题描述

字符串是一种常见的数据类型，在现实生活中有着广泛的应用。本次课程设计需要选择合适的结构完成字符串的建立，实现串的基本操作，编写三种模式匹配算法和字符串的加密与解密算法，并利用它们实现字符串的应用:包括文本文件对单词的检索和计数。

二、基本要求

程序要求选择合适的存储结构，并实现以下功能：

1.完成串的基本操作，如：串的赋值，比较，连接，插入，删除；

2.实现串的模式匹配，包括：穷举法，BF算法和KMP算法；

3.字符串的应用：字符串的加密与解密；文本文件单词的计数；文本文件单词的检索；

三、测试数据

1.对模式匹配(穷举法，KMP算法和BF算法)的测试：如：在“asd sfhasd asd”中找从第3个下标开始匹配的模式串“asd”。

2.对加密与解密的测试：如：对串“afhbs 537hsj/sjdh”加密，再将加密后的串还原。

3.对文本文件单词的计数和检索的测试：如创建一个文本文件，在其中对单词“me”进行计数并且检索其所处行、列。

四、算法思想

1、用结构体SString记录字符串信息，其中ch代表字符串，length代表字符串长度。

2、模式匹配：

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位置字符开始,每个字符依次和目标串t中的对应字符相等,则匹配成功,该算法返回i；否则,匹配失败,函数返回-1。

3）KMP算法：

该算法较BF算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。

定义next[j]函数，表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。

max{ k|0<k<j,且“p0 pk-1”=“pj-k pj-1” }

当此集合非空时 当j=0时 其他情况

若“p0 pk-1”=“pj-k pj-1”，即next[j] = k，则next[j+1] = ? ①若pk=pj，则有“p0 pk-1pk”=“pj-k pj-1pj” （0<k<j），如果在 j+1发生不匹配，说明next[j+1] = k+1 = next[j]+1。 ②若pk≠pj，可把求next值问题看成是一个模式匹配问 题，整个模式串既是主串，又是子串。

Kmp:从S的pos位置开始与T进行匹配，若S与T对应位置相等或T回到0位置时，S与T同时右移;否则T回到next[j]位置。

3、字符串的加密、解密： 1)Encrypt算法：

对字符串中的单个字符c的二进制形式进行操作，通过右移和与位运算等其分为两部分，存储在两个字符中。

2)Decrypt算法：

对字符串中的单个字符c的二进制形式进行操作，通过左移和与位运算等两个字符还原累加，得到原字符。 4.文本文件单词的检索与计数； 1）建立文件的实现思路是：

(1) 定义一个串变量； (2) 定义文本文件；

(3) 输入文件名，打开该文件；

(4) 循环读入文本行，写入文本文件，其过程如下：

while(不是文件输入结束){

读入一文本行至串变量；

串变量写入文件； 输入是否结束输入标志；｝

(5) 关闭文件。

2）给定单词计数的实现思路是：

(1) 输入要检索的文本文件名，打开相应的文件；

(2) 输入要检索统计的单词；

(3) 循环读文本文件，读入一行，将其送入定义好的串中，并求该串的实

际长度，调用串匹配函数进行计数。具体描述如下：

while(不是文件结束){

读入一行并到串中； 求出串长度； 模式匹配函数计数；｝

(4) 关闭文件，输出统计结果。

3）检索单词出现在文本文件中的行号、次数及其位置的实现思路是：

(1) 输入要检索的文本文件名，打开相应的文件； (2) 输入要检索统计的单词； (3) 行计数器置初值0； (4) while(不是文件结束){

读入一行到指定串中； 求出串长度； 行单词计数器0；

调用模式匹配函数匹配单词定位、该行匹配单词计数； 行号计数器加1；

if(行单词计数器!=0)输出行号、该行有匹配单词的个数以及相应的位置；}

五、模块划分 1.串的模式匹配：

穷举法:Index(S, T, pos)

S为主串，T为模式串，从pos位置开始进行

BF算法:IndexBF(SString S,SString T,int pos)

朴素的模式匹配算法，S为主串，T为模式串，从pos位置开始进行。

KMP算法:get_next(SString T, int next[])

获取字符串T对应的 next[]数组。

IndexKMP(SString S,SString T,int pos,int next[])

利用模式串T的next函数求T在主串S中第pos个字符之后的位置。

2.字符串的加密与解密:

加密：Encrypt(SString S,SString *T)

将字符串S加密后存储在T中

解密：Decrypt(SString S,SString *T)

将字符串S解密后存储到T中

3.文本文件单词的计数和检索：

CreatTextFile() 创建文本文件 SubStrCount()

利用模式匹配，给定单词计数 SubStrInd()

利用模式匹配，检索单词出现在文本文件中的行号、次数及其位置 int match(char a[],int n,char c)

判断字符是否为标点或空格，换行符等，若相符返回1，否则返回0。

六、数据结构

ADT String{

数据对象：D={ai|ai∈CharacterSet,i=1,2,3, n,n≥0} 数据关系：R1={<a(i-1),ai>|a(i-1),ai∈D,i=2, n} 基本操作：

InitString(&S, a[])

初始条件：a[]是字符型数组。

操作结果：生成一个其值为a[]的串S。 StrLength(S) 初始条件：串S存在 操作结果：返回的元素个数。 StrCompare(S, T)

初始条件： 串S、T存在。

操作结果：若S>T,则返回值大于0；若S<T，则返回值小于0；若S=T，则返回值为0。

SubString(&sub, S, pos, len)

初始条件：串S存在,0≤pos<S.length ,0≤len≤S.length-pos。 操作结果：用sub返回串S的第pos下标起长度为len的字串。 StrInsert(&S,T, pos)

初始条件：串S,T存在，0≤pos≤S.length。 操作结果：在串S的第个下标开始插入串T。 StrDelete(&S, pos, len)

初始条件：串S存在, 0≤pos≤S.length-len。

操作结果：从串的第pos个下标开始删除长度为len的子串。 StrContact(&S, T) 初始条件：串S,T存在。

操作结果：用S返回S与T连接而成的新串。 Index(S, T, pos)

初始条件：串S、T存在，0≤pos≤S.length-1。

操作结果：若主串S中存在与串T相同的串则返回从下标pos开始的第一个出现的位置，否则返回-1。 show(S)

初始条件：串S存在。 操作结果：显示串S。 } ADT String

七、源程序（格式调整，添加注释）

#include<stdio.h> #include<string.h>

#define MaxStrSize 256 typedef struct {

char ch[MaxStrSize]; int length;

} SString;//定义顺序串类型 //pos为下标

//实现串的赋值、比较 …… 此处隐藏：8301字，全部文档内容请下载后查看。喜欢就下载吧 ……