Lecture 16 Examples
 |
| Program | Demonstrates |
|---|---|
| date.h | This header contains the definition of the class date that is used in many different examples. |
| bst.cpp | Demonstrates BST searching. |
| bst2.cpp | Extends bst.cpp by adding a function to display the binode data values. |
| bst3.cpp | Extends bst.cpp by adding a function to delete a particular binode |
| bst4.cpp | Extends bst.cpp by adding a function to delete a particular binode |
| bst.h | Implements a BST on general data. |
| bst2.h | Implements a BST on general data This header adds to the header bst.h the ability to display the data of the nodes. |
| bst3.h | Implements a BST on general data. This header adds to the header bst.h the ability to display the data of the nodes. |
| bst4.h | Implements a BST on general data. This header adds to the header bst.h the ability to display the data of the nodes. |
| linked.h | The link list class is contained in this header. |
| linked2.cpp | Demonstrates a search on a linked list of dates. |
| vector6.cpp | Demonstrates that a vector of non-system data can be searched using a linear search. |
| vector7.cpp | Demonstrates that a vector of non-system data can be searched using a linear search after being sorted. Then the search is exited if the value exceed. |
| vector8.cpp | Demonstrates that a vector of non-system data can be searched using a binary search after being sorted. Then the search is exited if the value exceed. |
Open table as spreadsheet |
// program_id bst2.cpp // written_by don voils // date_written 11/3/2006 // // description Extends BST.CPP by adding a // function to display the binode // data values. // // #include<iostream> using namespace std; void clear_screen(); #include"date.h" typedef Date datatype; #include"bst2.h" void main() { Date a_date[7]; a_date[0].set_date(3L,19L,1984L); a_date[1].set_date(5L,5L,1957L); a_date[2].set_date(11L,24L,1934L); a_date[3].set_date(9L,29L,1962L); a_date[4].set_date(1L,19L,1955L); a_date[5].set_date(9L,13L,1960L); a_date[6].set_date(9L,7L,1940L); bst<datatype> bst1; cout << "The following dates are being entered into the BST:" << endl; short index; for(index=0;index<7;++index) { cout << a_date[index] << "\n"; bst1.insert(a_date[index]); } char resp; cout << endl << endl << "Continue? (Y/N) "; cin >> resp; cout << endl << endl << "The data value of the nodes are: " << endl; bst1.display(cout); cout << endl << endl << "Continue? (Y/N) "; cin >> resp; cout << endl << endl; } void clear_screen() { for(short index=0;index<250;++index) cout << endl; } // header_id bst2.h // written_by don voils // date_written 11/3/2006 // // // descripton Implements a BST on general data // This header adds to the header bst.h // the ability to display the data of the nodes. // #ifndef BST #define BST class binode { public: datatype data; binode * left; binode * right; binode() { left = right = NULL; } binode(datatype value) { data = value; left = right = NULL; } binode(datatype value,binode* ptr1,binode * ptr2) { data = value; left = ptr1; right = ptr2; } }; template <typename datatype> class bst { private: binode * root; public: bst() { root = NULL; } ~bst() { binode * ptr, * parent; bool left_node; while(!empty()) { ptr = root; while((ptr->left!=NULL)||(ptr->right!=NULL)) { left_node = false; if(ptr->left!=NULL) { parent = ptr; ptr = ptr->left; left_node = true; } else { parent = ptr; ptr = ptr->right; } } if(root==ptr) root = NULL; else if(left_node) parent->left = NULL; else parent->right = NULL; delete ptr; } if(!empty()) cerr << endl << "The destructor did not work correctly." << endl << endl; } bool empty() { return (root == NULL); } void insert(datatype& item); bool search(datatype &item,binode* &location); void display(ostream & out); void traverse(ostream& out,binode * ptr); }; template<typename datatype> void bst<datatype>::display(ostream & out) { traverse(out,root); } template<typename datatype> void bst<datatype>::traverse(ostream& out, binode * ptr) { if(ptr != NULL) { traverse(out,ptr->left); out << ptr->data << "\n"; traverse(out,ptr->right); } } template<typename datatype> void bst<datatype>::insert(datatype& item) { binode* ptr = root, * parent = NULL; bool found = false; for(;;) { if(found || (ptr == NULL)) break; parent = ptr; if(item < ptr->data) ptr = ptr->left; else if(item > ptr->data) ptr = ptr->right; else found = true; } if(found) cerr << "The item " << item << " already is in the tree.\n"; else { ptr = new binode(item); if(parent == 0) root = ptr; else if(item < (parent->data)) parent->left = ptr; else parent->right = ptr; } } template<typename datatype> bool bst<datatype>::search(datatype &item,binode* &location) { binode* ptr = root; bool found = false; for(;;) { if(found || (ptr == NULL)) break; if(item < ptr->data) ptr = ptr->left; else if(item > ptr->data) ptr = ptr->right; else { found = true; location = ptr; } } return found; } #endif // program_id bst3.cpp // date_written 11/3/2006 // // program description Extends BST.CPP by adding a // function to delete a particular binode // ‥ // // #include<iostream> using namespace std; void clear_screen(); #include"date.h" typedef Date datatype; #include"bst3.h" void main() { Date a_date[7]; a_date[0].set_date(3L,19L,1984L); a_date[1].set_date(5L,5L,1957L); a_date[2].set_date(11L,24L,1934L); a_date[3].set_date(9L,29L,1962L); a_date[4].set_date(1L,19L,1955L); a_date[5].set_date(9L,13L,1960L); a_date[6].set_date(9L,7L,1940L); bst<datatype> bst1; short index; for(index=0;index<7;++index) { bst1.insert(a_date[index]); } Date delete_date; char resp; do { clear_screen(); cout << endl << endl << "The data value of the nodes are: " << endl; bst1.display(cout); cout << endl<< endl << "What date do you want to delete? (mm/dd/yyyy) "; cin >> delete_date; cout << endl; bst1.delete_node(delete_date); cout << endl << endl << "The data value of the nodes are: " << endl; bst1.display(cout); cout << endl << endl << "Do you want to delete another? (Y/N) "; cin >> resp; }while((resp=='y') || (resp=='Y')); cout << endl << endl << "Continue? (Y/N) "; cin >> resp; clear_screen(); cout << endl << endl; } void clear_screen() { for(short index=0;index<250;++index) cout << endl; } // header_id bst3.h // written_by don voils // date_written 11/3/2006 // // descripton Implements a BST on general data // This header adds to the header bst.h // the ability to display the data of the nodes. // #ifndef BST #define BST class binode { public: datatype data; binode * left; binode * right; binode() { left = right = NULL; } binode(datatype value) { data = value; left = right = NULL; } binode(datatype value,binode* ptr1,binode * ptr2) { data = value; left = ptr1; right = ptr2; } }; template <typename datatype> class bst { private: binode * root; public: bst() { root = NULL; } ~bst() { binode * ptr, * parent; bool left_node; while(!empty()) { ptr = root; while((ptr->left!=NULL)||(ptr->right!=NULL)) { left_node = false; if(ptr->left!=NULL) { parent = ptr; ptr = ptr->left; left_node = true; } else { parent = ptr; ptr = ptr->right; } } if(root==ptr) root = NULL; else if(left_node) parent->left = NULL; else parent->right = NULL; delete ptr; } if(!empty()) cerr << endl << "The destructor did not work correctly." << endl << endl; } bool empty() { return (root == NULL); } void insert(datatype& item); bool search(datatype &item,binode* &location,binode* &parent); void display(ostream & out); void traverse(ostream& out,binode * ptr); void delete_node(datatype& item); }; template<typename datatype> void bst<datatype>::display(ostream & out) { traverse(out,root); } template<typename datatype> void bst<datatype>::traverse(ostream& out,binode * ptr) { if(ptr != NULL) { traverse(out,ptr->left); out << ptr->data << "\n"; traverse(out,ptr->right); } } template<typename datatype> void bst<datatype>::insert(datatype& item) { binode* ptr = root, * parent = NULL; bool found = false; for(;;) { if(found || (ptr == NULL)) break; parent = ptr; if(item < ptr->data) ptr = ptr->left; else if(item > ptr->data) ptr = ptr->right; else found = true; } if(found) cerr << "The item " << item << " already is in the tree.\n"; else { ptr = new binode(item); if(parent == 0) root = ptr; else if(item < (parent->data)) parent->left = ptr; else parent->right = ptr; } } template<typename datatype> bool bst<datatype>::search(datatype &item,binode* &location, binode* &parent) { binode* ptr = root; parent = NULL; bool found = false; for(;;) { if(found || (ptr == NULL)) break; if(item < ptr->data) { parent = ptr; ptr = ptr->left; } else if(item > ptr->data) { parent = ptr; ptr = ptr->right; } else { found = true; location = ptr; } } return found; } template<typename datatype> void bst<datatype>::delete_node(datatype& item) { bool found; binode* ptr, *location, *parent; found = search(item,location,parent); if(!found) cerr << "Item not in the BST\n"; else { ptr = location; if((ptr->left != NULL) && (ptr->right != NULL)) { binode *successor = ptr->right; parent = ptr; while(successor->left != NULL) { parent = successor; successor = successor -> left; } ptr->data = successor->data;; ptr = successor; } binode * subtree = ptr->left; if(subtree==NULL) subtree = ptr->right; if(parent==NULL) root = subtree; else if(parent->left == ptr) parent->left = subtree; else parent->right = subtree; delete ptr; } } #endif // program_id bst4.cpp // written_by don voils // date_written 11/12/2006 // // description Extends BST.CPP by adding a // function to delete a particular binode // ‥ // // #include<iostream> #include<fstream> using namespace std; #include"date.h" typedef Date datatype; #include"bst4.h" void clear_screen(); void insert_from_file(bst<datatype> &bst1); void store_in_file(bst<datatype> &bst1); void save_file_destroy(bst<datatype> &bst1); void main() { Date a_date[7]; a_date[0].set_date(3L,19L,1984L); a_date[1].set_date(5L,5L,1957L); a_date[2].set_date(11L,24L,1934L); a_date[3].set_date(9L,29L,1962L); a_date[4].set_date(1L,19L,1955L); a_date[5].set_date(9L,13L,1960L); a_date[6].set_date(9L,7L,1940L); bst<datatype> bst1; datatype b_date; short which, index; char resp; do { clear_screen(); cout << "Select an option:" << endl << endl << "1. Insert data into the BST from the file" << endl << endl << "2. Insert data from the stored array"<< endl << endl << "3. Insert data into the BST from the keyboard" << endl << endl << "4. Is the BST empty?" << endl << endl << "5. Delete data from the BST" << endl << endl << "6. Display all of the elements of the list" << endl << endl << "7. Send the data from the BST to the file" << endl << endl << "8. Exit the program." << endl << endl << endl <<endl << "Which option? "; cin >> which; switch(which) { case 1: insert_from_file(bst1); break; case 2: clear_screen(); cout << "The elements being inserted are: " << endl << endl; for(index=0;index<7;++index) { cout << a_date[index] << " "; bst1.insert(a_date[index]); } cout << endl << endl << "The array stored in the BST. " << endl << endl << "Continue? (Y/N)"; cin >> resp; break; case 3: clear_screen(); cout << "What date do you want to insert into the BST? "; cin >> b_date; bst1.insert(b_date); cout << endl << endl << "The date " << b_date << " is stored in BST. " << endl << endl << "Continue? (Y/N)"; cin >> resp; break; case 4: clear_screen(); if(bst1.empty()) cout << "The BST is empty."; else cout << "The BST is not empty."; cout << endl << endl << "Continue? (Y/N)"; cin >> resp; break; case 5: clear_screen(); cout << "The dates in the BST are the following: " << endl; bst1.display(cout); cout << endl << endl << "What date do you want to delete from the BST? "; cin >> b_date; bst1.delete_node(b_date); cout << endl << endl << "The date " << b_date << " is stored in BST. " << endl << endl << "Continue? (Y/N)"; cin >> resp; break; break; case 6: clear_screen(); cout << "The dates in the BST are the following: " << endl; bst1.display(cout); cout << endl << endl << "Continue? (Y/N)"; cin >> resp; break; case 7: clear_screen(); save_file_destroy(bst1); cout << "The data in the BST is the following: " << endl << endl; bst1.display(cout); cout << endl << endl << "Continue? (Y/N)"; cin >> resp; break; case 8: break; default: break; } }while(which != 8); clear_screen(); } void clear_screen() { for(short index=1;index<=250;++index) cout << endl; } void insert_from_file(bst<datatype> &bst1) { clear_screen(); ifstream infile("date.dat",ios::binary|ios::in); if(!infile||infile.eof()) { cout << "\nError opening the file.\n"; return; } datatype b_date; while(infile) { infile.read((char*)&b_date,sizeof(datatype)); bst1.insert(b_date); } infile.close(); cout << endl << endl << "The data from the file was inserted " << "into the BST. " << endl << endl << "Continue? (Y/N)"; char resp; cin >> resp; } void save_file_destroy(bst<datatype> &bst1) { binode * ptr, * parent; ofstream outfile("date.dat",ios::binary | ios::out); if(!outfile) { cout << "Error opening the file."; char resp; cin >> resp; return; } datatype a_date; bool left_node; while(!bst1.empty()) { ptr = bst1.root; while((ptr->left!=NULL)||(ptr->right!=NULL)) { left_node = false; if(ptr->left!=NULL) { parent = ptr; ptr = ptr->left; left_node = true; } else { parent = ptr; ptr = ptr->right; } } if(bst1.root==ptr) bst1.root = NULL; else if(left_node) parent->left = NULL; else parent->right = NULL; outfile.write((char*)&(ptr->data),sizeof(datatype)); delete ptr; } } // header_id bst4.h // written_by don voils // date_written 11/3/2006 // // // descripton Implements a BST on general data // This header adds to the header bst.h // the ability to display the data of the nodes. // #ifndef BST #define BST class binode { public: datatype data; binode * left; binode * right; binode() { left = right = NULL; } binode(datatype value) { data = value; left = right = NULL; } binode(datatype value,binode* ptr1,binode * ptr2) { data = value; left = ptr1; right = ptr2; } }; template <typename datatype> class bst { private: binode * root; public: bst() { root = NULL; } ~bst() { binode * ptr, * parent; bool left_node; while(!empty()) { ptr = root; while((ptr->left!=NULL)||(ptr->right!=NULL)) { left_node = false; if(ptr->left!=NULL) { parent = ptr; ptr = ptr->left; left_node = true; } else { parent = ptr; ptr = ptr->right; } } if(root==ptr) root = NULL; else if(left_node) parent->left = NULL; else parent->right = NULL; delete ptr; } if(!empty()) cerr << endl << "The destructor did not work correctly." << endl << endl; } bool empty() { return (root == NULL); } void insert(datatype& item); bool search(datatype &item,binode* &location,binode* &parent); void display(ostream & out); void traverse(ostream& out,binode * ptr); void delete_node(datatype& item); friend void save_file_destroy(bst &bst1); }; template<typename datatype> void bst<datatype>::display(ostream & out) { traverse(out,root); } template<typename datatype> void bst<datatype>::traverse(ostream& out,binode * ptr) { if(ptr != NULL) { traverse(out,ptr->left); out << ptr->data << "\n"; traverse(out,ptr->right); } } template<typename datatype> void bst<datatype>::insert(datatype& item) { binode* ptr = root, * parent = NULL; bool found = false; for(;;) { if(found || (ptr == NULL)) break; parent = ptr; if(item < ptr->data) ptr = ptr->left; else if(item > ptr->data) ptr = ptr->right; else found = true; } if(found) cerr << "The item " << item << " already is in the tree.\n"; else { ptr = new binode(item); if(parent == 0) root = ptr; else if(item < (parent->data)) parent->left = ptr; else parent->right = ptr; } } template<typename datatype> bool bst<datatype>::search(datatype &item,binode* &location, binode* &parent) { binode* ptr = root; parent = NULL; bool found = false; for(;;) { if(found || (ptr == NULL)) break; if(item < ptr->data) { parent = ptr; ptr = ptr->left; } else if(item > ptr->data) { parent = ptr; ptr = ptr->right; } else { found = true; location = ptr; } } return found; } template<typename datatype> void bst<datatype>::delete_node(datatype& item) { bool found; binode* ptr, *location, *parent; found = search(item,location,parent); if(!found) cerr << "Item not in the BST\n"; else { ptr = location; if((ptr->left != NULL) && (ptr->right != NULL)) { binode *successor = ptr->right; parent = ptr; while(successor->left != NULL) { parent = successor; successor = successor -> left; } ptr->data = successor->data;; ptr = successor; } binode * subtree = ptr->left; if(subtree==NULL) subtree = ptr->right; if(parent==NULL) root = subtree; else if(parent->left == ptr) parent->left = subtree; else parent->right = subtree; delete ptr; } } #endif // program_id bst.cpp // written_by don voils // date_written 11/3/2006 // // description Demonstrates BST searching. // // #include<iostream> using namespace std; void clear_screen(); #include"date.h" typedef Date datatype; #include"bst.h" void main() { bool found; binode* location; Date a_date[8]; a_date[0].set_date(5L,5L,1977L); a_date[1].set_date(11L,24L,1934L); a_date[2].set_date(1L,19L,1955L); a_date[3].set_date(5L,5L,1957L); a_date[4].set_date(9L,13L,1960L); a_date[5].set_date(9L,29L,1962L); a_date[6].set_date(5L,5L,1977L); a_date[7].set_date(9L,7L,1940L); bst<datatype> bst1; cout << "The following dates are being entered into the BST:" << endl; short index; for(index=0;index<8;++index) { cout << a_date[index] << endl; bst1.insert(a_date[index]); } char resp; cout << endl << endl << "Continue? (Y/N) "; cin >> resp; while((resp=='y')||(resp=='Y')) { clear_screen(); cout << "The following dates are in the BST:" << endl; short index; for(index=0;index<8;++index) { cout << a_date[index] << endl; } cout << endl << endl << "What Date do you want to search for in the BST? (mm/dd/yyyy) "; Date new_date; cin >> new_date; found = bst1.search(new_date, location); if(found) cout << endl << "The date " << new_date << " was found at location "<< location << endl; else cout << endl << "The date " << new_date << " was not found in the BST." << endl; cout << endl << endl << "Another search? (Y/N) "; cin >> resp; cout << endl << endl; } clear_screen(); } void clear_screen() { for(short index=0;index<250;++index) cout << endl; } // header_id bst.h // written_by don voils // date_written 11/3/2006 // // descripton Implements a BST on general data. // #ifndef BST #define BST class binode { public: datatype data; binode * left; binode * right; binode() { left = right = NULL; } binode(datatype value) { data = value; left = right = NULL; } binode(datatype value,binode* ptr1,binode * ptr2) { data = value; left = ptr1; right = ptr2; } }; template <typename datatype> class bst { private: binode * root; public: bst() { root = NULL; } ~bst() { binode * ptr, * parent; bool left_node; while(!empty()) { ptr = root; while((ptr->left!=NULL)||(ptr->right!=NULL)) { left_node = false; if(ptr->left!=NULL) { parent = ptr; ptr = ptr->left; left_node = true; } else { parent = ptr; ptr = ptr->right; } } if(root==ptr) root = NULL; else if(left_node) parent->left = NULL; else parent->right = NULL; delete ptr; } if(!empty()) cerr << endl << "The destructor did not work correctly." << endl << endl; } bool empty() { return (root == NULL); } void insert(datatype& item); bool search(datatype &item,binode* &location); }; template<typename datatype> void bst<datatype>::insert(datatype& item) { binode* ptr = root, * parent = NULL; bool found = false; for(;;) { if(found || (ptr == NULL)) break; parent = ptr; if(item < ptr->data) ptr = ptr->left; else if(item > ptr->data) ptr = ptr->right; else found = true; } if(found) cerr << "\nThe item " << item << " already is in the tree.\n\n"; else { ptr = new binode(item); if(parent == 0) root = ptr; else if(item < (parent->data)) parent->left = ptr; else parent->right = ptr; } } template<typename datatype> bool bst<datatype>::search(datatype &item,binode* &location) { binode* ptr = root; bool found = false; for(;;) { if(found || (ptr == NULL)) break; if(item < ptr->data) ptr = ptr->left; else if(item > ptr->data) ptr = ptr->right; else { found = true; location = ptr; } } return found; } #endif // program_id date.h // written_by don voils // date_written 9/2/2006 // // description This header contains the definition // of the class date that is used in many // different examples. // #ifndef DATE #define DATE class Date { private: long month, day, year; public: Date(){ } Date(long m, long d, long y) { month = m; day = d; year = y; } void get_date(); void set_date(long m, long d, long y); long last_day(long m, long y); long show_day(); long show_month(); long show_year(); bool leap_year(long y); Date operator +(long number_days); Date operator -(long number_days); long operator -(Date other_date); long days_since(long m, long d, long y); long f(long m,long y); long g(long m); bool incorrect_date(long m,long d,long y); bool operator <(Date a_date); bool operator <=(Date a_date); bool operator ==(Date a_date); bool operator !=(Date a_date); bool operator >(Date a_date); bool operator >=(Date a_date); friend ostream &operator << (ostream &stream, Date ab); friend istream &operator >> (istream &stream, Date &ab); }; ostream &operator << (ostream &stream, Date ab) { stream << ab.month << "/"; stream << ab.day << "/"; stream << ab.year <<" "; return stream; } istream &operator >> (istream &stream, Date &ab) { char slash; stream >> ab.month >> slash >> ab.day >> slash >> ab.year; return stream; } long Date::show_day() { return day; } long Date::show_month() { return month; } long Date::show_year() { return year; } void Date::get_date() { char dash; do { cin >> month >> dash >> day >> dash >> year; }while(incorrect_date(month,day,year)); } void Date::set_date(long m,long d,long y) { month = long(m); day = long(d); year = long(y); } Date Date::operator + (long number_days) { Date next_day; next_day.set_date(month,day,year); for(long index=1;index <=number_days;++index) { if (next_day.day < last_day(next_day.month,next_day.year)) { next_day.day += 1L; } else { if(next_day.month<12L) { next_day.month += 1L; next_day.day = 1L; } else { next_day.month = 1L; next_day.day = 1L; next_day.year += 1L; } } } return next_day; } Date Date::operator - (long number_days) { Date next_day; next_day.set_date(month,day,year); for(short index=1;index <= number_days;++index) { if (next_day.day != 1L) { next_day.day -= 1L; } else { if(next_day.month != 1L) { next_day.month -= 1L; next_day.day = last_day(next_day.month,next_day.year); } else { next_day.month = 12L; next_day.day = 31L; next_day.year -= 1L; } } } return next_day; } long Date::last_day(long m, long y) { long last_day; long days_in_month[]={0L, 31L, 28L, 31L, 30L, 31L, 30L, 31L, 31L, 30L, 31L, 30L, 31L}; if (m!=2L) last_day=days_in_month[m]; else if (leap_year(y)) last_day =29L; else last_day=days_in_month[m]; return last_day; } bool Date::leap_year(long y) { bool leap_test; if (((y%4L== 0L) && (y%100L != 0L)) || (y%400L == 0L)) leap_test=true; else leap_test=false; return leap_test; } bool Date::incorrect_date(long m, long d, long y) { bool not_correct; if ((m>=1L) && (m<=12L) && (d>=1L) && (d<=last_day(m,y))) not_correct = false; else not_correct = true; return not_correct; } long Date::days_since(long m,long d,long y) { long number = 1461L*f(m,y)/4L + 153L*g(m)/5L + d; return(number); } long Date::f(long m,long y) { long number = (m<=2L) ? y - 1L :y; return(number); } long Date::g(long m) { long number = (m<=2L) ? m + 13L : m + 1L; return(number); } long Date::operator - (Date b_date) { long days; days = days_since(month,day,year) -days_since(b_date.month,b_date.day,b_date.year); return days; } bool Date::operator >(Date a_date) { bool resp; long first_date, second_date; first_date=days_since(month,day,year); second_date=days_since(a_date.month,a_date.day,a_date.year); resp = (first_date > second_date)? true : false; return resp; } bool Date::operator >=(Date a_date) { bool resp; long first_date, second_date; first_date=days_since(month,day,year); second_date=days_since(a_date.month,a_date.day,a_date.year); resp = (first_date >= second_date)? true : false; return resp; } bool Date::operator ==(Date a_date) { bool resp; long first_date, second_date; first_date=days_since(month,day,year); second_date=days_since(a_date.month,a_date.day,a_date.year); resp = (first_date == second_date)? true : false; return resp; } bool Date::operator !=(Date a_date) { bool resp; long first_date, second_date; first_date=days_since(month,day,year); second_date=days_since(a_date.month,a_date.day,a_date.year); resp = (first_date != second_date)? true : false; return resp; } bool Date::operator <(Date a_date) { bool resp; long first_date, second_date; first_date=days_since(month,day,year); second_date=days_since(a_date.month,a_date.day,a_date.year); resp = (first_date < second_date)? true : false; return resp; } bool Date::operator <= (Date a_date) { bool resp; long first_date, second_date; first_date=days_since(month,day,year); second_date=days_since(a_date.month,a_date.day,a_date.year); resp = (first_date <= second_date)? true : false; return resp; } #endif // program_id linked2.cpp // date_written 10/22/2006 // // // program description Demonstrates a search on a linked list. // of dates. // // #include<iostream> using namespace std; // The data searched will be date objects from the follow file. // #include"date.h" // The data used will be objects from the date class. // typedef Date datatype; // The link list class is contained in the following header. // The linear search function has been added as a member // function to the class. // #include"linked.h" void clear_screen(); void main() { short which; char resp; bool found; datatype item, value; List list1; do { clear_screen(); cout << "Select an option:" << endl << endl << "0. Search for an item " << endl << endl << "1. Insert an item at the front" << endl << endl << "2. Insert an item at the end" << endl << endl << "3. Insert an item after another item" << endl << endl << "4. Is the list empty?" << endl << endl << "5. Delete an item at the front" << endl << endl << "6. Delete an item at the end" << endl << endl << "7. Delete an item after another item" << endl << endl << "8. Display all of the elements of the linked list" << endl << endl << "9. Exit the program." << endl << endl << endl <<endl << "Which option? "; cin >> which; switch(which) { case 0: clear_screen(); cout << "Enter the value to find in the list: (mm/dd/yyyy) "; cin >> item; node *location; found = list1.linearsearch(item,location); if(found) cout << endl << endl << "The item " << item << " was found " << " at location " << location << endl; else cout << endl << endl << "The item " << item << " was not found." << endl; cout << endl << endl << "Continue? (Y/N)"; cin >> resp; break; case 1: clear_screen(); cout << "Enter the value to add to the front of the list: (mm/dd/yyyy) "; cin >> item; list1.insert_front(item); break; case 2: clear_screen(); cout << "Enter the value to add to the end of the list: (mm/dd/yyyy) "; cin >> item; list1.insert_end(item); break; case 3: clear_screen(); cout << "Enter the value in the list to be inserted after: (mm/dd/yyyy) "; cin >> value; cout << endl << endl << "Enter the value to add to the list after " << value << ": "; cin >> item; list1.insert_middle(item,value); break; case 4: clear_screen(); if(list1.empty()) cout << "The list is empty."; else cout << "The list is not empty."; cout << endl << endl << "Continue? (Y/N)"; cin >> resp; break; case 5: clear_screen(); list1.delete_front(); break; case 6: clear_screen(); list1.delete_end(); break; case 7: clear_screen(); cout << "Enter the value in the list to be deleted: (mm/dd/yyyy) "; cin >> value; list1.delete_middle(value); break; case 8: clear_screen(); list1.display(); cout << endl << "Continue? (Y/N)"; cin >> resp; break; case 9: break; default: break; } }while(which != 9); clear_screen(); } void clear_screen() { for(short index=1;index<=250;++index) cout << endl; } // program_id linked.h // written_by don voils // date_written 10/1/2006 // description This file contains the definition of the classes node and List. // #ifndef LINKED #define LINKED class node { public: datatype data; node * next; node(datatype value,node* ptr) { data = value; next = ptr; } }; class List { private: node* first; public: List() { first = NULL; } ~List() { node * ptr; while(first!=NULL) { ptr = first; first = first->next; delete ptr; } } bool empty() { return (first==NULL); } void insert_front(datatype new_value) { node * newptr = new node(new_value,first); first = newptr; } void insert_end(datatype new_value) { node * newptr = new node(new_value,NULL); if(first!=NULL) { node * preptr = first; while((preptr->next)!=NULL) preptr = preptr->next; preptr->next = newptr; } else first = newptr; } void insert_middle(datatype new_value,datatype value) { if(!empty()) { node * preptr = first; while(((preptr->next)!=NULL) && ((preptr->data)!=value)) preptr = preptr->next; if((preptr->data)==value) { node * newptr = new node(new_value,preptr->next); preptr->next = newptr; } } } void delete_front() { if(!empty()) { node *ptr = first; first = first->next; delete ptr; } } void delete_end() { if(!empty()) { if((first->next)==NULL) { delete first; first = NULL; } else { node *ptr; node *preptr = first; while(((preptr->next)->next)!=NULL) preptr = preptr->next; ptr = preptr->next; preptr -> next = NULL; delete ptr; } } } void delete_middle(datatype value) { if(!empty()) { if((first->next)!=NULL) { node *ptr; node *preptr = first; while((preptr->next)!=NULL && (preptr->data)!=value) preptr = preptr->next; ptr = preptr->next; if(ptr!=NULL && ((preptr->data)==value)) { preptr->next = ptr->next; delete ptr; } } } } void display() { cout << "The elements in the list are:" << endl; node * ptr = first; while(ptr != NULL) { cout << ptr->data << endl; ptr = ptr->next; } } // The follow function provides the search for the linked list. // template<typename datatype> bool linearsearch(datatype &item, node* &location) { bool found = false; location = first; for(;;) { if(found || (location == NULL)) break; if(item == location->data) found = true; else location = location->next; } return found; } }; #endif // program_id vector6.cpp // written_by don voils // date_written 10/1/2006 // // description Demonstrates that a vector of non-system // data can be searched using a linear // search. // // #include<iostream> #include<vector> using namespace std; // Header contains the type of data being searched. // #include"date.h" // The generalized data type of the example is set to date // typedef Date Datatype; // Function Declarations // void clear_screen(); template<typename Datatype> bool linearsearch(const vector<Datatype> & a_vector, Datatype &item, short &location) { bool found = false; location = 0; for(;;) { if(found || (location == a_vector.size())) break; if(item == a_vector[location]) found = true; else location++; } return found; } void main() { bool found; short location; char resp; Date date1(1L,1L,1970L); Date date2(1L,19L,1955L); Date date3(5L,5L,1957L); Date date4(9L,13L,1960L); Date date5(9L,29L,1962L); Date date6(11L,24L,1934L); Date date7(9L,7L,1940L); Date date_array[ ] = {date1,date2,date3,date4,date5,date6}; vector<Date> vector1(date_array,date_array+6); do { clear_screen(); cout << "The Date vector contains the following elements:" << endl; short index; for(index=0;index < (int)vector1.size(); ++index) cout << vector1[index] << endl; cout << endl << endl; cout << "What Date do you want to search for in the vector? (mm/dd/yyyy) "; Date new_date; cin >> new_date; found = linearsearch(vector1,new_date,location); if(found) cout << endl << "The date " << new_date << " was found at location "<< location + 1<< endl; else cout << endl << "The date " << new_date << " was not found in the vector." << endl; cout << endl << endl << "Another search? (Y/N) "; cin >> resp; cout << endl << endl; }while((resp=='y')||(resp=='Y')); } void clear_screen() { for(short index=1;index<250;++index) cout << endl; } // program_id vector7.cpp // date_written 10/1/2006 // // description Demonstrates that a vector of non-system // data can be searched using a linear // search after being sorted. Then the // search is exited if the value exceed. // // #include<iostream> #include<vector> #include<algorithm> using namespace std; // Header contains the type of data being searched. // #include"date.h" // The generalized data type of the example is set to date // typedef Date Datatype; // Function Declarations // void clear_screen(); template<typename Datatype> bool linearsearch(const vector<Datatype> & a_vector, Datatype &item, short &location) { bool found = false; location = 0; for(;;) { if(found || (location == a_vector.size()) || (item < a_vector[location])) break; if(item == a_vector[location]) found = true; else location++; } cout << endl << "The number of records counted was: " << location + 1 << endl <<endl; return found; } void main() { bool found; short location; char resp; Date date1(1L,1L,1970L); Date date2(1L,19L,1955L); Date date3(5L,5L,1957L); Date date4(9L,13L,1960L); Date date5(9L,29L,1962L); Date date6(11L,24L,1934L); Date date7(9L,7L,1940L); Date date_array[ ] = {date1, date2, date3, date4, date5, date6}; vector<Date> vector1(date_array,date_array+6); do { clear_screen(); cout << "The date vector contains the following elements:" << endl; short index; for(index=0;index < (int)vector1.size(); ++index) cout << vector1[index] << endl; sort(vector1.begin(),vector1.end()); cout << endl << endl << "The date vector after the sort contains the following elements:" << endl; for(index=0;index < (int) vector1.size(); ++index) cout << vector1[index] << endl; cout << endl << endl << "What date do you want to search for in the vector? (mm/dd/yyyy) "; Date new_date; cin >> new_date; found = linearsearch(vector1, new_date, location); if(found) cout << endl << "The date " << new_date << " was found at location "<< location + 1<< endl; else cout << endl << "The date " << new_date << " was not found in the vector." << endl; cout << endl << endl << "Another search? (Y/N) "; cin >> resp; cout << endl << endl; }while((resp=='y')||(resp=='Y')); } void clear_screen() { for(short index=1;index<250;++index) cout << endl; } // program_id vector8.cpp // written_by don voils // date_written 10/1/2006 // // description Demonstrates that a vector of non-system // data can be searched using a binary // search after being sorted. Then the // search is exited if the value exceed. // // #include<iostream> #include<vector> #include<algorithm> using namespace std; // Header contains the type of data being searched. // #include"date.h" // The generalized data type of the example is set to date // typedef Date Datatype; // Function Declarations // void clear_screen(); template<typename Datatype> bool binarysearch(const vector<Datatype> & a_vector, Datatype &item, short &location) { bool found = false; location = 0; short counted = 0, first = 0, last = (int)a_vector.size() - 1; for(;;) { if(found || (first > last)) break; ++counted; location = (first + last)/2; if(item < a_vector[location]) last = location - 1; else if(item > a_vector[location]) first = location + 1; else found = true; } cout << endl << "The number of records counted was: " << counted << endl <<endl; return found; } void main() { bool found; short location; char resp; Date date1(1L,1L,1970L); Date date2(1L,19L,1955L); Date date3(5L,5L,1957L); Date date4(9L,13L,1960L); Date date5(9L,29L,1962L); Date date6(11L,24L,1934L); Date date7(9L,7L,1940L); Date date_array[ ] = {date1, date2, date3, date4, date5, date6}; vector<Date> vector1(date_array, date_array+6); do { clear_screen(); cout << "The date vector contains the following elements:" << endl; short index; for(index=0;index < (int)vector1.size(); ++index) cout << vector1[index] << endl; sort(vector1.begin(),vector1.end()); cout << endl << endl << "The Date vector after the sort contains the following elements:" << endl; for(index=0;index < (int)vector1.size(); ++index) cout << vector1[index] << endl; cout << endl << endl << "What Date do you want to search for in the vector? (mm/dd/yyyy) "; Date new_date; cin >> new_date; found = binarysearch(vector1,new_date,location); if(found) cout << endl << "The date " << new_date << " was found at location "<< location + 1 << endl; else cout << endl << "The date " << new_date << " was not found in the vector." << endl; cout << endl << endl << "Another search? (Y/N) "; cin >> resp; cout << endl << endl; }while((resp=='y')||(resp=='Y')); } void clear_screen() { for(short index=1;index<250;++index) cout << endl; } 
Intermediate Business Programming with C++
ISBN: 738453099
EAN: N/A
EAN: N/A
Year: 2007
Pages: 142
Pages: 142