SRM INSTITUTE OF SCIENCE AND TECHNOLOGY

(Regulations 2021)

21CSC201J -DATA STRUCTURES AND ALGORITHMS

LAB MANUAL

i
 EX. NO. 1
Implementation of Structures
DATE:

• Structures in C are user-defined data types that allow the grouping of related data items of
potentially different data types under a single name. They are a way to create a composite
data type that can represent a real-world entity with multiple attributes.
• Structures are defined using the struct keyword, followed by a structure name (tag), and then
a block of code containing the declarations of its member variables.
• Each variable in the structure is known as a member of the structure.
Syntax: Example:

• Declaration of Variables: After defining a structure, variables of that structure type can be
declared.
Syntax:

Example:

• Accessing Members: Individual members of a structure variable are accessed using the dot (.)
operator.
Syntax:

Example:

2
Now you can easily create multiple structure variables with different values, using just one structure:

Initialization:
Structure variables can be initialized at the time of declaration using an initializer list, or members can be
assigned values individually after declaration.

Member-wise Assignment after Declaration.

After a structure variable has been declared, its individual members can be assigned values using the dot
(.) operator (member access operator).

3
Practice Programs:
1.Create a structure called "Student" with members name, age, and total marks. Write a C program to input
data for two students, display their information, and find the average of total marks.

Program:
#include <stdio.h>

// Define the structure "Student"

struct Student {
char name[50];
int age;
float totalMarks;
};

int main() {
// Declare variables to store information for two students
struct Student student1, student2;

// Input data for the first student

printf("Input details for Student 1:\n");
printf("Name: ");
scanf("%s", student1.name); // Assuming names do not contain spaces
printf("Age: ");
scanf("%d", &student1.age);
printf("Total Marks: ");
scanf("%f", &student1.totalMarks);

// Input data for the second student

printf("\nInput details for Student 2:\n");
printf("Name: ");
scanf("%s", student2.name); // Assuming names do not contain spaces
printf("Age: ");
scanf("%d", &student2.age);
printf("Total Marks: ");
scanf("%f", &student2.totalMarks);

// Display information for both students

printf("\nStudent 1 Information:\n");
printf("Name: %s\n", student1.name);
printf("Age: %d\n", student1.age);
printf("Total Marks: %.2f\n", student1.totalMarks);

printf("\nStudent 2 Information:\n");
printf("Name: %s\n", student2.name);
printf("Age: %d\n", student2.age);
printf("Total Marks: %.2f\n", student2.totalMarks);

// Calculate and display the average total marks

4
 float averageMarks = (student1.totalMarks + student2.totalMarks) / 2;
printf("\nAverage Total Marks: %.2f\n", averageMarks);

return 0;
}
Output:
Input details for Student 1:
Name: Climacus
Age: 14
Total Marks: 189

Input details for Student 2:

Name: Meredith
Age: 14
Total Marks: 192

Student 1 Information:
Name: Climacus
Age: 14
Total Marks: 189.00

Student 2 Information:
Name: Meredith
Age: 14
Total Marks: 192.00

Average Total Marks: 190.50

2.Define a structure named Time with members hours, minutes, and seconds. Write a C program to input
two times, add them, and display the result in proper time format.
3.Create a structure named Book to store book details like title, author, and price. Write a C program to
input details for three books, find the most expensive and the lowest priced books, and display their
information.
4.Define a structure named Circle to represent a circle with a radius. Write a C program to calculate the
area and perimeter of two circles and display the results.
5.Create a structure named "Employee" to store employee details such as employee ID, name, and salary.
Write a program to input data for three employees, find the highest salary employee, and display their
information.
6. Define a structure named "Date" with members day, month, and year. Write a C program to input two
dates and find the difference in days between them.
7. Write a C program that implements a simple queue using a structure. The structure should contain an
array representing the queue and front and rear indices. Include functions for enqueue and dequeue
operations
8. Create a structure named Complex to represent a complex number with real and imaginary parts. Write
a C program to add and multiply two complex numbers.
9. Design a structure named "Car" to store details like car ID, model, and rental rate per day. Write a C
program to input data for three cars, calculate the total rental cost for a specified number of days, and
display the results.

5
 EX. NO. 2
Implementation of Structures using Pointers
DATE:

Structures can be effectively implemented and manipulated using pointers in C and C++. This
approach offers flexibility and efficiency, particularly when dealing with large structures, dynamic
memory allocation, or passing structures to functions.
1. Declaring and Initializing a Structure Pointer:
A structure pointer is declared by placing an asterisk (*) before the pointer variable name, similar
to declaring pointers to other data types. It must be of the same type as the structure it will point
to.

To initialize the pointer, assign it the memory address of an existing structure variable using the address-
of operator (&).

2. Accessing Structure Members using Pointers:

When a pointer points to a structure, its members are accessed using the arrow operator (->). This operator
dereferences the pointer and then accesses the specified member.

3. Dynamic Memory Allocation for Structures:

Pointers are crucial for dynamically allocating memory for structures during runtime, often
using malloc() (in C) or new (in C++).

6
4. Passing Structures to Functions using Pointers:
Passing a structure by value to a function creates a copy, which can be inefficient for large
structures. Passing by pointer avoids this copying, improving performance.

Practice Programs:
1. Write a program in C to demonstrate the use of the &(address of) and *(value at address)
operators.
2. Write a program in C to store n elements in an array and print the elements using a pointer.
3. Write a C program to demonstrate how a function returns a pointer.
4. Write a program in C to find the largest element using Dynamic Memory Allocation.
5. Write a program in C to demonstrate the use of pointers to structures.
6. Write a program in C to show a pointer to an array whose contents are pointers to structures.

7
 EX. NO. 3 Implementation of matrix Multiplication – Dynamic
DATE: Memory Allocation

Dynamic memory allocation in C refers to the process of allocating and deallocating memory
during program execution (runtime) rather than at compile time. This allows for flexible memory
management, especially when dealing with data structures or data sizes that are unknown or can
change during the program's lifetime.

Key Functions for Dynamic Memory Allocation in C:

malloc() (memory allocation):

• Allocates a block of memory of a specified size in bytes.

• Returns a void pointer to the beginning of the allocated block, or NULL if allocation
fails.
• The allocated memory is not initialized and contains garbage values.

calloc() (contiguous allocation):

• Allocates a block of memory for a specified number of elements, each of a given size.
• Initializes all bytes in the allocated memory to zero.
• Returns a void pointer to the beginning of the allocated block, or NULL if allocation
fails.

#include <stdlib.h> // Required for calloc

int *ptr = (int *)calloc(5, sizeof(int)); // Allocates space for 5 integers and initializes to 0

realloc() (re-allocation):

• Changes the size of a previously allocated memory block.

• Can increase or decrease the size.
• Returns a void pointer to the new memory block, or NULL if re-allocation fails.

8
free():

• Deallocates memory previously allocated by malloc(), calloc(), or realloc().

• Releases the memory back to the system, preventing memory leaks.

Importance of Dynamic Memory Allocation:

• Flexibility: Allows programs to adapt to varying data sizes during runtime.

• Efficient Memory Usage: Allocates memory only when needed and releases it when no longer
required, optimizing resource utilization.
• Handling Dynamic Data Structures: Essential for implementing data structures like linked
lists, trees, and graphs, where the size and structure can change dynamically.

Implementing matrix multiplication with dynamic memory allocation in C offers flexibility,

especially when matrix dimensions are not known at compile time. This approach involves
allocating memory for the matrices during program execution using functions
like malloc or calloc in C.

Steps for Implementation:

Include necessary headers.

Declare pointers to pointers:

For a 2D matrix, a pointer to a pointer (e.g., int **matrix) is used to represent the matrix. This
allows for allocating an array of pointers, where each pointer then points to a row of the matrix.

9
Get matrix dimensions from the user:

Prompt the user to enter the number of rows and columns for both matrices. Validate that the
number of columns of the first matrix equals the number of rows of the second matrix, as this is
a requirement for matrix multiplication.

Allocate memory for each matrix:

• Allocate memory for the array of row pointers: matrix = (int **)malloc(rows * sizeof(int *));
• For each row, allocate memory for the elements in that row: matrix[i] = (int *)malloc(cols *
sizeof(int));

Input matrix elements:

Use nested loops to prompt the user to enter elements for each matrix and store them in the
dynamically allocated memory.

Perform matrix multiplication:

• Allocate memory for the result matrix using the appropriate dimensions (rows of the first
matrix, columns of the second matrix).
• Implement the standard matrix multiplication algorithm using three nested loops:

• Display the result matrix: Print the elements of the dynamically allocated result matrix.

• Free allocated memory: It is crucial to deallocate the dynamically allocated memory

after use to prevent memory leaks. This involves freeing memory for each row and then
freeing the array of row pointers for all matrices:

#include <stdio.h>

10
#include <stdlib.h>

void multiplyMatrices(int **mat1, int r1, int c1, int **mat2, int r2, int c2, int **result) {

int i, j, k;

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

for (j = 0; j < c2; j++) {

result[i][j] = 0;

for (k = 0; k < c1; k++) {

result[i][j] += mat1[i][k] * mat2[k][j];

int main() {

int r1, c1, r2, c2;

int **mat1, **mat2, **result;

int i;

printf("Enter rows and columns for first matrix: ");

scanf("%d %d", &r1, &c1);

printf("Enter rows and columns for second matrix: ");

scanf("%d %d", &r2, &c2);

if (c1 != r2) {

printf("Error: Columns of first matrix must be equal to rows of second matrix for
multiplication.\n");

return 1;

// Allocate memory for matrices

mat1 = (int **)malloc(r1 * sizeof(int *));

11
for (i = 0; i < r1; i++) mat1[i] = (int *)malloc(c1 * sizeof(int));

mat2 = (int **)malloc(r2 * sizeof(int *));

for (i = 0; i < r2; i++) mat2[i] = (int *)malloc(c2 * sizeof(int));

result = (int **)malloc(r1 * sizeof(int *));

for (i = 0; i < r1; i++) result[i] = (int *)malloc(c2 * sizeof(int));

printf("Enter elements of first matrix:\n");

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

for (int j = 0; j < c1; j++) {

scanf("%d", &mat1[i][j]);

printf("Enter elements of second matrix:\n");

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

for (int j = 0; j < c2; j++) {

scanf("%d", &mat2[i][j]);

multiplyMatrices(mat1, r1, c1, mat2, r2, c2, result);

printf("\nResultant Matrix:\n");

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

for (int j = 0; j < c2; j++) {

printf("%d\t", result[i][j]);

printf("\n");

// Free allocated memory

for (i = 0; i < r1; i++) free(mat1[i]);

12
 free(mat1);

for (i = 0; i < r2; i++) free(mat2[i]);

free(mat2);

for (i = 0; i < r1; i++) free(result[i]);

free(result);

return 0;

Practice Programs:

1. Create a program that dynamically allocates memory for an array of integers. Allow the user to
input the size of the array and elements, and then print the array.
2. Implement a program to perform matrix addition and multiplication using dynamic memory
allocation. Allow the user to input the dimensions and elements of the matrices.
3. Write a program that takes a string as input, dynamically allocates memory to store the reversed
string, and then prints the reversed string.
4. Write a program that concatenates two strings using dynamic memory allocation. Allocate
memory only for the resulting string.
5. Define a structure representing a student with name, roll number, and marks. Dynamically
allocate memory for an array of such structures and allow the user to input and display the data.

13
 EX. NO. 4
Array Implementation of List
DATE:

Array Implementation of list: Array: A set of data elements of same data type is called array. Array
is a static data structure i.e., the memory should be allocated in advance and the size is fixed. This
will waste the memory space when used space is less than the allocated space. An array
implementation allows the following operations.

The basic operations are:

a. Creation of a List.

b. Insertion of a data in the List

c. Deletion of a data from the List

d. Searching of a data in the list

Global Declaration:

int list[25], index=-1;

Note: The initial value of index is -1.

a. Create Operation:

Procedure

• The list is initially created with a set of elements.

• Get the no. of elements (n) to be added in the list.

• Check n is less than or equal to maximum size. If yes, add the elements to the list.

• Otherwise, give an error message

Program

void create() {

int n,i;

14
printf("\nEnter the no.of elements to be added in the list");

scanf("%d",&n); if(n<=maxsize) for(i=0;i<n;i++)

scanf("%d",&list[i]); index++;

Else

printf("\nThe size is limited. You cannot add data into the list");

b.Insert Operation:

Procedure:

• Get the data element to be inserted.

• Get the position at which element is to be inserted.

• If index is less than or equal to maxsize, then Make that position empty by altering the position of
the elements

in the list.

• Insert the element in the poistion.

• Otherwise, it implies that the list is empty.

Program

void insert()

int i,data,pos;

printf("\nEnter the data to be inserted");

scanf("%d",&data);

15
printf("\nEnter the position at which element to be inserted");

scanf("%d",&pos);

if(index<maxsize)

for(i=index;i>=pos-1;i--)

list[i+1]=list[i];

index++;

list[pos-1]=data

else

printf("\nThe list is full");

c.Deletion

Procedure

• Get the position of the element to be deleted.

• Alter the position of the elements by performing an assignment operation, list[i-1]=list[i], where i
value ranges

from position to the last index of the array.

Program:

void del()

int i,pos;

printf("\nEnter the position of the data to be deleted");

16
scanf("%d",&pos);

printf("\nThe data deleted is %d",list[pos-1]);

for(i=pos;i<=index;i++)

list[i-1]=list[i];

index--;

d.Display

Procedure

• Formulate a loop, where i value ranges from 0 to index (index denotes the index of the last
element in the array.

• Display each element in the array.

Program

void display()

int i; for(i=0;i<=index;i++) printf("\t%d",list[i]);

Limitation of array implementation

• An array size is fixed at the start of execution and can store only the limited number of elements.

• Insertion and deletion of array are expensive. Since insertion is performed by pushing the entire

array one position down and deletion is performed by shifting the entire.

17
In C programming, an "array using a list" typically refers to the array-based implementation of a
List Abstract Data Type (ADT). This means using a standard C array to store the elements of a list,
where the list's operations (like insertion, deletion, display) are implemented using array
manipulations.

Here's how you can conceptualize and implement a list using an array in C:

1. Data Structure Definition:

You define a structure to represent your list, which includes an array to store elements and a
variable to keep track of the current number of elements (or length) in the list.

2. List Operations:

You then implement functions to perform common list operations:

Initialization: Sets the length to 0.

18
Insertion: Adds an element at a specific position. This often requires shifting existing elements.

Deletion: Removes an element from a specific position. This also often requires shifting.

Display: Prints all elements in the list.

Fixed Size:

Array-based lists have a fixed maximum size defined at compile time. If you need a dynamically
resizable list, you would typically use dynamic memory allocation (malloc, realloc) or a linked list.

Efficiency:

Insertion and deletion in the middle of an array-based list can be inefficient as it requires shifting
elements. Accessing elements by index is very efficient (O(1)).

19
Practice Progams:

1. Write a program in C to read n number of values in an array and display them in reverse
order.
2. Write a program in C to count the total number of duplicate elements in an array.
3. Write a program in C to merge two arrays of the same size sorted in descending order.
4. Write a program in C to traverse the array [3, 1, 4, 5, 2] from the start and insert each
element at the end of the linked list.
(or)
You are given an array nums[] of length n. The task is to create a linked list from the given
array.
Example
Input
n=5
nums[] = {3, 1, 4, 5, 2};

Output:

20
 EX. NO. 5

DATE: IMPLEMENTATION OF LINKED LIST

A linked list in C is a linear data structure implemented using structures and pointers, where
each element, called a node, contains data and a pointer to the next node in the sequence.

1. Node Structure Definition:

A struct is used to define the node, typically containing an integer data field and a self-referential
pointer next of the same structure type.

2. Basic Operations:

Creation:

Nodes are dynamically allocated using malloc().

Insertion:

• At the beginning: A new node's next pointer points to the current head, and the head is
updated to the new node.
• At the end: The list is traversed to find the last node, and its next pointer is set to the new
node.
• At a specific position: The list is traversed to the desired position, and pointers are adjusted
to insert the new node.

Deletion:

• From the beginning: The head pointer is moved to the next node, and the old head node is
freed.
• From the end: The list is traversed to find the second-to-last node, and its next pointer is set
to NULL. The last node is freed.
• A specific node: The list is traversed to find the node to be deleted and its preceding
node. The preceding node's next pointer is updated to bypass the deleted node, and the
deleted node is freed.

Traversal:

The list is iterated from the head, printing the data of each node until a NULL pointer is
encountered.

21
Searching:

The list is traversed, comparing the data of each node with the target value until a match is found
or the end of the list is reached.

Example (Insertion at the End and Traversal):

#include <stdio.h>

#include <stdlib.h>

struct Node {

int data;

struct Node* next;

};

// Function to add a node at the end

void addLast(struct Node** head, int val) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = val;

newNode->next = NULL;

if (*head == NULL) {

*head = newNode;

} else {

struct Node* lastNode = *head;

while (lastNode->next != NULL) {

lastNode = lastNode->next;

lastNode->next = newNode;

// Function to print the linked list

void printList(struct Node* head) {

22
 struct Node* temp = head;

while (temp != NULL) {

printf("%d -> ", temp->data);

temp = temp->next;

printf("NULL\n");

int main() {

struct Node* head = NULL; // Initialize an empty linked list

addLast(&head, 10);

addLast(&head, 20);

addLast(&head, 30);

printList(head); // Output: 10 -> 20 -> 30 -> NULL

return 0;

Practice Programs:

1. Write a program in C to create and display a Singly Linked List.

2. Write a program in C to create a singly linked list of n nodes and display it in reverse order.
3. Write a program in C to create a singly linked list of n nodes and count the number of nodes.
4. Write a program in C to insert a new node at the beginning of a Singly Linked List.
5. Write a program in C to search for an existing element in a singly linked list.
6. Write a C program that converts a singly linked list into an array and returns it.
7. Write a C program to check if a singly linked list is a palindrome or not.
8. Write a C program to create a copy of a singly linked list with random pointers.
9. Write a C program that takes two linked lists of numbers. Each node contains a single digit
and returns the sum of those numbers of said linked lists as a linked list.
10. Write a C program to find a pair in a singly linked list whose sum is equal to a given value.

Test Data and Expected Output :

Original singly linked list:

1 234567

Find a pair whose sum is equal to 4:

23
(1,3)

Find a pair whose sum is equal to 11:

(4,7) (5,6)

Find a pair whose sum is equal to 5:

(1,4) (2,3)

Find a pair whose sum is equal to 14:

Pair not found.

24