C语言数据结构之模式匹配字符串定位问题分享

—-想了解C语言数据结构之模式匹配字符串定位问题分享的全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>

C语言数据结构之模式匹配字符串定位问题

 主要实现了三种字符串的模式匹配，主要包括字符串子操作的集合，字符串指针回溯，和KMP算法 

头文件 

  #ifndef INDEXHEAD_H_INCLUDED  #define INDEXHEAD_H_INCLUDED  #include <stdio.h>  #include <stdlib.h>  #include <string.h>  #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( "%dn" , i ) ;    int j = StrCompare( str , str1 ) ;    printf( "%dn" , 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( "%dn" , i ) ;*/    /*Sstring str1 ;//验证StrIndex2()    Sstring sub ;    StrAssign( str1 , "shfiodshfdghafhs" ) ;    StrAssign( sub , "dgh" ) ;    int i = StrIndex2( str1 , sub , 1 ) ;    printf( "%dn" , i ) ;*/    Sstring str1 ;//验证StrIndex3()    Sstring sub ;    StrAssign( str1 , "shfiodshfdghafhs" ) ;    StrAssign( sub , "dgh" ) ;    int i = StrIndex3( str1 , sub , 1 ) ;    printf( "%dn" , i ) ;    return 0;  }    

如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！