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

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

2、d 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,

3、 T,pos)主串S从pos位置开始，模式串T从0位置开始，从目标串s=“s0s2sn-1"的第一个字符开始和模式串t=“t0t2tm-1"中的第一个字符比较,若相等,则继续逐个比较后续字符；否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。依次类推,若从模式串s的i位置字符开始,每个字符依次和目标串t中的对应字符相等,则匹配成功,该算法返回i；否则,匹配失败,函数返回-1。3）KMP算法：该算法较BF算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。定义nextj函数，表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需

4、重新和主串中该字符进行比较的字符的位置。 max k|0<k<j,且“p0pk-1”=“pj-kpj-1” nextj= 当此集合非空时 -1 当j=0时 0 其他情况若“p0pk-1”=“pj-kpj-1”，即nextj = k，则nextj+1 = ?若pk=pj，则有“p0pk-1pk”=“pj-kpj-1pj” （0<k<j），如果在 j+1发生不匹配，说明nextj+1 = k+1 = nextj+1。若pkpj，可把求next值问题看成是一个模式匹配问 题，整个模式串既是主串，又是子串。Kmp:从S的pos位置开始与T进行匹配，若S与T对应位置相等或T回到0

5、位置时，S与T同时右移;否则T回到nextj位置。3、字符串的加密、解密：1)Encrypt算法：对字符串中的单个字符c的二进制形式进行操作，通过右移和与位运算等其分为两部分，存储在两个字符中。2)Decrypt算法：对字符串中的单个字符c的二进制形式进行操作，通过左移和与位运算等两个字符还原累加，得到原字符。4.文本文件单词的检索与计数； 1）建立文件的实现思路是：(1) 定义一个串变量；(2) 定义文本文件；(3) 输入文件名，打开该文件；(4) 循环读入文本行，写入文本文件，其过程如下：while(不是文件输入结束)读入一文本行至串变量；串变量写入文件；输入是否结束输入标志；(5) 关闭

6、文件。2）给定单词计数的实现思路是：(1) 输入要检索的文本文件名，打开相应的文件；(2) 输入要检索统计的单词；(3) 循环读文本文件，读入一行，将其送入定义好的串中，并求该串的实际长度，调用串匹配函数进行计数。具体描述如下：while(不是文件结束)读入一行并到串中；求出串长度；模式匹配函数计数；(4) 关闭文件，输出统计结果。3）检索单词出现在文本文件中的行号、次数及其位置的实现思路是：(1) 输入要检索的文本文件名，打开相应的文件；(2) 输入要检索统计的单词；(3) 行计数器置初值0；(4) while(不是文件结束)读入一行到指定串中；求出串长度；行单词计数器0；调用模式匹配函数匹

7、配单词定位、该行匹配单词计数；行号计数器加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函数求

8、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 Strin

9、g数据对象：D=ai|aiCharacterSet,i=1,2,3,n,n0数据关系：R1=<a(i-1),ai>|a(i-1),aiD,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存在,0pos<S

10、.length ,0lenS.length-pos。操作结果：用sub返回串S的第pos下标起长度为len的字串。StrInsert(&S,T, pos)初始条件：串S,T存在，0posS.length。 操作结果：在串S的第个下标开始插入串T。StrDelete(&S, pos, len)初始条件：串S存在, 0posS.length-len。 操作结果：从串的第pos个下标开始删除长度为len的子串。StrContact(&S, T)初始条件：串S,T存在。 操作结果：用S返回S与T连接而成的新串。Index(S, T, pos)初始条件：串S、T存在，0posS.

11、length-1。操作结果：若主串S中存在与串T相同的串则返回从下标pos开始的第一个出现的位置，否则返回-1。show(S)初始条件：串S存在。 操作结果：显示串S。 ADT String 七、源程序（格式调整，添加注释）#include<stdio.h>#include<string.h>#define MaxStrSize 256 typedef struct char chMaxStrSize; int length; SString;/定义顺序串类型/pos为下标/实现串的赋值、比较、连接、插入和删除等操作，并在此基础上完成串的模式匹配void InitStr

12、ing(SString *s,char a)int i,j;for(j=0;aj!='0' j+);for(i=0;i<j;i+) s->chi=ai;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.chi!=t.chi) return s.chi-t.chi; retu

13、rn s.length-t.length; /串比较void SubString(SString *sub,SString S,int pos,int len) int i;for(i=0;i<len;i+)sub->chi=S.chpos+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->chi+n=s->chi;for(i=0;i<n;i+)s-

14、>chi+pos=t.chi;s->length=s->length+n;/插入算法void StrDelete(SString *s,int pos,int len)int i;for(i=pos+len;i<s->length;i+)s->chi-len=s->chi;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&l

15、t;S.length;i+)printf("%c",S.chi);/显示串/-加密与解密- void Encrypt(SString S,SString *T) char c; int i,h,l,j=0; for (i=0;i<S.length;i+) c=S.chi; h=(c>>4)&0xf; /取前四位 l=c&0xf; / 取后四位 T->chj=h+'x' T->chj+1=l+'z' j+=2; T->length=2*S.length; /加密void Decrypt(SSt

16、ring S,SString *T) int i,h,l,m,n,j=0; for(i=0;i<S.length;i=i+2) h=(S.chi-'x'); l=(S.chi+1-'z'); m=(h<<4); n=(l&0xf); T->chj=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=Str

17、Length(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.chi = T.chj) i+; j+; else i = i-j+1; j =0; if(j>=T.len

18、gth) k=i-T.length;return k;/BF算法void get_next(SString T, int next)int j,k;next0=-1; next1 = 0;j = 1;k=0; while( j<T.length)if(T.chj=T.chk) k+;j+;nextj=k; elseif(k=0)j+;nextj=0;elsek=nextk;int IndexKMP(SString S,SString T,int pos,int next) int i,j,k; i= pos;j =0;k=-1; while (i<S.length&&

19、;j<T.length) if (S.chi=T.chj) i+;j+; else if(j=0)i+; else j=nextj; 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(ai=c) return 1;return 0;void CreatTextFile()SString S; char fname10,yn; FILE *fp; printf("输入要建立的文件名：&quo

20、t;); 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=g

21、etchar(); fclose(fp);/关闭文件 printf("建立文件结束!"); void SubStrCount()char a7=',','.','','!','?',' ','n' FILE *fp; SString S,T;/定义两个串变量 char fname10; int i=0,j,k; printf("输入文本文件名："); scanf("%s",fname); fp=fopen(fname,&qu

22、ot;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) /检索整个主串Sj=IndexBF(S,T,k);/调用串匹配函数if(j<0 ) break;else if(j=0

23、) if(match(a,7,S.chT.length) i+;/单词计数器加1 k=j+T.length;/继续下一字串的检索 else if(match(a,7,S.chj-1)&&match(a,7,S.chj+T.length)i+;/单词计数器加1k=j+T.length;/继续下一字串的检索printf("n单词%s在文本文件%s中共出现%d次n",T.ch,fname,i);/统计单词出现的个数void SubStrInd()char a7=',','.','','!','

24、?',' ','n'FILE *fp;SString S,T; char fname10;int i,j,k,l,m;int wz20;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',2

25、56);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.chT.length)i+;wzi=j;k=j+T.length;elseif(match(a,7,S.chj-1)&&match(a,7,S.chj+T.length)i+;wzi=j;k=j+T.length;if(i>0)printf("行号：%d,次数：%d,位置分别为：

26、",l,i);for(m=1;m<=i;m+) printf("%4d",wzm+1); printf("n");/检索单词出现在文本文件中的行号、次数及其位置main()SString S, T,M;int xz,wz;int nextMaxStrSize;char aMaxStrSize,bMaxStrSize;do printf("n");printf("* * * * * * * * * * * * * * * * * * * * * * * * *n");printf("* *

27、* * * * * * * * * * * * * * * * * * * * * * *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

28、("%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

29、);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、