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

字符串操作

一、问题描述

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

二、基本要求

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

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为下标

//实现串的赋值、比较、连接、插入和删除等操作，并在此基础上完成串的模式匹配

void InitString(SString *s,char a[]) {int i,j;

for(j=0;a[j]!='\0'; j++); for(i=0;i<j;i++) s->ch[i]=a[i];

s->length=strlen(a); }

//串赋值

int StrLength(SString s) {return s.length;} //求串长

int StrCompare(SString s,SString t) { int i;

for (i=0; i<s.length && i<t.length; i++)

if (s.ch[i]!=t.ch[i]) return s.ch[i]-t.ch[i]; return s.length-t.length; } //串比较

void SubString(SString *sub,SString S,int pos,int len) { int i;

for(i=0;i<len;i++)

sub->ch[i]=S.ch[pos+i];

sub->length=len;} //截取串

void StrInsert(SString *s,SString t,int pos) {int i,m,n; m=s->length; n=t.length;

for(i=m-1;i>=pos-1;i--) s->ch[i+n]=s->ch[i]; for(i=0;i<n;i++)

s->ch[i+pos]=t.ch[i]; s->length=s->length+n; }//插入算法

void StrDelete(SString *s,int pos,int len) {int i;

for(i=pos+len;i<s->length;i++) s->ch[i-len]=s->ch[i]; s->length=s->length-len; }

//删除算法

void StrContact(SString *s,SString t) {StrInsert(s,t,s->length);} //连接算法

void show(SString S) {int i;

for(i=0;i<S.length;i++) printf("%c",S.ch[i]); }

//显示串

//-----------------加密与解密--------------------------- void Encrypt(SString S,SString *T) {char c;

int i,h,l,j=0;

for (i=0;i<S.length;i++) {c=S.ch[i];

h=(c>>4)&0xf; //取前四位 l=c&0xf; // 取后四位 T->ch[j]=h+'x'; T->ch[j+1]=l+'z'; j+=2; }

T->length=2*S.length; } //加密

void Decrypt(SString S,SString *T)

{ int i,h,l,m,n,j=0;

for(i=0;i<S.length;i=i+2) {h=(S.ch[i]-'x'); l=(S.ch[i+1]-'z'); m=(h<<4); n=(l&0xf); T->ch[j]=m+n; j++; }

T->length=S.length/2; }

//解密

//------------模式匹配----------------------- int Index(SString S,SString T, int pos) { int i,m,n; SString sub; if (pos>=0)

{ n=StrLength(S); m=StrLength(T); i=pos; while (i<=n-m)

{ SubString(&sub,S,i,m); if (StrCompare(sub,T)!=0) i++; else

return i; } }

return -1; }//穷举法

int IndexBF(SString S,SString T,int pos) {int i,j,k=-1; i= pos; 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) k=i-T.length; return k; }

//BF算法

void get_next(SString T, int next[]) {int j,k;

next[0]=-1; next[1] = 0; j = 1;k=0;

while( j<T.length){ if(T.ch[j]==T.ch[k])

{k++;j++;next[j]=k;}

else

if(k==0) {j++;

next[j]=0; } else

k=next[k]; } }

int IndexKMP(SString S,SString T,int pos,int next[]) { int i,j,k;

i= pos;j =0;k=-1;

while (i<S.length&&j<T.length) { if (S.ch[i]==T.ch[j]) {i++;j++;} else

if(j==0){i++;} else

j=next[j]; }

if (j>=T.length) k=i-T.length; return k; }

//KMP算法

//---------------文本文件单词的检索与计数------------------ int match(char a[],int n,char c) {int i;

for(i=0;i<n;i++)

if(a[i]==c) return 1; return 0; }

void CreatTextFile() {SString S;

char fname[10],yn; FILE *fp;

printf("输入要建立的文件名："); scanf("%s",fname); fp=fopen(fname,"w");

yn='n';//输入结束标志初值 while(yn=='n'||yn=='N')

{printf("请输入一行文本："); gets(S.ch);gets(S.ch); S.length=strlen(S.ch); fwrite(&S,S.length,1,fp);

fprintf(fp,"%c",10);

printf("结束输入吗？y or n ：");yn=getchar();} fclose(fp);//关闭文件 printf("建立文件结束!"); }

void SubStrCount()

{char a[7]={',','.',';','!','?',' ','\n'}; FILE *fp;

SString S,T;//定义两个串变量 char fname[10]; int i=0,j,k;

printf("输入文本文件名："); scanf("%s",fname); fp=fopen(fname,"r");

printf("输入要统计计数的单词："); scanf("%s",T.ch);

T.length=strlen(T.ch);

while(!feof(fp)){ //扫描整个文本文件 memset(S.ch,'\0',256);

fgets(S.ch,256,fp); //读入一行文本 S.length=strlen(S.ch); k=0; //初始化开始检索位置

while(k<S.length-1) //检索整个主串S {j=IndexBF(S,T,k);//调用串匹配函数 if(j<0 ) break; else if(j==0)

{ if(match(a,7,S.ch[T.length])) i++;//单词计数器加1

k=j+T.length;//继续下一字串的检索 }

else {if(match(a,7,S.ch[j-1])&&match(a,7,S.ch[j+T.length])) i++;//单词计数器加1

k=j+T.length;//继续下一字串的检索 } } }

printf("\n单词%s在文本文件%s中共出现%d次\n",T.ch,fname,i); }//统计单词出现的个数 void SubStrInd()

{char a[7]={',','.',';','!','?',' ','\n'}; FILE *fp;

SString S,T; char fname[10]; int i,j,k,l,m;

int wz[20];

printf("输入文本文件名："); scanf("%s",fname); fp=fopen(fname,"r");

printf("输入要检索的单词："); scanf("%s",T.ch);

T.length=strlen(T.ch); l=0;

while(!feof(fp)) {

memset(S.ch,'\0',256); fgets(S.ch,256,fp); S.length=strlen(S.ch); l++; k=0; i=0;

while(k<S.length-1) { j=IndexBF(S,T,k); if(j<0) break; else if(j==0) {

if(match(a,7,S.ch[T.length])) {i++;

wz[i]=j;}

k=j+T.length; } else

{if(match(a,7,S.ch[j-1])&&match(a,7,S.ch[j+T.length])) {i++;wz[i]=j;} k=j+T.length; } }

if(i>0){

printf("行号：%d,次数：%d,位置分别为：",l,i); for(m=1;m<=i;m++)

printf("%4d",wz[m]+1); printf("\n"); } }

}//检索单词出现在文本文件中的行号、次数及其位置 main()

{SString S, T,M; int xz,wz;

int next[MaxStrSize];

char a[MaxStrSize],b[MaxStrSize]; do {printf("\n");

printf("* * * * * * * * * * * * * * * * * * * * * * * * *\n");

printf("* * * * * * * * * * * * * * * * * * * * * * * * *\n"); printf("*1.穷举法，KMP算法和BF算法 *\n"); printf("*2.字符串的加密与解密 *\n"); printf("*3.建立文本文件 *\n"); printf("*4.单词字串的计数 *\n"); printf("*5.单词字串的定位 *\n"); printf("*0.退出整个程序 *\n"); printf("请选择(0--5)"); scanf("%d",&xz); switch(xz) { case 1 :

printf("\n请输入主串S："); gets(a); gets(a);

printf("\n请输入模式串T："); gets(b);

InitString(&S,a); InitString(&T,b);

printf("\n主串S：");show(S); printf("\n模式串T：");show(T);

printf("\n请输入开始匹配的下标："); scanf("%d",&wz);

printf("\n穷举法匹配位置：%d",Index( S,T,wz)+1); printf("\nBF算法匹配位置：%d",IndexBF(S,T,wz)+1); get_next(T, next);

printf("\nkmp算法匹配位置：%d",IndexKMP(S,T,wz,next)+1); break; case 2 :

printf("\n请输入串S："); gets(a); gets(a); InitString(&S,a);

printf("\n原字符串S：");show(S); Encrypt(S,&T);

printf("\n加密后串T：");show(T); Decrypt(T,&M);

printf("\n解密后串M：");show(M); break;

case 3 : CreatTextFile();break; case 4 : SubStrCount();break; case 5 : SubStrInd();break; case 0 : return 0;

default:printf("选择错误，重新选 \n"); } }while(1); }

八、测试情况

程序的测试结果如下：

九、参考文献

1、严蔚敏，《数据结构 C语言》，清华大学出版社。 2、谭浩强，《c语言程序设计》，清华大学出版社。

小结

通过本次课程设计让我学习到了很多，首先是搜集相关资料，有大概的设计思路，了解所需要实现的功能，然后再进行操作。这样可以使我们的程序设计有一个清晰的思路和方向。让我们在程序的设计过程中减少许多不必要的操作和错误。

我们选用的是定长顺序存储结构，因为它表示起来比较方便，设计起来思路会清晰些。也可以使程序检查起来更加方便，看起来更加简洁。

关于字符串的基本操作是比较容易编写的，但是我们对于字符串的加密解密比较陌生。一开始我们并不知道该如何编写，于是我们通过各种方式搜集资料，但是资料的搜集有很大的难度，但我们充分发挥了团队的协作性，大家积极地出主意，想方案，最终得到了我们想要的算法，这个算法相对而言，不会太过于简单，并且，通过位运算进行加密解密，让我们有机会复习和巩固一下学过的C语言的内容。

另外通过编写串的模式匹配让我们了解到优化算法的必要性，我们应当尽可能较少不必要的运算，提高运算效率减少运算的时间复杂度。在这次设计中，有关文本文件的编写最麻烦，因为文件本来就学得不是很好，在运行程序的过程中总是容易出错。于是，我们一起讨论，逐个筛选错误，在我们的共同努力下，最终完成整个设计。

通过这次课程设计让我认识到了团队协作的重要性，一起合作解决问题相较于个人而言轻松多了，能和大家一起完成一次作业我觉得很高兴，也让我们在这个过程中学到了很多。 就像我们在编写加密解密文件的程序时，遇到了困难，整个程序设计的进程像被卡住了，无法继续。但是我们互相鼓励，互相帮助，共同努力，度过了这个难关。

团队的协作在程序设计的过程中占有很重要的因素，俗话说：“三个臭皮匠，赛过一个诸葛亮。”没错，三个人的思路，的确要比一个人宽很多，思考问题的角度也会更加多样化。以至于编写出来的程序更加严谨，思维更加缜密。另一方面也大大提高了程序的正确率，节省了时间，提高了效率。

当然，在团队工作中，个人的独立性也是十分重要的。我们必须尽最大努力完成自己应完成的工作，不能把所有的任务都交给大家，否则会影响整个团队的工作进程。只有这样，才能使整个团队的工作像程序一样运行的有条不紊。

在这次课程设计中，我们不仅学到了知识，学到了怎要将学到的知识灵活运用，更重要的是，我们学到了如何与别人合作，学到了如何发挥团队精神，才能使我们做的更好，更出色！

wilyes11 收集 博客(与学习无关):/u/1810231802

本文来源：https://www.bwwdw.com/article/edvj.html