Scribd
Upload
5 views34 pages

DATA STRUCTURES Lab Exercises

The document contains a series of C programming exercises focused on data structures, including implementations for linear search, binary search, sorting algorithms (bubble, selection, insertion), stack and queue operations using arrays, and linked list operations (singly and doubly linked). Each exercise includes code snippets demonstrating the respective data structure functionality. The document serves as a practical guide for learning and applying fundamental data structure concepts in C programming.

Uploaded by

sindhyashiva
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
5 views34 pages

DATA STRUCTURES Lab Exercises

The document contains a series of C programming exercises focused on data structures, including implementations for linear search, binary search, sorting algorithms (bubble, selection, insertion), stack and queue operations using arrays, and linked list operations (singly and doubly linked). Each exercise includes code snippets demonstrating the respective data structure functionality. The document serves as a practical guide for learning and applying fundamental data structure concepts in C programming.

Uploaded by

sindhyashiva
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

DATA STRUCTURES Lab Exercises

PART A
1. Write a C program to perform linear search

#include <stdio.h>
int main()
{
int a[10], n, key, i, flag = 0;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
printf("Enter element to search: ");
scanf("%d", &key);
for(i = 0; i < n; i++)
{
if(a[i] == key)
{
flag = 1;
break;
}
}
if(flag==1)
{
printf("Element found at position %d\n", i + 1);
}
else
{
printf("Element not found\n");
}
return 0;
}
2. Write a C program to perform binary search

#include <stdio.h>
int main()
{
int a[10], n, key;
int low, high, mid, i;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements in sorted form:\n", n);
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
printf("Enter element to search: ");
scanf("%d", &key);
low = 0;
high = n - 1;
while(low <= high)
{
mid = (low + high) / 2;
if(a[mid] == key)
{
printf("Element found at position %d\n", mid + 1);
return 0;
}
else if(a[mid] < key)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
printf("Element not found\n");
return 0;
}
3. Write a C program to perform bubble sort

#include <stdio.h>
int main()
{
int a[10], n, i, j, temp;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
for(i = 0; i < n - 1; i++)
{
for(j = 0; j < n - i - 1; j++)
{
if(a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
printf("Sorted array:\n");
for(i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
return 0;
}
4. Write a C program to perform selection sort

#include <stdio.h>
int main()
{
int a[10], n, i, j, min, temp;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter elements:\n");
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
for(i = 0; i < n - 1; i++)
{
min = i;
for(j = i + 1; j < n; j++)
{
if(a[j] < a[min])
{
min = j;
}
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
printf("Sorted array:\n");
for(i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
return 0;
}
5. Write a C program to perform insertion sort

#include <stdio.h>
int main()
{
int a[10], n, i, j, key;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter elements:\n");
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
for(i = 1; i < n; i++)
{
key = a[i];
j = i - 1;
while(j >= 0 && a[j] > key)
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
printf("Sorted array:\n");
for(i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
return 0;
}
6. Write a C program to implement stack operations using array

#include <stdio.h>
#define MAXSIZE 5
int stack[MAXSIZE];
int top = -1;
void push(int data)
{
if(top == MAXSIZE - 1)
{
printf("Stack Overflow\n");
}
else
{
top=top+1;
stack[top] = data;
printf("%d pushed into stack\n", data);
}
}
void pop()
{
if(top == -1)
{
printf("Stack Underflow\n");
}
else
{
printf("%d popped from stack\n", stack[top]);
top=top-1;
}
}
void display()
{
int i;
if(top == -1)
{
printf("Stack is empty\n");
}
else
{
printf("Stack elements are:\n");
for(i = top; i >= 0; i--)
{
printf("%d\n", stack[i]);
}
}
}

int main()
{
int choice, data;
while(1)
{
printf("\n--- Stack Operations ---\n");
printf("1. Push\n");
printf("2. Pop\n");
printf("3. Display\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter data to push: ");
scanf("%d", &data);
push(data);
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
return 0;
default:
printf("Invalid choice\n");
}
}
return 0;
}
7. Write a C program to implement queue operations using array

#include <stdio.h>
#define MAXSIZE 5
int queue[MAXSIZE];
int front = -1, rear = -1;
void Enqueue(int data)
{
if(rear == MAXSIZE - 1)
{
printf("Queue Overflow\n");
}
else
{
if(front == -1)
{
front = 0;
}
rear=rear+1;
queue[rear] = data;
printf("%d inserted into queue\n", data);

}
}
void Dequeue()
{
if(front == -1 || front > rear)
{
printf("Queue Underflow\n");
}
else
{
printf("%d deleted from queue\n", queue[front]);
front++;
}
}
void display()
{
int i;
if(front == -1 || front > rear)
{
printf("Queue is empty\n");
}
else
{
printf("Queue elements are:\n");
for(i = front; i <= rear; i++)
{
printf("%d ", queue[i]);
}
printf("\n");
}
}

int main()
{
int choice, data;
while(1) {
printf("\n--- Queue Operations ---\n");
printf("1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Display\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter data to insert: ");
scanf("%d", &data);
Enqueue(data);
break;
case 2:
Dequeue();
break;
case 3:
display();
break;
case 4:
return 0;
default:
printf("Invalid choice\n");
}
}
return 0;
}

PART B

8. Write a C program to perform operations in singly linked list


#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* head = NULL;
void createList(int n)
{
int i, value;
struct Node *newNode, *temp;
if(n <= 0)
{
printf("Invalid number of nodes\n");
return;
}
printf("Enter data for nodes:\n");
for(i = 1; i <= n; i++)
{
newNode = (struct Node*)malloc(sizeof(struct Node));
printf("Enter data for node %d: ", i);
scanf("%d", &value);
newNode->data = value;
newNode->next = NULL;
if(head == NULL)
{
head = newNode;
temp = newNode;
}
else
{
temp->next = newNode;
temp = newNode;
}
}
printf("Linked list created successfully\n");
}
void insertBeginning(int value)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = head;
head = newNode;
printf("%d inserted at beginning\n", value);
}
void insertEnd(int value)
{
struct Node *newNode, *temp;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if(head == NULL)
{
head = newNode;
}
else
{
temp = head;
while(temp->next != NULL)
{
temp = temp->next;
}
temp->next = newNode;
}
printf("%d inserted at end\n", value);
}
void insertMiddle(int value, int position)
{
struct Node *newNode, *temp;
int i;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
temp = head;
for(i = 1; i < position && temp != NULL; i++)
{
temp = temp->next;
}
if(temp == NULL)
{
printf("Invalid position\n");
free(newNode);
}
else
{
newNode->next = temp->next;
temp->next = newNode;

printf("%d inserted at position %d\n", value, position + 1);


}
}
void deleteBeginning()
{
struct Node* temp;
if(head == NULL)
{
printf("List is empty\n");
}
else
{
temp = head;
printf("%d deleted from beginning\n", head->data);
head = head->next;
free(temp);
}
}
void deleteEnd()
{
struct Node *temp, *prev;
if(head == NULL)
{
printf("List is empty\n");
}
else if(head->next == NULL)
{
printf("%d deleted from end\n", head->data);
free(head);
head = NULL;
}
else
{
temp = head;
while(temp->next != NULL)
{
prev = temp;
temp = temp->next;
}
prev->next = NULL;
printf("%d deleted from end\n", temp->data);
free(temp);
}
}
void deleteMiddle(int position)
{
struct Node *temp, *prev = NULL;
int i;
if(head == NULL)
{
printf("List is empty\n");
return;
}
temp = head;
if(position == 1)
{
head = temp->next;
printf("%d deleted from position %d\n", temp->data, position);
free(temp);
return;
}
for(i = 1; i < position && temp != NULL; i++)
{
prev = temp;
temp = temp->next;
}
if(temp == NULL)
{
printf("Invalid position\n");
}
else
{
prev->next = temp->next;

printf("%d deleted from position %d\n", temp->data, position);


free(temp);
}
}
void display()
{
struct Node* temp;
if(head == NULL)
{
printf("List is empty\n");
}
else
{
temp = head;
printf("Linked List:\n");
while(temp != NULL)
{
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
}
int main()
{
int choice, value, position, n;
while(1)
{
printf("\n--- Singly Linked List Operations ---\n");
printf("1. Create List\n");
printf("2. Insert at Beginning\n");
printf("3. Insert at End\n");
printf("4. Insert at Middle\n");
printf("5. Delete from Beginning\n");
printf("6. Delete from End\n");
printf("7. Delete from Middle\n");
printf("8. Display\n");
printf("9. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter number of nodes: ");
scanf("%d", &n);
createList(n);
break;
case 2:
printf("Enter value: ");
scanf("%d", &value);
insertBeginning(value);
break;
case 3:
printf("Enter value: ");
scanf("%d", &value);
insertEnd(value);
break;
case 4:
printf("Enter value: ");
scanf("%d", &value);
printf("Enter position after which to insert: ");
scanf("%d", &position);
insertMiddle(value, position);
break;
case 5:
deleteBeginning();
break;
case 6:
deleteEnd();
break;
case 7:
printf("Enter position to delete: ");
scanf("%d", &position);
deleteMiddle(position);
break;
case 8:
display();
break;
case 9:
return 0;
default:
printf("Invalid choice\n");
}
}

return 0;
}

9. Write a C program to perform operations in doubly linked list

#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node* prev;
struct Node* next;
};
struct Node* head = NULL;
void createList(int n)
{
struct Node *newNode, *temp;
int value, i;
if(n <= 0)
{
printf("Invalid size\n");
return;
}
printf("Enter data for nodes:\n");
for(i = 1; i <= n; i++)
{
newNode = (struct Node*)malloc(sizeof(struct Node));
printf("Enter value for node %d: ", i);
scanf("%d", &value);
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
if(head == NULL)
{
head = newNode;
temp = newNode;
}
else
{
temp->next = newNode;
newNode->prev = temp;
temp = newNode;
}
}
printf("Doubly linked list created successfully\n");
}
void insertBeginning(int value)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct
Node));
newNode->data = value;
newNode->prev = NULL;
newNode->next = head;
if(head != NULL)
{
head->prev = newNode;
}
head = newNode;
printf("%d inserted at beginning\n", value);
}
void insertEnd(int value)
{
struct Node *newNode, *temp;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if(head == NULL)
{
newNode->prev = NULL;
head = newNode;
}
else
{
temp = head;
while(temp->next != NULL)
{
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
printf("%d inserted at end\n", value);
}
void insertMiddle(int value, int position)
{
struct Node *newNode, *temp;
int i;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
temp = head;
for(i = 1; i < position && temp != NULL; i++)
{
temp = temp->next;
}
if(temp == NULL)
{
printf("Invalid position\n");
free(newNode);
}
else
{
newNode->next = temp->next;
newNode->prev = temp;
if(temp->next != NULL)
{
temp->next->prev = newNode;
}
temp->next = newNode;
printf("%d inserted at position %d\n", value, position + 1);
}
}
void deleteBeginning()
{
struct Node* temp;
if(head == NULL)
{
printf("List is empty\n");
return;
}
temp = head;
printf("%d deleted from beginning\n", temp->data);
head = head->next;
if(head != NULL)
{
head->prev = NULL;
}
free(temp);
}
void deleteEnd()
{
struct Node* temp;
if(head == NULL)
{
printf("List is empty\n");
return;
}
temp = head;
if(temp->next == NULL)
{
printf("%d deleted from end\n", temp->data);
free(temp);
head = NULL;
return;
}
while(temp->next != NULL)
{
temp = temp->next;
}
printf("%d deleted from end\n", temp->data);
temp->prev->next = NULL;
free(temp);
}
void deleteMiddle(int position)
{
struct Node *temp;
int i;
if(head == NULL)
{
printf("List is empty\n");
return;
}
temp = head;
if(position == 1)
{
deleteBeginning();
return;
}
for(i = 1; i < position && temp != NULL; i++)
{
temp = temp->next;
}
if(temp == NULL)
{
printf("Invalid position\n");
}
else
{
printf("%d deleted from position %d\n", temp->data, position);
if(temp->next != NULL)
{
temp->next->prev = temp->prev;
}
if(temp->prev != NULL)
{
temp->prev->next = temp->next;
}
free(temp);
}
}
void display()
{
struct Node* temp;
if(head == NULL)
{
printf("List is empty\n");
return;
}
temp = head;
printf("Doubly Linked List (Forward):\n");
while(temp != NULL)
{
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main()
{
int choice, value, position, n;
while(1)
{
printf("\n--- Doubly Linked List Operations ---\n");
printf("1. Create List\n");
printf("2. Insert at Beginning\n");
printf("3. Insert at End\n");
printf("4. Insert at Middle\n");
printf("5. Delete from Beginning\n");
printf("6. Delete from End\n");
printf("7. Delete from Middle\n");
printf("8. Display\n");
printf("9. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter number of nodes: ");
scanf("%d", &n);
createList(n);
break;
case 2:
printf("Enter value: ");
scanf("%d", &value);
insertBeginning(value);
break;
case 3:
printf("Enter value: ");
scanf("%d", &value);
insertEnd(value);
break;
case 4:
printf("Enter value: ");
scanf("%d", &value);
printf("Enter position after which to insert: ");
scanf("%d", &position);
insertMiddle(value, position);
break;
case 5:
deleteBeginning();
break;
case 6:
deleteEnd();
break;
case 7:
printf("Enter position to delete: ");
scanf("%d", &position);
deleteMiddle(position);
break;
case 8:
display();
break;
case 9:
return 0;
default:
printf("Invalid choice\n");
}
}
return 0;
}

10. Write a C program to perform stack operations using linked list

#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node* next;
};
struct Node* top = NULL;
void push(int value)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct
Node));
if(newNode == NULL)
{
printf("Memory allocation failed\n");
return;
}
newNode->data = value;
newNode->next = top;
top = newNode;
printf("%d pushed into stack\n", value);
}
void pop()
{
struct Node* temp;
if(top == NULL)
{
printf("Stack Underflow\n");
}
else
{
temp = top;
printf("%d popped from stack\n", top->data);
top = top->next;
free(temp);
}
}
void peek()
{
if(top == NULL)
{
printf("Stack is empty\n");
}
else
{
printf("Top element is %d\n", top->data);
}
}
void display()
{
struct Node* temp;
if(top == NULL)
{
printf("Stack is empty\n");
}
else
{
temp = top;
printf("Stack elements:\n");
while(temp != NULL)
{
printf("%d\n", temp->data);
temp = temp->next;
}
}
}
int main()
{
int choice, value;
while(1)
{
printf("\n--- Stack using Linked List ---\n");
printf("1. Push\n");
printf("2. Pop\n");
printf("3. Peek\n");
printf("4. Display\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter value: ");
scanf("%d", &value);
push(value);
break;
case 2:
pop();
break;
case 3:
peek();
break;
case 4:
display();
break;
case 5:
return 0;
default:
printf("Invalid choice\n");
}
}
return 0;
}

[Link] a C program to perform queue operations using linked list


#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node* next;
};
struct Node* front = NULL;
struct Node* rear = NULL;
void enqueue(int value)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct
Node));
if(newNode == NULL)
{
printf("Memory allocation failed\n");
return;
}
newNode->data = value;
newNode->next = NULL;
if(front == NULL && rear == NULL)
{
front = rear = newNode;
}
else
{
rear->next = newNode;
rear = newNode;
}
printf("%d inserted into queue\n", value);
}
void dequeue()
{
struct Node* temp;
if(front == NULL)
{
printf("Queue Underflow\n");
return;
}
temp = front;
printf("%d deleted from queue\n", front->data);
front = front->next;
if(front == NULL)
{
rear = NULL;
}
free(temp);
}
void display()
{
struct Node* temp = front;
if(front == NULL)
{
printf("Queue is empty\n");
return;
}
printf("Queue elements:\n");
while(temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
void peek()
{
if(front == NULL)
{
printf("Queue is empty\n");
}
else
{
printf("Front element is %d\n", front->data);
}
}
int main()
{
int choice, value;
while(1)
{
printf("\n--- Queue using Linked List ---\n");
printf("1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Peek\n");
printf("4. Display\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter value: ");
scanf("%d", &value);
enqueue(value);
break;
case 2:
dequeue();
break;
case 3:
peek();
break;
case 4:
display();
break;
case 5:
return 0;
default:
printf("Invalid choice\n");
}
}
return 0;
}

[Link] a C program to perform tree traversals


#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *left, *right;
};
struct Node* createNode(int value)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
struct Node* createTree()
{
int value;
printf("Enter data (-1 for NULL): ");
scanf("%d", &value);
if(value == -1)
{
return NULL;
}
struct Node* root = createNode(value);
printf("Enter left child of %d\n", value);
root->left = createTree();
printf("Enter right child of %d\n", value);
root->right = createTree();
return root;
}
void inorder(struct Node* root)
{
if(root != NULL)
{
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
void preorder(struct Node* root)
{
if(root != NULL)
{
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
void postorder(struct Node* root)
{
if(root != NULL)
{
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}
int main()
{
struct Node* root;
printf("Create Binary Tree:\n");
root = createTree();
printf("\nInorder Traversal: ");
inorder(root);
printf("\nPreorder Traversal: ");
preorder(root);
printf("\nPostorder Traversal: ");
postorder(root);
return 0;
}

You might also like