数据结构综合实验报告

一、实验目的和要求

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;

}

for (k=i+j-1;k

str.data[k-j]=s.data[k]; str.length=s.length-j; return str;

//将s.data[i+j-1..s.length-1]复制到str

SqString RepStr(SqString s,int i,int j,SqString t) { int k; }

void DispStr(SqString s) { int i; }

设计如下exp4-1.cpp主程序： //文件名:exp4-1.cpp #include #define MaxSize 100 typedef struct

{ char data[MaxSize]; if (s.length>0)

{ for (i=0;i

printf(\printf(\SqString str; str.length=0;

if (i<=0 || i>s.length || i+j-1>s.length) //参数不正确时返回空串

return str;

//将s.data[0..i-2]复制到str //将t.data[0..t.length-1]复制到str //将s.data[i+j-1..s.length-1]复制到str

str.data[k]=s.data[k]; str.data[i+k-1]=t.data[k]; str.data[t.length+k-j]=s.data[k]; for (k=0;k

for (k=0;k

str.length=s.length-j+t.length; return str;

int length; } SqString;

extern void StrAssign(SqString &str,char cstr[]); extern void StrCopy(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);

extern 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(\建立串s和串s1\\n\StrAssign(s,\StrAssign(s1,\

printf(\输出串s:\

printf(\串s的长度:%d\\n\

printf(\在串s的第9个字符位置插入串s1而产生串s2\\n\s2=InsStr(s,9,s1);

printf(\输出串s2:\

printf(\删除串s第2个字符开始的5个字符而产生串s2\\n\s2=DelStr(s,2,3);

printf(\输出串s2:\

printf(\将串s第2个字符开始的5个字符替换成串s1而产生串s2\\n\s2=RepStr(s,2,5,s1);

printf(\输出串s2:\

printf(\提取串s的第2个字符开始的10个字符而产生串s3\\n\s3=SubStr(s,2,10);

printf(\输出串s3:\

printf(\将串s1和串s2连接起来而产生串s4\\n\

}

s4=Concat(s1,s2);

printf(\输出串s4:\

连编本工程生成可执行文件Proj4_1.exe.程序执行结果如下：

实验题4.2实现链串各种基本运算的算法

编写一个程序algo4-2.cpp,实现链串的各种基本运算，并在此基础上设计一个程序exp4-2.cpp完成如下功能：

1建立串谁“abcdefghefghijklmn”和串s1=”xyz”; 2输出串s; 3输出串s的长度；

4在串s的第9个字符位置插入串s1而产生串s2; 5输出串s2

6删除串s第2个字符开始的5个字符而产生串s2; 7输出串s2;

8将串s第2个字符开始的5个替换成串s2而产生串s2; 图4.3 Proj4_2工程组成 9输出串s2;

10提取串s的第2个字符开始的10个字符而产生串s3; 11输出串s3;

12将串s1和串s2连接起来而产生串s4; 13输出串s4.

本工程Proj4_2的组成结构如图4.3所示。 算法algo4-2.cpp文件，其中包含如下函数：

void StrAssign(LiString *&str,char cstr[])：有串常量cstr创建串str;

void StrCopy(LiString *&s,LiString *t)：将串t复制到串s.

bool StrEqual(LiString *s,LiString *t):判断两个串s和t是否相同。 int StrLength(LiString *s)：求串的长度

LiString *Concat(LiString *s,LiString *t)：将串t连接到串s之后产生新串

LiString *SubStr(LiString *s,int i,int j)：有串s的第i个字符开始的j个字符产生新串。 LiString *InsStr(LiString *s1,int i,LiString *s2)：将串s2插入到串s1的第i个位置处 LiString *DelStr(LiString *s,int i,int j)：删除串s的第i个字符开始的j个字符产生的新串。

LiString *RepStr(LiString *s,int i,int j,LiString *t)：将串s的第i个字符开始的j个字符替换成串t产生新串。 void DispStr(LiString *str)：输出串s的所有元素。 对应的程序如下： //文件名:algo4-2.cpp #include #include typedef struct snode {

char data; struct snode *next; } LiString;

void StrAssign(LiString *&s,char cstr[]) { }

int i; LiString *r,*p;

s=(LiString *)malloc(sizeof(LiString)); r=s;

//r始终指向尾节点

for (i=0;cstr[i]!='\\0';i++) { }

r->next=NULL;

p=(LiString *)malloc(sizeof(LiString)); p->data=cstr[i]; r->next=p;r=p;

void StrCopy(LiString *&s,LiString *t) { }

bool StrEqual(LiString *s,LiString *t) { }

int StrLength(LiString *s) {

int i=0;

LiString *p=s->next; while (p!=NULL) { }

i++; p=p->next;

LiString *p=s->next,*q=t->next;

while (p!=NULL && q!=NULL && p->data==q->data) { }

if (p==NULL && q==NULL) else

return false; return true; p=p->next; q=q->next;

LiString *p=t->next,*q,*r;

s=(LiString *)malloc(sizeof(LiString)); r=s;

//r始终指向尾节点

//将t的所有节点复制到s

while (p!=NULL) { }

r->next=NULL;

q=(LiString *)malloc(sizeof(LiString)); q->data=p->data; r->next=q;r=q; p=p->next;

}

return i;

LiString *Concat(LiString *s,LiString *t) { }

LiString *SubStr(LiString *s,int i,int j) {

int k;

LiString *str,*p=s->next,*q,*r; str=(LiString *)malloc(sizeof(LiString)); str->next=NULL; r=str;

//r指向新建链表的尾节点

LiString *str,*p=s->next,*q,*r; str=(LiString *)malloc(sizeof(LiString)); r=str;

while (p!=NULL) { } p=t->next; while (p!=NULL) { }

r->next=NULL; return str;

//将t的所有节点复制到str

//将s的所有节点复制到str

q=(LiString *)malloc(sizeof(LiString)); q->data=p->data; r->next=q;r=q; p=p->next;

q=(LiString *)malloc(sizeof(LiString)); q->data=p->data; r->next=q;r=q; p=p->next;

if (i<=0 || i>StrLength(s) || j<0 || i+j-1>StrLength(s))

return str;

//参数不正确时返回空串

连编本工程生成可执行文件Proj4_2.exe.程序执行结果如下：

实验题4.3 顺序串的各种模式匹配运算

编写一个程序exp4-3cpp,实现顺序串的各种模式匹配运算，并在此基础上完成如下功能： 1建立“abcabcdabcdeabcdefabcdefg”目标串s和“abcdeabcdefab”模式串t; 2采用简单匹配算法求t在s中的位置； 3有模式串t求next值和nextval值； 4采用KMP算法求t在s中的位置； 5采用改进的KMP算法求t在s中的位置。

本工程Proj4_3的组成结构如图4.5所示。 图4.5 Proj4_3工程组成 算法得到exp4-3.cpp文件，其中包含如下函数： Idex(SqString s,SqString t):简单模式匹配算法。 GetNext(SqString t,int next[]):由模式串t求出next值。 GetNextval(SqString t,int nextval[]):由模式串t求出nextval值。 KMPInex(SqString s,SqString t):KMP算法。

KMPIndex1(SqString s,SqString t):改进的KMP算法。 //文件名:exp4-3.cpp #include #include #define MaxSize 100 typedef struct

{ char data[MaxSize]; int length; } SqString;

//定义可容纳MaxSize个字符的空间

//标记当前实际串长

extern void StrAssign(SqString &,char []); //在algo4-1.cpp文件中 extern void DispStr(SqString); int Index(SqString s,SqString t) { }

void GetNext(SqString t,int next[]) {

int j,k;

j=0;k=-1;next[0]=-1; while (j

if (k==-1 || t.data[j]==t.data[k]) //k为-1或比较的字符相等时 {

j++;k++; next[j]=k;

//由模式串t求出next值

int i=0,j=0;

while (i

if (j>=t.length) else

return(-1);

//模式匹配不成功

return(i-t.length);

//返回匹配的第一个字符的下标

if (s.data[i]==t.data[j]) //继续匹配下一个字符 { } else { }

//主串、子串指针回溯重新开始下一次匹配 //主串从下一个位置开始匹配

//子串从头开始匹配

i++; j++;

//主串和子串依次匹配下一个字符

//简单匹配算法

i=i-j+1; j=0;

}

}

}

else k=next[k];

int KMPIndex(SqString s,SqString t) //KMP算法 { }

void GetNextval(SqString t,int nextval[]) //由模式串t求出nextval值 {

int j=0,k=-1; nextval[0]=-1; while (j

if (k==-1 || t.data[j]==t.data[k]) {

j++;k++;

if (t.data[j]!=t.data[k]) else

nextval[j]=k;

int next[MaxSize],i=0,j=0; GetNext(t,next);

while (i

if (j>=t.length) else

return(-1);

//返回不匹配标志

return(i-t.length);

//返回匹配模式串的首字符下标

if (j==-1 || s.data[i]==t.data[j]) { }

else j=next[j];

//i不变,j后退

i++; j++;

//i,j各增1

}

}

} else

nextval[j]=nextval[k];

k=nextval[k];

int KMPIndex1(SqString s,SqString t) //修正的KMP算法 { }

void main() {

int j;

int next[MaxSize],nextval[MaxSize]; SqString s,t;

StrAssign(s,\int nextval[MaxSize],i=0,j=0; GetNextval(t,nextval);

while (i

if (j>=t.length) else

return(-1); return(i-t.length);

if (j==-1 || s.data[i]==t.data[j]) { } else

j=nextval[j]; i++; j++;

}

StrAssign(t,\printf(\串s:\printf(\串t:\printf(\简单匹配算法:\\n\

printf(\ t在s中的位置=%d\\n\GetNext(t,next);

//由模式串t求出next值 //由模式串t求出nextval值

GetNextval(t,nextval); printf(\ j \for (j=0;j

printf(\

printf(\printf(\ \for (j=0;j

printf(\

printf(\printf(\ \for (j=0;j

printf(\

printf(\printf(\for (j=0;j

printf(\

printf(\

printf(\算法:\\n\

printf(\ t在s中的位置=%d\\n\printf(\改进的KMP算法:\\n\

printf(\ t在s中的位置=%d\\n\

本文来源：https://www.bwwdw.com/article/0tu7.html