Data Structures Lab
Data Structures Lab
Data Structures Lab
List of Experiments:
Exercise 1: Array Manipulation
i) Write a program to reverse an array.
ii) C Programs to implement the Searching Techniques – Linear & Binary Search
iii) C Programs to implement Sorting Techniques – Bubble, Selection and Insertion Sort
Exercise 2: Linked List Implementation
i) Implement a singly linked list and perform insertion and deletion operations.
ii) Develop a program to reverse a linked list iteratively and recursively.
iii) Solve problems involving linked list traversal and manipulation.
Exercise 3: Linked List Applications
i) Create a program to detect and remove duplicates from a linked list.
ii) Implement a linked list to represent polynomials and perform addition.
iii) Implement a double-ended queue (deque) with essential operations.
Exercise 4: Double Linked List Implementation
i) Implement a doubly linked list and perform various operations to understand its
properties and applications.
ii) Implement a circular linked list and perform insertion, deletion, and traversal
Exercise 5: Stack Operations
i) Implement a stack using arrays and linked lists.
ii) Write a program to evaluate a postfix expression using a stack.
iii) Implement a program to check for balanced parentheses using a stack.
Exercise 6: Queue Operations
i) Implement a queue using arrays and linked lists.
ii) Develop a program to simulate a simple printer queue system.
iii) Solve problems involving circular queues.
Exercise 7: Stack and Queue Applications
i) Use a stack to evaluate an infix expression and convert it to postfix.
ii) Create a program to determine whether a given string is a palindrome or not.
iii) Implement a stack or queue to perform comparison and check for symmetry.
Exercise 8: Binary Search Tree
i) Implementing a BST using Linked List.
ii) Traversing of BST.
Exercise 9: Hashing i) Implement a hash table with collision resolution techniques. ii) Write a program to implement
a simple cache using hashing.
Exercise 1: Array Manipulation
i) Write a program to reverse an array.
#include <stdio.h>
int main()
{
int a[100];
int n;
printf("enter size of the array:");
scanf("%d",&n);
readArray(a,n);
reverseArray(a,n);
writeArray(a,n);
return 0;
}
Exercise 1: Array Manipulation
ii) C Programs to implement the Searching Techniques – Linear & Binary Search
A) Linear Search
#include<stdio.h>
void readArray(int *a,int n)
{
int i;
printf("enter %d number of elements:\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
}
int main()
{
int a[1000],n,key,loc;
printf("enter array size:");
scanf("%d",&key);
readArray(a,n);
printf("enter key:");
scanf("%d",&key);
loc=linearSearch(a,n,key);
if(loc)
{
printf("element found at loc=%d\n",loc);
}
else
{
printf("element not found:\n");
}
return 0;
}
B) Binary Search
#include<stdio.h>
int main()
{
int a[1000], n, key, loc;
printf("Enter Array Size:");
scanf("%d", & n);
readArray(a, n);
printf("Enter key:");
scanf("%d", & key);
loc = binarySearch(a, n, key);
if (loc)
{
printf("Element found at loc=%d\n", loc);
}
else
{
printf("Element not found:\n");
}
return 0;
}
Exercise 1: Array Manipulation
iii) C Programs to implement Sorting Techniques – Bubble, Selection and Insertion Sort
A) Bubble
#include <stdio.h>
int main()
{
int a[100];
int n;
printf("enter size of the array:");
scanf("%d",&n);
readArray(a,n);
bubbleSort(a,n);
writeArray(a,n);
return 0;
}
B) Selection
#include<stdio.h>
int main()
{
int a[100];
int n;
printf("enter size of the array:");
scanf("%d",&n);
readArray(a,n);
selectionSort(a,n);
writeArray(a,n);
return 0;
}
C) Insertion Sort
#include<stdio.h>
void readArray(int *a,int n)
{
int i;
printf("enter %d number of elements:",n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
}
void writeArray(int *a,int n)
{
int i;
printf("the given array is:");
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
}
void insertionSort(int *a,int n)
{
int i,j,x,r;
for(i=1;i<=(n-1);i++)
{
x=a[i];
r=i;
while(r!=0 && x<a[r-1])
{
a[r]=a[r-1];
r=r-1;
}
a[r]=x;
}
int main()
{
int a[100];
int n;
printf("enter size of the array:");
scanf("%d",&n);
readArray(a,n);
insertionSort(a,n);
writeArray(a,n);
return 0;
}
Exercise 2: Linked List Implementation
i) Implement a singly linked list and perform insertion and deletion operations.
#include<stdio.h>
#include<stdlib.h>
}
return(head);
}
}
int main()
{
int ch,x,key;
node *head=NULL;
head=sllCreation(head);
while(1)
{
printf("\n........SLL Menu.......\n\n");
printf("Insertion...........1\n");
printf("Deletion............2\n");
printf("Traversal...........3\n");
printf("Exit................4\n");
switch(ch)
{
default: printf("Ivalid Choice. Try again.\n");
break;
case 1: printf("Enter Node Element:");
scanf("%d",&x);
printf("Enter Key Element:");
scanf("%d",&key);
sllInsertion(head,x,key);
break;
case 2: printf("Enter Key Element:");
scanf("%d",&key);
sllDeletion(head,key);
break;
case 3: sllTraversal(head);
break;
case 4: exit(0);
}
}
return 0;
}
Exercise 2: Linked List Implementation
ii) Develop a program to reverse a linked list
#include <stdio.h>
#include <stdlib.h>
return head;
}
int main()
{
node *head = NULL;
printf("Enter elements for the linked list:\n");
head = sllCreation(head);
printf("\nOriginal linked list:\n");
sllTraverse(head);
head = sllReverse(head);
return 0;
}
Exercise 3: Linked List Applications
i) Create a program to detect and remove duplicates from a linked list.
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node* link;
}node;
node* sllCreation(node *head)
{
int x;
node *p,*new;
while(1)
{
printf("Enter Node Element:");
scanf("%d",&x);
if(x==0) break;
new=(node*)malloc(sizeof(node));
new->data=x;
new->link=NULL;
if(head==NULL)
{
head=p=new;
}
else
{
p->link=new;
p=new;
}
}
return(head);
}
void removeDuplicates(node *head)
{
if (head == NULL) return;
int main()
{
node *head = NULL;
head=sllCreation(head);
removeDuplicates(head);
printf("\nReversed linked list\n");
sllTraverse(head);
return 0;
}
Exercise 3: Linked List Applications
ii) Implement a linked list to represent polynomials and perform addition.
#include<stdio.h>
#include<stdlib.h>
typedef struct polynode
{
int coef;
int exp;
struct polynode *link;
}polynode;
int main()
{
polynode *p1=NULL,*p2,*p;
p1=polyCreation(NULL);
p2=polyCreation(NULL);
printf("\nFirst Polynomial:");
polyDisplay(p1);
printf("\nSecond Polynomial:");
polyDisplay(p2);
p=polyAddition(p1,p2);
printf("\nAddition of Two Polynomials:");
polyDisplay(p);
return 0;
}
Exercise 3: Linked List Applications
iii) Implement a double-ended queue (deque) with essential operations.
#include <stdio.h>
#include <stdlib.h>
if (front == NULL)
{
front = new;
rear = new;
}
else
{
front->left = new;
front = new;
}
}
if (rear == NULL)
{
front = new;
rear = new;
}
else
{
rear->right = new;
rear = new;
}
}
void deleteFront()
{
if (front == NULL)
{
printf("Deque is empty, cannot delete from front.\n");
return;
}
node* temp = front;
front = front->right;
if (front != NULL)
{
front->left = NULL;
}
else
{
rear = NULL;
}
free(temp);
}
void deleteRear()
{
if (rear == NULL)
{
printf("Deque is empty, cannot delete from rear.\n");
return;
}
node* temp = rear;
rear = rear->left;
if (rear != NULL)
{
rear->right = NULL;
}
else
{
front = NULL;
}
free(temp);
}
void displayDeque()
{
if (front == NULL)
{
printf("Deque is empty.\n");
return;
}
node* p = front;
while (p != NULL)
{
printf("%d -> ", p->data);
p = p->right;
}
printf("NULL\n");
}
int main()
{
int ch,x;
while(1)
{
printf("\n......Double Ended Queue Menu......\n");
printf("Insert at Front........1\n");
printf("Insert at Rear.........2\n");
printf("Delete at Front........3\n");
printf("Delete at Rear.........4\n");
printf("DQ Display.............5\n");
printf("Exit...................6\n");
printf("Enter Your Choice(1-6):");
scanf("%d",&ch);
switch(ch)
{
default: printf("Invalid Choice, Try Again.\n");
break;
case 1: printf("Enter DQueue Element:");
scanf("%d",&x);
insertFront(x);
break;
case 2: printf("Enter DQueue Element:");
scanf("%d",&x);
insertRear(x);
break;
case 3: deleteFront();
break;
case 4: deleteRear();
break;
case 5: displayDeque();
break;
case 6: exit(0);
}
}
}
Exercise 4: Double Linked List Implementation
i) Implement a doubly linked list and perform various operations to understand its properties and applications.
#include<stdio.h>
#include<stdlib.h>
}
return(head);
}
int main()
{
int ch,x,key;
node *head=NULL;
head=dllCreation(head);
while(1)
{
printf("\n........dll Menu.......\n\n");
printf("Insertion...........1\n");
printf("Deletion............2\n");
printf("Traversal...........3\n");
printf("Exit................4\n");
switch(ch)
{
default: printf("Ivalid Choice. Try again.\n");
break;
case 1: printf("Enter Node Element:");
scanf("%d",&x);
printf("Enter Key Element:");
scanf("%d",&key);
dllInsertion(head,x,key);
break;
case 2: printf("Enter Key Element:");
scanf("%d",&key);
dllDeletion(head,key);
break;
case 3: dllTraversal(head);
break;
case 4: exit(0);
}
}
return 0;
}
Exercise 4: Double Linked List Implementation
ii) Implement a circular linked list and perform insertion, deletion, and traversal
#include <stdio.h>
#include <stdlib.h>
if (*head == NULL)
{
new->link = new;
*head = new;
}
else
{
while (last->link != *head)
{
last = last->link;
}
last->link = new;
new->link = *head;
}
if (p->data == key)
{
while (p->link != *head)
{
p = p->link;
}
if (*head == (*head)->link)
{
free(*head);
*head = NULL;
}
else
{
p->link = (*head)->link;
free(*head);
*head = p->link;
}
printf("Node deleted successfully.\n");
return;
}
previous = *head;
while (p->link != *head && p->data != key)
{
previous = p;
p = p->link;
}
if (p->data == key)
{
previous->link = p->link;
free(p);
printf("Node deleted successfully.\n");
}
else
{
printf("Node with data %d not found.\n", key);
}
}
node *p = head;
printf("Circular Single Linked List: ");
do
{
printf("%d -> ", p->data);
p = p->link;
} while (p != head);
printf("HEAD\n");
}
int main()
{
node *head = NULL;
int ch, x, key;
while (1)
{
printf("\nCircular Single Linked List Menu\n");
printf("Insert..............1\n");
printf("Delete..............2\n");
printf("Traverse............3\n");
printf("Exit................4\n");
printf("Enter your choice: ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter the data to insert: ");
scanf("%d", &x);
insert(&head, x);
break;
case 2:
printf("Enter the data to delete: ");
scanf("%d", &key);
delete(&head, key);
break;
case 3:
traverse(head);
break;
case 4:
printf("Exiting program.\n");
exit(0);
break;
default:
printf("Invalid choice. Please try again.\n");
}
}
return 0;
}
Exercise 5: Stack Operations
i) Implement a stack using arrays and linked lists.
A) Stack using Arrays
#include<stdio.h>
#include<stdlib.h>
#define MAX 5
void push(int *stack, int *top,int x)
{
if(*top>=(MAX)-1)
{
printf("Stack Overflow.\n");
return;
}
printf("top=%d\n",*top);
*top=*top+1;
printf("top=%d\n",*top);
stack[*top]=x;
}
int main()
{
int ch;
int x,top=-1;
int stack[10];
while(1)
{
printf("\n......Stack Menu......\n");
printf("Push........1\n");
printf("Pop.........2\n");
printf("Display.....3\n");
printf("Exit........4\n");
printf("Enter Your Choice(1-4):");
scanf("%d",&ch);
switch(ch)
{
default: printf("Invalid Choice, Try Again.\n");
break;
case 1: printf("Enter Stack Element:");
scanf("%d",&x);
push(stack,&top,x);
break;
case 2: x=pop(stack,&top);
if(x!=-1)
{
printf("Poped Element=%d\n",x);
}
break;
case 3: display(stack,top);
break;
case 4:exit(0);
}
}
}
int main()
{
int ch;
int x;
node* top = NULL;
while (1)
{
printf("\n......Stack Menu......\n");
printf("Push........1\n");
printf("Pop.........2\n");
printf("Display.....3\n");
printf("Exit........4\n");
printf("Enter Your Choice(1-4): ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter Stack Element: ");
scanf("%d", &x);
push(&top, x);
break;
case 2:
x = pop(&top);
if (x != -1)
{
printf("Popped Element = %d\n", x);
}
break;
case 3:
display(top);
break;
case 4:
exit(0);
default:
printf("Invalid Choice, Try Again.\n");
break;
}
}
return 0;
}
Exercise 5: Stack Operations
ii) Write a program to evaluate a postfix expression using a stack.
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX 50
int main()
{
char exp[MAX];
printf("Enter the postfix expression: ");
scanf("%s", exp);
int result = evaluatePostfix(exp);
if (result != -1)
{
printf("Result: %d\n", result);
}
return 0;
}
Exercise 5: Stack Operations
iii) Implement a program to check for balanced parentheses using a stack.
#include <stdio.h>
#include <stdlib.h>
#define MAX 50
int main()
{
char exp[MAX];
printf("Enter expression with parentheses: ");
scanf("%s", exp);
if (areParenthesesBalanced(exp))
{
printf("Parentheses are balanced.\n");
}
else
{
printf("Parentheses are not balanced.\n");
}
return 0;
}
Exercise 6: Queue Operations
i) Implement a queue using arrays and linked lists.
A) queue using arrays.
#include<stdio.h>
#include<stdlib.h>
#define QMAX 5
void ENQUEUE(int *Q, int *front,int *rear,int x)
{
if(*rear==QMAX-1)
{
printf("Queue Overflow.\n");
return;
}
if(*rear==-1)
{
*front=*rear=0;
}
else
{
*rear=*rear+1;
}
Q[*rear]=x;
}
int main()
{
int ch;
int x,front=-1,rear=-1;
int Q[10];
while(1)
{
printf("\n......Queue Menu......\n");
printf("Enqueue........1\n");
printf("Dequeue........2\n");
printf("Display........3\n");
printf("Exit...........4\n");
printf("Enter Your Choice(1-4):");
scanf("%d",&ch);
switch(ch)
{
default: printf("Invalid Choice, Try Again.\n");
break;
case 1: printf("Enter Queue Element:");
scanf("%d",&x);
ENQUEUE(Q,&front,&rear,x);
break;
case 2: x=DEQUEUE(Q,&front,&rear);
if(x!=-1)
{
printf("Poped Element=%d\n",x);
}
break;
case 3: display(Q,front,rear);
break;
case 4:exit(0);
}
}
}
if (rear == NULL)
{
front = rear = newNode;
return;
}
rear->link = newNode;
rear = newNode;
}
int dequeue()
{
if (front == NULL)
return -1;
node* temp = front;
int data = temp->data;
front = front->link;
if (front == NULL)
rear = NULL;
free(temp);
return data;
}
void display()
{
node* temp = front;
if (temp == NULL)
{
printf("Queue is empty.\n");
return;
}
int main()
{
int ch, data;
while (1)
{
printf("\n......Queue Menu......\n");
printf("Enqueue........1\n");
printf("Dequeue........2\n");
printf("Display........3\n");
printf("Exit...........4\n");
printf("Enter Your Choice(1-4): ");
scanf("%d", &ch);
switch (ch)
{
case 1: {
printf("Enter Queue Element: ");
scanf("%d", &data);
enqueue(data);
break;
}
case 2: {
data = dequeue();
if (data != -1)
printf("Dequeued Element: %d\n", data);
else
printf("Queue is empty.\n");
break;
}
case 3: {
display();
break;
}
case 4: {
exit(0);
}
default: {
printf("Invalid Choice, Try Again.\n");
}
}
}
return 0;
}
Exercise 6: Queue Operations
ii) Solve problems involving circular queues.
#include<stdio.h>
#include<stdlib.h>
#define CQMAX 5
void CQENQUEUE(int *CQ, int *front,int *rear,int x)
{
if(*front==(*rear+1)%CQMAX)
{
printf("Circular Queue Overflow.\n");
return;
}
if(*rear==-1)
{
*front=*rear=0;
}
else
{
*rear=(*rear+1)%CQMAX;
}
CQ[*rear]=x;
}
int main()
{
int ch;
int x,front=-1,rear=-1;
int CQ[10];
while(1)
{
printf("\n......Circular Queue Menu......\n");
printf("CQEnqueue........1\n");
printf("CQDequeue........2\n");
printf("CQDisplay........3\n");
printf("Exit...........4\n");
printf("Enter Your Choice(1-4):");
scanf("%d",&ch);
switch(ch)
{
default: printf("Invalid Choice, Try Again.\n");
break;
case 1: printf("Enter CQueue Element:");
scanf("%d",&x);
CQENQUEUE(CQ,&front,&rear,x);
break;
case 2: x=CQDEQUEUE(CQ,&front,&rear);
if(x!=-1)
{
printf("Poped Element=%d\n",x);
}
break;
case 3: display(CQ,front,rear);
break;
case 4:exit(0);
}
}
}
Exercise 7: Stack and Queue Applications
i) Use a stack to evaluate an infix expression and convert it to postfix.
#include <stdio.h>
#define MAX 50
int main()
{
char infix[MAX], postfix[MAX];
printf("Enter infix expression: ");
scanf("%s", infix);
if (infixToPostfix(infix, postfix))
{
printf("Postfix expression: %s\n", postfix);
}
return 0;
}
Exercise 7: Stack and Queue Applications
ii) Create a program to determine whether a given string is a palindrome or not.
/*Exercise 7(ii): Stack Application:Create a program to determine whether a given
string is a palindrome or not.*/
#include <stdio.h>
char pop()
{
if(top == -1)
{
printf("Stack Underflow\n");
}
else
{
return stack[top--];
}
}
while(input_string[i])
{
push(input_string[i]);
i=i+1;
}
i=0;
while(input_string[i])
{
if (input_string[i] != pop())
{
return 0;
}
i=i+1;
}
return 1;
}
int main()
{
char input_string[MAX_SIZE];
printf("Enter a string: ");
scanf("%s", input_string);
if(is_palindrome(input_string))
{
printf("%s is a palindrome.\n", input_string);
}
else
{
printf("%s is not a palindrome.\n", input_string);
}
return 0;
}
Exercise 7: Stack and Queue Applications
iii) Implement a stack or queue to perform comparison and check for symmetry.
#include <stdio.h>
#define MAX 50
typedef struct {
int items[MAX];
int front;
int rear;
} Queue;
if (size % 2 != 0)
{
i++;
}
return isQueueEmpty(&q);
}
int main()
{
int arr[MAX];
int size;
if (checkSymmetry(arr, size))
{
printf("The array is symmetric.\n");
}
else
{
printf("The array is not symmetric.\n");
}
return 0;
}
Exercise 8: Binary Search Tree
i) Implementing a BST using Linked List.
ii) Traversing of BST.
#include<stdio.h>
#include<stdlib.h>
#define TABLE_SIZE 10
int main() {
struct HashTable* hashTable = createHashTable();
return 0;
}
Exercise 9: Hashing
ii) Write a program to implement a simple cache using hashing.
#include <stdio.h>
#include <stdlib.h>
#define CACHE_SIZE 5
struct CacheNode
{
int key;
int value;
struct CacheNode* next;
};
struct Cache
{
struct CacheNode* table[CACHE_SIZE];
};
int main()
{
struct Cache* cache = createCache();
put(cache, 1, 10);
put(cache, 2, 20);
put(cache, 3, 30);
put(cache, 4, 40);
put(cache, 5, 50);
display(cache);
int keyToRetrieve = 3;
int value = get(cache, keyToRetrieve);
if (value != -1)
{
printf("Value for key %d is %d\n", keyToRetrieve, value);
}
else
{
printf("Key %d not found\n", keyToRetrieve);
}
return 0;
}