数据结构综合实验报告(4)

连编本工程生成可执行文件Proj4_2.exe.程序执行结果如下：

实验题4.3 顺序串的各种模式匹配运算

编写一个程序exp4-3cpp,实现顺序串的各种模式匹配运算，并在此基础上完成如下功能： 1建立“abcabcdabcdeabcdefabcdefg”目标串s和“abcdeabcdefab”模式串t; 2采用简单匹配算法求t在s中的位置； 3有模式串t求next值和nextval值； 4采用KMP算法求t在s中的位置； 5采用改进的KMP算法求t在s中的位置。

本工程Proj4_3的组成结构如图4.5所示。 图4.5 Proj4_3工程组成 算法得到exp4-3.cpp文件，其中包含如下函数： Idex(SqString s,SqString t):简单模式匹配算法。 GetNext(SqString t,int next[]):由模式串t求出next值。 GetNextval(SqString t,int nextval[]):由模式串t求出nextval值。 KMPInex(SqString s,SqString t):KMP算法。

KMPIndex1(SqString s,SqString t):改进的KMP算法。 //文件名:exp4-3.cpp #include #include #define MaxSize 100 typedef struct

{ char data[MaxSize]; int length; } SqString;

//定义可容纳MaxSize个字符的空间

//标记当前实际串长

extern void StrAssign(SqString &,char []); //在algo4-1.cpp文件中 extern void DispStr(SqString); int Index(SqString s,SqString t) { }

void GetNext(SqString t,int next[]) {

int j,k;

j=0;k=-1;next[0]=-1; while (j

if (k==-1 || t.data[j]==t.data[k]) //k为-1或比较的字符相等时 {

j++;k++; next[j]=k;

//由模式串t求出next值

int i=0,j=0;

while (i

if (j>=t.length) else

return(-1);

//模式匹配不成功

return(i-t.length);

//返回匹配的第一个字符的下标

if (s.data[i]==t.data[j]) //继续匹配下一个字符 { } else { }

//主串、子串指针回溯重新开始下一次匹配 //主串从下一个位置开始匹配

//子串从头开始匹配

i++; j++;

//主串和子串依次匹配下一个字符

//简单匹配算法

i=i-j+1; j=0;

}

}

}

else k=next[k];

int KMPIndex(SqString s,SqString t) //KMP算法 { }

void GetNextval(SqString t,int nextval[]) //由模式串t求出nextval值 {

int j=0,k=-1; nextval[0]=-1; while (j

if (k==-1 || t.data[j]==t.data[k]) {

j++;k++;

if (t.data[j]!=t.data[k]) else

nextval[j]=k;

int next[MaxSize],i=0,j=0; GetNext(t,next);

while (i

if (j>=t.length) else

return(-1);

//返回不匹配标志

return(i-t.length);

//返回匹配模式串的首字符下标

if (j==-1 || s.data[i]==t.data[j]) { }

else j=next[j];

//i不变,j后退

i++; j++;

//i,j各增1

}

}

} else

nextval[j]=nextval[k];

k=nextval[k];

int KMPIndex1(SqString s,SqString t) //修正的KMP算法 { }

void main() {

int j;

int next[MaxSize],nextval[MaxSize]; SqString s,t;

StrAssign(s,\int nextval[MaxSize],i=0,j=0; GetNextval(t,nextval);

while (i

if (j>=t.length) else

return(-1); return(i-t.length);

if (j==-1 || s.data[i]==t.data[j]) { } else

j=nextval[j]; i++; j++;

}

StrAssign(t,\printf(\串s:\printf(\串t:\printf(\简单匹配算法:\\n\

printf(\ t在s中的位置=%d\\n\GetNext(t,next);

//由模式串t求出next值 //由模式串t求出nextval值

GetNextval(t,nextval); printf(\ j \for (j=0;j

printf(\

printf(\printf(\ \for (j=0;j

printf(\

printf(\printf(\ \for (j=0;j

printf(\

printf(\printf(\for (j=0;j

printf(\

printf(\

printf(\算法:\\n\

printf(\ t在s中的位置=%d\\n\printf(\改进的KMP算法:\\n\

printf(\ t在s中的位置=%d\\n\

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构综合实验报告(4)在线全文阅读。