hhhh还好还好 发表于 2018-10-17 18:03:24

关于KMP算法的一个问题

//准确来说这个问题不是关于KMP算法的，具体问题在代码中的注释




#include <stdio.h>
#include <stdlib.h>
#define max_size 100


typedef struct
{
        char a;
        int length;
}string,*STRING;



void initstring(STRING L)         //初始化L
{
        int i;
        printf("Çëêäèë×Ö·ûêyÄ¿:");
        scanf("%d",&L->length);         //这个是输入长度

        printf("Çëêäèë′yÆ￥Åä′®»òÕßÄ￡ê½′®:");
        for(i=1;i<=L->length;i++)
                scanf("%c",&L->a);      //从a【1】开始进行输入字符
}



void get_next(STRING L2,int next[])
{
        int i=1,j;
        j=0;
        next=0;
        while(i<=L2->length)
        {
                if(j==0||L2->a==L2->a)
                {
                        i++;
                        j++;
                        next=j;
                }
                else
                        j=next;
        }
}







int KMP(STRING L1,STRING L2,int pos,int next[])
{
        int i,j,flag=0;
        i=pos;
        j=1;
        while(i<=L1->length&&j<=L2->length)
        {
                if(j==0||L1->a==L2->a)
                {
                        i++;
                        j++;
                }
                else
                {
                        j=next;
                }
        }
        if(i>L1->a)
        {
                printf("Î′Õòμ½¿éòÔÆ￥ÅäμÄ×Ö·û′®.\n");
                exit(-1);
        }
        else
                returni-L2->a;
}       




int main()
{
        int next;
        int pos,pos1;
        //char ch="abcac";
        STRING L1;
        STRING L2;
        L1=(STRING)malloc(sizeof(string));
        L2=(STRING)malloc(sizeof(string));       //这里我定义2个结构，用initstring分别进行初始化，其中 一个是模板串，另一个是模式串，但是问题就出在这里，我只能对模板串进行初始化，无法对模式串进行初始化，在进行完L1的初始化后
                                                                        执行对L2进行初始化的时候就不允许我进行输入，直接一套流程输出下来。返回的值为未知的。求大佬帮看看问题出在哪里。                                       
        initstring(L1);
//        printf("1\n");
        initstring(L2);
        get_next(L2,next);


        printf("Çëêäèë¿aê¼2éÕòμÄλÖÃ:");
        scanf("%d",&pos);

        pos1=KMP(L1,L2,pos,next);

        printf("′ó%dλÖÿaê¼ÎaÆ￥ÅäμÄ.\n",pos1);
}

claws0n 发表于 2018-10-17 22:03:44

修改指针内容用二级指针#include <stdio.h>
#include <stdlib.h>

#define max_size 100

typedef struct String
{
    char a;
    int length;
}String,*STRING;

void initString(STRING *L)         //3õê¼»ˉL
{
    int i;
    printf("init length:");
    scanf("%d",&(*L)->length);         //Õa¸öêÇêäèë3¤¶è
   
    printf("start key in char:");
    for(i = 1; i <= (*L)->length; i++)
    {
      scanf("%c",&(*L)->a);      //′óa¡¾1¡¿¿aê¼½øDDêäèë×Ö·û
      getchar();
    }
}

void get_next(STRING *L2,int next[])
{
    int i=1,j;
    j = 0;
    next = 0;
    while(i <= (*L2)->length)
    {
      if(j == 0 || (*L2)->a == (*L2)->a)
      {
            i++;
            j++;
            next = j;
      }
      else
            j = next;
    }
}

int KMP(STRING *L1,STRING *L2,int pos,int next[])
{
    int i,j,flag = 0;
    i = pos;
    j = 1;
    while(i <= (*L1)->length && j <= (*L2)->length)
    {
      if(j == 0 || (*L1)->a == (*L2)->a)
      {
            i++;
            j++;
      }
      else
      {
            j = next;
      }
    }
    if(i > (*L1)->a)
    {
      printf("KMP\n");
      exit(-1);
    }
    else
      returni-(*L2)->a;
}      

int main()
{
    int next;
    int pos,pos1;
    //char ch="abcac";
    STRING L1;
    STRING L2;
    L1=(STRING)malloc(sizeof(String));
    L2=(STRING)malloc(sizeof(String));
                                        
    initString(&L1);
    printf("1\n");
    initString(&L2);
    get_next(&L2,next);


    printf("here\n:");
    scanf("%d", &pos);

    pos1=KMP(&L1,&L2,pos,next);

    printf("there\n",pos1);
    return 0;
}

hhhh还好还好 发表于 2018-10-17 23:27:13

claws0n 发表于 2018-10-17 22:03
修改指针内容用二级指针

很感谢你的回复，但是还是没有解决问题，在初始化第二个串的时候还是出错。表现为无法继续输入。

claws0n 发表于 2018-10-17 23:29:47

hhhh还好还好 发表于 2018-10-17 23:27
很感谢你的回复，但是还是没有解决问题，在初始化第二个串的时候还是出错。表现为无法继续输入。

你的还是我的？我加了 getchar() 吸收回车，尤其是循环内用 scanf()，特别敏感
页: [1]
查看完整版本: 关于KMP算法的一个问题