AMITY UNIVERSITY

CHHATTISGARH - 492014

DATA STRUCTRES USING C LAB

CHHATTISGARH

Course Name: Data Structures using C

Course code: CSE3306

Submitted By: Submitted To:

NAME : Sonal Dhomne Ms. Jyoti Singh

E. No. : A80105221063 Assistant Professor

1
INDEX

S No. Programs Page Signature

No.
1 Singly Linked List

2 Doubly Linked List

3 Double Ended Queue using Array

Double Ended Queue using Linked

4
list

2
PROGRAM 1. 1. Write a C program that uses functions to perform the following:
a)Create a singly linked list of integers
b)Delete a given integer from the above linked list.
c)Display the contents of the above list after deletion.

CODE:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;

void beginsert ();

void lastinsert ();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{

printf("\n\nMain Menu");

3
printf("\n------------\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random location\n4.Delete from
Beginning"
"\n5.Delete from last\n6.Delete node after specified location\n7.Search for an element\n8.Show\
n9.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
beginsert();
break;
case 2:
lastinsert();
break;
case 3:
randominsert();
break;
case 4:
begin_delete();
break;
case 5:
last_delete();
break;
case 6:
random_delete();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
4
break;
default:
printf("Please enter valid choice..");
}
}
}
void beginsert()
{
struct node *ptr;
int item;
ptr = (struct node *) malloc(sizeof(struct node *));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value\n");
scanf("%d",&item);
ptr->data = item;
ptr->next = head;
head = ptr;
printf("\nNode inserted");
}

}
void lastinsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
5
}
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
ptr -> next = NULL;
head = ptr;
printf("\nNode inserted");
}
else
{
temp = head;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;
printf("\nNode inserted");
}
}
}
void randominsert()
{
int i,loc,item;
struct node *ptr, *temp;
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
6
else
{
printf("\nEnter element value");
scanf("%d",&item);
ptr->data = item;
printf("\nEnter the location after which you want to insert ");
scanf("\n%d",&loc);
temp=head;
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\ncan't insert\n");
return;
}

}
ptr ->next = temp ->next;
temp ->next = ptr;
printf("\nNode inserted");
}
}
void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nList is empty\n");
}
else
{
ptr = head;
head = ptr->next;
7
free(ptr);
printf("\nNode deleted from the begining ...\n");
}
}
void last_delete()
{
struct node *ptr,*ptr1;
if(head == NULL)
{
printf("\nlist is empty");
}
else if(head -> next == NULL)
{
head = NULL;
free(head);
printf("\nOnly node of the list deleted ...\n");
}

else
{
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
ptr1->next = NULL;
free(ptr);
printf("\nDeleted Node from the last ...\n");
}
}
void random_delete()
{
struct node *ptr,*ptr1;
8
int loc,i;
printf("\n Enter the location of the node after which you want to perform deletion \n");
scanf("%d",&loc);
ptr=head;
for(i=0;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;

if(ptr == NULL)
{
printf("\nCan't delete");
return;
}
}
ptr1 ->next = ptr ->next;
free(ptr);
printf("\nDeleted node %d ",loc+1);
}
void search()
{
struct node *ptr;
int item,i=0,flag;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
9
if(ptr->data == item)
{
printf("item found at location %d ",i+1);
flag=0;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("Item not found\n");
}
}

void display()
{
struct node *ptr;
ptr = head;
if(ptr == NULL)
{
printf("Nothing to print");
}
else
{
printf("\nprinting values . . . . .\n");
while (ptr!=NULL)
{
printf("\n%d",ptr->data);
10
ptr = ptr -> next;
}
}
}

OUTPUT:

11
12
13
PROGRAM 2. Write a C program that uses functions to perform the following:
a)Create a doubly linked list of integers.
b)Delete a given integer from the above doubly linked list.
c)Display the contents of the above list after deletion.

CODE:

#include <stdio.h>
#include <stdlib.h>

// Linked List Node

struct node {
int info;
struct node *prev, *next;
};
struct node* start = NULL;

// Function to traverse the linked list

void traverse()
{
// List is empty
if (start == NULL) {
printf("\nList is empty\n");
return;
14
}
// Else print the Data
struct node* temp;
temp = start;
while (temp != NULL) {
printf("Data = %d\n", temp->info);
temp = temp->next;
}
}

// Function to insert at the front

// of the linked list
void insertAtFront()
{
int data;
struct node* temp;
temp = (struct node*)malloc(sizeof(struct node));
printf("\nEnter number to be inserted: ");
scanf("%d", &data);
temp->info = data;
temp->prev = NULL;

// Pointer of temp will be

// assigned to start
temp->next = start;
start = temp;
printf("\nNode inserted.");
}

// Function to insert at the end of

// the linked list
void insertAtEnd()
{
15
int data;
struct node *temp, *trav;
temp = (struct node*)malloc(sizeof(struct node));
temp->prev = NULL;
temp->next = NULL;
printf("\nEnter number to be inserted: ");
scanf("%d", &data);
temp->info = data;
temp->next = NULL;
trav = start;

// If start is NULL
if (start == NULL) {

start = temp;
}

// Changes Links
else {
while (trav->next != NULL)
trav = trav->next;
temp->prev = trav;
trav->next = temp;
}
printf("\nNode inserted.");
}

// Function to insert at any specified

// position in the linked list
void insertAtPosition()
{
int data, pos, i = 1;
struct node *temp, *newnode;
newnode = malloc(sizeof(struct node));
16
newnode->next = NULL;
newnode->prev = NULL;

// Enter the position and data

printf("\nEnter position : ");
scanf("%d", &pos);

// If start==NULL,
if (start == NULL) {
start = newnode;
newnode->prev = NULL;
newnode->next = NULL;
}

// If position==1,
else if (pos == 1) {
// this is author method its correct but we can simply call insertAtfront() function for this special
case
/* newnode->next = start;
newnode->next->prev = newnode;
newnode->prev = NULL;
start = newnode; */
insertAtFront();

// Change links
else {
printf("\nEnter number to be inserted: ");
scanf("%d", &data);
newnode->info = data;
temp = start;
while (i < pos - 1) {

17
temp = temp->next;
i++;
}
newnode->next = temp->next;
newnode->prev = temp;
temp->next = newnode;
temp->next->prev = newnode;
}
printf("\nNode inserted.");
}

// Function to delete from the front

// of the linked list
void deleteFirst()
{
struct node* temp;
if (start == NULL)
printf("\nList is empty\n");
else {
temp = start;
start = start->next;
if (start != NULL)
start->prev = NULL;
free(temp);
}
printf("\nNode deleted.");
}

// Function to delete from the end

// of the linked list
void deleteEnd()
{
struct node* temp;
if (start == NULL)
18
printf("\nList is empty\n");
temp = start;
while (temp->next != NULL)
temp = temp->next;
if (start->next == NULL)
start = NULL;
else {
temp->prev->next = NULL;
free(temp);
}
printf("\nNode deleted.");
}

// Function to delete from any specified

// position from the linked list
void deletePosition()
{
int pos, i = 1;
struct node *temp, *position;
temp = start;

// If DLL is empty
if (start == NULL)
printf("\nList is empty\n");

// Otherwise
else {
// Position to be deleted
printf("\nEnter position : ");
scanf("%d", &pos);

// If the position is the first node

if (pos == 1) {
deleteFirst(); // im,proved by Jay Ghughriwala on GeeksforGeeks
19
if (start != NULL) {
start->prev = NULL;
}
free(position);
return;
}

// Traverse till position

while (i < pos - 1) {
temp = temp->next;
i++;
}
// Change Links
position = temp->next;
if (position->next != NULL)
position->next->prev = temp;
temp->next = position->next;

// Free memory
free(position);
}
printf("\nNode deleted.");
}

// Driver Code
int main()
{
int choice;
while (1) {
printf("\n\n\tMain Menu");
printf("\n\t------------\n");

printf("\n\t1 Display\n");
printf("\t2 Insertion at"
20
" starting\n");
printf("\t3 Insertion at"
" end\n");
printf("\t4 Insertion at "
"any position\n");
printf("\t5 Deletion of "
"first element\n");
printf("\t6 Deletion of "
"last element\n");
printf("\t7 Deletion of "
"element at any position\n");
printf("\t8 Exit\n");
printf("\nEnter Choice :\n");
scanf("%d", &choice);

switch (choice) {
case 1:
traverse();
break;
case 2:
insertAtFront();
break;
case 3:
insertAtEnd();
break;
case 4:
insertAtPosition();
break;
case 5:
deleteFirst();
break;
case 6:
deleteEnd();
break;
21
case 7:
deletePosition();
break;

case 8:
exit(1);
break;
default:
printf("Incorrect Choice. Try Again \n");
continue;
}
}
return 0;

OUTPUT:

22
23
24
25
PROGRAM 3. Write C programs to implement a double ended queue ADT using
i)array
ii)doubly linked list respectively.

CODE:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define size 5

int main()
{
int arr[size],R=-1,F=0,te=0,ch,n,i,x;

for(;;) // An infinite loop

{

printf("F=%d R=%d\n\n",F,R);
printf("1. Add Rear\n");
printf("2. Delete Rear\n");
printf("3. Add Front\n");
printf("4. Delete Front\n");
printf("5. Display\n");
printf("6. Exit\n");
printf("Enter Choice: ");
scanf("%d",&ch);

switch(ch)
{
case 1:
if(te==size)
{

26
printf("Queue is full");
getch(); // pause the loop to see the message
}
else
{
printf("Enter a number ");
scanf("%d",&n);
R=(R+1)%size;
arr[R]=n;
te=te+1;
}
break;

case 2:
if(te==0)
{
printf("Queue is empty");
getch(); // pause the loop to see the message
}
else
{
if(R==-1)
{
R=size-1;
}
printf("Number Deleted From Rear End = %d",arr[R]);
R=R-1;
te=te-1;
getch(); // pause the loop to see the number
}
break;

case 3:
if(te==size)
27
{
printf("Queue is full");
getch(); // pause the loop to see the message
}
else
{
printf("Enter a number ");
scanf("%d",&n);
if(F==0)
{
F=size-1;
}
else
{
F=F-1;
}
arr[F]=n;
te=te+1;
}
break;

case 4:
if(te==0)
{
printf("Queue is empty");
getch(); // pause the loop to see the message
}
else
{
printf("Number Deleted From Front End = %d",arr[F]);
F=(F+1)%size;
te=te-1;
getch(); // pause the loop to see the number
}
28
break;

case 5:
if(te==0)
{
printf("Queue is empty");
getch(); // pause the loop to see the message
}
else
{
x=F;
for(i=1; i<=te; i++)
{
printf("%d ",arr[x]);
x=(x+1)%size;
}
getch(); // pause the loop to see the numbers
}
break;

case 6:
exit(0);
break;

default:
printf("Wrong Choice");
getch(); // pause the loop to see the message
}
}
return 0;
}

29
OUTPUT:

30
31
CODE:
#include<stdio.h>
#include<process.h>
#define MAX 30

typedef struct dequeue

{
int data[MAX];
int rear,front;
}dequeue;

void initialize(dequeue *p);

int empty(dequeue *p);
int full(dequeue *p);
void enqueueR(dequeue *p,int x);
void enqueueF(dequeue *p,int x);
int dequeueF(dequeue *p);
int dequeueR(dequeue *p);
void print(dequeue *p);

void main()
{
int i,x,op,n;
dequeue q;
initialize(&q);
do
{
printf("\n1.Create\n2.Insert(rear)\n3.Insert(front)\n4.Delete(rear)\n5.Delete(front)");
printf("\n6.Print\n7.Exit\n\nEnter your choice:");
scanf("%d",&op);
switch(op)
{
case 1: printf("\nEnter number of elements:");

32
scanf("%d",&n);
initialize(&q);
printf("\nEnter the data:");
for(i=0;i<n;i++)
{
scanf("%d",&x);
if(full(&q))
{
printf("\nQueue is full!!");
exit(0);
}
enqueueR(&q,x);
}
break;
case 2: printf("\nEnter element to be inserted:");
scanf("%d",&x);
if(full(&q))
{
printf("\nQueue is full!!");
exit(0);
}
enqueueR(&q,x);
break;
case 3: printf("\nEnter the element to be inserted:");
scanf("%d",&x);
if(full(&q))
{
printf("\nQueue is full!!");
exit(0);
}

enqueueF(&q,x);
break;
case 4: if(empty(&q))
33
{
printf("\nQueue is empty!!");
exit(0);
}
x=dequeueR(&q);
printf("\nElement deleted is %d\n",x);
break;
case 5: if(empty(&q))
{
printf("\nQueue is empty!!");
exit(0);
}
x=dequeueF(&q);
printf("\nElement deleted is %d\n",x);
break;
case 6: print(&q);
break;
default: break;
}
}while(op!=7);
}

void initialize(dequeue *P)

{
P->rear=-1;
P->front=-1;
}

int empty(dequeue *P)

{
if(P->rear==-1)
return(1);
return(0);
}
34
int full(dequeue *P)
{
if((P->rear+1)%MAX==P->front)
return(1);
return(0);
}

void enqueueR(dequeue *P,int x)

{
if(empty(P))
{
P->rear=0;
P->front=0;
P->data[0]=x;
}
else
{
P->rear=(P->rear+1)%MAX;
P->data[P->rear]=x;
}
}

void enqueueF(dequeue *P,int x)

{
if(empty(P))
{
P->rear=0;
P->front=0;
P->data[0]=x;
}
else
{
P->front=(P->front-1+MAX)%MAX;
35
P->data[P->front]=x;
}
}

int dequeueF(dequeue *P)

{
int x;
x=P->data[P->front];
if(P->rear==P->front) //delete the last element
initialize(P);
else
P->front=(P->front+1)%MAX;
return(x);
}

int dequeueR(dequeue *P)

{
int x;
x=P->data[P->rear];
if(P->rear==P->front)
initialize(P);
else
P->rear=(P->rear-1+MAX)%MAX;
return(x);
}

void print(dequeue *P)

{
if(empty(P))
{
printf("\nQueue is empty!!");
exit(0);
}
int i;
36
i=P->front;
while(i!=P->rear)
{
printf("\n%d",P->data[i]);
i=(i+1)%MAX;
}
printf("\n%d\n",P->data[P->rear]);
}

37
OUTPUT:

38
39
40