首页 数据结构实验报告-串

数据结构实验报告-串

数据结构实验报告-串1/1文档可自由编辑i/i文档可自由编辑实验四串【实验目的】1、掌握串的存储表示及基本操作；2、掌握串的两种模式匹配算法：BF和KMP。3、了解串的应用。【实验学时】2学时【实验预习】回答以下问题：1、串和子串的定义串的定义：串是由零个或多个任意字符组成的有限序列。子串的定义：串中任意连续字符组成的子序列称为该串的子串。2、串的模式匹配串的模式匹配即子串定位是一种重要的串运算。设s和I是给定的两个串，从主串s的第start个字符开始查找等于子串t的过程称为模式匹配，如果在S中找到等于t的子串，则称匹配成功，函数返回...

1/1文档可自由编辑i/i文档可自由编辑实验四串【实验目的】1、掌握串的存储表示及基本操作；2、掌握串的两种模式匹配算法：BF和KMP。3、了解串的应用。【实验学时】2学时【实验预习】回答以下问题：1、串和子串的定义串的定义：串是由零个或多个任意字符组成的有限序列。子串的定义：串中任意连续字符组成的子序列称为该串的子串。2、串的模式匹配串的模式匹配即子串定位是一种重要的串运算。设s和I是给定的两个串，从主串s的第start个字符开始查找等于子串t的过程称为模式匹配，如果在S中找到等于t的子串，则称匹配成功，函数返回t在s中首次出现的存储位置（或序号）；否则，匹配失败，返回Oo【实验内容和要求】1、按照要求完成程序exp4」.c,实现串的相关操作。调试并运行如下测试数据给出运行结果：求"Thisisaboy"的串长；比较“abc3”和“abcde“；表示空格比较"english"和"student”；比较“abc”和“abc”；截取串"white”,起始2,长度2；截取串"white”，起始1,长度7；截取串"white”,起始6,长度2；连接串"asddffgh”和“12344”；#include#include^defineMAXSIZE100defineERROR0defineOK1/*串的定长顺序存储表示*/typedefstruct{chardata[MAXSIZE]；intlength；}SqString；intstrlnit(SqString*s)；/*初始化串*/intstrCreate(SqString*s)；/*生成一个串*/intstrLength(SqString*s)；/*求串的长度*/intstrCompare(SqString*sl,SqString*s2)；/*两个串的比较*/intsubString(SqString*sub,SqString*s,intpos,intlen)；/*求子串*/intstrConcat(SqString*t,SqString*sl,SqString*s2)；/*两个串的连接*//*初始化串*/intstrlnit(SqString*s){s->length=0；s->data[0]=，\0'；returnOK；}/*strInit*//*生成一个串*/intstrCreate(SqString*s)printf("inputstring：")；gets(s->data)；s->length=strlen(s->data)；returnOK；}/*strCreate*//*(1)-—求串的长度*/intstrLength(SqString*s){returns->length；}/*strLength*//*(2)—-两个串的比较，S1〉S2返回>0,sllength&&ilength；i++)(if(sl->data[i]>s2->data[i])(return1；i/i文档可自由编辑1/1文档可自由编辑if(sl->data[i]data[i])return-1；}}return0；}/*strCompare*//*(3)求子串，sub为返回的子串，pos为子串的起始位置,len为子串的长度*/intsubString(SqString*sub,SqString*s,intpos,intlen){inti；if(poss->length|len<0|len>s->length-pos+l)(returnERROR；}sub->length=0；for(i=0；idata[i]=s->data[i+pos-l]；sub->length++；}sub->data[i]=>\Of；returnOK；}/"subString*//*(4)—-两个串连接，s2连接在si后，连接后的结果串放在t中*/intstrConcat(SqString*t,SqString*sl,SqString*s2){inti=0,j=0；while(ilength)(t->data[i]=sl->data[i]；i++;}while(jlength)(t->data[i++]=s2->data[j++]；}t->data[i]=，\0'；t->length=sl->length+s2->length；returnOK；}/*strConcat*/intmain()intn,k,pos,len；SqStrings,t,x；do(printf('AnString\n")；printf(n1.strLentgh\n")；printf('>2.strCompare\nH)；printf(,F3.subString\n")；printf(,F4.strConcat\n")；printf(H0.EXIT\n'r)；printf(v\nString\n")；printf(n\ninputchoice：H)；scanf(,r%d",&n)；getchar()；switch(n)case1：printf(M\n***showstrLength***\n,F)；strCreate(&s)；printf(HstrLengthis%d\nn,strLength(&s))；1/1文档可自由编辑i/i文档可自由编辑break；case2：printf(n\n***showstrCompare***\nn)；strCreate(&s)；strCreate(&t)；k=strCompare(&sf&t)；/*(5)—调用串比较函数比较s,I*/if(k=O)printf(ntwostringequal!\nH)；elseif(k<0)printf(nfirststringsecondstring!\nn)；break；case3：printf(n\n***showsubString***\nH)；strCreate(&s)；printf(Hinputsubstringpos,len：，r)；scanf(H%d,%d,r,&pos,&1en)；if(subStringpos,len))printf(^substringis%s\nH,t.data)；elseprintf(MposorlenERROR!\nn)；break；case4：printf(f，\n***showsubConcat***\nH)；strCreate(&s)；strCreate(&t)；if(strConcat(&x,&s,&t))/*(6)—调用串连接函数连接s&t*/printf(HConcatstringis%s\x.data)；elseprintf("ConcatERROR!\n'*)；break；case0：exit(0)；default：break；}}while(n)；return0；}2、按照要求完成程序exp4_2.c,实现BF&KMP串的模式匹配算法。调试及测试数据并给出结果：•应用BF算法求子串“JING”在主串“BEIJING”中的位置，测试起始位置分别为1和5的情况；・应用KMP算法求子串”abaabcac”在主串"acabaabaabcacaabc”中的位置，测试起始位置分别为1,10的情况，并写出子串的next□值；exp4_2.c部分代码如下：#include#includedefineMAXSIZE100defineERROR0defineOK1/*串的定长顺序存储表示*/typedefstruct{chardata[MAXSIZE]；intlength；}SqString；intstrCreate(SqString*s)；intindexBf(SqString*s,SqString*t,intpos)；/*串的模式匹配BF*/voidgetNext(SqString*t,intnext[])；/*KMP求next值*/intindexKmp(SqString*s,SqString*t,intstart,intnext[])；/*串的模式匹配KMP*//*生成一个串*/intstrCreate(SqString*s)(printf(Hinputstring:")；gets(s->data)；s^length=strlen(s->data)；returnOK；}/*strCreate*//*(1)—一串的模式匹配BF*/intindexBf(SqString*stSqString*t,intpos){inti=pos-l,j=0；while(ilength&&jlength)(if(s->data[i]==t->data[j])(i++;j++；1/1文档可自由编辑1/1文档可自由编辑}else(i=i-j+l；j=0；}}if(j>=t->length)(returni-t->length+l；}else(return0；}}/*index_bf*//*(2)-—KMP求next值*/voidgetNext(SqString*t,intnext[])(inti=0J=-l；next[0]=-l；while(ilength)if((j==T)I(t->data[i]==t->data[j]))j++；i++;next[i]=j；}else(j=next[j]；}}}/*getNext*//*(3)-―KMP模式匹配*/intindexKmp(SqString*s,SqString*t,intstart,intnext[]){inti=start-l,j=0；while(ilength&&jlength)(if(j==-l|s->data[i]==t->data[j])i++;j++；}else(产next[j]；)}if(j>=t->length)(returni-t->length+l；}else(return0；}}/*index_kmp*/intmain()(intn,i,pos,next[MAXSIZE]；SqStrings,t；doi/i文档可自由编辑i/i文档可自由编辑printf(n\nString\n")；printf('>1.Index_BF\n'r)；printfC12.INdex_KMP\nu)；printfd0.EXIT\n'r);printf('r\nString\n")；printf(U\ninputchoice：")；scanf("%d",&n)；getchar()；switch(n)case1：printf("\n***showIndex_BF***\n")；printf("s：")；strCreate(&s)；printf("t：")；strCreate(&t)；printf(Hinputstartposition：H)；scanfCr%d'*,&pos)；printfC*BF：indexis%d\nn,indexBf(&s,&t,pos))；break；case2：printf("\n***showIndex_KMP***\nn)；printf("s：")；strCreate(&s)；printf("t：")；strCreate(&t)；printf("inputstartposition：")；scanf(，f%d'*,&pos)；getNext(&t,next)；printf("KMP：\n")；printf("next口：',)；for(i=0；i

                    本文档为【数据结构实验报告-串】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

数据结构实验报告-串

你可能还喜欢