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

数据结构实验报告-串

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

精品资料实验四串【实验目的】1、掌握串的存储表示及基本操作；2、掌握串的两种模式匹配算法：BF和KMP。3、了解串的应用。【实验学时】2学时【实验预习】回答以下问题：1、串和子串的定义串的定义：串是由零个或多个任意字符组成的有限序列。子串的定义：串中任意连续字符组成的子序列称为该串的子串。2、串的模式匹配串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串，从主串s的第start个字符开始查找等于子串t的过程称为模式匹配，如果在S中找到等于t的子串，则称匹配成功，函数返回t在s中首次出现的存储位置（或序号）；否则，匹配失败，返回0。【实验内容和要求】1、按照要求完成程序exp4_1.c，实现串的相关操作。调试并运行如下测试数据给出运行结果：求“Thisisaboy”的串长；比较”abc3”和“abcde“；表示空格比较”english”和“student“；比较”abc”和“abc“；截取串”white”，起始2，长度2；截取串”white”，起始1，长度7；截取串”white”，起始6，长度2；连接串”asddffgh”和”12344”；#include#include#defineMAXSIZE100#defineERROR0#defineOK1/*串的定长顺序存储表示*/typedefstruct{chardata[MAXSIZE];intlength;/*初始化串*/}SqString;intstrInit(SqString*s);intstrCreate(SqString*s);/*生成一个串*/intstrLength(SqString*s);/*求串的长度*/intstrCompare(SqString*s1,SqString*s2);/*两个串的比较*/intsubString(SqString*sub,SqString*s,intpos,intlen);/*求子串*/intstrConcat(SqString*t,SqString*s1,SqString*s2);/*两个串的连接*//*初始化串*/intstrInit(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，s1length&&ilength;i++){if(s1->data[i]>s2->data[i]){return1;}if(s1->data[i]data[i]){return-1;}}return0;}/*strCompare*//*(3)---求子串，sub为返回的子串，pos为子串的起始位置，intsubString(SqString*sub,SqString*s,intpos,intlen){inti;if(pos<1||pos>s->length||len<0||len>s->length-pos+1){returnERROR;}sub->length=0;for(i=0;idata[i]=s->data[i+pos-1];sub->length++;}sub->data[i]='\0';returnOK;}/*subString*/len为子串的长度*/t中*//*(4)---两个串连接，s2连接在s1后，连接后的结果串放在intstrConcat(SqString*t,SqString*s1,SqString*s2){inti=0,j=0;while(ilength){t->data[i]=s1->data[i];i++;}while(jlength){t->data[i++]=s2->data[j++];}t->data[i]='\0';t->length=s1->length+s2->length;returnOK;}/*strConcat*/intmain(){intn,k,pos,len;SqStrings,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("\ninputchoice:");scanf("%d",&n);getchar();switch(n){case1:printf("\n***showstrLength***\n");strCreate(&s);printf("strLengthis%d\n",strLength(&s));break;case2:printf("\n***showstrCompare***\n");strCreate(&s);strCreate(&t);精品资料k=strCompare(&s,&t);/*(5)---调用串比较函数比较s，t*/if(k==0)printf("twostringequal!\n");elseif(k<0)printf("firststringsecondstring!\n");break;case3:printf("\n***showsubString***\n");strCreate(&s);printf("inputsubstringpos,len:");scanf("%d,%d",&pos,&len);if(subString(&t,&s,pos,len))printf("subStringis%s\n",t.data);elseprintf("posorlenERROR!\n");break;case4:printf("\n***showsubConcat***\n");strCreate(&s);strCreate(&t);if(strConcat(&x,&s,&t))/*(6)---调用串连接函数连接s&t*/printf("Concatstringis%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#include#defineMAXSIZE100#defineERROR0#defineOK1/*串的定长顺序存储表示*/typedefstruct{chardata[MAXSIZE];intlength;}SqString;intstrCreate(SqString*s);intindexBf(SqString*s,SqString*t,intpos);/*串的模式匹配BF*/voidgetNext(SqString*t,intnext[]);/*KMP求next值*/KMP*/intindexKmp(SqString*s,SqString*t,intstart,intnext[]);/*串的模式匹配/*生成一个串*/intstrCreate(SqString*s){printf("inputstring:");gets(s->data);{returni-t->length+1;精品资料s->length=strlen(s->data);精品资料returnOK;}/*strCreate*//*(1)---串的模式匹配BF*/intindexBf(SqString*s,SqString*t,intpos){inti=pos-1,j=0;while(ilength&&jlength){if(s->data[i]==t->data[j]){i++;j++;}else{i=i-j+1;j=0;}}if(j>=t->length)}else{return0;}}/*index_bf*//*(2)---KMP求next值*/voidgetNext(SqString*t,intnext[]){inti=0,j=-1;next[0]=-1;while(ilength){if((j==-1)||(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-1,j=0;while(ilength&&jlength){if(j==-1||s->data[i]==t->data[j]){i++;j++;}else{j=next[j];}}if(j>=t->length)精品资料{returni-t->length+1;}else{return0;}}/*index_kmp*/intmain(){intn,i,pos,next[MAXSIZE];SqStrings,t;do{printf("\n---String---\n");printf("1.Index_BF\n");printf("2.INdex_KMP\n");printf("0.EXIT\n");printf("\n---String---\n");精品资料printf("\ninputchoice:");scanf("%d",&n);getchar();switch(n){case1:printf("\n***showIndex_BF***\n");printf("s:");strCreate(&s);printf("t:");strCreate(&t);printf("inputstartposition:");scanf("%d",&pos);printf("BF:indexis%d\n",indexBf(&s,&t,pos));break;case2:printf("\n***showIndex_KMP***\n");printf("s:");strCreate(&s);printf("t:");strCreate(&t);printf("inputstartposition:");scanf("%d",&pos);getNext(&t,next);printf("KMP:\n");printf("next[]:");for(i=0;i

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

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

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

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

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

立即下载

数据结构实验报告-串

你可能还喜欢