Data structures(assignment -1)
1Q.
Data Structures can be defined as a combination of three elements:
1. **Logical Structure**: It refers to the way the data is organized and represented within a program
or system. The logical structure defines the relationships and operations that can be performed on
the data. It includes concepts such as arrays, linked lists, trees, graphs, stacks, queues, and hash
tables.
2. **Physical Structure**: It pertains to how the data is stored in memory or secondary storage
devices. The physical structure determines the actual representation of the data and the
mechanisms used to access and manipulate it efficiently. It includes concepts such as arrays, linked
lists, trees, files, and databases.
3. **Operations**: These are the actions or functions that can be performed on the data within a
data structure. The operations define the behavior and functionality associated with the data
structure. Common operations include insertion, deletion, searching, traversal, sorting, and merging.
Based on their characteristics and behavior, data structures can be classified into the following
categories:
1. **Primitive Data Structures**: These are the basic or fundamental data structures provided by
the programming language itself. They include integers, floating-point numbers, characters,
booleans, and pointers. Primitive data structures are not defined by the user and are usually built
into the programming language.
2. **Linear Data Structures**: In linear data structures, data elements are arranged in a linear or
sequential manner. Examples include arrays, linked lists, stacks, and queues. The elements in linear
data structures can be accessed in a specific order, usually following a linear path.
3. **Non-Linear Data Structures**: Non-linear data structures organize data elements in a non-
sequential manner, allowing more complex relationships between the elements. Examples include
trees, graphs, and heaps. Non-linear data structures enable more flexible relationships and
hierarchies among the data.
4. **Homogeneous Data Structures**: In homogeneous data structures, all the elements are of the
same type and have a fixed size. Arrays are a common example of homogeneous data structures,
where all elements have the same data type and are stored contiguously in memory.
5. **Heterogeneous Data Structures**: Heterogeneous data structures can store elements of
different types and sizes. Examples include structures, records, and classes. Heterogeneous data
structures allow grouping different types of data together under a common structure.
6. **Static Data Structures**: Static data structures have a fixed size determined at compile time
and cannot be easily modified. Arrays are an example of a static data structure where the size is
predetermined and cannot be changed during runtime.
7. **Dynamic Data Structures**: Dynamic data structures can grow or shrink in size during runtime,
as needed. Linked lists and dynamic arrays are examples of dynamic data structures that can be
resized and modified dynamically.
These classifications provide a broad categorization of data structures, and there may be further
subcategories or variations within each type based on specific implementation details and
requirements.
2Q.
The given code represents a recursive function `fn(n)` that calculates the nth number in the
Fibonacci sequence. Let's analyze its time complexity.
In each recursive call, the function performs two base case checks:
1. `if (n < 0) return 0;`: This check ensures that negative values of `n` are handled correctly. It takes
constant time, O(1), to evaluate.
2. `if (n < 2) return n;`: This check handles the base cases when `n` is either 0 or 1. It returns the
value of `n` itself, which also takes constant time, O(1), to evaluate.
For values of `n` greater than or equal to 2, the function makes two recursive calls:
1. `return fn(n - 1) + fn(n - 2);`: This line invokes the function `fn()` twice, once with `n-1` and once
with `n-2`. The time complexity of each recursive call depends on the value of `n` and can be
represented as T(n-1) and T(n-2), respectively.
To calculate the overall time complexity of the function, we can analyze it using a recurrence
relation:
T(n) = T(n-1) + T(n-2) + O(1)
Here, the `O(1)` represents the constant time for the base case checks.
By looking at the Fibonacci sequence, we can observe that each number in the sequence is the sum
of the previous two numbers. This implies that each recursive call branches out into two more
recursive calls, and this branching continues until the base cases are reached.
If we draw a recursion tree for this function, it would have a branching factor of 2 at each level. The
height of the recursion tree is equal to `n` because each recursive call decreases the value of `n` by 1
until it reaches the base case.
Therefore, the number of nodes in the recursion tree is approximately 2^n. This means that the time
complexity of the function can be approximated as O(2^n).
However, it's important to note that this analysis assumes that each recursive call is distinct and
independent. In reality, the function exhibits overlapping subproblems since it recalculates the same
Fibonacci numbers multiple times. This results in a lot of redundant work.
To optimize the time complexity, you can implement dynamic programming techniques such as
memoization or bottom-up tabulation, which can reduce the time complexity to O(n) by avoiding the
redundant calculations.
So, the worst-case time complexity of the given code without any optimization is O(2^n), but it can
be improved using dynamic programming techniques.
3Q.
#include <stdio.h>
void deleteElement(int arr[], int size, int pos) {
if (pos < 0 || pos >= size) {
printf("Invalid position!\n");
return;
}
for (int i = pos; i < size - 1; i++) {
arr[i] = arr[i + 1];
}
printf("Element at position %d deleted successfully.\n", pos);
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);
int position;
printf("Enter the position of the element to delete (0 to %d): ", size - 1);
scanf("%d", &position);
deleteElement(arr, size, position);
printf("Updated array: ");
for (int i = 0; i < size - 1; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
Certainly! Here's an example of a C program that deletes an element from an array:
```c
#include <stdio.h>
void deleteElement(int arr[], int size, int pos) {
if (pos < 0 || pos >= size) {
printf("Invalid position!\n");
return;
}
for (int i = pos; i < size - 1; i++) {
arr[i] = arr[i + 1];
}
printf("Element at position %d deleted successfully.\n", pos);
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);
int position;
printf("Enter the position of the element to delete (0 to %d): ", size - 1);
scanf("%d", &position);
deleteElement(arr, size, position);
printf("Updated array: ");
for (int i = 0; i < size - 1; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
In this program, we define the function `deleteElement` which takes an array (`arr`), its size (`size`),
and the position of the element to delete (`pos`) as parameters. The function checks if the position is
valid, and if so, it shifts all elements from the specified position to the end of the array one step to
the left, effectively deleting the element.
In the `main` function, we create an array and get its size. Then we prompt the user to enter the
position of the element they want to delete. After calling the `deleteElement` function, we print the
updated array without the deleted element.
4Q.
To represent the given matrix as a sparse matrix, we need to identify the non-zero elements and
their corresponding positions. In a sparse matrix representation, we typically store the non-zero
elements along with their row and column indices.
Given matrix:
```
[0 0 0 0 9 0
080000
400200
000005
0 0 2 0 0 0]
```
Non-zero elements: 9, 8, 4, 2, and 5.
Corresponding positions:
```
(0, 4) -> 9
(1, 1) -> 8
(2, 0) -> 4
(2, 3) -> 2
(3, 5) -> 5
(4, 2) -> 2
```
Sparse matrix representation:
```
56
049
118
204
232
355
422
```
In this representation, the first row indicates the dimensions of the original matrix, which is a 5x6
matrix. The subsequent rows represent the non-zero elements and their corresponding row and
column indices.
5Q.
Below is a C program that finds the sum of two matrices using dynamic memory allocation (DMA):
#include <stdio.h>
#include <stdlib.h>
// Function to allocate memory for a matrix
int** allocateMatrix(int rows, int columns) {
int** matrix = (int**)malloc(rows * sizeof(int*));
for (int i = 0; i < rows; i++) {
matrix[i] = (int*)malloc(columns * sizeof(int));
}
return matrix;
}
// Function to free memory allocated for a matrix
void freeMatrix(int** matrix, int rows) {
for (int i = 0; i < rows; i++) {
free(matrix[i]);
}
free(matrix);
}
// Function to read matrix elements from the user
void readMatrix(int** matrix, int rows, int columns) {
printf("Enter matrix elements:\n");
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
scanf("%d", &matrix[i][j]);
}
}
}
// Function to display matrix elements
void displayMatrix(int** matrix, int rows, int columns) {
printf("Matrix:\n");
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
}
// Function to compute the sum of two matrices
int** addMatrices(int** matrix1, int** matrix2, int rows, int columns) {
int** sumMatrix = allocateMatrix(rows, columns);
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
sumMatrix[i][j] = matrix1[i][j] + matrix2[i][j];
}
}
return sumMatrix;
}
int main() {
int rows, columns;
printf("Enter the number of rows: ");
scanf("%d", &rows);
printf("Enter the number of columns: ");
scanf("%d", &columns);
int** matrix1 = allocateMatrix(rows, columns);
int** matrix2 = allocateMatrix(rows, columns);
printf("Enter elements for the first matrix:\n");
readMatrix(matrix1, rows, columns);
printf("Enter elements for the second matrix:\n");
readMatrix(matrix2, rows, columns);
int** sumMatrix = addMatrices(matrix1, matrix2, rows, columns);
displayMatrix(sumMatrix, rows, columns);
freeMatrix(matrix1, rows);
freeMatrix(matrix2, rows);
freeMatrix(sumMatrix, rows);
return 0;
}
```
This program first prompts the user to enter the number of rows and columns for the matrices. It
then dynamically allocates memory for the matrices using the `allocateMatrix` function. The user is
then asked to enter the elements for both matrices using the `readMatrix` function.
The `addMatrices` function performs the addition of the two matrices and stores the result in
another dynamically allocated matrix. The `displayMatrix` function is used to print the resulting sum
matrix.
Finally, the program frees the dynamically allocated memory using the `freeMatrix` function to avoid
memory leaks.
6Q.
The stack data structure follows the Last-In-First-Out (LIFO) principle, which means that the last
element added to the stack is the first one to be removed. Here are the main operations performed
on a stack:
1. Push: The push operation adds an element to the top of the stack. It takes the element as a
parameter and places it on top of the existing elements.
Example: Let's say we have an empty stack. We perform the following push operations: push(5),
push(8), and push(3). The stack will look like this after each push:
Stack: [5]
Stack: [5, 8]
Stack: [5, 8, 3]
2. Pop: The pop operation removes the topmost element from the stack and returns it. After the
removal, the element below it becomes the new top.
Example: Considering the same stack from the previous example, if we perform a pop operation,
the topmost element (3) will be removed and returned. The stack will then look like this:
Stack: [5, 8]
3. Peek or Top: The peek operation returns the topmost element from the stack without removing it.
Example: Using the same stack, if we perform a peek operation, it will return the value 8, but the
stack will remain unchanged:
Stack: [5, 8]
4. IsEmpty: The isEmpty operation checks if the stack is empty or not. It returns true if the stack has
no elements, and false otherwise.
Example: If we perform isEmpty on an empty stack, it will return true. If the stack contains
elements, it will return false.
5. Size: The size operation returns the number of elements present in the stack.
Example: If we perform size on the previous stack, it will return 2, indicating that there are two
elements in the stack.
These are the basic operations commonly associated with a stack data structure. They provide a
simple and efficient way to manage elements in a Last-In-First-Out manner.
7Q.
To convert the given infix expression into postfix notation, we'll use the shunting yard algorithm.
This algorithm utilizes a stack to keep track of operators and their precedence. Here's the step-by-
step conversion of the given expression into postfix form, along with the stack status at each step:
Expression: (A+B) *C+(D-E)/F+G
Step 1:
(A + B) * C + (D - E) / F + G
Stack: [empty]
Step 2:
AB+C*DE-F/G+
Stack: [(]
Step 3:
AB+C*DE-F/G+
Stack: [(, +]
Step 4:
AB+C*DE-F/G+
Stack: [(, +, )]
Step 5:
AB+C*DE-F/G+
Stack: [(, +, ), *]
Step 6:
AB+C*DE-F/G+
Stack: [(, +, ), *, +]
Step 7:
AB+C*DE-F/G+
Stack: [(, +, ), *, +, (]
Step 8:
AB+C*DE-F/G+
Stack: [(, +, ), *, +, (, -]
Step 9:
AB+C*DE-F/G+
Stack: [(, +, ), *, +, (, -]
Step 10:
AB+C*DE-F/G+
Stack: [(, +, ), *, +, (, -, )]
Step 11:
AB+C*DE-F/G+
Stack: [(, +, ), *, +, (, -, ), /]
Step 12:
AB+C*DE-F/G+
Stack: [(, +, ), *, +, (, -, ), /, +]
Step 13:
AB+C*DE-F/G+
Stack: [(, +, ), *, +, (, -, ), /, +]
Step 14:
AB+C*DE-F/G+
Stack: [(, +, ), *, +, (, -, ), /, +, G]
Final Postfix Expression: AB+C*DE-F/G+
8Q.
Stack and Queue are both fundamental data structures used in computer science to organize and
manipulate data. While they share some similarities, they differ in their operations and the order in
which elements are accessed. Here's a comparison of Stack and Queue data structures:
Stack:
1. LIFO (Last-In, First-Out): The last element added to the stack is the first one to be removed.
2. Elements are added and removed from only one end called the "top" of the stack.
3. Operations:
- Push: Adds an element to the top of the stack.
- Pop: Removes the top element from the stack.
- Peek or Top: Returns the top element without removing it.
4. It follows the principle of "last in, first out," making it suitable for applications such as function call
stacks, undo/redo mechanisms, and expression evaluation.
5. Common implementations include using arrays or linked lists.
Queue:
1. FIFO (First-In, First-Out): The first element added to the queue is the first one to be removed.
2. Elements are added at one end called the "rear" and removed from the other end called the
"front" of the queue.
3. Operations:
- Enqueue or Push: Adds an element to the rear of the queue.
- Dequeue or Pop: Removes the front element from the queue.
- Front: Returns the front element without removing it.
- Rear: Returns the rear element without removing it.
4. It follows the principle of "first in, first out," making it suitable for applications such as process
scheduling, breadth-first search, and buffering.
5. Common implementations include using arrays or linked lists.
Key Differences:
1. Access Order: Stack follows LIFO, while Queue follows FIFO.
2. Insertion and Removal: Stack allows insertion and removal at only one end (top), whereas Queue
allows insertion at one end (rear) and removal at the other end (front).
3. Data Manipulation: In a Stack, elements can be pushed and popped, while in a Queue, elements
can be enqueued and dequeued.
4. Usage: Stack is typically used for applications that require backtracking or maintaining a
temporary history, while Queue is suitable for applications that require processing elements in the
order they arrive.
5. Example: A stack can be visualized as a stack of books, where the last book added is the first to be
removed. A queue can be visualized as a line of people waiting, where the person who joins the line
first is the first to leave.
In summary, Stack and Queue differ in their access order, insertion/removal points, and the principle
they follow (LIFO vs. FIFO). These characteristics make them suitable for different types of
applications.
9Q.
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5
struct CircularQueue {
int items[MAX_SIZE];
int front;
int rear;
};
// Function prototypes
void initializeQueue(struct CircularQueue *queue);
int isFull(struct CircularQueue *queue);
int isEmpty(struct CircularQueue *queue);
void enqueue(struct CircularQueue *queue, int data);
int dequeue(struct CircularQueue *queue);
void displayQueue(struct CircularQueue *queue);
int main() {
struct CircularQueue queue;
int choice, data;
initializeQueue(&queue);
do {
printf("\nCircular Queue Operations\n");
printf("1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Display\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter the data to enqueue: ");
scanf("%d", &data);
enqueue(&queue, data);
break;
case 2:
data = dequeue(&queue);
if (data != -1)
printf("Dequeued element: %d\n", data);
break;
case 3:
displayQueue(&queue);
break;
case 4:
printf("Exiting the program...\n");
exit(0);
default:
printf("Invalid choice. Please enter a valid option.\n");
}
} while (1);
return 0;
}
// Function to initialize the circular queue
void initializeQueue(struct CircularQueue *queue) {
queue->front = -1;
queue->rear = -1;
}
// Function to check if the circular queue is full
int isFull(struct CircularQueue *queue) {
if ((queue->front == 0 && queue->rear == MAX_SIZE - 1) || (queue->rear == (queue->front - 1) %
(MAX_SIZE - 1)))
return 1;
return 0;
}
// Function to check if the circular queue is empty
int isEmpty(struct CircularQueue *queue) {
if (queue->front == -1)
return 1;
return 0;
}
// Function to add an element to the circular queue
void enqueue(struct CircularQueue *queue, int data) {
if (isFull(queue)) {
printf("Queue is full. Unable to enqueue.\n");
return;
}
if (isEmpty(queue))
queue->front = 0;
queue->rear = (queue->rear + 1) % MAX_SIZE;
queue->items[queue->rear] = data;
printf("Enqueued element: %d\n", data);
}
// Function to remove an element from the circular queue
int dequeue(struct CircularQueue *queue) {
if (isEmpty(queue)) {
printf("Queue is empty. Unable to dequeue.\n");
return -1;
}
int data = queue->items[queue->front];
if (queue->front == queue->rear)
initializeQueue(queue);
else
queue->front = (queue->front + 1) % MAX_SIZE;
return data;
}
// Function to display the elements in the circular queue
void displayQueue(struct CircularQueue *queue) {
if (isEmpty(queue)) {
printf("Queue is empty.\n");
return;
}
int i;
printf("Circular Queue elements: ");
if (queue->rear >= queue->front) {
for (i = queue->front
10Q.
#include <stdio.h>
#define MAX_SIZE 100
// Structure to represent a priority queue element
typedef struct {
int data;
int priority;
} QueueElement;
// Function to insert an element into the priority queue
void enqueue(QueueElement queue[], int *size, int data, int priority) {
int i;
// Check if the queue is full
if (*size >= MAX_SIZE) {
printf("Queue is full. Cannot enqueue element.\n");
return;
}
// Find the position to insert the new element
for (i = *size - 1; i >= 0; i--) {
if (priority < queue[i].priority) {
queue[i + 1] = queue[i];
} else {
break;
}
}
// Insert the new element
queue[i + 1].data = data;
queue[i + 1].priority = priority;
// Increment the size of the queue
(*size)++;
}
// Function to remove the highest priority element from the priority queue
void dequeue(QueueElement queue[], int *size) {
// Check if the queue is empty
if (*size <= 0) {
printf("Queue is empty. Cannot dequeue element.\n");
return;
}
// Remove the highest priority element (first element)
int i;
for (i = 0; i < *size - 1; i++) {
queue[i] = queue[i + 1];
}
// Decrement the size of the queue
(*size)--;
}
// Function to display the elements of the priority queue
void displayQueue(QueueElement queue[], int size) {
if (size <= 0) {
printf("Queue is empty.\n");
return;
}
printf("Priority Queue:\n");
for (int i = 0; i < size; i++) {
printf("%d (Priority: %d)\n", queue[i].data, queue[i].priority);
}
}
int main() {
QueueElement queue[MAX_SIZE];
int size = 0;
// Enqueue elements
enqueue(queue, &size, 5, 2);
enqueue(queue, &size, 10, 1);
enqueue(queue, &size, 15, 3);
// Display queue
displayQueue(queue, size);
// Dequeue an element
dequeue(queue, &size);
// Display queue after dequeue
displayQueue(queue, size);
return 0;
}
