Module 1: Introduction to Data Structures and Algorithms (21CS32) 1

Module 1
Introduction to Data Structures and Algorithms
1.1 BASIC TERMINOLOGY; ELEMENTARY DATA ORGANIZATION

➢ Data are simply the values or set of values. A data item refers to a single unit of values. Data
items that are not able to divide into sub-items are called Elementary items.
Example: r = {8050262021, 9844329766} is a set of phone numbers.
Here ‘8050262021’ is a singe unit of values i.e. data item.
➢ Entity: An entity is something that has certain attributes or properties which may be assigned
values. The values may be either numeric or non-numeric.
➢ 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.
Example: Entity – [Link] File name
Names Age Sex USN
Ramya 34 F 1RN20AI010
Sairam 23 M 1RN20CS005

Record
Field

Records may also be classified according to length. A file can have 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.

1.2 DATA STRUCTURES

The above organization of data into fields, records and files may not be enough to maintain and
efficiently process on certain collections of data. For this reason, data are organized into more
systematic structures. Data may be organized in many different ways; the logical or mathematical
model of a particular organization of data is called data structure.
The study of such data structures includes following three steps:
(1) Logical or mathematical description of the structure.
(2) Implementation of the structure on a computer
(3) Quantitative analysis of the structure, which includes determining the amount of memory
needed to store the structure and the time required to process the structure.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 2

1.2.1 Different Categories of Data Structures

Data structures are generally classified into

• Primitive data Structures
• Non-primitive data Structures

➢ Primitive data structures are the fundamental data types which are supported by a
programming language. Basic data types such as integer, real, character and Boolean are
known as Primitive data Structures. These data types consists of characters that cannot be
divided and hence they also called simple data types.

➢ Non-primitive data structures are those data structures which are created using primitive data
structures. Examples of non-primitive data structures is the processing of complex numbers,
linked lists, stacks, trees, and graphs. Based on the structure and arrangement of data, non-
primitive data structures is further classified into
i. Linear Data Structure
ii. Non-linear Data Structure

◆ Linear Data Structure: A data structure is said to be linear if its elements form a sequence
or a linear list. There are basically two ways of representing such linear structure in memory.
➢ One way is to have the linear relationships between the elements represented by
means of sequential memory location. These linear structures are called arrays.

➢ The other way is to have the linear relationship between the elements represented
by means of pointers or links. These linear structures are called linked lists.
Examples of Linear Data Structures are : Arrays, Linked Lists, Stack and Queues. The
following section briefly explains them.
✓ Arrays: The simplest type of data structure is a linear (or one dimensional) array. An array is
used to store a collection of data, it is often more useful to think of an array as a collection of
variables of the same type. An array holds several values of the same kind. A list of a finite

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 3

number n of similar data referenced respectively by a set of n consecutive numbers, usually

0,1, 2, 3 . . . . . . . n-1. if A is chosen the name for the array, then the elements of A are denoted
by subscript notation a0, a1, a2, a3….. an-1.

0 Satish
1 Jyothi
2 Sandeep

A linear array STUDENT consisting of the names of three students is pictured in below figure.
Here STUDENT [1] denotes Jyothi, STUDENT [2] denotes Sandeep, and so on. Linear arrays are
called one-dimensional arrays because each element in such an array is referenced by one subscript.
A two-dimensional array is a collection of similar data elements where each element is referenced
by two subscripts.

✓ Linked Lists: will be introduced by means of an example. Another way of storing the date
shown in the figure 1.x is to have a separate array for the sales people.

✓ Stack: A stack, also called a fast-in first-out (LIFO) system,

is a linear list in which insertions and deletions can take place only
at one end, called the top. This structure is similar in its operation
to a stack of dishes on a spring system as shown in fig. Note that
new 4 dishes are inserted only at the top of the stack and dishes
can be deleted only from the top of the Stack.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 4

✓ Queue: A queue, also called a first-in first-

out (FIFO) system, is a linear list in which
deletions can take place only at one end of
the list, the "from'' of the list, and insertions
can take place only at the other end of the list, the “rear” of the list. This structure operates
in much the same way as a line of people waiting at a bus stop, as pictured in Fig. the first
person in line is the first person to board the bus. Another analogy is with automobiles
waiting to pass through an intersection the first car in line is the first car through.
◆ Non-linear Data Structure: A data structure is said to be non-linear if the data are not arranged
in sequence or a linear. The insertion and deletion of data is not possible in linear fashion. This
structure is mainly used to represent data containing a hierarchical relationship between
elements. Trees and graphs are the examples of non-linear data structure.
Trees: Data frequently contain a hierarchical relationship between various elements. The data
structure which reflects this relationship is called a rooted tree graph or a tree. Some of the basic
properties of tree are explained by means of examples.

Example 1: Record Structure

Although a file may be maintained by means of one or more arrays a record, where one indicates
both the group items and the elementary items, can best be described by means of a tree structure.
For example, an employee personnel record may contain the following data items:
Social Security Number, Name, Address, Age, Salary, Dependents
However, Name may be a group item with the sub-items Last, First and MI (middle initial). Also
Address may be a group item with the subitems Street address and Area address, where Area itself
may be a group item having subitems City, State and ZIP code number. This hierarchical structure
is pictured below:

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 5

3. Graph: Data sometimes contain a relationship between pairs of elements which is not
necessarily hierarchical in nature. For example, suppose an airline flies only between the
cities connected by lines in Fig. The data structure which reflects this type of relationship
is called a graph.

1.2.2 DATA STRUCTURE OPERATIONS

The data appearing in data structures are processed by means of certain operations.
The following four operations play a major role in this text:
a) Traversing: accessing each record/node exactly once so that certain items in the record
may be processed. (This accessing and processing is sometimes called “visiting” the
record.)

b) Searching: Finding the location of the desired node with a given key value, or finding the
locations of all such nodes which satisfy one or more conditions.

c) Inserting: Adding a new node/record to the structure.

d) Deleting: Removing a node/record from the structure.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 6

The following two operations, which are used in special situations:

a) Sorting: Arranging the records in some logical order (e.g., alphabetically according to
some NAME key, or in numerical order according to some NUMBER key, such as social
security number or account number)

b) Merging: Combining the records in two different sorted files into a single sorted file.

1.3 REVIEW OF ARRAYS, STRUCTURES, SELF-REFERENTIAL STRUCTURES AND UNIONS

A variable is defined as a meaningful name given to a data storage location in the computer
memory. When using a variable, we actually refer to the address of the memory where the data is
stored. C language supports two basic kinds of variables.

1.3.1 Array
Array is a container which can hold fix number of items and these items should be of same type.
Most of the data structures make use of array to implement their algorithms. Following are
important terms to understand the concepts of Array.
• An Array is defined as, an ordered set of similar data items. All the data items of
an array are stored in consecutive memory locations.
• Arrays are of two types:
o One dimension Array
o Two / Multi-dimension Array
• The data items of an array are of same type and each data items can be accessed
using the same name but different index value.
• An array is a set of pairs, <index, value >, such that each index has a value associated
with it. It can be called as corresponding or a mapping.
Example:
<index, value>
< 0 , 25 > list[0]=25
< 1 , 15 > list[1]=15
< 2 , 20 > list[2]=20
< 3 , 17 > list[3]=17
< 4 , 35 > list[4]=35

Here, list is the name of array. By using, list [0] to list [4] the data items in list can be
accessed.

Array declaration: A one dimensional array in C is declared by adding brackets to the

name of a variable. Before using the array in the program, it must be declared.
Syntax: data_type array_name[size];

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 7

Where,
data_type represents the type of elements present in the array.
array_name represents the name of the array.
Size represents the number of elements that can be stored in the array.

Example: int age[100]; float sal[15]; char grade[20];

➢ Here age is an integer type array, which can store 100 elements of integer type.
➢ The array sal is floating type array of size 15, can hold float values.
➢ Grade is a character type array which holds 20 characters.

Initialize arrays at the time of declaration.

Syntax: data_type array_name[size] = {value1, value2,……..valueN};
Where, value1, value2, valueN are the constant values known as initializers, which are
assigned to the array elements one after another.
➢ Example: int marks[5]={10,2,0,23,4};
The values of the array elements after this initialization are:
marks[0]=10, marks[1]=2, marks[2]=0, marks[3]=23, marks[4]=4;

Representation of One-Dimensional Array in Memory

We have already discussed that whenever an array is declared in the program, contiguous memory
to it elements are allocated. Initial address of the array – i.e. address of the first element of the array
is called base address of the array.

Each element will occupy the memory space required to accommodate the values for its type, i.e.;
depending on elements datatype, 1, 4 or 8 bytes of memory is allocated for each element. Next
successive memory address is allocated to the next element in the array. This process of allocating
memory goes on till the number of elements in the array gets over.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 8

The elements of a one-dimensional array are stored at consecutive locations in memory. Each of
the locations is accessed with the help of array index identifier to retrieve the corresponding
element. Consider the following integer array:
Consider the following integer array:
arr[5] = {2,6,7,3};
Here, arr is a five-element integer array. Figure 2.12 shows the representation of array arr in
memory:

Figure : Array representation in memory

As shown in Fig. 2.12, each array element is stored at consecutive memory locations, i.e., 6000,
6002, 6004, and so on. The location of the first element, i.e., 6000 is also referred as the base
address of the array. If we know the base address of an array, then we can find the location
of its individual elements by using a simple formula, which is
address of A[k] = B + W * k
Here, A[k] is the array.
B is the base address, i.e., the address of the first element.
W is the word size or the size of an array element.
k is the index identifier.
For instance, the address of the third element of array arr stored at index location 2 and
assumed the word size is 2 bytes would be
Address of arr[2] = 6000 + 2 * 2
= 6000 + 4
= 6004
Note: The word size of a data type is decided by the programming language being used and the
hardware specifications.

1.3.2 Operations on Arrays

Following are the basic operations supported by an array.

o Traversal – processing each element in the list.
o Insertion − adding a new element at given index to the list.
o Deletion – removing an element at given index from the list.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 9

o Search − finding the location of the element with a given value or the record with a given key.
o Sorting: arranging the elements in some type of order.
o Merging: Combing two lists into a single list.

Traversing Linear Arrays: Let A be the array in the memory of the computer. If the operation
required is to print the contents of each element of A (OR) Count the number of elements of A.
Then this is accomplished by traversing A, i.e, by accessing and processing each element of A
exactly once.
// program to demonstrate the array creation and array traversal.
#include<stdio.h>
#include<conio.h>
# define SIZE 50
void main ()
{
int arr[SIZE]; // array declaration
int index, no_ele;
Scan to Execute

printf("Enter the number of elements\n");

scanf("%d", &no_ele);

printf("\nEnter the elements\n"); // Reading array elements

for(index=0; index<no_ele; index++)
scanf("%d", &arr[index]);

printf(" \nThe elements of the array are \n"); // Array traversal

for(index=0; index<no_ele;index++)
printf("%d\t", arr[index]);
}
Output :
Enter the number of elements
5
Enter the elements
11
22
33
44
55
The elements of the array are
33 11 22 44 55

Insertion Operation
Insert operation is to insert one or more data elements into an array. Based on the requirement, new
element can be added at the beginning, end or any given index of array. Here, we see a practical
implementation of insertion operation, where we add data at the end of the array –
Algorithm

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 10

INSERT(LA, N, K, ITEM)
HERE LA is a linear array with N elements and K is a positive integer such that K<=N. this
algorithm inserts an element ITEM into Kth position in LA.
Step 1. [Initalize the counter]. Set J=N.
Step 2. repeat steps 3 and 4 while J>=K
Step 3. [move jth element downward] set LA[J+1]=LA[J].
Step 4. [Decrease the counter] set J=J-1
[end of step 2 loop]
Step 5. [insert element] set LA[K]A=ITEM
Step 6. [reset N] set N=N+1
Step 7. Exit

// program to demonstrate array insertion operations.

#include<stdio.h>
#include<conio.h>
#define SIZE 50
void main ()
{
int arr [SIZE]; // array declaration
int i, no_ele, pos, new_ele;

printf ("Enter the number of elements \n");

scanf("%d", &no_ele); // read the elements for the array
printf ("\n Enter the elements \n");
for (i=0; i<no_ele; i++)
scanf ("%d", &arr[i]);
//traversal of the array to print all elements
printf ("\n The elements of the array are \n");
for (i=0;i<no_ele; i++)
printf ("%d\t", arr[i]);

printf("\n Enter the position of the new element to be inserted \n");

scanf("%d", &pos);

printf ("\n Enter the new element to be inserted\n");

scanf("%d", &new_ele);

for(i=no_ele-1;i>=pos-1;i--) // making the place to insertion

arr[i+1]=arr[i];

arr[pos-1]=new_ele; // storing the new element

printf("\nThe resultant array is \n");

for (i=0; i<no_ele+1;i++)
printf("%d\t",arr[i]);
}
Output:
Enter the number of elements
5
Enter the elements
11

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 11

22
33
44
55
The elements of the array are
11 22 33 44 55
Enter the position of the new element to be inserted
4
Enter the new element to be inserted
99
The resultant array is
11 22 33 99 44 55

Deletion Operation
Deletion refers to removing an existing element from the array and re-organizing all elements of
an array.
Algorithm
DELETE(LA, N, K, ITEM)
Consider LA is a linear array with N elements and K is a positive integer such that K<=N. Below
is the algorithm to delete an element available at the Kth position of LA.
Step 1. Set ITEM=LA[K]
Step 2. repeat for J=K to N-1
Step 3. [move (j+1)st element upward] set LA[J]=LA[J+1].
Step 4. [end of step 2 loop]
Step 5. [reset N] set N=N-1
Step 6. Exit

// program to demonstrate the array creation and deletion operations.

#include<stdio.h>
#include<conio.h>
#define SIZE 50
void main()
{
int arr[SIZE]; // array declaration
int i, no_ele, pos, new_ele;

printf("Enter the number of elements \n");

scanf("%d", &no_ele);
// read the elements for the array
printf ("\n Enter the elements \n");
for (i=0; i<no_ele; i++)
scanf("%d", &arr[i]);
//traveral of the array to print all elements
printf ("\n The elements of the array are \n");
for(i=0; i<no_ele;i++)
printf("%d\t", arr[i]);
printf("\n\n Enter the position of the deleting element \n");
scanf("%d", &pos); // find an appropriate position for deletion
for (i=pos-1; i<no_ele-1; i++)
arr[i]=arr[i+1];

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 12

printf("\n The resultant array is \n") ;

for(i=0; i<no_ele-1; i++)
printf ("%d\t", arr[i]);
}
Output
Enter the number of elements
5
Enter the elements
11
22
33
44
55
The elements of the array are
11 22 33 44 55
Enter the position from which the element to be deleted
4
The resultant array is
11 22 33 55

Searching
Searching is the process of finding some particular element in the list. If the element is present in
the list, then the process is called successful and the process returns the location of that element,
otherwise the search is called unsuccessful.

There are two popular search methods that are widely used in order to search some item into the
list. They are Linear Search and Binary Search, however choice of the algorithm depends upon
the arrangement of the list.
Linear Search
Linear search is the simplest search algorithm and often called sequential search. In this type of
searching, we simply traverse the list completely and match each element of the list with the item
whose location is to be found. If the match found then location of the item is returned otherwise
the algorithm return NULL. Linear search is mostly used to search an unordered list in which the
items are not sorted. The algorithm of linear search is given as follows.
Algorithm
LINEAR SEARCH (DATA, N, ITEM, LOC)
Here DATA is a linear array with N elements and ITEM is a given element to be searched. In linear
search, DATA array is traversed sequentially to locate ITEM. The given algorithm finds the
location LOC of item in DATA or set LOC=0, if the search is unsuccessful.
Step 1. Initialize set K=0 and LOC=0
Step 2. Repeat steps 3 & 4 while(LOC=0 and K<=N-1)
Step 3. If ITEM == DATA[K], then LOC=K
Step 4. Set K=K+1[Increment Counter]
Step 5. [End of step 2 loop]
Step 6. [Successful?]

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 13

If LOC=0, then
write: ITEM is not in the array DATA
else
write: LOC+1 is the position of ITEM
Step 7. Exit

#include<stdio.h>
void main ()
{
int a[10] = {10, 23, 40, 1, 2, 0, 14, 13, 50, 9};
int item, i,flag;
printf("\nEnter Item which is to be searched\n");
scanf("%d", &item);
for (i = 0; i< 10; i++)
{
if(a[i] == item)
{
flag = i+1;
break;
}
else
flag = 0;
}
if(flag != 0)
printf("\nItem found at location %d\n",flag);
else
printf("\nItem not found\n");
}
Output:
Enter Item which is to be searched
20
Item not found
Enter Item which is to be searched
23
Item found at location 2

Binary Search
Binary Search is a search algorithm that is used to find the position of an element (target value)
in a sorted array. The array should be sorted prior to applying a binary search. Binary search is
also known by these names, logarithmic search, binary chop, half interval search.
Algorithm
BINARY SEARCH (DATA, LB, UB, ITEM, LOC)
Here DATA is a sorted array with lower bound LB and upper bound UB and ITEM is a given item
of information. The variables BEG, END and MID denote respectively the beginning, end and
middle locations of a segment of elements of data. This algorithm finds the location LOC of item
in DATA or sets LOC=NULL.
Step 1. [Initialize segment variables]
Set BEG=LB, END=UB and MID=INT((BEG+END)/2);
Step 2. repeat steps 3 and 4 while BEG<=END and DATA[MID]!=ITEM

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 14

Step 3. if ITEM<DATA[MID] then

Set END=MID-1
else
Set BEG=MID+1
[end of loop]
Step 4. set MID=INT(BEG+END)/2
Step 5. if DATA[MID]=ITEM Then
set LOC=MID
else
set LOC=NULL
Step 6. Exit

#include <stdio.h>
int BinarySearch(int array[], int start, int end, int ele)
{
while (start <= end)
{
int mid = start + (end - start)/2;
if (array[mid] == ele)
return mid;
if (array[mid] < ele)
start = mid + 1;
else
end = mid - 1;
}
return -1;
}
int main(void)
{
int array[] = {1, 4, 7, 9, 16, 56, 70};
int n = 7;
int element;
printf("Enter the Searching Element : ");
scanf("%d", &element);
int found_index = BinarySearch(array, 0, n-1, element);
if(found_index == -1 )
printf("Element not found in the array ");
else
printf("Element found at index : %d",found_index);
return 0;
}
Output:
Enter the Searching Element: 56
Element found at index: 5

Enter the Searching Element: 23

Element not found in the array

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 15

Insertion sort Algorithm

Insertion sort is a simple sorting algorithm that builds the final sorted
array one element at a time by comparing each new element to those
already sorted and inserting it into its correct position. Here is the C
code for insertion sort:
#include <stdio.h>

void insertionSort(int arr[], int n) {

int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;

// Move elements of arr[0..i-1], that are greater than key,

// to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);

insertionSort(arr, n);

// Print sorted array

for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
Output:
5 6 11 12 13

Radix sort
❑ Radix Sort is a linear sorting algorithm (for fixed length digit counts) that sorts elements by
processing them digit by digit.
❑ Step1: Find the number with the maximum number of digits in the input array. All other
numbers are conceptually padded with leading zeros to match this length.
❑ Step 2: The algorithm makes passes equal to the maximum number of digits. In each pass, it
sorts the numbers based on a specific digit's place value (ones place, tens place, hundreds
place, etc.).

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 16

❑ Step 3: For each digit's place value, Radix Sort typically utilizes Counting Sort to sort the
numbers. Counting Sort is suitable here because the range of digit values (0-9 for decimal
numbers) is small and fixed.
❑ Step 4: Repeat: This process repeats for each digit, moving from the least significant digit to
the most significant digit.
Example 1:

Example 2::

#include <stdio.h>
// Function to get the maximum value in an array
int getMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
return max;
}

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 17

// Counting Sort used by Radix Sort

void countingSort(int arr[], int n, int exp) {
int output[n]; // output array
int count[10] = {0};

// Count occurrences of digits

for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;

// Change count[i] so that count[i] contains actual

// position of this digit in output[]
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];

// Build the output array (stable sorting)

for (int i = n - 1; i >= 0; i--) {
int digit = (arr[i] / exp) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}

// Copy the output array to arr[]

for (int i = 0; i < n; i++)
arr[i] = output[i];
}

// Main Radix Sort function

void radixSort(int arr[], int n) {
int max = getMax(arr, n);

// Apply counting sort for every digit (exp = 1, 10, 100, ...)
for (int exp = 1; max / exp > 0; exp *= 10)
countingSort(arr, n, exp);
}

// Function to print the array

void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}

// Driver program
int main() {
int arr[] = {501, 2, 89, 1000, 67, 700, 45, 9000};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: ");

printArray(arr, n);

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 18

radixSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}

1.4 Pointers in C Programming

A pointer is a variable that stores the address of another variable. Unlike other variables that hold
values of a certain type, pointer holds the address of a variable. For example, an integer variable
holds (or you can say stores) an integer value, however an integer pointer holds the address of a
integer variable.

A simple example to understand how to access the address of a variable without pointers
In this program, we have a variable num of int type. The value of num is 10 and this value must be
stored somewhere in the memory, right? A memory space is allocated for each variable that holds
the value of that variable, this memory space has an address. For example, we live in a house and
our house has an address, which helps other people to find our house. The same way the value of
the variable is stored in a memory address, which helps the C program to find that value when it is
needed.

So let’s say the address assigned to variable num is 0x7fff5694dc58, which means whatever
value we would be assigning to num should be stored at the location: 0x7fff5694dc58. See the
diagram below.

#include <stdio.h>
int main()
{
int num = 10;
printf("Value of variable num is: %d", num);
/* To print the address of a variable we use %p * format specifier
and ampersand (&) sign just * before the variable name like &num. */
printf("\n Address of variable num is: %p", &num);
return 0;
}
Output:
Value of variable num is: 10

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 19

Address of variable num is: 0x7fff5694dc58

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 *. Dereferencing is used to access or manipulate
data contained in memory location pointed to by a pointer. *(asterisk) is used with pointer variable
when dereferencing the pointer variable, it refers to variable being pointed, so this is called
dereferencing of pointers.

A Simple Example of Pointers in C

This program shows how a pointer is declared and used. There are several other things that we can
do with pointers, we have discussed them later in this guide. For now, we just need to know how
to link a pointer to the address of a variable.

Important point to note is: The data type of pointer and the variable must match, an int pointer can
hold the address of int variable, similarly a pointer declared with float data type can hold the
address of a float variable. In the example below, the pointer and the variable both are of int type.

#include int main()

{
//Variable declaration
int num = 10; //Pointer declaration
int *p; //Assigning address of num to the pointer p
p = &num;
printf("Address of variable num is: %p", p);
return 0;
}

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. 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.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 20

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 can also decrement a pointer once incremented. p-- moves back by one location.
As studied above, we can use a pointer to point to an Array, and then we can use that pointer to
access the array. Let’s have an example,
#include<stdio.h>
int main()
{
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++) {
printf("%d", *p);
p++;
}
return 0;
}

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.

1.5 DYNAMIC MEMORY ALLOCATION

The process of allocating memory during the runtime is

called as DMA (dynamic memory allocation) and memory
gets allotted in heap area of program stack Library routines
known as memory management functions are used for
allocating and freeing memory during execution of a
program. These functions are defined in stdlib.h header file.

The following functions are used in dynamic memory

allocation and are defined in <stdlib.h>
1. malloc() : allocates requested size of bytes and returns a void pointer pointing to the first byte
of the allocated space
Declaration: void *malloc(size_t size); // ptr=(datatpe*)malloc(sizeof(datatype));
int *x;

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 21

x = (int*)malloc(50 * sizeof(int));//memory allocated to variable x

free(x); //releases the memory allocated to variable x

2. calloc(): allocates space for an array of elements, initialize them to zero and then returns a
void pointer to the memory.
Declaration: void *calloc(size_t n,size_t size); //ptr=(datatype*)calloc(n,sizeof(datatype));
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.
int *x;
x = (int*)calloc(50, sizeof(int)); //memory allocated to variable x
free(x); //releases the memory allocated to variable x

1.5.1 Difference between malloc() and calloc()

calloc() malloc()
calloc() initializes the allocated memory with malloc() initializes the allocated memory with
0 value. garbage values.
Number of arguments is 2 Number of argument is 1
Syntax : Syntax :
(cast_type *)calloc(blocks, size); (cast_type *)malloc(size);
3. realloc() changes memory size that is already allocated dynamically to a variable.

Syntax: void* realloc(pointer, new-size)

Example:

int *x;
x = (int*)malloc(50 * sizeof(int));
x = (int*)realloc(x,100); //allocated a new memory to variable x

4. free(); 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.
Declaration: void free(void *p); //free(ptr);
Program implementation of Array Operations
//Program to demonstrate Array operation using Pointer
#include<stdio.h>
#include<stdlib.h>
int n,*a; // 'n' - no. of elements & '*a' - Pointer Array
void create(int n)
{
int i;
a=(int*)malloc(n*sizeof(int)); // Dynamic memory allocation
if(a==NULL) {
printf("\n ** Array not created ** \n");

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 22

return;
}
printf("\n Array created successfully \n");
printf("\n Enter array elements \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
}
void display()
{
int i;
for(i=0;i<n;i++)
{ Scan to Execute
printf("%d\t",a[i]);
}
}
void insert(int ele, int pos)
{ int j=n-1;
n++;
a=(int*)realloc(a,n*sizeof(int));
while(j>=pos)
{
a[j+1]=a[j];
j--;
}
a[pos]=ele;
}
void delArrEle(int pos)
{ int j,item;
item=a[pos];
printf("\n The deleted ele is %d\n",item);
for(j=pos;j<n-1;j++)
a[j]=a[j+1];
n--;
if(n==0)
printf("\n No element in the array\n");
}
void main()
{
int ch,ele,pos;
while(1)
{
printf("\n 1. Create\n 2. Display\n 3. Insert\n 4. Delete\n
5. Exit\n Enter a choice :");
scanf("%d",&ch);
if(n==0 && ch!=1) // when ZERO elements [[Link]] is allowed
{
printf("\n ** No element in the array ** \n");

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 23

continue;
}
switch(ch)
{
case 1: printf("\nEnter the size of array : ");
scanf("%d",&n);
create(n);
break;
case 2: display();
break;
case 3: printf("\n Enter the position : ");
scanf("%d",&pos);
if(pos>0 && pos<=(n+1))
{
printf("\n Enter the element : ");
scanf("%d",&ele);
insert(ele, pos-1);
}
else
printf("\n ** Invalid Position ** \n");
display(); break;
case 4: printf("\nEnter the deleleting element position :");
scanf("%d", &pos);
if(pos>0 && pos<=n)
delArrEle(pos-1);
else
printf("\n ** Invalid Position ** \n");
display();
break;
default: free(a); exit(0);
} // end of switch
} // end of while
} // end of main()
Output:

--------MENU ----------
[Link]
[Link]
[Link]
[Link]
[Link]
----------------------
ENTER YOUR CHOICE: 1

Enter the size of the array elements: 5

Enter the elements for the array:

1
2

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 24

3
4
5
--------MENU ----------
[Link]
[Link]
[Link]
[Link]
[Link]
----------------------
ENTER YOUR CHOICE: 2

The array elements are:

1 2 3 4 5

--------MENU ----------
[Link]
[Link]
[Link]
[Link]
[Link]
----------------------
ENTER YOUR CHOICE: 3

Enter the position for the new element: 3

Enter the element to be inserted: 31

The array elements are:

1 2 3 31 4 5

--------MENU ----------
[Link]
[Link]
[Link]
[Link]
[Link]
----------------------
ENTER YOUR CHOICE: 4

Enter the position of the element to be deleted: 3

The deleted element is =31

The array elements are:
1 2 31 4 5

--------MENU ----------
[Link]
[Link]
[Link]
[Link]

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 25

[Link]
----------------------
ENTER YOUR CHOICE: 5

Here are five key advantages of dynamic memory allocation in C:

1. Efficient memory usage – Memory is allocated at runtime, so you can request exactly
the amount of memory needed instead of wasting space with fixed-size arrays or
structures.
2. Flexibility – The size of data structures (like arrays, linked lists, trees, etc.) can grow or
shrink during program execution.
3. Scalability – Programs can handle varying input sizes without being limited by compile-
time memory allocation.
4. Lifetime control – Dynamically allocated memory persists until explicitly freed (free()),
unlike local variables that are deallocated automatically when a function exits.
5. Support for complex data structures – Enables creation of advanced data structures
(linked lists, stacks, queues, trees, graphs) that rely on nodes connected through pointers.

1.6 STRUCTURES

Along with built-in data types like int, float, char, double C provides the programmer to define
his/her own data-type. These are known as user-defined data types. A programmer can derive a
new data type based on existing data types. Structures, Unions and Enumerations are considered
to be major user-defined data types.

We know that an array is a collection of related elements of same data type. But, if the related
elements belong to different data types, then it is not possible to form an array. Consider a situation
of storing the information about students in a class. The information may include name of the
student, age of the student and marks of the student. It can be easily observed that name is a
character array (or string), age might be an integer and marks obtained may be a floating point
number. Though name, age and marks are of same student, we can not combine them into an array.
To overcome this problem with arrays, C allows the programmer to combine elements of different
data types into a single entity called as a structure.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 26

Structure is a collection of inter-related elements of

different data types. The syntax of structure is:

For example:
struct student
{
int age;
float marks;
}s1,s2;
Here, student is name of the structure or structure tag. age, marks are member variables of a
structure. s1, s2 are variables of new data type struct student.

1.6.1 Declaration of Structure Variables

Structure declaration is considered to as defining a new data type. So, to make use of it, the
programmer has to declare a variable of this new data type. There are two ways of declaring a
structure variable. The programmer can declare variables of structure at the time of structure
declaration itself as shown in the above example. Otherwise, one can declare them separately. For
example –
struct student
{
int age;
float marks;
};
struct student s1,s2;

Here, struct student is name of new data type and hence using it, one can declare the
variables s1 and s2.

Note that declaration of structure is just a prototype and it will not occupy any space in the memory.
When a variable of structure gets declared, memory will be allocated for those variables. The
memory space required for one structure variable will be the sum of the memories required for all
member variables. In the above example, each of the structure variables s1 and s2 takes 6 bytes of
memory (2 bytes for age and 4 bytes for marks). The memory map can be given as –
s1 s2
age marks age marks
2 bytes 4 bytes 2 bytes 4 bytes

Thus, s1 and s2 are considered to be separate variables.

Note: After declaring some of the structure variables along with the structure definition, it is
possible to declare some more structure variables in a separate statement as shown below:
struct student

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 27

{
int age;
float marks;
}s1,s2;

struct student s3, s4;

1.6.2 Structure Initialization

Just like any variable or an array, a structure variable also can be initialized at the time of its
declaration. Values for member variables are given in a comma-separated list as we do for arrays.
Consider an example:
struct student
{
int age;
float marks;
} s1 = {21, 84.5};

struct student s2 = {20, 91.3};

NOTE:
1. Providing lesser number of values during initialization will make the rest of the variables to
hold the value zero. That is,
struct test
{
int a,b,c;
} t = {12, 45};
Now, the values of a, b and c will be 12, 45 and 0 respectively.
2. It is not possible to give initial value to a member variable within a structure definition.
Because, structure definition is just a logical entity and member variables will not be having any
physical location until the structure variables are declared. Thus, following attempt is erroneous.
struct test
{
int a=10; //error
float b= 12.5; //error
};

1.6.3 Accessing Member Variables

Member variables of a structure can not be accessed just by referring to their names. The reason is
obvious. Refer to the memory map given in section 1.6.1. It can be observed that memory location
for the member variable age of s1 is different from that of s2. Similarly for the member marks.
Hence, it can be understood that each of the member variable is associated with a structure variable.
Or in other words, every structure variable has its own copy of member variables. Thus, for

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 28

accessing any member variable, its associated structure variable also should be specified. This is
done with the help of dot (.) operator.
The syntax is: Structure_variable.member_variable
Example for accessing member variable
#include<stdio.h>
struct student
{
int age;
float marks;
}s1, s2;

void main()
{
[Link]=21;
[Link]=[Link];
printf("Enter marks of students:");
scanf("%f%f", &[Link], &[Link]);
printf("\nAge1= %d Age2=%d", [Link], [Link]);
printf("\nMarks1= %f Marks2=%f", [Link], [Link]);
if([Link]>[Link])
printf("\n First Rank is Student1");
else
printf("\n First Rank is Student2");
}
The output would be:
Enter marks of students: 81.5 92.3
Age1 = 21
Age2 = 21
Marks1 = 81.5
Marks2 = 92.3
First Rank is Student2

1.6.4 Structure Assignment

In some situations, the programmer may need two structure variables to have same values for all
the member variables. Then, instead of assigning each member separately, it is possible to assign
whole structure variable to another structure variable of same type. For example:
struct student
{
int age;
float marks;
} s1, s2={21,92.3};

Now, the statement

s1=s2;
will assign values of all members of s2 to the corresponding members of s1.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 29

1.6.5 Arrays within Structure

A member variable of a structure can be an array of any data type. Consider the following example:
Example for array as a member of structure
#include<stdio.h>
struct student
{
char name[20]; //array as a member
int age;
float marks;
}s1, s2={“Kavya”,22,92.3};

void main()
{
[Link]=21;
printf(“Enter name of student:”);
scanf(“%s”, [Link]);
printf(“\nEnter marks of student:”);
scanf(“%f”, &[Link]);
printf(“\n Student Information:\n”);
printf(“\n Name \t\t Age \t\t Marks \n”);
printf(“%s \t %d \t %f \n”, [Link], [Link], [Link]);
printf(“%s \t %d \t %f \n”, [Link], [Link], [Link]);
}
The output would be:
Enter name of student: Ramu
Enter marks of students: 81.5
Student Information:
Name Age Marks
Ramu 21 81.5
Kavya 22 92.3

1.6.6 Arrays of Structures

We know that array is a collection of elements of same data type and the structure is a collection
of items of different data types. Some times, it may be necessary to have several structure variables.
For example, if the information (like name, age and marks) about 60 students studying in 6th
Semester is required, creating 60 structure variables is absurd. Instead, one can create an array of
structure variables. Memory allocation for array of structures will be in contiguous locations. This
concept is illustrated in the following example:
Example for array of structures
#include<stdio.h>
struct student
{
char name[20];
int age;
float marks;
} s[2]; //array of structures

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 30

void main()
{
int i;
for(i=0;i<2;i++)
{
printf("Enter name of student");
scanf("%s", s[i].name);
printf("\nEnter age of student");
scanf("%d",&s[i].age);
printf("\nEnter marks of student");
scanf("%f", &s[i].marks);
}
printf("\n Student Information:\n");
printf ("\n Name \t Age \t Marks \n");
for(i=0;i<2;i++)
printf("\n%s \t %d \t %f", s[i].name, s[i].age, s[i].marks);
}
The output would be:
Enter name of student: Suma
Enter age of student: 21
Enter marks of student: 81.5
Enter name of student: Roopa
Enter age of student: 22
Enter marks of student: 92.3
Student Information:
Name Age Marks
Suma 21 81.5
Rooja 22 92.3

In the above example, memory allocation for the array s[2] might be as follows:

s[0] s[1]
s[0].name s[0].age s[0].marks s[1].name s[1].age s[1].marks

Note that array of structure variables can also be initialized just like a normal array. For example:
struct student
{
int age;
float marks;
}s[3] = { {21, 81.5}, {22, 92.3}, {25, 88.4} };
Then, the individual elements will be assigned the values as –
s[0].age=21
s[1].age=22
s[2].age=25
s[0].marks=81.5
s[1].marks=92.3
s[2].marks=88.4
Note also that, un-initialized members will take the value as zero.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 31

1.6.7 Nested Structures

A member variable of a structure may be a variable of type another structure. This is known as
nesting of structures. For example:

struct address
{
int d_no; // 2 bytes
char street[20]; // 20 bytes
char city[20]; // 20 bytes
}; // Total 42 bytes
struct employee
{
char name[20]; // 20 bytes
int d_no; // 2 bytes
float sal; // 4 bytes
struct address add; // 42 bytes
}emp;
The total memory allocated for the variable emp would be 68 bytes. The memory map can be:

Here, the structure address contains the members d_no, street and city. Then the structure employee
contains the members name, d_no, sal and add. Here, add is a variable of structure address. To
access the members of the inner structure one has to use the following type of statements:
[Link].d_no
[Link]
[Link] etc.
1.6.8 Passing Structure to Functions

Just like a normal variable, it is possible to pass a structure variable as a function parameter either
using call-by-value method or call-by-address method. Member variables as arguments:
Individual members of a structure can be passed to function as arguments. In this situation,
members of structure are treated like any normal variable. Consider an example –
Structure member as a function argument
#include<stdio.h>
struct add
{
int a, b;
};

int sum(int x, int y)

{

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 32

return (x+y);
}
void main()
{
struct add var ;
int s ;
printf("Enter two numbers :" );
scanf(“%d%d”, &var.a, &var.b);
s=sum(var.a, var.b);
printf(“Sum is: %d”,s);
}
The output would be –
Enter two numbers : 5
8
Sum is: 13

Whole structure variable as an argument: Instead of passing each member of a structure to a

function, entire structure variable can be passed. For example:
#include<stdio.h>
struct add
{
int a, b;
};
int sum(struct add A) //parameter is a structure variable
{
return (A.x + A.y);
}
void main()
{
struct add var;
int s;
printf("Enter two numbers :" );
scanf(“%d%d”, &var.a, &var.b);
s=sum(var);
printf(“Sum is: %d”,s);
}
The output would be –
Enter two numbers : 5
8
Sum is: 13
1.6.9 Pointers and Structures
We can create a pointer to store the address of a structure variable. To access the member variables
of a structure using a pointer, we need to use either an indirectional operator -> or the combination
of * and dot(.). Let us consider an example:
#include<stdio.h>
struct student
{
char name[20];

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 33

int age;
};
void main()
{
struct student s={“Ramu”, 22};
struct student *p;
p= &s;
printf(“Student name =%s”, p ->name);
printf(“\nStudent age =%d”, (*p).age);
}
In the above example, note the usage:
(*p).age
Here, the pointer p is dereferenced first, and then dot operator is used to get the member variable
age. Instead of two operators * and dot, we can use single indirectional operator (arrow mark) to
achieve the same. That is, we can use
p->age, p->name etc.
We can even create a pointer to array of structures also. For example (with respect to structure
declared in the above example):
struct student s[10], *p;
p = s; // base address of the array s is assigned to p
Then, for accessing array members, we can use:
for(i=0; i<n;i++)
printf(“%s %d”, p[i]->name, p[i].age);
The similar approach can be used while passing structures to functions via call by address method.

1.6.10 Union
Union can be defined as a user-defined data type which is a collection of different variables of
different data types in the same memory location. The union can also be defined as many members,
but only one member can contain a value at a particular point in time. Union is a user-defined data
type, but unlike structures, they share the same memory location.

To define a union, you must use the union statement in the same way as you did while defining a
structure. The union statement defines a new data type with more than one member for your
program. The format of the union statement is as follows –
union [union tag] {
member definition;
member definition;
...
member definition;
} [one or more union variables];
Example:
union Data {

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 34

int i;
float f;
char str[20];
} data;

The memory occupied by a union will be large enough to hold the largest member of the union.
For example, in the above example, Data type will occupy 20 bytes of memory space because this
is the maximum space which can be occupied by a character string. The following example displays
the total memory size occupied by the above union –
#include<stdio.h>
#include<string.h>
union Data {
int i;
float f;
char str[20];
};

int main() {
union Data data;
printf( "Memory size occupied by data : %d\n", sizeof(data));
return 0;
}
When the above code is compiled and executed, it produces the following result −
Memory size occupied by data : 20

Accessing Union Members

To access any member of a union, we use the member access operator (.). The member access
operator is coded as a period between the union variable name and the union member that we wish
to access. You would use the keyword union to define variables of union type. The following
example shows how to use unions in a program –
#include<stdio.h>
#include<string.h>

union Data {
int i;
float f;
char str[20];
};

int main()
{
union Data data;
data.i = 10;
data.f = 220.5;

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 35

strcpy( [Link], "C Programming");

printf( "data.i : %d\n", data.i);

printf( "data.f : %f\n", data.f);
printf( "[Link] : %s\n", [Link]);

return 0;
}
When the above code is compiled and executed, it produces the following result −
data.i : 1917853763
data.f : 4122360580327794860452759994368.000000
[Link] : C Programming
Here, we can see that the values of i and f members of union got corrupted because the final value
assigned to the variable has occupied the memory location and this is the reason that the value of
str member is getting printed very well.

Now let's look into the same example once again where we will use one variable at a time which
is the main purpose of having unions –
#include <stdio.h>
#include <string.h>

union Data {
int i;
float f;
char str[20];
};

int main( )
{
union Data data;
data.i = 10;
printf( "data.i : %d\n", data.i);

data.f = 220.5;
printf( "data.f : %f\n", data.f);

strcpy( [Link], "C Programming");

printf( "[Link] : %s\n", [Link]);
return 0;
}
When the above code is compiled and executed, it produces the following result −
data.i : 10
data.f : 220.500000
[Link] : C Programming
Here, all the members are getting printed very well because one member is being used at a time.
Difference between Structure and union

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 36

Structure Union
The keyword struct is used to define a The keyword union is used to define a union.
structure
When a variable is associated with a When a variable is associated with a union,
structure, the compiler allocates the memory the compiler allocates the memory by
for each member. The sizeof structure is considering the size of the largest member.
greater than or equal to the sum of sizes of So, size of union is equal to the size of largest
its members. The smaller members may end member.
with unused slack bytes
Altering the value of a member will not affect Altering the value of any of the member will
other members of the structure alter other member values.
The address of each member will be in The address is same for all the members of a
ascending order This indicates that memory union. This indicates that every member
for each member will start at different offset begins at offset zero.
values.
Individual members can be accessed at any Only one member can be accessed at a time
time since separate memory is reserved for since memory is shared by each member.
each member.

1.7 APPLICATIONS OF ARRAYS and Structures

The two major applications of the arrays are polynomial and sparse matrix
Polynomial representation
Sparse matrix representations
1.7.1 POLYNOMIALS

Polynomial is a sum of terms where each term has a form axe , where x is the variable, a is the
coefficient and e is the exponent.
Examples:
A(x) = 3x20+2x5 +4
B(x) = x4 +10x3 +3x2 +1
The largest exponent of a polynomial is called its degree. In the above example, degree of first
polynomial is 20 and for the second polynomial it is 4.
Note: Coefficients that are zero are not displayed, the term with exponent zero does not show the
variable i.e. 4x2 +5x+1 where 1 is a term having exponent zero so variable is not displayed.
Operations on polynomials

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 37

• Addition
• Subtraction
• Multiplication
Now, let us consider a polynomial with only one variable and see “How to represent each term of
the polynomial?” Each term consists of a co-efficient multiplied by a variable raised to a power.
So, each term can be represented by a structure consisting of 2 fields namely:
 cf (representing coefficient)
 px (power of x)
The structure definition for a term of a polynomial can be written as shown below:
typedef struct
{
int cf; // used to hold the co-efficient
int px; // used to hold power of x
} POLY;
Now, consider the following declaration along with its memory representation:

Once the memory is allocated as shown above, the term 6x5 can be stored using the variable p
as shown below:

We have represented only one term. Now the question is “How to represent a polynomial with
more than one node?” This can be done using array of structures with the following declaration:
typedef struct
{
int cf; // used to hold the co-efficient
int px; // used to hold power of x
} POLY;
POLY p[10];
Using the above declaration, we have an array of 10 terms where each term has four fields.
Consider the following polynomial:
8x6 + 3x3 + 6x2 + 3x + 4
It can be stored as an array of 5 terms as shown below:

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 38

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 39

Program to add two polynomials

#include<stdio.h>
typedef struct
{
int cf; // used to hold the co-efficient
int px; // used to hold power of x
} POLY;

POLY p[10];
void read_poly(POLY p[], int n)
{
int i, cf, px;
for(i = 0; i < n; i++)
{
printf("cf, px:"); scanf("%d %d", &cf, &px);
p[i].cf = cf;
p[i].px = px;
}
}
void print_poly(POLY p[], int n)
{
int i;
for(i = 0; i < n; i++)
{
if(p[i].cf < 0)
printf("%d", p[i].cf);
else
printf("+ %d", p[i].cf);
if(p[i].px != 0)
printf("x^%d", p[i].px);
}
printf("\n");
}

int search (int px1, POLY p2[], int n)

{
int j, px2;
for( j = 0; j < n; j++)
{
px2 = p2[j].px;
if(px1 == px2)
return j;
}
return -1;
}

int add_poly (POLY p1[], int m, POLY p2[], int n, POLY p3[])
{
int i, k, cf1, px1, pos, sum;
k = 0;
for( i = 0; i < m; i++)

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 40

{
cf1 = p1[i].cf;
px1 = p1[i].px; /* Access each item of poly 1 */
pos = search(px1, p2, n); /* get position of px1 in poly 2 */
if(pos >= 0) /* px1 found in poly 2 */
{
sum = cf1 + p2[pos].cf; /* Add the coefficients */
if (sum != 0) p3[k].cf = sum; /*Insert sum into poly 3*/
p2[pos].cf = -999; /* Delete the term of poly2 */
}
else
p3[k].cf = cf1; /* Insert co-efficient of poly 1 */

p3[k].px = px1; /* Insert power of x into poly 3 */

k++;
}
k = copy_poly(p3, k, p2, n); /* Copy remaining terms of poly 2*/

return k; /* return total terms in poly 3 */

}

int copy_poly ( POLY p3[], int k, POLY p2[], int n)

{
int j;
for(j = 0; j < n; j++)
{
if(p2[j].cf != -999)
{
p3[k].cf = p2[j].cf;
p3[k].px = p2[j].px;
k++;
}
}
return k;
}

void main()
{
POLY p1[20], p2[20], p3[40];
int m, n, k;
printf("Enter total terms in Poly 1:"); scanf("%d", &m);
read_poly(p1, m);
printf("Enter total terms in Poly 2:"); scanf("%d", &n);
read_poly(p2, n);

printf("Poly 1: "); print_poly(p1, m);

printf("Poly 2: "); print_poly(p2, n);
printf("--------------------------------------------------------\n");
k = add_poly (p1, m, p2, n, p3);
printf("Poly 3: "); print_poly(p3, k);
}

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 41

Polynomial representation using 1 D arrays

Consider the two polynomials

A(x) = 2xl000+ 1
B(x) = x4 + 10x3 + 3x2 + 1
#define MAX 100
int coef[MAX]; //array to hold Coefficients
int expo[MAX]; // array to hold exponentials
int startA, startB; // to hold the starting index of polynomial A and B
int finishA, finishB; // to hold the ending index of polynomial A and B
int avail; // to indicate the next available location.

• The above figure shows how these polynomials are stored in the array terms. The index
of the first term of A and B is given by startA and startB, while finishA and finishB give
the index of the last term of A and B.
• The index of the next free location in the array is given by avail.
• For above example, startA=0, finishA=1, startB=2, finishB=5, & avail=6.

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 42

1.7.2 SPARSE MATRICES

Definition: A sparse matrix is a matrix that has very few non-zero elements spread out thinly.
Conversely, a matrix which has more number of zero elements (or high proportion of zeros
elements is called sparse matrix. The sparse matrix can be single dimensional or multidimensional
such as 2-dimensional, 3-dimensional and so on.
Consider the following two-dimensional matrices:

Note the following points with respect to above two matrices:

• In the first matrix, 10 non-zero elements are present and 2 zero elements. The number of
non-zero elements are more than the number of zero elements. So, it is not a sparse matrix.
• In the second matrix only 8 non-zero elements are present and 12 zero elements are present.
So, the number of non-zero elements are less than the number of zero elements. So, it is a
sparse matrix.

Now, let us see “What is the disadvantage of a sparse matrix?” The sparse matrix contains many
zeroes. If we are manipulating only non-zero values, then we are wasting the memory space by
storing unnecessary zero values. This disadvantage can be overcome by storing only non-zero
values thus saving the space.

For example, consider a matrix of size 1000 x 1000.

• Assume it has 2000 non-zero elements and remaining are zero elements.
• The corresponding two-dimensional array occupy 1,000,000 memory locations.
• Instead of storing both zero and non-zero elements, if we store only non-zero elements, the
space can be reduced. This can be done using sparse matrix representation as shown below:

Sparse Matrix Representation

Now, let us see “How sparse matrix can be represented by storing only non-zero values?” We know
that any element in the matrix can be uniquely defined using the triples <row, col, val>. Thus, a
sparse matrix can be created using the array of triples as shown below :

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 43

#define MAX 25 /* Maximum number of terms */

typdef struct
{
int row;
int col;
int val;
} TERM;
/* 1- dimensional array representing array of triples <row, col, val> */
TERM a[MAX_TERMS];

Example: How do you represent the following spare matrix using triples in a single
dimensional array?

The non-zero elements in the above matrix along with row and col position can be represented
using a single dimensional array starting from a[1] as shown below:

To get the transpose we exchange row, col indices along with val as shown below:

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 44

Program to transpose sparse matrix

#include<stdio.h>
#define MAX 20
typedef struct
{
int row;
int col;
int value;
} term;
void printsparse(term b[]);
void readsparse(term sp[]);
void transpose(term b1[], term b2[]);
int main()
{
term s1[MAX],trans[MAX];
int m,n;
printf("Enter the size of matrix (rows,columns):");
scanf("%d%d",&m,&n);
s1[0].row=m;
s1[0].col=n;
readsparse(s1);
printsparse(s1);
transpose(s1,trans);
printf("\nAfter Transpose:\n");
printsparse(trans);
}
void readsparse(term sp[])
{
int i,t;
printf("\nEnter no. of non-zero elements:");
scanf("%d",&t);
sp[0].value=t;
for(i=1;i<=t;i++)
{
printf("\nEnter the next triple(row,column,value):");
scanf("%d%d%d",&sp[i].row,&sp[i].col,&sp[i].value);
}
}

void printsparse(term b[])

{
int i,n;
n=b[0].value; //no of 3-triples
printf("\nrow\t\tcolumn\t\tvalue\n");
for(i=0;i<=n;i++)
printf("%d\t\t%d\t\t%d\n",b[i].row,b[i].col,b[i].value);
}

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 45

void transpose(term b1[],term b2[])

{
int i,j,k,n;
b2[0].row=b1[0].col;
b2[0].col=b1[0].row;
b2[0].value=b1[0].value;
k=1;
n=b1[0].value;
for(i=0;i<b1[0].col;i++)
for(j=1;j<=n;j++)
if(i==b1[j].col) //if a column number of current triple==i
{ // then insert the current triple in b2
b2[k].row=i;
b2[k].col=b1[j].row;
b2[k].value=b1[j].value;
k++;
}
}
Output:
Enter the size of matrix (rows,columns):5 4
Enter no. of non-zero elements:8
Enter the next triple(row,column,value):0 0 10
Enter the next triple(row,column,value):0 3 40
Enter the next triple(row,column,value):1 0 11
Enter the next triple(row,column,value):1 2 22
Enter the next triple(row,column,value):3 0 20
Enter the next triple(row,column,value):3 3 50
Enter the next triple(row,column,value):4 1 15
Enter the next triple(row,column,value):4 3 25
row column value
5 4 8
0 0 10
0 3 40
1 0 11
1 2 22
3 0 20
3 3 50
4 1 15
4 3 25

After Transpose:
row column value
4 5 8
0 0 10
0 1 11
0 3 20
1 4 15
2 1 22
3 0 40

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 46

3 3 50
3 4 25

Strings in C

In C programming, a string is a sequence of characters terminated by a null character '\0'. Unlike

many modern languages, C does not have a built-in string data type — instead, strings are
represented as arrays of characters.

1. Declaring and Initializing Strings

#include <stdio.h>

int main() {
char str1[20] = "Hello"; // initialization during declaration
char str2[20] = {'W', 'o', 'r', 'l', 'd', '\0'}; // another way

printf("%s %s\n", str1, str2);

return 0;
}
Output:

Hello World
2. Input and Output of Strings
• Using scanf() — stops at whitespace:

char name[50];
scanf("%s", name);
• Using gets() (unsafe) or fgets() (recommended):

fgets(name, sizeof(name), stdin);

• To display:

printf("Name: %s", name);

3. Common String Functions

Defined in <string.h>:
Function Description Example
strlen(str) Returns length of string strlen("Hello") → 5

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 47

strcpy(dest, src) Copies one string into strcpy(s1, s2)

another
strcat(dest, src) Appends one string to strcat(s1, s2)
another
strcmp(s1, s2) Compares two strings strcmp("a","b")
(returns 0 if equal)
strrev(str) (not Reverses a string -
standard) (available in some
compilers)
Example:

#include <stdio.h>
#include <string.h>

int main() {
char s1[20] = "Hello";
char s2[20] = "World";

strcat(s1, s2);
printf("Concatenated: %s\n", s1);
printf("Length: %lu\n", strlen(s1));
return 0;
}

4. Traversing a String

char str[] = "C Language";

for (int i = 0; str[i] != '\0'; i++) {
printf("%c ", str[i]);
}
Output:
C L a n g u a g e
Example Program: Reverse a String

#include <stdio.h>
#include <string.h>

int main() {
char str[100];
int len;

printf("Enter a string: ");

fgets(str, sizeof(str), stdin);

len = strlen(str);

// Remove newline from fgets

if (str[len - 1] == '\n') str[len - 1] = '\0';

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 48

// Reverse manually
for (int i = len - 1; i >= 0; i--) {
if (str[i] != '\0')
printf("%c", str[i]);
}
return 0;
}
Output:

Enter a string: Hello

olleH

Summary of String functions:

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 49

Representing Array of Strings:

#include <stdio.h>
int main() {
// Declare and initialize the array with sports names
char sports[5][15] = {
"golf",
"hockey",
"football",
"cricket",
"shooting"
};
// Optionally print out the array for verification
for (int i = 0; i < 5; i++) {
printf("%s\n", sports[i]);
}
return 0;
}
Representation of Multi-Dimensional Arrays
Arrays that we have considered up to now are one dimensional array, a single line of elements.
Often data come naturally in the form of a table, e.g. spreadsheet, which need a two-dimensional
array.
Declaration: The syntax is same as for 1-D array but here 2 subscripts are used.
Syntax: data_type array_name[rowsize][columnsize];
Where, Rowsize specifies the no. of rows Columnsize specifies the no. of columns.

Example: int a[4][5]; This is a 2-D array of 4 rows and 5 columns. Here the first element of
the array is a[0][0] and last element of the array is a[3][4] and total no. of elements is 4*5=20.
Column-0 Column-1 Column-2 Column-3 Column-4
Row-0 A[0][0] A[0][1] A[0][2] A[0][3] A[0][4]
Row-1 A[1][0] A[1][1] A[1][2] A[1][3] A[1][4]
Row-2 A[2][0] A[2][1] A[2][2] A[2][3] A[2][4]
Row-3 A[3][0] A[3][1] A[3][2] A[3][3] A[3][4]
Initialization:
2-D arrays can be initialized in a way similar to 1-D arrays.
Example: int m[4][3]={1,2,3,4,5,6,7,8,9,10,11,12};

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 50

Example: int m[][3]={ {1,10}, {2,20,200}, {3}, {4,40,400} };

2D arrays are used to perform matrix operations

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
 Module 1: Introduction to Data Structures and Algorithms (21CS32) 51

2D array creation using Dynamic Memory allocation

3D Array in C
A Three-Dimensional Array or 3D array in C is a collection of two-dimensional arrays. It can be visualized
as multiple 2D arrays stacked on top of each other.

Declaration of 3D Array in C
We can declare a 3D array with x 2D arrays each having m rows and n columns using the syntax shown
below:
type arr_name[x][m][n];
For example, we can declare 3d array, which is made by 2-2D array and each 2D array have 2 rows
and 2 columns:
int arr[2][2][2];
Initialization of 3D Array in C
Initialization in a 3D array is the same as that of 2D arrays. The difference is as the number of dimensions
increases so the number of nested braces will also increase.

int arr[2][3][2] = {0, 1, 2, 3, 4, 5, 6, 7 , 8, 9, 10, 11}

or

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]
Module 1: Introduction to Data Structures and Algorithms (21CS32) 52

int arr[2][3][2] = { { { 1, 1 }, { 2, 3 }, { 4, 5 } },
{ { 6, 7 }, { 8, 9 }, { 10, 11 } } };

3D Array Traversal
To traverse the entire 3D array, you need to use three nested loops: an outer loop that goes through the
depth (or the set of 2D arrays), a middle loop goes through the rows of each 2D array and at last an inner
loop goes through each element of the current row.

#include <stdio.h>

int main() {
// Create and Initialize the
// 3-dimensional array
int arr[2][3][2] = { { { 1, 1 }, { 2, 3 },
{ 4, 5 } }, { { 6, 7 },
{ 8, 9 }, { 10, 11 } } };
// Loop through the depth
for (int i = 0; i < 2; ++i) {
// Loop through the
// rows of each depth
for (int j = 0; j < 3; ++j) {
// Loop through the
// columns of each row
for (int k = 0; k < 2; ++k)
printf("arr[%i][%i][%i] = %d", i, j, k, arr[i][j][k]);
printf("\n");
}
printf("\n\n");
}
return 0;
}

Output:
arr[0][0][0] = 1 arr[0][0][1] = 1
arr[0][1][0] = 2 arr[0][1][1] = 3
arr[0][2][0] = 4 arr[0][2][1] = 5
arr[1][0][0] = 6 arr[1][0][1] = 7
arr[1][1][0] = 8 arr[1][1][1] = 9
arr[1][2][0] = 10 arr[1][2][1] = 11

By: Dr. Rama Satish KV, RNSIT, Associate Professor, Bengaluru. For latest updates visit: [Link]