还剩1页未读,继续阅读
文本内容:
上机实验2串的匹配算法及实现【实验目的】1了解串的相关概念2掌握串的有关存储方法3熟悉串的基本操作4通过串匹配算法的实现,掌握朴素的模式匹配算法【实验内容】实现朴素的模式匹配算法要求能够实现从键盘输入主串S和子串T,并且能够从键盘指定S的第pos位为开始匹配的位置,如果匹配成功,则在屏幕输出S中符合匹配的位置,即S中与T匹配的子序列第一个字符的序号,否则,返回0【实验步骤】1在Microsoft VisualC++中创建应用程序L22在程序中创建字符串的存储函数InitStr,使用数组的0号单元存储字符串的长度3创建字符串的匹配函数Index4创建主函数,实现从键盘上输入主串S、子串T,并能够指定开始匹配的位置5编译连接程序,执行并观察程序的运行效果【参考源代码】#include stdio.h#include string.h#define MAXSIZE100//字符串的最大存储长度typedef charSString[MAXSIZE+l];//使用0号单元存储长度void InitStrSStringrschar stmp[MAXSIZE];int i;getsstmp;rs
[0]=strlenstmp;for i=l;i=rs[01;i++rs[i]=stmp[i-l];rs[i]=\0;int IndexSStringS,SString T,int pos//返回T在S中第pos个字符后首次出现的位置,若不存在则返回0int i=posj=1;whilei=S
[0]j=T
[0]ifS[i]=T[j]//匹配继续比较后继字符++i;++j;else//不匹配,指针后退,重新开始匹配i=i-j+2;j=1;ifOT
[0]return i-T
[0];//匹配成功返回T在S中第pos个字符后首次出现的位置else return0;}//Index voidmainSString sstr;SString dstr;int pos;int n;printf请输入主串”;InitStrsstr;printf请输入子串”;InitStrdstr;printff请输入开始匹配的位置”;scanf H%d n,pos;n=Indexsstr,dstr,pos;printf n%d\n H,n;【运行结果】运行示例主串输入sit please子串输入please匹配位置输入2运行结果如附图2所示c.C:\VI!TOO¥S\syste32\cd.exe遭地入主亭sit please请输入子串please请输入开始匹配的位置2按任意键继续・.・■附图2上机实验2运行结果【实验总结】编程时应注意,存储字符串有一个转换的过程,通过InitStr函数,将键盘上获取的字符串转换成符合要求的存储结构,使得存储字符串数组的第一位为字符串的长度,这样方便了Index函数的编写,在比较时能够更直观地使用数组的下标进行操作,而不用再作相应的考虑与转换编写程序时应注意数组长度的设置,在保证有足够存储空间的情况下不必定义过长,参考源代码中指定的是100,编程者可根据实际情况自行设置其大小在编写Index函数时,应注意回退指针的计算,以免造成匹配出错的情况。