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.
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

The code is also available on GitHub.

#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.

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;
}

Friday, November 25, 2011

Analysis of Tower of Hanoi Problem with Algorithm and Source code in C/C++

The Towers of Hanoi is well-known game, played with three poles and a number of different-sized disks. Each disk has a hole in the center, allowing it to be stacked around any of the poles. Initially, the disks are stacked on the leftmost pole in the order of decreasing size, i.e., the largest on the bottom and the smallest on the top, as shown in the figure below.

The objective of the game is to transfer the disks from the leftmost pole to the rightmost pole, without ever placing a larger disk, on the top of a smaller disk. Only one disk may be moved at a time, and each disk must always be placed around one of the poles. The general strategy is to consider one of the poles to be the origin, and another to be the destination. The third pole will be used for intermediate storage, thus allowing the disks to be moved without placing a larger disk over a smaller disk. Assume there are n disks, numbered from smallest to largest, as above figure. If th disks are initially stacked on the left pole, the problem of moving all n disks to the right pole can be started using following Algorithm.

Algorithm

1. Declare necessary variables such as n, A, B, C etc.2. Input number of disks3. If n=1        move single disk from peg A to peg C and stop.    Else        move the top (n-1) disks from peg A to peg B using peg C as auxiliary.4. Move remaining disks from peg A to peg C.5. Move (n-1) disks from peg B to peg C using peg A as auxiliary

Source Code

#include<stdio.h>void transfer(int n, char from, char to, char temp);int main(){    int n;    printf("WELCOME TO THE TOWERS OF HONAI\n\n");    printf("How many disks? ");    scanf("%d", &n);    printf("\n");    transfer(n,'L','R','C');    return 0;}void transfer(int n, char from, char to, char temp){    /** n = number of disks        from = orinin        to = destination        temp = temporary storage  **/    if(n>0){        /** move n-1 disks from origin to temporary **/        transfer(n-1, from, temp, to);        /** move nth disk from origin to destination **/        printf("Move disk %d from %c to %c\n", n, from, to);        /** move n-1 disks from temporary to destination **/        transfer(n-1, temp, to, from);    }}

Output

WELCOME TO THE TOWERS OF HONAI

How many disks? 3

Move disk 1 from L to R
Move disk 2 from L to C
Move disk 1 from R to C
Move disk 3 from L to R
Move disk 1 from C to L
Move disk 2 from C to R
Move disk 1 from L to R

C++ Tutorial: File Handling in C++

Opening and Closing Files
In C++, a file is opened by either of two ways. First way is the constructor function of the file stream class and second way is by making use of member function open() of the same class. After using the file it must be closed. The file can also be closed by two ways. First way is automatically closing by the destructor of the file stream class and the second way is closing the file explicitly by the member function close() of the file stream class.
(A) Opening and Closing Files using Constructor and Destructor
For every action on file, it must be opened first. A file is opened in either read, write or append or other modes. Using constructor, a file can be opened by passing a filename as parameter in the constructor. Since constructor is invoked during the time of object creation, it can be used to initialize the file stream object with the filename, so that the file stream object refers to the file. The statement
ofstream oufile("myfile.txt");

opens the file myfile.txt for output. After opening the file through file stream object, the read/write operation can be performed through the stream operator insertion (<<) and extraction (>>). To write to the file “myfile.txt” opened through file stream object outfile we write the statement
outfile<<"John Doe";

Similarly, to read from file we open the file using constructor as
ifstream infile("myfile.txt");
infile>>age;
This statement reads data from file “myfile.txt” to variable age through file stream object infile.

(B) Opening and Closing Files Explicitly

Apart from constructor, file can be opened explicitly by making use of member function open(). The function open() is a member of all the file stream classes ofstream, ifstream and fstream. The syntax for opening and closing file explicitly for writing purpose is
ofstream fout;
fout.open("myfile.txt");
// some operation
fout.close();
Similarly for reading purpose
ifstream fin;
fin.open("myfile.txt");
//some operation
fin.close();

Stream Operator (Insertion(<<) and Extraction (>>)) Overloading in C++

The stream can be used not only with standard data types nut also with user defined classes. The C++ lets us treat user-defined data types in the same way as that of built in types like int or cahr. To read and display user defined data types like the built in data type, we have to overload the stream extraction (>>) and insertion (<<) operators to accept the user defined data. We can overload the stream the stream operator to read keyboard input and display output for user defined classes. After overloading the stream operator, single input/output statement can be used for input/output of user defined data reducing the number of statements. Without stream operator overloading,    we need to define member function like display() for a class and call them as
obj1.display();
obj2.display();

But with overloading of insertion operator both the objects can be displayed conveniently as
cout<<obj1<<obj2<<endl;
Reading can also be done in similar manner.The following code illustrate the insertion and extraction operator overloading.
#include<iostream>
#include<cstdlib>

using std::cin;
using std::cout;
using std::endl;
using std::istream;
using std::ostream;
using std::flush;

class Complex
{
private:
float real, imag;
public:
Complex():real(0),imag(0){}
friend istream & operator>>(istream &is, Complex &C);
friend ostream & operator<<(ostream &os, Complex &C);
};

istream &operator >> (istream &is, Complex &C)
{
is>>C.real>>C.imag;
return is;
}

ostream &operator << (ostream &os, Complex &C)
{
os<<C.real<<"+i"<<C.imag<<flush;
return os;
}

int main()
{
Complex C1;
cout<<"Enter Complex Number: ";
cin>>C1;
cout<<"Complex Number Entered is: ";
cout<<C1<<endl;
system("pause");
return 0;
}