fork download
copy 
  1. #include "stdio.h"
  2. #include "stdlib.h"
  3. #include "math.h"
  4. #include "time.h"
  5.  
  6. #define TRUE 1
  7. #define FALSE !TRUE
  8. #define SIZE_HASH_MAP 10
  9. #define HASH_CONSTANT ((sqrt(5) - 1) / 2)
  10.  
  11. typedef struct node{
  12.     int value;
  13.     struct node *next;
  14. }t_hashTableNode;
  15.  
  16. static t_hashTableNode* hashMapChained[SIZE_HASH_MAP];              // hash table
  17. /* HASH FUNCTIONS */
  18. int hash(int value);                                                /* hash function */
  19. void chainedHashInsert(int value);                                  /* inserts a value in the hash table, using chaining */
  20. int chainedHashSearch(int value);                                   /* searches for a value in the hash table */
  21. /* AUXILIARY FUNCTIONS */
  22. void populateHashMap(int numbersToBeGenerated);                     /* AUX: inserts random integer numbers in the hash table */
  23. void printList(int i);                                              /* AUX: prints the linked list stored in hashMapChained[i] */
  24. void printHashMap();                                                /* AUX: prints the whole hash hashMapChained */
  25. void searchNumbers(int numbersToBeSearched);                        /* AUX: searches random numbers in the hash map */
  26.  
  27. /* HASH FUNCTIONS */
  28. int hash(int value){
  29.     return (SIZE_HASH_MAP * fmod((value * HASH_CONSTANT),1));
  30. }
  31.  
  32. void chainedHashInsert(int value){
  33.     int probe = hash(value);                                        // stores the hash value of the number to be inserted
  34.     if(hashMapChained[probe] == NULL){                              // if the list in hashMapChained[probe] is empty
  35.         hashMapChained[probe] = malloc(sizeof(t_hashTableNode));    // then creates a new list
  36.         hashMapChained[probe]->value = value;
  37.         hashMapChained[probe]->next = NULL;
  38.     }else{                                                          // if the list in hashMapChained[probe] is not empty
  39.         t_hashTableNode *hashTableNode = hashMapChained[probe];
  40.         while(hashTableNode->next!=NULL){                           // scrolls down the list
  41.             hashTableNode = hashTableNode->next;
  42.         }
  43.         hashTableNode->next = malloc(sizeof(t_hashTableNode));      // inserst the value as the last element of the list
  44.         hashTableNode->next->value = value;
  45.         hashTableNode->next->next = NULL;
  46.     }
  47. }
  48.  
  49. int chainedHashSearch(int value){
  50.     t_hashTableNode *hashTableNode = hashMapChained[hash(value)];   // pointer to the list stored in hashMapChained[hash(value)]
  51.     while(hashTableNode!=NULL){                                     // scrolls the list
  52.         if(hashTableNode->value==value){
  53.             return TRUE;                                            // if the value is found, returns TRUE
  54.         }
  55.         hashTableNode = hashTableNode->next;
  56.     }
  57.     return FALSE;                                                   // else returns FALSE
  58. }
  59.  
  60. /* MAIN FUNCTION */
  61. int main (int argc, char const *argv[]){
  62.     srand(time(NULL));
  63.     populateHashMap(25);
  64.     printf("\nsituation after insertion of random integers:\n");
  65.     printHashMap();
  66.     printf("\nsearch of some random integers:\n");
  67.     searchNumbers(10);
  68. }
  69.  
  70.  
  71. /* AUXILIARY FUNCTIONS */
  72. void populateHashMap(int numbersToBeGenerated){                     // generates random numbers
  73.     int k = 1;
  74.     int randomNumber;
  75.     for(k=1;k<=numbersToBeGenerated;k++){
  76.         randomNumber = rand() % 100 + 1; 
  77.         chainedHashInsert(randomNumber);                            // inserts them in the hash map
  78.     }
  79. }
  80.  
  81. void printList(int hashMapRow){
  82.     t_hashTableNode *hashMapNode = hashMapChained[hashMapRow];      // pointer to the linked list stored in hashMapChained[hashMapRow]
  83.     while(hashMapNode!=NULL){
  84.         printf("%d ",hashMapNode->value);                           // prints out the value of the nodes
  85.         hashMapNode = hashMapNode->next;
  86.     }
  87. }
  88.  
  89. void printHashMap(){                                            
  90.     int i;
  91.     for(i=0;i<SIZE_HASH_MAP;i++){                                   // for every row of the hash map
  92.         printf("hashMapChained[%d]:\t",i);  
  93.         printList(i);                                               // prints the list contained in it
  94.         printf("\n");
  95.     }
  96. }
  97.  
  98. void searchNumbers(int numbersToBeSearched){
  99.     int k;
  100.     int randomNumber;
  101.     for(k=1;k<=numbersToBeSearched;k++){                            // searches a random number (from 1 to 100) numbersToBeSearched times
  102.         randomNumber = rand() % 100 + 1; 
  103.         printf("Is the value %d present? %d\n",randomNumber,chainedHashSearch(randomNumber));
  104.     }
  105. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function 'void chainedHashInsert(int)':
prog.cpp:35:63: error: invalid conversion from 'void*' to 't_hashTableNode* {aka node*}' [-fpermissive]
         hashMapChained[probe] = malloc(sizeof(t_hashTableNode));    // then creates a new list
                                                               ^
prog.cpp:43:61: error: invalid conversion from 'void*' to 'node*' [-fpermissive]
         hashTableNode->next = malloc(sizeof(t_hashTableNode));      // inserst the value as the last element of the list
                                                             ^
stdout
copy 
Standard output is empty
https://ideone.com/jGXJJH
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!