数据结构综合实验报告

一、实验目的和要求

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 #define MaxSize 100 typedef struct

{ 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;