Md. Anisur Rahman C Programming Lab Manual, Data Structure And Algorithm

C Programming Lab Manual – 63

Write a C program for Circular Linked List.

Algorithm
Create a structure definition for a node with two members: an integer 'num' and a pointer to the next node 'nextptr'
Declare a global variable 'stnode' of type 'struct node*' and initialize it to NULL
Define a function ClListcreation that takes an integer parameter 'n':
    Declare local variables: 'i', 'num'
    If 'n' is greater than or equal to 1, then do the following:
        Allocate memory for 'stnode' using 'malloc' and assign it to 'stnode'
        Prompt the user to input data for the first node and store it in 'num'
        Set the 'num' of 'stnode' to the input value
        Set 'nextptr' of 'stnode' to NULL
        Set 'preptr' to 'stnode'
        Iterate from 'i' = 2 to 'n':
            Allocate memory for a new node using 'malloc' and assign it to 'newnode'
            Prompt the user to input data for the 'i'th node and store it in 'num'
            Set the 'num' of 'newnode' to the input value
            Set 'nextptr' of 'newnode' to NULL
            Set 'nextptr' of 'preptr' to 'newnode'
            Set 'preptr' to 'newnode'
        Set 'nextptr' of 'preptr' to 'stnode'

Define a function displayClList:
    Declare a local variable 'tmp' of type 'struct node*'
    Declare a local variable 'n' and initialize it to 1
    If 'stnode' is NULL, then do the following:
        Print "No data found in the List yet."
    Else, do the following:
        Set 'tmp' to 'stnode'
        Print "Data entered in the list are :"
        Do the following:
            Print "Data 'n' = 'tmp->num'"
            Set 'tmp' to 'tmp->nextptr'
            Increment 'n' by 1
        While 'tmp' is not equal to 'stnode'
        
In the main function:
    Declare a local variable 'n'
    Set 'stnode' to NULL
    Print "Circular Linked List : Create and display a circular linked list :"
    Prompt the user to input the number of nodes and store it in 'n'
    Call the function ClListcreation with 'n' as the argument
    Call the function displayClList
    Return 0

Figure: Linked List Operations

C Programming Code

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

struct node {
    int num;
    struct node * nextptr;
}*stnode;
 

void ClListcreation(int n);
void displayClList();

int main()
{
    int n;
    stnode = NULL;
	printf("\n\n Circular Linked List : Create and display a circular linked list :\n");
	printf("\n");	   	

    printf(" Input the number of nodes : ");
    scanf("%d", &n);
 
    ClListcreation(n); 
    displayClList();
    return 0;
}

void ClListcreation(int n)
{
    int i, num;
    struct node *preptr, *newnode;

    if(n >= 1)
    {
        stnode = (struct node *)malloc(sizeof(struct node));

        printf(" Input data for node 1 : ");
        scanf("%d", &num);
        stnode->num = num;
        stnode->nextptr = NULL;
        preptr = stnode;
        for(i=2; i<=n; i++)
        {
            newnode = (struct node *)malloc(sizeof(struct node));
            printf(" Input data for node %d : ", i);
            scanf("%d", &num);
            newnode->num = num;
            newnode->nextptr = NULL;	// next address of new node set as NULL
            preptr->nextptr = newnode;	// previous node is linking with new node
            preptr = newnode;   		// previous node is advanced
        }
        preptr->nextptr = stnode; 		//last node is linking with first node
    }
}

void displayClList()
{
    struct node *tmp;
    int n = 1;

    if(stnode == NULL)
    {
        printf(" No data found in the List yet.");
    }
    else
    {
        tmp = stnode;
        printf("\n\n Data entered in the list are :\n");

        do {
            printf(" Data %d = %d\n", n, tmp->num);

            tmp = tmp->nextptr;
            n++;
        }while(tmp != stnode);
    }
}

Output

 Circular Linked List : Create and display a circular linked list :                                           
                                      
 Input the number of nodes : 3                                                                                
 Input data for node 1 : 2                                                                                    
 Input data for node 2 : 5                                                                                    
 Input data for node 3 : 8                                                                                    
                                                                                                              
 Data entered in the list are :                                                                               
 Data 1 = 2                                                                                                   
 Data 2 = 5                                                                                                   
 Data 3 = 8

Md. Anisur Rahman C Programming Lab Manual, Data Structure And Algorithm

C Programming Lab Manual – 62

Write a C program for Doubly Linked List.

Algorithm
//Create a new node
allocate memory for newNode
assign the data to newNode.

//Set prev and next pointers of new node
point next of newNode to the first node of the doubly linked list
point prev to null

//Make new node as head node
Point prev of the first node to newNode (now the previous head is the second node)
Point head to newNode

//Insertion in between two nodes
allocate memory for newNode
assign the data to newNode.

//Set the next pointer of new node and previous node
assign the value of next from previous node to the next of newNode
assign the address of newNode to the next of previous node

//Set the prev pointer of new node and the next node
assign the value of prev of next node to the prev of newNode
assign the address of newNode to the prev of next node

C Programming Code

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

// node creation
struct Node {
  int data;
  struct Node* next;
  struct Node* prev;
};

// insert node at the front
void insertFront(struct Node** head, int data) {
  // allocate memory for newNode
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

  // assign data to newNode
  newNode->data = data;

  // make newNode as a head
  newNode->next = (*head);

  // assign null to prev
  newNode->prev = NULL;

  // previous of head (now head is the second node) is newNode
  if ((*head) != NULL)
    (*head)->prev = newNode;

  // head points to newNode
  (*head) = newNode;
}

// insert a node after a specific node
void insertAfter(struct Node* prev_node, int data) {
  // check if previous node is null
  if (prev_node == NULL) {
    printf("previous node cannot be null");
    return;
  }

  // allocate memory for newNode
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

  // assign data to newNode
  newNode->data = data;

  // set next of newNode to next of prev node
  newNode->next = prev_node->next;

  // set next of prev node to newNode
  prev_node->next = newNode;

  // set prev of newNode to the previous node
  newNode->prev = prev_node;

  // set prev of newNode's next to newNode
  if (newNode->next != NULL)
    newNode->next->prev = newNode;
}

// insert a newNode at the end of the list
void insertEnd(struct Node** head, int data) {
  // allocate memory for node
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

  // assign data to newNode
  newNode->data = data;

  // assign null to next of newNode
  newNode->next = NULL;

  // store the head node temporarily (for later use)
  struct Node* temp = *head;

  // if the linked list is empty, make the newNode as head node
  if (*head == NULL) {
    newNode->prev = NULL;
    *head = newNode;
    return;
  }

  // if the linked list is not empty, traverse to the end of the linked list
  while (temp->next != NULL)
    temp = temp->next;

  // now, the last node of the linked list is temp

  // assign next of the last node (temp) to newNode
  temp->next = newNode;

  // assign prev of newNode to temp
  newNode->prev = temp;
}

// delete a node from the doubly linked list
void deleteNode(struct Node** head, struct Node* del_node) {
  // if head or del is null, deletion is not possible
  if (*head == NULL || del_node == NULL)
    return;

  // if del_node is the head node, point the head pointer to the next of del_node
  if (*head == del_node)
    *head = del_node->next;

  // if del_node is not at the last node, point the prev of node next to del_node to the previous of del_node
  if (del_node->next != NULL)
    del_node->next->prev = del_node->prev;

  // if del_node is not the first node, point the next of the previous node to the next node of del_node
  if (del_node->prev != NULL)
    del_node->prev->next = del_node->next;

  // free the memory of del_node
  free(del_node);
}

// print the doubly linked list
void displayList(struct Node* node) {
  struct Node* last;

  while (node != NULL) {
    printf("%d->", node->data);
    last = node;
    node = node->next;
  }
  if (node == NULL)
    printf("NULL\n");
}

int main() {
  // initialize an empty node
  struct Node* head = NULL;

  insertEnd(&head, 5);
  insertFront(&head, 1);
  insertFront(&head, 6);
  insertEnd(&head, 9);

  // insert 11 after head
  insertAfter(head, 11);

  // insert 15 after the seond node
  insertAfter(head->next, 15);

  displayList(head);

  // delete the last node
  deleteNode(&head, head->next->next->next->next->next);

  displayList(head);
}

Output

6->11->15->1->5->9->NULL
6->11->15->1->5->NULL

Md. Anisur Rahman C Programming Lab Manual, Data Structure And Algorithm

C Programming Lab Manual – 61

Write a C program for Singly Linked List Operations.

Algorithm
// Create a Pointer
struct Node 
  int data;
  struct Node* next;
// Insert at the beginning
 set the data of the new node to new_data
  set the next pointer of the new node to the current head
  set the head_ref to the new node
// Insert a node after a node
  set the data of the new node to new_data
  set the next pointer of the new node to the next node of prev_node
  set the next pointer of prev_node to the new node
// Insert at the end
  set the data of the new node to new_data
  set the next pointer of the new node to null
  set the next pointer of last to the new node
//Delete a node
  set temp to head_ref
  set prev to null
    free the memory of temp
    return
set the next pointer of prev to the next pointer of temp
  free the memory of temp
// Sort the linked list
set index to the next node of current
 swap the data of current and index
set index to the next node of index
set current to the next node of current
// Print the linked list
print the data of node
 set node to the next node of node
//function main()
  set head to null
  print "Linked list: "
  printList(head)
  print "After deleting an element: "
  deleteNode(head, 3)
  printList(head)
  Link a node when deletion
  Delete Node
 print "Sorted List: "

Figure: Linked List Operations

C Programming Code

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

// Create a node
struct Node {
  int data;
  struct Node* next;
};

// Insert at the beginning
void insertAtBeginning(struct Node** head_ref, int new_data) {
  // Allocate memory to a node
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  // Insert the data
  new_node->data = new_data;

  // Set the next pointer of the new node to the current head
  new_node->next = (*head_ref);

  // Move head to the new node
  (*head_ref) = new_node;
}

// Insert a node after a given node
void insertAfter(struct Node* prev_node, int new_data) {
  // Check if the previous node is NULL
  if (prev_node == NULL) {
    printf("The given previous node cannot be NULL");
    return;
  }

  // Allocate memory to a new node
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  // Insert the data
  new_node->data = new_data;

  // Adjust the pointers to insert the new node
  new_node->next = prev_node->next;
  prev_node->next = new_node;
}

// Insert at the end
void insertAtEnd(struct Node** head_ref, int new_data) {
  // Allocate memory to a new node
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  // Assign the data to the new node
  new_node->data = new_data;

  // Set the next pointer of the new node to NULL
  new_node->next = NULL;

  // Check if the linked list is empty
  if (*head_ref == NULL) {
    // If the linked list is empty, make the new node the head
    *head_ref = new_node;
    return;
  }

  // Traverse to the last node
  struct Node* last = *head_ref;
  while (last->next != NULL)
    last = last->next;

  // Set the next pointer of the last node to the new node
  last->next = new_node;
}

// Delete a node
void deleteNode(struct Node** head_ref, int key) {
  // Store the head node
  struct Node* temp = *head_ref;
  struct Node* prev = NULL;

  // Check if the head node itself holds the key
  if (temp != NULL && temp->data == key) {
    // Change the head
    *head_ref = temp->next;

    // Free the old head
    free(temp);
    return;
  }

  // Search for the key to be deleted
  while (temp != NULL && temp->data != key) {
    prev = temp;
    temp = temp->next;
  }

  // If the key was not present in the linked list
  if (temp == NULL)
    return;

  // Unlink the node from the linked list
  prev->next = temp->next;

  // Free the memory allocated for the node
  free(temp);
}

// Search for a node
int searchNode(struct Node** head_ref, int key) {
  // Start from the head node
  struct Node* current = *head_ref;

  // Traverse the linked list
  while (current != NULL) {
    // If the key is found, return 1
    if (current->data == key)
      return 1;

    // Move to the next node
    current = current->next;
  }

  // Key not found
  return 0;
}

// Sort the linked list in ascending order
void sortLinkedList(struct Node** head_ref) {
  // Initialize current and index nodes
  struct Node* current = *head_ref;
  struct Node* index = NULL;

  // Temporary variable for swapping data
  int temp;

  // Check if the linked list is empty or has only one node
  if (head_ref == NULL)
    return;

  // Perform bubble sort on the linked list
  while (current != NULL) {
    // Set the index node to the node next to the current node
    index = current->next;

    while (index != NULL) {
      // Swap the data if the current node's data is greater than the index node's data
      if (current->data > index->data) {
        temp = current->data;
        current->data = index->data;
        index->data = temp;
      }

      // Move to the next index node
      index = index->next;
    }

    // Move to the next current node
    current = current->next;
  }
}

// Print the linked list
void printList(struct Node* node) {
  while (node != NULL) {
    printf(" %d ", node->data);
    node = node->next;
  }
}

// Driver program
int main() {
  // Initialize the head node
  struct Node* head = NULL;

  // Insert nodes into the linked list
  insertAtEnd(&head, 1);
  insertAtBeginning(&head, 2);
  insertAtBeginning(&head, 3);
  insertAtEnd(&head, 4);
  insertAfter(head->next, 5);

  printf("Linked list: ");
  printList(head);

  printf("\nAfter deleting an element: ");
  deleteNode(&head, 3);
  printList(head);

  int item_to_find = 3;
  if (searchNode(&head, item_to_find)) {
    printf("\n%d is found", item_to_find);
  } else {
    printf("\n%d is not found", item_to_find);
  }

  // Sort the linked list
  sortLinkedList(&head);
  printf("\nSorted List: ");
  printList(head);

  return 0;
}

Output

Linked list:  3  2  5  1  4 
After deleting an element:  2  5  1  4 
3 is not found
Sorted List:  1  2  4  5

Md. Anisur Rahman C Programming Lab Manual, Data Structure And Algorithm

C Programming Lab Manual – 60

Write a C program for Circular Queue Implementation.

Algorithm
#define MAX_SIZE 5 

int a[MAX_SIZE];
int front = -1;
int rear = -1;

void enqueue(int x)
if (front == -1 && rear == -1)
front = rear = 0;

else
rear = (rear + 1) % MAX_SIZE;
a[rear] = x;


void dequeue()
if (front == -1 && rear == -1)
printf("queue is empty \n");
return;

else if (front == rear)
front = rear = -1;
else
front = (front + 1) % MAX_SIZE;
Figure: Circular Queue Implementation
C Programming Code

// Circular Queue implementation in C

#include <stdio.h>


int items[5];
int front = -1, rear = -1;

// Check if the queue is full
int isFull() {
  if ((front == rear + 1) || (front == 0 && rear == 5 - 1)) 
return 1;
  return 0;
}

// Check if the queue is empty
int isEmpty() {
  if (front == -1) return 1;
  return 0;
}

// Adding an element
void enQueue(int element) {
  if (isFull())
    printf("\n Queue is full!! \n");
  else {
    if (front == -1) front = 0;
    rear = (rear + 1) % 5;
    items[rear] = element;
    printf("\n Inserted -> %d", element);
  }
}

// Removing an element
int deQueue() {
  int element;
  if (isEmpty()) {
    printf("\n Queue is empty !! \n");
    return (-1);
  } else {
    element = items[front];
    if (front == rear) {
      front = -1;
      rear = -1;
    } 
    // Q has only one element, so we reset the 
    // queue after dequeing it. ?
    else {
      front = (front + 1) % 5;
    }
    printf("\n Deleted element -> %d \n", element);
    return (element);
  }
}

// Display the queue
void display() {
  int i;
  if (isEmpty())
    printf(" \n Empty Queue\n");
  else {
    printf("\n Front -> %d ", front);
    printf("\n Items -> ");
    for (i = front; i != rear; i = (i + 1) % 5) {
      printf("%d ", items[i]);
    }
    printf("%d ", items[i]);
    printf("\n Rear -> %d \n", rear);
  }
}

int main() {
    //!showArray(items)

  deQueue();
  enQueue(1);
  enQueue(2);
  enQueue(3);
  enQueue(4);
  enQueue(5);
  enQueue(6);
  display();
  deQueue();
  display();
  enQueue(7);
  display();
  enQueue(8);

  return 0;
}

Output

Queue is empty !! 

 Inserted -> 1
 Inserted -> 2
 Inserted -> 3
 Inserted -> 4
 Inserted -> 5
 Queue is full!! 

 Front -> 0 
 Items -> 1 2 3 4 5 
 Rear -> 4 

 Deleted element -> 1 

 Front -> 1 
 Items -> 2 3 4 5 
 Rear -> 4 

 Inserted -> 7
 Front -> 1 
 Items -> 2 3 4 5 7 
 Rear -> 0 

 Queue is full!!

Md. Anisur Rahman C Programming Lab Manual, Data Structure And Algorithm

C Programming Lab Manual – 59

Write a C program for Queue Implementation.

Algorithm
FUNCTION is_full(front, rear)
    IF (rear + 1) MOD MAX_SIZE == front THEN
    	RETURN True    	
    ELSE
        RETURN False
    ENDIF
ENDFUNCTION 


FUNCTION enqueue(queue, front, rear, data)
    IF is_full(front, rear) == True THEN
        PRINT("Queue is full")
    ELSE
        rear = (rear + 1) MOD MAX_SIZE
    	queue[rear] = data
        IF front = -1 THEN // First item to be queued
            front = 0
        ENDIF
    ENDIF
    RETURN (front, rear)
ENDFUNCTION

FUNCTION dequeue(queue, front, rear)
    IF is_empty(rear) == True THEN
	PRINT("Queue is empty - nothing to dequeue")
        dequeued_item = Null
    ELSE
        dequeued_item = queue[front]
        // Check if the queue is empty
        IF front == rear THEN
            front = -1
            rear = -1
        ELSE
            front = (front + 1) MOD maxsize 
        ENDIF
    ENDIF
    RETURN (dequeued_item, front, rear)
ENDFUNCTION

Figure: Queue Implementation
C Programming Code

#include <stdio.h>

int queue[4];
int front = -1;
int rear = -1;

void enqueue(int value) {
    if (rear == 4 - 1) {
        printf("Queue is full. Cannot enqueue.\n");
        return;
    }
    if (front == -1)
        front = 0;
    rear++;
    queue[rear] = value;
}

void dequeue() {
    if (front == -1 || front > rear) {
        printf("Queue is empty. Cannot dequeue.\n");
        return;
    }
    front++;
}

int getFront() {
    if (front == -1 || front > rear) {
        printf("Queue is empty. No front element.\n");
        return -1;
    }
    return queue[front];
}

int isEmpty() {
    if (front == -1 || front > rear)
        return 1;
    else
        return 0;
}

int getSize() {
    if (front == -1)
        return 0;
    else
        return rear - front + 1;
}

void display() {
    if (front == -1 || front > rear) {
        printf("Queue is empty. Nothing to display.\n");
        return;
    }
    printf("Queue elements: ");
    for (int i = front; i <= rear; i++)
        printf("%d ", queue[i]);
    printf("\n");
}

int main() {
    //!showArray(queue)
    enqueue(10);
    display();
    enqueue(20);
    display();
    enqueue(30);
    display();
    enqueue(40);
    display();
    enqueue(50);
    display(); 
    printf("Front element: %d\n", getFront()); 
    printf("Queue size: %d\n", getSize()); 
    printf("Is queue empty? %s\n", isEmpty() ? "Yes" : "No");
    dequeue();
    display(); 
    dequeue();
    display(); 
    dequeue();
    display();
    dequeue();
    display();
    dequeue();
    return 0;
}

Output

Queue elements: 10 
Queue elements: 10 20 
Queue elements: 10 20 30 
Queue elements: 10 20 30 40 
Queue is full. Cannot enqueue.
Queue elements: 10 20 30 40 
Front element: 10
Queue size: 4
Is queue empty? No
Queue elements: 20 30 40 
Queue elements: 30 40 
Queue elements: 40 
Queue is empty. Nothing to display.
Queue is empty. Cannot dequeue.

Md. Anisur Rahman C Programming Lab Manual, Data Structure And Algorithm

C Programming Lab Manual – 58

Write a C program for Stack Implementation.

Algorithm

Figure: Stack Implementation
C Programming Code

#include <stdio.h>

int stack[4];
int top = -1;

void push(int element) {
    if (top == 4 - 1) {
        printf("Stack Overflow\n");
    } else {
        stack[++top] = element;
        printf("Pushed is: %d \n", element);
    }
}

void pop() {
    if (top == -1) {
        printf("Stack Underflow\n");
    } else {
        printf("Popped is: %d \n", stack[top--]);
    }
}

int peek() {
    if (top == -1) {
        printf("Stack is empty\n");
        return -1;
    } else {
        return stack[top];
    }
}

int main() {
    //!showArray(stack)
    push(10);
    push(20);
    push(30);
    push(40);
    push(50);
    printf("Top Element is: %d\n", peek());
    pop();
    pop();
    pop();
    pop();
    pop();
    printf("Top Element is: %d\n", peek());
    return 0;
}

Output

Pushed is: 10 
Pushed is: 20 
Pushed is: 30 
Pushed is: 40 
Stack Overflow
Top Element is: 40
Popped is: 40 
Popped is: 30 
Popped is: 20 
Popped is: 10 
Stack Underflow
Stack is empty
Top Element is:-1

Md. Anisur Rahman C Programming Lab Manual, Data Structure And Algorithm

C Programming Lab Manual – 57

Write a C program for Ternary Search.

Algorithm
double ternary_search(double l, double r) {
    double eps = 1e-9;              //set the error limit here
    while (r - l > eps) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        double f1 = f(m1);      //evaluates the function at m1
        double f2 = f(m2);      //evaluates the function at m2
        if (f1 < f2)
            l = m1;
        else
            r = m2;
    }
    return f(l);                    //return the maximum of f(x) in [l, r]
}

Figure: Ternary Search
C Programming Code

#include <stdio.h>

int ternarySearch(int l, int r, int key, int ar[])
{
	if (r >= l) {

		// Find the mid1 and mid2
		int mid1 = l + (r - l) / 3;
		int mid2 = r - (r - l) / 3;

		// Check if key is present at any mid
		if (ar[mid1] == key) {
			return mid1;
		}
		if (ar[mid2] == key) {
			return mid2;
		}

	

		if (key < ar[mid1]) {

			// The key lies in between l and mid1
			return ternarySearch(l, mid1 - 1, key, ar);
		}
		else if (key > ar[mid2]) { 

			// The key lies in between mid2 and r
			return ternarySearch(mid2 + 1, r, key, ar);
		}
		else {

			// The key lies in between mid1 and mid2
			return ternarySearch(mid1 + 1, mid2 - 1, key, ar);
		}
	}

	// Key not found
	return -1;
}

// Driver code
int main()
{
    //!showArray(ar)
	int l, r, p, key;

	// Get the array
	// Sort the array if not sorted
	int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	// Starting index
	l = 0;

	// end element index
	r = 9;

	// Checking for 5

	// Key to be searched in the array
	key = 5;

	// Search the key using ternarySearch
	p = ternarySearch(l, r, key, ar);

	// Print the result
	printf("Index of %d is %d\n", key, p);

	// Checking for 50

	// Key to be searched in the array
	key = 50;

	// Search the key using ternarySearch
	p = ternarySearch(l, r, key, ar);

	// Print the result
	printf("Index of %d is %d", key, p);
}

Output

Index of 5 is 4
Index of 50 is -1

Md. Anisur Rahman C Programming Lab Manual, Data Structure And Algorithm

C Programming Lab Manual – 56

Write a C program for Binary Search.

Algorithm
Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure
Figure: Binary Search
C Programming Code

#include <stdio.h>
int binarySearch(int [], int, int, int);

int main()
{
    //!showArray(array)
  int array[10], c, first, last, n, search,  index;

  printf("Enter number of elements\n");
  scanf("%d", &n);

  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++)
    scanf("%d", &array[c]);

  printf("Enter value to find\n");
  scanf("%d", &search);

  first = 0;
  last = n - 1;

  index = binarySearch(array, first, last, search);
 
  if (index == -1)
    printf("Not found! %d isn't present in the list.\n", search);
  else
    printf("%d is present at location %d.\n", search, index + 1);
 
  return 0;
} 

int binarySearch(int a[], int s, int e, int f) {
  int m;
 
  if (s > e) // Not found
     return -1;

  m = (s + e)/2;

  if (a[m] == f)  // element found
    return m;
  else if (f > a[m])  
    return binarySearch(a, m+1, e, f);
  else
    return binarySearch(a, s, m-1, f);
}

Output

Enter number of elements
5
Enter 5 integers
1
2
3
4
5
Enter value to find
5
5 is present at location 5.

Md. Anisur Rahman C Programming Lab Manual, Data Structure And Algorithm

C Programming Lab Manual – 55

Write a C program for Linear Search.

Algorithm

procedure linear_search (list, value)

   for each item in the list
      if match item == value
         return the item's location
      end if
   end for

end procedure
Figure: Linear Search
C Programming Code

#include <stdio.h>
 
int linear_search(int [], int, int);
 
int main()
{
    //!showArray(array)
int array[10], search, c, n, position;
 
   printf("Input number of elements in array\n");
   scanf("%d", &n);
 
   printf("Input %d numbers\n", n);
 
   for (c = 0; c < n; c++)
      scanf("%d", &array[c]);
 
   printf("Input a number to search\n");
   scanf("%d", &search);
 
   position = linear_search(array, n, search);
 
   if (position == -1)
      printf("%d isn't present in the array.\n", search);
   else
      printf("%d is present at location %d.\n", search, position+1);
 
   return 0;
}
 
int linear_search(int a[], int n, int find) {
int c;
 
   for (c = 0 ;c < n ; c++ ) {
      if (a[c] == find)
         return c;
   }
 
   return -1;
}

Output

Input number of elements in array
5
Input 5 numbers
5
4
3
2
1
Input a number to search
1
1 is present at location 5.

Md. Anisur Rahman C Programming Lab Manual, Data Structure And Algorithm

C Programming Lab Manual – 54

Write a C program for Marge Sort.

Algorithm
MergeSort(A,p,r):

	if p < r
  q = ⌊ (p+r)/2 ⌋
	 MergeSort(A,p,q)
	 MergeSort(A,q+1,r)
	 Merge(A,p,q,r)

Merge(A,p,q,r):

	n1 = q - p + 1
	n2 = r - q
	let L, R be new arrays
	for i = 1 to n1
	 L[i] = A[p+i-1]
	for j = 1 to n2
	 R[j] = A[q+j]
	L[n1+1] = ∞
	R[n2+1] = ∞
	i = 1
	j = 1
	for k = p to r
	 if L[i] ≤ R[j]
	 A[k] = L[i]
	 i = i + 1
	 else
	 A[k] = R[j]
	 j = j + 1

Figure: Marge Sort
C Programming Code

#include <stdio.h>

void merge_sort(int i, int j, int a[], int aux[]) {
    if (j <= i) {
        return;
    }
    int mid = (i + j) / 2;

    merge_sort(i, mid, a, aux);
    merge_sort(mid + 1, j, a, aux);
    int pointer_left = i;
    int pointer_right = mid + 1;
    int k;

    for (k = i; k <= j; k++) {
        if (pointer_left == mid + 1) {
            aux[k] = a[pointer_right];
            pointer_right++;
        } else if (pointer_right == j + 1) {
            aux[k] = a[pointer_left];
            pointer_left++;
        } else if (a[pointer_left] < a[pointer_right]) {
            aux[k] = a[pointer_left];
            pointer_left++;
        } else {
            aux[k] = a[pointer_right];
            pointer_right++;
        }
    }

    for (k = i; k <= j; k++) {
        a[k] = aux[k];
    }
}

int main() {
    //!showSort(a)
    int a[5], aux[5], n, i;
    printf("Enter number of elements in the array:\n");
    scanf("%d", &n);
    printf("Enter %d integers\n", n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);

    merge_sort(0, n - 1, a, aux);

    printf("Printing the sorted array:\n");
    for (i = 0; i < n; i++)
        printf("\t%d", a[i]);

    return 0;
}

Output

Enter number of elements in the array:
5
Enter 5 integers
5
4
3
2
1
Printing the sorted array:
	1	2	3	4	5