Category: C/C++

C++ training

Posted by – July 29, 2006

I just finished four days C++ training. I was extremely impressed by the instructor’s deep insight into C++ knowledge. Before I join Morgan Stanley, I thought I had a pretty good knowledge of C++. After this class, I found that still have a long way to go!

A trick using #if pre-processor

Posted by – February 13, 2006

I hit a small C++ grammar trick which I have never met before in my project. The problem is how to deal with the situation that two defined identifiers have the same compilation behavior. A simple solution to this is to write two same block code like this:

More

Thinking in C++

Posted by – February 2, 2006

I have read the volume 1 of the book during the last month.
It is a very famous book about C++. When I was searching the way to master the C++ language, everyone recommend this book to me.

More

Binary Search Tree

Posted by – January 12, 2006

Binary search tree is a binary tree in which each internal node x stores an element such that the elements stored in the left subtree of x are less than or equal to x and elements stored in the right subtree are greater than or equal to x. The following code is the class of binary search tree designed by me. I use a function pointer m_visit to construct the tree and visit the nodes of the tree.


template<typename T>
class BSTreeNode
{
public:
    BSTreeNode(T d, BSTreeNode<T> *p=NULL, BSTreeNode<T> *l=NULL,
               BSTreeNode<T> *r=NULL):data(d),parent(p),left(l),right(r){}
    T data;
    BSTreeNode<T> *parent;
    BSTreeNode<T> *left;
    BSTreeNode<T> *right;
};

template<typename T>
class BSTree
{
protected:
    BSTreeNode<T> *m_root;

// A function pointer that points the visit function
    typedef void (*v_func)(const T &data);
    v_func m_visit;//the visit function pointer
    void Inorder(BSTreeNode<T> *);//Inorder traversal of the tree
public:
    BSTree(v_func f, BSTreeNode<T> *p=NULL): m_visit(f), m_root(p) {}
    BSTreeNode<T>* GetRoot() { return m_root; } const

//inorder tree walk, thus prints a sorted list
    void InorderWalk() { Inorder(m_root);}
//query on the binary search tree
    BSTreeNode<T>* Search(const T &);
//find the successor of the given node in the sorted order which
//is determined by an inorder tree walk
    BSTreeNode<T>* Successor(BSTreeNode<T>*);
//return the maximum element of the binary tree
    const T& Maximum(void);
//return the minimum element of the binary tree
    const T& Minimum(void);
//insert a new value into the binary search tree
    void Insert(const T&);
//insert a new value with recursive version procedure
    void Insert2(const T&, BSTreeNode<T>*);
//delete a node from the binary search tree
    BSTreeNode<T>* Delete(BSTreeNode<T>*);
};

Let’s walk through the procedure of searching a given key in the above binary search data structure.

The procedure begins its search at the root and traces a path downward in the tree, and for each node it encounters, it compares the keys. If the searched key is bigger than the current key of the node, it goes down to left subtree. If the searched key is smaller than the current key of the node, it goes down to right subtree. If two keys are equal, the search terminates.

template<typename T>
BSTreeNode<T>* BSTree<T>::Search(const T &d)
{
    BSTreeNode<T>* p = m_root;
    while(p && p->data!=d)
    {
        if(p->data > d)
            p=p->left;
        else
            p=p->right;
    }
    return p;
}

The structure of a binary search tree allows us to determine the In Order successor of a node without ever comparing keys. The following procedure returns the successor of a node x in a binary search tree if it exists, or NULL if x has the largest key in the tree.

template<typename T>
BSTreeNode<T>* BSTree<T>::Successor(BSTreeNode<T>* x)
{
    //return the node x's successor if it exists.
    if(!x)
        return NULL;
    BSTreeNode<T>* y=x->right;

    //if x has right children, just return the leftmost node
    //in the right subtree.
    if(y)
    {
        while(y->left)
            y=y->left;
        return y;
    }


    //if x has no right child, then x's successor is the lowest
    //ancestor of x
    else
    {   //whose left child is also an ancestor of x.
        y=x->parent;
        while(y && x!=y->left)
        {
            x=y;
            y=y->parent;
        }
        return y;
    }
}

An element in a binary search tree whose key is a minimum can always be found by following left child pointers from the root until a NULL is encountered, thus the procedure of finding the maximum element is symmetric.

template<typename T>
const T& BSTree<T>::Minimum()
{
    BSTreeNode<T>* p = m_root;
    while(p->left)
        p=p->left;
    return p->data;
}
template<typename T>
const T& BSTree<T>::Maximum()
{
    BSTreeNode<T>* p = m_root;
    while(p->right)
        p=p->right;
    return p->data;
}

To insert a node into a binary search tree, we use a node pointer x which begins at the root of the tree and traces a path downward. The pointer x traces the path, and the pointer y is maintained as the parent of x. These two pointers to move down the tree, going left or right depending on the comparison of the key to be inserted with x->data, until x is set to NULL. At that time, we use y to help us to insert the key. Insert2 is a recursive version of the insertion procedure.

template<typename T>
void BSTree<T>::Insert(const T& da)
{
    BSTreeNode<T>* x=m_root,*y=NULL;
    if(!x)//the tree is empty
        m_root = new BSTreeNode<T>(da);
    else
    {
        while(x)
        {
            y=x;//store x's parent;
            if(da > x->data)
                x=x->right;
            else
                x=x->left;
        }//now y is the insertion node's parent
        x = new BSTreeNode<T>(da);
        x->parent=y;
        if(da > y->data)
            y->right=x;
        else
            y->left=x;
    }
}

template<typename T>
void BSTree<T>::Insert2(const T& data, BSTreeNode<T>* z=NULL)
{
    BSTreeNode<T>* x;
    if(!z)
    {
        m_root = new BSTreeNode<T>(data);
        return;
    }
    if(data > z->data && z->right)
        Insert2(data,z->right);
    if(data <= z->data && z->left)
        Insert2(data,z->left);

    if(!z->right && data > z->data)
    {
        x = new BSTreeNode<T>(data);
        z->right = x;
        x->parent = z;
    }

    if(!z->left && data < z->data)
    {
        x = new BSTreeNode<T>(data);
        z->left = x;
        x->parent = z;
    }
}

However, removing a node from a binary search tree is a bit more complex. Which node is actually removed is depends on how many children the node to be deleted has. If the node has one child then the child is spliced to the parent of the node, which means that we should remove the node itself. If the node has two children then its successor has no left child; copy the successor into the node and delete the successor instead. The following figure shows deleting a node z from a binary search tree. (a) z has no children, we just remove it. (b) z has only one child, we splice out z. (c) z has two children, we splice out its successor y, which has at most one child, and then replace z’s key and data with y’s key and data.

 

delsearchtree.gif

template<typename T>
void BSTree<T>::Delete(BSTreeNode<T>* z)
{
    if(!z)
        return NULL;
//y is the node should be removed, and x is the child of y
    BSTreeNode<T> *y, *x;
//if z has 2 children, we should remove its successor
    if(z->left && z->right)
        y=Successor(z);
    else//if z has 1 or no child, z itself should be removed.
        y=z;

//Let x be the y's child and if y is the successor of z,
//notice that x has at most one child
    if(y->left)
        x=y->left;
    else
        x=y->right;

//begin to remove y from the tree
    if(x)
        x->parent=y->parent;
    if(!y->parent)//if y is the root, let x be the root
        m_root=x;
    else
    {
        if(y==y->parent->left)
            y->parent->left = x;
        else
            y->parent->right = x;
    }

//if z has 2 children and we split out its successor
    if(y!=z)
        z->data=y->data;
    delete y;
}

Finally, Here is the piece of code to test out my little binary search tree. The function print() visits the data of the tree node. The rand() function can generate random integers ranges from -999 to 999 approximately.

#include <iostream>
#include <time.h>
time_t* tp;
int randx =time(tp);
int rand()
{
    randx = randx * 12345;
    return randx % 1000;
}
static void print(const int& data)
{
    cout<<data<<" ";
}

int main()
{
    BSTree<int> bstree1(&print);
    int i;
    for(i=0;i<10;i++)
        bstree1. Insertion(rand(),bstree1.GetRoot());
    bstree1.InorderWalk();
    cout<<endl;
    int min=bstree1.Minimum();
    int max=bstree1.Maximum();
    cout<<"The minimum element is: "<<min<<endl;
    cout<<"The maximum element is: "<<max<<endl; int secondmin=bstree1.Successor(bstree1.Search(min))->data;
    cout<<"The second minimum element is : "<<secondmin<<endl;
    int del=1;
    while(del!=0){
        cout<<"Choose an item to be deleted(Input '0' to quit):"; cin>>del;
        if(bstree1.Delete(bstree1.Search(del)))
            cout<<"Deletion Completed!n";
        bstree1.InorderWalk();
        cout<<endl;
    }
    return 0;
}

C++ Tips from Thinking in C++(4)

Posted by – November 21, 2005

This entry is continued from C++ Tips from Thinking in C++(3)

More

C++ Tips from Thinking in C++(3)

Posted by – November 18, 2005

This entry is continued from C++ Tips from Thinking in C++(2)

More

C++ Tips from Thinking in C++(2)

Posted by – November 13, 2005

Continued from C++ Tips from Thinking in C++(1)
5. Const pointer VS. Pointer to const
If you want to prevent any changes to the element you are pointing to, that is “Pointer to const”, you write a definition like this:

const int* u;

Starting from the identifier, we read “u is a pointer, which points to a const int.”
Here’s the mildly confusing part. You might think that to make the pointer itself unchangeable, that is, to prevent any change to the address contained inside u, you would simply move the const to the other side of the int like this:

int const* v;

Unfortunately, I will tell you that it’s wrong! Actually “const int* u;EQUALSint const* v;“. However, the way it actually reads is “v is an ordinary pointer to an int that happens to be const.” That is, the const has bound itself to the int again, and the effect is the same as the previous definition. So to avoid confusion, you should abandon the second form.
So how to make a “const pointer”? To make the pointer itself a const, you must place the const specifier to the right of the *, like this:

int d = 1;
int* const w = &d;

Now it reads: “w is a pointer, which is const, that points to an int.” Because the pointer itself is now the const, the compiler requires that it be given an initial value that will be unchanged for the life of that pointer.
You can also make a const pointer to a const object using either of two legal forms:

int d = 1;
const int* const x = &d; // (1)
int const* const x2 = &d; // (2)

Now neither the pointer nor the object can be changed.
6. Standard argument passing
In C it’s very common to pass by value, and when you want to pass an address your only choice is to use a pointer. However, in C++, Your first choice when passing an argument is to pass by reference, and by const reference at that. But, passing by reference produces a new situation that never occurs in C: a temporary, which is always const, can have its address passed to a function.So to allow temporaries to be passed to functions by reference, the argument must be a const reference.The following example demonstrates this: (c++11 introduced

class X {};
X f() { return X(); } // Return by value
void g1(X&) {} // Pass by non-const reference
void g2(const X&) {} // Pass by const reference


int main() {
// Error: const temporary created by f():
//! g1(f());
// OK: g2 takes a const reference:
g2(f());
} ///:~

f( ) returns an object of class X by value. That means when you immediately take the return value of f( ) and pass it to another function as in the calls to g1( ) and g2( ), a temporary is created and that temporary is const. Thus, the call in g1( ) is an error because g1( ) doesn’t take a const reference, but the call to g2( ) is OK.

C++ Tips from Thinking in C++(1)

Posted by – October 15, 2005

The following C++ grammar items are extracted from the book Thinking in C++. Most of them are often forgotten by myself. I will record here for my future quick reference.

More