DSA: Problems on Recursion, Pointers, and Dynamic Allocation
Reverse a String: Write a recursive C program to reverse a given string. The program should take a string as input and return its reverse.
Fibonacci Sequence: Write a recursive C program to find the n-th number in the Fibonacci sequence, utilizing memoization to optimize performance. The program should take an integer n as input and output the n-th Fibonacci number. Memoization should be implemented by storing previously calculated Fibonacci numbers to avoid redundant calculations and improve efficiency.
Subset Sum Problem: Write a recursive C program to determine if there is a subset of a given set with a sum equal to a given target. The input should be an array of integers and the target sum.
N-Queens Problem: Write a recursive C program to solve the N-Queens problem. Given an integer N, place N queens on an ( N x N ) chessboard so that no two queens threaten each other.
All Possible Permutations: Write a recursive C program to generate all possible permutations of a given array of distinct integers.
Partition Problem: Write a recursive C program to determine if a given array can be partitioned into two subsets such that the sum of elements in both subsets is the same.
Word Search: Write a recursive C program to determine if a given word exists in a 2D grid of characters. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring.
Dynamic Memory Allocation and Deallocation: Write a C program that dynamically allocates memory for an array of integers, fills it with values, and then deallocates the memory. Use both pointers and double pointers to manage the memory.
Dynamic Array of Strings: Write a C program to create a dynamic array of strings using pointers to pointers. Implement functions to add, remove, and search for strings within the array.
Hints
Reverse a String: Start by writing a function that takes the string, the starting index, and the ending index as parameters. Swap the characters at the starting and ending indices, then recursively call the function with the next inner indices. The base case is when the starting index is greater than or equal to the ending index.
Fibonacci Sequence: Initialize an array to store the Fibonacci numbers. Write a recursive function that takes an integer ( n ) and the memoization array as parameters. The base cases are for ( n = 0 ) and ( n = 1 ). For other values, if the result is already in the memoization array, return it. Otherwise, compute the Fibonacci number recursively, store it in the array, and return it.
Subset Sum Problem: Write a recursive function that takes the array, its size, and the target sum as parameters. The base cases are when the target sum is 0 (return true) or the array size is 0 (return false). For each element, check if the target can be achieved by including or excluding the current element, and recursively solve for the remaining elements and the reduced target.
N-Queens Problem: Use a recursive backtracking approach. Write a function to place queens one by one in different rows, starting from the leftmost column. For each column, check if placing the queen in the current row does not threaten any previously placed queens. If placing the queen is safe, mark the position and recursively place the rest of the queens. If a solution is found, return true; otherwise, backtrack and try the next row.
All Possible Permutations: Write a recursive function that generates permutations by swapping elements. Start with the first element and recursively generate permutations for the rest of the array by swapping each subsequent element with the current element. Use a helper function to swap elements and ensure the original array is restored before the next iteration.
Partition Problem: Calculate the total sum of the array. If the sum is odd, it's impossible to partition it into two equal subsets. Otherwise, write a recursive function to check if there is a subset with a sum equal to half of the total sum. Use a similar approach to the Subset Sum Problem, where you include or exclude elements and check for the target sum.
Word Search: Write a recursive function to search for the word in the grid. Start from each cell and recursively check if the word can be constructed by moving to adjacent cells. Use a visited array to mark cells as visited and backtrack if the word cannot be constructed from the current path. Ensure that the function checks all possible directions (up, down, left, right).
Dynamic Memory Allocation and Deallocation: Use
malloc
to allocate memory for an integer array. Write functions to fill the array with values, print its elements, and deallocate the memory usingfree
. Use a double pointer to handle the array in the main function and pass it to the functions for allocation and deallocation.Dynamic Array of Strings: Use
malloc
to allocate memory for an array of character pointers. Write functions to add, remove, and search for strings. Use a double pointer for the dynamic array and handle memory allocation and reallocation within these functions. Ensure proper memory management by deallocating memory when strings are removed.
Solutions and Explanation:
Reverse a String:
#include <stdio.h> #include <string.h> // Function to reverse a string using recursion void reverseString(char str[], int start, int end) { // Base case: if start index is greater than or equal to end index if (start >= end) { return; } // Swap the characters at start and end indices char temp = str[start]; str[start] = str[end]; str[end] = temp; // Recursive call with updated indices reverseString(str, start + 1, end - 1); } int main() { char str[] = "Hello, World!"; int length = strlen(str); // Reverse the string reverseString(str, 0, length - 1); // Print the reversed string printf("Reversed String: %s\n", str); return 0; }
Function Definition:
The function
reverseString
takes a stringstr
, and two integersstart
andend
as parameters.start
is the starting index, andend
is the ending index of the string.
Base Case:
- The base case for the recursion is when
start
is greater than or equal toend
. At this point, the function returns without making further recursive calls, as the string is fully reversed.
- The base case for the recursion is when
Swapping Characters:
- The characters at the
start
andend
indices are swapped.
- The characters at the
Recursive Call:
- The function calls itself with updated indices:
start + 1
andend - 1
, to move towards the middle of the string.
- The function calls itself with updated indices:
Main Function:
The main function initializes a string
str
with the value "Hello, World!" and calculates its length.It calls the
reverseString
function to reverse the string.Finally, it prints the reversed string.
Let's walk through the process with an example string "ABCDEF":
Original String: "ABCDEF"
Step 1: Swap 'A' and 'F'
A B C D E F
^ ^
F B C D E A
Step 2: Swap 'B' and 'E'
F B C D E A
^ ^
F E C D B A
Step 3: Swap 'C' and 'D'
F E C D B A
^ ^
F E D C B A
Final reversed string: "FEDCBA"
Each step involves swapping the characters at the current start
and end
indices and then recursively calling the function with the updated indices. The recursion continues until the start
index is no longer less than the end
index, which indicates that the entire string has been reversed.
Fibonacci Sequence:
#include <stdio.h> #include <stdlib.h> // Function to initialize memoization array with -1 void initializeMemo(int memo[], int size) { for (int i = 0; i < size; i++) { memo[i] = -1; } } // Recursive function to find n-th Fibonacci number using memoization int fibonacci(int n, int memo[]) { // Base cases if (n <= 1) { return n; } // Check if value is already computed if (memo[n] != -1) { return memo[n]; } // Recursive calculation with memoization memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo); return memo[n]; } int main() { int n; printf("Enter the position n to find the n-th Fibonacci number: "); scanf("%d", &n); // Allocate memory for memoization array int *memo = (int *)malloc((n + 1) * sizeof(int)); initializeMemo(memo, n + 1); // Get the n-th Fibonacci number int result = fibonacci(n, memo); // Print the result printf("The %d-th Fibonacci number is: %d\n", n, result); // Free allocated memory free(memo); return 0; }
Initialization Function:
- The
initializeMemo
function sets all elements of the memoization array to -1, indicating that no Fibonacci numbers have been computed yet.
- The
Fibonacci Function:
The
fibonacci
function takes an integern
and the memoization arraymemo
as parameters.Base Cases: If
n
is 0 or 1, it returnsn
(the 0th Fibonacci number is 0, and the 1st Fibonacci number is 1).Memoization Check: It checks if the Fibonacci number for
n
has already been computed and stored inmemo[n]
. If so, it returns the stored value.Recursive Calculation: If the value is not already computed, it calculates the Fibonacci number recursively and stores the result in
memo[n]
.
Main Function:
The main function prompts the user to enter the position
n
for which the Fibonacci number is to be found.It allocates memory for the memoization array and initializes it.
It calls the
fibonacci
function to compute the n-th Fibonacci number and prints the result.Finally, it frees the allocated memory.
Let's walk through the process for calculating the 5th Fibonacci number with memoization:
Initial Memo Array: [-1, -1, -1, -1, -1, -1]
Step 1: fibonacci(5)
- Not in memo, so calculate fibonacci(4) + fibonacci(3)
Step 2: fibonacci(4)
- Not in memo, so calculate fibonacci(3) + fibonacci(2)
Step 3: fibonacci(3)
- Not in memo, so calculate fibonacci(2) + fibonacci(1)
Step 4: fibonacci(2)
- Not in memo, so calculate fibonacci(1) + fibonacci(0)
Step 5: fibonacci(1) = 1 (base case)
- Memo Array: [-1, 1, -1, -1, -1, -1]
Step 6: fibonacci(0) = 0 (base case)
- Memo Array: [0, 1, -1, -1, -1, -1]
Step 7: fibonacci(2) = fibonacci(1) + fibonacci(0) = 1 + 0 = 1
- Memo Array: [0, 1, 1, -1, -1, -1]
Step 8: fibonacci(3) = fibonacci(2) + fibonacci(1) = 1 + 1 = 2
- Memo Array: [0, 1, 1, 2, -1, -1]
Step 9: fibonacci(4) = fibonacci(3) + fibonacci(2) = 2 + 1 = 3
- Memo Array: [0, 1, 1, 2, 3, -1]
Step 10: fibonacci(5) = fibonacci(4) + fibonacci(3) = 3 + 2 = 5
- Memo Array: [0, 1, 1, 2, 3, 5]
Final result: The 5th Fibonacci number is 5
Each step involves either returning a previously computed value from the memoization array or calculating a new Fibonacci number recursively and storing it in the memoization array for future use. This reduces redundant calculations and optimizes the performance of the program.
Subset Sum Problem:
#include <stdio.h> #include <stdbool.h> // Function to check if there is a subset with a given sum bool isSubsetSum(int set[], int n, int sum) { // Base Cases if (sum == 0) { return true; } if (n == 0 && sum != 0) { return false; } // If last element is greater than sum, ignore it if (set[n - 1] > sum) { return isSubsetSum(set, n - 1, sum); } // Check if sum can be obtained by any of the following: // (a) including the last element // (b) excluding the last element return isSubsetSum(set, n - 1, sum) || isSubsetSum(set, n - 1, sum - set[n - 1]); } int main() { int set[] = {3, 34, 4, 12, 5, 2}; int sum = 9; int n = sizeof(set) / sizeof(set[0]); if (isSubsetSum(set, n, sum)) { printf("Found a subset with the given sum\n"); } else { printf("No subset with the given sum\n"); } return 0; }
Function Definition:
The
isSubsetSum
function takes an arrayset
, the size of the arrayn
, and the target sumsum
as parameters.Base Cases:
If
sum
is 0, it returns true, as the empty subset has a sum of 0.If
n
is 0 andsum
is not 0, it returns false, as no subset can be formed from an empty set.
Ignoring Elements:
- If the last element of the set is greater than the target sum, it is ignored, and the function is called recursively with the remaining elements.
Recursive Cases:
- The function checks if the sum can be obtained either by including or excluding the last element of the set.
Main Function:
The main function initializes an array
set
with some integers and a target sumsum
.It calculates the size of the array
n
and calls theisSubsetSum
function to check if a subset with the given sum exists.It prints the result based on the return value of the
isSubsetSum
function.
Let's walk through the process for finding a subset with the sum of 9 in the set {3, 34, 4, 12, 5, 2}:
Initial Set: {3, 34, 4, 12, 5, 2}, Sum: 9
Step 1: Check last element 2
- Include 2: New Sum = 7
- Exclude 2: Sum remains 9
Step 2: Check next element 5 (include 2)
- Include 5: New Sum = 2
- Exclude 5: Sum remains 7
Step 3: Check next element 12 (include 5)
- Include 12: New Sum = -10 (ignore as negative)
- Exclude 12: Sum remains 2
Step 4: Check next element 4 (exclude 12)
- Include 4: New Sum = -2 (ignore as negative)
- Exclude 4: Sum remains 2
Step 5: Check next element 34 (exclude 4)
- Include 34: New Sum = -32 (ignore as negative)
- Exclude 34: Sum remains 2
Step 6: Check next element 3 (exclude 34)
- Include 3: New Sum = -1 (ignore as negative)
- Exclude 3: Sum remains 2
Step 7: Check remaining element (no elements left)
- Base Case: Sum is 0 or not (it is not 0)
Step 8: Backtrack to exclude 5 (with 2)
- New Sum = 7, Check next element 12
Step 9: Check next element 12 (exclude 5)
- Include 12: New Sum = -5 (ignore as negative)
- Exclude 12: Sum remains 7
Step 10: Check next element 4 (exclude 12)
- Include 4: New Sum = 3
- Exclude 4: Sum remains 7
Step 11: Check next element 34 (exclude 4)
- Include 34: New Sum = -27 (ignore as negative)
- Exclude 34: Sum remains 3
Step 12: Check next element 3 (include 4)
- Include 3: New Sum = 0 (found a subset)
- Exclude 3: Sum remains 3
Found a subset with the given sum: {4, 5, 2}
Each step involves checking whether the current element should be included in the subset or not. The function recursively explores both possibilities and backtracks when necessary. The recursion continues until a subset with the desired sum is found or all possibilities are exhausted.
N-Queens Problem:
#include <stdio.h> #include <stdbool.h> // Function to print the chessboard void printSolution(int board[], int N) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (board[i] == j) { printf("Q "); } else { printf(". "); } } printf("\n"); } printf("\n"); } // Function to check if a queen can be placed on board[row][col] bool isSafe(int board[], int row, int col, int N) { for (int i = 0; i < row; i++) { if (board[i] == col || abs(board[i] - col) == abs(i - row)) { return false; } } return true; } // Recursive function to solve N-Queens problem bool solveNQueens(int board[], int row, int N) { // Base case: If all queens are placed if (row == N) { printSolution(board, N); return true; } // Consider this row and try placing this queen in all columns one by one bool res = false; for (int col = 0; col < N; col++) { // Check if the queen can be placed on board[row][col] if (isSafe(board, row, col, N)) { board[row] = col; // Make result true if any placement is possible res = solveNQueens(board, row + 1, N) || res; // No need to reset the board[row] as we are overwriting it in the next iteration } } return res; } int main() { int N; printf("Enter the value of N for the N-Queens problem: "); scanf("%d", &N); // Create an array to store the column positions of queens int board[N]; if (!solveNQueens(board, 0, N)) { printf("Solution does not exist\n"); } return 0; }
Print Solution Function:
- The
printSolution
function prints the chessboard configuration where queens are placed. Queens are represented by 'Q' and empty spaces by '.'.
- The
Is Safe Function:
The
isSafe
function checks if a queen can be placed atboard[row][col]
without being threatened by other queens. It checks:If there is no queen in the same column.
If there is no queen in the same diagonal.
Solve N-Queens Function:
The
solveNQueens
function recursively tries to place queens on the board.Base Case: If all queens are placed (
row == N
), it prints the solution and returns true.It iterates through each column in the current row and checks if placing a queen at
board[row][col]
is safe.If safe, it places the queen and recursively attempts to place the next queen in the next row.
If a placement is possible, it sets the result to true.
Main Function:
The main function prompts the user to enter the value of
N
and initializes the board array.It calls the
solveNQueens
function to solve the problem and prints the result.
Let's walk through the process for solving the 4-Queens problem:
Initial Board: (Empty)
Step 1: Place queen in row 0, col 0
Q . . .
. . . .
. . . .
. . . .
Step 2: Place queen in row 1, col 2
Q . . .
. . Q .
. . . .
. . . .
Step 3: Place queen in row 2, col 3 (Backtrack, col 3 is not safe)
Step 4: Place queen in row 1, col 3 (Backtrack, col 3 is not safe)
Backtrack to row 0, col 0
Q . . .
. . . .
. . . .
. . . .
Step 5: Place queen in row 0, col 1
. Q . .
. . . .
. . . .
. . . .
Step 6: Place queen in row 1, col 3
. Q . .
. . . Q
. . . .
. . . .
Step 7: Place queen in row 2, col 0
. Q . .
. . . Q
Q . . .
. . . .
Step 8: Place queen in row 3, col 2
. Q . .
. . . Q
Q . . .
. . Q .
Solution Found:
. Q . .
. . . Q
Q . . .
. . Q .
Backtrack to row 2, col 0
. Q . .
. . . Q
. . . .
. . . .
Backtrack to row 1, col 3
. Q . .
. . . .
. . . .
. . . .
Step 9: Place queen in row 0, col 2
. . Q .
. . . .
. . . .
. . . .
Step 10: Place queen in row 1, col 0
. . Q .
Q . . .
. . . .
. . . .
Step 11: Place queen in row 2, col 3
. . Q .
Q . . .
. . . Q
. . . .
Step 12: Place queen in row 3, col 1
. . Q .
Q . . .
. . . Q
. Q . .
Solution Found:
. . Q .
Q . . .
. . . Q
. Q . .
The program explores different configurations by placing queens row by row and backtracking when it encounters a conflict. It continues this process until it finds all possible solutions or determines that no solution exists.
All Possible Permutations:
#include <stdio.h> // Function to swap two integers void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } // Function to print an array void printArray(int arr[], int size) { for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); } // Recursive function to generate all permutations void generatePermutations(int arr[], int start, int end) { if (start == end) { printArray(arr, end + 1); return; } for (int i = start; i <= end; i++) { // Swap the current element with the start element swap(&arr[start], &arr[i]); // Recurse for the next position generatePermutations(arr, start + 1, end); // Backtrack: swap back the elements to their original positions swap(&arr[start], &arr[i]); } } int main() { int arr[] = {1, 2, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("All possible permutations of the array are:\n"); generatePermutations(arr, 0, n - 1); return 0; }
Swap Function:
- The
swap
function swaps the values of two integers.
- The
Print Array Function:
- The
printArray
function prints the elements of an array.
- The
Generate Permutations Function:
The
generatePermutations
function takes an arrayarr
, a starting indexstart
, and an ending indexend
.Base Case: If
start
is equal toend
, it means a permutation is formed, and it prints the array.The function iterates through the array, swapping the
start
element with each element fromstart
toend
.It recursively calls itself to generate permutations for the next position.
After the recursive call, it swaps back the elements to their original positions to backtrack and explore other permutations.
Main Function:
The main function initializes an array
arr
with some integers and calculates its sizen
.It calls the
generatePermutations
function to generate all permutations and prints the result.
Let's walk through the process for generating all permutations of the array {1, 2, 3}:
Initial Array: {1, 2, 3}
Step 1: start = 0, i = 0
Swap(1, 1)
Array: {1, 2, 3}
Recursive call with start = 1
Step 2: start = 1, i = 1
Swap(2, 2)
Array: {1, 2, 3}
Recursive call with start = 2
Step 3: start = 2, i = 2
Swap(3, 3)
Array: {1, 2, 3}
Base case reached, print: 1 2 3
Backtrack: Swap(3, 3)
Array: {1, 2, 3}
Step 4: start = 1, i = 2
Swap(2, 3)
Array: {1, 3, 2}
Recursive call with start = 2
Step 5: start = 2, i = 2
Swap(2, 2)
Array: {1, 3, 2}
Base case reached, print: 1 3 2
Backtrack: Swap(2, 3)
Array: {1, 2, 3}
Backtrack: Swap(1, 1)
Array: {1, 2, 3}
Step 6: start = 0, i = 1
Swap(1, 2)
Array: {2, 1, 3}
Recursive call with start = 1
Step 7: start = 1, i = 1
Swap(1, 1)
Array: {2, 1, 3}
Recursive call with start = 2
Step 8: start = 2, i = 2
Swap(3, 3)
Array: {2, 1, 3}
Base case reached, print: 2 1 3
Backtrack: Swap(3, 3)
Array: {2, 1, 3}
Step 9: start = 1, i = 2
Swap(1, 3)
Array: {2, 3, 1}
Recursive call with start = 2
Step 10: start = 2, i = 2
Swap(1, 1)
Array: {2, 3, 1}
Base case reached, print: 2 3 1
Backtrack: Swap(1, 3)
Array: {2, 1, 3}
Backtrack: Swap(2, 1)
Array: {1, 2, 3}
Step 11: start = 0, i = 2
Swap(1, 3)
Array: {3, 2, 1}
Recursive call with start = 1
Step 12: start = 1, i = 1
Swap(2, 2)
Array: {3, 2, 1}
Recursive call with start = 2
Step 13: start = 2, i = 2
Swap(1, 1)
Array: {3, 2, 1}
Base case reached, print: 3 2 1
Backtrack: Swap(1, 1)
Array: {3, 2, 1}
Step 14: start = 1, i = 2
Swap(2, 1)
Array: {3, 1, 2}
Recursive call with start = 2
Step 15: start = 2, i = 2
Swap(2, 2)
Array: {3, 1, 2}
Base case reached, print: 3 1 2
Backtrack: Swap(2, 1)
Array: {3, 2, 1}
Backtrack: Swap(3, 1)
Array: {1, 2, 3}
All permutations printed:
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
Each step involves swapping the elements and recursively generating permutations for the remaining positions. The function backtracks after each recursive call to restore the array to its original state before exploring other permutations. This process continues until all permutations are generated and printed.
Partition Problem:
#include <stdio.h> #include <stdbool.h> // Function to check if there is a subset with a given sum bool isSubsetSum(int set[], int n, int sum) { // Base Cases if (sum == 0) { return true; } if (n == 0 && sum != 0) { return false; } // If last element is greater than sum, ignore it if (set[n - 1] > sum) { return isSubsetSum(set, n - 1, sum); } // Check if sum can be obtained by any of the following: // (a) including the last element // (b) excluding the last element return isSubsetSum(set, n - 1, sum) || isSubsetSum(set, n - 1, sum - set[n - 1]); } // Function to check if the array can be partitioned into two subsets of equal sum bool canPartition(int set[], int n) { int sum = 0; // Calculate the total sum of the array for (int i = 0; i < n; i++) { sum += set[i]; } // If sum is odd, partition is not possible if (sum % 2 != 0) { return false; } // Check if there is a subset with sum equal to half of total sum return isSubsetSum(set, n, sum / 2); } int main() { int set[] = {1, 5, 11, 5}; int n = sizeof(set) / sizeof(set[0]); if (canPartition(set, n)) { printf("The array can be partitioned into two subsets of equal sum.\n"); } else { printf("The array cannot be partitioned into two subsets of equal sum.\n"); } return 0; }
Is Subset Sum Function:
The
isSubsetSum
function takes an arrayset
, the size of the arrayn
, and the target sumsum
.Base Cases:
If
sum
is 0, it returns true, as the empty subset has a sum of 0.If
n
is 0 andsum
is not 0, it returns false, as no subset can be formed from an empty set.
Ignoring Elements:
- If the last element of the set is greater than the target sum, it is ignored, and the function is called recursively with the remaining elements.
Recursive Cases:
- The function checks if the sum can be obtained either by including or excluding the last element of the set.
Can Partition Function:
The
canPartition
function takes an arrayset
and its sizen
.It calculates the total sum of the array.
If the total sum is odd, it returns false because it's impossible to partition the array into two subsets of equal sum.
If the total sum is even, it calls the
isSubsetSum
function to check if there is a subset with a sum equal to half of the total sum.
Main Function:
The main function initializes an array
set
with some integers and calculates its sizen
.It calls the
canPartition
function to check if the array can be partitioned into two subsets of equal sum and prints the result.
Let's walk through the process for checking if the array {1, 5, 11, 5} can be partitioned into two subsets of equal sum:
Initial Array: {1, 5, 11, 5}
Total Sum: 1 + 5 + 11 + 5 = 22
Step 1: Total sum is even (22), so partition might be possible.
Target Sum for each subset: 22 / 2 = 11
Step 2: Check if there is a subset with sum 11
- Initial call: isSubsetSum({1, 5, 11, 5}, 4, 11)
Step 3: Check last element 5
- Include 5: New Sum = 6
- Exclude 5: Sum remains 11
Step 4: Check next element 11 (Exclude 5)
- Include 11: New Sum = 0 (Subset found)
- Exclude 11: Sum remains 11
Subset with sum 11 found: {11}
The array can be partitioned into two subsets of equal sum.
Each step involves checking whether the current element should be included in the subset or not. The function recursively explores both possibilities and backtracks when necessary. The recursion continues until a subset with the desired sum is found or all possibilities are exhausted. The main function then determines if the array can be partitioned into two equal subsets based on the result of the subset sum check.
Word Search:
#include <stdio.h> #include <stdbool.h> // Define the number of rows and columns #define ROWS 4 #define COLS 4 // Directions for moving in the grid int rowDir[] = {-1, 1, 0, 0}; int colDir[] = {0, 0, -1, 1}; // Function to check if a cell is within the grid and not visited bool isValid(int row, int col, bool visited[ROWS][COLS]) { return (row >= 0 && row < ROWS && col >= 0 && col < COLS && !visited[row][col]); } // Recursive function to search for the word in the grid bool searchWord(char grid[ROWS][COLS], bool visited[ROWS][COLS], int row, int col, const char *word, int index) { // Base case: if the entire word is found if (word[index] == '\0') { return true; } // Check if the current cell is valid and matches the current character if (isValid(row, col, visited) && grid[row][col] == word[index]) { // Mark the current cell as visited visited[row][col] = true; // Recur for all possible directions for (int i = 0; i < 4; i++) { int newRow = row + rowDir[i]; int newCol = col + colDir[i]; if (searchWord(grid, visited, newRow, newCol, word, index + 1)) { return true; } } // Backtrack: unmark the current cell visited[row][col] = false; } return false; } // Function to search for the word in the entire grid bool wordExists(char grid[ROWS][COLS], const char *word) { bool visited[ROWS][COLS] = {false}; // Start from each cell in the grid for (int row = 0; row < ROWS; row++) { for (int col = 0; col < COLS; col++) { if (searchWord(grid, visited, row, col, word, 0)) { return true; } } } return false; } int main() { char grid[ROWS][COLS] = { {'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}, {'A', 'B', 'E', 'E'} }; const char *word = "ABCCED"; if (wordExists(grid, word)) { printf("The word \"%s\" exists in the grid.\n", word); } else { printf("The word \"%s\" does not exist in the grid.\n", word); } return 0; }
Is Valid Function:
- The
isValid
function checks if a cell is within the grid and not visited. It returns true if the cell is within bounds and not visited, otherwise false.
- The
Search Word Function:
The
searchWord
function recursively searches for the word in the grid.Base Case: If the entire word is found (i.e.,
word[index]
is'\0'
), it returns true.It checks if the current cell is valid and matches the current character of the word.
If valid, it marks the current cell as visited.
It recursively searches in all four possible directions (up, down, left, right) for the next character in the word.
If the word is found in any direction, it returns true.
If not found, it backtracks by unmarking the current cell.
Word Exists Function:
The
wordExists
function searches for the word in the entire grid.It initializes a visited array to keep track of visited cells.
It starts the search from each cell in the grid by calling the
searchWord
function.If the word is found starting from any cell, it returns true. Otherwise, it returns false.
Main Function:
The main function initializes a grid with characters and a word to search.
It calls the
wordExists
function to check if the word exists in the grid and prints the result.
Let's walk through the process for searching the word "ABCCED" in the grid:
Initial Grid:
A B C E
S F C S
A D E E
A B E E
Word to Search: "ABCCED"
Start from cell (0,0):
A B C E
S F C S
A D E E
A B E E
^
Index 0: Matches 'A'
Move to cell (0,1):
A B C E
S F C S
A D E E
A B E E
^
Index 1: Matches 'B'
Move to cell (0,2):
A B C E
S F C S
A D E E
A B E E
^
Index 2: Matches 'C'
Move to cell (1,2):
A B C E
S F C S
A D E E
A B E E
^
Index 3: Matches 'C'
Move to cell (2,2):
A B C E
S F C S
A D E E
A B E E
^
Index 4: Matches 'E'
Move to cell (2,1):
A B C E
S F C S
A D E E
A B E E
^
Index 5: Matches 'D'
Entire word "ABCCED" found in the grid.
The function recursively checks each cell and explores all possible directions (up, down, left, right) while keeping track of visited cells to avoid revisiting. It backtracks if a path does not lead to the complete word and continues to explore other paths until the word is found or all possibilities are exhausted.
Dynamic Memory Allocation and Deallocation:
#include <stdio.h> #include <stdlib.h> // Function to allocate memory for an integer array void allocateArray(int **arr, int size) { *arr = (int *)malloc(size * sizeof(int)); if (*arr == NULL) { printf("Memory allocation failed\n"); exit(1); } } // Function to fill the array with values void fillArray(int *arr, int size) { for (int i = 0; i < size; i++) { arr[i] = i + 1; // Fill the array with values 1, 2, 3, ... } } // Function to print the elements of the array void printArray(int *arr, int size) { for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); } // Function to deallocate the memory of the array void deallocateArray(int **arr) { free(*arr); *arr = NULL; // Set the pointer to NULL after freeing the memory } int main() { int *array = NULL; int size; printf("Enter the size of the array: "); scanf("%d", &size); // Allocate memory for the array allocateArray(&array, size); // Fill the array with values fillArray(array, size); // Print the elements of the array printf("Array elements: "); printArray(array, size); // Deallocate the memory of the array deallocateArray(&array); if (array == NULL) { printf("Memory successfully deallocated\n"); } else { printf("Memory deallocation failed\n"); } return 0; }
Allocate Array Function:
The
allocateArray
function takes a double pointerarr
and an integersize
.It allocates memory for the array using
malloc
and assigns the allocated memory to the pointerarr
.If memory allocation fails, it prints an error message and exits the program.
Fill Array Function:
The
fillArray
function takes a pointerarr
and an integersize
.It fills the array with values from 1 to
size
using a loop.
Print Array Function:
The
printArray
function takes a pointerarr
and an integersize
.It prints the elements of the array using a loop.
Deallocate Array Function:
The
deallocateArray
function takes a double pointerarr
.It deallocates the memory of the array using
free
and sets the pointerarr
toNULL
.
Main Function:
The main function declares a pointer
array
and an integersize
.It prompts the user to enter the size of the array and reads the input.
It calls the
allocateArray
function to allocate memory for the array.It calls the
fillArray
function to fill the array with values.It calls the
printArray
function to print the elements of the array.It calls the
deallocateArray
function to deallocate the memory of the array.It checks if the memory was successfully deallocated and prints the result.
Let's walk through the process of dynamic memory allocation, filling, printing, and deallocation:
- Allocate Memory:
Before Allocation:
array -> NULL
After Allocation (size = 5):
array -> [_, _, _, _, _]
- Fill Array with Values:
array -> [1, 2, 3, 4, 5]
- Print Array Elements:
Output: 1 2 3 4 5
- Deallocate Memory:
Before Deallocation:
array -> [1, 2, 3, 4, 5]
After Deallocation:
array -> NULL
The program dynamically allocates memory for the array, fills it with values, prints its elements, and deallocates the memory using free
. The double pointer is used to handle the array in the main function and is passed to the functions for allocation and deallocation. This ensures that the changes made to the pointer in the functions are reflected in the main function.
Dynamic Array of Strings:
#include <stdio.h> #include <stdlib.h> #include <string.h> // Function to add a string to the dynamic array void addString(char ***arr, int *size, const char *str) { // Reallocate memory to accommodate the new string *arr = (char **)realloc(*arr, (*size + 1) * sizeof(char *)); if (*arr == NULL) { printf("Memory allocation failed\n"); exit(1); } // Allocate memory for the new string and copy it to the array (*arr)[*size] = (char *)malloc((strlen(str) + 1) * sizeof(char)); if ((*arr)[*size] == NULL) { printf("Memory allocation failed\n"); exit(1); } strcpy((*arr)[*size], str); // Increment the size (*size)++; } // Function to remove a string from the dynamic array void removeString(char ***arr, int *size, const char *str) { for (int i = 0; i < *size; i++) { if (strcmp((*arr)[i], str) == 0) { // Free the memory for the string to be removed free((*arr)[i]); // Shift the remaining strings for (int j = i; j < *size - 1; j++) { (*arr)[j] = (*arr)[j + 1]; } // Reallocate memory to shrink the array *arr = (char **)realloc(*arr, (*size - 1) * sizeof(char *)); if (*arr == NULL && *size - 1 > 0) { printf("Memory allocation failed\n"); exit(1); } // Decrement the size (*size)--; return; } } printf("String \"%s\" not found in the array\n", str); } // Function to search for a string in the dynamic array int searchString(char **arr, int size, const char *str) { for (int i = 0; i < size; i++) { if (strcmp(arr[i], str) == 0) { return i; // Return the index if the string is found } } return -1; // Return -1 if the string is not found } // Function to print the strings in the dynamic array void printStrings(char **arr, int size) { for (int i = 0; i < size; i++) { printf("%s\n", arr[i]); } } int main() { char **array = NULL; int size = 0; // Add strings to the dynamic array addString(&array, &size, "Hello"); addString(&array, &size, "World"); addString(&array, &size, "Dynamic"); addString(&array, &size, "Array"); addString(&array, &size, "of Strings"); printf("Array after adding strings:\n"); printStrings(array, size); // Search for a string const char *searchStr = "World"; int index = searchString(array, size, searchStr); if (index != -1) { printf("String \"%s\" found at index %d\n", searchStr, index); } else { printf("String \"%s\" not found in the array\n", searchStr); } // Remove a string from the dynamic array removeString(&array, &size, "Dynamic"); printf("Array after removing \"Dynamic\":\n"); printStrings(array, size); // Free the remaining allocated memory for (int i = 0; i < size; i++) { free(array[i]); } free(array); return 0; }
Add String Function:
The
addString
function takes a double pointer to the array of strings, a pointer to the size of the array, and the string to be added.It reallocates memory for the array to accommodate the new string.
It allocates memory for the new string and copies it to the array.
It increments the size of the array.
Remove String Function:
The
removeString
function takes a double pointer to the array of strings, a pointer to the size of the array, and the string to be removed.It searches for the string in the array.
If the string is found, it frees the memory for the string and shifts the remaining strings.
It reallocates memory to shrink the array.
It decrements the size of the array.
Search String Function:
The
searchString
function takes a pointer to the array of strings, the size of the array, and the string to be searched.It searches for the string in the array and returns the index if found, otherwise returns -1.
Print Strings Function:
The
printStrings
function takes a pointer to the array of strings and the size of the array.It prints each string in the array.
Main Function:
The main function initializes a double pointer to the array of strings and the size of the array.
It adds strings to the array using the
addString
function.It prints the array after adding strings.
It searches for a string in the array using the
searchString
function and prints the result.It removes a string from the array using the
removeString
function and prints the array after removal.It frees the remaining allocated memory for the strings and the array.
Let's walk through the process of adding, searching, removing, and deallocating strings in the dynamic array:
- Add Strings:
Initial Array:
NULL
Add "Hello":
array -> [Hello]
Add "World":
array -> [Hello, World]
Add "Dynamic":
array -> [Hello, World, Dynamic]
Add "Array":
array -> [Hello, World, Dynamic, Array]
Add "of Strings":
array -> [Hello, World, Dynamic, Array, of Strings]
- Search for a String:
Search for "World":
Found at index 1
- Remove a String:
Remove "Dynamic":
Before removal:
array -> [Hello, World, Dynamic, Array, of Strings]
After removal:
array -> [Hello, World, Array, of Strings]
- Deallocate Memory:
Free the remaining allocated memory:
array -> NULL
The program dynamically allocates and deallocates memory for the array of strings, handles adding and removing strings, and searches for strings within the array. The use of double pointers ensures that changes made to the array in the functions are reflected in the main function.