Advertisement
WONGDEEM

Untitled

Apr 1st, 2021
756
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define TABLESIZE 37
  5. #define PRIME     13
  6.  
  7. enum Marker {EMPTY,USED,DELETED};
  8.  
  9. typedef struct _slot{
  10.     int key;
  11.     enum Marker indicator;
  12. } HashSlot;
  13.  
  14. int HashInsert(int key, HashSlot hashTable[]);
  15. int HashDelete(int key, HashSlot hashTable[]);
  16.  
  17.  
  18. int hash1(int key);
  19. int hash2(int key);
  20.  
  21. int main()
  22. {
  23.     int opt;
  24.     int i;
  25.     int key;
  26.     int comparison;
  27.     HashSlot hashTable[TABLESIZE];
  28.  
  29.     for(i=0;i<TABLESIZE;i++){
  30.         hashTable[i].indicator = EMPTY;
  31.         hashTable[i].key = 0;
  32.     }
  33.  
  34.     printf("============= Hash Table ============\n");
  35.     printf("|1. Insert a key to the hash table  |\n");
  36.     printf("|2. Delete a key from the hash table|\n");
  37.     printf("|3. Print the hash table            |\n");
  38.     printf("|4. Quit                            |\n");
  39.     printf("=====================================\n");
  40.     printf("Enter selection: ");
  41.     scanf("%d",&opt);
  42.     while(opt>=1 && opt <=3){
  43.         switch(opt){
  44.         case 1:
  45.             printf("Enter a key to be inserted:\n");
  46.             scanf("%d",&key);
  47.             comparison = HashInsert(key,hashTable);
  48.             if(comparison <0)
  49.                 printf("Duplicate key\n");
  50.             else if(comparison < TABLESIZE)
  51.                 printf("Insert: %d Key Comparisons: %d\n",key, comparison);
  52.             else
  53.                 printf("Key Comparisons: %d. Table is full.\n",comparison);
  54.             break;
  55.         case 2:
  56.             printf("Enter a key to be deleted:\n");
  57.             scanf("%d",&key);
  58.             comparison = HashDelete(key,hashTable);
  59.             if(comparison <0)
  60.                 printf("%d does not exist.\n", key);
  61.             else if(comparison <= TABLESIZE)
  62.                 printf("Delete: %d Key Comparisons: %d\n",key, comparison);
  63.             else
  64.                 printf("Error\n");
  65.             break;
  66.         case 3:
  67.             for(i=0;i<TABLESIZE;i++) printf("%d: %d %c\n",i, hashTable[i].key,hashTable[i].indicator==DELETED?'*':' ');
  68.             break;
  69.         }
  70.         printf("Enter selection: ");
  71.         scanf("%d",&opt);
  72.     }
  73.     return 0;
  74. }
  75.  
  76. int hash1(int key)
  77. {
  78.     return (key % TABLESIZE);
  79. }
  80.  
  81. int hash2(int key)
  82. {
  83.     return (key % PRIME) + 1;
  84. }
  85.  
  86.  
  87. int HashInsert(int key, HashSlot hashTable[])
  88. {
  89.    int hash_1 = hash1(key), hash_2 = hash2(key), newIndex = 0, comparisons = 0;
  90.    int storedIndex = -1, i=0, internalCheck = 0, found = 0;
  91.  
  92.    newIndex = (hash_1+i++*hash_2) % TABLESIZE;
  93.  
  94.    // if slot is empty, it will insert immediately without checking for duplicates
  95.    if (hashTable[newIndex].indicator == EMPTY) {
  96.      hashTable[newIndex].key = key;
  97.      hashTable[newIndex].indicator = USED;
  98.      return comparisons;
  99.    }
  100.  
  101.    while (comparisons < TABLESIZE && internalCheck < TABLESIZE) {
  102.      //internalCheck because the maximum number of iterations should not exceed table size
  103.      internalCheck++;
  104.      //if current slot is DELETED and no previous deleted slot has been found
  105.      //store the current index into storedIndex and set found to true
  106.      //in a sense storing the first deleted slot found for future use
  107.  
  108.      //if current slot is USED and slot's key == key, return -1
  109.      // else increase comparison
  110.      if (hashTable[newIndex].indicator == DELETED && !found) {
  111.         storedIndex = newIndex;
  112.         found = 1;
  113.      } else if (hashTable[newIndex].indicator == USED) { //
  114.        if (hashTable[newIndex].key == key) {
  115.          return -1;
  116.        } else {
  117.          comparisons++;
  118.        }
  119.      }
  120.  
  121.      //set new index from hash functions for next iteration
  122.      newIndex = (hash_1+i++*hash_2) % TABLESIZE;
  123.      if (hashTable[newIndex].indicator == EMPTY) {
  124.        if (storedIndex == -1) {
  125.          hashTable[newIndex].key = key;
  126.          hashTable[newIndex].indicator = USED;
  127.          return comparisons--;
  128.        }
  129.      }
  130.    }
  131.  
  132.    //if storedIndex exists, then set the index to key and USED
  133.    if (storedIndex != -1) {
  134.      hashTable[storedIndex].key = key;
  135.      hashTable[storedIndex].indicator = USED;
  136.    }
  137.    return comparisons;
  138. }
  139.  
  140. int HashDelete(int key, HashSlot hashTable[])
  141. {
  142.    //Write your code here
  143.    int hash_1 = hash1(key);
  144.    int hash_2 = hash2(key);
  145.    int newIndex = 0;
  146.    int comparisons = 0;
  147.    int internalCheck = 0;
  148.    int i=0;
  149.  
  150.    while (comparisons < TABLESIZE && internalCheck <= TABLESIZE) {
  151.      internalCheck++;
  152.      newIndex = (hash_1+i++*hash_2) % TABLESIZE;
  153.  
  154.      if (hashTable[newIndex].indicator == USED) {
  155.        comparisons++;
  156.        if (hashTable[newIndex].key == key) {
  157.          hashTable[newIndex].indicator = DELETED;
  158.          return comparisons;
  159.        }
  160.      }
  161.    }
  162.  
  163.    return -1;
  164. }
  165.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement