数据结构实验报告-串.doc

《数据结构实验报告-串.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

2、的存储位置（或序号）；否则，匹配失败，返回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

3、#defineMAXSIZE100#defineERROR0#defineOK1/*串的定长顺序存储表示*/9《数据结构与算法》实验指导V2016typedefstruct{chardata[MAXSIZE];intlength;}SqString;intstrInit(SqString*s);/*初始化串*/intstrCreate(SqString*s);/*生成一个串*/intstrLength(SqString*s);/*求串的长度*/intstrCompare(SqString*s1,SqString*s2);/*两

4、个串的比较*/intsubString(SqString*sub,SqString*s,intpos,intlen);/*求子串*/intstrConcat(SqString*t,SqString*s1,SqString*s2);/*两个串的连接*//*初始化串*/intstrInit(SqString*s){s->length=0;s->data[0]='';returnOK;}/*strInit*//*生成一个串*/intstrCreate(SqString*s){printf("inputstring:");gets

5、(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->

6、data[i]>s2->data[i]){9《数据结构与算法》实验指导V2016return1;}if(s1->data[i]data[i]){return-1;}}return0;}/*strCompare*//*（3）---求子串，sub为返回的子串，pos为子串的起始位置，len为子串的长度*/intsubString(SqString*sub,SqString*s,intpos,intlen){inti;if(pos<1

7、

8、pos>s->length

9、

10、len<0

11、

12、len>s->length-pos+1){

13、returnERROR;}sub->length=0;for(i=0;idata[i]=s->data[i+pos-1];sub->length++;}sub->data[i]='';returnOK;}/*subString*//*（4）---两个串连接，s2连接在s1后，连接后的结果串放在t中*/intstrConcat(SqString*t,SqString*s1,SqString*s2){inti=0,j=0;while(ilength){t->data[i]=s1->dat

14、a[i];i++;}while(jlength){t->data[i++]=s2->data[j++];}t->data[i]='';t->length=s1->length+s2->length;returnOK;9《数据结构与算法》实验指导V2016}/*s