I Need help with implementing the Hash Search lab 8, please help there! Lab 8+ h
ID: 659663 • Letter: I
Question
I Need help with implementing the Hash Search lab 8, please help there!
Lab 8+ hashing
Objective
practice search by hashing techniques
Overview
Hashing with linear probing
(bonus) Hashing with quadratic probing
(bonus) Hashing with chaining
Note
Choose your hash function and hash table size that suits your test data such that collision code can be verified.
As an example, if I'm searching just 6 integers, I may have a table of 11 entries and a hashing function of "fold digits mod 11". By mindfully choosing the test data, I would be able to know if my collision algorithm and search algorithm works.
You should write the insertion routine to "add" items into the hash table. It will make it easier to create your database.
Try to do a delete routine too. There are additional considerations to be exercised.
===============================Lab 8========================================
Write a menu driven search program implementing the following:
do {
cout<<" Choose your search type:";
cout<<" 1. Arrays: Sequential Search without recursion";
cout<<" 2. Arrays: Sequential Search with recursion";
cout<<" 3. Ordered Arrays: Binary Search without recursion";
cout<<" 4. Ordered Arrays: Binary Search with recursion";
cout<<" 5. Linked List: Search without recursion";
cout<<" 6. Linked List: Search with recursion";
cout<<" Enter 0 to exit. Your choice: ";
...
cout<<" Specify the element to be searched for: ";
...
} while(i!=0);
Print the list before selecting the element to search for.
The search should return the position of the element (starting at zero). If the element is not in the list, the function should return a negative one (-1).
You may find it useful to create helper functions to create filled linked lists, filled arrays, and sorted arrays.
=================LAB 8 IMPLEMENTATION=================
/*============main.cpp=======================*/
#include <iostream>
#include "lab8.h"
#include <fstream>
using namespace std;
int main()
{
ofstream out_stream;
search as,asr,bs,bsr,ll,llr ;
int i , num;
out_stream.open("output.txt");
do
{
out_stream << " Preloaded list of numbers array and linked list" << endl;
out_stream << "41 67 34 0 69 24 78 58 62 64 " << endl;
cout << " Preloaded list of numbers array and linked list" << endl;
cout << "41 67 34 0 69 24 78 58 62 64 " << endl;
cout<<" Choose type of search:";
cout<<" 1. Arrays: Sequential Search without recursion";
cout<<" 2. Arrays: Sequential Search with recursion";
cout<<" 3. Ordered Arrays: Binary Search without recursion";
cout<<" 4. ordered Arrays: Binary Search with recursion";
cout<<" 5. Linked List: Search with recursion";
cout<<" 6. Linked List: Search without recursion";
cout<<" Enter 0 exit ";
out_stream<<" Choose type of search:";
out_stream<<" 1. Arrays: Sequential Search without recursion";
out_stream<<" 2. Arrays: Sequential Search with recursion";
out_stream<<" 3. Ordered Arrays: Binary Search without recursion";
out_stream<<" 4. ordered Arrays: Binary Search with recursion";
out_stream<<" 5. Linked List: Search with recursion";
out_stream<<" 6. Linked List: Search without recursion";
out_stream<<" Enter 0 exit ";
cin>>i;
cout <<"Picked # " << i << " ";
out_stream << "Picked # " << i << " ";
switch(i){
case 1: as.load();
out_stream << "Enter number in array to search: " << endl;
cout << "Enter number in array to search: ";
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(as.seqsearch(num)){
out_stream << num << " found!" << endl;
cout << num << " found!" << endl;
}else{
out_stream << num << " not found!" << endl;
cout << num << " not found!" << endl;
}
as.cleararray();
break;
case 2: asr.load();
out_stream << "Enter number in array to search: " << endl;
cout << "Enter number in array to search: " << endl;
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(asr.seqserachRecursion(0,num)){
out_stream << num << " found!" << endl;
cout << num << " found!" << endl;
}else{
out_stream << num << " not found!" << endl;
cout << num << " not found!" << endl;
}
asr.cleararray();
break;
case 3: bs.load();
bs.orderloaded();
out_stream << "Enter number in array to search: " << endl;
cout << "Enter number in array to search: " << endl;
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(bs.orderedbinarysearch(num)){
out_stream << num << " found! " << endl;
cout << num << " found! " << endl;
}else{
out_stream << num << " not found! " << endl;
cout << num << " not found! " << endl;
}
bs.cleararray();
break;
case 4: bsr.load();
bsr.orderloaded();
out_stream << "Enter number in array to search: " << endl;
cout << "Enter number in array to search: " << endl;
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(bsr.orderedbinarysearchRecursion(num,0,11)){
out_stream << num << " found! " << endl;
cout << num << " found! " << endl;
}else{
out_stream << num << " not found! " << endl;
cout << num << " not found! " << endl;
}
bsr.cleararray();
break;
case 5: ll.loadlinked();
out_stream << "Enter number in linked list to search: " << endl;
cout << "Enter number in linked list to search: " << endl;
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(ll.linkedsearch(num)){
out_stream << num << " found! " << endl;
cout << num << " found! " << endl;
}else{
out_stream << num << " not found! " << endl;
cout << num << " not found! " << endl;
}
ll.clearlist();
break;
case 6: llr.loadlinked();
out_stream << "Enter number in linked list to search: " << endl;
cout << "Enter number in linked list to search: " << endl;
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(llr.linkedsearchRecursion(num)){
out_stream << num << " found! " << endl;
cout << num << " found! " << endl;
}else{
out_stream << num << " not found! " << endl;
cout << num << " not found! " << endl;
}
llr.clearlist();
break;
}
}while(i!=0);
out_stream.close();
}
/*=================lab8.cpp===================*/
#include <iostream>
#include <vector>
#include <list>
#include <random>
#include <chrono>
#include "lab8.h"
using namespace std;
search::search(){
}
bool search::seqsearch(int num){
for(unsigned int i=0; i < array.size();i++){
if(array[i] == num){
return true;
}
}
return false;
}
bool search::seqserachRecursion(unsigned int start, int num){
if(start == array.size()){ //base case
return false;
}
if(array[start] == num){
return true;
}else{
seqserachRecursion(start+1, num);
}
}
bool search::orderedbinarysearch(int num){
int max = array.size();
int min = 0;
while(max>=min){
int mid = (max+min)/2;
if(array[mid] == num){
return true;
}
else if(array[mid]< num){// upper
min = mid+1;
}else{ // lower
max = mid-1;
}
}
return false;
}
bool search::orderedbinarysearchRecursion(int num, int min, int max){
if(max < min){
return false;
}else{
int mid = (min+max)/2;
if(array[mid]> num){
orderedbinarysearchRecursion(num,min,mid-1);
}
else if(array[mid]<num){
orderedbinarysearchRecursion(num,mid+1,max);
}
else{
return true;
}
}
}
bool search::linkedsearch(int num){
while(!nodes.empty()){
if(num == nodes.front()){
return true;
}else{
nodes.pop_front();
}
}
return false;
}
bool search::linkedsearchRecursion(int num){
if(nodes.empty()){
return false;
}
else if(nodes.front() == num){
return true;
}
else{
nodes.pop_front();
linkedsearchRecursion(num);
}
}
void search::load()
{
array.push_back(41);
array.push_back(67);
array.push_back(34);
array.push_back(0);
array.push_back(69);
array.push_back(24);
array.push_back(78);
array.push_back(58);
array.push_back(62);
array.push_back(64);
}
void search::orderloaded(){ // smallest to largest
for(unsigned int i=0; i<array.size(); i++){
for(unsigned int j=0; j< array.size()-1;j++){
if(array[j]> array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
void search::loadlinked()
{
nodes.push_back(41);
nodes.push_back(67);
nodes.push_back(34);
nodes.push_back(0);
nodes.push_back(69);
nodes.push_back(24);
nodes.push_back(78);
nodes.push_back(58);
nodes.push_back(62);
nodes.push_back(64);
}
void search::cleararray(){
while(!array.empty()){
array.pop_back();
}
}
void search::clearlist(){
while(!nodes.empty()){
nodes.pop_front();
}
}
/*=================lab8.h====================*/
#include <iostream>
#include <vector>
#include <list>
using namespace std;
class search{
public:
search();
bool seqsearch(int num);
bool seqserachRecursion(unsigned int start, int num);
bool orderedbinarysearch(int num);
bool orderedbinarysearchRecursion(int num, int min, int max);
bool linkedsearch(int num);
bool linkedsearchRecursion(int num);
void load();
void orderloaded();
void loadlinked();
void cleararray();
void clearlist();
private:
vector<int> array;
list <int> nodes;
};
Objective
practice search by hashing techniques
Overview
Enhance lab 8 to add more "search with hashing" options:Hashing with linear probing
(bonus) Hashing with quadratic probing
(bonus) Hashing with chaining
Note
Choose your hash function and hash table size that suits your test data such that collision code can be verified.
As an example, if I'm searching just 6 integers, I may have a table of 11 entries and a hashing function of "fold digits mod 11". By mindfully choosing the test data, I would be able to know if my collision algorithm and search algorithm works.
You should write the insertion routine to "add" items into the hash table. It will make it easier to create your database.
Try to do a delete routine too. There are additional considerations to be exercised.
Explanation / Answer
Here is the modified program with hashing and linear probing..enjoy :)
Hint - You can reduce redundancy of code - like instead of writing in each case statement the number to be searched write it once before the case statement.
Program -
Write a menu driven search program implementing the following:
do {
cout<<" Choose your search type:";
cout<<" 1. Arrays: Sequential Search without recursion";
cout<<" 2. Arrays: Sequential Search with recursion";
cout<<" 3. Ordered Arrays: Binary Search without recursion";
cout<<" 4. Ordered Arrays: Binary Search with recursion";
cout<<" 5. Linked List: Search without recursion";
cout<<" 6. Linked List: Search with recursion";
cout<<" 7. Hash Table: Search with hashing and linear probing";
cout<<" Enter 0 to exit. Your choice: ";
...
cout<<" Specify the element to be searched for: ";
...
} while(i!=0);
Print the list before selecting the element to search for.
The search should return the position of the element (starting at zero). If the element is not in the list, the function should return a negative one (-1).
You may find it useful to create helper functions to create filled linked lists, filled arrays, and sorted arrays.
=================LAB 8 IMPLEMENTATION=================
/*============main.cpp=======================*/
#include <iostream>
#include "lab8.h"
#include <fstream>
using namespace std;
int main()
{
ofstream out_stream;
search as,asr,bs,bsr,ll,llr,hashed ;
int i , num;
out_stream.open("output.txt");
do
{
out_stream << " Preloaded list of numbers array and linked list" << endl;
out_stream << "41 67 34 0 69 24 78 58 62 64 " << endl;
cout << " Preloaded list of numbers array and linked list" << endl;
cout << "41 67 34 0 69 24 78 58 62 64 " << endl;
cout<<" Choose type of search:";
cout<<" 1. Arrays: Sequential Search without recursion";
cout<<" 2. Arrays: Sequential Search with recursion";
cout<<" 3. Ordered Arrays: Binary Search without recursion";
cout<<" 4. ordered Arrays: Binary Search with recursion";
cout<<" 5. Linked List: Search with recursion";
cout<<" 6. Linked List: Search without recursion";
cout<<" 7. Hash Table: Search with hashing and linear probing";
cout<<" Enter 0 exit ";
out_stream<<" Choose type of search:";
out_stream<<" 1. Arrays: Sequential Search without recursion";
out_stream<<" 2. Arrays: Sequential Search with recursion";
out_stream<<" 3. Ordered Arrays: Binary Search without recursion";
out_stream<<" 4. ordered Arrays: Binary Search with recursion";
out_stream<<" 5. Linked List: Search with recursion";
out_stream<<" 6. Linked List: Search without recursion";
out_stream<<" 7. Hash Table: Search with hashing and linear probing ";
out_stream<<" Enter 0 exit ";
cin>>i;
cout <<"Picked # " << i << " ";
out_stream << "Picked # " << i << " ";
switch(i){
case 1: as.load();
out_stream << "Enter number in array to search: " << endl;
cout << "Enter number in array to search: ";
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(as.seqsearch(num)){
out_stream << num << " found!" << endl;
cout << num << " found!" << endl;
}else{
out_stream << num << " not found!" << endl;
cout << num << " not found!" << endl;
}
as.cleararray();
break;
case 2: asr.load();
out_stream << "Enter number in array to search: " << endl;
cout << "Enter number in array to search: " << endl;
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(asr.seqserachRecursion(0,num)){
out_stream << num << " found!" << endl;
cout << num << " found!" << endl;
}else{
out_stream << num << " not found!" << endl;
cout << num << " not found!" << endl;
}
asr.cleararray();
break;
case 3: bs.load();
bs.orderloaded();
out_stream << "Enter number in array to search: " << endl;
cout << "Enter number in array to search: " << endl;
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(bs.orderedbinarysearch(num)){
out_stream << num << " found! " << endl;
cout << num << " found! " << endl;
}else{
out_stream << num << " not found! " << endl;
cout << num << " not found! " << endl;
}
bs.cleararray();
break;
case 4: bsr.load();
bsr.orderloaded();
out_stream << "Enter number in array to search: " << endl;
cout << "Enter number in array to search: " << endl;
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(bsr.orderedbinarysearchRecursion(num,0,11)){
out_stream << num << " found! " << endl;
cout << num << " found! " << endl;
}else{
out_stream << num << " not found! " << endl;
cout << num << " not found! " << endl;
}
bsr.cleararray();
break;
case 5: ll.loadlinked();
out_stream << "Enter number in linked list to search: " << endl;
cout << "Enter number in linked list to search: " << endl;
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(ll.linkedsearch(num)){
out_stream << num << " found! " << endl;
cout << num << " found! " << endl;
}else{
out_stream << num << " not found! " << endl;
cout << num << " not found! " << endl;
}
ll.clearlist();
break;
case 6: llr.loadlinked();
out_stream << "Enter number in linked list to search: " << endl;
cout << "Enter number in linked list to search: " << endl;
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(llr.linkedsearchRecursion(num)){
out_stream << num << " found! " << endl;
cout << num << " found! " << endl;
}else{
out_stream << num << " not found! " << endl;
cout << num << " not found! " << endl;
}
llr.clearlist();
break;
}
case 7: hashed.hashsearch ();
out_stream << "Enter number in linked list to search: " << endl;
cout << "Enter number in list to search: " << endl;
cin >> num;
out_stream << "Number entered: " << num << endl;
cout << "Number entered: " << num << endl;
if(hashed.hashsearch (num)){
out_stream << num << " found! " << endl;
cout << num << " found! " << endl;
}else{
out_stream << num << " not found! " << endl;
cout << num << " not found! " << endl;
}
break;
}while(i!=0);
out_stream.close();
}
/*=================lab8.cpp===================*/
#include <iostream>
#include <vector>
#include <list>
#include <random>
#include <chrono>
#include "lab8.h"
using namespace std;
const int HTSIZE = 13;
search::search(){
}
bool search::seqsearch(int num){
for(unsigned int i=0; i < array.size();i++){
if(array[i] == num){
return true;
}
}
return false;
}
bool search::seqserachRecursion(unsigned int start, int num){
if(start == array.size()){ //base case
return false;
}
if(array[start] == num){
return true;
}else{
seqserachRecursion(start+1, num);
}
}
bool search::orderedbinarysearch(int num){
int max = array.size();
int min = 0;
while(max>=min){
int mid = (max+min)/2;
if(array[mid] == num){
return true;
}
else if(array[mid]< num){// upper
min = mid+1;
}else{ // lower
max = mid-1;
}
}
return false;
}
bool search::orderedbinarysearchRecursion(int num, int min, int max){
if(max < min){
return false;
}else{
int mid = (min+max)/2;
if(array[mid]> num){
orderedbinarysearchRecursion(num,min,mid-1);
}
else if(array[mid]<num){
orderedbinarysearchRecursion(num,mid+1,max);
}
else{
return true;
}
}
}
bool search::linkedsearch(int num){
while(!nodes.empty()){
if(num == nodes.front()){
return true;
}else{
nodes.pop_front();
}
}
return false;
}
bool search::linkedsearchRecursion(int num){
if(nodes.empty()){
return false;
}
else if(nodes.front() == num){
return true;
}
else{
nodes.pop_front();
linkedsearchRecursion(num);
}
}
void search::load()
{
array.push_back(41);
array.push_back(67);
array.push_back(34);
array.push_back(0);
array.push_back(69);
array.push_back(24);
array.push_back(78);
array.push_back(58);
array.push_back(62);
array.push_back(64);
}
void search::orderloaded(){ // smallest to largest
for(unsigned int i=0; i<array.size(); i++){
for(unsigned int j=0; j< array.size()-1;j++){
if(array[j]> array[j+1]){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
void search::loadlinked()
{
nodes.push_back(41);
nodes.push_back(67);
nodes.push_back(34);
nodes.push_back(0);
nodes.push_back(69);
nodes.push_back(24);
nodes.push_back(78);
nodes.push_back(58);
nodes.push_back(62);
nodes.push_back(64);
}
void search::cleararray(){
while(!array.empty()){
array.pop_back();
}
}
void search::clearlist(){
while(!nodes.empty()){
nodes.pop_front();
}
}
/*=================lab8.h====================*/
#include <iostream>
#include <vector>
#include <list>
using namespace std;
class search{
public:
search();
bool seqsearch(int num);
bool seqserachRecursion(unsigned int start, int num);
bool orderedbinarysearch(int num);
bool orderedbinarysearchRecursion(int num, int min, int max);
bool linkedsearch(int num);
bool linkedsearchRecursion(int num);
void load();
int hashsearch();
void orderloaded();
void loadlinked();
void cleararray();
void clearlist();
private:
vector<int> array;
list <int> nodes;
};
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.