C语言数据结构之模式匹配字符串定位问题
C语言数据结构之模式匹配字符串定位问题
主要实现了三种字符串的模式匹配，主要包括字符串子操作的集合，字符串指针回溯，和KMP算法
头文件
#ifndefINDEXHEAD_H_INCLUDED #defineINDEXHEAD_H_INCLUDED #include#include #include #defineMAXLEN255 typedefcharSstring[MAXLEN+1]; intStrAssign(Sstringstr,char*ps); intStrLength(Sstringstr); intStrPrint(Sstringstr); intStrCompare(Sstringstr1,Sstringstr2); intStrSub(Sstringsub,Sstringstr,intpos,intlength); intStrIndex1(Sstringstr,Sstringsub,intpos); intStrIndex2(Sstringstr,Sstringsub,intpos); intStrIndex3(Sstringstr,Sstringsub,intpos); intGetNext(Sstringstr,intnext[]); #endif//INDEXHEAD_H_INCLUDED
函数实现
#include"indexhead.h"
intStrAssign(Sstringstr,char*ps)
{
inti=0;
if(strlen(ps)>MAXLEN)
{
printf("ERROR!\n");
exit(1);
}
str[i++]=strlen(ps);
while(i<=strlen(ps))
{
str[i]=*(ps+i-1);
i++;
}
return0;
}
intStrPrint(Sstringstr)
{
inti=1;
while(i<=str[0])
{
printf("%c",str[i++]);
}
printf("\n");
return0;
}
intStrLength(Sstringstr)
{
returnstr[0];
}
intStrCompare(Sstringstr1,Sstringstr2)
{
inti=1;
intret=0;
while(i<=str1[0]&&i<=str2[0])
{
ret=(unsignedchar)str1[i]-(unsignedchar)str2[i];
if(ret<0)
{
return-1;
}
elseif(ret>0)
{
return1;
}
else
{
i++;
}
}
if(i<=str1[0])
{
return-1;
}
elseif(i<=str2[0])
{
return1;
}
else
{
return0;
}
}
intStrSub(Sstringsub,Sstringstr,intpos,intlength)
{
if(pos<1||pos>str[0]||length<0||length>str[0]-pos+1)
{
printf("ERROR!\n");
exit(1);
}
inti=1;
sub[0]=length;
while(i<=length)
{
sub[i]=str[pos+i-1];
i++;
}
return0;
}
intStrIndex1(Sstringstr,Sstringsub,intpos)
{
pos=1;
Sstringstemp;
while(pos<=str[0]-sub[0]+1)
{
StrSub(stemp,str,pos,sub[0]);
if(!StrCompare(stemp,sub))
{
returnpos;
}
pos++;
}
return0;
}
intStrIndex2(Sstringstr,Sstringsub,intpos)
{
if(pos<1||pos>str[0]-sub[0]+1)
{
printf("ERROR!\n");
exit(1);
}
inti=pos;
intj=1;
while((i<=str[0]-sub[0]+1)&&(j<=sub[0]))
{
if(str[i]==sub[j])
{
i++;
j++;
}
else
{
i=i-j+2;
j=1;
}
}
if(j>sub[0])
{
returni-sub[0];
}
return0;
}
intGetNext(Sstringstr,intnext[])
{
inti=1;
next[1]=0;
intj=0;
while(isub[0])
{
returni-sub[0];
}
return0;
}
测试匹配函数
#include"indexhead.h"
intmain()
{
/*Sstringstr;
Sstringstr1;
char*p="hello";
StrAssign(str,p);
StrAssign(str1,"ahello");
StrPrint(str);
inti=StrLength(str);
printf("%d\n",i);
intj=StrCompare(str,str1);
printf("%d\n",j);
StrSub(str,str1,3,4);
StrPrint(str);*/
/*Sstringstr1;//验证StrIndex1()
Sstringsub;
StrAssign(str1,"shfiodshfdghafhs");
StrAssign(sub,"dgh");
inti=StrIndex1(str1,sub,1);
printf("%d\n",i);*/
/*Sstringstr1;//验证StrIndex2()
Sstringsub;
StrAssign(str1,"shfiodshfdghafhs");
StrAssign(sub,"dgh");
inti=StrIndex2(str1,sub,1);
printf("%d\n",i);*/
Sstringstr1;//验证StrIndex3()
Sstringsub;
StrAssign(str1,"shfiodshfdghafhs");
StrAssign(sub,"dgh");
inti=StrIndex3(str1,sub,1);
printf("%d\n",i);
return0;
}
如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。