MODULE-1

INTRODUCTION TO DATA STRUCTURES

INTRODUCTION

“Data Structure is a way of collecting and organizing data in such a way

that the operations on these data can be performed in an effective way”.

“Data structure is a representation of logical relationship existing between

individual elements of data”. In other words, a data structure defines a way of
organizing all data items that considers not only the elements stored but also their
relationship to each other. The term data structure is used to describe the way data
is stored. Data Structures is about rendering data elements in terms of some
relationship, for better organization and storage in computer.

To develop a program of an algorithm we should select an appropriate data

structure for that algorithm. Therefore, data structure is represented as:
Algorithm + Data structure = Program
For example, data can be player's name "Virat" and age 26. Here "Virat" is
of String data type and 26 is of integer data type. This data can be recorded as a
Player record. Now, it is possible to collect and store player’s records in a file or
database as a data structure. For example: "Dhoni" 30, "Gambhir" 31, "Sehwag"
33.
In simple language, “Data Structures are structures programmed to store
ordered data, so that various operations can be performed on it easily. It’s an
arrangement of data in a computer’s memory. Algorithms manipulate the data in
these structures in order to accomplish some task”.

Basic Terminology of Data Organization:

 Data: The term ‘DATA’ simply refers to a value or a set of values. These
values may present anything about something, like it may be roll no of a

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 1

 student, marks, name of an employee, address of person etc.
 Data item: A data item refers to a single unit of value. For eg. roll no of a
student, marks, name of an employee, address of person etc. are data
items. Data items that can be divided into sub items are called group
items (Eg. Address, date, name), where as those who can not be divided in
to sub items are called elementary items (Eg. Roll no, marks, city, pin code
etc.).
 Entity - with similar attributes ( e.g all employees of an organization) form
an entity set.
 Information: Data with given attribute or processed data.
 Field is a single elementary unit of information representing an attribute of an
entity.
 Record is the collection of field values of a given entity.
 File is the collection of records of the entities in a given entity set.
 Each record in a file may contain many field items but the value in a certain
field may uniquely determine the record in the file. Such a field K is called a
primary key, and the values K1, K2, K3… in such a field are called keys or
key values.
 Records can be classified as fixed-length records or variable-length
records. In fixed length records, all the records contain the same data items
with the same amount of space assigned to each data item .In variable length
records , file records may contain different lengths.
EXAMPLE:
Attributes: Name Age Sex Roll Number Branch
Values: A 17 M 109cs0132 CSE
B 18 M 109ee1234 ISE

Here, it is an example of student details where STUDENT is the

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 2

 given entity. Then name, age, sex, roll number, branch are attributes and
their values are properties (A, 17, M, 109cs0132, CSE). Collection of
student details is student entity set and Roll number is the primary key
which uniquely indicates each student details.

CLASSIFICATION OF DATA STRUCTURES

The logical or mathematical model of a particular organization of data is

called a Data Structure.

Anything that can store data can be called as a data structure, hence
Integer, Float, Boolean, Char etc, all are data structures. They are known as
Primitive Data Structures and some complex Data Structures, which are used
to store large and connected data. They are called Non-primitive Data Structures.
Examples:
 Array
 Stack
 Queue
 Linked List
 Tree
 Graph

All these data structures allow us to perform different operations on data.

The s e l e c t i o n of these data structures is based on which type of operation is
required.

Data structures can be classified as

 Primitive data structure

 Non-Primitive data structure
 Linear data structure
 Nonlinear data structure

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 3

 Figure 1: Classification of data structure

Figure 1 gives the complete classification of the data structure.

Primitive Data Structure: A primitive data structure used to represent the

standard data types of any one of the computer languages. Variables, pointers, etc.
are examples of primitive data structures. Simple data structure can be constructed
with the help of primitive data structure.

Non-Primitive Data structure: Non-Primitive data structure can be

constructed with the help of any one of the primitive data structure and it is having
a specific functionality. It can be designed by user. Arrays, Structure, Union, linked
list, Stacks, Queue, trees, graphs etc are example for non primitive data structures.

It can be classified as

1) Linear data structure

2) Non-linear data structure

(Refer class notes for detailed explanation)

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 4

Linear Data Structures:
Linear data structures can be constructed as a continuous arrangement of
data elements in the memory. In linear data structure the elements are stored in
sequential order. In the linear Data Structures the relationship of adjacency is
maintained between the Data elements .It can be represented by using array data
type or linked list. The linear data structures are:

 Array: Array is a collection of data of same data type stored in consecutive

memory location and is referred by common name
 Stack: A stack is a Last-In-First-Out linear data structure in which insertion
and deletion takes place at only one end called the top of the stack.
 Queue: A Queue is a First in First-Out Linear data structure in which
insertions takes place one end called the rear and the deletions takes place at
one end called the Front.
 Linked list: Linked list is a collection of data of same data type but the data
items need not be stored in consecutive memory locations.

Non Linear Data Structures

Non-linear data structure can be constructed as a collection of randomly
distributed set of data item joined together by using a special pointer (tag). In non-
linear Data structure the relationship of adjacency is not maintained between the
Data items. Elements are stored based on the hierarchical relationship among the
data.

The following are some of the Non-Linear data structure

 Trees: Trees are used to represent data that has some hierarchical
relationship among the data elements.(as shown in figure 3)

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 5

 Figure 3: Trees
 Graph: Graph is used to represent data that has relationship between pair of
elements not necessarily hierarchical in nature. For example electrical and
communication networks, airline routes, flow chart, graphs for planning
projects.(as shown in figure 4)

Figure 4: Graph
DATA STRUCTURE OPERATIONS
The data in the data structures are processed by certain operations. The
particular data structure chosen largely depends on the frequency of the
operation that needs to be performed on the data structure.

• Traversing
• Searching
• Insertion
• Deletion
• Sorting
• Merging

(1) Traversing: Accessing each record exactly once so that certain items in
the record may be processed.

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 6

(2) Searching: Finding the location of a particular record with a given key value, or
finding the location of all records which satisfy one or more conditions.
(3) Inserting: Adding a new record to the structure.
(4) Deleting: Removing the record from the structure.
(5) Sorting: Managing the data or record in some logical order (Ascending or
descending order).
(6) Merging: Combining the record in two different sorted files into a single sorted
file.

(Refer First Lab Program – Array Operations)

STRUCTURES DEFINITION
“Structure is a collection of data items of same or dissimilar data type. Each
data item is identified by its name and type. (Or) A Structure is a user defined data
type that can store related information together. (Or) A structure is a collection of
different data items / heterogeneous data items under a single name.” The variable
within a structure are of different data types and each has a name that is used to
select it from the structure.

C arrays allow you to define type of variables that can hold several data items
of the same kind but structure is another user defined data type available in C
programming, which allows you to combine data items of different kinds. Structures
are used to represent a record, Suppose, track of books are kept in a library are
recorded then it is required to track the following attributes about each book:
• Title
• Author
• Subject
• Book ID

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 7

STRUCTURE DECLARATION
It is declared using a keyword struct followed by the name of the structure.
The variables of the structure are declared within the structure.
Example:
Struct struct-name
{
data_type1 var-name1;
data_type2 var-name2;
.. ..
data_typen var_namen;
};

STRUCTURE INITIALIZATION
Assigning values to the data members of the structure is called initializing of
structure.
Syntax:
struct struct_name
{
data _type member_name1;
data _type member_name2;
} struct_var={constant1,constant2};

Accessing the Members of a structure

A structure member variable is generally accessed using a ‘.’ dot operator.
Syntax: strcut_var. member_name;
The dot operator is used to select a particular member of the structure. To assign
value to the individual Data members of the structure variable stud, it is written as,
stud.roll=01;
stud.name=”Rahul”;

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 8

To input values for data members of the structure variable stud, can be written as,
scanf(“%d”,&stud.roll);
scanf(‘’%s”,&stud.name);
To print the values of structure variable stud, can be written as:
printf(“%s”,stud.roll);
printf(“%f”,stud.name);

Example for structure:

struct
{
char name[10];
int age;
float salary;
}person;
Here struct is a keyword.
This example creates a variable whose name is person and that has three fields
 A name that is a character array
 An integer value Age
 A float value salary
The . (Dot operator) is used as the structure member operator to select a
particular member of the structure.
Example strcpy(person.name,”james”);
person.age=20;
person.salary=40000;

Program to create a struct person , initializes its data member and print their
values
#include<stdio.h>
#include<conio.h>

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 9

void main()
{
struct person{
char name[10];
int age;
float salary;
};
struct person p1;
clrscr();
strcpy(p1.name,"james");
p1.age=10;
p1.salary=35000;
printf("\n name=%s age=%d salary=%f",p1.name,p1.age,p1.salary);
getch();
}

ARRAY OF STRUCTURE
An array of structure can also be declared. Each element of the array
representing a structure variable.Example : struct employee emp[5];
The above code define an array emp of size 5 elements. Each element of array emp
is of type employee
#include<stdio.h>
#include<conio.h>
struct employee
{
char ename[10];
int sal;
};
struct employee emp[5];
int i,j;
void ask()
{

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 10

 for(i=0;i<3;i++)
{
printf("\nEnter %dst employee record\n",i+1);
printf("\nEmployee name\t");
scanf("%s",emp[i].ename);
printf("\nEnter employee salary\t");
scanf("%d",&emp[i].sal);
}
printf("\nDisplaying Employee record\n");
for(i=0;i<3;i++)
{
printf("\nEmployee name is %s",emp[i].ename);
printf("\nSlary is %d",emp[i].sal);
}
}
void main()
{
clrscr();
ask();
getch();
}

Type definitions and structures

It is possible to create our own data types (user defined)by using typedef
statement as below
typedef struct
{
char name[10];
int age;

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 11

 } humanbeing;

Here humanbeing is the name of the type defined by structure definition and we
may follow this definition with declarations of variables such as humanbeing
person1, person2;
 Structures cannot be directly checked for equality or nor equality. i.e. directly
using person1==person2 is not allowed. If each individual data member is
checked for equality then the entire structure can be checked for equality.

Program to check equality to structure variables.

#include<stdio.h>
#include<conio.h>
#define FALSE 0
#define TRUE 1
typedef struct
{
char name[10];
int age;
float salary;
}humanbeing;
int humansEqual(humanbeing p1,humanbeing p2)
{
if(strcmp(p1.name,p2.name))
return FALSE;
if(p1.age!=p2.age)
return FALSE;
if(p1.salary!=p2.salary)
return FALSE;
else
return TRUE;
}
void main()
{
humanbeing p1,p2;

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 12

 clrscr();
strcpy(p1.name,"hiiiii");
p1.age=12;
p1.salary=12000;
strcpy(p2.name,"hi");
p2.age=12;
p2.salary=12000;
if(humansEqual(p1,p2))
printf("\n persons are same ");
else
printf("\n persons are not same");
getch();
}

POINTERS TO STRUCTURES
Pointer to a structure is a variable that holds the address of a structure. The
syntax to declare pointer to a structure can be given as:
strcut struct_name *ptr;
eg: struct stud *ptr_stud;
To assign address of stud to the pointer using address operator(&) we would write
ptr_stud=&stud;
To access the members of the structure (->) operator is used.
for example
Ptr_stud->name=Raj;

NESTED STRUCTURE

It is possible to embed a structure within a structure. “The structure that

contains another structure variable as its members is called a nested
structure or a structure within a structure is called nested structure.”
The structure should be declared separately and then be grouped into high
level structure. The data members of the nested structures can be accessed using (.)

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 13

Dot operator. Syntax to followed while accessing the data members of inner
structure in nested structure with dot operator is outer most structure variable.
Inner most structure variable. Inner data member ; and Syntax to followed
while accessing the data members of outer structure in nested structure with dot
operator is outer most structure variable .outer data member ;
Example :
typedef struct
{
int month;
int day;
int year;
}date;

typedef struct
{
char name[10];
int age;
salary;
date dob;
}humanbeing;
If humanbeing person1 and person2 declares person1 and person2 variables
of type humanbeing. Then consider a person born on feb 11, 1944, can have the
values for the date struct set as:
person1.dob.month=2;
person1.dob.day=11;
person1.dob.year=1944;

Similarly for considering person2, his dob is 3rd December 1956 then

person2.dob.month=12;
person2.dob.day=3;
person2.dob.year=1956;

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 14

Program for illustration of nested structures
#include<stdio.h>
#include<conio.h>
void main()
{
typedef struct
{
int month;
int day;
int year;
}date;

typedef struct
{
char name[10];
int age;
salary;
date dob;
}humanbeing;
humanbeing person1;
strcpy(person1.name,"james");
person1.age=10;
person1.salary=35000;
person1.dob.month=2;
person1.dob.day=11;
person1.dob.year=1944;
printf(“\n details of the person”);
printf("\n name=%s age=%d salary=%f dob=%d-%d-%d",person1.name,
person1.age,person1.salary,Person1.dob.day,Person1.dob.month,Person1.do
b.year);
getch();
}

UNIONS

Union is a collection of variables of different data types. Union information

can only be stored in one field at any one time.

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 15

 Definition: A union is a special data type available in C that enables you
to store different data types in the same memory location. union can define a
with many members, but only one member can contain a value at any given time.
Unions provide an efficient way of using the same memory location for multi-
purpose.

Declaring Union
union union-name
{
data_type1 var-name1;
data_type2 var-name2;
.. ..
data_typen var_namen;

};
Example:
Union data
{
char a;
int x;
float f;
}mydata;

The union tag is optional and each member definition is a normal variable
definition, such as int i; or float f; or any other valid variable definition.
At the end of the union's definition, before the final semicolon, you can specify
one or more union variables but it is optional. The memory occupied by a union will
be large enough to hold the largest member of the union. For example, in above
example Data type will occupy 4 bytes of memory space because this is the
maximum space which can be occupied by float data.

Accessing a Member of a Union

#include <stdio.h>
#include <string.h>
union Data
{
int i;

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 16

 float f;
char str[20];
};
int main( )
{
union Data data;
data.i = 10;
data.f = 220.5;
strcpy( data.str, "C Programming");
printf( "data.i : %d\n", data.i);
printf( "data.f : %f\n", data.f);
printf( "data.str : %s\n", data.str); return 0;
}
Dot operator can be used to access a member of the union. The member
access operator is coded as a period between the union variable name and the union
member that we wish to access.

Program to illustrate union.

#include<stdio.h>
#include<conio.h>
typedef struct
{
enum tagfield {female,male} sex;
union
{
int child;
int beard;
}u;
}sextype;
typedef struct
{
int m,d,y;
}date;
typedef struct
{
char name[10];
int age;
DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 17
 float salary;
date dob;
sextype sexinfo;
}humanbeing;
void main()
{
humanbeing p1;
p1.dob.m=2;
p1.dob.d=11;
p1.dob.y=1994;
p1.sexinfo.sex=female;
p1.sexinfo.u.beard=4;
printf("year=%d/%d/%d",p1.dob.m,p1.dob.d,p1.dob.y);
printf("\n sex=%d b=%d",p1.sexinfo.sex,p1.sexinfo.u.beard);
getch();
}

SELF REFERENTIAL STRUCTURES

“Self –referential structures are those structures that contain a reference to

data of its same type as that of structure. i.e one or more of the components of the
structure will be a pointer to itself.”

Example 1
struct node
{
int val;
struct node*next;
};
Example 2:
typedef struct
{
Char data;
Struct list * link;
}list;

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 18

In this example each instance of the structure list have two components data and
link.
Data is a single character, while link is a pointer to a list structure.
The value of link is either the address in memory of an instance of list or NULL
pointer.

Program to illustrate self-referential structures

#include <stdio.h>
#include <conio.h>
typedef struct
{
char data;
struct list *link;
}list;
void main()
{
list l1,l2,l3;
l1.data='a';
l2.data='b';
l3.data='c';
l1.link=&l1;
l2.link=&l2;
l3.link=&l3;
printf("\n data values of l1=%d,l2=%d,l3=%d",l1.data,l2.data,l3.data);
printf("\n link of l1,l2,l3=%d %d %d",l1.link,l2.link,l3.link);
getch();
}
Difference between structure and union

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 19

POINTERS
Pointers are variables that hold address of another variable of same data
type. Pointers are one of the most distinct and exciting features of C language. It
provides power and flexibility to the language. Although pointer may appear little
confusing and complicated in the beginning, but trust me its a powerful tool and
handy to use once its mastered.
Benefit of using pointers
 Pointers are more efficient in handling Array and Structure.
 Pointer allows references to function and thereby helps in passing of function
as arguments to other function.
 It reduces length and the program execution time.
 It allows C to support dynamic memory management.
Concept of Pointer
Whenever a variable is declared, system will allocate a location to that
variable in the memory, to hold value. This location will have its own address
DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 20
number. Let us assume that system has allocated memory location 80F for a variable
a. int a = 10 ;

The value 10 can be accessed by either using the variable name a or the
address 80F.Since the memory addresses are simply numbers they can be assigned
to some other variable. The variable that holds memory address are called pointer
variables. A pointer variable is therefore nothing but a variable that contains an
address, which is a location of another variable. Value of pointer variable will be
stored in another memory location.

Figure 5: Pointer variable

Declaring a pointer variable

General syntax of pointer declaration is, data-type *pointer_name;
Data type of pointer must be same as the variable, which the pointer is
pointing. void type pointer works with all data types, but isn't used oftenly.

Initialization of Pointer variable

Pointer Initialization is the process of assigning address of a variable to
pointer variable. Pointer variable contains address of variable of same data type. In

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 21

C language address operator & is used to determine the address of a variable. The
& (immediately preceding a variable name) returns the address of the variable
associated with it.
int a = 10 ;
int *ptr ; //pointer declaration
ptr = &a ; //pointer initialization
or,
int *ptr = &a ; //initialization and declaration together
Pointer variable always points to same type of data.
float a;
int *ptr;
ptr = &a;

Dereferencing of Pointer
Once a pointer has been assigned the address of a variable. To access the
value of variable, pointer is dereferenced, using the indirection operator * .
int a,*p;
a = 10;
p = &a;
printf("%d",*p); //this will print the value of a.
printf("%d",*&a); //this will also print the value of a.
printf("%u",&a); //this will print the address of a.
printf("%u",p); //this will also print the address of a.
printf("%u",&p); //this will also print the address of p.

Pointer and Arrays

When an array is declared, compiler allocates sufficient amount of memory to
contain all the elements of the array. Base address which gives location of the first
element is also allocated by the compiler.

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 22

Suppose we declare an array arr,
int arr[5]={ 1, 2, 3, 4, 5 };
Assuming that the base address of arr is 1000 and each integer requires two byte,
the five element will be stored as follows in figure 6

Figure 6: Array Representation

Here variable arr will give the base address, which is a constant pointer pointing to
the element, arr[0]. Therefore arr is containing the address of arr[0] i.e 1000.
We can declare a pointer of type int to point to the array arr.
int *p;
p = arr;
or p = &arr[0]; //both the statements are equivalent.
Now we can access every element of array arr using p++ to move from one element
to another. NOTE : You cannot decrement a pointer once incremented. p-- won't
work.

Pointer to Array (Dynamic Memory Allocation – 1D array Program can be referred)

As studied above, we can use a pointer to point to an Array, and then we can use
that pointer to access the array. Lets have an example,
int i;
int a[5] = {1, 2, 3, 4, 5};
int *p = a; // same as int*p = &a[0]
for (i=0; i<5; i++)
{

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 23

printf("%d", *p);
p++;
}
In the above program, the pointer *p will print all the values stored in the array one
by one.
We can also use the Base address (a in above case) to act as pointer and print all the
values.

Pointers to multidimensional array (Dynamic Memory Allocation – 2D array

Program can be referred)
A multidimensional array is of form, a[i][j] . Lets see how we can make a
pointer point to such an array. As we know now, name of the array gives its base
address. In a[i][j] , a will give the base address of this array, even a+0+0 will also
give the base address, that is the address of a[0][0] element. Here is the generalized
form for using pointer with multidimensional arrays.
*(*(ptr + i) + j)
is same as
a[i][j]

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 24

Pointer and Character strings
Pointer can also be used to create strings. Pointer variables of char type are
treated as string.
char *str = "Hello";
This creates a string and stores its address in the pointer variable str. The pointer
str now points to the first character of the string "Hello". Another important thing to
note that string created using char pointer can be assigned a value at runtime.
char *str;
str = "hello"; //this is Legal
The content of the string can be printed using printf() and puts() .
printf("%s", str);
puts(str);
Notice that str is pointer to the string, it is also name of the string. Therefore we do
not need to use indirection operator *.

Array of Pointers
Array of pointers can also be declared. Pointers are very helpful in handling
character array with rows of varying length.
char *name[3]={
"Adam",
"chris",
"Deniel"
};
//Now see same array without using pointer
char name[3][20]= {
"Adam", "chris",
"Deniel"
};

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 25

 Figure 7: Array of pointers
The figure 7 shows the array of pointers used to store the character arrays.
The pointers hold the address of each of the string. Each pointer will point to the
first character of their respective strings.

DYNAMIC MEMORY ALLOCATION

The memory allocation which is used till now was static memory allocation.
So the memory that could be used by the program was fixed. So it is not possible to
allocate or de allocate memory during the execution of the program. It is not
possible to predict how much memory will be needed by the program at run time.
For example assume an array with size 20 elements is declared, which is
fixed. So if at run time values to be stored in array are less than 20 then wastage of
memory occur or our program may fail if more than 20 values are to be stored in to
that array. To solve the above problems and allocate memory during runtime
dynamic memory allocation is used.
The process of allocating memory during the runtime is called as DMA
(dynamic memoey allocation) and memory gets allotted in heap area of program
stack.

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 26

The following functions are used in dynamic memory allocation and are defined in
<stdlib.h>
1. malloc()
Declaration: void *malloc(size_t size);
This function is used to allocate memory dynamically. The argument size
specifies the number of bytes to be allocated. On success, malloc() returns a pointer
to the first byte of allocated memory. The returned pointer is of type void, which can
be type cast to appropriate type of pointer. The memory allocated by malloc()
contains garbage value .
2. calloc()
Declaration: void *calloc(size_t n,size_t size);
This function is used to allocate multiple blocks of memory. The first
argument specifies the number of blocks and the second one specifies the size of
each block. The memory allocated by calloc() is initialized to zero.
3. realloc()
Declaration: void *realloc(void *ptr,size_t newsize);
The function realloc() is used to change the size of the memory block. It alters
the size of the memory block without losing the old data. This function takes two
arguments, first is a pointer to the block of memory that was previously allocated by
malloc() or calloc() and second one is the new size for that block.
4. free();
Declaration: void free(void *p);
This function is used to release the memory space allocated dynamically. The
memory released by free() is made available to the heap again and can be used for
some other purpose. We should not try to free any memory location that was not
allocated by malloc(), calloc() or realloc().
(Refer class notes)

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 27

The following program illustrates Dynamic memory allocation.
Void main()
{
int *p,n,i;
printf(“Enter the number of integers to be entered”);
scanf(“%d”,&n);
p=(int *)malloc(n*sizeof(int)); /* This is same as “(int
*)calloc(n,sizeof(int))”*/
/* If we write “(int *)malloc(sizeof(int))” then only 2 byte of memory will be
allocated dynamically*/
if(p==NULL)
{
printf(“Memory is not available”); exit(1);
}
for(i=0;i<n;i++)
{
printf(“Enter an integer”);
scanf(“%d”,p+i);
}
for(i=0;i<n;i++)
printf(”%d\t”,*(p+i));
}

DYNAMICALLY ALLOCATED ARRAYS

Array can be dynamically allotted using malloc(), calloc() or realloc()
functions, similarly the allotted memory can be freed after the use of array using
free() function.
One dimensional array
When large programs are written, it is difficult to determine how large array
to use. So, solution to this problem is to defer this decision to runtime and allocate
the required array size. The advantage of dynamic array is that the memory for the
array of any desired size can be allotted. There is no need to declare a fixed size
array.

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 28

Example program for illustration of use of dynamic array
#include<stdio.h>
#include<stdlib.h>
Void main()
{
Int i,n;
Int *ptr;
Printf(“\n enter the number of elements\n”);
Scanf(“%d”,&n);
Ptr=(int*)malloc(sizeof(int)*n);
If(ptr==NULL)
{
Printf(“\n insufficient memory”);
Return;
}
Printf(“\n enter the n elements”);
For(i=0;<n;i++)
Scanf(“%d”,(ptr+i));
Printf(“the given array elements are \n”);
For(i=0;i<n;i++)
Printf(“%d”,*(ptr+i));
}

Two dimensional array

A two dimensional array is represented as a one dimensional array in which
each element is itself a one dimensional array.
Int x[3][5];
Here, actually a one dimensional array x is created whose length is 3 and each
element of x is a one dimensional array whose length is 5.
C finds the element x[i][j] by first accessing the point in x[i].this pointer gives the
address in memory of the zeroth element of row I of the array. Then by adding
j*sizeof(int) to this pointer , the address of the [j]th elemnt of row i is determined.
Example program for allocating memory dynamically for 2D array (Refer class
notes)
#include<stdio.h>
#include<conio.h>
#include<alloc.h>

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 29

Void main()
{
Int **a;
Int p,q;
Int **make2darray();
Printf(“\n enter the no of rows”);
Scanf(“%d”,&p);
Printf(“\n enter the no of cols”);
Scanf(“%d”,&q);
a=make2darray(p,q);
printf(“successful memory creation address is”,a);
getch();
}
int **make2darray(int rows,int cols)
{
Int **x,i;
X=malloc(rows*sizeof(*x));
For(i=0;i<rows;i++)
X[i]=malloc(cols*sizeof(**x));
Return x;
}

C provides two additional Dynamic memory allocation functions calloc and

realloc . the calloc function allocates a user specified amount of memory and
initializes the allocated memory to 0 , a pointer to the start of the allocated memoey
is returned. In case ther is insufficient memory to make the allocation , the returned
value is NULL.so, the example statements could be used to define a one dimensional
array of integers with the capacity of this array is n and x ranges from 0 to n-1 with
initially 0 value.
Int *x;
X=calloc(n,sizeof(int));

DATA STRUCTURES-1(22SCS032) SEMESTER:3 Page 30