MOOGAMBIGAI CHARITABLE AND EDUCATIONAL TRUST

Rajarajeswari College of Engineering

(An Autonomous Institution under Visvesvaraya Technological University, Belagavi)

Prepared by
Ms.Yashaswini H R
Assistant Professor
Data Structures and its Applications(B24CS302
Applications(B24CS302)

Module 1:Introduction
Data Structures Definition
Data structures are frameworks for organizing, managing, and storing data efficiently in computer systems, with
applications in databases, operating systems, artificial intelligence, compiler design, web development, networking,
and computer graphics. They enable faster retrieval and manipulation of information, allowing for the optimization
of algorithms and improving overall system performance across various fields.
Introduction to Data Structures
What is a Data Structure?
A data structure is a way of organizing and storing data so that it can be used efficiently.
dataa for solving computational problems.
It provides a systematic way to access, modify, and manage dat
Why Data Structures?
 Efficient data storage and retrieval
 Better organization of large amounts of data
 Helps in optimizing algorithms
 Forms the backbone of software development and system design.
design
Types of Data Structures

1. Primitive Data Structures

o Basic building blocks
o Examples: int, float, char, boolean

Primitive data structures are the basic building blocks of data manipulation.

These include:

 IntRepresents integer values.

 CharUsed to store single characters.

 BoolHolds Boolean values, true or false.

Page 1 of 74
Data Structures and its Applications(B24CS302
Applications(B24CS302)

 FloatUsed for floating-point

point numbers, which are numbers with a decimal point.

 PointerStores memory addresses, pointing to the location of other variables.

2. Non-Primitive Data Structures

o Built using primitive types

Linear Structures:: Data arranged sequentially

 Arrays, Linked Lists, Stacks, Queues

Arrays

dimensional array is the simplest type of data structure. It is a list of a finite

A linear array or a one-dimensional
number, n, of data elements of a similar type. These elements are represented by a set of consecutive
numbers respectively. If A is the array name, then the array elements are represented as any of the
following notations.

A two-dimensional
dimensional array is a collection of similar data elements where each element is referenced by two
elements
subscripts.

Linked lists

A linked list is a collection of data elements whose order is not given by their physical location in
memory. It consists of nodes that contain data and link to the next node. The structure
stru allows easiness in
insertion and deletion operations. The last nodes are linked to NULL and signify the end of the list.

Page 2 of 74
Data Structures and its Applications(B24CS302
Applications(B24CS302)

Stack

Stack, LIFO(Last In First Out) system, is a linear data structure in which insertion(PUSH) and
deletion(POP) are restricted
ed to one endpoint called TOP.

Queue

A queue is a FIFO(First In First Out) system, in which insertion(ENQUEUE) can take place only at an end
called REAR and deletion(DEQUEUE) can take place only at another end called FRONT.

Non-Linear Structures: Dataa arranged hierarchically

 Trees, Graphs

Page 3 of 74
Data Structures and its Applications(B24CS302
Applications(B24CS302)

Trees

Some data contains a hierarchical relationship between various elements. These data are represented in
the form of a Rooted tree graph or simply Tree. Here node A is called the root of the tree.

Graphs

Sometimes
times data contain relationships that are not hierarchical in nature. This type of relationship can be
expressed in the form of a graph data structure.

Key Operations on Data Structures

 Traversal:: Accessing each element
 Insertion: Adding elements
 Deletion: Removing elements
 Searching:: Finding an element (Linear search, Binary search)
 Sorting:: Arranging elements (Ascending/Descending)
Real-World Examples
 Array:: Storing student marks in a list
 Stack:: Undo/Redo in text editors
 Queue:: Ticket booking system, CPU
C scheduling
 Tree: File directory structure
 Graph:: Social networks, Google Maps (shortest path)

Page 4 of 74
Data Structures and its Applications(B24CS302)

Importance in Computer Science

 Basis for algorithms and programming
 Used in databases, operating systems, AI, networking, and web development
 Essential for interviews and competitive programming
Data Structures = Organized way of managing data + Efficient problem solving.
Key Features Of Data Structures
Here are the key features of data structures:
1. Data Storage: Data structures provide a way to store data in an organized manner, making it easier to
manage and access the data efficiently.
2. Data Organization: They organize data in a structured format, such as linear (arrays, linked lists) or non-
linear (trees, graphs), facilitating easier data manipulation.
3. Data Processing: They enable efficient data manipulation, including operations like insertion, deletion, and
traversal, which are optimized for performance based on the data structure used.
4. Memory Management: They manage memory usage effectively, with some data structures like linked lists
and trees dynamically allocating memory as needed.
5. Homogeneous Data: Many data structures store homogeneous data elements, meaning all elements are of
the same type, ensuring consistency and predictability.
6. Indexing: Certain data structures, such as arrays, allow for efficient indexing, providing direct access to
elements based on their index positions.
7. Sequential Access: Linear data structures like arrays and linked lists allow for sequential access to
elements, facilitating ordered data processing.
8. Dynamic Size: Some data structures, like linked lists and dynamic arrays, can adjust their size dynamically
to accommodate varying amounts of data.
9. Hierarchy Representation: Non-linear data structures, such as trees and graphs, represent hierarchical
relationships between elements, useful for modeling complex systems.
10. Support for Multiple Operations: Data structures support a variety of operations, including searching,
sorting, merging, and splitting, making them versatile tools for data manipulation.
11. Ease of Implementation: Many data structures are supported by standard libraries in programming
languages, providing easy-to-use implementations for common data structures.

Arrays in Data Structures

1. Definition
An array is a collection of elements of the same data type stored in contiguous memory locations.
Each element is accessed using an index.
Index starts from 0 in most programming languages (like C, Java, Python).
2. Features
Fixed size (declared before use)
Random access using index
Page 5 of 74
Data Structures and its Applications(B24CS302
Applications(B24CS302)

Homogeneous (all elements are of same type)

3. Declaration & Example
int marks[5] = {85, 90, 78, 88, 92};
Here:
marks → array name
5 → size
{85, 90, 78, 88, 92} → stored values
Array Representation
Example: marks[5] = {85, 90, 78, 88, 92}
Index: 0 1 2 3 4
↓ ↓ ↓ ↓ ↓
Marks: 85 90 78 88 92

Each block in memory is contiguous.

Accessing Array Elements

Array in C provides random access to its elements, which means that we can access any element of the array by
providing the position of the element, called the index.
Syntax:
The index values start from 0 and goes up to array_size-1.
We pass the index inside square brackets [ ] with the name of the array.
Datatype array_name [index];
where, index value lies into this range - (0 ≤ index ≤ size-1).

Page 6 of 74
 Data Structures and its Applications(B24CS302
Applications(B24CS302)

5. Operations on Arrays
Traversal → Visiting all elements

Insertion → Adding new element at index (shifts elements)

// C program to insert an element into an array at a specified position involves shifting existing elements to
accommodate the new element.

#include <stdio.h>
int main( ) {
int arr[100]; // Declare an array with a maximum capacity
int size; // Current number of elements in the array
int element; // The element to be inserted
int position; // The position where the element will be inserted
int i;

printf("Enter the number of elements in the array: ");

scanf("%d", &size);

printf("Enter %d elements:\n",
n", size);
for (i = 0; i < size; i++) {
scanf("%d", &arr[i]);
}

printf("Enter the element to be inserted: ");

scanf("%d", &element);

Page 7 of 74
Data Structures and its Applications(B24CS302)

printf("Enter the position (1 to %d) where the element should be inserted: ", size + 1);
scanf("%d", &position);

// Validate the position

if (position < 1 || position > size + 1) {
printf("Invalid position!\n");
return 1; // Indicate an error
}

// Shift elements to the right to make space for the new element
for (i = size; i >= position - 1; i--) {
arr[i + 1] = arr[i];
}

// Insert the new element at the specified position

arr[position - 1] = element;

// Increment the size of the array

size++;

printf("Array after insertion:\n");

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

return 0; // Indicate successful execution

}
Explanation:

 Initialization: An array arr with a fixed maximum size (e.g., 100) is declared. Variables for the current size,
the element to insert, and the position for insertion are also declared.

 Input: The program prompts the user to enter the initial number of elements and then the elements
themselves. It also asks for the element to be inserted and the position where it should be placed.

 Position Validation: It checks if the entered position is valid (within the bounds of the array, including the
next available spot).

 Shifting Elements: A for loop iterates from the current size down to the position - 1. In each
iteration, arr[i] is moved to arr[i + 1], effectively shifting elements to the right to create an empty spot at
the position - 1 index.

 Insertion: The element is then placed into the arr[position - 1] index.

 Size Update: The size of the array is incremented to reflect the newly added element.

 Output: Finally, the program prints the modified array.

Page 8 of 74
Data Structures and its Applications(B24CS302)

Deletion → Removing element (shifts elements back)

// C program to delete an element from an array at a specified position:

#include <stdio.h>
int main( ) {
int arr[100]; // Declare an array with a maximum size of 100
int size, position, i;

// Get the size of the array from the user

printf("Enter the number of elements in the array: ");
scanf("%d", &size);

// Get the elements of the array from the user

printf("Enter %d elements:\n", size);
for (i = 0; i < size; i++) {
scanf("%d", &arr[i]);
}

// Get the position to delete from the user

printf("Enter the position (1-indexed) of the element to delete: ");
scanf("%d", &position);

// Validate the position

if (position < 1 || position > size) {
printf("Invalid position! Please enter a position between 1 and %d.\n", size);
} else {
// Shift elements to the left to overwrite the deleted element
for (i = position - 1; i < size - 1; i++) {
arr[i] = arr[i + 1];
}

// Decrement the size of the array

size--;

// Print the array after deletion

printf("Array after deleting the element:\n");
for (i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
Page 9 of 74
Data Structures and its Applications(B24CS302)

printf("\n");
}

return 0;
}
Explanation:
 Include Header:
The stdio.h header is included for standard input/output functions like printf and scanf.
 Declare Variables:
 arr[100]: An integer array to store the elements. Its maximum size is set to 100.
 size: Stores the actual number of elements in the array.
 position: Stores the 1-indexed position of the element to be deleted.
 i: Used as a loop counter.
Input Array Elements:
The program prompts the user to enter the size of the array and then the elements themselves.
Input Position to Delete:
The user is asked to enter the 1-indexed position of the element they wish to delete.
Position Validation:
It checks if the entered position is valid (within the bounds of the array). If not, an error message is displayed.
Deletion Logic (Shifting Elements):
 If the position is valid, a for loop iterates from position - 1 (the actual 0-indexed index of the
element to delete) up to size - 1.
 In each iteration, arr[i] is assigned the value of arr[i + 1]. This effectively shifts all elements to the
right of the deleted element one position to the left, overwriting the element at the
specified position.
Decrement Size:
After shifting, the size of the array is decremented because one element has been "removed."
Print Modified Array:
Finally, the program prints the array with the deleted element removed.

Update Array Element

We can update the value of array elements at the given index i in a similar way to accessing an element
by using the array square brackets [ ] and assignment operator (=).
array_name[i]=new_value;

Example:
int main( ) {
intarr[5] = {2, 4, 8, 12, 16};

Page 10 of 74
Data Structures and its Applications(B24CS302)

// Update the first value

// of the array
arr[0] = 1;
printf("%d", arr[0]);
return 0;
}
Searching
Array - Search Operation
Searching an element in the array using a key; The key element sequentially compares every value in the array to
check if the key is present in the array or not.
Algorithm
Consider LA is a linear array with N elements and K is a positive integer such that K<=N. Following is the
algorithm to find an element with a value of ITEM using sequential search.
1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop
Example
Following are the implementations of this operation in various programming languages −
Linear Search → Check one by one
Binary Search → Ef icient (works only on sorted arrays)
Example :Linear Search
#include <stdio.h>
void main( )
{
int LA[ ] = {1,3,5,7,8};
int item = 5, n = 5;
int i = 0, j = 0;
printf("The original array elements are :\n");
for(i = 0; i<n; i++)
{
printf("LA[%d] = %d \n", i, LA[i]);
}
for(i = 0; i<n; i++)
{
if( LA[i] == item )
{

Page 11 of 74
Data Structures and its Applications(B24CS302)

printf("Found element %d at position %d\n", item, i+1);

}
}
}

Binary Search
• Binary Search is used for searching an element in a sorted array.

• Binary search works on the principle of divide and conquer.

• This searching technique looks for a particular element by comparing the middle most element of the
collection.
• It is useful when there are large number of elements in an array.
• The above array is sorted in ascending order. As we know binary search is applied on sorted lists only
for fast searching.
Working of Binary Search in C
Example 1:
Consider an array arr[ ] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} and the key = 23

Page 12 of 74
Data Structures and its Applications(B24CS302)

// C Program to implement binary search using iteration

#include <stdio.h>

int binarySearch(int arr[], int left, int right, int key) {

// Loop will run till left > right. It means that there
// are no elements to consider in the given subarray
while (left <= right) {

// calculating mid point

int mid = left + (right - left) / 2;

// Check if key is present at mid

if (arr[mid] == key) {
return mid;
}

// If key greater than arr[mid], ignore left half

if (arr[mid] < key) {
left = mid + 1;
}

// If key is smaller than or equal to arr[mid],

// ignore right half
else {
right = mid - 1;
}
}

// If we reach here, then element was not present

return -1;
}

int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int size = sizeof(arr) / sizeof(arr[0]);

// Element to be searched

Page 13 of 74
Data Structures and its Applications(B24CS302)

int key = 23;

int result = binarySearch(arr, 0, size - 1, key);

if (result == -1) {
printf("Element is not present in array");
}
else {
printf("Element is present at index %d", result);
}
return 0;
}
Sorting → Bubble, Selection, Merge, Quick etc.

Bubble Sort Algorithm (With Program in C)

The Bubble Sort algorithm is one of the simplest sorting algorithms in computer science. It repeatedly steps
through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process
continues until the list is sorted. Its name comes from the way smaller elements "bubble" to the top of the list. It is
not suitable for large data sets.
Bubble short is majorly used where:
o Complexity does not matter
o Simple and short code is preferred
Here's a step-by-step explanation:
o Compare Adjacent Elements: Start from the first element. Compare it with the next one.
o Swap if Necessary: If the current element is greater than the next, swap them.
o Repeat for All Pairs: Do this for all adjacent elements in the list. After the first pass, the largest element will
"bubble up" to its correct position.
o Ignore the Last Sorted Elements: Repeat the process for the remaining unsorted elements, ignoring the last
sorted ones.
o Stop When No Swaps are Made: If in a complete pass no elements are swapped, the list is sorted.
Algorithm
bubbleSort(array)
n = length(array)
repeat
swapped = false
for i = 1 to n - 1
if array[i - 1] > array[i], then
swap(array[i - 1], array[i])
swapped = true
end if
end for
n=n-1
until not swapped
end bubbleSort
Page 14 of 74
Data Structures and its Applications(B24CS302)

Steps of Bubble Sort

Step 1: Compare the first two elements of the input array.
Step 2: If the first element is greater than the second element, swap them; otherwise, swapping is not required.
Step 3: According to step 2, do the comparison and swapping of the next pair of elements of the input array (the
second and the third element), i.e. if the second element is greater than the third element, do the swapping;
otherwise, not.
Step 4: Continue this process till the end of the input array is reached. At this point, the largest element will be
"bubble up" and get the end of the list.
Step 5: Repeat the steps from 1 to 4, excluding the last element, as it has already achieved its correct position.
Working of Bubble Sort Algorithm
C Program
#include<stdio.h>
#include<stdbool.h>
void print(int a[], int n) //function to print array elements
{
int i;
for(i = 0; i < n; i++) {
printf("%d ",a[i]);
}
}
void bubble(int a[], int n) // function to implement bubble sort
{
int i, j, temp;
bool isSwapped = false;
for(i = 0; i < n; i++) {
isSwapped = false;
for(j = 0; j < n - i - 1; j++) {
if(a[j] > a[j + 1]) {
isSwapped = true;
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
if(!isSwapped) {
// no swapping is done. Hence, break the loop
break;
}
}
}
void main() {
int i, j,temp;
int a[5] = { 15, 16, 11, 13, 14};
int n = sizeof(a)/sizeof(a[0]);
printf("Before sorting array elements are: \n");
print(a, n);
bubble(a, n);

Page 15 of 74
Data Structures and its Applications(B24CS302)

printf("\nAfter sorting array elements are: \n");

print(a, n);

Output:
Before sorting array elements are:
15 16 11 13 14
After sorting array elements are:
11 13 14 15 16
Selection Sort Algorithm :
In selection sort, the smallest value among the unsorted elements of the array is selected in every pass and inserted
into its appropriate position into the array. It is also the simplest algorithm. It is an in-place comparison sorting
algorithm.
In this algorithm, the array is divided into two parts; the first is the sorted part, and the other is the unsorted part.
Initially, the sorted part of the array is empty, and the unsorted part is the given array. The sorted part is placed at
the left, while the unsorted part is placed at the right.
Selection sort is generally used when:
o A small array is to be sorted
o Swapping cost does not matter
o It is compulsory to check all elements
Algorithm
// Function to do selection sort on the array 'a' of size 'n'
function selectionSort(a, s)
// Outer loop: for iterating through the array
// The last element is not included
for j = 0 to s - 1
// Assuming that the current element is the minimum
// storing its index.
minIdx = j
// Inner loop: for finding the minimum element in the unsorted portion
for k = j + 1 to s - 1
// If a smaller element is found
if a[k] < a[minIdx]
// Updating the index of the element, which is the minimum
minIdx = k
// Swapping the minimum element found with the current element
if minIdx != j
swap(a[j], a[minIdx])
// The array is now sorted. return it
return a

Page 16 of 74
Data Structures and its Applications(B24CS302)

Steps of Selection Sort Algorithm

Step 1: Find the smallest element and swap it with the first element of the input array. If the first element is the
smallest, then swapping is not required.
Step 2: Find the smallest element from the remaining elements (the second smallest element) and swap it with the
second element. Again, here also swapping is not required if the second smallest element is the second element of
the array.
Step 3: Repeat the process for the remaining elements of the input array until all elements achieve the correct
position.
Working of Selection Sort Algorithm
C Program
#include <stdio.h>
void selection(int arr[], int n)
{
int i, j, small;
for (i = 0; i < n-1; i++) // One by one move boundary of unsorted subarray
{
small = i; //minimum element in unsorted array
for (j = i+1; j < n; j++)
if (arr[j] < arr[small])
small = j;
// Swap the minimum element with the first element
if (small != i)
{
int temp = arr[small];
arr[small] = arr[i];
arr[i] = temp;
}
}
}
void printArr(int a[], int n) /* function to print the array */
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main()
{
int a[] = {65, 26, 13, 23, 12};
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are: \n");
printArr(a, n);
selection(a, n);
printf("\nAfter sorting array elements are: \n");
printArr(a, n);
return 0;
}

Page 17 of 74
Data Structures and its Applications(B24CS302)

Advantages
 Access of elements (O(1))
Easy to implement and use
Disadvantages

 Fixed size (cannot grow dynamically)

Insertion/Deletion is costly (requires shifting)

Types of Arrays in Data Structures

In Arrays we have 2 types

1.Static Arrays
2. Dynamic Arrays

1. One-Dimensional Array (1D Array)

The general syntax for declaring a one-dimensional array is:
data_type array_name[array_size];

 Stores elements in a single row.

 Accessed using one index.

Example:
int arr[5] = {10, 20, 30, 40, 50};
Diagram:
Index: 0 1 2 3 4
↓ ↓ ↓ ↓ ↓
Value: 10 20 30 40 50
Here:
 Array name: arr
 arr[0] = 10
 arr[1] = 20
 arr[4] = 50
Example :
int arr[5] = {10, 20, 30, 40, 50};
printf("%d", arr[2]); // Output: 30

1. Static Arrays
 Static Arrays are fixed in size.
 Size of static arrays should be determined at compile-time (before run-time).
 No need to delete static arrays, they are deleted automatically after going out of scope.

Page 18 of 74
Data Structures and its Applications(B24CS302)

Constructing Static Array

Static arrays can be constructed like so,
// Construction of array-of-integers with size 10.
int array1[10];

// Construction of array-of-characters with size 150.

char array2[150];
// Construction + Initialization of array-of-doubles with size 4
double physicalConstants[] = { 3.1415926 , 2.717 , 1.618 , 1.0 };

// Construction + Initialization of array-of-characters of size 6

char dna[] = { 'A' , 'A' , 'C' , 'T' , 'G' , 'C' };

Dynamic Arrays
 Dynamic Arrays are allocated on heap.
 Size of dynamic arrays can be determined either at compilation or at run-time (flexible).
 You can construct very large dynamic arrays on heap, unlike static arrays.
 You need to manually delete dynamic arrays after you no longer need them.

Constructing Dynamic Array

// Construction of array-of-integers with arbitrary.
int size = 0;
std::cin >> size; // size determined at run-time.
// You cannot construct static arrays with an arbitrary size like in dynamic array.
int *array1 = new int[ size ];
// Construction of array-of-characters with size 150000 (around 150 Mega Bytes in memory).
char string1 = new char[ 150000 ];

Example 1: Array Input/Output

// Program to take 5 values from the user and store them in an array
// Print the elements stored in the array

#include <stdio.h>
int main( ) {
int values[5];
printf("Enter 5 integers: ");
// taking input and storing it in an array
for(int i = 0; i < 5; ++i) {
scanf("%d", &values[i]);
}

printf("Displaying integers: ");

// printing elements of the array
for(int i = 0; i < 5; ++i) {
printf("%d\n", values[i]);
}
return 0;
}
Page 19 of 74
Data Structures and its Applications(B24CS302)

Example 2: Calculate Average

// Program to find the average of n numbers using arrays
#include <stdio.h>
int main( )
{

int marks[10], i, n, sum = 0;

double average;
printf("Enter number of elements: ");
scanf("%d", &n);
for(i=0; i < n; ++i)
{
printf("Enter number%d: ",i+1);
scanf("%d", &marks[i]);
// adding integers entered by the user to the sum variable
sum += marks[i];
}

// explicitly convert the sum to double

// then calculate average
average = (double) sum / n;
printf("Average = %.2lf", average);
return 0;
}

Example 3 : Sum of All Elements in Array

Adds and prints the sum of array elements.

#include <stdio.h>
int main( ) {
int arr[5] = {5, 10, 15, 20, 25};
int sum = 0;

for (int i = 0; i < 5; i++) {

sum += arr[i];
}

printf("Sum = %d", sum);

return 0;
}
Example 4 : Finds and prints the largest value in the array.
#include <stdio.h>

int main( ) {
int data[5] = {45, 72, 29, 90, 61};
int max = data[0];

for (int i = 1; i < 5; i++) {

if (data[i] > max) {
max = data[i];
}
Page 20 of 74
Data Structures and its Applications(B24CS302)

printf("Maximum = %d", max);

return 0;
}
Arrays and Pointers

Arrays and Pointers are closely related to each other such that we can use pointers to perform all the
possible operations of the array. The array name is a constant pointer to the first element of the array and
the array decays to the pointers when passed to the function.

Example :
#include <stdio.h>

int main() {

int arr[5] = { 10, 20, 30, 40, 50 };

int* ptr = &arr[0];

// Address store inside

// name
printf("%p\n", arr);

// Print the address which

// is pointed by pointer ptr
printf("%p\n", ptr);
return 0;
}

Passing Array to Function

In C, arrays are passed to functions using pointers, as the array name decays to a pointer to the first
element. So, we also need to pass the size of the array to the function.

Example:
#include <stdio.h>
// Functions that take array as argument
void printArray(int arr[ ], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
}
int main() {
int arr[] = {2, 4, 8, 12, 16};
int n = sizeof(arr) / sizeof(arr[0]);
// Passing array
printArray(arr, n);
return 0;
}

Page 21 of 74
Data Structures and its Applications(B24CS302
Applications(B24CS302)

2. Two-Dimensional
Dimensional Array (2D Array)
Declaration:
The general syntax for declaring a two-dimensional
two array is:

data_type array_name[rows][columns];
 data_type: Specifies the type of elements the array will store (e.g., int, float, char).
 array_name: The name given to the array.
 [rows]: Defines the number of rows in the array.
 [columns]: Defines the number of columns in the array.

 Stores elements in a rows × columns format (like a matrix).

 Accessed using two indices.
Example:
int matrix[2][3] = {{1, 2, 3}, {4, 5, 6}};
Diagram:
Column → 0 1 2
Row 0 → [1 2 3]
Row 1 → [4 5 6]
Example :
int matrix[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
Initialization of a 2d array
// Different ways to initialize two-dimensional
dimensional array
int c[2][3] = {{1, 3, 0}, {-1, 5, 9}};
int c[][3] = {{1, 3, 0}, {-1, 5, 9}};
int c[2][3] = {1, 3, 0, -1, 5, 9};

Example:

Page 22 of 74
Data Structures and its Applications(B24CS302
Applications(B24CS302)

int matrix[2][3] = { {1, 4, 2}, {3, 6, 8} };

matrix[0][0] = 9;
printf("%d", matrix[0][0]); // Now outputs 9 instead of 1

Example 1 :
Sum of two matrices
// C program
am to find the sum of two matrices of order 2*2

#include <stdio.h>
int main( )
{
float a[2][2], b[2][2], result[2][2];

// Taking input using nested for loop

printf("Enter elements of 1st matrix\n");
matrix
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
{
printf("Enter a[%d][%d]: ", i + 1, j + 1);
scanf("%f", &a[i][j]);
}

// Taking input using nested for loop

printf("Enter elements of 2nd matrix\n");
matrix
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
{
printf("Enter b%d%d: ", i + 1, j + 1);
scanf("%f", &b[i][j]);
}

// adding corresponding elements of two arrays

for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
{
result[i][j] = a[i][j] + b[i][j];
}

// Displaying the sum

printf("\nSum Of Matrix:");

for (int i = 0; i < 2; ++i)

for (int j = 0; j < 2; ++j)

Page 23 of 74
Data Structures and its Applications(B24CS302)

{
printf("%.1f\t", result[i][j]);

if (j == 1)
printf("\n");
}
return 0;
}

Example 2 :
Demonstrating the use of Two Dimensional Array(Transpose of a matrix) :
#include <stdio.h>
int main( ) {
int rows, cols;

// Input the dimensions of the matrix

printf("Enter the number of rows and columns of the matrix: ");
scanf("%d %d", &rows, &cols);

int matrix[rows][cols], transpose[cols][rows];

// Input the elements of the matrix

printf("Enter the elements of the matrix:\n");
for (inti = 0; i< rows; i++) {
for (int j = 0; j < cols; j++) {
printf("Element [%d][%d]: ", i + 1, j + 1);
scanf("%d", &matrix[i][j]);
}
}

// Compute the transpose

for (inti = 0; i< rows; i++) {
for (int j = 0; j < cols; j++) {
transpose[j][i] = matrix[i][j];
}
}

// Print the original matrix

printf("\nOriginal Matrix:\n");
for (inti = 0; i< rows; i++) {
for (int j = 0; j < cols; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}

// Print the transposed matrix

printf("\nTranspose of the Matrix:\n");
for (inti = 0; i< cols; i++) {
for (int j = 0; j < rows; j++) {
printf("%d ", transpose[i][j]);
}
printf("\n");
}

Page 24 of 74
Data Structures and its Applications(B24CS302)

return 0;
}
Jagged Array

A jagged array in C is an array of arrays where each inner array (or "row") can have a different length. This
contrasts with a traditional 2D array in C, which is always rectangular, meaning all rows have the same number of
columns.

Implementation in C:

Jagged arrays in C are typically implemented using pointers. You create an array of pointers, and each pointer in
that array points to a dynamically allocated 1D array representing a "row."
Example:

#include <stdio.h>
#include <stdlib.h>

int main( ) {
// Declare an array of pointers to integers (for 3 rows)
int **jaggedArray;
int numRows = 3;

// Dynamically allocate memory for the array of pointers

jaggedArray = (int **)malloc(numRows * sizeof(int *));

// Define the lengths of each row

int rowLengths[] = {3, 2, 4};

// Allocate memory for each individual row and populate it

for (int i = 0; i < numRows; i++) {
jaggedArray[i] = (int *)malloc(rowLengths[i] * sizeof(int));
// Populate the row (example values)
for (int j = 0; j < rowLengths[i]; j++) {
jaggedArray[i][j] = (i + 1) * 10 + j;
}
}

// Print the jagged array

printf("Jagged Array:\n");
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < rowLengths[i]; j++) {
printf("%d ", jaggedArray[i][j]);
}
printf("\n");
}

// Free the allocated memory

for (int i = 0; i < numRows; i++) {
free(jaggedArray[i]);
}
free(jaggedArray);

return 0;
}
Explanation:

Page 25 of 74
 Data Structures and its Applications(B24CS302)

 **`int ** jaggedArray;`**: This declares jaggedArray as a pointer to a pointer to an integer. It will hold the
address of the first element of an array of int* (pointers to integers).
 malloc(numRows * sizeof(int *));:
This allocates memory for an array of numRows number of int* pointers. Each of these pointers will eventually
point to a row of the jagged array.
 malloc(rowLengths[i] * sizeof(int));:
Inside the loop, for each row i, this allocates memory for rowLengths[i] number of integers. This creates a 1D array
of the specified length for that particular row.
 jaggedArray[i][j]:
This syntax allows you to access individual elements of the jagged array, similar to a regular 2D array, even though
the underlying memory structure is different.
 Memory Management:
It is crucial to free the dynamically allocated memory for each row and then for the array of pointers to prevent
memory leaks.

Pointers & 2D array

Pointers in C
A pointer is a variable that stores the memory address of another variable. Instead of holding a direct
value, it holds the address where the value is stored in memory. It is the backbone of low-level memory
manipulation in C. Accessing the pointer directly will just give us the address that is stored in the pointer.
For example,
#include <stdio.h>

int main( ) {

// Normal Variable
int var = 10;

// Pointer Variable ptr that

// stores address of var
int* ptr = &var;

// Directly accessing ptr will

// give us an address
printf("%d", ptr);

return 0;
}

Dangling Pointers in C
 The most common bugs related to pointers and memory management is dangling/wild pointers.
 Sometimes the programmer fails to initialize the pointer with a valid address, then this type of
initialized pointer is known as a dangling pointer in C.
 Dangling pointer occurs at the time of the object destruction when the object is deleted or de-allocated
from memory without modifying the value of the pointer.
 In this case, the pointer is pointing to the memory, which is de-allocated. The dangling pointer can point
to the memory, which contains either the program code or the code of the operating system.
 If we assign the value to this pointer, then it overwrites the value of the program code or operating
system instructions; in such cases, the program will show the undesirable result or may even crash.

Page 26 of 74
 Data Structures and its Applications(B24CS302)

 If the memory is re-allocated to some other process, then we dereference the dangling pointer will
cause the segmentation faults.

The following examples shows the working of dangling pointer:-

In the above figure, we can observe that the Pointer 3 is a dangling pointer. Pointer 1 and Pointer 2 are
the pointers that point to the allocated objects, i.e., Object 1 and Object 2, respectively. Pointer 3 is a
dangling pointer as it points to the de-allocated object.
Let's understand the dangling pointer through some C programs.
Using free() function to de-allocate the memory.
1. #include <stdio.h>
2. int main( )
3. {
4. int *ptr=(int *)malloc(sizeof(int));
5. int a=560;
6. ptr=&a;
7. free(ptr);
8. return 0;
9. }
In the above code, we have created two variables, i.e., *ptr and a where 'ptr' is a pointer and 'a' is a
integer variable. The *ptr is a pointer variable which is created with the help of malloc() function. As we
know that malloc() function returns void, so we use int * to convert void pointer into int pointer.
The statement int *ptr=(int *)malloc(sizeof(int)); will allocate the memory with 4 bytes shown in the
below image:

The statement free(ptr) de-allocates the memory as shown in the below image with a cross sign, and 'ptr'
pointer becomes dangling as it is pointing to the de-allocated memory.

Page 27 of 74
Data Structures and its Applications(B24CS302)

If we assign the NULL value to the 'ptr', then 'ptr' will not point to the deleted memory. Therefore, we can
say that ptr is not a dangling pointer, as shown in the below image:

Variable goes out of the scope

When the variable goes out of the scope then the pointer pointing to the variable becomes a dangling
pointer.
#include<stdio.h>
int main( )
{
char *str;
{
char a = ?A?;
str = &a;
}
// a falls out of scope
// str is now a dangling pointer
printf("%s", *str);
}
In the above code, we did the following steps:
o First, we declare the pointer variable named 'str'.
o In the inner scope, we declare a character variable. The str pointer contains the address of the
variable 'a'.
o When the control comes out of the inner scope, 'a' variable will no longer be available, so str
points to the de-allocated memory. It means that the str pointer becomes the dangling pointer.
Function call
Example.
#include <stdio.h>
int *fun( ){
int y=10;
return &y;
}
int main( )
{
int *p=fun( );

Page 28 of 74
Data Structures and its Applications(B24CS302)

printf("%d", *p);
return 0;
}
In the above code, we did the following steps:
o First, we create the main( ) function in which we have declared 'p' pointer that contains the return
value of the fun( ).
o When the fun( ) is called, then the control moves to the context of the int *fun(), the fun() returns
the address of the 'y' variable.
o When control comes back to the context of the main() function, it means the variable 'y' is no
longer available. Therefore, we can say that the 'p' pointer is a dangling pointer as it points to the
de-allocated memory.
Output

Let's represent the working of the above code diagrammatically.

Let's consider another example of a dangling pointer.

1. #include <stdio.h>
2. int *fun( )
3. {
4. static int y=10;
5. return &y;
6. }
7. int main( )
8. {
9. int *p=fun( );
10. printf("%d", *p);
11. return 0;
12. }
The above code is similar to the previous one but the only difference is that the variable 'y' is static. We
know that static variable stores in the global memory.

Page 29 of 74
Data Structures and its Applications(B24CS302)

Output

Now, we represent the working of the above code diagrammatically.

The above diagram shows the stack memory. First, the fun( ) function is called, then the control moves to
the context of the int *fun(). As 'y' is a static variable, so it stores in the global memory; Its scope is
available throughout the program. When the address value is returned, then the control comes back to
the context of the main(). The pointer 'p' contains the address of 'y', i.e., 100. When we print the value of
'*p', then it prints the value of 'y', i.e., 10. Therefore, we can say that the pointer 'p' is not a dangling
pointer as it contains the address of the variable which is stored in the global memory.
Avoiding Dangling Pointer Errors
The dangling pointer errors can be avoided by initializing the pointer to the NULL value. If we assign
the NULL value to the pointer, then the pointer will not point to the de-allocated memory.
Assigning NULL value to the pointer means that the pointer is not pointing to any memory location.

A 2D array as collection of several one dimensional arrays.

So abc[0] would have the address of first element of the first row (if we consider the above diagram number 1).
similarlyabc[1] would have the address of the first element of the second row. To understand it better, lets write a

Example 3:
#include <stdio.h>
int main()
{
int abc[5][4] ={
{0,1,2,3},
{4,5,6,7},
{8,9,10,11},
{12,13,14,15},
{16,17,18,19}
};
for (int i=0; i<=4; i++)
{

printf("%d ",abc[i]);
Page 30 of 74
Data Structures and its Applications(B24CS302
Applications(B24CS302)

}
return 0;
}
3. Multi-Dimensional
Dimensional Array (3D or more)
 Stores data in 3 or more dimensions.
dimensions
 Accessed using multiple indices.
indices
 Example: 3D array can be seen as a “stack of matrices.”
Three-dimensional array:
A 3-D Multidimensionalal array contains three dimensions, so it can be considered an array of two
two-
dimensional arrays.

Example:
int cube[2][2][2] =
{
{{1,2}, {3,4}},
{{5,6}, {7,8}}
};
Diagram (3D Array Concept):
Layer 0: Layer 1:
[1 2] [5 6]
[3 4] [7 8]

Dynamic Array in C(Dynamic

(Dynamic Memory Allocation)

Array in C is static in nature, so its size should be known at compile time and we can't change the size of
the array after its declaration. Due to this, we may encounter situations where our array doesn't have
enough space left for required elements or we allotted more than the required memory leading to
memory wastage. To solve this problem, dynamic arrays come into the picture.
A Dynamic Array is allocated memory at runtime and its size can be changed later in the program.
We can create a dynamic array in C by using the following methods:
1. Using malloc() Function
2. Using calloc() Function
3. Resizing Array Using realloc() Function
4. Using Free( ) Function
5. Using Variable Length Arrays(VLAs)
6. Using Flexible
xible Array Member.
Page 31 of 74
Data Structures and its Applications(B24CS302)

1. Dynamic Array Using malloc() Function

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. It is defined inside <stdlib.h> header file.

Syntax:
ptr = (cast-type*) malloc(byte-size);
We can use this function to create a dynamic array of any type by simply allocating a memory block of
some size and then typecasting the returned void pointer to the pointer of the required type.
Example:
ptr = (int*) malloc(100 * sizeof(int));

In the above example, we have created a dynamic array of type int and size 100 elements.
Note: It is to be noted that if malloc fails to allocate the required memory, it returns the NULL pointer. So,
it is a good practice to check for NULL pointer to see if the memory is successfully allocated or not.

Example:

// C program to create dynamic array using malloc() function

#include <stdio.h>
#include <stdlib.h>

int main()
{

// address of the block created hold by this pointer

int* ptr;
int size;

// Size of the array

printf("Enter size of elements:");
scanf("%d", &size);

// Memory allocates dynamically using malloc()

ptr = (int*)malloc(size * sizeof(int));

// Checking for memory allocation

if (ptr == NULL) {
printf("Memory not allocated.\n");
}
else {

// Memory allocated
printf("Memory successfully allocated using "
"malloc.\n");

// Get the elements of the array

for (int j = 0; j < size; ++j) {
Page 32 of 74
Data Structures and its Applications(B24CS302)

ptr[j] = j + 1;
}

// Print the elements of the array

printf("The elements of the array are: ");
for (int k = 0; k < size; ++k) {
printf("%d, ", ptr[k]);
}
}

return 0;
}

Output:
Enter size of elements:5
Memory successfully allocated using malloc.
The elements of the array are: 1, 2, 3, 4, 5,

2. Dynamic Array Using calloc() Function

The “calloc” or “contiguous allocation” method in C is used to dynamically allocate the specified number of
blocks of memory of the specified type and initialized each block with a default value of 0.
The process of creating a dynamic array using calloc() is similar to the malloc() method. The difference is
that calloc() takes arguments instead of one as compared to malloc(). Here, we provide the size of each
element and the number of elements required in the dynamic array. Also, each element in the array is
initialized to zero.

Syntax:
ptr = (cast-type*)calloc(n, element-size);
Example:
ptr = (int*) calloc(5, sizeof(float));

In the above example, we have created a dynamic array of type float having five elements.
Let's take another example to create a dynamic array using the calloc() method.

Example:
// C program to create dynamic array using calloc() function

#include <stdio.h>
#include <stdlib.h>

int main()
{
// address of the block created hold by this pointer
int* ptr;
int size;

// Size of the array

printf("Enter size of elements:");
scanf("%d", &size);

Page 33 of 74
Data Structures and its Applications(B24CS302)

// Memory allocates dynamically using calloc()

ptr = (int*)calloc(size, sizeof(int));

// Checking for memory allocation

if (ptr == NULL) {
printf("Memory not allocated.\n");
}
else {

// Memory allocated
printf("Memory successfully allocated using "
"malloc.\n");

// Get the elements of the array

for (int j = 0; j < size; ++j) {
ptr[j] = j + 1;
}

// Print the elements of the array

printf("The elements of the array are: ");
for (int k = 0; k < size; ++k) {
printf("%d, ", ptr[k]);
}
}

return 0;
}

Output:
Enter size of elements:6
Memory successfully allocated using malloc.
The elements of the array are: 1, 2, 3, 4, 5, 6,
3. Dynamically Resizing Array Using realloc() Function

The “realloc” or “re-allocation” method in C is used to dynamically change the memory allocation of a
previously allocated memory.
Using this function we can create a new array or change the size of an already existing array.

Syntax:
ptr = realloc(ptr, newSize);

Example :
// C program to resize dynamic array using realloc()function
#include <stdio.h>
#include <stdlib.h>

int main()
{

// address of the block created hold by this pointer

int* ptr;
Page 34 of 74
Data Structures and its Applications(B24CS302)

int size = 5;

// Memory allocates dynamically using calloc()

ptr = (int*)calloc(size, sizeof(int));

if (ptr == NULL) {
printf("Memory not allocated.\n");
exit(0);
}
else {
printf("Memory successfully allocated using "
"calloc.\n");
}

// inserting elements
for (int j = 0; j < size; ++j) {
ptr[j] = j + 1;
}

printf("The elements of the array are: ");

for (int k = 0; k < size; ++k) {
printf("%d, ", ptr[k]);
}

printf("\n");
size = 10;
int *temp = ptr;

// using realloc
ptr = realloc(ptr, size * sizeof(int));
if (!ptr) {
printf("Memory Re-allocation failed.");
ptr = temp;
}
else {
printf("Memory successfully re-allocated using "
"realloc.\n");
}

// inserting new elements

for (int j = 5; j < size; ++j) {
ptr[j] = j + 10;
}

printf("The new elements of the array are: ");

for (int k = 0; k < size; ++k) {
printf("%d, ", ptr[k]);
}
return 0;
}
Page 35 of 74
Data Structures and its Applications(B24CS302)

Output
Memory successfully allocated using calloc.
The elements of the array are: 1, 2, 3, 4, 5,
Memory successfully re-allocated using realloc.
The new elements of the array are: 1, 2, 3, 4, 5, 15, 16, 17, 18, 19,

4. Free( ) Function :
The free() function in C is used to deallocate dynamically allocated memory. It is a crucial part of memory
management in C, preventing memory leaks and ensuring efficient resource utilization.
Purpose:
 To release memory previously allocated by functions like malloc(), calloc(), or realloc() back to the
system.
 To prevent memory leaks, which occur when dynamically allocated memory is no longer needed but
remains occupied, consuming system resources.
Syntax:
void free(void *ptr);
 ptr: A pointer to the block of memory that was previously allocated by malloc(), calloc(), or
realloc( ).

How it works:
 When free() is called with a valid pointer to a dynamically allocated memory block, the memory is
returned to the heap, making it available for future allocations.
 The free() function does not erase the data that was stored in the memory block; it simply marks the
memory as available for reuse.
 If ptr is NULL, free() does nothing and simply returns.

Structures and Unions

Structures
Structures (also called structs) are a way to group several related variables into one place.
Each variable in the structure is known as a member of the structure.
Unlike an array, a structure can contain many different data types (int, float, char, etc.).
Create a Structure
You can create a structure by using the struct keyword and declare each of its members inside curly braces:
struct MyStructure { // Structure declaration
int myNum; // Member (int variable)
char myLetter; // Member (char variable)
}; // End the structure with a semicolon
To access the structure, you must create a variable of it.
Use the struct keyword inside the main() method, followed by the name of the structure and then the name of the
structure variable:

Page 36 of 74
Data Structures and its Applications(B24CS302)

Create a struct variable with the name "s1":

struct myStructure {
int myNum;
char myLetter;
};

int main( ) {
struct myStructure s1;
return 0;
}

Access Structure Members

To access members of a structure, use the dot syntax (.):
Example
// Create a structure called myStructure
struct myStructure {
int myNum;
char myLetter;
};
int main( ) {
// Create a structure variable of myStructure called s1
struct myStructure s1;

// Assign values to members of s1

s1.myNum = 13;
s1.myLetter = 'B';

// Print values
printf("My number: %d\n", s1.myNum);
printf("My letter: %c\n", s1.myLetter);

return 0;
}

Type defined Structures

In C programming, a "type-defined structure" refers to using the typedef keyword to create an alias (a new,
shorter name) for a struct data type. This simplifies the declaration of variables of that structure type, making the
code more readable.
Here's how to define a structure using typedef:

1. Using typedef with an anonymous struct:

This is a common and concise way to define a new type name directly for a structure without giving
the struct itself a separate name.
typedef struct {
int id;
char name[50];
float gpa;
} Student; // Student is now an alias for this structure
Page 37 of 74
 Data Structures and its Applications(B24CS302)

Now, instead of writing struct Student_struct_name student1;, you can simply write Student student1; to declare a
variable of this structure type.

2. Using typedef with a named struct:

You can also define a named struct first and then use typedef to create an alias for it. This can be useful if you need
to refer to the struct by its original name in some contexts (e.g., for forward declarations or self-referential
structures).

struct Person_struct {
char name[50];
int age;
};

typedef struct Person_struct Person; // Person is now an alias for struct Person_struct
Now, you can declare variables using either struct Person_struct p1; or Person p1;.

Benefits of using typedef with structures:

 Improved readability: Shorter, more descriptive type names make the code easier to understand.
 Reduced typing: You don't need to repeatedly type the struct keyword.
 Easier code maintenance: If the underlying structure definition changes, you only need to update
the typedef definition, not every instance where the structure is used.

Self-referential Structures:-
A self-referential structure is a struct data type in C, where one or more of its elements are pointer to variables of
its own type. Self-referential user-defined types are of immense use in C programming. They are extensively used
to build complex and dynamic data structures such as linked lists and trees.
In C programming, an array is allocated the required memory at compile-time and the array size cannot be
modified during the runtime. Self-referential structures let you emulate the arrays by handling the size
dynamically.

File management systems in Operating Systems are built upon dynamically constructed tree structures, which are
manipulated by self-referential structures. Self-referential structures are also employed in many complex
algorithms.
Defining a Self-referential Structure
A general syntax of defining a self-referential structure is as follows −
strut typename{
type var1;
type var2;
...
...
struct typename *var3;
}

Page 38 of 74
 Data Structures and its Applications(B24CS302)

Let us understand how a self-referential structure is used, with the help of the following example. We define a struct
type called mystruct. It has an integer element "a" and "b" is the pointer to mystruct type itself.
We declare three variables of mystruct type −
struct mystruct x = {10, NULL}, y = {20, NULL}, z = {30, NULL};
Next, we declare three "mystruct" pointers and assign the references x, y and z to them.
struct mystruct * p1, *p2, *p3;
p1 = &x;
p2 = &y;
p3 = &z;
The variables "x", "y" and "z" are unrelated as they will be located at random locations, unlike the array where all its
elements are in adjacent locations.

Examples of Self-referential Structure

Example 1
To explicitly establish a link between the three variable, we can store the address of "y" in "x" and the address of "z"
in "y". Let us implement this in the following program –
int main( )
{
struct mystruct x = {10, NULL}, y = {20, NULL}, z = {30, NULL};
struct mystruct * p1, *p2, *p3;
p1 = &x; p2 = &y;
p3 = &z; x.b = p2;
y.b = p3;
printf("Address of x: %d a: %d Address of next: %d\n", p1, x.a, x.b);
printf("Address of y: %d a: %d Address of next: %d\n", p2, y.a, y.b);
printf("Address of z: %d a: %d Address of next: %d\n", p3, z.a, z.b);
return 0;
}
Example 2

We use the malloc() function to dynamically allocate memory whose address is stored in pointer
variables. We then establish links between the three nodes as shown below −
#include <stdio.h>
#include <stdlib.h>
struct mystruct
{
int a;
struct mystruct *b;
};

int main()

Page 39 of 74
Data Structures and its Applications(B24CS302)

struct mystruct *p1, *p2, *p3;

p1 = (struct mystruct *)malloc(sizeof(struct mystruct));

p2 = (struct mystruct *)malloc(sizeof(struct mystruct));
p3 = (struct mystruct *)malloc(sizeof(struct mystruct));

p1 -> a = 10; p1->b=NULL;

p2 -> a = 20; p2->b=NULL;
p3 -> a =30; p3->b=NULL;

p1 -> b = p2;
p2 -> b = p3;

printf("Add of x: %d a: %d add of next: %d\n", p1, p1->a, p1->b);

printf("add of y: %d a: %d add of next: %d\n", p2, p2->a, p2->b);
printf("add of z: %d a: %d add of next: %d\n", p3, p3->a, p3->b);

return 0;
}
Output
Run the code and check its output −
Add of x: 10032160 a: 10 add of next: 10032192
add of y: 10032192 a: 20 add of next: 10032224
add of z: 10032224 a: 30 add of next: 0

Structures and Functions in C

In C programming, struct is a derived data type. Just as we can pass arguments of primary data types, a variable of
struct data type can also be passed to a function. You can also pass structures using call by value and call by
reference methods. A function in C may also return a struct data type.
Read this chapter to understand the following concepts −
 How to pass elements of struct type
 How to pass a struct variable
 How to return struct from a function
 How to return a struct pointer
Let's start with the first one and learn how to pass elements of struct type.
How to Pass Struct Elements
A derived type is a combination of one or more elements of any of the primary types as well as another derived
type. It is possible to pass elements to a function, either by value or by reference.
Example
In the following example, we have a derived type called "rectangle" with two elements. We have a struct variable
"r" with the elements "r.len" and "l.brd" and they are passed to a function. The area() function then computes the
area of the rectangle.

#include <stdio.h>
struct rectangle
{
float len, brd;
};

Page 40 of 74
Data Structures and its Applications(B24CS302)

int area(float, float);

int main()
{

struct rectangle r;
r.len = 10.50; r.brd = 20.5;
area(r.len, r.brd);

return 0;
}

int area(float a, float b){

double area = (double)(a*b);

printf("Length: %f \nBreadth: %f \nArea: %lf\n", a, b, area);

return 0;
}
Output
When you run this code, it will produce the following output −
Length: 10.500000
Breadth: 20.500000
Area: 215.250000

How to Pass a Struct Variable

Let us modify the above example to pass the struct variable itself (instead of its elements) to the area() function.
The rectangle struct type also has an additional element called "area".
Example
Inside the function, the elements of the struct variable are accessed though the dot operator (.) and the area is
calculated.
Open Compiler
#include <stdio.h>

struct rectangle{
float len, brd;
double area;
};

int area(struct rectangle);

int main(){

struct rectangle r;
r.len = 10.50; r.brd = 20.5;
area(r);

return 0;
}

int area(struct rectangle r){

Page 41 of 74
Data Structures and its Applications(B24CS302)

r.area = (double)(r.len*r.brd);
printf("Length: %f \nBreadth: %f \nArea: %lf\n", r.len, r.brd, r.area);

return 0;
}
Output
Run the code and check its output −
Length: 10.500000
Breadth: 20.500000
Area: 215.250000

How to Return Struct from a Function

We know that a function in C can return a value of any type. In this example, the area() function is defined to return
a struct variable.
Example
Inside the main() fuction, the inputs for the length and the breadth are passed to the area() function. Inside the
area() function, the area is computed and a struct variable is populated and returned to the main() function, where
its elements are displayed.
Open Compiler
#include <stdio.h>

struct rectangle {
float len, brd;
double area;
};

struct rectangle area(float x, float y);

int main ( ){

struct rectangle r;
float x, y;

x = 10.5; y = 20.5;
r = area(x, y);

printf("Length: %f \n Breadth: %f \n Area: %lf\n", r.len, r.brd, r.area);

return 0;
}
struct rectangle area(float x, float y){

double area = (double)(x*y);

struct rectangle r = {x, y, area};
return r;
}
Output
When you run this code, it will produce the following output −
Length: 10.500000
Breadth: 20.500000
Page 42 of 74
Data Structures and its Applications(B24CS302)

Area: 215.250000

How to Pass a Struct by Reference

In C language, a function may be defined to have its arguments passed by value or reference. A reference is
the pointer to an existing variable.

Example
In this example, a struct variable of "rectangle" type is declared in main() and its address is passed to a user-
defined function called area().
When the area() function is called, it can use the elements of the variable with the indirection operator (). It
computes the result and assigns it to the area element "r area".

#include <stdio.h>

struct rectangle{
float len, brd;
double area;
};

int area(struct rectangle *);

int main(){

struct rectangle r;
r.len = 10.50; r.brd = 20.5;
area(&r);

return 0;
}

int area(struct rectangle *r){

r -> area = (double)(r -> len * r -> brd);

printf("Length: %f \nBreadth: %f \nArea: %lf\n", r -> len, r -> brd, r -> area);

return 0;
}
Output
Run the code and check its output −
Length: 10.500000
Breadth: 20.500000
Area: 215.250000

How to Return a Struct Pointer

Let us rewrite the above code to define the area() function and return a pointer to a struct of rectangle data type.
Example

Page 43 of 74
Data Structures and its Applications(B24CS302)

The area() function has two call-by-value arguments. The main() function reads the length and breadth from the
user and passes them to the area() function, which populates a struct variable and passes its reference back to the
main() function.

#include <stdio.h>

struct rectangle {
float len, brd;
double area;
};

struct rectangle * area(float x, float y);

int main (){

struct rectangle *r;

float x, y;

x = 10.5; y = 20.5;
r = area(x, y);
printf("Length: %f \n Breadth: %f \n Area: %lf\n", r->len, r->brd, r->area);

return 0;
}

struct rectangle * area(float x, float y){

double area = (double)(x*y);

static struct rectangle r;
r.len = x; r.brd = y; r.area = area;

return &r;
}
Output
When you run this code, it will produce the following output −
Length: 10.500000
Breadth: 20.500000
Area: 215.250000

Unions in C

A union is a special data type available in C that allows to store different data types in the same memory location.
You can define a union with many members, but only one member can contain a value at any given time. Unions
provide an efficient way of using the same memory location for multiple purpose.
All the members of a union share the same memory location. Therefore, if we need to use the same memory
location for two or more members, then union is the best data type for that. The largest union member defines the
size of the union.

Defining a Union

Page 44 of 74
Data Structures and its Applications(B24CS302)

Union variables are created in same manner as structure variables. The keyword union is used to define unions in
C language.
Syntax

The syntax to define a union in C language −

union [union tag]{
member definition;
member definition;
...
member definition;
} [one or more union variables];

The "union tag" is optional and each member definition is a normal variable definition, such as "int i;" or "float f;"
or any other valid variable definition.
At the end of the union's definition, before the final semicolon, you can specify one or more union variables.

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

Syntax
Here is the syntax to access the members of a union in C language −
union_name.member_name;

Initialization of Union Members

You can initialize the members of the union by assigning the value to them using the assignment (=) operator.

Syntax

The syntax to initialize members of union −

union_variable.member_name = value;

Example
The following code statement shows to initialization of the member "i" of union "data" −
data.i = 10;

Examples of Union
Example 1
The following example shows how to use unions in a program −
Open Compiler
#include <stdio.h>
#include <string.h>

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

Page 45 of 74
Data Structures and its Applications(B24CS302)

int main(){
union Data data;

data.i = 10;
data.f = 220.5;
strcpy(data.str, "C Programming");

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

printf("data.f: %f \n", data.f);
printf("data.str: %s \n", data.str);
return 0;
}
Output
When the above code is compiled and executed, it produces the following result −
data.i: 1917853763
data.f: 4122360580327794860452759994368.000000
data.str: C Programming

Here, we can see that the values of i and f (members of the union) show garbage values 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.

Example 2:

#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(data.str, "C Programming");
printf("data.str: %s \n", data.str);
return 0;
}
Output
When the above code is compiled and executed, it produces the following result −
data.i: 10
data.f: 220.500000
data.str: C Programming
Here, the values of all the Union members are getting printed very well because one member is being used at a
time.

Size of a Union
Page 46 of 74
Data Structures and its Applications(B24CS302)

The size of a union is the size of its largest member. For example, if a union contains two members
of char and int types. In that case, the size of the union will be the size of int because int is the largest member.
You can use the sizeof( ) operator to get the size of a union.

Example

In the following example, we are printing the size of a union −

Open Compiler
#include <stdio.h>

// Define a union
union Data {
int a;
float b;
char c[20];
};

int main() {
union Data data;
// Printing the size of the each member of union
printf("Size of a: %lu bytes\n", sizeof(data.a));
printf("Size of b: %lu bytes\n", sizeof(data.b));
printf("Size of c: %lu bytes\n", sizeof(data.c));
// Printing the size of the union
printf("Size of union: %lu bytes\n", sizeof(data));
return 0;
}
Output
When you compile and execute the code, it will produce the following output −
Size of a: 4 bytes
Size of b: 4 bytes
Size of c: 20 bytes
Size of union: 20 bytes

Difference between Structure and Union

Parameter Structure Union

A structure is a user-defined data type A union is a user-defined data type that allows
that groups different data types into a storing different data types at the same
Definition single entity. memory location.

The keyword struct is used to define a

The keyword union is used to define a union
Keyword structure

The size is the sum of the sizes of all The size is equal to the size of the largest
Size members, with padding if necessary. member, with possible padding.

Page 47 of 74
Data Structures and its Applications(B24CS302)

Parameter Structure Union

Memory Each member within a structure is Memory allocated is shared by individual

Allocation allocated unique storage area of location. members of union.

Data No data overlap as members are Full data overlap as members shares the same
Overlap independent. memory.

Accessing Individual member can be accessed at a

Only one member can be accessed at a time.
Members time.

Both structures and unions are composite data types in C programming. The most significant difference between a
structure and a union is the way they store their data. A structure stores each member in separate memory
locations, whereas a union stores all its members in the same memory location.
Here is a definition of union type called myunion −
union myunion{
int a;
double b;
char c;
};
The definition of a union is similar to the definition of a structure. A definition of "struct type mystruct" with the
same elements looks like this −
struct mystruct{
int a;
double b;
char c;
};
The main difference between a struct and a union is the size of the variables. The compiler allocates the memory to
a struct variable, to be able to store the values for all the elements. In mystruct, there are three elements − an int, a
double, and char, requiring 13 bytes (4 + 8 + 1). Hence, sizeof(struct mystruct) returns 13.

For a union type variable, the compiler allocates a chunk of memory of the size enough to accommodate the
element of the largest byte size.
The myunion type has an int, a double and a char element. Out of the three elements, the size of the double variable
is the largest, i.e., 8. Hence, sizeof(union myunion) returns 8.

Polynomial representation using arrays:-

Polynomials and Sparse Matrix are two critical applications of arrays and linked lists. A polynomial
comprises different terms, each with a coefficient and an exponent. This tutorial includes the
representation of polynomials using linked lists and arrays.

What is a Polynomial?

Page 48 of 74
Data Structures and its Applications(B24CS302)

A polynomial 'p(x)' is an expression in variable 'x' taking the form '(axn + bxn-1 + …. + jx+ k)', where 'a, b,
c ….', k are real numbers, and 'n' is a non-negative integer known as the degree of the polynomial. Each
term in a polynomial comprises a coefficient and an exponent.

Example: In the polynomial '10x2 + 26x', 10 and 26 are coefficients, and 2 and 1 are their respective
exponents.

Key Points in Polynomial Representation

 Coefficients and exponents are stored with their signs.

 Polynomials may have terms with equal exponents.
 Terms are typically arranged in order of descending or ascending exponent value.

#include <stdio.h>
#include <stdlib.h>

// Define a structure for a polynomial term

struct Term {
intcoeff; // Coefficient
intexp; // Exponent
struct Term* next;
};

// Function to create a new term

struct Term* createTerm(intcoeff, intexp) {
struct Term* newTerm = (struct Term*)malloc(sizeof(struct Term));
newTerm->coeff = coeff;
newTerm->exp = exp;
newTerm->next = NULL;
returnnewTerm;
}

// Function to add a term to the polynomial

voidaddTerm(struct Term** poly, intcoeff, intexp) {
struct Term* newTerm = createTerm(coeff, exp);
newTerm->next = *poly;
*poly = newTerm;
}

Page 49 of 74
Data Structures and its Applications(B24CS302)

Example :Adding polynomials

// Function to add two polynomials

struct Term* addPolynomials(struct Term* poly1, struct Term* poly2) {
struct Term* result = NULL;

while (poly1 != NULL || poly2 != NULL) {

intcoeff, exp;
if (poly1 != NULL && (poly2 == NULL || poly1->exp> poly2->exp))
{
coeff = poly1->coeff;
exp = poly1->exp;
poly1 = poly1->next;
} else if (poly2 != NULL && (poly1 == NULL || poly2->exp> poly1->exp)) {
coeff = poly2->coeff;
exp = poly2->exp;
poly2 = poly2->next;
} else {
coeff = poly1->coeff + poly2->coeff;
exp = poly1->exp;
poly1 = poly1->next;
poly2 = poly2->next;
}

if (coeff != 0) {
addTerm(&result, coeff, exp);
}
}
return result;
}
// Function to display a polynomial
voiddisplayPolynomial(struct Term* poly) {
while (poly != NULL) {
printf("%dx^%d", poly->coeff, poly->exp);
if (poly->next != NULL) {
printf(" + ");
}
poly = poly->next;
}
printf("\n");
}
// Main function
int main() {
struct Term* poly1 = NULL;
struct Term* poly2 = NULL;

// Polynomial 1: 3x^3 + 5x^2 + 6

addTerm(&poly1, 3, 3);
addTerm(&poly1, 5, 2);
addTerm(&poly1, 6, 0);

Page 50 of 74
Data Structures and its Applications(B24CS302)

// Polynomial 2: 4x^3 + 2x^1 + 1

addTerm(&poly2, 4, 3);
addTerm(&poly2, 2, 1);
addTerm (&poly2, 1, 0);
printf("Polynomial 1: ");
displayPolynomial(poly1);
printf("Polynomial 2: ");
displayPolynomial(poly2);
struct Term* result = addPolynomials(poly1, poly2);
printf("Resultant Polynomial: ");
displayPolynomial(result);
return 0;
}

Sparse Matrix in Data Structure:

A sparse matrix in which most of its elements are zero. It is characterized by a small number of non-zero
elements compared to the total number of elements (mxn). In other words, a sparse matrix has a
significant proportion of zero values, often exceeding half of the total elements.
Given m and n, a sparse matrix of size mxn can be defined as follows:
 m: The number of rows
 n: The number of columns
For example, consider the following 4x4 matrix:
0001
0000
2000
0003

Why Sparse Matrix is Used?

Sparse matrices are extremely useful because they allow efficient storage and computational
performance. Instead of storing all elements, including the zeros, sparse matrix representations store
only the non-zero elements, which reduces memory consumption and speeds up computations. This is
vital in applications such as machine learning, where large datasets often contain numerous zero-values
such as text data. By utilizing sparse matrices, we can work with these datasets without loading large
amounts of redundant data.
Storing and processing these datasets using sparse matrix representations helps reduce computational
cost and memory usage, making it possible to train models more efficiently.

Operations on Sparse Matrices

Given two sparse matrices perform operations such as add, multiply or transpose of the matrices in their
sparse form itself. The result should consist of three sparse matrices, one obtained by adding the two
input matrices, one by multiplying the two matrices and one obtained by transpose of the first matrix.

Example: Note that other entries of matrices will be zero as matrices are sparse.
Input :
Matrix 1: (4x4)
Row Column Value

Page 51 of 74
Data Structures and its Applications(B24CS302)

1 2 10
1 4 12
3 3 5
4 1 15
4 2 12
Matrix 2: (4X4)
Row Column Value
1 3 8
2 4 23
3 3 9
4 1 20
4 2 25
Output :
Result of Addition: (4x4)
Row Column Value
1 2 10
1 3 8
1 4 12
2 4 23
3 3 14
4 1 35
4 2 37
Result of Multiplication: (4x4)
Row Column Value
1 1 240
1 2 300
1 4 230
3 3 45
4 3 120
4 4 276
Result of transpose on the first matrix: (4x4)

Row Column Value

Page 52 of 74
Data Structures and its Applications(B24CS302)

1 4 15
2 1 10
2 4 12
3 3 5
4 1 12
The sparse matrix used anywhere in the program is sorted according to its row values. Two elements
with the same row values are further sorted according to their column values.
Now to Add the matrices, we simply traverse through both matrices element by element and insert the
smaller element (one with smaller row and col value) into the resultant matrix. If we come across an
element with the same row and column value, we simply add their values and insert the added data into
the resultant matrix.

To Transpose a matrix, we can simply change every column value to the row value and vice-versa,
however, in this case, the resultant matrix won't be sorted as we require. Hence, we initially determine
the number of elements less than the current element's column being inserted in order to get the exact
index of the resultant matrix where the current element should be placed. This is done by maintaining an
array index[] whose ith value indicates the number of elements in the matrix less than the column i.

To Multiply the matrices, we first calculate transpose of the second matrix to simplify our comparisons
and maintain the sorted order. So, the resultant matrix is obtained by traversing through the entire
length of both matrices and summing the appropriate multiplied values.

Any row value equal to x in the first matrix and row value equal to y in the second matrix (transposed
one) will contribute towards result[x][y]. This is obtained by multiplying all such elements having col
value in both matrices and adding only those with the row as x in first matrix and row as y in the second
transposed matrix to get the result[x][y].
For example: Consider 2 matrices:
Row Col Val Row Col Val
1 2 10 1 1 2
1 3 12 1 2 5
2 1 1 2 2 1
2 3 2 3 1 8

The resulting matrix after multiplication will be obtained as follows:

Transpose of second matrix:
Row Col Val Row Col Val
1 2 10 1 1 2
1 3 12 1 3 8
2 1 1 2 1 5
2 3 2 2 2 1

Page 53 of 74
Data Structures and its Applications(B24CS302
Applications(B24CS302)

Summation of multiplied values:

result[1][1] = A[1][3]*B[1][3] = 12*8 = 96
result[1][2] = A[1][2]*B[2][2] = 10*1 = 10
result[2][1] = A[2][1]*B[1][1] + A[2][3]*B[1][3] = 2*1 + 2*8 = 18
result[2][2] = A[2][1]*B[2][1] = 1*5 = 5
Any other element cannot be obtained by any
any combination of row in Matrix A and Row in Matrix B.
Hence the final resultant matrix will be:
Row Col Val
1 1 96
1 2 10
2 1 18
2 2 5

Types of Sparse Matrices in Data Structures

Here are the types of sparse matrices in data structure:
struct
1. Lower Triangular Sparse Matrix
The diagonal element of a matrix is zero, and all other elements are positive. For a lower triangular
matrix, Ai,j = 0 for i < j.

Representation of Lower Triangular Matrix A[5,5]

Page 54 of 74
Data Structures and its Applications(B24CS302
Applications(B24CS302)

2. Upper Triangular Sparse Matrix

In an upper triangular matrix, the elements below the main diagonal are zero. For Ai,j = 0 where i > j.

Representation of Upper Triangular Sparse Matrix A[5,5]

3. Tri-Diagonal Sparse Matrix

A matrix where non-zero diagonal, or immediately above or below the
zero elements can appear only on the diagonal,
diagonal. In a tri-diagonal
diagonal matrix, Ai,j = 0 where |i - j| > 1
Representation of Tri-Diagonal
Diagonal Sparse Matrix A[5,5]

Page 55 of 74
Data Structures and its Applications(B24CS302)

Representation of Sparse Matrix

The Sparse Matrix can be represented using two methods:
 Sparse Matrix Using Array
 Sparse Matrix Using Linked List

 Sparse Matrix Using Array

#include<stdio.h>
int main()
{
// Assume 4x5 sparse matrix
int sparseMatrix[4][5] =
{
{0 , 0 , 3 , 0 , 4 },
{0 , 0 , 5 , 7 , 0 },
{0 , 0 , 0 , 0 , 0 },
{0 , 2 , 6 , 0 , 0 }
};

int size = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)
if (sparseMatrix[i][j] != 0)
size++;
int compactMatrix[3][size];

Page 56 of 74
Data Structures and its Applications(B24CS302)

// Making of new matrix

int k = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)
if (sparseMatrix[i][j] != 0)
{
compactMatrix[0][k] = i;
compactMatrix[1][k] = j;
compactMatrix[2][k] = sparseMatrix[i][j];
k++;
}

for (int i=0; i<3; i++)

{
for (int j=0; j<size; j++)
printf("%d ", compactMatrix[i][j]);

printf("\n");
}
return 0;
}

Output
001133
242312
345726

Strings in C
A string is an array of characters terminated by a special character '\0' (null character). This null
character marks the end of the string and is essential for proper string manipulation.
Unlike many modern languages, C does not have a built-in string data type. Instead, strings are
implemented as arrays of char.

Page 57 of 74
Data Structures and its Applications(B24CS302
Applications(B24CS302)

Example :
#include <stdio.h>
int /void main( ) {
// declaring and initializing a string
charstr[ ] = "Geeks";

// printing the string

printf("The string is: %s\n", str);
return 0;
}

Output
The string is: Geeks
 charstr[ ] = "Geeks";
nd initializes it with the string "Hello World!". Internally,
This line declares a character array str and
this creates an array like:
{ 'G', 'e', 'e', 'k', 's', '\0'}
The null character '\0' is automatically added at the end to terminate the string.
 printf("The string is: %s\n",
n", str);
%s is the format specifier used to print a string. printf starts at the memory location of str and
prints each character until it finds the terminating null character '\0'.

Declaration
one dimensional array of character type. Below is the
Declaring a string is as simple as declaring a one-dimensional
syntax for declaring a string.
char string_name[size];

In the above syntax string_name is any name given to the string variable and size is used to define the
length of the string, i.e. the number of characters strings will store.
char array_name[ ];
Page 58 of 74
Data Structures and its Applications(B24CS302)

Initialization
We can initialize a string either by specifying the list of characters or string literal.
// Using character list
charstr[] = {'G', 'e', 'e', 'k', 's', '\0'};
// Using string literal
charstr[] = "Geeks";
Note: When a Sequence of characters enclosed in the double quotation marks is encountered by the
compiler, a null character '\0' is appended at the end of the string by default.
Accessing
We can access any character of the string by providing the position of the character, like in array. We pass
the index inside square brackets [] with the name of the string.
Example:
#include <stdio.h>
int main( )
{
charstr[ ] = "Geeks";
// Access first character of string
printf("%c", str[0]);
return 0;
}

Update
Updating a character in a string is also possible. We can update any character of a string by using the
index of that character.
Example :
#include <stdio.h>
int main( ) {
charstr[] = "Geeks";
// Update the first character of string
str[0] = 'R';
printf("%c", str[0]);
return 0;
}

String Length

To find the length of a string in C, you need to iterate through each character until you reach the null
terminator '\0', which marks the end of the string. This process is handled efficiently by the
strlen( ) function from the C standard library.

Example
#include <stdio.h>
int main() {
charstr[ ] = "Geeks";
Page 59 of 74
Data Structures and its Applications(B24CS302)

printf("%d", strlen(str));
return 0;
}
Output
5

In this example, strlen() returns the length of the string "Geeks", which is 5, excluding the null character.
C language also provides several other useful string library functions to perform operations like copying,
comparing, and concatenating strings. You can refer to standard string functions for more details.

String Input

In C, reading a string from the user can be done using different functions, and depending on the use case,
one method might be chosen over another. Below, the common methods of reading strings in C will be
discussed, including how to handle whitespace, and concepts will be clarified to better understand how
string input works.

Using scanf()
The simplest way to read a string in C is by using the scanf( ) function.
Example :
#include<stdio.h>

int main() {
charstr[5];

// Read string
// from the user
scanf("%s",str);

// Print the string

printf("%s",str);
return 0;
}
Using fgets()
If someone wants to read a complete string, including spaces, they should use the fgets() function. Unlike
scanf(), fgets() reads the entire line, including spaces, until it encounters a newline.

Example
#include <stdio.h>
int main() {
charstr[20];
// Reading the string (with spaces) using fgets
fgets(str, 20, stdin);
// Displaying the string using puts
printf("%s", str);
return 0;
}

Page 60 of 74
Data Structures and its Applications(B24CS302
Applications(B24CS302)

Output
Geeks For Geeks (Enter by user)
Geeks For Geeks
Passing Strings to Function

As strings
rings are character arrays, we can pass strings to functions in the same way we pass an array to a
function.. Below is a sample program to do this:

#include <stdio.h>
voidprintStr(char str[]) {
printf("%s", str);
}
int main() {
charstr[] = "GeeksforGeeks";
// Passing string to a function
printStr(str);
return 0;
}

Strings and Pointers in C

Similar to arrays, In C, we can create a character pointer to a string that points to the starting address of
string. The string can be accessed with the help of pointers
the string which is the first character of the string. pointers.

Example :

#include <stdio.h>
int main(){
charstr[20] = "Geeks";
// Pointer variable which store the starting address ofthe character array str
char* ptr = str;
// While loop will run till the
he character value is notequal to null character
while (*ptr != '\0') {
printf("%c", *ptr);
ptr++;
}
return 0;
}
Strings Literals
Page 61 of 74
Data Structures and its Applications(B24CS302)

A string literal is a sequence of characters enclosed in double quotes, like "Hello" or "1234". Internally, it
is stored as a constant character array terminated by a null character '\0'.

#include <stdio.h>
int main( )
{
// pointer to a string literal
const char *str = "Hello World";
printf("%s\n", str);
return 0;
}

Output
Hello World

 "Hello World" is a string literal. It is stored in a read-only section of memory.

 const char *str = "Hello World";
This creates a pointer to the string literal. Using const is important because string literals should
not be modified.
 printf("%s\n", str); prints the string starting from the address stored in str.
Key Points
 String literals are automatically null-terminated.
 They are typically stored in read-only memory, so modifying them causes undefined behavior.
 You can assign string literals to char*, but it's recommended to use const char* for safety.

Operations and Pattern Matching in C Strings

C strings are arrays of characters terminated by a null character (\0). They are widely used in C
programming for text manipulation. Below is an overview of common operations and pattern-
matching techniques in C strings:

Common String Operations in C

String Basics in C

In C programming, strings are fundamental data structures used to store and manipulate text. Unlike
some high-level languages, C does not have a built-in string type. Instead, strings are represented as
arrays of characters terminated by a null character (\0).
String Declaration and Initialization
There are multiple ways to declare and initialize strings in C:
// Method 1: Character array declaration
char str1[10] = "Hello";

// Method 2: Character array with explicit null terminator

char str2[] = {'W', 'o', 'r', 'l', 'd', '\0'};

// Method 3: Pointer to a string literal

char *str3 = "LabEx";

String Length and Null Termination

Page 62 of 74
Data Structures and its Applications(B24CS302)

The null terminator is crucial in C strings. It indicates the end of the string and is used by string
manipulation functions.

String Memory
Hello'\0'
Common String Operations
Operation Function Description

Length strlen() Calculates string length

Copy strcpy( ) Copies one string to another

Concatenation strcat( ) Joins two strings

Comparison strcmp( ) Compares two strings

1. String Length (strlen):

o Determines the length of a string (excluding the null character).

#include <stdio.h>
#include <string.h>
int main() {
charstr[] = "Hello, World!";
printf("Length: %lu\n", strlen(str));
return 0;
}
2. String Copy (strcpy):
o Copies one string into another.

#include <stdio.h>
#include <string.h>
int main() {
charsrc[] = "Copy me!";
chardest[20];
strcpy(dest, src);
printf("Copied String: %s\n", dest);
return 0;
}
3. String Concatenation (strcat):
o Appends one string to another.

#include <stdio.h>
#include <string.h>
int main() {
char str1[20] = "Hello, ";
char str2[] = "World!";

Page 63 of 74
Data Structures and its Applications(B24CS302)

strcat(str1, str2);
printf("Concatenated String: %s\n", str1);
return 0;
}
4. String Comparison (strcmp):
o Compares two strings lexicographically.

#include <stdio.h>
#include <string.h>
int main() {
char str1[] = "apple";
char str2[] = "banana";
int result = strcmp(str1, str2);
printf("Comparison Result: %d\n", result); // Negative if str1 < str2
return 0;
}
5. Finding a Substring (strstr):
o Locates the first occurrence of a substring in a string.

#include <stdio.h>
#include <string.h>
int main() {
charstr[] = "Find the needle in the haystack.";
char *substr = strstr(str, "needle");
if (substr) {
printf("Substring found: %s\n", substr);
} else {
printf("Substring not found.\n");
}
return 0;
}
Pattern Matching in C Strings

What is Pattern Searching?

The pattern searching/matching algorithm is a technique that is used to locate or find a specific pattern
or substring within given text. Its basic idea is to find all the occurrences of a particular pattern in the
specified data structure. For instance, given an array of numbers [1, 2, 3, 4, 5, 6, 3, 4, 9] and we need to
find all the occurrences of the pattern [3, 4] in the array. The answer would be index number 2 and 6.

Page 64 of 74
 Data Structures and its Applications(B24CS302)

How pattern searching algorithm works?

There are multiple pattern searching algorithms that works in different ways. The main goal to design
these type of algorithms is to reduce the time complexity. The traditional approach may take lots of time
to complete the pattern searching task for a longer text.
If we are saying traditional approach, we are actually referring to brute force approach for solving pattern
searching problems. Let's see how it works −
 Slide the pattern over the text.
 Compare each character one by one.
 If all the characters match, we have found a match.
 If not, move the pattern one position to the right and repeat the process until we reach the end of
the text or find a match.

Remember, brute force is the simplest way to solve string matching or searching, but it is also the
slowest and most inefficient. The time complexity of this algorithm is O(nm), where 'n' is the length of
the text and 'm' is the length of the pattern. This means that in the worst case, we have to compare
every character of the text with every character of the pattern, which can be very slow if n and m are
large.
Example
In this example, we will practically demonstrates the brute force approach to solve a pattern matching
problem in various programming languages.

#include <stdio.h>
#include <string.h>
// method to find match
Page 65 of 74
Data Structures and its Applications(B24CS302)

voidfindMatch(char *orgText, char *pattern)

{
int n = strlen(orgText);
int m = strlen(pattern);
// comparing the text and pattern one by one
for (inti = 0; i<= n-m; i++)
{
int j = 0;
while (j < m &&orgText[i+j] == pattern[j])
{
j++;
}
// print result if found
if (j == m)
{
printf("Oohhoo! Match found at index: %d\n", i);
return;
}
}
// if not found
printf("Oopps! No match found\n");
}
int main( ) { // Original Text
charorgText[ ] = "Tutorials Point"; // pattern to be matched
char pattern[ ] = "Point"; // method calling
findMatch(orgText, pattern);
return 0;
}

Pattern matching involves searching for a specific sequence of characters (pattern) within a larger
string. Below are some common techniques:

1. Naive Pattern Matching Algorithm:

 Compares the pattern with each substring of the text.

#include <stdio.h>
#include <string.h>
voidnaivePatternMatch(char *text, char *pattern) {
int n = strlen(text);
int m = strlen(pattern);
for (inti = 0; i<= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if (text[i + j] != pattern[j]) {
break;
}
}
if (j == m) {
printf("Pattern found at index %d\n", i);
}
}
Page 66 of 74
Data Structures and its Applications(B24CS302)

}
int main( ) {
char text[] = "ababcabcabababd";
char pattern[] = "ababd";
naivePatternMatch(text, pattern);
return 0;
}
2. Boyer-Moore Algorithm:
 Efficient algorithm that skips unnecessary comparisons by using precomputed tables.
 Implementation is more complex but faster for large texts.
Example
In the following example, we are going to illustrate the working of Boyer-Moore Algorithm in various
programming languages.

#include<stdio.h>
#include<string.h> // Function for full suffix match
voidcomputeFullShift(intshiftArr[], intlongSuffArr[], char patrn[], int n)
{
inti = n;
int j = n+1;
longSuffArr[i] = j;
while(i> 0)
{
// Searching right if (i-1)th and (j-1)th item are not the same
while(j <= n &&patrn[i-1] != patrn[j-1] )
{
// to shift pattern from i to j
if(shiftArr[j] == 0) { shiftArr[j] = j-i;
}
// Updating long suffix value
j = longSuffArr[j];
}
i--;
j--;
longSuffArr[i] = j;
}
}
// Function for good suffix match
voidcomputeGoodSuffix(intshiftArr[], intlongSuffArr[], char patrn[], int n)
{
int j;
j = longSuffArr[0];

// Looping through the pattern

for(inti = 0; i<n; i++)
{
// setting shift to long suffix value
if(shiftArr[i] == 0)
{
shiftArr[i] = j;
if(i == j)
Page 67 of 74
Data Structures and its Applications(B24CS302)

{
// Updating long suffix value
j = longSuffArr[j];
}
}
}
}
// Function for searching the pattern
voidsearchPattern(char orgnStr[], char patrn[], int array[], int *index)
{

// length of the pattern

intpatLen = strlen(patrn);
// length of main string
intstrLen = strlen(orgnStr);
intlongerSuffArray[patLen+1];
intshiftArr[patLen + 1];
// Initializing shift array elements to 0
for(inti = 0; i<=patLen; i++)
{
shiftArr[i] = 0;
}
// Calling computeFullShift function
computeFullShift(shiftArr, longerSuffArray, patrn, patLen);
// Calling computeGoodSuffix function
computeGoodSuffix(shiftArr, longerSuffArray, patrn, patLen);
int shift = 0;
while(shift <= (strLen - patLen))

{
int j = patLen - 1;
// decrement j when pattern and main string character is matching
while(j >= 0 &&patrn[j] == orgnStr[shift+j])
{
j--;
}
if(j < 0)
{
(*index)++;
// to store the position where pattern is found
array[(*index)] = shift; shift += shiftArr[0];
}
else
{
shift += shiftArr[j+1];
}
}
}
int main( )
{
// original string
Page 68 of 74
Data Structures and its Applications(B24CS302)

charorgnStr[] = "AABAAABCEDBABCDDEBC";
// Pattern to be searched
charpatrn[] = "ABC";
// Array to store the positions where pattern is found
intlocArray[strlen(orgnStr)];
int index = -1;
// Calling the searchPattern function
searchPattern(orgnStr, patrn, locArray, &index);
// Printing the positions where pattern is found
for(inti = 0; i<= index; i++)
{
printf("Pattern found at position: %d\n", locArray[i]);
}
return 0;
}

3. Knuth-Morris-Pratt (KMP) Algorithm:

 Uses a partial match table to avoid redundant comparisons.
//Implementation of KMP Algorithm
voidcompute_lps(char* pattern, int* lps, int m)
{
intlen = 0;
lps[0] = 0;
inti = 1;

while (i< m) {
if (pattern[i] == pattern[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0)
len = lps[len - 1];
else {
lps[i] = 0;
i++;
}
}
}
}

intkmp_search(char* text, char* pattern) {

int n = strlen(text);
int m = strlen(pattern);
intlps[m];

compute_lps(pattern, lps, m);

inti = 0, j = 0;
while (i< n) {
if (pattern[j] == text[i]) {
Page 69 of 74
Data Structures and its Applications(B24CS302)

i++;
j++;
}

if (j == m)
returni - j;

if (i< n && pattern[j] != text[i]) {

if (j != 0)
j = lps[j - 1];
else
i++;
}
}
return -1;
}
Programming Examples:
Example 1 :
//Copy one string to another using strcpy
#include <stdio.h>
#include <string.h>

int main()
{
char source[] = "Hello, World!";
char destination[50];
strcpy(destination, source);
printf("Source: %s\n", source);
printf("Destination: %s\n", destination);
return 0;
}

//copy string without strcpy

#include <stdio.h>
voidcopyString(char *source, char *destination) {
while (*source != '\0') {
*destination = *source;
source++;
destination++;
}
*destination = '\0'; // Null-terminate the destination string
}

int main( ) {
char source[100], destination[100];
printf("Enter a string: ");
fgets(source, sizeof(source), stdin);
copyString(source, destination);
printf("Copied string: %s", destination);

Page 70 of 74
Data Structures and its Applications(B24CS302)

return 0;
}
Example 2 :
//Compare 2 strings without strcmp( )
/* without using strcmp() */

#include <stdio.h>
#include <string.h>
int main()
{
char Str1[100], Str2[100];
int result, i;
printf("\n Please Enter the First String : ");
gets(Str1);
printf("\n Please Enter the Second String : ");
gets(Str2);
for(i = 0; Str1[i] == Str2[i] && Str1[i] == '\0'; i++);
if(Str1[i] < Str2[i])
{
printf("\n str1 is Less than str2");
}
else if(Str1[i] > Str2[i])
{
printf("\n str2 is Less than str1");
}
else
{
printf("\n str1 is Equal to str2");
}
return 0;
}
Example 3:
//program to reverse a string
#include <stdio.h>
#include <string.h>

int main() {
charstr[100], temp;
inti, j;

printf("Enter a string: ");

gets(str);

j = strlen(str) - 1;

for (i = 0; i< j; i++, j--) {

temp = str[i];
str[i] = str[j];
str[j] = temp;
Page 71 of 74
Data Structures and its Applications(B24CS302)

printf("Reversed string: %s\n", str);

return 0;
}
Example Programs
Demonstrating the addition of two one-dimensional arrays:

#include <stdio.h>
intmain()
{
// Define the size of the arrays
int size = 5;

// Declare and initialize the two input arrays

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

// Declare a third array to store the result

intsum_array[size];

// Iterate through the arrays and add corresponding elements

for (inti = 0; i< size; i++) {
sum_array[i] = array1[i] + array2[i];
}

// Display the elements of the resultant array

printf("Resultant Array (Sum of array1 and array2): ");
for (inti = 0; i< size; i++) {
printf("%d ", sum_array[i]);
}
printf("\n");

return 0;
}

Page 72 of 74
Data Structures and its Applications(B24CS302)

Page 73 of 74