SOLUTION SET

NEC-451: DATA STRUCTURE USING C LAB

ASSIGNMENT NO. –1

OBJECTIVE:- Programs based on Simple C logic, Pointers and Structure.

(1) Write a Program to display two integer number 10 and 20.

Program:

#include<stdio.h>

#include<conio.h>

void main(){

int number1 =10;

int number2 =20;

clrscr();

printf("number1 is:%d and number2 is:%d ",number1,number2);

getch();

(2) Write a Program to read 4 data values from user without using an array or function.

Program:

#include<stdio.h>

#include<conio.h>

void main(){

string name,branch;

int batch;

float per;

clrscr();

printf("Enter your Name:");

scanf("%s",&name);

printf("Your Batch:");
scanf("%d",&batch);

printf("Your Branch:");

scanf("%s",&branch);

printf("Enter Aggregate Percentage: :");

scanf("%f",&per);

printf("Name:%s " name);

printf(“Batch:%d " batch);

printf("Branch:%s " branch);

printf("Aggregate Percent:%f "per);

getch();

(3) Write a Program to print table of a number entered by user without using an array
or function.

Program:

#include <stdio.h>
#include <conio.h>
void main(){
int i=1,number=0;
clrscr();

printf("Enter a number: ");

scanf("%d",&number);

for(i=1;i<=10;i++){
printf("%d \n",(number*i));
}

getch();
}

(4) Write a Program to read 10 different data values one by one using a variable .If
entered value is odd then add it to addsum else add it to evensum and then display
addsum and evensum.

Program:

#include <stdio.h>
#include <conio.h>
void main(){
int a,evensum=0,oddsum=0;
clrscr();

int check(int a)
{
int b= a;
if(a%2==0)
return 0;
else
return 1;
}
for (i=1;i<=10;i++){

printf("Enter a number: ");

scanf("%d",&a);
if(check(a)==0){
evensum= evensum+a;
else
oddsum =oddsum+a;
}
printf(" Sum of odd numbers is=:%d \n",oddsum);
printf Sum of even numbers is=:%d \n",evensum);
getch();
}

(5) Write a Program to read 3 data values from user and add first two data values.
After that subtract result from the 3 rd data value. If the final result negative then
display message “ Result –ve” else display “Result +ve”.

Program:

#include <stdio.h>
#include <conio.h>
void main(){
int a,b,c;
clrscr();

printf("Enter first number: ");

scanf("%d",&a);

printf("Enter second number: ");

scanf("%d",&b);

printf("Enter third number: ");

scanf("%d",&c);

if ( check(a,b,c)==0)
{
printf(“The result is –ve”);
else
printf(“The result is +ve”);

int check(int a, int b, int c)

{
int p =a; int q= b, int r =c;
if((r-(p+q)<0)
{
return 0;
else
return 1;
}

for(i=1;i<=10;i++){
printf("%d \n",(number*i));
}

getch();
}

(6) Write a Program to implement Reference operator(&) and Dereference operator(*) for
pointer.

Program:

#include <stdio.h>
int main(){
int* pc;

int c;

c=22;

printf("Address of c:%u\n",&c);

printf("Value of c:%d\n\n",c);

pc=&c;

printf("Address of pointer pc:%u\n",pc);

printf("Content of pointer pc:%d\n\n",*pc);

c=11;

printf("Address of pointer pc:%u\n",pc);

printf("Content of pointer pc:%d\n\n",*pc);

*pc=2;

printf("Address of c:%u\n",&c);

printf("Value of c:%d\n\n",c);

return 0;

(7) Write a Program to using pointer by “call by value” and “call by reference” method

Program1:Call by value in C

#include <stdio.h>

#include <conio.h>

void change(int num) {

printf("Before adding value inside function num=%d \n",num);

num=num+100;

printf("After adding value inside function num=%d \n", num);

int main(){

int x=100;

clrscr();

printf("Before function call x=%d \n", x);

change(x);//passing value in function

printf("After function call x=%d \n", x);

getch();

return 0;

Program2:Call by reference in C

#include <stdio.h>

#include <conio.h>

void change(int *num) {

printf("Before adding value inside function num=%d \n",*num);

(*num) += 100;

printf("After adding value inside function num=%d \n", *num);

int main() {

int x=100;

clrscr();

printf("Before function call x=%d \n", x);

change(&x);//passing reference in function

printf("After function call x=%d \n", x);

getch();

return 0;

(8) Write a Program to Store Information(name, roll and marks) of a Student Using
Structure.

Program:

#include <stdio.h>

struct student

char name[50];

int roll;

float marks;

} s;

int main()

printf("Enter information:\n");

printf("Enter name: ");

scanf("%s", s.name);

printf("Enter roll number: ");

scanf("%d", &s.roll);

printf("Enter marks: ");

scanf("%f", &s.marks);

printf("Displaying Information:\n");

printf("Name: ");

puts(s.name);

printf("Roll number: %d\n",s.roll);

printf("Marks: %.1f\n", s.marks);

return 0;

ASSIGNMENT NO. –2

OBJECTIVE:- Programs based on Arrays.

(1).Write A Program to insert an element in array.

Solution:
#include <stdio.h>

void main()
{
int array[10];
int i, j, n, m, temp, key, pos;

printf("Enter how many elements \n");

scanf("%d", &n);
printf("Enter the elements \n");
for (i = 0; i < n; i++)
{
scanf("%d", &array[i]);
}
printf("Input array elements are \n");
for (i = 0; i < n; i++)
{
printf("%d\n", array[i]);
}
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
if (array[i] > array[j])
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
printf("Sorted list is \n");
for (i = 0; i < n; i++)
{
printf("%d\n", array[i]);
}
printf("Enter the element to be inserted \n");
scanf("%d", &key);
for (i = 0; i < n; i++)
{
if (key < array[i])
{
pos = i;
break;
}
if (key > array[n-1])
{
pos = n;
break;
}
}
if (pos != n)
{
m = n - pos + 1 ;
for (i = 0; i <= m; i++)
{
array[n - i + 2] = array[n - i + 1] ;
}
}
array[pos] = key;
printf("Final list is \n");
for (i = 0; i < n + 1; i++)
{
printf("%d\n", array[i]);
}
}

(2).Write A Program to delete an element from array.

Solution:
#include <stdio.h>

int main()
{
int array[100], position, c, n;

printf("Enter number of elements in array\n");

scanf("%d", &n);

printf("Enter %d elements\n", n);

for ( c = 0 ; c < n ; c++ )

scanf("%d", &array[c]);

printf("Enter the location where you wish to delete element\n");

scanf("%d", &position);

if ( position >= n+1 )

printf("Deletion not possible.\n");

else
{
for ( c = position - 1 ; c < n - 1 ; c++ )
array[c] = array[c+1];

printf("Resultant array is\n");

for( c = 0 ; c < n - 1 ; c++ )

printf("%d\n", array[c]);
}
return 0;
}

(3).Write A Program to find the average of 10 integers using array.

Solution:

#include <stdio.h>
int main()
{
int avg = 0;
int sum =0;
int x=0;

/* Array- declaration – length 20*/

int num[5];

/* for loop for receiving inputs from user and storing it in array*/
for (x=0; x<=5;x++)
{
printf("enter the integer number %d\n", x);
scanf("%d", &num[x]);
}
for (x=0; x<=19;x++)
{
sum = sum+num[x];
}

avg = sum/20;
printf("%d", avg);
return 0;
}

(4).Write A Program to find the sum and multiplication of 2-D array

Solution:

#include <stdio.h>

void enterData(int firstMatrix[][10], int secondMatrix[][10], int rowFirst, int columnFirst, int
rowSecond, int columnSecond);

void multiplyMatrices(int firstMatrix[][10], int secondMatrix[][10], int multResult[][10], int

rowFirst, int columnFirst, int rowSecond, int columnSecond);

void display(int mult[][10], int rowFirst, int columnSecond);

int main()
{
int firstMatrix[10][10], secondMatrix[10][10], mult[10][10], rowFirst, columnFirst,
rowSecond, columnSecond, i, j, k;

printf("Enter rows and column for first matrix: ");

scanf("%d %d", &rowFirst, &columnFirst);

printf("Enter rows and column for second matrix: ");

scanf("%d %d", &rowSecond, &columnSecond);

// If colum of first matrix in not equal to row of second matrix, asking user to enter the
size of matrix again.
while (columnFirst != rowSecond)
{
printf("Error! column of first matrix not equal to row of second.\n");
printf("Enter rows and column for first matrix: ");
scanf("%d%d", &rowFirst, &columnFirst);
printf("Enter rows and column for second matrix: ");
scanf("%d%d", &rowSecond, &columnSecond);
}

// Function to take matrices data

enterData(firstMatrix, secondMatrix, rowFirst, columnFirst, rowSecond,
columnSecond);
// Function to multiply two matrices.
multiplyMatrices(firstMatrix, secondMatrix, mult, rowFirst, columnFirst, rowSecond,
columnSecond);

// Function to display resultant matrix after multiplication.

display(mult, rowFirst, columnSecond);

return 0;
}

void enterData(int firstMatrix[][10], int secondMatrix[][10], int rowFirst, int columnFirst, int
rowSecond, int columnSecond)
{
int i, j;
printf("\nEnter elements of matrix 1:\n");
for(i = 0; i < rowFirst; ++i)
{
for(j = 0; j < columnFirst; ++j)
{
printf("Enter elements a%d%d: ", i + 1, j + 1);
scanf("%d", &firstMatrix[i][j]);
}
}

printf("\nEnter elements of matrix 2:\n");

for(i = 0; i < rowSecond; ++i)
{
for(j = 0; j < columnSecond; ++j)
{
printf("Enter elements b%d%d: ", i + 1, j + 1);
scanf("%d", &secondMatrix[i][j]);
}
}
}

void multiplyMatrices(int firstMatrix[][10], int secondMatrix[][10], int mult[][10], int

rowFirst, int columnFirst, int rowSecond, int columnSecond)
{
int i, j, k;

// Initializing elements of matrix mult to 0.

for(i = 0; i < rowFirst; ++i)
{
for(j = 0; j < columnSecond; ++j)
{
mult[i][j] = 0;
}
}

// Multiplying matrix firstMatrix and secondMatrix and storing in array mult.

for(i = 0; i < rowFirst; ++i)
{
for(j = 0; j < columnSecond; ++j)
{
for(k=0; k<columnFirst; ++k)
{
mult[i][j] += firstMatrix[i][k] * secondMatrix[k][j];
}
}
}
}

void display(int mult[][10], int rowFirst, int columnSecond)

{
int i, j;
printf("\nOutput Matrix:\n");
for(i = 0; i < rowFirst; ++i)
{
for(j = 0; j < columnSecond; ++j)
{
printf("%d ", mult[i][j]);
if(j == columnSecond - 1)
printf("\n\n");
}
}
}

(5).Write A Program to find the diagonal elements of the 2-D array, also find the sum of
diagonal elements.
Solution:
#include<stdio.h>

void main()
{
int a[20][20],b[20][20],c[20][20],i,j,m,n;
printf("enter the rows and columns of the matrixs\n");
scanf("%d%d",&m,&n);
printf("Enter the first matrics\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]); //reads the matrics
}
}
printf("The diagonal element of the matrics are\n");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(i==j)
printf("%d ,",a[i][j]); //prints the diagonal element of the matrics
}

}
}

(6).Write A Program to find the transpose of 2-D array.

Solution:

#include <stdio.h>

int main()
{
int a[10][10], transpose[10][10], r, c, i, j;
printf("Enter rows and columns of matrix: ");
scanf("%d %d", &r, &c);

// Storing elements of the matrix

printf("\nEnter elements of matrix:\n");
for(i=0; i<r; ++i)
for(j=0; j<c; ++j)
{
printf("Enter element a%d%d: ",i+1, j+1);
scanf("%d", &a[i][j]);
}

// Displaying the matrix a[][] */

printf("\nEntered Matrix: \n");
for(i=0; i<r; ++i)
for(j=0; j<c; ++j)
{
printf("%d ", a[i][j]);
if (j == c-1)
printf("\n\n");
}

// Finding the transpose of matrix a

for(i=0; i<r; ++i)
for(j=0; j<c; ++j)
{
transpose[j][i] = a[i][j];
}

// Displaying the transpose of matrix a

printf("\nTranspose of Matrix:\n");
for(i=0; i<c; ++i)
for(j=0; j<r; ++j)
{
printf("%d ",transpose[i][j]);
if(j==r-1)
printf("\n\n");
}

return 0;
}

(7).Write A Program to merge two array.

Solution:

#include <stdio.h>

void main()
{
int array1[50], array2[50], array3[100], m, n, i, j, k = 0;

printf("\n Enter size of array Array 1: ");

scanf("%d", &m);
printf("\n Enter sorted elements of array 1: \n");
for (i = 0; i < m; i++)
{
scanf("%d", &array1[i]);
}
printf("\n Enter size of array 2: ");
scanf("%d", &n);
printf("\n Enter sorted elements of array 2: \n");
for (i = 0; i < n; i++)
{
scanf("%d", &array2[i]);
}
i = 0;
j = 0;
while (i < m && j < n)
{
if (array1[i] < array2[j])
{
array3[k] = array1[i];
i++;
}
else
{
array3[k] = array2[j];
j++;
}
k++;
}
if (i >= m)
{
while (j < n)
{
array3[k] = array2[j];
j++;
k++;
}
}
if (j >= n)
{
while (i < m)
{
array3[k] = array1[i];
i++;
k++;
}
}
printf("\n After merging: \n");
for (i = 0; i < m + n; i++)
{
printf("\n%d", array3[i]);
}
}

(8).Write A Program to enter college name using array.

Solution:

#include <stdio.h>

main ()
{
char name[39+1];
printf("Enter your college name name :");
scanf("%s", name);
printf("Hello %s", name);
}

ASSIGNMENT NO. –3

OBJECTIVE :- Programs Based on Linear Linked List.

(1) Write a function to create and display the linear linked list.

Program:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
};

struct node *head = NULL;

struct node *current = NULL;

//display the list

void printList() {
struct node *ptr = head;
printf"\n[ ");

//start from the beginning

while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}

printf(" ]");
}

//insert link at the first location

void insertFirst(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));

link->key = key;
link->data = data;

//point it to old first node

link->next = head;

//point first to new first node

head = link;
}

//delete first item

struct node* deleteFirst() {

//save reference to first link

struct node *tempLink = head;

//mark next to first link as first

head = head->next;

//return the deleted link

return tempLink;
}
//is list empty
bool isEmpty() {
return head == NULL;
}

int length() {
int length = 0;
struct node *current;

for(current = head; current != NULL; current = current->next) {

length++;
}

return length;
}

//find a link with given key

struct node* find(int key) {

//start from the first link

struct node* current = head;

//if list is empty

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

//navigate through list

while(current->key != key) {

//if it is last node

if(current->next == NULL) {
return NULL;
} else {
//go to next link
current = current->next;
}
}

//if data found, return the current Link

return current;
}

//delete a link with given key

struct node* delete(int key) {

//start from the first link

struct node* current = head;
struct node* previous = NULL;

//if list is empty

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

//navigate through list

while(current->key != key) {

//if it is last node

if(current->next == NULL) {
return NULL;
} else {
//store reference to current link
previous = current;
//move to next link
current = current->next;
}
}

//found a match, update the link

if(current == head) {
//change first to point to next link
head = head->next;
} else {
//bypass the current link
previous->next = current->next;
}

return current;
}

void sort() {

int i, j, k, tempKey, tempData;

struct node *current;
struct node *next;

int size = length();

k = size ;

for ( i = 0 ; i < size - 1 ; i++, k-- ) {

current = head;
next = head->next;

for ( j = 1 ; j < k ; j++ ) {

if ( current->data > next->data ) {

tempData = current->data;
current->data = next->data;
next->data = tempData;

tempKey = current->key;
current->key = next->key;
next->key = tempKey;
}

current = current->next;
next = next->next;
}
}
}

void reverse(struct node** head_ref) {

struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;

while (current != NULL) {

next = current->next;
current->next = prev;
prev = current;
current = next;
}

*head_ref = prev;
}

main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);

printf("Original List: ");

//print list
printList();

while(!isEmpty()) {
struct node *temp = deleteFirst();
printf("\nDeleted value:");
printf("(%d,%d) ",temp->key,temp->data);
}

printf("\nList after deleting all items: ");

printList();
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);

printf("\nRestored List: ");

printList();
printf("\n");

struct node *foundLink = find(4);

if(foundLink != NULL) {
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
} else {
printf("Element not found.");
}

delete(4);
printf("List after deleting an item: ");
printList();
printf("\n");
foundLink = find(4);

if(foundLink != NULL) {
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
} else {
printf("Element not found.");
}

printf("\n");
sort();

printf("List after sorting the data: ");

printList();

reverse(&head);
printf("\nList after reversing the data: ");
printList();
}

(2) Write functions to implement the insertion and deletion operation of linear linked
list .

Program:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

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

struct node *head = NULL;

struct node *current = NULL;

//display the list

void printList() {
struct node *ptr = head;
printf"\n[ ");

//start from the beginning

while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}

printf(" ]");
}

//insert link at the first location

void insertFirst(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));

link->key = key;
link->data = data;

//point it to old first node

link->next = head;

//point first to new first node

head = link;
}

//delete first item

struct node* deleteFirst() {

//save reference to first link

struct node *tempLink = head;

//mark next to first link as first

head = head->next;
//return the deleted link
return tempLink;
}

//is list empty

bool isEmpty() {
return head == NULL;
}

int length() {
int length = 0;
struct node *current;

for(current = head; current != NULL; current = current->next) {

length++;
}

return length;
}

//find a link with given key

struct node* find(int key) {

//start from the first link

struct node* current = head;

//if list is empty

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

//navigate through list

while(current->key != key) {

//if it is last node

if(current->next == NULL) {
return NULL;
} else {
//go to next link
current = current->next;
}
}

//if data found, return the current Link

return current;
}

//delete a link with given key

struct node* delete(int key) {
//start from the first link
struct node* current = head;
struct node* previous = NULL;

//if list is empty

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

//navigate through list

while(current->key != key) {

//if it is last node

if(current->next == NULL) {
return NULL;
} else {
//store reference to current link
previous = current;
//move to next link
current = current->next;
}
}

//found a match, update the link

if(current == head) {
//change first to point to next link
head = head->next;
} else {
//bypass the current link
previous->next = current->next;
}

return current;
}

void sort() {

int i, j, k, tempKey, tempData;

struct node *current;
struct node *next;

int size = length();

k = size ;

for ( i = 0 ; i < size - 1 ; i++, k-- ) {

current = head;
next = head->next;

for ( j = 1 ; j < k ; j++ ) {

if ( current->data > next->data ) {

tempData = current->data;
current->data = next->data;
next->data = tempData;

tempKey = current->key;
current->key = next->key;
next->key = tempKey;
}

current = current->next;
next = next->next;
}
}
}

void reverse(struct node** head_ref) {

struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;

while (current != NULL) {

next = current->next;
current->next = prev;
prev = current;
current = next;
}

*head_ref = prev;
}

main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);

printf("Original List: ");

//print list
printList();

while(!isEmpty()) {
struct node *temp = deleteFirst();
printf("\nDeleted value:");
printf("(%d,%d) ",temp->key,temp->data);
}

printf("\nList after deleting all items: ");

printList();
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);

printf("\nRestored List: ");

printList();
printf("\n");

struct node *foundLink = find(4);

if(foundLink != NULL) {
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
} else {
printf("Element not found.");
}

delete(4);
printf("List after deleting an item: ");
printList();
printf("\n");
foundLink = find(4);

if(foundLink != NULL) {
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
} else {
printf("Element not found.");
}

printf("\n");
sort();

printf("List after sorting the data: ");

printList();

reverse(&head);
printf("\nList after reversing the data: ");
printList();
}

(3) Write function to implement the concatenation operation of linear linked list.

Program:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

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

struct node *head = NULL;

struct node *current = NULL;

//display the list

void printList() {
struct node *ptr = head;
printf"\n[ ");

//start from the beginning

while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}

printf(" ]");
}

//insert link at the first location

void insertFirst(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));

link->key = key;
link->data = data;

//point it to old first node

link->next = head;

//point first to new first node

head = link;
}

//delete first item

struct node* deleteFirst() {

//save reference to first link

struct node *tempLink = head;

//mark next to first link as first

head = head->next;
//return the deleted link
return tempLink;
}

//is list empty

bool isEmpty() {
return head == NULL;
}

int length() {
int length = 0;
struct node *current;

for(current = head; current != NULL; current = current->next) {

length++;
}

return length;
}

//find a link with given key

struct node* find(int key) {

//start from the first link

struct node* current = head;

//if list is empty

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

//navigate through list

while(current->key != key) {

//if it is last node

if(current->next == NULL) {
return NULL;
} else {
//go to next link
current = current->next;
}
}

//if data found, return the current Link

return current;
}

//delete a link with given key

struct node* delete(int key) {
//start from the first link
struct node* current = head;
struct node* previous = NULL;

//if list is empty

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

//navigate through list

while(current->key != key) {

//if it is last node

if(current->next == NULL) {
return NULL;
} else {
//store reference to current link
previous = current;
//move to next link
current = current->next;
}
}

//found a match, update the link

if(current == head) {
//change first to point to next link
head = head->next;
} else {
//bypass the current link
previous->next = current->next;
}

return current;
}

void sort() {

int i, j, k, tempKey, tempData;

struct node *current;
struct node *next;

int size = length();

k = size ;

for ( i = 0 ; i < size - 1 ; i++, k-- ) {

current = head;
next = head->next;

for ( j = 1 ; j < k ; j++ ) {

if ( current->data > next->data ) {

tempData = current->data;
current->data = next->data;
next->data = tempData;

tempKey = current->key;
current->key = next->key;
next->key = tempKey;
}

current = current->next;
next = next->next;
}
}
}

void reverse(struct node** head_ref) {

struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;

while (current != NULL) {

next = current->next;
current->next = prev;
prev = current;
current = next;
}

*head_ref = prev;
}

void main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);

printf("Original List: ");

//print list
printList();

while(!isEmpty()) {
struct node *temp = deleteFirst();
printf("\nDeleted value:");
printf("(%d,%d) ",temp->key,temp->data);
}

printf("\nList after deleting all items: ");

printList();
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);

printf("\nRestored List: ");

printList();
printf("\n");

struct node *foundLink = find(4);

if(foundLink != NULL) {
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
} else {
printf("Element not found.");
}

delete(4);
printf("List after deleting an item: ");
printList();
printf("\n");
foundLink = find(4);

if(foundLink != NULL) {
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
} else {
printf("Element not found.");
}

printf("\n");
sort();

printf("List after sorting the data: ");

printList();

reverse(&head);
printf("\nList after reversing the data: ");
printList();
}

(4) Write function to implement the polynomial addition with the help of linear linked
list.

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

struct pNode {
int coeff, exp;
struct pNode *next;
};

struct pNode *head1, *head2, *head3;

/*
* creates new Node and fill the given data
*/
struct pNode * createNode(int coeff, int exp) {
struct pNode *ptr;
ptr = (struct pNode *) malloc(sizeof (struct pNode));
ptr->coeff = coeff;
ptr->exp = exp;
ptr->next = NULL;
return ptr;
}

/* insert data in decending order */

void polyInsert(struct pNode ** myNode, int coeff, int exp) {
struct pNode *xPtr, *yPtr, *zPtr = *myNode;
xPtr = createNode(coeff, exp);
/* if exp > exp in header then the new node is the header */
if (*myNode == NULL || (*myNode)->exp < exp) {
*myNode = xPtr;
(*myNode)->next = zPtr;
return;
}

/* placing new node in correct position - decending order */

while (zPtr) {
yPtr = zPtr;
zPtr = zPtr->next;
if (!zPtr) {
yPtr->next = xPtr;
break;
} else if ((exp < yPtr->exp) && (exp > zPtr->exp)) {
xPtr->next = zPtr;
yPtr->next = xPtr;
break;
}
}
return;
}

/* Adding poly nomial n2 and n3 and the output will be stroed in n1 list */
void polynomial_add(struct pNode **n1, struct pNode *n2, struct pNode *n3) {
struct pNode * temp;

/* if both list not exit, then output list *n1 is NULL */

if (!n2 && !n3)
return;

/* both list are present */

while (n2 && n3) {
if (*n1 == NULL) {
*n1 = (struct pNode *) malloc(sizeof (struct pNode));
temp = *n1;
} else {
temp->next = (struct pNode *)malloc(sizeof (struct pNode));
temp = temp->next;
}

/* polynomial addition operation */

if (n2->exp < n3->exp) {
temp->coeff = n3->coeff;
temp->exp = n3->exp;
n3 = n3->next;
} else if (n2->exp > n3->exp) {
temp->coeff = n2->coeff;
temp->exp = n2->exp;
n2 = n2->next;
} else {
temp->coeff = n2->coeff + n3->coeff;
temp->exp = n2->exp;
n2 = n2->next;
n3 = n3->next;
}
}

/*
* if some nodes in input list (n2) left remain, then add those
* nodes to the output list (n3).
*/
while (n2) {
if (*n1 == NULL) {
*n1 = (struct pNode *) malloc(sizeof (struct pNode));
temp = *n1;
} else {
temp->next = (struct pNode *) malloc(sizeof (struct pNode));
temp = temp->next;
}
temp->coeff = n2->coeff;
temp->exp = n2->exp;
n2 = n2->next;
}
/*
* if some nodes in the input list (n3) left remain, then add those
* nodes to the output list n3.
*/
while (n3) {
if (*n1 == NULL) {
*n1 = (struct pNode *) malloc(sizeof (struct pNode));
temp = *n1;
} else {
temp->next = (struct pNode *) malloc(sizeof (struct pNode));
temp = temp->next;
}
temp->coeff = n2->coeff;
temp->exp = n2->exp;
n3 = n3->next;
}
return;
}

/* delete the given input list */

struct pNode * deletePolyList(struct pNode *ptr) {
struct pNode *temp;
while (ptr){
temp = ptr->next;
free(ptr);
ptr = temp;
}
return NULL;
}

/* traverse the given input list and print the data in each node */
void walkPolyList(struct pNode *ptr) {
int i = 0;
while (ptr) {
printf("%dX^%d %c ", ptr->coeff, ptr->exp, ptr->next?'+':'\0');
ptr = ptr->next;
i++;
}
printf("\n");
return;
}

int main (int argc, char *argv[]) {

int coeff, exp, i, n;
FILE *fp1, *fp2;
fp1 = fopen(argv[1], "r");
fp2 = fopen(argv[2], "r");
if (!fp1 || !fp2) {
printf("Unable to open file\n");
fcloseall();
exit(0);
}

/* reading co-efficient and exponent from the file argv[1] */

while (fscanf(fp1, "%d%d", &coeff, &exp) != EOF) {
polyInsert(&head1, coeff, exp);
}

/* reading co-efficient and exponent from the input file argv[2] */

while (fscanf(fp2, "%d%d", &coeff, &exp) != EOF) {
polyInsert(&head2, coeff, exp);
}

walkPolyList(head1);
walkPolyList(head2);
polynomial_add(&head3, head1, head2);
walkPolyList(head3);
head1 = deletePolyList(head1);
head2 = deletePolyList(head2);
head3 = deletePolyList(head3);
return 0;
}

(5) Write function to insert a data value after given data value in linear/single linked
list.

Program:

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

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

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

struct node *header, *ptr, *temp;

//Prototypes for various user defined functions.

void insert_front();
void insert_end();
void insert_any();
void display();

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

//Allocate memory for header node.

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

clrscr();

//Set the content of header node

header->data = NULL;
header->link = NULL;

while(cont == 1)
{
//Display menu to the user
printf("\n1. Insert at front\n");
printf("\n2. Insert at end\n");
printf("\n3. Insert at any position\n");
printf("\n4. Display linked list\n");
printf("\nEnter your choice: ");
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;
temp->link = header->link;
header->link = temp;
}

//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.

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

temp->data = data_value;
temp->link = ptr->link;
ptr->link = temp;
}

//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.

ptr = header;
while(ptr->link != NULL && ptr->data != key)
{
ptr = ptr->link;
}
if(ptr->data == key)
{
temp->data = data_value;
temp->link = ptr->link;
ptr->link = temp;
}
else
{
printf("\nValue %d not found\n",key);
}
}

//Function to display the contents of the linked list.

void display()
{
printf("\nContents of the linked list are: \n");
//Print the contents of the linked list starting from header
ptr = header;
while(ptr->link != NULL)
{
ptr = ptr->link;
printf("%d ", ptr->data);
}
}

(6) Write function to insert a data value after given no. of node in linear/single linked
list.

Program:

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

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

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

struct node *header, *ptr, *temp;

//Prototypes for various user defined functions.

void insert_front();
void insert_end();
void insert_any();
void display();
void main()
{
int choice;
int cont = 1;

//Allocate memory for header node.

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

clrscr();

//Set the content of header node

header->data = NULL;
header->link = NULL;

while(cont == 1)
{
//Display menu to the user
printf("\n1. Insert at front\n");
printf("\n2. Insert at end\n");
printf("\n3. Insert at any position\n");
printf("\n4. Display linked list\n");
printf("\nEnter your choice: ");
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;
temp->link = header->link;
header->link = temp;
}

//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.

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

temp->data = data_value;
temp->link = ptr->link;
ptr->link = temp;
}

//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.

ptr = header;
while(ptr->link != NULL && ptr->data != key)
{
ptr = ptr->link;
}
if(ptr->data == key)
{
temp->data = data_value;
temp->link = ptr->link;
ptr->link = temp;
}
else
{
printf("\nValue %d not found\n",key);
}
}

//Function to display the contents of the linked list.

void display()
{
printf("\nContents of the linked list are: \n");
//Print the contents of the linked list starting from header
ptr = header;
while(ptr->link != NULL)
{
ptr = ptr->link;
printf("%d ", ptr->data);
}
}

ASSIGNMENT NO. –4

OBJECTIVE :- Programs Based on Circular Linked List.

(1) Write a program to create and display the Circular linked list.

Program:

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

struct circular
{
int i;
struct circular *next;
};

struct circular *temp;

struct circular *head;
struct circular *p;
struct circular *mid;
struct circular *move;

int cnt=0;
void create(void);
void insert(void);
void display(void);
void del(void);

void main()
{
int ch=0;
clrscr();
while(ch!=5)
{
printf("\n1.CREATE");
printf("\n2.INSERT");
printf("\n3.DELETE");
printf("\n4.DISPLAY");
printf("\n5.EXIT");
scanf("%d",&ch);

if(ch==1)
{
create();
cnt++;
cnt++;
}
if(ch==2)
{
insert();
cnt++;
}
if(ch==3)
{
del();
cnt--;
}

if(ch==4)
{
display();
}
if(ch==5)
{
break;
}
}
getch();
}
void create()
{
head=(struct circular *)malloc(sizeof(struct circular));
head->next=head;
printf("ENETER THE DATA");
scanf("%d",&head->i);
temp=head;

temp->next=(struct circular *)malloc(sizeof(struct circular));

temp=temp->next;
temp->next=head;
printf("ENETER THE DATA");
scanf("%d",&temp->i);

}
void insert()
{
int add,t;

printf("\n\t ENTER ANY NUMBER BETWEEN 1 AND %d",cnt);

scanf("%d",&add);
p=head;
t=1;
while(t<add)
{
p=p->next;
t++;
}
printf("%d",p->i);
clrscr();
mid=(struct circular *)malloc(sizeof(struct circular));
printf("ENETER THE DATA");
scanf("%d",&mid->i);
mid->next=p->next;
p->next=mid;
}

void display()
{
p=head;
printf("%d-->",p->i);
p=p->next;
while(p!=head)
{
printf("%d-->",p->i);
p=p->next;
}
}

void del(void)
{
int add,t;

printf("\n\t ENTER ANY NUMBER BETWEEN 1 AND %d",cnt);

scanf("%d",&add);
p=head;
t=1;
while(t<add-1)
{
p=p->next;
t++;
}
printf("%d",p->i);
clrscr();
mid=p->next;
p->next=mid->next;

(2) Write a program to implement delete and display operation of Circular linked list.

Program:

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

struct circular
{
int i;
struct circular *next;
};

struct circular *temp;

struct circular *head;
struct circular *p;
struct circular *mid;
struct circular *move;
int cnt=0;

void create(void);
void insert(void);
void display(void);
void del(void);
void main()
{
int ch=0;
clrscr();
while(ch!=5)
{
printf("\n1.CREATE");
printf("\n2.INSERT");
printf("\n3.DELETE");
printf("\n4.DISPLAY");
printf("\n5.EXIT");
scanf("%d",&ch);

if(ch==1)
{
create();
cnt++;
cnt++;
}

if(ch==2)
{
insert();
cnt++;
}
if(ch==3)
{
del();
cnt--;
}

if(ch==4)
{
display();
}

if(ch==5)
{
break;
}
}
getch();
}
void create()
{
head=(struct circular *)malloc(sizeof(struct circular));
head->next=head;
printf("ENETER THE DATA");
scanf("%d",&head->i);
temp=head;

temp->next=(struct circular *)malloc(sizeof(struct circular));

temp=temp->next;
temp->next=head;
printf("ENETER THE DATA");
scanf("%d",&temp->i);

}
void insert()
{
int add,t;

printf("\n\t ENTER ANY NUMBER BETWEEN 1 AND %d",cnt);

scanf("%d",&add);
p=head;
t=1;
while(t<add)
{
p=p->next;
t++;
}
printf("%d",p->i);
clrscr();
mid=(struct circular *)malloc(sizeof(struct circular));
printf("ENETER THE DATA");
scanf("%d",&mid->i);
mid->next=p->next;
p->next=mid;
}

void display()
{
p=head;
printf("%d-->",p->i);
p=p->next;
while(p!=head)
{
printf("%d-->",p->i);
p=p->next;
}
}

void del(void)
{
int add,t;

printf("\n\t ENTER ANY NUMBER BETWEEN 1 AND %d",cnt);

scanf("%d",&add);
p=head;
t=1;
while(t<add-1)
{
p=p->next;
t++;
}
printf("%d",p->i);
clrscr();
mid=p->next;
p->next=mid->next;

(3) Write a program to display all the data values starting from 3rd node in the circular
linked list.

Program:

void display()
{
struct circular *q;
p=head;
p=p->next;
p=p->next;
q=p;
printf("%d-->",p->i);
while(p!=q)
{
printf("%d-->",p->i);
p=p->next;
}
}

(4) Write a program to delete first node of the circular linked list.

Program:

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

struct circular
{
int i;
struct circular *next;
};

struct circular *temp;

struct circular *head;
struct circular *p;
struct circular *mid;
struct circular *move;
int cnt=0;
void create(void);
void insert(void);
void display(void);
void del(void);

void main()
{
int ch=0;
clrscr();
while(ch!=5)
{
printf("\n1.CREATE");
printf("\n2.INSERT");
printf("\n3.DELETE");
printf("\n4.DISPLAY");
printf("\n5.EXIT");
scanf("%d",&ch);

if(ch==1)
{
create();
cnt++;
cnt++;
}

if(ch==2)
{
insert();
cnt++;
}
if(ch==3)
{
del();
cnt--;
}

if(ch==4)
{
display();
}

if(ch==5)
{
break;
}
}
getch();
}
void create()
{
head=(struct circular *)malloc(sizeof(struct circular));
head->next=head;
printf("ENETER THE DATA");
scanf("%d",&head->i);
temp=head;

temp->next=(struct circular *)malloc(sizeof(struct circular));

temp=temp->next;
temp->next=head;
printf("ENETER THE DATA");
scanf("%d",&temp->i);

}
void insert()
{
int add,t;

printf("\n\t ENTER ANY NUMBER BETWEEN 1 AND %d",cnt);

scanf("%d",&add);
p=head;
t=1;
while(t<add)
{
p=p->next;
t++;
}
printf("%d",p->i);
clrscr();
mid=(struct circular *)malloc(sizeof(struct circular));
printf("ENETER THE DATA");
scanf("%d",&mid->i);
mid->next=p->next;
p->next=mid;
}

void display()
{
p=head;
printf("%d-->",p->i);
p=p->next;
while(p!=head)
{
printf("%d-->",p->i);
p=p->next;
}
}

void del(void)
{
int add,t;

printf("\n\t ENTER ANY NUMBER BETWEEN 1 AND %d",cnt);

scanf("%d",&add);
p=head;
t=1;
while(t<add-1)
{
p=p->next;
t++;
}
printf("%d",p->i);
clrscr();
mid=p->next;
p->next=mid->next;

ASSIGNMENT NO. –5

OBJECTIVE :- Programs Based on Doubly and Circular Doubly Linked List.

(1) Write functions to create and display the double linked list.

Program:

#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node * prev;
struct node * next;
}*head, *last;
void createList(int n);
void displayListFromFirst();
void displayListFromEnd();

int main()
{
int n, choice;

head = NULL;
last = NULL;
printf("Enter the number of nodes you want to create: ");
scanf("%d", &n);
createList(n); //Creates list of n nodes
printf("\nPress 1 to display list from First");
printf("\nPress 2 to display list from End : ");
scanf("%d", &choice);
if(choice==1)
{
displayListFromFirst();
}
else if(choice == 2)
{
displayListFromEnd();
}

return 0;
}
void createList(int n)
{
int i, data;
struct node *newNode;

if(n >= 1)
{
head = (struct node *)malloc(sizeof(struct node));

if(head != NULL)
{
printf("Enter data of 1 node: ");
scanf("%d", &data);

head->data = data;
head->prev = NULL;
head->next = NULL;

last = head;

for(i=2; i<=n; i++)

{
newNode = (struct node *)malloc(sizeof(struct node));

if(newNode != NULL)
{
printf("Enter data of %d node: ", i);
scanf("%d", &data);

newNode->data = data;
newNode->prev = last; //Links new node with the previous node
newNode->next = NULL;

last->next = newNode; //Links previous node with the new node

last = newNode; //Makes new node as last/previous node
}
else
{
printf("Unable to allocate memory.");
break;
}
}

printf("\nDOUBLY LINKED LIST CREATED SUCCESSFULLY\n");

}
else
{
printf("Unable to allocate memory");
}
}
}

void displayListFromFirst()
{
struct node * temp;
int n = 1;

if(head == NULL)
{
printf("List is empty.");
}
else
{
temp = head;
printf("\n\nDATA IN THE LIST:\n");

while(temp != NULL)
{
printf("DATA of %d node = %d\n", n, temp->data);

n++;

/* Moves the current pointer to next node */

temp = temp->next;
}
}
}

void displayListFromEnd()
{
struct node * temp;
int n = 0;

if(last == NULL)
{
printf("List is empty.");
}
else
{
temp = last;
printf("\n\nDATA IN THE LIST:\n");

while(temp != NULL)
{
printf("DATA of last-%d node = %d\n", n, temp->data);

n++;

/* Moves the current pointer to previous node */

temp = temp->prev;
}
}
}

(2) Write functions to implement the insertion and deletion operation of double linked
list.

Program:

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

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

//this link always point to first Link

struct node *head = NULL;

//this link always point to last Link

struct node *last = NULL;

struct node *current = NULL;

//is list empty

bool isEmpty() {
return head == NULL;
}

int length() {
int length = 0;
struct node *current;

for(current = head; current != NULL; current = current->next){

length++;
}

return length;
}

//display the list in from first to last

void displayForward() {

//start from the beginning

struct node *ptr = head;

//navigate till the end of the list

printf("\n[ ");

while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}

printf(" ]");
}

//display the list from last to first

void displayBackward() {

//start from the last

struct node *ptr = last;

//navigate till the start of the list

printf("\n[ ");

while(ptr != NULL) {

//print data
printf("(%d,%d) ",ptr->key,ptr->data);

//move to next item

ptr = ptr ->prev;
printf(" ");
}

printf(" ]");
}

//insert link at the first location

void insertFirst(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;

if(isEmpty()) {
//make it the last link
last = link;
} else {
//update first prev link
head->prev = link;
}

//point it to old first link

link->next = head;

//point first to new first link

head = link;
}

//insert link at the last location

void insertLast(int key, int data) {

//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;

if(isEmpty()) {
//make it the last link
last = link;
} else {
//make link a new last link
last->next = link;

//mark old last node as prev of new link

link->prev = last;
}

//point last to new last node

last = link;
}

//delete first item

struct node* deleteFirst() {

//save reference to first link

struct node *tempLink = head;

//if only one link

if(head->next == NULL){
last = NULL;
} else {
head->next->prev = NULL;
}

head = head->next;
//return the deleted link
return tempLink;
}

//delete link at the last location

struct node* deleteLast() {

//save reference to last link
struct node *tempLink = last;

//if only one link

if(head->next == NULL) {
head = NULL;
} else {
last->prev->next = NULL;
}

last = last->prev;

//return the deleted link

return tempLink;
}

//delete a link with given key

struct node* delete(int key) {

//start from the first link

struct node* current = head;
struct node* previous = NULL;

//if list is empty

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

//navigate through list

while(current->key != key) {
//if it is last node

if(current->next == NULL) {
return NULL;
} else {
//store reference to current link
previous = current;

//move to next link

current = current->next;
}
}

//found a match, update the link

if(current == head) {
//change first to point to next link
head = head->next;
} else {
//bypass the current link
current->prev->next = current->next;
}

if(current == last) {
//change last to point to prev link
last = current->prev;
} else {
current->next->prev = current->prev;
}

return current;
}

bool insertAfter(int key, int newKey, int data) {

//start from the first link
struct node *current = head;

//if list is empty

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

//navigate through list

while(current->key != key) {

//if it is last node

if(current->next == NULL) {
return false;
} else {
//move to next link
current = current->next;
}
}

//create a link
struct node *newLink = (struct node*) malloc(sizeof(struct node));
newLink->key = key;
newLink->data = data;
if(current == last) {
newLink->next = NULL;
last = newLink;
} else {
newLink->next = current->next;
current->next->prev = newLink;
}

newLink->prev = current;
current->next = newLink;
return true;
}

main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);

printf("\nList (First to Last): ");

displayForward();

printf("\n");
printf("\nList (Last to first): ");
displayBackward();

printf("\nList , after deleting first record: ");

deleteFirst();
displayForward();

printf("\nList , after deleting last record: ");

deleteLast();
displayForward();

printf("\nList , insert after key(4) : ");

insertAfter(4,7, 13);
displayForward();

printf("\nList , after delete key(4) : ");

delete(4);
displayForward();
}

(3) Write function to display data values in reverse order using double linked list.

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

struct node {
int data;
struct node * prev;
struct node * next;
}*head, *last;

void createList(int n);

void displayList();
void reverseList();

int main()
{
int n, data, choice=1;

head = NULL;
last = NULL;

while(choice != 0)
{
printf("============================================\n");
printf("DOUBLY LINKED LIST PROGRAM\n");
printf("============================================\n");
printf("1. Create List\n");
printf("2. Reverse List\n");
printf("3. Display list\n");
printf("0. Exit\n");
printf("--------------------------------------------\n");
printf("Enter your choice : ");

scanf("%d", &choice);

switch(choice)
{
case 1:
printf("Enter the total number of nodes in list: ");
scanf("%d", &n);
createList(n);
break;
case 2:
reverseList();
break;
case 3:
displayList();
break;
case 0:
break;
default:
printf("Error! Invalid choice. Please choose between 0-3");
}

printf("\n\n\n\n\n");
}

return 0;
}

void createList(int n)
{
int i, data;
struct node *newNode;

if(n >= 1)
{
head = (struct node *)malloc(sizeof(struct node));

printf("Enter data of 1 node: ");

scanf("%d", &data);

head->data = data;
head->prev = NULL;
head->next = NULL;

last = head;

for(i=2; i<=n; i++)

{
newNode = (struct node *)malloc(sizeof(struct node));

printf("Enter data of %d node: ", i);

scanf("%d", &data);

newNode->data = data;
newNode->prev = last; //Links new node with the previous node
newNode->next = NULL;

last->next = newNode; //Links previous node with the new node

last = newNode; //Makes new node as last/previous node
}

printf("\nDOUBLY LINKED LIST CREATED SUCCESSFULLY\n");

}
}

/* Displays the content of the list from beginning to end */

void displayList()
{
struct node * temp;
int n = 1;

if(head == NULL)
{
printf("List is empty.\n");
}
else
{
temp = head;
printf("DATA IN THE LIST:\n");

while(temp != NULL)
{
printf("DATA of %d node = %d\n", n, temp->data);

n++;

/* Moves the current pointer to next node */

temp = temp->next;
}
}
}

/**
* Reverses the order of the doubly linked list
*/
void reverseList()
{
struct node *current, *temp;

current = head;
while(current != NULL)
{
/*
* Swap the previous and next address fields of current node
*/
temp = current->next;
current->next = current->prev;
current->prev = temp;

/* Move the current pointer to next node which is stored in temp */

current = temp;
}

/*
* Swap the head and last pointers
*/
temp = head;
head = last;
last = temp;

printf("LIST REVERSED SUCCESSFULLY.\n");

}

(4) Write function to insert a data value after given data value in double linked list.

Program:

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

/*
* Basic structure of Node
*/
struct node {
int data;
struct node * prev;
struct node * next;
}*head, *last;

/*
* Functions used in this program
*/
void createList(int n);
void displayList();
void insertAtBeginning(int data);
void insertAtEnd(int data);
void insertAtN(int data, int position);

int main()
{
int n, data, choice=1;

head = NULL;
last = NULL;

/*
* Runs forever until user chooses 0
*/
while(choice != 0)
{
/*
* Menu creation to use the program
*/
printf("============================================\n");
printf("DOUBLY LINKED LIST PROGRAM\n");
printf("============================================\n");
printf("1. Create List\n");
printf("2. Insert node - at beginning\n");
printf("3. Insert node - at end\n");
printf("4. Insert node - at N\n");
printf("5. Display list\n");
printf("0. Exit\n");
printf("--------------------------------------------\n");
printf("Enter your choice : ");

scanf("%d", &choice);
/*
* Chooses from different menu operation
*/
switch(choice)
{
case 1:
printf("Enter the total number of nodes in list: ");
scanf("%d", &n);

createList(n);
break;
case 2:
printf("Enter data of first node : ");
scanf("%d", &data);

insertAtBeginning(data);
break;
case 3:
printf("Enter data of last node : ");
scanf("%d", &data);

insertAtEnd(data);
break;
case 4:
printf("Enter the position where you want to insert new node: ");
scanf("%d", &n);
printf("Enter data of %d node : ", n);
scanf("%d", &data);

insertAtN(data, n);
break;
case 5:
displayList();
break;
case 0:
break;
default:
printf("Error! Invalid choice. Please choose between 0-5");
}

printf("\n\n\n\n\n");
}
return 0;
}

/**
* Creates a doubly linked list of n nodes.
*
* @n Number of nodes to be created
*/
void createList(int n)
{
int i, data;
struct node *newNode;

if(n >= 1)
{
/*
* Creates and links the head node
*/
head = (struct node *)malloc(sizeof(struct node));

printf("Enter data of 1 node: ");

scanf("%d", &data);

head->data = data;
head->prev = NULL;
head->next = NULL;

last = head;

/*
* Creates and links rest of the n-1 nodes
*/
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));

printf("Enter data of %d node: ", i);

scanf("%d", &data);

newNode->data = data;
newNode->prev = last; //Links new node with the previous node
newNode->next = NULL;

last->next = newNode; //Links previous node with the new node

last = newNode; //Makes new node as last/previous node
}

printf("\nDOUBLY LINKED LIST CREATED SUCCESSFULLY\n");

}
}
/**
* Displays the content of the list from beginning to end
*/
void displayList()
{
struct node * temp;
int n = 1;

if(head == NULL)
{
printf("List is empty.\n");
}
else
{
temp = head;
printf("DATA IN THE LIST:\n");

while(temp != NULL)
{
printf("DATA of %d node = %d\n", n, temp->data);

n++;

/* Moves the current pointer to next node */

temp = temp->next;
}
}
}
/**
* Inserts a new node at the beginning of the doubly linked list
*
* @data Data of the first node i.e. data of the new node
*/
void insertAtBeginning(int data)
{
struct node * newNode;

if(head == NULL)
{
printf("Error, List is Empty!\n");
}
else
{
newNode = (struct node *)malloc(sizeof(struct node));

newNode->data = data;
newNode->next = head; //Points to next node which is currently head
newNode->prev = NULL; //Previous node of first node is NULL

/* Links previous address field of head with newnode */

head->prev = newNode;
/* Makes the new node as head node */
head = newNode;

printf("NODE INSERTED SUCCESSFULLY AT THE BEGINNING OF THE LIST\

n");
}
}

/**
* Inserts a new node at the end of the doubly linked list
*
* @data Data of the last node i.e data of the new node
*/
void insertAtEnd(int data)
{
struct node * newNode;

if(last == NULL)
{
printf("Error, List is empty!\n");
}
else
{
newNode = (struct node *)malloc(sizeof(struct node));

newNode->data = data;
newNode->next = NULL;
newNode->prev = last;

last->next = newNode;
last = newNode;

printf("NODE INSERTED SUCCESSFULLY AT THE END OF LIST\n");

}
}
/**
* Inserts a node at any position in the doubly linked list
*
* @data Data of the new node to be inserted
* @position Position where to insert the new node
*/
void insertAtN(int data, int position)
{
int i;
struct node * newNode, *temp;

if(head == NULL)
{
printf("Error, List is empty!\n");
}
else
{
temp = head;
i=1;

while(i<position-1 && temp!=NULL)

{
temp = temp->next;
i++;
}

if(position == 1)
{
insertAtBeginning(data);
}
else if(temp == last)
{
insertAtEnd(data);
}
else if(temp!=NULL)
{
newNode = (struct node *)malloc(sizeof(struct node));

newNode->data = data;
newNode->next = temp->next; //Connects new node with n+1th node
newNode->prev = temp; //Connects new node with n-1th node

if(temp->next != NULL)
{
/* Connects n+1th node with new node */
temp->next->prev = newNode;
}
/* Connects n-1th node with new node */
temp->next = newNode;

printf("NODE INSERTED SUCCESSFULLY AT %d POSITION\n", position);

}
else
{
printf("Error, Invalid position\n");
}
}
}

(5) Write function to insert a data value after given no. of node in double linked list.

Program:

#include <stdio.h>
#include <stdlib.h>
/*
* Basic structure of Node
*/
struct node {
int data;
struct node * prev;
struct node * next;
}*head, *last;

/*
* Functions used in this program
*/
void createList(int n);
void displayList();
void insertAtBeginning(int data);
void insertAtEnd(int data);
void insertAtN(int data, int position);
int main()
{
int n, data, choice=1;

head = NULL;
last = NULL;

/*
* Runs forever until user chooses 0
*/
while(choice != 0)
{
/*
* Menu creation to use the program
*/
printf("============================================\n");
printf("DOUBLY LINKED LIST PROGRAM\n");
printf("============================================\n");
printf("1. Create List\n");
printf("2. Insert node - at beginning\n");
printf("3. Insert node - at end\n");
printf("4. Insert node - at N\n");
printf("5. Display list\n");
printf("0. Exit\n");
printf("--------------------------------------------\n");
printf("Enter your choice : ");

scanf("%d", &choice);

/*
* Chooses from different menu operation
*/
switch(choice)
{
case 1:
printf("Enter the total number of nodes in list: ");
scanf("%d", &n);

createList(n);
break;
case 2:
printf("Enter data of first node : ");
scanf("%d", &data);

insertAtBeginning(data);
break;
case 3:
printf("Enter data of last node : ");
scanf("%d", &data);

insertAtEnd(data);
break;
case 4:
printf("Enter the position where you want to insert new node: ");
scanf("%d", &n);
printf("Enter data of %d node : ", n);
scanf("%d", &data);

insertAtN(data, n);
break;
case 5:
displayList();
break;
case 0:
break;
default:
printf("Error! Invalid choice. Please choose between 0-5");
}

printf("\n\n\n\n\n");
}

return 0;
}

/**
* Creates a doubly linked list of n nodes.
*
* @n Number of nodes to be created
*/
void createList(int n)
{
int i, data;
struct node *newNode;
if(n >= 1)
{
/*
* Creates and links the head node
*/
head = (struct node *)malloc(sizeof(struct node));

printf("Enter data of 1 node: ");

scanf("%d", &data);

head->data = data;
head->prev = NULL;
head->next = NULL;

last = head;
/*
* Creates and links rest of the n-1 nodes
*/
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));

printf("Enter data of %d node: ", i);

scanf("%d", &data);

newNode->data = data;
newNode->prev = last; //Links new node with the previous node
newNode->next = NULL;

last->next = newNode; //Links previous node with the new node

last = newNode; //Makes new node as last/previous node
}

printf("\nDOUBLY LINKED LIST CREATED SUCCESSFULLY\n");

}
}
/**
* Displays the content of the list from beginning to end
*/
void displayList()
{
struct node * temp;
int n = 1;

if(head == NULL)
{
printf("List is empty.\n");
}
else
{
temp = head;
printf("DATA IN THE LIST:\n");

while(temp != NULL)
{
printf("DATA of %d node = %d\n", n, temp->data);

n++;

/* Moves the current pointer to next node */

temp = temp->next;
}
}
}
/**
* Inserts a new node at the beginning of the doubly linked list
*
* @data Data of the first node i.e. data of the new node
*/
void insertAtBeginning(int data)
{
struct node * newNode;

if(head == NULL)
{
printf("Error, List is Empty!\n");
}
else
{
newNode = (struct node *)malloc(sizeof(struct node));

newNode->data = data;
newNode->next = head; //Points to next node which is currently head
newNode->prev = NULL; //Previous node of first node is NULL

/* Links previous address field of head with newnode */

head->prev = newNode;
/* Makes the new node as head node */
head = newNode;

printf("NODE INSERTED SUCCESSFULLY AT THE BEGINNING OF THE LIST\

n");
}
}
/**
* Inserts a new node at the end of the doubly linked list
*
* @data Data of the last node i.e data of the new node
*/
void insertAtEnd(int data)
{
struct node * newNode;
if(last == NULL)
{
printf("Error, List is empty!\n");
}
else
{
newNode = (struct node *)malloc(sizeof(struct node));

newNode->data = data;
newNode->next = NULL;
newNode->prev = last;

last->next = newNode;
last = newNode;

printf("NODE INSERTED SUCCESSFULLY AT THE END OF LIST\n");

}
}

/**
* Inserts a node at any position in the doubly linked list
* @data Data of the new node to be inserted
* @position Position where to insert the new node
*/
void insertAtN(int data, int position)
{
int i;
struct node * newNode, *temp;

if(head == NULL)
{
printf("Error, List is empty!\n");
}
else
{
temp = head;
i=1;

while(i<position-1 && temp!=NULL)

{
temp = temp->next;
i++;
}

if(position == 1)
{
insertAtBeginning(data);
}
else if(temp == last)
{
insertAtEnd(data);
}
else if(temp!=NULL)
{
newNode = (struct node *)malloc(sizeof(struct node));

newNode->data = data;
newNode->next = temp->next; //Connects new node with n+1th node
newNode->prev = temp; //Connects new node with n-1th node

if(temp->next != NULL)
{
/* Connects n+1th node with new node */
temp->next->prev = newNode;
}
/* Connects n-1th node with new node */
temp->next = newNode;

printf("NODE INSERTED SUCCESSFULLY AT %d POSITION\n", position);

}
else
{
printf("Error, Invalid position\n");
}
}
}

(6) Write a program to create and display the Circular double linked list.

Program:

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

int data;

struct DCLL
{
int info;
struct DCLL *rptr, *lptr;
}*start = NULL, *temp, *neww, *prev, *end = NULL;

void ins_beg_dcll();
void ins_end_dcll();
void del_beg_dcll();
void del_end_dcll();
void create_dcll();
void travers();
void insert();
void delet();
void search();
void update();

void main()
{
int choice;
char ch, ch2 = 'y';
do
{
if (start == NULL)
{
do
{
clrscr();
printf("\n\nError : Linked LIst is Empty Want to Create (Y/N).. ");
fflush(stdin);
scanf("%c", &ch);
if (ch == 'n' || ch == 'N')
{
exit();
}
else if (ch == 'y' || ch == 'Y')
{
create_dcll();
break;
}
else
{
printf("\n\nError : Invalid Choice");
}
} while (ch == 'y' || ch == 'Y');
}
else
{
clrscr();

printf("\n1. Insert");
printf("\n2. Delete");
printf("\n3. Traverse");
printf("\n4. Search");
printf("\n5. Update");
printf("\n\nPress 0 to Exit");

printf("\n\nEnter your Choice : ");

scanf("%d", &choice);

switch (choice)
{
case 0:
exit();
break;
case 1:
insert();
travers();
break;
case 2:
delet();
travers();
break;
case 3:
travers();
break;
case 4:
search();
break;
case 5:
update();
break;
default:
printf("\n\nError : Invalid Choice. \n");
}
printf("\n\nWant to Continue (Y/N)... ");
fflush(stdin);
scanf("%c", &ch2);
}

} while (ch2 == 'y' || ch2 == 'Y');

}
void create_dcll()
{
char ch;
do
{
clrscr();
printf("\nEnter Node Info");
printf("\n\nEnter Info : ");
scanf("%d", &data);

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

temp->info = data;
temp->rptr = start;
temp->lptr = start;

if (start == NULL)
{
start = temp;
end = temp;
start->rptr = start;
start->lptr = start;
}
else
{
temp->lptr = end;
end->rptr = temp;
temp->rptr = start;
start->lptr = temp;
end = temp;
}

printf("\n\nDo you want to insert another Node (Y/N)... ");

fflush(stdin);
scanf("%c", &ch);

} while (ch == 'y' || ch == 'Y');

}
void ins_beg_dcll()
{
neww->rptr = start;
start->lptr = neww;
neww->lptr = end;
end->rptr = neww;
start = neww;
}
void ins_end_dcll()
{
neww->lptr = end;
end->rptr = neww;
neww->rptr = start;
start->lptr = neww;
end = neww;
}
void travers()
{
temp = start;
if (start == NULL)
{
printf("\n\nError : Linked list is Empty");
}
else
{
if (start == end)
{
printf("\n%d", temp->info);
}
else
{
printf("\n%d", temp->info);
do
{
temp = temp->rptr;
printf("\n%d", temp->info);
} while (temp != end);
}
}
}
void insert()
{
int pos, count = 1;
printf("\nEnter Position : ");
scanf("%d", &pos);
printf("\nEnter Info :");
scanf("%d", &data);

neww = (struct DCLL *)malloc(sizeof(struct DCLL));

neww->info = data;
temp = start;

if (pos == 1)
{
ins_beg_dcll();
}
else
{
while (count != pos - 1 && temp->rptr != start)
{
count++;
temp = temp->rptr;
}
if (temp->rptr == start && count < pos - 1)
{
printf("\n\nError : Invalid Position...");
}
else if (temp->rptr == start && count == pos - 1)
{
ins_end_dcll();
}
else
{
neww->rptr = temp->rptr;
neww->lptr = temp;
temp->rptr->lptr = neww;
temp->rptr = neww;
}
}
}
void delet()
{
int pos, count = 1;
printf("\n\nEnter Position : ");
scanf("%d", &pos);
temp = start;
if (pos == 1)
{
del_beg_dcll();
}
else
{
while (count != pos && temp != end)
{
prev = temp;
temp = temp->rptr;
count++;
}

if (temp == end && count < pos - 1)

{
printf("\n\nError : Invalid Position.");
}
else if (temp == end && count == pos)
{
del_end_dcll();
}
else
{
prev->rptr = temp->rptr;
temp->rptr->lptr = prev;
free(temp);
}
}
}
void del_beg_dcll()
{
start = start->rptr;
start->lptr = end;
end->rptr = start;
free(temp);
}
void del_end_dcll()
{
end = end->lptr;
end->rptr = start;
start->lptr = end;
free(temp);
}
void search()
{
int src, count = 1;
printf("\n\nEnter Info : ");
scanf("%d", &src);
temp = start;
do
{
prev = temp;
if (prev->info == src)
{
printf("\n\nSearch Value found at %d Position.", count);
break;
}
count++;
temp = temp->rptr;
} while (prev != end);

if (temp == start)
{
printf("\n\nError : Search value doesn't exists.");
}
}
void update()
{
int pos, count = 1, dt;
printf("\n\nEnter Position : ");
scanf("%d", &pos);
printf("\nEnter New Info : ");
scanf("%d", &dt);

temp = prev = start;

do
{
if (count == pos && prev != end)
{
prev->info = dt;
break;
}
prev = temp;
temp = temp->rptr;
count++;
} while (prev != end);

if (temp == start)
{
printf("\n\nError : Invalid Choice ");
}
}

ASSIGNMENT NO. –6

OBJECTIVE:- Programs Based on Stack.

1. Write a function to implement the push operation in stack with the help of static
memory allocation

Program:

/*PUSH FUNCTION*/
void push (int stack[], int item)
{ if (top == (MAX-1))
status = 0;
else
{ status = 1;
++top;
stack [top] = item;
}
}

2. Write a function to implement the pop operation in stack with the help of static
memory

allocation .

Program:

/*POP FUNCTION*/
int pop (int stack[])
{
int ret;
if (top == -1)
{ ret = 0;
status = 0;
}
else
{ status = 1;
ret = stack [top];
--top;
}
return ret;
}

3. Write a function to implement the peek operation in stack with the help of static
memory allocation.

Program:

//Peek operation..................
void peek()
{

if(top==-1)
{
printf("stack is under flow");
}
else
{

printf("\n\n top is on %d",a[top]);

}
}

Note: A complete c program for PUSH, POP and PEEK operation in stack with the
help of static memory allocation(i.e. Array).

Program:

#include<stdio.h>

#define MAX 50
void push();
void pop();
void peep();
void display();
int a[MAX],top = -1,item,i;
int main()
{
int n;
do
{
printf("\n\n\nwhat u want to do \n\n1. for push \n\n2. for pop \n\n3.for peek \n\n4. for
display \n\n5.for exit\n\n ");
scanf("%d",&n);

switch(n)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
peek();
break;
case 4:
display();
break;

default :
printf("invalid no");
}
}while(n!=5);
}
//Push operation................................
void push()
{
if(top==MAX-1)
{
printf("stack is over flow");
}
else
{
printf("entet the item");
scanf("%d",&item);
top++;
a[top]=item;
printf("\n\n\ninsreted item is %d",item);
}
}
// Pop Opretion........................
void pop()
{
if(top==-1)
{
printf("stack is under flow");
}
else
{
item=a[top];
top--;
printf("\n\n deleted item is %d",item);
}
}
//Peek operation..................
void peek()
{
if(top==-1)
{
printf("stack is under flow");
}
else
{
printf("\n\n top is on %d",a[top]);
}
}
void display()
{
if(top == -1)
{
printf("stack is Empty");
}
else
{
for(i=0; i<=top; i++)
{
printf("\n\n stack is %d",a[i]);
}
}
}

4. Write a function to implement the push operation in stack with the help of dynamic
memory allocation.

Program:

// to insert elements in stack

void push()

{
int val,count;

struct node *temp;

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

count = st_count();

if (count <= MAX - 1)

{
printf("\nEnter value which you want to push into the stack :\n");

scanf("%d",&val);

temp->data = val;

temp->link = top;

top = temp;

}
else
printf("WARNING: STACK FULL\n");
}
5. Write a function to implement the pop operation stack with the help of dynamic
memory allocation.

Program:

// to delete elements from stack

void pop()
{
struct node *temp;
if (top == NULL)
printf("**Stack is empty**\n");
else

{
temp = top;
printf("Value popped out is %d \n",temp->data);
top = top->link;
free(temp);
}
}

6. Write a function to implement the peek operation stack with the help of dynamic
memory allocation.

Program:

int peek()
{
if(isEmpty())
{
printf("Stack is Empty\n");
exit(1);
}
return top->data;
}

Note: A complete c program for PUSH, POP and PEEK operation in stack with the
help of dynamic memory allocation (i.e. using malloc function).

Program:

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

struct node
{
int data;
struct node *link;
}*top = NULL;
int isEmpty()
{
if(top == NULL)
{
return 1;
}
else
{
return 0;
}
}

void push(int item)

{
struct node *temp;
temp = (struct node *)malloc(sizeof(struct node));
if(temp == NULL)
{
printf("Stack is Full\n");
return;
}
temp->data = item;
temp->link = top;
top = temp;
}

int delete_node()
{
struct node *temp;
int item;
if(isEmpty())
{
printf("Stack is Empty\n");
exit(1);
}
temp = top;
item = temp->data;
top = top->link;
free(temp);
return item;
}

void display()
{
struct node *ptr;
if(isEmpty())
{
printf("Stack is Empty\n");
return;
}
printf("Stack Elements:\n\n");
for(ptr = top; ptr != NULL; ptr = ptr->link)
{
printf(" %d\n", ptr->data);
}
printf("\n");
}

int peek()
{
if(isEmpty())
{
printf("Stack is Empty\n");
exit(1);
}
return top->data;
}
int main()
{
int option, element;
while(1)
{
printf("1. Push an Element on the Stack\n");
printf("2. delete_node or Delete an Element from the Stack\n");
printf("3. Display Top-most item (Peek) of the Stack\n");
printf("4. Display All Element of the Stack\n");
printf("5. Exit\n");
printf("Enter your Option:\t");
scanf("%d", &option);
switch(option)
{
case 1:
printf("Enter the item to be Pushed on the Stack:\t");
scanf("%d", &element);
push(element);
break;
case 2:
element = delete_node();
printf("Deleted Element:\t%d\n", element);
break;
case 3:
printf("Element at the Top of Stack:\t%d\n", peek());
break;
case 4:
display();
break;
case 5:
exit(1);
default :
printf("Wrong Option Selected\n");
}
}
return 0;
}

7. Write a function to implement two stacks in a single array.

Program:

#include<stdio.h>
#include<stdlib.h>
void main()
{
int n,top1,top2,ch=1,a,i,arr[100];
printf("Enter size of array you want to use\n");
scanf("%d",&n);
top1=-1;
top2=n;
while(ch!=0)
{
printf("What do u want to do?\n");
printf("1.Push element in stack 1\n");
printf("2.Push element in stack 2\n");
printf("3.Pop element from stack 1\n");
printf("4.Pop element from stack 2\n");
printf("5.Display stack 1\n");
printf("6.Display stack 2\n");
printf("0.EXIT\n");
scanf("%d",&ch);
switch(ch)
{
case 1:
{
printf("Enter the element\n");
scanf("%d",&a);
if(top1!=(top2-1))
arr[++top1]=a;
else
printf("Overflow\n");
break;
}
case 2:
{
printf("Enter the element\n");
scanf("%d",&a);
if(top2!=(top1+1))
arr[--top2]=a;
else
printf("Overflow\n");
break;
}
case 3:
{
if(top1==-1)
printf("Stack1 is empty\n");
else
{
a=arr[top1--];
printf("%d\n",a);
}
break;
}
case 4:
{
if(top2==n)
printf("Stack2 is empty\n");
else
{
a=arr[top2++];
printf("%d\n",a);
}
break;
}
case 5:
{
if(top1==-1)
printf("Stack1 is empty\n");
else
{
printf("Stack1 is-->>\n");
for(i=0;i<=top1;i++)
printf("%d ",arr[i]);
printf("\n");
}
break;
}
case 6:
{
if(top2==n)
printf("Stack2 is empty\n");
else
{
printf("Stack2 is-->>\n");
for(i=(n-1);i>=top2;i--)
printf("%d ",arr[i]);
printf("\n");
}
break;
}
case 0:
break;
}
}
}
ASSIGNMENT NO. –7

OBJECTIVE :- Programs Based on Queues and Circular Queues

(1)Write a function to implement insertion in a linear queue with the help of static
memory allocation.

Program:

insert()
{
int add_item;
if (rear == MAX - 1)
printf("Queue Overflow \n");
else
{
if (front == - 1)
/*If queue is initially empty */
front = 0;
printf("Inset the element in queue : ");
scanf("%d", &add_item);
rear = rear + 1;
queue_array[rear] = add_item;
}
} /*End of insert()*/

(2) Write a function to implement deletion in a linear queue with the help of static
memory allocation.

Program:

delete()
{
if (front == - 1 || front > rear)
{
printf("Queue Underflow \n");
return ;
}
else
{
printf("Element deleted from queue is : %d\n", queue_array[front]);
front = front + 1;
}
} /*End of delete() */

Note: A complete c program for insertion, deletion operation in linear queue with the
help of static memory allocation.

Program:
#include <stdio.h>
#define MAX 50
int queue_array[MAX];
int rear = - 1;
int front = - 1;
main()
{
int choice;
while (1)
{
printf("1.Insert element to queue \n");
printf("2.Delete element from queue \n");
printf("3.Display all elements of queue \n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
default:
printf("Wrong choice \n");
} /*End of switch*/
} /*End of while*/
} /*End of main()*/
insert()
{
int add_item;
if (rear == MAX - 1)
printf("Queue Overflow \n");
else
{
if (front == - 1)
/*If queue is initially empty */
front = 0;
printf("Inset the element in queue : ");
scanf("%d", &add_item);
rear = rear + 1;
queue_array[rear] = add_item;
}
} /*End of insert()*/
delete()
{
if (front == - 1 || front > rear)
{
printf("Queue Underflow \n");
return ;
}
else
{
printf("Element deleted from queue is : %d\n", queue_array[front]);
front = front + 1;
}
} /*End of delete() */
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_array[i]);
printf("\n");
}
} /*End of display() */

(3) Write a function to implement insertion in a linear queue with the help of dynamic
memory allocation.

Program:

// to insert elements in queue

void insert()
{
struct node *temp;
temp = (struct node*)malloc(sizeof(struct node));
printf("Enter value to be inserted \n");
scanf("%d", &temp->data);
temp->link = NULL;
if (rear == NULL)
{
front = rear = temp;
}
else
{
rear->link = temp;
rear = temp;
}
}
(4) Write a function to implement deletion in a linear queue with the help of dynamic
memory allocation.

Program:

// delete elements from queue

void delete()
{
struct node *temp;
temp = front;
if (front == NULL)
{
printf("queue is empty \n");
front = rear = NULL;
}
else
{
printf("deleted element is %d\n", front->data);
front = front->link;
free(temp);
}
}

Note: A complete c program for insertion, deletion operation in linear queue with the
help of dynamic memory allocation.

Program:

#include <stdio.h>
#include <stdlib.h>
#define MAX 10
struct node
{
int data;
struct node *link;
}*front, *rear;

// function protypes
void insert();
void delete();
void queue_size();
void check();
void first_element();
void main()
{
int choice, value;

while(1)
{
printf("enter the choice \n");
printf("1 : create an empty queue \n2 : Insert element\n");
printf("3 : Dequeue an element \n4 : Check if empty\n");
printf("5. Get the first element of the queue\n");
printf("6. Get the number of entries in the queue\n");
printf("7. Exit\n");
scanf("%d", &choice);
switch (choice) // menu driven program
{
case 1:
printf("Empty queue is created with a capacity of %d\n", MAX);
break;
case 2:
insert();
break;
case 3:
delete();
break;
case 4:
check();
break;
case 5:
first_element();
break;
case 6:
queue_size();
break;
case 7:
exit(0);
default:
printf("wrong choice\n");
break;
}
}
}

// to insert elements in queue

void insert()
{
struct node *temp;
temp = (struct node*)malloc(sizeof(struct node));
printf("Enter value to be inserted \n");
scanf("%d", &temp->data);
temp->link = NULL;
if (rear == NULL)
{
front = rear = temp;
}
else
{
rear->link = temp;
rear = temp;
}
}

// delete elements from queue

void delete()
{
struct node *temp;
temp = front;
if (front == NULL)
{
printf("queue is empty \n");
front = rear = NULL;
}
else
{
printf("deleted element is %d\n", front->data);
front = front->link;
free(temp);
}
}

// check if queue is empty or not

void check()
{
if (front == NULL)
printf("\nQueue is empty\n");
else
printf("*************** Elements are present in the queue **************\n");
}

// returns first element of queue

void first_element()
{
if (front == NULL)
{
printf("**************** The queue is empty ****************\n");
}
else
printf("**************** The front element is %d ***********\n", front->data);
}

// returns number of entries and displays the elements in queue

void queue_size()
{
struct node *temp;
temp = front;
int cnt = 0;
if (front == NULL)
{
printf(" queue empty \n");
}
while (temp)
{
printf("%d ", temp->data);
temp = temp->link;
cnt++;
}
printf("********* size of queue is %d ******** \n", cnt);
}

(5) Write a functions to implement the insertion and deletion operations on a circular
queue with the help of static memory allocation.

Program:

#include<stdio.h>
#define SIZE 5 /* Size of Circular Queue */
int CQ[SIZE],f=-1,r=-1; /* Global declarations */

CQinsert(int elem)
{ /* Function for Insert operation */
if( CQfull()) printf("\n\n Overflow!!!!\n\n");
else
{
if(f==-1)f=0;
r=(r+1) % SIZE;
CQ[r]=elem;
}
}
int CQdelete()
{ /* Function for Delete operation */
int elem;
if(CQempty()){ printf("\n\nUnderflow!!!!\n\n");
return(-1); }
else
{
elem=CQ[f];
if(f==r){ f=-1; r=-1;} /* Q has only one element ? */
else
f=(f+1) % SIZE;
return(elem);
}
}
int CQfull()
{ /* Function to Check Circular Queue Full */
if( (f==r+1) || (f == 0 && r== SIZE-1)) return 1;
return 0;
}

int CQempty()
{ /* Function to Check Circular Queue Empty */
if(f== -1) return 1;
return 0;
}

display()
{ /* Function to display status of Circular Queue */
int i;
if(CQempty()) printf(" \n Empty Queue\n");
else
{
printf("Front[%d]->",f);
for(i=f;i!=r;i=(i+1)%SIZE)
printf("%d ",CQ[i]);
printf("%d ",CQ[i]);
printf("<-[%d]Rear",r);
}
}

main()
{ /* Main Program */
int opn,elem;
do
{

printf("\n ### Circular Queue Operations ### \n\n");

printf("\n Press 1-Insert, 2-Delete,3-Display,4-Exit\n");
printf("\n Your option ? ");
scanf("%d",&opn);
switch(opn)
{
case 1: printf("\n\nRead the element to be Inserted ?");
scanf("%d",&elem);
CQinsert(elem); break;
case 2: elem=CQdelete();
if( elem != -1)
printf("\n\nDeleted Element is %d \n",elem);
break;
case 3: printf("\n\nStatus of Circular Queue\n\n");
display(); break;
case 4: printf("\n\n Terminating \n\n"); break;
default: printf("\n\nInvalid Option !!! Try Again !! \n\n");
break;
}
printf("\n\n\n\n Press a Key to Continue . . . ");

}while(opn != 4);}
ASSIGNMENT NO. –8

OBJECTIVE :- Implement the following programs with the help of Binary Tree.

(1) Write a program in C to create and travel thr tree in in-order.

Program: Inorder solution

#include<stdio.h>
#include<malloc.h>
struct binNode
{
int val;
struct binNode *left,*right;
};
struct binNode *createbinTree();
struct binNode *attach(struct binNode *tree, struct binNode *node);
void inOrderTravel(struct binNode *binTree);
void main()
{
struct binNode *binTree;
binTree=createbinTree();
printf("The tree is:");
inOrderTravel(binTree);
}
struct binNode *createbinTree()
{
int val,size;
struct binNode *treePtr,*newNode;
treePtr=NULL;
val=0;
size=sizeof(struct binNode);
while(val>=0)
{
printf("\nEnter the val");
scanf("%d",&val);
if (val>=0)
{
newNode=(struct binNode *) malloc (size );
newNode->val=val;
newNode->left=NULL;
newNode->right=NULL;
treePtr=attach(treePtr,newNode);
}
}
return treePtr;
}
struct binNode *attach(struct binNode *tree,struct binNode *node)
{
if (tree==NULL)
tree=node;
else
{
if (node->val<tree->val)
tree->left=attach(tree->left,node);
else
tree->right=attach(tree->right,node);
}
return tree;
}
void inOrderTravel(struct binNode *binTree)
{
if( binTree==NULL)
return ;
inOrderTravel(binTree->left);
printf("%d-",binTree->val);
inOrderTravel(binTree->right);
}

(2) Write a program in C to create and travel thr tree in pre-order.

Program: Solution Preorder

#include<stdio.h>
#include<malloc.h>
struct binNode
{
int val;
struct binNode *left,*right;
};
struct binNode *createbinTree();
struct binNode *attach(struct binNode *tree, struct binNode *node);
void inOrderTravel(struct binNode *binTree);
void main()
{
struct binNode *binTree;
binTree=createbinTree();
printf("The tree is:");
inOrderTravel(binTree);
}
struct binNode *createbinTree()
{
int val,size;
struct binNode *treePtr,*newNode;
treePtr=NULL;
val=0;
size=sizeof(struct binNode);
while(val>=0)
{
printf("\nEnter the val");
scanf("%d",&val);
if (val>=0)
{
newNode=(struct binNode *) malloc (size );
newNode->val=val;
newNode->left=NULL;
newNode->right=NULL;
treePtr=attach(treePtr,newNode);
}
}
return treePtr;
}
struct binNode *attach(struct binNode *tree,struct binNode *node)
{
if (tree==NULL)
tree=node;
else
{
if (node->val<tree->val)
tree->left=attach(tree->left,node);
else
tree->right=attach(tree->right,node);
}
return tree;
}
void inOrderTravel(struct binNode *binTree)
{
if( binTree==NULL)
return ;
printf("%d-",binTree->val);
inOrderTravel(binTree->left);
inOrderTravel(binTree->right);
}

(3) Write a program in C to create and travel thr tree in post-order.

Program: Solution PostOrder

#include<stdio.h>
#include<malloc.h>
struct binNode
{
int val;
struct binNode *left,*right;
};
struct binNode *createbinTree();
struct binNode *attach(struct binNode *tree, struct binNode *node);
void inOrderTravel(struct binNode *binTree);
void main()
{
struct binNode *binTree;
binTree=createbinTree();
printf("The tree is:");
inOrderTravel(binTree);
}
struct binNode *createbinTree()
{
int val,size;
struct binNode *treePtr,*newNode;
treePtr=NULL;
val=0;
size=sizeof(struct binNode);
while(val>=0)
{
printf("\nEnter the val");
scanf("%d",&val);
if (val>=0)
{
newNode=(struct binNode *) malloc (size );
newNode->val=val;
newNode->left=NULL;
newNode->right=NULL;
treePtr=attach(treePtr,newNode);
}
}
return treePtr;
}
struct binNode *attach(struct binNode *tree,struct binNode *node)
{
if (tree==NULL)
tree=node;
else
{
if (node->val<tree->val)
tree->left=attach(tree->left,node);
else
tree->right=attach(tree->right,node);
}
return tree;
}
void inOrderTravel(struct binNode *binTree)
{
if( binTree==NULL)
return ;
inOrderTravel(binTree->left);
inOrderTravel(binTree->right);
printf("%d-",binTree->val);
}
ASSIGNMENT NO. –9

OBJECTIVE:- Implement the following programs with the help of Binary Search Tree

(1) Write a program in C to insert an element in a Binary Search Tree

Solution:

#include<stdio.h>
#include<malloc.h>
struct binNode
{
int val;
struct binNode *left,*right;
};
struct binNode *createbinTree();
struct binNode *attach(struct binNode *tree, struct binNode *node);
struct binNode *insertBST(struct binNode *binTree,int val,int *flag);
void inOrderTravel(struct binNode *binTree);
void main()
{
int result,val;
struct binNode *binTree;
binTree=createbinTree();
printf("\nEnter the value to be inserted:");
scanf("%d",&val);
binTree=insertBST(binTree,val,&result);
if(result==1)
{
printf("\nInsertion Successful:");
inOrderTravel(binTree);
}
else
printf("\nDuplicate value");
}
struct binNode *createbinTree()
{
int val,size;
struct binNode *treePtr,*newNode;
treePtr=NULL;
val=0;
size=sizeof(struct binNode);
while(val>=0)
{
printf("\nEnter the val");
scanf("%d",&val);
if (val>=0)
{
newNode=(struct binNode *) malloc (size );
newNode->val=val;
newNode->left=NULL;
newNode->right=NULL;
treePtr=attach(treePtr,newNode);
}
}
return treePtr;
}
struct binNode *attach(struct binNode *tree,struct binNode *node)
{
if (tree==NULL)
tree=node;
else
{
if (node->val<tree->val)
tree->left=attach(tree->left,node);
else
tree->right=attach(tree->right,node);
}
return tree;
}
struct binNode *insertBST(struct binNode *binTree, int val,int *flag)
{
int size;
struct binNode *ptr;
size= sizeof(struct binNode);
if(binTree==NULL)
{
ptr=(struct binNode *)malloc (size);
ptr->val=val;
ptr->left=NULL;
ptr->right=NULL;
binTree=ptr;
*flag=1;
return binTree;
}
if(val==binTree->val)
{
*flag=0;
return binTree;
}
else
if(val<binTree->val)
binTree->left=insertBST(binTree->left,val,flag);
else
binTree->right=insertBST(binTree->right,val,flag);
return binTree;
}
void inOrderTravel(struct binNode *binTree)
{
if( binTree==NULL)
return ;
inOrderTravel(binTree->left);
printf("%d-",binTree->val);
inOrderTravel(binTree->right);
}

(2) Write a program in C to search an element in Binary Search Tree

Solution
#include<stdio.h>
#include<malloc.h>
struct binNode
{
int val;
struct binNode *left,*right;
};
struct binNode *createbinTree();
struct binNode *attach(struct binNode *tree, struct binNode *node);
int searchBST(struct binNode *binTree,int val);

void inOrderTravel(struct binNode *binTree);

void main()
{
int val,result;
struct binNode *binTree;
binTree=createbinTree();
//printf("The tree is:");
//inOrderTravel(binTree);

printf("\nEnter the value to be search:");

scanf("%d",&val);
result=searchBST(binTree,val);

if(result==1)
{

printf("\nSearch Successful");
}
else
printf("Search Un-Successful");

}
struct binNode *createbinTree()
{
int val,size;
struct binNode *treePtr,*newNode;
treePtr=NULL;
val=0;
size=sizeof(struct binNode);
while(val>=0)
{
printf("\nEnter the val");
scanf("%d",&val);
if (val>=0)
{
newNode=(struct binNode *) malloc (size );
newNode->val=val;
newNode->left=NULL;
newNode->right=NULL;
treePtr=attach(treePtr,newNode);
}
}
return treePtr;
}
struct binNode *attach(struct binNode *tree,struct binNode *node)
{
if (tree==NULL)
tree=node;
else
{

if (node->val<tree->val)
tree->left=attach(tree->left,node);
else
tree->right=attach(tree->right,node);
}
return tree;
}
/*void inOrderTravel(struct binNode *binTree)
{
if( binTree==NULL)
return ;
inOrderTravel(binTree->left);
printf("%d-",binTree->val);
inOrderTravel(binTree->right);
}*/
int searchBST (struct binNode *binTree,int val)
{
int flag;
if(binTree==NULL)
return 0;

if (val==binTree->val)
return 1;
else
if(val<binTree->val)
flag=searchBST(binTree->left,val);
else
flag=searchBST(binTree->right,val);
return flag; }
(3) Write a program in C to delete a node from binary search tree
Solution

#include<stdio.h>
#include<malloc.h>
struct binNode
{
int val;
struct binNode *left,*right;
};
struct binNode *createbinTree();
struct binNode *attach(struct binNode *tree, struct binNode *node);
struct binNode *searchBST(struct binNode *binTree,int val,int *flag);
struct binNode *findParent(struct binNode *binTree, struct binNode *ptr);
struct binNode *delNodeBST(struct binNode *binTree, int val,int *flag);
struct binNode *findSucc(struct binNode *ptr);

void inOrderTravel(struct binNode *binTree);

void main()
{
int val,result;
struct binNode *binTree;
binTree=createbinTree();

printf("\nEnter the value to be deleted:");

scanf("%d",&val);

binTree=delNodeBST(binTree,val,&result);
if(result==1)
{

printf("\nDeletion Successful");
inOrderTravel(binTree);
}
else
printf("\nNode not present in tree");
}
struct binNode *createbinTree()
{
int val,size;
struct binNode *treePtr,*newNode;
treePtr=NULL;
val=0;
size=sizeof(struct binNode);
while(val>=0)
{
printf("\nEnter the val");
scanf("%d",&val);
if (val>=0)
{
newNode=(struct binNode *) malloc (size );
newNode->val=val;
newNode->left=NULL;
newNode->right=NULL;
treePtr=attach(treePtr,newNode);
}
}
return treePtr;
}
struct binNode *attach(struct binNode *tree,struct binNode *node)
{
if (tree==NULL)
tree=node;
else
{
if (node->val<tree->val)
tree->left=attach(tree->left,node);
else
tree->right=attach(tree->right,node);
}
return tree;
}
struct binNode *delNodeBST (struct binNode *binTree,int val,int *flag)
{
int size, nval;
struct binNode *ptr,*parent,*succPtr;
if(binTree==NULL)
{
*flag=0;
return binTree;
}
ptr=searchBST(binTree,val,flag);
if(*flag==1)
parent=findParent(binTree,ptr);
else
return binTree;
if(ptr->left==NULL && ptr->right==NULL)
{
if(parent->left==ptr)
parent->left=NULL;
else
if(parent->right==ptr)
parent->right==NULL;
free(ptr);
}
if(ptr->left!=NULL && ptr->right==NULL)
{
if (parent ->left==ptr)
parent->left=ptr->left;
else
if(parent->right==ptr)
parent->right=ptr->left;
free(ptr);
return binTree;
}
else
if (ptr->left==NULL && ptr->right!=NULL)
{
if(parent->left==ptr)
parent->left=ptr->right;
else
if(parent->right==ptr)
parent->right=ptr->right;
free(ptr);
return binTree;
}
if(ptr->left!=NULL && ptr->right!=NULL)
{
succPtr=findSucc(ptr);
nval=succPtr->val;
delNodeBST(binTree, succPtr->val,flag);
ptr->val=nval;
}
return binTree;
}
void inOrderTravel(struct binNode *binTree)
{
if( binTree==NULL)
return ;
inOrderTravel(binTree->left);
printf("%d-",binTree->val);
inOrderTravel(binTree->right);
}
struct binNode *searchBST (struct binNode *binTree,int val,int *flag)
{
if(binTree==NULL)
{
*flag=0;
return binTree;
}
else
{
if (val==binTree->val)
{
*flag=1;
return binTree;
}
else
{
if(val<binTree->val)
return searchBST(binTree->left,val,flag);
else
return searchBST(binTree->right,val,flag);
}
}
}
struct binNode *findSucc(struct binNode *ptr)
{
struct binNode *succPtr;
succPtr=ptr->right;
while(succPtr->left!=NULL)
succPtr=succPtr->left;
return succPtr;
}
struct binNode *findParent(struct binNode *binTree,struct binNode *ptr)
{
struct binNode *pt;
if(binTree==NULL)
return binTree;
else
{
if(binTree->left==ptr || binTree->right==ptr)
{
pt=binTree;
return pt;
}
else
{
if(ptr->val<binTree->val)
pt=findParent(binTree->left,ptr);
else
pt=findParent(binTree->right,ptr);
}
}
return pt;
}
ASSIGNMENT NO. –10

OBJECTIVE:- Implement the following programs with the help of Graphs.

1. Write a program to implement the BFS algorithm with the help of graph.

Program:

#include<stdio.h>
#include<conio.h>
int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;
void bfs(int v)
{
for(i=1;i<=n;i++)
if(a[v][i] && !visited[i])
q[++r]=i;
if(f<=r)
{
visited[q[f]]=1;
bfs(q[f++]);
}
}
void main()
{
int v;
clrscr();
printf("\n Enter the number of vertices:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
q[i]=0;
visited[i]=0;
}
printf("\n Enter graph data in matrix form:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
printf("\n Enter the starting vertex:");
scanf("%d",&v);
bfs(v);
printf("\n The node which are reachable are:\n");
for(i=1;i<=n;i++)
if(visited[i])
printf("%d\t",i);
else
printf("\n Bfs is not possible");
getch();
}
2. Write a program to implement the DFS algorithm with the help of graph.

PROGRAM:

#include <stdio.h>
#include <stdlib.h>
/* ADJACENCY MATRIX */
int source,V,E,time,visited[20],G[20][20];
void DFS(int i)
{
int j;
visited[i]=1;
printf(" %d->",i+1);
for(j=0;j<V;j++)
{
if(G[i][j]==1&&visited[j]==0)
DFS(j);
}
}
int main()
{
int i,j,v1,v2;
printf("\t\t\tGraphs\n");
printf("Enter the no of edges:");
scanf("%d",&E);
printf("Enter the no of vertices:");
scanf("%d",&V);
for(i=0;i<V;i++)
{
for(j=0;j<V;j++)
G[i][j]=0;
}
/* creating edges :P */
for(i=0;i<E;i++)
{
printf("Enter the edges (format: V1 V2) : ");
scanf("%d%d",&v1,&v2);
G[v1-1][v2-1]=1;

for(i=0;i<V;i++)
{
for(j=0;j<V;j++)
printf(" %d ",G[i][j]);
printf("\n");
}
printf("Enter the source: ");
scanf("%d",&source);
DFS(source-1);
return 0;
}

(3) Write a program to implement the prim’s algorithm for Minimum cost spanning
tree.
PROGRAM:
#include<stdio.h>
#include<conio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
void main()
{
clrscr();
printf("\n Enter the number of nodes:");
scanf("%d",&n);
printf("\n Enter the adjacency matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
visited[1]=1;
printf("\n");
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]<min)
if(visited[i]!=0)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0)
{
printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n Minimun cost=%d",mincost);
getch();
}

(4) Write a program to implement the kruskal’s algorithm for Minimum cost spanning
tree.
PROGRAM:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0,cost[9][9],parent[9];
int find(int);
int uni(int,int);
void main()
{
clrscr();
printf("\n\n\tImplementation of Kruskal's algorithm\n\n");
printf("\nEnter the no. of vertices\n");
scanf("%d",&n);
printf("\nEnter the cost adjacency matrix\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
}
printf("\nThe edges of Minimum Cost Spanning Tree are\n\n");
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]<min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v))
{
printf("\n%d edge (%d,%d) =%d\n",ne++,a,b,min);
mincost +=min;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n\tMinimum cost = %d\n",mincost);
getch();
}
int find(int i)
{
while(parent[i])
i=parent[i];
return i;
}
int uni(int i,int j)
{
if(i!=j)
{
parent[j]=i;
return 1;
}
return 0;
}

(5) Write a program to implement the shortest path Dijkstra's algorithm in C

language.
PROGRAM:
#include <stdio.h>
#include <conio.h>
#define infinity 999

void dij(int n,int v,int cost[10][10],int dist[])

{
int i,u,count,w,flag[10],min;
for(i=1;i<=n;i++)
flag[i]=0,dist[i]=cost[v][i];
count=2;
while(count<=n)
{
min=99;
for(w=1;w<=n;w++)
if(dist[w]<min && !flag[w])
min=dist[w],u=w;
flag[u]=1;
count++;
for(w=1;w<=n;w++)
if((dist[u]+cost[u][w]<dist[w]) && !flag[w])
dist[w]=dist[u]+cost[u][w];
}
}
void main()
{
int n,v,i,j,cost[10][10],dist[10];
clrscr();
printf("\n Enter the number of nodes:");
scanf("%d",&n);
printf("\n Enter the cost matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=infinity;
}
printf("\n Enter the source matrix:");
scanf("%d",&v);
dij(n,v,cost,dist);
printf("\n Shortest path:\n");
for(i=1;i<=n;i++)
if(i!=v)
printf("%d->%d,cost=%d\n",v,i,dist[i]);
getch();
}
ASSIGNMENT NO. 11

OBJECTIVE:- Implement the following programs with the help of Searching.

1. Write a program to input how many numbers and then input the numbers and
then search any number with the help of sequential/Linear search.

PROGRAM:
#include <stdio.h>
void main()
{
int array[10];
int i, num, keynum, found = 0;
printf("Enter the value of num \n");
scanf("%d", &num);
printf("Enter the elements one by one \n");
for (i = 0; i < num; i++)
{
scanf("%d", &array[i]);
}
printf("Input array is: \n");
for (i = 0; i < num; i++)
{
printf("%d", array[i]);
}
printf("\n Enter the element to be searched \n");
scanf("%d", &keynum);
/* Linear search begins */
for (i = 0; i < num ; i++)
{
if (keynum == array[i] )
{
found = 1;
break;
}
}
if (found == 1)
printf("Element is present in the array\n");
else
printf("Element is not present in the array\n");
}

2. Write a program to input how many numbers and then input the numbers and
then search any number with the help of Binary search.
PROGRAM:

#include <stdio.h>
int main()
{
int c, first, last, middle, n, search, array[100];
printf("Enter number of elements\n");
scanf("%d",&n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++)
scanf("%d",&array[c]);
printf("Enter value to find\n");
scanf("%d", &search);
first = 0;
last = n - 1;
middle = (first+last)/2;
while (first <= last) {
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search) {
printf("%d found at location %d.\n", search, middle+1);
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
if (first > last)
printf("Not found! %d is not present in the list.\n", search);
return 0;
}
ASSIGNMENT NO. –12

OBJECTIVE:- Implement the following programs with the help of Sorting

(1) Write a program to input 10 numbers and then sort that numbers with the help
of bubble sort.
Solution

#include<stdio.h>
void main()
{
int array[100],size,i,j,temp;
printf("Enter the size of the array:");
scanf("%d",&size);
printf("\nEnter the elements:");
for(i=0;i<size;i++)
{
scanf("\n%d",&array[i]);
}
for(i=0;i<size;i++)
{
for(j=0;j<size-i-1;j++)
{
if(array[j+1]<array[j])
{
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
printf("\nThe sorted array is:");
for(i=0;i<size;i++)
{
printf("\n%d",array[i]);
}
}

(2) Write a program to input 10 numbers and then sort that numbers with the help
of Selection sort.
Solution
#include<stdio.h>
void main()
{
int array[100],size,i,j,temp,pos;
printf("Enter the size of the array:");
scanf("%d",&size);
printf("\nEnter the elements:");
for(i=0;i<size;i++)
{
scanf("\n%d",&array[i]);
}
for(i=0;i<size;i++)
{
pos=i;
temp=array[i];
for(j=i+1;j<size;j++)
{
if(array[j]<temp)
{
temp=array[j];
pos=j;
}
temp=array[i];
array[i]=array[pos];
array[pos]=temp;
}
}
printf("\nThe sorted array is:");
for(i=0;i<size;i++)
{
printf("\n%d",array[i]);
}
}
(3) Write a program to input 10 numbers and then sort that numbers with the help
of Insertion sort.
Solution
#include<stdio.h>
void main()
{
int array[100],size,i,j,temp;
printf("Enter the size of the array:");
scanf("%d",&size);
printf("\nEnter the elements:");
for(i=0;i<size;i++)
{
scanf("\n%d",&array[i]);
}
for(i=1;i<size;i++)
{
temp=array[i];
j=i-1;
while(j>=0 && temp<=array[j])
{
array[j+1]=array[j];
j--;
}
array[j+1]=temp;
}
printf("\nThe sorted array is:");
for(i=0;i<size;i++)
{
printf("\n%d",array[i]);
}
}
ASSIGNMENT NO. –13

OBJECTIVE:- Implement the following programs with the help of Sorting

(1) Write a program to input 10 numbers and then sort that numbers with the help
of Merge sort.

Solution

#include<stdio.h>

void mergesort(int,int,int array[]);

void merge (int,int,int,int array[]);
void main()
{
int array[100],i,size;
printf("Enter the size of the array:");
scanf("%d",&size);
printf("\nEnter the list:");
for(i=0;i<size;i++)
{
scanf("%d",&array[i]);
}
mergesort(0,size-1,array);
printf("\nThe sorted list is:");
for(i=0;i<size;i++)
{
printf("\n%d",array[i]);
}
}
void mergesort(int lb,int ub, int array[])
{
int mid;
if(lb<ub)
{
mid=(lb+ub)/2;
mergesort(lb,mid,array);
mergesort(mid+1,ub,array);
merge(lb,mid+1,ub,array);
}
}
void merge(int lb,int mid,int ub,int array[])
{
int mergeList[20],ptr1, ptr2,ptr3;
int i;
ptr1=lb;
ptr2=mid;
ptr3=lb;
while((ptr1<mid)&&(ptr2<=ub))
{
if(array[ptr1]<=array[ptr2])
{
mergeList[ptr3]=array[ptr1];
ptr1++;
ptr3++;
}
else
{
mergeList[ptr3]=array[ptr2];
ptr2++;
ptr3++;
}
}
while(ptr1<mid)
{
mergeList[ptr3]=array[ptr1];
ptr1++;
ptr3++;
}
while(ptr2<=ub)
{
mergeList[ptr3]=array[ptr2];
ptr2++;
ptr3++;
}
for(i=lb;i<ptr3;i++)
{
array[i]=mergeList[i];
}
}
(2) Write a program to input 10 numbers and then sort that numbers with the help
of Heap sort.

Solution
#include <stdio.h>
#include <stdlib.h>
#define lchild(j) ((2 * j) + 1)

void processHeap(int *data, int i, int n) {

int mchild, temp, j;
for (temp = data[i]; lchild(i) < n; i = mchild) {
mchild = lchild(i);

if (mchild != n-1 && data[mchild] < data[mchild+1])

mchild++;
if (temp < data[mchild])
data[i] = data[mchild];
else
break;
}
data[i] = temp;
}
void heapSort(int *data, int n) {
int i, temp, j;
for (i = n/2; i >= 0; i--) {
processHeap(data, i, n);
}
for (i = n-1; i > 0; i--) {
temp = data[0];
data[0] = data[i];
data[i] = temp;
processHeap(data, 0, i);
}
}
int main() {
int n, i, *data;
printf("Enter your no of entries:");
scanf("%d", &n);
data = (int *)malloc(sizeof (int) * n);
/* input data from the user */
for (i = 0; i < n; i++)
scanf("%d", &data[i]);
heapSort(data, n);
printf("Data after sorting:\n");
for (i = 0; i < n; i++)
printf("%3d ", data[i]);
printf("\n");
return 0;
}
ASSIGNMENT NO. –14

OBJECTIVE:- Application of Data Structure in C based projects.

Q1. Application of Data Structure in Project “Calendar Program”

Program:

#include<stdio.h>
#include<string.h>
#include<conio.h>
int getNumberOfDays(int month,int year)
{
switch(month)
{
case 1 : return(31);
case 2 : if(year%4==0)
return(29);
else
return(28);
case 3 : return(31);
case 4 : return(30);
case 5 : return(31);
case 6 : return(30);
case 7 : return(31);
case 8 : return(31);
case 9 : return(30);
case 10: return(31);
case 11: return(30);
case 12: return(31);
default: return(-1);
}
}
char *getName(int odd)
{
switch(odd)
{
case 0 :return("Sunday");
case 1 :return("Monday");
case 2 :return("Tuesday");
case 3 :return("Wednesday");
case 4 :return("Thursday");
case 5 :return("Friday");
case 6 :return("Saturday");
default:return("Error in getName() module.Invalid argument
passed");
}
}
int getOddNumber(int day,int mon,int year)
{
int res=0,t1,t2,y=year;
year = year-1600;
while(year>=100)
{
res=res+5;
year=year-100;
}
res=(res%7);
t1=((year-1)/4);
t2=(year-1)-t1;
t1=(t1*2)+t2;
t1=(t1%7);
res = res+t1;
res=res%7;
t2=0;
for(t1=1;t1<mon;t1++)
{
t2+=getNumberOfDays(t1,y);
}
t2 = t2+day;
t2 = t2%7;
res = res+t2;
res = res%7;
if(y>2000)
res=res+1;
res = res%7;
return res;
}
char *getWeek(int dd,int mm,int yy)
{
int odd;
if(!(mm>=1 && mm<=12))
{
return("Invalid month value");
}
if(!(dd>=1 && dd<=getNumberOfDays(mm,yy)))
{
return("Invalid date");
}
if(yy>=1600)
{
odd = getOddNumber(dd,mm,yy);
odd=odd%7;
return(getName(odd));
}
else
{
return("
Please give year more than 1600");
}
}
void printMonth(int mon,int year,int x,int y)
{
int nod,odd,cnt,d=1,x1=x,y1=y;
if(!(mon>=1 && mon<=12))
{
printf("
INVALID MONTH");
getch();
return;
}
if(!(year>=1600))
{
printf("
INVALID YEAR");
getch();
return;
}
if(x<=0)
x=wherex();
if(y<=0)
y=wherey();
gotoxy(x,y);
textcolor(RED);
cprintf("S");
textcolor(YELLOW);
cprintf(" M T W T F S");
/* 1234567891234567891234567 */
textcolor(7);
cprintf("");
y++;
nod=getNumberOfDays(mon,year);
odd=getOddNumber(d,mon,year);
switch(odd)
{
case 0 : x=x;
cnt=1;
break;
case 1 : x=x+4;
cnt=2;
break;
case 2 : x=x+8;
cnt=3;
break;
case 3 : x=x+12;
cnt=4;
break;
case 4 : x=x+16;
cnt=5;
break;
case 5 : x=x+20;
cnt=6;
break;
case 6 : x=x+24;
cnt=7;
break;
default : printf("

INVALID DATA FROM THE getOddNumber()

MODULE");
return;
}
gotoxy(25,25);
gotoxy(x,y);
printf("%02d",d);
for(d=2;d<=nod;d++)
{
if(cnt%7==0)
{
y++;
cnt=0;
x=x1-4;
}
x = x+4;
cnt++;
gotoxy(x,y);
printf("%02d",d);
}
}
main()
{
char ch='k';
int dd,mm,yy;
while(ch!='0')
{
clrscr();
printf("
1.Know the day");
printf("
2.Print the month");
printf("
0.EXIT");
printf("

ENTER YOUR CHOICE : ");

flushall();
fflush(stdin);
ch=getche();
clrscr();
switch(ch)
{
case '1': printf("Enter date (DD MM YYYY) : ");
scanf("%d %d %d",&dd,&mm,&yy);
printf("
Day is : %s",getWeek(dd,mm,yy));
flushall();
getch();
break;
case '2' : printf("Enter month and year (MM YYYY) : ");
scanf("%d %d",&mm,&yy);
printf("

");
printMonth(mm,yy,-1,-1);
flushall();
getch();
break;
case '0' : exit(0);
}
}
}
ASSIGNMENT NO. –15

OBJECTIVE:- Application of Data Structure in C based projects.

1. Application of Data Structure in Project “Employee Database Project”

Program:

#include <stdio.h>

typedef struct Employee

char fname[20];

char lname[20];

char sub_taken[20];

char last_edu[20];

char join_date[20];

int id;

int age;

float bsal;

}Employee;

int main(void)

int id;

FILE *fp,*ft;

char another,choice;

Employee emp;

char fname[20];

char lname[20];

long int recsize;

fp=fopen("EMP.DAT","rb+");

if(fp==NULL)
{

fp=fopen( "EMP.DAT","wb+");

if(fp==NULL)

printf("

Can't Open File");

exit();

recsize=sizeof(emp);

while(1)

printf("

1.Add Records

2.Delete Records

3.Modify Records

4.List

Records

5.Exit");

printf("

Enter your choice");

fflush(stdin);

scanf("%c",&choice);

switch(choice)

case'1':
fseek(fp,0,SEEK_END);

another='Y';

while(another=='Y'|| another=='y')

printf("Enter the first name,last name,age and basic

salary : ");

scanf("%s %d %f",emp.fname,&emp.age,&emp.bsal);

printf("

Enter joining date,id,last education,subject taken");

scanf("%s %d %s
%s",emp.join_date,&emp.id,emp.last_edu,

emp.sub_taken);

fwrite(&emp,recsize,1,fp);

printf("

Add another Record (Y/N): ");

fflush(stdin);

another=getchar();

break;

case '2':

another='Y';

while(another=='Y'|| another=='y')

printf("

Enter the id of the employee to be deleted : ");

scanf("%d",&id);

ft=fopen("TEMP.DAT","wb");
rewind(fp);

while(fread(&emp,recsize,1,fp)==1)

if(strcmp(emp.id,id)!=0)

fwrite(&emp,recsize,1,ft);

fclose(fp);

fclose(ft);

remove("EMP.DAT");

rename("TEMP.DAT","EMP.DAT");

fp=fopen("EMP.DAT","rb+");

printf("Delete another Record(Y/N): ");

fflush(stdin);

another=getchar();

break;

case '3':

another='Y';

while(another=='Y'|| another=='y')

printf("

Enter name of employee to modify : ");

scanf("%s",emp.fname);

rewind(fp);

while(fread(&emp,recsize,1,fp)==1)

{
if(strcmp(emp.id,id)==0)

printf("

Enter new fname,new lname,age,basic

salary,joining_date,subject taken and last education : ");

scanf("%s%s%d%f%s%s%s",emp.fname,emp.lname,&emp.age,&emp.bsal,emp.join_dat

e,emp.sub_taken,emp.last_edu);

fseek(fp,-recsize,SEEK_CUR);

fwrite(&emp,recsize,1,fp);

break;

printf("

Want to Modify another record(Y/N): ");

fflush(stdin);

another=getchar();

break;

case '4':

rewind(fp);

while(fread(&emp,recsize,1,fp)==1)

printf("

%s %s %d
%g",emp.fname,emp.lname,emp.age,emp.bsal,emp.join_date,emp.last_edu,emp.su

b_taken);

break;

case '5':

fclose(fp);

exit();