dynamic linked lists

[Amy Oppor]

a partner and I are writting a code that we are stuck on with the linked list. I am sure the problem lies with how the array is declared but I am stuck and can't get any farther. Any ideas?

//************
// CODE FILENAME: ProgAssn2_Oppor-Schlumbohm2[4]-5.cpp
// DESCRIPTION: create a list of random numbers and execute
// hashing methods and collision tests on the numbers
// output results of each method
// DATE: Date to be turned in-September 28 2008 11:59pm
// DESIGNER: Christy Schlumbohm, Amy Oppor
// FUNCTIONS: void introduction()
// void initialize_Array()
// void create_List()
// bool unique_search()
// int tableSize()
// void modulo_Division_Method()
// void init_sep_chaining()
// void init_linear()
// void linear_Probe()
// void init_double()
// int double_Hashing()
// void separate_Chaining()
// void num_search_linear()
// void num_search_double()
// void num_search_sepChaining()
// void display_intro()
// void display()
//*************

include <iostream>

include <ctime>

include <cstdlib>

include <iomanip>

include <cmath>

using namespace std;

struct node
{

   int number;                  //number to be stored in the list
   struct node *next;           //pointer to the next item in the list

};

const int HIGH_NUM = 5000; //number of random numbers to generate
const int LOW = 6000; // LOW number that can be used for table

static int list[HIGH_NUM]; // array as list[]

void introduction();
void initialize_Array();
void create_List();
bool unique_search(int random, int list[]);
int tableSize(int LOW);
void modulo_Division_Method(int tblSz, int list[], node chainingArray[],
node first, int linearArray[], int doubleArray[]);
void init_sep_chaining(node first, node chainingArray[], int tblSz);
void init_linear(int linearArray[], int tblSz);
void linear_Probe(int address, int linearArray[], int tblSz, int list[],
int key);
void init_double(int doubleArray[], int tblSz);
int double_Hashing(int address, int key, int doubleArray[], int tblSz);
void separate_Chaining(node first, node chainingArray[], int address, int key);
void num_search_linear(int list[], int linearArray[], int tblSz, int key,
int address);
void num_search_double(int list[], int doubleArray[], int tblSz, int key,
int address);
void num_search_sepChaining(int list[], node chainingArray[], node first,
int tblSz, int key, int address);
void display_intro(int tblSz);
void display(int total, double avg, string res_method,int tblSz);

int main ()
{

introduction(); //FUNCTION
int tblSz;
tblSz = tableSize(LOW);
int linearArray;
linearArray = new int[tblSz]; //array for linear probing
int doubleArray;
doubleArray = new int[tblSz]; //array for doublehashing
struct node first = NULL;
struct node chainingArray;
//chainingArray = new node[tblSz]; //array for chaining

initialize_Array(); //FUNCTION

create_List(); //FUNCTION
init_linear(linearArray, tblSz); //FUNCTION
init_double(doubleArray, tblSz); //FUNCTION
init_sep_chaining(first, chainingArray, tblSz)
modulo_Division_Method(tblSz, list, chainingArray, first,
linearArray, doubleArray); // FUNCTION

system("pause");
return 0;
}

//************
// FUNCTION: introduction()
// DESCRIPTION: describes what the program does for the user
// INPUT:
// Parameters: NONE
// File: NONE
// OUTPUT:
// Return Val: NONE
// Parameters: NONE
// File:
// CALLS TO: MAIN
// IMPLEMENTED BY: Amy Oppor
//*************
void introduction()
{

 cout << "     This program will compare the three different hashing " 
               << endl;
 cout << "     collision stategies:" << endl;
 cout << "    --------------------------------------------------------";
 cout <<      "------" << endl;
 cout << "         ---------------------------------------------------" 
               << endl;
 cout << "     1.) Linear Probing " << endl;
 cout << "     2.) Double Hashing " << endl;
 cout << "     3.) Separate Chaining " << endl << endl;
 cout << "              Each method will determine" << endl;
 cout << "              --------------------------" << endl;
 cout << "             -Total number of items examined " << endl;
 cout << "             -Average number or items examined per search " 
                       << endl;
 cout << "    ---------------------------------------------------" << endl;
 cout << endl << endl;

}

//************
// FUNCTION: initialize_Array()
// DESCRIPTION: initializes all cells in array to -1
// INPUT:
// Parameters:
// File:
// OUTPUT:
// Return Val:
// Parameters:
// File:
// CALLS TO: MAIN
// IMPLEMENTED BY: Amy Oppor
//*************
void initialize_Array()
{
int num;

 for(num = 0; num < HIGH_NUM; num++)
    { //for each pass it assigns the cell to -1
       list[num] = -1;
    }

}

//************
// FUNCTION: create_List()
// DESCRIPTION: creates an array of random unique numbers
// INPUT:
// Parameters:
// File:
// OUTPUT:
// Return Val:
// Parameters:
// File:
// CALLS TO: MAIN
// IMPLEMENTED BY: Amy Oppor
//*************
void create_List()
{
int random, count;
bool duplicate;

    for(count = 0; count < HIGH_NUM; count++)
       {//for each pass creates a random number and stores it in array list[]
        random = (rand() + time(0)) % 30000;
        duplicate = unique_search(random, list);
        //if the number is not random or if the number is equal to zero
        if (duplicate == true || random == 0)  
          count--;                             //decrease the count 
        else                                   //re-run number
          list[count] = random;            //else store the number in array

       }

}

//************
// FUNCTION: unique_search()
// DESCRIPTION: confirms the number is random
// INPUT:
// Parameters: random, list[]
// File:
// OUTPUT:
// Return Val: bool dublicate
// Parameters:
// File:
// CALLS TO:
// IMPLEMENTED BY: Christy Schlumbohm
//*************
bool unique_search(int random, int list[])
{
int index;
bool duplicate;
//for each number, confirm it is unique,
for (index = 0; index < HIGH_NUM; index++)
{ // if not random
if (list[index] == random)
return true;
}
}

//************
// FUNCTION: tableSize(LOW)
// DESCRIPTION: Ask the user for the size of the table. Table cannot be
// less than 6000. If so, re-prompt.
// INPUT:
// Parameters: tblSize, LOW
// File:
// OUTPUT:
// Return Val: tblSize
// Parameters:
// File:
// CALLS TO:
// IMPLEMENTED BY: Christy Schlumbohm
//*************
int tableSize(int LOW)
{
int tblSize;

 cout << "Please enter the size for the hash table: ";
 cin >> tblSize;        //hash table size

do
{
if (tblSize < LOW) {
cout << "Table size cannot be less than 6000. Please re-enter: ";
cin >> tblSize;
} //end if

 cout << endl << endl;

}
while(tblSize < LOW); //keep asking for number larger than 6000 until
return tblSize; //number is entered as a number > 6000
}

//************
// FUNCTION: modulo_Division_Method()
// DESCRIPTION: determine storage address for data(key)
// INPUT:
// Parameters: list[] array, hash table size
// File:
// OUTPUT:
// Return Val:
// Parameters: list[] array filled with random numbers, address
// File:
// CALLS TO: Main, HASHTABLE_SIZE, create_List
// IMPLEMENTED BY: Amy Oppor
//***********
void modulo_Division_Method(int tblSz, int list[], node chainingArray[], node first, int linearArray[], int doubleArray[]) //
{
int index;
int key;
int address;
int count;
int linearaddress;
//test linear probing
init_sep_chaining(first, chainingArray[], tblSz)

for(index = 0; index < HIGH_NUM; index++)
{
key = list[index]; //determine key
address = key % tblSz; //find address based on key

         linear_Probe(address, linearArray, tblSz, list, key);
         }  //number search for linear
     num_search_linear(list, linearArray, tblSz, key, address);

//test double hashing
for(index = 0; index < HIGH_NUM; index++)
{
key = list[index]; //determine key
address = key % tblSz; //find address based on key

      double_Hashing(address, key, doubleArray, tblSz);
         }   //number search for double
      num_search_double(list, doubleArray, tblSz, key, address);

//test separate chaining
for(index = 0; index < HIGH_NUM; index++)
{
key = list[index]; //determine key
address = key % tblSz; //find address based on key
separate_Chaining(first, chainingArray, address, key);

     }
     //sepChaining search - 
     num_search_sepChaining(list, chainingArray, first, tblSz, key, address);

}

//************
// FUNCTION: init_linear()
// DESCRIPTION: array initialization
// INPUT:
// Parameters: tblSize
// File:
// OUTPUT:
// Return Val:
// Parameters: linearArray
// File:
// CALLS TO: Main,
// IMPLEMENTED BY: Amy Oppor
//*************
void init_linear(int linearArray[], int tblSz)
{
int index;
//initialize each cell to -1
for (index = 0; index < tblSz; index++)
{
linearArray[index] = -1;
}
}

//************
// FUNCTION: linear_Probe()
// DESCRIPTION: collision resolution for hashing
// INPUT:
// Parameters: list[] array, address of each set of data
// File:
// OUTPUT:
// Return Val:
// Parameters: list[] array filled with random numbers, address
// File:
// CALLS TO: Main, tblSz, create_List, modulo_Division_Method
// IMPLEMENTED BY: Amy Oppor
//*************
void linear_Probe(int address, int linearArray[], int tblSz, int list[], int key)
{

      //if address is full
  if (linearArray[address] != -1)
 {
    do //figure out new address
    {
       address = (address + 1);
           if (address > tblSz)
              {
              address = 0;
              }
    }  while(linearArray[address] != -1);//while the cell is full
    //store new address
    linearArray[address] = key;

 }
 else
 {  //otherwise store address
    linearArray[address] = key;
 }

}

//************
// FUNCTION: init_double()
// DESCRIPTION: array initialization
// INPUT:
// Parameters: tblSize
// File:
// OUTPUT:
// Return Val:
// Parameters: doubleArray
// File:
// CALLS TO: Main,
// IMPLEMENTED BY: Amy Oppor
//*************

void init_double(int doubleArray[], int tblSz)
{
int index;
//initialize each cell to -1
for (index = 0; index < tblSz; index++)
{
doubleArray[index] = -1;
}
}

//************
// FUNCTION: double_Hashing()
// DESCRIPTION: collision resolution for hashing
// INPUT:
// Parameters: address, tblSz
// File:
// OUTPUT:
// Return Val:
// Parameters: doubleArray
// File:
// CALLS TO: Main, , create_List, modulo_Division_Method
// IMPLEMENTED BY: Amy Oppor
//*************
int double_Hashing(int address, int key, int doubleArray[], int tblSz)
{
int address2;
//if arraycell is full
if(doubleArray[address] != -1)
{
do // figure out new address
{
//orignal address that collided = address1
address2 = ((key % (tblSz - 2)) + 1);
address = (address2 + address);
if (address > tblSz)
address = address % tblSz;
} while(doubleArray[address] != -1);//while the cell is full
//store number
doubleArray[address] = key;
}
else
{ //store number
doubleArray[address] = key;
}

}

//************
// FUNCTION: init_sep_chaining()
// DESCRIPTION: initialize the separate chaining array
// INPUT:
// Parameters: chainingArray[], first, tblSz
// File:
// OUTPUT:
// Return Val:
// Parameters:
// File:
// IMPLEMENTED BY: Christy Schlumbohm
//**********
void init_sep_chaining(node first, node chainingArray[], int tblSz)
{
int index; //int variable used to increment array position
chainingArray = (struct node) malloc(sizeof(struct node));

 //initialize array
 for (index = 0; index < tblSz; index++) 
 {
     chainingArray[index] = new *node;
     chainingArray[index]->number = -1;
     chainingArray[index]->next = NULL;
 }

}

//************
// FUNCTION: separate_Chaining()
// DESCRIPTION: collision resolution for hashing
// INPUT:
// Parameters: first, chainingArray, address, key
// File:
// OUTPUT:
// Return Val:
// Parameters: chainingArray
// File:
// IMPLEMENTED BY: Christy Schlumbohm
//***********
void separate_Chaining(node first, node chainingArray[], int address, int key)
{
if (chainingArray[address]->number == -1)
{
chainingArray[address]->number = key;
}
else
{
first = chainingArray[address];
chainingArray[address] = new node;
chainingArray[address]->number = key;
chainingArray[address]->next = first;
}

}

//************
// FUNCTION: num_search_linear()
// DESCRIPTION: searches for half the numbers in the array and calculates average
// INPUT:
// Parameters: list[], linearArray[], tblSz
// File:
// OUTPUT:
// Return Val:
// Parameters: avg, total, res_method
// File:
// CALLS TO: display
// IMPLEMENTED BY: Christy Schlumbohm
//*************
void num_search_linear(int list[], int linearArray[], int tblSz, int key, int address)
{
int num;
int index;
int sec_index;
int total = 0;
int num_search = 0;
int count;
double avg;
string res_method = "Linear Probing";

//for each pass
for (index = 0; index < HIGH_NUM; index = index + 2)
{
    num = list[index];   //num = the number in the index
    count = 1;
    num_search++;        //increase the number search

    address = num % tblSz;  //address computes

    if (linearArray[address] == num)
           total = total + count;   //increase count
    else
    {
        while (linearArray[address] != num)
        {
            if (address < tblSz)
            {
                 address++;    //increase count
                 count++;       //increase count
            }
            else 
            {
                 address = 0;
                 count ++;
            }

        }// end while

        total = total + count;
    }// end else

}// end for
                          //compute average
 avg = static_cast<double>(total) / static_cast<double>(num_search);
 display_intro(tblSz);          //FUNCTION
 display(total, avg, res_method, tblSz);  //FUNCTION

}

//************
// FUNCTION: num_search_double()
// DESCRIPTION: searches for half the numbers in the array and calculates average
// INPUT:
// Parameters: list[], linearArray[], tblSz
// File:
// OUTPUT:
// Return Val:
// Parameters: avg, total, res_method
// File:
// CALLS TO: display
// IMPLEMENTED BY: Christy Schlumbohm
//*************
void num_search_double(int list[], int doubleArray[], int tblSz, int key, int address)
{
int num;
int index;
int sec_index;
int total = 0;
int num_search = 0;
int count;
int address2;
double avg;
string res_method = "Double Hashing";

//for each pass
for (index = 0; index < HIGH_NUM; index = index + 2)
{
    num = list[index];     //num = number in the index
    count = 1;
    num_search++;         //increase count

    address = num % tblSz;    //compute address

    if (doubleArray[address] == num)
           total = total + count;     //increase total
    else
    {
        do 
        {
                count++;               //increase count
                key = num;

                //orignal address that collided = address1
                address2 = ((key % (tblSz - 2)) + 1);

                address = (address2 + address);
                    if (address > tblSz)
                        address = address % tblSz;
        }while (doubleArray[address] != num);  // end while

        total = total + count;
    }// end else

}// end for
                 //compute avg.
 avg = static_cast<double>(total) / static_cast<double>(num_search);
 display(total, avg, res_method, tblSz);   //FUNCTION

}

//************
// FUNCTION: num_search_sepChaining()
// DESCRIPTION: searches for half the numbers in the array and calculates average
// INPUT:
// Parameters: list[], chainingArray[], first, tblSz, address
// File:
// OUTPUT:
// Return Val:
// Parameters: avg, total, res_method
// File:
// CALLS TO: display
// IMPLEMENTED BY: Christy Schlumbohm
//**********
void num_search_sepChaining(int list[], node chainingArray[], node first, int tblSz, int key, int address)
{
int num;
int index;
int total = 0;
int num_search = 0;
int count;
double avg;
bool found = false;
string res_method = "Chained Hashing";
node current;
//for each pass
for (index = 0; index < HIGH_NUM; index = index + 2)
{
if (list[index] > 0)
{
num = list[index]; //num = num in index
count = 1;
num_search++; //increase num_search

       key = list[index];       //assign key
       address = key % tblSz;   //compute address

       current = chainingArray[address];  //node

    do {
        if (current->number == num)
        {
          total = total + count;      //increase total
          found = true;
        }//end if
        else 
        {
        if (current->next != NULL)    //next node
           current = current->next; 
           count++;                  //increase count
           found = false;
        }//end else

    }while (found == false);//end while
    }// end if

}

      //compute avg.
 avg = static_cast<double>(total) / static_cast<double>(num_search);
 display(total, avg, res_method, tblSz);   //SEND TO FUNCTION

}

//************
// FUNCTION: display()
// DESCRIPTION: displays results to screen
// INPUT:
// Parameters: total, avg, res_method
// File:
// OUTPUT:
// Return Val:
// Display: avg, total, res_method
// File:
// IMPLEMENTED BY: Christy Schlumbohm
//*************
void display_intro(int tblSz)
{
cout << fixed << showpoint << setprecision(2) << endl;
cout << endl;
//convert the lo1ad factor into a double variable
double loadFactor = static_cast<double>(HIGH_NUM)/static_cast<double>(tblSz);
//output the numbers below
cout << HIGH_NUM << " items loaded in to a " << tblSz << " element hash table" << endl;
cout << "Load Factor = " << loadFactor << endl << endl;

cout << "Results of searching for " << HIGH_NUM/2 << " items: " << endl << endl;

}

void display(int total, double avg, string res_method, int tblSz)
{ //for each number search call this functiont to output the data
cout << fixed << showpoint << setprecision(2) << endl;
cout << res_method << endl;
cout << " " << total << " items examined ";
cout << " (avg = " << avg << " items examined per search)" << endl << endl;

}

[Amy Oppor]

I am stuck (I believe) on the function 'void init_sep_chaining(node first, node chainingArray[], int tblSz)' - I can not seem to figure out how to make the array chainingArray[tblSz] - declared in main. which should be (if I set it up right) a linked list. I think I need to make the chainingArray a dynamic array first so that it can pass the data in any compiler. If you compile this code, and use hash table size 6000 in the Dev c++ I get errors.
I was able to figure out how to declare the other arrays (linearArray, and doubleArray as dynamic, but I am stuck with how to do it with the array that holds the linked list.

Any ideas?

[cpns]

The code you have posted does not compile! If that was your problem you should have said that and posted the log.

I posted a detailed list of the compiler errors and their solutions, only to have SourceForge tell me I could not post because I was not logged on (which I was, otherwise I would not have had the edit box!). Anyway, it lost all my text and I have now lost the will to live, so I am not doing that again. That's not your fault, everytime the gods at SourceForge change the way the forum works, they screw it up - usually for several days! However you will now not get the benefit of the explanation, but I can just dump the 'fixed' code.

Note I compiled it in VC++, there may still be GCC issues - post the log is so. Also the code does not run - it crashes. That's a different problem perhaps, and perhaps because the code is not complete (there were a number of declared but unreferenced variables - which I left in for you to fix or complete). The most efficient way to fix it is to use a debugger. I cannot recommend Dev-C++ for that. Use VC++ as I did. VC++ will also reformat and indent the mess that this forum makes of code, so is worth installing if only for that feature.

Here it is:

//************
// CODE FILENAME: ProgAssn2_Oppor-Schlumbohm2[4]-5.cpp
// DESCRIPTION: create a list of random numbers and execute
// hashing methods and collision tests on the numbers
// output results of each method
// DATE: Date to be turned in-September 28 2008 11:59pm
// DESIGNER: Christy Schlumbohm, Amy Oppor
// FUNCTIONS: void introduction()
// void initialize_Array()
// void create_List()
// bool unique_search()
// int tableSize()
// void modulo_Division_Method()
// void init_sep_chaining()
// void init_linear()
// void linear_Probe()
// void init_double()
// int double_Hashing()
// void separate_Chaining()
// void num_search_linear()
// void num_search_double()
// void num_search_sepChaining()
// void display_intro()
// void display()
//*************

include <iostream>

include <ctime>

include <cstdlib>

include <iomanip>

include <cmath>

include <string>

using namespace std;

struct node
{

int number; //number to be stored in the list 
struct node *next; //pointer to the next item in the list

};

const int HIGH_NUM = 5000; //number of random numbers to generate
const int LOW = 6000; // LOW number that can be used for table

static int list[HIGH_NUM]; // array as list[]

void introduction();
void initialize_Array();
void create_List();
bool unique_search(int random, int list[]);
int tableSize(int LOW);
void modulo_Division_Method(int tblSz, int list[], node chainingArray[],
node first, int linearArray[], int doubleArray[]);
void init_sep_chaining(node first, node chainingArray[], int tblSz);
void init_linear(int linearArray[], int tblSz);
void linear_Probe(int address, int linearArray[], int tblSz, int list[],
int key);
void init_double(int doubleArray[], int tblSz);
int double_Hashing(int address, int key, int doubleArray[], int tblSz);
void separate_Chaining(node first, node chainingArray[], int address, int key);
void num_search_linear(int list[], int linearArray[], int tblSz, int key,
int address);
void num_search_double(int list[], int doubleArray[], int tblSz, int key,
int address);
void num_search_sepChaining(int list[], node chainingArray[], node first,
int tblSz, int key, int address);
void display_intro(int tblSz);
void display(int total, double avg, string res_method,int tblSz);

int main ()
{

introduction(); //FUNCTION  
int tblSz; 
tblSz = tableSize(LOW); 
int *linearArray; 
linearArray = new int[tblSz]; //array for linear probing 
int *doubleArray; 
doubleArray = new int[tblSz]; //array for doublehashing 
struct node *first = NULL; 
struct node* chainingArray; 
//chainingArray = new node[tblSz]; //array for chaining

initialize_Array(); //FUNCTION

create_List(); //FUNCTION 
init_linear(linearArray, tblSz); //FUNCTION 
init_double(doubleArray, tblSz); //FUNCTION 
init_sep_chaining(first, &chainingArray, tblSz) ; 
    modulo_Division_Method(tblSz, list, &chainingArray, first,  
    linearArray, doubleArray); // FUNCTION

system("pause"); 
return 0;

}

//************
// FUNCTION: introduction()
// DESCRIPTION: describes what the program does for the user
// INPUT:
// Parameters: NONE
// File: NONE
// OUTPUT:
// Return Val: NONE
// Parameters: NONE
// File:
// CALLS TO: MAIN
// IMPLEMENTED BY: Amy Oppor
//*************
void introduction()
{

cout << " This program will compare the three different hashing "  
    << endl; 
cout << " collision stategies:" << endl; 
cout << " --------------------------------------------------------"; 
cout << "------" << endl; 
cout << " ---------------------------------------------------"  
    << endl; 
cout << " 1.) Linear Probing " << endl; 
cout << " 2.) Double Hashing " << endl; 
cout << " 3.) Separate Chaining " << endl << endl; 
cout << " Each method will determine" << endl; 
cout << " --------------------------" << endl; 
cout << " -Total number of items examined " << endl; 
cout << " -Average number or items examined per search "  
    << endl; 
cout << " ---------------------------------------------------" << endl; 
cout << endl << endl;

}

//************
// FUNCTION: initialize_Array()
// DESCRIPTION: initializes all cells in array to -1
// INPUT:
// Parameters:
// File:
// OUTPUT:
// Return Val:
// Parameters:
// File:
// CALLS TO: MAIN
// IMPLEMENTED BY: Amy Oppor
//*************
void initialize_Array()
{
int num;

for(num = 0; num < HIGH_NUM; num++) 
{ //for each pass it assigns the cell to -1 
    list[num] = -1; 
}

}

//************
// FUNCTION: create_List()
// DESCRIPTION: creates an array of random unique numbers
// INPUT:
// Parameters:
// File:
// OUTPUT:
// Return Val:
// Parameters:
// File:
// CALLS TO: MAIN
// IMPLEMENTED BY: Amy Oppor
//*************
void create_List()
{
int random, count;
bool duplicate;

for(count = 0; count < HIGH_NUM; count++) 
{//for each pass creates a random number and stores it in array list[] 
    random = (rand() + time(0)) % 30000; 
    duplicate = unique_search(random, list); 
    //if the number is not random or if the number is equal to zero 
    if (duplicate == true || random == 0)  
        count--; //decrease the count  
    else //re-run number 
        list[count] = random; //else store the number in array

}

}

//************
// FUNCTION: unique_search()
// DESCRIPTION: confirms the number is random
// INPUT:
// Parameters: random, list[]
// File:
// OUTPUT:
// Return Val: bool dublicate
// Parameters:
// File:
// CALLS TO:
// IMPLEMENTED BY: Christy Schlumbohm
//*************
bool unique_search(int random, int list[])
{
int index;
bool duplicate;
//for each number, confirm it is unique,
for (index = 0; index < HIGH_NUM; index++)
{ // if not random
if (list[index] == random)
return true;
}
return false ;
}

//************
// FUNCTION: tableSize(LOW)
// DESCRIPTION: Ask the user for the size of the table. Table cannot be
// less than 6000. If so, re-prompt.
// INPUT:
// Parameters: tblSize, LOW
// File:
// OUTPUT:
// Return Val: tblSize
// Parameters:
// File:
// CALLS TO:
// IMPLEMENTED BY: Christy Schlumbohm
//*************
int tableSize(int LOW)
{
int tblSize;

cout << "Please enter the size for the hash table: "; 
cin >> tblSize; //hash table size 
do 
{  
    if (tblSize < LOW) { 
        cout << "Table size cannot be less than 6000. Please re-enter: "; 
        cin >> tblSize; 
    } //end if

    cout << endl << endl;  
} 
while(tblSize < LOW); //keep asking for number larger than 6000 until  
return tblSize; //number is entered as a number > 6000

}

//************
// FUNCTION: modulo_Division_Method()
// DESCRIPTION: determine storage address for data(key)
// INPUT:
// Parameters: list[] array, hash table size
// File:
// OUTPUT:
// Return Val:
// Parameters: list[] array filled with random numbers, address
// File:
// CALLS TO: Main, HASHTABLE_SIZE, create_List
// IMPLEMENTED BY: Amy Oppor
//***********
void modulo_Division_Method(int tblSz, int list[], node chainingArray[], node first, int linearArray[], int doubleArray[]) //
{
int index;
int key;
int address;
int count;
int linearaddress;
//test linear probing
init_sep_chaining(first, chainingArray, tblSz) ;

    for(index = 0; index < HIGH_NUM; index++) 
    {  
        key = list[index]; //determine key 
        address = key % tblSz; //find address based on key

        linear_Probe(address, linearArray, tblSz, list, key); 
    } //number search for linear 
    num_search_linear(list, linearArray, tblSz, key, address); 
    //test double hashing 
    for(index = 0; index < HIGH_NUM; index++) 
    {  
        key = list[index]; //determine key 
        address = key % tblSz; //find address based on key

        double_Hashing(address, key, doubleArray, tblSz); 
    } //number search for double 
    num_search_double(list, doubleArray, tblSz, key, address);  
    //test separate chaining  
    for(index = 0; index < HIGH_NUM; index++) 
    {  
        key = list[index]; //determine key 
        address = key % tblSz; //find address based on key 
        separate_Chaining(first, chainingArray, address, key);

    } 
    //sepChaining search -  
    num_search_sepChaining(list, chainingArray, first, tblSz, key, address);

}

//************
// FUNCTION: init_linear()
// DESCRIPTION: array initialization
// INPUT:
// Parameters: tblSize
// File:
// OUTPUT:
// Return Val:
// Parameters: linearArray
// File:
// CALLS TO: Main,
// IMPLEMENTED BY: Amy Oppor
//*************
void init_linear(int linearArray[], int tblSz)
{
int index;
//initialize each cell to -1
for (index = 0; index < tblSz; index++)
{
linearArray[index] = -1;
}
}

//************
// FUNCTION: linear_Probe()
// DESCRIPTION: collision resolution for hashing
// INPUT:
// Parameters: list[] array, address of each set of data
// File:
// OUTPUT:
// Return Val:
// Parameters: list[] array filled with random numbers, address
// File:
// CALLS TO: Main, tblSz, create_List, modulo_Division_Method
// IMPLEMENTED BY: Amy Oppor
//*************
void linear_Probe(int address, int linearArray[], int tblSz, int list[], int key)
{

//if address is full 
if (linearArray[address] != -1) 
{ 
    do //figure out new address 
    { 
        address = (address + 1); 
        if (address > tblSz) 
        { 
            address = 0; 
        } 
    } while(linearArray[address] != -1);//while the cell is full 
    //store new address 
    linearArray[address] = key;

} 
else 
{ //otherwise store address 
    linearArray[address] = key; 
}

}

//************
// FUNCTION: init_double()
// DESCRIPTION: array initialization
// INPUT:
// Parameters: tblSize
// File:
// OUTPUT:
// Return Val:
// Parameters: doubleArray
// File:
// CALLS TO: Main,
// IMPLEMENTED BY: Amy Oppor
//*************

void init_double(int doubleArray[], int tblSz)
{
int index;
//initialize each cell to -1
for (index = 0; index < tblSz; index++)
{
doubleArray[index] = -1;
}
}

//************
// FUNCTION: double_Hashing()
// DESCRIPTION: collision resolution for hashing
// INPUT:
// Parameters: address, tblSz
// File:
// OUTPUT:
// Return Val:
// Parameters: doubleArray
// File:
// CALLS TO: Main, , create_List, modulo_Division_Method
// IMPLEMENTED BY: Amy Oppor
//*************
int double_Hashing(int address, int key, int doubleArray[], int tblSz)
{
int address2;
//if arraycell is full
if(doubleArray[address] != -1)
{
do // figure out new address
{
//orignal address that collided = address1
address2 = ((key % (tblSz - 2)) + 1);
address = (address2 + address);
if (address > tblSz)
address = address % tblSz;
} while(doubleArray[address] != -1);//while the cell is full
//store number
doubleArray[address] = key;
}
else
{ //store number
doubleArray[address] = key;
}
return address2;
}

//************
// FUNCTION: init_sep_chaining()
// DESCRIPTION: initialize the separate chaining array
// INPUT:
// Parameters: chainingArray[], first, tblSz
// File:
// OUTPUT:
// Return Val:
// Parameters:
// File:
// IMPLEMENTED BY: Christy Schlumbohm
//*********
void init_sep_chaining(node first, node chainingArray[], int tblSz)
{
int index; //int variable used to increment array position
chainingArray = (struct node) malloc(sizeof(struct node));

//initialize array 
for (index = 0; index < tblSz; index++)  
{ 
    chainingArray[index] = new node; 
    chainingArray[index]->number = -1; 
    chainingArray[index]->next = NULL; 
}

}

//************
// FUNCTION: separate_Chaining()
// DESCRIPTION: collision resolution for hashing
// INPUT:
// Parameters: first, chainingArray, address, key
// File:
// OUTPUT:
// Return Val:
// Parameters: chainingArray
// File:
// IMPLEMENTED BY: Christy Schlumbohm
//***********
void separate_Chaining(node first, node chainingArray[], int address, int key)
{
if (chainingArray[address]->number == -1)
{
chainingArray[address]->number = key;
}
else
{
first = chainingArray[address];
chainingArray[address] = new node;
chainingArray[address]->number = key;
chainingArray[address]->next = first;
}

}

//************
// FUNCTION: num_search_linear()
// DESCRIPTION: searches for half the numbers in the array and calculates average
// INPUT:
// Parameters: list[], linearArray[], tblSz
// File:
// OUTPUT:
// Return Val:
// Parameters: avg, total, res_method
// File:
// CALLS TO: display
// IMPLEMENTED BY: Christy Schlumbohm
//*************
void num_search_linear(int list[], int linearArray[], int tblSz, int key, int address)
{
int num;
int index;
int sec_index;
int total = 0;
int num_search = 0;
int count;
double avg;
string res_method = "Linear Probing";

//for each pass 
for (index = 0; index < HIGH_NUM; index = index + 2) 
{ 
    num = list[index]; //num = the number in the index 
    count = 1; 
    num_search++; //increase the number search

    address = num % tblSz; //address computes

    if (linearArray[address] == num) 
        total = total + count; //increase count 
    else 
    { 
        while (linearArray[address] != num) 
        { 
            if (address < tblSz) 
            { 
                address++; //increase count 
                count++; //increase count 
            } 
            else  
            { 
                address = 0; 
                count ++; 
            }

        }// end while

        total = total + count; 
    }// end else

}// end for 
//compute average 
avg = static_cast<double>(total) / static_cast<double>(num_search); 
display_intro(tblSz); //FUNCTION 
display(total, avg, res_method, tblSz); //FUNCTION

}

//************
// FUNCTION: num_search_double()
// DESCRIPTION: searches for half the numbers in the array and calculates average
// INPUT:
// Parameters: list[], linearArray[], tblSz
// File:
// OUTPUT:
// Return Val:
// Parameters: avg, total, res_method
// File:
// CALLS TO: display
// IMPLEMENTED BY: Christy Schlumbohm
//*************
void num_search_double(int list[], int doubleArray[], int tblSz, int key, int address)
{
int num;
int index;
int sec_index;
int total = 0;
int num_search = 0;
int count;
int address2;
double avg;
string res_method = "Double Hashing";

//for each pass 
for (index = 0; index < HIGH_NUM; index = index + 2) 
{ 
    num = list[index]; //num = number in the index 
    count = 1; 
    num_search++; //increase count

    address = num % tblSz; //compute address

    if (doubleArray[address] == num) 
        total = total + count; //increase total 
    else 
    { 
        do  
        { 
            count++; //increase count 
            key = num;

            //orignal address that collided = address1 
            address2 = ((key % (tblSz - 2)) + 1);

            address = (address2 + address); 
            if (address > tblSz) 
                address = address % tblSz; 
        }while (doubleArray[address] != num); // end while

        total = total + count; 
    }// end else

}// end for 
//compute avg. 
avg = static_cast<double>(total) / static_cast<double>(num_search); 
display(total, avg, res_method, tblSz); //FUNCTION

}

//************
// FUNCTION: num_search_sepChaining()
// DESCRIPTION: searches for half the numbers in the array and calculates average
// INPUT:
// Parameters: list[], chainingArray[], first, tblSz, address
// File:
// OUTPUT:
// Return Val:
// Parameters: avg, total, res_method
// File:
// CALLS TO: display
// IMPLEMENTED BY: Christy Schlumbohm
//**********
void num_search_sepChaining(int list[], node chainingArray[], node first, int tblSz, int key, int address)
{
int num;
int index;
int total = 0;
int num_search = 0;
int count;
double avg;
bool found = false;
string res_method = "Chained Hashing";
node current;
//for each pass
for (index = 0; index < HIGH_NUM; index = index + 2)
{
if (list[index] > 0)
{
num = list[index]; //num = num in index
count = 1;
num_search++; //increase num_search

        key = list[index]; //assign key 
        address = key % tblSz; //compute address

        current = chainingArray[address]; //node

        do { 
            if (current->number == num) 
            { 
                total = total + count; //increase total 
                found = true; 
            }//end if 
            else  
            { 
                if (current->next != NULL) //next node 
                    current = current->next;  
                count++; //increase count 
                found = false; 
            }//end else

        }while (found == false);//end while 
    }// end if

}

//compute avg. 
avg = static_cast<double>(total) / static_cast<double>(num_search); 
display(total, avg, res_method, tblSz); //SEND TO FUNCTION

}

//************
// FUNCTION: display()
// DESCRIPTION: displays results to screen
// INPUT:
// Parameters: total, avg, res_method
// File:
// OUTPUT:
// Return Val:
// Display: avg, total, res_method
// File:
// IMPLEMENTED BY: Christy Schlumbohm
//*************
void display_intro(int tblSz)
{
cout << fixed << showpoint << setprecision(2) << endl;
cout << endl;
//convert the lo1ad factor into a double variable
double loadFactor = static_cast<double>(HIGH_NUM)/static_cast<double>(tblSz);
//output the numbers below
cout << HIGH_NUM << " items loaded in to a " << tblSz << " element hash table" << endl;
cout << "Load Factor = " << loadFactor << endl << endl;

cout << "Results of searching for " << HIGH_NUM/2 << " items: " << endl << endl;

}

void display(int total, double avg, string res_method, int tblSz)
{ //for each number search call this functiont to output the data
cout << fixed << showpoint << setprecision(2) << endl;
cout << res_method << endl;
cout << " " << total << " items examined ";
cout << " (avg = " << avg << " items examined per search)" << endl << endl;

}

[cpns]

BTW, you know that the C++ STL includes a <list> container don't you!?

Clifford

[cpns]

That's a lot of code to just dump and say "I'm stuck". What are yoy stuck on?

This code appears to be more that just a linked list, and I am not really sure where list[] comes in - that is an array not a linked list.

What is your problem?

[Amy Oppor]

I am going to try the VC++, thanks