Question

Project Description:

In this project, you will combine the work you’ve done in previous assignments to create a separate chaining hash table.

Overview of Separate Chaining Hash Tables

The purpose of a hash table is to store and retrieve an unordered set of items. A separate chaining hash table is an array of linked lists. The hash function for this project is the modulus operator item%tablesize. This is similar to the simple array hash table from lab 5. However, the elements of array will contain a different data structure from lab 5. In this project, each element of the array will store a head pointer to a linked list. The hash function tells us in which list to insert an item from our data set. When two items hash to the same bucket value, the item is added to the linked list located at that bucket.

In the example below, our data set consists of {40, 53, 363, 46, 16, 218}. The name of the hash table is an array named vals. The hash table size is 10. The index values are also called buckets. The example below has ten buckets. Each item is stored in a node in a linked list based on the result of the hash function. The node is a struct with two data members, an int to store the value of the data set item, and a next pointer.

vals[0]	40%10	= 0		and	363%10	=	3
vals[3]	53%10	= 3
vals[6]	46%10	=	6	and	16%10	=	6
vals[8] 218%10		=	8

Project Specifications:

The project specifications are similar to those in lab 5 with a few differences. The hash table has a different size. The array elements are head pointers to linked lists. And the final print format has changed to accommodate linked lists.

• Your program will have 3 integer values as its command line parameters:

1. 1. seed A random number seed
2. 2. dataSetRange The upper bound of the range of values for the integers in the input data. The lower bound will always be zero.
3. 3. dataSetSize The size of the input data set. This will be the length of the input array.

• Your program will start by printing an informational message, stating your name, lab section, and what the program will do.
• In main() it will allocate memory for two arrays. The inputArray will contain the set of random integers within the specified dataSetRange. The inputArray length can be any positive integer and is input on the command line in dataSetSize. It is recommended to use small numbers at first to more easily test whether your results are correct.

The second array will be the hash table. It is an array of head pointers to linked lists named hashTable. Each element is a pointer to a node struct. The length will be dataSetSize.

• The program will then perform the following steps:

1. Call a function that will assign random integers within the data set range to the elements in the input array. The prototype of the function should be:

void CreateInputArray(int *inputArray, const int dataSetSize, int dataSetRange);

2. After returning from the function described in 1 above, print the input array to the

screen. Use a single blank space between each number so the list fits on one line of an 80 character wide terminal. Make a separate function to do this.

3. A separate function is then called to initialize the array that will be the hash table. The length of the hash table, htSize, is dataSetSize. The hash table element values are initialized to NULL pointers to node structs. The prototype for this functions is:

void InitializeHashTable(node **hashTable, const int htSize);

4. A separate function is then called to process the input data set and store the items in the hashTable. This function will pass in parameters for the two arrays. The prototype for this function is:

void processData(node **hashTable, const int htSize,

int *inputArray, const int dataSetSize);

This function will call linked list functions similar to project 2 to create nodes and store them in linked lists. You can either append or insert the nodes. There is an opportunity to earn extra credit by using a sorted linked list. (Extra credit details are on the last page.)

Details to process the data in linked lists:

• Define a node struct appropriate for holding a random integer. This struct will also contain a “next” pointer to reference a separate instance of the struct.
• Use the typedef keyword to give your struct a separate type name.
• The program will read each integer from the input array. The integer will become the data value for the node.
• The program will use the hash function to compute the hash value of the integer.
• The node will be added to the linked list at the bucket for the hash value.
• You will implement the program using a pointer to the head of the linked list. The head of the list will be accessed through a pointer. (If you choose to use a sorted list, the data contained in the head of the list will be used for sorting purposes.) Do not use a “dummy node” for the linked list.
• Your program must contain the following functions:
• • insertNode( ) – You may implement this either of two ways
• • • Use the head of the list as one parameter and the integer value as the second. The function will allocate memory for the node, initialize it and then insert it into the linked list.
    • Pass the head of the list as one parameter and a previously allocated and initialized node as the other. The existing node is inserted into the list.
  • printList( ) – Takes the head of the list as its only parameter, traverses the list, printing out the data in sorted order.
• • deleteList( ) – Takes the head of the list as its only parameter, traverses the list, deleting all nodes.

5. After returning from the function described in 4, the hash table is printed to the screen in the format below. Make a separate function to do this.

The example vals from above would print as follows:

1. 40
2. 53 363
3. 46 16
4. 218

6. After printing the hash table, delete all the linked lists then free all the memory allocated for the arrays.

Your program must not use any global variables.

Answer 1

The completed C Program is given below. I have added comments to explain what each function does. Please make sure that you fill in your name and lab section in the printf statements at lines 134 and 135.

Source Code:

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

/*

Defines a Linked List node with integer data and a pointer to the next node

*/

struct node {

    int data;

    struct node *next;

};

//Type definition for the node structure

typedef struct node node;

//Function Prototypes for the LinkedList methods

void insertNode(node **,int);

void printList(node *);

void deleteList(node **);

//Fills the input array with random numbers in the range [1,datasetRange]

void createInputArray(int *inputArray, const int datasetSize, int datasetRange) {

    for(int i = 0; i < datasetSize; i++)

        inputArray[i] = rand() % datasetRange + 1;

}

//Initializes the elements in the hashTable (which is an array of node pointers) to NULL

void InitializeHashTable(node **hashTable, const int htSize) {

    for(int i = 0; i < htSize; i++)

        hashTable[i] = NULL;

}

//Inserts the data in the inputArray into the hashTable. It calculates the hashCode as

//val % htSize and inserts it as node in the LinkedList at the index given by the hash code

void processData(node **hashTable, const int htSize, int *inputArray, const int dataSetSize) {

    for(int i = 0; i < dataSetSize; i++) {

        insertNode(&hashTable[inputArray[i]%htSize],inputArray[i]);

    }

}

//Prints the values in hash Table row by row. It only prints non-empty rows (hashTable[i] != NULL)

void printHashTable(node **hashTable, int htSize) {

    for(int i = 0; i < htSize; i++) {

        if(hashTable[i] != NULL) {

            printList(hashTable[i]);

            printf("\n");

        }

    }

}

//Deletes all the elements in the linked lists at each index in the hashTable

void clearHashTable(node **hashTable, int htSize) {

    for(int i = 0; i < htSize; i++) {

        if(hashTable[i] != NULL) {

            deleteList(&hashTable[i]);

        }

    }

}

//Inserts an element into a linked list in sorted order

void insertNode(node **head, int data) {

    //create the new node and fill it with our data parameter

    node *newNode = (node *) malloc(sizeof(node));

    newNode->data = data;

    newNode->next = NULL;

    //check for empty list condition

    if(*head == NULL) {

        *head = newNode;

    }

    else {

        //set two tacers, temp (for the current node), prev for the previous node

        node *temp = *head;

        node *prev = NULL;

        //walk till temp[next] is not NULL and data is greater than the data at current node

        while(temp != NULL && data > temp->data) {

            prev = temp;

            temp = temp->next;

        }

        //once stopped check if prev is still NULL. If prev is NULL this means, our data is smaller

        //than head node. Then we insert at head

        if(prev == NULL) {

            newNode->next = temp;

            *head = newNode;

        }

        //Otheriwse the prev Node is the node on which we perform insert

        else {

            //If our element is not the last element connect it to the next of prev

            if(prev->next != NULL) {

                newNode->next = prev->next;

            }

            prev->next = newNode;

        }

    }

}

//Prints the data of LinkedList

void printList(node *head) {

    node *temp = head;

    while(temp != NULL) {

        printf("%d ",temp->data);

        temp = temp->next;

    }

}

//Deletes all nodes in the Linked List one by one

void deleteList(node **head) {

    node *curr = *head;

    node *nextNode;

    while(curr != NULL) {

        nextNode = curr->next;

        free(curr);

        curr = nextNode;

    }

    *head = NULL;

}

int main(int argc, char **argv[]) {

    //check if sufficient arguments have been provided

    //if not print an error message

    if(argc < 4) {

        printf("Too few arguments povided : %d. Expected 3",argc-1);

        return 1;

    }

    else {

        //use atoi to convert character arrays/pointers to integer values

        int seed = atoi(argv[1]);

        int datasetRange = atoi(argv[2]);

        int datasetSize = atoi(argv[3]);

        //In this section write your name and Lab section

        printf("Name: Your Name Here\n");

        printf("Lab Section: Your Lab Section Here\n");

        printf("This program creates a hashtable that uses separate chaining, with the data\n");

        printf("it recieves from the input array which has its data generated randomly in the range\n");

        printf("[0,%d] as provided in the command line arguments\n\n",datasetRange);

        int *inputArray = (int *)malloc(datasetSize * sizeof(int));

        srand(seed);

        createInputArray(inputArray,datasetSize,datasetRange);

        printf("\n");

        for(int i = 0; i < datasetSize; i++) {

            printf("%d ",inputArray[i]);

        }

        printf("\n");

        node **hashTable = (node **)malloc(datasetSize * sizeof(node *));

        InitializeHashTable(hashTable,datasetSize);

        processData(hashTable,datasetSize,inputArray,datasetSize);

        printHashTable(hashTable,datasetSize);

        clearHashTable(hashTable,datasetSize);

        free(inputArray);

        free(hashTable);

    }

    return 0;

}

Sample Output:

In the first run we are passing a seed value of 153678, datasetRange = 93 and datasetSize = 10, as the command line arguments to our executable. If you don't specify the command line arguments, you will get a message like: "Too few arguments povided".

In the second run, our seed value and datasetSize is same but we have increased datasetRange to 350

HP@DESKTOP-807BNBF $ ./hash 1536787 93 10 Name: Your Name Here Lab Section: Your Lab Section Here This program creates a hashtable that uses separate chaining, with the data it recieves from the input array which has its data generated randomly in the range [0,93] as provided in the command line arguments 62 92 11 1 35 44 70 35 65 60 60 70 1 11 62 92 44 35 35 65 HP@DESKTOP-807BNBF $ ./hash 1536787 350 10 Name: Your Name Here Lab Section: Your Lab Section Here This program creates a hashtable that uses separate chaining, with the data it recieves from the input array which has its data generated randomly in the range [0,350] as provided in the command line arguments 79 248 125 163 121 168 227 174 298 205 121 163 174 125 205 227 168 248 298 79 HP@DESKTOP-807BNBF $1