Assignment 9
Objectives
â€¢ Hash tables and applications
â€¢ Binary heap
â€¢ Dynamic arrays
Write C programs hash.h, hash.c to implement chained hash table. hash.h and hash.c contains the following structures, functions and implementations.
1. data structure and function specifications
typedef struct hashnode {
char name[10]; // used as key variable
int value;
struct hashnode *next;
} HTNODE;
typedef struct hashtable {
HTNODE **hnp; // pointer pointing to the array of hashnode pointers
int size; // hash table size, maximum number of different indices
int count; // number of data elements in the hash table
} HASHTABLE;
/* hash function that hash name string to an integer of modular htsize */
int hash(char *name);
/* create dynamically a hash node and set name and value and return the point
*/
HTNODE *new_hashnode(char *name, int vale);
/* create dynamically a chained hash table of the size */
HASHTABLE *new_hashtable(int size);
/* search the hash table and return the pointer of found hashnode */
HTNODE *search(HASHTABLE *ht, char *name);
/* insert hashnode np to hash table
* when the named hashnode exists, update the hashnode's value by np->value,
free np, return 0;
* otherwise insert into the hash table, return 1
*/
int insert(HASHTABLE *ht, hashnode *np);
/* delete hashnode by name. If the named hash node exists, delete it and
return 1;
* otherwise return 0
*/

int delete(HASHTABLE *ht, char *name);
Use the provided a9q1.c to test the above functions. The output should be like the
following.
public test
gcc hash.c a9q1.c -o a9q1
a9q1
hash table after insertion
size: 10
count: 8
hash data:
index: list of the data elements
0: (d, 3)
1: (e, 4)
2: (f, 5)
3: (g, 6)
4: (h, 7)
7: (a, 0)
8: (b, 1)
9: (c, 2)
search data by name a
Find data element: (a, 0)
delete data by name a
Not found
size: 10
count: 7
hash data:

index: list of the data elements
0: (d, 3)
1: (e, 4)
2: (f, 5)
3: (g, 6)
4: (h, 7)
8: (b, 1)
9: (c, 2)
d=3
e=4
f=5
g=6
h=7
b=1
c=2
Update a6q3 to create a program which can evaluate algebra expressions which contains pre-defined symbol name. For example, a=2; b=3; c=a+b; c will have value 3. Requirements:
1. Use the hash table data structure hash.h and hash.c of question 1 to store resolved name-value pairs.
2. Modify functions in expeval.h and expeval.c of a6q3.
/*
* convert infix expression string to postfix expression represented by queue,
* and get symbol values from hash table
*/
QUEUE infix_to_postfix(char *infixstr, HASHTABLE *ht);
int evaluate_postfix(QUEUE queue);
int get_priority(char opr);
/*
* evaluate symbolic infix expression,

* calling infix_to_postfix(char *infixstr, HASHTABLE *ht); then
* calling evaluate_postfix(QUEUE queue);
*/
int evaluate_infix(char *infixstr, HASHTABLE *ht);
/*
* parsing statement symbol=expression, to get left-side symbol string, and
* evaluate the right side expression using evaluate_infix(char *infixstr,
HASHTABLE *ht);
* insert the symbol and its value into hashtable
*/
int resolve_assignment(char* statement, HASHTABLE *ht);
3. Use the provided a9q2.c and expression.txt to test. The output should be like the following.
public test
gcc common.c queue.c stack.c hash.c expeval.c a9q2.c -o a9q2
a9q2 expression.txt
Symbolic expressions:
a=5
b=3
c=(a+b)*(a-b)
b=a+b+c
Symbolic expression evaluation:
a=5
b=24
c=16
Write C programs heap.h and heap.c to implement binary min-heap using dynamic array. Requirements:
1. heap.h and heap.c contain the following heap structure and operation functions.

typedef int KEYTYPE; // key type
typedef int DATA; // data type
typedef struct heap_node { // data element ds for binary heap
KEYTYPE key;
DATA data;
} HNODE;
typedef struct heap {
unsigned int capacity; // the MAX length of array
unsigned int size; // the current heap size, i.e. heap node count
HNODE *hnap; // pointer pointing the heap node array
} HEAP;
/* create and return a heap data structure
to instantiate and return the pointer of the above heap structure, size=0,
capacity=4, allocate memory space to hold array of
elements of the capacity and store pointer in data
*/
HEAP *new_heap(int capacity);
/* this inserts the given node data a into the heap; When the heap size is equal to the capacity, the inserting process needs first to expand data array by doubling its amount. This may need to copy the data of old array to new array, secondly insert the new data element into the end of the array,
heapify and update size.*/
void insert(HEAP *heap, HNODE a);
/* this gets the data element of minimum key and delete the element from the binary heap. When the heap size is no more than a quarter of the capacity, it needs to shrink the data array by half to free the unused memory space. */
HNODE extract_min(HEAP *heap);
/* this decreases the key value of given element by index to new_key_value */
void decrease_key(HEAP *heap, int index, KEYTYPE new_key_value);
/* this finds and returns the first index of heap node of given data d*/
int find_index(HEAP *heap, DATA d);
/* this displays data elements in heap by index ordering. */
void display_heap(HEAP *heap);
/* this compare two key values a and b, return -1 if a<b, 0 if a=b, 1 if a>b
*/
int cmp(KEYTYPE a, KEYTYPE b);
2. Use this public test driver program a9q3.c to test the implementations of the above functions. The output should be like the following. Write your own main test program to test and make sure your functions work properly. public test
gcc heap.c a9q3.c -o a9q3

a9q3
size:0
capacity:4
(index, key, data):
insert to heap:
display heap after insertion:
size:10
capacity:16
(index, key, data):
(0 4 10) (1 5 9) (2 8 6) (3 7 7) (4 6 8) (5 12 2) (6 9 5) (7 13 1) (8 10 4)
(9 11 3)
the index of data value 6 is 2
decrease key value at index 2 to 2
size:10
capacity:16
(index, key, data):
(0 2 6) (1 5 9) (2 4 10) (3 7 7) (4 6 8) (5 12 2) (6 9 5) (7 13 1) (8 10 4)
(9 11 3)
call extract_min for 8 times:
(2 6) (4 10) (5 9) (6 8) (7 7) (9 5) (10 4) (11 3)
display heap after extract min:
size:2
capacity:4
(index, key, data):
(0 12 2) (1 13 1)

Assignment 9 Objectives â€¢ Hash tables and applications â€¢ Bin...