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

《字符串操作(算法与数据结构课程设计)(13页).doc》由会员分享，可在线阅读，更多相关《字符串操作(算法与数据结构课程设计)(13页).doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、P算法和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进行比较，若找到则返回位置；否则继续。若没

3、找到，返回-1。2）BF算法： IndexBF(S, 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|0kj,且“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” （0kj），如果在 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函数求T在

8、主串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数

9、据对象：D=ai|aiCharacterSet,i=1,2,3,n,n0数据关系：R1=|a(i-1),aiD,i=2,n基本操作：InitString(&S, a)初始条件：a是字符型数组。操作结果：生成一个其值为a的串S。StrLength(S)初始条件：串S存在 操作结果：返回的元素个数。StrCompare(S, T)初始条件： 串S、T存在。操作结果：若ST,则返回值大于0；若ST，则返回值小于0；若S=T，则返回值为0。SubString(&sub, S, pos, len)初始条件：串S存在,0posS.length ,0lenS.length-pos。操作结果：用sub返回串S

10、的第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.length-1。操作结果：若主串S中存在与串T相同的串则返回从下标pos开始的第一个出现的位置，否则

11、返回-1。show(S)初始条件：串S存在。 操作结果：显示串S。 ADT String 七、源程序（格式调整，添加注释）#include#include#define MaxStrSize 256 typedef struct char chMaxStrSize; int length; SString;/定义顺序串类型/pos为下标/实现串的赋值、比较、连接、插入和删除等操作，并在此基础上完成串的模式匹配void InitString(SString *s,char a)int i,j;for(j=0;aj!=0; j+);for(i=0;ichi=ai;s-length=strlen(a

12、);/串赋值int StrLength(SString s)return s.length;/求串长int StrCompare(SString s,SString t) int i; for (i=0; is.length & it.length; i+) if (s.chi!=t.chi) return s.chi-t.chi; return s.length-t.length; /串比较void SubString(SString *sub,SString S,int pos,int len) int i;for(i=0;ichi=S.chpos+i; sub-length=len;/截

13、取串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;ichi+pos=t.chi;s-length=s-length+n;/插入算法void StrDelete(SString *s,int pos,int len)int i;for(i=pos+len;ilength;i+)s-chi-len=s-chi;s-length=s-length-len;/删除算法void StrContact(SString

14、 *s,SString t)StrInsert(s,t,s-length);/连接算法void show(SString S)int i;for(i=0;iS.length;i+)printf(%c,S.chi);/显示串/-加密与解密- void Encrypt(SString S,SString *T) char c; int i,h,l,j=0; for (i=0;i4)&0xf; /取前四位 l=c&0xf; / 取后四位 T-chj=h+x; T-chj+1=l+z; j+=2; T-length=2*S.length; /加密void Decrypt(SString S,SStri

15、ng *T) int i,h,l,m,n,j=0; for(i=0;iS.length;i=i+2) h=(S.chi-x); l=(S.chi+1-z); m=(hchj=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)!

16、=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( iS.length & j=T.length) 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( jT.length)if(T.chj=T.chk) k+;j+;nextj=k; elseif(k=0)j+;n

17、extj=0;elsek=nextk;int IndexKMP(SString S,SString T,int pos,int next) int i,j,k; i= pos;j =0;k=-1; while (iS.length&j=T.length) k=i-T.length; return k;/KMP算法/-文本文件单词的检索与计数-int match(char a,int n,char c)int i;for(i=0;in;i+)if(ai=c) return 1;return 0;void CreatTextFile()SString S; char fname10,yn; FIL

18、E *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 a7=,.

19、,;,!,?, ,n; FILE *fp; SString S,T;/定义两个串变量 char fname10; 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(kS

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

21、!,?, ,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,256);fgets(S.ch,256,fp); S.length=strlen(S.ch);l+;k=0;i=0; while(kS.length-1) j=IndexBF(S,T,k

22、); if(j0)printf(行号：%d,次数：%d,位置分别为：,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(* * * * * * * * * * * * * * * * *

23、* * * * * * * *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)

24、;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：

25、);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语言程序设计，清华大

26、学出版社。小结通过本次课程设计让我学习到了很多，首先是搜集相关资料，有大概的设计思路，了解所需要实现的功能，然后再进行操作。这样可以使我们的程序设计有一个清晰的思路和方向。让我们在程序的设计过程中减少许多不必要的操作和错误。我们选用的是定长顺序存储结构，因为它表示起来比较方便，设计起来思路会清晰些。也可以使程序检查起来更加方便，看起来更加简洁。关于字符串的基本操作是比较容易编写的，但是我们对于字符串的加密解密比较陌生。一开始我们并不知道该如何编写，于是我们通过各种方式搜集资料，但是资料的搜集有很大的难度，但我们充分发挥了团队的协作性，大家积极地出主意，想方案，最终得到了我们想要的算法，这个算法

27、相对而言，不会太过于简单，并且，通过位运算进行加密解密，让我们有机会复习和巩固一下学过的C语言的内容。另外通过编写串的模式匹配让我们了解到优化算法的必要性，我们应当尽可能较少不必要的运算，提高运算效率减少运算的时间复杂度。在这次设计中，有关文本文件的编写最麻烦，因为文件本来就学得不是很好，在运行程序的过程中总是容易出错。于是，我们一起讨论，逐个筛选错误，在我们的共同努力下，最终完成整个设计。通过这次课程设计让我认识到了团队协作的重要性，一起合作解决问题相较于个人而言轻松多了，能和大家一起完成一次作业我觉得很高兴，也让我们在这个过程中学到了很多。就像我们在编写加密解密文件的程序时，遇到了困难，整

28、个程序设计的进程像被卡住了，无法继续。但是我们互相鼓励，互相帮助，共同努力，度过了这个难关。 团队的协作在程序设计的过程中占有很重要的因素，俗话说：“三个臭皮匠，赛过一个诸葛亮。”没错，三个人的思路，的确要比一个人宽很多，思考问题的角度也会更加多样化。以至于编写出来的程序更加严谨，思维更加缜密。另一方面也大大提高了程序的正确率，节省了时间，提高了效率。 当然，在团队工作中，个人的独立性也是十分重要的。我们必须尽最大努力完成自己应完成的工作，不能把所有的任务都交给大家，否则会影响整个团队的工作进程。只有这样，才能使整个团队的工作像程序一样运行的有条不紊。 在这次课程设计中，我们不仅学到了知识，学到了怎要将学到的知识灵活运用，更重要的是，我们学到了如何与别人合作，学到了如何发挥团队精神，才能使我们做的更好，更出色！