A C Program to demonstrate adjacency list representation of graphs

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

// A structure to represent an adjacency list node
struct AdjListNode
{
    int dest;
    struct AdjListNode* next;
};

// A structure to represent an adjacency list
struct AdjList
{
    struct AdjListNode *head; // pointer to head node of list
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
    int V;
    struct AdjList* array;
};

// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest)
{
    struct AdjListNode* newNode =
            (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;

    // Create an array of adjacency lists. Size of array will be V
    graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));

    // Initialize each adjacency list as empty by making head as NULL
    int i;
    for (i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest)
{
    // Add an edge from src to dest. A new node is added to the adjacency
    // list of src. The node is added at the begining
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // Since graph is undirected, add an edge from dest to src also
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// A utility function to print the adjacenncy list representation of graph
void printGraph(struct Graph* graph)
{
    int v;
    for (v = 0; v < graph->V; ++v)
    {
        struct AdjListNode* pCrawl = graph->array[v].head;
        printf("\n Adjacency list of vertex %d\n head ", v);
        while (pCrawl)
        {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

// Driver program to test above functions
int main()
{
    // create the graph given in above fugure
    int V = 5;
    struct Graph* graph = createGraph(V);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    // print the adjacency list representation of the above graph
    printGraph(graph);

    return 0;
}

Output:

 Adjacency list of vertex 0
 head -> 4-> 1

 Adjacency list of vertex 1
 head -> 4-> 3-> 2-> 0

 Adjacency list of vertex 2
 head -> 3-> 1

C program to demonstrate delete operation in binary search tree

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

struct node
{
    int key;
    struct node *left, *right;
};

// A utility function to create a new BST node
struct node *newNode(int item)
{
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// A utility function to do inorder traversal of BST
void inorder(struct node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d ", root->key);
        inorder(root->right);
    }
}

/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, int key)
{
    /* If the tree is empty, return a new node */
    if (node == NULL) return newNode(key);

    /* Otherwise, recur down the tree */
    if (key < node->key)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);

    /* return the (unchanged) node pointer */
    return node;
}

/* Given a non-empty binary search tree, return the node with minimum
key value found in that tree. Note that the entire tree does not
need to be searched. */
struct node * minValueNode(struct node* node)
{
    struct node* current = node;

    /* loop down to find the leftmost leaf */
    while (current->left != NULL)
        current = current->left;

    return current;
}

/* Given a binary search tree and a key, this function deletes the key
and returns the new root */
struct node* deleteNode(struct node* root, int key)
{
    // base case
    if (root == NULL) return root;

    // If the key to be deleted is smaller than the root's key,
    // then it lies in left subtree
    if (key < root->key)
        root->left = deleteNode(root->left, key);

    // If the key to be deleted is greater than the root's key,
    // then it lies in right subtree
    else if (key > root->key)
        root->right = deleteNode(root->right, key);

    // if key is same as root's key, then This is the node
    // to be deleted
    else
    {
        // node with only one child or no child
        if (root->left == NULL)
        {
            struct node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            struct node *temp = root->left;
            free(root);
            return temp;
        }

        // node with two children: Get the inorder successor (smallest
        // in the right subtree)
        struct node* temp = minValueNode(root->right);

        // Copy the inorder successor's content to this node
        root->key = temp->key;

        // Delete the inorder successor
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

// Driver Program to test above functions
int main()
{
    /* Let us create following BST
            50
        /     \
        30     70
        / \ / \
    20 40 60 80 */
    struct node *root = NULL;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);

    printf("Inorder traversal of the given tree \n");
    inorder(root);

    printf("\nDelete 20\n");
    root = deleteNode(root, 20);
    printf("Inorder traversal of the modified tree \n");
    inorder(root);

    printf("\nDelete 30\n");
    root = deleteNode(root, 30);
    printf("Inorder traversal of the modified tree \n");
    inorder(root);

    printf("\nDelete 50\n");
    root = deleteNode(root, 50);
    printf("Inorder traversal of the modified tree \n");
    inorder(root);

    return 0;
}

Output:

Inorder traversal of the given tree 
20 30 40 50 60 70 80 
Delete 20
Inorder traversal of the modified tree 
30 40 50 60 70 80 
Delete 30
Inorder traversal of the modified tree 
40 50 60 70 80 
Delete 50
Inorder traversal of the modified tree 

C program to demonstrate insert operation in binary search tree

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

struct node
{
    int key;
    struct node *left, *right;
};

// A utility function to create a new BST node
struct node *newNode(int item)
{
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// A utility function to do inorder traversal of BST
void inorder(struct node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d \n", root->key);
        inorder(root->right);
    }
}

/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, int key)
{
    /* If the tree is empty, return a new node */
    if (node == NULL) return newNode(key);

    /* Otherwise, recur down the tree */
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);

    /* return the (unchanged) node pointer */
    return node;
}

// Driver Program to test above functions
int main()
{
    /* Let us create following BST
            50
        /     \
        30     70
        / \ / \
    20 40 60 80 */
    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);

    // print inoder traversal of the BST
    inorder(root);

    return 0;
}

Output:

20 
30 
40 
50 
60 
70 
80

Tree Traversals (Inorder, Preorder and Postorder)

// C program for different tree traversals
#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
    int data;
    struct node* left;
    struct node* right;
};

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node = (struct node*)
                                malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return(node);
}

/* Given a binary tree, print its nodes according to the
"bottom-up" postorder traversal. */
void printPostorder(struct node* node)
{
    if (node == NULL)
        return;

    // first recur on left subtree
    printPostorder(node->left);

    // then recur on right subtree
    printPostorder(node->right);

    // now deal with the node
    printf("%d ", node->data);
}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
    if (node == NULL)
        return;

    /* first recur on left child */
    printInorder(node->left);

    /* then print the data of node */
    printf("%d ", node->data);

    /* now recur on right child */
    printInorder(node->right);
}

/* Given a binary tree, print its nodes in preorder*/
void printPreorder(struct node* node)
{
    if (node == NULL)
        return;

    /* first print data of node */
    printf("%d ", node->data);

    /* then recur on left sutree */
    printPreorder(node->left);

    /* now recur on right subtree */
    printPreorder(node->right);
}

/* Driver program to test above functions*/
int main()
{
    struct node *root = newNode(1);
    root->left             = newNode(2);
    root->right         = newNode(3);
    root->left->left     = newNode(4);
    root->left->right = newNode(5);

    printf("\nPreorder traversal of binary tree is \n");
    printPreorder(root);

    printf("\nInorder traversal of binary tree is \n");
    printInorder(root);

    printf("\nPostorder traversal of binary tree is \n");
    printPostorder(root);

    getchar();
    return 0;
}

Output:

Preorder traversal of binary tree is 
1 2 4 5 3 
Inorder traversal of binary tree is 
4 2 5 1 3 
Postorder traversal of binary tree is 
4 5 2 3 1 

A C program to show implementation of LRU cache




#include <stdio.h>

#include <stdlib.h>

 

// A Queue Node (Queue is implemented using Doubly Linked List)

typedef struct QNode

{

    struct QNode *prev, *next;

    unsigned pageNumber;  // the page number stored in this QNode

} QNode;

 

// A Queue (A FIFO collection of Queue Nodes)

typedef struct Queue

{

    unsigned count;  // Number of filled frames

    unsigned numberOfFrames; // total number of frames

    QNode *front, *rear;

} Queue;

 

// A hash (Collection of pointers to Queue Nodes)

typedef struct Hash

{

    int capacity; // how many pages can be there

    QNode* *array; // an array of queue nodes

} Hash;

 

// A utility function to create a new Queue Node. The queue Node

// will store the given 'pageNumber'

QNode* newQNode( unsigned pageNumber )

{

    // Allocate memory and assign 'pageNumber'

    QNode* temp = (QNode *)malloc( sizeof( QNode ) );

    temp->pageNumber = pageNumber;

 

    // Initialize prev and next as NULL

    temp->prev = temp->next = NULL;

 

    return temp;

}

 

// A utility function to create an empty Queue.

// The queue can have at most 'numberOfFrames' nodes

Queue* createQueue( int numberOfFrames )

{

    Queue* queue = (Queue *)malloc( sizeof( Queue ) );

 

    // The queue is empty

    queue->count = 0;

    queue->front = queue->rear = NULL;

 

    // Number of frames that can be stored in memory

    queue->numberOfFrames = numberOfFrames;

 

    return queue;

}

 

// A utility function to create an empty Hash of given capacity

Hash* createHash( int capacity )

{

    // Allocate memory for hash

    Hash* hash = (Hash *) malloc( sizeof( Hash ) );

    hash->capacity = capacity;

 

    // Create an array of pointers for refering queue nodes

    hash->array = (QNode **) malloc( hash->capacity * sizeof( QNode* ) );

 

    // Initialize all hash entries as empty

    int i;

    for( i = 0; i < hash->capacity; ++i )

        hash->array[i] = NULL;

 

    return hash;

}

 

// A function to check if there is slot available in memory

int AreAllFramesFull( Queue* queue )

{

    return queue->count == queue->numberOfFrames;

}

 

// A utility function to check if queue is empty

int isQueueEmpty( Queue* queue )

{

    return queue->rear == NULL;

}

 

// A utility function to delete a frame from queue

void deQueue( Queue* queue )

{

    if( isQueueEmpty( queue ) )

        return;

 

    // If this is the only node in list, then change front

    if (queue->front == queue->rear)

        queue->front = NULL;

 

    // Change rear and remove the previous rear

    QNode* temp = queue->rear;

    queue->rear = queue->rear->prev;

 

    if (queue->rear)

        queue->rear->next = NULL;

 

    free( temp );

 

    // decrement the number of full frames by 1

    queue->count--;

}

 

// A function to add a page with given 'pageNumber' to both queue

// and hash

void Enqueue( Queue* queue, Hash* hash, unsigned pageNumber )

{

    // If all frames are full, remove the page at the rear

    if ( AreAllFramesFull ( queue ) )

    {

        // remove page from hash

        hash->array[ queue->rear->pageNumber ] = NULL;

        deQueue( queue );

    }

 

    // Create a new node with given page number,

    // And add the new node to the front of queue

    QNode* temp = newQNode( pageNumber );

    temp->next = queue->front;

 

    // If queue is empty, change both front and rear pointers

    if ( isQueueEmpty( queue ) )

        queue->rear = queue->front = temp;

    else  // Else change the front

    {

        queue->front->prev = temp;

        queue->front = temp;

    }

 

    // Add page entry to hash also

    hash->array[ pageNumber ] = temp;

 

    // increment number of full frames

    queue->count++;

}

 

// This function is called when a page with given 'pageNumber' is referenced

// from cache (or memory). There are two cases:

// 1. Frame is not there in memory, we bring it in memory and add to the front

//    of queue

// 2. Frame is there in memory, we move the frame to front of queue

void ReferencePage( Queue* queue, Hash* hash, unsigned pageNumber )

{

    QNode* reqPage = hash->array[ pageNumber ];

 

    // the page is not in cache, bring it

    if ( reqPage == NULL )

        Enqueue( queue, hash, pageNumber );

 

    // page is there and not at front, change pointer

    else if (reqPage != queue->front)

    {

        // Unlink rquested page from its current location

        // in queue.

        reqPage->prev->next = reqPage->next;

        if (reqPage->next)

           reqPage->next->prev = reqPage->prev;

 

        // If the requested page is rear, then change rear

        // as this node will be moved to front

        if (reqPage == queue->rear)

        {

           queue->rear = reqPage->prev;

           queue->rear->next = NULL;

        }

 

        // Put the requested page before current front

        reqPage->next = queue->front;

        reqPage->prev = NULL;

 

        // Change prev of current front

        reqPage->next->prev = reqPage;

 

        // Change front to the requested page

        queue->front = reqPage;

    }

}

 

// Driver program to test above functions

int main()

{

    // Let cache can hold 4 pages

    Queue* q = createQueue( 4 );

 

    // Let 10 different pages can be requested (pages to be

    // referenced are numbered from 0 to 9

    Hash* hash = createHash( 10 );

 

    // Let us refer pages 1, 2, 3, 1, 4, 5

    ReferencePage( q, hash, 1);

    ReferencePage( q, hash, 2);

    ReferencePage( q, hash, 3);

    ReferencePage( q, hash, 1);

    ReferencePage( q, hash, 4);

    ReferencePage( q, hash, 5);

 

    // Let us print cache frames after the above referenced pages

    printf ("%d ", q->front->pageNumber);

    printf ("%d ", q->front->next->pageNumber);

    printf ("%d ", q->front->next->next->pageNumber);

    printf ("%d ", q->front->next->next->next->pageNumber);

 

    return 0;

}

Output:

5 4 1 3

C++ implementation of De-queue using circular array




#include<iostream>

using namespace std;

 

// Maximum size of array or Dequeue

#define MAX 100

 

// A structure to represent a Deque

class Deque

{

    int  arr[MAX];

    int  front;

    int  rear;

    int  size;

public :

    Deque(int size)

    {

        front = -1;

        rear = 0;

        this->size = size;

    }

 

    // Operations on Deque:

    void  insertfront(int key);

    void  insertrear(int key);

    void  deletefront();

    void  deleterear();

    bool  isFull();

    bool  isEmpty();

    int  getFront();

    int  getRear();

};

 

// Checks whether Deque is full or not.

bool Deque::isFull()

{

    return ((front == 0 && rear == size-1)||

            front == rear+1);

}

 

// Checks whether Deque is empty or not.

bool Deque::isEmpty ()

{

    return (front == -1);

}

 

// Inserts an element at front

void Deque::insertfront(int key)

{

    // check whether Deque if  full or not

    if (isFull())

    {

        cout << "Overflow\n" << endl;

        return;

    }

 

    // If queue is initially empty

    if (front == -1)

    {

        front = 0;

        rear = 0;

    }

 

    // front is at first position of queue

    else if (front == 0)

        front = size - 1 ;

 

    else // decrement front end by '1'

        front = front-1;

 

    // insert current element into Deque

    arr[front] = key ;

}

 

// function to inset element at rear end

// of Deque.

void Deque ::insertrear(int key)

{

    if (isFull())

    {

        cout << " Overflow\n " << endl;

        return;

    }

 

    // If queue is initially empty

    if (front == -1)

    {

        front = 0;

        rear = 0;

    }

 

    // rear is at last position of queue

    else if (rear == size-1)

        rear = 0;

 

    // increment rear end by '1'

    else

        rear = rear+1;

 

    // insert current element into Deque

    arr[rear] = key ;

}

 

// Deletes element at front end of Deque

void Deque ::deletefront()

{

    // check whether Deque is empty or not

    if (isEmpty())

    {

        cout << "Queue Underflow\n" << endl;

        return ;

    }

 

    // Deque has only one element

    if (front == rear)

    {

        front = -1;

        rear = -1;

    }

    else

        // back to initial position

        if (front == size -1)

            front = 0;

 

        else // increment front by '1' to remove current

            // front value from Deque

            front = front+1;

}

 

// Delete element at rear end of Deque

void Deque::deleterear()

{

    if (isEmpty())

    {

        cout << " Underflow\n" << endl ;

        return ;

    }

 

    // Deque has only one element

    if (front == rear)

    {

        front = -1;

        rear = -1;

    }

    else if (rear == 0)

        rear = size-1;

    else

        rear = rear-1;

}

 

// Returns front element of Deque

int Deque::getFront()

{

    // check whether Deque is empty or not

    if (isEmpty())

    {

        cout << " Underflow\n" << endl;

        return -1 ;

    }

    return arr[front];

}

 

// function return rear element of Deque

int Deque::getRear()

{

    // check whether Deque is empty or not

    if(isEmpty() || rear < 0)

    {

        cout << " Underflow\n" << endl;

        return -1 ;

    }

    return arr[rear];

}

 

// Driver program to test above function

int main()

{

    Deque dq(5);

    cout << "Insert element at rear end  : 5 \n";

    dq.insertrear(5);

 

    cout << "insert element at rear end : 10 \n";

    dq.insertrear(10);

 

    cout << "get rear element " << " "

         << dq.getRear() << endl;

 

    dq.deleterear();

    cout << "After delete rear element new rear"

         << " become " << dq.getRear() << endl;

 

    cout << "insert element at front end \n";

    dq.insertfront(15);

 

    cout << "get front element " << " "

         << dq.getFront() << endl;

 

    dq.deletefront();

 

    cout << "After delete front element new "

       << "front become " << dq.getFront() << endl;

    return 0;

}

Output:

insert element at rear end  : 5
insert element at rear end : 10
get rear element : 10
After delete rear element new rear become : 5
insert element at front end : 15
get front element : 15
After delete front element new front become : 5

A C program to demonstrate linked list based implementation of queue




#include <stdlib.h>

#include <stdio.h>

 

// A linked list (LL) node to store a queue entry

struct QNode

{

    int key;

    struct QNode *next;

};

 

// The queue, front stores the front node of LL and rear stores ths

// last node of LL

struct Queue

{

    struct QNode *front, *rear;

};

 

// A utility function to create a new linked list node.

struct QNode* newNode(int k)

{

    struct QNode *temp = (struct QNode*)malloc(sizeof(struct QNode));

    temp->key = k;

    temp->next = NULL;

    return temp;

}

 

// A utility function to create an empty queue

struct Queue *createQueue()

{

    struct Queue *q = (struct Queue*)malloc(sizeof(struct Queue));

    q->front = q->rear = NULL;

    return q;

}

 

// The function to add a key k to q

void enQueue(struct Queue *q, int k)

{

    // Create a new LL node

    struct QNode *temp = newNode(k);

 

    // If queue is empty, then new node is front and rear both

    if (q->rear == NULL)

    {

       q->front = q->rear = temp;

       return;

    }

 

    // Add the new node at the end of queue and change rear

    q->rear->next = temp;

    q->rear = temp;

}

 

// Function to remove a key from given queue q

struct QNode *deQueue(struct Queue *q)

{

    // If queue is empty, return NULL.

    if (q->front == NULL)

       return NULL;

 

    // Store previous front and move front one node ahead

    struct QNode *temp = q->front;

    q->front = q->front->next;

 

    // If front becomes NULL, then change rear also as NULL

    if (q->front == NULL)

       q->rear = NULL;

    return temp;

}

 

// Driver Program to test anove functions

int main()

{

    struct Queue *q = createQueue();

    enQueue(q, 10);

    enQueue(q, 20);

    deQueue(q);

    deQueue(q);

    enQueue(q, 30);

    enQueue(q, 40);

    enQueue(q, 50);

    struct QNode *n = deQueue(q);

    if (n != NULL)

      printf("Dequeued item is %d", n->key);

    return 0;

}

Output:

Dequeued item is 30

C program for array implementation of queue




#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

 

// A structure to represent a queue

struct Queue

{

    int front, rear, size;

    unsigned capacity;

    int* array;

};

 

// function to create a queue of given capacity. It initializes size of

// queue as 0

struct Queue* createQueue(unsigned capacity)

{

    struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));

    queue->capacity = capacity;

    queue->front = queue->size = 0;

    queue->rear = capacity - 1;  // This is important, see the enqueue

    queue->array = (int*) malloc(queue->capacity * sizeof(int));

    return queue;

}

 

// Queue is full when size becomes equal to the capacity

int isFull(struct Queue* queue)

{  return (queue->size == queue->capacity);  }

 

// Queue is empty when size is 0

int isEmpty(struct Queue* queue)

{  return (queue->size == 0); }

 

// Function to add an item to the queue.  It changes rear and size

void enqueue(struct Queue* queue, int item)

{

    if (isFull(queue))

        return;

    queue->rear = (queue->rear + 1)%queue->capacity;

    queue->array[queue->rear] = item;

    queue->size = queue->size + 1;

    printf("%d enqueued to queue\n", item);

}

 

// Function to remove an item from queue.  It changes front and size

int dequeue(struct Queue* queue)

{

    if (isEmpty(queue))

        return INT_MIN;

    int item = queue->array[queue->front];

    queue->front = (queue->front + 1)%queue->capacity;

    queue->size = queue->size - 1;

    return item;

}

 

// Function to get front of queue

int front(struct Queue* queue)

{

    if (isEmpty(queue))

        return INT_MIN;

    return queue->array[queue->front];

}

 

// Function to get rear of queue

int rear(struct Queue* queue)

{

    if (isEmpty(queue))

        return INT_MIN;

    return queue->array[queue->rear];

}

 

// Driver program to test above functions./

int main()

{

    struct Queue* queue = createQueue(1000);

 

    enqueue(queue, 10);

    enqueue(queue, 20);

    enqueue(queue, 30);

    enqueue(queue, 40);

 

    printf("%d dequeued from queue\n", dequeue(queue));

 

    printf("Front item is %d\n", front(queue));

    printf("Rear item is %d\n", rear(queue));

 

    return 0;

}

Output:

10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
40 enqueued to queue
10 dequeued from queue
Front item is 20
Rear item is 40