C语言数据结构之如何解决模式匹配字符串定位问题
这篇文章主要为大家展示了“C语言数据结构之如何解决模式匹配字符串定位问题”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“C语言数据结构之如何解决模式匹配字符串定位问题”这篇文章吧。
创新互联建站于2013年开始，先为武山等服务建站，武山等地企业，进行企业商务咨询服务。为武山企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。
主要实现了三种字符串的模式匹配，主要包括字符串子操作的集合，字符串指针回溯，和KMP算法
头文件
#ifndef INDEXHEAD_H_INCLUDED #define INDEXHEAD_H_INCLUDED #include#include #include #define MAXLEN 255 typedef char Sstring[MAXLEN + 1] ; int StrAssign( Sstring str , char* ps ) ; int StrLength( Sstring str ) ; int StrPrint( Sstring str ) ; int StrCompare( Sstring str1 , Sstring str2 ) ; int StrSub( Sstring sub , Sstring str , int pos , int length ) ; int StrIndex1( Sstring str , Sstring sub , int pos ) ; int StrIndex2( Sstring str , Sstring sub , int pos ) ; int StrIndex3( Sstring str , Sstring sub , int pos ) ; int GetNext( Sstring str , int next[] ) ; #endif // INDEXHEAD_H_INCLUDED
函数实现
#include "indexhead.h"
int StrAssign( Sstring str , char* ps )
{
int i = 0 ;
if( strlen( ps ) > MAXLEN )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
str[i++] = strlen( ps ) ;
while( i <= strlen( ps ) )
{
str[i] = *( ps + i - 1 ) ;
i++ ;
}
return 0 ;
}
int StrPrint( Sstring str )
{
int i = 1 ;
while( i <= str[0] )
{
printf( "%c" , str[i++] ) ;
}
printf( "\n" ) ;
return 0 ;
}
int StrLength( Sstring str )
{
return str[0] ;
}
int StrCompare( Sstring str1 , Sstring str2 )
{
int i = 1 ;
int ret = 0 ;
while( i <= str1[0] && i <= str2[0] )
{
ret = ( unsigned char )str1[i] - ( unsigned char )str2[i] ;
if( ret < 0 )
{
return -1 ;
}
else if( ret > 0 )
{
return 1 ;
}
else
{
i++ ;
}
}
if( i <= str1[0] )
{
return -1 ;
}
else if( i <= str2[0] )
{
return 1 ;
}
else
{
return 0 ;
}
}
int StrSub( Sstring sub , Sstring str , int pos , int length )
{
if( pos < 1 || pos > str[0] || length < 0 || length > str[0] - pos + 1 )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
int i = 1 ;
sub[0] = length ;
while( i <= length )
{
sub[i] = str[pos + i - 1] ;
i++ ;
}
return 0 ;
}
int StrIndex1( Sstring str , Sstring sub , int pos )
{
pos = 1 ;
Sstring stemp ;
while( pos <= str[0] - sub[0] + 1 )
{
StrSub( stemp , str , pos , sub[0] ) ;
if( !StrCompare( stemp , sub ) )
{
return pos ;
}
pos++ ;
}
return 0 ;
}
int StrIndex2( Sstring str , Sstring sub , int pos )
{
if( pos < 1 || pos > str[0] - sub[0] + 1 )
{
printf( "ERROR!\n" ) ;
exit( 1 ) ;
}
int i = pos ;
int j = 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] )
{
return i - sub[0] ;
}
return 0 ;
}
int GetNext( Sstring str , int next[] )
{
int i = 1 ;
next[1] = 0 ;
int j = 0 ;
while( i < str[0] )
{
if( j== 0 || str[i] == str[j] )
{
++i ;
++j ;
next[i] = j ;
}
else
{
j = next[j] ;
}
}
return 0 ;
}
int StrIndex3( Sstring str , Sstring sub , int pos )
{
int i = pos ;
int j = 1 ;
int next[ sub[0] ] ;
GetNext( sub , next ) ;
while( i <= str[0] && j <= sub[0] )
{
if( j == 0 || str[i] == sub[j] )
{
++i ;
++j ;
}
else
{
j = next[j] ;
}
}
if( j > sub[0] )
{
return i - sub[0] ;
}
return 0 ;
} 测试匹配函数
#include "indexhead.h"
int main()
{
/*Sstring str ;
Sstring str1 ;
char* p = "hello" ;
StrAssign( str , p ) ;
StrAssign( str1 , "ahello" ) ;
StrPrint( str ) ;
int i = StrLength( str ) ;
printf( "%d\n" , i ) ;
int j = StrCompare( str , str1 ) ;
printf( "%d\n" , j ) ;
StrSub( str , str1 , 3 , 4 ) ;
StrPrint( str ) ;*/
/*Sstring str1 ;//验证StrIndex1()
Sstring sub ;
StrAssign( str1 , "shfiodshfdghafhs" ) ;
StrAssign( sub , "dgh" ) ;
int i = StrIndex1( str1 , sub , 1 ) ;
printf( "%d\n" , i ) ;*/
/*Sstring str1 ;//验证StrIndex2()
Sstring sub ;
StrAssign( str1 , "shfiodshfdghafhs" ) ;
StrAssign( sub , "dgh" ) ;
int i = StrIndex2( str1 , sub , 1 ) ;
printf( "%d\n" , i ) ;*/
Sstring str1 ;//验证StrIndex3()
Sstring sub ;
StrAssign( str1 , "shfiodshfdghafhs" ) ;
StrAssign( sub , "dgh" ) ;
int i = StrIndex3( str1 , sub , 1 ) ;
printf( "%d\n" , i ) ;
return 0;
}以上是“C语言数据结构之如何解决模式匹配字符串定位问题”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注创新互联行业资讯频道！
网页名称：C语言数据结构之如何解决模式匹配字符串定位问题
文章源于：http://6mz.cn/article/jcepos.html