数据结构实验指导书
实验四 串
一、实验目的
通过训练，加深理解并把握串的基本运算的特点。
二、链接串设计
本题目中的串编辑要求对串实现以下两种功能： ⑴插入：把一个字符串插入到给定串的指定位置；
⑵删除：将串中某指定位置开始的若干字符从串中删除；
【实现提示】
⑴ 数据结构
① 结点结构：一个结点由DATA和LINK两个字段组成，如下所示：
DATA 在DATA字段中存放一个字符
② 字符串结构：用一个单循环链表表示一个字符串，如，T=‘ABCD’串可以由下面的单链循环表来表示： A Ｂ Ｃ Ｄ T
T指向循环链表的表尾。
③插入或置换子串的结构：用一个单链表表示要插入的子串，tp为头指阵，bn为尾指针，如：
1
LINK １ ２ ３ 数据结构实验指导书
tp bn
⑵算法基本思想：算法开始时给出一个空串，用户可以在此基础上进行编辑。
a）插入
·输入插入起始位置； ·构造插入子串；
·实现插入 ； ·打印输出插入后的子串。 b) 删除
·输出删除起始位置和删除长度；.实现删除； ·打印输出删除后的字符串。
c）编辑
结束串编辑，终止编辑过程。
三、顺序串的常用操作
1. 根据以下参考程序，完成未实现的方法； 2. 用C++ 标准库中的string类，完成同样的功能。
【参考程序】
#include #include using namespace std;//———————串————————
class String1
{
public:
String1(){}; ~String1(){};
void Insert(char *s2,int pos); //插入数据 void Delete(int pos,int num); //删除数据 void Creat(); //生成新字符串函数
2
数据结构实验指导书
void Display(); //输出结果 private:
char *str; //数据内容 int size; //长度
};
//——————生成新字符串函数————————
void String1:: Creat()
{
char *s=new char[20];
//char *s=\"follow me sunshine\"; cin>>s;
size=strlen(s); //测算长度 str=new char[size]; //新建临时str if(str==0)
cout<<\"没有申请到空间！\";
strcpy(str,s); //把s数据内容复制给str
}
//————————输出——————————
void String1::Display()
{
int i;
for(i=0;icout<cout<}//——插入运算:在串对象s的pos位置后插入一个串t—— void String1::Insert(string t,int pos)
{
3
数据结构实验指导书
char *x=str;
int size1=strlen(s2); if(pos<0||pos>size)
cout<<\"\\n pos 位置错误\"; else
{ //计算新的串长
//strcpy(x,str); //x暂存主串原内容 //delete []str; //释放原先存储空间 //str=new char[size0+1]; //重新分配存储空间
//恢复主串内容
for (int i=size-1; i>=pos; i--)
x[i+size1]=x[i]; //字符逐个向后移，跳过s.size个
x[pos+j]=s2[j]; // str[j+pos]=str[j]; //pos++;}
//新的串长
size=size1+size; str=x;//strcpy(str,x); // str[size]= '\\0'; }
}
for(int j=0; j//新的串结束标志//————删除:删除串中的一个子串——————
void String1:: Delete(int pos,int num)
{
pos--;
if(pos<0||pos>=size) cout<<\"\\n 位置错误!\"; else
{ if(pos+num>size) size=pos; //删除长度超出主串，截尾
4
数据结构实验指导书
else { for (int i=pos+num;istr[i-num]=str[i]; //字符逐个前移，跳过num个size=size-num; //设置删除后的新串长
}
str[size]= '\\0'; }
}
//————————主函数—————————
int main(int argc, char* argv[])
{
int pos,num,k; String1 s1,s,t; char s2[20];
do{ cout<<\"\\n\\n 1.生成字符串\" ; cout<<\"\\n\\n 2.插入子串s1\"; cout<<\"\\n\\n 3.删除子串\"; cout<<\"\\n\\n 4.结束程序\";
cout<<\"\\n****************************** \"; cout<<\"\\n 请输入你的选择(1,2,3,4)\"; cin>>k; switch(k){
case 1:{cout<<\"请输入一个字符串：\"; s.Creat();
cout<<\"字符串为： \";
s.Display();
}break;
5
数据结构实验指导书
case 2:{
cout<<\"请输入子串插入位置pos\"<>pos;cout<<\"请输入要插入的子串: \";
cin>>s2; // s1.Creat();
s.Insert(s2,pos);
cout<<\"插入后的字符串为： \";
s.Display(); }break; case 3:{
cout<<\"请输入要删除子串的开始位置pos及子串长度num\"<cin>>pos>>num; s.Delete(pos,num);cout<<\"删除后的字符串为： \"; s.Display(); }break; default:break
}
cout<<\"\\n--------------------------------- \"; }while(k>=1&&k<4); cout<<\"\\n 再见!\"; cout<<\"\\n 按任意键，返回。\"; return 0;}
6
数据结构实验指导书
四、实验结果
1. 输入一个字符串：
2、插入子串：
7
数据结构实验指导书
3、删除子串：
4、结束程序
8
数据结构实验指导书
五、总结
（软件设计与实现过程种的经验与体会，进一步的改进设想，可再加入哪些部分？哪些部分可删除？哪些部分可合并？哪些可降低复杂度？怎样设计能提高其可复用性？多思考，多总结，才能不断提高程序设计能力。）
答:
人们用计算机做各种各样的文档，如工作计划、法规、工
作总结、书信、小说、论文等，还经常会对词汇或短语进行修改、插入、删
除等操作。
经常会在网上搜索和查找自己所需的信息，当输入关键词汇后网站能够很快地提供大量相关信息，这个过程也是字符串的查找匹配过程。 因此，在计算机上处理的非数值对象基本上是字符串数据。
而，当今世界人们几乎离不开网络，人们常在网上搜索和查找自
己所需要的信息。网络的自动搜索过程，就用到了字符串匹配技术。串的
模式匹配算法，实质上仅是串的精确搜索和查找。
Ps：网站搜索技术远不止这些，有些技术还在研究探索之中。
9
