DATA STRUCTURES LAB

1. Use a recursive function to find the GCD of two numbers.

#include <stdio.h>

int gcd(int a, int b) {

if (b == 0)
return a;
return gcd(b, a % b);
}

int main() {
int num1, num2;
printf("Enter two numbers: ");
scanf("%d %d", &num1, &num2);
printf("GCD of %d and %d is %d\n", num1, num2, gcd(num1, num2));
return 0;
}

2. Use a recursive function to find the Fibonacci series.

#include <stdio.h>

int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n-1) + fibonacci(n-2);
}

int main() {
int n, i;
printf("Enter the number of terms: ");
scanf("%d", &n);
printf("Fibonacci Series: ");
for (i = 0; i < n; i++) {
printf("%d ", fibonacci(i));
}
printf("\n");
return 0;
}

3. Use pointers to find the length of a string and to concatenate two strings.
#include <stdio.h>

int stringLength(char *str) {

int length = 0;
while (*str != '\0') {
length++;
str++;
}
return length;
}
void concatenateStrings(char *str1, char *str2) {
while (*str1 != '\0') {
str1++;
}
while (*str2 != '\0') {
*str1 = *str2;
str1++;
str2++;
}
*str1 = '\0';
}

int main() {
char str1[100], str2[50];
printf("Enter first string: ");
scanf("%s", str1);
printf("Enter second string: ");
scanf("%s", str2);

printf("Length of first string: %d\n", stringLength(str1));

printf("Length of second string: %d\n", stringLength(str2));

concatenateStrings(str1, str2);
printf("Concatenated string: %s\n", str1);

return 0;
}

4. Use pointers to copy a string and extract a substring from a given string.
#include <stdio.h>

void copyString(char *source, char *destination) {

while (*source != '\0') {
*destination = *source;
source++;
destination++;
}
*destination = '\0';
}

void extractSubstring(char *source, char *substring, int start, int length) {

source += start;
while (length > 0 && *source != '\0') {
*substring = *source;
substring++;
source++;
length--;
}
*substring = '\0';
}

int main() {
char source[100], copy[100], substring[50];
int start, length;
 printf("Enter a string: ");
scanf("%s", source);

copyString(source, copy);
printf("Copied string: %s\n", copy);

printf("Enter start index and length for substring: ");

scanf("%d %d", &start, &length);

extractSubstring(source, substring, start, length);

printf("Extracted substring: %s\n", substring);

return 0;
}

5. Write a C program to find the maximum and minimum elements in an array.

#include <stdio.h>

void findMinMax(int arr[], int size, int *min, int *max) {

*min = *max = arr[0];
for (int i = 1; i < size; i++) {
if (arr[i] < *min) {
*min = arr[i];
}
if (arr[i] > *max) {
*max = arr[i];
}
}
}

int main() {
int size, min, max;
printf("Enter the size of the array: ");
scanf("%d", &size);

int arr[size];
printf("Enter %d elements: ", size);
for (int i = 0; i < size; i++) {
scanf("%d", &arr[i]);
}

findMinMax(arr, size, &min, &max);

printf("Minimum element: %d\n", min);
printf("Maximum element: %d\n", max);

return 0;
}

6. Write a C program to delete an integer from an array.

#include <stdio.h>
void deleteElement(int arr[], int *size, int element) {
int i, j, found = 0;
for (i = 0; i < *size; i++) {
if (arr[i] == element) {
found = 1;
for (j = i; j < *size - 1; j++) {
arr[j] = arr[j + 1];
}
(*size)--;
i--;
}
}
if (!found) {
printf("Element %d not found in the array.\n", element);
}
}

int main() {
int size, element;
printf("Enter the size of the array: ");
scanf("%d", &size);

int arr[size];
printf("Enter %d elements: ", size);
for (int i = 0; i < size; i++) {
scanf("%d", &arr[i]);
}

printf("Enter the element to delete: ");

scanf("%d", &element);

deleteElement(arr, &size, element);

printf("Array after deletion: ");

for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");

return 0;
}

7. Write a program to create a linked list and display it.

#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));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

void insertAtEnd(struct Node** head, int data) {

struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}

8. Write a program to sort N numbers using insertion sort.

#include <stdio.h>

void insertionSort(int arr[], int n) {

int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

void printArray(int arr[], int n) {

for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}

int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);

int arr[n];
printf("Enter %d elements: ", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
 printf("Original array: ");
printArray(arr, n);

insertionSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}

9. Write a program to sort N numbers using selection sort.

#include <stdio.h>

void swap(int *xp, int *yp) {

int temp = *xp;
*xp = *yp;
*yp = temp;
}

void selectionSort(int arr[], int n) {

int i, j, min_idx;
for (i = 0; i < n-1; i++) {
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
swap(&arr[min_idx], &arr[i]);
}
}

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);

int arr[n];
printf("Enter %d elements: ", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

printf("Original array: ");

printArray(arr, n);
 selectionSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}

10. Write a program to Insert a node into a singly linked list.

#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));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

void insertAtBeginning(struct Node** head, int data) {

struct Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}

void insertAtEnd(struct Node** head, int data) {

struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}

void insertAfter(struct Node* prevNode, int data) {

if (prevNode == NULL) {
printf("Previous node cannot be NULL");
return;
}
struct Node* newNode = createNode(data);
newNode->next = prevNode->next;
prevNode->next = newNode;
}
void displayList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main() {
struct Node* head = NULL;
int choice, data, position;

while (1) {
printf("\n1. Insert at beginning\n2. Insert at end\n3. Insert after a node\n4.
Display\n5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter data to insert: ");
scanf("%d", &data);
insertAtBeginning(&head, data);
break;
case 2:
printf("Enter data to insert: ");
scanf("%d", &data);
insertAtEnd(&head, data);
break;
case 3:
printf("Enter data to insert: ");
scanf("%d", &data);
printf("Enter position after which to insert: ");
scanf("%d", &position);
struct Node* temp = head;
for (int i = 1; i < position && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf("Position out of range\n");
} else {
insertAfter(temp, data);
}
break;
case 4:
displayList(head);
break;
case 5:
exit(0);
default:
printf("Invalid choice\n");
}
 }

return 0;
}

11 Write a program to delete a node from a singly linked list.

#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));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

void insertAtEnd(struct Node** head, int data) {

struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}

void deleteNode(struct Node** head, int key) {

struct Node* temp = *head;
struct Node* prev = NULL;

if (temp != NULL && temp->data == key) {

*head = temp->next;
free(temp);
return;
}

while (temp != NULL && temp->data != key) {

prev = temp;
temp = temp->next;
}

if (temp == NULL) {
printf("Key not found in the list\n");
return;
 }

prev->next = temp->next;
free(temp);
}

void displayList(struct Node* head) {

struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main() {
struct Node* head = NULL;
int n, data, key;

printf("Enter the number of elements: ");

scanf("%d", &n);

for (int i = 0; i < n; i++) {

printf("Enter element %d: ", i + 1);
scanf("%d", &data);
insertAtEnd(&head, data);
}

printf("Original list: ");

displayList(head);

printf("Enter the element to delete: ");

scanf("%d", &key);

deleteNode(&head, key);

printf("List after deletion: ");

displayList(head);

return 0;

12. Write a program to implement stack operations using a pointer.

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

#define MAX_SIZE 100

struct Stack {
int* array;
int top;
int capacity;
};

struct Stack* createStack(int capacity) {

struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (int*)malloc(stack->capacity * sizeof(int));
return stack;
}

int isFull(struct Stack* stack) {

return stack->top == stack->capacity - 1;
}

int isEmpty(struct Stack* stack) {

return stack->top == -1;
}

void push(struct Stack* stack, int item) {

if (isFull(stack)) {
printf("Stack Overflow! Cannot push %d\n", item);
return;
}
stack->array[++stack->top] = item;
printf("%d pushed to stack\n", item);
}

int pop(struct Stack* stack) {

if (isEmpty(stack)) {
printf("Stack Underflow! Cannot pop from an empty stack\n");
return -1;
}
return stack->array[stack->top--];
}

int peek(struct Stack* stack) {

if (isEmpty(stack)) {
printf("Stack is empty\n");
return -1;
}
return stack->array[stack->top];
}

void displayStack(struct Stack* stack) {

if (isEmpty(stack)) {
printf("Stack is empty\n");
return;
}
printf("Stack elements: ");
for (int i = stack->top; i >= 0; i--) {
printf("%d ", stack->array[i]);
}
printf("\n");
}
int main() {
struct Stack* stack = createStack(MAX_SIZE);
int choice, item;

while (1) {
printf("\n1. Push\n2. Pop\n3. Peek\n4. Display\n5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter the element to push: ");
scanf("%d", &item);
push(stack, item);
break;
case 2:
item = pop(stack);
if (item != -1) {
printf("Popped item: %d\n", item);
}
break;
case 3:
item = peek(stack);
if (item != -1) {
printf("Top item: %d\n", item);
}
break;
case 4:
displayStack(stack);
break;
case 5:
free(stack->array);
free(stack);
exit(0);
default:
printf("Invalid choice\n");
}
}

return 0;
}

13 Write a program to search an element in an array using linear search.

#include <stdio.h>

int linearSearch(int arr[], int n, int key) {

for (int i = 0; i < n; i++) {
if (arr[i] == key) {
return i;
}
}
return -1;
}
int main() {
int n, key;

printf("Enter the number of elements: ");

scanf("%d", &n);

int arr[n];
printf("Enter %d elements: ", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

printf("Enter the element to search: ");

scanf("%d", &key);

int result = linearSearch(arr, n, key);

if (result == -1) {
printf("Element %d not found in the array.\n", key);
} else {
printf("Element %d found at index %d.\n", key, result);
}

return 0;
}

14. Write a program to implement queue operation.

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

#define MAX_SIZE 100

struct Queue {
int items[MAX_SIZE];
int front;
int rear;
};

void initQueue(struct Queue* q) {

q->front = -1;
q->rear = -1;
}

int isFull(struct Queue* q) {

return (q->rear == MAX_SIZE - 1);
}

int isEmpty(struct Queue* q) {

return (q->front == -1);
}

void enqueue(struct Queue* q, int value) {

if (isFull(q)) {
 printf("Queue is full!\n");
return;
}
if (isEmpty(q)) {
q->front = 0;
}
q->rear++;
q->items[q->rear] = value;
printf("%d enqueued to queue\n", value);
}

int dequeue(struct Queue* q) {

if (isEmpty(q)) {
printf("Queue is empty!\n");
return -1;
}
int item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
q->front = q->rear = -1;
}
return item;
}

void displayQueue(struct Queue* q) {

if (isEmpty(q)) {
printf("Queue is empty\n");
return;
}
printf("Queue elements: ");
for (int i = q->front; i <= q->rear; i++) {
printf("%d ", q->items[i]);
}
printf("\n");
}

int main() {
struct Queue q;
initQueue(&q);

int choice, value;

while (1) {
printf("\n1. Enqueue\n2. Dequeue\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter the value to enqueue: ");
scanf("%d", &value);
enqueue(&q, value);
break;
case 2:
 value = dequeue(&q);
if (value != -1) {
printf("Dequeued value: %d\n", value);
}
break;
case 3:
displayQueue(&q);
break;
case 4:
exit(0);
default:
printf("Invalid choice\n");
}
}

return 0;
}

15. Write a C program to swap two numbers using pointers.

#include <stdio.h>

void swap(int *a, int *b) {

int temp = *a;
*a = *b;
*b = temp;
}

int main() {
int num1, num2;

printf("Enter first number: ");

scanf("%d", &num1);

printf("Enter second number: ");

scanf("%d", &num2);

printf("Before swapping: num1 = %d, num2 = %d\n", num1, num2);

swap(&num1, &num2);

printf("After swapping: num1 = %d, num2 = %d\n", num1, num2);

return 0;
}