From ba837332565a2b4a667bd1350a062e1007d4a5c4 Mon Sep 17 00:00:00 2001 From: Adam Carpenter <53hornet@gmail.com> Date: Sat, 3 Dec 2016 10:47:17 -0500 Subject: Uploading programming assignments -- typeset assignments may come later --- Assign5/table.cpp | 267 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 267 insertions(+) create mode 100644 Assign5/table.cpp (limited to 'Assign5/table.cpp') diff --git a/Assign5/table.cpp b/Assign5/table.cpp new file mode 100644 index 0000000..33a44de --- /dev/null +++ b/Assign5/table.cpp @@ -0,0 +1,267 @@ +#include +#include"table.hpp" + +Table::Table(bool useChaining = false) { + /* This constructor takes in a boolean value as a parameter. + The boolean value useChaining represents + whether or not the user intends on using separate chaining + as their hashing method. When set to true, the constructor + will create a table object represented by an array of pointers + to the heads of linked lists, a structure more appropriate + for separate chaining. When useChaining is false, the + constructor defaults to a simple array-based hash table. + */ + + if (useChaining) { + + // initialize array of linked list heads + for (int i = 0; i < 10; i++) { + tableHeads[i] = NULL; + } + + } + else { + unhashable = false; + + // initialize array with 'empty' values + for (int i = 0; i < 10; i++) { + tableArray[i] = EMPTY; + unhashableList[i] = EMPTY; + } + + } + +} + +void Table::hashLinear(int intList[]) { + /* Implementation of hash table insertion using linear probing. + This method takes in an array of integers (10 items max) and hashes + them into a table object using linear probing for conflict resolution. + This means that the probe distance is equal to the number of probing + attempts, or, f(i) = i. An item cannot be hashed into the table if the probing + results in cycling around to the original insertion location again. + */ + int count = 0; + int slotIndex = 0; + int originalSlotIndex; + bool probeFinished; + + while (intList[count] != EMPTY && count < 10) { + slotIndex = intList[count] % 10; + + if (tableArray[slotIndex] == EMPTY) { // slot empty; insert item + tableArray[slotIndex] = intList[count]; + } + else { // slot taken; must probe + originalSlotIndex = slotIndex; + probeFinished = false; + + while (!probeFinished) { + slotIndex++; // f(i) = i + + if (slotIndex > 9) { // wrap around array + slotIndex = slotIndex - 10; + } + + if (slotIndex == originalSlotIndex) { // gone over whole array; end probing + unhashable = true; + unhashableList[count] = intList[count]; + probeFinished = true; + } + + if (tableArray[slotIndex] == EMPTY) { // slot empty; insert item + tableArray[slotIndex] = intList[count]; + probeFinished = true; + } + + } + + } + + count++; + } + +} + +void Table::hashQuad(int intList[]) { + /* Implementation of hash table insertion using quadratic probing. + This method takes in an array of integers (10 items max) and hashes + them into a table object using quadratic probing for conflict resolution. + This means that the probe distance is equal to the number of probing + attempts squared, or, f(i) = i^2. An item cannot be hashed into the table if the probing + results in cycling around to the original insertion location again. + */ + int count = 0; + int probeCount = 0; + int slotIndex = 0; + int originalSlotIndex; + bool probeFinished; + + while (intList[count] != EMPTY && count < 10) { + slotIndex = intList[count] % 10; + + if (tableArray[slotIndex] == EMPTY) { // slot empty; insert item + tableArray[slotIndex] = intList[count]; + } + else { // slot taken; must probe + originalSlotIndex = slotIndex; + probeCount = 0; + probeFinished = false; + + while (!probeFinished) { + probeCount++; + slotIndex = originalSlotIndex + (probeCount * probeCount); // f(i) = i^2 + + while (slotIndex > 9) { // wrap around array multiple times + slotIndex = slotIndex - 10; + } + + if (probeCount > 5) { + unhashable = true; + unhashableList[count] = intList[count]; + probeFinished = true; + } + + if (tableArray[slotIndex] == EMPTY) { // slot empty; insert item + tableArray[slotIndex] = intList[count]; + probeFinished = true; + } + + } + + } + + count++; + } + +} + +void Table::hashDouble(int intList[]) { + /* Implementation of hash table insertion using double hashing. + This method takes in an array of integers (10 items max) and hashes + them into a table object using a second hash function for conflict resolution. + The second hash function is equivalent to f(x) = 7 - x % 7. An item cannot be + hashed into the table if the probing results in cycling around to the original + insertion location again. + */ + int count = 0; + int probeCount = 0; + int slotIndex = 0; + int originalSlotIndex; + bool probeFinished; + + while (intList[count] != EMPTY && count < 10) { + slotIndex = intList[count] % 10; + + if (tableArray[slotIndex] == EMPTY) { // slot empty; insert item + tableArray[slotIndex] = intList[count]; + } + else { // slot taken; must probe + originalSlotIndex = slotIndex; + probeCount = 0; + probeFinished = false; + + while (!probeFinished) { + probeCount++; + slotIndex = originalSlotIndex + (probeCount * (7 - intList[count] % 7)); // f(x) = 7 - x % 7 + + while (slotIndex > 9) { // wrap around array + slotIndex = slotIndex - 10; + } + + if (slotIndex == originalSlotIndex) { // gone over whole array; end probing + unhashable = true; + unhashableList[count] = intList[count]; + probeFinished = true; + } + + if (tableArray[slotIndex] == EMPTY) { // slot empty; insert item + tableArray[slotIndex] = intList[count]; + probeFinished = true; + } + + } + + } + + count++; + } + +} + +void Table::hashChaining(int intList[]) { + /* Implementation of hash table insertion using separate chaining. + This method takes in an array of integers (10 items max) and hashes + the items into a table object using separate chaining for conflict + resolution. This means for each insertion index, a linked list exists + where all of the values that hash to that index are inserted at the head + of the linked list. + */ + int count = 0; + int slotIndex = 0; + NODE *newHead; + + while (intList[count] != EMPTY && count < 10) { + newHead = new NODE(); + slotIndex = intList[count] % 10; + newHead->key = intList[count]; + newHead->next = tableHeads[slotIndex]; + tableHeads[slotIndex] = newHead; + count++; + } + +} + +void Table::printTable(bool useChaining = false) { + /* A method for printing out the contents of a hash table object + that creates a visual representation of the hash table and its + contents and prints them to the console (or a file if directed). + This method takes in a boolean value letting the method know + whether or not to print a separately-chained linked hash table + with a linke list or a hash table based on an array (ex. linear + probing). + */ + if (useChaining) { + NODE *node = new NODE(); + + // print visual hash table of items from linked lists + for (int i = 0; i < 10; i++) { + std::cout << "[" << i << "]" << "-> "; + + for (node = tableHeads[i]; node != NULL; node = node->next) { + std::cout << node->key << " -> "; + delete node; // have to clean up nodes from memory + } + + std::cout << "_\n"; + } + + } + else { + // print visual hash table of items from array + for (int i = 0; i < 10; i++) { + std::cout << "[" << i << "]" << " "; + + if (tableArray[i] != EMPTY) { + std::cout << tableArray[i]; + } + + std::cout << "\n"; + } + + // print items that could not be inserted + if (unhashable) { + std::cout << "The following item(s) could not be inserted: "; + + for (int i = 0; i < 10; i++) { + + if (unhashableList[i] != EMPTY) { + std::cout << unhashableList[i] << " "; + } + + } + + std::cout << "\n"; + } + } +} -- cgit v1.2.3