数据结构实验三实验报告

数据结构实验报告

实验报告

实验三 串

一．实验目的：

1. 熟悉串类型的实现方法，了解简单文字处理的设计方法；

2. 熟悉C语言的字符和把字符串处理的原理和方法；

3. 熟悉并掌握模式匹配算法。

二．实验原理：

1.顺序存储结构下的关于字符串操作的基本算法。

2.模式匹配算法BF、KMP

三．实验内容：

4-19.

在4.4.3节例4—6的基础上，编写比较Brute_Force算法和KMP算法比较次数的程序。 4-20.

设串采用静态数组存储结构，编写函数实现串的替换Replace(S,start,T,V),即要求在主串S中，从位置start开始查找是否存在子串T,若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回0。并要求设计主函数进行测试。一个测试例子为：S=“I am a student”,T=”student”,V=”teacher”。

四．程序代码：

4-19

/*BFandKMP.h*/

void GetNext(String T, int next[])

{

int j=1, k=0;

next[0]=-1;

next[1]=0;

while(j<T.length)

{

if(T.str[j]==T.str[k])

{

next[j+1]=k+1;

j++;

k++;

}

else if(k==0)

{

next[j+1]=0;

j++;

}