# Data Structure PPTs.

Slides and Presentations of subject DFS (Data and File Structure) are attached:

# C++ program to find Factorial of a number.

Example of Factorial:
*************************************
Factorial of 1: 1
Factorial of 2: 2 x 1 = 2
Factorial of 3: 3 x 2 x 1 = 6
Factorial of 4: 4 x 3 x 2 x 1 = 24
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
Iterative Factorial of n: n x (n-1) x (n-2) x . . . . .1
Recursive Factorial of n: n x Factorial of n-1
*************************************
Iterative program for factorial:

```#include<iostream.h>
#include<conio.h>

void main()
{
clrscr();

int num, i, fact=1;

cout<<"Enter an integer greater than or equal to 1: ";
cin>>num;

for(i=num; i>=1; i--)
{
fact = fact*i;
}

cout<<"Factorial of "<<num<<" is: "<<fact;

getch();
}```

Recursive program for factorial:

```#include<iostream.h>
#include<conio.h>

int factorial(int n);

void main()
{
clrscr();

int num, fact;

cout<<"Enter an integer greater than or equal to 1: ";
cin>>num;

fact = factorial(num);

cout<<"Factorial of "<<num<<" is: "<<fact;

getch();
}

int factorial(int n)
{

if(n==1)
{
}
else
{
}

}```

# C program to insert a node at front, at end, and at any position in a Single Linked List.

sll-insert.c

```#include<stdio.h>
#include<conio.h>

//Create a basic structure for NODE from which new nodes can be created.
struct node
{
int data;
};

//Initialize 3 pointers as globals so that they do not need to be passed in functions.

//Prototypes for various user defined functions.
void insert_front();
void insert_end();
void insert_any();
void display();

void main()
{
int choice;
int cont = 1;

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

clrscr();

//Set the content of header node

while(cont == 1)
{
printf("\n1. Insert at front\n");
printf("\n2. Insert at end\n");
printf("\n3. Insert at any position\n");
scanf("%d", &choice);

switch(choice)
{
case 1:
insert_front();
break;
case 2:
insert_end();
break;
case 3:
insert_any();
break;
case 4:
display();
break;
}

printf("\n\nDo you want to continue? (1 / 0): ");
scanf("%d", &cont);
}

getch();
}

//Function to insert a node at the front of a single linked list.
void insert_front()
{
int data_value;

printf("\nEnter data of the node: ");
scanf("%d", &data_value);

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

temp->data = data_value;
}

//Function to insert a node at the end of a single linked list.
void insert_end()
{
int data_value;

printf("\nEnter data of the node: ");
scanf("%d", &data_value);

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

//Traverse to the end of the linked list.
{
}

temp->data = data_value;
}

//Function to insert a node at any position after a particular node.
void insert_any()
{
int data_value, key;

printf("\nEnter data of the node: ");
scanf("%d", &data_value);
printf("\nEnter data of the node after which new node is to be inserted: ");
scanf("%d", &key);

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

//Traverse till key is found or end of the linked list is reached.
while(ptr->link != NULL && ptr->data != key)
{
}
if(ptr->data == key)
{
temp->data = data_value;
}
else
{
}
}

//Function to display the contents of the linked list.
void display()
{
printf("\nContents of the linked list are: \n");
{
printf("%d ", ptr->data);
}
}```

# C program to delete a node from front, from end, and from any position in a Single Linked List.

sll-delete.c

```#include<stdio.h>
#include<conio.h>

//Create a basic structure for NODE from which new nodes can be created.
struct node
{
int data;
};

//Initialize pointers as globals so that they do not need to be passed in functions.
struct node *header, *ptr, *ptr1, *temp;

//Prototypes for various user defined functions.
void insert_end();
void delete_front();
void delete_end();
void delete_any();
void display();

void main()
{
int choice;
int cont = 1;

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

clrscr();

//Set the content of header node

while(cont == 1)
{
printf("\n1. Insert at end\n");
printf("\n2. Delete from front\n");
printf("\n3. Delete from end\n");
printf("\n4. Delete from anywhere\n");
scanf("%d", &choice);

switch(choice)
{
case 1:
insert_end();
break;
case 2:
delete_front();
break;
case 3:
delete_end();
break;
case 4:
delete_any();
break;
case 5:
display();
break;
}

printf("\n\nDo you want to continue? (1 / 0): ");
scanf("%d", &cont);
}

getch();
}

//Function to insert a node at the end of a single linked list.
void insert_end()
{
int data_value;

printf("\nEnter data of the node: ");
scanf("%d", &data_value);

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

//Traverse to the end of the linked list.
{
}

temp->data = data_value;
}

//Function to delete a node from the front of a linked list.
void delete_front()
{
//If the list is already empty
{
printf("\nEmpty Linked List. Deletion not possible.\n");
}
else
{
free(ptr);
printf("\nNode deleted from the front.\n");
}
}

//Function to delete a node from the end of a linked list.
void delete_end()
{
{
printf("\nEmpty Linked List. Deletion not possible.\n");
}
else
{
//Traverse to the end of the list.
{
ptr1 = ptr;
}
free(ptr);
printf("\nNode deleted from the end.\n");
}
}

//Function to delete any node from linked list.
void delete_any()
{
int key;

{
printf("\nEmpty Linked List. Deletion not possible.\n");
}
else
{
printf("\nEnter the data of the node to be deleted: ");
scanf("%d", &key);

while((ptr->link != NULL) && (ptr->data != key))
{
ptr1 = ptr;
}
if(ptr->data == key)
{
free(ptr);
printf("\nNode with data %d deleted.\n", key);
}
else
{
}
}
}

//Function to display the contents of the linked list.
void display()
{
printf("\nContents of the linked list are: \n");
{
printf("%d ", ptr->data);
}
}```

# C program for push, pop and peep operations in a stack using array.

stack.c

C program to implement push, pop and peep operations in a stack using an array is as follows:

```#include<stdio.h>
#include<conio.h>

#define SIZE 5
int top = -1;
int stack[SIZE];

//Function prototypes
void push(int item);
int pop();
int peep();

void main()
{
int item, choice, cont = 1;
clrscr();

while(cont == 1)
{
printf("\n1.Push onto stack.\n");
printf("\n2.Pop from stack.\n");
printf("\n3.Peep into stack.\n");

scanf("%d",&choice);

switch(choice)
{
case 1:
printf("\nEnter the value of item: ");
scanf("%d",&item);
push(item);
break;

case 2:
item = pop();
if(item != NULL)
{
printf("\nItem popped out: %d\n",item);
}
break;

case 3:
item = peep();
if(item != NULL)
{
printf("\nItem at top of stack: %d\n",item);
}
break;

default:
printf("\nInvalid choice.\n");
break;
}

printf("\nDo you want to continue (1/0): ");
scanf("%d",&cont);
}

getch();
}

//Function for push operation
void push(int item)
{
if(top >= SIZE-1)
{
printf("\nStack Overflow. Push not possible.\n");
}
else
{
top = top+1;
stack[top] = item;
}
}

//Function for pop operation
int pop()
{
int item = NULL;

if(top <= -1)
{
printf("\nStack Underflow. Pop not possible.\n");
}
else
{
item = stack[top];
stack[top] = NULL;
top = top-1;
}
return(item);
}

//Function for peep operation
int peep()
{
int item = NULL;

if(top <= -1)
{
printf("\nStack Underflow. No element in stack.\n");
}
else
{
item = stack[top];
}
return(item);
}```

# C program to insert a node at front, at end, and at any position in a Circular Linked List.

cll-insert.c

C program to insert a node at front, at end, and at any position in a Circular Linked List is as follows:

```#include<stdio.h>
#include<conio.h>

//Create a basic structure for NODE from which new nodes can be created.
struct node
{
int data;
};

//Initialize 3 pointers as globals so that they do not need to be passed in functions.

//Prototypes for various user defined functions.
void insert_front();
void insert_end();
void insert_any();
void display();

void main()
{
int choice;
int cont = 1;

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

clrscr();

//Set the content of header node

while(cont == 1)
{
printf("\n1. Insert at front\n");
printf("\n2. Insert at end\n");
printf("\n3. Insert at any position\n");
scanf("%d", &choice);

switch(choice)
{
case 1:
insert_front();
break;
case 2:
insert_end();
break;
case 3:
insert_any();
break;
case 4:
display();
break;
}

printf("\n\nDo you want to continue? (1 / 0): ");
scanf("%d", &cont);
}

getch();
}

//Function to insert a node at the front of a circular linked list.
void insert_front()
{
int data_value;

printf("\nEnter data of the node: ");
scanf("%d", &data_value);

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

temp->data = data_value;
}

//Function to insert a node at the end of a circular linked list.
void insert_end()
{
int data_value;

printf("\nEnter data of the node: ");
scanf("%d", &data_value);

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

//Traverse to the end of the linked list.
{
}

temp->data = data_value;
}

//Function to insert a node at any position after a particular node.
void insert_any()
{
int data_value, key;

printf("\nEnter data of the node: ");
scanf("%d", &data_value);
printf("\nEnter data of the node after which new node is to be inserted: ");
scanf("%d", &key);

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

//Traverse till key is found or end of the linked list is reached.
{
}
if(ptr->data == key)
{
temp->data = data_value;
}
else
{
}
}

//Function to display the contents of the linked list.
void display()
{
printf("\nContents of the linked list are: \n");
{
printf("%d ", ptr->data);
}
}```

# C program to delete a node from front, from end, and from any position in a Circular Linked List.

cll-delete.c

C program to delete a node from front, from end, and from any position in a Circular Linked List is as follows:

```#include<stdio.h>
#include<conio.h>

//Create a basic structure for NODE from which new nodes can be created.
struct node
{
int data;
};

//Initialize pointers as globals so that they do not need to be passed in functions.
struct node *header, *ptr, *ptr1, *temp;

//Prototypes for various user defined functions.
void insert_end();
void delete_front();
void delete_end();
void delete_any();
void display();

void main()
{
int choice;
int cont = 1;

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

clrscr();

//Set the content of header node

while(cont == 1)
{
printf("\n1. Insert at end\n");
printf("\n2. Delete from front\n");
printf("\n3. Delete from end\n");
printf("\n4. Delete from anywhere\n");
scanf("%d", &choice);

switch(choice)
{
case 1:
insert_end();
break;
case 2:
delete_front();
break;
case 3:
delete_end();
break;
case 4:
delete_any();
break;
case 5:
display();
break;
}

printf("\n\nDo you want to continue? (1 / 0): ");
scanf("%d", &cont);
}

getch();
}

//Function to insert a node at the end of a circular linked list.
void insert_end()
{
int data_value;

printf("\nEnter data of the node: ");
scanf("%d", &data_value);

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

//Traverse to the end of the linked list.
{
}

temp->data = data_value;
}

//Function to delete a node from the front of a linked list.
void delete_front()
{
//If the list is already empty
{
printf("\nEmpty Linked List. Deletion not possible.\n");
}
else
{
free(ptr);
printf("\nNode deleted from the front.\n");
}
}

//Function to delete a node from the end of a linked list.
void delete_end()
{
{
printf("\nEmpty Linked List. Deletion not possible.\n");
}
else
{
//Traverse to the end of the list.
{
ptr1 = ptr;
}
free(ptr);
printf("\nNode deleted from the end.\n");
}
}

//Function to delete any node from linked list.
void delete_any()
{
int key;

{
printf("\nEmpty Linked List. Deletion not possible.\n");
}
else
{
printf("\nEnter the data of the node to be deleted: ");
scanf("%d", &key);

{
ptr1 = ptr;
}
if(ptr->data == key)
{
free(ptr);
printf("\nNode with data %d deleted.\n", key);
}
else
{
}
}
}

//Function to display the contents of the linked list.
void display()
{
printf("\nContents of the linked list are: \n");
{
printf("%d ", ptr->data);
}
}```

# C program to convert from Infix to Postfix.

infix-to-postfix.c

C program to convert an arithmetic expression given in Infix notation to Postfix notation is as follows:

```#include<stdio.h>
#include<conio.h>

#define SIZE 100

int top = -1;
char stack[SIZE];

//Function prototypes
void push(char item);
char pop();
int is_operator(char symbol);
int precedence(char symbol);

void main()
{
int i, j;
char infix_exp[SIZE], postfix_exp[SIZE];
char item, x;
clrscr();

printf("\nEnter the arithmetic expression in Infix notation enclosed in parentheses: \n");
gets(infix_exp);

i = 0;
j = 0;
item = infix_exp[i++];
//Read symbol from Input string one at a time.
while(item != '\0')
{
//If the symbol is left parenthesis
if(item == '(')
{
push(item);
}
//If the symbol is an operand
else if((item >= 'A'  && item <= 'Z') || (item >= 'a' && item <= 'z'))
{
postfix_exp[j++] = item;
}
//If the symbol is an operator
else if(is_operator(item) == 1)
{
x = pop();
while(is_operator(x) == 1 && precedence(x) >= precedence(item))
{
postfix_exp[j++] = x;
x = pop();
}
push(x);
push(item);
}
//If the symbol is a right parenthesis
else if(item == ')')
{
x = pop();
while(x != '(')
{
postfix_exp[j++] = x;
x = pop();
}
}
//If the symbol is any other invalid character
else
{
printf("\nInvalid Arithmetic Expression.\n");
getch();
exit(0);
}

item = infix_exp[i++];
}

postfix_exp[j++] = '\0';
printf("\nArithmetic expression in Postfix notation: ");
puts(postfix_exp);

getch();
}

//Function for push operation
void push(char item)
{
if(top >= SIZE-1)
{
printf("\nStack Overflow. Push not possible.\n");
}
else
{
top = top+1;
stack[top] = item;
}
}

//Function for pop operation
char pop()
{
char item = NULL;

if(top <= -1)
{
printf("\nStack Underflow. Pop not possible.\n");
}
else
{
item = stack[top];
stack[top] = NULL;
top = top-1;
}
return(item);
}

//Function to check whether the symbol is an operator.
int is_operator(char symbol)
{
if(symbol == '^' || symbol == '*' || symbol == '/' || symbol == '+' || symbol == '-')
{
return 1;
}
else
{
return 0;
}
}

//Function which returns the precedence of the operator.
int precedence(char symbol)
{
if(symbol == '^')
{
return(3);
}
else if(symbol == '*' || symbol == '/')
{
return(2);
}
else if(symbol == '+' || symbol == '-')
{
return(1);
}
else
{
return(0);
}
}```

# C program to insert and delete elements from a Queue.

queue.c

C program to insert (Enqueue) and delete (Dequeue) elements from a simple Queue which is implemented using an array is as follows:

```#include<stdio.h>
#include<conio.h>

#define SIZE 5
int front = -1;
int rear = -1;
int queue[SIZE];

//Function prototypes
void enqueue(int item);
int dequeue();

void main()
{
int item, choice, cont = 1;
clrscr();

while(cont == 1)
{
printf("\n1.Enqueue into queue.\n");
printf("\n2.Dequeue from queue.\n");

scanf("%d",&choice);

switch(choice)
{
case 1:
printf("\nEnter the value of item: ");
scanf("%d",&item);
enqueue(item);
break;

case 2:
item = dequeue();
if(item != NULL)
{
printf("\nItem dequeued: %d\n",item);
}
break;

default:
printf("\nInvalid choice.\n");
break;
}

printf("\nDo you want to continue (1/0): ");
scanf("%d",&cont);
}

getch();
}

//Function for push operation
void enqueue(int item)
{
if(rear >= SIZE-1)
{
printf("\nQueue is full. Enqueue not possible.\n");
}
else
{
if(front == -1 && rear == -1)
{
front = front + 1;
}
rear = rear + 1;
queue[rear] = item;
printf("\nItem enqueued: %d\n", item);
}
}

//Function for pop operation
int dequeue()
{
int item = NULL;

if(front == -1 && rear == -1)
{
printf("\nQueue is empty. Dequeue not possible.\n");
}
else
{
item = queue[front];
queue[front] = NULL;

if(front == rear)
{
front = -1;
rear = -1;
}
else
{
front = front + 1;
}
}
return(item);
}```

# C program to insert and delete elements in a Circular Queue.

circular-queue.c

C program to insert (Enqueue) and delete (Dequeue) elements in a Circular Queue which is implemented using an array is as follows:

```#include<stdio.h>
#include<conio.h>

#define SIZE 5
int front = -1;
int rear = -1;
int queue[SIZE];

//Function prototypes
void enqueue_cq(int item);
int dequeue_cq();

void main()
{
int item, choice, cont = 1;
clrscr();

while(cont == 1)
{
printf("\n1.Enqueue into circular queue.\n");
printf("\n2.Dequeue from circular queue.\n");

scanf("%d",&choice);

switch(choice)
{
case 1:
printf("\nEnter the value of item: ");
scanf("%d",&item);
enqueue_cq(item);
break;

case 2:
item = dequeue_cq();
if(item != NULL)
{
printf("\nItem dequeued: %d\n",item);
}
break;

default:
printf("\nInvalid choice.\n");
break;
}

printf("\nDo you want to continue (1/0): ");
scanf("%d",&cont);
}

getch();
}

//Function for push operation
void enqueue_cq(int item)
{
int next;

if(front == -1 && rear == -1)
{
front = front + 1;
rear = rear + 1;
queue[rear] = item;
printf("\nItem enqueued: %d\n", item);
}
else
{
next = ((rear == (SIZE-1)) ? (rear % (SIZE-1)) : ((rear % (SIZE-1)) + 1));
if(next == front)
{
printf("\nQueue is full. Enqueue not possible.\n");
}
else
{
rear = next;
queue[rear] = item;
printf("\nItem enqueued: %d\n", item);
}
}
}

//Function for pop operation
int dequeue_cq()
{
int item = NULL;

if(front == -1 && rear == -1)
{
printf("\nQueue is empty. Dequeue not possible.\n");
}
else
{
item = queue[front];
queue[front] = NULL;

if(front == rear)
{
front = -1;
rear = -1;
}
else
{
front = ((front == (SIZE-1)) ? (front % (SIZE-1)) : ((front % (SIZE-1)) + 1));
}
}
return(item);
}```