数据结构——串实践报告
-
成绩：
实
验
报
告
课程名称：
数据结构实践课
实验项目：
定长串存储方法
姓
名：
专
业：
班
级：
学
号：
计算机科学与技术学院
实验教学中心
2017
年
9
月
23
日
哈尔滨理工大学计算机科学与技术学院实验教学中心
实验报告
实验项目名称：
串的定长存储表示方法
一、实践目的：
1.
熟练掌握串的定长顺序存储表示方法。
2.
利用串的基本操作实现相关算法。
二、实践内容：
1.
实现串的定长顺序存储表示的基本操作。并用主程序进行多次验证。
2.
设
s='abcdefghij
k'
、
t='cde'
为两个字符串，
利用定长顺序存储结构的串操
作，判断
t
是否为
s
的子串。如果是，输出子串所在位置（第一个字符）
。
编程实现。
3.
已知三个字符串分别为
s=
’
ababababcaabcbcaaaaaa
< br>’
，
s1=
’
< br>caab
’
, s2=
’
bcb
’
。
利
用
所
学
字
符
串
基
本
运
算
的
函
数
得
到
结
果
串
为
：
s3
=
’
caabcbcaaaaaacaaaaaa
’
。编程实现。
三、实验用设备仪器及材料
计算机
四、实验原理及接线
五、实验操作步骤
//
检验
的主程序
// c1.h (
程序名
)
#include
#include
#include
等
#include
等
#include
或
F6),NULL
#include
#include
哈尔滨理工大学计算机科学与技术学院实验教学中心
实验报告
#include
#include
// #include
//
函数结果状态代码
#define TRUE 1
#define FALSE
0
#define OK 1
#define ERROR
0
#define INFEASIBLE -1
//
#define OVERFLOW -2
因为在
math.
h
中已定义
OVERFLOW
的值为<
/p>
3,
故去掉此行
typedef int Status; // Status
是函数的类型
,
其值是函数结果状态代码，如
OK
等
typedef
int Boolean; // Boolean
是布尔类型
,
其值是
TRUE
或
< br>FALSE
// c4-1.h
串的定长顺序存储表示
#define MAXSTRLEN 30 //
用户可在
255
以内定义最大串长（
1
个字节）
typedef char
SString[MAXSTRLEN+1]; //
0
号单元存放串的长度
//
串采用定长顺序存储结构
(<
/p>
由
c4-1.h
定义
)
的基本操作
(14
个
)
// SString
是数组，故不需引用类
型。此基本操作包括算法
4.2,4.3,4.5
Status StrAssign(SString &T,char
*chars)
{
///
生成一个其值等于
chars
的串
T
int i;
if(strlen(chars)>MAXSTRLEN)
return ERROR;
else
{
T[0]=strlen(chars);
for(i=1; i<=T[0]; i++)
T[i]=*(chars+i-1);
return OK;
}
}
Status StrCopy(SString
T,SString S)
{
///
由串
S
复制得串
T
int i;
for(i=0;
i<=S[0]; i++)
T[i]=S[i];
return OK;
}
Status StrEmpty(SString S)
{
哈尔滨理工大学计算机科学与技术学院实验教学中心
实验报告
///
若
S
为空串
,
则返回
TRUE,
否则返回
FALSE
if(S[0]==0)
return TRUE;
else
return FALSE;
}
int
StrCompare(SString S,SString T)
{
///
初始条件
:
串
S
和
T
存在
///
操作结果
:
若
S>T,
则返回值
>0;
若
S=T,
则返回值
=0;
若
<
br>:
<
br>在主串
S
则返回值
<0
int i;
for(i=1;
i<=S[0]&&i<=T[0]; ++i)
if(S[i]!=T[i])
return S[i]-T[i];
return S[0]-T[0];
}
int StrLength(SString S)
{
///
返回串的元素个数
return S[0];
}
Status ClearString(SString S)
{
///
初始条件
串
S
存在。操作结果
:
将
S
清为空串
S[0]=0;//
令串长为零
return OK;
}
Status Concat(SString &T,SString
S1,SString S2) //
算法
4.2
改
{
//
用
T
返回
S1
和
S
2
联接而成的新串。若未截断，则返回
TRUE
，否则
FALSE
int i;
if(S1[0]+S2[0]<=MAXSTRLEN)
{
//
未截断
for(i=1; i<=S1[0]; i++)
T[i]=S1[i];
for(i=1;
i<=S2[0]; i++)
T[S1[0]+i]=S2[i];
T[0]=S1[0]+S2[0];
return TRUE;
}
哈尔滨理工大学计算机科学与技术学院实验教学中心
实验报告
else
{
//
截断
S2
for(i=1;
i<=S1[0]; i++)
T[i]=S1[i];
for(i=1; i<=MAXSTRLEN-S1[0]; i++)
T[S1[0]+i]=S2[i];
T[0]=MAXSTRLEN;
return FALSE;
}
}
Status SubString(SString &Sub,SString
S,int pos,int len)
{
///
用
Sub
返回串
S
的第
pos
个字符起长度为
len
的子串。算法
4.3
int i;
if(pos<1||pos>S
[0]||len<0||len>S[0]-pos+1)
return ERROR;
for(i=1;
i<=len; i++)
Sub[i]=S[pos+i-1];
Sub[0]=len;
return OK;
}
int
Index(SString S,SString T,int pos)
{
///
返回子串
T
S
中第
pos
个字符之后的位置。若不存在
,
则函数值为
0
。
///
其中
,T
非空
,1≤pos≤StrLength(S)
。算法
4.5
int i,j;
if(1<=pos&&pos<=S[0])
{
i=pos;
j=1;
while(i<=S[0]&&j<=T[0])
if(S[i]==T[j]) //
继续比较后继字符
{
++i;
++j;
}
else //
指针后退重新开始匹配
{
i=i-j+2;
j=1;
}
if(j>T[0])
哈尔滨理工大学计算机科学与技术学院实验教学中心
实验报告
return i-T[0];
else
return 0;
}
else
return 0;
}
Status StrInsert(SString S,int
pos,SString T)
{
//
初始条件
:
串
S
和
T
存在
,1≤pos≤StrLength(S)+1
//
操作结果
:
在串
S
的第
pos
个字符之前插入串<
/p>
T
。完全插入返回
TRUE,
部分插入返回
FALSE
int
i;
if(pos<1||pos>S[0]+1)
return ERROR;
if(S[0]+T[0]<=MAXSTRLEN)
{
///
完全插入
for(i=S[0]; i>=pos; i--)
S[i+T[0]]=S[i];
S ,T <
br>用
for(i=pos;
i
S[i]=T[i-pos+1];
S[0]=S[0]+T[0];
return TRUE;
}
else
{
///
部分插入
for(i=MAXSTRLEN; i<=pos; i--)
S[i]=S[i-T[0]];
for(i=pos;
i
S[i]=T[i-pos+1];
S[0]=MAXSTRLEN;
return FALSE;
}
}
Status StrDelete(SString S,int pos,int
len)
{
//
初始条件
:
串
S
存在
,1≤pos≤StrLength(S)
-len+1
//
操作结果
:
从串
中删除第
pos
个字符起长度为
len
的子串
int i;
if(pos<1||pos>S[0]-len+1||len<0)
return ERROR;
哈尔滨理工大学计算机科学与技术学院实验教学中心
实验报告
for(i=pos+len;
i<=S[0]; i++)
S[i-len]=S[i];
S[0]-=len;
return OK;
}
Status Replace(SString S,SString
T,SString V)
{
//
初始条件
:
串
S,T
和
V
存在
是非空串（此函数与串的存储结构无关）
//
操作结果
:
V
替换主串
S
中出现的所有与
T
相等的不重叠的子串
int i=1; //
从串
S
的第一个字符起查找串
T
if(StrEmpty(T)) //
T
是空串
return ERROR;
do
{
i=Index(S,T,i);
//
结果
i
为从上一个
i
之后找到的子串
T
的位置
if(i) //
串
S
中存在串
T
{
StrDelete(S,i,StrLength(T)); //
删除该串
T
StrInsert(S,i,V); //
在原串
T
的位置插入串
V
i+=StrLength(V); //
在插入的串
V
后面继续查找串
T
}
}
while(i);
return OK;
}
void DestroyString()
{
//
由于
SString
是定长类型
,
无法销毁
}
void
StrPrint(SString T)
{
//
输出字符串
T
。另加
< br>
int i;
for(i=1; i<=T[0]; i++)
printf(
printf(
//
printf(
}
int main()
{