实验四串
【实验目的】
1、掌握串的存储
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示及基本操作;
2、掌握串的两种模式匹配算法:BF和KMP。
3、了解串的应用。
【实验学时】
2学时
【实验预习】
回答以下问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
:
1、串和子串的定义
串的定义:串是由零个或多个任意字符组成的有限序列。
子串的定义:串中任意连续字符组成的子序列称为该串的子串。
2、串的模式匹配
串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串,从主串s的第start个字符开始查找等于子串t的过程称为模式匹配,如果在S中找到等于t的子串,则称匹配成功,函数返回t在s中首次出现的存储位置(或序号);否则,匹配失败,返回0。
【实验内容和要求】
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
#include
#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,s1length&&ilength;i++)
{
if(s1->data[i]>s2->data[i])
{
return 1;
}
if(s1->data[i]data[i])
{
return -1;
}
}
return 0;
}/*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;idata[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(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;
return OK;
}/*strConcat*/
int main()
{
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 stringsecond 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);
else
printf("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);
else
printf("Concat ERROR!\n");
break;
case 0:
exit(0);
default:
break;
}
}
while(n);
return 0;
}2、按照要求完成程序exp4_2.c,实现BF&KMP串的模式匹配算法。调试及测试数据并给出结果:
?应用BF算法求子串”JING”在主串”BEIJING”中的位置,测试起始位置分别为1和5的情况;
?应用KMP算法求子串”abaabcac”在主串”acabaabaabcacaabc”中的位置,测试起始位置分别为1,10的情况,并写出子串的next[]值;
exp4_2.c部分代码如下:
#include
#include
#define MAXSIZE 100
#define ERROR 0
#define OK 1
/*串的定长顺序存储表示*/
typedef struct
{
char data[MAXSIZE];
int length;
} SqString;
int strCreate(SqString *s);
int indexBf(SqString *s,SqString *t,int pos); /*串的模式匹配BF*/
void getNext(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 *s,SqString *t,int pos)
{
int i=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)
{
return i-t->length+1;
}
else
{
return 0;
}
}/*index_bf*/
/*(2)---KMP求next值*/
void getNext(SqString *t,int next[])
{
int i=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模式匹配*/
int indexKmp(SqString *s,SqString *t,int start,int next[]) {
int i=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)
{
return i-t->length+1;
}
else
{
return 0;
}
}/*index_kmp*/
int main()
{
int n,i,pos,next[MAXSIZE];
SqString s,t;
{
printf("\n ---String--- \n");
printf(" 1. Index_BF\n");
printf(" 2. INdex_KMP\n");
printf(" 0. EXIT\n");
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:");
scanf("%d",&pos);
printf("BF:index is %d\n",indexBf(&s,&t,pos));
break;
case 2:
printf("\n***show Index_KMP***\n");
printf(" s:");
strCreate(&s);
printf(" t:");
strCreate(&t);
printf("input start position:");
scanf("%d",&pos);
getNext(&t,next);
printf("KMP:\n");
printf("next[]:");
for(i=0; i
本文档为【数据结构实验报告-串】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483