Answer Happy

please write code at fixed me only and check your work before
answer posting because on my last post someone answered wrong code
and I had to gave it dislike.
Part 1. Implement a hash table
ht_insert, ht_lookup and ht_remove should be o(1) run time
complaxity
hash_table.c
#include
#include "dynarray.h"
#include "list.h"
#include "hash_table.h"
/*
* This is the structure that represents a hash table. You must
define
* this struct to contain the data needed to implement a hash
table.
*/
struct ht;
/*
* This function should allocate and initialize an empty hash table
and
* return a pointer to it.
*/
struct ht* ht_create(){
/*
* FIXME:
*/
return NULL;
}
/*
* This function should free the memory allocated to a given hash
table.
* Note that this function SHOULD NOT free the individual elements
stored in
* the hash table. That is the responsibility of the caller.
*
* Params:
* ht - the hash table to be destroyed. May not be NULL.
*/
void ht_free(struct ht* ht){
/*
* FIXME:
*/
return;
}
/*
* This function should return 1 if the specified hash table is
empty and
* 0 otherwise.
*
* Params:
* ht - the hash table whose emptiness is to be checked. May not
be
* NULL.
*
* Return:
* Should return 1 if ht is empty and 0 otherwise.
*/
int ht_isempty(struct ht* ht){
/*
* FIXME:
*/
return -1;
}
/*
* This function returns the size of a given hash table (i.e. the
number of
* elements stored in it, not the capacity).
*/
int ht_size(struct ht* ht){
/*
* FIXME:
*/
return -1;
}
/*
* This function takes a key, maps it to an integer index value in
the hash table,
* and returns it. The hash algorithm is totally up to you. Make
sure to consider
* Determinism, Uniformity, and Speed when design the hash
algorithm
*
* Params:
* ht - the hash table into which to store the element. May not be
NULL.
* key - the key of the element to be stored
* convert - pointer to a function that can be passed the void* key
from
* to convert it to a unique integer hashcode
*/
int ht_hash_func(struct ht* ht, void* key, int
(*convert)(void*)){
/*
* FIXME:
*/
return -1;
}
/*
* This function should insert a given element into a hash table
with a
* specified key. Note that you cannot have two same keys in one
hash table.
* If the key already exists, update the value associated with the
key.
* This function is passed a function pointer that is used to
convert the key (void*)
* to a unique hashcode (int).
* Resolution of collisions is requried, use either chaining or open
addressing.
* If using chaining, double the number of buckets when the load
factor is >= 4
* If using open addressing, double the array capacity when the load
factor is >= 0.75
* load factor = (number of elements) / (hash table capacity)
*
* Params:
* ht - the hash table into which to insert an element. May not be
NULL.
* key - the key of the element
* value - the value to be inserted into ht.
* convert - pointer to a function that can be passed the void* key
from
* to convert it to a unique integer hashcode
*/
void ht_insert(struct ht* ht, void* key, void* value, int
(*convert)(void*)){
/*
* FIXME:
*/
return;
}
/*
* This function should search for a given element in a hash table
with a
* specified key provided.
* This function is passed a function pointer that is used to
convert the key (void*)
* to a unique hashcode (int).
* If the key is found, return the corresponding value (void*) of
the element,
* otherwise, return NULL
*
* Params:
* ht - the hash table into which to loop up for an element. May not
be NULL.
* key - the key of the element to search for
* convert - pointer to a function that can be passed the void* key
from
* to convert it to a unique integer hashcode
*/
void* ht_lookup(struct ht* ht, void* key, int
(*convert)(void*)){
/*
* FIXME:
*/
return NULL;
}
/*
* This function should remove a given element in a hash table with
a
* specified key provided.
* This function is passed a function pointer that is used to
convert the key (void*)
* to a unique hashcode (int).
* If the key is found, remove the element and return, otherwise, do
nothing and return
*
* Params:
* ht - the hash table into which to remove an element. May not be
NULL.
* key - the key of the element to remove
* convert - pointer to a function that can be passed the void* key
from
* to convert it to a unique integer hashcode
*/
void ht_remove(struct ht* ht, void* key, int
(*convert)(void*)){
/*
* FIXME:
*/
return;
}
----------------------------------------------------list.c============================
#include
#include
#include "list.h"
/*
* This structure is used to represent a single node in a
singly-linked list.
* It is not defined in list.h, so it is not visible to the
user.
*/
struct node {
void* val;
struct node* next;
};
/*
* This structure is used to represent an entire singly-linked list.
Note that
* we're keeping track of just the head of the list here, for
simplicity.
*/
struct list {
struct node* head;
};
/*
* This function allocates and initializes a new, empty linked list
and
* returns a pointer to it.
*/
struct list* list_create() {
struct list* list = malloc(sizeof(struct list));
list->head = NULL;
return list;
}
/*
* This function frees the memory associated with a linked list.
Freeing any
* memory associated with values still stored in the list is the
responsibility
* of the caller.
*
* Params:
* list - the linked list to be destroyed. May not be NULL.
*/
void list_free(struct list* list) {
assert(list);
/*
* Free all individual nodes.
*/
struct node* next, * curr = list->head;
while (curr != NULL) {
next = curr->next;
free(curr);
curr = next;
}
free(list);
}
/*
* This function inserts a new value into a given linked list. The
new element
* is always inserted as the head of the list.
*
* Params:
* list - the linked list into which to insert an element. May not
be NULL.
* val - the value to be inserted. Note that this parameter has type
void*,
* which means that a pointer of any type can be passed.
*/
void list_insert(struct list* list, void* val) {
assert(list);
/*
* Create new node and insert at head.
*/
struct node* temp = malloc(sizeof(struct node));
temp->val = val;
temp->next = list->head;
list->head = temp;
}
/*
* This function removes an element with a specified value from a
given
* linked list. If the specified value appears multiple times in the
list,
* only the *first* instance of that value (i.e. the one nearest to
the head
* of the list) is removed. This function is passed a function
pointer that
* is used to compare the value `val` to be removed with the values
stored in
* the list to determine which element (if any) to remove.
*
* Params:
* list - the linked list from which to remove an element. May not
be NULL.
* val - the value to be removed. Note that this parameter has type
void*,
* which means that a pointer of any type can be passed.
* cmp - pointer to a function that can be passed two void* values
from
* to compare them for equality, as described above. If the two
values
* passed are to be considered equal, this function should return
0.
* Otherwise, it should return a non-zero value.
*/
void list_remove(struct list* list, void* val, int (*cmp)(void* a,
void* b)) {
assert(list);
struct node* prev = NULL, * curr = list->head;
while (curr) {
/*
* If current node's value matches query value, update node prior to
curr
* to point around curr, then free curr and return. This removes
curr from
* the list.
*/
if (cmp(val, curr->val) == 0) {
if (prev) {
prev->next = curr->next;
} else {
list->head = curr->next;
}
free(curr);
return;
}
prev = curr;
curr = curr->next;
}
}
/*
* This returns the position (i.e. the 0-based "index") of the first
instance
* of a specified value within a given linked list (i.e. the one
nearest to the
* head of the list). If the list does not contain the specified
value, this
* function returns the special value -1. This function is passed a
function
* pointer called `cmp` that is used to compare the value `val` to
be located
* with the values stored in the list to determine which node (if
any) contains
* `val`.
*
* Params:
* list - the linked list from which to remove an element. May not
be NULL.
* val - the value to be located. Note that this parameter has type
void*,
* which means that a pointer of any type can be passed.
* cmp - pointer to a function that can be passed two void* values
from
* to compare them for equality, as described above. If the two
values
* passed are to be considered equal, this function should return
0.
* Otherwise, it should return a non-zero value.
*
* Return:
* This function returns the 0-based position of the first instance
of `val`
* within `list`, as determined by the function `cmp` (i.e. the
closest
* such instance to the head of the list) or -1 if `list` does not
contain
* the value `val`.
*/
int list_position(struct list* list, void* val, int (*cmp)(void* a,
void* b)) {
assert(list);
struct node* curr = list->head;
int i = 0;
while (curr) {
/*
* If curr's value matches the query value, return the position of
curr.
*/
if (cmp(val, curr->val) == 0) {
return i;
}
curr = curr->next;
i++;
}
/*
* If we got all the way through the list and no element matched
`val`, then
* `val` didn't exist in the list, so return -1.
*/
return -1;
}
/*
* This function should reverse the order of the nodes in a given
linked list.
* The reversal should be done *in place*, i.e. within the existing
list, and
* new memory should not be allocated to accomplish the reversal.
You should
* be able to accomplish the reversal with a single pass through the
list.
*
* Params:
* list - the linked list to be reversed. May not be NULL. When
this
* function returns this should contain the reversed list.
*/
void list_reverse(struct list* list) {
assert(list);
/*
* Reverse the list by reversing the individual nodes, making each
node's
* next pointer point to what used to be the previous node. Move the
list's
* head pointer through the list as we iterate from node to node, so
at the
* end of the iteration, the head pointer will end up pointing to
what used
* to be the tail of the list.
*/
struct node* next, * curr = list->head, * prev = NULL;
while (curr) {
next = curr->next;
curr->next = prev;
list->head = prev = curr;
curr = next;
}
}
it is commented as a too large a question but you just
have to update codes in the hash_table.c not in list and list.c is
only for the reference of the list in hash_table .