1. [30%] Code Snippet 1

Given snippet code below that you are required to complete. You are not allowed to make a new function or change any given code. Please complete each section that are marked with the notation INSERT YOUR CODE HERE.

Once you complete the snippet below, your output should have the same result with the given output below.

Descriptions:

1. [10%] generateKey()

This function is built for generating key in the hashTable. The key should be generated by calculate the summation of each ascii character of attribute name, subsequently use division method in corresponding to tableSize.

2. [10%] searchNode()

This function is built for searching whether the current node has the same data with the existing data in the hash table. If it is found, then the location of the current node will be returned. The similary checking by comparing the name and category.

3. [10%] push()

This function is built for inserting a new data in the hashTable. This hashTable could handle the duplicated data by increasing the qty number. If the new data is novel (not found in the existing hashTable), then the new node will be generated in the hashTable.

// // Created by Hanry Ham on 2020-05-24. // #include #include #include #define tableSize 29 struct storage{ int key; int qty; char name[25]; char category[20]; struct storage *next; }; struct hashPool{ struct storage *head; struct storage *tail; }; struct hashPool hashTable[tableSize]; void init(){ for(int i=0; ikey = generateKey(name); curr->qty = 1; strcpy(curr->name, name); strcpy(curr->category, category); curr->next = NULL; return curr; } struct storage *searchNode(struct storage *node){ struct storage *search= hashTable[node->key].head; struct storage *temp = NULL; // [10%] (2) INSERT YOUR CODE HERE 

 return temp; } void push(struct storage *node){ // [10%] (3) INSERT YOUR CODE HERE } void printAll(){ for(int i=0; i ", curr->name, curr->qty); curr = curr->next; } printf("NULL "); } } int main(){ init(); push(newNode("Sate Ayam", "Daging")); push(newNode("Sate Ayam", "Daging")); push(newNode("Gulai Kambing", "Daging")); push(newNode("Kangkung", "Sayuran")); push(newNode("Sate Ayam", "Daging")); push(newNode("Coca Cola", "Minuman")); push(newNode("Sate Ayam", "Daging")); push(newNode("Coca Cola", "Minuman")); push(newNode("Gulai Kambing", "Daging")); push(newNode("Sate Kambing", "Daging")); push(newNode("Opor Ayam", "Daging")); push(newNode("Sate Kambing", "Daging")); push(newNode("Sate Kambing", "Daging")); printAll(); return 0; }

Output:

[ 0] : NULL

[ 1] : NULL

[ 2] : NULL

[ 3] : NULL

[ 4] : NULL

[ 5] : NULL

[ 6] : Coca Cola (2 ) -> NULL

[ 7] : NULL

[ 8] : NULL

[ 9] : Sate Ayam (4 ) -> Gulai Kambing (2 ) -> NULL

[10] : Kangkung (1 ) -> NULL

[11] : NULL

[12] : NULL

[13] : NULL

[14] : NULL

[15] : NULL

[16] : NULL

[17] : NULL

[18] : NULL

[19] : NULL

[20] : NULL

[21] : NULL

[22] : NULL

[23] : NULL

[24] : Sate Kambing (3 ) -> NULL

[25] : NULL

[26] : NULL

[27] : NULL

[28] : Opor Ayam (1 ) -> NULL

2. [30%] Code Snippet 2

Given snippet code below that you are required to complete. You are not allowed to make a new function or change any given code. Please complete each section that are marked with the notation INSERT YOUR CODE HERE.

Once you complete the snippet below, your output should have the same result with the given output below.

Descriptions:

1. [15%] linearProbing()

This function is built for executing linearProbing. Basically, linearProbing will check all the index in hashTable, and will put new data in the empty index. If all the indexes are occupied then it will return -1 and if the index in hashTable is still empty, it will return the new key.

2. [15%] insert()

This function is built for inserting a new data by using linearProbing.

// // Created by Hanry Ham on 2020-05-24. // #include #include #include struct storage{ char name[25]; char category[20]; }; const int tableSize = 7; struct storage hashTable[tableSize]; void init(){ for(int i=0; i 
 
 

Output:

The hashTable is full!

The hashTable is full!

[ 0] : Opor Ayam

[ 1] : Sprite

[ 2] : Coca Cola

[ 3] : Kangkung

[ 4] : Sate Ayam

[ 5] : Sate Kambing

[ 6] : Gulai Kambing

3. [40%] Code Snippet 3

Given snippet code below that you are required to complete. You are not allowed to make a new function or change any given code. Please complete each section that are marked with the notation INSERT YOUR CODE HERE.

Once you complete the snippet below, your output should have the same result with the given output below.

Descriptions:

1. [10%] insert()

This function is built for inserting a new node in our existing Binary Search Tree (BST). In this insert function, you should handle if any duplicated data found, then the quantity should be increase as well.

2. [5%] predecessor()

This function is built for finding the left right most node in the existing BST.

3. [5%] successor()

This function is built for finding the right left most node in the existing BST.

4. [15%] deleteKey()

This function is built for deleting a node in our BST. If the qty of the interested node > 1, then program will decrease the number of qty by 1. On the other hand, if the qty = 1, then you are allowed to delete the node.

5. [5%] inOrder()

This function is built for printing out the existing BST inOrder way.

// // Created by Hanry Ham on 2020-05-25. // #include #include #include struct storage{ int qty; char name[25]; char category[20]; struct storage *left; struct storage *right; }; struct storage *newNode(const char *name, const char *category){ struct storage *curr = (struct storage *) malloc(sizeof(struct storage)); curr->qty = 1; strcpy(curr->name, name); strcpy(curr->category, category); curr->left = NULL; curr->right = NULL; return curr; } struct storage *insert(struct storage *root, const char *name, const char *category){ // [10%] (1) INSERT YOUR CODE HERE return root; } struct storage *predecessor(struct storage *root){ // [5%] (2) INSERT YOUR CODE HERE } struct storage *successor(struct storage *root){ // [5%] (3) INSERT YOUR CODE HERE } struct storage *deleteKey(struct storage *root, const char *name){ // [15%] (4) INSERT YOUR CODE HERE return root; } void inOrder(struct storage *root){ if(root){

 // [5%] (5) INSERT YOUR CODE HERE

 } } struct storage *freeAll(struct storage *root){ if(root){ freeAll(root->left); freeAll(root->right); free(root); root = NULL; } return root; } int main(){ struct storage *root = NULL; root = insert(root, "Sate Ayam", "Daging"); root = insert(root, "Gulai Kambing", "Daging"); root = insert(root, "Kangkung", "Sayuran"); root = insert(root, "Coca Cola", "Minuman"); root = insert(root, "Sate Kambing", "Daging"); root = insert(root, "Opor Ayam", "Daging"); root = insert(root, "Sprite", "Minuman"); root = insert(root, "Fanta", "Minuman"); root = insert(root, "Ayam Kalasan", "Daging"); root = insert(root, "Kangkung", "Sayuran"); root = insert(root, "Fanta", "Minuman"); root = insert(root, "Coca Cola", "Minuman"); root = insert(root, "Opor Ayam", "Daging"); printf("Predecessor : %s ", predecessor(root)->name); printf("Successor : %s ", successor(root)->name); printf(" Inorder : "); inOrder(root); root = deleteKey(root, "Sate Ayam"); root = deleteKey(root, "Gulai Kambing"); root = deleteKey(root, "Coca Cola"); root = deleteKey(root, "Opor Ayam"); root = deleteKey(root, "Sate Kambing"); root = deleteKey(root, "Ayam Kalasan"); printf(" After Del Inorder : "); inOrder(root); freeAll(root); return 0; }

Output:

Predecessor : Opor Ayam

Successor : Sate Kambing

Inorder :

Ayam Kalasan(1 )

Coca Cola (2 )

Fanta (2 )

Gulai Kambing(1 )

Kangkung (2 )

Opor Ayam (2 )

Sate Ayam (1 )

Sate Kambing(1 )

Sprite (1 )

After Del Inorder :

Coca Cola (1 )

Fanta (2 )

Kangkung (2 )

Opor Ayam (1 )

Sprite (1 )