Programming with C\C++ and java

Stack implementation using arrays

deveshucer@gmail.com (Devesh) — Wed, 05 Mar 2014 11:38:00 +0000

#include<stdio.h>
#include<stdlib.h>

void push(int S[],int item);
void pop(int S[]);
void displayStack(int S[]);
int top = -1,s_max;

int main(void)
{

        int choice,item;
        printf("\nEnter the Size of the stack : ");
        scanf("%d",&s_max);

        int S[s_max];

        while(1)
        {
        printf("\nEnter the operations choice\n1.Push\n2.Pop\n3.Display Stack\n4.Exit\n\n");
        scanf("%d",&choice);
        switch(choice)
        {
                case 1 :printf("\nEnter the element to push into the stack : ");
                        scanf("%d", &item);
                        push(S,item);
                        //displayStack(S);
                        break;
                case 2 : pop(S);
                        //displayStack(S);
                        break;
                case 3 : displayStack(S);
                         break;
                case 4 : exit(0);
                default:printf("\n\nYou have entered wrong choice !\n\n");
        }
        }
        return 0;

}

void push(int S[],int item)
{
    if(top == s_max-1)
        printf("\n Overflow Error : Stack is full you can't enter any more element.\n");
    else
    {
        top=top+1;
        S[top]=item;
    }
}

void pop(int S[])
{
    if(top == -1)
        printf("\n Underflow Error : Stack is Empty you can't delete any more element.\n");
    else
    {
       top = top-1;
        S[top+1];
        printf("\n%d is poped!\n", S[top+1]);
    }
}

void displayStack(int S[])
{
    int i;
    if(top == -1)
        printf("\nStack is Empty |__| !\n");
    else
    for(i=top; i>=0; i--)
    {
        printf("\t%d\n",S[i]);
    }
}

Output :

Queue Implementation using arrays

deveshucer@gmail.com (Devesh) — Wed, 05 Mar 2014 07:20:00 +0000

#include<stdio.h>
#include<stdlib.h>
#define MAX 4       //you can increase or decrease the
                    //queue size by modifying MAX value

void Enqueue(int Q[], int item);
void Dequeue(int Q[]);
void display_Q(int Q[]);

int Front=-1,Rear=-1;


int main(void)
{
    int item,choice;
    int Q[MAX];

    while(1)
    {
        printf("\n1.Insert an item into Q\n2.Delete an item from Q"
               "\n3.Display Queue\n4.Exit\n\nEnter the choice as given : ");
        scanf("%d",&choice);

        switch(choice)
        {
            case 1:printf("\nEnter the element : ");
                    scanf("%d",&item);
                    Enqueue(Q,item);
                    break;
            case 2:Dequeue(Q);
                    break;
            case 3:display_Q(Q);
                    break;
            case 4:exit(0);
                    break;
            default: printf("\n\nYou have entered wrong choice !\n\n");
        }
    }
    return 0;
}

void Enqueue(int Q[], int item)
{

    if(Rear == MAX-1)
    {
        if(Front == 0)
            printf("\nQueue is full, you can't enter any more elemetns !\n\n");
        else
            printf("\nYou can't insert untill queue will not be empty !\n");
    }
    else
    {
        Rear++;
        Q[Rear]= item;
        if(Front==-1)
            Front = 0;
    }
}

void Dequeue(int Q[])
{
    int x;
    if(Front == -1)
        printf("\nQueue is Empty, you can't delete any more element !\n\n");
    else
    {
        x = Q[Front];
        Front++;
        if(Front == Rear+1)
        {
            Front = -1;
            Rear = -1;
        }
        printf("\n%d is deleted form Queue !\n",x);
    }
}

void display_Q(int Q[])
{
    int i;
    if(Front == -1)
        printf("\nQueue is Empty !\n\n");
    else
        for(i=Front; i<=Rear; i++)
        printf(" %d",Q[i]);
}

//Note => once you started deletion You can't insert another
//element in queue untill the queue is empty.
//cause it is array implementation and it is also not a circular queue

Output:

List of HTML tags with description

deveshucer@gmail.com (Devesh) — Wed, 11 Apr 2012 15:28:00 +0000

Tag	What it is	When to use it
<a>	Anchor (most commonly a link)	Vital. Use to create links in content. Use the title attribute whenever the contents of the <a>…</a> pair do not accurately describe what you’ll get from selecting the link. Title attribute often displays as a tooltip in visual browsers, which may be a helpful usability aid.
<abbr>	Defines an abbreviation	Works in a similar way to <dfn> and <acronym>, using a title attribute (displays a tooltip in standard visual browsers). e.g. <abbr title=”Hypertext markup language”>HTML</abbr>
<ACRONYM>	Defines an acronym	Works in a similar way to <abbr> and <dfn>, using a title attribute (displays a tooltip in standard visual browsers).
<ADDRESS>	Used for marking up a physical (e.g. mailing) address	Not commonly used. Recommend looking into microformats, which allow for more detail and interoperability.
<APPLET>	Inserts a Java applet	The old way to insert a Java app. Use <object> instead today.
<AREA>	Hotspot in image map	Avoid image maps where possible. Occasionally necessary.
<BASE>	Specifies the base location of the document.	Use only when necessary. Adjusts any relative links and paths within the document.
<BASEFONT>	Sets default font size	Display info – never use it
<BIG>	Larger text	Display info – never use it
<BLINK>	Makes text blink	You go to hell if you use this
<BLOCKQUOTE>	Large quoted block of text	Use for any quoted text that constitutes one or more paragraphs (note: should contain <p> tags as well). Use <q> for quotations within a paragraph. Often used in conjunction with <cite> to cite the quotation’s source.
<BODY>	Document body	Essential (unless you’re using frames)
<BR>	Line break	This is arguably display information. Still in common use, but use with restraint.
<B>	Bold text	Display info – never use it
<BUTTON>	Used for a standard clickable button within a form	Often better than <input type=”button” /> or <input type=”submit” />, as it allows you to assign different styles based on the HTML element alone, whereas differentiating style based on the type of input is less well supported.
<CAPTION>	Caption for a table: describes the table’s contents	The correct way to assign a title to a table
<CENTER>	Centred block	Display info – never use it. Use <div> or some other block-level tag with the style text-align:center instead
<CITE>	Defines a citation	Defines the source of a quotation (in conjunction with content in <q> or <blockquote> pairs).
<CODE>	Defines an extract of code	Not commonly used. Similar to <pre> tag, but collapses consecutive white spaces and line breaks in the source.
<COL>	Identifies a particular column in a table	Can be very useful. e.g. <col class=”namecol”> can be applied to each first column in a series of tables, then the width of each column may be set to be equal in the stylesheet, overriding the table’s natural tendency to adjust its own column widths to fit its contents.
<DFN>	Definition of a term	Works in a similar way to <abbr> and <acronym>, using a title attribute (displays a tooltip in standard visual browsers).
<DIR>	Directory list	Now deprecated. Use a standard <ul> or other list instead.
<DIV>	Division	Specifies a logical division within a document. Use it to separate or identify chunks of content that are not otherwise distinguished naturally using other tags. One of the most common HTML tags.
<DL>	Definition list	Contains one or more definition-term / definition-description pairs.
<DT>	Definition term	Used as part of a <dt></dt><dd></dd> pair within a definition list (<dl></dl>)
<DD>	Definition description
<EM>	Emphasis	Commonly used in place of the old <i> (italics) tag to indicate emphasis (but less than <strong>)
<FONT>	Font settings	Display info – never use it
<FORM>	Input form	Essential for data input
<H1>	Level 1 header	Aim to have one H1 on each page, containing a description of what the page is about.
<H2>	Level 2 header	Defines a section of the page
<H3>	Level 3 header	Defines a sub-section of the page (should always follow an H2 in the logical hierarchy)
<H4>	Level 4 header	Etc. Less commonly used
<H5>	Level 5 header	Less commonly used. Only complex academic documents will break down to this level of detail.
<H6>	Level 6 header	Less commonly used
<HEAD>	Document head	Essential. Contains information about a page that does not constitute content to be communicated as part of the page.
<HR>	Horizontal rule	Display info with no semantic value – never use it. “Horizontal”, by definition, is a visual attribute.
<HTML>		Core element of every web page.
<IMG >	Show an image	Vital. Always use the alt or longdesc attributes when the image has content value
<INPUT>	Input fields within forms	Vital. (I prefer to use <button> for buttons and submit buttons though)
<ISINDEX>	Old type of search input	Not really used any more. Use <form> instead.
<I>	Italicised text	Display info – never use it
<KBD>	Keyboard input	Display info – never use it
<LINK>	Defines a relationship to another document	Commonly used to reference external stylesheets, but has other minor uses
<LI>	List item	Specifies an item in an unordered or ordered list (<ul> or <ol>)
<MAP>	Client-side imagemap	May have occasional value, but only use when absolutely necessary
<MARQUEE>	Makes text scroll across the screen	See <blink>
<MENU>	Menu item list	Deprecated. Do not use. Use other standard list types instead.
<META>	Meta-information	Useful way to insert relevant information into the <head> section of the page that does not need to be displayed.
<OL>	Ordered list	Type of list where the order of elements has some meaning. Generally rendered with item numbers (best managed with CSS).
<OPTION>	Selection list option	Vital for options within a drop-down control.
<PARAM>	Parameter for Java applet	Used in conjunction with an <object> or <applet> tag to pass additional setting information at runtime.
<PRE>	Preformatted text	Renders text in a pre-formatted style, preserving line breaks and all spaces present in the source. May be useful. (This one’s a paradox, as it is strictly display info that applies only to visual browsing, but it’s still so commonly used and useful that I’m hesitant to advise against using it.)
<P>	Paragraph	Only use to denote a paragraph of text. Never use for spacing alone.
<Q>	Short quotation	Use for inline quotations (whereas <blockquote> should be used for quotations of a paragraph or more). Often used in conjunction with <cite> to cite the quotation’s source.
<SAMP>	Denotes sample output text	Similar to the <code> tag. Rarely used. Avoid.
<SCRIPT>	Inline script (e.g. JavaScript)	It’s better to have all scripts as separate files than to write inline or in the <head> section, however still has its uses.
<SELECT>	Selection list	A drop-down selector for a form.
<SMALL>	Smaller text	Display info – never use it
<SPAN>	An inline span within text	Use to apply meaning (and style) to a span of text that goes with the flow of content (whereas a <div> tag is block-level and breaks the flow)
<Strikeout>		Display info – never use it
<STRONG>	Strong emphasis	Use this instead of the old <b> tag.
<STYLE>	CSS style settings	Normally used in <head> section of a page. Try to use external stylesheets, to enable you to apply different styles for different output media.
<SUB>	Subscript text	Arguably display info – recommend using alternative tags (e.g. <cite>). May be required in some academic uses, e.g. Chemical formulas.
<SUP>	Superscript text
<TABLE>	Table	Use for repeated data that has a naturally tabular form. Never use for layout purposes.
<TD>	Table data cell	A cell containing actual data. If a cell actually contains a descriptor or identifier for a row or column, use a <th> (table header) tag, not a <td>. This usually applies to column headers (within a <thead>), column footers (within a <tfoot>), as well as row headers (usually the first cell in a row in the <tbody>).
<TEXTAREA>	Multi-line text input area in a form	Essential
<TH>	Table column or row header cell	May appear in a <thead> (to denote a column header cell), <tbody> (to denote a row header), and in <tfoot> (to denote a column foot cell, e.g. a total)
<TBODY>	Indicates the main body of a data table	It is always worth using this tag, as well as using <thead> and <tfoot> where appropriate. Note that it is permissible to have more than one <tbody>, <thead>, and <tfoot> in the same table.
<THEAD>	The head section of a table	The place to put column header cells (<th>)
<TFOOT>	The foot section of a table	Good place to put e.g. summary data, such as totals. Note that it goes before the <tbody> tag!
<TITLE>	Document title	Essential
<TR>	Table row	Essential with tables
<TT>	“Teletype” - simulates typewriter output	Similar to <pre>, except that it collapses white space like normal HTML (whereas <pre> leaves all consecutive white space intact). Avoid if possible
<UL>	Unordered list	Essential. Use for lists where the order or items has no particular importance.
<U>	Underline text	Display info – never use it
<VAR>	Variable in computer code	Obscure tag, may only be useful in academic documents. Avoid.

Program for character Stuffing

deveshucer@gmail.com (Devesh) — Wed, 11 Apr 2012 15:10:00 +0000

#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<process.h>
int _tmain(int argc, _TCHAR* argv[])
{
int i=0,j=0,n,pos;
char a[20],b[50],ch;
printf("Enter string\n");
scanf("%s",&a);
n=strlen(a);
printf("\nEnter position : ");
scanf("%d",&pos);
if(pos>n)
{
printf("Invalid position, Enter again : ");
scanf("%d",&pos);
}
printf("Enter the character: ");
ch=getche();

b[0]='d';
b[1]='l';
b[2]='e';
b[3]='s';
b[4]='t';
b[5]='x';
j=6;
while(i<n)
{
if(i==pos-1)
{
b[j]='d';
b[j+1]='l';
b[j+2]='e';
b[j+3]=ch;
b[j+4]='d';
b[j+5]='l';
b[j+6]='e';
j=j+7;
}
if(a[i]=='d' && a[i+1]=='l' && a[i+2]=='e')
{
b[j]='d';
b[j+1]='l';
b[j+2]='e';
j=j+3;
}

b[j]=a[i];
i++;
j++;
}
b[j]='d';
b[j+1]='l';
b[j+2]='e';
b[j+3]='e';
b[j+4]='t';
b[j+5]='x';
b[j+6]='\0';
printf("\n\nFrame after stuffing: ");
printf("%s",b);
getch();
return 0;
}

Function Overloading in C++

deveshucer@gmail.com (Devesh) — Sat, 25 Feb 2012 10:12:00 +0000

In C++, following function declarations cannot be overloaded.

1) Function declarations that differ only in the return type. For example, the following program fails in compilation.

#include&lt;iostream&gt;

int foo() {

  return 10;

}

char foo() {

  return 'a';

}

int main()

{

   char x = foo();

   getchar();

   return 0;

}

2) Member function declarations with the same name and the name parameter-type-list cannot be overloaded if any of them is a static member function declaration. For example, following program fails in compilation.

#include&lt;iostream&gt;

class Test {

   static void fun(int i) {}

   void fun(int i) {}

};

int main()

{

   Test t;

   getchar();

   return 0;

}

3) Parameter declarations that differ only in a pointer * versus an array [] are equivalent. That is, the array declaration is adjusted to become a pointer declaration. Only the second and subsequent array dimensions are significant in parameter types. For example, following two function declarations are equivalent.

int fun(int *ptr);

int fun(int ptr[]); // redeclaration of fun(int *ptr)

4) Parameter declarations that differ only in that one is a function type and the other is a pointer to the same function type are equivalent.

void h(int ());

void h(int (*)()); // redeclaration of h(int())

5) Parameter declarations that differ only in the presence or absence of const and/or volatile are equivalent. That is, the const and volatile type-specifiers for each parameter type are ignored when determining which function is being declared, defined, or called. For example, following program fails in compilation with error “redefinition of `int f(int)’ “
Example:

#include&lt;iostream&gt;

#include&lt;stdio.h&gt;

using namespace std;

int f ( int x) {

    return x+10;

}

int f ( const int x) {

    return x+10;

}

int main() {

  getchar();

  return 0;

}

Only the const and volatile type-specifiers at the outermost level of the parameter type specification are ignored in this fashion; const and volatile type-specifiers buried within a parameter type specification are significant and can be used to distinguish overloaded function declarations. In particular, for any type T,
“pointer to T,” “pointer to const T,” and “pointer to volatile T” are considered distinct parameter types, as are “reference to T,” “reference to const T,” and “reference to volatile T.” For example, see the example in this comment posted by Venki.
6) Two parameter declarations that differ only in their default arguments are equivalent. For example, following program fails in compilation with error “redefinition of `int f(int, int)’ “

#include&lt;iostream&gt;

#include&lt;stdio.h&gt;

using namespace std;

int f ( int x, int y) {

    return x+10;

}

int f ( int x, int y = 10) {

    return x+y;

}

int main() {

  getchar();

  return 0;

}

AVL Tree | Set 1 (Insertion)

deveshucer@gmail.com (Devesh) — Sat, 25 Feb 2012 10:08:00 +0000

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.
Why AVL Trees?
Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that height of the tree remains O(Logn) after every insertion and deletion, then we can guarantee an upper bound of O(Logn) for all these operations. The height of an AVL tree is always O(Logn) where n is the number of nodes in the tree (See this video lecture for proof).
Insertion
To make sure that the given tree remains AVL after every insertion, we must augment the standard BST insert operation to perform some re-balancing. Following are two basic operations that can be performed to re-balance a BST without violating the BST property (keys(left) < key(root) < keys(right)).
1) Left Rotation
2) Right Rotation

T1, T2 and T3 are subtrees of the tree rooted with y (on left side)
or x (on right side)
                y                               x
               / \     Right Rotation          /  \
              x   T3   – - – - – - – >        T1   y
             / \       < - - - - - - -            / \
            T1  T2     Left Rotation            T2  T3
Keys in both of the above trees follow the following order
      keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)
So BST property is not violated anywhere.

Steps to follow for insertion
Let the newly nserted node be w
1) Perform standard BST insert for w.
2) Starting from w, travel up and find the first unbalanced node. Let z be the first unbalanced node, y be the child of z that comes on the path from w to z and x be the grandchild of z that comes on the path from w to z.
3) Re-balance the tree by performing appropriate rotations on the subtree rooted with z. There can be 4 possible cases that needs to be handled as x, y and z can be arranged in 4 ways. Following are the possible 4 arrangements:
a) y is left child of z and x is left child of y (Left Left Case)
b) y is left child of z and x is right child of y (Left Right Case)
c) y is right child of z and x is right child of y (Right Right Case)
d) y is right child of z and x is left child of y (Right Left Case)
Following are the operations to be performed in above mentioned 4 cases. In all of the cases, we only need to re-balance the subtree rooted with z and the complete tree becomes balanced as the height of subtree (After appropriate rotations) rooted with z becomes same as it was before insertion. (See thisvideo lecture for proof)

a) Left Left Case

T1, T2, T3 and T4 are subtrees.
         z                                      y
        / \                                   /   \
       y   T4      Right Rotate (z)          x      z
      / \          - - - - - - - - ->      /  \    /  \
     x   T3                               T1  T2  T3  T4
    / \
  T1   T2

b) Left Right Case

     z                               z                           x
    / \                            /   \                        /  \
   y   T4  Left Rotate (y)        x    T4  Right Rotate(z)    y      z
  / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
T1   x                          y    T3                    T1  T2 T3  T4
    / \                        / \
  T2   T3                    T1   T2

c) Right Right Case

  z                                y
 /  \                            /   \
T1   y     Left Rotate(z)       z      x
    /  \   - - - - - - - ->    / \    / \
   T2   x                     T1  T2 T3  T4
       / \
     T3  T4

d) Right Left Case

   z                            z                            x
  / \                          / \                          /  \
T1   y   Right Rotate (y)    T1   x      Left Rotate(z)   z      x
    / \  - - - - - - - - ->     /  \   - - - - - - - ->  / \    / \
   x   T4                      T2   y                  T1  T2  T3  T4
  / \                              /  \
T2   T3                           T3   T4

C implementation

Following is the C implementation for AVL Tree Insertion. The following C implementation uses the recursive BST insert to insert a new node. In the recursive BST insert, after insertion, we get pointers to all ancestors one by one in bottom up manner. So we don’t need parent pointer to travel up. The recursive code itself travels up and visits all the ancestors of the newly inserted node.
1) Perform the normal BST insertion.
2) The current node must be one of the ancestors of the newly inserted node. Update the height of the current node.
3) Get the balance factor (left subtree height – right subtree height) of the current node.
4) If balance factor is greater than 1, then the current node is unbalanced and we are either in Left Left case or left Right case. To check whether it is left left case or not, compare the newly inserted key with the key in left subtree root.
5) If balance factor is less than 1, then the current node is unbalanced and we are either in Right Right case or Right Left case. To check whether it is Right Right case or not, compare the newly inserted key with the key in right subtree root.

#include<stdio.h>

#include<stdlib.h>

// An AVL tree node

struct node

{

    int key;

    struct node *left;

    struct node *right;

    int height;

};

// A utility function to get maximum of two integers

int max(int a, int b);

// A utility function to get height of the tree

int height(struct node *N)

{

    if (N == NULL)

        return 0;

    return N->height;

}

// A utility function to get maximum of two integers

int max(int a, int b)

{

    return (a > b)? a : b;

}

/* Helper function that allocates a new node with the given key and

    NULL left and right pointers. */

struct node* newNode(int key)

{

    struct node* node = (struct node*)

                        malloc(sizeof(struct node));

    node->key   = key;

    node->left   = NULL;

    node->right  = NULL;

    node->height = 1;  // new node is initially added at leaf

    return(node);

}

// A utility function to right rotate subtree rooted with y

// See the diagram given above.

struct node *rightRotate(struct node *y)

{

    struct node *x = y->left;

    struct node *T2 = x->right;

    // Perform rotation

    x->right = y;

    y->left = T2;

    // Update heights

    y->height = max(height(y->left), height(y->right))+1;

    x->height = max(height(x->left), height(x->right))+1;

    // Return new root

    return x;

}

// A utility function to left rotate subtree rooted with x

// See the diagram given above.

struct node *leftRotate(struct node *x)

{

    struct node *y = x->right;

    struct node *T2 = y->left;

    // Perform rotation

    y->left = x;

    x->right = T2;

    //  Update heights

    x->height = max(height(x->left), height(x->right))+1;

    y->height = max(height(y->left), height(y->right))+1;

    // Return new root

    return y;

}

// Get Balance factor of node N

int getBalance(struct node *N)

{

    if (N == NULL)

        return 0;

    return height(N->left) - height(N->right);

}

struct node* insert(struct node* node, int key)

{

    /* 1.  Perform the normal BST rotation */

    if (node == NULL)

        return(newNode(key));

    if (key < node->key)

        node->left  = insert(node->left, key);

    else

        node->right = insert(node->right, key);

    /* 2. Update height of this ancestor node */

    node->height = max(height(node->left), height(node->right)) + 1;

    /* 3. Get the balance factor of this ancestor node to check whether

       this node became unbalanced */

    int balance = getBalance(node);

    // If this node becomes unbalanced, then there are 4 cases

    // Left Left Case

    if (balance > 1 && key < node->left->key)

        return rightRotate(node);

    // Right Right Case

    if (balance < -1 && key > node->right->key)

        return leftRotate(node);

    // Left Right Case

    if (balance > 1 && key > node->left->key)

    {

        node->left =  leftRotate(node->left);

        return rightRotate(node);

    }

    // Right Left Case

    if (balance < -1 && key < node->right->key)

    {

        node->right = rightRotate(node->right);

        return leftRotate(node);

    }

    /* return the (unchanged) node pointer */

    return node;

}

// A utility function to print preorder traversal of the tree.

// The function also prints height of every node

void preOrder(struct node *root)

{

    if(root != NULL)

    {

        printf("%d ", root->key);

        preOrder(root->left);

        preOrder(root->right);

    }

}

/* Drier program to test above function*/

int main()

{

  struct node *root = NULL;

  /* Constructing tree given in the above figure */

  root = insert(root, 10);

  root = insert(root, 20);

  root = insert(root, 30);

  root = insert(root, 40);

  root = insert(root, 50);

  root = insert(root, 25);

  /* The constructed AVL Tree would be

            30

           /  \

         20   40

        /  \     \

       10  25    50

  */

  printf("Pre order traversal of the constructed AVL tree is \n");

  preOrder(root);

  return 0;

}

Output:

  Pre order traversal of the constructed AVL tree is
  30 20 10 25 40 50

Time Complexity: The rotation operations (left and right rotate) take constant time as only few pointers are being changed there. Updating the height and getting the balance factor also take constant time. So the time complexity of AVL insert remains same as BST insert which is O(h) where h is height of the tree. Since AVL tree is balanced, the height is O(Logn). So time complexity of AVL insert is O(Logn).
The AVL tree and other self balancing search trees like Red Black are useful to get all basic operations done in O(Logn) time. The AVL trees are more balanced compared to Red Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves many frequent insertions and deletions, then Red Black trees should be preferred. And if the insertions and deletions are less frequent and search is more frequent operation, then AVL tree should be preferred over Red Black Tree

HTML Layout source code

deveshucer@gmail.com (Devesh) — Mon, 13 Feb 2012 17:41:00 +0000

<html><bodybackground="http://img.wallpaperstock.net:81/abstract-fantasy-land-wallpapers_10123_1600x1200.jpg">

<img src="http://lh3.ggpht.com/-flGvqUJT4Tc/TWeVrfVKntI/AAAAAAAAAaI/ODtm2kpIsJg/Dev.3.jpg" height="75" width="63" border="1" alt="Devesh"/>



<table width="800" height ="600" border="0" align="center">
<tr>
<td colspan="2" style="background-color: purple;">
<center> <h1><font color="white"> Main title of the webpage </font> </h1></center>
</td>
</tr>

<tr valign="top">
<td style="background-color:yellowgreen;width:100px;text-align:top;">
<br/>
<b>  Menu</b><br />
<font color="blue">
  HTML<br />
  CSS<br />
  JavaScript <br/>
  PHP </br>
  ASP
</font>
</td>
<td style="background-color:lightgray;height:500px;width:400px;text-align:top;">
  Page content goes here....</td>
</tr>

<tr>
<td colspan="2" style="background-color:skyblue;text-align:center;">
Copyright © 2012 <a href="http:\\www.deveshucer.blogspot.com">deveshucer.blogspot.com</a></td>
</tr>
</table>

</body>
</html>

Output look like this.........

Main title of the webpage
Menu HTML CSS JavaScript PHP ASP	Page content goes here....
Copyright © 2012 deveshucer.blogspot.com

How to use function ?

deveshucer@gmail.com (Devesh) — Sun, 25 Dec 2011 11:07:00 +0000

#include<stdio.h>

#include<conio.h>
int header();
int sum; /* This is a global variable */
int main( )
{
int index;
header(); /* This calls the function named header */
for (index = 1;index <= 7;index++)
square(index); /* This calls the square function */
ending();
getch(); /* This calls the ending function */
}

header() /* This is the function named header */
{
sum = 0; /* initialize the variable "sum" */
printf("This is the header for the square program\n\n");
}

square(number) /* This is the square function */
int number;
{
int numsq;
numsq = number * number; /* This produces the square */
sum += numsq;
printf("The square of %d is %d\n",number,numsq);
}
ending() /* This is the ending function */
{
printf("\nThe sum of the squares is %d\n",sum);

}

Data Types in C

deveshucer@gmail.com (Devesh) — Sun, 25 Dec 2011 11:01:00 +0000

A programming language is proposed to help programmer to process certain kinds of data and to

provide useful output. The task of data processing is accomplished by executing series of commands

called program. A program usually contains different types of data types (integer, float, character

etc.) and need to store the values being used in the program. C language is rich of data types. A C

programmer has to employ proper data type as per his requirements.

C has different data types for different types of data and can be broadly classified as:

1. Primary Data Types

2. Secondary Data Types

Primary Data Types:

Integer Data Types:

Integers are whole numbers with a range of values, range of values are machine dependent.

Generally an integer occupies 2 bytes memory space and its value range limited to -32768 to +32767

(that is, -215 to +215-1). A signed integer use one bit for storing sign and rest 15 bits for number.

To control the range of numbers and storage space, C has three classes of integer storage namely

short int, int and long int. All three data types have signed and unsigned forms. A short

int requires half the amount of storage than normal integer. Unlike signed integer, unsigned

integers are always positive and use all the bits for the magnitude of the number. Therefore, the

range of an unsigned integer will be from 0 to 65535. The long integers are used to declare a longer

range of values and it occupies 4 bytes of storage space.

Syntax:

int <variable name>;

int num1;

short int num2;

long int num3;

Example: 5, 6, 100, 2500.

Integer Data Type Memory Allocation:

Floating Point Data Types:

The float data type is used to store fractional numbers (real numbers) with 6 digits of precision.

Floating point numbers are denoted by the keyword float. When the accuracy of the floating point

number is insufficient, we can use the double to define the number. The double is same as float but with longer precision and takes double space (8 bytes) than float. To extend the precision

further we can use long double which occupies 10 bytes of memory space.

Syntax :

float <variable name>;

float num1;

double num2;

long double num3;

Example: 9.125, 3.1254.

Floating Point Data Type Memory Allocation :

Character Data Type:

Character type variable can hold a single character and are declared by using the keyword char. As

there are singed and unsigned int (either short or long), in the same way there are signed and

unsigned chars; both occupy 1 byte each, but having different ranges. Unsigned characters have

values between 0 and 255, signed characters have values from –128 to 127.

Syntax:

char <variable name>;

char ch = ‘a’;

Example: a, b, g, S, j.

Void Type:

The void type has no values therefore we cannot declare it as variable as we did in case of integer

and float. The void data type is usually used with function to specify its type.

Program to finding TRANSPOSE matrix of a matrix

deveshucer@gmail.com (Devesh) — Fri, 23 Dec 2011 20:27:00 +0000

//program to transpose a matrix//

#include<stdio.h>
#include<conio.h>
#define max 5
void main()
{
int i,j,m,n,a[max][max],b[max][max];
clrscr();
printf("\t\t\t**** TRANSPOSE OF A MATRIX ****");
printf("\nEnter the no. of rows & coloumns:\n");
scanf("%d%d",&m,&n);
printf("Enter the elements of matrix:\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
b[j][i]=a[i][j];
}
}
printf("\nInputed Matrixes is:\n\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("%-4d\t",a[i][j]); //4 digit right alignment
}
printf("\n");
}
printf("\nTransposed matrix is:\n\n");
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
printf("%-4d\t",b[i][j]); //4 digit right alignment
}
printf("\n");
}
getch();
}

//Snap shot of output...

MULTIPLICATION of Two Matrices

deveshucer@gmail.com (Devesh) — Fri, 23 Dec 2011 20:20:00 +0000

// *****MULTIPLICATION of Two Matrices*****//
#include<stdio.h>
#include<conio.h>
void main()
{
int i,j,sum,a[10][10],b[10][10],c[10][10],m,n,k=0;
clrscr();
printf(" *** MULTIPLICATION OF TWO MATRIXES ***");
printf("\nEnter the no. of rows & coloumns :\n");
scanf("%d%d",&m,&n);
if(m!=n)
printf("\nEnter The same no. of rows & coloumns !");
else
{
printf("Enter the elements of 1st matrix :\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
}
printf("Enter the elements of 2nd matrix :\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
scanf("%d",&b[i][j]);
}
{
while(k<n)
{
sum=0;
for(i=0;i<m;i++)
{
for (j=0;j<n;j++)
{
for(k=0;k<n;k++)
sum=sum+a[i][k]*b[k][j];
c[i][j]=sum;
sum=0;
}
}
}
printf("Result- Multipliccation of two Matrixes :\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
printf("%d\t",c[i][j]);
{
printf("\n");
}
}
}
printf("\nThanks ! For using my Program.");
getch();
}
}

//Snap shot of output...

A Program for ADDITION of two matrix

deveshucer@gmail.com (Devesh) — Fri, 23 Dec 2011 20:13:00 +0000

//*****A program for ADDITION of two matrixes*****//

#include<stdio.h>
#include<conio.h>
void main()
{
int i,j,a[10][10],b[10][10],c[10][10],m,n;
clrscr();
printf("\t\t *** ADDITION OF MATRIXES ***");
printf("\nEnter the no. of row & coloumn :\n");
scanf("%d%d",&m,&n);
printf("Enter the elements of 1st matrix:\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
}
printf("Enter the element of 2nd matrix :\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
scanf("%d",&b[i][j]);
}
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
c[i][j]=a[i][j]+b[i][j];
}
printf("Addition of both matirxes is :\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
printf("%d\t",c[i][j]);
{
printf("\n");
}
}
printf("\nThanks! for using the programe.......@Devesh");
getch();

}

//output look like this....

BST Creation, Insertion and Display

deveshucer@gmail.com (Devesh) — Mon, 12 Dec 2011 19:53:00 +0000

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

struct searchtree
{
int element;
struct searchtree *left,*right;
}*root;
typedef struct searchtree *node;
typedef int ElementType;

node insert(ElementType, node);
void makeempty();
void display(node, int);
void makeempty()
{
root = NULL;
}

void main()
{
int ch;
ElementType a;
makeempty();
while(1)
{

printf("\n1. Insert\n2. Display\n3. Exit\n");
printf("\nEnter Your Choice : ");
scanf("%d",&ch);
switch(ch)
{

case 1:
printf("Enter an element : ");
scanf("%d", &a);
root = insert(a, root);
break;
case 2: if(root==NULL)
printf("\nEmpty tree");
else display(root, 1);
break;
case 3: exit(0);
default:printf("Invalid Choice");
}
}
}
node insert(ElementType x, node t)
{
if( t == NULL)
{
t = (node)malloc(sizeof(node));
t->element = x;
t->left = t->right = NULL;

}else
{
if(x < t->element) t->left = insert(x, t->left);
else if(x > t->element) t->right = insert(x, t->right);
}
return t;
}

void display(node t,int level)
{
int i;
if(t)
{

display(t->right, level+1);
printf("\n");
for(i=0;i<level;i++)

printf(" ");
printf("%d", t->element);
display(t->left, level+1);

}

}

Output look like this :

Human face or Smiley program in java using Applet

deveshucer@gmail.com (Devesh) — Sat, 10 Dec 2011 09:02:00 +0000

import java.awt.*;
import java.applet.*;

public class HumanFace extends Applet{
private int mouseX, mouseY;
private boolean mouseclicked = false;
public void init(){
setBackground(Color.GREEN);
}

public void paint(Graphics g)
{
g.setColor(Color.YELLOW);
g.fillOval(40,40,120,150);
g.setColor(Color.BLACK);
g.drawOval(57,75,30,30);
g.drawOval(110,75,30,30);
g.fillOval(68,81,10,10);
g.fillOval(121,81,10,10);
g.setColor(Color.RED);
g.drawLine(100,100,100,130);
g.fillRect(75,140,50,7);
if (mouseclicked) {
g.clearRect(75,140,50,7);
g.setColor(Color.BLUE);
g.fillRect(70,139,60,9);
//g.drawArc(40,100,100,50,0,-120);
mouseclicked = true;
}

}

public boolean mouseDown(Event e, int x, int y )
{
mouseX=x; mouseY=y;
mouseclicked = true;
repaint();
return true;
}
}
/* <applet code="HumanFace.class" height= "300" width="200" >
</applet> */

//Output look like this...

Clock applet program in java

deveshucer@gmail.com (Devesh) — Sat, 12 Nov 2011 18:59:00 +0000

import java.util.*;
import java.awt.*;
import java.applet.*;
import java.text.*;

/**
* programmingwithdev.blogspot.com
* clock applet program
**/
public class Clock extends Applet implements Runnable {
private volatile Thread timer; // The thread that displays clock
private int lastxs, lastys, lastxm,
lastym, lastxh, lastyh; // Dimensions used to draw hands
private SimpleDateFormat formatter; // Formats the date displayed
private String lastdate; // String to hold date displayed
private Font clockFaceFont; // Font for number display on clock
private Date currentDate; // Used to get date to display
private Color handColor; // Color of main hands and dial
private Color numberColor; // Color of second hand and numbers

public void init() {
int x,y;
lastxs = lastys = lastxm = lastym = lastxh = lastyh = 0;
formatter = new SimpleDateFormat ("EEE MMM dd hh:mm:ss yyyy",
Locale.getDefault());
currentDate = new Date();
lastdate = formatter.format(currentDate);
clockFaceFont = new Font("Serif", Font.PLAIN, 14);
handColor = Color.blue;
numberColor = Color.red;

try {
setBackground(new Color(Integer.parseInt(getParameter("bgcolor"),
16)));
} catch (NullPointerException e) {
} catch (NumberFormatException e) {
}
try {
handColor = new Color(Integer.parseInt(getParameter("fgcolor1"),
16));
} catch (NullPointerException e) {
} catch (NumberFormatException e) {
}
try {
numberColor = new Color(Integer.parseInt(getParameter("fgcolor2"),
16));
} catch (NullPointerException e) {
} catch (NumberFormatException e) {
}
resize(300,300); // Set clock window size
}

// Paint is the main part of the program
public void paint(Graphics g) {
int xh, yh, xm, ym, xs, ys;
int s = 0, m = 10, h = 10;
int xcenter = 80, ycenter = 55;
String today;

currentDate = new Date();

formatter.applyPattern("s");
try {
s = Integer.parseInt(formatter.format(currentDate));
} catch (NumberFormatException n) {
s = 0;
}
formatter.applyPattern("m");
try {
m = Integer.parseInt(formatter.format(currentDate));
} catch (NumberFormatException n) {
m = 10;
}
formatter.applyPattern("h");
try {
h = Integer.parseInt(formatter.format(currentDate));
} catch (NumberFormatException n) {
h = 10;
}

// Set position of the ends of the hands
xs = (int) (Math.cos(s * Math.PI / 30 - Math.PI / 2) * 45 + xcenter);
ys = (int) (Math.sin(s * Math.PI / 30 - Math.PI / 2) * 45 + ycenter);
xm = (int) (Math.cos(m * Math.PI / 30 - Math.PI / 2) * 40 + xcenter);
ym = (int) (Math.sin(m * Math.PI / 30 - Math.PI / 2) * 40 + ycenter);
xh = (int) (Math.cos((h*30 + m / 2) * Math.PI / 180 - Math.PI / 2) * 30
+ xcenter);
yh = (int) (Math.sin((h*30 + m / 2) * Math.PI / 180 - Math.PI / 2) * 30
+ ycenter);

// Draw the circle and numbers
g.setFont(clockFaceFont);
g.setColor(Color.blue);
g.drawArc(xcenter-50, ycenter-50, 100, 100, 10, 360);
g.setColor(numberColor);
g.drawString("9", xcenter-45, ycenter+3);
g.drawString("3", xcenter+40, ycenter+3);
g.drawString("12", xcenter-5, ycenter-37);
g.drawString("6", xcenter-3, ycenter+45);

// Get the date to print at the bottom
formatter.applyPattern("EEE MMM dd HH:mm:ss yyyy");
today = formatter.format(currentDate);

// Erase if necessary
g.setColor(getBackground());
if (xs != lastxs || ys != lastys) {
g.drawLine(xcenter, ycenter, lastxs, lastys);
g.drawString(lastdate, 5, 125);
}
if (xm != lastxm || ym != lastym) {
g.drawLine(xcenter, ycenter-1, lastxm, lastym);
g.drawLine(xcenter-1, ycenter, lastxm, lastym);
}
if (xh != lastxh || yh != lastyh) {
g.drawLine(xcenter, ycenter-1, lastxh, lastyh);
g.drawLine(xcenter-1, ycenter, lastxh, lastyh);
}

// Draw date and hands
g.setColor(Color.black);
g.drawString(today, 5, 125);
g.drawLine(xcenter, ycenter, xs, ys);
g.setColor(handColor);
g.drawLine(xcenter, ycenter-1, xm, ym);
g.drawLine(xcenter-1, ycenter, xm, ym);
g.drawLine(xcenter, ycenter-1, xh, yh);
g.drawLine(xcenter-1, ycenter, xh, yh);
lastxs = xs; lastys = ys;
lastxm = xm; lastym = ym;
lastxh = xh; lastyh = yh;
lastdate = today;
currentDate = null;
}

public void start() {
timer = new Thread(this);
timer.start();
}

public void stop() {
timer = null;
}

public void run() {
Thread me = Thread.currentThread();
while (timer == me) {
try {
Thread.currentThread().sleep(100);
} catch (InterruptedException e) {
}
repaint();
}
}

public void update(Graphics g) {
paint(g);
}

public String getAppletInfo() {
return "Title: A Clock \n"
+ "Author: Rachel Gollub, 1995 \n"
+ "An analog clock.";
}

public String[][] getParameterInfo() {
String[][] info = {
{"bgcolor", "hexadecimal RGB number",
"The background color. Default is the color of your browser."},
{"fgcolor1", "hexadecimal RGB number",
"The color of the hands and dial. Default is blue."},
{"fgcolor2", "hexadecimal RGB number",
"The color of the second hand and numbers. Default is dark gray."}
};
return info;
}
}

/* <applet code="Clock.class" height = "300" width = "200" >
</applet>
*/

My Clock

My Applet Clock

Binary Search Tree (BST) Operations

deveshucer@gmail.com (Devesh) — Tue, 08 Nov 2011 17:38:00 +0000

// BST.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <cstdlib>
using namespace std;

class BinarySearchTree
{
private:
struct tree_node
{
tree_node* left;
tree_node* right;
int data;
};
tree_node* root;
public:
BinarySearchTree()
{
root = NULL;
}
bool isEmpty() const { return root==NULL; }
void print_inorder();
void inorder(tree_node*);
void print_preorder();
void preorder(tree_node*);
void print_postorder();
void postorder(tree_node*);
void insert(int);
void remove(int);
void search(int);
};

// Smaller elements go left
// larger elements go right
void BinarySearchTree::insert(int d)
{
tree_node* t = new tree_node;
tree_node* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;
// is this a new tree?
if(isEmpty()) root = t;
else
{
//Note: ALL insertions are as leaf nodes
tree_node* curr;
curr = root;
// Find the Node's parent
while(curr)
{
parent = curr;
if(t->data > curr->data) curr = curr->right;
else curr = curr->left;
}

if(t->data < parent->data)
parent->left = t;
else
parent->right = t;
}
}

void BinarySearchTree::remove(int d)
{
//Locate the element
bool found = false;
if(isEmpty())
{
cout<<" This Tree is empty! "<<endl;
return;
}
tree_node* curr;
tree_node* parent;
curr = root;
while(curr != NULL)
{
if(curr->data == d)
{
found = true;
break;
}
else
{
parent = curr;
if(d>curr->data) curr = curr->right;
else curr = curr->left;
}
}
if(!found)
{
cout<<" Data not found! "<<endl;
return;
}

// 3 cases :
// 1. We're removing a leaf node
// 2. We're removing a node with a single child
// 3. we're removing a node with 2 children

// Node with single child
if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL&& curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{
if(parent->left == curr)
{
parent->left = curr->right;
delete curr;
}
else
{
parent->right = curr->right;
delete curr;
}
}
else // left child present, no right child
{
if(parent->left == curr)
{
parent->left = curr->left;
delete curr;
}
else
{
parent->right = curr->left;
delete curr;
}
}
return;
}

//We're looking at a leaf node
if( curr->left == NULL && curr->right == NULL)
{
if(parent->left == curr) parent->left = NULL;
else parent->right = NULL;
delete curr;
return;
}

//Node with 2 children
// replace node with smallest value in right subtree
if (curr->left != NULL && curr->right != NULL)
{
tree_node* chkr;
chkr = curr->right;
if((chkr->left == NULL) && (chkr->right == NULL))
{
curr = chkr;
delete chkr;
curr->right = NULL;
}
else // right child has children
{
//if the node's right child has a left child
// Move all the way down left to locate smallest element

if((curr->right)->left != NULL)
{
tree_node* lcurr;
tree_node* lcurrp;
lcurrp = curr->right;
lcurr = (curr->right)->left;
while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}
curr->data = lcurr->data;
delete lcurr;
lcurrp->left = NULL;
}
else
{
tree_node* tmp;
tmp = curr->right;
curr->data = tmp->data;
curr->right = tmp->right;
delete tmp;
}

}
return;
}

}

void BinarySearchTree::print_inorder()
{
inorder(root);
}

void BinarySearchTree::inorder(tree_node* p)
{
if(p != NULL)
{
if(p->left) inorder(p->left);
cout<<" "<<p->data<<" ";
if(p->right) inorder(p->right);
}
else return;
}

void BinarySearchTree::print_preorder()
{
preorder(root);
}

void BinarySearchTree::preorder(tree_node* p)
{
if(p != NULL)
{
cout<<" "<<p->data<<" ";
if(p->left) preorder(p->left);
if(p->right) preorder(p->right);
}
else return;
}

void BinarySearchTree::print_postorder()
{
postorder(root);
}

void BinarySearchTree::postorder(tree_node* p)
{
if(p != NULL)
{
if(p->left) postorder(p->left);
if(p->right) postorder(p->right);
cout<<" "<<p->data<<" ";
}
else return;
}

int main()
{
BinarySearchTree b;
int ch,tmp,tmp1;
while(1)
{
cout<<endl<<endl;
cout<<" Binary Search Tree Operations "<<endl;
cout<<" ----------------------------- "<<endl;
cout<<" 1. Insertion/Creation "<<endl;
cout<<" 2. In-Order Traversal "<<endl;
cout<<" 3. Pre-Order Traversal "<<endl;
cout<<" 4. Post-Order Traversal "<<endl;
cout<<" 5. Removal "<<endl;
cout<<" 6. Exit "<<endl;
cout<<" Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1 : cout<<" Enter Number to be inserted : ";
cin>>tmp;
b.insert(tmp);
break;
case 2 : cout<<endl;
cout<<" In-Order Traversal "<<endl;
cout<<" -------------------"<<endl;
b.print_inorder();
break;
case 3 : cout<<endl;
cout<<" Pre-Order Traversal "<<endl;
cout<<" -------------------"<<endl;
b.print_preorder();
break;
case 4 : cout<<endl;
cout<<" Post-Order Traversal "<<endl;
cout<<" --------------------"<<endl;
b.print_postorder();
break;
case 5 : cout<<" Enter data to be deleted : ";
cin>>tmp1;
b.remove(tmp1);
break;
case 6 : system("pause");
return 0;
break;
}
}
}

/*Note :: This solution works on visual studio platform if you want to run in another platform then be careful it needs some modification in main */

Data Types in C Language

deveshucer@gmail.com (Devesh) — Fri, 14 Oct 2011 21:15:00 +0000

A programming language is proposed to help programmer to process certain kinds of data and to
provide useful output. The task of data processing is accomplished by executing series of commands
called program. A program usually contains different types of data types (integer, float, character
etc.) and need to store the values being used in the program. C language is rich of data types. A C
programmer has to employ proper data type as per his requirements.
C has different data types for different types of data and can be broadly classified as:
1. Primary Data Types
2. Secondary Data Types