实验---数据结构中字符串的匹配问题

2018-06-17 23:36:24来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

【问题描述】对任意输入的一串字符,在某文档中进行匹配,并给出匹配结果。

【测试数据】

1)输入的一行程序,与源代码匹配,源程序自行选择;

2)输入的一串字符,在某文本文件中匹配,文本文件自行选择。

#include <stdio.h>    
#include "stdlib.h"  
#include <iostream>  
#include<fstream>
using namespace std;  
  
//宏定义      
#define TRUE   1      
#define FALSE   0      
#define OK    1      
#define ERROR   0    
  
#define  MAXSTRLEN 100  
typedef char  SString[MAXSTRLEN + 1];
/*
***************
**     字符串的匹配
**     @autho  刘辉
**     @time   2016年11月7日
***************
*/

  

int length(SString S)                   //计算字符数组的长度
{
    int i=0;
    while(S[i]!='\0')
        i++;
    return i;
}
/*
***********************************************************************
存放长度change()


1、将字符串的长度存到字符数组的第一个字符位
2、不能返回一个字符数组,定义一个字符指针指向数组,返回指针
3、注意的是长度的类型是int ,这里存到字符数组中之后会进行自动转码
   但如果要使用的时候要进行强制类型转化
4、这里我设置的字符数组的长度没有加上首字符的空间
***********************************************************************
*/

char *change(SString S)                //将字符的长度存到字符数组的第一个字符位S[0]
{
    int i = 0;
    char *p;
    for(i=length(S);i>=0;i--)
        S[i+1] = S[i];
    S[0] = length(S)-1;
    p = S;
    return p;
}

/*
***********************************************************************
算法的实现 index__BF()

1、BF算法,匹配两个字符串,并返回匹配的字符串首字母所在位置
2、这里参数传递进来的方式是,主函数通过字符指针传递给函数的字符数组接收
3、这里要注意判断条件时的强制类型转换
4、要注意最后的判断条件,长度减一后使用
***********************************************************************
*/

int index__BF(SString S,SString T, int pos)                 //BF算法,匹配两个字符串,并返回匹配的字符串首字母所在位置
{
    if (pos <1 ||  pos > (int)S[0] ) return 0;
    int i = pos, j =1;
    while (i<= (int)S[0]&& j <= (int)T[0])  
    {  
        if (S[i] == T[j])  
        {  
            ++i; ++j;  
        } else {  
            i = i-j+ 2;  
            j = 1;  
        }  
    } 
    if(j > (int)T[0]) return (i - (int)T[0]);  
    return 0;  
}  
  


/*
************************************************************************ 
  求子串next[i]值的算法 
  1、注意算法的使用
  2、这里的if句内包含了很多巧合的实现
/************************************************************************/  
void GetNext(SString T, int next[])  
{   int j = 1, k = 0;  
    next[1] = 0;  
    while(j < (int)T[0]){  
        if(k == 0 || T[j]==T[k]) {     
            ++j;  ++k;   next[j] = k; 

        } else {  
            k = next[k];   
        }  
    } 
}


/*
***************
KMP算法的具体实现
***************
*/
int KMPindex(SString S, SString T, int pos)  
{  
    if (pos <1 ||  pos > (int)S[0] ) exit(ERROR);  
    int i = pos, j =1;  
    int next[MAXSTRLEN];  
    GetNext( T, next);  
    while (i<= (int)S[0] && j <= (int)T[0])  
    {  
        if (S[i] == T[j]||j==0) {  
            ++i; ++j;  
        } else {  
            j = next[j];  
        }  
    } 
    if(j > (int)T[0]) return i - (int)T[0];  
    return ERROR;  
}




/*
*******************************************************
主函数main()


1、以字符数组保存
2、然后建立指针指向经过change()后的数组。
3、再建立字符数组存放指针指向的内容
4、用数组参与到BF算法中
******************************************************
*/

void main(){  
    SString S = "abcacdbadab";
    //或者用SString S = {'a','b','c','a','c','d','b','a','d','a','b'};
    SString S3;
    int i = 0;
    ifstream in("d:/test.txt");               //文件流读取文件内的字符串
    if(!in)
    {
        cout<<"open file error!"<<endl;
    }
    while(in)                                //循环读取数据
    {
        in.get(S3[i]);
        i++;
    }
    in.close();
    S3[i] = '\0';

    SString T ;
    cout<<"请输入要匹配的字符串:";
    cin>>T;
    int pos = 0,pos1 = 0,pos2 = 0;  
    char *p = change(S);
    char *q = change(T);
    char *k = change(S3);
    SString S1,S2,S4;
    for(int i=0;i<length(S)+1;i++)
        S1[i] = p[i];
    for(int i=0;i<length(T)+1;i++)
        S2[i] = q[i];
    for(int i=0;i<length(S3)+1;i++)
        S4[i] = k[i];
    pos = index__BF( S1, S2, 1);  
    pos1 = KMPindex( S1, S2, 1);
    pos2 = KMPindex( S3, S2, 1);
    cout<<"Pos:"<<pos<<endl;
    cout<<"Pos1:"<<pos1<<endl;  
    cout<<"Pos2:"<<pos2<<endl;  

}  

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:c++ __declspec用法解析

下一篇:Codevs 1860 最大数