字符串定位 C语言数据结构之模式匹配字符串定位问题
llcomeon1_ 人气:0想了解C语言数据结构之模式匹配字符串定位问题的相关内容吗,llcomeon1_在本文为您仔细讲解字符串定位的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:C语言数据结构之模式匹配字符串,数据结构串的模式匹配,下面大家一起来学习吧。
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( "%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; }
如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
加载全部内容