一、实验目的和要求
1理解串的一般线性表之间的差异。
2重点掌握在顺序串上和链串上实现串的基本运算算法。 3掌握串的简单匹配算法和KMP算法。
4灵活运用串这种数据结构解决一些综合应用问题。
二、实验环境、内容和方法
实验内容：
1实现顺序串的各种基本运算。 2实现链串的各种基本运算。
3实现顺序串的各种模式匹配运算。 4求一个串中出现的第一个最长重复串。 实验方法：
通过上机操作完成各内容。 实验环境：
实验用PC机一台，使用操作系统为Windows XP Professional，安装OFFICE 2003、VC++等软件。
三、实验过程描述
实验题4.1实现顺序串各种基本运算的算法
编写一个程序algo4-1.cpp，实现顺序串的各种基本运算，并在此基础上设计一个程序exp4-1.cpp 完成如下功能：
1建立串谁“abcdefghefghefghijklmn”和串s1=”xyz”; 2输出串s; 3输出串s的长度；
4在串s的第9个字符位置插入串s1而产生串s2; 5输出串s2;
6删除串s第2个字符开始的5个字符替换成串s1而产生串s2； 7输出串s2;
8将串s第2个字符开始的5个字符替换成串s1而产生串s2; 9输出串s2;
10提取串s的第2个字符开始的10个字符而产生串s3; 11输出串s3；
12将串s1和串s2连接起来而产生串s4; 13输出串s4.
解：本工程Proj4_1组成结构如图4.1所示。algo4-1.cpp文件，其中包含如下函数： StrAssign(SqString &str,char cstr[]):由串常量cstr创建串str. StrCopy(SqString &s,SqString t):将串t复制到串s.
StrEqual(SqString s,SqString t):判断两个串s和t是否相同。 StrLength(SqString s):求串s的长度。
Concat(SqString s,SqString t):将串t连接到串s之后产生新串。
SubStr(SqString s,int i,int j)：由串s的第i个字符开始的j个字符产生新串。 InsStr(SqString s1,int i,SqString s2):将串s2插入到串s1的第i个位置处。 DelStr(SqString s,int i,int j):删除串s的第i个字符开始的j个字符产生新串。 RepStr(SqString s,int i,int j,SqString t):将串s的第i个字符开始的j个字符替换成串 t产生新串
DispStr(SqString s):输出串s的所有元素。 对应的程序如下：
图4.1 Proj4_1工程组成
//文件名:algo4-1.cpp #include
{ char data[MaxSize]; } SqString;
void StrAssign(SqString &s,char cstr[]) //s为引用型参数 { int i;
for (i=0;cstr[i]!='\\0';i++)
s.data[i]=cstr[i]; s.length=i;
//定义可容纳MaxSize个字符的空间 //标记当前实际串长
int length;
//最多的字符个数
}
void StrCopy(SqString &s,SqString t) //s为引用型参数 { int i; }
bool StrEqual(SqString s,SqString t) { bool same=true; }
int StrLength(SqString s) { }
SqString Concat(SqString s,SqString t) { SqString str; } int i;
str.length=s.length+t.length;
for (i=0;i str.data[i]=s.data[i]; str.data[s.length+i]=t.data[i]; for (i=0;i if (s.length!=t.length) same=false; for (i=0;i if (s.data[i]!=t.data[i]) { same=false; } break; //有一个对应字符不相同时返回0 else //长度不相等时返回0 for (i=0;i s.data[i]=t.data[i]; s.length=t.length; return same; SqString SubStr(SqString s,int i,int j) { SqString str; } SqString InsStr(SqString s1,int i,SqString s2) { int j; } SqString DelStr(SqString s,int i,int j) { int k; SqString str; str.length=0; if (i<=0 || i>s.length || i+j>s.length+1) //参数不正确时返回空串 return str; //将s.data[0..i-2]复制到str str.data[k]=s.data[k]; for (k=0;k if (i<=0 || i>s1.length+1) //参数不正确时返回空串 return str; //将s1.data[0..i-2]复制到str //将s2.data[0..s2.length-1]复制到str //将s1.data[i-1..s1.length-1]复制到str str.data[j]=s1.data[j]; str.data[i+j-1]=s2.data[j]; str.data[s2.length+j]=s1.data[j]; for (j=0;j if (i<=0 || i>s.length || j<0 || i+j-1>s.length) return str; //参数不正确时返回空串 //将s.data[i..i+j]复制到str for (k=i-1;k str.data[k-i+1]=s.data[k]; for (j=i-1;j str.length=s1.length+s2.length; return str;
相关推荐：
loading