Saturday, 31 December 2011

INSERTION SORT




Source code of simple insertion sort implementation using array in ascending order in c programming language

#include<stdio.h>
int main(){

  int i,j,s,temp,a[20];

  printf("Enter total elements: ");
  scanf("%d",&s);

  printf("Enter %d elements: ",s);
  for(i=0;i<s;i++)
      scanf("%d",&a[i]);

  for(i=1;i<s;i++){
      temp=a[i];
      j=i-1;
      while((temp<a[j])&&(j>=0)){
      a[j+1]=a[j];
          j=j-1;
      }
      a[j+1]=temp;
  }

  printf("After sorting: ");
  for(i=0;i<s;i++)
      printf(" %d",a[i]);

  return 0;
}

Output:
Enter total elements: 5
Enter 5 elements: 3 7 9 0 2
After sorting:  0 2 3 7 9

Friday, 30 December 2011

basics


  1. What will print out?
    main()

            char
     *p1=“name”
            char
     *p2;
            p2=(char*)malloc(20);
            memset (p2, 0, 20);
            while(*p2++ = *p1++); 
            printf
    (“%sn”,p2);
    }
    Answer:empty string.
  2. What will be printed as the result of the operation below:
    main()

        int
     x=20,y=35;
        x=y++ + x++;
        y= ++y + ++x; 
        printf
    (“%d%dn”,x,y);
    }
    Answer : 5794
  3. What will be printed as the result of the operation below:
    main()
    {
        int x=5;
        printf(“%d,%d,%dn”,x,x< <2,x>>2);
    }
    Answer: 5,20,1
  4. What will be printed as the result of the operation below:
    #define swap(a,b) a=a+b;b=a-b;a=a-b;
    void main()
    {
        int x=5, y=10;
        swap (x,y);
        printf(“%d %dn”,x,y);
        swap2(x,y);
        printf(“%d %dn”,x,y);
    }
    int swap2(int a, int b)
    {
        int temp;
        temp=a;
        b=a;
        a=temp;
        return 0;
    }
    Answer: 10, 5
    10, 5
  5. What will be printed as the result of the operation below:
    main()
    {
        char *ptr = ” Cisco Systems”;
        *ptr++; printf(“%sn”,ptr);
        ptr++;
        printf(“%sn”,ptr);
    }
    Answer:Cisco Systems
    isco systems
  6. What will be printed as the result of the operation below:
    main()
    {
        char s1[]=“Cisco”;
        char s2[]= “systems”;
        printf(“%s”,s1);
    }
    Answer: Cisco
  7. What will be printed as the result of the operation below:
    main()
    {
        char *p1;
        char *p2;
        p1=(char *)malloc(25);
        p2=(char *)malloc(25);
        strcpy(p1,”Cisco”);
        strcpy(p2,“systems”);
        strcat(p1,p2);
        printf(“%s”,p1);
    }
    Answer: Ciscosystems
  8. The following variable is available in file1.c, who can access it?:
    static int average;
    
    Answer: all the functions in the file1.c can access the variable.
  9. WHat will be the result of the following code?
    #define TRUE 0 // some code
    while(TRUE)
    {
        // some code
    }
    Answer: This will not go into the loop as TRUE is defined as 0.
  10. What will be printed as the result of the operation below:
    int x;
    int modifyvalue()
    {
        return(x+=10);
    }
    int changevalue(int x)
    {
        return(x+=1);
    }
    void main()
    {
        int x=10;
        x++;
        changevalue(x);
        x++;
        modifyvalue();
        printf("First output:%dn",x);
        x++;
        changevalue(x);
        printf("Second output:%dn",x);
        modifyvalue();
        printf("Third output:%dn",x);
    }
    Answer: 12 , 13 , 13
  11. What will be printed as the result of the operation below:
    main()
    {
        int x=10, y=15;
        x = x++;
        y = ++y;
        printf(“%d %dn”,x,y);
    }
    Answer: 11, 16
  12. What will be printed as the result of the operation below:
    main()
    {
        int a=0;
        if(a==0)
            printf(“Cisco Systemsn”);
            printf(“Cisco Systemsn”);
    }
    Answer: Two lines with “Cisco Systems” will be printed.

Thursday, 29 December 2011

basic binary tree routines


Basic binary search tree routines

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

struct tnode {
 int data;
 struct tnode *left;
 struct tnode *right;
};

/* insert, swap, search value, search minimum and search maximum values */
struct tnode *tnode_insert(struct tnode *p, int value);
struct tnode *tnode_swap(struct tnode *p);
struct tnode *tnode_search(struct tnode *p, int key);
struct tnode *tnode_searchmin(struct tnode *p);
struct tnode *tnode_searchmax(struct tnode *p);

/* destroy, count tree nodes */
void tnode_destroy(struct tnode *p);
int tnode_count(struct tnode *p);

/* print binary tree inorder, preorder, postorder [recursive] */
void print_inorder(struct tnode *p);
void print_preorder(struct tnode *p);
void print_postorder(struct tnode *p);

int main(void) {
 int demo_nr[] = {1, 3, 4, 7, 2, 9, 9, 0, 5, 6, 8, 7, 1, 2, 4};
 struct tnode *root = NULL;
 struct tnode *searchval = NULL;
 int querry = 0;
 int i = 0;

 /* demo: insert some nr's into the binary tree */
 for(i = 0; i < 15; i++)
  root = tnode_insert(root, demo_nr[i]);

 printf("=-=-=\n");
 printf("Total number of tree nodes: %d\n", tnode_count(root));
 printf("inorder  : ");
 print_inorder(root);
 printf("\n");

 printf("preorder : ");
 print_preorder(root);
 printf("\n");

 printf("postorder: ");
 print_postorder(root);
 printf("\n");

 printf("=-=-=\n");
 printf("Enter integer, find: ");
 scanf("%d", &querry);
 searchval = tnode_search(root, querry);
 if(searchval == NULL)
  printf(" * %d Not! found in btree\n", querry);
 else
  printf(" * Found! %d in btree\n", searchval->data);

 searchval = NULL;
 printf("Searching for Minimum value\n");
 searchval = tnode_searchmin(root);
 if(searchval == NULL)
  printf(" * Minimum Not! found in btree ?\n");
 else
  printf(" * Found! minimum value %d in btree\n", searchval->data);

 searchval = NULL;
 printf("Searching for Maximum value\n");
 searchval = tnode_searchmax(root);
 if(searchval == NULL)
  printf(" * Maximum Not! found in btree ?\n");
 else
  printf(" * Found! Maximum value %d in btree\n", searchval->data);

 printf("=-=-=\n");
 printf("Exchanging all tree nodes: left <-> right\n");
 root = tnode_swap(root);

 printf("inorder  : ");
 print_inorder(root);
 printf("\n");

 printf("preorder : ");
 print_preorder(root);
 printf("\n");

 printf("postorder: ");
 print_postorder(root);
 printf("\n");

 printf("=-=-=\n");
 printf("Destroying btree... bye!\n");
 tnode_destroy(root);

 return 0;
}

/* insert a tnode into the binary tree */
struct tnode *tnode_insert(struct tnode *p, int value) {
 struct tnode *tmp_one = NULL;
 struct tnode *tmp_two = NULL;

 if(p == NULL) {
  /* insert [new] tnode as root node */
  p = (struct tnode *)malloc(sizeof(struct tnode));
  p->data = value;
  p->left = p->right = NULL;
 } else {
  tmp_one = p;
  /* Traverse the tree to get a pointer to the specific tnode */
  /* The child of this tnode will be the [new] tnode */
  while(tmp_one != NULL) {
   tmp_two = tmp_one;
   if(tmp_one ->data > value)
    tmp_one = tmp_one->left;
   else
    tmp_one = tmp_one->right;
  }

  if(tmp_two->data > value) {
   /* insert [new] tnode as left child */
   tmp_two->left = (struct tnode *)malloc(sizeof(struct tnode));
   tmp_two = tmp_two->left;
   tmp_two->data = value;
   tmp_two->left = tmp_two->right = NULL;
  } else {
   /* insert [new] tnode as left child */
   tmp_two->right = (struct tnode *)malloc(sizeof(struct tnode));
   tmp_two = tmp_two->right;
   tmp_two->data = value;
   tmp_two->left = tmp_two->right = NULL;
  }
 }

 return(p);
}

/* print binary tree inorder */
void print_inorder(struct tnode *p) {
 if(p != NULL) {
  print_inorder(p->left);
  printf("%d ", p->data);
  print_inorder(p->right);
 }
}

/* print binary tree preorder */
void print_preorder(struct tnode *p) {
 if(p != NULL) {
  printf("%d ", p->data);
  print_preorder(p->left);
  print_preorder(p->right);
 }
}

/* print binary tree postorder */
void print_postorder(struct tnode *p) {
 if(p != NULL) {
  print_postorder(p->left);
  print_postorder(p->right);
  printf("%d ", p->data);
 }
}

/* returns the total number of tree nodes */
int tnode_count(struct tnode *p) {
 if(p == NULL)
  return 0;
 else {
  if(p->left == NULL && p->right == NULL)
   return 1;
  else
   return(1 + (tnode_count(p->left) + tnode_count(p->right)));
 }
}

/* exchange all left and right tnodes */
struct tnode *tnode_swap(struct tnode *p) {
 struct tnode *tmp_one = NULL;
 struct tnode *tmp_two = NULL;

 if(p != NULL) {
  tmp_one = tnode_swap(p->left);
  tmp_two = tnode_swap(p->right);
  p->right = tmp_one;
  p->left  = tmp_two;
 }

 return(p);
}

/* locate a value in the btree */
struct tnode *tnode_search(struct tnode *p, int key) {
 struct tnode *temp;
 temp = p;

 while(temp != NULL) {
  if(temp->data == key)
   return temp;
  else if(temp->data > key)
   temp = temp->left;
  else
   temp = temp->right;
 }

 return NULL;
}

/* locate a minimum value in the btree */
struct tnode *tnode_searchmin(struct tnode *p) {
 if(p == NULL)
  return NULL;
 else
  if(p->left == NULL)
   return p;
  else
   return tnode_searchmin(p->left);
}

/* locate a maximum value in the btree */
struct tnode *tnode_searchmax(struct tnode *p) {
 if(p != NULL)
  while(p->right != NULL)
   p = p->right;

 return p;
}

/* destroy the binary tree */
void tnode_destroy(struct tnode *p) {
 if(p != NULL) {
  tnode_destroy(p->left);
  tnode_destroy(p->right);

  free(p);
 }
}

create a copy of a linked list

How to create a copy of a linked list? Write a C program to create a copy of a linked list. 



copy_linked_lists(struct node *q, struct node **s)
 {
       if(q!=NULL)
       {
                           *s=malloc(sizeof(struct node));
                             (*s)->data=q->data;
                             (*s)->link=NULL;
                           copy_linked_list(q->link, &((*s)->link));
        }
 }


How would you check if a binary tree is balanced?


How would you check if a binary tree is balanced?
Solution:


A tree is considered balanced when the difference between the min depth and max depth does not exceed 1.
Recursive algorithms always work well on trees, so here’s some code.


int min_depth( Node * root )
{
    if( !root )
    {
        return 0;
    }
    return 1 + min( min_depth( root->left ),min_depth( root->right ));
}
int max_depth( Node * root )
{
    if( !root )
    {
        return 0;
    }
    return 1 + max( max_depth( root->left ),max_depth( root->right ));
} 

bool is_balanced( Node * root )
{
    return ( max_depth( root ) - min_depth( root ) ) <= 1
}