220410149032

PRACTICAL 9
AIM: To write a C Program to Implement Queue Data Structure using Linked List
#include <stdio.h>
#include <stdlib.h>
struct node
{
int info;
struct node *ptr;
}*front,*rear,*temp,*front1;

int frontelement();
void enq(int data);
void deq();
void empty();
void display();
void create();
void queuesize();

int count = 0;

void main()
{
int no, ch, e;

printf("\n 1 - Enque");
printf("\n 2 - Deque");
printf("\n 3 - Front element”) ;
printf ("\n 4 - Empty");
printf("\n 5 - Exit");
printf("\n 6 - Display");
printf("\n 7 - Queue size");
create();
 220410149032
while (1)
{
printf("\n Enter choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter data : ");
scanf("%d", &no);
enq(no);
break;
case 2:
deq();
break;
case 3:
e = frontelement();
if (e != 0)
printf("Front element : %d", e);
else
printf("\n No front element in Queue as queue is empty");
break;
case 4:
empty();
break;
case 5:
exit(0);
case 6:
display();
break;
case 7:
queuesize();
break;
default:
 220410149032
printf("Wrong choice, Please enter correct choice ");
break;
}
}
}
void create()
{
front = rear = NULL;
}
void queuesize()
{
printf("\n Queue size : %d", count);
}
void enq(int data)
{
if (rear == NULL)
{
rear = (struct node *)malloc(1*sizeof(struct node));
rear->ptr = NULL;
rear->info = data;
front = rear;
}
else
{
temp=(struct node *)malloc(1*sizeof(struct node));
rear->ptr = temp;
temp->info = data;
temp->ptr = NULL;

rear = temp;
}
count++;
}
 220410149032
void display()
{
front1 = front;

if ((front1 == NULL) && (rear == NULL))

{
printf("Queue is empty");
return;
}
while (front1 != rear){
printf("%d ", front1->info);
front1 = front1->ptr;
}
if (front1 == rear)
printf("%d", front1->info);
}
void deq()
{
front1 = front;

if (front1 == NULL)
{
printf("\n Error: Trying to display elements from empty queue");
return;
}
else
if (front1->ptr != NULL)
{
front1 = front1->ptr;
printf("\n Dequed value : %d", front->info);
free(front);
front = front1;
}
 220410149032
else {
printf("\n Dequed value : %d", front->info);
free(front);
front = NULL;
rear = NULL;
}
count--;
}
int frontelement()
{
if ((front != NULL) && (rear != NULL))
return(front->info);
else
return 0;
}
void empty()
{
if ((front == NULL) && (rear == NULL))
printf("\n Queue empty");
else
printf("Queue not empty");
}
 220410149032

PRACTICAL 10
AIM:Write a program to implement following operations on the doubly linked list.
(a) Insert a node at the front of the linked list.
(b) Insert a node at the end of the linked list.
(c) Delete a last node of the linked list.
(d) Delete a node before specified position.
#include<stdio.h>
#include<stdlib.h>
struct ND{
int info;
struct ND *next,*prev;
};
struct ND *inbeg(struct ND *first,int X){
struct ND *nn;
nn=(struct ND *)malloc(sizeof(struct ND));
if (nn==NULL){
printf("Allocation Error!!");
return first;
}
nn->info=X;
nn->prev=NULL;
nn->next=NULL;
if(first==NULL){
first=nn;
return first;
}
else{
nn->next=first;
first->prev=nn;
first=nn;
return first;
}
 220410149032
};
struct ND *inend(struct ND *first,int X){
struct ND *nn,*temp;
temp=first;
nn=(struct ND *)malloc(sizeof(struct ND));
if (nn==NULL){
printf("Allocation Error!!");
return first;
}
nn->info=X;
nn->prev=NULL;
nn->next=NULL;
if(first==NULL){
first=nn;
return first;
}
while(temp->next!=NULL){
temp=temp->next;
}
nn->prev=temp;
temp->next=nn;
return first;
};
struct ND *delbeg(struct ND *first){
if(first==NULL){
printf("EMPTY LIST\n");
return first;}
if(first->next==NULL){
struct ND *temp=first;
first=NULL;
free(temp);
return first; }
else{
struct ND *temp=first;
first=first->next;
 220410149032
first->prev=NULL;
free(temp);
return first;
}
};
struct ND *delast(struct ND *first){
if(first==NULL){
printf("UNDERFLOW\n");
return first; }
else if(first->next==NULL){
struct ND *temp=first;
first=NULL;
free(temp);
return first; }
else{
struct ND *temp=first;
while(temp->next!=NULL){
temp=temp->next; }
temp->prev->next=NULL;
free(temp);
return first;
}
};
void delposbefore(struct ND **first,int y){
int i=0;
int n=y;
struct ND *temp=*first;
struct ND *del;
if(temp==NULL){
printf("LIST IS EMPTY!! Kindly add elements..\n");
return;
}
while(i!=n){
 220410149032
temp=temp->next;
if(temp==NULL){
printf("End of list!!!\n");
return;
}
i++;
}
del=temp;
(temp->prev->next)=temp->next;
(temp->next->prev)=temp->prev;
free(temp);
}
void traverse(struct ND *first){
struct ND *curr;
if(first==NULL){
printf("Empty list.\n");
return;
}
curr=first;
while(curr->next!=NULL){
printf("%d\n",curr->info);
curr=curr->next;
}
printf("%d\n",curr->info);
}
int main(){
struct ND *first=NULL;
first=inbeg(first,10);
first=inbeg(first,20);
first=inbeg(first,30);
first=inbeg(first,40);
first=inend(first,50);
first=inend(first,60);
 220410149032
first=inend(first,70);
first=inend(first,80);
traverse(first);
printf("After deletion operation:\n");
first=delbeg(first);
first=delbeg(first);
first=delast(first);
first=delast(first);
delposbefore(&first,2);
traverse(first);
return 0;
}
 220410149032

PRACTICAL 11
AIM: Write a program to implement following operations on the circular linked list.
(a) Insert a node at the end of the linked list.
(b) Insert a node before specified position.
(c) Delete a first node of the linked list.
(d) Delete a node after specified position.
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *next;
};
struct node *head;
struct node *create(int);
void insert_at_begin(int);
void insert_at_end(int);
void insert_at_position(int, int);
void delete_at_begin();
void delete_at_end();
void delete_at_position(int);
void search(int);
void update(int, int);
void print_list();
void print_list_reverse();
int size_of_list();
 220410149032
int getData();
int getPosition();
int main()
{
char user_active = 'Y';
int user_choice;
int data, position;
while(user_active == 'Y' || user_active == 'y')
{
printf("\n\n------ Circular Singly Linked List -------\n");
printf("\n1. Insert a node at beginning");
printf("\n2. Insert a node at end");
printf("\n3. Insert a node at given position");
printf("\n\n4. Delete a node from beginning");
printf("\n5. Delete a node from end");
printf("\n6. Delete a node from given position");
printf("\n\n7. Print list from beginning");
printf("\n8. Print list from end");
printf("\n9. Search a node data");
printf("\n10. Update a node data");
printf("\n11. Exit");
printf("\n\n------------------------------\n");
printf("\nEnter your choice: ");
scanf("%d", &user_choice);
printf("\n------------------------------\n");
switch(user_choice)
{
case 1:
printf("\nInserting a node at beginning");
data = getData();

insert_at_begin(data);
break;
case 2:
printf("\nInserting a node at end");
data = getData();
 220410149032
insert_at_end(data);
break;
case 3:
printf("\nInserting a node at the given position");
data = getData();
position = getPosition();
insert_at_position(data, position);
break;
case 4:
printf("\nDeleting a node from beginning\n");
delete_at_begin();
break;
case 5:
printf("\nDeleting a node from end\n");
delete_at_end();
break;
case 6:
printf("\nDelete a node from given position\n");
position = getPosition();
delete_at_position(position);
break;
case 7:
printf("\nPrinting the list from beginning\n\n");
print_list();
break;
case 8:
printf("\nPrinting the list from end\n\n");
if (head == NULL) {
printf("\n\tList is Empty!\n");
} else {
print_list_reverse(head);
}
break;
case 9:
printf("\nSearching the node data");
data = getData();
 220410149032
search(data);
break;
case 10:
printf("\nUpdating the node data");
data = getData();
position = getPosition();
update(position, data);
break;
case 11:
printf("\nProgram was terminated\n\n");
return 0;
default:
printf("\n\t Invalid Choice\n");
} printf("\
n...............................\n");
printf("\nDo you want to continue? (Y/N) : ");
fflush(stdin);
scanf(" %c", &user_active);
}
return 0;
}
struct node *create(int data){
struct node *new_node = (struct node *)malloc(sizeof(struct node));

if (new_node == NULL) {
printf("\nMemory can't be allocated.\n");
return NULL;
}
new_node->data = data;
new_node->next = NULL;
return new_node;
}
void insert_at_begin(int data){
struct node *new_node = create(data);

if (new_node != NULL){
 220410149032
struct node *last = head;
if (head == NULL){
head = new_node;
new_node->next = head;
return;
}
while (last->next != head){
last = last->next;
}
last->next = new_node;
new_node->next = head;
head = new_node;
}
}
void insert_at_end(int data){
struct node *new_node = create(data);
if (new_node != NULL)
{
if (head == NULL) {
head = new_node;
new_node->next = head;
return;
}
struct node *last = head;
while (last->next != head){
last = last->next;
}
}
}
void insert_at_position(int position, int data){
if (position <= 0){
printf("\nInvalid Position\n");
}
else if (head == NULL && position > 1) {
printf("\nInvalid Position\n");
}
 220410149032
else if (head != NULL && position > size_of_list()) {
printf("\nInvalid Position\n");
}
else if (position == 1){
insert_at_begin(data);
}
else {
struct node *new_node = create(data);
if (new_node != NULL){
struct node *temp = head, *prev = NULL;
int i = 1;
while (++i <= position) {
prev = temp;
temp = temp->next;
}
prev->next = new_node;

new_node->next = temp;
}
}
}

void delete_at_begin(){
if (head == NULL){
printf("\n List is Empty! \n");
return;
}
struct node *last = head;
struct node *temp = head;

if (last->next == head){
free(last);
head = NULL;
return;
}
while (last->next != head) {
 220410149032
last = last->next;
}
head = head->next;
last->next = head;
free(temp);
temp = NULL;
}
void delete_at_end(){
if (head == NULL){
printf("\n List is Empty! \n");
return;
}
struct node *prev = head;
struct node *temp = head->next;
if (prev->next == head) {
free(prev);
head = NULL;
return;
}
while (temp->next != head){
prev = temp;
temp = temp->next;
}
prev->next = head;
free(temp);
temp = NULL;
}
void delete_at_position(int position){
if (position <= 0){
printf("\n Invalid Position \n");
}
else if (position > size_of_list()){
printf("\n Invalid position \n");
}
else if (position == 1){
delete_at_begin();
 220410149032
}
else if (position == size_of_list()){
delete_at_end();
}
else{
struct node *temp = head;
struct node *prev = NULL;
int i = 1;
while (i < position){
prev = temp;
temp = temp->next;
i += 1;
}
prev->next = temp->next;
free(temp);
temp = NULL;
}
}
void print_list(){
struct node *temp = head;

if (head == NULL) {
printf("\n List is Empty! \n");
return;
}
printf("\n");
do{
printf("%d ", temp->data);
temp = temp->next;
}
while (temp != head);
printf("\n");
}
void print_list_reverse(struct node* temp){
if (temp->next == head) {
printf("%d ", temp->data);
 220410149032
return;
}
print_list_reverse(temp->next);
printf("%d ", temp->data);
}
void search(int key){
struct node* temp = head;

do {
if (temp->data == key){
printf("\n\t Data Found\n");
return;
}
temp = temp->next;
}
while (temp->next != head);
printf("\n\tData not Found\n");
}
void update(int position, int new_data){
if (position <= 0 || position > size_of_list()){
printf("\n Invalid position\n");
return;
}
struct node* temp = head;
int i = 0;
while (i <= position) {
temp = temp->next;
i += 1;
}
temp->data = new_data;
}
int size_of_list(){
if (head == NULL) {
return 0;
}
struct node *temp = head;
 220410149032
int count = 1;

count += 1;
temp = temp->next;
}
return count;
}
int getData(){
int data;
printf("\n\nEnter Data: ");
scanf("%d", &data);
return data;
}
int getPosition(){
int pos;
printf("\n\nEnter Position: ");
scanf("%d", &pos);
return pos;
}
 220410149032

PRACTICAL 13
AIM: To write a program to implement Quick Sort
#include<stdio.h>
void quicksort(int number[25],int first,int last){
int i, j, pivot, temp;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
 220410149032
while(number[i]<=number[pivot]&&i<last)
i++;
while(number[j]>number[pivot])
j--;
if(i<j){
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}
temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
quicksort(number,first,j-1);
quicksort(number,j+1,last);
}
}
int main(){

int i, count, number[25];

220410149032
printf("How many elements are u going to enter?: ");
scanf("%d",&count);
printf("Enter %d elements: ", count);
for(i=0;i<count;i++)
scanf("%d",&number[i]);
quicksort(number,0,count-1);
printf("Order of Sorted elements: ");
for(i=0;i<count;i++)
printf(" %d",number[i]);
return 0;
}
 220410149032

PRACTICAL 14
AIM: To write a program to implement Merge Sort
#include <stdio.h>
void mergeSort(int[], int, int, int);
void partition(int[], int, int);
int main() {
int list[50];
 220410149032
int i, size;
printf("Enter Total Number of Elements:");
scanf("%d", & size);
printf("Enter The Elements:\n");
for (i = 0; i < size; i++) {
scanf("%d", & list[i]);
}
partition(list, 0, size - 1);
printf("After Merge Sort:\n");
for (i = 0; i < size; i++) {
printf("%d ", list[i]);
}
return 0;
}
void partition(int list[], int low, int high) {
int mid;
if (low < high) {
mid = (low + high) / 2;
partition(list, low, mid);
partition(list, mid + 1, high);
mergeSort(list, low, mid, high);
}
}
void mergeSort(int list[], int low, int mid, int high) {
int i, mi, k, lo, temp[50];
lo = low;
i = low;
mi = mid + 1;
while ((lo <= mid) && (mi <= high)) {
if (list[lo] <= list[mi]) {
temp[i] = list[lo];
lo++;
} else {
temp[i] = list[mi];
mi++;
}
i++;
}
 220410149032
if (lo > mid) {
for (k = mi; k <= high; k++) {
temp[i] = list[k];
i++;
}
} else {
for (k = lo; k <= mid; k++) {
temp[i] = list[k];
i++;
}
}
for (k = low; k <= high; k++) {
list[k] = temp[k];
}
}
220410149032
220410149032