## Friday, June 29, 2012

### Singleton implementation in c++ !!

Below is the implementation of Singleton in C++.
```#include<iostream>
using namespace std;

class single
{
private:
static single *ptr;
single()
{
}
public:
static single* getInstance();
};

single* single::getInstance()
{
if(ptr==NULL)
{
ptr = new single();
cout<<"creating the instance and address is "<<ptr<<endl;
}
else
{
return ptr;
}
}
single* single::ptr=NULL; //initialising the static variable

int main()
{
single *s,*ss,*sss;
s=single::getInstance();
ss=single::getInstance();
sss=single::getInstance();
}

```

## Wednesday, June 27, 2012

### Construct binary tree from inorder and preorder

Here we will learn how to construct a binary tree from a given traversals Inorder and Preorder/Postorder. Traversal means visiting each node in the tree in some specified order like preorder, postorder or inorder. We will get the traversal from the given binary tree. And we can also construct binary tree from the given traversals. We see how to construct the tree from traversals.

Construct Binary Tree from Traversals: To construct binary tree we need
• Inorder traversal data and
• Postorder or Preorder traversal data
Lets construct bianry tree withe example:

Inorder:    DBEAFCG
PreOrder: ABDECFG

As mentioned above, to construct a tree we need at least two traversals in that one must be Inorder and another must be either Preorder or Postorder. Inorder is for finding left and right child nodes and pre or post order is for finding the root node.
If the preorder is given, first element in the preoder is root node. And if the postorder is given last element is the root node. After finding the root node, go to Inorder and find the root node in the inorder and left elements of the root node are left childs and right elements of the root node are right childs. Repeat this process for all elements.

Step1:  From Preorder first eleement is the root node.So here it is 'A'. If you see 'A' in in order and left of the A are left childs here DBE and right childs of A are FCG.

 Step1 tree
PreOrder:    ABDECFG
Inorder:       DBE A FCG

Step 2: we will repeat the step1 for two sub elements BDE and CFG. from preorder first element is root node, here B and C are root nodes and from the Inorder D is the left child and E is the right child for B. Similarly F is the left child and G is the right child for C.

PreOrder: A BDE CFG

 Step2 Tree
﻿Inorder:    DBE A FCG

Lets take another example with Inorder and Postorder.

Postorder: DHIEBJFGCA
Inorder:     DBHEIAFJCG

﻿﻿
 Step1 Binary tree
﻿﻿Step1: From postorder last element is the root node, So here A is the root node and from from inorder we will find the left and right sub elements.

Postorder: DHIEB JFGC A
Inorder:     DBHEI A FJCG
﻿
 Step2 Binary Tree
﻿Step2: we will repeat the step1 for left and right sub elements. From Inorder  left elements are 5 and right elements are 4. we will split the Postorder like that and take the root nodes as B and C.

Postorder: DHIEB JFGC A
Inorder: D B HEI A FJ C G

 Final Binary tree
Step3: For root node B left element is one(D) and right elements are three(HIE) and for C left element are two(JF) and right element is one(G).

Postorder: D HIE B JF G C A
Inorder: D B HEI A FJ C G

## Tuesday, June 26, 2012

### Binary Search Tree !!!

In computer science Binary search tree or BST is one of most common data structure used. A Binary search tree is a binary tree which follow the below properties
• left sub tree of the node should contain less than or equal to node
• right sub tree of the node should contain the greater than to the node
• both left and right subtrees should also be a binary search tree
Binary search tree for the input values 8,13,3,11,1,6,14,12,4,7 is given below.
 Binary Search Tree

One of the most advantage of Binary search tree is , sorting and searching operations are very efficient. Worst case complexity of searching using BST method is O(log(n)) where n is no. of nodes. And worst case for sorting using BST is O(n), Where as traditional sorting algorithms like bubble sort or quick sort the worst case is O(n*n). In the average case for the sorting in BST, the complexity reduces to (log(n)).

Operations on Binary Search Tree:
• Searching
• inserting
• deleting
• sort
• traversal

Applications of the binary search tree:
• Dictionaries
• sets
• multi sets
• associate array

## Friday, June 22, 2012

Linked list is a sequence of lists or nodes in such a way that one node is pointing to the another node and another node pointing to the another node like a train. Node or list contains a data field which stores data or info and another field is for address, which stores the address of the next node and last node address field in the points to the NULL. There are different forms of the linked lists namely
• circular linked list: Similar to single linked list, but the difference is last node address field pointr to head node and not NULL.
• trees: Similar to double linke list.

Structure of a linked list: The basic structure of a linked list contains data Field and address field. It is also called singly linked list. Because it stores the address of the another list or node.

```struct node
{
int info;
struct node *next;
};

// creating the head node statically.
//accessing the data

// creating the head node dynamically.
//accessing the data

```
﻿﻿﻿﻿
﻿
﻿
 Image 1
﻿ ﻿

Structure of a linked list in a pictorial view you can see in the right side image 1. It is one node or list  which contains data field as info and address field as ptr.

﻿
 Image 2
﻿ ﻿Example for the linked list: we can see in the image 2. The linked list with three nodes and last node ptr is NULL. Head node contains the address of the second pointer. And data field of the head node is 10. In the linked list we will be having only head node. using that head node only we need to do the operations.

﻿﻿﻿﻿﻿ ﻿﻿﻿ ﻿
﻿
 Image3
﻿﻿
﻿Doubly linked list:﻿﻿  Structure of the double linked list is given below. Which contains one data feild and two address fields namely previous and next or left and right.

```struct node
{
int info;
struct node *left;
struct node *right;

};

// creating the head node statically.
//accessing the data

// creating the head node dynamically.
//accessing the data

```

﻿
 Image1
﻿
﻿﻿
 Image2
﻿﻿

• System programming
• Memory organization
• File management implementations.
• Tree implementations
Here is the complete working linked list C programming language Code.

## Thursday, June 21, 2012

### linked list program in C.

This is single linked list implementation in C. It contains all the possible operations in single linked list.
```#include<stdio.h>
#include<stdlib.h>

struct node
{
int info;
struct node *next;
};

//making typdef so we can use Node instead of 'struct node'
typedef struct node Node;

//inserting or creating the list or adding the element @ end
Node* insert(Node *h, int info)
{
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->info = info;
newNode->next = NULL;
if(tempHead == NULL) // if the list has zero elements. make new node as a head
{
h=newNode;
}
else if(tempHead->next==NULL)  // if the list is having only one node
{
}
else
{
Node *tempNode = h;
while(tempNode->next != NULL)  // if the list has more than one node, so moving to the last node
{
tempNode = tempNode->next;
}
tempNode->next = newNode; // appending the new node at the end
}
return h;
}

//deleting a node from list. It has three cases
//1. empty list
//2. deleting first node in the list (this is similar to deleting current node in the list)
//3. other than first node
{
Node *temp=NULL;
if(h==NULL)
{
return ;
}
{
else
{
free(temp);
}
printf("----------------- given %d element is deleted from the list----------------- \n",info);
return ;
}
while(h->next!=NULL)
{
if((h->next->info == info))
{
temp = h->next;
h->next=h->next->next;
free(temp);
printf("----------------- given %d element is deleted from the list----------------- \n",info);
return;
}
h=h->next;
}
printf("-------------- %d is not in the list ------------\n",info);
return ;
}

//deleting current node
void deleteCurrent(Node *current)
{
current->info = current->next->info;
current->next = current->next->next;
}

/*****************************************************************************
for displaying the nodes in the list
*****************************************************************************/
void display(Node *h)
{
Node *temp = h;
while (temp->next!=NULL)
{
printf("%d->",temp->info);
temp = temp->next;
}
printf("%d\n",temp->info);
}

{
{
}
{
}
}

// looking for a element in the list
{
while(tmp)
{
if(tmp->info == element)
{
printf("%d found in the list\n",element);
break;
}
tmp=tmp->next;
}
}

//finding the size of the linked list
{
int size=0;
while(tmp)
{
size++;
tmp=tmp->next;
}
return size;
}

{
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->info = element;
newNode->next = NULL;
if(!location)
{
}
while(tmp!=NULL)
{
if(!location)
{
newNode->next = tmp->next;
tmp->next = newNode;
}
tmp = tmp->next;
location--;
}
}

int main()
{
int i,n,element,choice,pos,size;
printf("Enter no. of elements in the list\n");
scanf("%d",&n);
printf("Enter the elements in the list\n");
for (i=0;i<n;i++)
{
scanf("%d",&element);
}
printf("Below are the operation we can perform on the linked list\n");
printf("1. Adding Element\n2. Deleting Element\n3. Display list\n4. Reverse list\n5. Finding element\n6. Finding nth element from last\n");
scanf("%d",&choice);
while(choice!=8)
{
switch(choice)
{
case 1:
printf("Enter the element to add to the list\n");
scanf("%d",&element);
printf("Enter the position where to ad the element \n");
scanf("%d",&pos);
break;
case 2:
printf("Enter the element to delete from the list\n");
scanf("%d",&element);
break;
case 3:
printf("----------------- list of elements in the linked list are----------------- \n");
printf("----------------- ----------------- ----------------- ----------------- \n");
break;
case 4:
printf("----------------- given linked list is reversed ----------------- \n");
break;
case 5:
printf("Enter the element to be searched in the list\n");
scanf("%d",&element);
break;
case 6:
printf("Enter the position from last\n");
scanf("%d",&pos);
if(tmp)
printf("%dth element from last is %d\n",pos,tmp->info);
else
printf("enter the pos less the list size\n");
break;
case 7:
if(size)
printf("----------------- linked list size is %d----------------- \n",size);
else
printf("----------------- list is empty----------------- \n");
break;
case 8:
return 0;
break;
default:
printf("Enter the choice between 1-9 only\n");
break;
}
printf("1. Adding Element\n2. Deleting Element\n3. Display list\n4. Reverse list\n5. Finding element\n6. Finding nth element from last\n");
scanf("%d",&choice);
}
}

```

## Tuesday, June 19, 2012

### string reverse in c

String reverse function is the one of the most common question you may face in C interviews. I will explain here, the concept and how to write the function to reverse the string and C code for that. In C we can do this in three ways like using arrays, pointers and recursion.

Using pointers and arrays: the concept is same for the both methods. But implementation is different. We can do the string reverse by maintaining two indices one from the begin and another one is from end. Swap the begin element and end  element, then increment begin index and decrement end index and again swap both the elements. And proceed this until begin  reaches half of the string. Because after that its already swapped.

Algorithm for string reverse function:
1. Get the string which is to be reversed
2. find the length of the string.
3. make two indices or pointers, one is pointing to beginning of the string and another one is pointing to end of the string (make end of the string one less than string length, because index starts from zero).
4. swap begin and end elements
5. increment begin and decrement end.
6. repeat from step 4 until begin reaches length/2.
C code for String reverse function using Arrays:
```void str_rev_arry(char *str)
{
int len = strlen(str);
int i=0,j=len-1;
for(i=0;i&lt;len/2;i++,j--)
{
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
}
```
C code for String reverse function using pointers:
```void str_rev_ptr(char *str)
{
int len = strlen(str);
int i;
char *begin, *end;
begin = str;
end = str+len-1;
for(i=0;i&lt;len/2;i++)
{
char temp = *begin;
*begin = *end;;
*end = temp;
begin++;
end--;
}
}
```

String reverse function using recursion: The recursion is calling same function itself repeatedly until it reaches some termination condition. so the concept is swapping the begin and end  elements repeatedly until begin reaches or greater than or equal to end. For every time we need to pass begin and end indices to the function along with string by increasing begin and decreasing end.

C code for String reverse function using recursion:
```void str_rev_rec(char *str, int begin, int end)
{
char temp;
if(begin>=end)
return;
temp = *(str+begin);
*(str+begin) = *(str+end);
*(str+end) = temp;
str_rev_rec(str, ++begin, --end);
}
```

String reverse program in C: Click Here for a complete working example with all three methods for string reverse function in C Programming language.

### C program to reverse a string !!

Below is the complete working example for string reverse fuction in C programming language.
```#include<stdio.h>
#include<string.h>

//strrev function using arrays
void str_rev_arry(char *str)
{
int len = strlen(str);
int i=0,j=len-1;
for(i=0;i<len/2;i++,j--)
{
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
}

//strrev function using pointers
void str_rev_ptr(char *str)
{
int len = strlen(str);
int i;
char *begin, *end;
begin = str;
end = str+len-1;
for(i=0;i<len/2;i++)
{
char temp = *begin;
*begin = *end;;
*end = temp;
begin++;
end--;
}
}

//strrev function using recursion
void str_rev_rec(char *str, int begin, int end)
{
char temp;
if(begin>=end)
return;
temp = *(str+begin);
*(str+begin) = *(str+end);
*(str+end) = temp;
str_rev_rec(str, ++begin, --end);
}
main()
{
char str[]="Hello string";
int len,begin,end,choice;
printf("Enter the String which is to be reversed\n");
printf("1. Using Arrays\n2. Using Pointers\n3. Using Recursion\n4. Exit\n");
printf("Enter the method choice\n");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("before reverse the string is '%s'\n",str);
str_rev_arry(str);
printf("after reverse the string is '%s'\n",str);
break;
case 2:
printf("before reverse the string is '%s'\n",str);
str_rev_ptr(str);
printf("after reverse the string is '%s'\n",str);
break;
case 3:
len = strlen(str);
begin = 0;
end = len-1;
printf("before reverse the string is '%s'\n",str);
str_rev_rec(str,begin,end);
printf("after reverse the string is '%s'\n",str);
break;
default:
printf("wrong choice\n");
break;
}
}

```

## Monday, June 18, 2012

### binary search tree C program !!

Below is the complete working C code with all operations in Binary Search Tree.
```#include<stdio.h>
#include<malloc.h>

struct bst
{
int info;
struct bst *left;
struct bst *right;
};

void delete(struct bst *root, int key);
struct bst *find_min(struct bst *node);
struct bst *find_max(struct bst *node);
struct bst *insert(struct bst *node, int key);
void print_postorder(struct bst *root);
void print_preorder(struct bst *root);
void print_inorder(struct bst *root);
int height(struct bst *root);

//deleting the element which handles three cases
//1. deleting node has no leaf nodes
//2. deleting node has one child(left or right)
//3. deleting node has two childs
void delete(struct bst *root, int key)
{
struct bst *current;
struct bst *prev;
int found = 0;
if(root == NULL)
{
printf("The BST is empty\n");
return;
}
current = root;
while(current!=NULL)
{
if(current->info == key)
{
found = 1;
break;
}
else
{
prev = current;
if(current->info >= key)
current = current->left;
else
current = current->right;
}
}
if(!found)
{
printf("given key element is not in the BST\n");
return;
}

//leaf node , no left n right childs
if((current->left == NULL) && (current->right == NULL))
{
if(prev->left == current)
prev->left = NULL;
else
prev->right = NULL;
free(current);
}

//single child node (either left or right child)
if(current->left == NULL && current->right != NULL)
{
if(prev->left == current)
prev->left = current->right;
else
prev->right = current->right;
free (current);
}

if(current->right == NULL && current->left!=NULL)
{
if(prev->left = current)
prev->left = current->left;
else
prev->right = current->left;
free(current);
}

// need to handle the very complex case(node with both left n right childs)
if(current->left != NULL && current->right != NULL)
{
struct bst *tmp = current->right;
if(tmp->left == NULL && tmp->right == NULL)
{
current->info = tmp->info;
free(tmp);
current->right = NULL;
}
else if(current->right->left != NULL)
{
struct bst *left_current = current->right;
struct bst *left_current_prev = current->right->left;
while(left_current->left != NULL)
{
left_current_prev = left_current;
left_current = left_current->left;
}
current->info = left_current->info;
free(left_current);
left_current_prev->left = NULL;
}
else
{
struct bst *temp;
temp = current->right;
current->info = temp->info;
current->right = temp->right;
free(temp);
}
}
}

//finding the min value
struct bst *find_min(struct bst *node)
{
if(node == NULL)
return NULL;
if(node->left == NULL)
return node;
else
return find_min(node->left);
}

//finding the max value
struct bst *find_max(struct bst *node)
{
if(node!=NULL)
{
while(node->right!=NULL)
node = node->right;
}
return node;
}

//adding the new element to the BST
struct bst *insert(struct bst *node, int key)
{
if(node == NULL)
{
//creating the new node with the key and left n right sub nodes empty
node = (struct bst *)malloc(sizeof(struct bst));
node->info = key;
node->left = node->right = NULL;
}
else if(node->info >= key)
node->left = insert(node->left, key);
else
node->right= insert(node->right, key);
return node;
}

//printing post order (LRP)
void print_postorder(struct bst *root)
{
struct bst *temp = root;
if(temp!=NULL)
{
print_postorder(temp->left);
print_postorder(temp->right);
printf("%d ",temp->info);
}
}

//printing preorder(PLR)
void print_preorder(struct bst *root)
{
struct bst *temp = root;
if(temp!=NULL)
{
printf("%d ",temp->info);
print_preorder(temp->left);
print_preorder(temp->right);
}
}

//printing inorder (LPR)
void print_inorder(struct bst *root)
{
struct bst *temp = root;
if(temp!=NULL)
{
print_inorder(temp->left);
printf("%d ",temp->info);
print_inorder(temp->right);
}
}
// to find the height of the tree
int height(struct bst *root)
{
struct bst *temp = root;
int leftH = 0;
int rightH = 0;
if(temp == NULL)
return 0;
if(temp->left)
leftH = height(temp->left);
if(temp->right)
rightH = height(temp->right);
return leftH >rightH ? leftH+1 : rightH+1;
}

int main()
{
struct bst *root=NULL;
struct bst *tmp=NULL;
int i,n,key,option;
printf("Enter the no. elements in the BST\n");
scanf("%n",&n);
printf("Enter the list of elements in the BST\n");
for(i=0;i<n;i++)
{
scanf("%d",&key);
root = insert(root,key);
}
printf("Below are the possible opetaions you can performe in the above created BST\n");
printf("1. Insert\n2. Delete\n3. In-Order\n4. Pre-Order\n5. Post-Order\n6. Find Minimum\n7. Find Max\n8. height\n other value for exit");
scanf("%d,&option");
while(1)
{
switch(option)
{
case 1:
printf("Enter the valeu to insert into the BST\n");
scanf("%d",&key);
root = insert(root,key);
break;
case 2:
printf("Enter the value to delete from the BST\n");
scanf("%d",&key);
delete(root,key);
break;
case 3:
print_inorder(root);
break;
case 4:
print_preorder(root);
break;
case 5:
print_postorder(root);
break;
case 6:
if(tmp)
printf("Min value in BST is %d\n",tmp->info);
break;
case 7:
tmp = find_max(root);
if(tmp)
printf("Max value in BST is %d\n",tmp->info);
break;
case 8:
printf("height of the BST is %d\n",height(root));
break;
default:
return 0;
break;
}
printf("Below are the possible opetaions you can performe in the above created BST\n");
printf("1. Insert\n2. Delete\n3. In-Order\n4. Pre-Order\n5. Post-Order\n6. Find Minimum\n7. Find Max\n8. height\n other value for exit");
scanf("%d,&option");
}
}

```

## Wednesday, June 13, 2012

### strncpy function in C

strncpy string function is used to copy the specified no. of characters from one string to another string. This is similar to strcpy string function. But the difference is , strcpy is just copies all the characters from source string to destination string until source reaches termination character. whereas strncpy copies only n characters from the source string to destination string if there is no terminal character. If any terminal character is ther before the nth character, it will stop the copying. strncpy is not a null termination character function. So strncpy is more advisable to use over strcpy.  Because memory overwriting will not happen in strncpy.

Syntax for strncpy:

```char *strncpy(char *dest, const char *src, size_t n);
```

strncpy function in C using array:
```//using arrays , need to move the string using index
void strcpy_arry(char * dest, char *src)
{
int i=0;
while((dest[i]=src[i])!='\0')
i++;
}

```

strncpy function in C using pointers:
```//using pointers, need to move the position of the pointer
void strcpy_ptr(char *dest, char *src)
{
while((*dest=*src)!='\0')
{
src++;
dest++;
}
}
```

## Thursday, June 7, 2012

### strlen function in C

strlen string function is the one of the most common function used regularly to find the length of the string in C programming language. It returns the length of the string excluding (not including) null character or '\0'.  String library provides the inbuilt function for finding the length of the string and syntax is given below.

```int strlen(const char *str);

```
Below is the sample code to find the length of string using strlen string function and later we will see our own function to find the string length.

```main()
{
char str[]="this is string";
int len = strlen(str);
printf("len is %d\n",len);
}

```
Output:
len is 14

strlen function definition: Below are the function for finding string length. I have given the code for finding strign length using both array and pointers.

strlen function with arrays:
```int strlen_arry(char *str)
{
int len=0;
while(str[len]!='\0')
len++;
return len;
}

```
strlen function with pointers:
```int strlen_ptr(char *str)
{
int len=0;
while(str!='\0')
{
str++;
len++;
}
return len;
}
```

Explaination:  We will get the length of the string by counting the no. characters in the string. For this we need to traverse the string starting from zeroth character. In first method for arrays, we will traverse the string using index until reaches the null or terminal charater. Where as in second method for pointers ,we need to increase the pointer until pointer reaches the null or terminal characater.

## Tuesday, June 5, 2012

### strcpy function in C!!

C  provides the string library (string.h) for manipulating the string operations like strcpy, strlen, strcmp etc. Here I will give undefined implementation of the each string function. I will start with strcpy function.

strcpy  is one of the most common and regularly used function. Its is used to copy one string into another string making original string as it is. It will be very use full while parsing the strings. The syntax for strcpy  is given below.

`char *strcpy(char *dst, char *src);`

Syntax is taken from the man page. This function copies all the characters (including null character) from src to the dst.  first argument for this function is destination string and second argument is the source string. See the sample code snippet for string copy using strcpy function.

```#include&lt;stdio.h>
#include&lt;string.h>
main()
{
char amessage[] = "this is a string";
char newmessage[20];

//copying amessage to newmessage
strcpy(newmessage,amessage);

printf("amessage is '%s'\n",amessage);
printf("newmessage is '%s'\n",newmessage);
}
```

Output:
amessage is 'this is a string'
newmessageis 'this is a string'

To compile above program successfully, we need to include string.h header as we are using strcpy  string function to copy.

Implementing our own user defined string copy function is the common question regularly asked in general C/C++ interviews. So I am giving different ways (arrays and pointers) of implementing string copy function.

String copy function using arrays:

```//using arrays , need to move the string using index
void strcpy_arry(char * dest, char *src)
{
int i=0;
while((dest[i] = src[i])!='\0')
i++;
}
```

Explanation: Using arrays, it is very easy to copy the string. Just take the index value , copy the character at the index into new array and increment the index and continue this until null or '\0' character occurs.

String copy function using pointers:

Method1:

```//using pointers, need to move the position of the pointer
void strcpy_ptr(char *dest, char *src)
{
while((*dest = *src)!='\0')
{
src++;
dest++;
}
}

```
Explanation: Using pointers copying the string is little bit tricky. As most of you know , accessing the value is asterisk(*), assign the value to the new pointer  and increment both the pointers.  Continue this until pointer reaches the null or '\0' character.

Method2:

```//using pointers, need to move the position of the pointer
void strcpy_ptr_short(char *dest, char *src)
{
while((*dest++ = *src++)!='\0')
;
}
```

Explanation: Same as the above method1, but the difference is, we can use the incrementing pointer statements with in the if statement.

Main function:

```main()
{
char amessage[] = "this is a string";
char newmessage[20];

strcpy_arry(newmessage,amessage);
//strcpy_ptr(newmessage,amessage);
//strcpy_ptr_short(newmessage,amessage);

printf("amessage is '%s'\n",amessage);
printf("newmessage is '%s'\n",newmessage);

}
```

Output:
amessage is 'this is a string'
newmessage is 'this is a string'

In main I commented remaining function calls. you can un-comment and test all the functions.

Even though strcpy  is use full function , there are some important points to remember before using it.
• strcpy function copies the null character also, so its better allocate extra memory for that if you use any memory allocation.
• check the destination string size and make sure that its enough to store the source string.
• if both source and destination strings are overlapped, this functin is undefined.