Term work

on

DATA STRUCTURE WITH C

(PCS 302)
2021-22

Submitted to: Submitted by:

Mr Rakesh Patra Sachin Rawat
Assistant Professor University Roll. No.: 2018675
GEHU, [Link] Class Roll. No./Section: 47/A

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

GRAPHIC ERA HILL UNIVERSITY, DEHRADUN

 2

Table of Contents
Program Program Name Page No
No.
1 Write a the C program to create an array by inserting N elements in it
then find second non repeating element from the array.

2 Write a the C program to create an array by inserting N elements in it

then find third repeating element from the array.

3 Write a C program Create a Dynamic array and then Reverse the array using
recursion and then finally print the array

4 Write a C Program implement STACK using array in menu driven form.

5
Write a C Program to Convert Infix to Postfix Expression using Stack.

6 Write a C Program to create singly linked list by adding nodes in the right
hand side and delete alternate node from the list and then print the final list.

7 Write a C Program implement STACK using Link List in menu driven form.

8 Write a C Program implement QUEUE using Link List in menu driven

form.

9 Write a C Program implement priority QUEUE using array in menu

driven form.

10 . Write a C Program implement QUEUE using array in menu driven form.

11 Write a C program to Evaluate Postfix Expression using Stack

12 . Write a C program to create TWO singly linked list L1 and L2 and sort both

Name- Sachin Rawat Roll Number: 2018675 Section-A

 3

the list and finally merge both the list such that L2 comes after L1.[ use double
pointer]

13 Write C program to create a doubly link list by adding the node right hand side
and then check list is in palindrome form or not.

14 Write a C program to create a circular link list by adding the nodes in right
hand side and then print the list.

Name- Sachin Rawat Roll Number: 2018675 Section-A

 4

DEPARTMENT OF CS & IT
[Link]. (CS & IT)
STUDENT LAB REPORT SHEET
Photograph
Name of Student ……………………………………….…….[Link]……………………………….………….. Passport Size

Address Permanent ………………………………………………………………………………………….………..

Father’s Name …………………………Occupation ……………………………MoNo……..…….….………

Mother’s Name ………………… …..Occupation……………………………MoNo…………….…………..

Section …………….Branch……………………Semester……………..Class Roll No………………. Grade ABC

Local Address…………………………………………………Email……………….……………………. Marks 5 3 1

S.N Practical D.O.P. Date of Grade Grade Total Student’s Teacher’s

o. Submiss (Viva) (Report Marks Signature Signature
ion File) (out of
10)
1 Practical-01

2 Practical-02

3 Practical-03

4 Practical-04

5 Practical-05

6 Practical-06

7 Practical-07

8 Practical-08

9 Practical-09

10 Practical-10

11 Practical-11

Name- Sachin Rawat Roll Number: 2018675 Section-A

 5

12 Practical-12

13 Practical-13

14 Practical-14

Name- Sachin Rawat Roll Number: 2018675 Section-A

 6

Q1. Write a the C program to create an array by inserting N elements

in it then find second non repeating element from the array.

#include<stdio.h>
#include<limits.h>

int main()
{

int n;
printf("enter the size of array ");
scanf("%d",&n);

int a[n];
printf("enter the elements \n");
for(int i=0;i<n;i++)
scanf("%d",&a[i]);

int maximum=a[0];
for(int i=1;i<n;i++)
{
if(maximum<a[i])
maximum=a[i];
}

int hash[maximum+1],counter=0,ans;
for(int i=0;i<maximum+1;i++)
{
hash[i]=0;
}

for(int i=0;i<n;i++)
{
hash[a[i]]++;

Name- Sachin Rawat Roll Number: 2018675 Section-A

 7

int flag=0;
for(int i=0;i<n;i++)
{
if(hash[a[i]]==1)
{
counter++;
if(counter==2)
{
flag=1;
ans=a[i];
break;
}
}
}

if(flag)
printf("Second Non Repeating number is %d",ans);
else
printf("There is no Second Non Repeating ");
}

Name- Sachin Rawat Roll Number: 2018675 Section-A

 8

Q2. Write a the C program to create an array by inserting N elements

in it then find third repeating element from the array.

#include<stdio.h>
#include<limits.h>

int main()
{

int n;
printf("enter the size of array ");
scanf("%d",&n);

int a[n];
printf("enter the elements \n");
for(int i=0;i<n;i++)
scanf("%d",&a[i]);

int maximum=a[0];
for(int i=1;i<n;i++)
{
if(maximum<a[i])
maximum=a[i];
}

int hash[maximum+1],counter=0,ans;
for(int i=0;i<maximum+1;i++)
{
hash[i]=0;
}

for(int i=0;i<n;i++)
{
hash[a[i]]++;
}

Name- Sachin Rawat Roll Number: 2018675 Section-A

 9

int flag=0;
for(int i=0;i<maximum+1;i++)
{
if(hash[i]>1)
{
counter++;
if(counter==3)
{
flag=1;
ans=i;
break;
}
}
}

if(flag)
printf("Third Repeating Element in array is %d",ans);
else
printf("There is no Third Repeating Element ");
}

Name- Sachin Rawat Roll Number: 2018675 Section-A

 10

Q3. Write a C program Create a Dynamic array and then Reverse the
array using recursion and then finally print the array.

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

void reverse(int a[],int n,int i)

{
if(n==0)
return ;

int temp=a[n-1];
reverse(a,n-1,i+1);
a[i]=temp;

int main()
{
int n;
printf("Enter the size of array ");
scanf("%d",&n);

int *p=(int*)malloc(n*sizeof(int));

for(int i=0;i<n;i++)
*(p+i)=i+1;

reverse(p,n,0);

for(int i=0;i<n;i++)
printf("%d ",p[i]);
}

Name- Sachin Rawat Roll Number: 2018675 Section-A

 11

Q4. Write a C Program implement STACK using array in menu

driven form.

#include<stdio.h>

void push(int stack[],int *top,int n)

{

int x;
if(*top>=n-1)
printf(" \n\tSTACK is over flow ");

else
{
printf(" Enter a value to be pushed:");
scanf("%d",&x);
*top=*top+1;
stack[*top]=x;
}

void pop(int stack[],int *top)

{

if(*top<=-1)
printf("\n\t Stack is under flow ");
else
{
printf("\n\t The popped elements is % d ",stack[*top]);
*top=*top-1;
}

void display(int stack[],int *top)

{
if(*top>=0)

Name- Sachin Rawat Roll Number: 2018675 Section-A

 12

{
printf("\n The elements in STACK \n");
for(int i=*top; i>=0; i--)
printf("\n%d ",stack[i]);

printf("\nPress Next Choice ");

}
else
printf("\n The STACK is empty ");

int main ()
{
int stack[100], choice, n, top=-1;

printf ("\n Enter the size of STACK[MAX=100]:");

scanf ("%d", &n);
printf ("\n\t STACK OPERATIONS USING ARRAY");
printf ("\n\t--------------------------------");
printf ("\n\t [Link]\n\t [Link]\n\t [Link]\n\t [Link]");
do{
printf ("\n Enter the Choice:");
scanf ("%d", &choice);

switch(choice)
{
case 1:
{
push(stack,&top,n);
break;
}
case 2:
{
pop(stack,&top);
break;
}
case 3:
{
display(stack,&top);
break;

Name- Sachin Rawat Roll Number: 2018675 Section-A

 13

}
case 4:
{
printf("\n\t EXIT POINT ");
break;
}
default:
printf ("\n\t Please Enter a Valid Choice (1 / 2 / 3 / 4) ");

}while(choice!=4);

return 0;
}

Name- Sachin Rawat Roll Number: 2018675 Section-A

 14

Q5. Write a C Program to Convert Infix to Postfix Expression using

Stack.

#include <stdio.h>
#include <ctype.h>

void push(char ch,char stack[],int* top)

{
if(*top+1==10)
printf("stack is full");
else
{
*top=*top+1;
stack[*top]=ch;
}
}

char pop(char stack[],int *top)

{
if(*top==-1)
{
printf("stack is empty");
}

char ch = stack[*top];
*top=*top-1;
return ch;

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

Name- Sachin Rawat Roll Number: 2018675 Section-A

 15

int main()
{
char stack[10];
int top=-1;

char exp[20];
char *e;
printf("enter the infix expression ");
scanf("%s",exp);

e=exp;

while(*e!='\0')
{
if(isalpha(*e))
printf("%c",*e);

else if(*e=='(')
push(*e,stack,&top);

else if(*e==')')
{
while(stack[top]!='(')
{

printf("%c",pop(stack,&top));
}
pop(stack,&top);
}

else
{
while( priority(stack[top]) >= priority(*e) )
{
printf("%c",pop(stack,&top));
}
push(*e,stack,&top);
}

e++;

Name- Sachin Rawat Roll Number: 2018675 Section-A

 16

while(top!=-1)
{
printf("%c",pop(stack,&top));
}

return 0;
}

Name- Sachin Rawat Roll Number: 2018675 Section-A

 17

Q6. Write a C Program to create singly linked list by adding nodes in

the right hand side and delete alternate node from the list and then
print the final list.

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

struct node
{
int data;
struct node *link;
};

struct node* insert(struct node* head,int x)

{
struct node *temp=(node *)malloc(sizeof(node));
temp->data=x;
temp->link=NULL;

if(head==NULL)
{
head=temp;
return head;
}

struct node *temp1=head;

while(temp1->link!=NULL)
{
temp1=temp1->link;
}

temp1->link=temp;

return head;
}

void print(struct node* temp1)

{
while(temp1!=NULL)

Name- Sachin Rawat Roll Number: 2018675 Section-A

 18

{
printf("%d ",temp1->data);
temp1=temp1->link;
}
}

void altranate_node(struct node* temp1)

{

struct node *temp2=temp1->link;

if(temp1==NULL || temp2==NULL)
return ;

while(temp1!=NULL && temp2!=NULL)

{

temp1->link=temp2->link;
temp1=temp2->link;

if(temp1!=NULL)
temp2=temp1->link;
}

int main()
{

struct node* head=NULL;

int x,n;
printf("enter the no of element you want to insert in linked list ");
scanf("%d",&n);

for(int i=0;i<n;i++)
{
scanf("%d",&x);
head=insert(head,x);
}
printf("\nPRINTIG LINKED LIST : ");
print(head);

Name- Sachin Rawat Roll Number: 2018675 Section-A

 19

printf("\n\nPRINTING ALTRANATE nodes in linked list : ");

altranate_node(head);

print(head);

Name- Sachin Rawat Roll Number: 2018675 Section-A

 20

Q7. Write a C Program implement STACK using Link List in menu

driven form.

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

struct node
{
int data;
struct node* link;
};

struct node* push(int x,struct node *head)

{

struct node* temp=(struct node *)malloc(sizeof(struct node));

temp->data=x;
temp->link=NULL;

if(head==NULL)
{
head=temp;
}
else
{
temp->link=head;
head=temp;
}

return head;
}

struct node* pop(struct node* head)

{
if(head==NULL)
{
printf("stack is empty\n");
}
else
{
printf("poped element is %d \n",head->data);
struct node *temp=head;

Name- Sachin Rawat Roll Number: 2018675 Section-A

 21

head=head->link;

free(temp);
}
return head;
}

void top_ele(struct node *head)

{
if(head==NULL)
{
printf("stack is empty\n");
}
else
{
printf("Toped element is %d \n",head->data);
}
}

void display(struct node *head)

{
if(head==NULL)
{
printf("stack is empty\n");
}
else
{
struct node* temp=head;
while(temp!=NULL)
{
printf("%d ",temp->data);
temp=temp->link;
}

}
}

int main()
{
int ch,x;
struct node* head=NULL;

Name- Sachin Rawat Roll Number: 2018675 Section-A

 22

printf("1. push\n2. pop\n3. top\n4. display\n5. exit\n");

while(1)
{
printf("\nEnter your choice ");
scanf("%d",&ch);

switch(ch)
{

case 1:
printf("Enter the value ");
scanf("%d",&x);
head = push(x,head);
break;

case 2:
head = pop(head);
break;

case 3:
top_ele(head);
break;

case 4:
display(head);
break;

case 5:
exit(0);
break;

Name- Sachin Rawat Roll Number: 2018675 Section-A

 23

Q8. Write a C Program implement QUEUE using Link List in menu

driven form.

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

struct node
{
int data;
struct node* link;
};

void push(int x,struct node **head,struct node **front)

{

struct node* temp=(struct node *)malloc(sizeof(struct node));

temp->data=x;
temp->link=NULL;

if(*head==NULL && *front==NULL)

{
*head=*front=temp;
}
else
{
(*head)->link=temp;
*head=temp;
}

void pop(struct node **head,struct node **front)

{
if(*head==NULL && *front==NULL)
{
printf("stack is empty\n");

Name- Sachin Rawat Roll Number: 2018675 Section-A

 24

}
else if(*head==*front)
{
printf("poped element is %d \n",(*front)->data);
*head=*front=NULL;
}
else
{
printf("poped element is %d \n",(*front)->data);
struct node *temp=*front;
*front=(*front)->link;

free(temp);
}

void top_ele(struct node **head,struct node **front)

{
if(*head==NULL && *front==NULL)
{
printf("stack is empty\n");
}
else
{
printf("top element is %d \n",(*front)->data);
}
}

void display(struct node **head,struct node **front)

{
if(*head==NULL)
{
printf("stack is empty\n");
}
else
{
struct node *temp=*front;
while(temp!=NULL)
{
printf("%d ",temp->data);
temp=temp->link;

Name- Sachin Rawat Roll Number: 2018675 Section-A

 25

}
}

int main()
{
int ch,x;
struct node *head=NULL,*front=NULL;

printf("1. push\n2. pop\n3. front element\n4. display\n5. exit\n");

while(1)
{
printf("\nEnter your choice ");
scanf("%d",&ch);

switch(ch)
{
case 1:
printf("Enter the value ");
scanf("%d",&x);
push(x,&head,&front);
break;

case 2:
pop(&head,&front);
break;

case 3:
top_ele(&head,&front);
break;

case 4:
display(&head,&front);
break;

case 5:
exit(0);
break;
} } }

Name- Sachin Rawat Roll Number: 2018675 Section-A

 26

Q9. Write a C Program implement priority QUEUE using array in

menu driven form.

#include<stdio.h>
#define MAX 10

void insert(int a[],int p[],int *rear)

{
if(*rear==MAX)
{
printf("Queue is full.\n");
return;
}

(*rear)++;

printf("Enter the value: ");

scanf("%d",&a[(*rear)]);
printf("Enter its priority: ");
scanf("%d",&p[(*rear)]);
}

int max_p(int p[],int rear)

{
if(rear==-1)
{
printf("Queue is empty.\n");
return -1;
}

int max_index=0;
for(int i=1;i<=rear;i++)
{
if(p[max_index]<p[i])
max_index=i;
}
return max_index;
}

void delete(int a[],int p[],int *rear)

{
if(*rear==-1)

Name- Sachin Rawat Roll Number: 2018675 Section-A

 27

{
printf("Queue is empty.\n");
return;
}

int p_index=max_p(p,*rear);
while(p_index<(*rear))
{
a[p_index]=a[p_index+1];
p[p_index]=p[p_index+1];
p_index++;
}
(*rear)--;

void display(int a[],int rear)

{
if(rear==-1)
printf("Queue is empty.\n");

for(int i=0;i<=rear;i++)
printf("%d ",a[i]);
printf("\n");
}

int main()
{
int a[MAX],p[MAX],rear=-1,choice;
printf("[Link]\[Link]\[Link]\n [Link]\n");

do
{
printf("Enter your choice: \n");
scanf("%d",&choice);

switch (choice)
{
case 1:
insert(a,p,&rear);
break;

case 2:

Name- Sachin Rawat Roll Number: 2018675 Section-A

 28

delete(a,p,&rear);
break;

case 3:
display(a,rear);
break;

case 0:
printf("Thanks for using the program");
break;
}

} while (choice!=0);

return 0;

Name- Sachin Rawat Roll Number: 2018675 Section-A

 29

Q10. Write a C Program implement QUEUE using array in menu

driven form.

#include <stdio.h>
#include<stdlib.h>
#include <stdbool.h>
#define N 5

int enqueue(int a[],int rear,int *front,int x)

{
if(rear==-1 && *front==-1)
rear=*front=0;

else if( ((rear+1)%N) == *front )

{
printf("Queue is FULL\n");
return rear;
}
else
rear=(rear+1)%N;

a[rear]=x;
return rear;
}

int dequeue(int a[],int *rear,int front)

{
if( *rear==-1 && front==-1 )
printf("Queue is empty\n");

else if(*rear==front)
*rear=front=-1;

else
front=(front+1)%N;

return front;
}

Name- Sachin Rawat Roll Number: 2018675 Section-A

 30

void display(int a[],int rear,int front)

{
int i;
for(i=front;(i%N)!=rear;i++)
{
printf("%d ",a[(i%N)]);
}
printf("%d ",a[i]);

void peek(int a[],int front)

{
if(front == -1)
{
printf("Error: cannot return front from empty queue\n");
return ;
}
else
printf("\nfront elemet is %d ",a[front]);
}

int main()
{
int a[N],rear=-1,front=-1;
int n,x;

printf("1. Enqueue\n2. Dequeue\n3. Display\n4. Front\n5. Exit");

while(1)
{

printf("\nEnter a choice ");

scanf("%d",&n);

switch(n)
{
case 1:
printf("Enter a element ");
scanf("%d",&x);
rear=enqueue(a,rear,&front,x);
break;

Name- Sachin Rawat Roll Number: 2018675 Section-A

 31

case 2:
front=dequeue(a,&rear,front);
break;

case 3:
display(a,rear,front);
break;

case 4:
peek(a,front);
break;

case 5:
exit(0);
}

Name- Sachin Rawat Roll Number: 2018675 Section-A

 32

Q11. Write a C program to Evaluate Postfix Expression using Stack

#include <stdio.h>
#include <ctype.h>

void push(int x,int stack[],int *top)

{
if(*top+1==20)
{
printf("stack is full");
return ;
}
else
{
*top=*top+1;
stack[*top]=x;
}

int pop(int stack[],int *top)

{
if(*top==-1)
{
printf("stack is empty");
}

int x = stack[*top];
*top=*top-1;

return x;
}

int operation(char x,int op1,int op2)

{
if(x=='/')
return op1/op2;
if(x=='*')
return op1*op2;
if(x=='+')

Name- Sachin Rawat Roll Number: 2018675 Section-A

 33

return op1+op2;
if(x=='-')
return op1-op2;

int main()
{
char ch[20];
int stack[20];
printf("Enter the postfix expression : ");
scanf("%s",ch);

char *e=ch;
int top=-1;

while(*e!='\0')
{
if(isdigit(*e))
push(*e-'0',stack,&top);

else
{
int op2=pop(stack,&top);
int op1=pop(stack,&top);

int ans=operation(*e,op1,op2);
push(ans,stack,&top);
}

e++;
}

printf("ANS = %d ",stack[top]);

return 0;
}

Name- Sachin Rawat Roll Number: 2018675 Section-A

 34

Q 12. Write a C program to create TWO singly linked list L1 and L2

and sort both the list and finally merge both the list such that L2
comes after L1.[ use double pointer]

#include<stdlib.h>

struct node
{
int value;
struct node *next;
};

void insert(struct node** head)

{
int value;
struct node* ptr;
ptr=(struct node*)malloc(sizeof(struct node));

if(ptr==NULL)
{
printf("Can't insert node.\n");
}

printf("Enter the value: ");

scanf("%d",&value);

ptr->value=value;
ptr->next=NULL;

if(*head==NULL)
*head=ptr;
else
{
ptr->next=*head;
*head=ptr;
}
}

Name- Sachin Rawat Roll Number: 2018675 Section-A

 35

void swap(struct node *a, struct node *b)

{
int temp = a->value;
a->value = b->value;
b->value = temp;
}

void sort(struct node *start)

{
if(start==NULL)
return;
struct node *ptr=start,*temp=start;

while(ptr!=NULL)
{
start=temp;
while(start->next!=NULL)
{
if(start->value>start->next->value)
{
swap(start,start->next);
}
start=start->next;
}
ptr=ptr->next;
}

printf("Sorting succesful.\n");
}

void display(struct node *ptr)

{
printf("Elements of the list are: ");
while(ptr!=NULL)
{
printf("%d ",ptr->value);
ptr=ptr->next;
}
printf("\n");
}

Name- Sachin Rawat Roll Number: 2018675 Section-A

 36

void merge(struct node **l1,struct node **l2)

{
struct node *ptr=*l1;
while(ptr->next!=NULL)
ptr=ptr->next;
ptr->next=*l2;
printf("Merging completed.\n");
}

int main()
{
int n;
struct node *l1=NULL,*l2=NULL;
printf("How many nodes you want to enter in L1: ");
scanf("%d",&n);

for(int i=0;i<n;i++)
insert(&l1);

printf("How many nodes you want to enter in L2: ");

scanf("%d",&n);

for(int i=0;i<n;i++)
insert(&l2);

display(l1);
display(l2);

sort(l1);
sort(l2);

merge(&l1,&l2);
printf("Sorted and merged list is: ") ;

display(l1);
return 0;
}

Name- Sachin Rawat Roll Number: 2018675 Section-A

 37

Q 13. Write C program to create a doubly link list by adding the node
right hand side and then check list is in palindrome form or not.

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

struct node
{
int data;
struct node *pre;
struct node *next;
};

struct node* insert_at_tail(struct node* head,int x)

{
struct node *temp=(struct node *)malloc(sizeof(struct node));
temp->pre=NULL;
temp->data=x;
temp->next=NULL;

if(head==NULL)
{
head=temp;
}
else
{
struct node *temp1=head;
while(temp1->next!=NULL)
{
temp1=temp1->next;
}
temp1->next=temp;
temp->pre=temp1;
}

return head;
}

void display(struct node *head)

Name- Sachin Rawat Roll Number: 2018675 Section-A

 38

{
struct node *temp1=head;

if(head==NULL)
{
printf("\nlist is empty");
}
else
{
while(temp1!=NULL)
{
printf("%d ",temp1->data);
temp1=temp1->next;
}
printf("\n");
}

int palindrome(struct node* head)

{
struct node* temp=head;
while(temp->next!=NULL)
{
temp=temp->next;
}

int flag=1;
while( (temp!=head) )
{
if(temp->data != head->data)
{
flag=0;
break;
}

temp=temp->pre;
head=head->next;
}

return flag;
}

Name- Sachin Rawat Roll Number: 2018675 Section-A

 39

int main()
{

struct node *head=NULL;

int n;

printf("Enter how many number you want to enter ");

scanf("%d",&n);

for(int i=0;i<n;i++)
{
int x;
printf("\nEnter the value ");
scanf("%d",&x);
head=insert_at_tail(head,x);
}

display(head);

if( palindrome(head) )
printf("\nPALINDROME ");
else
printf("\nNON PALINDROME");

return 0;
}

Name- Sachin Rawat Roll Number: 2018675 Section-A

 40

Q14. Write a C program to create a circular link list by adding the

nodes in right hand side and then print the list.

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

struct node
{
int data;
struct node *next;
};

struct node* insert_at_tail(struct node* head,int x)

{
struct node *temp=(struct node *)malloc(sizeof(struct node));
temp->next=NULL;
temp->data=x;
temp->next=NULL;

if(head==NULL)
{
head=temp;
temp->next=head;
}
else
{
struct node *temp1=head;
while(temp1->next!=head)
{
temp1=temp1->next;
}
temp1->next=temp;
temp->next=head;
}

return head;
}

Name- Sachin Rawat Roll Number: 2018675 Section-A

 41

void display(struct node* head)

{
struct node *temp1=head;

if(head==NULL)
{
printf("\nlist is empty");
}
else
{
while(temp1->next!=head)
{
printf("%d ",temp1->data);
temp1=temp1->next;
}
printf("%d ",temp1->data);
printf("\n");
}
}

int main()
{

struct node *head=NULL;

int n;
printf("Enter the number of values you want to insert in circular linked list ");
scanf("%d",&n);

for(int i=0;i<n;i++)
{
int x;
scanf("%d",&x);
head=insert_at_tail(head,x);

display(head);

return 0;
}

Name- Sachin Rawat Roll Number: 2018675 Section-A