// From the software distribution accompanying the textbook // "A Practical Introduction to Data Structures and Algorithm Analysis, // Third Edition (C++)" by Clifford A. Shaffer. // Source code Copyright (C) 2007-2011 by Clifford A. Shaffer. #include "book.h" int main(int argc, char** argv) { if (argc != 3) { cout << "Usage: hashsim <#_of_records> <#_of_iterations>\n"; return -1; } int recs = atoi(argv[1]); int iterations = atoi(argv[2]); srand(1); int hashtable[2*recs]; // This is the pseudo hash table, twice the # of records // Data collecting variables int maxlen = 0; // Maximum length of any chain, ever int avglen = 0; // Average for the maximum (per iteration) chain length int minslots = (2*recs); // Minimum slots used by any interation int avgslots = 0; // Average number of slots used per iteration for(int i=0; i (2*recs)) cout << "ERROR\n"; hashtable[homeslot]++; // Imagine that we are inserting here, bump the count } // Update the statistics for (j=0; j<(2*recs); j++) { if (hashtable[j] > maxlen) maxlen = hashtable[j]; // longest chain ever if (hashtable[j] > len) len = hashtable[j]; // longest chain this iteration if (hashtable[j] > 0) slots++; // Something hit this slot } if (slots < minslots) minslots = slots; avglen += len; avgslots += slots; } // Calculate the final statistics cout << "For " << iterations << " iterations on " << recs << " records\n"; cout << "The longest chain ever generated was " << maxlen << endl; cout << "The average length for the maximum chain was " << ((double)avglen)/((double)iterations) << endl; cout << "The minimum number of slots ever used was " << minslots << endl; cout << "The average number of slots used was " << ((double)avgslots)/((double)iterations) << endl; return 0; }