C Program To Perform Reversal Of A String IN PLACE

Approach:

The trick behind this is very simple maintain two pointers one end pointer and one start pointer and swap their contents iteratively till they meet each other.

Let’s try to code it:

Program:

#include<stdio.h> /*for printf and scanf*/

void InplaceRev(char* str)

{

    char* temp=str; // end pointer

    char var;

    if(str==NULL)

       return str ;

    while(*temp)

        temp++; /*temp is pointing to '\0' i.e. end of string*/

    temp--; /*temp decremented to point to the last character of the string*/

    while(str<temp) // run a loop till the start and end pointer meet

    {

        var=*str;

        *str++=*temp;

        *temp--=var;

    }

}

int main()

{

    char str[]="THIS IS IT..";

    char* temp=str;

    printf("Original String is:\n%s\n\n",str);

    printf("String after reversal is : \n");

    InplaceRev(temp);

    printf("%s",temp);

    return 0;

}

Viva La Raza

Sid

C Program to find Middle element in a linked list

Approach #1:

The Naïve way to do this, is to loop through the linked list and increment a count variable with every iteration till null is encountered. Then finally traverse again from the start to count/2.

Isn’t this the obvious approach…..

Let’s go to the not so obvious one…

 Approach#2:

Maintain two pointers from the start of the linked list. A fast and a slow pointer. Increment slow pointer by one and the fast pointer by two. When the fast one reaches the end , the slow one wil reach the middle node of the linked list.

Let’s try to code it:

Program:

#include<stdio.h> /*for printf & scanf*/

#include<stdlib.h> /*for malloc*/

struct node

{

    int data;

    struct node* next;

};

void insert(struct node** head_ref,int data)

{

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

    temp->data=data;

    temp->next=(*head_ref);

    (*head_ref)=temp;

}

void findMid(struct node* head)

{

    struct node* slow_ptr=head;

    struct node* fast_ptr=head;

    if (head!=NULL)

    {

        while(slow_ptr&&fast_ptr&&fast_ptr->next)

    {

        slow_ptr=slow_ptr->next;

        fast_ptr=fast_ptr->next->next;

    }

    }

    printf("\n\nThe Middle point of the given linked list is %d\n",slow_ptr->data);

}

void printList(struct node* head)

{

    struct node*temp=head;

    while(temp)

    {

       printf("%d -> ",temp->data);

       temp=temp->next;

    }

    printf("NULL");

}

int main()

{

    struct node* head=NULL;

    int i;

    for(i=1;i<=5;i++)

        insert(&head,i);

    printf("\nLinked List : \n\n");

    printList(head);

    findMid(head);

    return 0;

}

Viva La Raza

Sid

C Program to check whether two trees are identical or not

Two trees are identical if they have the same data arrangement w.r.t each other.

Algorithm:

identicalTrees(Tree1,Tree2)

1. Check if both trees are empty if so then return 1;

2. Recursively check for the following tree:

         a.       Return 1 if both have same data

         b.      Check left tree recursively : identicalTrees(tree1->left,tree2->left)

         c.       Check right tree recursively : identicalTrees(tree1->right,tree2->right)

         d.      Return 1 if a,b,c are true else return 0;

      3. Return 0 if one tree is empty and other is not.

    

   Program:

   

   /*Program to check whether two trees are identical or not*/

   #include<stdio.h> /*for printf & scanf*/

   #include<stdlib.h>/*fro malloc & calloc */

   /*structure to define tree node*/

   struct node

  {

    int data;

    struct node* left;

    struct node* right;

   };

   /*function to insert a new node in tree*/

   struct node* insert(int new_data)

  {

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

    temp->data=new_data;

    temp->left=NULL;

    temp->right=NULL;

    return (temp);

  };

   /*function return true or 1 if both trees are idential*/

   int identicalTrees(struct node* tree1,struct node* tree2)

   

{
    else if(tree1!=NULL && tree2!=NULL)
}
}
    tree1=insert(1);
    tree2=insert(1);
        if(identicalTrees(tree1,tree2))
    return 0;

    if(tree1==NULL && tree2==NULL)

       return 1;

        return(

               (tree1->data==tree2->data)&&

               (identicalTrees(tree1->left,tree2->left))&&

               (identicalTrees(tree1->right,tree2->right))

               );

    else

        return 0;

   int main()

  {

    struct node*tree1=NULL;

    struct node*tree2=NULL;

    tree1->left=insert(2);

    tree1->right=insert(3);

    tree1->left->left=insert(4);

    tree1->left->right=insert(5);

    tree2->left=insert(2);

    tree2->right=insert(3);

    tree2->left->left=insert(4);

    tree2->left->right=insert(5);

            printf("Both tree are identical");

        else

            printf("Both tree are not identical");

   

   }

Viva La Raza

Sid