Wednesday, November 30, 2011

C++ Tutorial: Class Templates

We also have the possibility to write class templates, so that a class can have members that use template parameters as types. For example:
template <class T>
class mypair {
    T values [2];
  public:
    mypair (T first, T second)
    {
      values[0]=first; values[1]=second;
    }
};

The class that we have just defined serves to store two elements of any valid type. For example, if we wanted to declare an object of this class to store two integer values of type int with the values 115 and 36 we would write:

mypair<int> myobject (115, 36); 

this same class would also be used to create an object to store any other type:

mypair<double> myfloats (3.0, 2.18); 

The following example further illustrates the concept of class templates. Here class Stack is a template class so it can be used for various data types like int, float , char etc.
#include<iostream>
using namespace std;

const int MAX = 20;
template <class T>
class Stack
{
    private:
        T arr[MAX];
        int top;
    public:
        Stack();
        void push(T data);
        T pop();
        int size();
};
template <class T>
Stack<T>::Stack()
{
    top =-1;
}

template <class T>
void Stack<T>::push(T data){
    arr[++top] = data;}

template <class T>
T Stack<T>::pop()
{
    return arr[top --];
}

template <class T>
int Stack<T>::size()
{
    return (top +1);
}

int main()
{
    cout<<"Stack for integer data type "<<endl;
    Stack <int>s1;
    cout<<"Size of stack "<<s1.size()<<endl;
    s1.push(11);
    s1.push(22);
    s1.push(44);

    cout<<"Size of stack: "<<s1.size()<<endl;
    cout<<"Number Popped: "<<s1.pop()<<endl;

    cout<<"Size of Stack: "<<s1.size()<<endl;
    return 0;
}





C++ Tutorial: Function Templates

Function Templates
Function templates are used to reduce the repeated code. I want to make you clear about function templates by giving a small example here. Functions abs() and fabs() are used to find the absolute value or non-negative value of a integer and floating point variable respectively. To calculate the absolute value of integer and floating point variable, we need to call two different functions. And they are defined differently with almost same code except for data types. In case of function call, if we want absolute value of –2 then we need to call abs() function and to calculate the value of –6.6 we need to call fabs() function and function definition for both of them must be different. This shows that there is redundancy in coding for both function call and function definition. One important question arises here and that is “Can I use only one function call and only one function definition to calculate absolute value of both integer and floating point??”. The simple answer for this question is YES you can by the use of function template. Note that: only one function call can be made to call both the function by using function overloading but the problem of different function definition is still unsolved. Let us explore this idea by considering another example with source code:
#include <iostream>

using namespace std;

int find_max(int a, int b){
    int result;
    if(a > b)
        result = a;
    else
        result = b;
}

float find_max(float a, float b){
    float result;
    if(a > b)
        result = a;
    else
        result = b;
    return result;
}

int main(){
    int a = 5, b = 6;
    float x = 2.7, y = 9.3;
    cout<<"The greater between a and b is "<<find_max(a,b)<<endl;
    cout<<"The greater between x and y is "<<find_max(x,y);
    return 0;
}




In above example although same function call find_max() is used to call both integer and floating point, two different function definitions must be written in order call functions. So by the use of function template you can avoid this problem.
#include <iostream>

using namespace std;

template <class T>

T find_max(T a, T b){
    T result;
    if(a > b)
        result = a;
    else
        result = b;
    return result;
}

int main(){
    int a = 5, b = 6;
    float x = 2.7, y = 9.3;
    cout<<"The greater between a and b is "<<find_max(a,b)<<endl;
    cout<<"The greater between x and y is "<<find_max(x,y);
    return 0;
}

Tuesday, November 29, 2011

C++ Tutorial: Templates

C++ Template is one of the most sophisticated, flexible and powerful feature. It was not the original feature of C++ as it was added later  on. The older versions of compilers do not support this feature.  Templates support generic programming, allowing development of reusable software components with functions and classes, supporting deferent data types in a single framework.
In C++, templates allow a type as a parameter in the definition of a function or a class. For example, if the same operation is to be performed with different data types then we need to write the same code for the different data types.This causes redundant code in the program with only difference in data type. For example, if we need to write functions for swap or sort that support different data types then we need to make functions for all different data types. Similarly, if we need to make a vector class that supports different data types, then we need to make classes each data type. But with the template mechanism, we can make a single sort or swap function that takes type as a parameter. The template declared for function are called function templates and those declared for classes are called class templates.

Binary tree Implementation on C++ – Algorithm and Source Code

Algorithm for inserting a node in a binary tree:

1. Declare and initialize necessary variables
2. Read the data item to be inserted in the tree say x.
3. Create a new node with its left and right pointers to null.
4. Assign data x to info field of new node.
5. If (tree == NULL)
then tree = address of new node
else if (x < tree -> info)
if(tree->left == NULL)
then tree->left = new node
else
tree = tree->left
repeat step 5.
else if(x>tree->info)
if(tree->right == NULL)
then tree->right = new node
else
tree = tree->right
repeat step 5
else if(x == tree->info)
print "Duplicated data" and exit
6. For next insertion, goto step 5.



Deletion Algorithm

1. Declare and initialize necessary variable
2. Read data to be deleted say x.
3. Find th enode where data is exist.
if node is not found
print "node not found" and exit
4. If the node has no subtree
* then assign the father node's pointer with null that points to the node
* delete the node that contains data item.
5. If the node has to be deleted has only one subtree
* move its son up, to take its place
* delete the node that contains data item
6. If the node has to be deleted has two subtrees
* set the information of node to be deleted by the information of leftmost node of rightmost subtree of the node to be deleted
7. For next deletion, goto step 2



Source Code for Insertion , Deletion, inorder, preorder and postorder tree traversal

#include<iostream>
#include<cstdlib>
using namespace std;
struct tree{
    int info;
    tree *Left, *Right;
};
tree *root;
class Binary_tree{
    public:
        Binary_tree();
        void insert1(int);
        tree *insert2(tree *, tree *);
        void Delete(int);
        void pretrav(tree *);
        void intrav(tree *);
        void posttrav(tree *);
};
Binary_tree::Binary_tree(){
    root = NULL;
}
tree* Binary_tree::insert2(tree *temp,tree *newnode){
    if(temp==NULL){
        temp=newnode;
    }
    else if(temp->info < newnode->info){
        insert2(temp->Right,newnode);
        if(temp->Right==NULL)
            temp->Right=newnode;
    }
    else{
        insert2(temp->Left,newnode);
        if(temp->Left==NULL)
            temp->Left=newnode;
    }
    return temp;
}
void Binary_tree::insert1(int n){
    tree *temp=root,*newnode;
    newnode=new tree;
    newnode->Left=NULL;
    newnode->Right=NULL;
    newnode->info=n;
    root=insert2(temp,newnode);
}
void Binary_tree::pretrav(tree *t = root){
    if(root == NULL){
        cout<<"Nothing to display";
    }else
    if(t != NULL){
        cout<<t->info<<" ";
        pretrav(t->Left);
        pretrav(t->Right);
    }
}
void Binary_tree::intrav(tree *t = root){
    if(root==NULL){
        cout<<"Nothing to display";
    }else
    if(t!=NULL){
        intrav(t->Left);
        cout<<t->info<<" ";
        intrav(t->Right);
    }
}
void Binary_tree::posttrav(tree *t = root){
    if(root==NULL){
        cout<<"Nothing to display";
    }else
        if(t!=NULL){
        posttrav(t->Left);
        posttrav(t->Right);
        cout<<t->info<<" ";
    }
}
void Binary_tree::Delete(int key)
{
    tree *temp = root,*parent = root, *marker;
    if(temp==NULL)
        cout<<"The tree is empty"<<endl;
    else{
        while(temp!=NULL && temp->info!=key){
            parent=temp;
            if(temp->info<key){
                temp=temp->Right;
            }else{
                temp=temp->Left;
            }
        }
    }
    marker=temp;
    if(temp==NULL)
        cout<<"No node present";
    else if(temp==root){
        if(temp->Right==NULL && temp->Left==NULL){
            root=NULL;
        }
        else if(temp->Left==NULL){
            root=temp->Right;
        }
        else if(temp->Right==NULL){
            root=temp->Left;
        }
        else{
            tree *temp1;
            temp1 = temp->Right;
            while(temp1->Left!=NULL){
                temp=temp1;
                temp1=temp1->Left;
            }
            if(temp1!=temp->Right){
                temp->Left=temp1->Right;
                temp1->Right=root->Right;
            }
            temp1->Left=root->Left;
            root=temp1;
        }
    }
    else{
        if(temp->Right==NULL && temp->Left==NULL){
            if(parent->Right==temp)
                parent->Right=NULL;
            else
                parent->Left=NULL;
        }
        else if(temp->Left==NULL){
            if(parent->Right==temp)
                parent->Right=temp->Right;
            else
                parent->Left=temp->Right;
        }
        else if(temp->Right==NULL){
            if(parent->Right==temp)
                parent->Right=temp->Left;
            else
                parent->Left=temp->Left;
        }else{
            tree *temp1;
            parent=temp;
            temp1=temp->Right;
            while(temp1->Left!=NULL){
                parent=temp1;
                temp1=temp1->Left;
            }
            if(temp1!=temp->Right){
                temp->Left=temp1->Right;
                temp1->Right=parent->Right;
            }
            temp1->Left=parent->Left;
            parent=temp1;
        }
    }
    delete marker;
}
int main(){
    Binary_tree bt;
    int choice, n, key;
    while(1){
        cout<<"\n\t1. Insert\n\t2. Delete\n\t3. Preorder Traversal\n\t4. Inorder Treversal\n\t5. Postorder Traversal\n\t6. Exit"<<endl;
        cout<<"Enter your choice: ";
        cin>>choice;
        switch(choice){
            case 1:
                cout<<"Enter item: ";
                cin>>n;
                bt.insert1(n);
                break;
            case 2:
                cout<<"Enter element to delete: ";
                cin>>key;
                bt.Delete(key);
                break;
            case 3:
                cout<<endl;
                bt.pretrav();
                break;
            case 4:
                cout<<endl;
                bt.intrav();
                break;
            case 5:
                cout<<endl;
                bt.posttrav();
                break;
            case 6:
                exit(0);
        }
    }
    return 0;
}

Sunday, November 27, 2011

Binary Tree and Operations on Binary Tree

Tree is a non linear data structure which consists of non-empty set of vertices ( or nodes ) and a set of edges where each nodes are connected to each other with no multiple edges or loops (i.e. no simple circuits)

A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the root and other two are left and right sub trees which can be also empty. Each element of binary tree is called node of the tree. OR, a rooted tree is called binary tree if every internal vertex has no more than two children. Btree2

In figure,

  • A is father of B & C
  • B is left son of A & C is right son of A
  • Two nodes are brothers, if they are left and right son of the same father.
  • Direction from root to leaves is “down” and reverse is “up”. It grows downward not like that of natural tree.

Operations on Binary tree

There are number of primitive operations that can be applied to a binary tree. If p is a pointer to a node nd of  a binary tree, then

  • info(p) returns contents of node nd.
  • Functions left(p), right(p), father(p) and brother(p) returns pointers to the left son, right son, father and brother of node nd respectively.
  • logical functions isleft(p) and isright(p) returns value true if node nd is left or right son respectively otherwise returns false.
  • maketree(x) creates  a new binary tree consisting of single node with information field x and returns a pointer to that node.
  • setleft(p,x) crrates a new left son of node(p) with information field x.

Saturday, November 26, 2011

C++ Tutorial: Standard Manipulators

It is seen that for formatted input/output the stream class ios function are used. To call ios function for formatting, we need to write separate statement and call the function through stream objects cin and cout. Manipulators are the formatting function for input/output that are embedded directly into the C++ input/output statements so that extra statements are not required. Manipulators are used along with the extraction >> and insertion << operators for stream input and output formatting. According to the number of arguments to be supplied manipulators are categorized in the  following types.
  1. Non-parameterized Manipulators
  2. Parameterized Manipulators
Non parameterized Manipulators do no take argument to control the formatting of input/output where as parameterized manipulators take argument for formatting. The Following table shows different non parameterized manipulators.
Manipulator Effect produced
left sets ios::left flag of ios::adjustfield
right sets ios::right flag of ios::adjustfield
internal sets ios::internal flag of ios::adjustfield
dec sets ios::dec flag of ios::adjustfield
hex sets ios::hex flag of ios::adjustfield
oct sets ios::oct flag of ios::adjustfield
scientific sets ios::scientific flag of ios::floatfield
fixed sets ios::fixed flag of ios::floatfield
showbase sets ios::showbase flag
noshowbase resets ios::showbase flag
showpoint sets ios::showpoint flag
noshowpoint resets ios::showpoint flag
showpos sets ios::showpos flag
noshowpos resets ios::showpos flag
uppercase sets ios::uppercase flag
nouppercase resets ios::uppercase flag
skipws sets ios::skipws flag
noskipws resets ios::skipws flag
boolalpha sets ios::boolalpha flag
noboolalpha resets ios::boolalpha flag
unitbuf sets ios::unitbuf flag
nounitbuf resets ios::unitbuf flag
endl output newline and flush
ends ouput ‘\0’ character
flush flush the stream, same as ostream::flush
ws removes all white space from input stream until non white space character.
Following table shows different parameterized manipulators
Manipulators Effect produced
setw(int n) equivalent to ios function width()
setprecision (int n) equivalent to ios function precision()
setfill(int c) equivalent to ios::function fill()
setbase (int b) sets base for integer output, argument 0 is passed for decimal, 8 or octal, 10 for decimal and 16 for hexadecimal.
setiosflags(ios::fmtflags f) equivalent to ios function setf()
resetiosflags(ios::fmtflags f) equivalent to ios function unsetf()

Mini project Banking Record System in C++

Mini project Banking Record System is a simple database project in C++. It is done using file handling mechanism in C++. The record of the customer can be added, updated, searched and deleted. It is simple project made using console application of C++. This means, no graphics component are added. The main target user of this project are the C++ beginners who want to make the project in C++ and especially those who are interested in File handling. This projects is complete package to learn how to use file as database. The complete source code for the project is given below:
/**********************************************************************************
    Program Name : Banking Record System
    Language Used : C++
    by Bibek Subedi
    Tribhuvan University, Nepal
***********************************************************************************/


#include<iostream>
#include<fstream>
#include<cstdlib>

using std::cout;
using std::cin;
using std::endl;
using std::fstream;
using std::ofstream;
using std::ifstream;
using std::ios;

class account_query
{
    private:
        char account_number[20];
        char firstName[10];
        char lastName[10];
        float total_Balance;
    public:
        void read_data();
        void show_data();
        void write_rec();
        void read_rec();
        void search_rec();
        void edit_rec();
        void delete_rec();

};

void account_query::read_data()
{
    cout<<"\nEnter Account Number: ";
    cin>>account_number;
    cout<<"Enter First Name: ";
    cin>>firstName;
    cout<<"Enter Last Name: ";
    cin>>lastName;
    cout<<"Enter Balance: ";
    cin>>total_Balance;
    cout<<endl;
}

void account_query::show_data()
{
    cout<<"Account Number: "<<account_number<<endl;
    cout<<"First Name: "<<firstName<<endl;
    cout<<"Last Name: "<<lastName<<endl;
    cout<<"Current Balance: Rs.  "<<total_Balance<<endl;
    cout<<"-------------------------------"<<endl;
}

void account_query::write_rec()
{
    ofstream outfile;
    outfile.open("record.bank", ios::binary|ios::app);
    read_data();
    outfile.write(reinterpret_cast<char *>(this), sizeof(*this));
    outfile.close();
}

void account_query::read_rec()
{
    ifstream infile;
    infile.open("record.bank", ios::binary);
    if(!infile)
    {
        cout<<"Error in Opening! File Not Found!!"<<endl;
        return;
    }
    cout<<"\n****Data from file****"<<endl;
    while(!infile.eof())
    {
        if(infile.read(reinterpret_cast<char*>(this), sizeof(*this))>0)
        {
            show_data();
        }
    }
    infile.close();
}

void account_query::search_rec()
{
    int n;
    ifstream infile;
    infile.open("record.bank", ios::binary);
    if(!infile)
    {
        cout<<"\nError in opening! File Not Found!!"<<endl;
        return;
    }
    infile.seekg(0,ios::end);
    int count = infile.tellg()/sizeof(*this);
    cout<<"\n There are "<<count<<" record in the file";
    cout<<"\n Enter Record Number to Search: ";
    cin>>n;
    infile.seekg((n-1)*sizeof(*this));
    infile.read(reinterpret_cast<char*>(this), sizeof(*this));
    show_data();
}

void account_query::edit_rec()
{
    int n;
    fstream iofile;
    iofile.open("record.bank", ios::in|ios::binary);
    if(!iofile)
    {
        cout<<"\nError in opening! File Not Found!!"<<endl;
        return;
    }
    iofile.seekg(0, ios::end);
    int count = iofile.tellg()/sizeof(*this);
    cout<<"\n There are "<<count<<" record in the file";
    cout<<"\n Enter Record Number to edit: ";
    cin>>n;
    iofile.seekg((n-1)*sizeof(*this));
    iofile.read(reinterpret_cast<char*>(this), sizeof(*this));
    cout<<"Record "<<n<<" has following data"<<endl;
    show_data();
    iofile.close();
    iofile.open("record.bank", ios::out|ios::in|ios::binary);
    iofile.seekp((n-1)*sizeof(*this));
    cout<<"\nEnter data to Modify "<<endl;
    read_data();
    iofile.write(reinterpret_cast<char*>(this), sizeof(*this));
}

void account_query::delete_rec()
{
    int n;
    ifstream infile;
    infile.open("record.bank", ios::binary);
    if(!infile)
    {
        cout<<"\nError in opening! File Not Found!!"<<endl;
        return;
    }
    infile.seekg(0,ios::end);
    int count = infile.tellg()/sizeof(*this);
    cout<<"\n There are "<<count<<" record in the file";
    cout<<"\n Enter Record Number to Delete: ";
    cin>>n;
    fstream tmpfile;
    tmpfile.open("tmpfile.bank", ios::out|ios::binary);
    infile.seekg(0);
    for(int i=0; i<count; i++)
    {
        infile.read(reinterpret_cast<char*>(this),sizeof(*this));
        if(i==(n-1))
            continue;
        tmpfile.write(reinterpret_cast<char*>(this), sizeof(*this));
    }
    infile.close();
    tmpfile.close();
    remove("record.bank");
    rename("tmpfile.bank", "record.bank");

}
int main()
{
    account_query A;
    int choice;
    cout<<"***Acount Information System***"<<endl;
    while(true)
    {
        cout<<"Select one option below ";
        cout<<"\n\t1-->Add record to file";
        cout<<"\n\t2-->Show record from file";
        cout<<"\n\t3-->Search Record from file";
        cout<<"\n\t4-->Update Record";
        cout<<"\n\t5-->Delete Record";
        cout<<"\n\t6-->Quit";
        cout<<"\nEnter your choice: ";
        cin>>choice;
        switch(choice)
        {
            case 1:
                A.write_rec();
                break;
            case 2:
                A.read_rec();
                break;
            case 3:
                A.search_rec();
                break;
            case 4:
                A.edit_rec();
                break;
            case 5:
                A.delete_rec();
                break;
            case 6:
                exit(0);
                break;
            default:
                cout<<"\nEnter corret choice";
                exit(0);
        }
    }
    system("pause");
    return 0;
}