0

==3139== 条件付きジャンプまたは移動は、初期化されていない値に依存します

==3139== at 0x4A0673F: strcpy (mc_replace_strmem.c:311)

==3139== by 0x400ADB: htable_insert (hashtable.c:56)

==3139== by 0x400F25: メイン (mylib.c:11)

こんにちは、私はまだハッシュテーブルに挿入しようとしています。問題があるかもしれないと思ったからといって、印刷方法を含めました。私は線形プロービングをしようとしています。valgrind を実行すると、このエラーが発生しました。文字列へのコピーに関係していると思いますが、意味がよくわかりません。この時点で、この挿入を機能させる方法が本当にわかりません。いくつかの入力は素晴らしいでしょう..
ハッシュテーブル挿入の56行目はstrcpy(str, key)です

int htable_insert(htable h, char *str) {
   int i;
   /*convert string to integer*/
   unsigned int index = htable_word_to_int(str);
   /*calculate index to insert into hash table*/
   int remainder = index%h->capacity;
   /*once calculated position in the hash table, 3 possibilities occur*/
   /*no string in this positon, copy string to that position, increment number of keys, return 1*/
   if (h->key[remainder] == NULL) {
      char *key = emalloc(strlen(str) + 1);
      strcpy(str, key);
      h->key[remainder] = key;
      h->frequencies[remainder] = 1;
      h->num_keys++;
      return 1;
   }
   /*the exact same string is at the position, increment frequency at that position, return frequency*/
   if (strcmp(str, h->key[remainder]) == 0) {
      h->frequencies[remainder]++;
      return h->frequencies[remainder];
   }/*a string is at that position, but it isnt the rightone, keep moving along the array
      until you find either an open space or the string you are looking for*/
   if (h->key[remainder] != NULL && strcmp(str, h->key[remainder]) != 0) {
      /*you may need to wrap back around to the beginning of the table, so each time you add
        to the position you should also mod by the table capacity.*/
      for (i = 0; i <= h->capacity; i++) {
         /*no string in this positon, copy string to that position, increment number of keys*/
         if (h->key[remainder] == NULL) {
            char *key = emalloc(strlen(str) + 1);
            strcpy(str, key);
            h->key[remainder] = key;
            h->frequencies[remainder] = 1;
            h->num_keys++;
         }
         /*if you find the string you were looking for, increment the frequecny at the position
           and return the frequency*/
         if (strcmp(str, h->key[remainder]) == 0) {
            h->frequencies[remainder]++;
            return h->frequencies[remainder];
         }
         if (h->key[remainder] != NULL && h->capacity ==  i) {
            i = 0;
         }
      }   
   }
   /*if you have kept looking for an open space but there isnt one, the hash table must fu*/
   return 0;
}

void htable_print(htable h, FILE *stream) {
   int i;
   for(i = 0; i < h->capacity; i++) {
      if(h->key[i] != NULL) {
         fprintf(stream, "%d%s\n", h->frequencies[i], h->key[i]);
      }
   }
}
4

1 に答える 1

1

strcpy は strcpy(key, str) である必要があり、その逆ではありません。（strdup、btwを使用して、malloc + strcpyを保存できます）。

また、次の場合: if (h->key[remainder] != NULL && strcmp(str, h->key[remainder]) != 0) {

条件 "h->key[remainder] != NULL" は冗長です: 上記で既に確認済みです。

最後に、ループ (バケツを通過) では、次のようになります。

  1. ループ条件は <= ではなく < にする必要があります
  2. どこかで剰余をインクリメントするか、「remainder+i」と h->keys へのインデックスを使用する必要があります
  3. "capacity==i" --> "i=0" の代わりに、"(remainder+i)%capacity" を h->keys のインデックスとして使用します

..最後に最後に-最初の部分、つまりループの外側にある部分がループ内にある可能性があり、コードを節約できます。

于 2012-08-30T03:17:59.680 に答える