C Program to Implement a Hash Table with chaining

#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;

}
Bhanu Namikaze

Bhanu Namikaze is an Ethical Hacker, Web Developer, Student and Mechanical Engineer. He Enjoys writing articles, Blogging, Solving Errors and Social Networking. Feel Free to let me know any of your concerns about hacking or let me know if you need any more methods on hacking anything. Enjoy Learning

No comments:

Post a Comment