Showing posts with label Data Structure. Show all posts
Showing posts with label Data Structure. Show all posts

Data Structure - [Binary Tree Example]

♠ Posted by Unknown in ,

The Binary Tree with Example


A tree is a binary tree if each node of it can have at the most two branches. 

A binary tree T is a finite set of nodes, which is either empty or consists of special node called root R and two disjoint binary trees T1 and T2 (which are called the left sub-tree and right sub-trees, respectively). If T1 is non-empty then the root of T1 is called the left successor of R. If T2 is non-empty then the root of T2 is known as right successor of R.

Image: Binary Tree



Recursive algorithm for binary tree creation :


Create_Tree (Info, Node)

Where, 
             Info -> Information for which we have to create node. 
             Node -> structure type variable to points both left and right child.

Step 1: [Check whether the tree is empty]
            If Node = NULL
            Node = Create a node
            Left_Child [Node] = NULL
            Right_Child [Node]] = NULL
Step 2: [Test for the left child]
            If  Info [node] >= Info
            Left_child [Node] = call Create_Tree
(Info, Left_child [Node])
            Else
            Right_child [Node] = call Create_Tree
(info, Right_child [Node])
Step 3: Return (Node)

Recursive algorithm of preorder traversing:


Preorder (Node)

Step 1: [Do through step 3]
            If Node  is not equal to NULL
            Output Info [Node]
Step 2: Call Preorder (Left_child [Node])
Step 3: Call Preorder (Right_child Node])
Step 4: Exit

Recursive algorithm of inorder traversing:

Inorder (Node)

Step 1: [Do through Step 4]
            If  Node is not equal to NULL
Step 2: Call Inorder (Left_Child [Node])
Step 3: Output Info [Node]
Step 4: Call Inorder (Right_child [Node])
Step 5: Exit

Recursive algorithm of postorder traversing:


Postorder (Node)

Step 1: [Do through step 4]
            If Node is not equal to NULL
Step 2: Call Postorder  (Left_Child [Node])
Step 3: Call Postorder (Right_Child Node)
Step 4: Output Info [Node]
Step 5: Exit


Example :

/*program for tree operation*/
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct tree
{
   int no;
   struct tree *r,*l;
};
void insert(struct tree *root,int x);
void preorder(struct tree *root);
void inorder(struct tree *root);
void postorder(struct tree *root);
void main()
{
  struct tree *root = NULL;
  int ch=1,x,level,info;
  root=(struct tree *)malloc(sizeof(struct tree));
  clrscr();
  printf("\n enter the value of root:=");
  scanf("%d",&root->no);
  root->l = root->r=NULL;
  while(ch!=0)
  {
    printf("\n 1:inert\t 2:preorder\t 3:inorder\t 4:postorder");
    printf("\t 0:exit");
    printf("\n\n enter the choice:=");
    scanf("%d",&ch);
    switch(ch)
    {
      case 1:
               printf("\n enter the no");
               scanf("%d",&x);
               insert(root,x);
               break;
      case 2:
               preorder(root);
               break;
      case 3:
               inorder(root);
               break;
      case 4:
               postorder(root);
               break;
    }
  }
}//main over

void insert(struct tree *root,int x)
{
    if(x==root->no)
    {
      printf("\n duplicate no \n\n\n");
      return;
    }
    if(x < root->no)
    {
       if(root->l!=NULL)
             insert(root->l,x);
       else
       {
             root->l=(struct tree*)malloc(sizeof(struct tree));
             root->l->no=x;
             root->l->l=root->l->r=NULL;
       }
    }
    else
    {
      if(root->r!=NULL)
            insert(root->r,x);
      else
      {
            root->r=(struct tree*)malloc(sizeof(struct tree));
            root->r->no=x;
            root->r->r=root->r->l=NULL;
      }
    }
}//insert over

void inorder(struct tree *root)
{
  if(root!=NULL)
  {
    inorder(root->l);
    printf("\n %d",root->no);
    inorder(root->r);
  }
}//inorder over

void preorder(struct tree *root)
{
  if(root !=NULL)
  {
    printf("\n %d",root->no);
    preorder(root->l);
    preorder(root->r);
  }
}//preorder over

void postorder(struct tree *root)
{
  if(root!=NULL)
  {
    postorder(root->l);
    postorder(root->r);
    printf("\n %d",root->no);
  }
}//postorder over
Read More

Data Structure - [Circular Linked List]

♠ Posted by Unknown in ,

Example of Circular Linked List



The node in circular linked list is as like as linear linked list having two rooms one is for storing data and another is storing the reference of next node. Instead of linear list the last node is stored the reference of first node in the "next" room of it.




Image: Circular Linked List

Example: 

#include<stdio.h>
#include<malloc.h>
struct node
{
            int data;
            struct node *next;
};

main()
{
            struct node *front,*rear;
            int ans;
            front = rear = NULL;
            do
            {
                        printf("\n 1.insert node:\n");
                        printf("\n 2.delet node:\n");
                        printf("\n 3.display:\n");
                        printf("\n 4.exit\n");
                        printf("enter choice\n");
                        scanf("%d",&ans);
                        switch(ans)
                        {
                                    case 1:
                                                add(&front,&rear);
                                                break;
                                    case 2:
                                                delet(&front,&rear);
                                                break;
                                    case 3:
                                                display(front);
                                                break;
                                    case 4:
                                                break;
                        }
            }while(ans!=4);
            return;
}

add(struct node **f,struct node **r)
{
            struct node *q;
            int a;
            q=(struct node*)malloc(sizeof(struct node));
            printf("\n enter the value:");
            scanf("%d",&a);
            q->data=a;
            if(*f==NULL)
                        *f=q;
            else
                        (*r)->next=q;
            *r=q;
            (*r)->next=*f;
            return;
}


delet(struct node **f,struct node **r)
{
            struct node *q;
            int a;
            if(*f==NULL)
                        printf("\n list empty");
            else
            {
                        if(*f==*r)
                        {
                                    a=(*f)->data;
                                    free(*f);
                                    *f=NULL;
                                    *r=NULL;
                        }
                        else
                        {
                                    q=*f;
                                    a=q->data;
                                    (*f)=(*f)->next;
                                    (*r)->next=*f;
                                    free(q);
                        }
                        printf("\n deleted node %d",a);
                        return;
            }
       return;
}

display(struct node *f)
{
            struct node *q=f,*p=NULL;
            while(q!=p)
            {
                        printf("%2d\t",q->data);
                        q=q->next;
                        p=f;
            }
            return;
}
Read More

Data Structure - [Example of Sorted Linked List]

♠ Posted by Unknown in ,

Example of Sorted Linked List


#include<stdio.h>
#include<malloc.h>
struct link
{
   int data;
   struct link *next;
};
int i;
int number;

struct link *start, *node, *previous, *new1, *counter;


void main()
{
 link_sort();
}


//User Defined Function (UDF) to sort list
//It is only swap data instead of whole node to sort list
void link_sort()
{
  printf("\n Input the number of node we need to create:");
  scanf("%d",&number);

  start->next = NULL;
  node = start;
  for(i=0;i<number;i++)
  {
    node->next = (struct link*)malloc(sizeof(struct link));
    node = node->next;
    printf("\n Input the first node: %d; ", i+1);
    scanf("%d", &node->data);
    node->next = NULL;
  }
  for(new1 = start; new1->next != NULL; new1 = new1->next)
  {
   for(counter = new1->next; counter !=NULL; counter = counter->next)
    {
     if(new1->data > counter->data)
       {
            int temp = new1->data;
            new1->data = counter->data;
            counter->data = temp;
       }
    }
  }
  node = start->next;
  printf("\n After sorting the list is as follows:\n");
  while(node)
  {
    printf("%d", node->data);
    node = node->next;
  }
}

Read More

Data Structure - [Doubly Linked List]

♠ Posted by Unknown in ,

Doubly Linked list Operations


A doubly linked list is defined as a collection of nodes. Each node has three parts.
1.      Information
2. Pointer to previous node
3.      Pointer to next node


Image: Doubly Linked List Node

Information part may consists of one or more than one fields. In other words a linked list consists of series of structures, which are not necessarily contiguous. Each structure contains one or more than one contiguous information fields and a pointer to a structure containing its successor. The last node of the list contains NULL (‘\0’) in the pointer field. The pointer contains the address of the location where next information is stored.
There are following algorithms for the linked list.


Doubly linked list creation algorithm

Step 1 :  [Initilization]
1)      Start. Next = null
2)      Previous. Next = null
Step 2 :   [Assign address of start variable to node]
               Node = address of start
Step 3 :    [Make left and right links of a node]
1)      Next [node] = node [make link to node]
2)      Previous [node] = node [make link to node]
3)      Node = Next [node] [Move  pointer to next node]
4)      Info [node] = value [Information value of a node]
5)      Next  [node] = NULL  [Assign NULL  to the address field]
Step 4 :    [ Call  Step 3]
                Repeat Step 3 to create required number of nodes for linked list
Step  5 :   End .

Algorithm for traversing a doubly inked list


Step 1 :  [initialization]
              Node = start. Next [points to the first node in the list]
Step 2 :  [Traverse the list in forward direction]
               Repeat while Next [node] # NULL process Info [Node]
Step 3 :  [Traverse the list in backward direction]
               Repeat while Node # NULL  Process Info [Node]
Step 4 :  Exit.

Algorithm to insert a node at right of the right most node

Step 1 :    [Initialization]
                Node =Start
Step 2 :    [Create a new node]
  New = Create  a Node
Step 3 :    [Read information associated with newly created node]
                 Info [Newly] = value
Step 4 :    [Perform the insertion]
 I)  Next [new] = node
II)                  Previous [New] = Previous [node]
III)                Next [Previous[node]] = New
IV)               Next [Node] = New
Step 5 :   Exit

Algorithm to delete right most node

Step 1 : [Initialization]
             Node  = Start
Step 2 : [Initialization counter]
             Counter = 0
Step 3 : [check the list]
             If  Node  = Null
             Output “underflow” and exit
Step 4 : [count the number of nodes available in the list]
             Repeat while Node # NULL
I)                    Node = Next [Node]
II)                  Counter = Counter + 1
Step 5 : [perform deletion]
             Node = Start
             Repeat through (II) while counter # 1
I)                    Node = Next [Node]
II)                  Counter = Counter – 1
III)                Next [previous[node]] = Next [Node]
IV)               Previous [Next [node]] = previous [node]
V)                 Delete (node)
Step 6 : Exit.

Algorithm to delete a desired node

Step 1 : [Initialization]
             Node = Start
Step 2 : [Check the list]
             If node = NULL
             Output “underflow” and Exit
Step 3 : [Set the counter ]
             Search = 0
Step 4 : [Input the node number to which you want to delete]
             Node delete = value
Step 5 : [Perform deletion]
             Repeat while Node # NULL
             If Search = Delete _Node
             Next [Previous [Node]] = Next [Node]
             Previous [Next[Node]] = Previous [Node]
             Delete (Node)
             Else
                   Node = Next [node]
                   Search = Search + 1
Step 6 : Exit


Example:

#include<stdio.h>
#include<malloc.h>
struct dnode
{
            struct dnode *prv;
            int data;
            struct dnode *next;
};

main()
{
            struct dnode *p;
            int ans;
            p=NULL;
            clrscr();
            do
            {
                        printf("\n1:enter new node:\n");
                        printf("2:enter new node at begining:\n");
                        printf("3:enter new node at position:\n");
                        printf("4:display value:\n");
                        printf("5:delete node:\n");
                        printf("6:exit\n");
                        printf("enter your choice :");
                        scanf("%d",&ans);
                        switch(ans)
                        {
                                    case 1:
                                                append(&p);
                                                break;
                                    case 2:
                                                addatbeg(&p);
                                                break;
                                    case 3:
                                                addatpos(&p);
                                                break;
                                    case 4:
                                                display(p);
                                                break;
                                    case 5:
                                                deletatpos(&p);
                                                break;
                                    case 6:
                                                exit(0);
                                                break;
                        }
            }while(ans!=6);
            getch();
            return;
}

append(struct dnode **q)
{
            struct dnode *temp,*r;
            int n;
            temp=(*q);
            if(*q==NULL)
            {
                        *q=(struct dnode*)malloc(sizeof(struct dnode*));
                        (*q)->prv=NULL;
                        (*q)->next=NULL;
                        temp=(*q);
            }
            else
            {
                        while(temp->next!=NULL)
                                    temp=temp->next;
                        r=(struct dnode*)malloc(sizeof(struct dnode));
                        temp->next=r;
                        r->prv=temp;
                        r->next=NULL;
                        temp=temp->next;
            }
            printf("Enter value:");
            scanf("%d",&n);
            temp->data=n;
            return;
}

addatbeg(struct dnode **q)
{
            struct dnode *temp;
            int n;
            temp=(struct dnode*)malloc(sizeof(struct dnode));
            temp->prv=NULL;
            temp->next=*q;
            (*q)->prv=temp;
            printf("Enter value:\n");
            scanf("%d",&n);
            temp->data=n;
            (*q) = (*q)->prv;
            return;
}

addatpos(struct dnode **q)
{
            struct dnode *temp;
            int pos,n,flag=0;
            printf("Enter position:\n");
            scanf("%d",&pos);
            while((*q)->next!=NULL)
            {
                        if((*q)->data==pos)
                        {
                                    flag=1;
                                    break;
                        }
                        else
                        {
                                    flag=0;
                        }
                        (*q)=(*q)->next;
            }



            if(flag==1)
            {
                        printf("enter value :");
                        scanf("%d",&n);
                        temp=(struct dnode*)malloc(sizeof(struct dnode));
                        temp->prv=(*q)->prv->next;
                        (*q)->prv->next=temp;
                        temp->next=*q;
                        (*q)->prv=temp;
                        temp->data=n;
            }
            else
            {
                        printf("element is not available:\n");
            }
            return;
}

deletatpos(struct dnode **q)
{
            struct dnode *temp;
            int n;
            printf("Enter the position:\n");
            scanf("%d",&n);
            temp=*q;
            while(temp->next!=NULL)
            {
                        if(temp->data==n)
                        {
                                    if(temp==*q)
                                    {
                                                (*q)=(*q)->next;
                                                (*q)->prv=NULL;
                                    }
                                    else
                                    {
                                                if(temp->next==NULL)
                                                            temp->prv->next=NULL;
                                                else
                                                {
                                                            temp->prv->next=temp->next;
                                                            temp->next->prv=temp->prv;
                                                            free(temp);
                                                }

                                    }
                        }temp=temp->next;

            }
            return;
}

display(struct dnode *q)
{
            while(q!=NULL)
            {
                        printf("%d ",q->data);
                        q=q->next;
            }
            return;}
Read More