EECE 230 Final, Fall 2008

//Paul Salameh 200700446 FINAL // removeDuplicates function added #ifndef H_LinkedListType #define H_LinkedListType #include <iostream> #include <cassert> using namespace std; //Definition of the node template <class Type> struct nodeType { Type info; nodeType<Type> *link; }; template<class Type> class linkedListType { public: void deleteLargerThan(Type item); const linkedListType<Type>& operator= (const linkedListType<Type>&); //Overload the assignment operator. void initializeList(); //Initialize the list to an empty state. //Postcondition: first = NULL, last = NULL, count = 0; bool isEmptyList() const; //Function to determine whether the list is empty. //Postcondition: Returns true if the list is empty, // otherwise it returns false. void print() const; //Function to output the data contained in each node. //Postcondition: none int length() const; //Function to return the number of nodes in the list. //Postcondition: The value of count is returned. void destroyList(); //Function to delete all the nodes from the list. //Postcondition: first = NULL, last = NULL, count = 0; Type front() const; //Function to return the first element of the list. //Precondition: The list must exist and must not be // empty. //Postcondition: If the list is empty, the program // terminates; otherwise, the first // element of the list is returned. Type back()const; //Function to return the last element of the list. //Precondition: The list must exist and must not be // empty. //Postcondition: If the list is empty, the program // terminates; otherwise, the last // element of the list is returned. bool search(const Type& searchItem) const; //Function to determine whether searchItem is in the list. //Postcondition: Returns true if searchItem is in the // list, otherwise the value false is // returned. void insertFirst(const Type& newItem); //Function to insert newItem at the beginning of the list. //Postcondition: first points to the new list, newItem is // inserted at the beginning of the list, // last points to the last node in the list, // and count is incremented by 1. void insertLast(const Type& newItem); //Function to insert newItem at the end of the list. //Postcondition: first points to the new list, newItem // is inserted at the end of the list, // last points to the last node in the list, // and count is incremented by 1. void deleteNode(const Type& deleteItem); //Function to delete deleteItem from the list. //Postcondition: If found, the node containing // deleteItem is deleted from the list. // first points to the first node, last // points to the last node of the updated // list, and count is decremented by 1. linkedListType(); //default constructor //Initializes the list to an empty state. //Postcondition: first = NULL, last = NULL, count = 0; linkedListType(const linkedListType<Type>& otherList); //copy constructor ~linkedListType(); //destructor //Deletes all the nodes from the list. //Postcondition: The list object is destroyed. protected: int count; //variable to store the number of //elements in the list nodeType<Type> *first; //pointer to the first node of the list nodeType<Type> *last; //pointer to the last node of the list private: void copyList(const linkedListType<Type>& otherList); //Function to make a copy of otherList. //Postcondition: A copy of otherList is created and // assigned to this list. public: void removeDuplicates(); }; template<class Type> void linkedListType<Type>::removeDuplicates() {// assumes list is sorted in nondecreasing order nodeType<Type> *current; //pointer to traverse the list current = first; //set current to point to the first node in the list if(current == NULL) return; while (current->link!=NULL) { if(current -> link ->info == current -> info) {//delete next node nodeType<Type> * temp = current->link; current->link = temp->link; delete [] temp; count --; } else current = current->link; //make current point to //the next node } } template<class Type> bool linkedListType<Type>::isEmptyList() const { return(first == NULL); } template<class Type> linkedListType<Type>::linkedListType() //default constructor { first = NULL; last = NULL; count = 0; } template<class Type> void linkedListType<Type>::destroyList() { nodeType<Type> *temp; //pointer to deallocate the memory //occupied by the node while (first != NULL) //while there are nodes in the list { temp = first; //set temp to the current node first = first->link; //advance first to the next node delete temp; //deallocate the memory occupied by temp } last = NULL; //initialize last to NULL; first has already //been set to NULL by the while loop count = 0; } template<class Type> void linkedListType<Type>::initializeList() { destroyList(); //if the list has any nodes, delete them } template<class Type> void linkedListType<Type>::print() const { nodeType<Type> *current; //pointer to traverse the list current = first; //set current so that it points to //the first node while (current != NULL) //while more data to print { cout << current->info << " "; current = current->link; } cout<<endl; }//end print template<class Type> int linkedListType<Type>::length() const { return count; } //end length template<class Type> Type linkedListType<Type>::front() const { assert(last != NULL); return first->info; //return the info of the first node }//end front template<class Type> Type linkedListType<Type>::back() const { assert(last != NULL); return last->info; //return the info of the first node }//end back template<class Type> bool linkedListType<Type>::search(const Type& searchItem) const { nodeType<Type> *current; //pointer to traverse the list bool found = false; current = first; //set current to point to the first //node in the list while (current != NULL && !found) //search the list if (current->info == searchItem) //searchItem is found found = true; else current = current->link; //make current point to //the next node return found; }//end search template<class Type> void linkedListType<Type>::insertFirst(const Type& newItem) { nodeType<Type> *newNode; //pointer to create the new node newNode = new nodeType<Type>; //create the new node assert(newNode != NULL); //if unable to allocate memory, //terminate the program newNode->info = newItem; //store the new item in the node newNode->link = first; //insert newNode before first first = newNode; //make first point to the //actual first node count++; //increment count if (last == NULL) //if the list was empty, newNode is also //the last node in the list last = newNode; }//end insertFirst template<class Type> void linkedListType<Type>::insertLast(const Type& newItem) { nodeType<Type> *newNode; //pointer to create the new node newNode = new nodeType<Type>; //create the new node assert(newNode != NULL); //if unable to allocate memory, //terminate the program newNode->info = newItem; //store the new item in the node newNode->link = NULL; //set the link field of newNode //to NULL if (first == NULL) //if the list is empty, newNode is //both the first and last node { first = newNode; last = newNode; count++; //increment count } else //the list is not empty, insert newNode after last { last->link = newNode; //insert newNode after last last = newNode; //make last point to the actual last node count++; //increment count } }//end insertLast template<class Type> void linkedListType<Type>::deleteNode(const Type& deleteItem) { nodeType<Type> *current; //pointer to traverse the list nodeType<Type> *trailCurrent; //pointer just before current bool found; if (first == NULL) //Case 1; the list is empty. cout << "Cannot delete from an empty list." << endl; else { if (first->info == deleteItem) //Case 2 { current = first; first = first->link; count--; if (first == NULL) //the list has only one node last = NULL; delete current; } else //search the list for the node with the given info { found = false; trailCurrent = first; //set trailCurrent to point //to the first node current = first->link; //set current to point to //the second node while (current != NULL && !found) { if (current->info != deleteItem) { trailCurrent = current; current = current-> link; } else found = true; }//end while if (found) //Case 3; if found, delete the node { trailCurrent->link = current->link; count--; if (last == current) //node to be deleted //was the last node last = trailCurrent; //update the value //of last delete current; //delete the node from the list } else cout << "The item to be deleted is not in " << "the list." << endl; }//end else }//end else }//end deleteNode template<class Type> void linkedListType<Type>::copyList (const linkedListType<Type>& otherList) { nodeType<Type> *newNode; //pointer to create a node nodeType<Type> *current; //pointer to traverse the list if (first != NULL) //if the list is nonempty, make it empty destroyList(); if (otherList.first == NULL) //otherList is empty { first = NULL; last = NULL; count = 0; } else { current = otherList.first; //current points to the //list to be copied count = otherList.count; //copy the first node first = new nodeType<Type>; //create the node assert(first != NULL); first->info = current->info; //copy the info first->link = NULL; //set the link field of //the node to NULL last = first; //make last point to the //first node current = current->link; //make current point to //the next node //copy the remaining list while (current != NULL) { newNode = new nodeType<Type>; //create a node assert(newNode != NULL); newNode->info = current->info; //copy the info newNode->link = NULL; //set the link of //newNode to NULL last->link = newNode; //attach newNode after last last = newNode; //make last point to //the actual last node current = current->link; //make current point //to the next node }//end while }//end else }//end copyList template<class Type> linkedListType<Type>::~linkedListType() //destructor { destroyList(); }//end destructor template<class Type> linkedListType<Type>::linkedListType (const linkedListType<Type>& otherList) { first = NULL; copyList(otherList); }//end copy constructor //overload the assignment operator template<class Type> const linkedListType<Type>& linkedListType<Type>::operator= (const linkedListType<Type>& otherList) { if (this != &otherList) //avoid self-copy { copyList(otherList); }//end else return *this; } template <class Type> void linkedListType<Type>::deleteLargerThan(Type item) { if (first ->info > item) first=first->link; nodeType<Type> *current; current = first; if(current == NULL) return; while (current->link!=NULL) { if (current->link->info > item) { nodeType<Type> *temp = current->link; current->link = temp->link; delete [] temp; count --; } else current = current->link; } } #endif #ifndef H_myDynamicArray #define H_myDynamicArray // Preprocessor directive used to avoid problems resulting from multiple include. // See [Malik, pages 637-638]. #include <iostream> using namespace std; #include <cmath> //////////////////////////////////////////////////////////////////////////////// //////////////////// template<class Type> class myDynamicArray { protected: Type * A; int size; public: myDynamicArray(int sizeValue); myDynamicArray(); myDynamicArray(const myDynamicArray<Type> & other); ~myDynamicArray(); const myDynamicArray<Type>& operator=(const myDynamicArray<Type> & other); void copy(const myDynamicArray<Type> & copied); void set(int i, Type x); Type get(int i) const; int getSize() const; void print() const; int search(Type query) const; bool isSorted() const; void insertionSort(); void concatinate(myDynamicArray & B); }; //////////////////////////////////////////////////////////////////////////////// //////////////////// template<class Type> myDynamicArray<Type>::myDynamicArray() { A= new Type[999]; size=999; for(int i=0;i<size;i++) A[i]=0; } template<class Type> myDynamicArray<Type>::myDynamicArray(int sizeValue) { size=sizeValue; A=new Type[size]; for(int i=0;i<size;i++) A[i]=0; } template<class Type> myDynamicArray<Type>::~myDynamicArray() { delete [] A; size = 0; } template<class Type> myDynamicArray<Type>::myDynamicArray(const myDynamicArray<Type> & other) { copy(other); } template<class Type> const myDynamicArray<Type>& myDynamicArray<Type>::operator=(const myDynamicArray<Type> & other) { if(this != & other) copy(other); return *this; } template<class Type> void myDynamicArray<Type>::set(int i, Type x) { A[i] = x; } template<class Type> Type myDynamicArray<Type>::get(int i) const { return A[i]; } template<class Type> int myDynamicArray<Type>::getSize() const { return size; } template<class Type> int myDynamicArray<Type>::search(Type query) const { for(int i=0; i<size; i++) if(A[i]==query) return i; return -1; } template<class Type> void myDynamicArray<Type>::print() const { for(int i=0;i<size;i++) cout<<A[i]<<" "; cout<<endl; } template<class Type> bool myDynamicArray<Type>::isSorted() const { bool sorted=true; for(int i=1;i<size;i++) if(A[i-1]>A[i]) sorted=false; return sorted; } template<class Type> void myDynamicArray<Type>::insertionSort() { Type temp; for(int j=1;j<size;j++) { temp=A[j]; for(int i=j-1; (A[i]>temp) && (i>-1);i--) A[i+1]=A[i]; A[i+1]=temp; } } template<class Type> void myDynamicArray<Type>::copy(const myDynamicArray & copied) { delete [] A; A = new Type[copied.size]; size=copied.size; for(int i=0; i<size; i++) A[i]=copied.A[i]; } template<class Type> void myDynamicArray<Type>::concatinate(myDynamicArray & B) { Type * final; final = new Type[size+B.size]; for(int i=0;i<size;i++) final[i]=A[i]; for(i=size; i<(size+B.size); i++) final[i]=B.A[i-size]; delete [] A; A = final; size=size + B.size; } //////////////////////////////////////////////////////////////////////////////// ///////////////////// #endif #include <iostream> using namespace std; bool subArraySum(int *A,int n, int t, int & start, int & end); bool subArraySum(int *A,int n, int t, int & start, int & end) { for (int i=0;i<n;i++) { int sum =0; for (int j=i;j<n;j++) { sum = sum + A[j]; if (sum == t) { start = i; end = j; return true; } } } return false; } void main() { int A[]={1,7,5,3,2,12,-25}, t = 22, start,end; if (subArraySum(A,7,t,start,end)) cout<<"YES, it contains subarray and start = "<<start<<" and end = "<<end<<endl; else if (!subArraySum(A,7,t,start,end)) cout<<"NO, it doesn't contain subarray\n"; } #include <iostream> using namespace std; int signChangeLocator(int * A,int start,int end); int signChangeLocator(int * A,int start,int end) { if(start <=end) { int mid = (start+end)/2; if (A[mid] > 0 && mid+1 <= end && A[mid+1] > 0) { if (A[mid+1] > 0) return signChangeLocator(A,mid+1,end); } else if (A[mid] < 0) return signChangeLocator(A,start,mid-1); else if (A[mid] > 0) { if (mid+1 > end || A[mid+1] < 0) return mid; } } else return -1; } void main() { int A[] = {3,18,5,2,10,7,-4,-10,-1}; int B[] = {7,-4,-10,-1}; int C[] = {3,18,5,2,10,7,-4}; int D[] = {3,18,5,2,10,7}; int E[] = {-4,-10,-1}; int index = signChangeLocator(A,0,8); cout<<index<<endl; index = signChangeLocator(B,0,3); cout<<index<<endl; index = signChangeLocator(C,0,6); cout<<index<<endl; index = signChangeLocator(D,0,5); cout<<index<<endl; index = signChangeLocator(E,0,2); cout<<index<<endl; } #include <iostream> #include "myDynamicArray.h" #include <cassert> using namespace std; class permutation: public myDynamicArray<int> { public: permutation(int dimensionValue) : myDynamicArray<int>(dimensionValue) { for (int i=0;i<dimensionValue ; i++) A[i]=i+1; }; permutation(const permutation & other) {copy(other);} int length() const {return size;} permutation operator*(const permutation & q) const { assert(length()==q.length()); permutation product(length()); for(int i=0;i<length();i++) product.A[i]= A[q.A[i]-1]; return product;//Here I'm having error with return although I'm using the copy }; //constructor the same way it was used in the previous final exam!! permutation operator!() const { permutation temp(length()); for(int i=0;i<length();i++) temp.A[i]= A[A[i]-1]; return temp;//Here I'm having error with return although I'm using the copy }; //constructor the same way it was used in the previous final exam: /*realVector operator-() const { realVector r(dimension()); for(int i=0;i<dimension();i++) r.A[i] = - A[i]; return r; }; */ void set(int i, int j) { A[i]=j; }; void print() const { cout<<"("; for(int i=0;i<length();i++) { cout<<A[i]; if(i!=length()-1) cout<<" "; } cout<<")"<<endl; }; }; void main() { permutation p(5); p.print(); p.set(0,2); p.set(1,3); p.set(2,1); p.set(3,5); p.set(4,4); p.print(); permutation q(5); q.set(0,5); q.set(1,3); q.set(2,2); q.set(3,1); q.set(4,4); q.print(); permutation r(5); r = p*q; r.print(); permutation t(5); t= !p; t.print(); cout<<t.length()<<endl; } #include <iostream> #include "linkedList.h" using namespace std; void main () { linkedListType<int> L; L.insertLast(1); L.insertLast(7); L.insertLast(12); L.insertLast(3); L.insertLast(4); L.insertLast(20); L.insertLast(7); L.insertLast(8); L.insertLast(15); L.insertLast(11); L.insertLast(2); cout<<"L: ";L.print(); L.deleteLargerThan(10); cout<<"L: ";L.print(); linkedListType<int> S; S.insertLast(11); S.insertLast(7); S.insertLast(12); S.insertLast(3); S.insertLast(14); cout<<"S: ";S.print(); S.deleteLargerThan(10); cout<<"S: ";S.print(); linkedListType<int> T; T.insertLast(11); cout<<"T: ";T.print(); T.deleteLargerThan(10); cout<<"T: ";T.print(); }