数据结构实验三实验报告

数据结构实验报告

实验报告

实验三 串

一．实验目的：

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++;

}

数据结构实验报告

else k=next[k];

}

}

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

{

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

while(i<S.length && j<T.length)

{

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<S.length && j<T.length)

{

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("The parameter pos is error!\n");

return 0;

}

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

{

printf("The space of the array is not enough!\n");

return 0;

}

else

{

for(i=S->length-1; i>=pos; i--)

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

for(i=0; i<T.length; i++)

S->str[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("No elements deleting!\n");

return 0;

}

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

{

printf("The parameters pos and len are not correct!\n");

数据结构实验报告

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("The parameters pos and len are not correct!\n");

return 0;

}

else

{

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

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

T->length=len;

return 1;

}

}

/*BFcomKMP.c*/

#include<stdio.h>

#define MaxSize 100

#include"SString.h"

#include"BFandKMP.h"

void main(void)

{

String S1={{"cddcdc"},6}, T1={{"abcde"},5};

String S2={{"aaaaaaaa"},8}, T2={{"aaaab"},5};

int next[10], count;

count=BFIndexC(S1,0,T1);

printf("the comparison counts of Brute-Force is:%d\n",count);

GetNext(T1, next);

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

printf("the comparison counts of KMP is:%d\n",count);

数据结构实验报告

count=BFIndexC(S2,0,T2);

printf("the comparison counts of Brute-Force is:%d\n",count);

GetNext(T2, next);

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

printf("the comparison counts of KMP is:%d\n",count);

}

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("The parameter pos is error!\n");

return 0;

}

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

{

printf("The space of the array is not enough!\n");

return 0;

}

else

{

for(i=S->length-1; i>=pos; i--)

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

for(i=0; i<T.length; i++)

S->str[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("No elements deleting!\n");

return 0;

}

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

{

printf("The parameters pos and len are not correct!\n");

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("The parameters pos and len are not correct!\n");

return 0;

}

else

{

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

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

T->length=len;

return 1;

}

}

int BFIndex(String S, int start, String T)

{

数据结构实验报告

int i= start, j=0, v;

while(i<S.length && j<T.length)

{

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

{

i++;

j++;

}

else

{

i=i-j+1;

j=0;

}

}

if(j==T.length)

v=i-T.length;

else

v=-1;

return v;

}

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++;

}

else k=next[k];

}

}

数据结构实验报告

int KMPIndex(String S, int start, String T, int next[])

{

int i= start, j=0, v;

while(i<S.length && j<T.length)

{

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

{

i++;

j++;

}

else j=next[j];

}

if(j==T.length)

v=i-T.length;

else

v=-1;

return v;

}

/*RepFun.c*/

#include<stdio.h>

#define MaxSize 100

#include"SString.h"

int Replace(String *S,int start,String T,String V)

{

int i,a;

if(S->length<V.length) return 0;

a=BFIndex(*S,start,T);

if(a!=-1)

{

Delete(S,a,T.length);

Insert(S,a,V);

return 1;

}

else return 0;

}

void main(void)

{

int start=0,b;

String S={{"I am a student"},14}, T={{"student"},7},V={{"teacher"},7}; b=Replace(&S,start,T,V);

printf("run successfully and return %d\n",b);

数据结构实验报告

printf("S=%s\n",&S);

}

实验结果：

4-19

4-20

总结与思考

本次试验对串类型的实现方法有所了解，同时也对简单文字处理的设计方法有了初步的了解， 熟悉C语言的字符和把字符串处理的原理和方法，C语言把字符串字面量作为字符数组来处理。当C语言编译器在程序中遇到长度为n的字符串字面量时，它会为字符串字面量分配长度为n+1的内存空间，在末尾增加一个额外的字符——空字符(\0)。

了解实践了模式匹配算法。

BF算法的基本思想是：

从目标串T的起始比较位置pos开始（在后面的案例中，我们默认pos = 0），和模式串P的第一个字符比较之，若匹配，则继续逐个比较后继字符，否则从串T的下一个字符起再重新和串P的字符比较之。依此类推，直至串P中的每个字符依次和串T中的一个连续的字符序列（即匹配子串）相等，则称匹配成功，返回该匹配子串的首字符下标；否则成匹配不成功，返回-1。BF算法的思想很直接，也很容易理解，其时间复杂度为O（lenT*lenP），其中lenT和lenP分别为串T和串P的长度。

KMP算法：

这是三个人提出的算法，三人的姓氏首字母命名。其思想很简单，却很有效。这种思想同时也是后面三种算法的基础。KMP算法的基本思想是：若某趟匹配过程中T[i]和P[j]不匹配，而前j-1个字符已经匹配。此时只需右移模式串P，文本串T不动，即指针i不回溯，让P[k]与T[i]继续比较。移动后重新开始比较的位置k仅与模式串P有关，而与目标串S无关，因此K可以事先确定。若定义函数next(j)=K，则next函数的定义应为： next(j)=Max{k| P[1..K-1]=P[j-k+1.. j-1] } 本次试验过程中，最重要的是看书，通过看书再实践，对知识点有更多的了解。

本文来源：https://www.bwwdw.com/article/egbe.html