-1

ボイヤームーアホースプールアルゴリズムを実装しようとしています。このコードは、WindowsのTurboC++で記述されています。機能した。これをubuntuに移植する必要があります。

typedef struct skip_table
{
    char index;
    int value;
}skip_table;

void create_table(char*,int);
int discrete_char(char*,int);
int bm(char*, char*);
int lookup(char);
int check_EOF(char*,int);

skip_table *t1;
int tab_len;
FILE *fptr;

int main()
{
    time_t first, second;
    double time_spent;
    long int cnt=0;

    char *key_string,*buf,c; // String to be matched and text
    int i,key_len,text_len,def_shift_len,flag_match=0;

    gets(key_string);
    key_len=strlen(key_string);

    fptr=fopen("test_file.txt","r");
    first = clock();
    fseek(fptr,SEEK_SET,0);
    create_table(key_string,key_len);

    while(flag_match!=1)
    {
        fseek(fptr,100*cnt,0);
        fread(buf,100-key_len-1, 1, fptr);
        flag_match = bm(buf, key_string);
        cnt++;

    printf("\n%d",cnt);
     }
    second =clock();
time_spent=(double)(second-first)/CLOCKS_PER_SEC;

if(flag_match==1)
    printf("\n\nMatch Found in %lf seconds",time_spent);
else
    printf("\n\nMatch NOT Found in %lf seconds",time_spent);

    fclose(fptr);
    return 0;
}

int discrete_char(char* key_string,char* temp,int key_len)
{
    int i,j,count=1,flag=0;

for(i=1;i<key_len;i++)
{
    for(j=0; j<count; j++)
    {
        flag=0;
        if(temp[j] == key_string[i])
        {
            flag=1;
            break;
        }
    }
        if(flag!=1)
        {
            temp[count++]=key_string[i];
            flag=0;
        }
}

temp[count]='\0';
return count;
}

void create_table(char* key_string,int key_len)
{
    int i,j,k,max_index;
char *temp;
temp[0] = key_string[0];

tab_len=discrete_char(key_string,temp,key_len);
t1=(skip_table*)malloc((tab_len-1)*sizeof(skip_table));

for(i=0;i<tab_len;i++)
{
    for(j=0;j<key_len;j++)
    {
        if(temp[i]==key_string[j])
            max_index=j;
    }

    t1[i].index=temp[i];
    t1[i].value=key_len-max_index-1;

    printf("\n\n %c %d",t1[i].index,t1[i].value);
}
}

int bm(char* text, char* key_string)
{
int i_t, i_k, j,k, text_len, key_len, shift, count=0, flag_match=0;
int loop_count;

text_len = strlen(text);
key_len = strlen(key_string);
i_t=key_len;
i_k=key_len;

loop_count=0;

while(i_t<=text_len)
{
    if(count != key_len)
    {
        if(text[i_t-1]==key_string[i_k-1])
        {
            count++;
            i_t--;  i_k--;
            loop_count++;
        }
        else
        {
            if(loop_count>key_len)
            {
                i_t=i_t+lookup(text[i_t-1])+1;
                i_k=key_len;
                loop_count=0;
                continue;
            }
            shift = lookup(text[i_t-1]);
            if(shift<=0)
                shift=key_len;
            i_t = i_t+shift;
            i_k = key_len;
            count=0;
        }
    }
    else
    {
        flag_match =  1;
        break;
    }
}
return flag_match;
}

「intlookup（char index）」は、「temp」に存在する場合はインデックスのそれぞれの値フィールドを返し、それ以外の場合は-1を返します。

私のコード全体があります。

4

2 に答える 2

0

出力が示すように、valgrind オプションでも使用してみて--track-origins=yes ください。これは、初期化されていない変数がどこから来たのかを追跡するのに役立ちます。

他の人が示唆しているように、valgrind が報告している問題は内部create_tableにあるため、そのコードも投稿してください。

于 2013-03-07T08:08:16.230 に答える
0

何がうまくいかなかったのかを正確に把握しているわけではありませんが、防御的なプログラミングのヒントをいくつか紹介します。

int main()
{
  // initialize all variables before use
  time_t first = 0, second = 0;
  double time_spent = 0.0;
  long int cnt=0;

  char *key_string = NULL;
  char *buf = NULL;
  char  c = '\0';  
  char temp[50] = {0};
  int i = 0,key_len=0,text_len=0,def_shift_len=0,flag_match=0;

// use fgets instead of gets, fgets allows you specify max length

  fgets(temp,sizeof(temp),stdin);
  key_len=strlen(temp);
  key_string = (char*) malloc(key_len+1);

// use strncpy or strcpy_s to specify max size
  strncpy(key_string, temp, sizeof(key_string));

  fptr = fopen("test_file.txt","r");

  first = clock();

// here arguments have wrong order, fseek takes origin as last arg:
  fseek(fptr,0,SEEK_SET);

// could be something in create_table, but you have not supplied it
  create_table(key_string,key_len);

関数に非常に多くの変数がある場合、関数の一部を他の関数に移動することを検討できます。

于 2013-03-07T05:54:55.910 に答える