0

次のコードスニペットを検討します。

#include<stdio.h>
#include<conio.h>
#define TABLESIZE 100

sturct record{
       int k;
       int r;
       }table[TABLESIZE];

int tcount=0;

int search_and_insert(int key,int rec){
    int i;
    i=h(key);
    while(table[i].k!=key && table[i].k!=NULL)
                                              i=rh(i);

    if(table[i].key==NULL){
                           table[i].k=key;
                           table[i].r=rec;
                           tcount++;
                           }
    return i;
    }

int h(int key){

    return key%1000;

    } 

int rh(int hkey){

    int k;
    if(hkey==99)
    return 0;
    return ((hkey+1)%1000);

    }

whileテーブルがすでにいっぱいの場合、ループは無限ループになる可能性があります。この問題を解決するために、次のようなステートメントを導入できますif。

   if(tcount<TABLESIZE){
    while(table[i].k!=key && table[i].k!=NULL)
                                              i=rh(i);/*Rehash*/

    if(table[i].key==NULL){
                           table[i].k=key;
                           table[i].r=rec;
                           tcount++;
                         }
}

しかし、私によれば、これは別の問題を引き起こします。つまり、テーブルがいっぱいになると、検索結果が間違った場合に、テーブルにすでに存在するレコードを検索できなくなります。

この問題は解決できますか？

4

2 に答える 2

0

この種の問題の一般的な解決策は連鎖です。これは、ハッシュキーがリンクされた構造を指すようにすることです。

struct h_value
{
  int rec;
  struct h_value *next;
};

挿入するときに、場所を調べて、recが挿入しているものではない場合は、recの次のすべてのポインターを調べ、リストに見つからない場合は、新しいh_valueを作成して最後に追加します。最悪の場合、単一リンクリストが作成されますが、通常の場合、すべてのバケットに値が均等に分散されます。

値を事前に知っている場合は、gperfのような完全なハッシュを調べたいと思うかもしれません。

于 2013-03-26T13:10:15.727 に答える
0

単純な線形プロービングを行っているため、現在のハッシュ値を元のハッシュ値と比較することで、ハッシュテーブルを完全に一周したかどうかを簡単に確認できます。

int h0 = hash(key);
int h = h0;

do {
    if (found_in_bucket(key, h))
        return value_in_bucket(h);
    h = rehash(h);
} while (h != h0);
于 2013-03-26T13:12:56.827 に答える