//************************ intSLList.cpp **************************

#include #include "intSLList.h"

using namespace std;

IntSLList::~IntSLList() { for (IntSLLNode *p; !isEmpty(); ) { p = head->next; delete head; head = p; } }

void IntSLList::addToHead(int el) { head = new IntSLLNode(el,head); if (tail == 0) tail = head; }

void IntSLList::addToTail(int el) { if (tail != 0) { // if list not empty; tail->next = new IntSLLNode(el); tail = tail->next; } else head = tail = new IntSLLNode(el); }

int IntSLList::deleteFromHead() { int el = head->info; IntSLLNode *tmp = head; if (head == tail) // if only one node on the list; head = tail = 0; else head = head->next; delete tmp; return el; }

int IntSLList::deleteFromTail() { int el = tail->info; if (head == tail) { // if only one node on the list; delete head; head = tail = 0; } else { // if more than one node in the list, IntSLLNode *tmp; // find the predecessor of tail; for (tmp = head; tmp->next != tail; tmp = tmp->next); delete tail; tail = tmp; // the predecessor of tail becomes tail; tail->next = 0; } return el; }

void IntSLList::deleteNode(int el) { if (head != 0) // if non-empty list; if (head == tail && el == head->info) { // if only one delete head; // node on the list; head = tail = 0; } else if (el == head->info) { // if more than one node on the list IntSLLNode *tmp = head; head = head->next; delete tmp; // and old head is deleted; } else { // if more than one node in the list IntSLLNode *pred, *tmp; for (pred = head, tmp = head->next; // and a non-head node tmp != 0 && !(tmp->info == el);// is deleted; pred = pred->next, tmp = tmp->next); if (tmp != 0) { pred->next = tmp->next; if (tmp == tail) tail = pred; delete tmp; } } }

bool IntSLList::isInList(int el) const { IntSLLNode *tmp; for (tmp = head; tmp != 0 && !(tmp->info == el); tmp = tmp->next); return tmp != 0; }

void IntSLList::printAll() const { for (IntSLLNode *tmp = head; tmp != 0; tmp = tmp->next) cout info

int IntSLList::find_min() {

return 0; }

IntSLList IntSLList::sort_list(){ IntSLList list; return list; }

void IntSLList::swap_nodes(int val) {

}

//************************ intSLList.h ************************** // singly-linked list class to store integers

#ifndef INT_LINKED_LIST #define INT_LINKED_LIST

class IntSLLNode { public: IntSLLNode() { next = 0; } IntSLLNode(int el, IntSLLNode *ptr = 0) { info = el; next = ptr; } int info; IntSLLNode *next; };

class IntSLList { public: IntSLList() { head = tail = 0; } ~IntSLList(); int isEmpty() { return head == 0; } void addToHead(int); void addToTail(int); int deleteFromHead(); // delete the head and return its info; int deleteFromTail(); // delete the tail and return its info; void deleteNode(int); bool isInList(int) const; void printAll() const; IntSLList sort_list(); void swap_nodes(int); int find_min(); private: IntSLLNode *head, *tail; };

#endif

#include #include

// Well, power operation in C++ requires this library. // I'm pretty sure you'll find out why the power operation would be required. #include

#include "intSLList.h"

using namespace std;

// This one is our hash table IntSLList hashTable[10];

// Also we need to store our input types to differentiate strings and large integers // Using 0 for Int, 1 for String, basically? IntSLList hashType[10];

// Function initial declarations void pleaseHelpMeWithHashValues(); void insertIntoHashTable(int input); void insertIntoHashTable(const char* input); bool searchInHashTable(int input); bool searchInHashTable(const char* input); void printHashTable();

// Hashing function for integer inputs. // This function should insert an element only // if there are no duplicates within the table. void insertIntoHashTable(int input) {

int hashAddress = input % 10;

// We need to check whether the value is in hash or not if (!searchInHashTable(input)) { // We need to input for both our Hash Table and Hash Type tables }

return; }

// This may be helpful for your understanding. void pleaseHelpMeWithHashValues() { cout

// Hint: The largest integer that C++ supports is 2147483647 // These characters are 2-digit each. // Let's go with 4-character string support then. // Listed values are greater than 21, that's why we aren't using 5 digits.

return; }

// Hashing function for string inputs. // Remember, one of the best features of C++ is function overloading, // as long as the function signatures are different // you can have two different functions with the same name. void insertIntoHashTable(const char* input) { // Now... Strings. How would you store a string within an integer list? // IntSLList, as the "Int" in its name indicates, only stores Integers. // Then, what magic allows us to somehow do it?.. // Hashing itself! Hashing your string into an integer! // So you should hash your value to hash it. // "ifte kavrulmu" hash? Sort of...

// To treat const char* as a string, you should use string's standard constructor string s = input;

// And you need to hash elements into 2-digits, each, right? // Therefore you need to multiply values to add 0's and separate them.

return; }

// Function to return whether a value is in our hash table or not. bool searchInHashTable(int input) {

// This one is simple. Simply get input's hash value and search input within HashTable[hash]. // There is a function that scans a linked list implemented already. // If the value exists, this function returns true. False otherwise. }

// The same as above, overloaded as hash table insertion. bool searchInHashTable(const char* input) {

// Same as above. However, now you should first hash string to integer for lookup first. }

// You already know printing. No need to take your time with this function. void printHashTable() { for (int i = 0; i

int main() { // ASCII helper function call pleaseHelpMeWithHashValues();

// Sample test lines, comment/delete them initially to be able to run your code. insertIntoHashTable(1); insertIntoHashTable(11); insertIntoHashTable(6); insertIntoHashTable(121); insertIntoHashTable("AAA"); insertIntoHashTable("Y"); insertIntoHashTable("30E"); printHashTable(); cout

return 0; }

I had asked before, but your answer was wrong and incomplete. You did not answer in accordance with the codes I sent. This time, please answer in accordance with the codes and photos I sent. Do not change the names and inputs of the functions. (Please be quick.)

Aim: To learn and implement basics of hashing and to improve your understanding of working within constraints (ie, being have to use the asked function types, learning from the comments...) What is hashing? Hashing is the process of converting a given key into another value. It is used for a fast-access data storage in implementations called "Hash Tables. Let's assume that you have values 5,9,23, 4, 78, 8, 42, 7, 1, 271, 251, 420 in a linked list and you want to find 251. Traditionally, you iterate from the beginning and only access 251 in your 11th iteration. However, a hash table with key value of 10 stores data like this: 0:420 1:1, 271, 251 2:42 3:23 4:4 5:5 6: 7:7 8: 78,8 9:9 Simply, takes modulus of these variables and puts them accordingly. Therefore, if you look up for 251, you simply 251 % 10 and get 1 and only check 1's to find 251 for a much higher search speed. This is a simple hash table application. Another implementation of hashing is for validating data within different data types. Such as encryption and svirtographic operations. There will be some future details given after your assignment explanation. Q (100pts): Write a hash implementation for both integer and up-to-4-digit string type inputs into the main with the prototypes given in the source file main.cpp. Also, you should use linked list implementation given to you previously this semester: IntSLList. The functions you are asked to build are: void insertInto HashTablelint input); void insertInto HashTable(const char* input); bool searchinHashTable(int input); bool searchinHash Table(const char* input); Important: Your work should compile & run along with the example main file provided to you. You can compile multiple spr files using: g++ main.cpp intSlList.cpp Also, make no changes to the given main class except corresponding areas for your functions. You can use existing source and header files intSLList.cpp and intSLList.h which are totally complete. You may also want to use comments efficiently, especially if your assignment isn't 100% done for helping us to understand your studies better. So, if you realized, you are being asked to implement a hash table that can store both integer and up-to-4-digit string values. Yet, your list implementation that should hold values only store integers. How are you supposed to store strings within integers, right? Maybe stoi, but then you cannot differentiate "ASD" from "ADS since the totals would be the same. Then how? With hashing. You can hash the string's character values individually into an integer one by one. For example, ASCII value of character A is 65 and B is 66. If you were to store ABB, you can simply store it as 656666" or "666665" within an integer. And if you unhash it you get ABB. That's another use of hashing for a very simple cryptographic implementation. So, here is an execution snippet for helping you to visualize: insertintoHashTable(1); insertintoHashTable(11); insertintoHashTable(6); insert IntoHashTable(121); insertintoHashTable("AAA"); insertIntoHashTable("Y"); insertintoHashTable("30"); printHashTable(); cout ? @ABCDEFGHIJKLMNO PQRSTUVWXYZ ASCII val. of 'A' is: 65 Value 65 equals to character: A 1:-/Desktop/cse211as95$