数据结构域算法设计-实验三 串的应用

《数据结构域算法设计-实验三 串的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验三串的应用基本思路；串是非数值运算中的处理的主要对象，如信息检索、文本编辑、符号处理等得到广泛应用。本实验的目的在于让学生有效实现串的处理，这就要求学生熟悉串的存储结构及其基本运算。首先设计出串的定位算法及其实现；然后再利用串的定位算法设计文本的检索及单词的计数等操作。一、串模式匹配算法的设计与实现1、设计要求：子串的定位就是要求子串在主串中首次出现的位置。称为模式匹配。只要求学生能用最简单的朴素模式算法即可。算法思路为：将给定的子串与主串从第一个字符开始比较，找到首次与子串完全匹配的子串为止，并记住位置。2、算法分析及设计朴素模式匹配算法：设计需要有三个指针：

2、i、j、k，用i批示主串S每次开始比较的位置；指针j和k分别批示主串S和模式串T中当前正在等待比较的字符位置；一开始从主串S的第一个字符（i=0,j=0）和模式T的第一个字符（k=0）比较，若相等，则继续逐个比较后续字符（j++,k++），否则从主串的下一个字符（i++）起重新和模式串（j=0）的字符开始比较。依次类推，直到模式T中的所有字符都比较完，而且一直相等，则称匹配成功，并返回位置；否则返回-1，表示失败。intindex(sstringS,sstringT){//求子串T在主串中首次出现的位置（朴素匹配算法）inti,j,k,m,n;m=T.length;

3、n=S.length;for(i=0;i<=n-m;i++){j=0;k=i;while(j<=m&&S.ch[k]==T.ch[j]){k++;j++;}//继续下一个字符的比较if(j==m)}/returni;//若相等，则说明找到匹配的子串，返回匹配位置i//若则从下一个字符重新开始比较}return-1;}给定位置的串匹配算法：intpartposition(sstrings1,sstringt1,intk){//求子串T在主串中首次出现的位置（朴素匹配算法）inti,j,i=k-1;j=0;;while(i<=s1.length&&j

4、)if(s1.ch[i]==s2.ch[j]){i++;j++;}else{i=i-j+1;j=0;}if(j>s2.length)returni-s2.length;elsereturn-1;}return-1;}1、数据类型的存储表示：#defineMaxstrsize256//字符数组的最大容量Typedefstruct{Charch[Maxstrsize];intlength;}sstring;//定义顺序串类型2、参考源代码：#include#include#include//包含串类型sstring

5、和朴素模式匹配算法等。voidmain(){intI,j,k;Sstrings1,t1;intwz[80];//记录子串的位置i=0;//计数器清零s1.length=strlen(s1.ch);t1.length=strlen(t1.ch);k=0;while(k

6、索与计数1、设计要求：要求编程建立一个文本文件，每个单词不包含空格且不跨行，单词由字符序列构成且区分大小写；统计给单词在文本中出现的总次数检索输出某个单词出现在文本中的行号、在该行中出现的次数以及位置。2、算法分析：（1）建立文本文件思路：定义一个串变量和文本文件，然后输入文件名，并打开该文件，再循环读入文本行，并写入文本文件中，最后关闭文件。算法：输入文本文件名；打开该文件；while(文件输入没有结束){读入一文本行到串数据；串变量写入文件；输入是否结束输入标志；}关闭该文件；（1）给定单词的计数算法：输入检索的文本文件名；打开该文件；while(文件没有结束)

7、{读入一行到串中；求出串长度；模式匹配计数；}关闭文件；输出统计结果；（2）检索单词出现在文本中的行号、次数及其位置算法：输入检索的文本文件名；打开该文件；输入要检索统计的单词；行计数器清0;while(文件没有结束){读入一行到串中；求出串长度；行单词计数器置0;模式匹配计数；行号计数器加1；if(行单词计数器！=0)输出行号、该行有匹配单词的个数及出现的位置；}关闭文件；输出统计结果；（3）主控程序结构菜单结构：建立文件、单词计数、单词定位、退出。四个功能选项，输入1-4执行相应的操作，否则为非法。1、参考源代码：//********************