PROGRAM 6

PROGRAM 6 // FILENAME: PROGRAM6.CPP AUTHOR: ANTHONY F. ORTIZ // HEADER FILES. #include #include #include #include #include #include // OUTFILE ofstream OUTFILE; // DECLARATION OF HASH TABLE WITH QUADRATIC OR LINEAR PROBING. // DEFAULT SIZE OF HASH TABLE. SHOULD BE TWICE AS LARGE AS THE NUMBER // OF PLANNED INSERTIONS. ALSO, IT SHOULD BE PRIME. (THIS WILL HAPPEN // LATER ON. const int DEFAULT_SIZE = 200; template class HASH_TABLE { public: // KIND OF ENTRY. enum KIND_OF_ENTRY {LEGITIMATE, EMPTY, DELETED}; protected: // HASH ENTRY. struct HASH_ENTRY { ELEMENT_TYPE ELEMENT; KIND_OF_ENTRY INFO; HASH_ENTRY (ELEMENT_TYPE E = -1, KIND_OF_ENTRY I = EMPTY) : ELEMENT (E), INFO (I) {} }; // THE SIZE OF HASH TABLE. SHOULD BE TWICE AS LARGE AND // PRIME. unsigned int H_SIZE; // THE CELLS OF THE HASH TABLE. HASH_ENTRY * THE_CELLS; // LAST CELL ACCESSED. unsigned int CURRENT_CELL; // ALLOCATE CELLS FROM THE HEAP. void ALLOCATE_CELLS (); // DISABLED. HASH_TABLE (HASH_TABLE & VALUE); // NUMBER OF COLLISIONS. int COLLISIONS; public: // CONSTRUCTORS. HASH_TABLE (unsigned int INITIAL_SIZE = DEFAULT_SIZE); // DESTRUCTOR. virtual ~HASH_TABLE () {delete [] THE_CELLS;} // OPERATORS. // COPY A HASH TABLE USING THE '=' OPERATOR. const HASH_TABLE & operator = (const HASH_TABLE & VALUE); // GET AN INDIVIDUAL HASH TABLE CELL. ELEMENT_TYPE operator () () const {return THE_CELLS [CURRENT_CELL].ELEMENT;} // MEMBER FUNCTIONS. virtual void INITIALIZE_TABLE (); // INSERT INTO HASH TABLE USING EITHER QUADRATIC OR // LINEAR PROBING. virtual void INSERT (const ELEMENT_TYPE & KEY); // REMOVE FROM THE HASH TABLE USING EITHER QUADRATIC OR // LINEAR PROBING. void REMOVE (const ELEMENT_TYPE & KEY); // FIND A OPEN HASH CELL USING QUADRATIC PROBING. int FIND (const ELEMENT_TYPE & KEY); // FIND A OPEN HASH CELL USING LINEAR PROBING. int FIND2 (const ELEMENT_TYPE & KEY); // HASH FUNCTION. int HASH (const int KEY, const int H_SIZE); // PRINT THE HASH TABLE. void PRINT_TABLE (); // PRINT THE NUMBER OF COLLISIONS. void PRINT_COLLISIONS (); }; // ALLOCATE CELLS FROM THE HEAP. template void HASH_TABLE :: ALLOCATE_CELLS () { THE_CELLS = new HASH_ENTRY [H_SIZE]; if (THE_CELLS == 0) cout << "OUT OF SPACE!!"; } // INITIALIZE COLLISIONS AND HASH SIZE. template HASH_TABLE :: HASH_TABLE (unsigned int INITIAL_SIZE) { // FLAG TO TELL WHETHER NUMBER IS PRIME. int FLAG; COLLISIONS = 0; // FIND A PRIME NUMBER GREATER THAN TWICE THE NUMBER OF INSERTIONS. do { FLAG = 1; for (int I = 2; I < INITIAL_SIZE; I++) { if (INITIAL_SIZE % I == 0) { FLAG = 0; break; } } if (FLAG == 0) { INITIAL_SIZE++; } } while (FLAG == 0); H_SIZE = INITIAL_SIZE; ALLOCATE_CELLS (); } // INITIALIZE HASH TABLE. template void HASH_TABLE :: INITIALIZE_TABLE () { delete [] THE_CELLS; ALLOCATE_CELLS (); } // COPY HASH TABLE USING '=' OPERATOR. template const HASH_TABLE & HASH_TABLE :: operator = (const HASH_TABLE & VALUE) { if (this != &VALUE) { delete [] THE_CELLS; H_SIZE = VALUE.H_SIZE; ALLOCATE_CELLS (); for (int I = 0; I < H_SIZE; I++) THE_CELLS [I] = VALUE.THE_CELLS [I]; } return *this; } // FIND OPEN HASH TABLE CELL USING QUADRATIC PROBING. template int HASH_TABLE :: FIND (const ELEMENT_TYPE & KEY) { unsigned int I = 0; CURRENT_CELL = HASH (KEY, H_SIZE); while (THE_CELLS [CURRENT_CELL].INFO != EMPTY && THE_CELLS [CURRENT_CELL].ELEMENT != KEY) { COLLISIONS++; CURRENT_CELL += 2 * (++I) - 1; if (CURRENT_CELL >= H_SIZE) CURRENT_CELL -= H_SIZE; } return THE_CELLS [CURRENT_CELL].INFO == LEGITIMATE && THE_CELLS [CURRENT_CELL].ELEMENT == KEY; } // FIND OPEN HASH TABLE CELL USING LINEAR PROBING. template int HASH_TABLE :: FIND2 (const ELEMENT_TYPE & KEY) { unsigned int I = 0; CURRENT_CELL = HASH (KEY, H_SIZE); while (THE_CELLS [CURRENT_CELL].INFO != EMPTY && THE_CELLS [CURRENT_CELL].ELEMENT != KEY) { COLLISIONS++; CURRENT_CELL += ++I; if (CURRENT_CELL >= H_SIZE) CURRENT_CELL -= H_SIZE; } return THE_CELLS [CURRENT_CELL].INFO == LEGITIMATE && THE_CELLS [CURRENT_CELL].ELEMENT == KEY; } // INSERT INTO THE HASH TABLE USING EITHER QUADRARIC OR LINEAR PROBING. template inline void HASH_TABLE :: INSERT (const ELEMENT_TYPE & KEY) { if (FIND (KEY) == 0) THE_CELLS [CURRENT_CELL] = HASH_ENTRY (KEY, LEGITIMATE); } // REMOVE FROM THE HASH TABLE USING EITHER QUADRATIC OR LINEAR PROBING. template inline void HASH_TABLE :: REMOVE (const ELEMENT_TYPE & KEY) { if (FIND (KEY)) THE_CELLS [CURRENT_CELL] = HASH_ENTRY (-1, DELETED); else cout << "ITEMS NOT FOUND"; } // PRINT THE HASH TABLE. template void HASH_TABLE :: PRINT_TABLE () { for (int I = 0; I < H_SIZE; I++) { OUTFILE << setw (8) << THE_CELLS [I].ELEMENT; if ((I + 1) % 10 == 0) { OUTFILE << "\n"; } } } // PRINT THE NUMBER OF COLLISIONS IN THE HASH TABLE. template void HASH_TABLE :: PRINT_COLLISIONS () { OUTFILE << "\nTHERE WERE " << COLLISIONS << " COLLISIONS.\n"; } // HASH FUNCTION. template int HASH_TABLE :: HASH (const int KEY, const int H_SIZE) { return KEY % H_SIZE; } // INSERT 100 INTEGERS INTO A HASH TABLE AND DELETE 20 OF THEM FROM THE // HASH TABLE USING EITHER (QUADRTIC OR LINEAR PROBING). ALSO, PRINT THE // HASH TABLE AND THE NUMBER OF COLLISIONS. int main () { // OPEN OUT FILE. OUTFILE.open ("HASH.OUT", ios :: out); // CLEAR SCREEN. clrscr (); // MAKE EACH EXECUTION DIFFERENT. randomize (); // DECLARE VARIABLE FOR HASH TABLE. HASH_TABLE A_INT_TABLE; // HOLDS THE CURRENT RANDOM NUMBER. int RANDOM_NUMBER; // HOLDS THE CURRENT RANDOM NUMBER. NEEDED FOR REMOVAL. int TEMP; // HOLDS THE 100 RANDOM INTEGERS. // THIS WILL BE USED FOR DELETION. int RANDOM_ARRAY [100]; // INSERT 100 RANDOM INTEGERS FROM 0 TO 9999 INTO THE HASH TABLE. for (int I = 0; I <= 99; I++) { // GET RANDOM NUMBER. RANDOM_NUMBER = rand () % 10000; // INSERT IT INTO THE HASH TABLE. A_INT_TABLE.INSERT (RANDOM_NUMBER); // ALSO, INSERT IT INTO AN ARRAY. RANDOM_ARRAY [I] = RANDOM_NUMBER; } // PRINT A HEADING AND THEN THE HASH TABLE. OUTFILE << "AFTER 100 INSERTIONS:\n"; A_INT_TABLE.PRINT_TABLE (); A_INT_TABLE.PRINT_COLLISIONS (); // REMOVE 20 ELEMENTS FROM THE HASH TABLE. for (int J = 0; J <= 19; J++) { // LOOP IF THE RANDOM NUMBER IS NOT IN THE ARRAY. // THIS MIGHT HAPPEN IF IT HAS BEEN REMOVED FROM // TABLE AND THE ARRAY. do { // RANDOM NUMBER FROM 0 TO 99. // INDEX OF THE ARRAY. RANDOM_NUMBER = (rand () % 100); } while (RANDOM_ARRAY [RANDOM_NUMBER] == 0); // HOLD THE RANDOM NUMBER. TEMP = RANDOM_ARRAY [RANDOM_NUMBER]; // PUT 0 IN THE ARRAY OF THE APPROPRIATE INDEX. RANDOM_ARRAY [RANDOM_NUMBER] = 0; // PUT THE RANDOM NUMBER IN THE TEMP VARIABLE INTO // THE RANDOM NUMBER VARIABLE. RANDOM_NUMBER = TEMP; // REMOVE THE RANDOM NUMBER. A_INT_TABLE.REMOVE (RANDOM_NUMBER); } OUTFILE << "\nAFTER 20 DELETIONS:\n"; A_INT_TABLE.PRINT_TABLE (); // CLOSE OUTFILE. OUTFILE.close (); return 0; } // OUTFILE: HASH.OUT AFTER 100 INSERTIONS: 2532 -1 9075 -1 1903 -1 1905 9924 2117 9503 2960 -1 -1 8871 -1 5501 4868 -1 -1 441 -1 5929 -1 -1 -1 -1 -1 4880 -1 -1 -1 -1 7839 6152 1722 1300 -1 4890 -1 -1 -1 -1 5317 6795 -1 -1 -1 -1 -1 -1 -1 8491 9547 -1 -1 -1 -1 -1 9764 481 -1 6391 484 -1 5339 694 5341 -1 1967 -1 7033 -1 1549 7660 3239 1973 -1 6618 285 -1 1135 8309 8733 1138 -1 -1 272 -1 -1 -1 8108 9797 725 4945 9589 3259 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1584 -1 2219 7494 -1 7497 4122 -1 -1 -1 2860 -1 963 -1 6451 7084 -1 -1 -1 -1 2237 7724 4770 -1 4140 2031 -1 -1 2245 4145 6678 -1 983 3726 7948 -1 -1 5204 -1 -1 6883 -1 360 -1 -1 -1 -1 -1 5430 5642 9019 -1 -1 582 -1 8813 -1 3118 7339 588 -1 3755 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 180 -1 -1 6724 -1 -1 8415 -1 5885 4620 -1 -1 4197 4412 5047 -1 -1 830 8638 8216 -1 1252 3996 4001 -1 -1 619 -1 2107 6312 -1 THERE WERE 49 COLLISIONS. AFTER 20 DELETIONS: 2532 -1 9075 -1 1903 -1 1905 -1 2117 9503 2960 -1 -1 8871 -1 5501 -1 -1 -1 441 -1 5929 -1 -1 -1 -1 -1 4880 -1 -1 -1 -1 7839 6152 1722 1300 -1 4890 -1 -1 -1 -1 5317 6795 -1 -1 -1 -1 -1 -1 -1 8491 9547 -1 -1 -1 -1 -1 9764 481 -1 -1 484 -1 5339 694 5341 -1 -1 -1 7033 -1 1549 7660 -1 -1 -1 6618 285 -1 1135 8309 -1 1138 -1 -1 272 -1 -1 -1 8108 -1 725 4945 -1 3259 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1584 -1 2219 -1 -1 7497 -1 -1 -1 -1 2860 -1 -1 -1 6451 -1 -1 -1 -1 -1 2237 -1 4770 -1 -1 2031 -1 -1 2245 4145 6678 -1 983 -1 7948 -1 -1 5204 -1 -1 6883 -1 360 -1 -1 -1 -1 -1 5430 -1 -1 -1 -1 582 -1 8813 -1 3118 7339 588 -1 3755 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 180 -1 -1 6724 -1 -1 8415 -1 5885 4620 -1 -1 4197 4412 5047 -1 -1 830 8638 8216 -1 1252 3996 4001 -1 -1 619 -1 -1 -1 -1 BACK TO CS3240 PAGE.