Uploading programming assignments -- typeset assignments may come laterHEADmaster

8 files changed, 421 insertions, 0 deletions

diff --git a/Assign5/hash.cpp b/Assign5/hash.cpp
new file mode 100644
index 0000000..2e63984
--- /dev/null
+++ b/Assign5/hash.cpp
@@ -0,0 +1,78 @@
+#include<iostream>
+#include"table.hpp"
+
+/* hash.cpp by Adam Carpenter - acarpent - acarpenter@email.wm.edu
+
+This program is a driver that utilizes the table.cpp hash table. It
+reads in input from the command line (or fed in from file) and creates
+an array containing the given items. It then creates hash table objects
+and hashes the items into each of these objects using the four different
+methods described in class: linear probing, quadratic probing, double 
+hashing, and separate chaining. It then calls for printing out all of 
+the hash tables.
+
+*/
+
+void readInput(int inputArray[]) {
+	/* Reads input from command line or from a given file of keys 
+	into an array of size 10 (the maximum number of input items. 
+	*/
+	std::cout << "\nHash Tables!\n\n";
+	std::cout << "Enter up to 10 positive integers to be hashed one at a time.\nWhen you are done, enter -1\n";
+	int tmp = 0;
+	int count = 0;
+	
+	while (tmp != EMPTY && count < 10) {
+		std::cin >> tmp;
+		inputArray[count] = tmp;
+		count++;
+	}
+	
+	// Print entered list
+	std::cout << "\nEntered integers:  ";
+	
+	for (int i = 0; i < 10; i++) {
+	
+		if (inputArray[i] != EMPTY) {
+			std::cout << inputArray[i] << " ";
+		}
+
+	}
+	
+	std::cout << "\n";
+}
+
+int main() {
+	/* main is the primary driver of the hash table demonstration. 
+	It is the caller of all of the subsequent functions and hash
+	table methods. 
+	*/
+	int integerList[10] = {EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY};
+	readInput(integerList);
+	
+	// Linear Probing
+	Table linearTable(false); 
+	linearTable.hashLinear(integerList);
+	std::cout << "\nLinear Probing Hash Table: \n";
+	linearTable.printTable(false);
+	
+	// Quadratic Probing
+	Table quadraticTable(false);
+	quadraticTable.hashQuad(integerList);
+	std::cout << "\nQuadratic Probing Hash Table: \n";
+	quadraticTable.printTable(false);
+	
+	// Double Hashing
+	Table doubleTable(false);
+	doubleTable.hashDouble(integerList);
+	std::cout << "\nExtra Credit: Double Hashing Hash Table: \n";
+	doubleTable.printTable(false);
+	
+	// Separate Chaining
+	Table chainTable(true);
+	chainTable.hashChaining(integerList);
+	std::cout << "\nExtra Credit: Separate Chaining Hash Table: \n";
+	chainTable.printTable(true);
+	
+	return 0;
+}
diff --git a/Assign5/keys.txt b/Assign5/keys.txt
new file mode 100644
index 0000000..9699b3a
--- /dev/null
+++ b/Assign5/keys.txt
@@ -0,0 +1,9 @@
+4371
+1323
+6173
+4199
+4344
+9679
+1989
+-1
+
diff --git a/Assign5/keys2.txt b/Assign5/keys2.txt
new file mode 100644
index 0000000..8ab3f83
--- /dev/null
+++ b/Assign5/keys2.txt
@@ -0,0 +1,9 @@
+4379
+1329
+6179
+4199
+4349
+9679
+1989
+-1
+
diff --git a/Assign5/keys3.txt b/Assign5/keys3.txt
new file mode 100644
index 0000000..245f188
--- /dev/null
+++ b/Assign5/keys3.txt
@@ -0,0 +1,12 @@
+4371
+1323
+6173
+4199
+4344
+9679
+1989
+1788
+2001
+9000
+-1
+
diff --git a/Assign5/keys4.txt b/Assign5/keys4.txt
new file mode 100644
index 0000000..c6ea24d
--- /dev/null
+++ b/Assign5/keys4.txt
@@ -0,0 +1,11 @@
+4379
+1329
+6179
+4199
+4349
+9679
+1989
+9
+2009
+-1
+
diff --git a/Assign5/run.sh b/Assign5/run.sh
new file mode 100644
index 0000000..312e3a1
--- /dev/null
+++ b/Assign5/run.sh
@@ -0,0 +1,8 @@
+clear
+g++ *.cpp -lm -o hash
+./hash < keys.txt
+./hash < keys.txt > myout.txt
+./hash < keys2.txt > myout2.txt
+./hash < keys3.txt > myout3.txt
+./hash < keys4.txt > myout4.txt
+
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<iostream>
+#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";
+		}
+	}
+}
diff --git a/Assign5/table.hpp b/Assign5/table.hpp
new file mode 100644
index 0000000..e8c6336
--- /dev/null
+++ b/Assign5/table.hpp
@@ -0,0 +1,27 @@
+/* Header file containing definitions for the table object class. 
+Also contains the NODE structure for the linked list used for 
+separate chaining. NODE objects contain a key and a pointer to 
+another NODE representing the next node. I created a constant 
+called EMPTY that uses the int -1 to represent an empty slot in a table. 
+*/
+static const int EMPTY = -1;
+
+struct NODE {
+	int key;
+	NODE *next;
+};
+
+class Table {
+	private: 
+		int tableArray[10];
+		int unhashableList[10];
+		bool unhashable;
+		NODE *tableHeads[10];
+	public:
+		Table(bool);
+		void hashLinear(int[]);
+		void hashQuad(int[]);
+		void hashDouble(int[]);
+		void hashChaining(int[]);
+		void printTable(bool);
+};