数据结构实验三实验报告

实验报告

课程 学号

数据结构 080673220 姓名 实验名称 邵爱华 实验三 串 实验日期： 2010年11月19日 实验三 串

一．实验目的：

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

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

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

else if(k==0) {

next[j+1]=0; j++; }

else k=next[k]; } }

int BFIndexC(String S, int start, String T) {

int i= start, j=0, t=0;

while(i

if(S.str[i]==T.str[j]) {

i++; j++; } else {

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

return t; }

int KMPIndexC(String S, int start, String T, int next[]) {

int i= start, j=0,t=0;

while(i

if(j==-1||S.str[i]==T.str[j]) {

i++; j++; }

else j=next[j]; t++; }

return t; }

/*SString.h*/ typedef struct {

char str[MaxSize]; int length;

}String;

void Initiate(String *S) {

S->length=0; }

int Insert(String *S, int pos, String T) {

int i;

if(pos<0||pos>S->length) {

printf(\ return 0; }

else if(S->length+T.length>MaxSize) {

printf(\ return 0; } else {

for(i=S->length-1; i>=pos; i--) S->str[i+T.length]=S->str[i]; for(i=0; istr[pos+i]=T.str[i]; S->length=S->length+T.length; return 1; } }

int Delete(String *S, int pos, int len) {

int i;

if(S->length<=0) {

printf(\ return 0; }

else if(pos<0||len<0||pos+len>S->length) {

printf(\

return 0; } else {

for(i=pos+len; i<=S->length-1; i++) S->str[i-len]=S->str[i]; S->length=S->length-len; return 1; } }

int SubString(String S, int pos, int len, String *T) {

int i;

if(pos<0||len<0||pos+len>S.length) {

printf(\ return 0; } else {

for(i=0; i<=len; i++)

T->str[i]=S.str[pos+i]; T->length=len;

return 1; } }

/*BFcomKMP.c*/ #include #define MaxSize 100 #include\#include\void main(void) {

String S1={{\ String S2={{\ int next[10], count; count=BFIndexC(S1,0,T1);

printf(\ GetNext(T1, next);

count=KMPIndexC(S1,0,T1,next);

printf(\

count=BFIndexC(S2,0,T2);

printf(\ GetNext(T2, next);

count=KMPIndexC(S1,0,T2,next);

printf(\} 4-20

/*SString.h*/ typedef struct {

char str[MaxSize]; int length; }String;

void Initiate(String *S) {

S->length=0; }

int Insert(String *S, int pos, String T) {

int i;

if(pos<0||pos>S->length) {

printf(\ return 0; }

else if(S->length+T.length>MaxSize) {

printf(\ return 0; } else {

for(i=S->length-1; i>=pos; i--) S->str[i+T.length]=S->str[i]; for(i=0; istr[pos+i]=T.str[i]; S->length=S->length+T.length; return 1; } }