数据结构串实验报告
- 格式：doc
- 大小：275.00 KB
- 文档页数：8
下载文档原格式
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
实验报告
实验三串
实验目的：
1. 熟悉串类型的实现方法，了解简单文字处理的设计方法；
2. 熟悉C语言的字符和把字符串处理的原理和方法；
3. 熟悉并掌握模式匹配算法。
实验原理：
顺序存储结构下的关于字符串操作的基本算法。
模式匹配算法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的代码：
/*静态存储结构*/
typedef struct
{
char str[MaxSize];
int length;
}String;
/*初始化操作*/
void Initiate(String *S)
{
S->length=0;
}
/*插入子串操作*/
int Insert(String *S, int pos, String T)
/*在串S的pos位置插入子串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 S->str[pos+i]=T.str[i]; /*插入*/ S->length=S->length+T.length; /*产生新的串长度值*/ return 1; } } /*删除子串操作*/ int Delete(String *S, int pos, int len) /*删除串S的从pos位置开始长度为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) /*取串S的从pos位置开始长度为len的子串值赋给子串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赋值*/ T->length=len; /*给子串T的长度域赋值*/ return 1; } } /*查找子串BF(Brute-Force)操作*/ int BFIndex(String S, int start, String T) /*查找主串S从start开始的子串T，找到返回T在S中的开始字符下标，否则返回-1*/ { int i= start, j=0, v; while(i { 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; } /*查找子串KMP(D.E.Knuth-J.H.Morris-V.R.Pratt)操作*/ int KMPIndex(String S, int start, String T, int next[]) /*查找主串S从start开始的子串T，找到返回T在S中的首字符下标，*/ /*否则返回-1*/ /*数组Next中存放有模式串T的next[j]值*/ { int i= start, j=0, v; while(i { if(S.str[i]==T.str[j]) { i++; j++; } else if(j==0) i++; else j=next[j]; } if(j==T.length) v=i-T.length; else v=-1; return v; } /*求模式串next[j]值的操作*/ void GetNext(String T, int next[]) /*求子串T的next[j]值并存放于数组next中*/ { int j=1, k=0; next[0]=-1;