Concept of trees in C:

The concept of trees is same to real world tree. In real word every tree has roots, and can have many branches. Each branch can have sub-branches. If you look at branches and sub-branches as a whole, the combination looks like a tree (lets call it a sub-tree). Same is the case of a tree in programming jargon. There is only one difference in plotting the trees. A real world tree has roots on the downside while in C programming, a tree is upside down which has roots on the top and sub-trees below that. Tree is a variation of linked lists.

Here in programming the most commonly used tree is a binary tree. Now lets come to data-structural jargon. A binary tree is a tree in a tree (data structure) in which each node (say current node) has addresses of 2 next possible nodes. The current node is called parent node and these next 2 nodes are called children of that node. We'll call them left child and right child. From the current node, if you want to come down, you have 2 options (either you can come on left child or the right child).

You people have seen that we can traverse a singly linked list in one direction and doubly linked list in two directions in the similar way in a tree you can reach max three nodes from a current node. So in a binary tree each node has only 2 address pointers, you can traverse only in the down direction. If you want to traverse the tree in both the directions (downward as well as upward), each node must be having address of its parent node also.

Here the node structure is a bit different. You can think of a binary tree as a continuation of linked lists from singly to doubly to binary tree. Let me explain further. In node of a singly connected linked list we have one single pointer pointing to next node and in node of a doubly connected linked list we have 2 pointers which can point to other 2 nodes (next and previous nodes). Similarly in a node of a binary tree we have 3 pointers which can point to 3 other nodes one to parent, one to left child, one to right child so that we can traverse easily in both the directions.

A program to count the occurrences of a string in a given text

The need: 

     This is a simple program to count the occurrences of a string in a given text. The code is straight forward and uses built-in function strstr().

The code: 
---------------------------------------------------------

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

int count_occur(char *big, char *small);

int main()
{
    char big_string[]="The fat cat sat on a mat",search_string[]="at";
    printf("total %d occurrences found\n",count_occur(big_string,search_string));
    return 0;
}

int count_occur(char *big, char *small)
{
    char *temp;
    int count=0;
    temp=strstr(big,small);
    while (temp!=NULL)
    {
        temp=strstr(temp+1,small);
        count++;
    }
    return (count);
}

--------------------------------------------------------

program 78: do everything with linked list

The need:
This is a program to show almost all basic operations on linked lists. This program is just a combination of various programs of linked lists written by me. This is written in a way that you can pick data and function definitions and can use as-it-is in other programs.
The code:
------------------------------------------------------------

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

// defining data-type node 
struct linked_list 
{ 
    int num;
    struct linked_list *next;
}; 
typedef struct linked_list node ;   //defining datatype node 

//declaration of functions 

node *create_list(node *p); 
node *reverse(node *p); 
int count (node *p); 
void print(node *p); 
node *insert(node *p); 
node *find(node *p,int a); 
node *hatana(node *p); 
node *insert_sort(node *head,int n); 
void sort(node *p); 
node *rearrange(node *p); 

main() 
{ 
    int i;
    node *head=NULL ;
    printf("This is a program to do with linked list .\n\n");
    lebel:
    printf("Options :\n(1)Create linked list.\n(2)view list.\n(3)Insert element.\n(4)Delete Element.\n");
    printf("(5)To arrange list in increasing order.\n");
    printf("(6)To remove double entries .\n(7)to reverse the list\n(8)Exit program.\n");
    scanf("%d",&i);
    switch(i)
    {
        case 1 :
                printf("Enter element numbers .\n");
                printf("Type -999 to end :\n");
                head=create_list(head);
                printf("List created successfully .\nNumber of items in the list are %d.\n\n\n",count(head));
                goto lebel;
        case 2 :
                print(head);
                goto lebel ;
        case 3 :         
                head=insert(head);
                goto lebel ;
        case 4 :         
                head=hatana(head);
                goto lebel ;
        case 5 :
                sort(head);
                printf("\nsorted in increasing order\n\n");
                goto lebel;
        case 6 :
                rearrange(head);
                printf("\nduplicate entries deleted\n\n");
                goto lebel;
        case 7 :
                head=reverse(head);
                printf("\nList reversed\n\n");
                goto lebel;
        case 8 :
                exit (0);
                break;         
        default:     
                printf("Invalid Choice !!!.\n");
                goto lebel ;
                break;
    }
     
     
    return 0;
        
}                //main ends here 

node *create_list(node *list) 
{ 
    int i;
    list=NULL;
    scanf("%d",&i);
    if(i!=-999)
    {
        list=(node*)malloc(sizeof(node));
        list->num=i;
        list->next=create_list(list->next);
    }
    return list;
} 

node *reverse(node *p) 
{ 
    node *temp=NULL,*rev=NULL;
    while(p)
    {
        temp=p;
        p=p->next;
        temp->next=rev;
        rev=temp;
    }
    return(rev);
} 

int count (node *list) 
{ 
    if(list==NULL)
    return 0;
    else
    return (1+count(list->next));            //recursion 
} 


void print(node *list) 
{ 
    if(list==NULL)
    printf("The list is empty.\n\n");
    else
    {
        printf("%d-->",list->num);
        if(list->next==NULL)
        printf("END\n\n\n");
        else
        print(list->next);            //recursion 
    }
} 



node *find(node *list, int key)            //This function returns the node after which 
{     
    if(list->next)
    {                                    //the key is found .                             
        if(list->next->num == key)     /* key found */ 
            return(list);
        else if(list->next->next == NULL)    /* end */ 
            return(NULL);
        else
        find(list->next, key);
    }
    else
    return NULL;
} 



node *insert(node *head) 
{ 
    node *new_node;          /* pointer to new node */ 
    node *n1=head;        /* pointer to node preceding key node */ 
    int key;
    int x;            /* new item (number) to be inserted */ 
    if(!head)
    {
        printf("\nlist is not created yet.\n\n");
        return head;
    }
    printf("What value you want to insert?");
    scanf("%d", &x);
    printf("before which key item ? (type -999 if to be inserted last) ");
    scanf("%d", &key);

    if(key==-999)        /* insert new node at last*/ 
    {
        while(n1->next)
            n1=n1->next;    //navigate to last node 
            
        new_node = (node *)malloc(sizeof(node));
        new_node->num = x;
        new_node->next = n1->next;
        n1->next = new_node;
    }
    else if(head->num == key)        /* new node is first */ 
    {
        new_node = (node *)malloc(sizeof(node));
        new_node->num = x;
        new_node->next = head;
        head = new_node;
    }
    else        /* find key node and insert new node */ 
    {            /* before the key node */ 
        n1 = find(head, key);    /* find key node */

        if(n1 == NULL&&key!=-999)
           printf("\n key is not found !!!\n\n");
            
        else        /* insert new node */ 
        {
          new_node = (node *)malloc(sizeof(node));
          new_node->num = x;
          new_node->next = n1->next;
          n1->next = new_node;
        }
      }
      return head;
} 



node *hatana(node *list) 
{ 
    void delete_node(node *);
    node *n1,*n2;
    int key;
    if(!list)
    {
        printf("\nlist is not created yet.\n\n");
        return list;
    }
    printf("What value do you want to delete ?");
    scanf("%d",&key);
    if(key==list->num)                        //key is the first node 
    {
        n2=list->next;
        free(list);
        list=n2;
        printf("\n%d is deleted successfully .\n\n",key);
    }
    else
    {
         n1=find (list ,key);
         if(n1)
        {
            delete_node(n1);                        //This function deletes n1->next 
            printf("\n%d is deleted successfully .\n\n",key);
        }
         else
         printf("\nItem is not in the list !!! \n\n\n");
    }
return(list); 
} 


void delete_node(node *list)  //This function deletes list->next 
{ 
    node *n2;
    n2=list->next->next;
    free(list->next);
    list->next=n2;
} 



node *rearrange(node *list) 
{ 
    node *p1;
    sort(list);
    for(p1=list;p1->next!=NULL;p1=p1->next)
    {
        if(p1->num==p1->next->num)
        delete_node(p1);
    }
    return(list);
} 


void sort(node *list) 
{ 
    void exchange(int *s1,int *s2);
    node *p,*q;
    for(p=list;(p->next)!=NULL;p=p->next)
        for(q=list;(q->next)!=NULL;q=q->next)
        {
            if(q->num > q->next->num)            //simple bubble sort 
            exchange(&(q->num),&(q->next->num));
        }
} 

void exchange(int *s1,int *s2) 
{ 
    int temp;
    temp =*s1;
    *s1=*s2;
    *s2=temp;
}

------------------------------------------------------------

Remarks:

This program has a small bug try and find out.

Program 77: Queue implementation on linked lists general case

The need:
    This program shows how one can implement concept of queue in linked lists. This is extension of previous program. This program is analogous to program75 of this blog.
The code:
------------------------------------------------------

/*
This is a program showing the queue implimentation on linked list
program writtem by RP Singh
compiled and tested on C-free4.0 standard
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node1
{
    int item;
    struct node1 *next;
};
typedef struct node1 node;        //defining datatype node

struct q1
{
    node *front;
    node *rear;
    int length;
};
typedef struct q1 queue;        //defining queue datatype

void enqueue(node *, queue *);
node *dequeue(queue *);
int queue_length(queue *);
void view_queue(queue *);
node *create_node(void);
void fill_node(node *);


int main()
{
    int i,j;
    node *current_node;
    queue que;                    //local queue
    que.front=NULL;
    que.rear=NULL;
    que.length=0;
    printf("This is a demo program to show working of queues");
    anchor:                    //anchor is a label
    printf("\n\nyou have following options\n");
    printf("1. enqueue an item\n2. dequeue an item\n3. view queue\n");
    printf("4. count items in queue\n5. exit program\n\n");
    scanf("%d",&j);
    switch(j)
    {
        case 1:
            printf("\nEnter a number to be enqueued =>\t");
            current_node=create_node();
            fill_node(current_node);
            enqueue(current_node, &que);
            goto anchor;
        case 2:
            current_node = dequeue(&que);
            if(current_node)
            printf("The item %d dequeued successfully\n",current_node->item);
            goto anchor;
        case 3:
            view_queue(&que);
            goto anchor;
        case 4:
            printf("total items in the queue are %d\n",que.length);
            goto anchor;
        case 5:
            printf("Thank you\n");
            exit(0);
            goto anchor;
        default:
            printf("Invalid choice...!!!\n try choosing again\n\n");
            goto anchor;
    }
  
    return 0;
}

void enqueue(node *p,queue *q)                    //definition of enqueue function
{
    if(q->rear==NULL&&q->front==NULL)
    {
        q->rear=p;
        q->front=p;
    }
    else
    {
        q->rear->next=p;
        q->rear=p;
    }
    q->length++;
    printf("item %d enqueued successfully.\n",p->item);
}

node *dequeue(queue *q)                    //definition of dequeue function
{
    node *temp=NULL;
    if(q->rear==NULL&&q->front==NULL)        //this is the case when queue is empty
    {
        printf("queue is empty hence can not be dequeued\n");
        return temp;
    }
    else if(q->rear==q->front&&q->front!=NULL)    //this is the case when queue has only one node
    {
        temp=q->front;
        q->front=NULL;
        q->rear=NULL;
    }
    else
    {
        temp=q->front;
        q->front=q->front->next;
    }
    q->length--;
    return temp;
}

void view_queue(queue *q)
{
    node *temp_front;
    temp_front=q->front;
    if(q->length==0)
    {
        printf("\nThe queue is empty...!!!\n");
        return;
    }
    printf("The queue is\n");
    while(temp_front!=NULL)
    {
        printf("%d -> ",temp_front->item);
        temp_front=temp_front->next;
    }
    printf("\n");
    return;
}

node *create_node()                    //function to create a blank node
{
    node *temp;
    temp=(node*)malloc(sizeof(node));
    temp->next=NULL;
    return temp;
}

void fill_node(node *p)                    //function to fill a blank node with values taken from user
{
    int i;
    scanf("%d",&i);                    //this is the value taken from user
    p->item=i;
}

------------------------------------------------------

program 76: Queue implementation on linked list

The need:
    This program shows how one can implement concept of queue in linked lists. I have already told that linked lists are needed when we practically don't want a bound on size of data being used in program. So unlike array implementation this program will never show "cannot enqueue" message until your computer is out of memory.
The code:
------------------------------------------------------

/*
This is a program showing the queue implimentation on linked list
program writtem by RP Singh
compiled and tested on C-free4.0 standard
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node1
{
    int item;
    struct node1 *next;
};
typedef struct node1 node;        //defining datatype node
void enqueue(node *);
node* dequeue(void);
node *create_node(void);
void fill_node(node *);
void print_node(node *);

node *front=NULL, *rear=NULL;                //global implementation of queue

int main()
{
    int i,j;
    node *current_node;
    printf("Enter 3 items into queue\n");
    for(i=0;i<3;i++)
    {
        current_node=create_node();
        fill_node(current_node);
        enqueue(current_node);
        printf("item %d inserted into queue successfully\n",current_node->item);
    }
    printf("all items successfully entered into queue\n");
    printf("press any key to dequeue and see all values you entered");
    fflush(stdin);
    getchar();
    while(!(rear==NULL&&front==NULL))
    {
        current_node=dequeue();
        print_node(current_node);
    }
    return 0;
}

void enqueue(node *p)                    //definition of enqueue function
{
    if(rear==NULL&&front==NULL)
    {
        rear=p;
        front=p;
    }
    else
    {
        rear->next=p;
        rear=p;
    }
}

node *dequeue(void)                    //definition of dequeue function
{
    node *temp=NULL;
    if(rear==NULL&&front==NULL)        //this is the case when queue is empty
    {
        printf("queue is empty hence can not be dequeued\n");
    }
    else if(rear==front&&front!=NULL)    //this is the case when queue has only one node
    {
        temp=front;
        front=NULL;
        rear=NULL;
    }
    else
    {
        temp=front;
        front=front->next;
    }
    return temp;
}

node *create_node()                    //function to create a blank node
{
    node *temp;
    temp=(node*)malloc(sizeof(node));
    temp->next=NULL;
    return temp;
}

void fill_node(node *p)                    //function to fill a blank node with values taken from user
{
    int i;
    printf("Enter an integer\n");
    scanf("%d",&i);                    //this is the value taken from user
    p->item=i;
}

void print_node(node *p)                    //printing the node data
{
    printf("%d\n",p->item);            //in our case node has only one item
}

------------------------------------------------------

Program 75: Circular Queues implementation on local Array

The need:
    To show how circular queue can be implemented on integer array with user defined functions (UDFs). This is general implementation of queues. This lets you handle more than one  queue by using same functions for all queues. For this some changes are made UDFs.
The code:
-----------------------------------------------------------

/*
This is a program showing the circular queue implimentation on array.
This program shows how we can implement queue on local variables.
In this first I have defined a structure containinf an array and front and rear
so that I can have front and rear for each local queue.
You can have multiple queues in this program all you need to do is 
declare another variable of type node.
In this convention front indexeses to the first item
and rear indexes the location after last item
this convention lets you fill maximum (SIZE-1) items in a queue
where SIZE is size of the array being used
program writtem by RP Singh
compiled and tested on C-free4.0 standard
*/
#define SIZE 5
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct node1
{
    int array[SIZE];
    int front,rear;
};
typedef struct node1 queue;

void enqueue(int, queue *);
int dequeue(queue *);
int queue_length(queue *);
void view_queue(queue *);

int main()
{
    int i=0,j,current_item;
    char c;
    queue que;            //local implementation of queue
    que.front=0;
    que.rear=0;
    printf("This is a demo program to show working of queues");
    anchor:                    //anchor is a label
    printf("\n\nyou have following options\n");
    printf("1. enqueue an item\n2. dequeue an item\n3. view queue\n");
    printf("4. count items in queue\n5. exit program\n\n");
    scanf("%d",&j);
    switch(j)
    {
        case 1:
            printf("\nEnter a number to be enqueued =>\t");
            scanf("%d",&current_item);
            enqueue(current_item, &que);
            goto anchor;
        case 2:
            current_item = dequeue(&que);
            goto anchor;
        case 3:
            view_queue(&que);
            goto anchor;
        case 4:
            printf("total items in the queue are %d\n",queue_length(&que));
            goto anchor;
        case 5:
            printf("Thank you\n");
            exit(0);
            goto anchor;
        default:
            printf("Invalid choice...!!!\n try choosing again\n\n");
            goto anchor;
    }
   
    return 0;
}

void enqueue(int a, queue *p)                    //definition of enqueue function
{
    if((p->rear+1)%SIZE==p->front)
        printf("cannot enqueue because the queue is already full.\n");
    else
        {
            p->array[p->rear]=a;                    //enqueing an item
            p->rear=(p->rear+1)%SIZE;
            printf("item %d inserted into queue successfully\n\n",a);
        }
}

int dequeue(queue *p)                    //definition of dequeue function
{
    int temp;
    if(p->rear==p->front)        //this is the case when queue is empty
    {
        printf("queue is empty hence can not be dequeued\n");
    }
    else
    {
        temp=p->array[p->front];
        p->front=(p->front+1)%SIZE;
        printf("item %d dequeued successfully\n",temp);
    }
    return temp;
}

int queue_length(queue *p)
{
    int length=0;
    if(p->rear>=p->front)
    length=p->rear-p->front;
    else
    length=(p->rear+SIZE)-p->front;
    return length;
}

void view_queue(queue *p)
{
    int temp_front;
    temp_front=p->front;
    if(queue_length(p)==0)
    {
        printf("\nThe queue is empty...!!!\n");
        return;
    }
    printf("The queue is\n");
    while(temp_front!=p->rear)
    {
        printf("%d -> ",p->array[temp_front]);
        temp_front=(temp_front+1)%SIZE;
    }
    printf("\n");
    return;
}

-----------------------------------------------------------

Remarks:

This is a program showing implementation of circular queue on array. For simplicity I have taken a simple integer array. This program may look different from previous ones but this is also simply follows the concept of queue.

Program 72: Queue implementation on array

The need:
    To show how queue concept can be implemented on an array in the simplest way possible.
The code:
-----------------------------------------------------------

/*
This is a program showing the queue implimentation on integer array
We can have array implementation on array of any datatype including derived datatypes
This program does not include any user defined function
In this front and rear are taken as array indices
program writtem by RP Singh
compiled and tested on C-free4.0 standard
*/

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

int main()
{
    int i=0,arr[MAX];
    char c='y';
    int front=0,rear=-1,current_item;        //I follow the convention of takingthese values of front and rear when queue is empty
    printf("Enter 3 items into queue\n");
    while(c=='y'||c=='Y')
    {
        printf("\nEnter integer %d\t=>\t",++i);
        scanf("%d",&current_item);                    //this is the value taken from user
        if(rear==MAX-1)
        printf("cannot enqueue because the array end has been reached.\n");
        else
        arr[++rear]=current_item;                    //enqueing an item
        printf("item %d inserted into queue successfully\n\n",current_item);
        printf("Enter press y to enqueue more items. else press any other key.\n");
        fflush(stdin);
        c=getchar();
    }
    printf("all items successfully entered into queue\n");
    printf("value of front = %d\t rear = %d\n",front,rear);
    printf("length of queue is %d\n",rear-front+1);
    printf("\n\npress any key to dequeue and see all values you entered\n");
    fflush(stdin);
    getchar();
    printf("all items you entered are listed below\n");
    while(front<=rear)
    {
        printf("%d\n",arr[front++]);                    //dequeing an item
    }
    return 0;
}

-----------------------------------------------------------

Remarks:

This is a simple program showing implementation of queue concept on array. For simplicity I have taken a simple integer array. I also have not used any UDFs here. I just wanted to show that queue is an abstract entity, we dont even need enqueue and dequeue to implement that on simplest level. The only thing to remember is the concept of queue.

Program 71: Conversion to any base

The need:
    The program was given to me in my online quiz. Actually this is not the same program I made at that time. This is a modified one and I made it after 6 months of the quiz. This can also handle conversion of relatively large numbers.
The code:
----------------------------------------------------

/*base conversion from 10 to any base up to Z*/

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<conio.h>
double divide(double a,double b);
main()
   {char h;
do
{
 double k,m;
 int i=0,j,l;
 float str[100];
 char temp[100];
 printf("This is a program to convert decimal integers to any base less than 62\n");
 printf("'A' means 10 and so on. 'a' means 36 and so on\n");
 printf("\nEnter a decimal integer => ");
 scanf("%lf",&k);
 printf("Enter the base in which to be converted =>");
 scanf("%lf",&m);
 if(m==0)
 {
 printf("Please enter a natural number less than 36. program exiting..\n");
 exit(0);
 }
 while(k>0)
    {
 str[i]=fmod(k,m);
 k=divide(k,m);
 i++;
    } 
 l=i;
 j=l;
 for(i=0;j>=0;i++,j--)
  {
  if(str[i]<10)
  temp[j]= (int)str[i]+'0';
  else if(str[i]<36)
  temp[j]= (int)str[i]+'A'-10;
  else if(str[i]<62)
  temp[j]= (int)str[i]+'a'-36;
  if(m>61)
  {
  printf("base should be less than 62.\n");
  exit(1);
  }
  }
  printf("The conversion to base %.0f is => ",m);
 for(j=1;j<=l;j++)
printf("%c",temp[j]);
printf("\n\nWant to try more ? y/n");
fflush(stdin);
h=getchar();
}while(h=='y'||h=='Y');
printf("hit any key to continue...\n");
getche();
}
double divide(double a,double b)
{
 double d=0,e;
 for(e=1000000000000;e>=1;e/=10)
    {
    while(a>=e*b)
    {
  a-=e*b;
  d+=e;
 }
 } 
 return (d);
}

----------------------------------------------------


Remark:
  1. This program has a bug which is : "It works accurate upto 15digit numbers but it loses accuracy if the input number becomes larger than that." Try to find out.