#include
<stdio.h>
#include
<stdlib.h>
#define NumItems
50
#define
MinTableSize 10
struct ListNode
{
int element;
struct ListNode *Next;
};
typedef struct ListNode *Position;
typedef Position List;
/* List
*TheList will be an array of lists, allocated later */
/* The lists
use headers (for simplicity), */
/* though this
wastes space */
struct HashTbl
{
int TableSize;
struct ListNode **TheLists;
};
typedef struct HashTbl *HashTable;
typedef unsigned int Index;
/* Hash
function for ints */
Index Hash( int Key, int TableSize )
{
return Key % TableSize;
}
HashTable InitializeTable( int
TableSize )
{
HashTable H;
int i;
/* 1*/
if( TableSize <
MinTableSize )
{
/* 2*/
printf( "Table
size too small" );
/* 3*/
return NULL;
}
/* Allocate table */
/* 4*/
H = malloc( sizeof( struct HashTbl ) );
/* 5*/
if( H == NULL )
/* 6*/
printf( "Out
of space!!!" );
/* 7*/
H->TableSize = 7;
/* Allocate array of lists */
/* 8*/
H->TheLists = malloc( sizeof(
List ) * H->TableSize );
/* 9*/
if( H->TheLists ==
NULL )
/*10*/
printf( "Out
of space!!!" );
/* Allocate list headers */
/*11*/
for( i = 0; i < H->TableSize; i++ )
{
/*12*/
H->TheLists[ i ] = malloc( sizeof(
struct ListNode ) );
/*13*/
if( H->TheLists[ i ]
== NULL )
/*14*/ printf( "Out of space!!!" );
else
/*15*/ H->TheLists[ i ]->Next =
NULL;
}
/*16*/
return H;
}
Position Find( int Key,
HashTable H )
{
Position P;
List L;
/* 1*/
L = H->TheLists[ Hash( Key, H->TableSize ) ];
/* 2*/
P = L->Next;
/* 3*/
while( P != NULL
&& P->element != Key )
/* Probably need strcmp!! */
/* 4*/
P = P->Next;
/* 5*/
return P;
}
void Insert( int Key, HashTable H )
{
Position Pos, NewCell;
List L;
/* 1*/
Pos = Find( Key, H );
/* 2*/
if( Pos == NULL ) /* Key is not found */
{
/* 3*/
NewCell = malloc( sizeof(
struct ListNode ) );
/* 4*/
if( NewCell == NULL )
/* 5*/ printf( "Out of space!!!" );
else
{
/* 6*/ L = H->TheLists[ Hash( Key,
H->TableSize ) ];
/* 7*/ NewCell->Next = L->Next;
/* 8*/ NewCell->element = Key; /* Probably need strcpy! */
/* 9*/ L->Next = NewCell;
}
}
}
int Retrieve( Position P
)
{
printf("\t %d", P->element);
return P->element;
}
void DestroyTable(
HashTable H )
{
int i;
for( i = 0; i < H->TableSize; i++ )
{
Position P = H->TheLists[ i
];
Position Tmp;
while( P != NULL )
{
Tmp = P->Next;
free( P );
P = Tmp;
}
}
free( H->TheLists );
free( H );
}
/* now show
the contents that were assigned */
void display( HashTable H
)
{
Position P;
List L;
int i;
for ( i = 0; i < H->TableSize; i++)
{
L = H->TheLists[i];
P = L->Next;
int j=0;
while( P != NULL )
{
printf( "\nTheLists[%d][%d] element is
:\t%d",i,j,
P->element );
P = P->Next;
j++;
}
}
}
main( )
{
HashTable H;
Position P;
int i;
int CurrentSize;
H = InitializeTable( CurrentSize = 11 );
for( i = 0; i < NumItems; i++ )
{Insert( i, H );}
printf( "\nThe
following numbers inserted in to the chained hash table whose
size is
7\n");
for( i = 0; i < NumItems; i++ )
if( ( P = Find( i, H ) )
== NULL || Retrieve( P ) != i )
printf( "Error at %d\n", i );
//printf(
"End of program.\n" );
display(H);
return 0;
}
No comments:
Post a Comment