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(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。