DATA STRUCTURES AND APPLICATIONS (21CS32)

Module 1- Introduction
Introduction: Data Structures,
Classifications (Primitive & Non-
Primitive), Data structure operations
Module 1 Syllabus (Traversing, inserting, deleting, searching,
and sorting). Review of Arrays. Structures:
Array of structures Self-Referential
Structures. Dynamic Memory Allocation
Functions. Representation of Linear Arrays
in Memory, dynamically allocated arrays
and Multidimensional Arrays.
Demonstration of representation of
Polynomials and Sparse Matrices with
arrays.

1.1 Data Structure

 Data is basically a fact or an entity and is used for calculation or manipulation.

 Data structure is a representation of logical relationship existing between
individual elements of data.
 Data Structure is a way of collecting and organizing data in such a way that we
can perform operations on these data in an effective way.
 A data structure is a storage that is used to store and organize data. It is a way of
arranging data on a computer so that it can be accessed and updated efficiently.
 Ex: GPS, Escalators, Queue System, Feeds, Online ticket Booking .

1.2 Classification of data structures

Data structures are generally categorized into two classes:

 Primitive data Structures
 Non-primitive data Structures

Prepared by Saritha Suvarna, Dept of CSE, CEC Page 1

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Primitive Data Structures: Primitive data structures are the basic data structures that
directly operate upon the machine [Link] are the fundamental data types which
are supported by a programming language. Some basic data types are integer, real,
character, and Boolean. The terms ‘data type’, ‘basic data type’, and ‘primitive data type’
are often used interchangeably.
Non-Primitive Data Structures: Non-primitive data structures are those data structures
which are created using primitive data structures. Examples of such data structures
include linked lists, stacks, trees, and graphs.
Based on the structure and arrangement of data, non-primitive data structures is further
classified into
 Linear Data Structure
 Non-linear Data Structure
Linear data Structures : If the elements of a data structure are stored in a linear or
sequential order, then it is a linear data [Link] data structures can be represented
in memory in two different ways.
 One way is to have to a linear relationship between elements by means of
sequential memory locations.
 The other way is to have a linear relationship between elements by means of links.
 Examples include arrays, linked lists, stacks, and queues.

1. Array: Simplest type of data structure is linear array. It is the list of finite
numbers n of similar data elements referenced respectively by a set of n
consecutive numbers. Ex: array of students consisting of six students shown in
fig.

2. A linked list is a very flexible, dynamic data structure in which elements (called
nodes) form a sequential list. A linked list, every node contains the following two
types of data:
 The value of the node or any other data that corresponds to that node
 A pointer or link to the next node in the list

Prepared by Saritha Suvarna, Dept of CSE, CEC Page 2

 DATA STRUCTURES AND APPLICATIONS (21CS32)

The last node in the list contains a NULL pointer to indicate that it is the end or tail of
the list. Since the memory for a node is dynamically allocated when it is added to the
list, the total number of nodes that may be added to a list is limited only by the
amount of memory available. Figure shows a linked list of four nodes shown in fig.

3. A stack is a linear data structure in which insertion and deletion of elements are
done at only one end, which is known as the top of the stack. Stack is called a
last-in, first-out (LIFO) structure because the last element which is added to the
stack is the first element which is deleted from the stack.

4. A queue is a first-in, first-out (FIFO) data structure in which the element that is
inserted first is the first one to be taken out. The elements in a queue are added at
one end called the rear and removed from the other end called the front.

Non-linear data Structures If the elements of a data structure are not stored in a
sequential order, then it is a non-linear data structure.

Prepared by Saritha Suvarna, Dept of CSE, CEC Page 3

 DATA STRUCTURES AND APPLICATIONS (21CS32)

 The relationship of adjacency is not maintained between elements of a non-linear

data structure.
 This structure is mainly used to represent data containing a hierarchical
relationship between elements.
 Examples include trees and graphs.
1. A graph is a non-linear data structure which is a collection of vertices (also
called nodes) and edges that connect these vertices. A graph is often viewed as a
generalization of the tree structure, where instead of a purely parent-to-child
relationship between tree nodes, any kind of complex relationships between the
nodes can exist.

2. A tree is a non-linear data structure which consists of a collection of nodes

arranged in a hierarchical order. One of the nodes is designated as the root node,
and the remaining nodes can be partitioned into disjoint sets such that each set is
a sub-tree of the root.

1.3 Data structure Operations

The data appearing in our data structures are processed by means of certain operations.
Infact the particular data structure that one chooses for a given situation depends largely
on the frequency with which specific operations are performed such as:
1. Creating - Creating a new record with some data.
2. Traversing- It is used to access each data item exactly once so that it can be
processed. This accessing and processing sometimes called as visiting the record.
3. Searching- It is used to find out the location of the data item if it exists in the given
collection of data items.

Prepared by Saritha Suvarna, Dept of CSE, CEC Page 4

 DATA STRUCTURES AND APPLICATIONS (21CS32)

4. Inserting- It is used to add a new data item in the given collection of data items.
5. Deleting- It is used to delete an existing data item from the given collection of data
items.
6. Sorting- It is used to arrange the data items in some order i.e. in ascending or
descending order in case of numerical data and in dictionary order in case of
alphanumeric data.
7. Merging- It is used to combine the data items of two sorted files into single file in the
sorted form.

1.4 Review of Arrays

 An array data structure, or simply an array, is a data structure consisting of a
collection of (mainly of similar data types) elements (values or variables), each
identified by at least one array index or key. An array is stored so that the position
of each element can be computed from its index tuple by a mathematical formula.
 An array is a collection of items stored at contiguous memory locations.

1.4.1 Linear arrays

 Linear arrays are called one dimensional arrays which is referenced by one
subscript. A 1-D array is a collection of similar data elements where each element
is referenced by one subscripts.
 An array must be declared before being used. Declaring an array means specifying
the following:
1. Data_type—the kind of values it can store, for example, int, char, float,
double.
2. Name—to identify the array.
3. Size—the maximum number of values that the array can hold.
 Arrays are declared using the following syntax:

Prepared by Saritha Suvarna, Dept of CSE, CEC Page 5

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Data_type Name[Size];

 The type can be either int, float, double, char, or any other valid data type.
 The number within brackets indicates the size of the array, i.e., the maximum
number of elements that can be stored in the array.
 For example, if we write, int marks[10]; The above statement declares an array
marks that contains 10 elements. In C, the array index starts from zero. This
means that the array marks will contain 10 elements in all. The first element will
be stored in marks[0], second element in marks[1], so on and so forth.
Therefore, the last element, that is the 10th element, will be stored in
marks[9].
1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th
eleme eleme eleme eleme eleme eleme eleme eleme eleme eleme
nt nt nt nt nt nt nt nt nt nt
Mark Mark Mark Mark Mark Mark Mark Mark Mark Mark
s[0] s[1] s[2] s[3] s[4] s[5] s[6] s[7] s[8] s[9]

Calculating the address of array Elements

 Since an array stores all its data elements in consecutive memory locations,
storing just the base address, that is the address of the first element in the array, is
sufficient. The address of other data elements can simply be calculated using the
base address. The formula to perform this calculation is, Address of data element
A[k] = BA(A) + w(k – lower_bound)
or
A[k]= α+ k * sizeof (int) where α =base address

 Here, A is the array, k is the index of the element of which we have to calculate
the address, BA is the base address of the array A, and w is the size of one
element in memory, for example, size of int is 4 .Ex: Given an array int marks[] =
{99,67,78,56,88,90,34,85}, calculate the address of marks[4] if the base address =
1000.
99 67 78 56 88 90 34 85
Marks[0 Marks[1 Marks[2 Marks[3 Marks[4 Marks[5 Marks[6 Marks[7
] ] ] ] ] ] ] ]

Prepared by Saritha Suvarna, Dept of CSE, CEC Page 6

 DATA STRUCTURES AND APPLICATIONS (21CS32)

1000 1002 1004 1006 1008 1010 1012 1014

.
marks[4] = 1000 + 4(4 – 0) = 1000 + 4(4) = 1016
or
marks[4]=1000+4*4=1016

Calculating the length of array Elements

The length of an array is given by the number of elements stored in it. The general
formula to calculate the length of an array is:
Length = upper_bound – lower_bound + 1
Whereupper_bound is the index of the last element and lower_bound is the index of
the first element in the [Link]: in the above diagram,
length of the array = 7-0+1=8

Initialization of one-dimensional array

 Arrays can be initialized at declaration time as:
int age[5]={2,4,34,3,4};
 It is not necessary to define the size of arrays during initialization. Below
instruction justifies it
int age[]={2,4,34,3,4};
 In this case, the compiler determines the size of array by calculating the number of
elements of an array.
 An array can be initialized by inputting values from the keyboard. In this method,
a while/do–while or a for loop is executed to input the value for each element of
the array.

Example: C program calculates the sum of marks of n students using arrays.

#include <stdio.h>
int main(){
int marks[10],i,n,sum=0;

Prepared by Saritha Suvarna, Dept of CSE, CEC Page 7

 DATA STRUCTURES AND APPLICATIONS (21CS32)

printf("Enter number of students: ");

scanf("%d",&n);
for(i=0;i<n;i++){
printf("Enter marks of student%d: ",i+1);
scanf("%d",&marks[i]);
sum+=marks[i];
}
printf("Sum= %d",sum);
return 0;
}

1.4.2 Multi-Dimensional Array

 A multi-dimensional array can be termed as an array of arrays that stores
homogeneous data in tabular form. Data in multidimensional arrays are stored in
row-major order. A three-dimensional (3D) array is an array of arrays of arrays.
In C programming an array can have two, three, or even ten or more dimensions.
The maximum dimensions a C program can have depend on which compiler is
being used. More dimensions in an array means more data is held, but also means
greater difficulty in managing and understanding arrays.
Syntax: data_type array_name[size1][size2]....[sizeN];
 Ex: Two dimensional array: int two_d[10][20];
 Three dimensional array: int three_d[10][20][30];
Example: 2-Dimensional Program to print the array contents
#include <stdio.h>
void main ()
{
int arr[3][3],i,j;
for (i=0;i<3;i++)
{
for (j=0;j<3;j++)

Prepared by Saritha Suvarna, Dept of CSE, CEC Page 8

 DATA STRUCTURES AND APPLICATIONS (21CS32)

{
printf("Enter a[%d][%d]: ",i,j);
scanf("%d",&arr[i][j]);
}
}
printf("\n printing the elements ....\n");
for(i=0;i<3;i++)
{
printf("\n");
for (j=0;j<3;j++)
{
printf("%d\t",arr[i][j]);
}
}
}

1.5 Structures
 Structure is a user defined data type that can hold data items of different data
types.
 The major difference between a structure and an array is that an array can
store only information of same data type.
Syntax
struct{
member1;

Prepared by Saritha Suvarna, Dept of CSE, CEC Page 9

 DATA STRUCTURES AND APPLICATIONS (21CS32)

member2;
…..
member n;
}; structurename

Example
struct {
char name[10];
int age;
float salary;
} person;
 The above example creates a structure and variable name is Person and that has
three fields:
name = a name that is a character array
age = an integer value representing the age of the person
salary = a float value representing the salary of the individual
 Assign values to fields :to assign values to the fields, use. (dot) as the structure
member operator. This operator is used to select a particular member of the
structure
Ex: strcpy([Link],“james”);
[Link] = 10;
[Link] = 35000;
1.5.1 Structure Declaration
 Structure definition with a tag name-Tagged Structure
Syntax:
Struct structure_name
{ member1;
member2;
…
member n;
};

Example:
struct person

Prepared by Saritha Suvarna, Dept of CSE, CEC Page 10

 DATA STRUCTURES AND APPLICATIONS (21CS32)

{
char name[10];
int age;
float salary;
};
 Example1: Program that uses a simple structure to store the student
marks details
#include <stdio.h>
#include <string.h>
struct student
{
char name[20], subject[20];
float percentage;
}s1;
int main()

{
strcpy([Link], "aditi");
strcpy([Link], "Maths");
[Link] = 91.25;
printf(" Name : %s \n", [Link]);
printf(" Subject : %s \n", [Link]);
printf(" Percentage : %f \n", [Link]);
return 0;
}

 Type Defined Structure: We can create our own structure data type by using
typedef statement as:
typedef struct
{
data_type member 1;
Prepared by Saritha Suvarna, Dept of CSE, CEC Page 11
 DATA STRUCTURES AND APPLICATIONS (21CS32)

data_type member 2;
………………………
………………………
data_type member n;
} TypeName;

 typedef is the keyword used at the beginning of the definition and by using
typedef user defined data type can be obtained.
 struct is the keyword which tells structure is defined to the complier
 The members are declared with their data_type
 Type_name is not a variable; it is user defined data_type
Method-1:
typedef struct person{
char name[10];
int age;
float salary;
};
person person1, person2;
Method-2:
typedef struct {
char name[10];
int age;
float salary
} person;
person person1, person2;
 In above example, person is the name of the type and it is a user defined data
type. Declarations of structure variables: person person1, person2;
 This statement declares the variable person1 and person2 are of type person.
 Example2:Program that uses a simple structure to store the student marks
details using typedef structure
#include <stdio.h>
#include <string.h>
typedef struct stud
{

Prepared by Saritha Suvarna, Dept of CSE, CEC Page 12

 DATA STRUCTURES AND APPLICATIONS (21CS32)

char name[20], subject[20];

float percentage;
}students;
int main()

{
students s1;
strcpy([Link], "aditi");
strcpy([Link], "Maths");
[Link] = 91.25;
printf(" Name : %s \n", [Link]);
printf(" Subject : %s \n", [Link]);
printf(" Percentage : %f \n", [Link]);
return 0;
}

Example3:Program that uses a simple structure to store the student details.

#include <stdio.h>
struct student
{
char name[30];
int rollno;
int t_marks;
};
void main()
{
int num,i;
struct student std[10];//statement declares array of structure
printf("enter the number of students:");
scanf("%d",&num);
Prepared by Saritha Suvarna, Dept of CSE, CEC Page 13
 DATA STRUCTURES AND APPLICATIONS (21CS32)

for(i=0;i<num;i++)
{
printf("\n enter the details of student %d",i+1);
printf("\n name:");
scanf("%s",std[i].name);
printf("\n Rollno:");
scanf("%d",&std[i].rollno);
printf("\n totalmarks:");
scanf("%d",&std[i].t_marks);
}
printf("\n the student details are:");
for(i=0;i<num;i++)
printf("\n student %d \n name %s \n Rollno %d\n Total marks
%d\n",i+1,std[i].name,std[i].rollno,std[i].t_marks);
}

1.6 Unions

Prepared by Saritha Suvarna, Dept of CSE, CEC Page 14

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Union is a derived data type, like structure, i.e. collection of elements of different data
types which are grouped together. Each element in a union is called member. Union
allocates one common storage space for all its members, or memory space is shared
between its members. So only one field of union is active at any given time
Syntax:
Method-1:
union tagname
{
Type1 member1;
Type2 member2;
….
};
Method-2:
typedef union
{
Type1 member1;
Type2 member2;
….
};
 Similar to structures, a union is a collection of variables of different data types.
The only difference between a structure and a union is that in case of unions, you
can only store information in one field at any one time.
 To better understand a union, think of it as a chunk of memory that is used to
store variables of different types. When a new value is assigned to a field, the
existing data is replaced with the new data.
 Thus, unions are used to save memory. They are useful for applications that
involve multiple members, where values need not be assigned to all the members
at any one time. Table below shows the difference between structures and unions.

Basis of
Structure Union
comparison
The separate memory location is allotted All members of the 'union'
Basic to each member of the 'structure'. share the same memory
location.
struct struct_name{ union u_name{
Declaration type element1; type element1;
type element2; type element2;

Prepared by Saritha Suvarna, Dept of CSE, CEC Page 15

 DATA STRUCTURES AND APPLICATIONS (21CS32)

…. ….
} variable1, variable2, ...; } variable1, variable2, ...;
Keyword 'struct' 'union'
Size of Structure= sum of size of all the Size of Union=size of the
Size
data members. largest members.
Stores distinct values for all the members. Stores same value for all the
Store Value
members.
A 'structure' stores multiple values, of the A 'union' stores a single value
At a Time
different members, of the 'structure'. at a time for all members.
Way of Provide single way to view each memory Provide multiple way to view
Viewing location. same memory location.

 Example
#include <stdio.h>
#include <string.h>
union student
{
char name[20], subject[20];
float percentage;
}s1;
int main()
{
strcpy([Link], "aditi");
strcpy([Link], "Maths");
[Link] = 91.25;
printf(" Name : %s \n", [Link]);
printf(" Subject : %s \n", [Link]);
printf(" Percentage : %f \n", [Link]);
return 0;
}

1.7 Self- Referential Structure

Prepared by Saritha Suvarna, Dept of CSE, CEC Page 16

 DATA STRUCTURES AND APPLICATIONS (21CS32)

 Self-referential structures are those structures that contain a reference to the data
of its same type. That is, a self-referential structure, in addition to other data,
contains a pointer to a data that is of the same type as that of the structure.
 For example, consider the structure node given below. Here, the structure node
will contain two types of data: a character data and a pointer link. The value of
link is either the address in the memory of an instance of a list or the null pointer.

 Consider these statements which create 3 structures and assign values to their
respective fields:

link item1, item2, item3;

[Link]=’a’;
[Link]=’b’;
[Link]=’c’;
[Link]=[Link]=[Link]=NULL;
 Structures item1, item2 and item3 each contains the data item a, b and c and the
null pointer. We can attach these structures together by replacing the null link
field in item 2 with one that points to item 3 and by replacing the null link field in
item 1 with one that points to item2.
[Link]=&item2;
[Link]=&item3;

Prepared by Saritha Suvarna, Dept of CSE, CEC Page 17

 DATA STRUCTURES AND APPLICATIONS (21CS32)

1.8 Pointers
 In computer science, a pointer is a programming language data type whose value
refers directly to (or "points to") another value stored elsewhere in the computer
memory using its address.
 This is a memory-location which holds the address of another memory-location.
 The 2 most important operators used w.r.t pointer are:
& (address operator)
* (dereferencing/indirection operator)
 Example
#include <stdio.h>
int main ()
{
int var = 20;
int *p;
p = &var;
printf("Address of var variable: %u\n", &var );
printf("Address stored in p variable: %u\n", p );
printf("Value of *p variable: %d\n", *p );
return 0;
}

1.9 Dynamic Memory Management functions

 When we write a program, we may not know how much space we need nor do
you wish to allocate very large space that may never be required.
 To solve this C programming has a concept called heap, for allocating storage at
run time. Dynamic memory allocation is the process of allocating memory at run
time.
 C language offers 4 dynamic memory allocation functions. All functions are
stored in the header file stdlib.h. They are:

Prepared by Saritha Suvarna, Dept of CSE, CEC Page 18

 DATA STRUCTURES AND APPLICATIONS (21CS32)

1. malloc() : The “malloc” or “memory allocation” method in C is used to dynamically

allocate a single large block of memory with the specified size. It returns a pointer of type
void which can be cast into a pointer of any form. The malloc() function reserves a block of
memory of the specified number of [Link] is used to allocate space in memory during the
execution of the program. malloc() does not initialize the memory allocated during execution.
It carries garbage value. It returns null pointer if it couldn‟t able to allocate requested amount
of memory. If memory allocation succeeds, then address of first byte of allocated space is
returned. If memory allocation fails, then NULL is returned.
Syntax: ptr = (cast-type*) malloc(byte-size)

Example: Program to calculate the sum of n numbers entered by the user by using
malloc()

#include <stdio.h>
#include <stdlib.h>
int main() {
int n, i, *list, sum = 0;
printf("Enter number of elements: ");
scanf("%d", &n);
list = (int*) malloc(n * sizeof(int));
// if memory cannot be allocated
if(list == NULL) {
printf("Error! memory not allocated.");
exit(0);
}
printf("Enter elements: ");
for(i = 0; i < n; ++i) {
scanf("%d", list + i);
sum += *(list + i);

Prepared By Saritha Suvarna, Department of CSE,CEC Page 19

 DATA STRUCTURES AND APPLICATIONS (21CS32)

}
printf("Sum = %d", sum);
// deallocating the memory
free(list);
printf("\n Array Contents after deallocation...\n");
for(i=0;i<n;i++)
printf("%d\t\t",*(list+i));
return 0;
}

2. calloc(): “calloc” or “contiguous allocation” method in C is used to dynamically allocate

the specified number of blocks of memory of the specified type. It is very much similar to
malloc() but has two different points and these are:
 It initializes each block with a default value ‘0’.
 It has two parameters or arguments as compare to malloc().

Syntax: ptr = (cast-type*)calloc(n, element-size);

Prepared By Saritha Suvarna, Department of CSE,CEC Page 20

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Example: Program to calculate the sum of n numbers entered by the user

#include <stdio.h>
#include <stdlib.h>
int main() {
int n, i, *list, sum = 0;
printf("Enter number of elements: ");
scanf("%d", &n);
list = (int*) calloc(n, sizeof(int));
// if memory cannot be allocated
if(list == NULL) {
printf("Error! memory not allocated.");
exit(0);
}
printf("Enter elements: ");
for(i = 0; i < n; ++i) {
scanf("%d", list + i);
sum += *(list + i);
}
printf("Sum = %d", sum);
// deallocating the memory
free(list);
printf("\n Array Contents after deallocation...\n");
for(i=0;i<n;i++)
printf("%d\t\t",*(list+i));
return 0;
}

Prepared By Saritha Suvarna, Department of CSE,CEC Page 21

 DATA STRUCTURES AND APPLICATIONS (21CS32)

[Link]()
 “realloc” or “re-allocation” method in C is used to dynamically change the memory
allocation of a previously allocated memory. In other words, if the memory previously
allocated with the help of malloc or calloc is insufficient, realloc can be used
to dynamically re-allocate memory. re-allocation of memory maintains the already
present value and new blocks will be initialized with the default garbage value.
Syntax: ptr = realloc(ptr, newSize);

Example:
#include <stdio.h>
#include <stdlib.h>
int main() {
int *list, i , n1, n2;

Prepared By Saritha Suvarna, Department of CSE,CEC Page 22

 DATA STRUCTURES AND APPLICATIONS (21CS32)

printf("Enter size: ");

scanf("%d", &n1);
list = (int*) malloc(n1 * sizeof(int));
printf("Addresses of previously allocated memory:\n");
for(i = 0; i < n1; ++i)
printf("%u\n",list + i);
printf("\nEnter the new size: ");
scanf("%d", &n2);
// rellocating the memory
list = realloc(list, n2 * sizeof(int));
printf("Addresses of newly allocated memory:\n");
for(i = 0; i < n2; ++i)
printf("%u\n", list + i);
free(list);
return 0;
}

[Link](): free() method in C is used to dynamically de-allocate the memory. The memory
allocated using functions malloc() and calloc() is not de-allocated on their own. Hence the free()
method is used, whenever the dynamic memory allocation takes place. It helps to reduce wastage
of memory by freeing it.

Syntax: free(ptr);

Prepared By Saritha Suvarna, Department of CSE,CEC Page 23

 DATA STRUCTURES AND APPLICATIONS (21CS32)

1.9.1 Difference between malloc() and calloc()

Malloc Calloc
The name malloc stands for memory allocation. The name calloc stands for contiguous allocation.
malloc () doesn‟t initializes the allocated calloc () initializes the allocated memory to zero
memory. It contains garbage values
Since no initialization, time efficiency is More expensive because of zero fillings. But
greater than calloc() convenient than malloc
Syntax Syntax
variable_name=(datatype*)malloc(sizeof(datat variable_name=(datatype*)calloc(n,size);
ype));
Required no. of bytes to be allocated is Takes 2 arguments: nno. of blocks to be
specified as arguments. i.e., size in bytes allocated, sizeno. of bytes in each block

1.10 Dynamically Allocated Array

If the array size is decided during run time, then it is called dynamically allocated array.

1.10.1 1-D Array:

 Consider # define max[100];
 Now 100 locations has been created. If we want more locations, we increase the size of max
in definition and recompile the program. But if we set it very large, there occurs wastage of

Prepared By Saritha Suvarna, Department of CSE,CEC Page 24

 DATA STRUCTURES AND APPLICATIONS (21CS32)

space, or if we make it small, sometimes our data may not fit in that. A good solution for
this is to do run time allocation of array.
 Example:
int *list, n;
printf(“enter the no. of elements to generate”);
scanf(“%d”,&n);
if(n<1)
{ printf(“improper value of n”);
exit(0);
}
list=(int*)malloc(n*sizeof(int));
 Now if n<1, it will come out of the program, else, it will create n*4bytes during run time.i.e,
if n=3, we need to generate 3 memory location for integer no’s (12 bytes

1.10.2 Two-D Array:

 C uses array of array representation to represent a multi-dimensional array. Normally, a
pointer contains the address of a variable. A pointer-to-pointer contains address of another
pointer. When we define a pointer to a pointer, the first pointer contains the address of the
second pointer, which points to the location that contains the actual value as shown below.
 int a; allocates memory for variable ‘a’ where integer can be stored
 int *p1; allocates memory for variable ‘p1’ where address of an integer can
be stored
 int **p2; allocates a memory for variable ‘p2’ where address of pointer can
be stored
 A 2-D array represented as a 1-D array of pointers where each pointer contains address of 1-D
array. ex: int x[3][5]; The figure shows array to array representation, where each of 3 pointers
points to 1-D array consisting of 5 locations

Prepared By Saritha Suvarna, Department of CSE,CEC Page 25

 DATA STRUCTURES AND APPLICATIONS (21CS32)

 Example:
#include <stdio.h>
#include <stdlib.h>
int main() {
int row = 2, col = 3;
int *arr = (int *)malloc(row * col * sizeof(int));
int i, j;
for (i = 0; i < row; i++)
for (j = 0; j < col; j++)
*(arr + i*col + j) = i + j;
printf("The matrix elements are:\n");
for (i = 0; i < row; i++) {
for (j = 0; j < col; j++)
{
printf("%d ", *(arr + i*col + j));
}
printf("\n");
}
free(arr);
return 0;
}

1.11 Polynomials

Prepared By Saritha Suvarna, Department of CSE,CEC Page 26

 DATA STRUCTURES AND APPLICATIONS (21CS32)

 A polynomial is a sum of terms, where each term has a form axe ,Where x=variable,
a=coefficient and e=exponent.
For ex, A(x)=3x20+2x5+4 and B(x)=x4+10x3+3x2+[Link] largest (or leading) exponent of a
polynomial is called its degree.
 Assume that we have 2 polynomials, A(x)= ∑ai x i & B(x)= ∑bi xi ,then A(x)+B(x)= ∑ (ai +
bi) xi i.e the above sum would be S(x)=3x20+2x5+ x4+10x3+3x2 +5
 A polynomial thus may be represented using arrays or linked [Link] any term is not present,
then we assign 0’s in the corresponding coefficient.
 A structure may be defined such that it contains two parts- one is the coefficient and second is
the corresponding degree. Given below is the polynomial representation using structure.
#define max_degree 100
typedef struct
{
float coef[max_degree];
int degree;
}polynomial;
 Array of Structure: Instead of using one array for each polynomial, we use one array to store
all polynomials, which saves space

 Polynomial Addition: Suppose a is one polynomial and b is another polynomial then c=a+b,
where c is the addition of polynomial a and b. inorder to add 2 polynomials, there are
different cases to be verified:
Case 1: Power of Polynomial a is Equal to Power of Polynomial b
Ex: a = 25x6+10x5+7x2+9 b = 15x6+5x4+4x3
lead exponent(a)=6 lead exponent(b)=6
so, lead exponent(a)=lead exponent(b)
sum is,
25x6+10x5+7x2+9

Prepared By Saritha Suvarna, Department of CSE,CEC Page 27

 DATA STRUCTURES AND APPLICATIONS (21CS32)

15x6+5x4+4x3
c=40 x6+………
Case 2:Power of Polynomial a is Greater than Power of Polynomial b
Remaining polynomial is: a =10x5+7x2+9 lead exponent(a)=5
b = 5x4+4x3 lead exponent(b)=4
so, lead exponent(a)>lead exponent(b). so copy lead exponent(a) directly to c
sum is,
10x5+7x2+9
5x4+4x3
c=10 x5+………
Case 3: Power of Polynomial a is Less than Power of Polynomial b
Remaining polynomial is: a =7x2+9 lead exponent(a)=2
b = 5x4+4x3 lead exponent(b)=4
so, lead exponent(a)< lead exponent(b). so copy lead exponent(b) directly to c
sum is,

7x2+9
5x4+4x3
c=5x4+………
so final polynomial is: 40x6+10x5+5x4+4x3 +7x2+9
 Coding:
/* d =a + b, where a, b, and d are polynomials */
d = Zero( )
while (! IsZero(a) && ! IsZero(b)) do {
switch COMPARE (Lead_Exp(a), Lead_Exp(b)) {
case -1: d = Attach(d, Coef (b, Lead_Exp(b)), Lead_Exp(b));
b = Remove(b, Lead_Exp(b));
break;
case 0: sum = Coef (a, Lead_Exp (a)) + Coef ( b, Lead_Exp(b));
if (sum) {
Attach (d, sum, Lead_Exp(a));
a = Remove(a , Lead_Exp(a));
b = Remove(b , Lead_Exp(b));

Prepared By Saritha Suvarna, Department of CSE,CEC Page 28

 DATA STRUCTURES AND APPLICATIONS (21CS32)

}
break;
case 1: d = Attach(d, Coef (a, Lead_Exp(a)), Lead_Exp(a));
a = Remove(a, Lead_Exp(a));
}
}
insert any remaining terms of a or b into d

1.12 Sparse Matrix

 A sparse matrix is a matrix in which most of the elements are zero. By contrast, if most of the
elements are nonzero, then the matrix is considered dense. Sparse data is by nature more easily
compressed and thus require significantly less storage. If we apply the operations using
standard matrix structures and algorithms to sparse matrices, then the execution will slow
down and the matrix will consume large amount of memory
 When a sparse matrix is represented as a 2-dimensional array, we waste space. For ex, if
100*100 matrixes contain only 100 non-zero entries then we waste 9900 out of 10000 memory
spaces. Solution is to Store only the non-zero elements.
 A matrix is typically stored as a two-dimensional array. Each entry in the array represents an
element aij of the matrix and is accessed by the two indices i and j. Conventionally, i is the row
index, numbered from top to bottom, and j is the column index, numbered from left to right.
For an m × n matrix, the amount of memory required to store the matrix in this format is
proportional to m × n. In the case of a sparse matrix, substantial memory requirement
reductions can be realized by storing only the non-zero entries.
 Sparse Matrix Representstion:
A sparse matrix can be represented by using TWO representations:
1. Triplet Representation
2. Linked Representation

 Triplet Representation
#define max 101
typedefstruct
{
int col, row,val;

Prepared By Saritha Suvarna, Department of CSE,CEC Page 29

 DATA STRUCTURES AND APPLICATIONS (21CS32)

}term;
term a[max];
 In this representation, we consider only non-zero values along with their row and column
index values. Each non zero value is a triplet of the form <R,C,Value> where R represents
the row in which the value appears, C represents the column in which the value appears and
Value represents the nonzero value itself. In this representation, the 0th row stores total
rows, total columns and total non-zero values in the matrix. For example, consider a matrix
of size 5 X 6 containing 6 number of non-zero values. This matrix can be represented as
shown in the fig.

 In above example matrix, there are only 6 non-zero elements (those are 9, 8, 4, 2, 5 & 2) and
matrix size is 5 X 6. We represent this matrix as shown in the above image. Here the first
row in the right side table is filled with values 5, 6 & 6 which indicate that it is a sparse
matrix with 5 rows, 6 columns & 6 non-zero values. Second row is filled with 0, 4, & 9
which indicates the value in the matrix at 0th row, 4th column is 9. In the same way the
remaining non-zero values also follows the similar pattern.

 To transpose a matrix we just interchange the rows and columns. This means that each
element a[i][j] in the original matrix becomes b[j][i] in the transpose matrix (Fig 2.11).

We can write the algorithm as:

For each row i
Take element <i, j, val>
transpose it as element <j, i, val>

Prepared By Saritha Suvarna, Department of CSE,CEC Page 30

 DATA STRUCTURES AND APPLICATIONS (21CS32)

 The product of 2 sparse matrixes may no longer be sparse. For example see the Fi

 In linked representation, we use linked list data structure to represent a sparse matrix. In
this linked list, we use two different nodes namely header node and element node. Header
node consists of three fields and element node consists of five fields as shown in the fig.

[Link] and element node representation

Linked list representation of sparse matrix

 Consider the sparse matrix used in the Triplet representation. This sparse matrix can be
represented using linked representation as shown in the below image. In this representation,
H0, H1..., H5 indicates the header nodes which are used to represent indexes. Remaining
nodes are used to represent non-zero elements in the matrix, except the very first node which
is used to represent abstract information of the sparse matrix (i.e., It is a matrix of 5 X 6 with
6 non-zero elements). In this representation, in each row and column, the last node right
field points to its respective header node in the above figure.

Question Bank
1. Define data structures
2. Explain classifications of data structures
3. Explain the different operations of data structures
4. Define structures. Explain different types of structure declaration and initialization
5. Write the difference between structures and union

Prepared By Saritha Suvarna, Department of CSE,CEC Page 31

 DATA STRUCTURES AND APPLICATIONS (21CS32)

6. Explain pointers with an example

7. What are pointer variables? How to declare a pointer variable?
8. Define a pointer. Write a C function to swap two numbers using pointers.
9. Explain self-referential structures
10. Define array and explain with an example
11. What are the different operations of array? Explain
12. Explain multi-dimensional array
13. Explain sparse matrix and its representation
14. Explain with example the functions supported by C to carryout dynamic memory allocation
15. What are the various memory allocation techniques? Explain how memory can be dynamically
allocated using malloc().
16. Write the difference between malloc and calloc
17. Explain how the 2-D array can be created dynamically
18. Develop a structure to represent a solar system. Each planet has 3 fields - name, distance from
sun, no of moons. Write a program to read the data for each planet and store. Also print the
name of the planets that has the highest number of moons.
19. What is a polynomial? What is the degree of a polynomial? Write a function to add two
polynomials.
20. Define structure and unions with example.
21. Write a C program with suitable structure definition and variable declaration to store
information about employee. Consider the following fields: Ename, EID, DOJ(Date, month,
year), and salary (basic, DA, HRA).
22. Write a C program for demonstrating all array operations.
23. For the given sparse matrix and its transpose, give the triplet representation using one
dimensional array.

24. Consider two polynomials A(x)=2x1000+1 and B(x)=x4+10x3+3x2+1 with a diagram show how
these two polynomials are stored using 1D array and also give its C representation.

Prepared By Saritha Suvarna, Department of CSE,CEC Page 32