数据结构课程设计-字符串操作

安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称《数据结构》课题名称字符串操作专业计算机科学与技术班级学号姓名联系方式指导教师2011年12月25日目录一、问题描述………………………………………………………1二、基本要求………………………………………………………1三、测试数据………………………………………………………1四、算法思想………………………………………………………11、注释………………………………………………….………12、模式匹配……………………………………………………..13、KMP算法…………………………………………….………24、文本文件单词的检索与计数……………………………………2五、模块划分………………………………………….……………31、串的模式匹配…………………………………….…………32、字符串的加密与解密…………………………..……………43、文本文件单词的计数和检索……………………….…………4六、数据结构………………………………………………………4七、源程序（格式调整，添加注释）……………………………5八、测试情况………………………………………………………12九、参考文献………………………………………………………13十、总结……………………………………………………………14一、问题描述字符串是一种常见的数据类型，在现实生活中有着广泛的应用。本次课程设计需要选择合适的结构完成字符串的建立，实现串的基本操作，编写三种模式匹配算法和字符串的加密与解密算法，并利用它们实现字符串的应用:包括文本文件对单词的检索和计数。二、基本要求程序要求选择合适的存储结构，并实现以下功能：1.完成串的基本操作，如：串的赋值，比较，连接，插入，删除；2.实现串的模式匹配，包括：穷举法，BF算法和KMP算法；3.字符串的应用：字符串的加密与解密；文本文件单词的计数；文本文件单词的检索；三、测试数据1.对模式匹配(穷举法，KMP算法和BF算法)的测试：如：在“asdsfhasdasd”中找从第3个下标开始匹配的模式串“asd”。2.对加密与解密的测试：如：对串“afhbs537hsj/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|0kj,且“p0…pk-1”=“pj-k…pj-1”}next[j]=当此集合非空时-1当j=0时0其他情况若“p0…pk-1”=“pj-k…pj-1”，即next[j]=k，则next[j+1]=?①若pk=pj，则有“p0…pk-1pk”=“pj-k…pj-1pj”（0kj），如果在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(SStringS,SStringT,intpos)朴素的模式匹配算法，S为主串，T为模式串，从pos位置开始进行。KMP算法:get_next(SStringT,intnext[])获取字符串T对应的next[]数组。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()利用模式匹配，检索单词出现在文本文件中的行号、次数及其位置intmatch(chara[],intn,charc)判断字符是否为标点或空格，换行符等，若相符返回1，否则返回0。六、数据结构ADTString{数据对象：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存在。操作结果：若ST,则返回值大于0；若ST，则返回值小于0；若S=T，则返回值为0。SubString(&sub,S,pos,len)初始条件：串S存在,0≤posS.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。}ADTString七、源程序（格式调整，添加注释）#includestdio.h#includestring.h#defineMaxStrSize256typedefstruct{charch[MaxStrSize];intlength;}SString;//定义顺序串类型//pos为下标//实现串的赋值、比较、连接、插入和删除等操作，并在此基础上完成串的模式匹配voidInitString(SString*s,chara[]){inti,j;for(j=0;a[j]!='\0';j++);for(i=0;ij;i++)s-ch[i]=a[i];s-length=strlen(a);}//串赋值intStrLength(SStrings){returns.length;}//求串长intStrCompare(SStrings,SStringt){inti;for(i=0;is.length&&it.length;i++)if(s.ch[i]!=t.ch[i])returns.ch[i]-t.ch[i];returns.length-t.length;}//串比较voidSubString(SString*sub,SStringS,intpos,intlen){inti;for(i=0;ilen;i++)sub-ch[i]=S.ch[pos+i];sub-length=len;}//截取串voidStrInsert(SString*s,SStringt,intpos){inti,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;in;i++)s-ch[i+pos]=t.ch[i];s-length=s-length+n;}//插入算法voidStrDelete(SString*s,intpos,intlen){inti;for(i=pos+len;is-length;i++)s-ch[i-len]=s-ch[i];s-length=s-length-len;}//删除算法voidStrContact(SString*s,SStringt){StrInsert(s,t,s-length);}//连接算法voidshow(SStringS){inti;for(i=0;iS.length;i++)printf(%c,S.ch[i]);}//显示串//-----------------加密与解密---------------------------voidEncrypt(SStringS,SString*T){charc;inti,h,l,j=0;for(i=0;iS.length;i++){c=S.ch[i];h=(c4)&0xf;//取前四位l=c&0xf;//取后四位T-ch[j]=h+'x';T-ch[j+1]=l+'z';j+=2;}T-length=2*S.length;}//加密voidDecrypt(SStringS,SString*T){inti,h,l,m,n,j=0;for(i=0;iS.length;i=i+2){h=(S.ch[i]-'x');l=(S.ch[i+1]-'z');m=(h4);n=(l&0xf);T-ch[j