数据结构串与模式匹配

1、常熟理工学院数据结构与算法实验指导与报告书_2017-2018_ _ 学年 第_1_ 学期专业：物联网工程实验名称：串与模式匹配实验地点：N6-210指导教师：聂盼红计算机科学与工程学院2017实验四 串与模式匹配【实验目的】1、掌握串的存储表示及基本操作；2、掌握串的两种模式匹配算法： BF 和 KMP 。3、了解串的应用。【实验学时】2 学时【实验预习】回答以下问题：1、串和子串的定义串：串是由零个或多个任意字符组成的有限序列。子串：串中任意连续字符组成的子序称为该串的字串。2、串的模式匹配串的模式匹配是数据结构中字符串的一种基本运算， 给定一个子串， 要求在某个字符串 中找出与该子串相同

2、的所有子串， 这就是模式匹配。 假设 P 是给定的子串， T 是待查找的字 符串，要求从T中找出与P相同的所有子串，这个问题成为模式匹配问题。P称为模式，T称为目标。如果 T 中存在一个或多个模式为 P 的子串，就给出该子串在 T 中的位置，称为 匹配成功；否则匹配失败实1验内容和要求】/调试并运行如下测试数据给出运1、按照要求完成程序 exp4_1.c ,实现串的相关操作。行结果：求This is a boy "的串长;input choice:1*show strLength*input string :This is a boy strLength is 13比较"a

3、bc 3 "和abcde ； 表示空格*show strCompare* input string :abc 3 input string :abcde first string<second string：比较"english "和 Student*show 航rCompare* input string :english input 呂tring :student first string<second string!比较"abc "和abc ；*show strCompare* input string :abc input

4、string :abc two string equal!截取串” white ”起始2，长度2 ;input choice:3*show subString* input string :white input substring pos?len:2, 2 subString is hi截取串”white ”起始1，长度7 ；*show subString* input string :white input substring pos, len：1, 7 pos or len ERROR!截取串” white ”起始6，长度2 ;*show subString*input string :

5、white input substring pos, len:6, 2 pos or len ERROR!连接串” asddffgh”和 ”12344 ”;show subConcat* input string :asddffgh input string :12344Concat string is asddffghl2344 String实验代码:#in clude<stdio.h>#in clude<stri ng.h>#defi ne MAXSIZE 100#defi ne ERROR 0#defi ne OK 1/*串的定长顺序存储表示*/typedef s

6、tructchar dataMAXSIZE;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,

7、SqString *s1,SqString *s2);/* 两个串的连接 */* 初始化串 */int strInit(SqString *s) s->length=0;s->data0='0' return OK;/*strInit*/* 生成一个串 */int strCreate(SqString *s)printf("input string :");gets(s->data);s->length=strlen(s->data);return OK;/*strCreate*/* (1) - 求串的长度 */ int str

8、Length(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->datai != s2->datai)return s1->datai - s2->datai;return s

9、1->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->datai =

10、s->datai+pos-1;sub->length+;sub->datai = '0'return OK;/*subString*/* (4)-两个串连接，s2连接在si后，连接后的结果串放在 t中*/int strConcat(SqString *t,SqString *s1,SqString *s2)int i=0, j=0;while(i<s1->length)t->datai = s1->datai;i+;while( j<s2->length)t->datai+ = s2->dataj+;t->

11、datai = '0't->length = s1->length + s2->length; return OK;/*strConcat*/int main()system("color 1f");int n,k,pos,len;SqString s,t,x;doprintf("n -String- n");printf(" 1. strLentghn");printf(" 2. strComparen");printf(" 3. subStringn");p

12、rintf(" 4. strConcatn");printf(" 0. EXITn");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 %dn",strLength(&s);bre

13、ak;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

14、");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 %sn",t.data);elseprintf("pos or len ERROR!n");break;case 4

15、:printf("n*show subConcat*n");strCreate(&s);strCreate(&t);s&t*/if(strConcat(&x, &s, &t) /* (6)- 调用串连接函数连接printf("Concat string is %s",x.data);elseprintf("Concat ERROR!n");break;case 0:exit(O);default:break;while( n);return 0;2、按照要求完成程序exp4_2.c，实现

16、BF&KMP串的模式匹配算法。调试及测试数据并给出结果：应用BF算法求子串” JING ”在主串” BEIJING ”中的位置，测试起始位置分别为1和5的情况；*show IndeX-BF*s:input string :BEIJING t:input 航ring :JING input start position:1 BF:index is 4*show Index_BF*s:input string :BEIJING t:input string :JIXG input start position:5 BF:index is 0应用 KMP 算法求子串” abaabcac ”在

17、主串” acabaabaabcacaabc ”中的位置，测试起始位置分别为1， 10的情况，并写出子串的next值;*show Index_KMP*s:input string :acabaabaabcacaabc t:input string :abaabcacinput start position:1KMP：nexttL -10 0112 01index is 6申材show Index_KMP*s:input string :acabaabaabcacaabc t:input string :abaabcacinput start position:10KMP *next: -10 0

18、112 O' 1index is 0exp4_2.c部分代码如下:#in clude<stdio.h>#in clude<stri ng.h>#defi ne MAXSIZE 100#defi ne ERROR 0#defi ne OK 1/*串的定长顺序存储表示*/typedef structchar dataMAXSIZE; int len gth; SqStri ng;int strCreate(SqStri ng *s);int indexBf(SqString *s,SqString *t,int pos);/* 串的模式匹配 BF*/void get

19、Next(SqString *t,int next);/*KMP 求 next 值 */int indexKmp(SqString *s,SqString *t,int start,int next); /*串的模式匹配 KMP*/* 生成一个串 */int strCreate(SqString *s)printf("input string :");gets(s->data);s->length=strlen(s->data);return OK;/*strCreate*/* (1) - 串的模式匹配 BF*/int indexBf(SqString *

20、s,SqString *t,int pos)int i = pos-1, j = 0;while(i<s->length &&j<t->length)if(s->datai = t->dataj)i+;j+;elsei = i - j +1;j = 0;if(j >= t->length)return i - t->length+1;elsereturn 0;/*index_bf*/* (2) -KMP 求 next 值*/void getNext(SqString *t,int next)int i = 0, j = -1

21、;next0 = -1;while(i < t->length)if(j=-1) | (t->datai=t->dataj)i+;j+;nexti = j;elsej = nextj;/*getNext*/* (3) -KMP 模式匹配 */int indexKmp(SqString *s,SqString *t,int start,int next) int i = start - 1, j = 0;while(i<s->length && j<t->length)if(j=-1 | s->datai=t->data

22、 j) i+;j+;elsej = nextj;if(j >= t->length)return i - t->length+1;elsereturn 0;/*index_kmp*/int main()system("color 1f");int n,i,pos,nextMAXSIZE;SqString s,t;doprintf("n -String- n");printf(" 1. Index_BFn");printf(" 2. INdex_KMPn");printf(" 0. EXITn");printf("n -String-n");printf("ninput choice:");scanf("%d",&n);getchar();switch(n)case 1:printf("n*show Index_BF*n");printf(" s:");strCreate(&s);printf(" t:");strCreate(&t);printf("input start position:");s