实验三 串的应用.doc

实验三 串的应用基本思路； 串是非数值运算中的处理的主要对象，如信息检索、文本编辑、符号处理等得到广泛应用。本实验的目的在于让学生有效实现串的处理，这就要求学生熟悉串的存储结构及其基本运算。首先设计出串的定位算法及其实现；然后再利用串的定位算法设计文本的检索及单词的计数等操作。一、 串模式匹配算法的设计与实现1、 设计要求：子串的定位就是要求子串在主串中首次出现的位置。称为模式匹配。只要求学生能用最简单的朴素模式算法即可。算法思路为：将给定的子串与主串从第一个字符开始比较，找到首次与子串完全匹配的子串为止，并记住位置。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，表示失败。int index(sstring S,sstring T)/求子串T在主串中首次出现的位置（朴素匹配算法）int i,j,k,m,n;m=T.length;n=S.length;for (i=0;i=n-m;i+) j=0;k=i; while (j=m&S.chk=T.chj) k+;j+;/继续下一个字符的比较if (j=m)/return i;/若相等，则说明找到匹配的子串，返回匹配位置i /若则从下一个字符重新开始比较return -1;给定位置的串匹配算法：int partposition(sstring s1,sstring t1,int k)/求子串T在主串中首次出现的位置（朴素匹配算法）int i,j,i=k-1;j=0;while (i=s1.length&js2.length) return i-s2.length;else return -1;return -1;3、 数据类型的存储表示：#define Maxstrsize 256/字符数组的最大容量Typedef struct Char chMaxstrsize;int length;sstring;/定义顺序串类型4、 参考源代码：#include #include #include /包含串类型sstring和朴素模式匹配算法等。void main()int I,j,k;Sstring s1,t1;int wz80;/记录子串的位置i=0;/计数器清零s1.length=strlen(s1.ch);t1.length=strlen(t1.ch);k=0;while(ks1.length-1)/检索整个主串s1j=partposition(s1,t1,k);if (j0)printf(“没有检索到需要的子串”)；break;else i+;wzi=j;k=j+t1.length;printf(“子串%s出现在主串中的位置为：”)二、 文本文件单词的检索与计数1、 设计要求：要求编程建立一个文本文件，每个单词不包含空格且不跨行，单词由字符序列构成且区分大小写；统计给单词在文本中出现的总次数检索输出某个单词出现在文本中的行号、在该行中出现的次数以及位置。2、 算法分析：（1） 建立文本文件思路：定义一个串变量和文本文件，然后输入文件名，并打开该文件，再循环读入文本行，并写入文本文件中，最后关闭文件。算法：输入文本文件名；打开该文件；while (文件输入没有结束)读入一文本行到串数据；串变量写入文件；输入是否结束输入标志； 关闭该文件；（2） 给定单词的计数算法：输入检索的文本文件名；打开该文件；while (文件没有结束)读入一行到串中；求出串长度；模式匹配计数；关闭文件；输出统计结果；（3） 检索单词出现在文本中的行号、次数及其位置算法：输入检索的文本文件名；打开该文件；输入要检索统计的单词；行计数器清0;while (文件没有结束)读入一行到串中；求出串长度；行单词计数器置0;模式匹配计数；行号计数器加1；if (行单词计数器！=0)输出行号、该行有匹配单词的个数及出现的位置；关闭文件；输出统计结果；（4） 主控程序结构菜单结构：建立文件、单词计数、单词定位、退出。四个功能选项，输入1-4执行相应的操作，否则为非法。3、 参考源代码：/*/ 建立文本文件函数/*void creattextfile()sstrint s;char fname10,yn;FILE *fp;printf(“请输入要建立的文件名：”);scanf(“%s”,fname);fp=fopen(fname);yn=”n”;while (yn=”n”&yn=”N”)printf(“输入一行文本：”);gets(s.ch);s.length=strlen(s.ch);fwrite(&s,size(s),1,fp);printf(“结束输入吗？”);yn=getchar();fclose(fp);printf(“建立文件结束！”);/*/ 文本文件单词计数函数/*void substrcount() File *fp;Sstring s,t;int i=0,j,k;printf(“输入文本文件名：”);scanf(“%s”,fname);fp=fopen(fanme,”r”);printf(“输入单词要统计计数的单词：”);scanf(“%s”,t.ch);t.length=strlen(t.ch);while (!feof(fp)fread(s,sizeof(s),1,fp);k=0;while (ks.length-1)j=partposition(s,t,k);k=0;if (j0) break;else i+;k=j+t.length;printf(“n单词%s在文本文件%s中共出现%d次n,t.ch,fname,i”);/*/检索单词出现在文件中的行号、位置及出现的次数的函数/*void substrind()FILE *fp;sstring s,t;char fname10;int i,j,k,l,m;int wz20;printf(“输入文本文件名：”);scanf(“%s”,fname);fp=fopen(fanme,”r”);printf(“输入需要检索的单词：”);scanf(“%s”,t.ch);t.length=strlen(t.ch);l=0;while (!feof(fp)fread(&s,sizeof(s),fp);l+;k=0;i=0;while (ks.length-1)j=partpositoin(s,t,k);if (j0)printf(“行号：%d，次数，%d，位置分别为：”，l,i);for (m=1;m=I;m+)printf(“%4d”,wzm);printf(“n”);)/*/ 主 控 菜 单 程 序/*#include #include #include “strpp.h”/包含串类型和匹配函数#include “fun.h”/存储三个函数的头文件void main() void creattextfile(),subst