C Implementation of Queues, Linked Lists, and Search Algorithms

Circular Queue Implementation Using Linked Lists

This C program demonstrates the implementation of a circular queue using a linked list structure. The queue handles integer data.

Data Structure Definition

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

typedef struct QueueType {
    int Data;
    struct QueueType *Next;
} QUEUE;

QUEUE *Front = NULL; // Pointer to the front of the queue
QUEUE *Rear = NULL;  // Pointer to the rear of the queue

// Function prototypes
void Enqueue(int Num);
int Dequeue();
void DisplayQueue();
int Menu();

Enqueue Operation

The Enqueue function inserts a number into the circular queue. It handles memory allocation and maintains the circular link by ensuring Rear->Next always points to Front.

void Enqueue(int Num) {
    QUEUE *Node = (QUEUE *)malloc(sizeof(QUEUE)); // Allocate memory for the new node
    if (Node == NULL) { // Check for memory allocation failure
        printf("Memory allocation failed!\n");
        return;
    }
    Node->Data = Num;
    Node->Next = NULL;

    if (Front == NULL) { // Case 1: Queue is empty
        Front = Rear = Node; // Initialize Front and Rear to the new node
        Rear->Next = Front; // Make it circular by pointing Rear to Front
    } else { // Case 2: Queue is not empty
        Rear->Next = Node; // Link the new node after Rear
        Rear = Node;       // Update Rear to the new node
        Rear->Next = Front; // Maintain the circular link
    }
    printf("%d inserted into the circular queue.\n", Num);
}

Dequeue Operation

The Dequeue function deletes a number from the front of the circular queue. It handles the case where the queue becomes empty after deletion.

int Dequeue() {
    if (Front == NULL) { // Check if the queue is empty
        printf("The circular queue is empty. Dequeue operation cannot be performed.\n");
        return -1;
    }
    int data = Front->Data; // Store the data of the front node

    if (Front == Rear) { // Case 1: Only one node in the queue
        free(Front);
        Front = Rear = NULL; // Set both Front and Rear to NULL
    } else { // Case 2: More than one node in the queue
        QUEUE *Temp = Front;
        Front = Front->Next; // Move Front to the next node
        Rear->Next = Front;  // Update Rear to point to the new Front
        free(Temp);          // Free the memory of the old Front
    }
    printf("%d deleted from the circular queue.\n", data);
    return data; // Return the data of the deleted node
}

Displaying the Queue

void DisplayQueue() {
    if (Front == NULL) { // Check if the queue is empty
        printf("The circular queue is empty.\n");
        return;
    }
    QUEUE *Curr = Front;
    printf("Circular Queue Contents: ");
    do { // Traverse and print each node
        printf("%d -> ", Curr->Data);
        Curr = Curr->Next;
    } while (Curr != Front); // Stop when we loop back to the Front
    printf("(Back to Front)\n"); // Indicate the circular link
}

Main Program and Menu

The main function provides a menu interface for queue operations:

1. Insert a number (ENQUEUE)
2. Delete a number (DEQUEUE)
3. Display the contents of the Queue
4. Exit

int Menu() {
    int ch;
    printf("\nMenu\n");
    printf("1. Insert a number (ENQUEUE)\n");
    printf("2. Delete a number (DEQUEUE)\n");
    printf("3. Display the contents of the Queue\n");
    printf("4. Exit\n");
    printf("Enter your choice: ");
    scanf("%d", &ch);
    return ch;
}

int main() {
    int choice, value;
    while (1) {
        choice = Menu();
        switch (choice) {
            case 1: // Enqueue
                printf("Enter the number to insert: ");
                scanf("%d", &value);
                Enqueue(value);
                break;
            case 2: // Dequeue
                Dequeue();
                break;
            case 3: // Display queue
                DisplayQueue();
                break;
            case 4: // Exit
                printf("Exiting the program.\n");
                exit(0);
            default:
                printf("Invalid choice! Please try again.\n");
                break;
        }
    }
}

Standard Queue Implementation for Strings

This implementation uses a linked list to create a standard queue (FIFO), storing strings (names) up to 100 characters long.

Structure and Initialization

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN 100

typedef struct QueueNode {
    char Name[MAX_LEN];
    struct QueueNode* next;
} QUEUENODE;

QUEUENODE *FRONT = NULL, *REAR = NULL;

QUEUENODE* createNode(char S[]) {
    QUEUENODE* newNode = (QUEUENODE*)malloc(sizeof(QUEUENODE));
    if (!newNode) {
        printf("Memory allocation failed!\n");
        return NULL;
    }
    strcpy(newNode->Name, S);
    newNode->next = NULL;
    return newNode;
}

Queue Operations

void Enqueue(char S[]) {
    QUEUENODE* newNode = createNode(S);
    if (!newNode) return;

    if (REAR == NULL)
        FRONT = REAR = newNode;
    else {
        REAR->next = newNode;
        REAR = newNode;
    }
    printf("Enqueued: %s\n", S);
}

void Dequeue() {
    if (!FRONT) {
        printf("Queue is empty. Cannot dequeue.\n");
        return;
    }
    QUEUENODE* temp = FRONT;
    printf("Dequeued: %s\n", temp->Name);
    FRONT = FRONT->next;
    if (!FRONT)
        REAR = NULL;
    free(temp);
}

void Peek() {
    if (!FRONT) {
        printf("Queue is empty.\n");
        return;
    }
    printf("Front element: %s\n", FRONT->Name);
}

void DisplayQueue() {
    if (!FRONT) {
        printf("Queue is empty.\n");
        return;
    }
    QUEUENODE* temp = FRONT;
    printf("Queue: ");
    while (temp) {
        printf("%s -> ", temp->Name);
        temp = temp->next;
    }
    printf("NULL\n");
}

Example Usage

int main() {
    Enqueue("Arya");
    Enqueue("Babu");
    Enqueue("Chandini");
    DisplayQueue();
    Peek();
    Dequeue();
    DisplayQueue();
    return 0;
}

Ordered Linked List Management

This section provides functions for managing a singly linked list where elements are kept in ascending order upon insertion.

Data Structure and Insertion

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

typedef struct ListType {
    int Data;
    struct ListType *Next;
} LISTNODE;

LISTNODE *Head = NULL;

void InsertOrderedListNode(int Num) {
    LISTNODE *Node = (LISTNODE *)malloc(sizeof(LISTNODE));
    if (Node == NULL) {
        printf("Memory allocation failed!\n");
        return;
    }
    Node->Data = Num;
    Node->Next = NULL;

    if (Head == NULL || Head->Data >= Num) {
        Node->Next = Head;
        Head = Node;
        printf("%d inserted into the linked list.\n", Num);
        return;
    }

    LISTNODE *Curr = Head;
    while (Curr->Next != NULL && Curr->Next->Data < Num)
        Curr = Curr->Next;

    Node->Next = Curr->Next;
    Curr->Next = Node;
    printf("%d inserted into the linked list.\n", Num);
}

Utility Functions

void Display() {
    if (Head == NULL) {
        printf("The list is empty.\n");
        return;
    }
    LISTNODE *Curr = Head;
    printf("Ordered Linked List: ");
    while (Curr != NULL) {
        printf("%d -> ", Curr->Data);
        Curr = Curr->Next;
    }
    printf("NULL\n");
}

int DeleteNumber(int Num) {
    if (Head == NULL) {
        printf("The list is empty.\n");
        return -1;
    }

    LISTNODE *Curr = Head, *Prev = NULL;

    if (Head->Data == Num) {
        Head = Head->Next;
        free(Curr);
        printf("%d deleted from the list.\n", Num);
        return Num;
    }

    while (Curr != NULL && Curr->Data != Num) {
        Prev = Curr;
        Curr = Curr->Next;
    }

    if (Curr == NULL) {
        printf("%d not found in the list.\n", Num);
        return -1;
    }

    Prev->Next = Curr->Next;
    free(Curr);
    printf("%d deleted from the list.\n", Num);
    return Num;
}

int SearchNumber(int Num) {
    LISTNODE *Curr = Head;
    int position = 1;
    while (Curr != NULL) {
        if (Curr->Data == Num) {
            printf("%d found at position %d in the list.\n", Num, position);
            return position;
        }
        Curr = Curr->Next;
        position++;
    }
    printf("%d not found in the list.\n", Num);
    return -1;
}

int CountNodes() {
    int count = 0;
    LISTNODE *Curr = Head;
    while (Curr != NULL) {
        count++;
        Curr = Curr->Next;
    }
    printf("The number of nodes in the list is: %d\n", count);
    return count;
}

Main Program and Menu

The menu provides options for managing the ordered linked list:

1. Insert a number into the ordered linked list
2. Display the contents of the linked list
3. Delete a given number from the linked list
4. Search for a given number in the linked list
5. Return the number of nodes/data items in the list
6. Exit

int Menu() {
    int ch;
    printf("\nMenu\n1. Insert a number into the ordered linked list\n2. Display the contents of the linked list\n3. Delete a given number from the linked list\n4. Search for a given number in the linked list\n5. Return the number of nodes/data items in the list\n6. Exit\nEnter your choice: ");
    scanf("%d", &ch);
    return ch;
}

int main() {
    int choice, value;
    while (1) {
        choice = Menu();
        switch (choice) {
            case 1:
                printf("Enter the number to insert: ");
                scanf("%d", &value);
                InsertOrderedListNode(value);
                break;
            case 2:
                Display();
                break;
            case 3:
                printf("Enter the number to delete: ");
                scanf("%d", &value);
                DeleteNumber(value);
                break;
            case 4:
                printf("Enter the number to search: ");
                scanf("%d", &value);
                SearchNumber(value);
                break;
            case 5:
                CountNodes();
                break;
            case 6:
                printf("Exiting the program.\n");
                exit(0);
            default:
                printf("Invalid choice! Please try again.\n");
                break;
        }
    }
}

Basic Linked List Operations (Unordered)

This implementation focuses on fundamental linked list operations, including insertion at the end, deletion from the front and rear, and finding the maximum element.

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

typedef struct ListType{
    int Data;
    struct ListType *Next;
} LISTNODE;

LISTNODE *Head=NULL;

void InsertListNode(int Num){
    LISTNODE *Node,*Curr;
    Node=(LISTNODE*)malloc(sizeof(LISTNODE));
    if(Node==NULL){
        printf("Memory allocation failed!\n");
        return;
    }
    Node->Data=Num;
    Node->Next=NULL;
    
    if(Head==NULL){
        Head=Node;
    } else {
        Curr=Head;
        while(Curr->Next!=NULL){
            Curr=Curr->Next;
        }
        Curr->Next=Node;
    }
    printf("%d inserted into the linked list.\n",Num);
}

void Display(){
    LISTNODE *Curr;
    if(Head==NULL){
        printf("The list is empty.\n");
        return;
    }
    Curr=Head;
    while(Curr!=NULL){
        printf("%d -> ",Curr->Data);
        Curr=Curr->Next;
    }
    printf("NULL\n");
}

int DeleteFirstNode(){
    if(Head==NULL){
        printf("List is empty.\n");
        return -1;
    }
    LISTNODE *Temp=Head;
    int data=Temp->Data;
    Head=Head->Next;
    free(Temp);
    printf("Deleted first node with data: %d\n",data);
    return data;
}

int DeleteLastNode(){
    if(Head==NULL){
        printf("List is empty.\n");
        return -1;
    }
    if(Head->Next==NULL){
        int data=Head->Data;
        free(Head);
        Head=NULL;
        printf("Deleted last node with data: %d\n",data);
        return data;
    }
    LISTNODE *Curr=Head,*Prev=NULL;
    while(Curr->Next!=NULL){
        Prev=Curr;
        Curr=Curr->Next;
    }
    Prev->Next=NULL;
    int data=Curr->Data;
    free(Curr);
    printf("Deleted last node with data: %d\n",data);
    return data;
}

int MaxNumber(){
    if(Head==NULL){
        printf("List is empty.\n");
        return -1;
    }
    LISTNODE *Curr=Head;
    int Max=Curr->Data;
    while(Curr!=NULL){
        if(Curr->Data>Max){
            Max=Curr->Data;
        }
        Curr=Curr->Next;
    }
    printf("Maximum number in the list is: %d\n",Max);
    return Max;
}

Main Program and Menu

The menu options include:

1. Insert a number into the linked list
2. Display the contents of the linked list
3. Delete and return the data on the first node
4. Delete and return the data on the last node
5. Return the maximum number in the list
6. Exit

int Menu(){
    int ch;
    printf("\nMenu\n1. Insert a number into the linked list\n2. Display the contents of the linked list\n3. Delete and return the data on the first node\n4. Delete and return the data on the last node\n5. Return the maximum number in the list\n6. Exit\nEnter your choice: ");
    scanf("%d",&ch);
    return ch;
}

int main(){
    int choice,value;
    while(1){
        choice=Menu();
        switch(choice){
            case 1:
                printf("Enter the number to insert: ");
                scanf("%d",&value);
                InsertListNode(value);
                break;
            case 2:
                printf("Contents of the linked list: ");
                Display();
                break;
            case 3:
                DeleteFirstNode();
                break;
            case 4:
                DeleteLastNode();
                break;
            case 5:
                MaxNumber();
                break;
            case 6:
                printf("Exiting the program.\n");
                exit(0);
            default:
                printf("Invalid choice! Please try again.\n");
                break;
        }
    }
}

Array Searching and Sorting Algorithms in C

This program demonstrates fundamental array operations, including input/output, linear search, binary search, and bubble sort.

Array Utility Functions

#include <stdio.h>

void InputArray(int A[20], int N) {
    for (int i = 0; i < N; i++)
        scanf("%d", &A[i]);
}

void PrintArray(int A[20], int N) {
    for (int i = 0; i < N; i++)
        printf("%d \t", A[i]);
    printf("\n");
}

Search Algorithms

Linear Search

Checks every element sequentially until the key is found.

int LinearSearch(int A[20], int N, int Key) {
    for (int i = 0; i < N; i++)
        if (A[i] == Key)
            return i;
    return -1;
}

Binary Search

Requires the array to be sorted. It repeatedly divides the search interval in half.

int BinarySearch(int A[20], int N, int Key) {
    int Low = 0, High = N - 1, Mid;
    while (Low <= High) {
        Mid = (Low + High) / 2;
        if (A[Mid] == Key)
            return Mid;
        else if (A[Mid] < Key)
            Low = Mid + 1;
        else
            High = Mid - 1;
    }
    return -1;
}

Sorting Algorithm: Bubble Sort

A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

void BubbleSort(int A[20], int N) {
    for (int i = 0; i < N - 1; i++)
        for (int j = 0; j < N - 1 - i; j++)
            if (A[j] > A[j+1]) {
                int T = A[j];
                A[j] = A[j+1];
                A[j+1] = T;
            }
}

Main Program Execution

The main function initializes the array and allows the user to choose between Linear Search and Binary Search (which automatically sorts the array first).

int main() {
    int A[20], N, Key, Result, Choice;
    printf("Enter the number of elements\n");
    scanf("%d", &N);
    printf("Enter the elements\n");
    InputArray(A, N);
    printf("Entered elements of the array are\n");
    PrintArray(A, N);

    do {
        printf("\nChoose a search method:\n");
        printf("1. Linear Search\n");
        printf("2. Binary Search\n");
        printf("3. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &Choice);

        if (Choice == 1 || Choice == 2) {
            printf("Enter the number to search: ");
            scanf("%d", &Key);
        }

        switch (Choice) {
            case 1:
                Result = LinearSearch(A, N, Key);
                if (Result != -1)
                    printf("Element found at position %d (index %d)\n", Result + 1, Result);
                else
                    printf("Element not found in the array.\n");
                break;
            case 2:
                BubbleSort(A, N);
                printf("Array after sorting for Binary Search:\n");
                PrintArray(A, N);
                Result = BinarySearch(A, N, Key);
                if (Result != -1)
                    printf("Element found at position %d (index %d)\n", Result + 1, Result);
                else
                    printf("Element not found in the array.\n");
                break;
            case 3:
                printf("Exiting...\n");
                break;
            default:
                printf("Invalid choice! Please try again.\n");
        }
    } while (Choice != 3);
}