MINISTRY OF EDUCATION, CULTURE AND RESEARCH

OF THE REPUBLIC OF MOLDOVA

Technical University of Moldova
Faculty of Computers, Informatics and Microelectronics
Department of Software and Automation Engineering

NAME SURNAME STUDENT

Report
Laboratory Work No.4

of the "Data Structures and Algorithms" course

Checked:
Burlacu Natalia, PhD, associate professor
Department of Software and Automation Engineering,
FCIM Faculty, UTM

Chisinau – 2023

1
 1. The purpose of the laboratory work
The objective of this lab work is to enhance my practical C programming skills
through the implementation and modification of complex algorithms, particularly
focusing on dynamic memory management, subarray sum calculations, and sorting
techniques. Throughout this lab, I have been tasked with identifying all subarrays
within a 2D matrix that sum up to a given value. This process required me to
adeptly manage memory dynamically, ensuring efficient allocation, usage, and
deallocation to prevent leaks and ensure program stability.In addition to subarray
identification, I have delved into sorting algorithms, specifically adapting the
Quick Sort and Radix Sort algorithms to sort matrix columns under certain
conditions. Also we had to learn working with structures, and to optimize it using
bitwise operators and unions.
Condition

Task:

2
Problems:

2. The program code

Principal.c
(where i appeal to version 1 or 2)
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include "structure.h" // Assumes this header file declares functions for
the struct-based approach
#include "structure2.h" // Assumes this header file declares functions for
the union-based approach

int main() {
int mainChoice;
printf("Use the program with:\n");
printf("1. Struct\n");
printf("2. Union\n");
printf("Enter your choice: ");

if (scanf("%d", &mainChoice) != 1) {
3
 printf("Invalid input. Exiting.\n");
return 1; // Early return if the choice input fails
}
if (mainChoice == 1) {
int choice;
int num_equipment = 0; // Keeps track of the number of equipment
entries
struct Equipment* equipmentArray = NULL; // Pointer to the array
of Equipment structures

while (1) {
printf("\nMenu:\n");
printf("1. Input new equipment\n");
printf("2. Display all equipment\n");
printf("3. Sort by type (ascending) \n");
printf("4. Sort by registration number (ascending) \n");
printf("5. Change the informations in base of reg_num\n");
printf("6. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
num_equipment++;
equipmentArray = realloc(equipmentArray,
num_equipment * sizeof(struct Equipment));

inputEquipment(&equipmentArray[num_equipment - 1]);
break;
case 2: // Display all equipment
for (int i = 0; i < num_equipment; ++i) {
displayEquipment(&equipmentArray[i]);
}
break;
case 3: // Sort by type (ascending)
quickSort(equipmentArray, 0, num_equipment-1);
printf("\nSorted by type (ascending):\n");
for (int i = 0; i < num_equipment; i++) {
displayEquipment(&equipmentArray[i]);
}
break;
case 4:
radixSort(equipmentArray, num_equipment);
printf("\nSorted by registration number (ascending):\
n");
for (int i = 0; i < num_equipment; i++) {
displayEquipment(&equipmentArray[i]);
}
break;
case 5: // Modify existing equipment by registration
number
modifyEquipmentByRegNum(equipmentArray,
num_equipment);
break;
case 6: // Exit
// Free the allocated memory before exiting
for (int i = 0; i < num_equipment; ++i) {
// Assume we have a function to free the
internals of an Equipment
freeEquipment(&equipmentArray[i]);
}
free(equipmentArray);
printf("Exiting program.\n");

4
 return 0;
default:
printf("Invalid choice. Please try again.\n");
}
}

} else if (mainChoice == 2) {
int choice;
int num_equipment = 0; // Keeps track of the number of equipment
entries
struct Equipment2* equipmentArray = NULL; // Pointer to the array
of Equipment structures

while (1) {
clearScreen();
printf("\nMenu:\n");
printf("1. Input new equipment\n");
printf("2. Display all equipment\n");
printf("3. Sort by type (ascending) \n");
printf("4. Sort by registration number (ascending) \n");
printf("5. Change the informations in base of reg_num\n");
printf("6. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1: // Input new equipment
equipmentArray = realloc(equipmentArray,
(num_equipment + 1) * sizeof(struct Equipment2));
if (equipmentArray == NULL) {
printf("Memory allocation failed\n");
exit(1); // Exit if we fail to allocate memory
}
inputEquipmentu(&equipmentArray[num_equipment]);
num_equipment++;
break;
case 2: // Display all equipment
for (int i = 0; i < num_equipment; ++i) {
displayEquipmentu(&equipmentArray[i]);
}
getch(); // Wait for user input to continue
break;
case 3: // Sort by type (ascending)
quickSortu(equipmentArray, 0, num_equipment-1);
printf("\nSorted by type (ascending):\n");
for (int i = 0; i < num_equipment; i++) {
displayEquipmentu(&equipmentArray[i]);
}
break;
case 4:
radixSortu(equipmentArray, num_equipment);
printf("\nSorted by registration number (ascending):\
n");
for (int i = 0; i < num_equipment; i++) {
displayEquipmentu(&equipmentArray[i]);
}
break;
case 5: // Modify equipment by registration number
modifyEquipmentByRegNumu(equipmentArray,
num_equipment);
getch(); // Wait for user input to continue
break;

5
 case 6: // Exit
// Free the allocated memory before exiting
for (int i = 0; i < num_equipment; ++i) {
freeEquipmentu(&equipmentArray[i]);
}
free(equipmentArray);
equipmentArray = NULL;
printf("Exiting program.\n");
return 0; // Return from version2 to end the program
default:
printf("Invalid choice. Please try again.\n");
getch(); // Wait for user input to continue
}
}
}
return 0;
}
Version 1 that uses streucture
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <ctype.h>
#include "structure.h"

void clearScreen() {
// Clear the console screen
#ifdef _WIN32
system("cls");
#else
system("clear");
#endif
}
// Function to input details into provided Equipment structure
void inputEquipment(struct Equipment* equip) {
// Allocate memory for the strings within the structure
equip->type = malloc(50 * sizeof(char));
equip->brand = malloc(50 * sizeof(char));
equip->color = malloc(50 * sizeof(char));
equip->owner_info.name = malloc(50 * sizeof(char));
equip->owner_info.surname = malloc(50 * sizeof(char));
equip->owner_info.id_code = malloc(50 * sizeof(char));

printf("Enter registration number: ");

scanf("%d", &equip->reg_num);

printf("Enter equipment type: ");

scanf("%49s", equip->type);

printf("Enter brand: ");

scanf("%49s", equip->brand);

printf("Enter color: ");

scanf("%49s", equip->color);

printf("Enter inspection date (dd mm yyyy): ");

scanf("%d %d %d", &equip->inspection_date.day, &equip-
>inspection_date.month, &equip->inspection_date.year);

printf("Enter owner's identification code: ");

scanf("%49s", equip->owner_info.id_code);

6
 printf("Enter owner's name: ");
scanf("%49s", equip->owner_info.name);

printf("Enter owner's surname: ");

scanf("%49s", equip->owner_info.surname);
}

void displayEquipment(struct Equipment* equip) {

printf("\nEquipment Details:\n");
printf("Registration Number: %d\n", equip->reg_num);
printf("Type: %s\n", equip->type);
printf("Brand: %s\n", equip->brand);
printf("Color: %s\n", equip->color);
printf("Inspection Date: %02d/%02d/%04d\n", equip->inspection_date.day,
equip->inspection_date.month, equip->inspection_date.year);
printf("Owner's ID Code: %s\n", equip->owner_info.id_code);
printf("Owner's Name: %s\n", equip->owner_info.name);
printf("Owner's Surname: %s\n", equip->owner_info.surname);
}
void freeEquipment(struct Equipment *equip) {
// Check if the pointers are not NULL before calling free
if (equip->type) {
free(equip->type);
equip->type = NULL; // Set the pointer to NULL after freeing
}
if (equip->brand) {
free(equip->brand);
equip->brand = NULL; // Set the pointer to NULL after freeing
}
if (equip->color) {
free(equip->color);
equip->color = NULL; // Set the pointer to NULL after freeing
}
if (equip->owner_info.name) {
free(equip->owner_info.name);
equip->owner_info.name = NULL; // Set the pointer to NULL after
freeing
}
if (equip->owner_info.surname) {
free(equip->owner_info.surname);
equip->owner_info.surname = NULL; // Set the pointer to NULL after
freeing
}
if (equip->owner_info.id_code) {
free(equip->owner_info.id_code);
equip->owner_info.id_code = NULL; // Set the pointer to NULL after
freeing
}
// No need to free the structure itself if it wasn't allocated
dynamically
}
void swap(struct Equipment* a, struct Equipment* b) {
struct Equipment t = *a;
*a = *b;
*b = t;
}
int partition(struct Equipment arr[], int low, int high) {
struct Equipment pivot = arr[high];
int i = (low - 1);

for (int j = low; j <= high - 1; j++) {

if (strcmp(arr[j].type, pivot.type) <= 0) {
i++;

7
 swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(struct Equipment* arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);
}
}

int getMax(struct Equipment arr[], int n) {

int mx = arr[0].reg_num;
for (int i = 1; i < n; i++)
if (arr[i].reg_num > mx)
mx = arr[i].reg_num;
return mx;
}

// A function to do counting sort of arr[] according to the digit represented

by exp (exponent)
void countSort(struct Equipment arr[], int n, int exp) {
struct Equipment *output = (struct Equipment *)malloc(n * sizeof(struct
Equipment)); // Output array
int i, count[10] = {0};

// Store count of occurrences in count[]

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

// Change count[i] so that count[i] now contains actual position of this

digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];

// Build the output array

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

// Copy the output array to arr[], so that arr[] now contains sorted
numbers according to current digit
for (i = 0; i < n; i++)
arr[i] = output[i];

// Free the memory used for the output array

free(output);
}

// The main function to that sorts arr[] of size n using Radix Sort
void radixSort(struct Equipment arr[], int n) {
// Find the maximum number to know the number of digits
int m = getMax(arr, n);

// Do counting sort for every digit. Note that instead of passing digit

8
number, exp is passed. exp is 10^i where i is current digit number
for (int exp = 1; m / exp > 0; exp *= 10)
countSort(arr, n, exp);
}
void modifyEquipmentByRegNum(struct Equipment* equipmentArray, int
num_equipment) {
int reg_num;
char input[50]; // General purpose input buffer for user responses
printf("Enter registration number of the equipment to modify: ");
scanf("%d", &reg_num);
getchar(); // To consume the newline character after number input

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

if (equipmentArray[i].reg_num == reg_num) {
printf("Matching equipment found. Registration Number: %d\n",
reg_num);

printf("Do you want to change the type? (y/n): ");

if (scanf(" %49s", input) && tolower(input[0]) == 'y') {
printf("Enter new equipment type: ");
scanf("%49s", input);
// Reallocate memory for the new type and copy it
free(equipmentArray[i].type);
equipmentArray[i].type = strdup(input);
}

printf("Do you want to change the brand? (y/n): ");

if (scanf(" %49s", input) && tolower(input[0]) == 'y') {
printf("Enter new brand: ");
scanf("%49s", input);
// Reallocate memory for the new brand and copy it
free(equipmentArray[i].brand);
equipmentArray[i].brand = strdup(input);
}

printf("Do you want to change the color? (y/n): ");

if (scanf(" %49s", input) && tolower(input[0]) == 'y') {
printf("Enter new color: ");
scanf("%49s", input);
// Reallocate memory for the new color and copy it
free(equipmentArray[i].color);
equipmentArray[i].color = strdup(input);
}

printf("Do you want to change the inspection date? (y/n): ");

if (scanf(" %49s", input) && tolower(input[0]) == 'y') {
printf("Enter new inspection date (dd mm yyyy): ");
scanf("%d %d %d", &equipmentArray[i].inspection_date.day,
&equipmentArray[i].inspection_date.month,
&equipmentArray[i].inspection_date.year);
}

printf("Equipment with registration number %d has been updated

successfully.\n", reg_num);
return;
}
}
printf("No matching equipment found with the registration number %d.\n",
reg_num);
}

Version 2 that uses unions and bitwise

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

#include "structure2.h"

unsigned int packDate(int day, int month, int year) {

return ((year << (DAY_BITS + MONTH_BITS)) | (month << DAY_BITS) | day);
}

void unpackDate(unsigned int packedDate, int* day, int* month, int* year) {
*day = packedDate & DAY_MASK;
*month = (packedDate >> DAY_BITS) & ((1 << MONTH_BITS) - 1);
*year = (packedDate >> (DAY_BITS + MONTH_BITS));
}

void inputEquipmentu(struct Equipment2* equip) {

equip->type = malloc(50 * sizeof(char));
equip->brand = malloc(50 * sizeof(char));
equip->color = malloc(50 * sizeof(char));
equip->owner_info.name = malloc(50 * sizeof(char));
equip->owner_info.surname = malloc(50 * sizeof(char));

printf("Enter registration number: ");

scanf("%d", &equip->reg_num);

printf("Enter equipment type: ");

scanf("%49s", equip->type);

printf("Enter brand: ");

scanf("%49s", equip->brand);

printf("Enter color: ");

scanf("%49s", equip->color);

printf("Enter owner's ID as a string or number (s/n): ");

char type;
scanf(" %c", &type); // Note the space before %c to consume any leftover
whitespace
if (type == 's') {
equip->owner_info.id.str_id = malloc(50 * sizeof(char));
scanf("%49s", equip->owner_info.id.str_id);
} else if (type == 'n') {
scanf("%u", &equip->owner_info.id.int_id);
}

printf("Enter owner's name: ");

scanf("%49s", equip->owner_info.name);

printf("Enter owner's surname: ");

scanf("%49s", equip->owner_info.surname);

printf("Enter inspection date (dd mm yyyy): ");

int day, month, year;

10
 scanf("%d %d %d", &day, &month, &year);
equip->inspection_date.packedDate = packDate(day, month, year);

void displayEquipmentu(const struct Equipment2* equip) {

printf("\nEquipment Details:\n");
printf("Registration Number: %d\n", equip->reg_num);
printf("Type: %s\n", equip->type);
printf("Brand: %s\n", equip->brand);
printf("Color: %s\n", equip->color);

int day, month, year;

unpackDate(equip->inspection_date.packedDate, &day, &month, &year);
printf("Inspection Date: %02d/%02d/%04d\n", day, month, year);

if (equip->owner_info.id.str_id != NULL) {
printf("Owner's ID: %s\n", equip->owner_info.id.str_id);
} else {
printf("Owner's ID Code: %u\n", equip->owner_info.id.int_id);
}printf("Owner's Name: %s\n", equip->owner_info.name);
printf("Owner's Surname: %s\n", equip->owner_info.surname);
}

void freeEquipmentu(struct Equipment2 *equip) {

free(equip->type);
free(equip->brand);
free(equip->color);
free(equip->owner_info.name);
free(equip->owner_info.surname);
free(equip->owner_info.id.str_id);

}
void modifyEquipmentByRegNumu(struct Equipment2* equipmentArray, int
num_equipment) {
int reg_num;
printf("Enter registration number of the equipment to modify: ");
scanf("%d", &reg_num);

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

if (equipmentArray[i].reg_num == reg_num) {
printf("Matching equipment found for registration number: %d\n",
reg_num);

char input[50]; // General input buffer for user responses

printf("Do you want to change the type? (y/n): ");
scanf("%s", input);
if (tolower(input[0]) == 'y') {
printf("Enter new equipment type: ");
scanf("%49s", input);
free(equipmentArray[i].type);
equipmentArray[i].type = strdup(input);
}

printf("Do you want to change the brand? (y/n): ");

scanf("%s", input);
if (tolower(input[0]) == 'y') {
printf("Enter new brand: ");

11
 scanf("%49s", input);
free(equipmentArray[i].brand);
equipmentArray[i].brand = strdup(input);
}

printf("Do you want to change the color? (y/n): ");

scanf("%s", input);
if (tolower(input[0]) == 'y') {
printf("Enter new color: ");
scanf("%49s", input);
free(equipmentArray[i].color);
equipmentArray[i].color = strdup(input);
}

printf("Do you want to change the owner's name? (y/n): ");

scanf("%s", input);
if (tolower(input[0]) == 'y') {
printf("Enter new owner's name: ");
scanf("%49s", input);
free(equipmentArray[i].owner_info.name);
equipmentArray[i].owner_info.name = strdup(input);
}

printf("Do you want to change the owner's surname? (y/n): ");

scanf("%s", input);
if (tolower(input[0]) == 'y') {
printf("Enter new owner's surname: ");
scanf("%49s", input);
free(equipmentArray[i].owner_info.surname);
equipmentArray[i].owner_info.surname = strdup(input);
}

printf("Do you want to change the owner's ID (string) or code

(number)? (s/n): ");
char type;
scanf(" %c", &type); // Note the space before %c to consume any
leftover whitespace
if (type == 's') {
printf("Enter new owner's ID (string): ");
scanf("%49s", input);
free(equipmentArray[i].owner_info.id.str_id);
equipmentArray[i].owner_info.id.str_id = strdup(input);
} else if (type == 'n') {
printf("Enter new owner's ID code (number): ");
scanf("%u", &equipmentArray[i].owner_info.id.int_id);
}

printf("Do you want to change the inspection date? (y/n): ");

scanf("%s", input);
if (tolower(input[0]) == 'y') {
int day, month, year;
printf("Enter new inspection date (dd mm yyyy): ");
scanf("%d %d %d", &day, &month, &year);
equipmentArray[i].inspection_date.packedDate = packDate(day,
month, year);
}

printf("Equipment updated successfully.\n");

return; // Exit the loop after modifying the equipment
}
}

12
 printf("No equipment found with registration number %d.\n", reg_num);
}
void swap2(struct Equipment2* a, struct Equipment2* b) {
struct Equipment2 t = *a;
*a = *b;
*b = t;
}
int partition2(struct Equipment2 arr[], int low, int high) {
struct Equipment2 pivot = arr[high];
int i = (low - 1);

for (int j = low; j <= high - 1; j++) {

if (strcmp(arr[j].type, pivot.type) <= 0) {
i++;
swap2(&arr[i], &arr[j]);
}
}
swap2(&arr[i + 1], &arr[high]);
return (i + 1);
}

void quickSortu(struct Equipment2 arr[], int low, int high) {

if (low < high) {
int pi = partition2(arr, low, high);

quickSortu(arr, low, pi - 1);

quickSortu(arr, pi + 1, high);
}
}
int getMax2(struct Equipment2 arr[], int n) {
int mx = arr[0].reg_num;
for (int i = 1; i < n; i++)
if (arr[i].reg_num > mx)
mx = arr[i].reg_num;
return mx;
}

// A function to do counting sort of arr[] according to the digit represented

by exp (exponent)
void countSort2(struct Equipment2 arr[], int n, int exp) {
struct Equipment2 *output = (struct Equipment2 *)malloc(n * sizeof(struct
Equipment2)); // Output array
int i, count[10] = {0};

// Store count of occurrences in count[]

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

// Change count[i] so that count[i] now contains actual position of this

digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];

// Build the output array

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

// Copy the output array to arr[], so that arr[] now contains sorted
numbers according to current digit

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

// Free the memory used for the output array

free(output);
}

// The main function to that sorts arr[] of size n using Radix Sort
void radixSortu(struct Equipment2 arr[], int n) {
// Find the maximum number to know the number of digits
int m = getMax2(arr, n);

// Do counting sort for every digit. Note that instead of passing digit
number, exp is passed. exp is 10^i where i is current digit number
for (int exp = 1; m / exp > 0; exp *= 10)
countSort2(arr, n, exp);
}

Structure1.h

#ifndef STRUCTURE_H
#define STRUCTURE_H

struct Date {

int day; // Separate day field

int month; // Separate month field
int year; // Separate year field

};

struct Owner {
char* name;
char* surname;

char* id_code; // Straightforward string for ID

};

struct Equipment {
int reg_num;
char* type;
char* brand;
char* color;
struct Date inspection_date;
struct Owner owner_info;
};
void inputEquipment(struct Equipment* equip);
void displayEquipment(struct Equipment* equip);
void freeEquipment(struct Equipment *equip);
void quickSort(struct Equipment* arr[], int low, int high);
void modifyEquipmentByRegNum(struct Equipment* equipmentArray, int
num_equipment);
void radixSort(struct Equipment arr[], int n);

#endif // STRUCTURE_H
Structure2.h

#ifndef STRUCTURE2_H
#define STRUCTURE2_H

#define DAY_MASK 0x1F

#define DAY_BITS 5

14
#define MONTH_BITS 4
#define MONTH_MASK (0xF << DAY_BITS)
#define YEAR_MASK (0xFFF << (DAY_BITS + MONTH_BITS))

// Structures that support both versions

struct Date2 {
unsigned int packedDate; // Packed date using bitwise operators
};

struct Owner2 {
char* name;
char* surname;
union ID {
char* str_id;
unsigned int int_id;
} id;
};

struct Equipment2 {
int reg_num;
char* type;
char* brand;
char* color;
struct Date2 inspection_date;
struct Owner2 owner_info;
};

unsigned int packDate(int day, int month, int year);

void unpackDate(unsigned int packedDate, int* day, int* month, int* year);
void clearScreen();
void inputEquipmentu(struct Equipment2* equip);
void displayEquipmentu(const struct Equipment2* equip);
void freeEquipmentu(struct Equipment2 *equip);
void modifyEquipmentByRegNumu(struct Equipment2* equipmentArray, int
num_equipment);
void quickSortu(struct Equipment2 arr[], int low, int high);
void radixSortu(struct Equipment2 arr[], int n);

#endif // STRUCTURE2_H

3. Screenshots of the results

4. Conclusions

The laboratory work focusing on structures, unions, and bitwise operations serves as a
fundamental exploration into the efficient manipulation and storage of data in C programming.
Through this hands-on approach, learners are introduced to advanced aspects of data
management and optimization techniques that are pivotal for developing performant and
15
resource-efficient applications.Structures provide a means to aggregate different data types into a
single unit, facilitating complex data handling. By using structures, programmers can create
more organized and readable code, which is essential for representing objects or entities within
software applications. This lab work emphasizes not just the creation of structures but also their
practical application in managing data more coherently.Unions, on the other hand, introduce an
effective way to manage memory by allowing different data types to share the same memory
location. Through lab exercises, the utility of unions in scenarios where variable types may
change or where memory footprint is a critical consideration becomes evident. Unions
underscore the flexibility of C in handling data, illustrating how to economize memory usage
without compromising functionality.Bitwise operations further the discussion on optimization by
delving into the manipulation of individual bits. These operations are instrumental in tasks
requiring compact data representation, encryption, quick arithmetic operations, or direct
hardware manipulation. The laboratory work showcases how bitwise operations can serve as a
powerful tool for optimization, allowing for operations that are both speed-efficient and
memory-efficient.

16