Guest User

Untitled

a guest
Nov 8th, 2020
75
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Implements a dictionary's functionality
  2.  
  3. #include <stdbool.h>
  4.  
  5.  
  6. #include "dictionary.h"
  7. #include <stdio.h>
  8. #include <string.h>
  9. #include <strings.h>
  10. #include <stdlib.h>
  11. #include <stdbool.h>
  12. #include <cs50.h>
  13. #include <ctype.h>
  14.  
  15. // Represents a node in a hash table
  16. typedef struct node
  17. {
  18.     char word[LENGTH + 1];
  19.     struct node *next;
  20. }
  21. node;
  22.  
  23. // Number of buckets in hash table
  24. const unsigned int N = 26;
  25. // 26 for 26 letters in alphabet
  26.  
  27. //global variable for word count used in load() and size()
  28. int     nWordCount = 0;
  29.  
  30. // Hash table
  31. node *table[N];
  32.  
  33. //initializing empty and NULL values to table
  34. for(int i = 0; i < N; i++)
  35. {
  36.     node *n = malloc(sizeof(node));
  37.    
  38.     if (n == NULL)
  39.     {
  40.         printf("\n \t Unable to malloc.");
  41.         return 1;
  42.     }
  43.    
  44.     strcpy(table[i]->word, "");
  45.     table[i]->next = n;
  46.    
  47.     table[i]->next = NULL;    
  48. }
  49.  
  50.  
  51. // Returns true if word is in dictionary else false
  52. bool check(const char *word)
  53. {
  54.     // TODO
  55.    
  56.     //case insensitive
  57.     // 1) hash word using has function
  58.     // 2) traverse linked list at has index , use strcasecmp()
  59.     /*  Start with cursor set to first item in linked list.
  60.         keep moving cursor until you get to NULL, checking each node for the word.
  61.     */
  62.     bool bFound = false;
  63.    
  64.     int key = hash(word);
  65.    
  66.     node *temp = malloc(sizeof(node));
  67.     temp = NULL;
  68.  
  69.     //checks if the list is outright empty == NULL
  70.     if(table[key]->next == NULL)
  71.     {
  72.         bFound = false;
  73.     }
  74.        
  75.     //if list is not emtpy
  76.     else
  77.     {
  78.         for (temp = table[key]; temp->next != NULL; temp = temp->next)
  79.         {
  80.             if (strcasecmp(word, temp->word))
  81.             {
  82.                 bFound = true;
  83.             }
  84.         }
  85.     }
  86.    
  87.     free(temp);
  88.     return bFound;
  89. }
  90.  
  91. // Hashes word to a number
  92. unsigned int hash(const char *word)
  93. {
  94.     // TODO
  95.    
  96.     //hash by first letter
  97.     int val = 0;
  98.     char c = tolower(word[0]);
  99.  
  100.    
  101.     switch(c)
  102.     {
  103.         case ('a'):
  104.             val = 0;
  105.             break;
  106.         case ('b'):
  107.             val = 1;
  108.             break;
  109.         case ('c'):
  110.             val = 2;
  111.             break;
  112.         case ('d'):
  113.             val = 3;
  114.             break;
  115.         case ('e'):
  116.             val = 4;
  117.             break;
  118.         case ('f'):
  119.             val = 5;
  120.             break;
  121.         case ('g'):
  122.             val = 6;
  123.             break;
  124.         case ('h'):
  125.             val = 7;
  126.             break;
  127.         case ('i'):
  128.             val = 8;
  129.             break;
  130.         case ('j'):
  131.             val = 9;
  132.             break;
  133.         case ('k'):
  134.             val = 10;
  135.             break;
  136.         case ('l'):
  137.             val = 11;
  138.             break;
  139.         case ('m'):
  140.             val = 12;
  141.             break;
  142.         case ('n'):
  143.             val = 13;
  144.             break;
  145.         case ('o'):
  146.             val = 14;
  147.             break;
  148.         case ('p'):
  149.             val = 15;
  150.             break;
  151.         case ('q'):
  152.             val = 16;
  153.             break;
  154.         case ('r'):
  155.             val = 17;
  156.             break;
  157.         case ('s'):
  158.             val = 18;
  159.             break;
  160.         case ('t'):
  161.             val = 19;
  162.             break;
  163.         case ('u'):
  164.             val = 20;
  165.             break;
  166.         case ('v'):
  167.             val = 21;
  168.             break;
  169.         case ('w'):
  170.             val = 22;
  171.             break;
  172.         case ('x'):
  173.             val = 23;
  174.             break;
  175.         case ('y'):
  176.             val = 24;
  177.             break;
  178.         case ('z'):
  179.             val = 25;
  180.             break;
  181.         default:
  182.             printf("Invalid operation");
  183.     }
  184.    
  185.     return val;
  186. }
  187.  
  188. // Loads dictionary into memory, returning true if successful else false
  189. bool load(const char *dictionary)
  190. {
  191.     int  key = 0;
  192.     char word[45];
  193.  
  194.     node *cursor = malloc(sizeof(node));
  195.     cursor = NULL;
  196.    
  197.    
  198.     // TODO
  199.    
  200.     //open file
  201.     FILE *fp1 = fopen(dictionary, "r");
  202.    
  203.     //check if file is NULL
  204.     if (fp1 == NULL)
  205.     {
  206.         printf ("/n /t Error opening file!");
  207.         return(1);
  208.     }
  209.    
  210.  
  211.     while (fscanf(fp1, "%s", word) != EOF)
  212.     {
  213.         //creating the node
  214.         node *n = malloc(sizeof(node));
  215.        
  216.         strcpy (n->word, word);
  217.         nWordCount++;
  218.         n->next = NULL;
  219.        
  220.         //call hash function to get hash value of word
  221.         key = hash(word);
  222.    
  223.         //inserts first node / head if array is empty
  224.         if (table[key] == NULL)
  225.         {
  226.             table[key]->next = n;
  227.         }
  228.        
  229.         //else array is not empty,  inserts new node at the end
  230.         else if (table[key] != NULL)
  231.         {
  232.             //goes to index in table
  233.             cursor->next = table[(N-1)];
  234.            
  235.             //traverses linked list to get to the last node
  236.             while(cursor->next != NULL)
  237.             {
  238.                 cursor->next = cursor->next->next;
  239.             }
  240.            
  241.             //adds new node to the end
  242.             cursor->next = n;
  243.         }
  244.     }
  245.    
  246.     fclose(fp1);
  247.    
  248.      /* 1) Open dictionary file
  249.             use fopen, check if return value is NULL    */
  250.     /* 2) Read strings from file one at a time
  251.             fscanf(file, "%s", word), EOF at End of File */
  252.     /* 3) Create a new word for each node
  253.             use malloc, check if return value is NULL, copy word into node using strcpy */
  254.     // 4) Hash word to obtain hash value
  255.     // 5) Insert node into hash table at that location
  256.    
  257.     //return false;
  258.     return true;
  259. }
  260.  
  261. // Returns number of words in dictionary if loaded else 0 if not yet loaded
  262. unsigned int size(void)
  263. {
  264.     // TODO
  265.    
  266.     //return number of words in dictionary
  267.     return nWordCount;
  268.    
  269.     //return 0;
  270. }
  271.  
  272. // Unloads dictionary from memory, returning true if successful else false
  273. bool unload(void)
  274. {
  275.     // TODO
  276.  
  277.     // free all nodes in the linked lists
  278.     // runner + trailer. Runner keeps moving forward, trailer is the one freeing the node.
  279.    
  280.     node *runner = malloc(sizeof(node));
  281.     runner = NULL;
  282.    
  283.     node *trailer = malloc(sizeof(node));
  284.     trailer = NULL;
  285.  
  286.    
  287.     for (int i = 0; i < N; i++)
  288.     {
  289.         runner = table[i];
  290.         trailer = table[i];
  291.        
  292.         do
  293.         {
  294.             //move runner 1 node forward
  295.             runner->next = table[i]->next;
  296.            
  297.             //move trailer 1 node forward, same position as runner
  298.             trailer->next = runner;
  299.            
  300.             //move runner 1 node forward, now 1 node ahead of trailer
  301.             runner->next = runner->next->next;
  302.            
  303.             free(trailer);
  304.            
  305.             trailer->next = runner;
  306.            
  307.         }while (runner->next != NULL);
  308.        
  309.         free(runner);
  310.     }
  311.    
  312.     return false;
  313. }
  314.  
RAW Paste Data