Data Structures | Sample Programs
Brief:
This file contains standard header files, macros, structure definition and function prototypes required for single linked list.
Header File:
/*-----------------------------------------------------------------------------------------------
* Author : Emertxe (https://emertxe.com)
* Date : Mon 20 Mar 2017 9:05:30 IST
* File : sll.h
* Title : Header file
* Description : This file contains standard header files, macros, structure definition and
* function prototypes required for single linked list
*---------------------------------------------------------------------------------------------*/
#ifndef SLL_H
#define SLL_H
#include <stdio.h>
#include <stdlib.h>
#define SUCCESS 0
#define FAILURE -1
typedef int data_t;
typedef struct node
{
data_t data;
struct node *link;
}Slist;
int select_operation();
int insert_at_last(Slist **head, data_t data);
void print_list(Slist *head);
int delete_at_first(Slist **head);
#endifBrief:
This function acts like a driver function, it is user interactive.
Driver Function:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 20 Mar 2017 9:05:30 IST
* File : main.c
* Title : Driver function
* Description : This function acts like a driver function, it is user interactive.
*------------------------------------------------------------------------------------------*/
#include "sll.h"
int main()
{
system("clear");
Slist *head = NULL;
int choice;
int num;
char option;
do
{
choice = select_operation();
switch (choice)
{
case 1: //read element which needs to be inserted at last
printf("Enter the number to insert at last: ");
scanf("%d", &num);
//call the function to insert element in last
if (insert_at_last(&head, num) == FAILURE)
{
printf("Failed: Inserting the new data at lastn");
printf("Try again...n");
}
else
{
printf("Success: Element inserted at lastn");
}
break;
case 2: //call the function to print the list
print_list(head);
break;
case 3: //Call the function to delete first element in the list
if (delete_at_first(&head) == FAILURE)
{
printf("Failed: Inserting the new data at lastn");
printf("Try again...n");
}
else
{
printf("Success: First element deleted from the listn");
}
break;
default: printf("Invalid inputn");
}
printf("Press [y] to continue: ");
scanf("n%c", &option);
}while (option == 'y');
return 0;
}
int select_operation(void)
{
int choice;
//read choice from user
printf("1.Insert at lastn");
printf("2.Print listn");
printf("3.Delete at firstn");
printf("Select an option: ");
scanf("%d", &choice);
return choice;
}Brief:
This function inserts the new node at the end of the existing single linked list..
Insert the node to the last:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 20 Mar 2017 9:05:30 IST
* File : insert_at_last.c
* Title : Function to insert the node to the last
* Description : This function inserts the new node at the end of the existing
* single linked list.
*------------------------------------------------------------------------------------------*/
#include "sll.h"
int insert_at_last(Slist **head, data_t data)
{
/* Creating the new node */
Slist *new = malloc(sizeof(Slist));
/* Check whether new node created or not */
if (new == NULL)
{
return FAILURE;
}
/* Fill the data and link parts of the node */
new->data = data;
new->link = NULL;
/* If list is empty */
if (*head == NULL)
{
*head = new;
return SUCCESS;
}
/* If list is non-empty, traverse till the last node */
Slist *temp = *head;
while (temp->link)
{
temp = temp->link;
}
/* Establish link */
temp->link = new;
return SUCCESS;
}Brief:
This function deletes the first node existing single linked list.
Delete the node in the beginning:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 20 Mar 2017 9:05:30 IST
* File : delete_at_first.c
* Title : Function to delete the node in the begining
* Description : This function deletes the first node existing single linked list.
*------------------------------------------------------------------------------------------*/
#include "sll.h"
int delete_at_first(Slist **head)
{
/* Check whether list is empty or not */
if (*head == NULL)
{
/* If Empty */
return FAILURE;
}
/* If non-empty */
/* Update head to next node & free the first node */
Slist *temp = *head;
*head = (*head)->link;
free(temp);
return SUCCESS;
}
Brief:
This function prints the data in the list by traversing first node to the last node.
Print the list:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 20 Mar 2017 9:05:30 IST
* File : print_list.c
* Title : Function to print the list
* Description : This function prints the data in the list by traversing first node to
* the last node.
*------------------------------------------------------------------------------------------*/
#include "sll.h"
void print_list(Slist *head)
{
if (head == NULL)
{
printf("List is Emptyn");
}
else
{
while (head)
{
printf("%d ", head->data);
head = head->link;
}
printf("n");
}
}Make File:
SRC:=$(wildcard *.c)
OBJ:=$(patsubst *.c, *.o, $(SRC))
CC:=gcc
sll.exe: $(OBJ)
gcc -o $@ $^
clean:
rm *.o *.exeSteps to run the program:
Step-1: Run the Makefile present the same directory
$make
Step-2: Run the executable file
$./sll.exe
Example output 1: Compiling the Program
Example output 2:
Brief:
This file contains standard header files, macros, structure definition and function prototypes required for single linked list.
Header File:
#ifndef SLL_H
#define SLL_L
#include <stdio.h>
#include <stdlib.h>
#define SUCCESS 0
#define FAILURE -1
typedef int data_t;
typedef struct node
{
data_t data;
struct node *link;
}Slist;
int select_operation();
int insert_at_first(Slist **head, data_t data);
void print_list(Slist *head);
int delete_at_last(Slist **head);
#endifBrief:
This function acts like a driver function, it is user interactive.
Driver Function:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Tue 21 Mar 2017 4:50:34 IST
* File : main.c
* Title : Driver function
* Description : This function acts like a driver function, it is user interactive.
*------------------------------------------------------------------------------------------*/
#include "sll.h"
int main()
{
system("clear");
Slist *head = NULL;
int choice;
int num;
char option;
do
{
choice = select_operation();
switch (choice)
{
case 1:
printf("Enter the number to insert at first: ");
scanf("%d", &num);
if (insert_at_first(&head, num) == FAILURE)
{
printf("Failed: Inserting the new data at firstn");
printf("Try again...n");
}
else
{
printf("Success: Element is inserted at firstn");
}
break;
case 2:
print_list(head);
break;
case 3:
if (delete_at_last(&head) == FAILURE)
{
printf("Failed: Deleting the new data at lastn");
printf("Try again...n");
}
else
{
printf("Success: Last element in the list is deletedn");
}
}
printf("Press [y] to continue: ");
scanf("n%c", &option);
}while (option == 'y');
return 0;
}
int select_operation(void)
{
int choice;
printf("1.Insert at firstn");
printf("2.Print listn");
printf("3.Delete at lastn");
printf("Select an Option: ");
scanf("%d", &choice);
return choice;
}Brief:
This function is the template, where some parts of the code are missing needs to filled. In the code below, you can see the lines with TODO which needs to be updated with the code.
Insert the new node in the beginning:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Tue 21 Mar 2017 4:50:34 IST
* File : insert_at_first.c
* Title : Function insert the new node in the begining
* Description : This function is the template, where some parts of the code are missing
* needs to filled. In the code below, you can see the lines with TODO which
* needs to be updated with the code.
*------------------------------------------------------------------------------------------*/
#include "sll.h"
int insert_at_first(Slist **head, data_t data)
{
/* Creating the new node */
Slist *new = malloc(sizeof(Slist));
/* Check whether new node created or not */
if (new == NULL)
{
return FAILURE;
}
/* Fill the parts of the node */
new->data = data;
new->link = NULL;
/* If list is empty */
if (*head == NULL)
{
*head = new;
return SUCCESS;
}
/* List is non-empty */
new->link = *head;
*head = new;
return SUCCESS;
}Brief:
This function is the template, where some parts of the code are missing needs to filled. In the code below, you can see the lines with TODO which needs to be updated with the code.
Delete the node present at the last:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Tue 21 Mar 2017 4:50:34 IST
* File : delete_at_last.c
* Title : Function to delete the node present at the last
* Description : This function is the template, where some parts of the code are missing
* needs to filled. In the code below, you can see the lines with TODO
* which needs to be updated with the code.
*------------------------------------------------------------------------------------------*/
#include "sll.h"
int delete_at_last(Slist **head)
{
/* Check whether list is empty or not */
if (*head == NULL)
{
/* If Empty */
return FAILURE;
}
/* If non-empty */
/* If list has only one node */
if ((*head)->link == NULL)
{
free(*head);
*head = NULL;
return SUCCESS;
}
/* If list has more than one node */
Slist *temp = *head;
Slist *prev = NULL;
while (temp->link != NULL)
{
prev = temp;
temp = temp->link;
}
free(temp);
prev->link = NULL;
return SUCCESS;
}Brief:
This function prints the data in the list by traversing first node to the last node.
Print the list:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Tue 21 Mar 2017 4:50:34 IST
* File : print_list.c
* Title : Function to print the list
* Description : This function prints the data in the list by traversing first node to
* the last node.
*------------------------------------------------------------------------------------------*/
#include "sll.h"
void print_list(Slist *head)
{
if (head == NULL)
{
printf("List is Emptyn");
}
else
{
while (head)
{
printf("%d ", head->data);
head = head->link;
}
printf("n");
}
}Make File:
SRC:=$(wildcard *.c)
OBJ:=$(patsubst *.c, *.o, $(SRC))
CC:=gcc
sll.exe: $(OBJ)
$(CC) -o $@ $^
clean:
rm *.exe
~ Steps to run the program:
Step-1: Run the Makefile present the same directory
$make
Step-2: Run the executable file
$./sll.exe
Example output 1: Compiling the Program
Example output 2:
Brief:
This file contains standard header files, macros, structure definition and function prototypes required for single linked list.
Header File:
/*-----------------------------------------------------------------------------------------------
* Author : Emertxe (https://emertxe.com)
* Date : Mon 20 Mar 2017 9:05:30 IST
* File : sll.h
* Title : Header file
* Description : This file contains standard header files, macros, structure definition and
* function prototypes required for single linked list
*----------------------------------------------------------------------------------------------*/
#ifndef SLL_H
#define SLL_H
#include <stdio.h>
#include <stdlib.h>
#define SUCCESS 0
#define FAILURE -1
#define LIST_EMPTY 2
#define ELEMENT_NOT_FOUND 3
typedef int data_t;
typedef struct node
{
data_t data;
struct node *link;
}Slist;
int delete_list(Slist **head);
int find_node(Slist *head, data_t key);
int insert_at_first(Slist **head, data_t data);
void print_list(Slist *head);
#endifBrief:
This function acts like a driver function, it is user interactive.
Driver Function:
/*-----------------------------------------------------------------------------------------------
* Author : Emertxe (https://emertxe.com)
* Date : Mon 20 Mar 2017 9:05:30 IST
* File : main.c
* Title : Driver function
* Description : This function acts like a driver function, it is user interactive.
*----------------------------------------------------------------------------------------------*/
#include <stdio.h>
#include "sll.h"
int main()
{
// Declare local variables
Slist *head = NULL;
int op, num, g_data, n_data;
char ch;
system("clear");
do
{
// Read input from user
printf("1. Insert at firstn2. Find noden3. Delete listn4. Printn");
printf("Select an Option: ");
scanf("%d", &op);
switch(op)
{
case 1:
printf("Enter the number: ");
scanf("%d", &num);
// Function call
if (insert_at_first(&head, num) == FAILURE)
{
printf("Failed: Inserting the new data at firstn");
}
else
{
printf("Success: Element inserted into listn");
}
break;
case 2:
printf("Enter the element to found: ");
scanf("%d", &g_data);
// Function call
if (find_node(head, g_data) == SUCCESS)
{
printf("Success: Finding noden");
}
else
{
printf("Failure: Element not foundn");
}
break;
case 3:
// Function call
if (delete_list(&head) == LIST_EMPTY)
{
printf("Failure: List is emptyn");
}
else
{
printf("Success: List is deletedn");
}
break;
case 4:
// Function call
print_list(head);
break;
default:
printf("Invalid Inputn");
}
printf("Press [y] to continue: ");
scanf(" %c", &ch);
}while (ch == 'y');
return 0;
}Brief:
This function finds whether the given key is present in the list or not, if present it will return the address of the node where the key is found.
Find the node:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Wed 22 Mar 2017 5:30:17 IST
* File : find_node.c
* Title : Function to find the key
* Description : This function finds whether the given key is present in the list or not,
* if present it will return the address of the node where the key is found.
*------------------------------------------------------------------------------------------*/
#include "sll.h"
int find_node(Slist *head, data_t key)
{
/*
TODO:
1. Find the first node with key as data part by traversing the list
2. Return macro to indicate the presence or absence of that particular node
*/
if (head == NULL)
{
return LIST_EMPTY;
}
Slist *temp = head;
while (temp)
{
if (temp->data == key)
{
return SUCCESS;
}
temp = temp->link;
}
return ELEMENT_NOT_FOUND;
}Brief:
This function deletes all the nodes present in the list, finally the head will be updated to NULL.
Delete the complete list:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Wed 22 Mar 2017 5:24:07 IST
* File : delete_list.c
* Title : Function to delete the complete list
* Description : This function deletes all the nodes present in the list, finally the
* head will be updated to NULL.
*------------------------------------------------------------------------------------------*/
#include "sll.h"
int delete_list(Slist **head)
{
/*
TODO:
1. Free all nodes
2. Update head to NULL
*/
if (*head == NULL)
return LIST_EMPTY;
Slist *temp = *head;
Slist *prev = NULL;
while (temp->link != NULL)
{
prev = temp;
*head = temp->link;
temp->link = NULL;
temp = *head;
free(prev);
}
free(temp);
*head = NULL;
return SUCCESS;
}Brief:
This function is the template, where some parts of the code are missing needs to filled. In the code below, you can see the lines with TODO which needs to be updated with the code.
Insert at first:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Tue 21 Mar 2017 4:44:30 IST
* File : insert_at_first.c
* Title : Function insert the new node in the begining
* Description : This function is the template, where some parts of the code are missing
* needs to filled. In the code below, you can see the lines with TODO which
* needs to be updated with the code.
*------------------------------------------------------------------------------------------*/
#include "sll.h"
int insert_at_first(Slist **head, data_t data)
{
/* Creating the new node */
Slist *new = malloc(sizeof(Slist));
/* Check whether new node created or not */
if (new == NULL)
{
return FAILURE;
}
/* Fill the parts of the node */
new->data = data;
new->link = NULL;
/* If list is empty */
if (*head == NULL)
{
*head = new;
return SUCCESS;
}
/* List is non-empty */
new->link = *head;
*head = new;
return SUCCESS;
}Steps to compile and run the program:
After Implementing
– find node
– Delete list
functions
- Integrate these two function with functions available in the Template folder.
- Run the Makefile
- Test it.
Example output 1: Compiling the Program
Example output 1: Compiling the Program
Brief:
This file contains standard header files, macros, structure definition and function prototypes required for double linked list.
Header File:
#ifndef DLL_H
#define DLL_H
#include <stdio.h>
#include <stdlib.h>
#define SUCCESS 0
#define FAILURE -1
#define LIST_EMPTY -2
typedef int data_t;
typedef struct node
{
struct node *l_link;
data_t data;
struct node *r_link;
}Dlist;
int dl_insert_at_last(Dlist **head, Dlist **tail, data_t data);
int dl_delete_at_first(Dlist **head, Dlist **tail);
void dl_print_list(Dlist *head);
int select_operation();
#endifBrief:
This function acts like a driver function, it is user interactive.
Driver Function:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 27 Mar 2017 3:20:30 IST
* File : main.c
* Title : Driver function
* Description : This function acts like a driver function, it is user interactive.
*------------------------------------------------------------------------------------------*/
#include "dll.h"
int main()
{
Dlist *head, *tail;
head = tail = NULL;
int choice;
int num;
char option;
system("clear");
do
{
choice = select_operation();
switch (choice)
{
case 1:
printf("Enter the number to insert at last: ");
scanf("%d", &num);
if (dl_insert_at_last(&head, &tail, num) == SUCCESS)
{
printf("Success: Element inserted at lastn");
}
else
{
printf("Failed: Inserting the new data at lastn");
printf("Try again...n");
}
break;
case 2:
dl_print_list(head);
break;
case 3:
if (dl_delete_at_first(&head, &tail) == FAILURE)
{
printf("Failed: Inserting the new data at lastn");
printf("Try again...n");
}
else
{
printf("Success: First element deleted from the listn");
}
break;
default: printf("Invalid optionn");
}
printf("Press [y] to continue: ");
scanf("n%c", &option);
}while (option == 'y');
return 0;
}
int select_operation()
{
int choice;
printf("1.Insert at lastn");
printf("2.Print listn");
printf("3.Delete at firstn");
printf("Select an Option: ");
scanf("%d", &choice);
return choice;
}Brief:
This function inserts the new node at the end of the existing double linked list..
Insert the node to the last:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 27 Mar 2017 2:59:00 IST
* File : dl_insert_at_last.c
* Title : Function to insert the node to the last
* Description : This function inserts the new node at the end of the existing
* double linked list.
*------------------------------------------------------------------------------------------*/
#include "dll.h"
int dl_insert_at_last(Dlist **head, Dlist **tail, data_t data)
{
/* Creating the new node */
Dlist *new = malloc(sizeof(Dlist));
/* Check whether new node created or not */
if (new == NULL)
{
return FAILURE;
}
/* Fill the parts of the node */
new->l_link = NULL;
new->data = data;
new->r_link = NULL;
/* If list is empty */
if (*head == NULL)
{
*head = new;
*tail = new;
return SUCCESS;
}
/* List is non-empty */
new->l_link = *tail;
(*tail)->r_link = new;
(*tail) = new;
return SUCCESS;
}Brief:
This function deletes the first node existing double linked list.
Delete the node in the beginning:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 27 Mar 2017 3:05:26 IST
* File : dl_delete_at_first.c
* Title : Function to delete the node in the begining
* Description : This function deletes the first node existing double linked list.
*------------------------------------------------------------------------------------------*/
#include "dll.h"
int dl_delete_at_first(Dlist **head, Dlist **tail)
{
Dlist *temp = *head;
if (*head == NULL)
{
printf("List is Emptyn");
return FAILURE;
}
if ((*head)->r_link == NULL)
{
free(temp);
*head = NULL;
*tail = NULL;
return SUCCESS;
}
*head = temp->r_link;
temp->r_link = NULL;
(*head)->l_link = NULL;
free(temp);
return SUCCESS;
}Brief:
This function prints the data in the list by traversing first node to the last node.
Print the list:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 27 Mar 2017 3:12:04 IST
* File : dl_print_list.c
* Title : Function to print the list
* Description : This function prints the data in the list by traversing first node to
* the last node.
*------------------------------------------------------------------------------------------*/
#include "dll.h"
void dl_print_list(Dlist *head)
{
if (head == NULL)
{
printf("List is Emptyn");
}
else
{
while (head)
{
printf("%d <-> ", head->data);
head = head->r_link;
}
printf("n");
}
}Make File:
SRC:=$(wildcard *.c)
OBJ:=$(patsubst *.c, *.o, $(SRC))
CC:=gcc
dll.exe: $(OBJ)
$(CC) -o $@ $^
clean:
rm *.exe
~ Steps to run the program:
Step-1: Run the Makefile present the same directory
$make
Step-2: Run the executable file
$./dll.exe
Example output 1:
Example output 2:
Brief:
This file contains standard header files, macros, structure definition and function prototypes required for double linked list.
Header File:
#ifndef DLL_H
#define DLL_H
#include <stdio.h>
#include <stdlib.h>
#define SUCCESS 0
#define FAILURE -1
typedef int data_t;
typedef struct node
{
struct node *l_link;
data_t data;
struct node *r_link;
}Dlist;
int dl_insert_at_first(Dlist **head, Dlist **tail, data_t data);
int dl_delete_at_last(Dlist **head, Dlist **tail);
void dl_print_list(Dlist *head);
int select_operation();
#endifBrief:
This function acts like a driver function, it is user interactive.
Driver Function:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 27 Mar 2017 3:20:30 IST
* File : main.c
* Title : Driver function
* Description : This function acts like a driver function, it is user interactive.
*------------------------------------------------------------------------------------------*/
#include "dll.h"
int main()
{
Dlist *head, *tail;
head = tail = NULL;
int choice;
int num;
char option;
system("clear");
do
{
choice = select_operation();
switch (choice)
{
case 1:
printf("Enter the number to insert at last: ");
scanf("%d", &num);
if (dl_insert_at_first(&head, &tail, num) == FAILURE)
{
printf("Failed: Inserting the new data at first.n");
printf("Try again...n");
}
else
{
printf("Success: Element inserted at firstn");
}
break;
case 2:
dl_print_list(head);
break;
case 3:
if (dl_delete_at_last(&head, &tail) == FAILURE)
{
printf("Failed: Deleting the element at lastn");
printf("Try again...n");
}
else
{
printf("Success: Last element deletedn");
}
break;
default: printf("Invalid optionn");
}
printf("Press [y] to continue: ");
scanf("n%c", &option);
}while (option == 'y');
return 0;
}
int select_operation()
{
int choice;
printf("1.Insert at firstn");
printf("2.Print listn");
printf("3.Delete at lastn");
printf("Select an Option: ");
scanf("%d", &choice);
return choice;
}Brief:
This function is the template, where some parts of the code are missing needs to filled. In the code below, you can see the lines with TODO which needs to be updated with the code.
Insert the new node in the beginning:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Tue 27 Mar 2017 3:29:30 IST
* File : dl_insert_at_first.c
* Title : Function insert the new node in the begining
* Description : This function is the template, where some parts of the code are missing
* needs to filled. In the code below, you can see the lines with TODO which
* needs to be updated with the code.
*------------------------------------------------------------------------------------------*/
#include "dll.h"
int dl_insert_at_first(Dlist **head, Dlist **tail, data_t data)
{
/* Creating the new node */
Dlist *new = malloc(sizeof(Dlist));
/* Check whether new node created or not */
if (new == NULL)
{
return FAILURE;
}
/* Fill the parts of the node */
new->l_link = NULL;
new->data = data;
new->r_link = NULL;
/* If list is empty */
if (*head == NULL)
{
*head = new;
*tail = new;
return SUCCESS;
}
/* List is non-empty */
new->r_link= *head;
(*head)->l_link = new;
new->l_link = NULL;
*head = new;
return SUCCESS;
}Brief:
This function is the template, where some parts of the code are missing needs to filled. In the code below, you can see the lines with TODO which needs to be updated with the code.
Delete the node present at the last:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Tue 27 Mar 2017 3:29:30 IST
* File : dl_delete_at_last.c
* Title : Function to delete the node present at the last
* Description : This function is the template, where some parts of the code are missing
* needs to filled. In the code below, you can see the lines with TODO
* which needs to be updated with the code.
*------------------------------------------------------------------------------------------*/
#include "dll.h"
int dl_delete_at_last(Dlist **head, Dlist **tail)
{
/* Check whether list is empty or not */
if (*head == NULL)
{
/* If Empty */
return FAILURE;
}
/* If non-empty */
Dlist *temp = *tail;
*tail = (*tail) -> l_link;
if (*tail)
(*tail)-> r_link = NULL;
free(temp);
/* If list is empty after deleting */
if (*tail == NULL)
{
*head = NULL;
}
return SUCCESS;
}Brief:
This function is the template, where some parts of the code are missing needs to filled. In the code below, you can see the lines with TODO which needs to be updated with the code.
Insert new node in the beginning:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Tue 27 Mar 2017 3:29:30 IST
* File : dl_insert_at_first.c
* Title : Function insert the new node in the begining
* Description : This function is the template, where some parts of the code are missing
* needs to filled. In the code below, you can see the lines with TODO
* which needs to be updated with the code.
*------------------------------------------------------------------------------------------*/
#include "dll.h"
int dl_insert_at_first(Dlist **head, Dlist **tail, data_t data)
{
/* Creating the new node */
Dlist *new = malloc(sizeof(Dlist));
/* Check whether new node created or not */
if (new == NULL)
{
return FAILURE;
}
/* Fill the parts of the node */
new->l_link = NULL;
new->data = data;
new->r_link = NULL;
/* If list is empty */
if (*head == NULL)
{
*head = new;
*tail = new;
return SUCCESS;
}
/* List is non-empty */
new->r_link= *head;
(*head)->l_link = new;
new->l_link = NULL;
*head = new;
return SUCCESS;
}Compiling and running the program:
- Implement the functions
- Test these functions by integrating into the files present in the 1-Template folder.
- Modify the main function.
- Run the Makefile file
- Finally, run the dll.exe and verify the output.
Example output 1:
Example output 2:
Brief:
This file contains standard header files, macros, structure definition and function prototypes required for double linked list.
Header File:
#ifndef DLL_H
#define DLL_H
#include <stdio.h>
#include <stdlib.h>
#define SUCCESS 0
#define FAILURE -1
#define ELEMENT_NOT_FOUND -2
typedef int data_t;
typedef struct node
{
struct node *l_link;
data_t data;
struct node *r_link;
}Dlist;
int dl_delete_list(Dlist **head, Dlist **tail);
int dl_find_node(Dlist *head, data_t key);
void dl_print_list(Dlist *head);
int dl_insert_at_first(Dlist **head, Dlist **tail, data_t data);
int select_operation();
#endifBrief:
This function acts like a driver function, it is user interactive .
Driver Function:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 27 Mar 2017 3:20:30 IST
* File : main.c
* Title : Driver function
* Description : This function acts like a driver function, it is user interactive.
*------------------------------------------------------------------------------------------*/
#include "dll.h"
int main()
{
Dlist *head, *tail;
head = tail = NULL;
int choice;
int num, key;
char option;
system("clear");
do
{
choice = select_operation();
switch (choice)
{
case 1:
printf("Enter the number to insert at first: ");
scanf("%d", &num);
if (dl_insert_at_first(&head, &tail, num) == SUCCESS)
{
printf("Success: Element inserted at firstn");
}
else
{
printf("Failed: Inserting the new data at firstn");
printf("Try again...n");
}
break;
case 2:
dl_print_list(head);
break;
case 3:
if (dl_delete_list(&head, &tail) == SUCCESS)
{
printf("SUCCESS: All elements are deletedn");
}
break;
case 4: printf("Enter the element to be searched :");
scanf("%d", &key);
if (dl_find_node(head, key) == SUCCESS)
{
printf("SUCCESS: Element found in the listn");
}
else
{
printf("Failure: Element not foundn");
}
break;
default: printf("Invalid optionn");
}
printf("Press [y] to continue: ");
scanf("n%c", &option);
}while (option == 'y');
return 0;
}
int select_operation()
{
int choice;
printf("1.Insert at firstn");
printf("2.Print listn");
printf("3.Delete Listn");
printf("4.Find Noden");
printf("Select an Option: ");
scanf("%d", &choice);
return choice;
}Brief:
This function finds whether the given key is present in the list or not, if present it will return the address of the node where the key is found.
Find the node:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 27 Mar 2017 3:43:17 IST
* File : dl_find_node.c
* Title : Function to find the key
* Description : This function finds whether the given key is present in the list or not,
* if present it will return the address of the node where the key is found.
*------------------------------------------------------------------------------------------*/
#include "dll.h"
int dl_find_node(Dlist *head, data_t key)
{
if (head == NULL)
printf("List is Emptyn");
while (head)
{
if (head -> data == key)
{
return SUCCESS;
}
head = head -> r_link;
}
return ELEMENT_NOT_FOUND;
}Brief:
This function deletes all the nodes present in the list, finally the head will be updated to NULL.
Delete the complete list:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 27 Mar 2017 3:42:07 IST
* File : dl_delete_list.c
* Title : Function to delete the complete list
* Description : This function deletes all the nodes present in the list, finally the
* head will be updated to NULL.
*------------------------------------------------------------------------------------------*/
#include "dll.h"
int dl_delete_list(Dlist **head, Dlist **tail)
{
Dlist *temp = *head;
Dlist *temp2 = NULL;
if (*head == NULL)
{
printf("List is emptyn");
}
while (temp)
{
if ((*head)->r_link == NULL)
{
free(temp);
*head = NULL;
*tail = NULL;
temp = temp->r_link;
}
else
{
temp2 = temp;
*head = temp->r_link;
(*head)->l_link = NULL;
temp = temp->r_link;
temp2->r_link = NULL;
free(temp2);
}
}
return SUCCESS;
}Brief:
This function is the template, where some parts of the code are missing needs to filled. In the code below, you can see the lines with TODO which needs to be updated with the code.
Insert new node in the beginning:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Tue 27 Mar 2017 3:29:30 IST
* File : dl_insert_at_first.c
* Title : Function insert the new node in the begining
* Description : This function is the template, where some parts of the code are missing
* needs to filled. In the code below, you can see the lines with TODO
* which needs to be updated with the code.
*------------------------------------------------------------------------------------------*/
#include "dll.h"
int dl_insert_at_first(Dlist **head, Dlist **tail, data_t data)
{
/* Creating the new node */
Dlist *new = malloc(sizeof(Dlist));
/* Check whether new node created or not */
if (new == NULL)
{
return FAILURE;
}
/* Fill the parts of the node */
new->l_link = NULL;
new->data = data;
new->r_link = NULL;
/* If list is empty */
if (*head == NULL)
{
*head = new;
*tail = new;
return SUCCESS;
}
/* List is non-empty */
new->r_link= *head;
(*head)->l_link = new;
*head = new;
return SUCCESS;
}Steps to compile and run the program:
After Implementing
– find node
– Delete list
functions
- Integrate these two function with functions available in the Template folder.
- Run the Makefile
- Test it.
Example output 1:
Example output 2:
Brief:
This is the header file which contains the stack definitions, Macros, typedefs, function prototypes.
Header File:
/*-------------------------------------------------------------------------------------------
* Author : Emertxe (https://emertxe.com)
* Date : Mon 30 Mar 2017 4:27:30 IST
* File : stack.h
* Title : Header file
* Description : This is the header file which contains the stack definitions, Macros,
* typedefs, function prototypes.
*-----------------------------------------------------------------------------------------*/
#ifndef STACK_H
#define STACK_H
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
#define STACK_OVERFLOW 9
#define EMPTY_STACK 0
#define SUCCESS 1
#define FAILURE 2
typedef int data_t;
typedef struct
{
data_t array[MAX];
int top;
}arr_stack_t;
int select_operation();
int push(arr_stack_t *S, data_t item);
int peep(arr_stack_t S);
int peek(arr_stack_t S, data_t *item);
int pop(arr_stack_t *S, data_t *item);
#endifBrief:
This function acts like a driver function, it is user interactive.
Driver Function:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 30 Mar 2017 4:05:30 IST
* File : main.c
* Title : Driver function
* Description : This function acts like a driver function, it is user interactive.
*------------------------------------------------------------------------------------------*/
#include "stack.h"
int main()
{
system("clear");
// Create stack
arr_stack_t *S = malloc(sizeof(arr_stack_t));
if (S == NULL)
{
printf("Unable to create Stackn");
return FAILURE;
}
// If created
S->top = -1;
printf("An array stack is created with size %dn", MAX);
int operation, result;
char choice;
data_t data;
do{
// Selection of operation to be performed
operation = select_operation();
switch (operation)
{
// If PUSH
case 1 :
printf("Enter new data: ");
scanf("%d", &data);
if ((push(S, data)) == STACK_OVERFLOW)
{
printf("STACK OVERFLOW.....n");
}
else
{
printf("Element inserted into the stackn");
}
break;
//If PEEP
case 2 :
if (peep(*S) == EMPTY_STACK)
{
printf("STACK is EMPTY.....n");
}
break;
case 3:
result = pop(S, &data);
(result == SUCCESS) ? printf("Success: %d removed from Stackn", data) : printf("Failure: Stack is Emptyn");
break;
case 4:
result = peek(*S, &data);
(result == SUCCESS) ? printf("Success: peek operation and peek value = %dn", data) : printf("Failure: peek operation, stack is emptyn");
break;
default:
printf("Invalid operationn");
}
// Continue/Stop
printf("Press [y] to continue: ");
scanf("n%c", &choice);
}while (choice == 'y');
}
int select_operation()
{
int op;
printf("[1]. Pushn");
printf("[2]. Peepn");
printf("[3]. Popn");
printf("[4]. Peekn");
printf("Select an Operation: ");
scanf("%d", &op);
return op;
}Brief:
This function adds the given item into the stack pointed by the top index variable..
Push Element:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 30 Mar 2017 4:15:34 IST
* File : push.c
* Title : Push element
* Description : This function adds the given item into the stack pointed by the top
* index variable.
*------------------------------------------------------------------------------------------*/
#include "stack.h"
int push(arr_stack_t *S, data_t item)
{
// Is space available in stack
if((S->top) == (MAX - 1))
{
// If NO
return STACK_OVERFLOW;
}
// If YES
// Increment top
(S->top)++;
// Store data
S->array[S->top] = item;
return SUCCESS;
}Brief:
This function prints the stack items from top index variable.
Print the stack Items:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 30 Mar 2017 4:25:26 IST
* File : peep.c
* Title : Print the stack Items
* Description : This function prints the stack items from top index variable.
*------------------------------------------------------------------------------------------*/
#include "stack.h"
int peep(arr_stack_t S)
{
// Is stack EMPTY
if(S.top == -1)
{
// If YES
return EMPTY_STACK;
}
// If NO
// print stack elements
printf("Items in stack :");
for(;S.top > -1; (S.top)--)
{
printf("->%d", S.array[S.top]);
}
printf("n");
return SUCCESS;
}Brief:
This function removes the item present on the top of the stack..
Pop Element:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Thu 30 Mar 2017 4:15:34 IST
* File : pop.c
* Title : pop element
* Description : This function removes the item present on the top of the stack.
*------------------------------------------------------------------------------------------*/
#include "stack.h"
int pop(arr_stack_t *S, data_t *item)
{
// Is stack EMPTY
if(S->top == -1)
{
// If YES
return EMPTY_STACK;
}
// If No
*item = (S)->array[(S)->top];
((S)->top)--;
return SUCCESS;
}Brief:
This function returns the top item without altering the top index variable.
Peek Element:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Thu 30 Mar 2017 4:20:34 IST
* File : peek.c
* Title : Extract the top item
* Description : This function returns the top item without altering the top index
* variable.
*------------------------------------------------------------------------------------------*/
#include "stack.h"
int peek(arr_stack_t S, data_t *item)
{
// Is stack EMPTY
if(S.top == -1)
{
// If YES
return EMPTY_STACK;
}
*item = (S).array[S.top];
return SUCCESS;
}Make File:
SRC:=$(wildcard *.c)
OBJ:=$(patsubst *.c, *.o, $(SRC))
CC:=gcc
stack_array.exe: $(OBJ)
$(CC) -o $@ $^
clean:
rm *.exe
~ Steps to compile and run the program:
- Read the comments given in the file and convert it into the code.
- Integrate this function into the main function.
- Run the Makefile
- Verify the output
Example output 1: Compiling the Program
Example output 2: Push and Peep
Example output 3: Pop
Example output 4: Peek
Brief:
This is the header file which contains the queue definitions, Macros, typedefs, function prototypes.
Header File:
#include <stdio.h>
#include <stdlib.h>
#define QUEUE_FULL -1
#define QUEUE_EMPTY 0
#define SUCCESS 1
#define MAX 4
typedef int data_t;
typedef struct
{
data_t array[MAX];
int f, r;
}queue_array_t;
int select_operation();
int enqueue(queue_array_t *Q, data_t item);
int dequeue(queue_array_t *Q, data_t *item);
void print_queue(queue_array_t Q);Brief:
This function acts like a driver function, it is user interactive.
Driver Function:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sat 1 April 2017 11:40:30 IST
* File : main.c
* Title : Driver function
* Description : This function acts like a driver function, it is user interactive.
*------------------------------------------------------------------------------------------*/
#include "queue.h"
int main()
{
system("clear");
// Create Queue
queue_array_t *Q = malloc(sizeof(queue_array_t));
if(Q == NULL)
{
printf("Unable to create Queuen");
return 0;
}
// If created
Q->r = Q->f = -1;
printf("An array Queue is created with size %dn", MAX);
int operation;
char choice;
data_t data;
do{
// Selection of operation to be performed
operation = select_operation();
switch(operation)
{
// If Enqueue
case 1 :
printf("Enter new data: ");
scanf("%d", &data);
if((enqueue(Q, data)) == QUEUE_FULL)
{
printf("Queue is fulln");
}
break;
//If Dequeue
case 2 :
if(dequeue(Q, &data) == QUEUE_EMPTY)
{
printf("Queue is emptyn");
}
else
{
printf("Removed item is -> %dn", data);
}
break;
//If Print Queue
case 3 :
print_queue(*Q);
break;
default:
printf("Invalid operationn");
}
// Continue/Stop
printf("Press [y] to continue: ");
scanf("n%c", &choice);
}while(choice == 'y');
return 0;
}
int select_operation()
{
int op;
printf("[1]. Enqueuen[2]. Dequeuen[3]. Printn");
printf("Select an Operation: ");
scanf("%d", &op);
return op;
}Brief:
This function adds the given item into the queue pointed by the rear index variable..
Add Element:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sat 1 April 2017 11:15:34 IST
* File : enqueue.c
* Title : Add element
* Description : This function adds the given item into the queue pointed by the rear
* index variable.
*------------------------------------------------------------------------------------------*/
#include "queue.h"
int enqueue(queue_array_t *Q, data_t item)
{
//Is queue full
if(Q->r == MAX - 1)
{
// If yes
return QUEUE_FULL;
}
// If No
// Is queue empty
if(Q->f == -1)
{
//If yes
(Q->f)++;
}
//Increment rare
(Q->r)++;
// Store data
Q->array[Q->r] = item;
return SUCCESS;
}Brief:
This function deletes the item from the stack pointed by the front index variable..
Delete Element:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sat 1 April 2017 11:15:34 IST
* File : dequeue.c
* Title : Delete element
* Description : This function deletes the item from the stack pointed by the front
* index variable.
*------------------------------------------------------------------------------------------*/
#include "queue.h"
int dequeue(queue_array_t *Q, data_t *item)
{
// Is queue empty
if(Q->f == -1)
{
//If yes
return QUEUE_EMPTY;
}
// If no
//Store front element in item
*item = (Q->array)[Q->f];
//Increment front
(Q->f)++;
//If front crosses rare, It is the case of queue empty
if (Q->f > Q->r)
{
//Initialize front and top to -1
Q->f = -1;
Q->r = -1;
}
return SUCCESS;
}Brief:
This function prints the queue items from front to rear.
Print the queue Items:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 30 Mar 2017 4:25:26 IST
* File : print_queue.c
* Title : Print the queue Items
* Description : This function prints the queue items from front to rear
*------------------------------------------------------------------------------------------*/
#include "queue.h"
void print_queue(queue_array_t Q)
{
// Is queue empty
if(Q.f == -1)
{
// If Yes
printf("Queue is empty");
}
// If No
else
{
printf("Queue Elements :");
for(; Q.f <= Q.r; (Q.f)++)
{
printf("~ %d ", Q.array[Q.f]);
}
}
printf("n");
}Make File:
SRC:=$(wildcard *.c)
OBJ:=$(patsubst *.c, *.o, $(SRC))
CC:=gcc
queue.exe: $(OBJ)
$(CC) -o $@ $^
clean:
rm *.exe
~ Example output 1:
Example output 2:
Brief:
This is the header file which contains the queue definitions, Macros, typedefs, function prototypes.
Header File:
#ifndef QUEUE_H
#define QUEUE_H
#include <stdio.h>
#include <stdlib.h>
#define QUEUE_FULL -1
#define QUEUE_EMPTY 0
#define SUCCESS 1
#define MAX 4
typedef int data_t;
typedef struct
{
data_t array[MAX];
int f, r, count;
}queue_array_t;
int select_operation();
int enqueue(queue_array_t *Q, data_t item);
int dequeue(queue_array_t *Q, data_t *item);
void print_queue(queue_array_t *queue);
#endifBrief:
This function acts like a driver function, it is user interactive.
Driver Function:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sat 1 April 2017 11:40:30 IST
* File : main.c
* Title : Driver function
* Description : This function acts like a driver function, it is user interactive.
*------------------------------------------------------------------------------------------*/
#include "queue.h"
int main()
{
system("clear");
// Create Queue
queue_array_t *Q = malloc(sizeof(queue_array_t));
if (Q == NULL)
{
printf("Unable to create Queuen");
return 0;
}
// If created
Q->r = -1;
Q->f = -1;
Q->count = 0;
;
printf("An array Circular Queue is created with size %dn", MAX);
int operation;
char choice;
data_t data;
do
{
// Selection of operation to be performed
operation = select_operation();
switch (operation)
{
// If Enqueue
case 1:
printf("Enter new data: ");
scanf("%d", &data);
if ((enqueue(Q, data)) == QUEUE_FULL)
{
printf("FAILURE: Queue is fulln");
}
else
{
printf("SUCCESS: Element inserted into the Queuen");
}
break;
case 2:
if (dequeue(Q, &data) == QUEUE_EMPTY)
{
printf("FAILURE: Queue is Emptyn");
}
else
{
printf("SUCCESS: %d removed from the Queuen", data);
}
//If print Queue
case 3:
print_queue(Q);
break;
default:
printf("Invalid operationn");
}
// Continue/Stop
printf("Press [y] to continue: ");
scanf("n%c", &choice);
} while (choice == 'y');
return 0;
}
int select_operation()
{
int op;
printf("[1]. Enqueuen[2]. Dequeuen[3]. Printn");
printf("Select Operation: ");
scanf("%d", &op);
return op;
}Brief:
This function adds the given item into the queue pointed by the rear index variable..
Add Element:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sat 1 April 2017 11:15:34 IST
* File : enqueue.c
* Title : Add element
* Description : This function adds the given item into the queue pointed by the rear
* index variable.
*------------------------------------------------------------------------------------------*/
#include "queue.h"
int enqueue(queue_array_t *Q, data_t item)
{
// Is queue full
if(Q->count == MAX)
{
// If yes
return QUEUE_FULL;
}
// If no
// Is queue empty
if(Q->f == -1)
{
// If yes
(Q->f)++;
}
//Update rare
Q->r = ((Q->r) + 1) % MAX;
//Store data
Q->array[Q->r] = item;
// Increment count
(Q->count)++;
return SUCCESS;
}Brief:
This function prints the queue items from front to rear.
Print the queue Items:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 30 Mar 2017 4:25:26 IST
* File : print_queue.c
* Title : Print the queue Items
* Description : This function prints the queue items from front to rear
*------------------------------------------------------------------------------------------*/
#include "queue.h"
void print_queue(queue_array_t *queue)
{
if (queue->count == 0)
printf("Queue is Emptyn");
else
{
// Storing front in one temporary variable
data_t temp = queue->f;
int total = 0;
// Prinitng queue till rear
while (total < queue->count)
{
if (temp == MAX)
temp = 0;
printf("%d->", queue->array[temp]);
temp++;
total++;
}
printf("NULLn");
}
}Brief:
This function deletes the given item into the queue pointed by the rear index variable..
Delete Element:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sat 1 April 2017 11:49:12 IST
* File : dequeue.c
* Title : Delete element
* Description : This function deletes the item from the queue pointed by the front
* index variable.
*------------------------------------------------------------------------------------------*/
#include "queue.h"
int dequeue(queue_array_t *Q, data_t *item)
{
// Is queue empty
if(Q->count == 0)
{
// If yes
return QUEUE_EMPTY;
}
*item = (Q)->array[(Q)->f];
// Incrementing front
(Q)->f = (((Q)->f) + 1) % MAX;
--((Q)->count);
return SUCCESS;
}Make File:
SRC:=$(wildcard *.c)
OBJ:=$(patsubst *.c, *.o, $(SRC))
CC:=gcc
queue.exe: $(OBJ)
$(CC) -o $@ $^
clean:
rm *.exe
~ Example output 1:
Example output 2:
Brief:
This is the header file which contains the queue definitions, Macros, typedefs, function prototypes.
Header File:
#ifndef SEARCH
#define SEARCH
#define ELEMENT_NOT_FOUND 2
typedef enum
{
e_true,
e_false
}status;
/* Function prototypes */
/* Binary Search Iterative */
int binary_search_iterative(int arr[], int size, int key);
/* Sort Array */
int sort_array(int arr[], int size);
#endifBrief:
This function acts like a driver function, it is user interactive.
Driver Function:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sat 1 April 2017 11:40:30 IST
* File : main.c
* Title : Driver function
* Description : This function acts like a driver function, it is user interactive.
*------------------------------------------------------------------------------------------*/
#include <stdio.h>
#include "binary_search.h"
int main()
{
// Declaring local variables
int size, i, key, res;
// Read input from user
printf("Enter the size of array: ");
scanf("%d", &size);
int arr[size];
printf("Enter %d elements: ", size);
for(i = 0; i < size; i++)
{
scanf("%d", &arr[i]);
}
printf("Enter the key element: ");
scanf("%d", &key);
// Sort array before searching
sort_array(arr, size);
res = binary_search_iterative(arr, size, key);
res == -1 ? printf("Key element not foundn") :printf("Position of key element %d is %dn", key, res);
return 0;
}Brief:
This function searches the given key in the sorted array.
Source Code:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 11:15:34 IST
* File : binary_search.c
* Title : Binary Search
* Description : This function searches the given key in the sorted array.
*------------------------------------------------------------------------------------------*/
#include "binary_search.h"
int binary_search_iterative(int *array,int length, int key)
{
int start = 0;
int end = length - 1;
while(1)
{
// If start=end
if((start == end) && (array[end] != key))
{
return -1;
}
int mid = (start + end) / 2;
// If key is greater
if(key > array[mid])
{
start = mid + 1;
}
//If key is less
else if(key < array[mid])
{
end = mid - 1;
}
else
{
return mid;
}
}
return ELEMENT_NOT_FOUND;
}Brief:
This function sort the given array.
Sort:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 11:15:34 IST
* File : sort.c
* Title : Sort
* Description : This function sorts the given array.
*------------------------------------------------------------------------------------------*/
#include "binary_search.h"
int sort_array(int *arr, int size)
{
int i, j;
// sort the array
for(i = 0; i < size; i++)
{
for(j = i + 1; j < size; j++)
{
if(arr[i] > arr[j])
{
int temp;
// swap the elements
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}Steps to compile and execute the program:
- Implement the comment part.
- Write the header file called binary_iterative.h
- Write the driver function
- Write the Makefile
- Run the Makefile
- Finally, run the executable file
Example output:
Brief:
This is the header file which contains the queue definitions, Macros, typedefs, function prototypes.
Header File:
#ifndef SEARCH
#define SEARCH
#define ELEMENT_NOT_FOUND 2
typedef enum
{
e_true,
e_false
}status;
/* Function prototypes */
/* Binary Search Recursive */
int binary_search_recursive(int arr[], int key, int low, int high);
/* Sort Array */
int sort_array(int arr[], int size);
#endifBrief:
This function acts like a driver function, it is user interactive.
Driver Function:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sat 1 April 2017 11:40:30 IST
* File : main.c
* Title : Driver function
* Description : This function acts like a driver function, it is user interactive.
*------------------------------------------------------------------------------------------*/
#include <stdio.h>
#include "binary_search.h"
int main()
{
// Declaring local variables
int size, i, key, res, low, high;
// Read input from user
printf("Enter the size of array: ");
scanf("%d", &size);
int arr[size];
printf("Enter %d elements: ", size);
for(i = 0; i < size; i++)
{
scanf("%d", &arr[i]);
}
printf("Enter the key element: ");
scanf("%d", &key);
// Sort array before searching
sort_array(arr, size);
low = 0;
high = size - 1;
res = binary_search_recursive(arr, key, low, high);
res == -1 ? printf("Key element not foundn") :printf("Position of key element %d is %dn", key, res);
return 0;
}Brief:
This function searches the given key in the sorted array.
Source Code:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 11:15:34 IST
* File : binary_search.c
* Title : Binary Search
* Description : This function searches the given key in the sorted array.
*------------------------------------------------------------------------------------------*/
#include "binary_search.h"
int binary_search_recursive(int *array,int key, int start, int end)
{
// If start=end
if((start == end) && (array[end] != key))
{
return -1;
}
int mid = (start + end) / 2;
// If key is greater
if(key > array[mid])
{
binary_search_recursive(array, key, mid + 1, end);
}
//If key is less
else if(key < array[mid])
{
binary_search_recursive(array, key, start, mid - 1);
}
else
{
return mid;
}
}Brief:
This function sort the given array.
Sort:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 11:15:34 IST
* File : sort.c
* Title : Sort
* Description : This function sorts the given array.
*------------------------------------------------------------------------------------------*/
#include "binary_search.h"
int sort_array(int *arr, int size)
{
int i, j;
// sort the array
for(i = 0; i < size; i++)
{
for(j = i + 1; j < size; j++)
{
if(arr[i] > arr[j])
{
int temp;
// swap the elements
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}Steps to compile and execute the program:
- Implement the comment part.
- Write the header file called binary_iterative.h
- Write the driver function
- Write the Makefile
- Run the Makefile
- Finally, run the executable file
Example output:
Brief:
This is the header file which contains the queue definitions, Macros, typedefs, function prototypes.
Header File:
#ifndef SORT_H
#define SORT_H
// macros
#define SUCCESS 0
#define FAILURE 1
#define SINGLE_ELEMENT 2
#include <stdio.h>
/* prototypes */
// quick sort
int quick_sort(int *arr, int low, int high);
// partition
int partition(int *arr, int low, int high);
// swaping
void swap(int *a, int *b);
//printing
void print_array(int *arr, int size);
#endifBrief:
This is the driver function, user interactive.
Driver Function:
/*---------------------------------------------------------------------------------------
* Author : Emertxe (https://emertxe.com)
* Date : Sun 2 April 2021 1:15:34 IST
* File : merge.c
* Title : Driver function
* Description : This function acts like a driver function, it is user interactive.
*-------------------------------------------------------------------------------------*/
#include <stdio.h>
#include "sort.h"
int main()
{
// Declaring local variables
int op, len;
//Read size of the array
printf("Enter the Size: ");
scanf("%d", &len);
int arr[len];
printf("Enter %d elements: ", len);
for(int i = 0; i < len; i++)
{
scanf("%d", &arr[i]);
}
quick_sort(arr, 0, len - 1);
print_array(arr, len);
return 0;
}Brief:
This function divides the array into two sub-array after fixing the position for the pivot item.
Split:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 1:15:34 IST
* File : split.c
* Title : Split
* Description : This function divides the array into two sub-array after fixing the
* position for the pivot item.
*------------------------------------------------------------------------------------------*/
#include "sort.h"
/* partition */
int partition(int *arr, int low, int high)
{
int pivot, p, q;
pivot = low;
p = low + 1;
q = high;
while(p <= q)
{
// checking the elements with pivot element and update the index from both side
while(arr[p] < arr[pivot])
{
p++;
}
while(arr[q] > arr[pivot])
{
q--;
}
if (p < q)
{
// swap the elements
swap(&arr[p], &arr[q]);
}
swap(&arr[q], &arr[pivot]);
}
return q;
}
/* swaping */
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}Brief:
This function sorts the given array by calling split function.
Quick Sort:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 1:15:34 IST
* File : quick_sort.c
* Title : Quick Sort
* Description : This function sorts the given array by calling split function.
*------------------------------------------------------------------------------------------*/
#include "sort.h"
int quick_sort(int *arr, int low, int high)
{
// validation for single element
int index;
if (low == 0 && high == 0)
{
return SINGLE_ELEMENT;
}
// recursive function calls
if(low < high)
{
index = partition(arr, low, high);
quick_sort(arr, low, index - 1);
quick_sort(arr, index + 1, high);
}
else
{
return SUCCESS;
}
}Brief:
This function prints the sorted array.
Print the Sorted array:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 1:15:34 IST
* File : print.c
* Title : Quick Sort
* Description : This function prints the array.
*------------------------------------------------------------------------------------------*/
#include "sort.h"
void print_array(int *arr, int size)
{
printf("After sortingn");
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("n");
}Steps to compile and execute the program:
- Implement the comments in the source code
- Write the driver function(main.c) and call it from main.c
- Write the Makefile
- Run the Makefile
- Run the .exe file and verify the output
Example output:
Brief:
This is the header file which contains the queue definitions, Macros, typedefs, function prototypes.
Header File:
#ifndef SORT
#define SORT
#include <stdio.h>
#include <stdlib.h>
#define e_true 0
#define e_false 1
//Function declaration of merge sort method
int merge_sort(int * arr, int size);
//Function prototype for merging sub arrays
int merge(int * arr, int size, int * L_arr, int mid, int * R_arr, int rem);
//Function prototype for printing array
int print_array(int * arr, int size);
//Function prototypes for swapping elements
void swap(int * data1, int * data2);
#endif
Brief:
This is the driver function, user interactive.
Driver Function:
/*---------------------------------------------------------------------------------------
* Author : Emertxe (https://emertxe.com)
* Date : Sun 2 April 2021 1:15:34 IST
* File : merge.c
* Title : Driver function
* Description : This function acts like a driver function, it is user interactive.
*-------------------------------------------------------------------------------------*/
#include <stdio.h>
#include "sort.h"
int main()
{
//Variable declaration
int size, iter;
//Take size from user
printf("Enter the size: ");
scanf("%d", &size);
int arr[size];
//Get elements of array from user
printf("Enter the elements: ");
for(iter = 0; iter < size; iter++)
{
scanf("%d", &arr[iter]);
}
//Calling function merge sort to sort the array
if(merge_sort(arr, size) == e_false)
printf("Failed : Sorting is not done. n");
printf("After sorting : n");
print_array(arr, size);
}
Brief:
This function splits the given array recursively and calls finally the merge function.
Merge Sort:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 1:15:34 IST
* File : merge.c
* Title : Merge Sort
* Description : This function splits the given array recursively and calls finally the
* merge function.
*------------------------------------------------------------------------------------------*/
#include "sort.h"
//Function Definition for merge sort technique
int merge_sort(int * arr, int size)
{
//Variable Declarations
int mid,iter, *L_arr, *R_arr;
//If only one element is there the return
if(size == 1)
return 1;
//Find mid
mid = size / 2;
//Allocate memeory for left and right sub arrays
L_arr = malloc(sizeof(int) * mid);
if(L_arr == NULL)
return e_false;
//Add elements from arr to sub arrays
for(iter = 0; iter < mid; iter++)
{
L_arr[iter] = arr[iter];
}
R_arr = malloc(sizeof(int) * (size - mid));
if(R_arr == NULL)
return e_false;
for(iter = mid; iter < size; iter++)
{
R_arr[iter - mid] = arr[iter];
}
//Call functions recursively to divide the array into sub arrays
merge_sort(L_arr, mid);
merge_sort(R_arr, size - mid);
//Merge the subarrays
merge(arr, size, L_arr, mid, R_arr, size - mid);
}Brief:
This function merges two sorted sub-array into one.
Merge two arrays:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 1:15:34 IST
* File : merge.c
* Title : Merge two arrays
* Description : This function merges two sorted sub-array into one.
*------------------------------------------------------------------------------------------*/
#include "sort.h"
//Function Definition for merging arrays
int merge(int *arr, int size, int *L_arr, int mid, int *R_arr, int rem)
{
//Variable Declarations
int i = 0, j = 0;
int k = 0;
//Comparing each element of sub arrays
while (i < mid && j < rem)
{
//If element of left sub array is less than that of right sub array, add it to arr
if (L_arr[i] < R_arr[j])
{
arr[k] = L_arr[i];
i++;
k++;
}
//else add the element of right sub array to arr
else
{
arr[k] = R_arr[j];
k++;
j++;
}
}
//Add remaining element of sub array to arr
while (j < rem)
{
arr[k] = R_arr[j];
k++;
j++;
}
while (i < mid)
{
arr[k] = L_arr[i];
k++;
i++;
}
}
Brief:
This function prints the sorted array.
Print the Sorted array:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 1:15:34 IST
* File : print.c
* Title : Merge Sort
* Description : This function prints the array.
*------------------------------------------------------------------------------------------*/
#include "sort.h"
//Function Definition for printing array
int print_array(int * arr, int size)
{
//Variable Declarations
int iter1;
for(iter1 = 0; iter1 < size; iter1++)
{
printf("%d ", arr[iter1]);
}
puts("");
return e_true;
}
Steps to compile and execute the program:
- Implement the comments in the source code
- Write the driver function(main.c) and call it from main.c
- Write the Makefile
- Run the Makefile
- Run the .exe file and verify the output
Example output:
Brief:
This is the header file which contains the heap definitions, Macros, typedefs, function prototypes.
Header File:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 1:15:34 IST
* File : heap.h
* Title : Header file
* Description : This is the header file which contains the heap definitions, Macros,
* typedefs, function prototypes.
*------------------------------------------------------------------------------------------*/
#ifndef HEAP_H
#define HEAP_H
#include <stdio.h>
#include <stdlib.h>
void heap_sort(int *A, int n);
void build_max(int *A, int heap_size);
void max_heapify(int* A, int heap_size, int root);
#endifBrief:
This function converts the given array of items into the max heap.
Convert to Max Heap:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 1:15:34 IST
* File : max_heapify.c
* Title : Convert to Max Heap
* Description : This function converts the given array of items into the max heap.
*------------------------------------------------------------------------------------------*/
#include "heap.h"
void max_heapify(int* A, int heap_size, int root)
{
// Initialize largest as root
int largest = root;
// Index of left child
int l = (root << 1) + 1;
// Index of Right child
int r = (root << 1) + 2;
// If left child is larger than root
if (l < heap_size && A[l] > A[largest])
{
largest = l;
}
// If right child is larger than largest so far
if (r < heap_size && A[r] > A[largest])
{
largest = r;
}
// If largest is not root
if (largest != root)
{
//swap A[root] with A[largest]
int temp = A[root];
A[root] = A[largest];
A[largest] = temp;
// Recursively Max-Heapify the affected sub-tree
max_heapify(A, heap_size, largest);
}
}Brief:
This function converts the given array of items into the max heap.
Build Max Heap:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 1:15:34 IST
* File : build_max.c
* Title : Convert to Max Heap
* Description : This function converts the given array of items into the max heap.
*------------------------------------------------------------------------------------------*/
#include "heap.h"
void build_max(int *A, int heap_size)
{
int i;
for (i = (heap_size >> 1) - 1; i >= 0; i--)
{
max_heapify(A, heap_size, i);
}
}Brief:
This function sorts the given array using the heaps.
Heap Sort:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 1:15:34 IST
* File : heap_sort.c
* Title : Heap sort
* Description : This function sorts the given array using the heaps.
*------------------------------------------------------------------------------------------*/
#include "heap.h"
void heap_sort(int *A, int n)
{
//Build MaxHeap
build_max(A, n);
int heap_size, temp;
// One by one extract an element from heap and get the sorted array
for (heap_size = n - 1; heap_size >= 0; heap_size--)
{
// Move top root element to end element
temp = A[0];
A[0] = A[heap_size];
A[heap_size] = temp;
// Call max heapify on the reduced heap
max_heapify(A, heap_size, 0);
}
}Brief:
This function acts like a driver function.
Driver Function:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 1:15:34 IST
* File : main.c
* Title : Driver function
* Description : This function acts like a driver function.
*------------------------------------------------------------------------------------------*/
#include "heap.h"
int main()
{
int size;
printf("Enter the size: ");
scanf("%d", &size);
int array[size];
// Intake array elements
int i;
printf("Enter %d elements: ", size);
for(i = 0; i < size; i++)
{
scanf("%d", &(array[i]));
}
//Heap Sort
heap_sort(array, size);
// Print Sorted array
printf("Sorted arrayn");
for(i = 0; i < size; i++)
{
printf("%d ", array[i]);
}
printf("n");
return 0;
}
Make File:
SRC:=$(wildcard *.c)
OBJ:=$(patsubst *.c, *.o, $(SRC))
CC:=gcc
heap_sort.exe: $(OBJ)
$(CC) -o $@ $^
clean:
rm *.exeExample output:
Brief:
This is the header file which contains the bst definitions, Macros, typedefs, function prototypes.
Header File:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 1:15:34 IST
* File : bst.h
* Title : Header file
* Description : This is the header file which contains the bst definitions, Macros,
* typedefs, function prototypes.
*------------------------------------------------------------------------------------------*/
#ifndef BST_H
#define BST_H
#include <stdio.h>
#include <stdlib.h>
#define SUCCESS 'S'
#define FAILURE 'F'
typedef int data_t;
typedef struct tree_node
{
struct tree_node *l_child;
data_t data;
struct tree_node *r_child;
}Tnode_t;
int select_operation();
int bst_insert(data_t data, Tnode_t **root);
void bst_traverse_in_order(Tnode_t *node);
#endifBrief:
This function inserts the new data into the existing BST.
Insert into BST:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 30 Mar 2017 4:27:30 IST
* File : bst_insert.c
* Title : Insert into BST
* Description : This function inserts the new data into the existing BST
*------------------------------------------------------------------------------------------*/
#include "bst.h"
int bst_insert(data_t data, Tnode_t **root)
{
//Create new node
Tnode_t *new = malloc(sizeof(Tnode_t));
//Check whether new node created or not
if (new == NULL)
{
return FAILURE;
}
//Fill fields of new node created
new->data = data;
new->l_child = NULL;
new->r_child = NULL;
//If tree is empty
if (*root == NULL)
{
*root = new;
return SUCCESS;
}
//Tree is not empty
Tnode_t *temp = *root;
while (1)
{
//If new data already present
if(temp->data == data)
{
printf("Failure: Element already presentn");
return FAILURE;
}
//If new data is less
if (temp->data > data)
{
//If no left child
if (temp->l_child == NULL)
{
//Make new node as left child
temp->l_child = new;
return SUCCESS;
}
temp = temp->l_child;
}
//If new data is greater
else
{
//If no right child
if (temp->r_child == NULL)
{
//Make new node as right child
temp->r_child = new;
return SUCCESS;
}
temp = temp->r_child;
}
}
}Brief:
This function prints the items of BST according to in-order traversal.
Print BST:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 30 Mar 2017 4:27:30 IST
* File : bst_traverse_in_order.c
* Title : Print BST
* Description : This function prints the items of BST according to in-order traversal.
*------------------------------------------------------------------------------------------*/
#include "bst.h"
void bst_traverse_in_order(Tnode_t *node)
{
//If given node is not empty
if (node)
{
//Traverse left sub tree
bst_traverse_in_order(node->l_child);
//Print data of node
printf("-> %d ", node->data);
//Traverse right sub tree
bst_traverse_in_order(node->r_child);
}
}Brief:
This function acts like a driver function, it is user interactive.
Driver Function:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 1:15:34 IST
* File : main.c
* Title : Driver function
* Description : This function acts like a driver function.
*------------------------------------------------------------------------------------------*/
#include "bst.h"
int main(void)
{
system("clear");
Tnode_t *root = NULL;
char choice;
data_t data;
int option;
do
{
option = select_operation();
switch (option)
{
case 1:
printf("Enter the data to insert: ");
scanf("%d", &data);
if (bst_insert(data, &root) == SUCCESS)
{
printf("Element inserted into the Treen");
}
break;
case 2:
printf("In order traversaln");
bst_traverse_in_order(root);
printf("n");
break;
default :
printf("Invalid entryn");
}
printf("Press [y] to continue: ");
scanf("n%c", &choice);
}while (choice == 'y');
return 0;
}
int select_operation()
{
int option;
printf("1. Insertn2. Traverse 'IN ORDER'n");
printf("Select an Option: ");
scanf("%d", &option);
return option;
}
Make File:
SRC:=$(wildcard *.c)
OBJ:=$(patsubst *.c, *.o, $(SRC))
CC:=gcc
bst.exe: $(OBJ)
$(CC) -o $@ $^
clean:
rm *.exeExample output:
Example output:
Brief:
This is the header file which contains the bst definitions, Macros, typedefs, function prototypes.
Header File:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 1:15:34 IST
* File : bst.h
* Title : Header file
* Description : This is the header file which contains the bst definitions, Macros,
* typedefs, function prototypes.
*------------------------------------------------------------------------------------------*/
#ifndef BST_H
#define BST_H
#include <stdio.h>
#include <stdlib.h>
#define SUCCESS 'S'
#define FAILURE 'F'
typedef int data_t;
typedef struct tree_node
{
struct tree_node *l_child;
data_t data;
struct tree_node *r_child;
}Tnode_t;
int select_operation();
int bst_insert(data_t data, Tnode_t **root);
void bst_traverse_in_order(Tnode_t *node);
int bst_find_node(data_t data, Tnode_t *root);
#endifBrief:
This function inserts the new data into the existing BST.
Insert into BST:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 30 Mar 2017 4:27:30 IST
* File : bst_insert.c
* Title : Insert into BST
* Description : This function inserts the new data into the existing BST
*------------------------------------------------------------------------------------------*/
#include "bst.h"
int bst_insert(data_t data, Tnode_t **root)
{
//Create new node
Tnode_t *new = malloc(sizeof(Tnode_t));
//Check whether new node created or not
if (new == NULL)
{
return FAILURE;
}
//Fill fields of new node created
new->data = data;
new->l_child = NULL;
new->r_child = NULL;
//If tree is empty
if (*root == NULL)
{
*root = new;
return SUCCESS;
}
//Tree is not empty
Tnode_t *temp = *root;
while (1)
{
//If new data already present
if(temp->data == data)
{
printf("Failure: Element already presentn");
return FAILURE;
}
//If new data is less
if (temp->data > data)
{
//If no left child
if (temp->l_child == NULL)
{
//Make new node as left child
temp->l_child = new;
return SUCCESS;
}
temp = temp->l_child;
}
//If new data is greater
else
{
//If no right child
if (temp->r_child == NULL)
{
//Make new node as right child
temp->r_child = new;
return SUCCESS;
}
temp = temp->r_child;
}
}
}Brief:
This function prints the items of BST according to in-order traversal.
Print BST:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 30 Mar 2017 4:27:30 IST
* File : bst_traverse_in_order.c
* Title : Print BST
* Description : This function prints the items of BST according to in-order traversal.
*------------------------------------------------------------------------------------------*/
#include "bst.h"
void bst_traverse_in_order(Tnode_t *node)
{
//If given node is not empty
if (node)
{
//Traverse left sub tree
bst_traverse_in_order(node->l_child);
//Print data of node
printf("-> %d ", node->data);
//Traverse right sub tree
bst_traverse_in_order(node->r_child);
}
}Brief:
This function acts like a driver function, it is user interactive.
Driver Function:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 1:15:34 IST
* File : main.c
* Title : Driver function
* Description : This function acts like a driver function.
*------------------------------------------------------------------------------------------*/
#include "bst.h"
int main(void)
{
system("clear");
Tnode_t *root = NULL;
char choice;
data_t data;
int option;
do
{
option = select_operation();
switch (option)
{
case 1:
printf("Enter the data to insert: ");
scanf("%d", &data);
if (bst_insert(data, &root) == SUCCESS)
{
printf("Element inserted into the Treen");
}
break;
case 2:
printf("In order traversaln");
bst_traverse_in_order(root);
printf("n");
break;
case 3: printf("Enter element to be searched :");
scanf("%d", &data);
if (bst_find_node(data, root) == SUCCESS)
{
printf("Node found in the treen");
}
else
{
printf("Node not foundn");
}
break;
default :
printf("Invalid entryn");
}
printf("Press [y] to continue: ");
scanf("n%c", &choice);
}while (choice == 'y');
return 0;
}
int select_operation()
{
int option;
printf("1.Insertn2.Traverse 'IN ORDER'n3.Find Noden");
printf("Select an Option: ");
scanf("%d", &option);
return option;
}Brief:
This function searches the given key in the BST and if found returns the address of the node which contains the key.
Search the data:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 30 Mar 2017 4:05:30 IST
* File : bst_find.c
* Title : Search the data
* Description : This function searches the given key in the BST and if found returns
* the address of the node which contains the key.
*------------------------------------------------------------------------------------------*/
#include "bst.h"
Tnode_t *bst_find(data_t data, Tnode_t *node)
{
while (node != NULL)
{
if(node->data == data)
{
// To Do : Return node
}
else if (node->data > data)
{
//To Do : Go to Left Subtree
}
else
{
//To Do : Go to Right Subtree
}
}
return NULL;
}Brief:
This function finds the node in the BST.
Find Node:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 30 Mar 2017 4:05:30 IST
* File : bst_find.c
* Title : find the node
* Description : This function finds the given node in the BST
*------------------------------------------------------------------------------------------*/
#include "bst.h"
int bst_find_node(data_t data, Tnode_t *root)
{
if (root == NULL)
printf("Tree is emptyn");
else
{
while (root != NULL)
{
if (root -> data == data)
{
return SUCCESS;
}
else if (root -> data > data)
{
root = root ->l_child;
}
else
{
root = root ->r_child;
}
}
return FAILURE;
}
}
Make File:
SRC:=$(wildcard *.c)
OBJ:=$(patsubst *.c, *.o, $(SRC))
CC:=gcc
bst.exe: $(OBJ)
$(CC) -o $@ $^
clean:
rm *.exeExample output:
Example output:
Brief:
This is the header file which contains the bst definitions, Macros, typedefs, function prototypes.
Header File:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 1:15:34 IST
* File : bst.h
* Title : Header file
* Description : This is the header file which contains the bst definitions, Macros,
* typedefs, function prototypes.
*------------------------------------------------------------------------------------------*/
#ifndef BST_H
#define BST_H
#include <stdio.h>
#include <stdlib.h>
#define SUCCESS 'S'
#define FAILURE 'F'
typedef int data_t;
typedef struct tree_node
{
struct tree_node *l_child;
data_t data;
struct tree_node *r_child;
}Tnode_t;
int select_operation();
int bst_insert(data_t data, Tnode_t **root);
void bst_traverse_in_order(Tnode_t *node);
data_t bst_find_max(Tnode_t *node);
data_t bst_find_min(Tnode_t *node);
#endifBrief:
This function inserts the new data into the existing BST.
Insert into BST:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 30 Mar 2017 4:27:30 IST
* File : bst_insert.c
* Title : Insert into BST
* Description : This function inserts the new data into the existing BST
*------------------------------------------------------------------------------------------*/
#include "bst.h"
int bst_insert(data_t data, Tnode_t **root)
{
//Create new node
Tnode_t *new = malloc(sizeof(Tnode_t));
//Check whether new node created or not
if (new == NULL)
{
return FAILURE;
}
//Fill fields of new node created
new->data = data;
new->l_child = NULL;
new->r_child = NULL;
//If tree is empty
if (*root == NULL)
{
*root = new;
return SUCCESS;
}
//Tree is not empty
Tnode_t *temp = *root;
while (1)
{
//If new data already present
if(temp->data == data)
{
printf("Failure: Element already presentn");
return FAILURE;
}
//If new data is less
if (temp->data > data)
{
//If no left child
if (temp->l_child == NULL)
{
//Make new node as left child
temp->l_child = new;
return SUCCESS;
}
temp = temp->l_child;
}
//If new data is greater
else
{
//If no right child
if (temp->r_child == NULL)
{
//Make new node as right child
temp->r_child = new;
return SUCCESS;
}
temp = temp->r_child;
}
}
}Brief:
This function prints the items of BST according to in-order traversal.
Print BST:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 30 Mar 2017 4:27:30 IST
* File : bst_traverse_in_order.c
* Title : Print BST
* Description : This function prints the items of BST according to in-order traversal.
*------------------------------------------------------------------------------------------*/
#include "bst.h"
void bst_traverse_in_order(Tnode_t *node)
{
//If given node is not empty
if (node)
{
//Traverse left sub tree
bst_traverse_in_order(node->l_child);
//Print data of node
printf("-> %d ", node->data);
//Traverse right sub tree
bst_traverse_in_order(node->r_child);
}
}Brief:
This function acts like a driver function, it is user interactive.
Driver Function:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Sun 2 April 2017 1:15:34 IST
* File : main.c
* Title : Driver function
* Description : This function acts like a driver function.
*------------------------------------------------------------------------------------------*/
#include "bst.h"
int main(void)
{
system("clear");
Tnode_t *root = NULL;
char choice;
data_t data;
int option;
do
{
option = select_operation();
switch (option)
{
case 1:
printf("Enter the data to insert: ");
scanf("%d", &data);
if (bst_insert(data, &root) == SUCCESS)
{
printf("Element inserted into the Treen");
}
break;
case 2:
printf("In order traversaln");
bst_traverse_in_order(root);
printf("n");
break;
case 3: data = bst_find_min(root);
if (data != -1)
printf("Min data in the tree = %dn", data);
break;
case 4: data = bst_find_max(root);
if (data != -1)
printf("Max data in the tree = %dn", data);
break;
default :
printf("Invalid entryn");
}
printf("Press [y] to continue: ");
scanf("n%c", &choice);
}while (choice == 'y');
return 0;
}
int select_operation()
{
int option;
printf("1.Insertn2.Traverse 'IN ORDER'n3.Find Minn4.Find Maxn");
printf("Select an Option: ");
scanf("%d", &option);
return option;
}Brief:
This function finds the max data present in the BST and returns to the calling function.
Find the Max data:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 30 Mar 2017 4:05:30 IST
* File : bst_find_max.x
* Title : Find the Max data
* Description : This function finds the max data present in the BST and returns to the
* calling function
*------------------------------------------------------------------------------------------*/
#include "bst.h"
data_t bst_find_max(Tnode_t *root)
{
if (root == NULL)
{
printf("Tree is Emptyn");
return -1;
}
else
{
while (root -> r_child != NULL)
root = root -> r_child;
return root->data;
}
}Brief:
This function finds the min data present in the BST and returns to the calling function.
Find the Min data:
/*--------------------------------------------------------------------------------------------
* Author : Emertxe (https://www.emertxe.com)
* Date : Mon 30 Mar 2017 4:05:30 IST
* File : bst_find_min.x
* Title : Find the Min data
* Description : This function finds the min data present in the BST and returns to the
* calling function
*------------------------------------------------------------------------------------------*/
#include "bst.h"
data_t bst_find_min(Tnode_t *root)
{
if (root == NULL)
{
printf("Tree is Emptyn");
return -1;
}
else
{
while (root -> l_child != NULL)
root = root -> l_child;
return root->data;
}
}
Make File:
SRC:=$(wildcard *.c)
OBJ:=$(patsubst *.c, *.o, $(SRC))
CC:=gcc
bst.exe: $(OBJ)
$(CC) -o $@ $^
clean:
rm *.exeExample output:
Example output:
