数据结构串实验报告
-
实验报告
课程
学号
数据结构
姓名
实验名称
实验三
串
实验日期：
实验三
串
实验目的：
1.
熟悉串类型的实现方法，了解简单文字处理的设计方法；
2.
熟悉
C
语言的字符和把字符串处理的原理和方法；
3.
熟悉并掌握模式匹配算法。
实验原理：
顺序存储结构下的关于字符串操作的基本算法。
模式匹配算法
BF
、
KMP
实验内容：
4-19.
在
4.4.3
节例
4-6
的基础上，编写比较
< br>Brute-Force
算法和
KMP
< br>算法比较次数的
程序。
4-20.
设串采用静态数组存储结构，
编写函数实现串的替换
Replace
（
< br>S
，
start
，
T
，
V
）
< br>，
即要求在主串
S
中，从位置<
/p>
start
开始查找是否存在字串
T
。若主串
S
中存在子串
T
，则用
子串
V
< br>替换子串
T
，且函数返回
1
；若主串
S
中不存在子串
< br>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+>MaxSize)
{
printf(
return 0;
}
else
{
for(i=S->length-1; i>=pos; i--)
S->str[i+]=S->str[i];
/*
依次后移数据元素
*/
for(i=0; i<; i++)
S->str[pos+i]=[i];
/*
插入
*/
S->length=S->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)
/*
< br>取串
S
的从
pos
位置开始长度为
len
的子串值赋给子串
T*/
{
int i;
if(pos<0||len<0||pos+len>)
{
printf(
return 0;
}
else
{
for(i=0; i<=len; i++)
T->str[i]=[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< && j<)
{
if([i]==[j])
{
i++;
j++;
}
else
{
i=i-j+1;
j=0;
}
}
if(j==)
v=;
else
v=-1;
return v;
}
/*
查
找子串
KMP(-V
.)
操作
*/
int
KMPIndex(String S, int start, String T, int
next[])
/*
查找主串
S
从
start
开始的子串
< br>T
，找到返回
T
在
S
中的首字符下标，
*/
/*
否则返回
-1*/
/*
数组
Next
中存放有
模式串
T
的
next[j]
值
*/
{
int i= start, j=0, v;
while(i< && j<)
{
if([i]==[j])
{
i++;
j++;
}
else if(j==0) i++;
else j=next[j];
}
if(j==)
v=;
else
v=-1;
return v;
}
/*
求模式串
next[j]
值的操作
*/
void GetNext(String T,
int next[])
/*
求子串
T
的
next[j]
值并存放于数组<
/p>
next
中
*/
{
int j=1, k=0;
next[0]=-1;