Advertisement
Guest User

Untitled

a guest
Dec 7th, 2019
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.32 KB | None | 0 0
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4. #include "Dictionary.h"
  5.  
  6. const int tableSize = 101;
  7.  
  8. typedef struct NodeObj* Node;
  9.  
  10. typedef struct NodeObj{
  11. char* key;
  12. char* value;
  13. struct NodeObj* next;
  14. } NodeObj;
  15.  
  16. Node newNode(char* k, char* v){
  17. Node N = malloc(sizeof(NodeObj));
  18. N->key = k;
  19. N->value = v;
  20. N->next = NULL;
  21. return N;
  22. }
  23.  
  24. void freeNode(Node* pN){
  25. if(pN != NULL && *pN != NULL){
  26. free(*pN);
  27. *pN = NULL;
  28. }
  29. }
  30.  
  31. void freeAllNodes(Node H){
  32. if(H != NULL){
  33. freeAllNodes(H->next);
  34. freeNode(&H);
  35. }
  36. }
  37.  
  38. // Dictionary
  39. typedef struct DictionaryObj* Dictionary;
  40.  
  41. typedef struct DictionaryObj{
  42. Node* table;
  43. int size;
  44. } DictionaryObj;
  45.  
  46. // Constructors-Destructors ---------------------------------------------------
  47.  
  48. // newDictionary()
  49. // Constructor for the Dictionary ADT.
  50. Dictionary newDictionary(){
  51. Dictionary D = malloc(sizeof(DictionaryObj));
  52. D->table = calloc(tableSize, sizeof(Node));
  53. D->size = 0;
  54. return D;
  55. }
  56.  
  57. // freeDictionary()
  58. // Destructor for the Dictionary ADT.
  59. void freeDictionary(Dictionary* pD){
  60. Node* H = (*pD)->table;
  61. if(pD != NULL && *pD != NULL){
  62. makeEmpty(*pD);
  63. free(H);
  64. free(*pD);
  65. *pD = NULL;
  66. }
  67. }
  68.  
  69.  
  70. // ADT operations -------------------------------------------------------------
  71.  
  72. // rotate_left()
  73. // rotate the bits in an unsigned int
  74. unsigned int rotate_left(unsigned int value, int shift) {
  75. int sizeInBits = 8 * sizeof(unsigned int);
  76. shift = shift & (sizeInBits - 1);
  77.  
  78. if(shift == 0){
  79. return value;
  80. }
  81. return (value << shift) || (value >> (sizeInBits - shift));
  82. }
  83.  
  84. // pre_hash()
  85. // turn a string into an unsigned int
  86. unsigned int pre_hash(char* input) {
  87. unsigned int result = 0xBAE86554;
  88. while(*input){
  89. result ^= *input++;
  90. result = rotate_left(result, 5);
  91. }
  92. return result;
  93. }
  94.  
  95. // hash()
  96. // turns a string into an int in the range 0 to tableSize-1
  97. int hash(char* key){
  98. return pre_hash(key) % tableSize;
  99. }
  100.  
  101. // size()
  102. // Return the number of (key, value) pairs in Dictionary D.
  103. int size(Dictionary D){
  104. if(D == NULL){
  105. fprintf(stderr, "Dictionary Error: size() called on a NULL Dictionary reference\n");
  106. exit(EXIT_FAILURE);
  107. }
  108.  
  109. return D->size;
  110. }
  111.  
  112. //returns the node that has the matching key
  113. Node findKey(Dictionary D, char* k){
  114. Node* H = D->table;
  115. Node N = H[hash(k)];
  116. while(N != NULL){
  117. if(strcmp(N->key, k) == 0){
  118. return N;
  119. break;
  120. }
  121. N = N->next;
  122. }
  123.  
  124. return NULL;
  125. }
  126.  
  127. // lookup()
  128. // If D contains a pair whose key matches argument k, then return the
  129. // corresponding value, otherwise return NULL.
  130. char* lookup(Dictionary D, char* k){
  131. Node* H;
  132. Node N;
  133. if(D == NULL){
  134. fprintf(stderr, "Dictionary Error: lookup() called on a NULL Dictionary reference\n");
  135. exit(EXIT_FAILURE);
  136. }
  137.  
  138. H = D->table;
  139. N = findKey(D, k);
  140. if(N != NULL){
  141. return N->value;
  142. }
  143. else{
  144. return NULL;
  145. }/*
  146. if(H[hash(k)] != NULL){
  147. N = H[hash(k)];
  148. while(N != NULL){
  149. if(strcmp(N->key, k) == 0){
  150. return N->value;
  151. }
  152. N = N->next;
  153. }
  154. }
  155.  
  156. return NULL;*/
  157. }
  158.  
  159. // insert()
  160. // Insert the pair (k,v) into D.
  161. // Pre: lookup(D, k)==NULL (D does not contain a pair whose first member is k.)
  162. void insert(Dictionary D, char* k, char* v){
  163. Node* H;
  164. Node N, M;
  165.  
  166. if(lookup(D, k) != NULL){
  167. fprintf(stderr, "Dictionary Error: cannot insert() duplicate key: \"%s\"\n", k);
  168. exit(EXIT_FAILURE);
  169. }
  170.  
  171. H = D->table;
  172. N = newNode(k, v);
  173. if(H[hash(k)] == NULL){ //node does not have any keys yet
  174. H[hash(k)] = N;
  175. }
  176. else{ //node already has keys
  177. //M = H[hash(k)];
  178. N->next = H[hash(k)];
  179. H[hash(k)] = N;
  180. }
  181. D->size++;
  182. }
  183.  
  184. // delete()
  185. // Remove pair whose first member is the argument k from D.
  186. // Pre: lookup(D,k)!=NULL (D contains a pair whose first member is k.)
  187. void delete(Dictionary D, char* k){
  188. Node* H;
  189. Node N, M;
  190. if(D == NULL){
  191. fprintf(stderr, "Dictionary Error: delete() called on a NULL Dictionary reference\n");
  192. exit(EXIT_FAILURE);
  193. }
  194. if(lookup(D, k) == NULL){
  195. fprintf(stderr, "Dictionary Error: cannot delete() non-existent key: \"%s\"\n", k);
  196. exit(EXIT_FAILURE);
  197. }
  198.  
  199. H = D->table;
  200. M = H[hash(k)];
  201. N = findKey(D, k);
  202. if(strcmp(M->key, k) == 0){ //if node only has one key
  203. N = H[hash(k)];
  204. H[hash(k)] = H[hash(k)]->next;
  205. }
  206. else{
  207. while(M != NULL){
  208. if(M->next == N){
  209. M->next = N->next;
  210. break;
  211. }
  212. else{
  213. M = M->next;
  214. }
  215. }
  216. }
  217.  
  218. //N->next = NULL;
  219. freeNode(&N);
  220.  
  221. D->size--;
  222. }
  223.  
  224. // makeEmpty()
  225. // Reset D to the empty state, the empty set of pairs.
  226. void makeEmpty(Dictionary D){
  227. //Node* H;
  228. if(D == NULL){
  229. fprintf(stderr, "Dictionary Error: makeEmpty() called on a NULL Dictionary reference\n");
  230. exit(EXIT_FAILURE);
  231. }
  232.  
  233. //H = D->table;
  234.  
  235. for(int i = 0; i < tableSize; i++){
  236. freeAllNodes(D->table[i]);
  237. D->table[i] = NULL;
  238. }
  239.  
  240. D->size = 0;
  241. }
  242.  
  243. //return number of characters in a node
  244. int countChars(Dictionary D){
  245. Node* H = D->table;
  246. Node N;
  247. int count = 0;
  248.  
  249. for(int i = 0; i < tableSize; i++){
  250. if(H[i] != NULL){
  251. N = H[i];
  252. while(N != NULL){
  253. count += strlen(N->key);
  254. count++;
  255. count += strlen(N->value);
  256. count++;
  257. N = N->next;
  258. }
  259. }
  260. }
  261.  
  262. return count;
  263. }
  264.  
  265. // Other Operations -----------------------------------------------------------
  266.  
  267. // DictionaryToString()
  268. // Determines a text representation of the current state of Dictionary D. Each
  269. // (key, value) pair is represented as the chars in key, followed by a space,
  270. // followed by the chars in value, followed by a newline '\n' char. The pairs
  271. // occur in alphabetical order by key. The function returns a pointer to a char
  272. // array, allocated from heap memory, containing the text representation
  273. // described above, followed by a terminating null '\0' char. It is the
  274. // responsibility of the calling function to free this memory.
  275. char* DictionaryToString(Dictionary D){
  276. Node* H;
  277. Node N;
  278. char* str;
  279. int count;
  280.  
  281. if(D == NULL){
  282. fprintf(stderr, "Dictionary Error: DictionaryToString() called on a NULL Dictionary reference\n");
  283. exit(EXIT_FAILURE);
  284. }
  285.  
  286. count = countChars(D);
  287. str = calloc(count + 1, sizeof(char));
  288. H = D->table;
  289.  
  290. for(int i = 0; i < tableSize; i++){
  291. if(H[i] != NULL){
  292. N = H[i];
  293. while(N != NULL){
  294. strcat(str, N->key);
  295. strcat(str, " ");
  296. strcat(str, N->value);
  297. strcat(str, "\n");
  298. N = N->next;
  299. }
  300. }
  301. }
  302. //str[count] = '\0';
  303.  
  304. return str;
  305. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement