数据结构5串 (1)

实验日期2010.5.10 教师签字成绩实验报告【实验名称】第四章串的基本操作及应用【实验目的】1、熟悉将算法转换成程序代码的过程。

2、了解串的逻辑结构特性，熟练掌握串顺序存储结构的C 语言描述方法。

3、熟练掌握串的基本操作：求长度、串的连接、插入、删除等，掌握串的存取特性。

【实验原理】1.串可以可以有三种存储方式，分别为顺序存储、堆分配存储、链式存储，串的基本操作在这三种存储方式下操作。

2.串的模式匹配KMP算法在每一趟匹配过程中出现字符不等时，不需回溯指针，而是利用已经得到的部分匹配结果的结果将模式向右滑动尽可能远的一段距离，继续进行比较。

【实验内容】1.串的顺序存储表示及基本操作（插入、删除、求串长、合并连接串、求子串、串比较等）#include<stdio.h>#include<iostream.h>#include<malloc.h>#include<string.h>#define SIZE 20struct HString{char ch[SIZE];int length;};void StrInsert(HString &s,int pos,HString t){int i,j;if(pos<1||pos>s.length+1)cout<<"ERROR!";if(t.length){for(i=s.length-1;i>=pos-1;--i)s.ch[i+t.length]=s.ch[i];for(j=0;j<=t.length-1;j++)s.ch[pos-1+j]=t.ch[j];s.length+=t.length;}}void StrDelete(HString &s,int pos,int len){int i;int v=pos-1;if(pos<1||pos>s.length||len<0||len>s.length-pos+1)cout<<"ERROR!";for(i=pos+len-1;i<=s.length-1;i++)s.ch[v++]=s.ch[i];s.length-=len;}void StrAssign(HString &t,char chars[]){int i;char *c;for(i=0,c=chars;*c;++i,++c);if(!i){t.length=0;}else{for(int j=0;j<i;j++)t.ch[j]=chars[j];t.length=i;}}int StrLen(HString &s){return s.length;}int StrCompare(HString &s,HString t){for(int i=0;i<s.length&&i<t.length;i++){if(s.ch[i]!=t.ch[i])return (int)(t.ch[i]-s.ch[i]);}return s.length-t.length;}void Concat(HString &t,HString s1,HString s2){int i=s1.length+s2.length;for(i=0;i<s1.length;i++)t.ch[i]=s1.ch[i];t.length=s1.length+s2.length;for(i=s1.length;i<t.length;i++)t.ch[i]=s2.ch[i-s1.length];}int SubString(HString &sub,HString s,int pos,int len) {if(pos<1||pos>s.length||len<0||len>s.length-pos+1) {cout<<"ERROR!"<<endl;return 0;}if(!len){sub.length=0;}else{int i=len;for(i=0;i<len;i++)sub.ch[i]=s.ch[pos+i-1];sub.length=len;}}void Display(HString &t){for(int i=0;i<=t.length-1;i++)cout<<t.ch[i];cout<<endl;}void main(){int i;char s[20];do{cout<<"选择您要进行的串的基本操作:"<<endl;cout<<"1.插入"<<endl<<"2.删除"<<endl<<"3.串连结"<<endl<<"4.取子串"<<endl<<"5.串比较"<<endl<<"6.求串长"<<endl<<"7.结束"<<endl;cin>>i;switch(i){case 1:{HString s,t;int pos;cout<<"请输入串s:";cin>>s.ch;StrAssign(s,s.ch);cout<<endl;cout<<"请输入要插入的串t:";cin>>t.ch;StrAssign(t,t.ch);cout<<endl;cout<<"请输入你所要插入的位置:";cin>>pos;StrInsert(s,pos,t);cout<<"插入之后串变为:";Display(s);break;}case 2:{HString s;int pos,len;cout<<"请输入串s:";cin>>s.ch;StrAssign(s,s.ch);cout<<"请输入你所要删除串的首位置为:";cin>>pos;cout<<"请输入你需要删除的串的长度:";cin>>len;StrDelete(s,pos,len);cout<<"删除之后串变为:";Display(s);break;}case 3:{HString s1,s2,t;cout<<"请输入串s1:";cin>>s1.ch;StrAssign(s1,s1.ch);cout<<"请输入串s2:";cin>>s2.ch;StrAssign(s2,s2.ch);Concat(t,s1,s2);cout<<"s1与s2合并后的串为:";Display(t);break;}case 4:{HString sub,s;int pos,len;cout<<"请输入主串s:";cin>>s.ch;StrAssign(s,s.ch);cout<<"请输入所取原串的起始位置pos:";cin>>pos;cout<<"请输入子串的长度len:";cin>>len;SubString(sub,s,pos,len);cout<<"取出的子串为:";Display(sub);break;}case 5:{HString s,t;int value;cout<<"请输入串s:";cin>>s.ch;StrAssign(s,s.ch);cout<<"请输入串t:";cin>>t.ch;StrAssign(t,t.ch);value=StrCompare(s,t);if(value>0) cout<<"串s大于串t"<<endl;else if(value==0) cout<<"串s等于串t"<<endl;else cout<<"串s小于串t"<<endl;cout<<endl;break;}case 6:HString s;char *chars;int val;cout<<"请输入串s:";cin>>s.ch;StrAssign(s,s.ch);val=StrLen(s);cout<<"串的长度为:"<<val<<endl;break;case 7:cout<<"操作结束!"<<endl;break;default:cout<<"输入错误!请重新输入!"<<endl;break;}}while(i!=7);}2.串的堆分配存储表示及基本操作（插入、删除、求串长、合并连接串、求子串、串比较等）#include<stdio.h>#include<iostream.h>#include<malloc.h>#include<string.h>struct HString{char *ch;int length;};void StrInsert(HString &s,int pos,HString t){int i,j;if(pos<1||pos>s.length+1)cout<<"ERROR!";if(t.length){s.ch=(char*)realloc(s.ch,(s.length+t.length)*sizeof(char));for(i=s.length-1;i>=pos-1;--i)s.ch[i+t.length]=s.ch[i];for(j=0;j<=t.length-1;j++)s.ch[pos-1+j]=t.ch[j];s.length+=t.length;}}void StrDelete(HString &s,int pos,int len){int i;int v=pos-1;if(pos<1||pos>s.length||len<0||len>s.length-pos+1)cout<<"ERROR!";for(i=pos+len-1;i<=s.length-1;i++)s.ch[v++]=s.ch[i];s.length-=len;}void StrAssign(HString &t,char *chars){int i;char *c;for(i=0,c=chars;*c;++i,++c);if(!i){t.ch=NULL;t.length=0;}else{t.ch=(char *)malloc(i*sizeof(char));for(int j=0;j<i;j++)t.ch[j]=chars[j];t.length=i;}}int StrLen(HString &s){return s.length;}int StrCompare(HString &s,HString t){for(int i=0;i<s.length&&i<t.length;i++){if(s.ch[i]!=t.ch[i])return (int)(t.ch[i]-s.ch[i]);}return s.length-t.length;}void Concat(HString &t,HString s1,HString s2){int i=s1.length+s2.length;t.ch=(char *)malloc(i*sizeof(char));for(i=0;i<s1.length;i++)t.ch[i]=s1.ch[i];t.length=s1.length+s2.length;for(i=s1.length;i<t.length;i++)t.ch[i]=s2.ch[i-s1.length];}int SubString(HString &sub,HString s,int pos,int len){if(pos<1||pos>s.length||len<0||len>s.length-pos+1){cout<<"ERROR!"<<endl;return 0;}if(!len){sub.ch=NULL;sub.length=0;}else{int i=len;sub.ch=(char *)malloc(i*sizeof(char));for(i=0;i<len;i++)sub.ch[i]=s.ch[pos+i-1];sub.length=len;}}void Display(HString &t){for(int i=0;i<=t.length-1;i++)cout<<t.ch[i];cout<<endl;}void main(){int i;char s[20];cout<<"选择您要进行的串的基本操作:"<<endl;do{cout<<"1.插入"<<endl<<"2.删除"<<endl<<"3.串连结"<<endl<<"4.取子串"<<endl<<"5.串比较"<<endl<<"6.求串长"<<endl<<"7.结束"<<endl;cin>>i;switch(i){case 1:{HString s,t;char a[20],b[20];char *sa,*sb;int pos;cout<<"请输入串s:";cin>>a;sa=a;StrAssign(s,sa);cout<<endl;cout<<"请输入要插入的串t:";cin>>b;sb=b;StrAssign(t,sb);cout<<endl;cout<<"请输入你所要插入的位置:";cin>>pos;StrInsert(s,pos,t);cout<<"插入之后串变为:";Display(s);break;}case 2:{HString s;char str[20];char *chars;int pos,len;cout<<"请输入串s:";cin>>str;chars=str;StrAssign(s,chars);cout<<"请输入你所要删除串的首位置为:";cin>>pos;cout<<endl;cout<<"请输入你需要删除的串的长度:";cin>>len;cout<<endl;StrDelete(s,pos,len);cout<<"删除之后串变为:";Display(s);break;}case 3:{HString s1,s2,t;char a[20],b[20];char *sa,*sb;cout<<"请输入串s1:";cin>>a;sa=a;StrAssign(s1,sa);cout<<"请输入串s2:";cin>>b;sb=b;StrAssign(s2,sb);Concat(t,s1,s2);cout<<"s1与s2合并后:";Display(t);break;}case 4:{HString sub,s;char a[20];char *sa;int pos,len;cout<<"请输入主串s:";cin>>a;sa=a;StrAssign(s,sa);cout<<"请输入所取原串的起始位置pos:";cin>>pos;cout<<"请输入子串的长度len:";cin>>len;SubString(sub,s,pos,len);cout<<"该子串为:";Display(sub);break;}case 5:{HString s,t;int value;char a[20],b[20];char *sa,*sb;cout<<"请输入串s:";cin>>a;sa=a;StrAssign(s,sa);cout<<"请输入串t:";cin>>b;sb=b;StrAssign(t,sb);value=StrCompare(s,t);if(value>0) cout<<"串s大于串t"<<endl;else if(value==0) cout<<"串s等于串t"<<endl;else cout<<"串s小于串t"<<endl;cout<<endl;break;}case 6:HString s;char str[20];char *chars;int val;cout<<"请输入串s:";cin>>str;chars=str;StrAssign(s,chars);val=StrLen(s);cout<<"串的长度为:"<<val<<endl;break;case 7:cout<<"操作结束!"<<endl;break;default:cout<<"输入错误!请重新输入!"<<endl;break;}}while(i!=7);3.KMP算法的C实现#include<iostream.h>#include<malloc.h>#include<string.h>struct HString{char *ch;int length;};void StrAssign(HString &t,char *chars){int i;char *c;for(i=0,c=chars;*c;++i,++c);if(!i){t.ch=NULL;t.length=0;}else{t.ch=(char *)malloc(i*sizeof(char));for(int j=0;j<i;j++)t.ch[j]=chars[j];t.length=i;}}void get_next(HString s,int next[]){int i,j;i=1;j=0;next[1]=0;while(i<s.length){if(j==0||s.ch[i-1]==s.ch[j-1]){i++;j++;next[i]=j;}else j=next[j];}for(i=1;next[i]!='\0';i++)cout<<next[i]<<" ";}int Index(HString s,HString t,int pos){int i=pos;int j=1;int next[20];get_next(t,next);while(i<=s.length&&j<=t.length){if(s.ch[i-1]==t.ch[j-1]||j==0){ ++i;++j;}else{j=next[j];}}if(j>t.length)return i-t.length;else return 0;}void Display(HString t){for(int i=0;i<t.length;i++)cout<<t.ch[i];cout<<endl;}void main(){ HString s,t;int pos,k;char a[20],b[20];char *sa,*sb;cout<<"请输入主串s:";cin>>a;sa=a;StrAssign(s,sa);cout<<"请输入模式串t:";cin>>b;sb=b;StrAssign(t,sb);cout<<"请输入起始位置pos:";cin>>pos;k=Index(s,t,pos);if(k==0)cout<<"匹配失败!"<<endl<<endl;else{cout<<"从第"<<k<<"个位置开始匹配"<<endl;Display(s);for(int i=1;i<k;i++)cout<<" ";Display(t);}}【小结讨论】1. 此程序关键在于位置查询，由于对C语言函数的陌生导致问题变的繁琐，自己的C语言水平有待提高。

第5章串5.1 知识点分析1．串的定义串（String）是由零个或多个任意字符组成的有限序列。

一般记作：s=＂a1 a2 …a i…a n＂。

其中s 是串名，用双引号括起来的字符序列为串值，但引号本身并不属于串的内容。

a i（1<=i<=n）是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号；n为串的长度，表示串中所包含的字符个数。

2．几个术语（1）长度串中字符的个数，称为串的长度。

（2）空串长度为零的字符串称为空串。

（3）空格串由一个或多个连续空格组成的串称为空格串。

（4）串相等两个串相等，是指两个串的长度相等，且每个对应字符都相等。

（5）子串串中任意连续字符组成的子序列称为该串的子串。

（6）主串包含子串的串称为该子串的主串。

（7）模式匹配子串的定位运算又称为串的模式匹配，是一种求子串的第一个字符在主串中序号的运算。

被匹配的主串称为目标串，子串称为模式。

3．串的基本运算（1）求串长：LenStr(s)。

（2）串连接：ConcatStr(s1,s2) 。

（3）求子串：SubStr (s,i,len)。

（4）串比较：EqualStr (s1,s2)。

（5）子串查找：IndexStr (s,t)，找子串t在主串s中首次出现的位置（也称模式匹配）。

（6）串插入：InsStr (s,t,i)。

（7）串删除：DelStr(s,i,len)。

4．串的存储（1）定长顺序存储。

（2）链接存储。

（3）串的堆分配存储。

5.2 典型习题分析【例1】下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储分析：空串是不含任何字符的串，即空串的长度是零。

空格串是由空格组成的串，其长度等于空格的个数。

答案为B。

【例2】两个串相等的充分必要条件是( )。

A．两个串长度相等B．两个串有相同字符C．两个串长度相等且有相同字符D．以上结论均不正确分析：根据串相等定义，两个串是相等是指两个串的长度相等且对应字符都相等，故A、B、C均不正确，答案为D。

数据结构第五章习题1.名词解释（1）串（2）广义表2.判断题〔以下各题，正确的请在前面的括号内打√，错误的打×〕〔〕〔1〕串中不可以包含空白字符。

〔〕〔2〕两个串相等必有串长度相同。

〔〕〔3〕两个串相等那么各位置上的字符不一定对应相同。

〔〕〔4〕串的长度不能为零。

〔〕〔5〕子串是主串中字符构成的有限序列。

〔〕〔6〕串是一种特殊的线性表。

〔〕〔7〕空格串是由一个或多个空格字符组成的串，其长度为1。

〔〕〔8〕广义表最大子表的深度为广义表的深度。

〔〕〔9〕广义表不能递归定义。

〔〕〔10〕广义表的组成元素可以是不同形式的元素。

3.填空题（1）串中字符的个数称为串的____________。

（2）不含有任何字符的串称为____________，它的长度是____________。

（3）串的___________就是把串所包含的字符序列，依次存入连续的存储单元中去。

（4）串的链式存储结构是将存储区域分成一系列大小相同的节点，每个节点有两个域：____________域和____________域。

其中____________域用于存储数据，____________域用于存储下一个节点的指针。

（5）子串的定位操作通常称为串的____________。

（6）串的两种最根本的存储方式是____________和____________。

（7）广义表((a), ((b), c), (((d))))的表头是____________，表尾是____________。

（8）广义表的表尾总是一个____________。

4.选择题（1）串是一种特殊的线性表，其特殊性表达在〔〕。

A．可以顺序存储B．数据元素是一个字符C．可以链接存储D．数据元素可以任意（2）串的长度是〔〕。

A．串中不同字母的个数B．串中不同字符的个数C．串中所含字符的个数且大于零D．串中所含字符的个数（3）空串与空格串〔〕。

A．相同B．不相同C．可能相同D．无法确定（4）求字符串T在字符串S中首次出现的位置的操作为〔〕。

数据结构的串操作数据结构的串操作
⒈概述
⑴串的定义
⑵串的基本操作
⒉串的存储结构
⑴顺序存储结构
⑵链式存储结构
⒊串的基本操作
⑴串的长度
⑵串的比较
⑶串的连接
⑷串的截取
⑸串的插入
⑹串的删除
⑺串的替换
⒋字符串匹配算法
⑴朴素模式匹配算法
⑵ KMP 算法
⑶ Boyer-Moore 算法
⑷ Rabin-Karp 算法
附件：
⒈示例代码
⒉数据集
法律名词及注释：
⒈串：在计算机科学中，串（String）是由零个或多个字符组成的有限序列。

⒉顺序存储结构：串的顺序存储结构是将串的字符按线性次序逐个存储在一组地址连续的存储单元里。

⒊链式存储结构：串的链式存储结构是通过定义一个节点类型来存储串的字符，每个节点包含一个字符和一个指向下一个节点的指针。

⒋朴素模式匹配算法：朴素模式匹配算法是最简单的字符串匹
配算法之一，通过对目标串的每个字符依次与模式串进行比较，直
到找到匹配的位置或遍历完所有字符。

⒌ KMP 算法：KMP 算法是一种高效的字符串匹配算法，通过利
用模式串的前缀和后缀信息，在匹配失败时将模式串移动比朴素算
法更远的位置，减少比较次数。

⒍ Boyer-Moore 算法：Boyer-Moore 算法是一种基于多种规则
的字符串匹配算法，通过从右到左比较模式串和目标串的字符，根
据不匹配字符在模式串中的位置和字符表进行移动，提高匹配效率。

⒎ Rabin-Karp 算法：Rabin-Karp 算法是一种利用哈希函数的
字符串匹配算法，通过计算目标串和模式串的哈希值，并逐个比较，减少比较次数。

数据结构(串)数据结构(串)数据结构中的串（String）是由字符构成的有限序列。

在计算机科学中，串是一种基本的数据结构，被广泛应用于字符串处理、文本搜索、模式匹配等领域。

1. 串的定义和基本操作串可以使用多种方式来定义和表示，常见的方式有：- 定长顺序存储表示：使用数组来存储串，数组的长度和最大串长相等，不足的部分用特定字符填充（通常用空格）。

- 堆分配存储表示：使用堆（动态内存分配区）来存储串，可以根据实际需要动态分配和释放串的存储空间。

- 串的块链存储表示：将串分成多个块，将每个块使用链表进行表示，将各块在一起组成完整的串。

串的基本操作包括：- 串的赋值：将一个串赋值给另一个串。

- 串的连接：将两个串按顺序连接成一个新的串。

- 串的比较：比较两个串的大小关系。

- 串的截取：从一个串中截取出一段子串。

- 串的插入：将一个串插入到另一个串的指定位置。

- 串的删除：删除一个串中指定位置的字符或一段子串。

- 串的替换：将一个串中指定位置的字符或一段子串替换成另一个串。

2. 串的匹配算法串的匹配是指在一个主串中查找一个模式串的过程。

常见的串匹配算法包括：- 朴素匹配算法：也称为暴力匹配算法，是最简单的匹配算法。

它从主串的第一个字符开始，与模式串逐个字符进行比较，若不匹配，则主串向后移动一位，直到找到匹配的子串或主串遍历完。

- KMP算法：即Knuth-Morris-Pratt算法，通过利用模式串自身的信息，减少字符的比较次数。

该算法具有线性时间复杂度，是一种高效的匹配算法。

- Boyer-Moore算法：基于模式串中的字符发生不匹配时的启发式策略，通过跳跃式地移动模式串，减少字符的比较次数，从而提高匹配效率。

3. 串的应用串作为一种基本的数据结构，在实际应用中具有广泛的用途，主要包括以下几个方面：- 字符串处理：串在文本编辑、编译器设计、语法分析、文件操作等方面都有广泛应用。

- 模式匹配：串的匹配算法常被用于字符串搜索、DNA序列分析、信息检索等领域。

一、实验目的1. 理解串的定义、性质和操作；2. 掌握串的基本操作，如串的创建、复制、连接、求子串、求逆序、求长度等；3. 熟练运用串的常用算法，如串的模式匹配算法（如KMP算法）；4. 培养编程能力和算法设计能力。

二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发环境：Visual Studio 2019三、实验内容1. 串的创建与初始化2. 串的复制3. 串的连接4. 串的求子串5. 串的求逆序6. 串的求长度7. 串的模式匹配算法（KMP算法）四、实验步骤1. 串的创建与初始化（1）创建一个串对象；（2）初始化串的长度；（3）初始化串的内容。

2. 串的复制（1）创建一个目标串对象；（2）使用复制构造函数将源串复制到目标串。

3. 串的连接（1）创建一个目标串对象；（2）使用连接函数将源串连接到目标串。

4. 串的求子串（1）创建一个目标串对象；（2）使用求子串函数从源串中提取子串。

5. 串的求逆序（1）创建一个目标串对象；（2）使用逆序函数将源串逆序。

6. 串的求长度（1）获取源串的长度。

7. 串的模式匹配算法（KMP算法）（1）创建一个模式串对象；（2）使用KMP算法在源串中查找模式串。

五、实验结果与分析1. 串的创建与初始化实验结果：成功创建了一个串对象，并初始化了其长度和内容。

2. 串的复制实验结果：成功将源串复制到目标串。

3. 串的连接实验结果：成功将源串连接到目标串。

4. 串的求子串实验结果：成功从源串中提取了子串。

5. 串的求逆序实验结果：成功将源串逆序。

6. 串的求长度实验结果：成功获取了源串的长度。

7. 串的模式匹配算法（KMP算法）实验结果：成功在源串中找到了模式串。

六、实验总结通过本次实验，我对串的定义、性质和操作有了更深入的了解，掌握了串的基本操作和常用算法。

在实验过程中，我遇到了一些问题，如KMP算法的编写和调试，但在老师和同学的指导下，我成功地解决了这些问题。