数据结构-顺序串基本操作实验报告.doc

数据结构实验报告
课程 数据结构 _ 实验名称 顺序串基本操作
院系 电信学院 专业班级 计科10-4
姓名 学 号

一、实验目的
1）熟悉串的定义和串的基本操作。
2）掌握顺序串的基本运算。
3）加深对串数据结构的理解，逐步培养解决实际问题的编程能力。
二、实验环境
装有Visual C＋＋6.0的计算机。
本次实验共计2学时。
三、实验内容
编写一个程序，实现顺序串的各种基本运算，并在此基础上设计一个主程序。具体如下：

编写串的基本操作函数
顺序串类型定义如下所示：
typedef struct {
char ch[MAX];
int length;
} SeqString;

（1）串赋值 Assign(s,t)
将一个字符串常量赋给串s,即生成一个其值等于t的串s
（2）串复制 StrCopy(s,t)
将串t赋给串s
（3） 计算串长度 StrLength(s)
返回串s中字符个数

（4）判断串相等StrEqual(s,t)
若两个串s与t相等则返回1；否则返回0。
（5）串连接 Concat(s,t)
返回由两个串s和t连接在一起形成的新串。
（6）求子串 SubStr(s,i,j)
返回串s中从第i(1≤i≤StrLength(s))个字符开始的、由连续j个字符组成的子串。

（7）插入InsStr (s,i,t)
将串t插入到串s的第i(1≤i≤StrLength(s)+1)个字符中,即将t的第一个字符作为s的
第i个字符,并返回产生的新串
（8）串删除 DelStr (s,i,j)
从串s中删去从第i(1≤i≤StrLength(s))个字符开始的长度为j的子串,并返回产生新串。

（9）串替换 RepStr (s,s1,s2)
在串s中,将所有出现的子串s1均替换成s2。
（10）输出串DispStr(s)
输出串s的所有元素值
（11） 判断串是否为空 IsEmpty(s)
为空返回1，不为空返回0

编写主函数

调用上述函数实现下列操作：
（1） 建立串s=“abcdefghijklmn”，串s1=“xyz”，串t＝“hijk”
（2） 复制串t到t1，并输出t1的长度
（3） 在串s的第9个字符位置插入串s1而产生串s2，并输出s2
（4） 删除s第2个字符开始的5个字符而产生串s3，并输出s3
（5） 将串s第2个字符开始的3个字符替换成串s1产生串s4，输出s4
（6） 提取串s的第2个字符开始的10个字符而产生串s5，并输出s5
（7） 将串s1和串t连接起来而产生串s4，并输出s4
（8） 比较串s1和s5是否相等，输出结果
（9） 判断s3是否为空

四、源程序代码
#include<stdio.h>
#define MAX 100

typedef struct
{
char ch[MAX];
int length;
} SqString;

void StrAssign(SqString &s,char t[]) //串赋值
{
int i;
for(i=0;t[i]!='\0';i++)
s.ch[i]=t[i];
s.length=i;
}

void StrCopy(SqString &s,SqString t) //串复制
{
int i;
for(i=0;i<t.length;i++)
s.ch[i]=t.ch[i];
s.length=t.length;
}

int StrEqual(SqString s,SqString t) //判断串相等
{
int same=1,i;

if(s.length!=t.length){
same=0;
}
else{
for(i=0;i<s.length;i++)
if(s.ch[i]!=t.ch[i]){
same=0;
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;i<s.length;i++)
str.ch[i]=s.ch[i];
for(i=0;i<t.length;i++)
str.ch[s.length+i]=t.ch[i];
return str;
}

SqString SubStr(SqString s,int i,int j)//求子串
{
SqString str;
int k;
str.length=0;
if(i<=0||i>s.length||j<0||i+j-1>s.length)
return str;
for(k=i-1;k<i+j-1;k++)
str.ch[k-i+1]=s.ch[k];
str.length=j;
return str;
}

SqString InsStr(SqString s1,int i,SqString s2) //插入
{
int j;
SqString str;
str.length=0;
if(i<=0||i>s1.length+1)
return str;
for(j=0;j<i-1;j++)
str.ch[j]=s1.ch[j];
for(j=0;j<s2.length;j++)
str.ch[i+j-1]=s2.ch[j];
for(j=i-1;j<s1.length;j++)
str.ch[s2.length+j]=s1.ch[j];
str.length=s1.length+s2.length;
return str;
}

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;

for(k=0;k<i-1;k++)
str.ch[k]=s.ch[k];

for(k=i+j-1;k<s.length;k++)
str.ch[k-j]=s.ch[k];

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(i<=0||i>s.length||i+j-1>s.length)
return str;

for(k=0;k<i-1;k++)
str.ch[k]=s.ch[k];

for(k=0;k<t.length;k++)
str.ch[i+k-1]=t.ch[k];

for(k=i+j-1;k<s.length;k++)
str.ch[t.length+k-j]=s.ch[k];
str.length=s.length-j+t.length;
return str;
}

void DispStr(SqString s) //输出串所有元素
{
int i;
if(s.length>0){
for(i=0;i<s.length;i++)
printf("%c",s.ch[i]);
printf("\n");
}
}

int IsEmpty(SqString s) //判断串是否为空
{
if(s.length>0)
return 0; //不为空
else
return 1; //为空
}

int main(void)
{
void StrAssign(SqString &s,char t[]);//串赋值
void StrCopy(SqString &s,SqString t);//串复制
int StrEqual(SqString s,SqString t);//判断串相等
int StrLength(SqString s);//计算串长度
SqString Concat(SqString s,SqString t);//串连接
SqString SubStr(SqString s,int i,int j);//求子串
SqString InsStr(SqString s1,int i,SqString s2);//插入
SqString DelStr(SqString s,int i,int j);//删除
SqString RepStr(SqString s,int i,int j,SqString t);//替换
void DispStr(SqString s);//输出串所有元素
int IsEmpty(SqString s);//判断串是否为空

char ch1[]="abcdefghijklmn",ch2[]="xyz",ch3[]="hijk";
SqString s,s1,s2,s3,s4,s5,s6,t,t1,t2;
int longth,same,kong;
StrAssign(s,ch1); //建立串s="abcdefghijklmn"
StrAssign(s1,ch2); //建立串s1="xyz"
StrAssign(t,ch3); //建立串t＝"hijk"

StrCopy(t1,t); //将串t复制给t1
printf("串t1: ");
DispStr(t1);
longth=StrLength(t1); //求串t1的长度
printf("串t1的长度为：%d\n",longth);

printf("串 s: ");
DispStr(s);
s2=InsStr(s,9,s1); //将串s1插入串s的第9个位置，得串s2
printf("串s2：");
DispStr(s2); //输出串s2

s3=DelStr(s,2,5); //删除s第2个字符开始的5个字符而产生串s3，并输出s3
printf("串s3：");
DispStr(s3); //输出串s3

s4=RepStr(s,2,5,s1); //用串s1替换串s中从第2个字符起连续5个字符得到新串s4
printf("串s4：");
DispStr(s4); //输出串s4

s5=SubStr(s,2,10); //提取串s中第2个字符开始的10个字符而产生串s5
printf("串s5：");
DispStr(s5); //输出串s5

s6=Concat(s1,t); //连接串s1和t而产生串s6
printf("串s6：");
DispStr(s6); //输出串s6

same=StrEqual(s1,s5); //判断s1、s5是否相等
if(same==1)
printf("串s1、s5相等！");
else
printf("串s1、s5不相等！");

kong=IsEmpty(s3); //判断s3是否为空
if(kong==1)
printf("\n串s3为空！");
else
printf("\n串s3不为空！\n");

}