DSA using C – Overview

What is a Data Structure?

Data Structure is a way to organized data in such a way that it can be used efficiently. Following terms are foundation terms of a data structure.

• Interface − Each data structure has an interface. Interface represents the set of operations that a datastructure supports.An interface only provides the list of supported operations, type of parameters they can accept and return type of these operations.

• Implementation − Implementation provides the internal representation of a data structure. Implementation also provides the definition of the algorithms used in the operations of the data structure.

Characteristics of a Data Structure

• Correctness − Data Structure implementation should implement its interface correctly.

• Time Complexity − Running time or execution time of operations of data structure must be as small as possible.

• Space Complexity − Memory usage of a data structure operation should be as little as possible.

Need for Data Structure

As applications are getting complex and data rich, there are three common problems applications face now-a-days.

• Data Search − Consider an inventory of 1 million(10⁶) items of a store. If application is to search an item. It has to search item in 1 million(10⁶) items every time slowing down the search. As data grows, search will become slower.

• Processor speed − Processor speed although being very high, falls limited if data grows to billion records.

• Multiple requests − As thousands of users can search data simultaneously on a web server,even very fast server fails while searching the data.

To solve above problems, data structures come to rescue. Data can be organized in a data structure in such a way that all items may not be required to be search and required data can be searched almost instantly.

Execution Time Cases

There are three cases which are usual used to compare various data structure”s execution time in relative manner.

• Worst Case − This is the scenario where a particular data structure operation takes maximum time it can take. If a operation”s worst case time is ƒ(n) then this operation will not take time more than ƒ(n) time where ƒ(n) represents function of n.

• Average Case − This is the scenario depicting the average execution time of an operation of a data structure. If a operation takes ƒ(n) time in execution then m operations will take mƒ(n) time.

• Best Case − This is the scenario depicting the least possible execution time of an operation of a data structure. If a operation takes ƒ(n) time in execution then actual operation may take time as random number which would be maximum as ƒ(n).

DSA using C – Environment Setup

Local Environment Setup

If you are still willing to set up your environment for C programming language, you need the following two softwares available on your computer, (a) Text Editor and (b) The C Compiler.

Text Editor

This will be used to type your program. Examples of few editors include Windows Notepad, OS Edit command, Brief, Epsilon, EMACS, and vim or vi.

Name and version of text editor can vary on different operating systems. For example, Notepad will be used on Windows, and vim or vi can be used on windows as well as Linux or UNIX.

The files you create with your editor are called source files and contain program source code. The source files for C programs are typically named with the extension “.c“.

Before starting your programming, make sure you have one text editor in place and you have enough experience to write a computer program, save it in a file, compile it and finally execute it.

The C Compiler

The source code written in source file is the human readable source for your program. It needs to be “compiled”, to turn into machine language so that your CPU can actually execute the program as per instructions given.

This C programming language compiler will be used to compile your source code into final executable program. I assume you have basic knowledge about a programming language compiler.

Most frequently used and free available compiler is GNU C/C++ compiler, otherwise you can have compilers either from HP or Solaris if you have respective Operating Systems.

Following section guides you on how to install GNU C/C++ compiler on various OS. I”m mentioning C/C++ together because GNU gcc compiler works for both C and C++ programming languages.

Installation on UNIX/Linux

If you are using Linux or UNIX, then check whether GCC is installed on your system by entering the following command from the command line −

$ gcc -v

If you have GNU compiler installed on your machine, then it should print a message something as follows −

Using built-in specs.
Target: i386-redhat-linux
Configured with: ../configure --prefix=/usr .......
Thread model: posix
gcc version 4.1.2 20080704 (Red Hat 4.1.2-46)

If GCC is not installed, then you will have to install it yourself using the detailed instructions available at https://gcc.gnu.org/install/

This tutorial has been written based on Linux and all the given examples have been compiled on Cent OS flavor of Linux system.

Installation on Mac OS

If you use Mac OS X, the easiest way to obtain GCC is to download the Xcode development environment from Apple”s web site and follow the simple installation instructions. Once you have Xcode setup, you will be able to use GNU compiler for C/C++.

Xcode is currently available at developer.apple.com/technologies/tools/.

Installation on Windows

To install GCC at Windows you need to install MinGW. To install MinGW, go to the MinGW homepage, www.mingw.org, and follow the link to the MinGW download page. Download the latest version of the MinGW installation program, which should be named MinGW-<version>.exe.

While installing MinWG, at a minimum, you must install gcc-core, gcc-g++, binutils, and the MinGW runtime, but you may wish to install more.

Add the bin subdirectory of your MinGW installation to your PATH environment variable, so that you can specify these tools on the command line by their simple names.

When the installation is complete, you will be able to run gcc, g++, ar, ranlib, dlltool, and several other GNU tools from the Windows command line.

DSA using C – Algorithms

Algorithm

Algorithm is a step by step procedure, which defines a set of instructions to be executed in certain order to get the desired output. In term of data structures, following are the categories of algorithms.

• Search − Algorithms to search an item in a datastrucure.

• Sort − Algorithms to sort items in certain order

• Insert − Algorithm to insert item in a datastructure

• Update − Algorithm to update an existing item in a data structure

• Delete − Algorithm to delete an existing item from a data structure

Algorithm analysis

Algorithm analysis deals with the execution time or running time of various operations of a data structure. Running time of an operation can be defined as no. of computer instructions executed per operation. As exact running time of any operation varies from one computer to another computer, we usually analyze the running time of any operation as some function of n, where n is the no. of items processed in that operation in a datastructure.

Asymptotic analysis

Asymptotic analysis refers to computing the running time of any operation in mathematical units of computation. For example, running time of one operation is computed as f(n) and of another operation as g(n²). Which means first operation running time will increase linearly with the increase in n and running time of second operation will increase exponentially when n increases. Similarly the running time of both operations will be nearly same if n is significantly small.

Asymptotic Notations

Following are commonly used asymptotic notations used in calculating running time complexity of an algorithm.

• Ο Notation

• Ω Notation

• θ Notation

Big Oh Notation, Ο

The Ο(n) is the formal way to express the upper bound of an algorithm”s running time. It measures the worst case time complexity or longest amount of time an algorithm can possibly take to complete.

For example, for a function f(n)

Big Oh notation is used to simplify functions. For example, we can replace a specific functional equation 7nlogn + n – 1 with Ο(f(nlogn)). Consider the scenario as follows −

It demonstrates that f(n) = 7nlogn +n – 1 is within the range of outout of O(nlogn) using constants c = 8 and n₀ = 2.

Omega Notation, Ω

The Ω(n) is the formal way to express the lower bound of an algorithm”s running time. It measures the best case time complexity or best amount of time an algorithm can possibly take to complete.

For example, for a function f(n)

Theta Notation, θ

The θ(n) is the formal way to express both the lower bound and upper bound of an algorithm”s running time. It is represented as following.

DSA using C – Concepts

Data Structure is a way to organized data in such a way that it can be used efficiently. Following terms are basic terms of a data structure.

Data Definition

Data Definition defines a particular data with following characteristics.

• Atomic − Definition should define a single concept

• Traceable − Definition should be be able to be mapped to some data element.

• Accurate − Definition should be unambiguous.

• Clear and Concise − Definition should be understandable.

Data Object

Data Object represents an object having a data.

Data Type

Data type is way to classify various types of data such as integer, string etc. which determines the values that can be used with the corresponding type of data, the type of operations that can be performed on the corresponding type of data. Data type of two types −

• Built-in Data Type

• Derived Data Type

Built-in Data Type

Those data types for which a language has built-in support are known as Built-in Data types. For example, most of the languages provides following built-in data types.

• Integers

• Boolean (true, false)

• Floating (Decimal numbers)

• Character and Strings

Derived Data Type

Those data types which are implementation independent as they can be implemented in one or other way are known as derived data types. These data types are normally built by combination of primary or built-in data types and associated operations on them. For example −

• List

• Array

• Stack

• Queue

DSA using C – Arrays

Overview

Array is a container which can hold fix number of items and these items should be of same type. Most of the datastructure make use of array to implement their algorithms. Following are important terms to understand the concepts of Array.

• Element − Each item stored in an array is called an element.

• Index − Each location of an element in an array has a numerical index which is used to identify the element.

Array Representation

As per above shown illustration, following are the important points to be considered.

• Index starts with 0.

• Array length is 8 which means it can store 8 elements.

• Each element can be accessed via its index. For example, we can fetch element at index 6 as 9.

Basic Operations

Following are the basic operations supported by an array.

• Insertion − add an element at given index.

• Deletion − delete an element at given index.

• Search − search an element using given index or by value.

• Update − update an element at given index.

In C, when an array is initialized with size, then it assigns defaults values to its elements in following order.

Example

#include <stdio.h>
#include <string.h>

static void display(int intArray[], int length){
   int i=0;
   printf("Array : [");
   for(i = 0; i < length; i++) {
      /* display value of element at index i. */
      printf(" %d ", intArray[i]);
   }
   printf(" ]n ");   
}

int main() {
   int i = 0;
   /* Declare an array */
   int intArray[8];

   // initialize elements of array n to 0          
   for ( i = 0; i < 8; i++ ) {
      intArray[ i ] = 0; // set elements to default value of 0;
   }
   printf("Array with default data.");

   /* Display elements of an array.*/
   display(intArray,8);     

   /* Operation : Insertion 
   Add elements in the array */
   for(i = 0; i < 8; i++) {
      /* place value of i at index i. */
      printf("Adding %d at index %dn",i,i);
      intArray[i] = i;
   }
   printf("n");
   printf("Array after adding data. ");
   display(intArray,8);

   /* Operation : Insertion 
   Element at any location can be updated directly */
   int index = 5;
   intArray[index] = 10;

   printf("Array after updating element at index %d.n",index);
   display(intArray,8);

   /* Operation : Search using index
   Search an element using index.*/
   printf("Data at index %d:%dn" ,index,intArray[index]);

   /* Operation : Search using value
   Search an element using value.*/
   int value = 4;
   for(i = 0; i < 8; i++) {
      if(intArray[i] == value ){
         printf("value %d Found at index %d n", intArray[i],i);
         break;
      }
   }
   return 0;
}

Array with default data.Array : [ 0 0 0 0 0 0 0 0 ]
Adding 0 at index 0
Adding 1 at index 1
Adding 2 at index 2
Adding 3 at index 3
Adding 4 at index 4
Adding 5 at index 5
Adding 6 at index 6
Adding 7 at index 7

Array after adding data. Array : [ 0 1 2 3 4 5 6 7 ]
Array after updating element at index 5.
Array : [ 0 1 2 3 4 10 6 7 ]
Data at index 5: 10
4 Found at index 4

//insert link at the first location
void insertFirst(int key, int data){
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   
   //point it to old first node
   link->next = head;
   
   //point first to new first node
   head = link;
}

//delete first item
struct node* deleteFirst(){
   //save reference to first link
   struct node *tempLink = head;
   
   //mark next to first link as first 
   head = head->next;
   
   //return the deleted link
   return tempLink;
}

//display the list
void printList(){
   struct node *ptr = head;
   printf("n[ ");
   
   //start from the beginning
   while(ptr != NULL){        
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
   printf(" ]");
}

void sort(){
   int i, j, k, tempKey, tempData ;
   struct node *current;
   struct node *next;
   int size = length();
   k = size ;
   for ( i = 0 ; i < size - 1 ; i++, k-- ) {
      current = head ;
      next = head->next ;
      for ( j = 1 ; j < k ; j++ ) {            
         if ( current->data > next->data ) {
            tempData = current->data ;
            current->data = next->data;
            next->data = tempData ;

            tempKey = current->key;
            current->key = next->key;
            next->key = tempKey;
         }
         current = current->next;
         next = next->next;                        
      }
   }
}

void reverse(struct node** head_ref) {
   struct node* prev   = NULL;
   struct node* current = *head_ref;
   struct node* next;
   while (current != NULL) {
      next  = current->next;  
      current->next = prev;   
      prev = current;
      current = next;
   }
   *head_ref = prev;
}

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

struct node {
   int data;
   int key;
   struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;

//display the list
void printList(){
   struct node *ptr = head;
   printf("n[ ");
   
   //start from the beginning
   while(ptr != NULL){        
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
   printf(" ]");
}
//insert link at the first location
void insertFirst(int key, int data){
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   
   //point it to old first node
   link->next = head;
   
   //point first to new first node
   head = link;
}
//delete first item
struct node* deleteFirst(){
   //save reference to first link
   struct node *tempLink = head;
   
   //mark next to first link as first 
   head = head->next;
   
   //return the deleted link
   return tempLink;
}
//is list empty
bool isEmpty(){
   return head == NULL;
}
int length(){
   int length = 0;
   struct node *current;
   for(current = head; current!=NULL;
      current = current->next){
      length++;
   }
   return length;
}
//find a link with given key
struct node* find(int key){
   //start from the first link
   struct node* current = head;

   //if list is empty
   if(head == NULL){
      return NULL;
   }
   //navigate through list
   while(current->key != key){
      //if it is last node
      if(current->next == NULL){
         return NULL;
      } else {
         //go to next link
         current = current->next;
      }
   }
   //if data found, return the current Link
   return current;
}
//delete a link with given key
struct node* delete(int key){
   //start from the first link
   struct node* current = head;
   struct node* previous = NULL;
   
   //if list is empty
   if(head == NULL){
      return NULL;
   }
   //navigate through list
   while(current->key != key){
      //if it is last node
      if(current->next == NULL){
         return NULL;
      } else {
         //store reference to current link
         previous = current;
         
         //move to next link
         current = current->next;             
      }
   }
   //found a match, update the link
   if(current == head) {
      //change first to point to next link
      head = head->next;
   } else {
      //bypass the current link
      previous->next = current->next;
   }
   return current;
}
void sort(){
   int i, j, k, tempKey, tempData ;
   struct node *current;
   struct node *next;
   int size = length();
   k = size ;
   for ( i = 0 ; i < size - 1 ; i++, k-- ) {
      current = head ;
      next = head->next ;
      for ( j = 1 ; j < k ; j++ ) {            
         if ( current->data > next->data ) {
            tempData = current->data ;
            current->data = next->data;
            next->data = tempData ;

            tempKey = current->key;
            current->key = next->key;
            next->key = tempKey;
         }
         current = current->next;
         next = next->next;                        
      }
   }
}
void reverse(struct node** head_ref) {
   struct node* prev   = NULL;
   struct node* current = *head_ref;
   struct node* next;
   while (current != NULL) {
      next  = current->next;  
      current->next = prev;   
      prev = current;
      current = next;
   }
   *head_ref = prev;
}

main() {
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56); 

   printf("Original List: "); 
   //print list
   printList();

   while(!isEmpty()){            
      struct node *temp = deleteFirst();
      printf("nDeleted value:");  
      printf("(%d,%d) ",temp->key,temp->data);        
   }         
   printf("nList after deleting all items: ");          
   printList();
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56); 
   printf("nRestored List: ");  
   printList();
   printf("n");  

   struct node *foundLink = find(4);
   if(foundLink != NULL){
      printf("Element found: ");  
      printf("(%d,%d) ",foundLink->key,foundLink->data);  
      printf("n");  
   } else {
      printf("Element not found.");  
   }
   delete(4);
   printf("List after deleting an item: ");  
   printList();
   printf("n");
   foundLink = find(4);
   if(foundLink != NULL){
      printf("Element found: ");  
      printf("(%d,%d) ",foundLink->key,foundLink->data);  
      printf("n");  
   } else {
      printf("Element not found.");  
   }
   printf("n");  
   sort();
   printf("List after sorting the data: ");  
   printList();
   reverse(&head);
   printf("nList after reversing the data: ");  
   printList();
}

Original List: 
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Deleted value:(6,56) 
Deleted value:(5,40) 
Deleted value:(4,1) 
Deleted value:(3,30) 
Deleted value:(2,20) 
Deleted value:(1,10) 
List after deleting all items: 
[ ]
Restored List: 
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]
Element found: (4,1) 
List after deleting an item: 
[ (6,56) (5,40) (3,30) (2,20) (1,10) ]
Element not found.
List after sorting the data: 
[ (1,10) (2,20) (3,30) (5,40) (6,56) ]
List after reversing the data: 
[ (6,56) (5,40) (3,30) (2,20) (1,10) ]

//insert link at the first location
void insertFirst(int key, int data){
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()){
      //make it the last link
      last = link;
   } else {
      //update first prev link
      head->prev = link;
   }
   //point it to old first link
   link->next = head;
   
   //point first to new first link
   head = link;
}

//delete first item
struct node* deleteFirst(){
   //save reference to first link
   struct node *tempLink = head;
   
   //if only one link
   if(head->next == NULL){
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
   head = head->next;
   
   //return the deleted link
   return tempLink;
}

//insert link at the last location
void insertLast(int key, int data){
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()){
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }
   //point last to new last node
   last = link;
}

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

struct node {
   int data;
   int key;
   struct node *next;
   struct node *prev;
};
//this link always point to first Link 
struct node *head = NULL;

//this link always point to last Link 
struct node *last = NULL;
struct node *current = NULL;

//is list empty
bool isEmpty(){
   return head == NULL;
}
int length(){
   int length = 0;
   struct node *current;
   for(current = head; current!=NULL;
      current = current->next){
      length++;
   }
   return length;
}
//display the list in from first to last
void displayForward(){
   //start from the beginning
   struct node *ptr = head;
   
   //navigate till the end of the list
   printf("n[ ");
   while(ptr != NULL){        
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
   printf(" ]");
}
//display the list from last to first
void displayBackward(){
   //start from the last
   struct node *ptr = last;
   
   //navigate till the start of the list
   printf("n[ ");
   while(ptr != NULL){    
      //print data
      printf("(%d,%d) ",ptr->key,ptr->data);
      
      //move to next item
      ptr = ptr ->prev;
      printf(" ");
   }
   printf(" ]");
}
//insert link at the first location
void insertFirst(int key, int data){
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()){
      //make it the last link
      last = link;
   } else {
      //update first prev link
      head->prev = link;
   }
   //point it to old first link
   link->next = head;
   
   //point first to new first link
   head = link;
}
//insert link at the last location
void insertLast(int key, int data){
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
   if(isEmpty()){
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }
   //point last to new last node
   last = link;
}
//delete first item
struct node* deleteFirst(){
   //save reference to first link
   struct node *tempLink = head;
   
   //if only one link
   if(head->next == NULL){
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
   head = head->next;
   //return the deleted link
   return tempLink;
}
//delete link at the last location
struct node* deleteLast(){
   //save reference to last link
   struct node *tempLink = last;
   
   //if only one link
   if(head->next == NULL){
      head = NULL;
   } else {
      last->prev->next = NULL;
   }
   last = last->prev;
   //return the deleted link
   return tempLink;
}
//delete a link with given key
struct node* delete(int key){
   //start from the first link
   struct node* current = head;
   struct node* previous = NULL;
   
   //if list is empty
   if(head == NULL){
      return NULL;
   }
   //navigate through list
   while(current->key != key){
      //if it is last node
      if(current->next == NULL){
         return NULL;
      } else {
         //store reference to current link
         previous = current;
         
         //move to next link
         current = current->next;             
      }
   }
   //found a match, update the link
   if(current == head) {
      //change first to point to next link
      head = head->next;
   } else {
      //bypass the current link
      current->prev->next = current->next;
   }    
   if(current == last){
      //change last to point to prev link
      last = current->prev;
   } else {
      current->next->prev = current->prev;
   }
   return current;
}
bool insertAfter(int key, int newKey, int data){
   //start from the first link
   struct node *current = head;      
   
   //if list is empty
   if(head == NULL){
      return false;
   }
   //navigate through list
   while(current->key != key){
      //if it is last node
      if(current->next == NULL){
         return false;
      } else {           
         //move to next link
         current = current->next;             
      }
   }
   //create a link
   struct node *newLink = (struct node*) malloc(sizeof(struct node));
   newLink->key = key;
   newLink->data = data;

   if(current==last) {
      newLink->next = NULL; 
      last = newLink; 
   } else {
      newLink->next = current->next;         
      current->next->prev = newLink;
   }
   newLink->prev = current; 
   current->next = newLink; 
   return true; 
}
main() {
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56); 

   printf("nList (First to Last): ");  
   displayForward();
   printf("n");
   printf("nList (Last to first): "); 
   displayBackward();

   printf("nList , after deleting first record: ");
   deleteFirst();        
   displayForward();

   printf("nList , after deleting last record: ");  
   deleteLast();
   displayForward();

   printf("nList , insert after key(4) : ");  
   insertAfter(4,7, 13);
   displayForward();

   printf("nList  , after delete key(4) : ");  
   delete(4);
   displayForward();
}

List (First to Last): 
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]

List (Last to first): 
[ (1,10) (2,20) (3,30) (4,1) (5,40) (6,56) ]
List , after deleting first record: 
[ (5,40) (4,1) (3,30) (2,20) (1,10) ]
List , after deleting last record: 
[ (5,40) (4,1) (3,30) (2,20) ]
List , insert after key(4) : 
[ (5,40) (4,1) (4,13) (3,30) (2,20) ]
List , after delete key(4) : 
[ (5,40) (4,13) (3,30) (2,20) ]

//insert link at the first location
void insertFirst(int key, int data){
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key =key;
   link->data=data;
   if (isEmpty()) {
      head  = link;
      head->next = head;
   } else {
      //point it to old first node
      link->next = head;
      
      //point first to new first node
      head = link;
   }
}

//delete first item
struct node * deleteFirst(){
   //save reference to first link
   struct node *tempLink = head;
   if(head->next == head){  
      head = NULL;
      return tempLink;
   }     
   //mark next to first link as first 
   head = head->next;
   
   //return the deleted link
   return tempLink;
}

//display the list
void printList(){
   struct node *ptr = head;
   printf("n[ ");
   //start from the beginning
   if(head != NULL){
      while(ptr->next != ptr){     
         printf("(%d,%d) ",ptr->key,ptr->data);
         ptr = ptr->next;
      }
   }
   printf(" ]");
}

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

struct node {
   int data;
   int key;
   struct node *next;
};

struct node *head = NULL;
struct node *current = NULL;

bool isEmpty(){
   return head == NULL;
}
int length(){
   int length = 0;

   //if list is empty
   if(head == NULL){
      return 0;
   }
   current = head->next;
   while(current != head){
      length++;
      current = current->next;   
   }
   return length;
}
//insert link at the first location
void insertFirst(int key, int data){
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key =key;
   link->data=data;
   if (isEmpty()) {
      head  = link;
      head->next = head;
   } else {
      //point it to old first node
      link->next = head;
      
      //point first to new first node
      head = link;
   }      
}
//delete first item
struct node * deleteFirst(){
   //save reference to first link
   struct node *tempLink = head;
   if(head->next == head){  
      head = NULL;
      return tempLink;
   }     
   //mark next to first link as first 
   head = head->next;
   
   //return the deleted link
   return tempLink;
}
//display the list
void printList(){
   struct node *ptr = head;
   printf("n[ ");
   
   //start from the beginning
   if(head != NULL){
      while(ptr->next != ptr){     
         printf("(%d,%d) ",ptr->key,ptr->data);
         ptr = ptr->next;
      }
   }
   printf(" ]");
}
main() {
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56); 
   printf("Original List: "); 
   
   //print list
   printList();

   while(!isEmpty()){            
      struct node *temp = deleteFirst();
      printf("nDeleted value:");  
      printf("(%d,%d) ",temp->key,temp->data);        
   }         
   printf("nList after deleting all items: ");          
   printList();   
}

Original List: 
[ (6,56) (5,40) (4,1) (3,30) (2,20) ]
Deleted value:(6,56) 
Deleted value:(5,40) 
Deleted value:(4,1) 
Deleted value:(3,30) 
Deleted value:(2,20) 
Deleted value:(1,10) 
List after deleting all items: 
[ ]

// Operation : Push
// push item on the top of the stack 
void push(int data) {
   if(!isFull()){
      // increment top by 1 and insert data 
      intArray[++top] = data;
   } else {
      printf("Cannot add data. Stack is full.n");
   }      
}

// Operation : Pop
// pop item from the top of the stack 
int pop() {
   //retrieve data and decrement the top by 1
   return intArray[top--];        
}

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

// size of the stack
int size = 8;       

// stack storage
int intArray[8];     

// top of the stack
int top = -1;            

// Operation : Pop
// pop item from the top of the stack 
int pop() {
   //retrieve data and decrement the top by 1
   return intArray[top--];        
}
// Operation : Peek
// view the data at top of the stack 
int peek() {       
   //retrieve data from the top
   return intArray[top];
}
//Operation : isFull
//return true if stack is full 
bool isFull(){
   return (top == size-1);
}

// Operation : isEmpty
// return true if stack is empty 
bool isEmpty(){
   return (top == -1);
}
// Operation : Push
// push item on the top of the stack 
void push(int data) {
   if(!isFull()){
      // increment top by 1 and insert data 
      intArray[++top] = data;
   } else {
      printf("Cannot add data. Stack is full.n");
   }      
}
main() {
   // push items on to the stack 
   push(3);
   push(5);
   push(9);
   push(1);
   push(12);
   push(15);

   printf("Element at top of the stack: %dn" ,peek());
   printf("Elements: n");

   // print stack data 
   while(!isEmpty()){
      int data = pop();
      printf("%dn",data);
   }
   printf("Stack full: %sn" , isFull()?"true":"false");
   printf("Stack empty: %sn" , isEmpty()?"true":"false");
}

Element at top of the stack: 15
Elements: 
15
12
1
9
5
3
Stack full: false
Stack empty: true

#include<stdio.h> 
#include<string.h> 

//char stack
char stack[25]; 
int top=-1; 

void push(char item) { 
   stack[++top]=item; 
}
char pop() { 
   return stack[top--]; 
}

//returns precedence of operators
int precedence(char symbol) { 
   switch(symbol) { 
      case ''+'': 
      case ''-'':
         return 2; 
         break; 
      case ''*'': 
      case ''/'':
         return 3; 
         break; 
      case ''^'': 
         return 4; 
         break; 
      case ''('': 
      case '')'': 
      case ''#'':
         return 1; 
         break; 
   }
}

//check whether the symbol is operator?
int isOperator(char symbol) { 
   switch(symbol){ 
      case ''+'': 
      case ''-'': 
      case ''*'': 
      case ''/'': 
      case ''^'': 
      case ''('': 
      case '')'':
         return 1; 
      break; 
         default:
         return 0; 
   } 
}
//converts infix expression to postfix
void convert(char infix[],char postfix[]){ 
   int i,symbol,j=0; 
   stack[++top]=''#''; 
   for(i=0;i<strlen(infix);i++){ 
      symbol=infix[i]; 
      if(isOperator(symbol)==0){ 
         postfix[j]=symbol; 
         j++; 
      } else {
         if(symbol==''(''){			
            push(symbol); 
         } else { 
            if(symbol=='')''){ 
               while(stack[top]!=''(''){ 
                  postfix[j]=pop(); 
                  j++; 
               } 
               pop();//pop out (. 
            } else { 
               if(precedence(symbol)>precedence(stack[top])) {
                  push(symbol); 
               } else { 
                  while(precedence(symbol)<=precedence(stack[top])) { 
                     postfix[j]=pop(); 
                     j++; 
                  } 
                  push(symbol); 
               }
            }
         }
      }
   }
   while(stack[top]!=''#'') {
      postfix[j]=pop(); 
      j++; 
   }
   postfix[j]='''';//null terminate string. 
} 
//int stack
int stack_int[25]; 
int top_int=-1; 

void push_int(int item) { 
   stack_int[++top_int]=item; 
} 

char pop_int() { 
   return stack_int[top_int--]; 
} 
//evaluates postfix expression
int evaluate(char *postfix){
   char ch;
   int i=0,operand1,operand2;

   while( (ch=postfix[i++]) != '''') {
      if(isdigit(ch)){ 
	     push_int(ch-''0''); // Push the operand 
      } else {
         //Operator,pop two  operands 
         operand2=pop_int();
         operand1=pop_int();
         switch(ch) {
            case ''+'':
               push_int(operand1+operand2);
               break;
            case ''-'':
               push_int(operand1-operand2);
               break;
            case ''*'':
               push_int(operand1*operand2);
               break;
            case ''/'':
               push_int(operand1/operand2);
               break;
         }
      }
   }
   return stack_int[top_int];
}
void main() {
   char infix[25] = "1*(2+3)",postfix[25]; 
   convert(infix,postfix); 
   printf("Infix expression is: %sn" , infix);
   printf("Postfix expression is: %sn" , postfix);
   printf("Evaluated expression is: %dn" , evaluate(postfix));
} 

Infix expression is: 1*(2+3)
Postfix expression is: 123+*
Result is: 5

void insert(int data){
   if(!isFull()){
      if(rear == MAX-1){
         rear = -1;            
      }       
      intArray[++rear] = data;
      itemCount++;
   }
}

int removeData(){
   int data = intArray[front++];
   if(front == MAX){
      front = 0;
   }
   itemCount--;
   return data;  
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6

int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;

int peek(){
   return intArray[front];
}
bool isEmpty(){
   return itemCount == 0;
}
bool isFull(){
   return itemCount == MAX;
}
int size(){
   return itemCount;
}
void insert(int data){
   if(!isFull()){
      if(rear == MAX-1){
         rear = -1;            
      }       
      intArray[++rear] = data;
      itemCount++;
   }
}
int removeData(){
   int data = intArray[front++];
   if(front == MAX){
      front = 0;
   }
   itemCount--;
   return data;  
}
int main() {
   /* insert 5 items */
   insert(3);
   insert(5);
   insert(9);
   insert(1);
   insert(12);

   // front : 0
   // rear  : 4
   // ------------------
   // index : 0 1 2 3 4 
   // ------------------
   // queue : 3 5 9 1 12
   insert(15);

   // front : 0
   // rear  : 5
   // ---------------------
   // index : 0 1 2 3 4  5 
   // ---------------------
   // queue : 3 5 9 1 12 15
   if(isFull()){
      printf("Queue is full!n");   
   }

   // remove one item 
   int num = removeData();
   printf("Element removed: %dn",num);
   // front : 1
   // rear  : 5
   // -------------------
   // index : 1 2 3 4  5
   // -------------------
   // queue : 5 9 1 12 15

   // insert more items
   insert(16);

   // front : 1
   // rear  : -1
   // ----------------------
   // index : 0  1 2 3 4  5
   // ----------------------
   // queue : 16 5 9 1 12 15

   // As queue is full, elements will not be inserted. 
   insert(17);
   insert(18);

   // ----------------------
   // index : 0  1 2 3 4  5
   // ----------------------
   // queue : 16 5 9 1 12 15
   printf("Element at front: %dn",peek());

   printf("----------------------n");
   printf("index : 5 4 3 2  1  0n");
   printf("----------------------n");
   printf("Queue:  ");
   while(!isEmpty()){
      int n = removeData();           
      printf("%d ",n);
   }   
}

Queue is full!
Element removed: 3
Element at front: 5
----------------------
index : 5 4 3 2 1 0
----------------------
Queue: 5 9 1 12 15 16

void insert(int data){
   int i =0;

   if(!isFull()){
      // if queue is empty, insert the data 
      if(itemCount == 0){
         intArray[itemCount++] = data;        
      } else {
         // start from the right end of the queue 
         for(i = itemCount - 1; i >= 0; i-- ){
            // if data is larger, shift existing item to right end 
            if(data > intArray[i]){
               intArray[i+1] = intArray[i];
            } else {
               break;
            }          
         }   
         // insert the data 
         intArray[i+1] = data;
         itemCount++;
      }
   }
}

int removeData(){
   return intArray[--itemCount]; 
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6

int intArray[MAX];
int itemCount = 0;

int peek(){
   return intArray[itemCount - 1];
}
bool isEmpty(){
   return itemCount == 0;
}
bool isFull(){
   return itemCount == MAX;
}
int size(){
   return itemCount;
}
void insert(int data){
   int i =0;

   if(!isFull()){
      // if queue is empty, insert the data 
      if(itemCount == 0){
         intArray[itemCount++] = data;        
      } else {
         // start from the right end of the queue 
         for(i = itemCount - 1; i >= 0; i-- ){
            // if data is larger, shift existing item to right end 
            if(data > intArray[i]){
               intArray[i+1] = intArray[i];
            } else {
               break;
            }            
         } 
         // insert the data 
         intArray[i+1] = data;
         itemCount++;
      }
   }
}
int removeData(){
   return intArray[--itemCount]; 
}
int main() {
   /* insert 5 items */
   insert(3);
   insert(5);
   insert(9);
   insert(1);
   insert(12);

   // ------------------
   // index : 0  1 2 3 4 
   // ------------------
   // queue : 12 9 5 3 1 
   insert(15);

   // ---------------------
   // index : 0  1 2 3 4  5 
   // ---------------------
   // queue : 15 12 9 5 3 1 
   if(isFull()){
      printf("Queue is full!n");   
   }

   // remove one item 
   int num = removeData();
   printf("Element removed: %dn",num);
   // ---------------------
   // index : 0  1  2 3 4 
   // ---------------------
   // queue : 15 12 9 5 3  

   // insert more items
   insert(16);

   // ----------------------
   // index :  0  1 2 3 4  5
   // ----------------------
   // queue : 16 15 12 9 5 3

   // As queue is full, elements will not be inserted. 
   insert(17);
   insert(18);

   // ----------------------
   // index : 0   1  2 3 4 5
   // ----------------------
   // queue : 16 15 12 9 5 3
   printf("Element at front: %dn",peek());

   printf("----------------------n");
   printf("index : 5 4 3 2  1  0n");
   printf("----------------------n");
   printf("Queue:  ");
   while(!isEmpty()){
      int n = removeData();           
      printf("%d ",n);
   }   
}

Queue is full!
Element removed: 1
Element at front: 3
----------------------
index : 5 4 3 2 1 0
----------------------
Queue: 3 5 9 12 15 16

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
   while(current->data != data){
      if(current != NULL)
         printf("%d ",current->data); 
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }//else go to right tree
         else{               
            current = current->rightChild;
         }
         //not found
         if(current == NULL){
            return NULL;
         }
      }
   return current;
}

void insert(int data){
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL){
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1){                
         parent = current;
         //go to left of the tree
         if(data < parent->data){
            current = current->leftChild;                
            //insert to the left
            if(current == NULL){
               parent->leftChild = tempNode;
               return;
            }
         }//go to right of the tree
         else{
            current = current->rightChild;
            //insert to the right
            if(current == NULL){
               parent->rightChild = tempNode;
               return;
            }
         }
      }
   }
}        

void preOrder(struct node* root){
   if(root!=NULL){
      printf("%d ",root->data);
      preOrder(root->leftChild);
      preOrder(root->rightChild);
   }
}

void inOrder(struct node* root){
   if(root!=NULL){
      inOrder(root->leftChild);
      printf("%d ",root->data);          
      inOrder(root->rightChild);
   }
}

void postOrder(struct node* root){
   if(root!=NULL){            
      postOrder(root->leftChild);
      postOrder(root->rightChild);
      printf("%d ",root->data);
   }
}

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

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};
struct node *root = NULL;
void insert(int data){
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL){
      root = tempNode;
   } else {
      current = root;
      parent = NULL;
      while(1){                
         parent = current;
         //go to left of the tree
         if(data < parent->data){
            current = current->leftChild;                
            //insert to the left
            if(current == NULL){
               parent->leftChild = tempNode;
               return;
            }
         }//go to right of the tree
         else{
            current = current->rightChild;
            //insert to the right
            if(current == NULL){
               parent->rightChild = tempNode;
               return;
            }
         }
      }       
   }
}
struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
   while(current->data != data){
      if(current != NULL)
         printf("%d ",current->data); 
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }//else go to right tree
         else{                
            current = current->rightChild;
         }
         //not found
         if(current == NULL){
            return NULL;
         }
      }
   return current;
}
void preOrder(struct node* root){
   if(root!=NULL){
      printf("%d ",root->data);
      preOrder(root->leftChild);
      preOrder(root->rightChild);
   }
}
void inOrder(struct node* root){
   if(root!=NULL){
      inOrder(root->leftChild);
      printf("%d ",root->data);          
      inOrder(root->rightChild);
   }
}
void postOrder(struct node* root){
   if(root!=NULL){            
      postOrder(root->leftChild);
      postOrder(root->rightChild);
      printf("%d ",root->data);
   }
}
void traverse(int traversalType){
   switch(traversalType){
      case 1:
         printf("nPreorder traversal: ");
         preOrder(root);
         break;
      case 2:
         printf("nInorder traversal: ");
         inOrder(root);
         break;
      case 3:
         printf("nPostorder traversal: ");
         postOrder(root);
         break;
   }            
}  

int main()
{
   /*                     11               //Level 0
   */
   insert(11);
   /*                     11               //Level 0
   *                      |
   *                      |---20           //Level 1
   */
   insert(20);
   /*                     11               //Level 0
   *                      |
   *                  3---|---20           //Level 1
   */
   insert(3);        
   /*                     11               //Level 0
   *                      |
   *                  3---|---20           //Level 1
   *                           |
   *                           |--42       //Level 2
   */
   insert(42);
   /*                     11               //Level 0
   *                      |
   *                  3---|---20           //Level 1
   *                           |
   *                           |--42       //Level 2
   *                               |
   *                               |--54   //Level 3
   */
   insert(54);
   /*                     11               //Level 0
   *                      |
   *                  3---|---20           //Level 1
   *                           |
   *                       16--|--42       //Level 2
   *                               |
   *                               |--54   //Level 3
   */
   insert(16);
   /*                     11               //Level 0
   *                      |
   *                  3---|---20           //Level 1
   *                           |
   *                       16--|--42       //Level 2
   *                               |
   *                           32--|--54   //Level 3
   */
   insert(32);
   /*                     11               //Level 0
   *                      |
   *                  3---|---20           //Level 1
   *                  |        |
   *                  |--9 16--|--42       //Level 2
   *                               |
   *                           32--|--54   //Level 3
   */
   insert(9);
   /*                     11               //Level 0
   *                      |
   *                  3---|---20           //Level 1
   *                  |        |
   *                  |--9 16--|--42       //Level 2
   *                     |         |
   *                  4--|     32--|--54   //Level 3
   */
   insert(4);
   /*                     11               //Level 0
   *                      |
   *                  3---|---20           //Level 1
   *                  |        |
   *                  |--9 16--|--42       //Level 2
   *                     |         |
   *                  4--|--10 32--|--54   //Level 3
   */
   insert(10);

   struct node * temp = search(32);
   if(temp!=NULL){
      printf("Element found.n");
      printf("( %d )",temp->data);
      printf("n");
   } else {
      printf("Element not found.n");
   }

   struct node *node1 = search(2);
   if(node1!=NULL){
      printf("Element found.n");
      printf("( %d )",node1->data);
      printf("n");
   } else {
      printf("Element not found.n");
   }        

   //pre-order traversal
   //root, left ,right
   traverse(1);
   //in-order traversal
   //left, root ,right
   traverse(2);
   //post order traversal
   //left, right, root
   traverse(3);       
}

Visiting elements: 11 20 42 Element found.(32)
Visiting elements: 11 3 Element not found.

Preorder traversal: 11 3 9 4 10 20 16 42 32 54 
Inorder traversal: 3 4 9 10 11 16 20 32 42 54 
Postorder traversal: 4 10 9 3 16 32 54 42 20 11

struct DataItem {
   int data;   
   int key;
};

int hashCode(int key){
   return key % SIZE;
}

struct DataItem *search(int key){               
   //get the hash 
   int hashIndex = hashCode(key);        
   
   //move in array until an empty 
   while(hashArray[hashIndex] !=NULL){
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex]; 
      //go to next cell
      ++hashIndex;
      //wrap around the table
      hashIndex %= SIZE;
   }
   return NULL;        
}

void insert(int key,int data){
   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;  
   item->key = key;     

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] !=NULL &&
      hashArray[hashIndex]->key != -1){
      //go to next cell
      ++hashIndex;
      //wrap around the table
      hashIndex %= SIZE;
   }
   hashArray[hashIndex] = item;        
}

struct DataItem* delete(struct DataItem* item){
   int key = item->key;

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty 
   while(hashArray[hashIndex] !=NULL){
      if(hashArray[hashIndex]->key == key){
         struct DataItem* temp = hashArray[hashIndex]; 
         
         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem; 
         return temp;
      }               
      //go to next cell
      ++hashIndex;
      //wrap around the table
      hashIndex %= SIZE;
   }
   return NULL;        
}

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

#define SIZE 20

struct DataItem {
   int data;   
   int key;
};

struct DataItem* hashArray[SIZE]; 
struct DataItem* dummyItem;
struct DataItem* item;

int hashCode(int key){
   return key % SIZE;
}

struct DataItem *search(int key){               
   //get the hash
   int hashIndex = hashCode(key);        
   
   //move in array until an empty 
   while(hashArray[hashIndex] !=NULL){
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex]; 
      //go to next cell
      ++hashIndex;
      //wrap around the table
      hashIndex %= SIZE;
   }        
   return NULL;        
}

void insert(int key,int data){
   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;  
   item->key = key;     

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] !=NULL &&
      hashArray[hashIndex]->key != -1){
      //go to next cell
      ++hashIndex;
      //wrap around the table
      hashIndex %= SIZE;
   }
   hashArray[hashIndex] = item;        
}
struct DataItem* delete(struct DataItem* item){
   int key = item->key;

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty 
   while(hashArray[hashIndex] !=NULL){
      if(hashArray[hashIndex]->key == key){
         struct DataItem* temp = hashArray[hashIndex]; 
         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem; 
         return temp;
      }
      //go to next cell
      ++hashIndex;
      //wrap around the table
      hashIndex %= SIZE;
   }
   return NULL;        
}
void display(){
   int i=0;
   for(i=0; i<SIZE; i++) {
      if(hashArray[i] != NULL)
         printf(" (%d,%d)",hashArray[i]->key,hashArray[i]->data);
      else
         printf(" ~~ ");
   }
   printf("n");
}
int main(){
   dummyItem = (struct DataItem*) malloc(sizeof(struct DataItem));
   dummyItem->data = -1;  
   dummyItem->key = -1; 

   insert(1, 20);
   insert(2, 70);
   insert(42, 80);
   insert(4, 25);
   insert(12, 44);
   insert(14, 32);
   insert(17, 11);
   insert(13, 78);
   insert(37, 97);

   display();
   item = search(37);

   if(item != NULL){
      printf("Element found: %dn", item->data);
   } else {
      printf("Element not foundn");
   }

   delete(item);
   item = search(37);

   if(item != NULL){
      printf("Element found: %dn", item->data);
   } else {
      printf("Element not foundn");
   }
}

 ~~  (1,20)  (2,70)  (42,80)  (4,25)  ~~  ~~  ~~  ~~  ~~  ~~  ~~ (12,44)  (13,78)  (14,32)  ~~  ~~  (17,11)  (37,97)  ~~ 
Element found: 97
Element not found

void insert(int value) {            
   size++;
   intArray[size - 1] = value;
   heapUp(size - 1);
}
void heapUp(int nodeIndex){
   int parentIndex, tmp;
   if (nodeIndex != 0) {
      parentIndex = getParentIndex(nodeIndex);
      if (intArray[parentIndex] > intArray[nodeIndex]) {
         tmp = intArray[parentIndex];
         intArray[parentIndex] = intArray[nodeIndex];
         intArray[nodeIndex] = tmp;
         heapUp(parentIndex);
      }
   }
}

int getMinimum(){
   return intArray[0];
}

void removeMin() {
   intArray[0] = intArray[size - 1];
   size--;
   if (size > 0)
      heapDown(0);
}
void heapDown(int nodeIndex){
   int leftChildIndex, rightChildIndex, minIndex, tmp;
   leftChildIndex = getLeftChildIndex(nodeIndex);
   rightChildIndex = getRightChildIndex(nodeIndex);
   if (rightChildIndex >= size) {
      if (leftChildIndex >= size)
         return;
      else
         minIndex = leftChildIndex;
   } else {
      if (intArray[leftChildIndex] <= intArray[rightChildIndex])
         minIndex = leftChildIndex;
      else
         minIndex = rightChildIndex;
   }
   if (intArray[nodeIndex] > intArray[minIndex]) {
      tmp = intArray[minIndex];
      intArray[minIndex] = intArray[nodeIndex];
      intArray[nodeIndex] = tmp;
      heapDown(minIndex);
   }
}

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

int intArray[10];
int size;

bool isEmpty(){
   return size == 0;
}
int getMinimum(){
   return intArray[0];
}
int getLeftChildIndex(int nodeIndex){
   return 2*nodeIndex +1;
}
int getRightChildIndex(int nodeIndex){
   return 2*nodeIndex +2;
}
int getParentIndex(int nodeIndex){
   return (nodeIndex -1)/2;
}
bool isFull(){
   return size == 10;
}
/**
* Heap up the new element,until heap property is broken. 
* Steps:
* 1. Compare node''s value with parent''s value. 
* 2. Swap them, If they are in wrong order.
* */
void heapUp(int nodeIndex){
   int parentIndex, tmp;
   if (nodeIndex != 0) {
      parentIndex = getParentIndex(nodeIndex);
      if (intArray[parentIndex] > intArray[nodeIndex]) {
         tmp = intArray[parentIndex];
         intArray[parentIndex] = intArray[nodeIndex];
         intArray[nodeIndex] = tmp;
         heapUp(parentIndex);
      }
   }
}
/**
* Heap down the root element being least in value,until heap property is broken. 
* Steps:
* 1.If current node has no children, done.  
* 2.If current node has one children and heap property is broken, 
* 3.Swap the current node and child node and heap down.
* 4.If current node has one children and heap property is broken, find smaller one
* 5.Swap the current node and child node and heap down.
* */
void heapDown(int nodeIndex){
   int leftChildIndex, rightChildIndex, minIndex, tmp;
   leftChildIndex = getLeftChildIndex(nodeIndex);
   rightChildIndex = getRightChildIndex(nodeIndex);
   if (rightChildIndex >= size) {
      if (leftChildIndex >= size)
         return;
      else
         minIndex = leftChildIndex;
   } else {
      if (intArray[leftChildIndex] <= intArray[rightChildIndex])
         minIndex = leftChildIndex;
      else
         minIndex = rightChildIndex;
   }
   if (intArray[nodeIndex] > intArray[minIndex]) {
      tmp = intArray[minIndex];
      intArray[minIndex] = intArray[nodeIndex];
      intArray[nodeIndex] = tmp;
      heapDown(minIndex);
   }
}
void insert(int value) {            
   size++;
   intArray[size - 1] = value;
   heapUp(size - 1);
}
void removeMin() {
   intArray[0] = intArray[size - 1];
   size--;
   if (size > 0)
      heapDown(0);
}
main() {
   /*                     5                //Level 0
   * 
   */
   insert(5);
   /*                     1                //Level 0
   *                     |
   *                 5---|                 //Level 1
   */   
   insert(1);
   /*                     1                //Level 0
   *                     |
   *                 5---|---3             //Level 1
   */
   insert(3);
   /*                     1                //Level 0
   *                     |
   *                 5---|---3             //Level 1
   *                 |
   *              8--|                     //Level 2
   */
   insert(8);
   /*                     1                //Level 0
   *                     |
   *                 5---|---3             //Level 1
   *                 |
   *              8--|--9                  //Level 2
   */
   insert(9);
   /*                     1                 //Level 0
   *                     |
   *                 5---|---3              //Level 1
   *                 |       |
   *              8--|--9 6--|              //Level 2
   */
   insert(6);
   /*                     1                 //Level 0
   *                     |
   *                 5---|---2              //Level 1
   *                 |       | 
   *              8--|--9 6--|--3           //Level 2
   */
   insert(2);

   printf("%d", getMinimum());

   removeMin();
   /*                     2                 //Level 0
   *                     |
   *                 5---|---3              //Level 1
   *                 |       |
   *              8--|--9 6--|              //Level 2
   */
   printf("n%d", getMinimum());   
}

1
2

//add vertex to the vertex list
void addVertex(char label){
struct vertex* vertex = 
   (struct vertex*) malloc(sizeof(struct vertex));
   vertex->label = label;  
   vertex->visited = false;     
   lstVertices[vertexCount++] = vertex;
}

//add edge to edge array
void addEdge(int start,int end){
   adjMatrix[start][end] = 1;
   adjMatrix[end][start] = 1;
}

//display the vertex
void displayVertex(int vertexIndex){
   printf("%c ",lstVertices[vertexIndex]->label);
}      

void depthFirstSearch(){
   int i;
   //mark first node as visited
   lstVertices[0]->visited = true;
   
   //display the vertex
   displayVertex(0);   
   
   //push vertex index in stack
   push(0);

   while(!isStackEmpty()){
      //get the unvisited vertex of vertex which is at top of the stack
      int unvisitedVertex = getAdjUnvisitedVertex(peek());
      
      //no adjacent vertex found
      if(unvisitedVertex == -1){
         pop();
      } else {
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         push(unvisitedVertex);
      }
   }
   //stack is empty, search is complete, reset the visited flag        
   for(i=0;i < vertexCount;i++){
      lstVertices[i]->visited = false;
   }        
}

void breadthFirstSearch(){
   int i;
   //mark first node as visited
   lstVertices[0]->visited = true;
   
   //display the vertex
   displayVertex(0);   
   
   //insert vertex index in queue
   insert(0);
   int unvisitedVertex;
   while(!isQueueEmpty()){
      //get the unvisited vertex of vertex which is at front of the queue
      int tempVertex = removeData();         
      
      //no adjacent vertex found
      while((unvisitedVertex=getAdjUnvisitedVertex(tempVertex)) != -1){    
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         insert(unvisitedVertex);               
      }
   } 
   //queue is empty, search is complete, reset the visited flag        
   for(i=0;i<vertexCount;i++){
      lstVertices[i]->visited = false;
   }    
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 10

struct Vertex {
   char label;
   bool visited;
};

//stack variables
int stack[MAX]; 
int top=-1; 

//queue variables
int queue[MAX];
int rear=-1;
int front=0;
int queueItemCount = 0;

//graph variables
//array of vertices
struct Vertex* lstVertices[MAX];

//adjacency matrix
int adjMatrix[MAX][MAX];

//vertex count
int vertexCount = 0;

//stack functions
void push(int item) { 
   stack[++top]=item; 
}
int pop() { 
   return stack[top--]; 
} 
int peek() {         
   return stack[top];
}
bool isStackEmpty(){
   return top == -1;
}
//queue functions
void insert(int data){
   queue[++rear] = data;
   queueItemCount++;
}
int removeData(){
   queueItemCount--;
   return queue[front++]; 
}
bool isQueueEmpty(){
   return queueItemCount == 0;
}
//graph functions
//add vertex to the vertex list
void addVertex(char label){
   struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
   vertex->label = label;  
   vertex->visited = false;     
   lstVertices[vertexCount++] = vertex;
}
//add edge to edge array
void addEdge(int start,int end){
   adjMatrix[start][end] = 1;
   adjMatrix[end][start] = 1;
}
//display the vertex
void displayVertex(int vertexIndex){
   printf("%c ",lstVertices[vertexIndex]->label);
}
//get the adjacent unvisited vertex
int getAdjUnvisitedVertex(int vertexIndex){
   int i;
   for(i=0; i<vertexCount; i++)
      if(adjMatrix[vertexIndex][i]==1 && lstVertices[i]->visited==false)
         return i;
   return -1;
}
void depthFirstSearch(){
   int i;
   //mark first node as visited
   lstVertices[0]->visited = true;
   
   //display the vertex
   displayVertex(0);   
   
   //push vertex index in stack
   push(0);

   while(!isStackEmpty()){
      //get the unvisited vertex of vertex which is at top of the stack
      int unvisitedVertex = getAdjUnvisitedVertex(peek());
      
      //no adjacent vertex found
      if(unvisitedVertex == -1){
         pop();
      } else {
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         push(unvisitedVertex);
      }
   }
   //stack is empty, search is complete, reset the visited flag        
   for(i=0;i < vertexCount;i++){
      lstVertices[i]->visited = false;
   }        
}
void breadthFirstSearch(){
   int i;
   //mark first node as visited
   lstVertices[0]->visited = true;
   
   //display the vertex
   displayVertex(0);   
   
   //insert vertex index in queue
   insert(0);
   int unvisitedVertex;
   while(!isQueueEmpty()){
      //get the unvisited vertex of vertex which is at front of the queue
      int tempVertex = removeData();         
      
      //no adjacent vertex found
      while((unvisitedVertex=getAdjUnvisitedVertex(tempVertex)) != -1){    
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         insert(unvisitedVertex);               
      }
   }
   //queue is empty, search is complete, reset the visited flag        
   for(i=0;i<vertexCount;i++){
      lstVertices[i]->visited = false;
   }    
}
main() {
   int i, j;
   
   for(i=0; i<MAX; i++) // set adjacency
      for(j=0; j<MAX; j++) // matrix to 0
         adjMatrix[i][j] = 0;

   addVertex(''A'');   //0
   addVertex(''B'');   //1
   addVertex(''C'');   //2
   addVertex(''D'');   //3
   addVertex(''E'');   //4
   addVertex(''F'');   //5
   addVertex(''G'');   //6

   /*      1  2  3   
   * 0  |--B--C--D
   * A--|
   * |
   * |     4 
   * |-----E
   * |     5  6
   * |  |--F--G
   * |--| 
   */        
   addEdge(0, 1);   //AB
   addEdge(1, 2);   //BC
   addEdge(2, 3);   //CD
   addEdge(0, 4);   //AC
   addEdge(0, 5);   //AF
   addEdge(5, 6);   //FG
   printf("Depth First Search: ");
   
   //A B C D E F G
   depthFirstSearch();              
   printf("nBreadth First Search: ");
   
   //A B E F C G D
   breadthFirstSearch();
}

Depth First Search: A B C D E F G 
Breadth First Search: A B E F C G D

int factorial(int n){
   //base case
   if(n == 0){
      return 1;
   } else {
      return n * factorial(n-1);
   }
}

#include <stdio.h>

int factorial(int n){
   //base case
   if(n == 0){
      return 1;
   } else {
      return n * factorial(n-1);
   }
}
int fibbonacci(int n){
   if(n ==0){
      return 0;
   }
   else if(n==1){
      return 1;
   } else {
      return (fibbonacci(n-1) + fibbonacci(n-2));
   }
}
main(){
   int n = 5;
   int i;
   printf("Factorial of %d: %dn" , n , factorial(n));
   printf("Fibbonacci of %d: " , n);
   for(i=0;i<n;i++){
      printf("%d ",fibbonacci(i));            
   }
}

Factorial of 5: 120
Fibbonacci of 5: 0 1 1 2 3