字符串操作算法与数据结构课程方案

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

2、测试：如：在“asdsfhasdasd”中找从第3个下标开始匹配的模式用“asd”。2 .对力口密与解密的测试：如：对用“afhbs537hsj/sjdh”力口密，再将加密后的用还原。3 .对文本文件单词的计数和检索的测试：如创建一个文本文件，在其中对单词“mS进行计数并且检索其所处行、歹上四、算法思想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） KM骑法：个人资料整理仅限学习使用该算法较BF算法有较大改进，主要是消除了主审指针的回溯，从而使算法效率有了某种程度

4、的提高。定义nextj函数，表明当模式中第j个字符与主用中相应字符“失配”时，在模式中需重新和主审中该字符进行比较的字符的位置。maxk|0<k<j,且“p0pk-1”="pj-kpj-1”)nextj=当此集合非空时-1|当j=0时01其他情况若"p0pk-1”="pj-kpj-1"，即nextj=k，贝Unextj+1=?若pk=pj,则有“p0pk-1pk”="pj-kpj-1pj"<0<k<j),如果在j+1发生不匹配，说明nextj+1=k+1=nextj+1。若pkwpj,可把求next值问题

5、看成是一个模式匹配问题，整个模式用既是主用，又是子用。Kmp从S的pos位置开始与T进行匹配，若S与T对应位置相等或T回到0位置时，S与T同时右移。否则T回到nextj位置。3、字符串的加密、解密：1>Encrypt算法：对字符串中的单个字符c的二进制形式进行操作，通过右移和与位运算等其分为两部分，存储在两个字符中。2>Decrypt算法：对字符串中的单个字符c的二进制形式进行操作，通过左移和与位运算等两个字符还原累加，得到原字符。4.文本文件单词的检索与计数；1)建立文件的实现思路是：(1>定义一个用变量；(2>定义文本文件；(3>输入文件名，打开该文件；(4&

6、gt;循环读入文本行，写入文本文件，其过程如下：while(不是文件输入结束>读入一文本行至用变量；用变量写入文件；输入是否结束输入标志；(5>关闭文件。2)给定单词计数的实现思路是：(1>输入要检索的文本文件名，打开相应的文件；个人资料整理仅限学习使用(2输入要检索统计的单词；(3循环读文本文件，读入一行，将其送入定义好的申中，并求该用的实际长度，调用用匹配函数进行计数。具体描述如下：while(不是文件结束读入一行并到申中；求出用长度；模式匹配函数计数；(4关闭文件，输出统计结果。3)检索单词出现在文本文件中的行号、次数及其位置的实现思路是：(1输入要检索的文本文件名，打

7、开相应的文件；(2输入要检索统计的单词；(3行计数器置初值0;(4while(不是文件结束读入一行到指定用中；求出用长度；行单词计数器0;调用模式匹配函数匹配单词定位、该行匹配单词计数；行号计数器加1;if(行单词计数器！=0输出行号、该行有匹配单词的个数以及相应的位置；五、模块划分1 .用的模式匹配：穷举法:Index(S,T,posS为主用，T为模式用，从pos位置开始进行BF算法：IndexBF(SStringS,SStringT,intpos朴素的模式匹配算法，S为主用，T为模式用，从pos位置开始进行。KMPW法:get_next(SStringT,intnext获应字符串T对应的n

8、ext口数组。IndexKMP(SStringS,SStringT,intpos,intnext利用模式用T的next函数求T在主用S中第pos个字符之后的位置2 .字符串的加密与解密：力口密：Encrypt(SStringS,SString*T将字符用S加密后存储在T中解密：Decrypt(SStringS,SString*T将字符用S解密后存储到T中个人资料整理仅限学习使用3 .文本文件单词的计数和检索:CreatTextFile(>创建文本文件SubStrCount(>利用模式匹配，给定单词计数SubStrInd(>利用模式匹配，检索单词出现在文本文件中的行号、次数及其

9、位置intmatch(chara,intn,charc>判断字符是否为标点或空格，换行符等，若相符返回1,否则返回00六、数据结构ADTString数据对象：D=ai|aiCCharacterSet,i=1,2,3,n,n>0数据关系：R1=<a(i-1>,ai>|a(i-1>,aiD,i=2,n基本操作：InitString(&S,a>初始条件：a是字符型数组。操作结果：生成一个其值为a口的用SoStrLength(S>初始条件：用S存在操作结果：返回的元素个数。StrCompare(S,T>初始条件：用S、T存在。操作结果：若S

10、>T,则返回值大于0;若S<T,则返回值小于0;若S=T,则返回值为00SubString(&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的第个下标开始插入用ToStrDelete(&S,pos,len>初始条件：用S存在，0<pos<S.length

11、-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存在。操作结果：显示用SoADTString七、源程序<格式调整，添加注释)#include<stdio.h>#include<strin

12、g.h>#defineMaxStrSize256typedefstructcharchMaxStrSize。intlength。SString。/定义顺序用类型/pos为下标/实现用的赋值、比较、连接、插入和删除等操作，并在此基础上完成用的模式匹配voidInitString(SString*s,chara>inti,j。for(j=0。aj!='0'。j+>。for(i=0oi<joi+>s->chi=ai。s->length=strlen(a>。/用赋值intStrLength(SStrings>returns.leng

13、th。/求用长intStrCompare(SStrings,SStringt>intifor(i=0。i<s.length&&i<t.length。i+>if(s.chi!=t.chi>returns.chi-t.chi。returns.length-t.length。/比较voidSubString(SString*sub,SStringS,intpos,intlen>intifor(i=0。i<len。i+>sub->chi=S.chpos+i个人资料整理仅限学习使用sub->length=len。/截取用void

14、StrInsert(SString*s,SStringt,intpos>inti,m,n。m=s->length。n=t.length。for(i=m-1oi>=pos-1。i->s->chi+n=s->chi。for(i=0oi<n。i+>s->chi+pos=t.chi。s->length=s->length+n。/插入算法voidStrDelete(SString*s,intpos,intlen>intifor(i=pos+len。i<s->length。i+>s->chi-len=s->

15、;chi。s->length=s->length-len。/删除算法voidStrContact(SString*s,SStringt>StrInsert(s,t,s->length>。/连接算法voidshow(SStringS>inti。for(i=0oi<S.length。i+>printf("%c",S.chi>。/显示用/加密与解密voidEncrypt(SStringS,SString*T>charc。inti,h,l,j=0。for(i=0oi<S.length。i+>c=S.chi。h=

16、(c>>4>&0xf。/取前四位l=c&0xfo/取后四位T->chj=h+'x'。T->chj+1=l+'z'。j+=2。T->length=2*S.length。/加密voidDecrypt(SStringS,SString*T>个人资料整理仅限学习使用inti,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&

17、;0xf>。T->chj=m+n。j+。T->length=S.length/2。/解密/模式匹配intIndex(SStringS,SStringT,intpos>inti,m,n。SStringsub。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+oelsereturni。return-1。/穷举法intIndexBF(SStringS,S

18、StringT,intpos>inti,j,k=-1。i=posoj=0owhile(i<S.length&&j<T.length>if(S.chi=T.chj>i+。j+。elsei=i-j+1。j=0。if(j>=T.length>k=i-T.length。returnk。/BF算法voidget_next(SStringT,intnext>intj,k。next0=-1onext1=0。j=1ok=0owhile(j<T.length>if(T.chj=T.chk>k+oj+onextj=k。个人资料整理仅

19、限学习使用elseif(k=0>j+。nextj=0。)elsek=nextk。)intIndexKMP(SStringS,SStringT,intpos,intnext>inti,j,ki=posoj=0ok=-1owhile(i<S.length&&j<T.length>if(S.chi=T.chj>i+oj+oelseif(j=0>i+0elsej=nextjoif(j>=T.length>k=i-T.length。returnk。/KMP算法/文本文件单词的检索与计数intmatch(chara,intn,charc

20、>intifor(i=0oi<n。i+>if(ai=c>return1。return0。voidCreatTextFile(>SStringS。charfname10,yn。FILE*fp。printf("输入要建立的文件名：">。scanf("%s",fname>。fp=fopen(fname,"w">。yn='n'。/输入结束标志初值while(yn='n'|yn='N'>printf("请输入一行文本："&g

21、t;ogets(S.ch>。gets(S.ch>。S.length=strlen(S.ch>。fwrite(&S,S.length,1,fp>。个人资料整理仅限学习使用fprintf(fp,"%c",10>。printf("结束输入吗？yorn:">。yn=getchar(>。fclose(fp>。/关闭文件printf("建立文件结束!">。voidSubStrCount(>chara7=',','.','。',

22、9;!','?','','n'。FILE*fp。SStringS,T。/定义两个用变量charfname10。inti=0,j,koprintf("输入文本文件名：">。scanf("%s",fname>。fp=fopen(fname,"r">。printf("输入要统计计数的单词：">oscanf("%s",T.ch>。T.length=strlen(T.ch>。while(!feof(fp>&g

23、t;/扫描整个文本文件memset(S.ch,'0',256>。fgets(S.ch,256,fp>。/读入一行文本S.length=strlen(S.ch>。k=0o/初始化开始检索位置while(k<S.length-1>/检索整个主用Sj=IndexBF(S,T,k>。调用用匹配函数if(j<0>break。elseif(j=0>if(match(a,7,S.chT.length>>i+。/单词计数器加1k=j+T.length。/继续下一字用的检索elseif(match(a,7,S.chj-1>&

24、amp;&match(a,7,S.chj+T.length>>i+。/单词计数器加1k=j+T.length。/继续下一字用的检索printf("n单词sft文本文件$中共出现d次n",T.ch,fname,i>。/统计单词出现的个数voidSubStrInd(>chara7=',','.','。','!','?','','n'。FILE*fp。SStringS,T。charfname10。inti,j,k,l,m。个人资料整理仅限

25、学习使用intwz20。printf("输入文本文件名：">oscanf("%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

26、>。l+ok=0oi=0owhile(k<S.length-1>j=IndexBF(S,T,k>。if(j<0>break。elseif(j=0>if(match(a,7,S.chT.length>>i+owzi=jok=j+T.length。elseif(match(a,7,S.chj-1>&&match(a,7,S.chj+T.length>>i+owzi=jok=j+T.length。if(i>0>printf("行号：d次数：d位置分别为：",l,i>for(m

27、=1om<=i。m+>printf("%4d",wzm+1>。printf("n">。/检索单词出现在文本文件中的行号、次数及其位置main(>SStringS,T,M。intxz,wzointnextMaxStrSize。charaMaxStrSize,bMaxStrSizedoprintf("n">printf('*n”>个人资料整理仅限学习使用printf("*n">printf("*1.穷举法，KM骑法和BF算法*n">pri

28、ntf("*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(&qu

29、ot;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("nB

30、F算法匹配位置：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:"&

31、gt;。show(T>。Decrypt(T,&M>。printf("n解密后用M">。show(M>break。case 3 :CreatTextFile(>。break。case 4 :SubStrCount(>。break。case 5 :SubStrInd(>。break。case0:return0。default:printf("选择错误，重新选n">while(1>。个人资料整理仅限学习使用八、测试情况程序的测试结果如下:哼律,'I汇.T加短?<的的程>1勺工rm

32、rn-,5kmr.,Jliulag.，-迂串工工或岸鞠繇嚣谓输入主串配I-andHlh占令d4口也潘簿人横式串had_L_用雷i-ncdlcfha?dlasd俎11串11Alid芾翻：.开始匹配的下标：3I,向cwjiJDe北口四气之件央单"Deteug'L3b5：本环，e、eMfiK?阈特计定序*即码又的量>zM的1_.:Jnn.-,5tibF二JU冒-一定用X字字可0-1-工词词出轨置受退；IE-H-NNM-MM-N-MM,»W畀*H"M信输人串"Wm&37hsj/tJ(ihiiFkbsiE37hsi；J/sJldhE£F"1怪aflibs537hi:jXH1iidh工人口出哨21HMjDe北口普干建立性央口丸口由蚂旧浮文本文H.exMKMn灾的臼程k.Jr.:l-lEa3n,£0311311La:!壬干s个人资料整理仅限学习使用tx词-14，的£N口勺勺1-1I':,K«.-p-tki->+T白r-3S33.,-3feLU，甘NUUUU7WW4亍整»-【卜：*"KHn.MFIM程