SORTING

WAP TO ENTER 10 NO.S IN AN ARRAY AND ARRANGE THAT NO.S IN ASCENDING ORDER.
    (2nd METHOD- SELECTION SORT) */

#include<stdio.h>
#include<conio.h>
 void main()
 {
int arr[10];
int i,j;
int temp;
int small,pos;

clrscr();

for(i=0;i<10;i++)
{
printf(" Enter value= ");
scanf("%d",&arr[i]);
}
printf("\nUnsorted array -->\n");
for(i=0;i<10;i++)
printf("%d\t",arr[i]);

for(i=0;i<10;i++)
{
small=arr[i];
for(j=i;j<10;j++)
{
if(small>arr[j])
{
small=arr[j];
pos=j;
}
}
temp=arr[i];
arr[i]=arr[pos];
arr[pos]=temp;
}
printf("\nSorted array -->\n");

for(i=0;i<10;i++)
printf("%d\t",arr[i]);

getch();
 }

Stack vs Queue

Stack vs Queue 

Stack is an ordered list in which insertion and deletion of list items can be done only in one end called the top. Due to this reason, stack is considered as a Last in First out (LIFO) data structure. Queue is also an ordered list in which insertion of list items are done in one end called the rear, and the deletion of items are done in the other end called the front. This insertion and deletion mechanism makes the queue a First in First out (FIFO) data structure.

What is Stack?

As mentioned earlier, stack is a data structure in which elements are added and removed from only one end called the top. Stacks allow only two fundamental operations called push and pop. The push operation adds a new element to the top of the stack. The pop operation removes an element from the top of the stack. If the stack is already full, when a push operation is performed, it is considered as a stack overflow. If a pop operation is performed on an already empty stack, it is considered as a stack underflow. Due to the small number of operations that could be performed on a stack, it is considered as a restricted data structure. Additionally, according to the way that the push and pop operations are defined, it is clear that elements that were added last in to the stack go out of the stack first. Therefore stack is considered as a LIFO data structure.

What is Queue?

In a queue, elements are added from the rear of the queue and removed from the front of the queue. Since the elements that are added first will be removed from the queue first, it maintains the FIFO order. Due to this order of adding and removing elements, queue represents the idea of a checkout line. General operations supported by a queue are en-queue and de-queue operations. En-queue operation will add an element at the rear of the queue, while the de-queue operation removes an element from the front of the queue. In general, queues do not have a limit on the number of elements that can be added to the queue besides the memory constraints.

What is the difference between Stack and Queue?

Even though both the stacks and queues are kinds of ordered lists, they have some important differences. In stacks, adding or deleting items can be done only from one end called the top, while in queues adding items is done from one end called the rear and deleting items is done from the other end called the front. In a stack, items that are added last to the stack will be removed first from the stack. Therefore stack is considered as a LIFO data structure. In queues, items that are added first will be removed from the queue first. Therefore queue is considered as a FIFO data structure.

What are the Differences between stack and queue?

• A stack is generally First In, Last Out,  and a queue is First In First Out.
• Data or elements can be added or removed only at one end in stack and in a queue insertion at the rear and deletion from the front.
• The basic operation of stack are 'push' and 'pop', on other hand of queue are 'enque' and 'dequeue'.
•  STACK = LIFO Last In First Out .  
•  Stack is a data dtructure in which addition of new element or deletion of an existing element pop.
•  Stack is also called last-in-first-out list.  

                                  

•  QUEUES = FIFO First In First Out .
• Queues is a linear data structure that permits insertion of new element at one end and deletion of element at the other end. 

What Is a Data Structure?

A data structure is a particular way of storing and organising data in computer so that it can be used efficiently. Data structures make it easy to manage huge amounts of data for instance databases and internet indexing services. Data structures are used in almost every program or software.

Advantage and Disadvantage of singly Linked list and Doubly Linked list

Que-    Advantage and Disadvantage of singly Linked list and Doubly Linked list


SINGLY LINKED LIST
*ADVANTAGE :-
1) Insertions and Deletions can be done easily.
2) It does not need movement of elements for insertion and deletion.
3) It space is not wasted as we can get space according to our requirements.
4) Its size is not fixed.
5) It can be extended or reduced according to requirements.
6) Elements may or may not be stored in consecutive memory available,even then we can store the data in computer.
7) It is less expensive.


*DISADVANTAGE :-
1) It requires more space as pointers  are also stored  with information.
2) Different amount of time is required to access each element.
3) If we have to go to a particular element then we have to go through all those elements that come before that element.
4) we can not traverse it from last & only from the beginning.
5) It is not easy to sort the elements stored in the linear linked list.



-----------------------------------------------------------------------------------------------------------

DOUBLY LINKED LIST

*ADVANTAGE :-

1) We can traverse in both direction i.e from starting to end & as well as from end to starting.
2) It is easy to reverse the linked list.
3) If we are at a node,the we can go at any node.But in linked list,it is not possible to reach the previous node.



*DISADVANTAGE :-

1) It requires more space per space per node because extra field is required for pointer to previous node.
20 Insertion and Deletion take more time than linear linked list because more pointer operations are required than linear linked list. 

Recursive algorithms

What is an recursive algorithm?

A recursive algorithm calls itself which usually passes the return value as a parameter to the algorithm again. This parameter is the input while the return value is the output.

What is an recursive algorithm?

Recursive algorithm is a method of simplification that divides the problem into sub-problems of the same nature. The result of one recursion is the input for the next recursion. The repletion is in the self-similar fashion. The algorithm calls itself with smaller input values and obtains the results by simply performing the operations on these smaller values. Generation of factorial, Fibonacci number series are the examples of recursive algorithms.

Que- write a program to construct B.S.T or it`s traversing algorithm in recursive way.

              #include<stdio.h>

              #include<conio.h>

              #include<process.h>

          

               struct BST*LC;

               int data;

               struct BST*RC;

               struct BST*start=NULL;

               void create( );

               void insert (int d);

               void inorder (struct BST*tmp);

               void preorder(struct BST*tmp);

               void postorder (struct BST*tmp);

               void main( )

               {

               int ch;

               while(1)

               {

               printf("press 1 for create\n");

               printf("press 2 for insert\n");

               printf("press 3 for inorder traversing\n");

               printf("press 4 for preorder traversing\n");

               printf("press 5 for postorder traversing\n");

               printf("press 6 for exit\n");

               printf("enter your choice\n")

               scanf("%d",&ch);

               switch(ch)

               {

               case 1:

               create();

               break;

               case 2:

               printf("enter data\n");

               scanf("%d",&d);

               insert(d);

               break;

               case 3:

              inorder(start);

              getch();

              break;

              case 4:

             preorder(start);

             getch();

             break;

             case 5:

            postorder(start);

            getch();

            break;

void creat()

{

struct BST*tmp;

if(start==NULL)

{

tmp=(struct BST*)malloc(sizeof(struct BST));

tmp-->LC=tmp-->RC=NULL;

printf("enter value\n");

scanf("%d",&tmp-->data);

start=tmp;

}

}

void insert(int d)

{

struct BST* tmp,*tmp1;

tmp=start;

while(1)

{

if(d==tmp-->data)

{

printf("duplicate not allow\n");

return;

}

if(d>tmp-->data)

{

if(tmp-->RC!= NULL)

{

tmp=tmp-->RC;

}

else

{

tmp1=(struct BST*)malloc(sizeof(struct BST));

tmp-->RC=tmp;

tmp-->RC=tmp1-->LC=NULL;

tmp-->data=d;

return;

}

else

{

if(tmp-->LC!=NULL)

{

tmp=tmp-->LC;

}

else

{

tmp1=(struct BST*)malloc(sizeof(struct BST));

tmp1-->LC=tmp1-->RC=NULL;

tmp1-->data=d;

tmp-->LC=tmp;

return;

}

}

}

}

TREE (DATA STRUCTURE)

Binary tree: 

Depth-first

·                    Pre-order traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right) 

·                    In-order traversal sequence: A, B, C, D, E, F, G, H, I (left, root, right) 

·                    Post-order traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root) 

Breadth-first

·          

Implementations

Depth-first

In-order

inorder(node)

  if node == null then return

  inorder(node.left)

  visit(node)

  inorder(node.right)

iterativeInorder(node)

  parentStack = empty stack

  while not parentStack.isEmpty() or node != null

    if node != null then

      parentStack.push(node)

      node = node.left

    else

      node = parentStack.pop()

      visit(node)

      node = node.right

Pre-order

preorder(node)

  if node == null then return

  visit(node)

  preorder(node.left) 

  preorder(node.right)

iterativePreorder(node)

  parentStack = empty stack

  while not parentStack.isEmpty() or node != null

    if node != null then

      visit(node)

      parentStack.push(node.right)

      node = node.left

    else

      node = parentStack.pop()

Post-order

postorder(node)

  if node == null then return

  postorder(node.left)

  postorder(node.right)

  visit(node)

iterativePostorder(node)

 if node == null then return

 nodeStack.push(node)

 prevNode = null

 while not nodeStack.isEmpty()

   currNode = nodeStack.peek()

   if prevNode == null or prevNode.left == currNode or prevNode.right == currNode

     if currNode.left != null

       nodeStack.push(currNode.left)

     else if currNode.right != null

       nodeStack.push(currNode.right)

   else if currNode.left == prevNode

     if currNode.right != null

       nodeStack.push(currNode.right)

   else

     visit(currNode)

     nodeStack.pop()

   prevNode = currNode

Difference Between Static Memory and Dynamic

STATIC MEMORY ALLOCATION	DYNAMIC MEMORY ALLOCATION
Memory is allocated before the execution of the program begins.	Memory is allocated during the execution of the program.
Implemented using stacks and heaps.	Implemented using data segments.
Pointer is needed to accessing variables.	No need of Dynamically allocated pointers.
Faster execution than Dynamic.	Slower execution than static.
More memory Space required.	Less Memory space required.

Circular Linked List (Singly)

Circular Linked List (Singly)




                                                                                                       

#include<conio.h>

#include<alloc.h>
struct list{
 int data;
 struct list *next;
}*head=NULL,*temp,*node;
void infirst(void), inpos(void), inlast(void), delfront(void), delpos(void), dellast(void), display(void), count(void);
int num,pos;
char con;
void main()
{
         printf("\nMain Menu\n1.Insert at first\n2.Insert at specified position\n3.Insert at last\n4.Delete       first\n5.Delete specified position\n6.Delete from last\n7.Display\n8.Count number of nodes\n9.Exit\nEnter choice:");
 scanf("%d",&num);
 switch(num)
 {
       case 1:
                    infirst();
                    break;
      case 2:
                    inpos();
                    break;
     case 3:
                    inlast();
                    break;
    case 4:
                   delfront();
                   break;
   case 5:
                 delpos();
                 break;
  case 6:
                dellast();
                break;
  case 7:
               display();
               break;
  case 8:
               count();
               break;
  case 9:
               clrscr();
               exit();
  default:
              clrscr();
              puts("\nWRONG INPUT!!");
 }
 main();
}
void infirst(void)
{
 do
 {
  printf("\nEnter number:");
  scanf("%d",&num);
  temp=head;
  node=(struct list*)malloc(sizeof(struct list));
  node->data=num;
  node->next=head;
  temp 
  head=temp;
  printf("Continue [y/n]?:");
  con=getche();
 }while(con=='y'||con=='Y');
}
void inpos(void)
{
 do
 {
  num=0;
  temp=head;
  printf("Enter position to insert at:");
  scanf("%d",&pos);
  while(temp->next!=NULL)
  {
   num++;
   if(num==pos-1)
    break;
   temp=temp->next;
  }
  printf("Enter number:");
  scanf("%d",&num);
  node=(struct list*)malloc(sizeof(struct list));
  node->data=num;
  node->next=temp->next;
  temp->next=node;
  printf("Continue [y/n]?:");
  con=getche();
 } while(con=='y'||con=='Y');
}
void inlast(void)
{
 do
 {
  printf("\nEnter number:");
  scanf("%d",&num);
  temp=head;
  while(temp->next!=NULL)
   temp=temp->next;
  node=(struct list *)malloc(sizeof(struct list));
  node->data=num;
  node->next=NULL;
  temp->next=node;
  printf("\nContinue [y/n]?:");
  con=getche();
 } while(con=='y'||con=='Y');
}

void delfront(void)
{
 do{
  if(head==NULL)
  {
   clrscr();
   printf("List is empty!!");
   break;
  }
  else
  {
   temp=head;
   head=temp->next;
   free(temp);
   printf("Continue [y/n]?:");
   con=getche();
  }
 } while(con=='y'||con=='Y');
}
void delpos(void)
{
 do
  {
  if(head==NULL)
  {
   clrscr();
   printf("List is empty!!");
   break;
  }
  else
  {
   num=0;
   temp=head;
   printf("Enter position:");
   scanf("%d",&pos);
   while(temp->next!=NULL)
   {
    num++;
    if(num==pos-1)
    break;
    temp=temp->next;
   }
   node=temp->next->next;
   free(temp->next);
   temp->next=node;
   printf("Continue [y/n]?:");
   con=getche();
  }
 } while(con=='y'||con=='Y');
}
void dellast(void)
{
 do{
  if(head==NULL)
  {
   clrscr();
   printf("List is empty!!");
   break;
  }
  else
  {
   temp=head;
   while(temp->next!=NULL)
   {
    node=temp;
    temp=temp->next;
   }
   node->next=NULL;
   free(temp);
   printf("Continue [y/n]?:");
   con=getche();
  }
 } while(con=='y'||con=='Y');
}
void display(void)
{
 if(head==NULL)
 {
  clrscr();
  printf("List is empty!!");
 }
 else
 {
  clrscr();
  for(temp=head;temp!=NULL;temp=temp->next)
   printf("%d ",temp->data);
 }
}
void count(void)
{
 num=0;
 temp=head;
 while(temp!=NULL)
 {
  num++;
  temp=temp->next;
 }
 clrscr();
 printf("Total number of nodes=%d",num);
}