Ex no:1a ARRAY IMPLEMENTATION USING STACK ADT

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
4. Length
5.Quit

Enter the choice: 2

40 is popped from the stack

1.Push
2. POP
3.Display
4. Length
5.Quit

Enter the choice: 4

Number of elements in the stack is 3

1. Push
2. POP
3.Display
4. Length
5.Quit

Enter the choice: 5

Ex no:1b ARRAY IMPLEMENTATION USING QUEUE ADT

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 :
40
30
20

1.Insert
2.Delete
3.Display
4.Quit
Enter your choice:4
EX : 2 ARRAY IMPLEMENTATION OF LIST ADT

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
5.Quit

Enter the choice: 5

Ex:3a
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

Ex:3b
LINKED LIST IMPLEMENTATION USING STACK
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
5.Quit

Enter the choice: 5

Ex:3c
LINKED LIST IMPLEMENTATION USING QUEUE
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
30
20

1.Insertion
2.Deletion
3.Display
4.Exit
Enter your choice:4
Ex:4a
POLYNOMIAL MANIPULATION
Aim
To implement polynomial manipulation using doubly linked lists.
Algorithm
POLYADD(POLY1: POLY2:POLY)
HEAD:POLY
Step 1: Assign HEAD+=NULL
Step2: While (POLY !=null)
Step3: HEAD=INSERTNODE(HEAD,COPYNODE,(POLY1,1))
Step4: POLY1=POLY1_NEXT
Step5: [End of Step2 while structure]
Step6: While(POLY2 1=NULL)
Step7: HEAD =INSERTNODE(HEAD,COPYNODE(POLY2,1))
Step8: POLY2=POLY2_NEXT
Step9: [End of Step 6 while Structure]
Step10: Return HEAD
END POLYADD()
Algorithm for polynomial subtraction
POLYSUB(POLY1:POLY, POLY2:POLY)
HEAD:POLY
Step1: Assign HEAD=NULL
Step2: While(POLY1!=NULL)
Step3: HEAD=INSERTNODE(HEAD,COPYNODE(POLY1,1))
Step4: POLY1=POLY1_ NEXT
Step5: [End of Step2 while Structure]
Step6:While(POLY2!=NULL)
Step7: HEAD=INSERTNODE(HEAD,COPYNODE(POLY2,1))
Step8: POLY2=POLY2_NEXT
Step9: [End of Step 6 While Structure]
Step10: Return HEAD
END POLYSUB()
PROGRAM
#include<malloc.h>
#include<conio.h>
struct link
{
int coeff;
int pow;
struct link *next;
};
struct link *poly1=NULL,*poly2=NULL,*poly=NULL;
void create(struct link *node)
{
char ch;
do
{
printf("\nEnter the coefficient :");
scanf("%d",&node>
coeff);
printf("\nEnter the power :");
scanf("%d",&node>
pow);
node>
next=(struct link *)malloc(sizeof(struct link));
node=node>
next;
node>
next=NULL;
printf("\nContinue??? (Y/N) :");
ch=getch();
}while(ch=='y' || ch=='Y');
}
void display(struct link *node)
{
while(node>
next!=NULL)
{
printf("%dx^%d",node>
coeff,node>
pow);
node=node>
next;
if(node>
next!=NULL)
printf(" + ");
}
}
void polyadd(struct link *poly1,struct link *poly2,struct link *poly)
{
while(poly1>
next && poly2>
next)
{
if(poly>
pow > poly2>
pow)
{
poly>
pow=poly1>
pow;
poly>
coeff=poly1>
coeff;
poly1=poly1>
next;
}
else if(poly1>
pow < poly2>
pow)
{
poly>
pow=poly2>
pow;
poly>
coeff=poly2>
coeff;
poly2=poly2>
next;
}
else
{
poly>
pow=poly1>
pow;
poly>
coeff=poly1>
coeff+poly2>
coeff;
poly1=poly1>
next;
poly2=poly2>
next;
}
poly>
next=(struct link *)malloc(sizeof(struct link));
poly=poly>
next;
poly>
next=NULL;
}
while(poly1>
next||poly2>
next)
{
if(poly1>
next)
{
poly>
pow=poly1>
pow;
poly>
coeff=poly1>
coeff;
poly1=poly1>
next;
}
if(poly2>
next)
{
poly>
pow=poly2>
pow;
poly>
coeff=poly2>
 coeff;
poly2=poly2>
next;
}
poly>
next=(struct link *)malloc(sizeof(struct link));
poly=poly>
next;
poly>
next=NULL;
}
}
void main()
{
poly1=(struct link *)malloc(sizeof(struct link));
poly2=(struct link *)malloc(sizeof(struct link));
poly=(struct link *)malloc(sizeof(struct link));
clrscr();
printf("\nEnter the first polynomial::");
create(poly1);
printf("\nFirst polynomial is :: \n");
display(poly1);
printf("\nEnter the second polynomial::");
create(poly2);
printf("\nSecond polynomial is :: \n");
display(poly2);
polyadd(poly1,poly2,poly);
printf("\nAddition of the two polynomials::");
display(poly);
getch();
}
OUTPUT
Enter the first polynomial:
Enter the coefficient :5
Enter the power :3
Continue??? (Y/N) :Y
Enter the coefficient :3
Enter the power :2
Continue??? (Y/N) :
First polynomial is ::
5x^3 + 3x^2
Enter the second polynomial::
Enter the coefficient :7
Enter the power :3
Continue??? (Y/N) :
Second polynomial is ::
7x^3
Addition of the two polynomials::12x^3 + 3x^2
Ex: 4b INFIX TO POSTFIX CONVERSION

Aim
To implement infix to postfix conversion using stack.
Algorithm

Step 1. Push left parenthesis onto STACK and add right parenthesis at the end of Q.

Step 2. Scan Q from left to right and repeat step 3 to 6 for each element of Q until the STACK is
empty.

Step 3. If an operand is encountered add it to P.

Step 4. If a left parenthesis is encountered push it onto the STACK.

Step 5. If an operator is encountered, the Repeatedly pop from STACK and add to P each
operator which has same precedence as or higher precedence than the operator
encountered.Push the encountered operator onto the STACK.

Step 6. If a right parenthesis is encountered, then Repeatedly pop from the STACK and add to P
each operator until a left parenthesis is encountered.Remove the left parenthesis; do not add it
to P.

Step 7. Exit
PROGRAM

include<stdio.h>
char stack[20];
int top = -1;
void push(char x)
{
stack[++top] = x;
}

char pop()
{
if(top == -1)
return -1;

else
return stack[top--];
}

int priority(char x)
{
if(x == '(')
return 0;
if(x == '+' || x == '-')
return 1;
if(x == '*' || x == '/')
return 2;
}

main()
{
char exp[20];
char *e, x;
printf("Enter the expression :: ");
scanf("%s",exp);
 e = exp;
while(*e != '\0')
{
if(isalnum(*e))
printf("%c",*e);
else if(*e == '(')
push(*e);
else if(*e == ')')
{
while((x = pop()) != '(')
printf("%c", x);

}
else
{
while(priority(stack[top]) >= priority(*e))
printf("%c",pop());
push(*e);
}
e++;
}
while(top != -1)
{
printf("%c",pop());
}
}
OUTPUT
Enter the expression :: a+b*c

abc*+
EX.N0. 5 BINARY TREE
Aim:
To write a c program for Implementation of binary tree.
Algorithm:
1. Declare pointer right and left
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<stdlib.h>
#include<stdio.h>

struct bin_tree {
int data;
struct bin_tree * right, * left;
};
typedef struct bin_tree node;

void insert(node ** tree, int val)

{
node *temp = NULL;
if(!(*tree))
{
temp = (node *)malloc(sizeof(node));
temp->left = temp->right = NULL;
temp->data = val;
*tree = temp;
return;
 }

if(val < (*tree)->data)

{
insert(&(*tree)->left, val);
}
else if(val > (*tree)->data)
{
insert(&(*tree)->right, val);
}

void print_preorder(node * tree)

{
if (tree)
{
printf("%d\n",tree->data);
print_preorder(tree->left);
print_preorder(tree->right);
}

void print_inorder(node * tree)

{
if (tree)
{
print_inorder(tree->left);
printf("%d\n",tree->data);
print_inorder(tree->right);
 }
}

void print_postorder(node * tree)

{
if (tree)
{
print_postorder(tree->left);
print_postorder(tree->right);
printf("%d\n",tree->data);
}
}

void deltree(node * tree)

{
if (tree)
{
deltree(tree->left);
deltree(tree->right);
free(tree);
}
}

node* search(node ** tree, int val)

{
if(!(*tree))
{
return NULL;
}

if(val < (*tree)->data)

 {
search(&((*tree)->left), val);
}
else if(val > (*tree)->data)
{
search(&((*tree)->right), val);
}
else if(val == (*tree)->data)
{
return *tree;
}
}

void main()
{
node *root;
node *tmp;
//int i;

root = NULL;
/* Inserting nodes into tree */
insert(&root, 9);
insert(&root, 4);
insert(&root, 15);
insert(&root, 6);
insert(&root, 12);
insert(&root, 17);
insert(&root, 2);

/* Printing nodes of tree */

printf("Pre Order Display\n");
 print_preorder(root);

printf("In Order Display\n");

print_inorder(root);

printf("Post Order Display\n");

print_postorder(root);

/* Search node into tree */

tmp = search(&root, 4);
if (tmp)
{
printf("Searched node=%d\n", tmp->data);
}
else
{
printf("Data Not found in tree.\n");
}

/* Deleting all nodes of tree */

deltree(root);
}
OUTPUT
Pre Order Display

15

12

17

In Order Display

12

15

17

Post Order Display

12

17

15

Searched node=4
EX: 6 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
 Ex.no.7
IMPLEMENTATION OF AVL TREES
Date:
Aim:
To write a C program to perform implementation of AVL tree.

ALGORITHM
The following two cases are possible-
Case-01:

 After the insertion, the balance factor of each node is either 0 or 1 or -1.
 In this case, the tree is considered to be balanced.
 Conclude the operation.
 Insert the next element if any.

Case-02:

 After the insertion, the balance factor of at least one node is not 0 or 1 or -1.
 In this case, the tree is considered to be imbalanced.
 Perform the suitable rotation to balance the tree.
 After the tree is balanced, insert the next element if any.
PROGRAM
#include<conio.h>
#include<stdio.h>
typedef enum {FALSE,TRUE}bool;
struct node
{
int info;
int balance;
struct node *lchild;
struct node *rchild;
}*root;
struct node *search(struct node *ptr,int info)
{
if(ptr!=NULL)
if(info<ptr>
info)
ptr=search(ptr>
lchild,info);
else if(info>ptr>
info)
ptr=search(ptr>
rchild,info);
return (ptr);
}
struct node *insert(int info,struct node *pptr,int *ht_inc)
{
struct node *aptr;
struct node *bptr;
if(pptr==NULL)
{
pptr=(struct node *)malloc(sizeof(struct node));
pptr>
info=info;
pptr>
lchild=NULL;
pptr>
rchild=NULL;
pptr>
balance=0;
*ht_inc=TRUE;
return(pptr);
}
if(info<pptr>
info)
{
pptr>
lchild=insert(info,pptr>
lchild,ht_inc);
if(*ht_inc==TRUE)
{
switch(pptr>
balance)
{
case 1:
pptr>
balance=0;
*ht_inc=FALSE;
break;
case 0:
pptr>
balance=1;
break;
case 1:
aptr=pptr>
lchild;
if(aptr>
balance==1)
{
printf("Left to Left Rotation\n");
pptr>
lchild=aptr>
rchild;
aptr>
rchild=pptr;
pptr>
balance=0;
aptr>
balance=0;
pptr=aptr;
}
else
{
printf("Left to Right Rotation\n");
bptr=aptr>
rchild;
aptr>
rchild=bptr>
lchild;
bptr>
lchild=aptr;
pptr>
lchild=bptr>
rchild;
bptr>
rchild=pptr;
if(bptr>
balance==1)
pptr>
balance=1;
else
pptr>
balance=0;
if(bptr>
balance==1)
aptr>
balance=1;
else
aptr>
balance=0;
bptr>
balance=0;
pptr=bptr;
}
*ht_inc=FALSE;
}
}
}
if(info>pptr>
info)
{
pptr>
rchild=insert(info,pptr>
rchild,ht_inc);
if(*ht_inc==TRUE)
{
switch(pptr>
balance)
{
case 1:
pptr>
balance=0;
*ht_inc=FALSE;
break;
case 0:
pptr>
balance=1;
break;
case 1:
aptr=pptr>
rchild;
if(aptr>
balance==1)
{
printf("Right to Right Rotation\n");
pptr>
rchild=aptr>
lchild;
aptr>
lchild=pptr;
pptr>
balance=0;
aptr>
balance=0;
pptr=aptr;
}
else
{
printf("Right to Left Rotation\n");
bptr=aptr>
lchild;
aptr>
lchild=bptr>
rchild;
bptr>
rchild=aptr;
pptr>
rchild=bptr>
lchild;
bptr>
lchild=pptr;
if(bptr>
balance==1)
pptr>
balance=1;
else
pptr>
balance=0;
if(bptr>
balance==1)
aptr>
balance=1;
else
aptr>
balance=0;
bptr>
balance=0;
pptr=bptr;
}
*ht_inc=FALSE;
}
}
}
return (pptr);
}
main()
{
bool ht_inc;
int info;
int choice;
clrscr();
root=(struct node *)malloc(sizeof(struct node));
root=NULL;
printf("1.Insert\n2.Display\n3.Exit\n");
while(1)
{
printf("Enter your choice :");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter the value to be inserted ::");
scanf("%d",&info);
if(search(root,info)==NULL)
root=insert(info,root,&ht_inc);
else
printf("Duplicate value ignored\n");
break;
case 2:
if(root==NULL)
{
printf("Tree is empty");
continue;
}
printf("Tree is \n");
display(root,1);
printf("\n\n");
printf("Inorder Traversal :: ");
inorder(root);
printf("\n");
break;
default:
printf("Invalid Choice !!!");
exit(0);
}
}
}
display(struct node *ptr,int level)
{
int i;
if(ptr!=NULL)
{
display(ptr>
rchild,level+1);
printf("\n");
for(i=0;i<level;i++)
printf("");
printf("%d",ptr>
info);
display(ptr>
lchild,level+1);
}
}
inorder(struct node *ptr)
{
if(ptr!=NULL)
{
inorder(ptr>
lchild);
printf("%d ",ptr>
info);
inorder(ptr>
rchild);
}
}
OUTPUT

1.Insert
2.Display

3.Exit
Enter your choice :1
Enter the value to be inserted ::15
Enter your choice :1
Enter the value to be inserted ::12
Enter your choice :1
Enter the value to be inserted ::24
Enter your choice :1
Enter the value to be inserted ::6
Enter your choice :2
Tree is
24
15
12
6
Inorder Traversal :: 6 12 15 24
Enter your choice :3
Ex.no.:8 PRIORITY QUEUE USING HEAP
Aim:
To implement priority queue using Heap in C program.
Algorithm:
Step 1: [Include necessary header files]
Step 2: [Define maxsize as 15]
Step 3: [Declare necessary variables]
Step 4: READ option, opt
IF opt is 1 THEN CALL INSERT()
IF opt is 2 THEN CALL DELMAX()
IF opt is 3 THEN CALL DIS()
Step 5: [END OF MAIN FUNCTION]
Algorithm For INSERT()
Step 1: I ne1+1
Step 2: IF (I MAXSIZE)
WRITE (“ Heap size exceeded”)
RETURN FALSE
IF ( (I> 1) && (arraysize [i/2]< item) )
array[I] array[i/2]
I I/2
Array[I ] item
RETURN TRUE
Algorithm For DELMAX()
Step 1: IF (!nel)
WRITE (“HEAP IS EMPTY”)
ELSE
*item array [I]
Array[i] array [nel]
CALL adjust (array,I,nel)
PROGRAM

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<malloc.h>
typedef struct heapstruct *pqueue;
struct heapstruct
{
int capacity;
int size;
int *elements;
};
void insert(int,pqueue);
pqueue initialize(int);
int deletemin(pqueue);
int isfull(pqueue);
int isempty(pqueue);
void display(pqueue);
void main()
{
pqueue heap;
int i,max,ele,ch,t;
clrscr();
printf("\nEnter the maximum no.of elements in the priority queue:");
scanf("%d",&max);
heap=initialize(max);
do
{
printf("\nMENU\n");
printf("\n1. Insertion\n");
printf("\n2.DeleteMin\n");
printf("\n3. Display\n");
printf("\n4. Exit\n");
printf("\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nEnter the element to be inserted:");
scanf("%d",&ele);
insert(ele,heap);
printf("\nThe element is inserted");
break;
case 2: t=deletemin(heap);
printf("\nThe minimum element %d is deleted\n",t);
break;
case 3: printf("\nThe elements in the HEAP are:");
display(heap);
break;
case 4: exit(0);
break;
}
}while(ch<4);
getch();
}
pqueue initialize(int max)
{
pqueue h;
if(max<3)
{
printf("\nPriority queue size is too small\n");
exit(0);
}
h=(heapstruct*)malloc(sizeof(struct heapstruct));
if(h==NULL)
exit(0);
h>
capacity=max;
h>
size=0;
return h;
}
void insert(int x,pqueue h)
{
int i;
if(isfull(h))
{
printf("\nPriority queue is full");
return;
}
if(h>
size==0)
{
h>
elements[1]=x;
h>
size++;
}
else
{
for(i=++h>
size;h>
elements[i/2]>x;i/=2)
h>
elements[i]=h>
elements[i/2];
h>
elements[i]=x;
}
}
int deletemin(pqueue h)
{
int i,child,minelement,lastelement;
if(isempty(h))
printf("\nPriority queue is empty");
exit(0);
}
minelement=h>
elements[1];
lastelement=h>
elements[h>
size]
;
for(i=1;i*2<=h>
size;i=child)
{
child=i*2;
if(child!=h>
size&&h>
elements[child+1]<h>
elements[child])
child++;
if(lastelement>h>
elements[child])
h>
elements[i]=h>
elements[child];
else
break;
}
h>
elements[i]=lastelement;
return minelement;
}
void display(pqueue h)
{
int i;
for(i=1;i<=h>
size;i++)
printf("\n%d",h>
elements[i]);
}
int isfull(pqueue h)
{
if(h>
size==h>
capacity)
return 1;
else
return 0;
}
int isempty(pqueue h)
{
if(h>
size==0)
return 1;
else
return 0;
}
OUTPUT
Enter the maximum no.of elements in the priority queue:5
MENU
1. Insertion
2.DeleteMin
3. Display
4. Exit
Enter your choice:1
Enter the element to be inserted:67
The element is inserted
MENU

1. Insertion
2.DeleteMin
3. Display
4. Exit
Enter your choice:1
Enter the element to be inserted:24
The element is inserted
MENU
1. Insertion
2.DeleteMin
3. Display
4. Exit
Enter your choice:1
Enter the element to be inserted:35
The element is inserted
MENU
1. Insertion
2.DeleteMin
3. Display
4. Exit
Enter your choice:3
The elements in the HEAP are:
24
67
35
MENU
1. Insertion
2.DeleteMin
3. Display
4. Exit
Enter your choice:2
The minimum element 24 is deleted
MENU
1. Insertion
2.DeleteMin
3. Display
4. Exit
Enter your choice:3
The elements in the HEAP are:
35
67
Enter your choice:4
Ex no 9 GRAPH TRAVERSAL USING DEPTH -FIRST SEARCH

Algorithm :

Step 1: Choose any node in the graph . Designate it as the search node and mark it as vivited.

Step 2: Using the adjacency matrix of the graph, find a node adjacent to the search node that has
not been visited yet. Designate this as the new search node and mark it as visited.

Step 3: Repeat step 2 using t he new search node. If no nodes satisfying(2) can be found, return to
the previous search node and continue from there.

Step 4: When a return to the previous search in(3) is impossible,the serach from the originally
choosen search node is complete.

Step 5: If the graph still contains unvisited nodes,choose any node that has not been visited and
repeat step(1) through(4).
PROGRAM

#include<stdio.h>
#include<conio.h>
int a [10][10],visited[10].n;
void main()
{
int i,j;
void search from(int);
clrscr();
printf("enter the no. of nodes\n");
scanf("%d",&n);
printf("enter the adjacency matrix\n");
for(i=1;<=n;i++)
for(j=1;<=n;j++)
scanf("%d",&a[i][j]);
for(i=1;i<=n;i++)
visited[i]=0;
printf("Depth First Path:");
for(i=1;i<=n;i++)
if(visited[i]==0)
searchfrom(i);
}
void search from(int k)
{
int i;
printf("%d\t",k);
visited[k]=1;
for(i=1;i<=n;i++)
if(visited[i]==0)
searchfrom(i);
return;
}
OUTPUT

Enter the no. of nodes

4
Enter the adjacency matrix
0101
0011
0001
0000

Depth First Path

1 2 3 4
Ex.no.10
DIJKSTRA’S ALGORITHM
Aim
To implement Dijkstra’s algorithm to find the shortest path.
Algorithm
Step1: [Include all the header files]
Step2: Call allSelected( )
Step3: Call Shortpath( )
Step4: Access the functions from main
Step5: End
Algorithm For ALLSELECTED( )
Step1: Initialise i=0
Step2: Check whether i<max
Step3: Check whether Selected[i]=0
Return 0
Step4: Else Return 1
Step5: Return
Algorithm For SHORTPATH( )
Step1: Initialise i=0 , Check i<max
Distance[i]=INFINITE
Step2: Assign selected[current].distance[0]=0,
Current=0
Step3: While(!allSelected(Selected))
Perform(Selected[i]= =0)
Current=k
Selected[current]=1
Print k
PROGRAM
#include<stdio.h>
#include<conio.h>
www.vidyarthiplus.com
www.vidyarthiplus.com
#define max 4
#define INFINITE 998
int allselected( int *selected)
{
int i;
for(i=0;i<max;i++)
if(selected[i]==0)
return 0;
return 1;
}
void shortpath(int cost[][max],int *preceed,int *distance)
{
int selected[max]={0};
int current=0,i,k,dc,smalldist,newdist;
for(i=0;i<max;i++)
distance[i]=INFINITE;
selected[current]=1;
distance[0]=0;
current=0;
while(!allselected(selected))
{
smalldist=INFINITE;
dc=distance[current];
for(i=0;i<max;i++)
{
if(selected[i]==0)
{
newdist=dc+cost[current][i];
if(newdist<distance[i])
{
distance[i]=newdist;
preceed[i]=current;
}
if(distance[i]<smalldist)
{
smalldist=distance[i];
k=i;
}
}}
current=k;
selected[current]=1;
}
}
int main()
{
int
cost[max][max]={{INFINITE,2,4,INFINITE},{2,INFINITE,1,5},{4,1,INFINITE,2},{INFINITE
,5,2,INFINITE}};
int preceed[max]={0},i,distance[max];
clrscr();
shortpath(cost,preceed,distance);
for(i=0;i<max;i++)
{
printf("The shortest path from 0 to %d is ",i);
printf("%d\n",distance[i]);
}
return 0;
getch();
}
OUTPUT
The shortest path from 0 to 0 is 0
The shortest path from 0 to 1 is 2
The shortest path from 0 to 2 is 3
The shortest path from 0 to 3 is 5
EX NO 11(A) IMPLEMENTATION OF SEARCHING ALGORITHM

Algorithm :

Step 1: Read the elements of the list.

Step 2: Sort the input list.

Step 3: Find the mid value.

Step 4: Look at the element in the middle. If the key is equal to that, the search is finished.

Step 5: If the key is less than the middle element, do a binary search on the first half.

Step 6: If it's greater, do a binary search of the second half.

PROGRAM

#include<stdio.h>
#include<conio.h>
void main()
{
int a[25],i,j,temp,s,n,low,mid,high;
clrscr();
printf("\nEnter the Limilt : ");
scanf("%d",&n);
printf("\n\nEnter the elements\n");
for(i=0;i<n;i++)
{

scanf("%d",&a[i]);
}
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
printf("\n\nSorted list");
for(i=0;i<n;i++)
{
printf("\n%d",a[i]);
}
printf("\n\nEnter the elements to be searched : ");
scanf("%d",&s);
high=n-1;
low=0;
while(low<=high)
{
mid=(low+high)/2;
if(s>a[mid])
low=mid+1;
else if(s<a[mid])
high=mid-1;
else if(s==a[mid])
{
printf("\n\nThe element %d is found",s);
getch();
exit(0);
}
}
 printf("\n\nThe element %d is not found",s);
getch();
}
OUTPUT

Enter the elements

5
4
3
2
1

Sorted list
1
2
3
4
5

Enter the element to be searched : 5

The element 5 is found.

Ex no 11(b) IMPLEMENTATION SELECTION SORT

ALGORITHM:

1. Find the minimum value in the list

2. Swap it with the value in the first position
3. Repeat the steps above for the remainder of the list (starting at the second position and
advancing each time)
PROGRAM

#include<stdio.h>
#include<conio.h>
int n,i=0,j=0,t=0,k=0,a[30];
void main()
{
clrscr();
printf("\nEnter how many numbers you want to sort\n");
scanf("%d",&n);
printf("\nEntyer the numbers \n");
for (i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for (i=1;i<n;i++)
{
printf("\n\nPASS %d-->",i);
t=a[i];
for(j=i-1;((j>=0)&&(t<a[j]));j--)
a[j+1]=a[j];
a[j+1]=t; //j decreases
for(k=0;k<n;k++)
printf("%d ",a[k]);
}
printf("\n\nThe sorted list is : ");
for (j=0;j<n;j++)
printf("%d ",a[j]);
getch();
}
OUTPUT

Enter how many elements you want to sort

Enter the numbers

5
4
3
2
1

PASS->1 15432
PASS->2 12543
PASS->3 12354
PASS->4 12345

Final sorted list is 1 2 3 4 5

Ex no 12 HASHING - COLLISION TECHNIQUE

ALGORITHM

1.Create an array of linked list(i.e) hash table.

2. take a key and a value to be stored in hash table as input.
3.Using the generated index extract the linked list sorted in that array index.
4.Incase of absence of a linked list, create one and insert a data item into it.
5. incase list exit search for the key in the linked list and add the data item at the end of the list.
6. To display all the element of hash table, linked list at each index is extracted and element are
read until we reach at its end.
7.TO remove a key from hash table we will first calculate its index and extract its linked list.
PROGRAM
#include <stdio.h>
#include <conio.h>
int tsize;

int hasht(int key)

{
int i ;
i = key%tsize ;
return i;
}

//-------LINEAR PROBING-------
int rehashl(int key)
{
int i ;
i = (key+1)%tsize ;
return i ;
}

//-------QUADRATIC PROBING-------
int rehashq(int key, int j)
{
int i ;
i = (key+(j*j))%tsize ;
return i ;
}

void main()
{
int key,arr[20],hash[20],i,n,s,op,j,k ;
clrscr() ;
printf ("Enter the size of the hash table: ");
scanf ("%d",&tsize);

printf ("\nEnter the number of elements: ");

scanf ("%d",&n);

for (i=0;i<tsize;i++)
hash[i]=-1 ;

printf ("Enter Elements: ");

for (i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}

do
{
printf("\n\n1.Linear Probing\n2.Quadratic Probing \n3.Exit \nEnter your option: ");
scanf("%d",&op);
switch(op)
{
case 1:
for (i=0;i<tsize;i++)
hash[i]=-1 ;

for(k=0;k<n;k++)
{
key=arr[k] ;
i = hasht(key);
while (hash[i]!=-1)
{
i = rehashl(i);
}
hash[i]=key ;
}
printf("\nThe elements in the array are: ");
for (i=0;i<tsize;i++)
{
printf("\n Element at position %d: %d",i,hash[i]);
}
break ;

case 2:
for (i=0;i<tsize;i++)
hash[i]=-1 ;

for(k=0;k<n;k++)
{
j=1;
key=arr[k] ;
i = hasht(key);
while (hash[i]!=-1)
{
i = rehashq(i,j);
j++ ;
}
hash[i]=key ;
}
printf("\nThe elements in the array are: ");
for (i=0;i<tsize;i++)
{
printf("\n Element at position %d: %d",i,hash[i]);
}
break ;

}
}while(op!=3);

getch() ;
}
OUTPUT

Enter the size of the hash table: 10

Enter the number of elements: 8

Enter Elements: 72 27 36 24 63 81 92 101

1.Linear Probing
2.Quadratic Probing
3.Exit
Enter your option: 1

The elements in the array are:

Element at position 0: -1
Element at position 1: 81
Element at position 2: 72
Element at position 3: 63
Element at position 4: 24
Element at position 5: 92
Element at position 6: 36
Element at position 7: 27
Element at position 8: 101
Element at position 9: -1

1.Linear Probing
2.Quadratic Probing
3.Exit
Enter your option: 2

The elements in the array are:

Element at position 0: -1
Element at position 1: 81
Element at position 2: 72
Element at position 3: 63
Element at position 4: 24
Element at position 5: 101
Element at position 6: 36
Element at position 7: 27
Element at position 8: 92
Element at position 9: -1