Question: IMPORTANT: ONLY need to finish lab4-q2.c, the other documents are supporting materials. lab4-q2.c is partly written, please help me to finish this file. only need
IMPORTANT: ONLY need to finish "lab4-q2.c", the other documents are supporting materials. "lab4-q2.c" is partly written, please help me to finish this file. only need to finish this file. thanks a lot. the first part is the word form of the question, the second part is the screenshot of the question, the third part is the code of "lab4-q2.c" structure. [please help me to finish "lab4-q2.c" but Do please not to change the structure of "lab4-q2.c"].
Question 2: Hash Table with Open Addressing (40%)
You are going to implement hash table abstract data type using open addressing with double hashing. The header file lab4-q2.h and the description of the functions are as follows.
Your program should not contain main(). Name your program as lab4-q2.c.
// lab4-q2.h // Cannot modify this file typedef struct node {
int key;
int value; } Node;
typedef struct hash_os { int size; /* hash table size */ Node * slots; /* array of slots */
} Hash_OA;
/* When the slot is unoccupied, the key is HASH_NULL_KEY */
#define HASH_NULL_KEY 2100
/* Hash Table Open Addressing Part */ /* Initialize the hash table to size s #1 */ /* Return a new empty hash table with size s */ Hash_OA * hash_init(int s);
4
/* Make the hash table T empty #2 */ void hash_make_empty(Hash_OA *T);
/* Insert (key, value) to the hash table T #3 #4 */ /* If key does not exist in T, then add (key, value) to the front of the list */ /* If key already exist in T, then update the value */ /* return 1 if key is added to T successfully */ /* return 2 if key already exists in T and value is updated */ /* return 0 if key cannot be added to T */ int hash_insert(Hash_OA *T, int key, int value);
/* Check if key exist in the hash table T or not #5 */ /* If key in T, return 1 */ /* If key not in T, return 0 */ int hash_contain(Hash_OA *T, int key);
/* Find the value based on the key in the hash table T #6 */ /* If key in T, return the value */ /* If key does not exist in T, return INT_MAX */ int hash_find(Hash_OA *T, int key);
/* Free the hash table T, if T is not NULL */
void hash_free(Hash_OA *T);
/* The hash function calculates the hash value #7 */ /* hash_value = key mod size */ /* key can be negative, but hash_value must be range between 0 and size - 1 */ int hash_function(int key, int size);
/* The hash function 2 calculates the step size if collision occurs */ /*step_size=v-(keymodv),wherev=size-2 #8 */ /* You can safely assume v > 0 (i.e. size > 2) */ int hash_function2(int key, int size);
/* The print function print the whole hash table in an output string */ /* The first number is the index, number in the bracket is key, number after bracket is value #9 */ /* If the hash table looks like */
/* 0:(69)105 */ /* 1:NULL */ /* 2:NULL */ /* 3:(58)104 */ /* 4:NULL */ /* 5:NULL */ /* 6:(49)103 */ /* 7:NULL */ /* 8:(18)102 */ /* 9:(89)101 */ /* Then, the output string is "0:(69)105 1: 2: 3:(58)104 4: 5: 6:(49)103 7: 8:(18)102 9:(89)1 01 " */
char * hash_print(Hash_OA *T);
///////////////////////////////////////////////////////////////////////[end of .h file]
Sample Test Case (lab4-q2-tc1.c):
// This file is named as lab4-q2-tc1.c #include"lab4-q2.h" #include
#include
int main(int argc, char *argv[]){ FILE *fout; Hash_OA *T; int isCorrect, i;
fout = fopen(argv[1], "w");
/* default, your program is correct*/
isCorrect = 1;
/* check the function, hash_init()*/
T = NULL; T = hash_init(11);
/* if T is not initialized appropriately */
if (T == NULL) { isCorrect = 0;
} else if (T->size != 11) { isCorrect = 0;
} for (i = 0; i
if (T->slots[i].key != HASH_NULL_KEY) isCorrect = 0; }
/* output "Correct" if the hash_init() is correctly implemented */
if (isCorrect == 1) { fprintf(fout, "Correct ");
} else { fprintf(fout, "Wrong Answer ");
} fclose(fout);
return 0; }
Useful commands:
-
Compile your program
gcc -o prog lab4-q2-tc1.c lab4-q2.c
-
Run the program with arguments
./prog outputfile.txt
code of "lab4-q2.c":
#include"lab4-q2.h"
#include
#include
#include
#include
/* Initialize the hash table to size s */
/* Return a new empty hash table with size s */
Hash_OA * hash_init(int s){
Hash_OA *T = NULL;
// your code here
return T;
}
/* Make the hash table T empty */
void hash_make_empty(Hash_OA *T){
// your code here
}
/* Insert (key, value) to the hash table T */
/* If key does not exist in T, then add (key, value) to the front of the list */
/* If key already exist in T, then update the value */
/* return 1 if key is added to T successfully */
/* return 2 if key already exists in T and values is updated accordingly */
/* return 0 if key cannot be added to T */
int hash_insert(Hash_OA *T, int key, int value){
// your code here
return 0;
}
/* Check if key exist in the hash table T or not */
/* If key in T, return 1 */
/* If key not in T, return 0 */
int hash_contain(Hash_OA *T, int key){
// your code here
return 0;
}
/* Find the value based on the key in the hash table T */
/* If key in T, return the value */
/* If key does not exist in T, return INT_MAX */
int hash_find(Hash_OA *T, int key){
// your code here
return 0;
}
/* Free the hash table T, if T is not NULL */
void hash_free(Hash_OA *T){
// your code here
}
/* The hash function calculates the hash value */
/* hash_value = key mod size */
/* key can be negative, but hash_value must be range between 0 and size - 1 */
int hash_function(int key, int size){
// your code here
return 0;
}
/* The second hash function calculates the step size if collision occurs */
/* step_size = v - (key mod v), where v = size - 2 */
/* You can safely assume v > 0 (i.e. size > 2) */
/* key can be negative, but hash_value must be range between 1 and size - 2 */
int hash_function2(int key, int size){
// your code here
return 0;
}
/* The print function print the whole hash table in an output string */
/* The first number is the index, number in the bracket is key, number after bracket is value */
/* If the hash table looks like */
/* 0:(69)105 */
/* 1:NULL */
/* 2:NULL */
/* 3:(58)104 */
/* 4:NULL */
/* 5:NULL */
/* 6:(49)103 */
/* 7:NULL */
/* 8:(18)102 */
/* 9:(89)101 */
/* Then, the output string is "0:(69)105 1: 2: 3:(58)104 4: 5: 6:(49)103 7: 8:(18)102 9:(89)101 " */
char * hash_print(Hash_OA *T){
char * output = NULL;
// your code here
return output;
}
Question 2: Hash Table with Open Addressing (40%) You are going to implement hash table abstract data type using open addressing with double hashing. The header file lab4-42.h" and the description of the functions are as follows. Your program should not contain main(). Name your program as lab4-q2.c". // lab4-42.h // Cannot modify this file typedef struct node { int key; int value; } Node; typedef struct hash_os { int size; /* hash table size */ Node * slots; /* array of slots */ } Hash_OA; /* When the slot is unoccupied, the key is HASH_NULL_KEY */ #define HASH_NULL_KEY 2100 /* Hash Table Open Addressing Part */ /* Initialize the hash table to size s #1 */ /* Return a new empty hash table with size s */ Hash_OA * hash_init(int s); 4 /* Make the hash table T empty #2 */ void hash_make_empty(Hash_OA *T); /* Insert (key, value) to the hash table T #3 #4 */ /* If key does not exist in T, then add (key, value) to the front of the list */ /* If key already exist in T, then update the value */ /* return 1 if key is added to T successfully */ /* return 2 if key already exists in T and value is updated */ /* return if key cannot be added to T */ int hash_insert(Hash_OA *T, int key, int value); /* Check if key exist in the hash table I or not #5 */ /* If key in T, return 1 */ /* If key not in T, return 0 */ int hash_contain(Hash_OA *T, int key); /* Find the value based on the key in the hash table T #6 */ /* If key in T, return the value */ /* If key does not exist in T, return INT_MAX */ int hash_find (Hash_OA *T, int key); /* Free the hash table T, if I is not NULL */ void hash_free(Hash_OA *T); /* The hash function calculates the hash value #7 */ /* hash_value = key mod size */ /* key can be negative, but hash_value must be range between 0 and size - 1 */ int hash_function(int key, int size); /* The hash function 2 calculates the step size if collision occurs */ /* step_size = V - (key mod v), where v = size - 2 #8 */ /* You can safely assumev> (i.e. size > 2) */ int hash_function2(int key, int size); /* The print function print the whole hash table in an output string */ /* The first number is the index, number in the bracket is key, number after bracket is value #9 */ /* If the hash table looks like */ /* 0:(69)105 */ /* 1:NULL */ /* 2:NULL */ /* 3:(58)104 */ /* 4:NULL */ /* 5:NULL */ /* 6:(49)103 */ /* 7:NULL */ /* 8:(18)102 */ /* 9:(89)101 */ /* Then, the output string is /* Then, the output string is "O:(69)105 1: 2: 3:(58)104 4: 5: 6:(49) 103 7: 8:(18)102 9:(89)1 01 " */ char * hash_print (Hash_0A *T); 5 Sample Test Case (lab4-42-tc1.c): // This file is named as lab4-42-tci.c #include"lab4-42.h" #include
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts