PROGRAM 7

PROGRAM 7 // FILENAME: PROGRAM7.CPP AUTHOR: ANTHONY F. ORTIZ // HEADER FILES. #include #include #include #include #include #include #include #include #include #include #include "ourstr.h" ifstream INFILE; ofstream OUTFILE; // DECLARATION FOR A LINKED LIST CLASS CALLED LIST. template class LIST { protected: // THE LIST IS A LINKED LIST WITH A HEADER NODE. struct NODE { ETYPE ELEMENT; NODE * NEXT; // CONSTRUCTOR FOR NODE. NODE (ETYPE E = 0, NODE * N = 0): ELEMENT (E), NEXT (N) {} }; // THE HEADER. NODE *LIST_HEAD; // THE CURRENT POSITION NODE *CURRENT_POS; // DELETE AN ENTIRE LIST. void DELETE_LIST (); // DISABLE CALL BY VALUE. LIST (LIST & VALUE); public: // CONSTRUCTOR. LIST () : LIST_HEAD (new NODE), CURRENT_POS (LIST_HEAD) {} // DESTRUCTOR. virtual ~LIST () {DELETE_LIST ();} // DUPLICATE A LIST. const LIST & operator = (LIST & VALUE); // ADVANCE THE CURRENT POSITION. const LIST & operator ++ (); // CHECK IF CURRENT POSITION IS NOT NULL. int operator ! () const; // RETRIEVE ELEMENT IN THE CURRENT POSITION. const ETYPE & operator () () const; // RETURNS TRUE IF THERE IS A EMPTY LIST. int IS_EMPTY () const {return LIST_HEAD -> NEXT == 0;} // FIND AN ELEMENT IN THE LINKED LIST. virtual int FIND (const ETYPE & X); // FIND THE PREVIOUS ELEMENT IN A LINKED LIST. USED FOR DELETION. virtual int FIND_PREVIOUS (const ETYPE & X); // DETERMINE IF AN ELEMENT IS IN THE LIST. int IN_LIST (const ETYPE & X); // SET THE CURRENT POSITION TO THE FIRST ELEMENT. void FIRST () {if (LIST_HEAD -> NEXT != 0) CURRENT_POS = LIST_HEAD -> NEXT;} // SET THE CURRENT POSITION TO THE HEADER. void HEADER () {CURRENT_POS = LIST_HEAD;} // REMOVE AN ELEMENT FROM THE LINKED LIST. int REMOVE (const ETYPE & X); // INSERT AN ELEMENT INTO THE LINKED LIST (ON TOP). virtual void INSERT (const ETYPE & X); // INSERT AN ELEMENT INTO THE LINKED LIST (ON BOTTOM). virtual void INSERT_AS_FIRST_ELEMENT (const ETYPE & X); // PRINT THE LINKED LISTS. void PRINT (); }; // IMPLEMENTATION OF A LINKED LIST CALLED LIST. // DELETE AN ENTIRE LIST. HEADER ASSUMED. template void LIST :: DELETE_LIST () { NODE * P = LIST_HEAD -> NEXT, * TEMP; while (P != 0) { TEMP = P -> NEXT; delete P; P = TEMP; } delete LIST_HEAD; } // DUPLICATE A LIST. CURRENT POSITION BECOMES FIRST ELEMENT IN BOTH LISTS. template const LIST & LIST :: operator = (LIST & VALUE) { // DON'T COPY TO YOURSELF. if (this == & VALUE) return * this; DELETE_LIST (); CURRENT_POS = LIST_HEAD = new NODE; for (VALUE.FIRST (); !VALUE; ++VALUE) { CURRENT_POS -> NEXT = new NODE (VALUE (), CURRENT_POS -> NEXT); CURRENT_POS = CURRENT_POS -> NEXT; } CURRENT_POS -> NEXT = 0; FIRST (); VALUE.FIRST (); return *this; } // ADVANCE THE CURRENT POSITION. template inline const LIST & LIST :: operator ++ () { if (CURRENT_POS != 0) CURRENT_POS = CURRENT_POS -> NEXT; return * this; } // CHECK IF CURRENT POSITION IS NOT NULL. template inline int LIST :: operator ! () const { return CURRENT_POS != 0; } // RETRIEVE ELEMENT IN THE CURRENT POSITION. RETURN VALUE IS UNDEFINED // IF CURRENT POSITION IS NULL. template inline const ETYPE & LIST :: operator () () const { if (CURRENT_POS != 0) return CURRENT_POS -> ELEMENT; else return LIST_HEAD -> ELEMENT; } // ASSUMING USE OF HEADER NODE, FIND X. IF FOUND, RETURN TRUE AND SET // THE CURRENT POSITION. template int LIST :: FIND (const ETYPE & X) { NODE * P; for (P = LIST_HEAD -> NEXT; P != 0; P = P -> NEXT) { if (P -> ELEMENT == X) { CURRENT_POS = P; return 1; } } return 0; } // ASSUMING USE OF HEADER NODE, FIND X. IF FOUND, RETURN TRUE AND SET // THE CURRENT POSITION TO BEFORE X. template int LIST :: FIND_PREVIOUS (const ETYPE & X) { NODE * P; for (P = LIST_HEAD; P -> NEXT != 0; P = P -> NEXT) if (P -> NEXT -> ELEMENT == X) { CURRENT_POS = P; return 1; } return 0; } // DETERMINE IF ELEMENT IS IN THE LIST. template int LIST :: IN_LIST (const ETYPE & X) { return FIND (X); } // REMOVE X FROM THE LIST. RETURN NONZERO IF DELETION WAS SUCCESSFUL. // HEADER NODE IS ASSUMED. template int LIST :: REMOVE (const ETYPE & X) { NODE * CELL_TO_DELETE; if (FIND_PREVIOUS (X)) { CELL_TO_DELETE = CURRENT_POS -> NEXT; CURRENT_POS -> NEXT = CELL_TO_DELETE -> NEXT; delete CELL_TO_DELETE; return 1; } return 0; } // INSERT X AFTER THE CURRENT POSITION. X BECOMES THE CURRENT ELEMENT. // HEADER IMPLEMENTATION ASSUMED. template void LIST :: INSERT (const ETYPE & X) { NODE * P = new NODE (X, CURRENT_POS -> NEXT); if (P == 0) cout << "OUT OF SPACE." << endl; else { CURRENT_POS -> NEXT = P; CURRENT_POS = CURRENT_POS -> NEXT; } } // INSERT X BEFORE THE CURRENT POSITION. HEADER IMPLEMENTATION ASSUMED. template void LIST :: INSERT_AS_FIRST_ELEMENT (const ETYPE & X) { HEADER (); INSERT (X); } template void LIST :: PRINT () { NODE * P; int COUNT = 0; for (P = LIST_HEAD -> NEXT; P != 0; P = P -> NEXT) { COUNT = COUNT + 1; OUTFILE << P -> ELEMENT << "\n"; } } // CLASS DECLARATION FOR A SORTED LINKED LIST. template class SORTED_LIST : public LIST { public: virtual void INSERT (const ETYPE & X); virtual void INSERT_AS_FIRST_ELEMENT (const ETYPE & X) {cout << "ILLEGAL OPERATION FOR SORTED LIST.";} }; // CLASS IMPLEMENTATION FOR A SORTED LINKED LIST. // SORTED INSERTION. template void SORTED_LIST :: INSERT (const ETYPE & X) { for (NODE * P = LIST_HEAD; P -> NEXT != 0; P = P -> NEXT) if (P -> NEXT -> ELEMENT > X) break; CURRENT_POS = P; LIST :: INSERT (X); } // CLASS DECLARATION FOR OPEN HASHING. static const DEFAULT_SIZE = 10; template class HASH_TABLE { private: // SIZE OF HASHING TABLE. unsigned int H_SIZE; // LINKED LIST FOR EACH HASHING CELL. SORTED_LIST * THE_LISTS; // THE LAST LIST ACCESSED. unsigned int CURRENT_LIST; // ALLOCATE MEMORY FROM THE HEAP FOR THE LINKED LISTS. void ALLOCATE_LISTS (); // DISABLE BY VALUE. HASH_TABLE (HASH_TABLE & VALUE); public: // CONSTRUCTORS. HASH_TABLE (unsigned int INITIAL_SIZE = DEFAULT_SIZE); // DESTRUCTORS. ~HASH_TABLE () {delete [] THE_LISTS;} // HASH FUNCTION. HASH (const ETYPE & KEY, const int H_SIZE); // COPY A HASH TABLE USING '='. const HASH_TABLE & operator = (const HASH_TABLE & VALUE); // RETURN A CELL IN THE HASH TABLE. const ETYPE & operator () () const {return THE_LISTS [CURRENT_LIST] ();} // INITIALIZE HASH TABLE. void INITIALIZE_TABLE (); // INSERT ELEMENT INTO THE HASH TABLE (OPEN HASHING). void INSERT (const ETYPE & KEY); // REMOVE ELEMENT FROM THE HASH TABLE (OPEN HASHING). void REMOVE (const ETYPE & KEY); // FIND AN ELEMENT IN THE HASH TABLE (OPEN HASHING). int FIND (const ETYPE & KEY); // PRINT THE HASH FILE. void PRINT (); }; // CLASS IMPLEMENTATION FOR OPENING HASHING. // ALLOCATE MEMORY FROM THE HEAP FOR LINKED LISTS. template void HASH_TABLE :: ALLOCATE_LISTS () { THE_LISTS = new SORTED_LIST [H_SIZE]; if (THE_LISTS == 0) cout << "OUT OF SPACE!!"; } // CONSTRUCTOR. template HASH_TABLE :: HASH_TABLE (unsigned int INITIAL_SIZE) { H_SIZE = INITIAL_SIZE; ALLOCATE_LISTS (); } // HASH FUNCTION. template int HASH_TABLE :: HASH (const ETYPE & KEY, const int H_SIZE) { int SUM = 0; for (int I = 0; KEY [I] != '\0' ; I++) { SUM += KEY [I]; } return SUM % H_SIZE; } // INITIAILZE THE HASH TABLE. template void HASH_TABLE :: INITIALIZE_TABLE () { delete [] THE_LISTS; ALLOCATE_LISTS (); } // COPY HASH TABLE USING '='. template const HASH_TABLE & HASH_TABLE :: operator = (const HASH_TABLE & VALUE) { if (this != &VALUE) { delete [] THE_LISTS; H_SIZE = VALUE.H_SIZE; ALLOCATE_LISTS (); for (int I = 0; I < H_SIZE; I++) THE_LISTS [I] = VALUE.THE_LISTS [I]; } return * this; } // FIND AN ELEMENT IN THE HASH TABLE. template int HASH_TABLE :: FIND (const ETYPE & KEY) { unsigned int HASH_VAL = HASH (KEY, H_SIZE); if (THE_LISTS [HASH_VAL].FIND (KEY)) { CURRENT_LIST = HASH_VAL; return 1; } return 0; } // INSERT AN ELEMENT INTO THE HASH TABLE. template inline void HASH_TABLE :: INSERT (const ELEMENT_TYPE & KEY) { unsigned int HASH_VAL = HASH (KEY, H_SIZE); if (!THE_LISTS [HASH_VAL].IN_LIST (KEY)) THE_LISTS [HASH_VAL].INSERT (KEY); } // DELETE AN ELEMENT FROM THE HASH TABLE template inline void HASH_TABLE :: REMOVE (const ELEMENT_TYPE & KEY) { THE_LISTS [HASH (KEY, H_SIZE)].REMOVE (KEY); } // PRINT THE HASH TABLE. template void HASH_TABLE :: PRINT () { for (int I = 0; I <= H_SIZE - 1; I++) { OUTFILE << "\nHASH CELL " << I << "\n\n"; THE_LISTS [I].PRINT (); } } // THIS PROGRAM WILL GET THE ENVIRONMENT PATH USING THE C++ FUNCTION // GET_PATH. THEN, IT WILL EXTRACT THE DIRECTORIES FROM THE PATH. // AFTER GETTING THE DIRECTORIES, IT WILL MAKE A SERIES OF SYSTEM CALLS // TO DOS. EACH SYSTEM CALL WILL EXECUTE THE FOLLOWING COMMAND // "C:\DIR DIRECTORY /B > DIR.OUT. IN OTHER WORDS, PUT ALL FILES IN // THIS DIRECTORY INTO A FILE CALLED DIR.DOC. THEN, THE PROGRAM WILL // EXTRACT ALL THE FILES FROM DIR.DOC AND PUT THEM IN A OPEN HASH // TABLE. THE COLLISIONS WILL BE HANDLE BY HAVING A SORTED LINKED // LIST. THE USER WILL BE PROMPTED TO SEARCH FOR A FILE AND MAY // REPEAT THE SEARCH IF HE OR SHE LIKES. AFTER THE SEARCH, THE PROGRAM // WILL PUT THE HASH TABLE IN A OUT FILE. int main() { // HOLDS THE PATH. char * PATH; // HOLDS ALL DIRECTORY IN THE PATH VARIABLE. char DIRECTORY [10][15]; // HOLDS THE SYSTEM INSTRUCTION TO DOS. char SYSTEM_INSTRUCTION [25]; // HOLDS THE FILE NAME. string FILE_NAME; // HOLDS ALL THE FILES IN A HASH TABLE. HASH_TABLE FILE_HASH; // THESE VARIABLES WILL HELP TO EXTRACT THE DIRECTORY NAMES. int FLAG = 0; int COUNT = 0; int COUNT2 = 0; // CLEAR THE SCREEN. clrscr (); // GET THE PATH. PATH = getenv("PATH"); // EXTRACT THE DIRECTORY NAMES. for (int I = 1; PATH [I] != '\0'; I++) { if ((isalpha (PATH [I]) || isdigit (PATH [I])) && PATH [I + 1] != ':') { DIRECTORY [COUNT2][COUNT] = PATH [I]; COUNT = COUNT + 1; FLAG = 1; } else if (PATH [I] == ';') { DIRECTORY [COUNT2][COUNT] = '\0'; COUNT2 = COUNT2 + 1; COUNT = 0; FLAG = 0; } } // CALL THE DOS SYSTEM AND PUT THE FILES IN A DATA FILE CALLED // DIR.DAT. for (int J = 0; J < (COUNT2 - 1); J++) { strcpy (SYSTEM_INSTRUCTION, "DIR "); strcat (SYSTEM_INSTRUCTION, DIRECTORY [J]); strcat (SYSTEM_INSTRUCTION," /B > DIR.DAT"); system ("C:"); system (SYSTEM_INSTRUCTION); // THEN OPEN DIR.DAT FILE AND PUT EACH OF THE FILES INTO THE // OPEN HASH TABLE. INFILE.open ("C:\DIR.DAT", ios :: in); while (!INFILE.eof ()) { INFILE >> FILE_NAME; FILE_HASH.INSERT (FILE_NAME); } // CLOSE DATA FILE. INFILE.close (); } // CLEAR THE SCREEN AND DO SOME FILE SEARCHES. clrscr (); do { cout << "ENTER A FILE NAME. "; cin >> FILE_NAME; cout << "\n"; // DISPLAY A MESSAGE TO THE SCREEN TELLING THE USER WHETHER // THE FILE WAS FOUND. if (FILE_HASH.FIND (FILE_NAME)) { cout << FILE_NAME << " WAS FOUND.\n\n"; } else if (FILE_NAME != "STOP") { cout << FILE_NAME << " WAS NOT FOUND.\n\n"; } } while (FILE_NAME != "STOP"); // OPEN OUT FILE, PUT THE HASH TABLE IN THE OUT FILE, AND CLOSE // THE FILE. OUTFILE.open ("DIR.OUT", ios :: out); OUTFILE << "PATH = " << PATH << "\n\n"; FILE_HASH.PRINT (); return 0; } // FILENAME: OURSTR.H, OURSTR.CPP // SEE PROGRAM 12 (COMP251 PAGE). // DATA FILE: DIR.DAT VIRSCAN.EXE VIRSCAN.MSG VSTOP.MSG VIRUSCK.PIF VIRUSCK.BAT COMMAND.PIF HWCHECK.PIF MAKECU.PIF PS1_TODO.PIF START.BAT GRP.DAT VIRUSCK.HLP VIRSIG.LST VERV.EXE VSTOP.COM VIRUSCK.EXE BACKREST.EXE BACKREST.HLP DATETIME.EXE DATETIME.HLP DISPSEL.EXE DISPSEL.HLP HWCHECK.EXE HWSPECS.EXE HWSPECS.HLP MAKECU.EXE PS1LIB.DLL PS1LOGO.EXE PS1MENU.EXE PS1SETUP.EXE PS1TOOLS.EXE REFDISK.EXE REFDISK.HLP WINRESET.EXE WINRESET.HLP YOURSOFT.EXE YOURSOFT.HLP HWCHECK.DAT // OUTFILE: PROG7.OUT ENTER A FILE NAME. GRP.DAT GRP.DAT WAS FOUND. ENTER A FILE NAME. ANTHONY.DAT ANTHONY.DAT WAS NOT FOUND. ENTER A FILE NAME. ^C BACK TO CS3240 PAGE.