《数据结构综合实验报告.》由会员分享，可在线阅读，更多相关《数据结构综合实验报告.（26页珍藏版）》请在金锄头文库上搜索。
1、一、实验目的和要求1理解串的一般线性表之间的差异。2重点掌握在顺序串上和链串上实现串的基本运算算法。3掌握串的简单匹配算法和KMP算法。4灵活运用串这种数据结构解决一些综合应用问题。二、实验环境、内容和方法实验内容： 1实现顺序串的各种基本运算。 2实现链串的各种基本运算。 3实现顺序串的各种模式匹配运算。 4求一个串中出现的第一个最长重复串。实验方法：通过上机操作完成各内容。实验环境：实验用PC机一台，使用操作系统为Windows XP Professional，安装OFFICE 2003、VC+等软件。三、实验过程描述实验题4.1实现顺序串各种基本运算的算法编写一个程序algo4-1.cp
2、p，实现顺序串的各种基本运算，并在此基础上设计一个程序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.
3、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
4、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 #define MaxSize 100 /最多的字符个数typedef struct char dataMaxSize;/定义可容纳
5、MaxSize个字符的空间 int length; /标记当前实际串长 SqString;void StrAssign(SqString &s,char cstr)/s为引用型参数int i;for (i=0;cstri!=0;i+)s.datai=cstri;s.length=i;void StrCopy(SqString &s,SqString t)/s为引用型参数int i;for (i=0;it.length;i+)s.datai=t.datai;s.length=t.length;bool StrEqual(SqString s,SqString t)bool same=true;i
6、nt i;if (s.length!=t.length)/长度不相等时返回0same=false;else for (i=0;is.length;i+)if (s.datai!=t.datai)/有一个对应字符不相同时返回0same=false;break;return same;int StrLength(SqString s)return s.length;SqString Concat(SqString s,SqString t)SqString str;int i;str.length=s.length+t.length;for (i=0;is.length;i+)/将s.data0.
7、s.length-1复制到strstr.datai=s.datai;for (i=0;it.length;i+)/将t.data0.t.length-1复制到strstr.datas.length+i=t.datai;return str;SqString SubStr(SqString s,int i,int j)SqString str;int k;str.length=0;if (is.length | js.length)return str;/参数不正确时返回空串for (k=i-1;ki+j-1;k+) /将s.datai.i+j复制到strstr.datak-i+1=s.data
8、k;str.length=j;return str; SqString InsStr(SqString s1,int i,SqString s2)int j;SqString str;str.length=0;if (is1.length+1) /参数不正确时返回空串return str;for (j=0;ji-1;j+) /将s1.data0.i-2复制到strstr.dataj=s1.dataj;for (j=0;js2.length;j+)/将s2.data0.s2.length-1复制到strstr.datai+j-1=s2.dataj;for (j=i-1;js1.length;j+
9、)/将s1.datai-1.s1.length-1复制到strstr.datas2.length+j=s1.dataj;str.length=s1.length+s2.length;return str;SqString DelStr(SqString s,int i,int j)int k;SqString str;str.length=0;if (is.length | i+js.length+1) /参数不正确时返回空串return str;for (k=0;ki-1;k+) /将s.data0.i-2复制到strstr.datak=s.datak;for (k=i+j-1;ks.len
10、gth;k+)/将s.datai+j-1.s.length-1复制到strstr.datak-j=s.datak;str.length=s.length-j;return str;SqString RepStr(SqString s,int i,int j,SqString t)int k;SqString str;str.length=0;if (is.length | i+j-1s.length) /参数不正确时返回空串return str;for (k=0;ki-1;k+)/将s.data0.i-2复制到strstr.datak=s.datak;for (k=0;kt.length;k+
11、) /将t.data0.t.length-1复制到strstr.datai+k-1=t.datak;for (k=i+j-1;k0)for (i=0;is.length;i+)printf(%c,s.datai);printf(n);设计如下exp4-1.cpp主程序：/文件名:exp4-1.cpp#include #define MaxSize 100 typedef struct char dataMaxSize; int length; SqString;extern void StrAssign(SqString &str,char cstr);extern void StrCopy(
12、SqString &s,SqString t);extern bool StrEqual(SqString s,SqString t);extern int StrLength(SqString s);extern SqString Concat(SqString s,SqString t);extern SqString SubStr(SqString s,int i,int j);extern SqString InsStr(SqString s1,int i,SqString s2);extern SqString DelStr(SqString s,int i,int j);exter
13、n SqString RepStr(SqString s,int i,int j,SqString t);extern void DispStr(SqString str);void main()SqString s,s1,s2,s3,s4;printf(顺序串的基本运算如下:n);printf( (1)建立串s和串s1n);StrAssign(s,abcdefghijklmn);StrAssign(s1,123);printf( (2)输出串s:);DispStr(s);printf( (3)串s的长度:%dn,StrLength(s);printf( (4)在串s的第9个字符位置插入串s1而产生串s2n);s2=InsStr(s,9,s1)
