ABOUT BLOG & AUTHORS

April 1, 2008

######…DATASTRUCTURES…######

………The Team Work of Bhanu,Swarna & Karthik    

 

Hi we are Studying 4th B.tech C.S.E.

in Sri Venkateswara University College of Engineering,Tirupati.This Blog is about the Datastructures.The C++ Programming Code is GIven.It is under DevelopmentSoon We Will Finish and Improve Further.

Please Visit and Comment on it(This blog will appear in google search just type ‘codefords’)
……………..Thank you visit again

CLICK HERE TO GOTO CONTENTS HOME PAGE

    

INTRODUCTION

April 1, 2008

HOME

Datastructures:
Data structures involve the organizing the data in different methods and performing the operations on these structures.

Datastructures are categorized as shown in fig:


Primitive Datastructures:
These are the datastructures which are directly supported by the machine.i.e.Any operation can be performed in these data items.
Eg:Integers,Real numbers,datatype involving characters

and some logical statements.

Non-primitive Datastructures:
These Datastructures do not allow any specific instructions to be performed on the Data items directly.
Eg: The set of Complex numbers

Linear Datastructures:
This DataStructures involve arranging the elements in Linear fashion.
Eg:Stacks,Queue,Lists.

Non-Linear Datastructures:
This Datastructures involve representing the elements in Hierarchical order.
Eg: Trees, Graphs

HOME

LINKED LIST

April 1, 2008

HOME

Linked list:

In order to store elements in the sequential
fashion we use Arrays. But they are fixed max
size,suppose if we want to use less memory than
that of fixed size then memory is wastaged, or
If we want to use more memory than that of fixed
size then deficiency of the memory will be the
problem.

In order to overcome all these type of problem
we use dynamically allocated memory ,which can
be allocated at run time called as node, so the
sequential arrangement of nodes are called linked
lists.

There are 2 types Single linkedlist and Double

linkedlist

HOME

STACKS

April 1, 2008

HOME

Stacks:
Stack is nothing but a list of elements where insertion and deletion are possible at one end i.e. stack top.

It follows Last In First Out [LIFO] property.

Stacks are represented using Arrays and Linked lists.


HOME

QUEUES

April 1, 2008

HOME

Queues:
Queue is also a list of elements with insertion is permitted at one end called rear end and deletion permitted at another end called front end.

It follows the property of First In First Out [FIFO].

Queues also implemented using Arrays and Linked

lists.

HOME

TREES

April 1, 2008

HOME


Definition of a Tree:

A tree is a set of one or more nodes T such that:
(i).There is a specially designated node called a root
(ii).The remaining nodes are partitioned into n disjointed
set of nodes T1, T2,…,Tn, each of which is a tree.

Degree of a Node of a Tree:
The degree of a node of a tree is the number of subtrees having this node as a root. In other words,the degree is the number of descendants of a node. If the degree is zero, it is called a terminal or leaf node of a tree.

Degree of a Tree:
The degree of a tree is defined as the maximum of degree of the nodes of the tree, that is, degree of tree = max(degree(node i) for I = 1 to n)

Level of a Node:
We define the level of the node by taking the level of the root node as 1, and incrementing it by 1 as we move from the root towards the subtrees.We then define the depth of the tree to be the maximum value of the level of the node of the tree.

Binary tree:
A tree T is finite set of nodes, such that
(i).T is empty(called Empty binary tree),
(ii).T contains specially designed node called the root
of T,and the remaining nodes of T form T1 and T2
which are called as left subtree and right subtree.

Binary Search Tree:
Def:
A Binary Tree is said to be Binary Search Tree, the values in the left subtree should be less than that of root element and the values in the right subtree should be greater than that of root element.


Tree Traversals:
Traversing is nothing but visiting all the nodes of a Tree exactly once.
In-order Traversal:
•visit left sub tree of the Root node using In-order traversal
•visit Root node
•visit right sub tree of the Root node using In-order traversal

Pre-order Traversal:
•visit Root node
•visit left sub tree of the Root node using Pre-order Traversal
•visit right sub tree of the Root node using Pre-order Traversal

Post-order Traversal:
•visit left sub tree of the Root node using Post-order Traversal
•visit right sub tree of the Root node using Post-order Traversal
•visit Root node

HOME

BINARY_TREE

March 29, 2008

BINARY TREE OPERATIONS

HOME
 
/*….PROGRAM
TO IMPLEMENT OPERATIONS

         
           
    ON THE BINARY TREE…*/

#include<iostream.h>
#include<conio.h>

class
tree;

class
stack //CLASS

NAME
{
  
 tree* pointer;

  
 stack *top;

public:
  
 stack()     

  
 {

  
 top=NULL;

  
 }

  
 void push(tree* i) //FUNCTION
TO PUSH

  
 {

  
 stack *p;

  
 p= new stack;

  
 p->pointer =i;

  
 p->top = top;

  
 top = p;

  
 }

  
 tree* pop() //FUNCTION
TO POP

  
 {

  
 tree* temp;

  
 stack *tempp;

  
 temp  = top->pointer;

  
 tempp = top->top;

  
 delete top;

  
 top = temp;

  
 return temp;

  
 }

  
 int empty();

};

int
stack::empty()

{
  
 if(top == NULL)

  
     return 1;

  
 return 0;

}

class
tree

{
  
 int data;

  
 tree* left;

  
 tree* right;

public:
  
 tree()

  
 {

  
 left = NULL;

  
 right = NULL;

  
 data =0;

  
 }

  
 

void
build_tree()//FUNCTION
TO BUILD BINARY TREE

{
  
 char option;

  
 cout<<“ENTER THE ELEMENT: “;

  
 cin >> data;

  
 cout<<“DO YOU WANT TO ADD LEFT
 SUBTREE =>”<<data<<”
(y/n)”;

  
 cin >>option;

  
 if(option ==’y’||option==’Y’)

  
 {

  
 cout<<“enter left tree: “<<endl;

  
 left = new tree;

  
 left->build_tree();//RECURSIVE CALLING

  
 }

cout<<“DO
YOU WANT TO ADD RIGHT
 SUBTREE =>”<<data<<” (y/n)
“;
  
 cin >>option;

if(option
==’y’||option==’Y’)

  
 {

  
 cout<<“enter right tree: “<<endl;

  
 right = new tree;

  
 right->build_tree();

  
 }

  
 }

void
pre_order()//FUNCTION
FOR PREORDER TRAVERSAL

{
 stack
s;

 tree
*p;

 cout<<endl;
 s.push(this);

 while(!s.empty())
 {
 p
= s.pop();

 while(p
!= NULL)

 {
 cout<<p->data<<
” “;

 if(p->right
!= NULL)

 s.push(p->right);
 p
= p->left;

 }
 }
 }
void
in_order()//FUNCTION
FOR THE INORDER TRAVERSAL

{
  
 stack s;

  
 tree *p;

  
 cout<<endl;

  
 p = this;

while(p
!= NULL || !s.empty())

{
  
 while( p!= NULL)

  
 {

  
 s.push(p);

  
 p = p->left;

  
 }

if(!s.empty())
  
 {

  
 p = s.pop();

  
 cout<<p->data<<” “;

  
 p = p->right;

  
 }

}
  
 }

//FUNCTION
FOR POSTORDER TRAVERSAL

void
post_order()

  
 {

  
 stack s;

  
 tree *p;

  
 cout<<endl;

  
 p = this;

  
 while(1)

  
 {

  
 while( p != NULL)

  
 {

  
     p->data =
-p->data;

  
     s.push(p);

  
     p = p->left;

  
 }

  
 if(s.empty())

  
     return;

  
 p = s.pop();

  
 while(p->data > 0)

  
 {

  
 cout<<p->data<<” “;

  
 if(s.empty())

  
 return;

  
 p= s.pop();

  
 }

  
 p->data = -p->data;

  
 s.push(p);

  
 p = p->right;

  
 }

  
 }

};

//main()
FUNCTION STARTS

void
main()

{
  
 tree t;//OBJECT
CREATION

  
 cout<<” (ROOT)  “;

  
 

  
 t.build_tree();

cout<<endl<<“PRE-ORDER
TRAVERSAL

          
OF GIVEN TREE: “;

  
 t.pre_order();

cout<<endl<<“IN-ORDER
TRAVERSAL

          &nbs

p; 
OF GIVEN TREE: “;
  
 t.in_order();

cout<<endl<<“POST-ORDER
TRAVERAL

          &nbs

p; 
OF GIVEN TREE: “;
  
 t.post_order();

}
//PROGRAM
ENDS

/*   
 

 OUTPUT:

(ROOT)  ENTER THE
ELEMENT: 100

DO
YOU WANT TO ADD LEFT

        
SUBTREE =>100 (y/n)Y

enter
left tree:

ENTER
THE ELEMENT: 70

DO
YOU WANT TO ADD LEFT

          
SUBTREE =>70 (y/n)N

DO
YOU WANT TO ADD RIGHT

          
SUBTREE =>70 (y/n) Y

enter
right tree:

ENTER
THE ELEMENT: 35

DO
YOU WANT TO ADD LEFT

           
SUBTREE =>35 (y/n)N

DO
YOU WANT TO ADD RIGHT

          
SUBTREE =>35 (y/n) n

DO
YOU WANT TO ADD RIGHT

        
SUBTREE =>100 (y/n) y

enter
right tree:

ENTER
THE ELEMENT: 125

DO
YOU WANT TO ADD LEFT

        
SUBTREE =>125 (y/n)Y

enter
left tree:

ENTER
THE ELEMENT: 56

DO
YOU WANT TO ADD LEFT

       
SUBTREE =>56 (y/n)N

DO
YOU WANT TO ADD RIGHT

        
SUBTREE =>56 (y/n) N

DO
YOU WANT TO ADD RIGHT

           
SUBTREE =>125 (y/n) Y

enter
right tree:

ENTER
THE ELEMENT: 78

DO
YOU WANT TO ADD LEFT

       
SUBTREE =>78 (y/n)N

DO
YOU WANT TO ADD RIGHT

        
SUBTREE =>78 (y/n) N

PRE-ORDER
TRAVERSAL OF

         
GIVEN TREE:

100
70 35 125 56 78

IN-ORDER
TRAVERSAL OF

         
GIVEN TREE:

70
35 100 56 125 78

POST-ORDER
TRAVERAL OF

        
GIVEN TREE:

35
70 56 78 125 100

 Press
any key to continue  */

HOME

HEAP_TREE

March 27, 2008

HOME

/* PROGRAM TO IMPLEMENT HEAPTREE #include "iostream.h" #define SIZE 100 class heap { private: int a[SIZE]; void siftup(int i); void siftdown(int i); public: heap(); void build_heap(); void insert(int num); int deletemin(); void put_data(); int empty(); }; heap::heap() { int i; a[0] =0; // no. of elements in the heap for(i=1; i<SIZE; i++) a[i] = -1; } void heap::siftup(int i) { //i is the index of heap element to be sifted up int temp = a[i]; int p = i/2; //parent index while(temp1) { a[i] = a[p]; i =p; p= i/2; } a[i] = temp; } void swap(int &a,int &b) { int temp; temp =a; a = b; b = temp; } void heap::siftdown(int i) { int lchild = 2*i; int rchild = 2*i+1; while(a[rchild] != -1) { if(a[lchild] < a[i] && a[lchild] <= a[rchild]) { swap(a[lchild],a[i]); i = lchild; lchild = 2*i; rchild = 2*i+1; } else if(a[rchild] < a[i] && a[rchild] <a[lchild]) { swap(a[rchild],a[i]); i = rchild; lchild = 2*i; rchild = 2*i+1; } else break; } if(a[lchild] != -1 && a[lchild] < a[i]) swap(a[lchild],a[i]); } void heap::build_heap() { int n,i; cout<<endl<>n; a[0] = n; cout<<endl<<"enter the elements: "; //build complete binary tree for(i=1; i>a[i]; //heapify the binary tree for(i = n/2; i>=1; i--) siftdown(i); } void heap::insert(int num) { int n; n = ++a[0]; if(n > SIZE) { cout<<"memory limit exceeded. no insertion performed."; a[0]--; return; } a[n] = num; siftup(n); } int heap::deletemin() { int n,temp; if(a[0] == 0) { cout<<"empty heap. no deletion possible."; return -1; } temp = a[1]; n = a[0]--; a[1] = a[n]; siftdown(1); return temp; } void heap::put_data() { int i; cout<<endl; cout<<"the heap is: "; cout<<endl; for(i=1; i<=a[0]; i++) cout<<" "<<a[i]; } int heap::empty() { if(a[0] == 0) return 1; return 0; } void main() { int x; heap h; h.build_heap(); h.put_data(); cout<<endl<>x; h.insert(x); cout<<endl<<"after insertion: "; h.put_data(); cout<<endl<<endl<<"minimum element deleted: "; x = h.deletemin(); cout<<x<<endl; cout<<"after deletion: "; h.put_data(); } //PROGRAM ENDS /*OUTPUT: enter no. of elements in the heap: 9enter the elements: 18 2 13 10 15 3 7 16 8 the heap is: 2 8 3 10 15 13 7 16 18 enter the element to insert: 4 after insertion: the heap is: 2 4 3 10 8 13 7 16 18 15 minimum element deleted: 2 after deletion: the heap is: 3 4 7 10 8 13 15 16 18 Press any key to continue */

HOME

BINARY_SEARCH_TREE

March 27, 2008

BINARY SEARCH TREE

HOME
/*PROGRAM
TO IMPLEMENT BINARY SEARCH TREE*/


#include<iostream.h>
#include<conio.h>

class
tree;

class
stack  //CLASS
DECLARATION

{
  
 tree* pointer;

  
 stack *top;

public:
  
 stack()

  
 {

  
     top=NULL;

  
 }

  
 void push(tree* i)

  
 {

  
     stack *p;

  
     p= new stack;

  
     p->pointer =i;

  
     p->top = top;

  
     top = p;

  
 }

  
 tree* pop()

  
 {

  
     tree* temp;

  
     stack *tempp;

  
     temp  =
top->pointer;

  
     tempp = top->top;

  
     delete top;

  
     top = tempp;

  
     return temp;

  
 }

  
 int empty();

};

int
stack::empty()

{
  
 if(top == NULL)

  
     return 1;

  
 return 0;

}

class
tree

{
  
 int data;

  
 tree* left;

  
 tree* right;

public:
  
 tree()

  
 {

  
     left = NULL;

  
     right = NULL;

  
     data =0;

  
 }

  
 void in_order()

  
 {

  
 stack s;

  
 tree *p;

  
 cout<<endl;

  
 p = this;

  
 while(p != NULL || !s.empty())

  
 {

  
 while( p!= NULL)

  
 {

  
 s.push(p);

  
 p = p->left;

  
 }

  
 if(!s.empty())

  
 {

  
 p = s.pop();

  
 cout<<p->data<<” “;

  
 p = p->right;

  
 }

       
}

  
 }

  
 void pre_order()

  
 {

  
 stack s;

  
 tree *p;

  
 cout<<endl;

  
 s.push(this);

  
 while(!s.empty())

  
 {

  
 p = s.pop();

  
 while(p != NULL)

  
 {

  
 cout<<p->data<< ” “;

  
 if(p->right != NULL)

  
 s.push(p->right);

  
 p = p->left;

  
 }

  
 }

  
 }

  
 void post_order()

  
 {

  
 stack s;

  
 tree *p;

  
 cout<<endl;

  
 p = this;

  
 while(1)

  
 {

  
 while( p != NULL)

  
 {

  
 p->data = -p->data;

  
 s.push(p);

  
 p = p->left;

  
 }

  
         

    
if(s.empty())

  
 return;

  
 p = s.pop();

  
 while(p->data > 0)

  
 {

  
 cout<<p->data<<” “;

  
 if(s.empty())

  
 return;

  
 p= s.pop();

  
 }

  
 p->data = -p->data;

  
 s.push(p);

  
 p = p->right;

  
 }

  
 }

  
 

  
 void deletion(int i)

  
 {

  
 int flag=0;

  
 tree *p,*q;

  
 p = this;

  
 while( p!= NULL)

  
 {

  
  if(i < p->data)

  
 {

  
 q=p;

  
 p= p->left;

  
 }

       
else if(i > p->data)

  
 {

  
 q=p;

  
 p=p->right;

  
 }

  
  else if(i== p->data)

  
 {

  
 flag=1;

  
 break;

  
 }

       
}

  
 if(flag == 0)

  
 {

  
 cout<<endl<<i<<”
not in the list.

          &nb

sp;           &n

bsp; 
no deletion performed.”;
  
 return;

  
 }

          &nb

sp;   // if deleting
element is root

  
 if(i == data)    

  
 {

  
 if(p->right == NULL)

  
 {//replace
with in-order predecessor

  
 int temp;

  
 temp =p->left->max();

  
 p->deletion(temp);

  
 p->data = temp;

  
 return;

  
 }

  
 else if(p->left == NULL)

  
 {//replace
with in-order successor

  
 int temp;

  
 temp = p->right->min();

  
 p->deletion(temp);

  
 p->data = temp;

  
 return;

  
 }

  
 }

  
 // p has no
children.

  
 if(p->right == NULL && p->left
== NULL)

  
 {

  
 if(q->right == p)

  
 q->right = NULL;

  
 else

  
 q->left  = NULL;

  
 delete p;

  
 }

  
 //p has
only one child.

  
 else if( p->right == NULL)

  
 {

  
 if(q->right == p)

  
 q->right = p->left;

  
 else

  
 q->left  = p->left;

  
 delete p;

  
 }

  
 else if( p->left == NULL)

  
 {

  
 if(q->right == p)

  
 q->right = p->right;

  
 else

  
 q->left  = p->right;

  
 delete p;

  
 }

  
 //p have
both children.

  
 else

  
 {

  
  int temp;

  
  temp = p->left->max();

  
  p->deletion(temp);

  
  p->data = temp;

  
 }

  
 }

  
 int max()

  
 {

  
 tree *p = this;

  
 while(p->right != NULL)

  
       
 p = p->right;

  
 return p->data;

  
 }

  
 int min()

  
 {

  
 tree *p = this;

  
     

  
 while(p->left != NULL)

  
       
 p = p->left;

  
 return p->data;

  
 }

  
 void insert(int i)

  
 {

  
 if(data == 0)//null
tree checking

  
 {

  
 data = i;

  
 return;

  
 }

  
 tree *p = this;

  
 tree *q = this;

  
 tree *temp;

  
 while(p != NULL)

  
 {

  
 q = p;

  
 if(i < p->data )

  
 p = p->left;

  
 else if(i > p->data)

  
 p = p->right;

  
 else

  
 return;

  
 }

  
 temp = new tree;

  
 temp->data = i;

  
 if(i < q->data)

  
 q->left = temp;

  
 else

  
 q->right = temp;

  
 }

};
void
main()

{
  
 tree t;

  
 int i,n,num;

cout<<endl<<“ENTER
THE NO OF  ELEMENTS

          &nb

sp; 
IN THE BINARY SEARCH TREE: “;
  
 cin >>n;

cout<<“ENTER
THE ELEMENTS:\t”;

  
 for(i=0; i<n; i++)

  
 {

  
     cin>>num;

  
     t.insert(num);

  
 }

cout<<“THE
ELEMENTS IN

          &nb

sp;
THE INORDER TRAVERSAL”;
  
 t.in_order();

cout<<“THE
ELEMENTS IN

          
THE POSTORDER TRAVERSAL\n”;

  
 t.post_order();

cout<<“THE
ELEMENTS IN

         
THE PREORDER TRAVERSAL”;

  
 t.pre_order();

  
 

cout<<“ENTER
THE

          &nb

sp;
ELEMENT TO BE DELETE: “;
  
 cin >>num;

  
 t.deletion(num);

cout<<endl<<“AFTER
DELETION: “;

  
 t.in_order();

}
//program ends
/* output:

ENTER
THE NO OF ELEMENTS IN THE BINARY SEARCH TREE: 5

ENTER
THE ELEMENTS:     1

45
2
67
9

THE
ELEMENTS IN THE INORDER TRAVERSAL

1
2 9 45 67

THE
ELEMENTS IN THE POSTORDER TRAVERSAL

9
2 67 45 1

THE
ELEMENTS IN THE PREORDER TRAVERSAL

1
45 2 9 67 ENTER THE ELEMENT TO BE DELETE: 1

AFTER
DELETION:

2
9 45 67 Press any key to continue

*/

HOME

DEQUEUE

March 27, 2008

DEQUEUE

HOME

/*
PROGRAM FOR ENQUEUEING THE ELEMENTS

 
USING SELF  REFERENTIAL CLASSES   */

#include”iostream.h”

class
queue  //NAME
OF THE CLASS

{
private:     //DATA MEMBERS
  
 int data;

  
 queue *next;

public:  //MEMBER
FUNCTIONS       

  
 int dequeue();

  
 void enqueue(int);  

   
void display();

}
*head; //OBJECT ACTS
AS NODE

//FUNCTION
DECLARATION

void
queue::enqueue(int ele)
{
  
 queue *n,*temp;

   
n=new(queue);  
//MEMORY ALLOCATION

  
 n->data=ele;

  
 n->next=NULL;

//IF
THE LIST IS EMPTY THEN ADD

//1st
NODE AS HEADER NODE

      
if(head==NULL)

  
     head=n;

  
 else

  
 {

  
 temp=head;

  
 while(temp->next!=NULL)

  
 temp=temp->next;

  
  temp->next=n;

  
 }

}
//FUNCTION
FOR DEQUEUEING

int
queue::dequeue()

{
  
 queue *temp;

  
 if(head==NULL)

  
 cout<<“QUEUE IS EMPTY:”;

  
 else

  
 {

  
 temp=head;

  
 head=temp->next;

  
 delete temp;

  
     

  
 }

  
 return(0);

}

//DISPLAY
THE RESULT

void
queue::display()

{
queue 
*temp;

  
 

  
 if(head==NULL)

  
 cout<<” EMPTY\n”;

  
 else

  
 {

  
 temp=head;

  
 while(temp!=NULL)

  
 {

  
         

  
 cout<<temp->data<<endl;

  
 temp=temp->next;

  
 }

  
 }

}

void
main() //main()
FUNCTION STARTS

{
  //INITIALIZATION OF HEADER
NODE

 
head=NULL;

queue
l;//OBJECT OF THE
CLASS List

  
 int x,a[20];

cout<<“ENTER
THE NO OF

     
ELEMENTS TO BE ENQUEUED\n”;

  
 cin>>x;

 cout<<“ENTER
“<<x<<“ELEMENTS\n”;

  
 for(int i=0;i<x;i++)

  
 {

  
     cin>>a[i];

//PASING
THE ELEMENTS TO THE

//
FUNCTION THROUGH OBJECT

    
l.enqueue(a[i]);

  
 }

  
 cout<<“THE LIST IS\n”;

 //CALLING
FUNCTION TO DISPLAY

//RESULT
THROUGH OBJECT

l.display();

  
 for(int j=0;j<x;j++)

  
 {

  
 l.dequeue();

cout<<“AFTER
DELETING THE FRONT

      
END “<<a[j]<<” THE QUEUE IS\n”;

  
 l.display();

  
 }

}

//PROGRAM
ENDS

/*
OUTPUT:

 
ENTER THE NO OF
ELEMENTS TO BE ENQUEUED

5
ENTER
5ELEMENTS

12
34
45
67
89
THE
LIST IS

12
34
45
67
89
AFTER
DELETING THE FRONT

        
END 12 THE QUEUE IS

34
45
67
89
AFTER
DELETING THE FRONT

        
END 34 THE QUEUE IS

45
67
89
AFTER
DELETING THE FRONT

         
END 45 THE QUEUE IS

67
89
AFTER
DELETING THE FRONT

        
END 67 THE QUEUE IS

89
AFTER
DELETING THE FRONT

       
END 89 THE QUEUE IS

 EMPTY
Press
any key to continue

*/

HOME