6-4線形検出法の検索関数(ハッシュテーブル)

6-4 線形検出法の検索関数(20 点)
線形検出法の検索関数を試してみます.
関数インターフェースの定義:

Position Find( HashTable H, ElementType Key );

HashTableはオープン・アドレス・フリーリストであり、以下のように定義される.

#define MAXTABLESIZE 100000  /*              */
typedef int ElementType;     /*          */
typedef int Index;           /*        */
typedef Index Position;      /*                  */
/*         ，    ：     、   、       */
typedef enum { Legitimate, Empty, Deleted } EntryType;

typedef struct HashEntry Cell; /*         */
struct HashEntry{
    ElementType Data; /*      */
    EntryType Info;   /*      */
};

typedef struct TblNode *HashTable; /*       */
struct TblNode {   /*         */
    int TableSize; /*        */
    Cell *Cells;   /*             */
};

関数Findは、審判によって定義されたハッシュ関数Hash( Key, H->TableSize )に従って、ハッシュリストHからKeyの位置を調べて返されるべきである.Keyが存在しない場合、線形検出法によって発見された最初の空単位の位置に戻る.空のセルがない場合はERRORに戻る.
審判試験手順の例:

#include 

#define MAXTABLESIZE 100000  /*              */
typedef int ElementType;     /*          */
typedef int Index;           /*        */
typedef Index Position;      /*                  */
/*         ，    ：     、   、       */
typedef enum { Legitimate, Empty, Deleted } EntryType;

typedef struct HashEntry Cell; /*         */
struct HashEntry{
    ElementType Data; /*      */
    EntryType Info;   /*      */
};

typedef struct TblNode *HashTable; /*       */
struct TblNode {   /*         */
    int TableSize; /*        */
    Cell *Cells;   /*             */
};

HashTable BuildTable(); /*     ，     */
Position Hash( ElementType Key, int TableSize )
{
    return (Key % TableSize);
}

#define ERROR -1
Position Find( HashTable H, ElementType Key );

int main()
{
    HashTable H;
    ElementType Key;
    Position P;

    H = BuildTable(); 
    scanf("%d", &Key);
    P = Find(H, Key);
    if (P==ERROR)
        printf("ERROR: %d is not found and the table is full.
", Key);
    else if (H->Cells[P].Info == Legitimate)
        printf("%d is at position %d.
", Key, P);
    else
        printf("%d is not found.  Position %d is returned.
", Key, P);

    return 0;
}

/*            */

入力例1:(注:-1はこの位置が空です.以下同じです.)

11
11 88 21 -1 -1 5 16 7 6 38 10
38

出力例1:

38 is at position 9.

入力例2:

11
11 88 21 -1 -1 5 16 7 6 38 10
41

出力例2:

41 is not found.  Position 3 is returned.

入力例3:

11
11 88 21 3 14 5 16 7 6 38 10
41

出力例3:

ERROR: 41 is not found and the table is full.

/*           ，    ：Find                   。   ：    Key           Hash ，           ，   H0，        H0       ==Key   H0       （            ）        （ H0）（          ，Key%  ，            ，             ，                    ，         ，      ；      ，       Key%   ，           ，             ，                  ），       %     ，            ，               ，           （ Hi），                  ，           ,   ERROR.

 /* これはハッシュ表のテーマです.問題を解く構想です.Find関数は私たちが探しているキーワードがあるかどうかを探しに来ます.第1ステップ:キーワードKeyとハッシュテーブルの表を関数Hashに転送してキーワードの位置を見つけ、H 0としてマークし、ハッシュリストのH 0番目の要素が存在し、==KeyまたはH 0番目の要素位置が空である場合(キーワードがハッシュリスト内にないことを証明する)、要素の位置(すなわちH 0)に戻る.(キーワードを探している間に、Key%表が長い、つまりキーワードがリスト内にある位置は、要素が存在する場合は、線形探知で再ハッシュの方法で一度下に位置を探します.ある位置が空いているまで元素を入れます.もし一つの数字であれば、初めてKey%表を作った時に、リスト内の位置が空であることを証明します.この要素はまったく存在しないので、初めての演算で得られた位置結果に戻ります.%を求めて初めての位置を求める場合、空でもないし、探したい元素でもない場合は、線形探知の方法で探し続けます.見つけたら元素の位置(すなわちHi)に戻ります.もし見つけられないなら、初めて演算をする時の位置に戻ります.でないと、この表は空です.ERRORに戻ります.

Position Find( HashTable H, ElementType Key )JI{
	Position H0,Hi;
	int i;
	H0=Hash(Key,H->TableSize);
	if(H->Cells[H0].Data==Key || H->Cells[H0].Info==Empty){
		return H0;
	}
	else{
		for(i=1;iTableSize;i++)
		{
			Hi=(H0+i)%(H->TableSize);
			if(H->Cells[Hi].Info== Empty || H->Cells[Hi].Data==Key)
				return Hi;
		}
		return ERROR;
	}


}