数据结构实验报告-串与模式匹配

【精品】数据结构串实验报告
（仅校内可用）
本次实验是基于数据结构串的相关知识，设计、实现及实验关于串的操作，并要求我们编写综合性实验报告。

1、实验目的是了解串结构及其实现方法，并能够用有限的时间内完成实验。

2、实验要求：
（1）实现关于串的一组基本操作
（2）实现串的模式匹配算法
3、实验的进度：
（1）完成程序的设计，要求建立合理的数据结构，编写部分重要算法，调试程序；
（2）设计一组完整的数据，并完成所设计程序的测试；
（3）对串模式匹配算法和高效率算法的效率、正确性进行测试；
（4）完成实验总结，参加试验验收。

4、实验结果：
（1）建立了串的节点数据结构，并编写相关操作算法，经测试结果显示，程序的实现能做到正确、有效的运行；
（2）完成对串模式匹配算法和高效率算法的测试，匹配算法水平介于暴力及KMP算法之间，效率较高；高效率算法在重复部分采用滑动窗口技术，同时避免了重复移动结点带来的时间开销，效率较高且正确性得到了优化；
（3）完成了实验总结，并得出本次实验的结论：实现串的模式匹配算法和高效率算法能够较好地实现串的基本操作，同时具有较高的效率；
最后，在实验过程中，我收获颇丰，加深了对串结构及实现方法的理解，使我对数据结构有了更全面的认识。

实验日期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语言水平有待提高。

串的模式匹配问题实验总结（用C实现）第一篇：串的模式匹配问题实验总结(用C实现)串的模式匹配问题实验总结1实验题目：实现Index(S,T,pos)函数。

其中，Index(S,T,pos)为串T在串S的第pos个字符后第一次出现的位置。

2实验目的：熟练掌握串模式匹配算法。

3实验方法：分别用朴素模式匹配和KMP快速模式匹配来实现串的模式匹配问题。

具体方法如下：朴素模式匹配：输入两个字符串，主串S和子串T，从S串的第pos个位置开始与T的第一个位置比较，若不同执行i=i-j+2；j=1两个语句；若相同，则执行语句++i;++j;一直比较完毕为止，若S中有与T相同的部分则返回主串（S字符串）和子串（T字符串）相匹配时第一次出现的位置，若没有就返回0。

KMP快速模式匹配：构造函数get_next(char *T,int *next)，求出主串S串中各个字符的next值，然后在Index_KMP(char *S,char *T,int pos)函数中调用get_next(char *T,int *next)函数并调用next值，从S串的第pos 位置开始与T的第一个位置进行比较，若两者相等或j位置的字符next值等于0，则进行语句++i;++j;即一直向下进行。

否则，执行语句j=A[j]；直到比较完毕为止。

若S中有与T相同的部分则返回主串（S字符串）和子串（T字符串）相匹配时第一次出现的位置，若没有就返回04实验过程与结果：（1）、选择1功能“输入主串、子串和匹配起始位置”，输入主串S：asdfghjkl, 输入子串T：gh,输入pos的值为：2。

选择2功能“朴素的模式匹配算法”，输出结果为 5；选择3功能“KMP快速模式匹配算法”，输出结果为 5；选择0功能，退出程序。

截图如下：（2）、选择1功能“输入主串、子串和匹配起始位置”，输入主串S：asdfghjkl, 输入子串T：wp, 输入pos的值为：2。

实验报告实验名称：串实验目的：（1）、熟悉C语言的上机环境，进一步掌握C语言的结构特点；（2）、掌握串的定义及C语言实现；（3）、掌握串的模式匹配及C语言实现；（4）、掌握串的各种基本操作；实验步骤：（1）、建立链串类型（2）、实现匹配过程中需考虑的链表的特征。

实验内容：4.一个字符串中的任意一个子序列，若子序列中各字符值均相同，则成为字符平台。

写一算法，输入任意以字符串S，输出S中长度最大的所有字符平台的起始位置及所含字符。

注意，最大字符平台有可能不止一个。

实验数据记录：（源代码及执行过程）#include<stdio.h>#include<stdlib.h>#define Maxsize 20#define n 100typedef struct Node{int element[Maxsize];int front;int rear;}Queue;int EnterQueue(Queue *Q,int x){if((Q->rear+1)%Maxsize == Q->front){printf("队列已满!\n");return 0;}Q->element[Q->rear] = x;Q->rear = (Q->rear+1)%Maxsize;return 1;}int DeleQueue(Queue *Q,int *x){if(Q->front == Q->rear){printf("队列为空!\n");return 0;}*x = Q->element[Q->front];Q->front = (Q->front+1)%Maxsize;return 1;}int Donull(Queue *Q){while(Q->front != Q->rear){Q->element[Q->front] = 0;Q->front = (Q->front+1)%Maxsize;}Q->front = Q->rear = 0;if(Q->front == Q->rear){return 1;}else{return 0;}}int main(void){char str[n];int i=0,j=1,k=1,ch,p=1,flag=1;Queue *Q;Q = (Queue *)malloc(sizeof(Queue));Q->front = Q->rear = 0;printf("请输入字符串：");gets(str);while('\0' != *(str+i)){ while(*(str+i+1) == *(str+i)){if(flag){p = i;flag = 0;}i++;j++;}if(flag){p = i;}if(j >= k){if(j > k){Donull(Q);k = j;}if(EnterQueue(Q ,j) == 0)break;if(EnterQueue(Q,p+1) == 0)break;if(EnterQueue(Q,*(str+i)) == 0)break;}j=1;i++;flag = 1;} while(Q->front < Q->rear){DeleQueue(Q,&j);DeleQueue(Q,&k);DeleQueue(Q,&ch);printf("%-10d",k);for(i = 0; i < j; i++){printf("%c",ch);}printf("\n");}printf("\n");system("pause");}。

实验三串的模式匹配⼀、实验⽬的1、了解串的基本概念2、掌握串的模式匹配算法的实现⼆、实验预习说明以下概念1、模式匹配：数据结构中字符串的⼀种基本运算，给定⼀个⼦串，要求在某个字符串中找出与该⼦串相同的所有⼦串。

2、BF算法：BF算法，即暴⼒(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将⽬标串S的第⼀个字符与模式串T的第⼀个字符进⾏匹配，若相等，则继续⽐较S的第⼆个字符和 T的第⼆个字符；若不相等，则⽐较S的第⼆个字符和T的第⼀个字符，依次⽐较下去，直到得出最后的匹配结果。

BF算法是⼀种蛮⼒算法。

3、KMP算法：KMP算法是⼀种改进的字符串匹配算法，KMP算法的核⼼是利⽤匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的⽬的。

具体实现就是通过⼀个next()函数实现，函数本⾝包含了模式串的局部匹配信息。

三、实验内容和要求1、阅读并运⾏下⾯程序，根据输⼊写出运⾏结果。

#include<stdio.h>#include<string.h>#define MAXSIZE 100typedef struct{char data[MAXSIZE];int length;}SqString;int strCompare(SqString *s1,SqString *s2); /*串的⽐较*/void show_strCompare();void strSub(SqString *s,int start,int sublen,SqString *sub);/*求⼦串*/void show_subString();int strCompare(SqString *s1,SqString *s2){int i;for(i=0;i<s1->length&&i<s2->length;i++)if(s1->data[i]!=s2->data[i])return s1->data[i]-s2->data[i];return s1->length-s2->length;}void show_strCompare(){SqString s1,s2;int k;printf("\n***show Compare***\n");printf("input string s1:");gets(s1.data);s1.length=strlen(s1.data);printf("input string s2:");gets(s2.data);s2.length=strlen(s2.data);if((k=strCompare(&s1,&s2))==0)printf("s1=s2\n");else if(k<0)printf("s1<s2\n");elseprintf("s1>s2\n");printf("\n***show over***\n");}void strSub(SqString *s,int start,int sublen,SqString *sub){int i;if(start<1||start>s->length||sublen>s->length-start+1){sub->length=0;}for(i=0;i<sublen;i++)sub->data[i]=s->data[start+i-1];sub->length=sublen;}void show_subString(){SqString s,sub;int start,sublen,i;printf("\n***show subString***\n");printf("input string s:");gets(s.data);s.length=strlen(s.data);printf("input start:");scanf("%d",&start);printf("input sublen:");scanf("%d",&sublen);strSub(&s,start,sublen,&sub);if(sub.length==0)printf("ERROR!\n");else{printf("subString is :");for(i=0;i<sublen;i++)printf("%c",sub.data[i]);}printf("\n***show over***\n");}int main(){int n;do {printf("\n---String---\n");printf("1. strCompare\n");printf("2. subString\n");printf("0. EXIT\n");printf("\ninput choice:");scanf("%d",&n);getchar();switch(n){case 1:show_strCompare();break;case 2:show_subString();break;default:n=0;break;}}while(n);return 0;}运⾏程序输⼊：1studentstudents2Computer Data Stuctures104运⾏结果：2、实现串的模式匹配算法。

数据结构串的实验总结《数据结构串的实验总结》整体感受嘛，这数据结构中的串实验就像一场充满挑战与惊喜的旅程。

开始的时候，真觉得有些头疼，就像面对一个错综复杂的迷宫，完全不知道从哪儿入手。

具体收获可真是不少。

首先，我对串的基本概念有了透彻的理解，什么是串，串的长度、空串、空格串等等。

在实现串的操作时，比如串的连接、匹配之类的，那可真是让我费了不少心思。

比如说在实现串的模式匹配算法中的BF算法时，我才清楚需要挨个比较字符，就像在人群中逐个查找一个特定的人一样辛苦但又很有成就感。

还有KMP算法，这个算法刚开始理解简直难上天了，它那复杂的部分匹配值计算和next数组的构建，但是一旦理解了它的精髓，就感觉像发现了一个快捷通道。

原来KMP 算法就是利用已经比较过的信息，避免不必要的比较，就像你走过一遍迷宫，记住了哪些路是死胡同，下次走的时候就可以避开了。

重要发现也得记一笔。

在做串的存储结构实验的时候，我发现顺序存储结构在某些情况下很方便，比如串的长度固定或者不需要频繁插入删除的时候。

而链式存储结构则在灵活处理串的变化方面更有优势，这就像是住在公寓和房车的区别，一个固定但是稳定，一个虽然变动大但是更灵活，可以随时根据需求调整内部布局。

反思一下，自己在做实验的过程中太过于关注实现结果而忽略了算法的时间复杂度和空间复杂度优化。

比如在BF算法中，如果字符串很长，那简单的逐个比较效率是非常低的，当时怎么就没有多想想怎么优化呢，真是太不应该了。

现在想想，如果当时能从一开始就着重关注效率方面的问题，后面可能就不需要花这么多时间返工了。

从这个串的实验中得到的启示就是做事情之前一定要考虑全面。

遇到难题的时候不要害怕，像理解KMP算法一样，多花时间多思考，总能找到解决方案的。

而且在解决问题的过程中，要不断思考有没有更好更高效的方法，不能仅仅满足于把功能实现了就好。

要从各个方面去考量，就像看待一个人的综合素质一样，不仅要看他能不能完成任务，还要看他完成任务的质量和效率。

串-数据结构实验报告串数据结构实验报告一、实验目的本次实验的主要目的是深入理解和掌握串这种数据结构的基本概念、存储方式以及相关的操作算法。

通过实际编程实现串的基本操作，提高对数据结构的理解和编程能力，培养解决实际问题的思维和方法。

二、实验环境本次实验使用的编程语言为C+＋，开发工具为Visual Studio 2019。

三、实验原理（一）串的定义串是由零个或多个字符组成的有限序列。

在本次实验中，我们主要关注的是字符串。

（二）串的存储方式1、顺序存储定长顺序存储：使用固定长度的数组来存储字符串，长度不足时用特定字符填充。

堆分配存储：根据字符串的实际长度动态分配存储空间。

2、链式存储每个节点存储一个字符，并通过指针链接起来。

（三）串的基本操作1、串的创建和初始化2、串的赋值3、串的连接4、串的比较5、求子串6、串的插入和删除四、实验内容及步骤（一）顺序存储方式下串的实现1、定义一个结构体来表示顺序存储的字符串，包含字符数组和字符串的实际长度。

｀｀｀cppstruct SeqString ｛char str;int length;｝；｀｀｀2、实现串的创建和初始化函数｀｀｀cppSeqString createSeqString(const char initStr) ｛int len ＝ strlen(initStr)；SeqString s;sstr ＝ new charlen ＋ 1;strcpy(sstr, initStr)；slength ＝ len;return s;｝｀｀｀3、串的赋值函数｀｀｀cppvoid assignSeqString(SeqString& s, const char newStr) ｛delete sstr;int len ＝ strlen(newStr)；sstr ＝ new charlen ＋ 1;strcpy(sstr, newStr)；slength ＝ len;｝｀｀｀4、串的连接函数｀｀｀cppSeqString concatSeqString(const SeqString& s1, const SeqString& s2) ｛SeqString result;resultlength ＝ s1length ＋ s2length;resultstr ＝ new charresultlength ＋ 1;strcpy(resultstr, s1str)；strcat(resultstr, s2str)；return result;｝｀｀｀5、串的比较函数｀｀｀cppint compareSeqString(const SeqString& s1, const SeqString& s2) ｛return strcmp(s1str, s2str)；｝｀｀｀6、求子串函数｀｀｀cppSeqString subSeqString(const SeqString& s, int start, int len) ｛SeqString sub;sublength ＝ len;substr ＝ new charlen ＋ 1;strncpy(substr, sstr ＋ start, len)；substrlen ＝＇＼0'；return sub;｝｀｀｀7、串的插入函数｀｀｀cppvoid insertSeqString(SeqString& s, int pos, const SeqString& insertStr) ｛int newLength ＝ slength ＋ insertStrlength;char newStr ＝ new charnewLength ＋ 1;strncpy(newStr, sstr, pos)；strcpy(newStr ＋ pos, insertStrstr)；strcpy(newStr ＋ pos ＋ insertStrlength, sstr ＋ pos)；delete sstr;sstr ＝ newStr;slength ＝ newLength;｝｀｀｀8、串的删除函数｀｀｀cppvoid deleteSeqString(SeqString& s, int start, int len) ｛int newLength ＝ slength len;char newStr ＝ new charnewLength ＋ 1;strncpy(newStr, sstr, start)；strcpy(newStr ＋ start, sstr ＋ start ＋ len)；delete sstr;sstr ＝ newStr;slength ＝ newLength;｝｀｀｀（二）链式存储方式下串的实现1、定义一个节点结构体｀｀｀cppstruct LinkNode ｛char data;LinkNode next;LinkNode(char c) ： data(c)， next(NULL) ｛｝｝；｀｀｀2、定义一个链式存储的字符串类｀｀｀cppclass LinkString ｛private:LinkNode head;int length;public:LinkString(const char initStr)；～LinkString(）；void assign(const char newStr)；LinkString concat(const LinkString& other)；int compare(const LinkString& other)；LinkString subString(int start, int len)；void insert(int pos, const LinkString& insertStr)；void deleteSub(int start, int len)；｝；｀｀｀3、实现各个函数｀｀｀cppLinkString:：LinkString(const char initStr) ｛length ＝ strlen(initStr)；head ＝ NULL;LinkNode p ＝ NULL;for （int i ＝ 0; i ＜ length; i+＋）｛LinkNode newNode ＝ new LinkNode(initStri)；if （head ＝＝ NULL) ｛head ＝ newNode;p ＝ head;｝ else ｛p>next ＝ newNode;p ＝ p>next;｝｝｝LinkString:：～LinkString(）｛LinkNode p ＝ head;while （p) ｛LinkNode temp ＝ p;p ＝ p>next;delete temp;｝｝void LinkString:：assign(const char newStr) ｛／／先释放原有的链表LinkNode p ＝ head;while （p) ｛LinkNode temp ＝ p;p ＝ p>next;delete temp;｝length ＝ strlen(newStr)；head ＝ NULL;p ＝ NULL;for （int i ＝ 0; i ＜ length; i+＋）｛LinkNode newNode ＝ new LinkNode(newStri)；if （head ＝＝ NULL) ｛head ＝ newNode;p ＝ head;｝ else ｛p>next ＝ newNode;p ＝ p>next;｝｝｝LinkString LinkString:：concat(const LinkString& other) ｛LinkString result;LinkNode p1 ＝ head;LinkNode p2 ＝ otherhead;LinkNode p ＝ NULL;while （p1) ｛LinkNode newNode ＝ new LinkNode(p1-＞data)；if （resulthead ＝＝ NULL) ｛resulthead ＝ newNode;p ＝ resulthead;｝ else ｛p>next ＝ newNode;p ＝ p>next;｝p1 ＝ p1-＞next;｝while （p2) ｛LinkNode newNode ＝ new LinkNode(p2-＞data)；if （resulthead ＝＝ NULL) ｛resulthead ＝ newNode;p ＝ resulthead;｝ else ｛p>next ＝ newNode;p ＝ p>next;｝p2 ＝ p2-＞next;｝resultlength ＝ length ＋ otherlength;return result;｝int LinkString:：compare(const LinkString& other) ｛LinkNode p1 ＝ head;LinkNode p2 ＝ otherhead;while （p1 ＆＆ p2 ＆＆ p1-＞data ＝＝ p2-＞data) ｛p1 ＝ p1-＞next;p2 ＝ p2-＞next;｝if （p1 ＝＝ NULL ＆＆ p2 ＝＝ NULL) ｛return 0;｝ else if （p1 ＝＝ NULL) ｛return －1;｝ else if （p2 ＝＝ NULL) ｛return 1;｝ else ｛return p1-＞data p2-＞data;｝｝LinkString LinkString:：subString(int start, int len) ｛LinkString sub;LinkNode p ＝ head;for （int i ＝ 0; i ＜ start; i+＋）｛p ＝ p>next;｝for （int i ＝ 0; i ＜ len; i+＋）｛LinkNode newNode ＝ new LinkNode(p>data)；if （subhead ＝＝ NULL) ｛subhead ＝ newNode;｝ else ｛LinkNode temp ＝ subhead;while （temp>next) ｛temp ＝ temp>next;｝temp>next ＝ newNode;｝p ＝ p>next;｝sublength ＝ len;return sub;｝void LinkString:：insert(int pos, const LinkString& insertStr) ｛LinkNode p ＝ head;for （int i ＝ 0; i ＜ pos 1; i+＋）｛p ＝ p>next;｝LinkNode insertHead ＝ insertStrhead;while （insertHead) ｛LinkNode newNode ＝ new LinkNode(insertHead>data)；newNode>next ＝ p>next;p>next ＝ newNode;p ＝ p>next;insertHead ＝ insertHead>next;｝length ＋＝ insertStrlength;｝void LinkString:：deleteSub(int start, int len) ｛LinkNode p ＝ head;for （int i ＝ 0; i ＜ start 1; i+＋）｛p ＝ p>next;｝LinkNode temp ＝ p>next;for （int i ＝ 0; i ＜ len; i+＋）｛LinkNode delNode ＝ temp;temp ＝ temp>next;delete delNode;｝p>next ＝ temp;length ＝ len;｝｀｀｀（三）测试用例1、顺序存储方式的测试｀｀｀cppint main(）｛SeqString s1 ＝ createSeqString(＂Hello"）；SeqString s2 ＝ createSeqString(＂World"）；SeqString s3 ＝ concatSeqString(s1, s2)；std:：cout ＜＜＂连接后的字符串: ＂＜＜ s3str ＜＜ std:：endl; int cmpResult ＝ compareSeqString(s1, s2)；if （cmpResult ＜ 0) ｛std:：cout ＜＜＂s1 小于 s2" ＜＜ std:：endl;｝ else if （cmpResult ＝＝ 0) ｛std:：cout ＜＜＂s1 等于 s2" ＜＜ std:：endl;｝ else ｛std:：cout ＜＜＂s1 大于 s2" ＜＜ std:：endl;｝SeqString sub ＝ subSeqString(s1, 1, 3)；std:：cout ＜＜＂子串: ＂＜＜ substr ＜＜ std:：endl; insertSeqString(s1, 2, s2)；std:：cout ＜＜＂插入后的字符串: ＂＜＜ s1str ＜＜ std:：endl; deleteSeqString(s1, 3, 2)；std:：cout ＜＜＂删除后的字符串: ＂＜＜ s1str ＜＜ std:：endl; return 0;｝｀｀｀2、链式存储方式的测试｀｀｀cppint main(）｛LinkString ls1(＂Hello"）；LinkString ls2(＂World"）；LinkString ls3 ＝ ls1concat(ls2)；std:：cout ＜＜＂连接后的字符串: ＂；LinkNode p ＝ ls3head;while （p) ｛std:：cout ＜＜ p>data;p ＝ p>next;｝std:：cout ＜＜ std:：endl;int cmpResult ＝ ls1compare(ls2)；if （cmpResult ＜ 0) ｛std:：cout ＜＜＂ls1 小于 ls2" ＜＜ std:：endl;｝ else if （cmpResult ＝＝ 0) ｛std:：cout ＜＜＂ls1 等于 ls2" ＜＜ std:：endl;｝ else ｛std:：cout ＜＜＂ls1 大于 ls2" ＜＜ std:：endl;｝LinkString sub ＝ ls1subString(1, 3)；std:：cout ＜＜＂子串: ＂；p ＝ subhead;while （p) ｛std:：cout ＜＜ p>data;p ＝ p>next;｝std:：cout ＜＜ std:：endl;ls1insert(2, ls2)；std:：cout ＜＜＂插入后的字符串: ＂；p ＝ ls1head;while （p) ｛std:：cout ＜＜ p>data;p ＝ p>next;｝std:：cout ＜＜ std:：endl;ls1deleteSub(3, 2)；std:：cout ＜＜＂删除后的字符串: ＂；p ＝ ls1head;while （p) ｛std:：cout ＜＜ p>data;p ＝ p>next;｝std:：cout ＜＜ std:：endl;return 0;｝｀｀｀五、实验结果及分析（一）顺序存储方式1、连接操作成功实现，输出了正确连接后的字符串。

数据结构串实验报告实验报告课程数据结构实验名称实验三串学号姓名实验日期:实验三串实验目的:1. 熟悉串类型的实现方法，了解简单文字处理的设计方法;2. 熟悉C语言的字符和把字符串处理的原理和方法;3. 熟悉并掌握模式匹配算法。

实验原理:顺序存储结构下的关于字符串操作的基本算法。

模式匹配算法BF、KMP实验内容:4-19. 在4.4.3节例4-6的基础上，编写比较Brute-Force算法和KMP算法比较次数的程序。

4-20. 设串采用静态数组存储结构，编写函数实现串的替换Replace(S，start，T，V)，即要求在主串S中，从位置start开始查找是否存在字串T。

若主串S中存在子串T，则用子串V替换子串T，且函数返回1;若主串S中不存在子串T，则函数返回0;并要求设计I am a student”,T=“student”,V=“teacher”。

主函数进行测试。

一个测试例子为:S=“程序代码:4-19的代码:/*静态存储结构*/typedef struct{char str[MaxSize];int length;}String;/*初始化操作*/void Initiate(String *S) {S->length=0;}/*插入子串操作 */int Insert(String *S, int pos, String T)/*在串S的pos位置插入子串T*/{int i;if(pos<0||pos>S->length){printf("The parameter pos is error!\n");return 0;}else if(S->length+T.length>MaxSize){printf("The space of the array is not enough!\n"); return 0;}else{for(i=S->length-1; i>=pos; i--)S->str[i+T.length]=S->str[i];/*依次后移数据元素*/for(i=0; i<T.length; i++)S->str[pos+i]=T.str[i]; /*插入*/S->length=S->length+T.length;/*产生新的串长度值*/return 1;}}/*删除子串操作 */int Delete(String *S, int pos, int len) /*删除串S的从pos位置开始长度为len的子串值*/{int i;if(S->length<=0){printf("No elements deleting!\n");return 0;}else if(pos<0||len<0||pos+len>S->length){printf("The parameters pos and len are not correct!\n"); return 0;}else{for(i=pos+len; i<=S->length-1; i++)S->str[i-len]=S->str[i];/*依次前移数据元素*/S->length=S->length-len;/*产生新的串长度值*/return 1;}}/*取子串操作 */int SubString(String S, int pos, int len, String *T)/*取串S的从pos位置开始长度为len的子串值赋给子串T*/ {int i;if(pos<0||len<0||pos+len>S.length){printf("The parameters pos and len are not correct!\n"); return 0;}else{for(i=0; i<=len; i++)T->str[i]=S.str[pos+i]; /*给子串T赋值*/T->length=len; /*给子串T的长度域赋值*/return 1;}}/*查找子串BF(Brute-Force)操作*/int BFIndex(String S, int start, String T)/*查找主串S从start开始的子串T，找到返回T在S中的开始字符下标，否则返回-1*/ {int i= start, j=0, v;while(i<S.length && j<T.length){if(S.str[i]==T.str[j]){i++;j++;}else{i=i-j+1;j=0;}}if(j==T.length)v=i-T.length;elsev=-1;return v;}/*查找子串KMP(D.E.Knuth-J.H.Morris-V.R.Pratt)操作 */ int KMPIndex(String S, int start, String T, int next[])/*查找主串S从start开始的子串T，找到返回T在S中的首字符下标，*/ /*否则返回-1*//*数组Next中存放有模式串T的next[j]值*/{int i= start, j=0, v;while(i<S.length && j<T.length){if(S.str[i]==T.str[j]){i++;j++;}else if(j==0) i++;else j=next[j];}if(j==T.length)v=i-T.length;elsev=-1;return v;}/*求模式串next[j]值的操作 */void GetNext(String T, int next[])/*求子串T的next[j]值并存放于数组next中*/ {int j=1, k=0;next[0]=-1;next[1]=0;while(j<T.length){if(T.str[j]=T.str[k]){next[j+1]=k+1;j++;k++;}else if(k==0){next[j+1]=0;j++;}else k=next[k];}}/*查找子串BF(Brute-Force)算法累计次数 */int BFIndexC(String S, int start, String T)/*查找主串S从start开始的子串T，找到返回T在S中的开始字符下标，否则返回-1*/{int i= start, j=0, t=0;while(i<S.length && j<T.length){if(S.str[i]==T.str[j]){i++;j++;}else{i=i-j+1;j=0;}t++;}return t;}/*查找子串KMP(D.E.Knuth-J.H.Morris-V.R.Pratt)操作 */ int KMPIndexC(String S, int start, String T, int next[])/*查找主串S从start开始的子串T，找到返回T在S中的首字符下标，*/ /*否则返回-1*//*数组Next中存放有模式串T的next[j]值*/{int i= start, j=0, t=0;while(i<S.length && j<T.length){if(S.str[i]==T.str[j]){i++;j++;}else if(j==0)i++;else j=next[j];t++;}return t;}测试主函数:#include<stdio.h>#define MaxSize 100#include"SString.h"#include"BFandKMP.h"void main(void){String S={{"cddcdc"},6}, T={{"abcde"},5};String S1={{"aaaaaaaa"},8}, T1={{"aaaab"},5};String S2={{"aaaaaaaaaaaaaaaaad"},18}, T2={{"aaaab"},5};int next[20], count;count=BFIndexC(S,0,T);printf("从S中查找T的Brute-Force算法比较次数:%d\n",count); GetNext(T, next);count=KMPIndexC(S,0,T,next);printf("从S中查找T的KMP算法比较次数:%d\n",count);count=BFIndexC(S1,0,T1);printf("从S1中查找T1的Brute-Force算法比较次数:%d\n",count); GetNext(T1, next);count=KMPIndexC(S1,0,T1,next);printf("从S1中查找T1的KMP算法比较次数:%d\n",count);count=BFIndexC(S2,0,T2);printf("从S2中查找T2的Brute-Force算法比较次数:%d\n",count); GetNext(T2, next);count=KMPIndexC(S2,0,T2,next);printf("从S2中查找T2的KMP算法比较次数:%d\n",count);}4-20的部分代码:Replace函数:/* 从主串S中查找字串T，若存在，并用串V替换串T并返回1，否则，返回0*/ int Replace(String S,int start,String T,String V){int i,v;Initiate(&S);Initiate(&T);Initiate(&V);for(i=0; i<strlen(S.str); i++)S.length=S.length+1;for(i=0; i<strlen(T.str); i++)T.length=T.length+1;for(i=0; i<strlen(V.str); i++)V.length=V.length+1;i=BFIndex(S, 0, T);if (i!=-1){if(Delete(&S, i, T.length))Insert(&S, i, V);for(i=0; i<S.length; i++)printf("%c", S.str[i]);printf("\n");return v=1;}else{printf("主串S中不存在串T\n");return v=0;}}测试主函数:#define MaxSize 80#include<stdio.h>#include<string.h>#include "SString.h"int main(void){ int v;String S={"I am a student."}, T={"student"}, V={"teacher"}; v=Replace(S,0,T,V);printf("返回%d\n",v);}实验结果:4-19.程序调式结果:4-20.程序调式结果:总结与思考KMP算法的比较次数比Brute-Force算法的少。

串的数据结构实验报告串的数据结构实验报告一、引言在计算机科学中，串（String）是一种基本的数据结构，用于存储和操作字符序列。

串的数据结构在实际应用中具有广泛的用途，例如文本处理、搜索引擎、数据库等。

本实验旨在通过实践掌握串的基本操作和应用。

二、实验目的1. 理解串的概念和基本操作；2. 掌握串的存储结构和实现方式；3. 熟悉串的常见应用场景。

三、实验内容1. 串的定义和基本操作在本实验中，我们采用顺序存储结构来表示串。

顺序存储结构通过一个字符数组来存储串的字符序列，并使用一个整型变量来记录串的长度。

基本操作包括：- 初始化串- 求串的长度- 求子串- 串的连接- 串的比较2. 串的模式匹配串的模式匹配是串的一个重要应用场景。

在实验中，我们将实现朴素的模式匹配算法和KMP算法，并比较它们的性能差异。

四、实验步骤1. 串的定义和基本操作首先，我们定义一个结构体来表示串，并实现初始化串、求串的长度、求子串、串的连接和串的比较等基本操作。

2. 串的模式匹配a. 实现朴素的模式匹配算法朴素的模式匹配算法是一种简单但效率较低的算法。

它通过逐个比较主串和模式串的字符来确定是否匹配。

b. 实现KMP算法KMP算法是一种高效的模式匹配算法。

它通过利用已匹配字符的信息，避免不必要的比较，从而提高匹配效率。

3. 性能比较与分析对比朴素的模式匹配算法和KMP算法的性能差异，分析其时间复杂度和空间复杂度，并讨论适用场景。

五、实验结果与讨论1. 串的基本操作经过测试，我们成功实现了初始化串、求串的长度、求子串、串的连接和串的比较等基本操作，并验证了它们的正确性和效率。

2. 串的模式匹配我们对两种模式匹配算法进行了性能测试，并记录了它们的运行时间和内存占用情况。

结果表明，KMP算法相较于朴素算法，在大规模文本匹配任务中具有明显的优势。

六、实验总结通过本实验，我们深入学习了串的数据结构和基本操作，并掌握了串的模式匹配算法。

实验题目：串的模式匹配一、实验目的1、加深理解串的基本操作；2、理解并实现串的朴素模式匹配算法。

二、实验内容输入主串S和模式T，在S中查找T出现的第一个位置。

三、设计与编码1、基本思想1，在串S和串T中设置比较的起始下标i和j；2，如果S[i]=T[j]，继续比较S和T的下一对字符，否则将下标i,j回溯，准备下一趟比较；3，如果T中所有字符都比较完，则匹配成功，返回匹配的开始位置，否则返回0；2、编码#include<iostream>#include<string>using namespace std;class BF{private:char *s,*t;public:BF(char a[],char b[]){s=a;t=b;}int bf(){int i=0,j=0;while((s[i]!='\0')&&(t[j]!='\0')){if(s[i]==t[j]){i++;j++;}else{i=i-j+1;j=0;}}if(t[j]=='\0')return i-j+1;}};int main(){char s[100],t[100];cin>>s>>t;BF A(s,t);cout<<"主串S:"<<s<<'\n'<<"模式T:"<<t<<endl;cout<<A.bf()<<endl;return 0;}四、调试与运行1、调试时遇到的主要问题及解决答：基本没有大的错误，大多是一些细节问题，就是字符串的上传问题，我最后直接用指针搞定。

2、运行结果（输入及输出，可以截取运行窗体的界面）输入：abcdefgh defg；输出：五、实验心得答：通过本次的实验，让我加深了理解了串的操作。

数据结构—串的模式匹配数据结构—串的模式匹配1.介绍串的模式匹配是计算机科学中的一个重要问题，用于在一个较长的字符串（称为主串）中查找一个较短的字符串（称为模式串）出现的位置。

本文档将详细介绍串的模式匹配算法及其实现。

2.算法一：暴力匹配法暴力匹配法是最简单直观的一种模式匹配算法，它通过逐个比较主串和模式串的字符进行匹配。

具体步骤如下：1.从主串的第一个字符开始，逐个比较主串和模式串的字符。

2.如果当前字符匹配成功，则比较下一个字符，直到模式串结束或出现不匹配的字符。

3.如果匹配成功，返回当前字符在主串中的位置，否则继续从主串的下一个位置开始匹配。

3.算法二：KMP匹配算法KMP匹配算法是一种改进的模式匹配算法，它通过构建一个部分匹配表来减少不必要的比较次数。

具体步骤如下：1.构建模式串的部分匹配表，即找出模式串中每个字符对应的最长公共前后缀长度。

2.从主串的第一个字符开始，逐个比较主串和模式串的字符。

3.如果当前字符匹配成功，则继续比较下一个字符。

4.如果当前字符不匹配，则根据部分匹配表的值调整模式串的位置，直到模式串移动到合适的位置。

4.算法三：Boyer-Moore匹配算法Boyer-Moore匹配算法是一种高效的模式匹配算法，它通过利用模式串中的字符出现位置和不匹配字符进行跳跃式的匹配。

具体步骤如下：1.构建一个坏字符规则表，记录模式串中每个字符出现的最后一个位置。

2.从主串的第一个字符开始，逐个比较主串和模式串的字符。

3.如果当前字符匹配成功，则继续比较下一个字符。

4.如果当前字符不匹配，则根据坏字符规则表的值调整模式串的位置，使模式串向后滑动。

5.算法四：Rabin-Karp匹配算法Rabin-Karp匹配算法是一种基于哈希算法的模式匹配算法，它通过计算主串和模式串的哈希值进行匹配。

具体步骤如下：1.计算模式串的哈希值。

2.从主串的第一个字符开始，逐个计算主串中与模式串长度相同的子串的哈希值。

串的模式匹配算法实验报告竭诚为您提供优质文档/双击可除串的模式匹配算法实验报告篇一：串的模式匹配算法串的匹配算法——bruteForce(bF)算法匹配模式的定义设有主串s和子串T，子串T的定位就是要在主串s中找到一个与子串T相等的子串。

通常把主串s称为目标串，把子串T称为模式串，因此定位也称作模式匹配。

模式匹配成功是指在目标串s中找到一个模式串T；不成功则指目标串s中不存在模式串T。

bF算法brute-Force算法简称为bF算法，其基本思路是：从目标串s的第一个字符开始和模式串T中的第一个字符比较，若相等，则继续逐个比较后续的字符；否则从目标串s的第二个字符开始重新与模式串T 的第一个字符进行比较。

以此类推，若从模式串T的第i个字符开始，每个字符依次和目标串s中的对应字符相等，则匹配成功，该算法返回i；否则，匹配失败，算法返回0。

实现代码如下：/*返回子串T在主串s中第pos个字符之后的位置。

若不存在，则函数返回值为0./*T非空。

intindex(strings,stringT,intpos){inti=pos;//用于主串s中当前位置下标，若pos不为1则从pos 位置开始匹配intj=1;//j用于子串T中当前位置下标值while(i j=1；}if(j>T[0])returni-T[0];elsereturn0;}}bF算法的时间复杂度若n为主串长度，m为子串长度则最好的情况是：一配就中，只比较了m次。

最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，最后m位也各比较了一次，还要加上m,所以总次数为：(n-m)*m+m=(n-m+1)*m从最好到最坏情况统计总的比较次数，然后取平均，得到一般情况是o(n+m).篇二：数据结构实验报告-串实验四串【实验目的】1、掌握串的存储表示及基本操作；2、掌握串的两种模式匹配算法：bF和Kmp。

3、了解串的应用。

一、实验目的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算法的编写和调试，但在老师和同学的指导下，我成功地解决了这些问题。

实验三串的模式匹配一、实验目的1．利用顺序结构存储串，并实现串的匹配算法。

2．掌握简单模式匹配思想，熟悉KMP算法。

二、实验要求1．认真理解简单模式匹配思想，高效实现简单模式匹配；2．结合参考程序调试KMP算法，努力算法思想；3．保存程序的运行结果，并结合程序进行分析。

三、实验内容1、通过键盘初始化目标串和模式串，通过简单模式匹配算法实现串的模式匹配，匹配成功后要求输出模式串在目标串中的位置；2、参考程序给出了两种不同形式的next数组的计算方法，请完善程序从键盘初始化一目标串并设计匹配算法完整调试KMP算法，并与简单模式匹配算法进行比较。

四、程序流程图、算法及运行结果3-1#include <stdio.h>#include <string.h>#define MAXSIZE 100int StrIndex_BF(char s[MAXSIZE],char t[MAXSIZE]){int i=1,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]);elsereturn -1;}int main(){char s[MAXSIZE];char t[MAXSIZE];int answer, i;printf("S String -->\n ");gets(s);printf("T String -->\n ");gets(t);printf("%d",StrIndex_BF(s,t)); /*验证*/if((answer=StrIndex_BF(s,t))>=0){printf("\n");printf("%s\n", s);for (i = 0; i < answer; i++)printf(" ");printf("%s", t);printf("\n\nPattern Found at location:%d\n", answer); }elseprintf("\nPattern NOT FOUND.\n");getch();return 0;}3-2#include <stdio.h>#include <string.h>#define MAXSIZE 100void get_nextval(unsigned char pat[],int nextval[]){int length = strlen(pat);int i=1;int j=0;nextval[1]=0;while(i<length){if(j==0||pat[i-1]==pat[j-1]){++i;++j;if(pat[i-1]!=pat[j-1]) nextval[i]=j;else nextval[i]=nextval[j];}else j=nextval[j];}}int Index_KMP(unsigned char text[], unsigned char pat[],int nextval[]) {int i=1;int j=1;int t_len = strlen(text);int p_len = strlen(pat);while(i<=t_len&&j<=p_len){if(j==0||text[i-1]==pat[j-1]){++i;++j;}else j=nextval[j];}if(j>p_len) return i-1-p_len;else return -1;}int main(){unsigned char text[MAXSIZE];unsigned char pat[MAXSIZE];int nextval[MAXSIZE];int answer, i;printf("\nBoyer-Moore String Searching Program"); printf("\n====================================");printf("\n\nText String --> ");gets(text);printf( "\nPattern String --> ");gets(pat);get_nextval(pat,nextval);if((answer=Index_KMP(text, pat,nextval))>=0){printf("\n");printf("%s\n", text);for (i = 0; i < answer; i++)printf(" ");printf("%s", pat);printf("\n\nPattern Found at location %d\n", answer); }elseprintf("\nPattern NOT FOUND.\n");getch();return 0;}3-3#include "stdio.h"void GetNext1(char *t,int next[]){int i=1,j=0;next[1]=0;while(i<=9){if(j==0||t[i]==t[j]){++i; ++j; next[i]=j; }elsej=next[j];}}void GetNext2(char *t , int next[]){int i=1, j = 0;next[1]= 0;while (i<=9){while (j>=1 && t[i] != t[j] )j = next[j];i++; j++;if(t[i]==t[j]) next[i] = next[j];else next[i] = j; }}void main(){char *p="abcaababc";int i,str[10];GetNext1(p,str);printf("Put out:\n");for(i=1;i<10;i++)printf("%d",str[i]);GetNext2(p,str);printf("\n");for(i=1;i<10;i++)printf("%d",str[i]);printf("\n");getch();}.。

数据结构—串的模式匹配数据结构—串的模式匹配1：引言1.1 背景在计算机科学中，模式匹配是一个常见的问题，涉及到在给定的文本字符串中查找特定的模式串。

串的模式匹配是一种重要的算法，广泛应用于字符串处理、数据查询和自然语言处理等领域。

1.2 目的本文档旨在介绍串的模式匹配算法的基本原理和常用的实现方法，以及其在实际应用中的一些应用场景。

通过阅读本文档，读者将能够理解串的模式匹配算法的工作原理，并能够根据具体的应用需要选择合适的算法进行实现。

2：基本概念2.1 字符串字符串是由字符组成的有限序列，在计算机中通常以字符数组或字符指针的形式来表示。

字符串是计算机科学中常用的数据类型之一，用于表示文本数据。

2.2 模式串模式串是在字符串匹配中需要查找的特定模式，它是一个想要在文本串中查找的子串。

3：算法实现3.1 简单匹配算法简单匹配算法，也称为朴素匹配算法，是最简单直观的一种模式匹配算法。

它的基本思想是，从文本串的第一个字符开始，逐个字符地与模式串进行匹配，如果匹配失败，则从文本串的下一个字符重新开始匹配。

3.2 KMP算法KMP算法是一种高效的模式匹配算法，它利用了模式串本身的信息来加速匹配过程。

该算法基于一个重要观察结果，即当模式串在某一位置匹配失败时，它的前缀与后缀可能存在一定的重叠，从而可以避免无效的匹配。

3.3 Boyer-Moore算法Boyer-Moore算法是一种高效的模式匹配算法，它利用了模式串和文本串的不同之处来加速匹配过程。

该算法在匹配失败时，根据坏字符规则和好后缀规则，可以跳过一定数量的字符，从而避免无效的匹配。

4：应用场景4.1 文本搜索串的模式匹配算法可以应用于文本搜索中，用于在大量文本数据中查找特定模式的出现位置。

4.2 数据处理串的模式匹配算法可以应用于数据处理中，用于对字符串数据进行匹配处理、替换等操作。

4.3 自然语言处理串的模式匹配算法可以应用于自然语言处理中，用于识别特定语义模式或词组的出现。

常熟理工学院《数据结构与算法》实验指导与报告书_2017-2018_____学年第__1__ 学期专业：物联网工程实验名称：串与模式匹配实验地点： N6-210 指导教师：聂盼红计算机科学与工程学院2017实验四串与模式匹配【实验目的】1、掌握串的存储表示及基本操作；2、掌握串的两种模式匹配算法：BF和KMP。

3、了解串的应用。

【实验学时】2学时【实验预习】回答以下问题：1、串和子串的定义串：串是由零个或多个任意字符组成的有限序列。

子串：串中任意连续字符组成的子序称为该串的字串。

2、串的模式匹配串的模式匹配是数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串，这就是模式匹配。

假设P是给定的子串，T是待查找的字符串，要求从T中找出与P相同的所有子串，这个问题成为模式匹配问题。

P称为模式，T 称为目标。

如果T中存在一个或多个模式为P的子串，就给出该子串在T中的位置，称为匹配成功；否则匹配失败【实1验内容和要求】/1、按照要求完成程序exp4_1.c，实现串的相关操作。

调试并运行如下测试数据给出运行结果：•求“This is a boy”的串长；•比较”abc 3”和“abcde“； 表示空格•比较”english”和“student“；•比较”abc”和“abc“；•截取串”white”，起始2，长度2；•截取串”white”，起始1，长度7；•截取串”white”，起始6，长度2；•连接串”asddffgh”和”12344”；实验代码：#include<stdio.h>#include<string.h>#define MAXSIZE 100#define ERROR 0#define OK 1/*串的定长顺序存储表示*/typedef struct{char data[MAXSIZE];int length;} SqString;int strInit(SqString *s); /*初始化串*/int strCreate(SqString *s); /*生成一个串*/ int strLength(SqString *s); /*求串的长度*/ int strCompare(SqString *s1,SqString *s2); /*两个串的比较*/ int subString(SqString *sub,SqString *s,int pos,int len); /*求子串*/ int strConcat(SqString *t,SqString *s1,SqString *s2); /*两个串的连接*//*初始化串*/int strInit(SqString *s){s->length=0;s->data[0]='\0';return OK;}/*strInit*//*生成一个串*/int strCreate(SqString *s){printf("input string :");gets(s->data);s->length=strlen(s->data);return OK;}/*strCreate*//*（1）---求串的长度*/int strLength(SqString *s){return s->length;}/*strLength*//*（2）---两个串的比较，S1>S2返回>0，s1<s2返回<0，s1==s2返回0*/int strCompare(SqString *s1,SqString *s2){int i;for(i=0; i<s1->length && i<s2->length; i++)if(s1->data[i] != s2->data[i])return s1->data[i] - s2->data[i];return s1->length - s2->length;}/*strCompare*//*（3）---求子串，sub为返回的子串，pos为子串的起始位置，len为子串的长度*/ int subString(SqString *sub,SqString *s,int pos,int len){int i;if(pos<1 || pos>s->length || len<0 || len>s->length-pos+1)return ERROR;sub->length = 0;for(i=0; i<len; i++){sub->data[i] = s->data[i+pos-1];sub->length++;}sub->data[i] = '\0';return OK;}/*subString*//*（4）---两个串连接，s2连接在s1后，连接后的结果串放在t中*/int strConcat(SqString *t,SqString *s1,SqString *s2){int i=0, j=0;while(i<s1->length){t->data[i] = s1->data[i];i++;}while(j<s2->length)t->data[i++] = s2->data[j++];t->data[i] = '\0';t->length = s1->length + s2->length;return OK;}/*strConcat*/int main(){system("color 1f");int n,k,pos,len;SqString s,t,x;do{printf("\n ---String--- \n");printf(" 1. strLentgh\n");printf(" 2. strCompare\n");printf(" 3. subString\n");printf(" 4. strConcat\n");printf(" 0. EXIT\n");printf("\n ---String---\n");printf("\ninput choice:");scanf("%d",&n);getchar();switch(n){case 1:printf("\n***show strLength***\n");strCreate(&s);printf("strLength is %d\n",strLength(&s));break;case 2:printf("\n***show strCompare***\n");strCreate(&s);strCreate(&t);k=strCompare(&s, &t); /*（5）---调用串比较函数比较s，t*/ if(k==0)printf("two string equal!\n");else if(k<0)printf("first string<second string!\n");elseprintf("first string>second string!\n");break;case 3:printf("\n***show subString***\n");strCreate(&s);printf("input substring pos,len:");scanf("%d,%d",&pos,&len);if(subString(&t,&s,pos,len))printf("subString is %s\n",t.data);elseprintf("pos or len ERROR!\n");break;case 4:printf("\n***show subConcat***\n");strCreate(&s);strCreate(&t);if(strConcat(&x, &s, &t)) /*（6）---调用串连接函数连接s&t*/ printf("Concat string is %s",x.data);elseprintf("Concat ERROR!\n");break;case 0:exit(0);default:break;}}while(n);return 0;}2、按照要求完成程序exp4_2.c，实现BF&KMP串的模式匹配算法。

数据结构-数组和串的模式匹配数据结构数组和串的模式匹配在计算机科学中，数据结构是我们组织和存储数据的方式，以便能够高效地对其进行操作和处理。

数组和串是两种常见的数据结构，而模式匹配则是在这两种结构中经常进行的重要操作。

首先，让我们来聊聊数组。

数组是一种线性的数据结构，它将相同类型的元素按照顺序存储在连续的内存空间中。

想象一下，数组就像是一排整齐排列的盒子，每个盒子里都放着相同类型的东西。

比如，一个整数数组，每个盒子里就装着一个整数。

数组的优点很明显，由于元素的存储是连续的，所以访问数组中的元素非常快。

只要知道元素的索引，就能在常数时间内找到对应的元素。

这就好比你知道了某个盒子在这一排中的位置，直接伸手就能拿到里面的东西。

然而，数组也有它的局限性。

当我们需要插入或删除元素时，如果不是在数组的末尾进行操作，那么就会涉及到大量元素的移动，这是非常耗时的。

接下来，再看看串。

串其实就是字符的数组，它是由一系列连续的字符组成的。

在很多应用中，我们需要在一个长串中查找是否存在特定的模式串。

模式匹配，简单来说，就是在给定的主串中查找是否存在与模式串完全相同的子串。

这就像是在一篇长长的文章里找特定的一段话。

在数组中进行模式匹配，常见的方法有直接比较法。

我们从数组的开头开始，逐个元素与模式串进行比较。

如果完全匹配，就找到了模式；如果不匹配，就继续往后移动。

例如，有一个整数数组1, 2, 3, 4, 5, 6, 7, 8, 9，我们的模式串是3, 4, 5。

我们从数组的第一个元素开始，依次与模式串的元素进行比较。

当比较到第三个元素时，发现与模式串的第一个元素相同，然后继续比较后面的元素，直到完全匹配。

但是这种方法在一些情况下效率可能不高。

比如，如果数组很大，而模式串比较短，那么可能需要进行大量的比较操作。

在串的模式匹配中，有一种经典的算法叫做朴素模式匹配算法。

它的基本思想很简单，就是从主串的第一个字符开始，依次与模式串进行比较。