Data Structures

Data Structures

Purpose of Dynamic memory allocation:

The process of allocating memory at run time is known as dynamic memory allocation. Although C does not inherently have this facility there are four library routines which allow this function. Many languages permit a programmer to specify an array size at run time. Such languages have the ability to calculate and assign during executions, the memory space required by the variables in the program. But C inherently does not have this facility but supports with memory management functions, which can be used to allocate and free memory during the program execution.
Dynamic memory allocation is the practice of assigning memory locations to variables during execution of the program by explicit request of the programmer. Dynamic allocation is a unique feature to C (amongst high level languages). It enables us to create data types and structures of any size and length to suit our programs need within the program.

The main advantage of using dynamic memory allocation is preventing the wastage of memory. This is because when we use static memory allocation, a lot of memory is wasted because all the memory allocated cannot be utilised. Thus dynamic memory allocation helps us to allocate memory as and when required and thus saves memory.

•    In static memory allocation, if we allocate 1000 memory locations as int name [1000]; while running the program only half of this may be used. The rest is unused and idle. It is wastage of memory.
•    If we want to change the size of the array in the program, it is possible by reediting the program. It is a time consuming process.

In dynamic memory allocation the above two problems won't occur because, the memory space for variables is allocated only during execution. The following functions are used in c for purpose of memory management.

malloc: Allocates memory requests size of bytes and returns a pointer to the Ist byte of allocated space

calloc: Allocates space for an array of elements initializes them to zero and returns a pointer to the memory

free: Frees previously allocated space

realloc: Modifies the size of previously allocated space.

Malloc, calloc, realloc and free:

malloc() Function:
This function is used to allocate a contiguous block of memory in bytes.

Syntax:

pointer variable = (cast-type*) malloc (size);
Where,
Pointer variable - A pointer variable contains the memory location of another variable.

Cast-type - type of the pointer return by malloc () such as int.char etc.

malloc - keyword

size - required size of the memory in bytes

The above function allocates memory of size and returns the starting address of the memory through pointer variable of type cast-type. The allocated area is not filled with zeroes.

Example:

i). y = (int *) malloc (20)

On execution of this function 20 bytes of memory are allocated and the starting address of the first byte is assigned to the pointer y of type 'int'.

ii). y = (int *) malloc (10 * sizeof (int);

On execution of this function 10 times the size of an 'int' i.e. 10x2=20 bytes is allocated and the starting address of the first byte is assigned to the pointer y of type 'int'. If the allocation is success it returns the starting address else NULL.

calloc() Function: This function is used to allocate multiple blocks of contiguous memory. All the blocks are of same size.

Syntax:

pointer variable = (cast - type *) calloc(n, size);

Where,
pointer variable - A pointer variable contains the memory location of another variable.

Cast-type - type of the pointer return by calloc () such as int. char etc.

calloc - keyword
n - number of blocks

size - required size of memory in bytes

Example:


y = (int *) calloc (3, 10);

On execution the function allocated 3 memory blocks of size 10 bytes and returns the starting address of the area through the pointer y of type "int".                

free() Function:
If you have allocated a memory block with the functions malloc(), calloc() or realloc() then you need to free the previously allocated memory. Its main features are

•    This function is used to de-allocate the previously allocated memory using malloc() or calloc() function.
•    free function is used to return the allocated memory block to the system memory RAM.

Syntax:

free(ptr);

Example:

•    y=(int *) malloc(10)
•    free(y)

realloc() Function:

Syntax:

void *realloc( void *ptr, size_t new_size);

Realloc is a function which attempts to change the size of a previous allocated block of memory. The new size can be larger or smaller. If the block is made larger than the old contents remain unchanged and memory is added to the end of the block. If the size is made smaller then the remaining contents are unchanged. If the original block size cannot be resized then realloc will attempt to assign a new block of memory and will copy the old block contents. Note a new pointer (of different value) will consequently be returned. You must use this new value. If new memory cannot be reallocated then realloc returns NULL. Thus to change the size of memory allocated to the *ip pointer above to an array block of 50 integers instead of 100, simply do
ip = (int *) realloc ( ip, 50);

Sorting:

Sorting is a process in which records are arranged in ascending or descending order. For example, the telephone directory contains names of the persons and the phone numbers are written according to ascending alphabets. The records of the list of these telephone holders are to be sorted by the name of the holder. By using this directory, we can find the telephone number of any person easily. Sort method has great importance in data structures.

For example, consider the five numbers 5 9 7 4 1

The above numbers can be sorted in ascending or descending order.

Ascending order (0 to n): 1 4 5 7 9

Descending order (n t 0): 9 7 5 4 1

Sorting is classified into following types, they are:

•    Bubble sort
•    Selection sort
•    Quick sort
•    Insertion sort
•    Merge sort

Bubble Sort:

Bubble Sort is probably one of the oldest, easiest, straight-forward, inefficient sorting algorithms. It is the algorithm introduced as a sorting routine in most introductory courses on Algorithms. Bubble Sort works by comparing each element of the list with the element next to it and swapping them if required. With each pass, the largest of the list is "bubbled" to the end of the list whereas the smaller values sink to the bottom. It is similar to selection sort although not as straight forward. Instead of "selecting" maximum values, they are bubbled to a part of the list.

/*program to example of bubble sorting*/
#include<stdio.h>
int main()
{
int s, temp, i, j, a [20];
printf ("Enter total numbers of elements: ");
scanf ("%d", &s);
printf ("Enter %d elements: ",s);
for (i=0;i<s;i++)
scanf ("%d", &a [i]);
//Bubble sorting algorithm
for (i=s-2;i>=0;i--){
for (j=0;j<=i;j++){
if (a[j]>a[j+1]){
temp=a[j];
a [j]=a[j+1];
a [j+1]=temp;
}
}
}
printf ("After sorting: ");
for (i=0;i<s;i++)
printf (" %d", a[i]);
return 0;
}

Output:


Enter total numbers of elements: 5

Enter 5 elements: 6 2 0 11 9

After sorting:  0 2 6 9 11

Selection Sort:

Selection sort is also called as push-down sorting. As the name suggests, the first element of the list is selected and compared repeatedly with each and every element up to last. If any element is found to be lesser than the selected element, these two are swapped. This procedure is repeated till the entire array is sorted. It is slow and not very intelligent, because it compares with each and every one.

/*program to demonstration of selection method*/

#include<stdio.h>
int main(){
int s, i, j, 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=0; i<s;i++){
for (j=i+1;j<s;j++){
if (a[i]>a[j]){
temp=a[i];
a [i]=a[j];
a [j]=temp;
}
}
}
printf ("After sorting is: ");
for (i=0;i<s;i++)
printf (" %d", a[i]);
return 0;
}

Output:


Enter total elements: 5

Enter 5 elements: 4 5 0 21 7

The array after sorting is:  0 4 5 7 21

Quick Sort:


It is considered to be a fast method to sort the elements. The method is also called partition exchange sorting. The method is based on divide-and-conquer technique i.e. the entire list is divided into various partitions and sorting applied again and again on the partitions.
In this method, the list is divided into two, based on an element called the pivot element. Usually the first element considered to be pivot element. Now move the pivot element into its correct position in the list. The elements to the left of the pivot are less than the pivot while the elements to the right of the pivot are greater than the pivot. The process is reapplied to each of these partitions. This process proceeds till we get the sorted list of elements.

/*program to demonstration of quick sort*/
#include<stdio.h>
void quicksort(int [10],int, int);
int main(){
int x[20],size, i;
printf ("Enter size of the array: ");
scanf ("%d", &size);
printf ("Enter %d elements: ",size);
for (i=0; i<size; i++);
scanf ("%d", &x[i]);
quicksort (x, 0, size-1);
printf ("Sorted elements: ");
for (i=0;i<size;i++)
printf (" %d", x[i]);
return 0;
}
void quicksort(int x[10],int first, int last){
int pivot, j, temp, i;
if (first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while (x[i]<=x[pivot]&&i<last)
i++;
while (x[j]>x[pivot])
j--;
if (i<j){
temp=x[i];
x [i]=x[j];
x [j]=temp;
}
}
temp=x [pivot];
x [pivot]=x[j];
x [j]=temp;
quicksort (x,first,j-1);
quicksort (x,j+1,last);
}
}

Output:


Enter size of the array: 5

Enter 5 elements: 3 8 0 1 2

Sorted elements: 0 1 2 3 8

Insertion Sort:


Insertion sort is a simple sorting algorithm. In insertion sort each element is compared with before element(s) and inserted before its higher element. This will be repeated until the sorting is finished.
Suppose an array with n elements a[1], a[2],……,a[n] is in memory. The insertion sort algorithm scans a from a[1] to a[n], inserting each element a[k] into its proper position in the previously sorted subarray a[1], a[2], ..., a[k-1].

/*program to demonstration of quick sort*/
#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

Merge Sort:

 

The merge sort technique sorts a given set of values by combining two sorted arrays into one larger sorted array. Consider a sorted array, A which contains p elements, and the sorted array B, containing q elements. The merge sort technique combines the elements of A and B into single sorted array C with p+q elements. The first data item of the A array is compared with the first data item of the B array. If the first data item of A is smaller than the first data item of B, then that data item from A is moved to the array, C. If the data item of B is smaller than the data item of A, then it is moved to array, C. This comparing of data items continues until one of the array ends.

/*program to demonstration of merge sort*/
#include< stdio.h>
#include< conio.h>
void mergesort(int a[],int n)
{
int b[50],c,low1,high1,high2,low2;
int i, k, j;
c=1;
while (c< n)
{
low1=0;
k=0;
while (low1+c< n)
{
low2=low1+c;
high1=low2-1;
if (low2+c-1< n)
high2=low2+c-1;
else
high2=n-1;
i=low1;
j=low2;
while (i< =high1 && j< =high2)
{
if (a[i]< =a[j])
b [k++] =a[i++];
else
b [k++] = a[j++];
}
while (i< =high1)
b [k++]=a[i++];
while (j< =high2)
b [k++] =a[j++];
low1=high2+1;
}
i=low1;
while (k< n)
b [k++] =a[i++];
for (i=0;i< n; i++)
a [i]=b[i];
c=c*2;
}
}
main ()
{
int a[20], i, n;
clrscr ();
printf ("Enter The number Of Elements\t: ");
scanf ("%d", &n);
for (i=0;i< n; i++)
{
printf ("\n Element %d\t: ",i+1);
scanf ("%d", &a[i]);
}
printf ("\n Array Before Sorting : ");
for (i=0;i< n; i++)
printf ("%5d", a[i]);
mergesort (a, n);
printf ("\n Array After Sorting: ");
for (i=0; i< n; i++)
printf ("%5d", a[i]);
getch ();
return 0;
}

Output:

Enter the number Of Elements: 10

Element 1: 12
Element 2: 54
Element 3: 98
Element 4: 6566
Element 5: 45
Element 6: 12
Element 7: 5
Element 8: 1
Element 9: 156
Element 10: 21

Array Before Sorting: 12 54 98 6566 45 12 5 1 156 21

Array After Sorting: 1 5 12 12 21 45 54 98 156 6566

0 comments:

Post a Comment