快捷導(dǎo)航

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之模式匹配字符串定位問題

更新時(shí)間：2017年10月31日 09:48:20 作者：llcomeon1_

這篇文章主要介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之模式匹配字符串定位問題的相關(guān)資料,希望通過(guò)本文能幫助到大家，讓大家理解這部分內(nèi)容，需要的朋友可以參考下

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之模式匹配字符串定位問題

主要實(shí)現(xiàn)了三種字符串的模式匹配，主要包括字符串子操作的集合，字符串指針回溯，和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

函數(shù)實(shí)現(xiàn)

#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 ;
}

測(cè)試匹配函數(shù)

#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 ;//驗(yàn)證StrIndex1()
  Sstring sub ;
  StrAssign( str1 , "shfiodshfdghafhs" ) ;
  StrAssign( sub , "dgh" ) ;
  int i = StrIndex1( str1 , sub , 1 ) ;
  printf( "%d\n" , i ) ;*/
  /*Sstring str1 ;//驗(yàn)證StrIndex2()
  Sstring sub ;
  StrAssign( str1 , "shfiodshfdghafhs" ) ;
  StrAssign( sub , "dgh" ) ;
  int i = StrIndex2( str1 , sub , 1 ) ;
  printf( "%d\n" , i ) ;*/
  Sstring str1 ;//驗(yàn)證StrIndex3()
  Sstring sub ;
  StrAssign( str1 , "shfiodshfdghafhs" ) ;
  StrAssign( sub , "dgh" ) ;
  int i = StrIndex3( str1 , sub , 1 ) ;
  printf( "%d\n" , i ) ;
  return 0;
}

如有疑問請(qǐng)留言或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！

您可能感興趣的文章: