Hashing With Separate Chaining In C.

As we know that in Hashing, we use a Hash Function that maps keys to certain values. Now, sometimes certain situation arises where these values which we obtain from our hash function collides, Well this conditions are termed as collisions. Now what can be done, so that collision can be prevented, well certain techniques are available which can prevent collisions and these techniques are as follows:

1 ) Closed Hashing, also called as Open Addressing.

2) Open Hashing, also called as Separate Chaining.

Separate Chaining / Open Hashing : 

The idea behind separate chaining is pretty straight forward, what we do in separate chaining is that we make each cell of hash table point to linked list data that corresponds to same hash value (i.e the value obtained from collision between to values.).

Following example can help us better understand the concept, lets create a hash function for N number of objects or numbers, that will be simply,

H.I = Key % N

Where,  H.I is the hash index.

               Key is any number from given set of numbers.

               N is the total of numbers of objects.

Now that we've a hash function let's take an example to start with the explanation, say we've the following sets of input for which we've to determine the hash table using separate chaining technique:

Let's take hash table with 7 buckets ( 0 , 1 , 2 , 3 , 4, 5 , 6 )  so value of N is 7, and the Keys being ( 14 , 16 , 21 , 24 , 18). Now to obtain the hash index for each of these keys we first need to put it in the H.I formula.

For Key = 14 and N =7  we have H.I = 0 ,

Similarly, for Key = 16 and N =7 , H.I = 2,

And for 21 H.I = 0 ,

For 24 H.I = 3 ,

Lastly for Key = 18 , H.I = 4

So, we can represent our Hash Table in like this.

As you can see in index 0 there is a collision between keys 14 and 21, but using separate chaining technique we simply linked the data(14 , 21) to the same hash value.

Hashing with separate chaining C code :

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

//Declarations Necessary for the Implementation Part.
struct node
{
    int info;
    struct node*link;
};

//Function Declarations
int index(int item);
struct node * insert_sorted(struct node *index,int data);
void search(struct node * index,int item);
struct node*delete_node(struct node *index,int item);
void display(struct node * index);


int main()
{   int data,choice,ind,i;
    struct node * H[10];
    //Initialization
    for(i=0;i<10;i++)
    {
        H[i]=NULL;
    }

    while(1)
    {
        printf("Please select a choice\n");
        printf("1. Insert\n");
        printf("2. Search\n");
        printf("3. Delete\n");
        printf("4. Display\n");
        printf("5. Exit\n");
        scanf("%d",&choice);

    switch(choice)
    {
        case 1:
            {
                printf("Please enter the data\n");
                scanf("%d",&data);
                H[index(data)]=insert_sorted(H[index(data)],data);
                printf("\n\n");
                break;
            }
        case 2:
            {
                printf("Please enter the item\n");
                scanf("%d",&data);
                search(H[index(data)],data);
                printf("\n\n");
                break;
            }
        case 3:
            {
                printf("Please enter the item\n");
                scanf("%d",&data);
                H[index(data)]=delete_node(H[index(data)],data);
                printf("\n\n");
                break;
            }
        case 4:
            {
                printf("Please enter the index to display the link info's\n");
                scanf("%d",&ind);
                display(H[ind]);
                printf("\n\n");
                break;
            }

        case 5:
            {
                printf("Sankyu For Using the Program\n");
                printf("\n\n");
                return 0 ;
            }
        default:
            printf("Wrong Choice\n");
            printf("\n\n");
            break;
    }

    }
return 0;
}

//Function Definitions
int index(int item) //Hash Function
{
    return item%10;
}

struct node * insert_sorted(struct node *index,int data)
{
    struct node* temp=(struct node*)malloc(sizeof(struct node)),*p;
    if(temp==NULL)
    {
        printf("New Node Can't be created\n");
        return index;
    }
    //Inserting the Data.
    temp->info=data;

    //Creating the links.

    if(index==NULL)
        {
            temp->link=NULL;
            index=temp;
            return index;
        }
    else //Insertion in the rest nodes.
        {   //Inserting Data at the Beginning
            if(index->info>data)
                {
                    temp->link=index;
                    index=temp;
                    return index;
                }
            p=index;
            while(p->link!=NULL)
            {
                if(p->link->info<data) //This scans till the last node.
                    p=p->link;
                else
                {
                    temp->link=p->link;
                    p->link=temp;
                    return index;
                }
            }
            //This is to insert the data after the last node.
            p->link=temp;
            temp->link=NULL;
            return index;
        }
};

void search(struct node * index,int item)
{
    struct node *p=index;
    while(p!=NULL&&p->info<=item) //To decrease the search time by breaking
        //search when we get any data which is greater than the data. As after that data
        //We can't get the requested data since the nodes are sorted.
    {
        if(p->info==item)
        {
            printf("Successful Search\n");
            return; //So that the address of the node where the data is present is given to the user.
        }
        p=p->link;
    }

    printf("Unsuccessful Search\n");
    return;
};

struct node*delete_node(struct node *index,int item)
{   if(index==NULL)
    {
            printf("The Index is empty\n");
            return index;
    };

    struct node*p=index,* temp;
    //The starting node has the item itself
    if(p->info==item)
    {
        temp=p;
        index=temp->link;
        free(temp);
        return index;
    }
    while(p->link!=NULL)
    {
        if(p->link->info<=item) //So to stop search after getting a
                                //node greater than the data.
        {
            if(p->link->info==item)
            {
                temp=p->link;
                p->link=temp->link;
                free(temp);
                return index;
            }
            p=p->link;
        }
    }

    printf("Item doesn't exist\n");
    return index;
};

void display(struct node * index)
{
    if(index==NULL)
        {
            printf("Index is empty\n");
            return;
        }
    struct node*p=index;
    while(p!=NULL)
    {
        printf("%d ",p->info);
        p=p->link;
    }
    printf("\n");
    return;
};

Output for the above program is :

Merge Sort In C

Merge Sort is a sorting technique based on Divide and Conquer principle, in merge sort we first divide the array into two equal halves and merge them together into sorted manner. With worst case time complexity of O(n log n), it is one of the most respected algorithms.

Explanation :

Basically what we do in merge sort is pretty straight forward, we first divide the array into equal halves until we reach a point where no more division can take place and then sorting takes place, once sorting is done completely, we merge the sorted array and hence we obtain our sorted array.

Example:

Let's take an unsorted array to start with our example.

                                      4  2  6  1  7  5  3  8

we now divide the array into two equal parts , i.e of three parts, so after this step we've our array as..

                                     4  2  6  1  -  7  5  3  8

                         (Where the ' - ' signifies the two divided parts.)

we still can divide our array into two parts, so..

                                   4  2  -  6  1  -  7  5  -  3  8

Again we divide to obtain..

                             4  -  2  -  6  -  1  -  7  -  5  -  3  -  8

Now we observe that no further division of array can take place, so our next step will be to combine them in the exact same order in which they were broken down. Here we first compare the elements in each list and then combine them into another list in sorted manner. We observe that 4 and 2 are not sorted order so we swap there positions, same goes for 6 & 1, so we swap there positions too, also for 7 & 5, but 3 and 8 are in correct position, so we leave them as it is. So we've our array as follows after this step..

                                  2  4  -  1  6  -  5  7  -  3  8

Now after this step we've to check order for 2,4,1 and 6 we see correct order is 1,2,4 and 6 similarly for 5,7,3 and 8 correct order is 3,5,7 and 8. so after this step we've our array as follows....

                                   1  2  4  6  -  3  5  7  8

and you can guess how the final step will turn up so we get our sorted array..

                                    1  2  3  4  5  6  7  8

Well, this the mechanism for Merge Sort , next we'll be looking at its coding part in C so that we can implement the concept we just understood.

Merge Sort C Code :

Output of the above program is :

                                             if you find any problem in the above code, then kindly add a comment in the comment section. 

Constructors & Destructors in C++

Constructors 

A constructor is defined as a 'special' member function, whose work is to initialize  the objects of its class. You might be wondering that why 'special' word is used in the definition of the constructor, well this is because the name of the constructor is same as the class name. The constructor is invoked whenever an object of its associated is created. Another question arises why is it named constructor, well one way to look at this is because it is used to create or construct the value of data member of its class.

Following example will help you understand constructor declaration and definition.

As you can see in the above example , the class name test has a constructor named 'test', it is first declared in the class itself and later defined outside the class using scope resolution operator ( ': :' ) as shown in the above example. Now this constructor will be invoked as soon as an object of class test is created, for example :

test t1 ;                              // constructor invoked.

Constructor can be of the following types :

• Default Constructor.

• Parameterized Constructor.

• Copy Constructor.

• Dynamic Constructor.

Destructors

Destructors, as the name suggests is something that will destroy something, in this context, destructor is a member function whose function is to destroy the object created by the constructor, like constructor, destructor also have same name as of class name, but it is preceded by a tilde.

In our previous example, if we want to destroy the object created by constructor 'test' , following has to be done.

~test( ){ }                        // Destructor declaration.

At the end of the program, all the test objects will be destroyed, always remember that a destructor never takes any argument nor returns any value, henceforth it will be invoked implicitly by the compiler when the program ends.

It is a good habbit to declare a destructor in your program as it will release memory space for future use.Whenever new operator is used to allocate memory in any program, in order to delete that space, we use delete operator, for example.

The primary use of destructor is in freeing up of memory reserved by the object before it gets destroyed.

Dynamic Memory Allocation.

Dynamic Memory Allocation 

Most often we face situations in programming where the data is dynamic in nature. i.e. the number of data items keep changing during the execution of the program. For example, consider a program for processing the list of customers of a corporation. The list grows when names are added and shrinks when names are deleted. When list grows we need to allocate more memory space to the list to accommodate additional data items. Such situations can be handled more easily and effectively by using what is known as dynamic data structures in conjunction with dynamic memory management techniques. Dynamic data structure provides flexibility in adding, deleting or rearranging data items at run time. Dynamic memory management (i.e. DMA) technique permits to allocate additional memory space or to release unwanted space at run time, thus optimizing the usage of storage space. 

 Introduction 

The exact size of an array is unknown until the compile-time i.e. time when a compiler compiles code written in a programming language into an executable form. The size of the array you have declared initially can be sometimes insufficient and sometimes more than required. What? The process of allocating memory during program execution is called dynamic memory allocation. It also allows a program to obtain more memory space, while running or to release space when no space is required. 

Following example will help you understand use of dynamic memory allocation in any program.

WAP to find out the smallest and largest element sorted in an array of n integers.

code contributed by anmol sinha

Memory Allocation Process

Global variables, static variables and program instructions get their memory in permanent storage area whereas local variables are stored in area called Stack. The memory space between these two region is known as Heap area. This region is used for dynamic memory allocation during execution of the program. The size of heap keep changing when program is executed due to creation and death of variables. Therefore it is possible to encounter memory “overflow” during dynamic allocation process. In such cases, the memory allocation process will return a NULL pointer.

Watch this Youtube video to better understand the topic.

More examples :

• WAP to sort an array of n numbers.
• WAP to reverse the contents of an array of n elements.