实验报告
课程 学号
数据结构 姓名 实验名称 实验三 串 实验日期： 串的操作
实验目的：
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(\ 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; 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(\ 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) /*取串S的从pos位置开始长度为len的子串值赋给子串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赋值*/ 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; 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]; } } /*查找子串BF(Brute-Force)算法累计次数 */ int BFIndexC(String S, int start, String T) /*查找主串S从start开始的子串T，找到返回T在S中的开始字符下标，否则返回-1*/ { 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; } /*查找子串KMP(D.E.Knuth-J.H.Morris-V.R.Pratt)操作 */ int KMPIndexC(String S, int start, String T, int next[]) /*查找主串S从start开始的子串T，找到返回T在S中的首字符下标，*/ /*否则返回-1*/ /*数组Next中存放有模式串T的next[j]值*/ { int i= start, j=0, t=0; while(i if(S.str[i]==T.str[j]) { i++; j++; } else if(j==0) i++; else j=next[j]; t++; } return t; } 测试主函数： #include
数据结构串的操作实验报告
