﻿ Sample Code

### An Implemenation of a Hash Table Using Linear Probing to Resolve Collisions.

```//-----------------------------------------------
// Demonstrate a hash table with linear probing.
//
// D. Searls
// Asbury University
// Jan 2012
//-----------------------------------------------

#include <iostream>
#include <iomanip>
#include <fstream>
using namespace std;

int const MAXSIZE = 211;  // Try 101, 211, and 997

struct shoeType
{
int stockNum;
string style;
string color;
int size;
string width;

void display()
{
cout << left << setw(10) << stockNum;
cout << setw(10) << style;
cout << setw(10) << color;
cout << setw(7) << size;
cout << setw(10) << width;
cout << endl;
}
};

//---------------------------------------------------------
// linearSearch
//
// Return the index at which the item with the specified
// stock number was found. If the item is not in the list,
// then return -1.
//
// In parameters: item, list, n
//---------------------------------------------------------
int linearSearch(int stockNum, const shoeType list[], int n)
{
int pos = n-1;
while (pos >= 0 && stockNum != list[pos].stockNum)
{
pos--;
}
return pos;
}

//---------------------------------------------------------
// hashInsert
//
// Insert the specified item into the hash table using
// linear probing to resolve collisions.
//
// Precondition: the table is not full.
//
// In Parameters: item, list
//---------------------------------------------------------
void hashInsert(shoeType item, shoeType list[])
{
int pos = item.stockNum % MAXSIZE;
while (list[pos].stockNum != 0)
{
pos++;
if (pos == MAXSIZE)
{
pos = 0;
}
}
list[pos] = item;
}

//---------------------------------------------------------
// hashSearch
//
// Return the index at which the item with the specified
// stock number was found. If the item is not in the list,
// then return -1.
//
// Precondition: the list is not full.
//
// In parameters: stockNum, list
//---------------------------------------------------------
int hashSearch(int stockNum, const shoeType list[])
{
int pos = stockNum % MAXSIZE;
while (list[pos].stockNum != stockNum && list[pos].stockNum != 0)
{
pos++;
if (pos == MAXSIZE)
{
pos = 0;
}
}
if (list[pos].stockNum == 0)
{
pos = -1;
}
return pos;
}

//*********************************************************
//*              M A I N   D R I V E R
//*********************************************************

int main()
{
ifstream infile;
shoeType shoe[MAXSIZE];
shoeType myShoe;
int pos;   // position of item in list
int count; // number of items found
int n;     // number of items in list

// Read data into ordinary array and search for all possible
// stock numbers.

infile.open("ShoeData.txt");
n = 0;
infile >> myShoe.stockNum >> myShoe.style >> myShoe.color >> myShoe.size >> myShoe.width;
while (!infile.fail())
{
shoe[n] = myShoe;
n++;
infile >> myShoe.stockNum >> myShoe.style >> myShoe.color >> myShoe.size >> myShoe.width;
}
infile.close();
cout << n << " items in list" << endl << endl;

count = 0;
for(int stockNum = 1000000; stockNum < 10000000; stockNum++)
{
pos = linearSearch(stockNum, shoe, n);
if (pos >= 0)
{
shoe[pos].display();
count++;
}
}
cout << count << " items were found" << endl << endl;

//****************************************************************
// Now, do it all over again using a hash table to store the data.
//****************************************************************

// Set up the table with invalid stock numbers.

for (int i = 0; i < MAXSIZE; i++)
{
shoe[i].stockNum = 0;
}

// Read the data into the file.

infile.open("ShoeData.txt");
n = 0;
infile >> myShoe.stockNum >> myShoe.style >> myShoe.color >> myShoe.size >> myShoe.width;
while (!infile.fail())
{
hashInsert(myShoe, shoe);
n++;
infile >> myShoe.stockNum >> myShoe.style >> myShoe.color >> myShoe.size >> myShoe.width;
}
infile.close();
cout << n << " items in list" << endl << endl;

// Perform the searches

count = 0;
for(int stockNum = 1000000; stockNum < 10000000; stockNum++)
{
pos = hashSearch(stockNum, shoe);
if (pos >= 0)
{
shoe[pos].display();
count++;
}
}
cout << count << " items were found " << endl << endl;

return 0;
}```