Advertisement
Guest User

Hashtabelle mit Verkettung

a guest
Oct 2nd, 2018
231
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 4.17 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #define N 31 // prime number for size of array
  5. #define h(x) (x % m) //h(x) = x mod m
  6.  
  7. // Node for List
  8. typedef struct Node{
  9.     int val;
  10.     struct Node *next;
  11. }Node;
  12.  
  13. //function's declaration
  14. Node *fill_table(Node *table, int table_range, int number);
  15. Node *insert(Node *table, int hash_index, int val);
  16. Node *del(Node *table,int table_range,int val);
  17. void print_table(Node *table, int table_range);
  18. void search_table(Node *table, int table_range, int val);
  19.  
  20. int main(){
  21.     Node *table; // hashtable
  22.     int n, i, j, choice, search;
  23.     int hash_num, val;     
  24.  
  25.     // allocate table
  26.     table = (Node*) malloc(N*sizeof(Node));
  27.     //make table "heads" NULL
  28.     for(i = 0; i < N; i++){
  29.         table[i].next = NULL;
  30.     }
  31.    
  32.     printf("--h(x) = xmod%d--\n",N);
  33.     printf("\n\n");  
  34.  
  35.     while(1){
  36.         printf("1.Insert random numbers\n");
  37.         printf("2.Delete a number\n");
  38.     printf("3.Search a number\n");
  39.     printf("4.Show Hash Table\n");
  40.     printf("0.Exit Programm\n");       
  41.     printf("\n--------\n");
  42.     printf("Choice: ");
  43.     scanf("%d",&choice);
  44.    
  45.     switch(choice){
  46.         case 0: return;
  47.         case 1:
  48.             // insert random numbers
  49.             printf("Lot to insert: ");
  50.             scanf("%d", &n);
  51.             table = fill_table(table, N, n);
  52.             printf("Filled HashTable with %d random values\n", n);
  53.             printf("\n--------\n");
  54.             break;
  55.         case 2:
  56.             // delete a number
  57.             printf("Give a number: ");
  58.             scanf("%d",&search);
  59.             table = del(table, N, search);
  60.             printf("\n--------\n");
  61.             break;
  62.         case 3:
  63.             // search for a number
  64.             printf("Give a number: ");
  65.             scanf("%d",&search);           
  66.             search_table(table, N, search);
  67.             printf("\n--------\n");
  68.             break;
  69.         case 4:
  70.             //print hashtable
  71.             printf("-HASHTABLE-\n\n");
  72.             print_table(table, N);
  73.             printf("\n--------\n");
  74.             break; 
  75.         }
  76.     }  
  77.     return 0;
  78. }
  79.  
  80. // FUNCTIONS
  81. Node *fill_table(Node *table, int table_range, int number){
  82.     int i;
  83.     int num;
  84.     for(i=0; i<number; i++){
  85.     num = rand()%10000; // random number from 0 to 9999
  86.     table = insert(table, num % table_range, num);
  87.     }
  88.     return table;
  89. }
  90.  
  91. void print_table(Node *table, int table_range){
  92.     int i;
  93.     Node* cur;
  94.     for(i = 0; i < table_range; i++){ // for each list
  95.     if(table[i].next == NULL){ // if empty
  96.                 printf("Table[%d] is empty!\n", i);
  97.         continue;
  98.     }
  99.     cur = table[i].next;
  100.     printf("Table[%d]", i);
  101.     while(cur!=NULL){ // else print all the values
  102.         printf("->%d",cur->val);
  103.         cur=cur->next; //cur=cur+1;
  104.     }
  105.     printf("\n");  
  106.     }
  107. }
  108.  
  109. Node *insert(Node *table, int hash_index, int val){
  110.     Node *nn, *cur;
  111.  
  112.     nn = (Node*)malloc(sizeof(Node));
  113.     nn->val=val;
  114.     nn->next=NULL;
  115.    
  116.     if(table[hash_index].next == NULL){
  117.     table[hash_index].next = nn;
  118.     return table;
  119.     }
  120.    
  121.     cur = table[hash_index].next;
  122.     while(cur->next != NULL){
  123.     cur=cur->next; //cur=cur+1;
  124.     }
  125.     cur->next = nn;
  126.     return table;
  127. }
  128.  
  129. void search_table(Node *table, int table_range, int val){
  130.     int index = val % table_range;
  131.     Node *cur;
  132.    
  133.     if(table[index].next == NULL){ // if empty
  134.         printf("Value %d not found cause Table[%d] is emtpy!\n", val,index);
  135.                 return;
  136.     }
  137.  
  138.     cur = table[index].next;
  139.     while(cur!=NULL){
  140.     if(cur->val == val){
  141.         printf("Value %d was found!\n", val);
  142.         return;
  143.     }
  144.     cur = cur->next;
  145.     }
  146.     printf("Value %d not found in Hashtable!\n", val);
  147. }
  148.  
  149. Node *del(Node *table, int table_range, int val){
  150.     int index = val % table_range;
  151.     Node *prev;
  152.    
  153.     if(table[index].next == NULL){ // if empty
  154.     printf("Value %d not found cause Table[%d] is emtpy!\n", val,index);
  155.     return table;
  156.     }
  157.    
  158.     if(table[index].next->val == val){ // if first item
  159.     printf("Value %d was found at table[%d] and Deleted!\n", val,index);
  160.     table[index].next = table[index].next->next;
  161.     return table;
  162.     }
  163.  
  164.     prev = table[index].next;
  165.     while(prev->next!=NULL){
  166.     if(prev->next->val == val){
  167.         prev->next = prev->next->next;
  168.         printf("Value %d was found at table[%d] and Deleted!\n", val,index);
  169.         return table;
  170.     }
  171.     prev = prev->next;
  172.     }
  173.     printf("Value %d was not found in Hashtable!\n", val);
  174.     return table;
  175. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement