DATA STRUCTURE USING C UCST

Unit-1
Introduction to data structures

Data structure definition:

The logical or mathematical organization of the data is called data structure.
(Or)
Arranging the data element in some particular order either ascending or descending order or
alphabetical order or in different manner is called as data structure.
(Or)
Representation of the data along with associated operation is known as data structure.
Goals of data structure:
1. Correctness: a data structure is designed to work correctly for all the input.
2. Efficiency: use of efficient memory space.
3. Robustness: a program produces the correct output for all the input.
4. Adoptability: use of modern software project to increase the CPU speed.
5. Reusability: the same code can be reusable in different system for various operations.
Classification of data structure:
Data structure

Primitive data structure Non –primitive data structure

Int
Char
Float Linear Non -linear
Double data structure data structure
Pointer Arrays Trees
Stacks Graphs
Linked lists
Queues

Kanyakumari B [dept. of CS] Page 1

 DATA STRUCTURE USING C UCST

Data structure can be classified into two types:

1. Primitive data structure
2. Non- primitive data structure
Primitive data structure: primitive data structure includes all the fundamental data structure
that can be directly manipulated by machine level instructions.
Ex: Int, float, char, double, pointer
Non-primitive data structure:
 Non-primitive data structure includes all the fundamental data structure that cannot be
directly manipulated by machine level instructions.
 Non-primitive data structure that are derived from one or more primitive data structure
Ex: Arrays, stacks, linked lists, trees, graphs.

Non-primitive data structures are further classified into two types.

1. Linear data structure: all the data elements are arranged in sequential or linear fashion
is known as linear data structure.
Ex: arrays, queues, stacks, linked lists
2. Non –linear data structure: all the data elements are arranged in non-sequential or non-
linear fashion is known as non-linear data structure.
Ex: graphs, trees
Arrays:
 An array is a linear data structure.
 An array is an ordered collection of similar type of data elements stored at a consecutive
location in the memory.
 The group of array elements referred with a common name called array name.
 Access to individual array element is provided with an index identifier.
Ex: Int a [5] = {1, 2, 3, 4, 5}
Array index a [0] a [1] a [2] a [3] a [4]

1 2 3 4 5
A
Address 1000 1002 1004 1006 1008

Kanyakumari B [dept. of CS] Page 2

 DATA STRUCTURE USING C UCST

Stacks:
 Stack is a linear data structure where insertion and deletion at one end i.e. top end.
 Stack is based on the Last-in-first-out [LIFO] principle.
Insertion Deletion

30 Top end
20
10

Queues:
 Queue is a linear data structure in which elements are inserted at one end is called rear
end and deletion at one end is called front end.
 Queue is based on the First-in-first-out [FIFO] principle.

Front end (deletion) Rear end (insertion)

Linked lists:
 Linked list is a linear data structure used for storing the data in the form of list.
 The multiple nodes are connected to each other through pointer.
 In the list the node contains two parts

Info Link

Info -> this part contains the actual information.

Link -> this part contains the next node address.
Trees:
 Tree is a non-linear data structure that arrays its nodes in the form of hierarchical tree
structure.

Kanyakumari B [dept. of CS] Page 3

 DATA STRUCTURE USING C UCST

Graphs:
 Graph is a non-linear data structure that comprises of a group of vertices called nodes
and a group of edges.
Operations on data structure:
Operations on primitive data structure:
1. Creation: used to create the storage representation for a particular data structure.
Ex: int a=10; a=variable name, 10=value, 100=address
2. Selection: used to access the data element with in a structure
Ex: printf (“%d”, a);
3. Update: used to modify or edit the data element
Ex: a=30;
4. Destroy: used to delete or remove the particular data element from its storage representation
Ex: free ()

Operations on non –primitive data structure:

1. Traversing: This is the process of visiting the data element of data structure exactly once.
2. Sorting: It is the process of arranging the data element of data structure in a specific order
such as alphabetical, ascending or descending order.
3. Merging: It is the process of combining the data of two different sorted data structure into
single sorted data structure.
4. Searching: It is a process of finding a key element in the data structure.
5. Inserting: It is the process of insert a new element into data structure.
6. Deleting: It is the process of removing an existing data element from a data structure.

Dynamic memory allocation:

Static and dynamic memory allocation:
1. Static memory allocation: The memory allocated for variables and constants during
declaration or compilation is called static memory allocation .The size of these variables
cannot be varied during run time (execution).
Ex: int x, y;
Int a [20];

Kanyakumari B [dept. of CS] Page 4

 DATA STRUCTURE USING C UCST

Characteristics of static memory:

It has fixed memory block hence there is wastage of memory.
It is difficult to perform insertion and deletion.
Not suitable for unpredictable storage requirements.
Pre – defined functions like malloc (), calloc (), free () not required.

2. Dynamic memory allocation: It is a process of allocating memory during execution. This

is a unique feature used to create variables of any size required during execution.
Characteristics of dynamic memory:
It has variable size of memory block hence no wastage of memory.
It is easy to perform insertion and deletion.
Used when there is an unpredictable storage requirement.
Requires predefined functions like malloc (), calloc (), free () etc.

Difference between static and dynamic memory allocation:

Static dynamic
In this memory is allocated at compile time In this memory is allocated at run time
In static memory allocation, once the memory In dynamic memory allocation, when memory
is allocated, the memory size cannot changed. is allocated the memory size can be changed.

Execution is faster Execution is slower

Static memory allocation is generally used for Dynamic memory allocation is used for linked
arrays. list.
Less efficient More efficient
It uses stack for managing the static allocation It uses heap for managing the dynamic
of memory. allocation of memory.

Memory allocation and de-allocation functions:

1) malloc () function: This function dynamically allocates requested bytes from the free
memory area. The prototype for this function is <alloc.h> or <stdlib.h>. The malloc ()

Kanyakumari B [dept. of CS] Page 5

 DATA STRUCTURE USING C UCST

function returns the starting address of the memory if it is successful to allocate the
required memory block, otherwise return NULL value to the specified pointer variable.
Syntax: ptrvar= [(data type*)] malloc (size);
Where, ptrvar is the pointer variable, data type is the conversion parameter; SIZE is the
required sized memory blocks.
Ex: int*p;
P= (int *) malloc (5* size of (int));
Ex: write a program to accept and display string using malloc () function.
#include<stdio.h>
#include<string.h>
#include<alloc.h>
Void main ()
{
Char *str;
if((str = (char *) malloc (10))== NULL) /*allocate memory for string */
{
printf (“out of memory\n”);
exit (1); /*terminate program */
}
Strcpy (str, “hello”); /*copy “hello” into str */
Printf (“string is %s\n”, str); /*display string*/
free(str); /*free memory*/
}

2) Calloc () function: It is used for allocating the requested memory space. It also
allocates multiple blocks of storage space such that the size of each block is same and
each byte of allocated memory space is initiated to zero. The prototype of this function is
defined in a header file <alloc.h> or <stdlib.h>.
Syntax: Ptr= (data type *) calloc (n, SIZE);
Where, ptr is a pointer variable of type data type.
Data type can be any of the basic, user defined data type

Kanyakumari B [dept. of CS] Page 6

 DATA STRUCTURE USING C UCST

SIZE is the number of bytes required

n is the number of blocks to be allocated of size bytes .
This function returns a pointer to the newly allocated block. The total number of bytes
allocated is equal to n* SIZE and each location in the allocated memory is initialized with value
Zero .If enough space does not exists for the new block or if n is zero or SIZE is zero, this
function returns NULL.
Ex: int*p;
P= (int*) calloc (5, size of (int));
Calloc () allocates 5 blocks, each block size is int.
Ex: write a program to accept and display string using malloc () function.
#include<stdio.h>
#include<string.h>
#include<alloc.h>
Void main ()
{
Char * str =NULL;
str = (char *) calloc (10, size of (char)); /*allocate memory for string */
if (str== NULL)
{
printf (“out of memory\n”);
exit (1); /*terminate program */
}
Strcpy (str, “hello”); /*copy “hello” into str */
Printf (“string is %s\n”, str); /*display string*/
free(str); /*free memory*/
}

3) Realloc () function: The memory allocated using malloc () or calloc () may not be
sufficient and we need additional memory space for some applications. Sometimes
previously allocated memory may be much larger and size of allocated memory need to be
reduced. In such a case, the size of allocated memory can be changed using realloc ()

Kanyakumari B [dept. of CS] Page 7

 DATA STRUCTURE USING C UCST

function and the process is called re-allocation of memory. This function guarantees that
re-allocation will not destroy the original contents of memory.
Syntax: Ptr= (data type *) realloc (ptr, new SIZE);
Where, ptr is a pointer variable of type data type.
new SIZE is the number of bytes required
int *p;
p= (int*) calloc (5, size of (int));
calloc () allocates 5blocks, each block size is int.
We want to increase the memory size to another 2 blocks as follows
P= (int*) realloc (p, 7);

4) free (): This function dynamically de- allocate the memory block, which is allocated by
malloc () or calloc (). This function prototype is available under <alloc.h> header file.
Syntax: free (p);
Ex: free (p);
Difference between malloc () and calloc ()
malloc () calloc ()
It allocated single block of requested memory It allocates multiple blocks of requested memory
Syntax:(single parameter ) malloc (number* Syntax: ( two parameters) calloc (number ,size of
size of (int)); (int));
malloc () does not initialize ; i.e. allocated calloc () initializes zero for allocated memory
memory has garbage value
eg ; ptr=(int*) malloc (5* size of(int)); Eg ; ptr=(int*)calloc (%=5,6 size of( int));
allocates single block of 5 *2bytes of memory Allocates 5 blocks each of (6*2=12) bytes of
memory

Recursion:
Definition: a function call itself again and again until certain condition is true is called recursion.
 Recursive is a process of calling the function repeatedly until it satisfies the specified
condition.

Kanyakumari B [dept. of CS] Page 8

 DATA STRUCTURE USING C UCST

 The recursive function calls are initially pushed onto the stack until the condition
encountered, after terminating the condition. The recursive functions are popped from
the stack one by one.
 The recursive function works under the stack technique. Last-In-First-Out [LIFO]
manner for execution.
 The recursive function must satisfies the following condition.
 The function must have terminating condition that is it should not to call infinite
times.
 Each time the function calls itself and must be recovering to the solution.
Syntax: function ()
{
If (condition)
Return;
.
.
.
Function ();

Types of recursion:
1. Direct recursion: A function call itself directly again and again is called direct recursion.
Syntax: function ()
{
.
.
Function ();
}

2. Indirect recursion: A function call eventually from another function is called indirect
recursion.
Syntax:

Function1 () function2 () function 3()

{ { {
. . .
. . .
Function2 (); function 3(); function 1();
} }

Kanyakumari B [dept. of CS] Page 9

 DATA STRUCTURE USING C UCST

Advantages:
 It reduces the coding lines.
 It works under divide and conquer technique.
 Programs are very simpler.
 Recursion programmer utilizes lesser coding time.
Dis advantages:
 Possible to get infinite times execution.
 Difficult to trace the program.
 It requires more space for variables.
Ex: Write a program to implement nCr using recursion.
#include<stdlib.h>
#include<conio.h>
Int fact (int);
Void main ()
{
Int n, r, nCr;
Clrscr ();
Printf (“\n enter the value of n :”);
Scanf (“%d”, &n);
Printf (“\n enter the value of r :”);
Scanf (“%d”, &r);
If (r>n)
{
Printf (“\n invalid input……”);
}
Else
{
n
Cr =fact (n)/ (fact(r)*fact (n-r));
Printf (“\n nCr = %d”, nCr);
}
getch ();
}
Int fact (int n)
{
If (n==0)
Return 1;
Else

Kanyakumari B [dept. of CS] Page 10

 DATA STRUCTURE USING C UCST

Return n*fact (n-1);

}

Ex: Program to find GCD using recursive function.

#include <stdio.h>
int hcf (int n1, int n2);
int main ()
{
int n1, n2;
printf (“enter two positive integers:”);
scanf (“%d %d”, &n1, &n2);
printf (“G.C.D of %d and %d is %d.”,n1, n2, hcf(n1, n2));
return 0;
}
int hcf (int n1, int n2)
{
if (n2 !=0)
return hcf(n2, n1 % n2);
else
return n1;
}
Tower of Hanoi:
 Tower of Hanoi is a game introduced by Hanoi.
 Tower of Hanoi is a game playing with 3 stands [stand A, stand B, stand C] and ‘n’
number of different sized disk. Each disk is moved from source (stand A) to destination
(stand C) in the order of decreasing size (smallest on top).

Stand A Stand B Stand C

The problem is to find the number of moves all the disk from source (stand A) to destination
(stand C).
We have to follow 3 rules.
 Only one disk can be moved at a time.
 Only top of disk on any stand can be moved to any other stand.
 The larger disk cannot be placed on smaller disk.

Kanyakumari B [dept. of CS] Page 11

 DATA STRUCTURE USING C UCST

In general the solution requires 2n-1 moves for n-disks.

For 1 disk the minimum number of moves =21-1=1 move
For 2 disk the minimum number of moves =22-2=3 move
For 3 disk the minimum number of moves =23-3=7 move
For 4 disk the minimum number of moves =24-4=15 move

Write a program to working of tower of Hanoi problem for n-disk and print the total
number of moves.
#include<stdio.h>
#include<conio.h>
int tower(int, char, char, char);
int count=0;
void main()
{
int n;
clrscr();
printf("\n Enter number of disks:");
scanf("%d", &n);
tower (n, 'A', 'C','B');
printf("\n Total disk movements : %d", count);
getch();
}
int tower(int n, char source,char dest, char aux)
{
if(n==0)
{
printf("\n No disk movement");
return;
}
else if(n==1)
{
printf("\n Move disk 1 from %c to %c", source, dest);
count++;
return;
}
else
{
tower((n-1),source, aux, dest);

Kanyakumari B [dept. of CS] Page 12

 DATA STRUCTURE USING C UCST

printf("\n Move disk %d from %c to %c",n,source,dest);

count ++
tower((n-1),aux,dest,source);
}
}

Difference between iterative and recursion

Iterative Recursion
In iteration loops are used to execute the set of A function call itself again and again until the
instructions repetitively until the condition is condition is satisfied
false
It is applied to loops It is always applied to functions
Fast in execution slow in execution
Iteration makes the code longer Recursion reduces the size of the code
It uses less memory space compared to It uses more memory space as compared to
recursion iteration

Kanyakumari B [dept. of CS] Page 13

 DATA STRUCTURE USING C UCST

Kanyakumari B [dept. of CS] Page 14