N.P.R.

COLLEGE OF ENGINEERING & Format

ACD
TECHNOLOGY No.
N.P.R. Nagar, Natham, Dindugul - 624 401, Tamil Nadu Issue No.
(AN ISO 9001:2008 Certified Institution) 01
(Approved by AICTE, New Delhi, Affiliated by Anna University, Tiruchirappalli)
Phone No. : 04544 -305500, 305501,305516,305511 & Fax No.: 04544-305562 Rev. No.
Website: www.nprcet.org, www.nprcolleges.org E-Mail: : nprgc@nprcolleges.org
ISO 9001:2008 00
Lab Manual

Lab Manual

EC303 Data Structures and Object Oriented Programming

Lab
(III Semester ECE)

Faculty Incharge HOD

 LIST OF PROGRAMS

1. Write a c++ program to implement class & Object

2. Write a c++ program to implement the default arguments

3. Write a c++ program to implement List ADT using Array

4. Write a c++ program to implement List ADT using Linked List

5. Write a c++ program to implement Cursor using List ADT

6. Write a c++ program to implement Stack using Array

7. Write a c++ program to implement Stack using List

8. Write a c++ program to implement Queue using Array

9. Write a c++ program to implement Queue using List

10. Write a c++ program to implement Binary search Tree

11. Write a c++ program to implement Heap Sort

12. Write a c++ program to implement Quick Sort

 DEFAULT ARGUMENTS
Aim:

To implement  function with default arguments.

Algorithm:
1.              Declare the default function.
2.              Invoke the default function.
3.              Display the  result
             
Program:
#include<iostream.h>
void printLine(char =’_’,int =70);
void main()
{
printLine();
printLine(‘/’);
printLine(‘*’,40);
printLine(‘R’,55);
}
void printLine(char ch, int Repeatcount)
{
int i;
cout<<endl;
for(i=0;i<Repeatcount;i++)
cout<<ch;
}
 
Output:
 
- - - - - - - -  - - - - - - - - - - - - - - - - - - - - - - - - - - -
///////////////////////////////////////
****************************
RRRRRRRRRRRRRRRRRRRRRRR
 
 
 
 
 
 
 
 
 
  
CLASS AND OBJECTS
Aim:
              To write a c++ program for employee wages calculation using class and objects.
 
Algorithm:
 
1. Employee class contains name and wage variable and member function a
putname(), putwage(),getwage() and getname().
2. Putname: Assign the valve for the character array name.
3. Getname: Retrieves the value of Variable name.
4. Putwage: Assign the valve for wage variable.
5. Getwage: Retrieves the value of wage variable.
6. Im main() Put and display both name and wages.
 
 
 Program:
#include <iostream.h>
using namespace std;
class employee {
char name[80]; // private by default
public:
void putname(char *n); // these are public
void getname(char *n);
private:
double wage; // now, private again
public:
void putwage(double w); // back to public
double getwage();
};
void employee::putname(char *n)
{
strcpy(name, n);
}
void employee::getname(char *n)
{
strcpy(n, name);
}
void employee::putwage(double w)
{
wage = w;
}
double employee::getwage()
{
return wage;
}
int main()
{
employee ted;
char name[80];
ted.putname("Ted Jones");
ted.putwage(75000);
ted.getname(name);
cout << name << " makes $";
cout << ted.getwage() << " per year.";
return 0;
}
 
 
Output:
 
Ted Jones makes $75000 per year.
 
 
 
 
 STACK USING ARRAY IMPLEMENTATION
Aim:
              To write a program for stack using array implementation.
 
Algorithm :

           Step1:Define a array which stores stack elements..

          Step 2: The operations on the stack are

a)PUSH data into the stack
         b)POP data out of stack
 
Step  3:  PUSH DATA INTO STACK
                   3a.Enter the data to be inserted into stack.
                   3b.If TOP is NULL
                         the input data is the first node in stack.
                         the link of the node is NULL.
                        TOP points to that node.
                   3c.If TOP is NOT NULL
                        the link of TOP points to the new node.
                        TOP points to that node.

           Step 4:   POP DATA FROM STACK

                   4a.If TOP is NULL
                        the stack is empty
                   4b.If TOP is NOT NULL
                        the link of TOP is the current TOP.
                        the pervious TOP is popped from stack.

            Step 5.  The stack represented by linked list is traversed to display its content.
 
 PROGRAM:
#include<stdio.h>
#include<conio.h>
#define SIZE 5
int  stack[SIZE],top=-1;
void push();
void pop();
void display();
void main()
{
int choice;
int isempty();
int length();
clrscr();
while(1)
{
              printf(“\n 1.Push”);
              printf(“\n 2. POP”);
              printf(“\n 3.Display”);
              printf(“\n 4. Length ”);
              printf(“\n 5.Quit”);
              printf(“\n Enter the choice:”);
              scanf(“\n %d”,&choice);
              switch(choice)
              {
                            case 1: push();
                                         break;
case 2: pop();
              break;
case 3: display();
             break;
case 4: printf(“\n No. of elements in the stack is %d”,length());
             break;
case 5: exit(0);
             break;
default: printf(“\n Invalid choice”);
                            }
              }
}
 
void push()
{
              int n;
if(top==SIZE-1)
printf(“\n Stack is full”);
else
{
printf(“\nEnter the no.”);
scanf(“%d”,&n);
top++;
stack[top]=n;
}
}
 
void pop()
{
              int n;
              if(isempty())
{
printf(“\nStack is empty”);
 top=-1;
}
else
{
              n=stack[top];             
printf(“\n %d is popped from the stack \n”,n);
--top;
}
}
 
void display()
{
              int i,temp=top;
if(isempty())
{
printf(“\n Stack Empty”);
return;
              }
printf(“\n Elements in the stack:”);
for(i=temp;i>=0;i--)
printf(“%d \n”,stack[i]);
}
 
int isempty()
{
              return (top==-1);
}
int length()
{
              return (top+1);
}
          
 
Output:
 
1.Push
2. POP
3.Display
4. Length
5.Quit
 
Enter the choice: 1
 
Enter the no. 10
 
1.Push
2. POP
3.Display
4. Length
5.Quit
 
Enter the choice: 1
 
Enter the no. 20
 
1.Push
2. POP
3.Display
4. Length
5.Quit
 
Enter the choice: 1
 
Enter the no. 30
 
1.Push
2. POP
3.Display
4. Length
5.Quit
 
Enter the choice: 1
 
Enter the no. 40
 
1.Push
2. POP
3.Display
4. Length
5.Quit
 
Enter the choice: 3
 
Elements in the stack:
40
30
20
10
 
1.Push
2. POP
3.Display
 STACK USING LINKED LIST
Aim:
              To write a program for stack using linked list implementation.
 
Algorithm :

           Step1:Define a C-struct for each node in the stack. Each node in the stack
                     contains data and link to the next node. TOP pointer points to last
                    node inserted in the stack.

          Step 2: The operations on the stack are

         a)PUSH data into the stack
         b)POP data out of stack
 
         Step  3:  PUSH DATA INTO STACK
                   3a.Enter the data to be inserted into stack.
                   3b.If TOP is NULL
                         the input data is the first node in stack.
                         the link of the node is NULL.
                        TOP points to that node.
                   3c.If TOP is NOT NULL
                        the link of TOP points to the new node.
                        TOP points to that node.

           Step 4:   POP DATA FROM STACK

                   4a.If TOP is NULL
                        the stack is empty
                   4b.If TOP is NOT NULL
                        the link of TOP is the current TOP.
                        the pervious TOP is popped from stack.

            Step 5.  The stack represented by linked list is traversed to display its content.
 
 
PROGRAM:
# include<stdio.h>
# include<conio.h>

struct node
{
int info;
struct node *link;
} *top=NULL;
main()
{
int choice;
while(1)
{ printf("1.Push\n");
printf("2.Pop\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ") ;
scanf("%d", &choice);

switch(choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(1);
default :
printf("Wrong choice\n");
}/*End of switch */
}/*End of while */
}/*End of main() */

push()
{
struct node *tmp;
int pushed_item;
tmp = (struct node *)malloc(sizeof(struct node));
printf("Input the new value to be pushed on the stack : ");
scanf("%d",&pushed_item);
tmp->info=pushed_item;
tmp->link=top;
top=tmp;
}/*End of push()*/

pop()
{
struct node *tmp;
if(top == NULL)
printf("Stack is empty\n");
else
{ tmp=top;
printf("Popped item is %d\n",tmp->info);
top=top->link;
free(tmp);
}

}/*End of pop()*/

display()
{ struct node *ptr;
ptr=top;
if(top==NULL)
printf("Stack is empty\n");
else
{
printf("Stack elements :\n");
while(ptr!= NULL)
{
printf("%d\n",ptr->info);
ptr = ptr->link;
}/*End of while */
}/*End of else*/
}/*End of display()*/

 
Output:
 
1.Push
2. POP
3.Display
5.Quit
 
Enter the choice: 1
 
Input the new value to be pushed on the stack :. 10
 
 
1.Push
2. POP
3.Display
5.Quit
 
Enter the choice: 1
 
Input the new value to be pushed on the stack : 20
 
1.Push
2. POP
3.Display
5.Quit
 
Enter the choice: 1
 
Input the new value to be pushed on the stack : 30
 
1.Push
2. POP
3.Display
5.Quit
 
Enter the choice: 1
 
Input the new value to be pushed on the stack :  40
 
1.Push
2. POP
3.Display
5.Quit
 
Enter the choice: 3
 
Elements in the stack:
40
30
20
10
 
1.Push
2. POP
3.Display
5.Quit
 
Enter the choice: 2
 
40 is popped from the stack
 
1.Push
2. POP
3.Display
 
 QUEUE USING ARRAY
Aim:
              To write a program for Queue using array implementation.
 
Algorithm :

           Step1:Define a array which stores queue elements..

          Step 2: The operations on the queue are

         a)INSERT data into the queue
         b)DELETE data out of queue
 
         Step  3:  INSERT DATA INTO queue
                   3a.Enter the data to be inserted into queue.
                   3b.If TOP is NULL
                         the input data is the first node in queue.
                         the link of the node is NULL.
                        TOP points to that node.
                   3c.If TOP is NOT NULL
                        the link of TOP points to the new node.
                        TOP points to that node.

           Step 4:   DELETE DATA FROM queue

                   4a.If TOP is NULL
                        the queue is empty
                   4b.If TOP is NOT NULL
                        the link of TOP is the current TOP.
                        the pervious TOP is popped from queue.

            Step 5.  The queue represented by linked list is traversed to display its content.
 
PROGRAM:
# include<stdio.h>
# define MAX 5

int queue_arr[MAX];
int rear = -1;
int front = -1;

main()
{
int choice;
while(1)
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1 :
insert();
break;
case 2 :
del();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of main()*/

insert()
{
int added_item;
if (rear==MAX-1)
printf("Queue Overflow\n");
else
{
if (front==-1) /*If queue is initially empty */
front=0;
printf("Input the element for adding in queue : ");
scanf("%d", &added_item);
rear=rear+1;
queue_arr[rear] = added_item ;
}
}/*End of insert()*/

del()
{
if (front == -1 || front > rear)
{
printf("Queue Underflow\n");
return ;
}
else
{
printf("Element deleted from queue is : %d\n", queue_arr[front]);
front=front+1;
}
}/*End of del() */

display()
{
int i;
if (front == -1)
printf("Queue is empty\n");
else
{
printf("Queue is :\n");
for(i=front;i<= rear;i++)
printf("%d ",queue_arr[i]);
printf("\n");
}
}/*End of display() */
 
 
 
 
 
 
 
 
 
 Output:
 
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice:1
 
Input the element for adding in queue :10
 
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice:1
 
Input the element for adding in queue :20
 
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice:1
 
Input the element for adding in queue :30
 
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice:1
 
Input the element for adding in queue :40
 
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice:3
 
Queue is :
40
30
20
10
 
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice:2
 
 
Element deleted from queue is :10
 
1.Insert
2.Delete
3.Display
4.Quit
Enter your choice:3
 
Queue is :
 
QUEUE OPERATIONS USING LINKED LIST
Aim:
              To write a program for Queue using Linked implementation.
 
Algorithm :

           Step1: Define a C-struct for each node in the queue. Each node in the queue
                     contains data and link to the next node. Front and rear pointer points to first
and last
                    node inserted in the queue.

          Step 2: The operations on the queue are

         a)INSERT data into the queue
         b)DELETE data out of queue
 
         Step  3:  INSERT DATA INTO queue
                   3a.Enter the data to be inserted into queue.
                   3b.If TOP is NULL
                         the input data is the first node in queue.
                         the link of the node is NULL.
                        TOP points to that node.
                   3c.If TOP is NOT NULL
                        the link of TOP points to the new node.
                        TOP points to that node.

           Step 4:   DELETE DATA FROM queue

                   4a.If TOP is NULL
                        the queue is empty
                   4b.If TOP is NOT NULL
                        the link of TOP is the current TOP.
                        the pervious TOP is popped from queue.

            Step 5.  The queue represented by linked list is traversed to display its content.
PROGRAM:
#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 10

void insertion();
void deletion();
void display();

struct node
{
int info;
struct node *link;
}*new,*temp,*p,*front=NULL,*rear=NULL;
typedef struct node N;

main()
{
int ch;
do
{
printf("\n\t\t\tLinked queue");
printf("\n 1.Insertion");
printf("\n 2.Deletion");
printf("\n 3.Display");
printf("\n 4.Exit");
printf("\n Enter your choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
insertion();
break;
case 2:
deletion();
break;
case 3:
display();
break;
default:
break;
}
}
while(ch<=3); }
void insertion()
{
int item;
new=(N*)malloc(sizeof(N));
printf("\nEnter the item : ");
scanf("%d",&item);
new->info=item;
new->link=NULL;
if(front==NULL)
front=new;
else
rear->link=new;
rear=new;
}

void deletion()
{
if(front==NULL)
printf("\nQueue is empty");
else
{
p=front;
printf("\nDeleted element is : %d",p->info);
front=front->link;
free(p);
}
}

void display()
{
if(front==NULL)
printf("\nQueue is empty");
else
{
printf("\nThe elements are : ");
temp=front;
while(temp!=NULL)
{
printf("%d",temp->info);
temp=temp->link;
}
}
}
 
 
Output:
 
1.Insertion
2.Deletion
3.Display
4.Exit
Enter your choice:1
Enter the item :10
 
1.Insertion
2.Deletion
3.Display
4.Exit
Enter your choice:1
Enter the item :20
 
1.Insertion
2.Deletion
3.Display
4.Exit
Enter your choice:1
Enter the item :30
 
1.Insertion
2.Deletion
3.Display
4.Exit
Enter your choice:1
Enter the item :40
 
1.Insertion
2.Deletion
3.Display
4.Exit
Enter your choice:3
 
The elements are :
40
30
20
10
 
1.Insertion
2.Deletion
3.Display
4.Exit
Enter your choice:2
 
Deleted element is : 10
 
1.Insertion
2.Deletion
3.Display
4.Exit
Enter your choice:3
 
The elements are :
40
 LINKED LIST IMPLEMENTATION USING LIST
 
AIM:
 
To implement a linked list and do all operations on it.
 
ALGORITHM:
 
Step 1 : Start the process.
 
Step 2: Initialize and declare variables.
 
Step 3: Enter the choice. INSERT / DELETE.
 
Step 4: If choice is INSERT then
a. Enter the element to be inserted.
 
b. Get a new node and set DATA[NEWNODE] = ITEM.
 
c. Find the node after which the new node is to be inserted.
 
d. Adjust the link fields.
 
e. Print the linked list after insertion.
 
Step 5: If choice is DELETE then
 
a. Enter the element to be deleted.
 
b. Find the node containing the element (LOC) and its preceding node (PAR).
 
c. Set  ITEM = DATA[LOC] and delete the node LOC.
 
d. Adjust the link fields so that PAR points to the next element. ie
LINK[PAR] = LINK [ LOC].
 
e. Print the linked list after deletion.
 
Step 6: Stop the process.
 
 
 
 
 
 
 
 Program:
#include<stdio.h>
#include<stlib.h>
#include<conio.h>
 
struct node;
typedef struct node *ptr;
typedef ptr list;
typedef ptr position;
typedef int data;
 
struct node
{
              data element;
              struct node *next;
}
 
//function prototypes
void makeempty(void);              //to make empty list
int isempty(void);                            //to check list is empty or not
void create(void);                            //to create initial set of elements
position findprevious(data);              //to find position of previous element
void delet(data);                            //to delete given element
void display(void);                            //to display all the elements
void insert(data, int);                            //to insert a new element
position getprevposition(int);              //to find position of previous element
data getelement(int);                            //to find the element at given position
int getposition(data);                            //to find position of given element
 
//global variable declarations
position first;
position last;
position L;
int length;
 
//to make empty list
void makeempty(void)
{
              position tmp;
              tmp = malloc(sizeof(list));
              tmp->next = NULL;
              L = tmp;
              first = last = NULL;
}
 
 
//to check list is empty or not
int isempty(void)
{
              if (L->next = NULL)
                            return 1;
              else
                            return 0;
}
 
//to create initial set of elements
void create(void)
{
              data e;
              int n, i;
              position tmp;
              makeempty();
              printf(“Enter number of element : \              “);
              scanf(“%d”, &n);
              for (i=0; i<n; i++)
              {
                            printf(“Enter an element : “);
                            scanf(“%d”, &e);
                            tmp = malloc(sizeof(list));
                            tmp->element = e;
                            tmp->next = NULL;
                            if (L->next == NULL)
                            {
                                          L->next = tmp;
                                          first = last = tmp;
                            }
                            else
                            {
                                          last->next = tmp;
                                          last = tmp;
                            }
              }
}
 
//to display all the elements
void display()
{
              position t;
              for(t=first; t!=NULL; t=t->next)
                            printf(“%d --> “, t->element);
              getch();
}
//to find position of previous element
position getprevposition(int index)
{
              position tmp;
              int count = 1;
              if (index>length)
              {
                            printf(“Invalid Position”);
                            return NULL;
              }
              else
              {
                            for (tmp=first; count<index-1; tmp=tmp->next)
                                          count++;
                            return tmp;
              }
}
 
//to insert a new element
void insert(data x, int p)
{
              position pos, tmp;
              tmp = malloc(sizeof(list));
              tmp->element=x;
              if (p==1)                            //first position
              {
                            tmp->next = first;
                            L->next = tmp;
                            first = tmp;
                            length++;
              }
              else if (p == length)              //last position
              {
                            last->next = tmp;
                            last = tmp;
                            tmp->next = NULL;
              }
              else                                          //arbitrary position
              {
                            pos = getpreviousposition(p);
                            if (pos == NULL)
                            {
                                          printf(“Invalid position”);
                                          getch();
                            }
                            else
                            {
                                          tmp->next = pos->next;
                                          pos->next = tmp;
                                          length++;
                            }
              }
}
 
//to find position of previous element
position findprevious(data x)
{
              position p;
              p = L;
              while (p->next->element!=x && p->next!=NULL)
                            p = p->next;
              return p;
}
 
//to delete given element
void delet(data x)
{
              position p, tmp;
              if (isempty())
              {
                            printf(“List is empty”);
                            getch();
              }
              else
              {
                            p = findprevious(x);
                            if (p->next = NULL)
                            {
                                          printf(“Element not found”);
                                          getch();
                            }
                            else
                            {
                                          if (p->next == last)
                                          {
                                                        free (p->next);
                                                        p->next =  NULL;
                                                        last = p;
                                                        length--;
                                                        return;
                                          }
                                          if (p == L)
                                          {
                                                        first = first->next;
                                          }
                                          tmp = p->next;
                                          p->next = tmp->next;
                                          free(tmp);
                                          length--;
                            }
              }
}
 
int menu()
{
              int ch;
              printf(“1. Create\n2. Display\n3.Insert\n4.Get Element\n5.Get Position\n6.
Delete\n7. Exit\n\n Enter your choice : “);
              scanf(“%d”, &choice);
              return choice;
}
 
//to find the element at given position
data getelement(int pos)
{
              position p;
              int i;
              p = L;
              if (pos > length)
                            return NULL;
              else
              {
                            for(i=0; i<pos; i++)
                                          p = p->next;
                            return p->element;
              }
}
 
//to find position of given element
int getposition(data e)
{
              position p;
              int i=0;
              for (p=first; p!=NULL; p=p->next)
              {
                            if (p->element == e)
                                          return i+1;
                            else
                                          i++;
              }
              return NULL;
}
 
void main()
{
              int ch;
              data n, p;
              while(1)
              {
                            clrscr();
                            ch = menu();
                            switch (ch)
                            {
                                          case 1:
                                                        create();
                                                        break;
                                          case 2:
                                                        display();
                                                        break;
                                          case 3:
                                                        printf(“Enter an element : “);
                                                        scanf(“%d”, &n);
                                                        printf(“Enter Position : “);
                                                        scanf(“%d”, &p);
                                                        insert (n, p);
                                                        break;
                                          case 4:
                                                        printf(“Enter an element : “);
                                                        scanf(“%d”, &n);
                                                        delet (n);
                                                        break;
                                          case 5:
                                                        printf(“Enter position : “);
                                                        scanf(“%d”, &p);
                                                        if (p<1 || p>length)
                                                                      printf(“Invalid position”);
                                                        else
printf(“Element at position %d is %d”, p, getelement(p));
                                                        getch();
                                                        break;
                                          case 6:
                                                        printf(“Enter an element : “);
                                                        scanf(“%d”, &n);
                                                        if (getposition(n) == NULL)
                                                                      printf(“Element doesn’t Exist”);
                                                        else
                                                                      printf(“%d exists at position %d”, n,
getposition(n));
                                                        getch();
                                                        break;
                                          default:
                                                        printf(“Invalid Choice”);
                                                        getch();
                            }
              }
}
 
 
 
 
 
 
 
 
 
 
 

Output:
 
1. Create
1. Display
2. Insert
3. Delete
4. Get element
5. Get position
6. Exit
 
Enter your Choice: 1
 
Enter number of element: 3
Enter an element: 10
Enter an element: 20
Enter an element: 30
 
 
Enter your Choice: 3
 
Enter element: 25
Enter Position: 3
 
 
Enter your Choice: 2
 
10 --> 20 --> 25 --> 30
 
 
Enter your Choice: 6
 
Enter an element:20
20 exists at position 2
 
 
Enter your Choice: 4
 
Enter an element 30
 
 
Enter your Choice: 2
 
10 --> 20 --> 25
 
 
Enter your Choice: 6
 
             
 
CURSOR IMPLEMENTATION – LIST
 
 
Aim:
              To write a c program for cursor implementation of list.
 
Algorithm:
 
1. Start the program.
2. Create a node with two fields data and link field.
o Allocate space for the node dynamically.
o Create link between the created nodes and let the last node be with NULL
Link
o Insert the input data in the data field and press –1 to stop the same.
3. Get the choice of operations either insertion or deletion.
 4. For insertion get the position in which insertion is to be done and the element to
be inserted. Check for the start, middle or end position of insertion. Insert the
node and change its link accordingly.
5. For deletion get the position in which deletion is to be done. Delete the node and
then link it to the next node. Before deletion check whether there is data in the list
to be deleted.
6. Using display option list the elements of the list.
7. Stop the program.
Program:
 
#include<stdio.h>
#include<conio.h>
struct cursor
{
char data;
int next;
}c[10];
int fp=0;
void create()
{
char a;
int p,i;
   for(i=0;i<10;i++)
 {
     c[i].data=' ';
     c[i].next=-1;
 }
printf("Enter the first element to be inserted");
scanf("%c",&a);
printf("Enter the position");
scanf("%d",&p);
fp=p;
c[p].data=a;
c[p].next=0;
}
void insert(char a,int pos)
{
int i;
   if(c[pos].next==-1)
    {
              c[pos].data=a;
      for(i=0;i<10;i++)
      {
              if(c[i].next==0)
              {
                c[i].next=pos;
              }
      }
      c[pos].next=0;
    }
    else
     printf("\n Already data is available");
}
 
 
void display()
{
int i;
i=fp;
do
{
printf("%d\t",i);
printf("%c\t",c[i].data);
printf("%d\n",c[i].next);
i=c[i].next;
}
while(i>0);
}
void del()
{
  int temp,i;
  char d;
  printf("\n Enter the character to be deleted");
  d=getch();
  if(c[fp].data==d)
 {
   c[fp].data=' ';
   temp=c[fp].next;
   c[fp].next=-1;
   fp=temp;
 }
  else
 {
   i=fp;
   do
   {
   if(c[c[i].next].data==d)
    {
     temp=c[i].next;
     c[i].next=c[c[i].next].next;
     c[temp].next=-1;
    }
    i=c[i].next;
    }
    while(i>0);
    }
}
 
 
 
 
 
 
void main()
{
int opt,p;
char a;
clrscr();
create();
do
{
printf("\n 1.Insert");
printf("\n 2.Delete");
printf("\n 3.Display");
printf("\n 4.Exit");
printf("\n Enter your choice");
scanf("%d",&opt);
              switch(opt)
              {
                     case 1:
                              printf("\nEnter the element to be inserted");
                              a=getch();
                              printf("\nEnter the position");
                              scanf("%d",&p);
                            insert(a,p);
                              break;
 
                      case 2:
                              del();
                            break;
 
                    case 3:
                          display();
                          break;
              }
     }
  while(opt<4);
}
Output:
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice:1
 
Enter the element to be inserted 20
 
Enter the position 1
 
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice:1
 
Enter the element to be inserted 40
 
Enter the position 2
 
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice:1
 
Enter the element to be inserted 30
 
Enter the position 3
 
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice:3
 
1.20
2.40
3.30
 
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice:1
 
Enter the element to be inserted 60
 
Enter the position 2
 
 
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice:3
 
1.20
2.60
3.40
4.30
 
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice:4
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 BINARY SEARCH TREE
 
Aim:
              To write a c program for binary search tree.
 
Algorithm:
 
1. Declare function add(),search(),findmin().find(),findmax(),Display().
2. Create a structure for  a tree contains left pointer and right pointer.
3. Insert an element is by checking the top node and the leaf node and the operation
will be performed.
4. Deleting an element contains searching the tree and deleting the item.
5. display the Tree elements.
Program:
#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);
node delete(ElementType, node);
void makeempty();
node findmin(node);
node findmax(node);
node find(ElementType, node);
void display(node, int);
 
void main()
{
              int ch;
              ElementType a;
              node temp;
              makeempty();
              while(1)
              {
                            printf("\n1. Insert\n2. Delete\n3. Find min\n4. Find max\n5. Find\n6.
Display\n7. Exit\nEnter Your Choice : ");
                            scanf("%d",&ch);
                            switch(ch)
                            {
                                          case 1:
                                                        printf("Enter an element : ");
                                                        scanf("%d", &a);
                                                        root = insert(a, root);
                                                        break;
                                          case 2:
                                                        printf("\nEnter the element to delete : ");
                                                        scanf("%d",&a);
                                                        root = delet(a, root);
                                                        break;
                                          case 3:
                                                        printf("\nEnter the element to search : ");
                                                        scanf("%d",&a);
                                                        temp = find(a, root);
                                                        if (temp != NULL)
                                                                      printf("Element found");
                                                        else
                                                                      printf("Element not found");
                                                        break;
                                          case 4:
                                                        temp = findmin(root);
                                                        if(temp==NULL)
                                                                      printf("\nEmpty tree");
                                                        else
                                                                      printf("\nMinimum element : %d", temp-
>element);
                                                        break;
                                          case 5:
                                                        temp = findmax(root);
                                                        if(temp==NULL)
                                                                      printf("\nEmpty tree");
                                                        else
                                                                      printf("\nMaximum element : %d", temp-
>element);
                                                        break;
                                          case 6:
                                                        if(root==NULL)
                                                                      printf("\nEmpty tree");
                                                        else
                                                                      display(root, 1);
                                                        break;
                                          case 7:
                                                        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;
}
 
node delet(ElementType x,node t)
{
              node temp;
              if(t == NULL)
                            printf("\nElement not found");
              else
              {
                            if(x < t->element)
                                          t->left = delet(x, t->left);
                            else if(x > t->element)
                                          t->right = delet(x, t->right);
                            else
                            {
                                          if(t->left && t->right)
                                          {
                                                        temp = findmin(t->right);
                                                        t->element = temp->element;
                                                        t->right = delet(t->element,t->right);
                                          }
                                          else if(t->left == NULL)
                                                        t=t->right;
                                          else
                                                        t=t->left;
                            }
              }
              return t;
}
void makeempty()
{
              root = NULL;
}
 
 
node findmin(node temp)
{
              if(temp == NULL || temp->left == NULL)
                            return temp;
              return findmin(temp->left);
}
 
 
node findmax(node temp)
{
              if(temp==NULL || temp->right==NULL)
                            return temp;
              return findmin(temp->right);
}
 
node find(ElementType x, node t)
{
              if(t==NULL) return NULL;
              if(x<t->element) return find(x,t->left);
              if(x>t->element) return find(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:
 
1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 1
Enter an element : 10
 
1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 1
Enter an element : 20
 
 
1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 1
Enter an element : 5
 
 
1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 4
The smallest Number is 5
 
1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 3
Enter an element : 100
Element not Found
 
1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 2
Enter an element : 20
 
1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 6
   5
10
 
1. Insert
2. Delete
3. Find
4. Find Min
5. Find Max
6. Display
7. Exit
Enter your Choice : 7
 
 
 
 
 
 
 
 
 
 
QUICK SORT
Aim:
              To  write a c program to perform quick sort.
 
Algorithm:
1. Get the value of how many no. to be sorted.

2. Get the elements from the user.

3. Two function qsort() and swap(). Quick sort to perform sorting.

4. Swap() is just to rearrange the values.

5. Quick sort algorithm works by partitioning the array to be sorted, then recursively

sorting each partition.

6. Display the sorted value.

 
Program:
#include<stdio.h>
#include<conio.h>
int i,j,n,pi,a[20];
void qsort(int a[],int ft,int lt);
void swap(in a[],int i,int j);
void main()
{
              int n,i,a[20];
clrscr();
printf(“\nEnter the size:”);
scanf(“%d”,&n);
printf(“Enter the elements:”);
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);
qsort(a,0,n-1);
printf(“\nSorted List:”);
for(i=0;i<n;i++)
printf(“\n%d\t”,a[i]);
getch();
}
void qsort(int a[],int lb,int ub)
{
if(lb<ub)
{
pi=a[lb];
i=lb;
j=ub;
while(i<j)
{while(a[i]<=pi && i<ub)
i++;
while(a[i]>=pi && j>lb)
j--;
if(i<j)
swap(a,i,j);
}
swap(a,lb,j);
qsort(a,lb,j-1);
qsort(a,j+1,ub);
}
}
void swap(int a[],int i,int j)
{
int t;
t=a[i];
a[i]=a[j];
a[j]=t;}
 
 
 
Output:
 
Enter the size:
5
 
Enter the elements:
 
85
32
46
04
96
 
Sorted list:
 
04
32
46
85
96
 HEAP SORT
Aim:
              To  write a c program to perform heap sort.
 
Algorithm:
1. Get the size of the array from the user.
2. Get the elements to be sorted.
3. Sorting is performed when we call the heap sort function.
4. Now the array is contained with sorted elements.
5. Display the sorted elements.
 
Program:
#include<stdio.h>
#include<conio.h>
void heapsort(int x[],int);
void main()
{
int x[100],i,n;
clrscr();
printf(“\nEnter the size:”);
scanf(“%d”,&n);
printf(“Enter %d elements:”,n);
for(i=0;i<n;i++)
{
scanf(“%d”,&x[i]);
}
for(i=n;i>1;i--)
{
heapsort(x,i-1);
}
printf(“\nSorted elements are:”);
for(i=0;i<n;i++)
{
printf(“-->%d\n”,x[i]);
}
getch();
}
void heapsort(int x[],int arr)
{
int i,m;
int lc,rc,mc,rt,temp;
rt=(arr-1)/2;
for(m=rt;m>=0;m--)
{
for(i=rt;i>=0;i--)
{
lc=(2*i)+1;
rc=(2*i)+2;
if((lc<=arr)&&(rc<=arr))
{
if(x[rc]>=x[lc])
mc=rc;
else
mc=lc;
}
else
{
if(rc>arr)
mc=lc;
else
mc=rc;
}
if(x[i]<x[mc])
{
temp=x[i];
x[i]=x[mc];
x[mc]=temp;
}
}
}
temp=x[0];
x[0]=x[arr];
x[arr]=temp;
return;
}
  
Output:
 
Enter the size:
5
 
Enter 5 elements:
90
67
12
75
01
 
sorted elements:
1 12 67 75 90