egy science

C++ exercise 3

2012-11-25T19:01:00.003+02:00

#include <iostream.H>

void main()
{


   for(int x=0;x<=100;x++)
   if (x%5!=0)
    cout<<x<<endl;

}

C++: Shifting array

2012-11-23T18:19:00.001+02:00

//This C++ program makes shift to all array members.

#include<iostream.h>
#include <cstdlib> // included to use exit(0)
void main()
{
    int a[10];int x,y;

    cout<<"Enter 10 numbers\n";
    ;
    for(int i=0;i<10;i++)
    {
        cout<<"No."<<i<<endl;
        cin>>x;
        a[i]=x;
    }
    cout<<"\n[";
    for(int k=0;k<10;k++)
        cout<<a[k]<<" ";
    cout<<"]";
    cout<<"\n Press 1 to shift right.\n Press 2 to shift left.\n press 0 to exit.\n";
        cin>>y;
        if(y==1)
            {

            for(int j=9;j>0;j--)
                {

                a[j]=a[j-1];

                }
                a[0]=0; //empty

                cout<<"\n[";
                for(int r=0;r<10;r++)
                cout<<a[r]<<" ";
                cout<<"]"<<endl;
            }
        else if (y==2)
            {

            for(int j=0;j<9;j++)
                {

                a[j]=a[j+1];

                }

                a[9]=0; //empty

                cout<<"\n[";
                for(int r=0;r<10;r++)
                cout<<a[r]<<" ";
                cout<<"]"<<endl;

            }
        else if (y==0)
            exit(0);

            else
               cout<<"Go To HeLL";

};

C++ exercise 2

2012-11-22T06:20:00.001+02:00

write a program that calculate (minimum, maximum and average) of 10 entered numbers

______________________________________________________

#include<iostream.h>
int main()
{
    int a[10],sum=0,max,min;
    float avg;
    cout<<"Enter the 10 numbers: ";
    for(int i=0;i<10;i++)
    {
        cin>>a[i];
        cout<<endl;
    }

    for(i=0;i<10;i++)
    {
        sum=a[i]+sum;
        avg= (float) sum/10;

    }
max=a[0];
min=a[0];

    cout<<"The average = "<<avg<<endl;
    for(i=0;i<9;i++)
    {
        for(i=0;i<9;i++)
        {
        if(a[i]>max)
        max=a[i];
        }

    }
    for(i=0;i<9;i++)
    {
        for(i=0;i<9;i++)
        {
        if(a[i]<min)
        min=a[i];
        }

    }
    cout<<"The max = "<<max<<endl<<"The min = "<<min<<endl;


          return 0;
}

C++ exercise 1

2012-11-22T05:54:00.002+02:00

Write a program that display a menu as following:

Press 1: to let user enter 2 numbers and print their
multiplication value
Press 2: to let user enter a range of 2 numbers and the program
will calculate the summation of all numbers in this Range.
Press 3: to let user enter many numbers until a negative value
entered then the program print the Maximum and Minimum
value entered.
Press 0: to Exit program.

________________________________________________________________________

#include<iostream.h>

#include <cstdlib> // included to use exit(0)

int main()

{

    int x,y,z,c,t;t=0;z=0;

    cout<<" 2Press 1: to enter 2 numbers and get their multiplication.\n " ;

    cout<<"Press 2: to enter range of 2 numbers and get summation of this range.\n ";

    cout<<"Press 3: to enter many numbers value and get thier Maximum and Minimum. \n ";

    cout<<"Press 0: to Exit program. \n ";



    cin>>x;

    if(x==1)

    {

        cout<<"Enter two No.\n2";

        cin>>y;

        cin>>z;

        c=y*z;

        cout<<endl<<c;

    }

        else if (x==2)

        {

            cout<<"Enter two numbers\n";

            cin>>y>>z;
            if(y<z)

            for(y;y<=z;y++)

            t=y+t;

            else
            for(y;y>=z;y--)

            t=y+t;

            cout<<t;

        }

        else if(x==3)

            {



            cin>>y;

            c=y;

            while(y>0)

              {

                  if(y>z)

                  z=y;

                  else if(y<c)

                      c=y;

                  cin>>y;

               }

            cout<<z<<endl<<c;

            }



        else if(x==0)

            exit(0);

        else

        cout<<"Go To Hell :D\n";

return 0;

}

C++: power calculating (function(

2012-11-21T00:15:00.003+02:00

#include<iostream.h>
int power(int x,int y)
{
   int k=x;
   if(y==0)
       return 1;
   else
       for(int i=1;i<y;++i)
           x=x*k;
       return x;
}
int main()
{
   int a,b,c;
   cout<<"enter the number:";
   cin>>a;
   cout<<"enter the power:";
   cin>>b;
   c=power(a,b);
   cout<<"the result is:"<<c<<endl;
   return 0;
}

C++: calculate power (function(

2012-11-20T09:48:00.002+02:00

C++: Greatest Common Divisor "GCD" (function)

2012-11-20T09:44:00.000+02:00

#include <iostream.h>

int GCD(int a, int b)

{

while( 1 )

{

a = a % b;

if( a == 0 )

return b;

b = b % a;

if( b == 0 )

return a;

}

int main()

{

int x, y;

cout << "This program allows calculating the GCD\n";

cout << "Value 1: ";

cin >> x;

cout << "Value 2: ";

cin >> y;

cout << "\nThe Greatest Common Divisor of "

<< x << " and " << y << " is " << GCD(x, y) << endl;

return 0;

}

C++: Finding area of a circle(function)

2012-11-20T09:34:00.001+02:00

#include<iostream.h>

float area(int x,float a )

{

a = (x*x)*(3.14);

return a;

}

int main()

{

float a,int x;

cout<<"enter x"<<endl;cin>>x;

a = (x*x)*(3.14);

cout<<"area="<<a;

return 0;

}

C++: Maximum of three numbers(function)

2012-11-20T09:31:00.000+02:00

#include<iostream.h>

int max(int x,int y ,int z)

{

if(x>y&&x>z) return x;

else if (y>x&&y>z)return y;

else if (z>x&&z>y)return z;

}

int main()

{

int x,y,z,m;

cout<<"enter x"<<endl;cin>>x;

cout<<"enter y"<<endl;cin>>y;

cout<<"enter z"<<endl;cin>>z;

m=max(x,y,z);

cout<<"Max is"<<m;

return 0;

}

C++: Maximum of two numbers(function)

2012-11-20T09:26:00.001+02:00

#include <iostream.h>

float greater(float, float);

int main()
{
   float a, b, c, d, e;
   cout<<"Enter the first number"<<endl<<"a=";
   cin>>a;
   cout<<endl<<"Enter the second number"<<endl<<"b=";
   cin>>b;
   cout<<endl<<"Enter the third number"<<endl<<"c=";
   cin>>c;
   d = greater(a,b);
   e = greater(d,c);
   cout<<e<<" is the greatest number"<<endl;

return 0;
}
float grater(float x, float y)
{
   if (x>y)
       return x;
   else
       return y;

}

C++: Maximum of three numbers

2012-11-20T09:23:00.001+02:00

#include <iostream.h>

int main()
{
   float a, b, c;
   cout<<"Enter the first number"<<endl<<"a=";
   cin>>a;
   cout<<endl<<"Enter the second number"<<endl<<"b=";
   cin>>b;
   cout<<endl<<"Enter the third number"<<endl<<"c=";
   cin>>c;
   if (a>b)
   {
       if (a>c)
           cout<<endl<<a<<" is the gratest"<<endl;
       else
           cout<<endl<<c<<" is the gratest"<<endl;
   }
   else
   {
       if (b>c)
           cout<<endl<<b<<" is the gratest"<<endl;
       else
           cout<<endl<<c<<" is the gratest"<<endl;
   }

return 0;
}

C++ classes: Priority Queue Minimum Heap

2012-11-16T21:38:00.000+02:00

____________________________________

First: Header file.h (functions prototype).

____________________________________

// File: PQ.h
// Priority Queue header file (Minimum Heap)
/* ______________________________________________________________________________
The PQ is implemented as a minimum Heap.
The elements of the heap are of type (E).
The top of the heap will contain the smallest element.
The heap condition is that a parent is always
less than or equal to the children.
The heap is implemented as a dynamic array a[] with a
size specified by the class constructor.
Location a[0] is reserved for a value "itemMin" smaller
than any possible value (e.g. a negative number)
_________________________________________________________________________________
*/

#ifndef PQ_H
#define PQ_H

template <class E>

class PQ
{
public:

   // Class Constructor with input size parameter
   PQ(int );
   // Class Destructor
   ~PQ();
   // Member Functions
   void insert(E );   // insert element into heap
   E remove();           // remove & return the top of the heap
   void dispHeap();   // Display Heap Array as a tree

   private:
   // Pointer to Storage Array
   E *a;
   // Maximum Size (not including a[0])
   int MaxSize;
   int N;                   // index of last element in the array
   E itemMin;               // itemMin to be stored in a[0]
   // Heap Adjustment Functions
   void upheap(int k);
   void downheap(int k);
   void disp_Level (int Nrows, int level, int s, int e);

};
#endif // PQ_H
#include "PQ.cpp"

________________________________________________

second: Implementation file.cpp

_____________________________________

// File:PQ.cpp
// PQ (min Heap) Class implementation
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

// Member Functions

// Constructor with argument. Max size is mVal elements
// not including a[0] which will receive -32767
// The constructor creates the heap array, initializes
// the end of the heap to N=0,and itmMin
template <class E>
PQ<E>::PQ(int mVal)
{
   MaxSize = mVal;
   a = new E[MaxSize+1];    N=0;
   itemMin = -32767; // Minimum Heap
   a[0] = itemMin ;
}
// Class Destructor
template <class E>
PQ<E>::~PQ()
{ delete [] a;}

// Heap Adjustment Functions
// upheap element at location (k) in the heap
// as long as it is less than the parent

template <class E>
void PQ<E>::upheap(int k)
{
   E v = a[k] ;
   while ( a[k/2] >= v)
       { a[k] = a[k/2] ;   k = k/2 ; }
   a[k] = v ;
}

// downheap element at (k) in the heap
template <class E>
void PQ<E>::downheap(int k)
{
   int j = 2 * k ;     E v = a[k] ;
   while (j <= N) {
       if ((j < N) && (a[j] > a[j+1])) j++ ;
       if ( v <= a[j] ) break;
       a[j/2] = a[j] ;     j *= 2 ;   }
   a[j/2] = v ;
}

// Insert element (v) in the heap and adjust heap
template <class E>
void PQ<E>::insert(E v)
{
   a[++N] = v ;    upheap(N) ;
}

// remove and return top of the heap, then adjust heap
template <class E>
E PQ<E>::remove()
{
   E v = a[1] ;
   a[1] = a[N--] ; downheap(1) ;
   return v;
}

template <class E>
void PQ<E>::dispHeap()
{
   int s = 1, e = 1, rlength, k,
       Nlevels = int(ceil(log(float(N))/log(2.0)+ 0.01));
   for (int level=0; level<Nlevels; level++)
   {
       disp_Level (Nlevels, level, s, e);
       rlength = e-s+1;
       s = e+1;
       k = e + 2*rlength;
       e = (k < N)? k : N;
   }
}

template <class E>
void PQ<E>::disp_Level (int Nrows, int level, int s, int e)
{
   int skip = int(pow(2.0, Nrows-level) - 1);
   for (int i = s; i <= e; i++)
   {
       cout << setw(skip) << " ";
       cout << setw(2) << a[i];
       cout << setw(skip) << " ";
   }
   cout << "\n\n\n";
}

________________________________________________

finally class test

_____________________________________

// FILE: HeapSortTest.cpp
// Heap Sorting of a random sequence of integers.
#include "PQ.h"
#include <time.h>
#include <conio.h>
#include <iostream>
using namespace std;

// ______________________________Globals __________________
const int Nmax = 200;       // Maximum number of elements

// Functions Prototype Definitions_________________________

// Swap element[i] with element[k]
void swap(int &, int &);
// Generate a random integer from (i) to (j)
int RandInt(int i,int j);
// Generate a random permutaion of the first N integers
void RandPerm(int X[], int N);
// Heapsort array X[] locations 1..N
void heapsort(int X[], int N);

//__________________________________________________________

int main()
{
   int X[Nmax+1];   // Array of random permutation of integers
   int i,N;
   cout<<"Input N: "; cin >> N;
   srand((unsigned)time(NULL));
   RandPerm(X,N);
   for(i=1; i<=N; i++) cout<<X[i] <<" ";
   cout<<endl;
   heapsort(X,N);
   for(i=1; i<=N; i++) cout<<X[i] <<" ";
   cout<<endl;
   _getch();
   return 0;
}

//Implementation of Functions________________________________
void swap(int &a, int &b)
{
   int t;
   t = a; a = b; b = t;
}

//____________________________________________________________
int RandInt(int i,int j)
{
   return (rand()%(j-i+1) + i);
}
//____________________________________________________________
void RandPerm(int X[], int s)
{
   int i,k;
   for(i=1;i<=s;i++) X[i] = i;
   for(i=2;i<=s;i++)
   {
       k = RandInt(1,i);
       swap(X[i],X[k]);
   }
}

//______________________________________________________________
void heapsort(int X[], int N)
{
   int i;
   PQ<int> Heap(N);
   for (i = 1; i <= N; i++) Heap.insert(X[i]);
   for (i = 1; i <= N; i++) X[i] = Heap.remove();
}

C++ classes: Minimum Heap

2012-11-16T21:33:00.000+02:00

____________________________________

First: Header file.h (functions prototype).

____________________________________

// File: MinHeap.h
// Heap Class header file (Minimum Heap for graph edges)
/* ________________________________________________________________________________________________
The following is a definition of a class for a Minimum Heap "MinHeap". The elements of the heap are
structs that model an edge in a non-directed weighted graph. Each edge is characterized by three
integers: (u,v,w). u is the index of a node, v is the index of the second node, and w is the weight
of the edge between u and v. The top of the heap will contain the edge with the minimum weight. The
heap condition is that a parent is always less than or equal to the children. The heap is implemented
as a dynamic array a[] with a size specified by the class constructor. Location a[0] is reserved to
contain a weight value "itemMin" smaller than any possible weight value (e.g. a negative number)
___________________________________________________________________________________________________
*/

#ifndef MINHEAP_H
#define MINHEAP_H
#include "Edge.h"
using namespace std;

class MinHeap
{
public:

    // Member Functions
    // Class Constructor with input size parameter
    MinHeap(int );
    // Class Destructor
    ~MinHeap();
    // Functions Prototype Definitions
    void insert(Edge e);            // insert edge into heap
    Edge remove();        // remove the top of the heap
   private:
    // Pointer to Storage Array
    Edge *a;
    // Maximum Size (not including a[0])
    int MaxSize;
    int N;                            // index of last element in the heap
    weightType itemMin;                // itemMin to be stored in a[0]
    // Heap Adjustment Functions
    void upheap(int k);
    void downheap(int k);

};
#endif // MINHEAP_H
#include "MinHeap.cpp"

________________________________________________

second: Implementation file.cpp

_____________________________________

// File:MinHeap.cpp
// Heape Class implementation file (Minimum heap for graph edges)

// Member Functions

// Constructor with argument. max size is mVal elements
// not including a[0] which will receive a weight -32767
// The constructor creates the heap array, initializes
// the end of the heap to N=0,and itmMin
MinHeap::MinHeap(int mVal)
{
    a = new Edge[mVal+1];     N=0;
    MaxSize = mVal; itemMin = -32767; // Minimum Heap
    a[0].w = itemMin ;
}
// Class Destructor
MinHeap::~MinHeap()
{ delete [] a;}

// Heap Adjustment Functions
// upheap element at location (k) in the heap
// as long as it is less than the parent

void MinHeap::upheap(int k)
{
    Edge e = a[k] ;
    while ( e <= a[k/2])
        { a[k] = a[k/2] ;   k = k/2 ; }
    a[k] = e ;
}

// downheap element at (k) in the heap
void MinHeap::downheap(int k)
{
    int j = 2 * k ;     Edge e = a[k] ;
    while (j <= N) {
        if ((j < N) && (a[j+1] < a[j])) j++ ;
        if ( e <= a[j] ) break;
        a[j/2] = a[j] ;     j *= 2 ;   }
    a[j/2] = e ;
}

// Insert (e) in a heap and adjust heap
void MinHeap::insert(Edge e)
{
    a[++N] = e ;    upheap(N) ;
}

// remove and return top of the heap, then adjust heap
Edge MinHeap::remove()
{
    Edge e = a[1] ;
    a[1] = a[N--] ; downheap(1) ;
    return e;
}

C++ classes: Linked list

2012-11-15T22:55:00.001+02:00

____________________________________

First: Header file.h (functions prototype).

____________________________________

// File: List.h
// Definition of Simple Linked List Template Class
#ifndef LIST_H
#define LIST_H

// Specification of the class

template <class keyType, class dataType>

class List
{
   public:

   // Member Functions
   // Create an empty List
   List();
   // Destroy List
   ~List();

   // Functions Prototype Definitions

   bool listIsEmpty() const;
   bool curIsEmpty() const;
   void toFirst();
   bool atFirst() const;
   void advance();
   void toEnd();
   bool atEnd() const;
   int listSize() const;
   void updateData(const dataType & );
   void retrieveData(dataType &) const;
   void insertFirst(const keyType &, const dataType & );
   void insertAfter(const keyType &, const dataType & );
   void insertBefore(const keyType &, const dataType & );
   void insertEnd(const keyType &, const dataType & );
   void deleteNode();
   void deleteFirst();
   void deleteEnd();
   void makeListEmpty();
   bool search(const keyType & );
   void orderInsert(const keyType &, const dataType & );
   void traverse();

private:
   // Node Class
       class node
       {
        public:
            keyType key;       // key
            dataType data;       // Data
            node *next;           // pointer to next node
        }; // end of class node declaration
       typedef node * NodePointer;

   // Pointers
   NodePointer head, cursor, prev;
};
#endif // LIST_H
#include "List.cpp"

________________________________________________

second: Implementation file.cpp

_____________________________________

// File:List.cpp
// Simple Linked List Class implementation file

#include <iostream>
using namespace std;

// Member Functions
// Class Constructor
template <class keyType, class dataType>
List<keyType, dataType>::List()
{
    head = NULL; cursor = NULL; prev = NULL;
}

// Class Destructor
template <class keyType, class dataType>
List<keyType, dataType>::~List()
{
    makeListEmpty();
}

// return True if list is empty
template <class keyType, class dataType>
bool List<keyType, dataType>::listIsEmpty() const
{
    return (head == NULL);
}

// return True if current position is empty
template <class keyType, class dataType>
bool List<keyType, dataType>::curIsEmpty() const
{
    return (cursor == NULL);
}

// to make the current node the first node; if list is empty,
// the current position is still empty
template <class keyType, class dataType>
void List<keyType, dataType>::toFirst()
{
    cursor = head; prev = NULL;
}

// to return True if the current node is the first node or
// if the list and the current position are both empty.
template <class keyType, class dataType>
bool List<keyType, dataType>::atFirst() const
{
    return (cursor == head);
}

// to advance to next node. Assume the current position
// is nonempty initially.
template <class keyType, class dataType>
void List<keyType, dataType>::advance()
{
    prev = cursor;
    cursor = cursor->next;
}

// to make the current node the tail node;
// if list is empty, the current position is still empty
template <class keyType, class dataType>
void List<keyType, dataType>::toEnd()
{
    toFirst();
    if (! listIsEmpty())
        while ( cursor->next != NULL) advance();
}

// to return True if the current node is the tail node or
// if the list and the current position are both empty.
template <class keyType, class dataType>
bool List<keyType, dataType>::atEnd() const
{
    if ( listIsEmpty()) return true;
        else if (curIsEmpty()) return false;
            else return (cursor->next == NULL);
}

// to return the size of the list
template <class keyType, class dataType>
int List<keyType, dataType>::listSize() const
{
    NodePointer q;     int count;
    q = head;    count = 0;
    while (q != NULL)
    {
        count++;     q = q->next;
    }
    return count;
}

// to update the data portion of the current node to contain el;
// assume the current position is nonempty.
template <class keyType, class dataType>
void List<keyType, dataType>::updateData(const dataType &d)
{
    cursor->data = d;
}

// to return the data in the current node;
// assume the current position is nonempty.
template <class keyType, class dataType>
void List<keyType, dataType>::retrieveData(dataType &d) const
{
    d = cursor->data;
}

// insert a node with data (el) at the head of the list;
// the new node becomes the current node.
template <class keyType, class dataType>
void List<keyType, dataType>::insertFirst(const keyType &k, const dataType &d )
{
    NodePointer pnew;
    pnew = new node;
    pnew->key = k; pnew->data = d;
    pnew->next = head;
    head = pnew;
    cursor = head;
    prev = NULL;
}

// insert a node with data (el) after the current node
// without changing the current position;
// assume the current position is nonempty in a non-empty list.
template <class keyType, class dataType>
void List<keyType, dataType>::insertAfter(const keyType &k, const dataType &d )
{
    NodePointer pnew;
    pnew = new node;
    pnew->key = k; pnew->data = d;
    pnew->next = cursor->next;
     cursor->next = pnew;
}

// insert a node with data (el) before the current node,
// current position becomes the new node.
template <class keyType, class dataType>
void List<keyType, dataType>::insertBefore(const keyType &k, const dataType &d )
{
    NodePointer pnew;
    pnew = new node;
    pnew->key = k; pnew->data = d;
    pnew->next = cursor;
    prev->next = pnew;
    cursor = pnew;
}

// insert a node with data (el) at the end of the list,
// current position becomes the new node.
template <class keyType, class dataType>
void List<keyType, dataType>::insertEnd(const keyType &k, const dataType &d )
{
    if (listIsEmpty()) insertFirst(k,d);
    else {toEnd(); insertAfter(k,d); }
}

// delete the current node and set the current position to the next node;
// if the current node is the last node initially, the current position becomes empty;
// assume the current position is nonempty initially.
template <class keyType, class dataType>
void List<keyType, dataType>::deleteNode()
{
    NodePointer q;
       if(! curIsEmpty())
    {            // current node is not empty
        if (atFirst())     // delete head node
           {    q = cursor;
            cursor = cursor->next;
            head = cursor;
              delete q;
        }

        else         // delete non-head node
           {    q = cursor;
            cursor = cursor->next;
            prev->next = cursor;
            delete q;
        }
   }
}

// delete the first node and set the current position to the next node;
// if it was initially the only node, the current position becomes empty;
// assume the current position is nonempty initially.
template <class keyType, class dataType>
void List<keyType, dataType>::deleteFirst()
{
    if(! listIsEmpty()) {toFirst(); deleteNode();}
}

// delete the last node and set the current position to empty;
// assume the current position is nonempty initially.
template <class keyType, class dataType>
void List<keyType, dataType>::deleteEnd()
{
    if(! listIsEmpty()) {toEnd(); deleteNode();}
}

// delete whole list
template <class keyType, class dataType>
void List<keyType, dataType>::makeListEmpty()
{
     toFirst();
     while (! listIsEmpty())
        deleteNode();
}

// search the list for the node with key part that matches (k).
// If found, set cursor to the node and return True,
// else return false and the current position becomes empty.
template <class keyType, class dataType>
bool List<keyType, dataType>::search(const keyType &k)
{
    bool found = false;
    toFirst();
    while ((! found) && (cursor != NULL))
        if (k == cursor->key) found = true;
            else advance();
    return found;
}

// insert a node in a position that maintains an ascending
// order of the key portion of the nodes.
template <class keyType, class dataType>
void List<keyType, dataType>::orderInsert(const keyType &k, const dataType &d)
{
    toFirst();
    while ((cursor != NULL) && (k > cursor->key))
        advance();
    if (prev == NULL) insertFirst(k,d);
        else insertBefore(k,d);
}

// traverse list to print key and data fields
template <class keyType, class dataType>
void List<keyType, dataType>::traverse()
{
    toFirst();
    while (! curIsEmpty())
    {
        cout << cursor->key << " " << cursor->data << endl;
        advance();
    }
}

________________________________________________

finally class test

_____________________________________

// File: ListAppl.cpp
// Applies List Class: Ordered linked list

#include <iostream>
#include <string>
using namespace std;
#include "List.h"

int main()
{
    List<char, int> clist;
    string s;
    char c;
    int i, count;
    bool keyfound;

    // Read a string
    cout << "Enter a string:" << endl;
    getline(cin,s);
    cout << s << endl;
    for (i = 0; i < s.length(); i++)
    {
        c = toupper(s.at(i));
        keyfound = clist.search(c);
        if (keyfound)
        {
            clist.retrieveData(count);
            count++;
            clist.updateData(count);
        }
        else clist.orderInsert(c,1);
    }

    clist.traverse();
    cout << clist.listSize() << endl;
    //clist.makeListEmpty();
    clist.~List();
    cout << clist.listSize() << endl;


    return 0;
}

C++ classes: Hash Table

2012-11-15T22:50:00.001+02:00

____________________________________

First: Header file.h (functions prototype).

____________________________________

// File: hashTable.h
// Definition of Hash Table Template Class
#ifndef HASH_TABLE_H
#define HASH_TABLE_H

// Specification of the class
template <class keyType, class dataType>

class hashTable
{
public:

    // Member Functions
    hashTable(int nelements = 11);        // Constructor
    ~hashTable();                        // Destructor

    // Functions Prototype Definitions

    void emptyTable(const keyType & );
    bool tableIsEmpty() const;
    bool tableIsFull() const;
    int occupancy() const;
    bool insert(const keyType &, const dataType & );
    bool search(const keyType & );
    //void remove();
    void updateData(const dataType & );
    void retrieveData(dataType &) const;
    void traverse() const;

private:

    // Slot Class
       class slot
       {
        public:
            keyType key;         // key
            dataType data;        // Data
        }; // end of class slot declaration

    slot *T;                            // Pointer to Storage Array
    int h;                                // Index to a slot
    int MaxSize, csize;                    // Maximum and Current Sizes
    keyType Empty;                        // empty symbol

    // Private Member function
    int hash(const keyType & ) const;
};
#endif // HASH_TABLE_H
#include "hashTable.cpp"

________________________________________________

second: Implementation file.cpp

_____________________________________

// File:hashTable.cpp
// hashTable Class implementation file

#include <iostream>
using namespace std;

// Constructor with argument, size is nelements, default is 11
template <class keyType, class dataType>
hashTable<keyType, dataType>::hashTable(int nelements)
{ MaxSize = nelements; T = new slot[MaxSize]; h = -1; csize = 0;}

// Destructor
template <class keyType, class dataType>
hashTable<keyType, dataType>::~hashTable()
{ delete [] T;}

// Empty all slots
template <class keyType, class dataType>
void hashTable<keyType, dataType>::emptyTable(const keyType &k)
{
    Empty = k;
    for(int i = 0; i < MaxSize; i++) T[i].key = Empty;
    h = -1; csize = 0;
}

// return True if table is empty
template <class keyType, class dataType>
bool hashTable<keyType, dataType>::tableIsEmpty() const
{
    return (csize == 0);
}

// return True if table is full
template <class keyType, class dataType>
bool hashTable<keyType, dataType>::tableIsFull() const
{
    return (csize == MaxSize);
}

// to return the current occupancy of the table
template <class keyType, class dataType>
int hashTable<keyType, dataType>::occupancy() const
{
    return csize;
}

// insert key and data at a hashed slot
template <class keyType, class dataType>
bool hashTable<keyType, dataType>::insert(const keyType &k, const dataType &d)
{
    if (!tableIsFull())
    {
        h = hash(k);
        while(T[h].key != Empty)
            h = (h+1) % MaxSize;
        T[h].key = k; T[h].data = d; csize++;
        return true;
    }
    else return false;
}

// Search the table for the slot that matches key.
// If found, return True, set current position to slot
template <class keyType, class dataType>
bool hashTable<keyType, dataType>::search(const keyType &k )
{

    if(!tableIsEmpty())
    {
        h = hash(k); int start = h;
        for ( ; ; )
        {
            if (T[h].key == Empty) return false;
            if (k == T[h].key) return true;
            h = (h+1) % MaxSize;
            if (h == start) return false;
        }
    }
    else return false;
}

/* Remove given key from (make deleted) current slot
template <class keyType, class dataType>
void hashTable<keyType, dataType>::remove()
{
    T[h].key = Deleted;
}
*/

// Update the data part of the current slot
template <class keyType, class dataType>
void hashTable<keyType, dataType>::updateData(const dataType &d )
{
    if ((h >=0)&&(h < MaxSize)) T[h].data = d;
}

// Retrieve the data part of the current slot
template <class keyType, class dataType>
void hashTable<keyType, dataType>::retrieveData(dataType &d) const
{
    if ((h >= 0)&&(h < MaxSize)) d = T[h].data;
        else d = T[0].data;
}

// Traverse whole table
template <class keyType, class dataType>
void hashTable<keyType, dataType>::traverse() const
{
    for(int i = 0; i < MaxSize; i++)
        cout << T[i].key << endl;
}

// Private Hashing Function
template <class keyType, class dataType>
int hashTable<keyType, dataType>::hash(const keyType &k ) const
{
    return (k % MaxSize);
}

________________________________________________

finally class test

_____________________________________

// File: hashtest.cpp
// Test class template hashTable
#include <iostream>
using namespace std;
#include "hashTable.h"

int main()
{
   const int N = 9;
   int A[N] = {55,35,66,76,59,48,84,70,54};
   int B[N] = {1,2,3,4,5,6,7,8,9};
   int e = -1;
   int x,d;
   hashTable<int, int> HT;
   cout << "Constructing empty Hash Table\n";
   HT.emptyTable(e);
   cout << "Table " << (HT.tableIsEmpty() ? "is" : "is not") << " empty\n";
   cout << "Traversing\n";
   HT.traverse();
   for(int i = 0; i<N; i++)
           if(HT.insert(A[i], B[i])) cout << A[i] <<" is inserted, occupancy = "
               << HT.occupancy() << endl;

   cout << "Table " << (HT.tableIsEmpty() ? "is" : "is not") << " empty\n";
   cout << "Traversing\n";
   HT.traverse();
   cout << "Searching\n";
   x = A[2];
   cout << x << (HT.search(x) ? " is" : " is not") << " found\n";
   cout << "Retrieving data part of " << x;
   HT.retrieveData(d); cout <<" = " << d;
   cout << endl;
   cout << "Updating\n";
   HT.updateData(99);
   cout << "Retrieving data part of " << x;
   HT.retrieveData(d); cout <<" = " << d;
   cout << endl;
   x = 123;
   cout << x << (HT.search(x) ? " is" : " is not") << " found\n";
   x = 70;
   cout << "Searching\n";
   cout << x << (HT.search(x) ? " is" : " is not") << " found\n";
   cout << "Retrieving data part of " << x;
   HT.retrieveData(d); cout <<" = " << d;
   cout << endl;
   cout << "Traversing\n";
   HT.traverse();
   x = 44;
   if(HT.insert(x, 10)) cout << x <<" is inserted, occupancy = "
               << HT.occupancy() << endl;
   cout << "Traversing\n";
   HT.traverse();
   return 0;
}

C++ classes: Simple String

2012-11-15T22:45:00.001+02:00

____________________________________

First: Header file.h (functions prototype).

____________________________________

// File simpleString.h
// Simple string class definition
#ifndef SIMPLESTRING_H
#define SIMPLESTRING_H

class simpleString
{
    public:
      // Member Functions
      // constructors
      simpleString();
    simpleString(int );

    // Destructor
    ~simpleString();

    // Function Prototype definition
    // Read a simple string
      void readString();

      // Display a simple string
      void writeString() const;

      // Retrieve the character at a specified position
      // Returns the character \0 if position is out of bounds
      char at(int) const;

    // Return the string length
      int getLength() const;

      // Return the string capacity
      int getCapacity() const;

      void getContents(char[]) const;

    private:
      // Data members (attributes)
    // maximum size
    int capacity;
    // pointer to storage array
      char *s;
    // current length
      int length;
};

#endif //SIMPLESTRING_H

________________________________________________

second: Implementation file.cpp

_____________________________________

// File simplestring.cpp
// Simple string class implementation

#include "simplestring.h"
#include <iostream>
using namespace std;

// Member Functions...
// constructors
// default constructor, capacity = 255
simpleString::simpleString()
{
    s = new char[255];
    capacity = 255; length = 0;
}

// Constructor with argument, capacity is mVal
simpleString::simpleString(int mVal)
{
    s = new char[mVal];
    capacity = mVal; length = 0;
}

// Class Destructor
simpleString::~simpleString()
{ delete [] s;}


// Read a simple string
void simpleString::readString()
{
   // Local data...
   char next;
   int pos = 0;

   cin.get(next);
   while ((next != '\n') && (pos < capacity))
   {
    // Insert next in array contents
      s[pos] = next;
      pos++;
      cin.get(next);
   }

   length = pos;
}

// Write a simple string
void simpleString::writeString() const
{
   for (int pos = 0; pos < length; pos++)
      cout << s[pos];
}

// Retrieve the character at a specified position
// Returns the character \0 if position is out
// of bounds
char simpleString::at(int pos) const
{
   // Local data
   const char nullcharacter = '\0';
   if ((pos < 0) || (pos >= length))
    {
        cerr << "position " <<    pos << " not defined." << endl;
        return nullcharacter;
    }
   else return s[pos];
}

// Return the string length
int simpleString::getLength() const
{
   return length;
}

// Return the string capacity
int simpleString::getCapacity() const
{
   return capacity;
}
void simpleString::getContents(char str[]) const
{
   for (int i = 0; i < length; i++)
      str[i] = s[i];
}

________________________________________________

finally class test

_____________________________________

// File: simpleStringTest.cpp
// Tests the simple string class

#include "simpleString.h"
#include "simpleString.cpp"
#include <iostream>

using namespace std;

int main()
{
    simpleString S1;
    simpleString S2(20);

    cout << S1.getCapacity() <<" "<<S1.getLength() << endl;
    cout << S2.getCapacity() <<" "<<S2.getLength() << endl;

    // Read in a string.
    cout << "Enter a string and press RETURN: ";
    S1.readString();

   // Display the string just read.
   cout << "The string read was: ";
   S1.writeString();
   cout << endl;

   // Display each character on a separate line.
   cout << "The characters in the string follow:" << endl;
   for (int pos = 0; pos < S1.getLength(); pos++)
       cout << S1.at(pos) << endl;


   return 0;
}

C++ classes: Sets

2012-11-15T22:39:00.002+02:00

____________________________________

First: Header file.h (functions prototype).

____________________________________

// File: Sets.h
// Definition of Disjoint Sets Class

#ifndef SETS_H
#define SETS_H

// Specification of the class
class Sets
{
   private:
        int *p, *c, n;
   public:
        Sets(int Size): n(Size)   // Constructor
        {
            p = new int[n+1]; c = new int[n+1];
            for (int i=0; i<=n; i++) {p[i] = -1; c[i] = 1;}
        }

        ~Sets()       // Destructor
        { delete [] p; delete [] c; }

        void SimpleUnion(int i, int j);
        int SimpleFind(int i);
        void dispSets() const;
};

#endif // SETS_H
#include "Sets.cpp"

________________________________________________

second: Implementation file.cpp

_____________________________________

// File: Sets.cpp
// Disjoint Sets class implementation

#include <iostream>
using namespace std;

// Make a union between set(i) and set(j)
   void Sets::SimpleUnion(int i, int j)
   {
       int sum = c[i] + c[j];
       if (c[i] > c[j]) {p[j] = i; c[i] = sum;   }
       else { p[i] = j; c[j] = sum;}
   }

// Find the parent set of subset(i)
   int Sets::SimpleFind(int i)
   {    while (p[i]>=0) i = p[i];
       return i;
   }

// Display parent array
   void Sets::dispSets() const
   {
       for (int i = 1; i<=n; i++)
           cout << i <<":"<<p[i]<<":"<<c[i]<<" ";
       cout << endl;
   }

________________________________________________

finally class test

_____________________________________

// File: SetsTest.cpp
// Test of class Sets
#include <iostream>
using namespace std;
#include "Sets.h"

int main() // Testing the Sets Class
{           // Union and find
   int i;
   Sets s(16);
   s.dispSets();
   s.SimpleUnion(7,1); s.SimpleUnion(8,1); s.SimpleUnion(9,1);
   s.SimpleUnion(2,5); s.SimpleUnion(10,5);
   s.SimpleUnion(4,3); s.SimpleUnion(6,3);
   s.dispSets();
   i = 1;
   cout << "parent set of " << i << " is " << s.SimpleFind(i) <<"\n";
   i = 4;
   cout << "parent set of " << i << " is " << s.SimpleFind(i) <<"\n";
   i = 10;
   cout << "parent set of " << i << " is " << s.SimpleFind(i) <<"\n";
   s.SimpleUnion(5,1);
   s.dispSets();
   i = 10;
   cout << "parent set of " << i << " is " << s.SimpleFind(i) <<"\n";

   return 0;
}

C++ classes: Queue (Using Dynamic array)

2012-11-15T22:29:00.001+02:00

____________________________________

First: Header file.h (functions prototype).

____________________________________

// File: Queuet.h
// Queue template class definition
// Dynamic array implementation
#ifndef QUEUET_H
#define QUEUET_H

template <class Type>

class Queuet
{
   public:

      Queuet(int nelements = 128);        // Constructor
    Queuet (const Queuet <Type> &);    // Copy Constructor
      ~Queuet();                        // Destructor

    // Member Functions
      void enqueue(Type );            // Add to rear
    void dequeue(Type &);            // Remove from front
    void queueFront(Type &) const;    // retrieve front
      bool queueIsEmpty() const;    // Test for Empty queue
      bool queueIsFull() const;        // Test for Full queue
    int queueLength() const;        // Queue Length

   private:
      Type *queue;                    // pointer to dynamic array
    int front, rear, count, MaxSize;

};

#endif // QUEUET_H
#include "Queuet.cpp"

________________________________________________

second: Implementation file.cpp

_____________________________________

// File: Queuet.cpp
// Queue template class implementation

#include <iostream>
using namespace std;

// Constructor with argument, size is nelements, default 128
template <class Type>
Queuet<Type>::Queuet(int nelements)
{ MaxSize = nelements; queue = new Type[MaxSize];
   front = 1; rear = 0; count = 0;
}

// Copy Constructor
template <class Type>
Queuet<Type>::Queuet (const Queuet<Type> &original)
:MaxSize(original.MaxSize), front(original.front), rear(original.rear), count(original.count)
    {
        queue = new Type[MaxSize];
        for (int i = 0; i < MaxSize; i++) queue[i] = original.queue[i];
    }

// Destructor
template <class Type>
Queuet<Type>::~Queuet()
{ delete [] queue;}

// Add to rear
template <class Type>
void Queuet<Type>::enqueue(Type v)
{
    if(queueIsFull()) cout << "Queue is Full" << endl;
    else
    {
        rear = (rear + 1) % MaxSize;
        queue[rear] = v; count++;
    }
}

// Remove from front
template <class Type>
void Queuet<Type>::dequeue(Type &v)
{
    if(queueIsEmpty()) cout << "Queue is Empty" << endl;
    else
    {
        v = queue[front];
        front = (front + 1) % MaxSize; count--;
    }
}

// Retrieve front without removing it
template <class Type>
void Queuet<Type>::queueFront(Type &v) const
{
    if(queueIsEmpty()) cout << "Queue is Empty" << endl;
        else     v = queue[front];
}

// Test for Empty queue
template <class Type>
bool Queuet<Type>::queueIsEmpty() const
{ return (count == 0); }

// Test for Full queue
template <class Type>
bool Queuet<Type>::queueIsFull() const
{ return (count == MaxSize); }

// Queue Length
template <class Type>
int Queuet<Type>::queueLength() const
{ return count; }

________________________________________________

finally class test

_____________________________________

// File: QueuetAppl.cpp
// Test if a string is a palindrome
#include <iostream>
#include <string>
using namespace std;
#include "Stackt.h"
#include "Queuet.h"
bool palindrome(string w);
int main()
{
    string w;
    cout << "Enter a string:" << endl;
    getline(cin,w); cout << w << endl;
    if (palindrome(w)) cout << "Palindrome" << endl;
        else cout << "NOT Palindrome" << endl;
    return 0;
}

bool palindrome(string w)
{
    Stackt<char> s;
    Queuet<char> q;
    int L = w.length();    char c,v;
    for (int i = 0; i < L; i++)
    { c = w.at(i); s.push(c); q.enqueue(c); }
    while(!q.queueIsEmpty())
    { q.dequeue(c); s.pop(v); if(c != v) return false; }
    return true;
}

____________________________________________

Another class test

___________________

// File: QueuetAppl2.cpp
// Passing a stack and a queue as reference parameters
#include <iostream>
#include <string>
using namespace std;
#include "Stackt.h"
#include "Queuet.h"
void fillqs(string ,Stackt<char> &,Queuet<char> &);
int main()
{
    string w;
    char c;
    Stackt<char> ST;
    Queuet<char> QU;
    cout << "Enter a string:" << endl;
    getline(cin,w); cout << w << endl;
    fillqs(w,ST,QU);
    while(!ST.stackIsEmpty())
        { ST.pop(c); cout << c; }
    cout<<endl;
    while(!QU.queueIsEmpty())
        { QU.dequeue(c); cout << c; }
    cout<< endl;
    return 0;
}

void fillqs(string w,Stackt<char> &s,Queuet<char> &q)
{
    int L = w.length();    char c;
    for (int i = 0; i < L; i++)
    { c = w.at(i); s.push(c); q.enqueue(c); }
}

C++ classes: BinaryTree

2012-11-15T22:23:00.001+02:00

____________________________________

First: Header file.h (functions prototype).

____________________________________

// FILE: binaryTree.h
// DEFINITION OF TEMPLATE CLASS BINARY SEARCH
// TREE

#ifndef BIN_TREE_H
#define BIN_TREE_H

// Specification of the class

template <class keyType, class dataType>

class binaryTree
{

   public:

      // Public Member functions ...
      // CREATE AN EMPTY TREE
      binaryTree();

      // INSERT AN ELEMENT INTO THE TREE
      bool insert (const keyType &, const dataType &);

      // CHECK IF THE TREE IS EMPTY
      bool empty() const;

      // SEARCH FOR A KEY IN THE TREE
      bool search (const keyType &) const;

    // RETRIEVE DATA FOR A GIVEN KEY
      bool retrieve (const keyType &, dataType &) const;

    // TRAVERSE A TREE
      void traverse() const;

    // Iterative Pre-order Traversal
    void preorder () const;

    // Iterative Level-order Traversal
    void levelorder () const;

    // GRAPHIC OUTPUT
      void graph() const;

    // REMOVE AN ELEMENT FROM THE TREE
      void remove (const keyType &);


   private:
      // Node Class
       class treeNode
       {
        public:
            keyType key;         // key
            dataType data;        // Data
            treeNode *left;        // left subtree
            treeNode *right;    // right subtree
       }; // end of class treeNode declaration
       typedef treeNode * NodePointer;
    // Data member ....
      NodePointer root;

      // Private Member functions ...

      // Searches a subtree for a key
      bool search2 (NodePointer , const keyType &) const;

      // Searches a subtree for a key and retrieves data
      bool retrieve2 (NodePointer , const keyType & , dataType &) const;

    // Inserts an item in a subtree
      bool insert2 (NodePointer &, const keyType &, const dataType &);

    // Traverses a subtree
      void traverse2 (NodePointer ) const;

    // Graphic output of a subtree
    void graph2 (int ,NodePointer ) const;

    // LOCATE A NODE CONTAINING ELEMENT AND ITS PARENT
      void parentSearch ( const keyType &k, bool &found,
                            NodePointer &locptr, NodePointer &parent) const;

};

#endif // BIN_TREE_H
#include "binaryTree.cpp"

________________________________________________

second: Implementation file.cpp

_____________________________________

// File: binaryTree.cpp
// Implementation of template class binary search tree
#include <iostream>
#include <iomanip>
#include "Stackt.h"
#include "Queuet.h"
using namespace std;

// Member functions ...

// constructor - create an empty tree
template <class keyType, class dataType>
binaryTree<keyType, dataType>::binaryTree()
{ root = NULL; }

//____________ Public search __________________
// Searches for the item with same key as k
// in a binary search tree.
// Pre : k is defined.
// Returns true if key is located,
//   otherwise, returns false.
template <class keyType, class dataType>
bool binaryTree<keyType, dataType>::search(const keyType &k) const
{
   return search2(root, k);
} // end of public search

//____________ Private search __________________
// Searches for the item with same key as k
// in the subtree pointed to by aRoot. Called
// by public search.
// Pre : k and aRoot are defined.
// Returns true if key is located,
// otherwise, returns false.
template <class keyType, class dataType>
bool binaryTree<keyType, dataType>::search2(NodePointer aRoot,
                                    const keyType &k)    const
{
    if (aRoot == NULL)
        return false;
    else if (k == aRoot->key)
        return true;
    else if (k < aRoot->key)
        return search2(aRoot->left, k);
    else
        return search2(aRoot->right, k);
} // end of private search
//____________ Public retrieve __________________
// Searches for the item with same key as k
// and retrieves data part if found
// Pre : k is defined.
// Returns true if key is located,
//   otherwise, returns false.
template <class keyType, class dataType>
bool binaryTree<keyType, dataType>::retrieve(const keyType &k,
                                             dataType &d) const
{
   return retrieve2(root, k, d);
} // end of public retrieve
//____________ Private retrieve __________________
// Searches for the item with same key as k
// in the subtree pointed to by aRoot and retrieves
// data part if key is found.Called by public retrieve.
// Pre : k and aRoot are defined.
// Returns true if key is located,
// otherwise, returns false.
template <class keyType, class dataType>
bool binaryTree<keyType, dataType>::retrieve2(NodePointer aRoot,
                                    const keyType &k,
                                    dataType &d)    const
{
    if (aRoot == NULL)
        return false;
    else if (k == aRoot->key)
    { d = aRoot->data; return true;}
    else if (k < aRoot->key)
        return retrieve2(aRoot->left, k, d);
    else
        return retrieve2(aRoot->right,k, d);
} // end of private retrieve

//____________ Public insert __________________
// Inserts element into a binary search tree.
// Pre : key k is defined.
// Post: Inserts element if k is not in the tree.
// Returns true if the insertion is performed.
// If there is a node with the same key value
// as k, returns false.
template <class keyType, class dataType>
bool binaryTree<keyType, dataType>::insert(const keyType &k, const dataType &d)
{
    return insert2 (root, k , d);
} // end of public insert

//____________ Private insert __________________
// Inserts element in the tree pointed to by
// aRoot.Called by public insert.
// Pre : aRoot k and d are defined.
// Post: If a node with same key as k is found,
// returns false. If an empty tree is reached,
// inserts element as a leaf node and returns true.
template <class keyType, class dataType>
bool binaryTree<keyType, dataType>::insert2(NodePointer &aRoot,
                                    const keyType &k, const dataType &d)
{

// Check for empty tree.
if (aRoot == NULL)
{ // Attach new node
    aRoot = new treeNode;
    aRoot->left = NULL;
    aRoot->right = NULL;
    aRoot->key = k;
    aRoot->data = d;
    return true;
}
else if (k == aRoot->key)
    return false;
else if (k < aRoot->key)
    return insert2 (aRoot->left, k, d);
else
    return insert2 (aRoot->right, k, d);
} // end of private insert

//____________ Public empty __________________
// Check if tree is empty
// Pre : none
// Post: Returns true if tree is empty, false
// otherwise
template <class keyType, class dataType>
bool binaryTree<keyType, dataType>::empty() const
{
   return(root == NULL);
} // end of empty

//____________ Public traverse__________________
// Traverses a binary search tree in key order.
// Pre : none
// Post: Each element of the tree is displayed.
// Elements are displayed in key order.
template <class keyType, class dataType>
void binaryTree<keyType, dataType>::traverse() const
{
   traverse2 (root);
} // end of public traverse

//____________ Private traverse__________________
// Traverses the binary search tree pointed to
// by aRoot in key order. Called by traverse.
// Pre : aRoot is defined.
// Post: displays each node in key order.
template <class keyType, class dataType>
void binaryTree<keyType, dataType>::traverse2 (NodePointer aRoot) const
{
   if (aRoot != NULL)
   { // recursive in-order traversal
     traverse2 (aRoot->left);
     cout << aRoot->key << " " << aRoot->data << endl;
     traverse2 (aRoot->right);
   }

} // end of private traverse

//____Public pre-order traversal (Iterative)______
template <class keyType, class dataType>
void binaryTree<keyType, dataType>::preorder () const
{
    Stackt<NodePointer> s;
    NodePointer t = root;
    s.push(t);
    while(!s.stackIsEmpty())
    {
        s.pop(t); cout << t->key << endl;
        if ( t->right != NULL ) s.push(t->right);
        if ( t->left != NULL ) s.push (t->left);
    }
}

//____Public Level-order traversal (Iterative)______
template <class keyType, class dataType>
void binaryTree<keyType, dataType>::levelorder () const
{
    Queuet<NodePointer> q;
    NodePointer t = root;
    q.enqueue(t);
    while(!q.queueIsEmpty())
    {
        q.dequeue(t); cout << t->key << endl;
        if ( t->left != NULL ) q.enqueue (t->left);
        if ( t->right != NULL ) q.enqueue (t->right);
    }
}

//____________ Public graph__________________
// Graphic output of a BST
// Pre : none
// Post: Graphical representation is displayed.
template <class keyType, class dataType>
void binaryTree<keyType, dataType>::graph() const
{
    graph2 (0 , root);
}// end of public graph

//____________ Private graph__________________
// Graphic output of a subtree pointed to by
// aRoot with indent spaces
// Pre : none
// Post: Graphical representation is displayed.
template <class keyType, class dataType>
void binaryTree<keyType, dataType>::graph2(int indent, NodePointer aRoot) const
{
    if (aRoot != NULL)
    { // recursive in-order traversal
      graph2 (indent+8, aRoot->right);
      cout << setw(indent) << " " << aRoot->key << endl;
      graph2 (indent+8, aRoot->left);
    }
}// end of private graph

//____________ Public remove __________________
// Remove an element from the binary search tree
// Pre : k is defined.
// Post: if k is present, its node will be
// removed and tree will be modified
template <class keyType, class dataType>
void binaryTree<keyType, dataType>::remove (const keyType &k)
{
    bool found;
    NodePointer x,parent;
    // Search for element and its parent
    parentSearch (k, found, x, parent);
    if (!found)
    {
        cout << "Item not in BST\n";
        return;
    }
    // else, element is found
    if ((x->left != NULL)&&(x->right != NULL))
    {    // Node has two children
        // Find inorder successor and its parent
        NodePointer xSucc = x->right;
        parent = x;
        while (xSucc->left != NULL) // descend left
        { parent = xSucc; xSucc = xSucc->left; }
        // Move contents of xSucc to x and change x
        // to point to successor, which will be removed
        x->key = xSucc->key; x->data = xSucc->data;
        x = xSucc;
    } // end if node has two children
    // Now, node has 0 or 1 child
    NodePointer subtree = x->left; // subtree of x
    if (subtree == NULL) subtree = x->right;
    if (parent == NULL) root = subtree; //remove root
    else if (parent->left == x) //parent left child
        parent->left = subtree;
    else parent->right = subtree; // right child
    delete x;
} // end of public remove

//____________ Private parentSearch __________________
// Locate a node containing key k and its parent
// Pre : none.
// Post: locptr points to node containing k
// or is NULL if not found, and parent points to
// its parent. Used by remove
template <class keyType, class dataType>
void binaryTree<keyType, dataType>::parentSearch (const keyType &k,
                                            bool &found,
                                            NodePointer &locptr,
                                               NodePointer &parent) const
{
    locptr = root; parent = NULL; found = false;
    while (!found && locptr != NULL)
    {
        if (k < locptr->key) // descend left
        {
            parent = locptr;    locptr = locptr->left;
        }
        else if (locptr->key < k) // descend right
        {
            parent = locptr;    locptr = locptr->right;
        }
        else found = true; // el found
    }// end while
} // end of private parentSearch

C++ classes: Queue (Using linked list)

2012-11-15T21:57:00.002+02:00

____________________________________

First: Header file.h (functions prototype).

____________________________________

// File: QueueL.h
// Linked List Queue class definition
#ifndef QUEUEL_H
#define QUEUEL_H

template <class Type>

class QueueL
{
   public:


      QueueL();                        // Constructor
    ~QueueL();                    // Destructor
      void enqueue(Type );            // Add to rear
    void dequeue(Type &);            // Remove from front
    void queueFront(Type &) const;    // retrieve front
      bool queueIsEmpty() const;    // Test for Empty queue
    int queueLength() const;        // Queue Length

   private:
    // Node Class
       class node
       {
        public:
            Type e;                    // queue element
            node *next;                // pointer to next node
        }; // end of class node declaration
    typedef node * NodePointer;

    NodePointer front , rear;        // Pointers
    int count;                        // length

};

#endif // QUEUEL_H
#include "QueueL.cpp"

________________________________________________

second: Implementation file.cpp

_____________________________________

// File:QueueL.cpp
// Linked List Queue Class implementation
#include <iostream>
using namespace std;

// Class Constructor
template <class Type>
QueueL<Type>::QueueL()
{
    front = NULL; rear = NULL; count = 0;
}

// Class Destructor
template <class Type>
QueueL<Type>::~QueueL()
{
    NodePointer cursor;
    while(front != NULL)
    {
        cursor = front;
        front = front->next;
        delete cursor;
    }
}

// Add a node with data (v) at the rear of the queue;
// the new node becomes the rear node.
template <class Type>
void QueueL<Type>::enqueue(Type v)
{
    NodePointer pnew = new node;
    pnew->e = v; pnew->next = NULL;
    if(queueIsEmpty())
    { front = pnew; rear = pnew;}
    else
    { rear->next = pnew; rear = pnew; }
    count++;
}

// dequeue front node. Next node becomes front node.
template <class Type>
void QueueL<Type>::dequeue(Type &v)
{
    NodePointer cursor;
    if(queueIsEmpty()) cout << "Queue is Empty" << endl;
    else
    {
            v = front->e;
            cursor = front;
            front = front->next;
            delete cursor; count--;
    }
}

// Retrieve front node without removing it
template <class Type>
void QueueL<Type>::queueFront(Type &v) const
{
    NodePointer cursor;
    if(queueIsEmpty()) cout << "Queue is Empty" << endl;
    else { v = front->e; }
}

// return True if queue is empty
template <class Type>
bool QueueL<Type>::queueIsEmpty() const
{
    return (count == 0);
}

// Queue Length
template <class Type>
int QueueL<Type>::queueLength() const
{ return count; }
________________________________________________

finally class test

_____________________________________

// File: QueueLAppl.cpp
// Applies Linked List Queue Class to a string
#include <iostream>
#include <string>
using namespace std;
#include "QueueL.h"

int main()
{
    QueueL<char> q;
    string instring, outstring;
    char c;
    int i;
    cout << q.queueLength() << endl;
    // Read a string
    cout << "Enter a string:" << endl;
    getline(cin,instring);
    cout << instring << endl;
    outstring = "";
    for (i = 0; i < instring.length(); i++)
    {
        c = instring.at(i);
        q.enqueue(toupper(c));
    }
    cout << q.queueLength() << endl;
    while(!q.queueIsEmpty())
    {
        q.dequeue(c);
        outstring = outstring + c;
    }
    cout << outstring << endl;
    cout << q.queueLength() << endl;

    return 0;
}

C++ classes: Time

2012-11-15T21:38:00.001+02:00

____________________________________

First: Header file.h (functions prototype).

____________________________________

//File: Time.h Time Class Header File
#ifndef TIME_H    // used to avoid multiple definitions
#define TIME_H    // not part of the class
class Time
{
    public:
        Time();        // constructor
        ~Time();     // destructor
        // Function prototypes
        void setTime(int, int, int );
        void displayTime() const;
    private:
        int hour, minute, second;
}; // a semicolon must appear here
#endif // TIME_H

________________________________________________

second: Implementation file.cpp

_____________________________________

//File: Time.cpp Time Class Implementation File
#include "Time.h"
#include <iostream>
using namespace std;

Time::Time()
{    hour = minute = second = 0; }

Time::~Time()
{ }

void Time::setTime(int h, int m, int s)
{
     hour   = (h >= 0 && h < 24) ? h : 0;
     minute = (m >= 0 && m < 60) ? m : 0;
     second = (s >= 0 && s < 60) ? s : 0;
}

void Time::displayTime() const
{ cout << hour << ":" << minute << ":" << second << endl; }

________________________________________________

finally class test

_____________________________________

//File: TimeAppl.cpp Time Class Application File
#include "Time.h"
#include "Time.cpp"
#include <iostream>
using namespace std;
int main()
{
    Time t1 , t2;
    cout << "Start Time is: ";     t1.displayTime();
    t2.setTime(5, 10, 30);
    cout << "End Time is: ";    t2.displayTime();
    return 0;
}

C++ classes: stack(Using dynamic array)

2012-11-15T21:23:00.001+02:00

____________________________________

First: Header file.h (functions prototype).

____________________________________

// File: Stackt.h
// Stack template class definition.
// Dynamic array implementation

#ifndef STACKT_H
#define STACKT_H

template <class Type>

class Stackt
{
   public:

      Stackt(int nelements = 128);        // Constructor
    Stackt (const Stackt<Type> &);    // Copy Constructor
    ~Stackt();                        // Destructor

    // Member Functions
      void push(Type );                // Push
      void pop(Type &);                // Pop
    void stackTop(Type &) const;    // retrieve top
      bool stackIsEmpty() const;    // Test for Empty stack
      bool stackIsFull() const;        // Test for Full stack

   private:
      Type *stack;                    // pointer to dynamic array
    int top, MaxSize;

};

#endif // STACKT_H
#include "Stackt.cpp"

________________________________________________

second: Implementation file.cpp

_____________________________________

// File: Stackt.cpp
// Stack template class implementation

#include <iostream>
using namespace std;

// Constructor with argument, size is nelements, default is 128
template <class Type>
Stackt<Type>::Stackt(int nelements)
{ MaxSize = nelements; stack = new Type[MaxSize]; top = -1; }

// Copy Constructor
template <class Type>
Stackt <Type>::Stackt(const Stackt<Type> &original)
    :MaxSize(original.MaxSize), top(original.top)
{
    stack = new Type[MaxSize];
    for (int i = 0; i <= top; i++) stack[i] = original.stack[i];
}

// Destructor
template <class Type>
Stackt<Type>::~Stackt()
{ delete [] stack;}

// Push
template <class Type>
void Stackt<Type>::push(Type v)
{
    if(stackIsFull()) cout << "Stack Overflow" << endl;
    else stack[++top] = v;
}

// Pop
template <class Type>
void Stackt<Type>::pop(Type &v)
{
    if(stackIsEmpty()) cout << "Stack Underflow" << endl;
    else v = stack[top--];
}

// Retrieve stack top without removing it
template <class Type>
void Stackt<Type>::stackTop(Type &v) const
{
    if(stackIsEmpty()) cout << "Stack Underflow";
    else v = stack[top];
}

// Test for Empty stack
template <class Type>
bool Stackt<Type>::stackIsEmpty() const
{ return (top < 0); }

// Test for Full stack
template <class Type>
bool Stackt<Type>::stackIsFull() const
{ return (top >= (MaxSize-1)); }

________________________________________________

finally class test

_____________________________________

   // File: StacktAppl.cpp
// Applies Stack template Class to reverse a string
#include <iostream>
#include <string>
using namespace std;
#include "Stackt.h"

int main() // Testing he Stackt Class
{            // Reverse a string and stack copy

    Stackt<char> s1;
    char c;
    string instring = "Testing Stack Class";
    string outstring = "";    cout << instring << endl;
    int L = instring.length();
    cout << "Pushing characters on s1\n";
    for (int i = 0; i < L; i++) s1.push(instring.at(i));
    cout << "Copying s1 to s2\n";
    Stackt<char> s2 = s1;
    cout << "Popping characters from s1\n";
    while(!s1.stackIsEmpty())
    { s1.pop(c); outstring = outstring + c;}
    cout << outstring << endl;
    cout <<"s1 is now empty. Trying to pop from empty s1\n";
    s1.pop(c);
    cout << "Now popping contents of s2" << endl;
    while(!s2.stackIsEmpty())
    { s2.pop(c); cout << c;    }
    cout<< endl;
    return 0;
}

C++ classes: Stack (using linked list)

2012-11-15T21:15:00.003+02:00

____________________________________

First: Header file.h (functions prototype).

____________________________________

// File: StackL.h
// Linked List Stack class definition
#ifndef STACKL_H
#define STACKL_H

template <class Type>

class StackL
{
   public:

      StackL();                        // Constructor
    ~StackL();                    // Destructor
      void push(Type );                // Push
    void pop(Type &);                // Pop
    void stackTop(Type &) const;    // retrieve top
      bool stackIsEmpty() const;    // Test for Empty stack

   private:

    // Node Class
       class node
       {
        public:
            Type e;                    // stack element
            node *next;                // pointer to next node
        }; // end of class node declaration

    typedef node * NodePointer;

    NodePointer top;                // pointer to top
};
#endif // STACKL_H
#include "StackL.cpp"

________________________________________________

second: Implementation file.cpp

_____________________________________

// File:StackL.cpp
// Linked List Stack Class implementation

#include <iostream>
using namespace std;

// Class Constructor
template <class Type>
StackL<Type>::StackL()
{ top = NULL; }

// Class Destructor
template <class Type>
StackL<Type>::~StackL()
{    NodePointer cursor;
    while(top != NULL)
    {     cursor = top;    top = top->next;
        delete cursor;     }
}

// return True if stack is empty
template <class Type>
bool StackL<Type>::stackIsEmpty() const
{ return (top == NULL);}

// push a node with data (v) at the top of the stack;
// the new node becomes the top node.
template <class Type>
void StackL<Type>::push(Type v)
{     NodePointer pnew = new node ;
    pnew->e = v; pnew->next = top; top = pnew; }

// Pop top node. Next node becomes top node.
template <class Type>
void StackL<Type>::pop(Type &v)
{    NodePointer cursor;
    if(stackIsEmpty()) cout << "Stack Underflow" << endl;
    else
    { v = top->e; cursor = top;
    top = top->next; delete cursor; }

}

// Retrieve top node without removing it
template <class Type>
void StackL<Type>::stackTop(Type &v) const
{    NodePointer cursor;
    if(stackIsEmpty()) cout << "Stack Underflow" << endl;
    else
    { v = top->e; }

}

________________________________________________

finally class test

_____________________________________

// File: StackLAppl.cpp
// Applies Linked List Stack Class to reverse a string
#include <iostream>
#include <string>
using namespace std;
#include "StackL.h"

int main()
{

    StackL<char> s;
    string instring, outstring;
    char c;
    int i;

    // Read a string
    cout << "Enter a string:" << endl;
    getline(cin,instring);
    cout << instring << endl;
    outstring = "";
    for (i = 0; i < instring.length(); i++)
    {
        c = instring.at(i);
        s.push(c);
    }
    while(!s.stackIsEmpty())
    {
        s.pop(c);
        outstring = outstring + c;
    }
    cout << outstring << endl;
    s.~StackL();
    return 0;
}

C++ classes: Rational

2012-11-15T20:57:00.001+02:00

____________________________________

First: Header file.h (functions prototype).

____________________________________

// File: Rational.h
// Rational class definition

#ifndef RATIONAL_H            // used to avoid multiple definitions
#define RATIONAL_H            //    not part of the class
class rational
{
   public:
    // Member functions
    // Constructors
    rational();            // Default Costructor
    rational(int);        // Initialize numerator with denom = 1
    rational(int, int);    // Initialize both numerator and denom.

    void setNum(int);    // Set numerator and denominator
    void setDenom(int);

    rational multiply(const rational &f);    // Multiply fractions
    rational divide(const rational &f);        // Divide fractions
    rational add(const rational &f);        // Add Fractions
    rational subtract(const rational &f);    // Subtract Fractions
    void readRational();                    // Read a fraction
    void displayRational() const;            // Display a fraction
    rational reduce() const;                // Reduce rational

    // Accessors
    int getNum() const;
    int getDenom() const;

    // Operator Style
    rational operator + (const rational &); // Add object to parameter
    bool operator == (const rational &);    // Test equality of object and parameter

   private:
    // Data members (attributes)
    int num;    // private data field
    int denom;    // private data field

};    // Note -- a class definition MUST end with a semicolon

#endif // RATIONAL_H

________________________________________________

second: Implementation file.cpp

_____________________________________

// File: Rational.cpp
// Rational class implementation

#include "rational.h"
#include <iostream>
using namespace std;

// Member functions
// Constructors
rational::rational()
{
   num = 0;
   denom = 0;
}

rational::rational(int n)
{
   num = n;
   denom = 1;
}

rational::rational(int n, int d)
{
   num = n;
   denom = d;
}

// Set numerator and denominator
void rational::setNum(int n)
{
   num = n;
}

void rational::setDenom(int d)
{
   denom = d;
}
// Multiply fractions
rational rational::multiply(const rational &f)
{
   rational temp(num * f.num, denom * f.denom);
   return temp;
}

// Divide fractions
rational rational::divide(const rational &f)
{
   rational temp(num * f.denom, denom * f.num);
   return temp;
}

// Add fractions
rational rational::add(const rational &f)
{
   rational temp(num * f.denom + f.num * denom,
                 denom * f.denom);
   return temp;
}

// Subtract Fractions
rational rational::subtract(const rational &f) {
   rational temp(num * f.denom - f.num * denom,
                 denom * f.denom);
   return temp;
}

// Read a fraction
void rational::readRational()
{
   char slash;       // storage for /
   do
   {
      cout << "Enter numerator / denominator: ";
      cin >> num >> slash >> denom;
   }
   while (slash != '/');
}

// Display a fraction
void rational::displayRational() const
{
   cout << num << '/' << denom;
}

// Reduce rational
rational rational::reduce() const
{
   int n,m,rem,gcd;

   // Get the two integers
   n = abs(num); m = abs(denom);
   while (n > 0)
   {
       rem = m % n;
       m = n;
       n = rem;
   }
   gcd = m;
   rational g(num/gcd,   denom/gcd);
   return g;
}

// Accessors
int rational::getNum() const
{
   return num;
}

int rational::getDenom() const
{
   return denom;
}

rational rational::operator + (const rational &f2)   // IN: right-operand
{
   rational temp(num * f2.denom + f2.num * denom,
                 denom * f2.denom);
   return temp;
}

bool rational::operator == (const rational &f)
{
   return(num == f.num && denom == f.denom);
}

________________________________________________

finally class test

_____________________________________

// File: RationalTest.cpp
// Tests the rational class

#include <iostream>
#include "rational.h"
#include "rational.cpp"
using namespace std;

int main()
{
    rational f1, f2;
    rational f3;

    // Read two rational numbers
    cout << "Enter 1st fraction:" << endl;
    f1.readRational();
    cout << "Enter 2nd fraction:" << endl;
    f2.readRational();

    // Fraction Arithmetic

    f3 = f1.multiply(f2);
    f1.displayRational(); cout << " * ";
    f2.displayRational(); cout << " = ";
    f3.displayRational();
    cout << " = ";
    f3 = f3.reduce();
    f3.displayRational(); cout << endl;

    f3 = f1.divide(f2);
    f1.displayRational(); cout << " / ";
    f2.displayRational(); cout << " = ";
    f3.displayRational();
    cout << " = ";
    f3 = f3.reduce();
    f3.displayRational(); cout << endl;

    f3 = f1.add(f2);
    f1.displayRational(); cout << " + ";
    f2.displayRational(); cout << " = ";
    f3.displayRational();
    cout << " = ";
    f3 = f3.reduce();
    f3.displayRational(); cout << endl;

    f3 = f1 + f2;
    f1.displayRational(); cout << " + ";
    f2.displayRational(); cout << " = ";
    f3.displayRational();
    cout << " = ";
    f3 = f3.reduce();
    f3.displayRational(); cout << endl;

    f3 = f1.subtract(f2);
    f1.displayRational(); cout << " - ";
    f2.displayRational(); cout << " = ";
    f3.displayRational();
    cout << " = ";
    f3 = f3.reduce();
    f3.displayRational(); cout << endl;

    return 0;

}

First order DE: Homogeneous equations

2012-04-05T21:42:00.000+02:00

First order DE: Homogeneous equations

General form:

Example:

By taking x³ from the first part and the second part as a common factor.