Time limit: 5000ms
Memory limit: 256mb
Description:
This program is to insert several key-record pairs into hash table using chaining, delete some keys and search some keys.
-------------------------Copy the following code, complete it and submit-------------------------
/*
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/
#include <stdio.h>
#include <stdlib.h>
const int hashTableSize = 29989;
struct Node {
int key;
int record;
struct Node* next;
struct Node* prev;
};
struct LinkedList {
struct Node* head;
struct Node* tail;
};
/**
* @brief: create a linked list
* @param: void
* @return: address of the linkd list
* @usage: struct LinkedList* newList = CreateEmptyList()
*/
struct LinkedList* CreateEmptyList() {
struct LinkedList* newList = (struct LinkedList*) malloc(sizeof(struct LinkedList));
struct Node* newHead = (struct Node*) malloc(sizeof(struct Node));
struct Node* newTail = (struct Node*) malloc(sizeof(struct Node));
newHead->next = newTail;
newHead->prev = NULL;
newTail->prev = newHead;
newTail->next = NULL;
newList->head = newHead;
newList->tail = newTail;
return newList;
}
/**
* @brief: create an node
* @param: 1. key 2. record
* @return: address of the node
* @usage: struct Node* newNode = CreateNode(yourKey, yourRecord)
*/
struct Node* CreateNode(int key, int record) {
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->key = key;
newNode->record = record;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
/**
* @brief: find the node in a list using key
* @param: 1. list 2. key
* @return: If founded, return the address of the node. If not, return NULL.
* @usage: struct Node* node = FindItemInList(yourList, yourKey)
*/
struct Node* FindItemInList(struct LinkedList* list, int key) {
struct Node* tmp = list->head->next;
while (tmp != list->tail) {
if (tmp->key == key) {
return tmp;
} else {
tmp = tmp->next;
}
}
return NULL;
}
/**
* @brief: insert a key-record pair into a list. If key has existed, modify its record with new one
* @param: 1. list 2. key 3. record
* @return: void
* @usage: InsertIntoList(yourList, yourKey, yourRecord)
*/
void InsertIntoList(struct LinkedList* list, int key, int record) {
struct Node* isExisted = FindItemInList(list, key);
if (isExisted != NULL) {
isExisted->record = record;
} else {
struct Node* newNode = CreateNode(key, record);
newNode->next = list->tail;
newNode->prev = list->tail->prev;
list->tail->prev->next = newNode;
list->tail->prev = newNode;
}
}
/**
* @brief: delete a key from a list. If key does not exist, do nothing.
* @param: 1. list 2. key
* @return: void
* @usage: DeleteFromList(yourList, yourKey)
*/
void DeleteFromList(struct LinkedList* list, int key) {
struct Node* isExisted = FindItemInList(list, key);
if (isExisted != NULL) {
struct Node* nextOne = isExisted->next;
struct Node* prevOne = isExisted->prev;
prevOne->next = nextOne;
nextOne->prev = prevOne;
free(isExisted);
}
}
/**
* @brief: get the hash value of a key
* @param: 1. key
* @return: hash value
* @usage: int hashValue = HashFunction(yourKey)
*/
int HashFunction(int key) {
return key % hashTableSize;
}
/**
* @brief: insert an node into a hashTable. If key has existed, modify its record with new one
* @param: 1. hashTable 2. key 3. record
* @return: void
* @usage: InsertNode(yourHashTable, yourKey, yourRecord)
*/
void InsertHashTable(struct LinkedList* hashTable[], int key, int record) {
// WRITE YOUR CODE HERE
// DO NOT MODIFY THE OTHER CODE
// you could use the function "InsertIntoList"
}
/**
* @brief: search an node in a hashTable.
* @param: 1. hashTable 2. key
* @return: If key does not exist, return -1. Or, return the record.
* @usage: int record = SearchNode(yourHashTable, yourKey)
*/
int SearchHashTable(struct LinkedList* hashTable[], int key) {
// WRITE YOUR CODE HERE
// DO NOT MODIFY THE OTHER CODE
// you could use the function "FindItemInList"
}
/**
* @brief: delete a key from a hashTable. If key does not exist, do nothing.
* @param: 1. hashTable 2. key
* @return: void
* @usage: DeleteNode(yourHashTable, yourKey)
*/
void DeleteHashTable(struct LinkedList* hashTable[], int key) {
// WRITE YOUR CODE HERE
// DO NOT MODIFY THE OTHER CODE
// you could use the function "DeleteFromList"
}
int main() {
struct LinkedList* hashTable[hashTableSize];
for (int i = 0; i < hashTableSize; i++) {
hashTable[i] = CreateEmptyList();
}
int operation;
int key, record;
int searchResult;
scanf("%d", &operation);
while (1) {
if (operation == 0) {
break;
} else if (operation == 1) {
scanf("%d%d", &key, &record);
InsertHashTable(hashTable, key, record);
} else if (operation == 2) {
scanf("%d", &key);
searchResult = SearchHashTable(hashTable, key);
printf("%d\n", searchResult);
} else if (operation == 3) {
scanf("%d", &key);
DeleteHashTable(hashTable, key);;
} else {
printf("error\n");
exit(30);
}
scanf("%d", &operation);
}
printf("\n");
}
-------------------------------------------End of Code-------------------------------------------
Input:
For every line, the first number is operation type.
If the operation type is 0, stop all the following input.
If the operation type is 1, it means insertion. And the second and third number of this line are the key and record. Then you should add this key-record into hash table using chaing. If key does already exist, modify its record.
If the operation type is 2, it means query. And the second number of this line is the search key. Then you should query this key in the hash table and print the record. If the key does not exist, print "-1".
If the operation type is 3, it means deletion. And the second number of this line is the key to be deleted. Then you should delete this key from hash table. If the key does not exist, do nothing.
Output:
For every insertion, print the search result.
Sample Input 1:
1 4 167
2 4
3 2
3 4
2 4
1 1 135
2 1
1 1 371
2 1
0
Sample Output 1:
167
-1
135
371