串基本操作的演示.docx
《串基本操作的演示.docx》由会员分享，可在线阅读，更多相关《串基本操作的演示.docx（31页珍藏版）》请在冰点文库上搜索。
串基本操作的演示
信息科学与技术学院
《数据结构》课程设计报告
题目名称：
串的基本操作演示
专业班级：
学生姓名：
学生学号：
指导教师：
完成日期：
一、需求分析
【问题描述】
如果语言没有把串作为一个预先定义好的基本类型对待,又需要用该语言写一个涉及串操作的软件系统时,用户必须自己实现串类型。
试实现串类型,并写一个串的基本操作的演示系统。
【基本要求】
在教科书4.2.2节用堆分配存储表示实现HString串类型的最小操作子集的基础上,实现串抽象数据类型的其余基本操作（不使用C语言本身提供的串函数）。
参数合法性检查必须严格。
利用基本操作函数构造以下系统:
它是一个命令解释程序,循环往复地处理用户键入的每一条命令,直至终止程序的命令为止。
命令定义如下:
（1）赋值。
格式:
A <串标识> <回车>
用<串标识>所表示的串的值建立新串,并显示新串的内部名和串值。
例:
A ‘Hi!
’
（2）判相等。
格式:
E <串标识1> <串标识2> <回车> 若两串相等,则显示"EQUAL",否则显示"UNEQUAL"。
（3）联接。
格式:
C <串标识1> <串标识2> <回车>
将两串拼接产生结果串,它的内部名和串值都显示出来。
（4）求长度。
格式:
L〈串标识> <回车>
显示串的长度。
（5）求子串。
格式:
S <串标识> +<数1>+<数2><回车>
如果参数合法,则显示子串的内部名和串值。
<数>不带正负号。
（6）子串定位。
格式:
I <串标识1> <串标识2> <回车>
显示第二个串在第一个串中首次出现时的起始位置。
（7）串替换。
格式:
R <串标识1> <串标识2> <串标识3> <回车>
将第一个串中所有出现的第二个串用第三个串替换,显示结果串的内部名和串值,原串不变。
（8）显示。
格式:
P <回车>
显示所有在系统中被保持的串的内部名和串值的对照表。
（9）删除。
格式:
D <内部名> <回车>
删除该内部名对应的串,即赋值的逆操作。
（10）退出。
格式:
Q <回车>
结束程序的运行。
在上述命令中,如果一个自变量是串,则应首先建立它。
基本操作函数的结果（即函数值）如果是一个串,则应在尚未分配的区域内新辟空间存放。
【测试数据】
自定。
但要包括以下几组:
（1）E ‘’ ‘’<回车>,应显示"EQUAL"。
（2）E ‘abc’ ‘abcd’<回车>,应显示"UNEQUAL"。
（3）C ‘ ‘ ‘ ‘ <回车>,应显示"。
（4）I ‘a’ ‘’ <回车>,应报告:
参数非法。
（5）R ‘aaa’ ‘aa’ ‘b’<回车>,应显示'ba’
（6）R ‘aaabc’ ‘a’ ‘aab’<回车>,应显示’aabaabaabbc’。
（7）R ‘Faaaaaaaa’ ‘aaaa’ ‘ab’,<
回车>,应显示’Fabab’。
二、概要设计
实现串的抽象数据类型和实现其基本操作，程序中将涉及下列抽象数据类型：
1．定义串的基本主结构
ADTString{
数据对象：
D={ai|ai∈charcaterset,i=1,2,…,n,n>=0}
数据关系：
R1={|ai-1,ai∈D,i=1,2,…,n}
基本操作：
compare（hstrings,hstringt）
初始条件：
S和T是已存在的Hstring类型。
操作结果：
比较其值，显示结果“UNEQUAL”或“EQUAL”。
length（hstrings）
初始条件：
S是已存在的Hstring类型。
操作结果：
返回该串的长度。
concat（hstring&t,hstrings1,hstrings2）
初始条件：
S1和S2是已存在的Hstring类型。
操作结果：
由S1和S2联接成新串。
index（hstrings,hstringt,intpos）
初始条件：
S和T是已存在的Hstring类型。
操作结果：
显示第二个串在第一个串中首次出现的起始位置。
replace（hstring&s,hstringt,hstringv）
初始条件：
M、t和v是已存在的Hstring类型。
操作结果：
将第一个串中所有出现的第二个串用第三个串替换，显示结果串的内部名和串值，原串不变。
sub（hstring&sub,hstrings,intpos,intlen）
初始条件：
S是已存在的Hstring类型。
操作结果：
如果参数合法，则显示子串的内部名和串值。
display（HStringS）
初始条件：
S是已存在的Hstring类型。
操作结果：
显示串S的内部名和串值。
copy（hstring&t,hstrings）
初始条件：
S是已存在的Hstring类型。
操作结果：
由串s复制得串t
getin（intn）
初始条件：
处理命令串S1,
操作结果：
把串值存入串头表中
}ADTString
三、详细设计
1、自定义数据类型
typedefstructhstring{
char*ch;
intlength;
}hstring;
hstringheadlist[100];//串头数组
2、基本操作函数
1、赋值
voidstrassign（）{
charc;
inti;
chara[20];
while（（c=getchar（））!
='\n'）{
if（c=='\''）{
i=0;
while（（c=getchar（））!
='\''）
a[i++]=c;
headlist[curnum].ch=（char*）malloc（（i+1）*sizeof（char））;
headlist[curnum].length=i;
for（i=0;iheadlist[curnum].ch[i]=a[i];
curnum++;
}
}
printf（"内部名：
%d串值:
",curnum-1）;
for（i=0;i<=headlist[curnum-1].length-1;i++）
printf（"%c",headlist[curnum-1].ch[i]）;
printf（"\n"）;
}
2比较
voidcompare（）{
charc;
inti,m,n,j=0;
while（（c=getchar（））!
='\n'）{
if（c>=48&&c<=57）{
i=0;
b[i++]=c;
while（（c=getchar（））>=48&&c<=57）//还是数字
b[i++]=c;
b[i]='\0';
s[j]=atoi（b）;
j++;
}
if（c=='\''）{
i=0;
while（（c=getchar（））!
='\''）
a[i++]=c;
headlist[curnum].ch=（char*）malloc（（i+1）*sizeof（char））;
headlist[curnum].length=i;
for（i=0;iheadlist[curnum].ch[i]=a[i];
s[j++]=curnum++;
}
}
if（s[0]>=curnum||s[1]>=curnum）
printf（"参数不合法\n"）;
else{
j=strcompare（headlist[s[0]],headlist[s[1]]）;
if（j==0）printf（"EQUAL\n"）;
elseprintf（"UNEQUAL\n"）;
}
}
3、求长
voidlength（）{
charc;
inti,m,n,j=0;
while（（c=getchar（））!
='\n'）{
if（c>=48&&c<=57）{
i=0;
b[i++]=c;
while（（c=getchar（））>=48&&c<=57）//还是数字
b[i++]=c;
b[i]='\0';
s[j]=atoi（b）;
j++;
}
if（c=='\''）{
i=0;
while（（c=getchar（））!
='\''）
a[i++]=c;
headlist[curnum].ch=（char*）malloc（（i+1）*sizeof（char））;
headlist[curnum].length=i;
for（i=0;iheadlist[curnum].ch[i]=a[i];
s[j]=curnum++;
}
}
if（s[0]>=curnum）{printf（"参数不合法\n"）;return;}
printf（"%d\n",headlist[s[0]].length）;
}
4、连接
voidconcat（）{
charc;
inti,m,n,j=0;
while（（c=getchar（））!
='\n'）{
if（c>=48&&c<=57）{
i=0;
b[i++]=c;
while（（c=getchar（））>=48&&c<=57）//还是数字
b[i++]=c;
b[i]='\0';
s[j]=atoi（b）;
j++;
}
if（c=='\''）{
i=0;
while（（c=getchar（））!
='\''）
a[i++]=c;
headlist[curnum].ch=（char*）malloc（（i+1）*sizeof（char））;
headlist[curnum].length=i;
for（i=0;iheadlist[curnum].ch[i]=a[i];
s[j++]=curnum++;
}
}
if（s[0]>=curnum||s[1]>=curnum）
printf（"参数不合法\n"）;
else{
printf（"连接后串内部名:
%d串值:
",curnum）;
strconcat（headlist[curnum++],headlist[s[0]],headlist[s[1]]）;
}
}
5、子串定位
voidindex（）{
charc;
inti,m,n,j=0;
while（（c=getchar（））!
='\n'）{
if（c>=48&&c<=57）{
i=0;
b[i++]=c;
while（（c=getchar（））>=48&&c<=57）//还是数字
b[i++]=c;
b[i]='\0';
s[j]=atoi（b）;
j++;
}
if（c=='\''）{
i=0;
while（（c=getchar（））!
='\''）
a[i++]=c;
headlist[curnum].ch=（char*）malloc（（i+1）*sizeof（char））;
headlist[curnum].length=i;
for（i=0;iheadlist[curnum].ch[i]=a[i];
s[j++]=curnum++;
}
}
if（s[0]>=curnum||s[1]>=curnum）
printf（"参数不合法\n"）;
else{
printf（"%d\n",strindex（headlist[s[0]],headlist[s[1]],1））;
}
}
6、显示
voiddisplay（）{
inti,j;
charc;
while（（c=getchar（））!
='\n'）{;}
for（i=0;iprintf（"\n内部名%d",i）;
for（j=0;jprintf（"%c",headlist[i].ch[j]）;
}
}
7、删除
voidDelete（）{
charc;
inti,m,n,j=0;
while（（c=getchar（））!
='\n'）{
if（c>=48&&c<=57）{
i=0;
b[i++]=c;
while（（c=getchar（））>=48&&c<=57）//还是数字
b[i++]=c;
b[i]='\0';
s[j]=atoi（b）;
j++;
}
}
if（s[0]>=curnum）printf（"参数不合法\n"）;
elseclearstring（headlist[s[0]]）;
}
8求子串
voidsub（）{
charc;
inti,m,n,j=0;
while（（c=getchar（））!
='\n'）{
if（c>=48&&c<=57）{
i=0;
b[i++]=c;
while（（c=getchar（））>=48&&c<=57）//还是数字
b[i++]=c;
b[i]='\0';
s[j]=atoi（b）;
j++;
}
if（c=='\''）{
i=0;
while（（c=getchar（））!
='\''）
a[i++]=c;
headlist[curnum].ch=（char*）malloc（（i+1）*sizeof（char））;
headlist[curnum].length=i;
for（i=0;iheadlist[curnum].ch[i]=a[i];
s[j++]=curnum++;
}
}
if（s[0]>=curnum）{printf（"参数不合法\n"）;return;}
j=substring（headlist[curnum],headlist[s[0]],s[1],s[2]）;
if（j==1）{
printf（"子串内部名:
%d",curnum）;
for（i=0;iprintf（"%c",headlist[curnum].ch[i]）;
curnum++;
}
}
9、替换
voidreplace（）{
charc;
inti;
chara[20];
while（（c=getchar（））!
='\n'）{
if（c=='\''）{
i=0;
while（（c=getchar（））!
='\''）
a[i++]=c;
headlist[curnum].ch=（char*）malloc（（i+1）*sizeof（char））;
headlist[curnum].length=i;
for（i=0;iheadlist[curnum].ch[i]=a[i];
curnum++;
}
}
strcopy（headlist[curnum],headlist[curnum-3]）;
strreplace（headlist[curnum-1],headlist[curnum-3],headlist[curnum-2]）;
for（i=0;iprintf（"%C",headlist[curnum-1].ch[i]）;
printf（"\n"）;
}
3、主函数
voidmain（）{
charc;
printf（"**************************************************************\n"）;
printf（"A:
赋值E：
判相等C：
联接L：
求长度\nS：
求子串I：
子串定位R：
串替换P:
显示\nD：
删除Q：
退出\n"）;
printf（"**************************************************************\n"）;
printf（"请输入命令：
\n"）;
while（（c=getchar（））!
='Q'）{
switch（c）{
case'E':
compare（）;printf（"串数：
%d\n",curnum）;
break;
case'A':
strassign（）;
printf（"串数：
%d\n",curnum）;break;
case'L':
length（）;
printf（"串数：
%d\n",curnum）;break;
case'C':
concat（）;
printf（"\n串数：
%d\n",curnum）;break;
case'I':
index（）;
printf（"\n串数：
%d\n",curnum）;break;
case'P':
display（）;printf（"\n"）;
break;
case'D':
Delete（）;
break;
case'S':
sub（）;
break;
case'R':
replace（）;
break;
}
}
}
四、调试分析
五、用户手册
1.本程序的运行环境为DOS操作系统，执行文件为：
数据结构课程设计.exe.
2.进入程序后即会显示可以使用的命令和命令用途和对应命令的语法格式的列表，用户可以根据命令列表输入正确的命令。
如果输入正确就会显示相应的结果，接着可以输入下一条命令。
如果输入错误，会显示相应的错误的原因并提示重新输入命令。
3.命令是以回车为结束的标志。
4.本程序只能输入字符串，且字符串支持空格符，不过字符串必须用双单引号括住。
所以Delete命令需要输入的数字也必须用双单引号括住。
但命令Substring并不需要如此，在提示“请输入子串的开始位置:
”和“请输入子串的结束中位置:
”直接输入数字即可。
5.命令Subsring在输出正确结果后会接着输出“此命令不存在！
请重新输入！
”此提示，此问题一直都没有解决，也是该程序的缺陷，但是结果是正确的。
6.若要退出程序，请键入命令：
Q。
六、测试结果
（1）E‘’‘’
命令输出的结果为:
EQUAL
（2）E‘abc’‘abcd’
命令输出的结果为:
UNEQUAL
（3）I‘a’‘’
语法格式错误！
请重新输入！
（4）R‘aaa’‘aa’’b’
命令输出的结果为：
ba
（5）R‘aaabc’’a’’aab’
命令输出的结果为:
aabaabaabbc
（6）R‘aaaaaaaa’‘aaaa’‘ab’
命令输出的结果为:
abab
（7）A‘string’
命令输出的结果为:
新赋值的字符串的内部名为:
4，串值为:
string
七、实验中出现的问题、解决方法和心得体会
这个实验是对串的操作的时间，实现串操作的基本函数，在接受命令的输入格式方面，试了很多种方法。
开始时尝试过用getchar（）函数来接收命令，并根据接受到的指令进行操作。
在调试程序的过程中，遇到一些结果不正确或超出范围的情况，又要重新返回相应的函数进行检查和修改补充，才能使程序更加健壮和完整，才能做出一个更加实用的软件
八、附录
源程序
#include
#include
#include
#include
typedefstructhstring{
char*ch;
intlength;
}hstring;
hstringheadlist[100];
intcurnum=0;//系统中现有的串的数目
ints[3];//命令的串参数的内部名（最多3）
chara[20];
charb[5];
intstrcompare（hstrings,hstringt）{
//若s>t,则返回值>0;若s=t,则返回值=0；若sinti;
for（i=0;iif（s.ch[i]!
=t.ch[i]）returns.ch[i]-t.ch[i];
returns.length-t.length;
}
voidclearstring（hstring&s）{
//将s清为空串
if（s.ch）{
free（s.ch）;
s.ch=0;
}
s.length=0;
}
voidstrconcat（hstring&t,hstrings1,hstrings2）{
//用t返回由s1和s2联接而成的新串
inti,j;
if（t.ch）free（t.ch）;
if（!
（t.ch=（char*）malloc（（s1.length+s2.length+1）*sizeof（char））））{
printf（"overflow\n"）;return;}
for（i=0;i<=s1.length-1;i++）
t.ch[i]=s1.ch[i];
t.length=s1.length+s2.length;
for（i=s1.length,j=0;i<=t.length-1;i++,j++）
t.ch[i]=s2.ch[j];
for（i=0;iprintf（"%c",t.ch[i]）;
}
intsubstring（hstring&sub,hstrings,intpos,intlen）{
//用sub返回串s的第
升级会员 