LAB PRACTICAL FILE
SESSION: 2023-24
Data Structure Lab
(CIC-255)
II Year, III Sem
Submitted to: Submitted by:
Name: Ms.Megha Kumar Name: Anushka Srivastava
Designation: Assistant Professor(CSE) Enrollment No.09118002722
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
INDEX
S.NO PROGRAM NAME REMA DATE OF DATE OF SIGN.
RKS EXPERIMENT SUBMISSION
1. Write a program to implement linear search
2. Write a program to implement binary search
3. Write a program to implement sparse matrix
4. Write a program to create and display a
linked list
5. Write a program to perform insertion in a
linked list
6. Write a program to perform deletion in a
linked list
7. Write a program to create doubly linked list
8. Write a program to perform push and pop
operation in stack
9. Write a program to implement dynamic
implementation of stack
10. Write a program to perform bubble sort
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
PROGRAM 1
Aim:Write a program to implement linear search
Source Code:
#include<stdio.h>
int main ()
{
int a[10], n, i, key;
printf ("Enter the number of elements:");
scanf ("%d", &n);
printf ("Enter the values:\n ");
for (i = 0; i < n; i++)
{
scanf ("%d", &a[i]);
}
printf ("Enter the elements which you want to searched:");
scanf ("%d", &key);
for (i = 0; i < n; i++)
{
if (a[i] == key)
{
printf ("Element is found at %d location ", i + 1);
break;
}
}
if (i == n)
{
printf ("Element is not found");
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
}
return 0;
}
Output:
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
PROGRAM 2
Aim:Write a program to implement binary search
Source Code:
#include<stdio.h>
int main(){
int a[10],i,key,beg,end,mid,n;
printf("Enter the no. of elements:");
scanf("%d",&n);
printf("Enter the values (sorted way):");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("Enter the element which you want to searched:");
scanf("%d",&key);
beg=0;
end=n-1;
mid=(beg+end)/2;
while(beg<=end){
if(a[mid]==key){
printf("Element is found at %d location",mid+1);
break;}
else if(a[mid]>key){
end=mid-1;}
else{
beg=mid+1;
}
mid=(beg+end)/2;
}
if(beg>end){
printf("Element not found");}
return 0;
}
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
OUTPUT:
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
PROGRAM 3
Aim:Write a program to implement sparse matrix
Source Code:
#include<stdio.h>
int main()
{
int a[10][10],m,n,i,j,count=0;
printf("Enter the no. of rows:");
scanf("%d",&m);
printf("Enter the no. of columns:");
scanf("%d",&n);
printf("Enter the values:");
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
}
}
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(a[i][j]==0){
count++;
}
}
}
if (count>(m*n)/2)
{
printf("____MATRIX IS SPARCE____");
}
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
else
{
printf("____MATRIX IS NOT SPARCE____");
}
return 0;
}
OUTPUT:
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
PROGRAM 4
Aim:Write a program to create and display a linked list
Source Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void displayList(struct Node* head) {
struct Node* current = head;
if (current == NULL) {
printf("Linked List is empty.\n");
return;
}
printf("Linked List: ");
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
int main() {
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
struct Node* head = NULL;
int value;
char choice;
do {
printf("Enter a value for the linked list: ");
scanf("%d", &value);
struct Node* newNode = createNode(value);
if (head == NULL) {
head = newNode;
} else {
struct Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
printf("Do you want to add another value to the linked list? (y/n): ");
scanf(" %c", &choice);
} while (choice == 'y' || choice == 'Y');
displayList(head);
return 0;
}
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
OUTPUT:
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
PROGRAM 5
Aim:Write a program to perform insertion in a linked list
Source Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
struct Node* insertAtBeginning(struct Node* head, int data) {
struct Node* newNode = createNode(data);
if (head == NULL) {
head = newNode;
} else {
newNode->next = head;
head = newNode;
}
return head;
}
void displayList(struct Node* head) {
struct Node* current = head;
if (current == NULL) {
printf("Linked List is empty.\n");
return;
}
printf("Linked List: ");
while (current != NULL) {
printf("%d -> ", current->data);
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
current = current->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
int value;
char choice;
do {
printf("Enter a value to insert into the linked list: ");
scanf("%d", &value);
head = insertAtBeginning(head, value);
printf("Do you want to insert another value into the linked list? (y/n): ");
scanf(" %c", &choice);
} while (choice == 'y' || choice == 'Y');
displayList(head);
return 0;
}
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
OUTPUT:
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
PROGRAM 6
Aim:Write a program to perform deletion in a linked list
Source Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
struct Node* insertAtBeginning(struct Node* head, int data) {
struct Node* newNode = createNode(data);
if (head == NULL) {
head = newNode;
} else {
newNode->next = head;
head = newNode;
}
return head;
}
struct Node* deleteNode(struct Node* head, int value) {
struct Node* current = head;
struct Node* prev = NULL;
if (current != NULL && current->data == value) {
head = current->next;
free(current);
return head;
}
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
while (current != NULL && current->data != value) {
prev = current;
current = current->next;
}
if (current == NULL) {
printf("Value not found in the linked list.\n");
return head;
}
prev->next = current->next;
free(current);
return head;
}
void displayList(struct Node* head) {
struct Node* current = head;
if (current == NULL) {
printf("Linked List is empty.\n");
return;
}
printf("Linked List: ");
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
int value;
char choice;
do {
printf("Enter a value to insert into the linked list: ");
scanf("%d", &value);
head = insertAtBeginning(head, value);
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
printf("Do you want to insert another value into the linked list? (y/n): ");
scanf(" %c", &choice);
} while (choice == 'y' || choice == 'Y');
printf("\n");
displayList(head);
printf("\nEnter a value to delete from the linked list: ");
scanf("%d", &value);
head = deleteNode(head, value);
printf("\nUpdated ");
displayList(head);
return 0;
}
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
OUTPUT:
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
PROGRAM 7
Aim:Write a program to create doubly linked list
Source Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
struct Node* insertAtEnd(struct Node* head, int data) {
struct Node* newNode = createNode(data);
if (head == NULL) {
head = newNode;
} else {
struct Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
return head;
}
void displayForward(struct Node* head) {
struct Node* current = head;
if (current == NULL) {
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
printf("Doubly Linked List is empty.\n");
return;
}
printf("Doubly Linked List (Forward): ");
while (current != NULL) {
printf("%d <-> ", current->data);
current = current->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
int value;
char choice;
do {
printf("Enter a value to insert into the doubly linked list: ");
scanf("%d", &value);
head = insertAtEnd(head, value);
printf("Do you want to insert another value into the doubly linked list? (y/n): ");
scanf(" %c", &choice);
} while (choice == 'y' || choice == 'Y');
printf("\n");
displayForward(head);
return 0;
}
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
OUTPUT:
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
PROGRAM 8
Aim:Write a program to perform push and pop operation in stack
Source Code:
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct Stack {
int items[MAX_SIZE];
int top;
};
void initializeStack(struct Stack* stack) {
stack->top = -1;
}
int isFull(struct Stack* stack) {
return stack->top == MAX_SIZE - 1;
}
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
void push(struct Stack* stack, int value) {
if (isFull(stack)) {
printf("Stack Overflow: Cannot push element, stack is full.\n");
} else {
stack->items[++stack->top] = value;
printf("Pushed %d into the stack.\n", value);
}
}
int pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack Underflow: Cannot pop element, stack is empty.\n");
return -1;
} else {
int popped = stack->items[stack->top--];
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
printf("Popped %d from the stack.\n", popped);
return popped;
}
}
int main() {
struct Stack stack;
initializeStack(&stack);
char choice;
int value;
do {
printf("\nEnter 'p' to push, 'o' to pop, or 'q' to quit: ");
scanf(" %c", &choice);
switch (choice) {
case 'p':
printf("Enter a value to push: ");
scanf("%d", &value);
push(&stack, value);
break;
case 'o':
value = pop(&stack);
if (value != -1) {
printf("Popped element: %d\n", value);
}
break;
case 'q':
printf("Exiting the program.\n");
break;
default:
printf("Invalid choice! Please enter 'p', 'o', or 'q'.\n");
}
} while (choice != 'q');
return 0;
}
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
OUTPUT:
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
PROGRAM 9
Aim:Write a program to implement dynamic implementation of stack
Source Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Stack {
struct Node* top;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(EXIT_FAILURE);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void initializeStack(struct Stack* stack) {
stack->top = NULL;
}
int isEmpty(struct Stack* stack) {
return stack->top == NULL;
}
void push(struct Stack* stack, int value) {
struct Node* newNode = createNode(value);
newNode->next = stack->top;
stack->top = newNode;
printf("Pushed %d into the stack.\n", value);
}
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
int pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack Underflow: Cannot pop element, stack is empty.\n");
return -1;
} else {
struct Node* temp = stack->top;
int popped = temp->data;
stack->top = temp->next;
free(temp);
printf("Popped %d from the stack.\n", popped);
return popped;
}
}
int main() {
struct Stack stack;
initializeStack(&stack);
char choice;
int value;
do {
printf("\nEnter 'p' to push, 'o' to pop, or 'q' to quit: ");
scanf(" %c", &choice);
switch (choice) {
case 'p':
printf("Enter a value to push: ");
scanf("%d", &value);
push(&stack, value);
break;
case 'o':
value = pop(&stack);
if (value != -1) {
printf("Popped element: %d\n", value);
}
break;
case 'q':
printf("Exiting the program.\n");
break;
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
default:
printf("Invalid choice! Please enter 'p', 'o', or 'q'.\n");
}
} while (choice != 'q');
return 0;
}
OUTPUT:
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
PROGRAM 10
Aim:Write a program to perform bubble sort
Source Code:
#include <stdio.h>
void bubbleSort(int arr[], int n) {
int i, j, temp;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[100], n, i;
printf("Enter the number of elements in the array: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
bubbleSort(arr, n);
printf("Sorted array in ascending order: ");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
return 0;
}
OUTPUT:
[Type here]
Department of Computer Science and Engineering
Delhi Technical Campus, Greater Noida
