Data Lab File 1 (AutoRecovered)

DATA STRUCTURES USING C
[CSIT124]
DEPARTMENT
OF
COMPUTER SCIENCE AND ENGINEERING
BACHOLAR OF TECHNOLOGY
IN
COMPUTER SCIENCE AND ENGINEERING
Submitted To: Submitted By:
Dr. ANKUR CHOUDHARY PERNI SRI

HARSHAVARDHAN
Associate Professor
A2305218054
CSE Department, ASET
B.tech(CSE), 3CSE1Y
AMITY SCHOOL OF ENGINEERING AND TECHNOLOGY

AMITY UNIVERSITY, UTTAR PRADESH
NOIDA - 201301
INDEX
alu
tur
Sig
teg
All
me
me
me
me
ax.
No
Ca
Co
No
Da
Da
sig
Ex
Ev
ati
tai
As
Name of Experiment
on
ob
na
de
pe
pe
or
ar
ex
M
ks
nt
nt
nt
nt
of
of
ot
of
of
S.
te
te
ri
ri
n
y
.
1. Mand L 1 WRITE A PROGRAM TO IMPLEMENT ALL THE 15/07/2 22/07/20 1
019 19
atory R OPERATIONS IN ARRAY
Experi (1 A. INSERTION OF AN ELEMENT IN ARRAY
ment 5) B. DELETION OF AN ELEMENT IN ARRAY
C. LINEAR SEARCH
D. BINARY SEARCH
2. 2 WRITE A PROGRAM TO IMPLEMENT SORTING 22/07/2 29/07/20 1
019 19
TECHNIQUES
A. BUBBLE SORTING
B. INSERTION SORTING
C. SELECTION SORTING
D. QUICK SORTING
3. 3 WRITE A PROGRAM TO IMPLEMENT ALL THE 29/07/2 05/08/20 1
019 19
OPERATIONS IN STACK
A. PUSH OPERATION
B. POP OPERATION
C. DISPLAY OPERATION
019 19
OPERATIONS IN QUEUE
A. INSERTION OPERATION
B. DELETION OPERATION
019 19
OPERATIONS IN LINKED STACK
A. PUSH OPERATION
B. POP OPERATION
019 19
OPERATIONS IN LINKED QUEUE
019 19
OPERATIONS IN LINKED LIST
A. INSERTION AT BEGINNING
B. INSERTION AT END
C. DISPLAY AT BEGINNING
D. DELETION AT END
E. DISPLAY OPERATION
019 19
OPERATIONS IN DOUBLY LINKED LIST
A. INSERTION AT BEGINNING
B. INSERTION AT END
C. DISPLAY AT BEGINNING
D. DELETION AT END
E. DISPLAY OPERATION
019 19
OPERATIONS IN BINARY SEARCH TREE
A. INSERTION 23/10/2
019
B. INSERTION
C. INORDER, PREORDER, POSTORDER TRAVERSAL
D. FIND SMALLEST, LARGEST, TOTAL NODES IN
TREE
10. 1 WRITE A PROGRAM TO IMPLEMENT GRAPH 30/09/2 21/10/20 1
019 19
0 TRAVERSAL ALGORITHM 14/10/2
A. DEPTH FIRST SEARCH 019
B. BREADTH FIRST SEARCH

11. Open P 21/10/2 04/11/20 5
019 19
Ended R
experi (5)
ment
12. Viva Vi 04/11/2 04/11/20 5
019 19
va
(5)
Experiment 1: Implementing Operations on an Array.
A: Insertion of an element in an Array:-
#include <stdio.h>
#define MAX_SIZE 100
int main()
{
int arr[MAX_SIZE];
int i, size, num, pos;
printf("Enter size of the array : ");

scanf("%d", &size);
printf("Enter elements in array : ");

for(i=0; i<size; i++)
{
scanf("%d", &arr[i]);
}
printf("Enter element to insert : ");
scanf("%d", &num);
printf("Enter the element position : ");
scanf("%d", &pos);
if(pos > size+1 || pos <= 0)

{
printf("Invalid position! Please enter position between 1 to %d", size);
}
else
{
for(i=size; i>=pos; i--)

{
arr[i] = arr[i-1];
}
arr[pos-1] = num;
size++;
printf("Array elements after insertion : ");
for(i=0; i<size; i++)
{
printf("%d\t", arr[i]);
}
}
return 0;
}
Output:-
B: Deletion of an element in an Array:-
#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:\n");
for (c = 0; c < n - 1; c++)

printf("%d\n", array[c]);
}
return 0;
}
Output:-
C: Linear search in an Array:-
#include <stdio.h>
int main()
{
int array[100], search, c, n;
printf("Enter number of elements in array\n");

scanf("%d", &n);
printf("Enter %d integer(s)\n", n);
for (c = 0; c < n; c++)

printf("Enter a number to search\n");

scanf("%d", &search);
for (c = 0; c < n; c++)

{
if (array[c] == search)
{
printf("%d is present at location %d.\n", search, c+1);
break;
}
}
if (c == n)
printf("%d isn't present in the array.\n", search);
return 0;
}
Output:-
D: Binary search in an Array:-
#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 isn't present in the list.\n", search);
return 0; }
Output:-
Internal Assessment (Mandatory Experiment) Sheet for Lab

Experiment Department of Computer Science & Engineering
Amity University, Noida (UP)
Programme Btech(cse) Course Name
ddahd
Course Code CSIT124 Semester 3
Student Name Harsha Enrollment No. A2305218054
Marking Criteria
Criteria Total Marks Marks Comments
Obtained
Concept (A) 2
Implementation (B) 2
Performance (C) 2
Total 6
Experiment 2: Implementing Sorting Techniques
A: Bubble Sorting:-
C Programme:- #include <stdio.h>
int main()
{
int array[100], n, c, d, swap;

scanf("%d", &n);
for (c = 0; c < n; c++)

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

{
for (d = 0 ; d < n - c - 1; d++)
{
if (array[d] > array[d+1])
{
swap = array[d];
array[d] = array[d+1];
array[d+1] = swap;
}
}
}
printf("Sorted list in ascending order:\n");
for (c = 0; c < n; c++)

return 0;
}
Output:-
B: Insertion Sorting:-
C Programme:-
#include <stdio.h>
int main()
{
int n, array[1000], c, d, t;

scanf("%d", &n);
for (c = 0; c < n; c++)

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

d = c;
while ( d > 0 && array[d-1] > array[d]) {

t = array[d];
array[d] = array[d-1];
array[d-1] = t;
d--;
}
}
for (c = 0; c <= n - 1; c++) {

}
return 0;
}
Output:-
C: Selection sorting:-
C Programme:-
#include <stdio.h>
int main()
{
int array[100], n, c, d, position, swap;

scanf("%d", &n);
for (c = 0; c < n; c++)

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

{
position = c;
for (d = c + 1; d < n; d++)

{
if (array[position] > array[d])
position = d;
}
if (position != c)
{
swap = array[c];
array[c] = array[position];
array[position] = swap;
}
}
for (c = 0; c < n; c++)

return 0;
}
Output :
D: Quick Sorting:-
#include<stdio.h>
#include<conio.h>
#define MAX_SIZE 5
void quick_sort(int, int);

int arr_sort[MAX_SIZE];
int main() {
int i;
printf("Simple Quick Sort Example");

printf("\nEnter %d Elements for Sorting\n", MAX_SIZE);
for (i = 0; i < MAX_SIZE; i++)
scanf("%d", &arr_sort[i]);
printf("\nYour Data :");

for (i = 0; i < MAX_SIZE; i++) {
printf("\t%d", arr_sort[i]);
}
quick_sort(0, MAX_SIZE - 1);
printf("\n\nSorted Data :");

for (i = 0; i < MAX_SIZE; i++) {
printf("\t%d", arr_sort[i]);
}
getch();
void quick_sort(int f, int l) {

int i, j, t, p = 0;
if (f < l) {
p = f;
i = f;
j = l;
while (i < j) {
while (arr_sort[i] <= arr_sort[p] && i < l)
i++;
while (arr_sort[j] > arr_sort[p])
j--;
if (i < j) {
t = arr_sort[i];
arr_sort[i] = arr_sort[j];
arr_sort[j] = t;
}
}
t = arr_sort[p];
arr_sort[p] = arr_sort[j];
arr_sort[j] = t;
quick_sort(f, j - 1);
quick_sort(j + 1, l);
}
}
Output:-

Programme BTECH(cse) Course Name
Student Name HARSHA Enrollment No. A2305218054
Marking Criteria
Obtained
Concept (A) 2
Performance (C) 2
Total 6
Experiment 3: Implementing the following operations in a stack
A: Push Operation.
B: Pop Operation.
C: Display Operation
#include<stdio.h>
int stack[100],choice,n,top,x,i;
void push(void);
void pop(void);
void display(void);
int main()
{
//clrscr();
top=-1;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t--------------------------------");
printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT");
do
{
printf("\n Enter the Choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("\n\t EXIT POINT ");
break;
}
default:
{
printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");
}
}
}
while(choice!=4);
return 0;
}
void push()
{
if(top>=n-1)
{
printf("\n\tSTACK is over flow");
}
else
{
printf(" Enter a value to be pushed:");
scanf("%d",&x);
top++;
stack[top]=x;
}
}
void pop()
{
if(top<=-1)
{
printf("\n\t Stack is under flow");
}
else
{
printf("\n\t The popped elements is %d",stack[top]);
top--;
}
}
void display()
{
if(top>=0)
{
printf("\n The elements in STACK \n");
for(i=top; i>=0; i--)
printf("\n%d",stack[i]);
printf("\n Press Next Choice");
}
else
{
printf("\n The STACK is empty");
}
Output:-

Marking Criteria
Obtained
Concept (A) 2
Performance (C) 2
Total 6
Experiment 4: Implementing the following operations in a queue.
A: Insertion Operation.
B: Deletion Operation.
C: Display Operation.
#include <stdio.h>
#define MAX 50
void insert();
void delete();
void display();
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("4.Quit \n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Wrong choice \n");
}
}
}
void insert()
{
int add_item;
if (rear == MAX - 1)
printf("Queue Overflow \n");
else
{
if (front == - 1)
front = 0;
printf("Inset the element in queue : ");
scanf("%d", &add_item);
rear = rear + 1;
queue_array[rear] = add_item;
}
}
void 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;
}
}
void 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");
}
}
Output:-

Marking Criteria
Obtained
Concept (A) 2
Performance (C) 2
Total 6
Experiment 5: Implementing following operations in a linked stack
A: Push Operation.
B: Pop Operation.
C: Display Operation.
#include<stdio.h>
#include<conio.h>
struct Node
{
int data;
struct Node *next;
}*top = NULL;
void push(int);
void pop();
void display();
void main()
{
int choice, value;
while(1){
printf("\n****** MENU ******\n");
printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d", &value);
push(value);
break;
case 2: pop(); break;
case 3: display(); break;
case 4: exit(0);
default: printf("\nWrong selection!!! Please try again!!!\n");
}
}
}
void push(int value)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if(top == NULL)
newNode->next = NULL;
else
newNode->next = top;
top = newNode;
printf("\nInsertion is Success!!!\n");
}
void pop()
{
if(top == NULL)
printf("\nStack is Empty!!!\n");
else{
struct Node *temp = top;
printf("\nDeleted element: %d", temp->data);
top = temp->next;
free(temp);
}
}
void display()
{
if(top == NULL)
printf("\nStack is Empty!!!\n");
else{
struct Node *temp = top;
while(temp->next != NULL){
printf("%d--->",temp->data);
temp = temp -> next;
}
printf("%d--->NULL",temp->data);
}
}
Output:-
Marking Criteria
Obtained
Concept (A) 2
Performance (C) 2
Total 6
6 WRITE A PROGRAM TO IMPLEMENT ALL THE OPERATIONS IN LINKED QUEUE
#include <stdio.h>
#include <stdlib.h>
struct node
{
int info;
struct node *ptr;
}*front,*rear,*temp,*front1;
void enq(int data);
void deq();
void display();
int count = 0;
void main()
{
int no, ch, e;
printf("\n 1 - Enque");
printf("\n 2 - Deque");
printf("\n 4 - Exit");
printf("\n 3 - Display");
while (1)
{
printf("\n Enter choice : ");
scanf("%d", &ch);
switch (ch) {
case 1: printf("Enter data : ");
scanf("%d", &no);
enq(no);
break;
case 2: deq();
break;
case 3: display();
break;
case 4: exit(0);
default: printf("Wrong choice, Please enter correct choice ");
break;
}
}
}
void enq(int data)
{
if (rear == NULL)
{
rear = (struct node *)malloc(sizeof(struct node));
rear->ptr = NULL;
rear->info = data;
front = rear;
}
else
{
temp=(struct node *)malloc(sizeof(struct node));
rear->ptr = temp;
temp->info = data;
temp->ptr = NULL;
rear = temp;
}
count++;
}
void display()
{ front1 = front;
if ((front1 == NULL) && (rear == NULL))
{
printf("Queue is empty");
return;
}
while (front1 != rear)
{
printf("%d ", front1->info);
front1 = front1->ptr;
}
if (front1 == rear)
printf("%d", front1->info);
}
void deq()
{
front1 = front;
if (front1 == NULL)
{
printf("\n Error: Trying to display elements from empty queue");
return;
}
else
if (front1->ptr != NULL)
{
front1 = front1->ptr;
printf("\n Dequed value : %d", front->info);
free(front);
front = front1;
}
else
{
printf("\n Dequed value : %d", front->info);
free(front);
front = NULL;
rear = NULL; }
count--;
}
void empty()
{
if ((front == NULL) && (rear == NULL))
printf("\n Queue empty");
else
printf("Queue not empty");
}

Marking Criteria
Obtained
Concept (A) 2
Performance (C) 2
Total 6
Write a program to implement all the operations in Linked List
A. Insertion at beginning
7)
B. insertion at end
C. Display at beginning
D. Deletion at end
E. Display Operation
#include<stdio.h>
#include<conio.h>
struct node
{
int data;
struct node *next;
}*start=NULL,*q,*t;
int main()
{
int ch;
void insert_beg();
void insert_end();
void display();
void delete_beg();
void delete_end();
while(1)
{
printf("\n\n---- Singly Linked List Menu ----");
printf("\n1.Insert\n2.Display\n3.Delete\n4.Exit\n\n");
printf("Enter your choice(1-4):");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\n---- Insert Menu ----");
printf("\n1.Insert at beginning\n2.Insert at end\n3.Exit");
printf("\n\nEnter your choice(1-3):");
scanf("%d",&ch);
switch(ch)
{
case 1: insert_beg();
break;
case 2: insert_end();
break;
case 3: exit(0);
default: printf("Wrong Choice!!");
}
break;
case 2: display();
break;
case 3: printf("\n---- Delete Menu ----");
printf("\n1.Delete from beginning\n2.Delete from end\n3.Exit");
printf("\n\nEnter your choice(1-3):");
scanf("%d",&ch);
switch(ch)
{
case 1: delete_beg();
break;
case 2: delete_end();
break;
case 3: exit(0);
}
break;
case 4: exit(0);
}
}
return 0;
}
void insert_beg()
{
int num;
t=(struct node*)malloc(sizeof(struct node));
printf("Enter data:");
scanf("%d",&num);
t->data=num;
if(start==NULL)
{
t->next=NULL;
start=t;
}
else
{
t->next=start;
start=t;
}
}
void insert_end()
{
int num;
t=(struct node*)malloc(sizeof(struct node));
printf("Enter data:");
scanf("%d",&num);
t->data=num;
t->next=NULL;
if(start==NULL)
{
start=t;
}
else
{
q=start;
while(q->next!=NULL)
q=q->next;
q->next=t;
}
}
void display()
{
if(start==NULL)
{
printf("List is empty!!");
}
else
{
q=start;
printf("The linked list is:\n");
while(q!=NULL)
{
printf("%d->",q->data);
q=q->next;
}
}
}
void delete_beg()
{
A.
if(start==NULL)
{
printf("The list is empty!!");
}
else
{
q=start;
start=start->next;
printf("Deleted element is %d",q->data);
free(q);
}
}
void delete_end()
{
if(start==NULL)
{
printf("The list is empty!!");
}
else
{
q=start;
while(q->next->next!=NULL)
q=q->next;
t=q->next;
q->next=NULL;
printf("Deleted element is %d",t->data);
free(t);
}

Marking Criteria
Obtained
Concept (A) 2
Performance (C) 2
Total 6
Write a program to implement all the operations in Doubly Linked List
8 A. Insertion at beginning
B. insertion at end
C. Display at beginning
D. Deletion at end
E. Display Operation
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void insertAtBeginning(int);
void insertAtEnd(int);
void deleteBeginning();
void deleteEnd();
void display();
struct Node
{
int data;
struct Node *previous, *next;
}*head = NULL;
void main()
{
int choice1, choice2, value, location;
while(1)
{
printf("\n*********** MENU *************\n");
printf("1. Insert\n2. Delete\n3. Display\n4. Exit\nEnter your choice: ");
scanf("%d",&choice1);
switch(choice1)
{
case 1: printf("Enter the value to be inserted: ");
scanf("%d",&value);
while(1)
{
printf("\nSelect from the following Inserting options\n");
printf("1. At Beginning\n2. At End\n3. Cancel\nEnter your choice: ");
switch(choice2)
{
case 1: insertAtBeginning(value);
break;
case 2: insertAtEnd(value);
break;
case 3: goto EndSwitch;
default: printf("\nPlease select correct Inserting option!!!\n");
}
}
case 2: while(1)
{
printf("\nSelect from the following Deleting options\n");
printf("1. At Beginning\n2. At End\n3. Cancel\nEnter your choice: ");
switch(choice2)
{
case 1: deleteBeginning();
break;
case 2: deleteEnd();
break;
case 3: goto EndSwitch;
default: printf("\nPlease select correct Deleting option!!!\n");
}
}
EndSwitch: break;
case 3: display();
break;
case 4: exit(0);
default: printf("\nPlease select correct option!!!");
}
}
}
void insertAtBeginning(int value)

{
newNode -> data = value;
newNode -> previous = NULL;
if(head == NULL)
{
newNode -> next = NULL;
head = newNode;
}
else
{
newNode -> next = head;
head = newNode;
}
printf("\nInsertion success!!!");
}
void insertAtEnd(int value)
{
newNode -> data = value;
newNode -> next = NULL;
if(head == NULL)
{
newNode -> previous = NULL;
head = newNode;
}
else
{
struct Node *temp = head;
while(temp -> next != NULL)
temp -> next = newNode;
newNode -> previous = temp;
}
printf("\nInsertion success!!!");
}
void deleteBeginning()
{
if(head == NULL)
printf("List is Empty!!! Deletion not possible!!!");
else
{
if(temp -> previous == temp -> next)
{
head = NULL;
free(temp);
}
else{
head = temp -> next;
head -> previous = NULL;
free(temp);
}
printf("\nDeletion success!!!");
}
}
void deleteEnd()
{
if(head == NULL)
printf("List is Empty!!! Deletion not possible!!!");
else
{
if(temp -> previous == temp -> next)
{
head = NULL;
free(temp);
}
else{
temp -> previous -> next = NULL;
free(temp);
}
printf("\nDeletion success!!!");
}
}
void display()
{
if(head == NULL)
printf("\nList is Empty!!!");
else
{
printf("\nList elements are: \n");
printf("NULL <--- ");
{
printf("%d <===> ",temp -> data);
}
printf("%d ---> NULL", temp -> data);
}
Marking Criteria
Obtained
Concept (A) 2
} Performance (C) 2
Total 6
9 WRITE A PROGRAM TO IMPLEMENT ALL THE OPERATIONS IN BINARY SEARCH TREE
A. INSERTION
B. DELERION
C. INORDER, PREORDER, POSTORDER TRAVERSAL
D. FIND SMALLEST, LARGEST, TOTAL NODES IN TREE
#include <stdio.h>
#include <stdlib.h>
struct btnode
{
int value;
struct btnode *l;
struct btnode *r;
}*root = NULL, *temp = NULL, *t2, *t1;
void delete1();
void insert();
void delete();
void inorder(struct btnode *t);
void create();
void search(struct btnode *t);
void preorder(struct btnode *t);
void postorder(struct btnode *t);
void search1(struct btnode *t,int data);
int smallest(struct btnode *t);
int largest(struct btnode *t);
int flag = 1;
void main()
{
int ch;
printf("\nOPERATIONS ---");
printf("\n1 - Insert an element into tree\n");
printf("2 - Delete an element from the tree\n");
printf("3 - Inorder Traversal\n");
printf("4 - Preorder Traversal\n");
printf("5 - Postorder Traversal\n");
printf("6 - Exit\n");
while(1)
{
printf("\nEnter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
inorder(root);
break;
case 4:
preorder(root);
break;
case 5:
postorder(root);
break;
case 6:
exit(0);
default :
printf("Wrong choice, Please enter correct choice ");
break;
}
}
}
void insert()
{
create();
if (root == NULL)
root = temp;
else
search(root);
}
void create()
{
int data;
printf("Enter data of node to be inserted : ");

scanf("%d", &data);
temp = (struct btnode *)malloc(1*sizeof(struct btnode));
temp->value = data;
temp->l = temp->r = NULL;
}
void search(struct btnode *t)

{
if ((temp->value > t->value) && (t->r != NULL))
search(t->r);
else if ((temp->value > t->value) && (t->r == NULL))
t->r = temp;
else if ((temp->value < t->value) && (t->l != NULL))
search(t->l);
else if ((temp->value < t->value) && (t->l == NULL))
t->l = temp;
}
void inorder(struct btnode *t)

{
if (root == NULL)
{
printf("No elements in a tree to display");
return;
}
if (t->l != NULL)
inorder(t->l);
printf("%d -> ", t->value);
if (t->r != NULL)
inorder(t->r);
}
void delete()
{
int data;
if (root == NULL)
{
printf("No elements in a tree to delete");
return;
}
printf("Enter the data to be deleted : ");
scanf("%d", &data);
t1 = root;
t2 = root;
search1(root, data);
}
void preorder(struct btnode *t)

{
if (root == NULL)
{
printf("No elements in a tree to display");
return;
}
if (t->l != NULL)
preorder(t->l);
if (t->r != NULL)
preorder(t->r);
}
void postorder(struct btnode *t)

{
if (root == NULL)
{
printf("No elements in a tree to display ");
return;
}
if (t->l != NULL)
postorder(t->l);
if (t->r != NULL)
postorder(t->r);
}
void search1(struct btnode *t, int data)

{
if ((data>t->value))
{
t1 = t;
search1(t->r, data);
}
else if ((data < t->value))
{
t1 = t;
search1(t->l, data);
}
else if ((data==t->value))
{
delete1(t);
}
}
void delete1(struct btnode *t)

{
int k;
if ((t->l == NULL) && (t->r == NULL))

{
if (t1->l == t)
{
t1->l = NULL;
}
else
{
t1->r = NULL;
}
t = NULL;
free(t);
return;
}
else if ((t->r == NULL))

{
if (t1 == t)
{
root = t->l;
t1 = root;
}
else if (t1->l == t)
{
t1->l = t->l;
}
else
{
t1->r = t->l;
}
t = NULL;
free(t);
return;
}
else if (t->l == NULL)

{
if (t1 == t)
{
root = t->r;
t1 = root;
}
else if (t1->r == t)
t1->r = t->r;
else
t1->l = t->r;
t == NULL;
free(t);
return;
}
else if ((t->l != NULL) && (t->r != NULL))

{
t2 = root;
if (t->r != NULL)
{
k = smallest(t->r);
flag = 1;
}
else
{
k =largest(t->l);
flag = 2;
}
search1(root, k);
t->value = k;
}
int smallest(struct btnode *t)

{
t2 = t;
if (t->l != NULL)
{
t2 = t;
return(smallest(t->l));
}
else
return (t->value);
}
int largest(struct btnode *t)

{
if (t->r != NULL)
{
t2 = t;
return(largest(t->r));
}
else
return(t->value);
}

Marking Criteria
Obtained
Concept (A) 2
Performance (C) 2
Total 6
10 WRITE A PROGRAM TO IMPLEMENT GRAPH TRAVERSAL ALGORITHM
A. DEPTH FIRST SEARCH
B. BREADTH FIRST SEARCH
B)
#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;
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");
}
A)
#include<stdio.h>
#include<conio.h>
int a[20][20],reach[20],n;
void dfs(int v) {
int i;
reach[v]=1;
for (i=1;i<=n;i++)
if(a[v][i] && !reach[i]) {
printf("\n %d->%d",v,i);
dfs(i);
}
}
int main() {
int i,j,count=0;
printf("\n Enter number of vertices:");

scanf("%d",&n);
for (i=1;i<=n;i++) {
reach[i]=0;
for (j=1;j<=n;j++)
a[i][j]=0;
}
printf("\n Enter the adjacency matrix:\n");
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
scanf("%d",&a[i][j]);
dfs(1);
printf("\n");
for (i=1;i<=n;i++) {
if(reach[i])
count++;
}
if(count==n)
printf("\n Graph is connected"); else
printf("\n Graph is not connected");
}

Marking Criteria
Obtained
Concept (A) 2
Performance (C) 2
Total 6

Data Lab File 1 (AutoRecovered)

Uploaded by

Copyright:

Available Formats

Data Lab File 1 (AutoRecovered)

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Data Lab File 1 (AutoRecovered)

Uploaded by

Copyright:

Available Formats

DATA STRUCTURES USING C

Submitted To: Submitted By:

Dr. ANKUR CHOUDHARY PERNI SRI

AMITY SCHOOL OF ENGINEERING AND TECHNOLOGY

B. BREADTH FIRST SEARCH

A: Insertion of an element in an Array:-

printf("Enter size of the array : ");

printf("Enter elements in array : ");

if(pos > size+1 || pos <= 0)

for(i=size; i>=pos; i--)

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

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

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

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

if (position >= n+1)

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

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

printf("Enter %d integer(s)\n", n);

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

printf("Enter a number to search\n");

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

int c, first, last, middle, n, search, array[100];

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

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

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

printf("Enter value to find\n");

if (array[middle] < search)

else if (array[middle] == search)

printf("%d found at location %d.\n", search, middle+1);

middle = (first + last)/2; }

if (first > last)

printf("Not found! %d isn't present in the list.\n", search);

Internal Assessment (Mandatory Experiment) Sheet for Lab

C Programme:- #include <stdio.h>

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

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

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

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

printf("Sorted list in ascending order:\n");

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

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

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

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

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

while ( d > 0 && array[d-1] > array[d]) {

printf("Sorted list in ascending order:\n");

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

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

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

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

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

for (d = c + 1; d < n; d++)

printf("Sorted list in ascending order:\n");

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

void quick_sort(int, int);

printf("Simple Quick Sort Example");

printf("\nYour Data :");

quick_sort(0, MAX_SIZE - 1);

printf("\n\nSorted Data :");