ADVANCED DATA STRUCTURES

Course Code: 22EEE452

1.1​ Data structures:
Data is simply a value and it can be organized in many different ways. Data
structure is a mathematical or logical model of a particular organization of data.
The choice of particular organization depends on two considerations: 1. It should
be rich enough to mirror the actual relationships of data. 2. It should be simple
enough so that one can effectively process the data when necessary.

1.2 Classification of Data structures:

Data structures are generally classified into two categories. Primitive and
non-primitive.

Fig 1. Classification of Data structures

Primitive data structure:

These are basic and built in data types that includes int, float, char and Boolean.
These consist of characters that cannot be divided, so they are also called simple
data types. They store single values.

Integer: The integer datatype in C is used to store the integer numbers (any
number including positive, negative and zero without decimal part). Octal values,
hexadecimal values, and decimal values can be stored in int data type in C. Format
specifier for int is %d.
Syntax: int var_name;
Float: Float in C is used to store decimal and exponential values. It is used to
store decimal numbers (numbers with floating point values) with single precision.
Format specifier is %f.
Syntax: float var_name;

Char: Character data type allows its variable to store only a single character.
Format specifier is %c. Syntax: char var_name;

Boolean: The bool in C is a fundamental data type in most that can hold one of
two values: true or false. It is used to represent logical values and is commonly
used in programming to control the flow of execution in decision-making
statements such as if-else statements, while loops, and for loops.

Non primitive data structure:

These are more complex structures built using primitive data types. These can store
collection of values with potential relationships between them. Based on structure
and arrangement of data, non-primitive data structure is divided into Linear and
Nonlinear data structure.
In linear data structure the data is arranged in a linear fashion, although the way
they are stored in memory need not to be in sequential form. This includes Arrays,
Linked list, Queues and Stacks.
In nonlinear data structure, the data is not arranged in sequence. This includes trees
and graphs.

1.​ Arrays:
It is a collection of elements of same data type stored at memory locations. It
is one of the most popular and simple data structures used in programming.

Basic terminologies:
●​ Array Index: In an array, elements are identified by their indexes. Array
index starts from 0.
●​ Array element: Elements are items stored in an array and can be accessed by
their index.
●​ Array Length: The length of an array is determined by the number of
elements it can contain.
Memory representation of Array
In an array, all the elements are stored in contiguous memory locations. So, if we
initialize an array, the elements will be allocated sequentially in memory.
Array elements

1 4 8 9 7 8
0 1 2 3 4 5

Array index
Declaration of array:
●​ int arr[5];
●​ char arr[10];
Initialization of array:
●​ int arr[] = { 1, 2, 3, 4, 5 };
●​ char arr[5] = { 'a', 'b', 'c', 'd', 'e' };
●​ float arr[10] = { 1.4, 2.0, 24, 5.0, 0.0 };

Types of arrays:
●​ Based on Size
●​ Based on dimension
Based on size:
●​ Fixed size arrays: We cannot alter or update the size of this array. Here
only a fixed size (i,e. the size that is mentioned in square brackets [])
of memory will be allocated for storage.
●​ Dynamic size arrays: The size of the array changes as per user
requirements during execution of code so the coders do not have to
worry about sizes. They can add and remove the elements as per the
need. The memory is mostly dynamically allocated and de-allocated
in these arrays.
Based on dimension:
●​ 1D array: Elements are stored one after the other.
●​ Multi-dimensional array: A multi-dimensional array is an array with
more than one dimension. We can use multidimensional array to store
complex data in the form of tables, etc. We can have 2-D arrays, 3-D
arrays, 4-D arrays and so on.

Operations on Array:
1.​ Array Traversal: Array traversal involves visiting all the elements of the
array once.
2.​ Insertion in array: We can insert one or multiple elements at any position in
the array.
3.​ Deletion in array: We can delete an element at any index in an array.
4.​ Searching in array: We can traverse over an array and search for an element.

2.​ Linked list:

It mainly allows efficient insertion and deletion operations compared to arrays.
Like arrays, it is also used to implement other data structures like stack, queue and
deque. It consists of nodes and a node consists of two fields one for storing data
and other for keeping the reference of next node. It is basically chains of
nodes where each node contains information such as data and a pointer to the next
node in the chain. The main cases where we prefer linked list over arrays is due to
ease of insertion and deletion in linked list.

Basic terminologies:
Node Structure: A node in a linked list typically consists of two components.
Those are node and next pointer or reference.
Data: It holds the actual value or data associated with the node.
Next Pointer or Reference: It stores the memory address (reference) of the next
node in the sequence.
Head: The linked list is accessed through the head node, which points to the first
node in the list.
Tail: The last node in the list points to NULL or nullptr, indicating the end of the
list. This node is known as the tail node.

Memory representation of linked list:

Operations on Linked list:

Insertion: Adding a new node to a linked list involves adjusting the pointers of the
existing nodes to maintain the proper sequence. Insertion can be performed at the
beginning, end, or any position within the list.
Deletion: Removing a node from a linked list requires adjusting the pointers of the
neighboring nodes to bridge the gap left by the deleted node. Deletion can be
performed at the beginning, end, or any position within the list.
Searching: Searching for a specific value in a linked list involves traversing the list
from the head node until the value is found or the end of the list is reached.

Types of linked list:

1.​ Singly linked list: A singly linked list is a fundamental data structure, it
consists of nodes where each node contains a data field and a reference to
the next node in the linked list.
2.​ Doubly linked list: It is a type of linked list in which nodes contain
information and two pointers i.e. left pointer and right pointer. The left
pointer in the doubly linked list points to the previous node and the right
pointer points to the next node in the linked list.
3.​ Circular linked list: A circular linked list is either a singly or doubly linked
list in which there are no NULL values. Here, we can implement the
Circular Linked List by making the use of Singly or Doubly Linked List. In
the case of a singly linked list, the next of the last node contains the address
of the first node and in case of a doubly-linked list, the next of last node
contains the address of the first node and Prev of the first node contains the
address of the last node.

3.​ Stack:
A Stack is a linear data structure that follows a particular order in which the
operations are performed. The order may be LIFO (Last In First Out) or FILO
(First In Last Out). LIFO implies that the element that is inserted last, comes out
first and FILO implies that the element that is inserted first, comes out last. It
behaves like a stack of plates, where the last plate added is the first one to be
removed.

Basic operations on stacks :

1.​ Push():
Adds an item to the stack. If the stack is full, then it is said to be an Overflow
condition.
Algorithm of push operation:
●​ Before pushing the element to the stack, we check if the stack is full .
●​ If the stack is full (top == capacity-1) , then Stack Overflows and we cannot
insert the element to the stack.
●​ Otherwise, we increment the value of top by 1 (top = top + 1) and the new
value is inserted at top position .
●​ The elements can be pushed into the stack till we reach the capacity of the
stack.

2.​ Pop(): Removes an item from the stack.

The items are popped in the reversed order in which they are pushed. If the stack is
empty, then it is said to be an Underflow condition.
Algorithm of push operation:
●​ Before popping the element from the stack, we check if the stack is empty .
●​ If the stack is empty (top == -1), then Stack Underflows and we cannot
remove any element from the stack.
●​ Otherwise, we store the value at top, decrement the value of top by 1 (top =
top – 1) and return the stored top value.

3.​ Isempty(): Returns true if the stack is empty, else false.

4.​ Peek():Returns the top element of the stack.

Empty stack PUSH 100 PUSH 200 POP 200

4.​ Queue:
It follows the principle of "First in, first out" (FIFO), where the first element
added to the queue is the first one to be removed. It means that the element that
is inserted first in the queue will come out first and the element that is inserted
last will come out last.

Basic terminologies:
Front: It is also referred as the head of the queue. Position of the entry in a queue
ready to be served, that is, the first entry that will be removed from the queue, is
called the front of the queue.
Rear: Position of the last entry in the queue, that is, the one most recently added, is
called the rear of the queue. It is also referred as the tail of the queue.
Size: Size refers to the current number of elements in the queue.

Operations on Queue:
1.​ Enqueue: Insertion of elements to the queue.
Operation:
●​ Check if the queue is full.
●​ If the queue is full, return overflow error and exit.
●​ If the queue is not full, increment the rear pointer to point to the next empty
space.
●​ Add the data element to the queue location, where the rear is pointing.
●​ return success.

2.​ Dequeue: Removal of elements from the queue.

Operation:
●​ Check if the queue is empty.
●​ If the queue is empty, return the underflow error and exit.
●​ If the queue is not empty, access the data where the front is pointing.
●​ Increment the front pointer to point to the next available data element.
●​ The Return success.

3.​ isEmpty(): This operation returns a Boolean value that indicates whether the
queue is empty or not.

Types of queues:
1.​ Simple queue: Simple Queue simply follows FIFO Structure. We can only
insert the element at the back and remove the element from the front of the
queue.

2.​ Double ended queue: In a double-ended queue the insertion and deletion
operations, both can be performed from both ends. They are of two types:
i.​ Input Restricted Queue: The input can be taken from only one
end but deletion can be done from any of the ends.
ii.​ Output Restricted Queue: The input can be taken from both
ends but deletion can be done from only one end.

3.​ Circular queue: This is a special type of queue where the last position is
connected back to the first position. Here also the operations are performed
in FIFO order.

4.​ Priority queue: A priority queue is a special queue where the elements are
accessed based on the priority assigned to them.
5.Trees:
It is a hierarchical structure that is used to represent and organize data in the form
of parent child relationship.

Basic terminologies:
1.​ Root: The root is the topmost node of the tree. It is the starting point of the
tree, and it has no parent. A is the root in the above tree.
2.​ Parent and child node: A parent node has branches to one or more child
nodes. A child node is derived from a parent node. B is the parent node of
D,E.
3.​ Leaf nodes: A leaf node is a node that has no children.
4.​ Edge: An edge is a connection (or link) between two nodes.
5.​ Subtree: A subtree is a smaller portion of a tree, consisting of a node and its
descendants.

Types of trees:
1.​ Binary tree: It is a tree where each node has at most two children (left and
right).
2.​ Complete tree: All levels are fully filled, except possibly the last. The
last level is filled from left to right.
3.​ Degenerate tree: A tree where each parent has only one child.
6.​ Graphs: Graph is a non-linear data structure consisting of vertices and
edges. The vertices are sometimes also referred to as nodes and the edges are
lines or arcs that connect any two nodes in the graph.
Basic terminologies:
1.​ Vertices: These are the fundamental units of the graph. Sometimes, vertices
are also known as vertex or nodes. Every node/vertex can be labeled or
unlabeled.
2.​ Edges: Edges are drawn or used to connect two nodes of the graph. It can be
ordered pair of nodes in a directed graph. Edges can connect any two nodes
in any possible way. There are no rules. Sometimes, edges are also known as
arcs. Every edge can be labelled/unlabeled.

1.3​ Tower of Hanoi problem:

It is a mathematical puzzle and also a classic problem in programming. It starts

with the three disks of different sizes in source rod, with the largest disk in the
bottom and smallest disk on the top. The goal is to move the entire stack to
destination rod in same order.
But there are 3 rules:
1.​ Only one disk has to be moved at a time.
2.​ Only top most disk can be moved.
3.​ Larger disk can not be put on the smaller disk.
C program for Tower of Hanoi:
#include <stdio.h>

// Function to solve Tower of Hanoi

void towerOfHanoi(int n, char source, char auxiliary, char destination) {
if (n == 1) {
printf("Move disk 1 from %c to %c\n", source, destination);
return;
}

// Move (n-1) disks from source to auxiliary using destination as buffer

towerOfHanoi(n - 1, source, destination, auxiliary);

// Move the nth disk from source to destination

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

// Move (n-1) disks from auxiliary to destination using source as buffer

towerOfHanoi(n - 1, auxiliary, source, destination);
}

int main() {
int n;

// Input number of disks

printf("Enter the number of disks: ");
scanf("%d", &n);

// Call the Tower of Hanoi function

printf("Steps to solve Tower of Hanoi:\n");
towerOfHanoi(n, 'A', 'B', 'C');

return 0;
}
Output
Enter the number of disks: 3
Steps to solve Tower of Hanoi:
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

1.4 Conversion of Expressions

An expression is a combination of operands and operators that represents a value.
Expressions can be represented in different notations. Such as infix, prefix and
postfix.
a.​ Infix notation: This is the most common way to represent expressions. In
this notation, the operator is placed between the pair of operands.
Ex: a + b
b.​ Prefix notation: The corresponding operators are placed before their
respective operands.
Ex: + a b
c.​ Postfix notation: The corresponding operators are placed after their
respective operands.
Ex: a b +
Conversion of expressions:
A.​Infix to Postfix:
To convert infix expression to postfix expression, use the stack data
structure. Scan the infix expression from left to right. Whenever we get an
operand, add it to the postfix expression and if we get an operator or
parenthesis add it to the stack by maintaining their precedence.
Algorithm:
●​ Scan the infix expression from left to right.
●​ If the scanned character is an operand, put it in the postfix expression.
●​ Otherwise, do the following
o​ If the precedence of the current scanned operator is higher than
the precedence of the operator on top of the stack, or if the stack
is empty, or if the stack contains a ‘(‘, then push the current
operator onto the stack.
o​ Else, pop all operators from the stack that have precedence
higher than or equal to that of the current operator. After that
push the current operator onto the stack.
●​ If the scanned character is a ‘(‘, push it to the stack.
●​ If the scanned character is a ‘)’, pop the stack and output it until a ‘(‘
is encountered, and discard both the parenthesis.
●​ Repeat steps 2-5 until the infix expression is scanned.
●​ Once the scanning is over, Pop the stack and add the operators in the
postfix expression until it is not empty.
●​ Finally, print the postfix expression.

Program to convert from infix to postfix :

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

#define MAX 100

// Stack for operators

char stack[MAX];
int top = -1;

// Push onto stack

void push(char c) {
if (top == MAX - 1) {
printf("Stack Overflow\n");
} else {
stack[++top] = c;
}
}

// Pop from stack

char pop() {
if (top == -1) {
return -1;
} else {
return stack[top--];
}
}

// Peek top of stack

char peek() {
if (top == -1)
return -1;
return stack[top];
}
// Function to return precedence of operators
int precedence(char op) {
switch(op) {
case '^': return 3;
case '*':
case '/': return 2;
case '+':
case '-': return 1;
default : return 0;
}
}

// Function to convert infix to postfix

void infixToPostfix(char infix[]) {
char postfix[MAX];
int i, k = 0;
char ch;
for (i = 0; infix[i] != '\0'; i++) {
ch = infix[i];
if (isalnum(ch)) {
postfix[k++] = ch; // operand goes directly to output
} else if (ch == '(') {
push(ch);
} else if (ch == ')') {
while (peek() != '(') {
postfix[k++] = pop();
}
pop(); // Remove '('
} else {
while (precedence(peek()) >= precedence(ch)) {
postfix[k++] = pop();
}
push(ch);
}
}
while (top != -1) {
postfix[k++] = pop();
}
postfix[k] = '\0';
printf("Postfix Expression: %s\n", postfix);
}
// Main function
int main() {
char infix[MAX];
printf("Enter an infix expression: ");
scanf("%s", infix);
infixToPostfix(infix);
return 0;
}
B.​ Prefix to Infix:
Algorithm for conversion of Prefix to Infix:
●​ Read the Prefix expression in reverse order (from right to left).
●​ If the symbol is an operand, then push it onto the Stack.
●​ If the symbol is an operator, then pop two operands from the Stack.
●​ Create a string by concatenating the two operands and the operator
between them.
●​ string = (operand1 + operator + operand2).
●​ And push the resultant string back to Stack.
●​ Repeat the above steps until the end of Prefix expression.
●​ At the end stack will have only 1 string i.e. resultant string.

Program to convert from prefix to infix:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX 100

// Stack to hold strings

char stack[MAX][MAX];
int top = -1;
// Push string onto stack
void push(char *str) {
if (top == MAX - 1) {
printf("Stack Overflow\n");
} else {
strcpy(stack[++top], str);
}
}
// Pop string from stack
char* pop() {
if (top == -1) {
printf("Stack Underflow\n");
exit(1);
} else {
return stack[top--];
}
}
// Function to check if character is operator
int isOperator(char ch) {
return (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^');
}
// Convert prefix to infix
void prefixToInfix(char prefix[]) {
int i;
char op1[MAX], op2[MAX], expr[MAX], ch[2];
// Traverse from right to left
for (i = strlen(prefix) - 1; i >= 0; i--) {
ch[0] = prefix[i];
ch[1] = '\0';
if (isalnum(prefix[i])) {
push(ch); // operand
} else if (isOperator(prefix[i])) {
strcpy(op1, pop());
strcpy(op2, pop());
sprintf(expr, "(%s%c%s)", op1, prefix[i], op2);
push(expr);
}
}
printf("Infix Expression: %s\n", pop());
}
// Main function
int main() {
char prefix[MAX];
printf("Enter a prefix expression: ");
scanf("%s", prefix);
prefixToInfix(prefix);
return 0;
}
C.​ Prefix to Postfix
●​ Read the Prefix expression in reverse order (from right to left)
●​ If the symbol is an operand, then push it onto the Stack
●​ If the symbol is an operator, then pop two operands from the Stack
●​ Create a string by concatenating the two operands and the operator after
them.
●​ string = operand1 + operand2 + operator
●​ And push the resultant string back to Stack
●​ Repeat the above steps until end of Prefix expression.
Input: Prefix: *+AB-CD
Output: Postfix: AB+CD-*
Explanation: Prefix to Infix: (A+B) * (C-D)
Infix to Postfix: AB+CD-*
C program to convert from prefix to postfix expression:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX 100

// Stack to hold strings

char stack[MAX][MAX];
int top = -1;
// Push string onto stack
void push(char *str) {
if (top >= MAX - 1) {
printf("Stack Overflow\n");
return;
}
strcpy(stack[++top], str);
}
// Pop string from stack
char* pop() {
if (top < 0) {
printf("Stack Underflow\n");
exit(1);
}
return stack[top--];
}
// Function to check if character is operator
int isOperator(char ch) {
return (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^');
}
// Function to convert prefix to postfix
void prefixToPostfix(char prefix[]) {
int i;
char op1[MAX], op2[MAX], expr[MAX], ch[2];

// Traverse prefix expression from right to left

for (i = strlen(prefix) - 1; i >= 0; i--) {
ch[0] = prefix[i];
ch[1] = '\0';
if (isalnum(prefix[i])) {
push(ch); // Operand
} else if (isOperator(prefix[i])) {
strcpy(op1, pop());
strcpy(op2, pop());
sprintf(expr, "%s%s%c", op1, op2, prefix[i]);
push(expr);
}
}
printf("Postfix Expression: %s\n", pop());
}
// Main function
int main() {
char prefix[MAX];
printf("Enter a prefix expression: ");
scanf("%s", prefix);

prefixToPostfix(prefix);
return 0;
}
1.5 Evaluation of Postfix expressions:
Given a postfix expression, the task is to evaluate the postfix expression. A
Postfix expression is of the form “a b operator” (ab+) i.e., a pair of operands is
followed by an operator. We can use a stack for the evaluation of the Postfix
expressions.
Scan the expression from left to right, if the symbol is operand, then push it into
the stack. If the symbol is an operator, pop two operands from the stack, apply
the operator and put back the resultant into the stack.
Ex: 1 2 3 + - 9 *
Illustrations of the above example:
i.​ 1 will go into the stack.
ii.​ 2 will go into the stack.
iii.​ 3 will go into the stack.
iv.​ There is an operand ‘+’ so take out 2 and 3, add both of them and put
back 5 into the stack.
v.​ There is an operand ‘-’ so take out 5 and 1, subtract and put back 4 into
the stack.
vi.​ 9 will go into the stack.
vii.​ There is an operand ‘*’ so take out and multiply 9 and 4. So the result
will be 36.

1.6 Iteration v/s Recursion

Iteration is a technique where a set of instructions are repeatedly executed using a
loop structure like ‘for’, ‘while’ or ‘do- while’ until a condition is met.
Ex:
#include <stdio.h>
int main()
{
// For Loop
for (int i = 0; i < 5; i++) {
printf("%d ", i);
}
printf("\n");

// While Loop
int count = 0;
while (count < 5) {
printf("%d ", count);
count++;
}
printf("\n");

// Do-While Loop
count = 0;
do {
printf("%d ", count);
count++;
} while (count < 5);
printf("\n");

return 0;
}

Output:
01234
01234
01234

Recursion is the process of a function calling itself repeatedly till the given
condition is satisfied. A function that calls itself directly or indirectly is called a
recursive function and such kind of function calls are called recursive calls. In
recursion a function calls itself directly or indirectly to solve a problem.
// C Program to calculate the sum of first N natural numbers using recursion
#include <stdio.h>
int nSum(int n)
{
// base condition to terminate the recursion when N = 0
if (n == 0) {
return 0;
}
// recursive case / recursive call
int res = n + nSum(n - 1);
return res;
}
int main()
{
int n = 5;
// calling the function
int sum = nSum(n);
printf("Sum of First %d Natural Numbers: %d", n, sum);
return 0;
}
Output:
Sum of First 5 Natural Numbers: 15

1.7 Application of queue:

A queue is a linear data structure that follows the “first-in, first-out” (FIFO)
principle. It is a collection of elements that supports two primary operations –
enqueue and dequeue. In the enqueue operation, an element is added to the back of
the queue, while in the dequeue operation, an element is removed from the front of
the queue. Queues are used to manage data flow and handle tasks in various
applications, such as operating systems, network protocols, and data processing
systems.
Here are some of the applications of queue.
Categorizing data: There is always a necessity to rearrange data making sure that
there is no change in their basic sequence.
Ex: Consider the following list of numbers.
​ ​ 3 22 12 6 10 34 65 29 9 30 81 4 5 19 20
Suppose we want to categorize them into four different groups:
Group 1: Less than 10
Group 2: Between 10 and 19
Group 3: Between 20 and 29
Group 4: 30 and greater
In other words, we want the list to be arranged as shown below:
|3 6 9 4 5| 12 10 19| 22 29 20| 34 65 30 81|

Categorizing data design:

One of the simplest solution for categorizing the data design is to build a queue for
all four categories.

Simulation of queues:
It acts as a modelling activity showcasing the statistics relating to the performance
of queues.

Task scheduling:

Queues are used in operating systems to manage processes in scheduling tasks,

such as in First-Come, First-Served (FCFS) and Round Robin scheduling.

Data Streaming:

Queues are useful in handling real-time data streams, where data is processed in
the order it is received. This is common in applications like video streaming and
network packets.

Message Queues:

Queues are heavily used in message-oriented middleware (e.g., RabbitMQ or

Kafka), where messages are enqueued by producers and dequeued by consumers
for processing.
Real-time Event Handling:

In systems where events are handled in real time (like in web servers or
event-driven architectures), events are queued and processed in the order of arrival.

1.8 Sparse matrix:

A matrix is a two-dimensional data object made of m rows and n columns,
therefore having total m x n values. If most of the elements of the matrix have 0
value, then it is called a sparse matrix.

Ex: 0 1 2 0 0 0 0 0 0

A sparse matrix is used when a matrix contains a large number of zero elements
and only a few non-zero values. Instead of storing and processing unnecessary
zeros, we use efficient storage formats to save memory and improve computational
performance.

Sparse matrix is useful because,

Memory Efficiency – Instead of storing zeros explicitly, only nonzero elements are
stored.
Faster Computation – Operations like addition and multiplication can ignore zero
elements, speeding up computations.
Better Performance – Useful in applications like graph representations, machine
learning, and scientific computing.

Sparse matrix representation in data structures:

A.​Coordinate list representation:

Stores only nonzero elements and their positions in three arrays: row index,
column index, and value.

Ex: ​ 0 0 5 0

0 8 0 0

0​ 0 0 3
Row Column Value

0 2 5

1 1 8

2 3 3

B.​ Compressed Sparse Row (CSR) Representation

For faster row-wise traversal this representation is useful.

Row Pointers: Stores the starting index of nonzero elements for each row.
Column Indices: Stores the column index of each nonzero element.
Values: Stores the nonzero elements.
Ex: ​ 0 0 5 0
​ 0 8 0 0
0​ 0 0 3
Values: [5, 8, 3]
Column Index: [2, 1, 3]
Row Pointer: [0, 1, 2, 3] (Starts from 0)
C.​ Compressed Sparse Column (CSC) Representation

Similar to CSR, but stores nonzero elements column-wise instead of row-wise.

Useful for column operations.

Ex: Values: [8, 5, 3]

Row Indices: [1, 0, 2]

Column Pointer: [0, 1, 2, 3, 3]

Write a program to check whether the given matrix is sparse or

not
#include <stdio.h>

void checkSparseMatrix(int rows, int cols, int matrix[rows][cols]) {

int zeroCount = 0;
int totalElements = rows * cols;

// Count zero elements

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

// Check if the matrix is sparse

if (zeroCount > totalElements / 2) {
printf("The given matrix is a Sparse Matrix.\n");
} else {
printf("The given matrix is NOT a Sparse Matrix.\n");
}
}

int main() {
int rows, cols;

// Input matrix size

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

// Input matrix elements

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

// Check if the matrix is sparse

checkSparseMatrix(rows, cols, matrix);

return 0;
}

Output:
Enter the number of rows: 3
Enter the number of columns: 3
Enter the elements of the matrix:
102010000
The given matrix is a Sparse Matrix.

Write a program to represent the matrix in sparse representation.

#include <stdio.h>

void convertToSparse(int rows, int cols, int matrix[rows][cols]) {

int nonZeroCount = 0;

// Count non-zero elements

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] != 0) {
nonZeroCount++;
}
}
}

// Sparse matrix storage (0-based triplet representation)

int sparseMatrix[nonZeroCount][3];

int k = 0; // Start from index 0

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] != 0) {
sparseMatrix[k][0] = i; // Row index
sparseMatrix[k][1] = j; // Column index
sparseMatrix[k][2] = matrix[i][j]; // Value
k++;
}
}
}

// Print the sparse matrix

printf("\nSparse Matrix Representation (Row, Column, Value):\n");
for (int i = 0; i < nonZeroCount; i++) {
printf("%d %d %d\n", sparseMatrix[i][0], sparseMatrix[i][1],
sparseMatrix[i][2]);
}
}

int main() {
int rows, cols;

// Input matrix size

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

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

// Convert to sparse representation

convertToSparse(rows, cols, matrix);

return 0;
}

Output:
Enter the number of rows: 3
Enter the number of columns: 3
Enter the elements of the matrix:
000123000

Sparse Matrix Representation (Row, Column, Value):

1 0 1
1 1 2
1 2 3

Transpose of sparse matrix

The transpose of a matrix is obtained by interchanging its rows and columns. In the
case of a sparse matrix, where most elements are zero, transposing efficiently
requires working with only the non-zero elements.
Matrix Operations – Transposition is useful in matrix multiplication and graph
algorithms.
Storage Optimization – Some formats (e.g., CSR, CSC) require transposition for
efficient access.
Better Performance – Avoids unnecessary operations on zero elements.
Write a program to determine the transpose of sparse
representation.

#include <stdio.h>

// Function to compute the transpose of a sparse matrix

void transposeSparse(int sparseMatrix[][3], int nonZeroCount) {
int transposed[nonZeroCount][3];

// Swap row and column indices

for (int i = 0; i < nonZeroCount; i++) {
transposed[i][0] = sparseMatrix[i][1]; // New row = Old column
transposed[i][1] = sparseMatrix[i][0]; // New column = Old row
transposed[i][2] = sparseMatrix[i][2]; // Value remains the same
}

// Sorting based on row index and then column index

for (int i = 0; i < nonZeroCount - 1; i++) {
for (int j = i + 1; j < nonZeroCount; j++) {
if (transposed[i][0] > transposed[j][0] ||
(transposed[i][0] == transposed[j][0] && transposed[i][1] >
transposed[j][1])) {
// Swap elements
int temp0 = transposed[i][0];
int temp1 = transposed[i][1];
int temp2 = transposed[i][2];

transposed[i][0] = transposed[j][0];
transposed[i][1] = transposed[j][1];
transposed[i][2] = transposed[j][2];

transposed[j][0] = temp0;
transposed[j][1] = temp1;
transposed[j][2] = temp2;
}
}
}

// Print the transposed sparse matrix

printf("\nTranspose of the Sparse Matrix (Row, Column, Value):\n");
for (int i = 0; i < nonZeroCount; i++) {
printf("%d %d %d\n", transposed[i][0], transposed[i][1], transposed[i][2]);
}
}

int main() {
int nonZeroCount;

// Input number of non-zero elements

printf("Enter the number of non-zero elements: ");
scanf("%d", &nonZeroCount);

int sparseMatrix[nonZeroCount][3];

// Input sparse matrix in triplet form

printf("Enter the sparse matrix (Row Column Value):\n");
for (int i = 0; i < nonZeroCount; i++) {
scanf("%d %d %d", &sparseMatrix[i][0], &sparseMatrix[i][1],
&sparseMatrix[i][2]);
}

// Compute the transpose

transposeSparse(sparseMatrix, nonZeroCount);
return 0;
}
Output:
Enter the number of non-zero elements: 3
Enter the sparse matrix (Row Column Value):
2 0 1
2 1 2
2 2 3

Transpose of the Sparse Matrix (Row, Column, Value):

0 2 1
1 2 2
2 2 3
1.9 Dynamic memory management:
Dynamic memory management is the process of allocating and freeing memory
blocks during a program's runtime. It is different from static memory allocation,
which is when memory is allocated during compilation. Dynamic memory
management allows programs to allocate memory on demand, rather than reserving
a fixed amount at the beginning.

There are 4 library functions provided by C defined under <stdlib.h> header file to
facilitate dynamic memory allocation in C programming. They are:
1.​ malloc ()
2.​ calloc ()
3.​ free ()
4.​ realloc ()

malloc (): It is used to dynamically allocate a single large block of memory with
the specified size.

Syntax: ptr = (cast-type*) malloc(byte-size)

Ex: int * ptr = (int*) malloc (5* sizeof(int)); // since the size of int 4 bytes, a large
20 bytes of memory block is dynamically allocated to ptr.

calloc (): It is used to dynamically allocate the specified number of blocks of

memory of the specified type.

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

Ex: int*ptr = (int*) calloc (5, sizeof(int)); //5 blocks of 4 bytes each is dynamically
allocated to ptr.

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

Syntax: free (ptr);

realloc ():It is used to dynamically change the memory allocation of a previously
allocated memory. In other words, if the memory previously allocated with the help
of malloc or calloc is insufficient, realloc can be used to dynamically to re-allocate
memory. Re-allocation of memory maintains the already present value and new
blocks will be initialized with the default garbage value.

Syntax: ptr = realloc (ptr, newSize);

C Program: Demonstrating malloc(), calloc(), realloc(), and free()

#include <stdio.h>

#include <stdlib.h>

int main() {

int *arr;

int n, i;

printf("Enter number of elements (for malloc): ");

scanf("%d", &n);

// malloc: allocate memory

arr = (int *)malloc(n * sizeof(int));

if (arr == NULL) {

printf("Memory allocation failed using malloc.\n");

return 1;

printf("\nMemory allocated using malloc:\n");

for (i = 0; i < n; i++) {

arr[i] = i + 1;

printf("%d ", arr[i]);

// free malloc block

free(arr);

printf("\n\nEnter number of elements (for calloc): ");

scanf("%d", &n);

// calloc: allocate and initialize to 0

arr = (int *)calloc(n, sizeof(int));

if (arr == NULL) {

printf("Memory allocation failed using calloc.\n");

return 1;

printf("\nMemory allocated using calloc (initialized to 0):\n");

for (i = 0; i < n; i++) {

printf("%d ", arr[i]);

// realloc: resize memory block

printf("\n\nEnter new size for realloc: ");

scanf("%d", &n);

arr = (int *)realloc(arr, n * sizeof(int));

if (arr == NULL) {

printf("Memory reallocation failed.\n");

return 1;

printf("\nMemory after realloc:\n");

for (i = 0; i < n; i++) {

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

printf("%d ", arr[i]);

// free memory

free(arr);

printf("\n\nMemory has been freed.\n");

return 0;

1.10 Abstract data types (ADT):

An ADT is a model that defines operations and behaviors for a data type without
specifying how these are implemented or how data is stored. The process of
providing only the essentials and hiding the details is known as abstraction. Using
ADTs effectively leads to optimized code performance, better readability, and
scalability, making software development more efficient and maintainable.
Choosing the right ADT for the problem at hand is key to writing efficient
programs. Abstract data types (ADTs) are a way of encapsulating data and
operations on that data into a single unit.
Key features of ADTs :
Abstraction: The user does not need to know the implementation of the data
structure only essentials are provided.

Better Conceptualization: ADT gives us a better conceptualization of the real

world.

Robust: The program is robust and has the ability to catch errors.

Encapsulation: ADTs hide the internal details of the data and provide a public
interface for users to interact with the data. This allows for easier maintenance and
modification of the data structure.

Data Abstraction: ADTs provide a level of abstraction from the implementation

details of the data. Users only need to know the operations that can be performed
on the data, not how those operations are implemented.

Data Structure Independence: ADTs can be implemented using different data

structures, such as arrays or linked lists, without affecting the functionality of the
ADT.

Information Hiding: ADTs can protect the integrity of the data by allowing access
only to authorized users and operations. This helps prevent errors and misuse of the
data.

Modularity: ADTs can be combined with other ADTs to form larger, more complex
data structures. This allows for greater flexibility and modularity in programming.

Overall, ADTs provide a powerful tool for organizing and manipulating data in a
structured and efficient manner.

Examples of ADTs:
1.​ List ADT:
The List ADT (Abstract Data Type) is a sequential collection of elements
that supports a set of operations without specifying the internal
implementation. It provides an ordered way to store, access, and modify
data.
The List ADT need to store the required data in the sequence and should have
the following operations:

●​ get(): Return an element from the list at any given position.

●​ insert(): Insert an element at any position in the list.
●​ remove(): Remove the first occurrence of any element from a non-empty
list.
●​ removeAt(): Remove the element at a specified location from a
non-empty list.
●​ replace(): Replace an element at any position with another element.
●​ size(): Return the number of elements in the list.
●​ isEmpty(): Return true if the list is empty; otherwise, return false.
●​ isFull(): Return true if the list is full; otherwise, return false.

2.​ Stack ADT:

The Stack ADT is a linear data structure that follows the LIFO (Last In, First
Out) principle. It allows elements to be added and removed only from one end,
called the top of the stack.

In Stack ADT, the order of insertion and deletion should be according to the
FILO or LIFO Principle. Elements are inserted and removed from the same end,
called the top of the stack. It should also support the following operations:

●​ push(): Insert an element at one end of the stack called the top.
●​ pop(): Remove and return the element at the top of the stack, if it is not
empty.
●​ peek(): Return the element at the top of the stack without removing it, if
the stack is not empty.
●​ size(): Return the number of elements in the stack.
●​ isEmpty(): Return true if the stack is empty; otherwise, return false.
●​ isFull(): Return true if the stack is full; otherwise, return false.

3.​ Queue ADT

The Queue ADT follows a design similar to the Stack ADT, but the order of
insertion and deletion changes to FIFO. Elements are inserted at one end (called
the rear) and removed from the other end (called the front). It should support
the following operations:

●​ enqueue(): Insert an element at the end of the queue.

●​ dequeue(): Remove and return the first element of the queue, if the queue
is not empty.
●​ peek(): Return the element of the queue without removing it, if the queue
is not empty.
●​ size(): Return the number of elements in the queue.
●​ isEmpty(): Return true if the queue is empty; otherwise, return false.

Question Bank for Module 1:

1.​ Define Data Structure and classify different types of Data Structures with
examples.
2.​ Explain the Tower of Hanoi problem and write the recurrence relation for it.
3.​ What is a Sparse Matrix? Explain with an example.
4.​ Compare iteration and recursion with an example.
5.​ Explain Abstract Data Type (ADT) with an example.
6.​ Convert the following infix expression to postfix:
(A+B)∗(C−D)/E(A + B) * (C - D) / E(A+B)∗(C−D)/E and explain the
process.
7.​ Describe the applications of Queue in real-life scenarios.
8.​ Write an algorithm to evaluate a postfix expression with an example.
9.​ Explain dynamic memory management in C/C++ with examples of malloc(),
calloc(), and free().
10.​Write an algorithm to find the transpose of a sparse matrix and explain with
an example.
11.​Discuss classification of Data Structures in detail with advantages and
disadvantages of each.
12.​Explain the Tower of Hanoi problem in detail and derive its recurrence
relation. Solve it for n=3.
13.​Describe different types of Queues and their applications. Implement a
circular queue using an array.
14.​Compare infix, postfix, and prefix expressions and explain the conversion of
infix to postfix using a stack.
15.​Explain Abstract Data Types (ADT) with examples of Stack, Queue, and
List.
16.​What is the need for data structures in programming?
17.​Explain the difference between linear and nonlinear data structures with
examples.
18.​What are the rules of the Tower of Hanoi problem?
19.​Define postfix expression and give an example of conversion from infix to
postfix.
20.​Differentiate between iteration and recursion with an example.
21.​What are the advantages of Sparse Matrices?
22.​What is dynamic memory allocation? Explain malloc() and calloc()
functions.
23.​What are the types of queues? Explain briefly.
24.​Explain Abstract Data Type (ADT) in the context of stacks.
25.​Define Queue and explain how it works with an example.
26.​Explain classification of data structures with a diagram.
27.​Write an algorithm for Tower of Hanoi and solve for n=3.
28.​What is infix, postfix, and prefix notation? Explain with examples.
29.​Write an algorithm to evaluate a postfix expression and demonstrate with an
example.
30.​Explain recursion and write a program for factorial calculation using
recursion.
31.​What is a sparse matrix? Write an algorithm to represent a sparse matrix in
triplet form.
32.​Write an algorithm to convert an infix expression to postfix expression using
a stack.
33.​What is dynamic memory management? Explain malloc(), calloc(), realloc(),
and free().
34.​Explain different types of queues (Simple Queue, Circular Queue, Deque,
Priority Queue).
35.​Explain applications of Queue in operating systems and computer science.
36.​Explain different types of data structures with advantages and disadvantages.
37.​Describe the Tower of Hanoi problem in detail, write its recurrence relation,
and solve it for n=4.
38.​Convert the following infix expression to postfix step by step and evaluate
it: (A+B)∗(C−D)/E(A + B) * (C - D) / E(A+B)∗(C−D)/E
39.​Compare iteration and recursion with an example. Write a recursive and an
iterative program for Fibonacci series.
40.​Explain Sparse Matrices with their types. Write an algorithm to find the
transpose of a sparse matrix.
41.​Explain dynamic memory management in C/C++ and demonstrate it with an
example program.
42.​Discuss Abstract Data Type (ADT) for stack and queue. Implement stack
using an array.
43.​Explain the application of queues in CPU scheduling, disk scheduling, and
network packet processing.
44.​Describe postfix evaluation with a detailed step-by-step example. Write an
algorithm for postfix evaluation.
45.​What is stack ADT? Implement a stack using a linked list and perform push,
pop, and display operations.

C - Programs:-
1.​ Write a C program to demonstrate dynamic memory allocation using
malloc() and free().
2.​ Implement a recursive function to solve the Tower of Hanoi problem for
n=3.
3.​ Write a C program to convert an infix expression to postfix using a stack.
4.​ Implement a C program to evaluate a postfix expression using a stack.
5.​ Write a C program to implement Queue using an array.
6.​ Implement a C program to represent a sparse matrix using a triplet
representation.
7.​ Write a C program to find the transpose of a sparse matrix.
8.​ Implement a C program to perform push, pop, and display operations on a
stack using an array.
9.​ Write a C program to demonstrate iteration vs recursion with an example of
the Fibonacci series.
10.​Implement a C program to perform enqueue and dequeue operations on a
circular queue using an array.
11.​Implement a C program to solve the Tower of Hanoi problem for n=4 using
recursion.
12.​Write a C program to implement a stack using a linked list with push, pop,
and display operations.
13.​Implement a C program to evaluate a postfix expression using a stack with a
step-by-step explanation.
14.​Write a C program to implement a queue using a linked list and perform
enqueue, dequeue, and display operations.
15.​Implement a C program to perform infix to postfix conversion and
evaluation using a stack.
16.​Write a C program to demonstrate dynamic memory allocation using
malloc(), calloc(), realloc(), and free().
17.​Implement a C program to insert, delete, and display elements in a
double-ended queue (Deque) using an array.
18.​Write a C program to find the transpose of a sparse matrix using an efficient
algorithm.
19.​Implement a C program to compare the execution time of iteration and
recursion using Fibonacci series computation.
20.​Write a C program to simulate CPU scheduling using a queue (Round Robin
algorithm).