Data Structures and Algorithms in C: A Comprehensive Guide

Posted on May 6, 2024 in Computers

Data Structures and Algorithms in C

Searching Algorithms

Linear Search

The linear search algorithm sequentially checks each element in a list until it finds the target value. It’s simple but inefficient for large lists.

C Code for Linear Search

#include #include void main(){ int a[50],i,n,elt,count; clrscr(); printf("\n\tLINEAR SEARCH"); printf("\n\t \n\n"); printf("\n\tEnter the limit:"); scanf("%d",&n); printf("\n\tEnter the elements:"); for(i=0;i

Binary Search

Binary search is a more efficient algorithm for searching sorted lists. It repeatedly divides the search interval in half until the target value is found or the interval is empty.

C Code for Binary Search
#include #include void main() { int a[50],i,j,n,elt,temp,flag=0,low=0,high,mid; clrscr(); printf("\n\tBINARY SEARCH"); printf("\n\t \n\n"); printf("\n\tEnter the limit:"); scanf("%d",&n); printf("\n\tEnter the elements:"); for(i=0;ia[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp;}}} printf("\n\n\tThe sorted array is"); for(i=0;ia[mid]) { low=mid+1; } else { printf("\n\n\tThe element is present"); flag=1; break;}} if(flag==0) { printf("\n\n\tThe element is not present"); } getch(); }

Sorting Algorithms

Bubble Sort

Bubble sort repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

C Code for Bubble Sort
#include #include void main() { int a[50],i,j,n,temp; clrscr(); printf("\n\tBUBBLE SORT"); printf("\n\t \n\n"); printf("\n\tEnter the limit:"); scanf("%d",&n); printf("\n\tEnter the elements:"); for(i=0;ia[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } printf("\n\n\tThe sorted array is"); for(i=0;i

Selection Sort

Selection sort repeatedly finds the minimum element from the unsorted part of the list and puts it at the beginning.

C Code for Selection Sort
#include #include void main() { int a[50],i,n,j,temp; clrscr(); printf("\n\n\t\tSELECTION SORT"); printf("\n\t\t \n\n"); printf("\n\n\tEnter the limit:"); scanf("%d",&n); printf("\n\n\tEnter the elements:"); for(i=0;ia[j]) { temp=a[i]; a[i]=a[j]; a[j]=temp; } } } printf("\n\n\tThe sorted array is:"); for(i=0;i

Insertion Sort

Insertion sort builds the final sorted array one item at a time. It iterates through the list, inserting each element into its correct position in the sorted portion.

C Code for Insertion Sort
#include #include void main() { int a[50],i,n,j,temp; clrscr(); printf("\n\t\tINSERTION SORT\n"); printf("\t\t \n"); printf("\n\n\tEnter the limit:"); scanf("%d",&n); printf("\n\n\tEnter the elements:"); for(i=0;i=0) { a[j+1]=a[j]; j--; } a[j+1]=temp; } printf("\n\n\tThe sorted array is:"); for(i=0;i

Stack

A stack is a LIFO (Last In First Out) data structure. Elements are added and removed from the top of the stack.

C Code for Stack Implementation
#include #include void main() { int st[50],top=-1,k,n,i,si; char ch; clrscr(); printf("\n\tProgram to push ,pop or display an element from a stack"); printf("\n\t \n\n"); printf("\n\tEnter the size of the stack:") ; scanf("%d",&si); do { printf("\n\t\tMENU"); printf("\n\t\t \n"); printf("\n\n\t1.Push\n\n\t2.Pop\n\n\t3.Display\n\n\t4.Exit"); printf("\n\n\tEnter your choice:"); scanf("%d",&n); if(n==1) { if(top==si-1) { printf("\n\tStack is overflow"); } else { printf("\n\tEnter the element to be inserted:"); scanf("%d",&k); top++; st[top]=k; printf("\n\tThe entered element is %d",st[top]); } } else if(n==2) { if(top==-1) { printf("\n\tStack is underflow"); } else { printf("\n\tThe deleted element is %d",st[top]); top--; } } else if(n==3) { if(top==-1) { printf("\n\tStack underflow"); } else { printf("\n\tThe stack is:"); for(i=top;i>=0;i--) { printf("\t\t%d",st[i]); } } } else {   break; } printf("\n\n\tDo you want to continue (Y/N) ?"); scanf(" %c",&ch); } while((ch=='Y')||(ch=='y')); getch(); }

Queue

A queue is a FIFO (First In First Out) data structure. Elements are added to the rear of the queue and removed from the front.

C Code for Queue Implementation
#include #include void main() { int no,i,front=-1,rear=-1,k,queue[50],element,n; char c; clrscr(); printf("\n\n\n\tPROGRAM TO INSERT, DELETE AND DISPLAY ELEMENTS TO QUEUE"); printf("\n\t \n\n\n"); printf("\n\n\tEnter the size of the queue: "); scanf("%d",&n); do { printf("\n\n\n\t\t\t\tMENU\n\n"); printf("\t\t1.INSERT\n\n\t\t2.DELETE\n\n\t\t3.DISPLAY\n\n\t\t4.EXIT\n\n\t\tEnter your choice: "); scanf("%d",&no); if(no==1) { if(rear==(n-1)) printf("\n\t\tOverflow"); else { printf("\n\n\t\tEnter the element: "); scanf("%d",&element); if(front==-1&&rear==-1) front=0; rear++; queue[rear]=element; }} if(no==2) { if(front==-1) printf("\n\t\tUnderflow\n"); else { k=queue[front]; printf("\n\t\tDeleted element is %d ",k); } if(front==rear) front=rear=-1; else front++; } if(no==3) { if(front==-1&&rear==-1) printf("\n\t\tUnderflow\n"); else { printf("\n\t\tQueue elements are\n "); for(i=front;i<=rear;i++) { printf("\n\n\t\t%d",queue[i]); } } } if(no==4) break; printf("\n\n\t\tDo you want to continue(y/n) "); scanf(" %c",&c); } while(c=='y'||c=='Y'); getch(); }

Circular Queue

A circular queue is a variation of a queue where the last element is connected to the first element, forming a circle.

C Code for Circular Queue Implementation
#include #include void main() { int no,i,front=0,rear=0,k,queue[50],element,size,next=1; char c; clrscr(); printf("\n\tPROGRAM TO INSERT, DELETE AND DISPLAY ELEMENTS TO CIRCULARQUEUE"); printf("\n\t "); printf("\n\tEnter the size of the queue: "); scanf("%d",&size); do { printf("\n\t\t\t\tMENU\n\n"); printf("\t\t1.INSERT\n\t\t2.DELETE\n\t\t3.DISPLAY\n\t\t4.EXIT\n\t\tEnter your choice: "); scanf("%d",&no); if(no==1) { if(rear==size-1) { printf("\n overflow "); } printf("\t\tEnter the element: "); scanf("%d",&element); if(front==0&&rear==0) { front=rear=1; queue[rear]=element; } else { next=(rear%size)+1; if(next==front) printf("\t\tOverflow\n"); else { rear=next; queue[rear]=element; } } } if(no==2) {   if(front==0) printf("\t\tUnderflow\n"); else { k=queue[front]; printf("\t\tDeleted element is %d\n",k); } if(front==rear) front=rear=0; else front=(front%size)+1; } if(no==3) { if(front==0&&rear==0) printf("\t\tUnderflow\n"); else { printf("\t\tQueue elements are"); if(front

Dequeue

A dequeue (double-ended queue) is a generalization of a stack and a queue that supports inserting and removing elements from both ends.

C Code for Dequeue Implementation
#include #include void main() { int no,i,front=-1,rear=-1,k,queue[50],element,n; char c; clrscr(); printf("\n\tPROGRAM TO INSERT, DELETE AND DISPLAY ELEMENTS TO DEQUEUE\n"); printf("\t "); printf("\n\tEnter the size of the queue: "); scanf("%d",&n); do { printf("\t\t\t\tMENU\n"); printf("\t\t1.INSERT_FRONT\n\t\t2.INSERT_END\n\t\t3.DELETE_FRONT\n\t\t4.DELETE_E  ND\n\t\t5.DISPLAY\n\t\t6.EXIT\n\t\tEnter your choice: "); scanf("%d",&no); if(no==1) { if(front==0) printf("\t\tOverflow\n"); else { printf("\t\tEnter the element: "); scanf("%d",&element); if(front==-1) {front=0; rear=0; queue[front]=element; } else if(front!=0) { front=front-1; queue[front]=element; } } } if(no==2) { if(rear==n-1) printf("\t\tOverflow\n"); else {   printf("\t\tEnter the element: "); scanf("%d",&element); if(front==-1) { front=rear=0; queue[rear]=element; } else { rear=rear+1; queue[rear]=element; } } } if(no==3) { if(front==-1) printf("\t\tUnderflow\n"); else { k=queue[front]; printf("\t\tDeleted element is %d ",k); printf("\n"); if(front==rear) front=rear=-1; else front++; } } if(no==4) { if(rear==-1) printf("\t\tUnderflow\n"); else { k=queue[rear]; printf("\t\tDeleted element is %d ",k); printf("\n"); if(front==rear) front=rear=-1; else rear--; } }   if(no==5) { if(front==-1&&rear==-1) printf("\t\tUnderflow\n"); else { printf("\t\tQueue elements are "); for(i=front;i<=rear;i++) printf("%d ",queue[i]); printf("\n"); } } if(no==6) break; printf("\t\tDo you want to continue(y/n) "); scanf(" %c",&c); } while(c=='y'||c=='Y'); getch(); }

Stack Using Linked List

A stack can also be implemented using a linked list. Each node in the list contains data and a pointer to the next node.

C Code for Stack Implementation Using Linked List
#include #include #include typedef struct node { int data; struct node *link; }NODE; NODE *start=NULL,*top=NULL,*s,*ptr,*disply; void main() { int no,item; char c; clrscr(); printf("\n\tPROGRAM TO INSERT, DELETE AND DISPLAY ELEMENTS TO STACK USING LINKED LIST"); printf("\n\t \n"); do { printf("\t\t\t\tMENU\n"); printf("\t\t1.INSERT\n\t\t2.DELETE\n\t\t3.DISPLAY\n\t\t4.EXIT\n\t\tEnter your choice: "); scanf("%d",&no); if(no==1) { ptr=(NODE*)malloc(sizeof(NODE)); printf("\n\t\tEnter the element: "); scanf("%d",&item); ptr->data=item; ptr->link=NULL; if(start==NULL) { start=ptr; top=ptr; } else { ptr->link=top; top=ptr; } } if(no==2) {   if(top==NULL) printf("\n\t\tStack is empty"); else { s=top; printf("\n\t\tDeleted Element is %d",top->data); top=top->link; free(s); if(top==NULL) start=NULL; } } if(no==3) { if(top==NULL) printf("\n\t\tStack is empty"); else { printf("\n\t\tStack elements are:"); disply=top; while(disply!=NULL) { item=disply->data; printf("\t %d\n",item); disply=disply->link; } } } if(no==4) break; printf("\n\t\tDo you want to continue(y/n) "); scanf(" %c",&c); } while(c=='y'||c=='Y'); getch(); }

Queue Using Linked List

A queue can also be implemented using a linked list. Each node in the list contains data and a pointer to the next node.

C Code for Queue Implementation Using Linked List
#include #include #include typedef struct node { int data; struct node *link; }NODE; NODE *front=NULL,*rear=NULL,*s,*ptr,*disply; void main() { int no,item; char c; clrscr(); printf("\n\tPROGRAM TO INSERT,DELETE AND DISPLAY ELEMENTS TO QUEUE USING LINKEDLIST"); printf("\t\t \n\n"); do { printf("\t\t\t\tMENU"); printf("\n\t\t1.INSERT\n\t\t2.DELETE\n\t\t3.DISPLAY\n\t\t4.EXIT\n\t\tEnter your choice: "); scanf("%d",&no); if(no==1) { ptr=(NODE*)malloc(sizeof(NODE)); printf("\t\tEnter the element: "); scanf("%d",&ptr->data); ptr->link=NULL; if(rear==NULL) { front=ptr; rear=ptr; } else { rear->link=ptr; rear=ptr; } } if(no==2) { if(front==NULL) printf("\t\tStack is empty\n"); else { s=front; printf("\t\tDeleted Element is %d\n",front->data); front=front->link; free(s); if(front==NULL) rear=NULL; } } if(no==3) { if(front==NULL) printf("\t\tQueue is empty\n"); else { printf("\t\tQueue elements are"); disply=front; while(disply!=NULL) { printf(" %d",disply->data); disply=disply->link; } printf("\n"); } } if(no==4) break; printf("\t\tDo you want to continue(y/n) "); scanf(" %c",&c); } while(c=='y'||c=='Y'); getch(); }

Singly Linked List

A singly linked list is a collection of nodes where each node contains data and a pointer to the next node in the list.

C Code for Singly Linked List Implementation
#include #include typedef struct Node { int data; struct Node* next; } Node; Node* createNode(int data) {     Node* newNode = (Node*)malloc(sizeof(Node));     if (newNode == NULL) { printf("Memory allocation failed\n"); exit(1); }     newNode->data = data; newNode->next = NULL;     return newNode; } Node* insertFront(Node* head, int data) {     Node* newNode = createNode(data);     newNode->next = head;     return newNode; } Node* insertEnd(Node* head, int data) {     Node* newNode = createNode(data);     if (head == NULL) return newNode;     Node* temp = head;     while (temp->next != NULL) temp = temp->next;     temp->next = newNode;     return head; } void displayList(Node* head) {     printf("List: ");     while (head != NULL) { printf("%d -> ", head->data); head = head->next; }     printf("NULL\n"); } int main() {     Node* head = NULL;     head = insertEnd(head, 10);     head = insertEnd(head, 20);     head = insertEnd(head, 30);     head = insertFront(head, 5);     displayList(head);     return 0; }

Polynomial Addition

Polynomial addition can be implemented using linked lists to represent the polynomials.

C Code for Polynomial Addition
#include #include typedef struct Node {     int coeff, exp;     struct Node* next; } Node; Node* createNode(int coeff, int exp) {     Node* newNode = (Node*)malloc(sizeof(Node));     if (newNode == NULL) {         printf("Memory allocation failed\n");         exit(1);     }     newNode->coeff = coeff;     newNode->exp = exp;     newNode->next = NULL;     return newNode; } Node* addPolynomials(Node* poly1, Node* poly2) {     Node* result = NULL;     while (poly1 != NULL && poly2 != NULL) {         if (poly1->exp > poly2->exp) {             result = createNode(poly1->coeff, poly1->exp);             poly1 = poly1->next;         } else if (poly1->exp < poly2->exp) {             result = createNode(poly2->coeff, poly2->exp);             poly2 = poly2->next;         } else {             int sumCoeff = poly1->coeff + poly2->coeff;             if (sumCoeff != 0)                 result = createNode(sumCoeff, poly1->exp);             poly1 = poly1->next;             poly2 = poly2->next;         }     }     while (poly1 != NULL) {         result = createNode(poly1->coeff, poly1->exp);         poly1 = poly1->next;     }     while (poly2 != NULL) {         result = createNode(poly2->coeff, poly2->exp);         poly2 = poly2->next;     }     return result; } void displayPolynomial(Node* poly) {     while (poly != NULL) {         printf("%dx^%d ", poly->coeff, poly->exp);         if (poly->next != NULL)             printf("+ ");         poly = poly->next;     }     printf("\n"); } int main() {     Node* poly1 = createNode(5, 2);     poly1->next = createNode(4, 1);     poly1->next->next = createNode(2, 0);     Node* poly2 = createNode(3, 2);     poly2->next = createNode(2, 1);     poly2->next->next = createNode(1, 0);     printf("Polynomial 1: ");     displayPolynomial(poly1);     printf("Polynomial 2: ");     displayPolynomial(poly2);     Node* result = addPolynomials(poly1, poly2);     printf("Result: ");     displayPolynomial(result);     return 0; }

Infix to Postfix Evaluation

Infix to postfix conversion is a common technique used in expression evaluation. It involves converting an expression from infix notation (where operators are between operands) to postfix notation (where operators follow their operands).

C Code for Infix to Postfix Evaluation
#include #include #include void push(char); void push1(int); int priority(char); void read(); int top=-1,top1=-1,j=0,i,x,y; char stk[50],stk1[50],a[50],ch,post[50]; void main() { clrscr(); printf("\n\n\tProgram for Infix to Postfix Evaluation"); printf("\n\t \n"); printf("\n\tEnter the expression: "); gets(a); for(i=0;a[i]!='\0';i++) { ch=a[i]; switch(ch) { case '(':push(ch); break; case')':while (stk[top]!='(') { post[j++]=stk[top]; top--; } top--; break; case '+': case '-': case '^': case '/': case '*': if (top== -1||stk[top]=='(') push(ch); else { x=priority(ch); y=priority(stk[top]); if(y>=x) { post[j++]=stk[top]; top--; push(ch);} else push(ch); } break;   default: if(isalpha(ch)) post[j++]=ch; break; } } while(stk[top]!='\0') { post[j++]=stk[top]; top--; } post[j]='\0'; printf("\n\tPostfix expression: "); puts(post); read(); getch(); } void push(char ch) { top++; stk[top]=ch; } void push1(int ch) { top1++; stk1[top1]=ch; } int priority(char c) { if (c=='t'||c=='-') return 1; else if(c=='*'||c=='/') return 2; else if(c=='^') return 3; else return 0; } void read() { int c,o1,o2; for(i=0;post[i]!='\0';i++) { ch=post[i]; if(isalpha(ch)) { printf("\n\tEnter the value for %c: ",ch); scanf("%d", &c); push1(c); } else { o1=stk1[top1]; top1--; o2=stk1[top1]; top1--; switch(ch) { case '+':x=o1+o2; break; case'-':x=o1-o2; break; case'*':x=o1*o2; break; case'/':x=o1/o2; break; case'^':x=o1^o2; break; default: break; } push1(x); } } printf("\n\tValue of the expression is %d",stk1[top1]); }

Implementation of Tree

A tree is a hierarchical data structure consisting of nodes connected by edges. Each node contains data and references to its child nodes.

C Code for Tree Implementation
#include #include struct Node {     int data;     struct Node* left;     struct Node* right; }; 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->left = NULL;     newNode->right = NULL;     return newNode; } Struct Node* insert(struct Node* root, int data) {     if (root == NULL)         return createNode(data);     if (data < root->data)         root->left = insert(root->left, data);     else if (data > root->data)         root->right = insert(root->right, data);     return root; } void inorderTraversal(struct Node* root) {     if (root != NULL) {         inorderTraversal(root->left);         printf("%d ", root->data);         inorderTraversal(root->right);  } } int main() {     struct Node* root = NULL;     root = insert(root, 50);     insert(root, 30);     insert(root, 20);    insert(root, 40);    insert(root, 70);     insert(root, 60);     insert(root, 80);     printf("Inorder traversal: ");     inorderTraversal(root);     printf("\n");     return 0; }