current position:Home>Hash tables store strings using open addressing

Hash tables store strings using open addressing

2022-02-03 02:05:26 CSDN Q & A

All the codes are attached below , Build the project with the following files , There is no problem with integer type storage , But you can't save the string , here we are strcpy The function can't run if it copies the string to the hash table , May be Element The type of is not written correctly , How stupid , It's been two days and I don't know how to change it , I hope someone can correct , It's best to give a specific solution .

hashquad.c

              #include "fatal.h"        #include "hashquad.h"        #include <stdlib.h>        #include <string.h>        #include "fashfunc.c"                #define MinTableSize (10)        enum KindOfEntry { Legitimate, Empty, Deleted };        struct HashEntry        {            ElementType  Element[10];            enum KindOfEntry Info;        };        typedef struct HashEntry Cell;        /* Cell *TheCells will be an array of */        /* HashEntry cells, allocated later */        struct HashTbl        {            int TableSize;            Cell *TheCells;        };        /* Return next prime; assume N >= 10 */        static int NextPrime( int N ) // Generate prime numbers  {            int i;            if( N % 2 == 0 )                N++;            for( ; ; N += 2 )            {                for( i = 3; i * i <= N; i += 2 )                    if( N % i == 0 )                        goto ContOuter;  /* Sorry about this! */                return N;              ContOuter: ;            }        }/* START: fig5_15.txt */        HashTable InitializeTable( int TableSize ) // Initialize hash table  {            HashTable H;            int i,j;/* 1*/      if( TableSize < MinTableSize )            {/* 2*/          Error( "Table size too small" );/* 3*/          return NULL;            }            /* Allocate table *//* 4*/      H = malloc( sizeof( struct HashTbl ) );/* 5*/      if( H == NULL )/* 6*/          FatalError( "Out of space!!!" );/* 7*/      H->TableSize = NextPrime( TableSize );            /* Allocate array of Cells *//* 8*/      H->TheCells = malloc( sizeof( Cell ) * H->TableSize );/* 9*/      if( H->TheCells == NULL )/*10*/          FatalError( "Out of space!!!" );/*11*/      for( i = 0; i < H->TableSize; i++ )/*12*/      {                     H->TheCells[ i ].Info = Empty;            }            /*13*/      return H;        }/* END *//* START: fig5_16.txt */        Position Find( ElementType *Key, HashTable H ) {            Position CurrentPos;            int CollisionNum;/* 1*/      CollisionNum = 0;/* 2*/      CurrentPos = Hash1( Key, H->TableSize );/* 3*/      while( H->TheCells[ CurrentPos ].Info != Empty&&            strcmp(H->TheCells[ CurrentPos ].Element,Key)!=0 )                            /* Probably need strcmp!! */            {                    printf("%s\t The first %d Insert failed --- Location %d\n",Key,CollisionNum+1,CurrentPos);/* 4*/          CurrentPos += 2 * ++CollisionNum - 1;/* 5*/          if( CurrentPos >= H->TableSize )/* 6*/              CurrentPos -= H->TableSize;            }/* 7*/      return CurrentPos;        }/* END *//* START: fig5_17.txt */        void Insert( ElementType *Key, HashTable H ) {            Position Pos;            Pos = Find( Key, H );            if( H->TheCells[ Pos ].Info != Legitimate )            {                /* OK to insert here */                H->TheCells[ Pos ].Info = Legitimate;                strcpy( Key , H->TheCells[ Pos ].Element );                         /* Probably need strcpy! */                printf("%s\t Insertion position %d\n",H->TheCells[Pos].Element,Pos);            }        }/* END */        void DestroyTable( HashTable H ) {            free( H->TheCells );            free( H );        }

fashfunc.c

/* Here are some of the hash functions *//* for strings that are in the text */typedef unsigned int Index;/* START: fig5_3.txt */        Index Hash1( const char *Key, int TableSize ) {            unsigned int HashVal = 0;/* 1*/      while( *Key != '\0' )/* 2*/          HashVal += *Key++;/* 3*/      return HashVal % TableSize;        }/* END *//* START: fig5_4.txt */        Index Hash2( const char *Key, int TableSize ) {            return ( Key[ 0 ] + 27 * Key[ 1 ] + 729 * Key[ 2 ] )                        % TableSize;        }/* END *//* START: fig5_5.txt */        Index Hash3( const char *Key, int TableSize ) {            unsigned int HashVal = 0;/* 1*/      while( *Key != '\0' )/* 2*/          HashVal = ( HashVal << 5 ) + *Key++;/* 3*/      return HashVal % TableSize;        }/* END */

testhash.c

#define QuadProb /* Define the appropriate hash algorithm */#ifdef QuadProb    #include "hashquad.h"#endif#include <stdio.h>#define NumItems 400char *MyBirds[13]={ "robin", "sparrow", "hawk", "eagle", "seagull", "bluejay", "owl", "cardinal", "Jakana", "Moa", "Egret", "Penguin", "hawk" };main( ){    HashTable H; // Position P;    int i;    int j = 0;    int CurrentSize;    for(i=0;i<13;i++)    {        printf("%s\n",MyBirds[i]);    }            H = InitializeTable( CurrentSize = 26 );    for(i=0;i<13;i++)        Insert(MyBirds[i],H);    printf("\n The insertion is complete \n");    return 0;}

hashquad.h

/* Interface for quadratic probing hash table */typedef char ElementType;/* START: fig5_14.txt */        #ifndef _HashQuad_H        #define _HashQuad_H        typedef unsigned int Index;        typedef Index Position;        struct HashTbl;        typedef struct HashTbl *HashTable;        HashTable InitializeTable( int TableSize );        void DestroyTable( HashTable H );        Position Find( ElementType *Key, HashTable H );        void Insert( ElementType *Key, HashTable H );        ElementType Retrieve( Position P, HashTable H );        HashTable Rehash( HashTable H );        /* Routines such as Delete are MakeEmpty are omitted */        #endif /* _HashQuad_H *//* END */

fatal.h

#include <stdio.h>#include <stdlib.h>#define Error( Str ) FatalError( Str )#define FatalError( Str ) fprintf( stderr, "%s\n", Str ), exit( 1 )



Refer to the answer 1:

C++ Words , String can be used string
C Language , Can only char * Add dynamic application memory




Refer to the answer 2:



Refer to the answer 3:

ok , I put this strcpy The function parameter is written backwards




Refer to the answer 4:

copyright notice
author[CSDN Q & A],Please bring the original link to reprint, thank you.
https://en.primo.wiki/2022/02/202202030205235308.html

Random recommended