PPS Unit -3

09 June 2024 16:49

A structure (or struct) in programming is a user-defined data type that allows the #include <stdio.h>
grouping of variables of different types under a single name. This is particularly useful int fact(int a);
for creating complex data models. In languages like C, C++, and C#, structures provide a int main()
way to organize and handle related data in a modular way. {
Structures in C are user-defined data types that allow grouping of Defining a Structure int a;
ANS 6--
variables of different data types under a single name. This is particularly In C, a structure is defined using the struct keyword: printf("Enter a number : ");
useful for representing complex data models. Structures enable better struct Person { scanf("%d", &a);
#include <stdio.h> char name[50];
organization and management of related data. Struct time_struct printf("Factorial of %d is %d", a, fact(a));
int age;
Program Implementing Array of Structures { return 0;
float height;
Here’s a C program that defines a structure to hold information about int hour; }
};
students and implements an array of such structures: int minute; int fact(int a){
Here, Person is a structure that contains a character array name, an integer age, and a
#include <stdio.h> int second;
float height.
if (a == 1 || a == 0){
}t; return 1;
Memory Storage of Structures
#define MAX_STUDENTS 3 Int main(void) }
When a structure is declared, the compiler allocates memory for each member of the
{ else {
printf("\n Enter Hour : "); structure. The memory layout depends on the order of the members and their
// Define a structure to hold student information respective data types, which may be affected by padding to align data in memory for return a * fact(a-1);
scanf("%d",&[Link]);
struct Student { performance reasons. }
printf("\n Enter Minute: ");
int id; scanf("%d",&[Link]); For example, the memory allocation for the above Person structure on a 32-bit system }
char name[50]; printf("\n Enter Second : "); might look like this:
float gpa; scanf("%d",&[Link]); 1. name (char array of 50 bytes)
}; printf("\n Time %d:%d:%d",[Link]%24,[Link]%60,[Link]%60); 2. age (int, typically 4 bytes) What is Recursion?
3. height (float, typically 4 bytes) Recursion is a programming technique where a function calls itself
int main() { return0; The total memory allocated for this structure would be 58 bytes, plus any padding directly or indirectly to solve a problem. Recursive functions solve a
// Declare an array of structures } added by the compiler. problem by breaking it down into smaller instances of the same
struct Student students[MAX_STUDENTS]; Dot Operator problem, typically using a base case to terminate the recursion.
The dot operator (.) is used to access members of a structure. Here's an example: Key Components of Recursion:
// Input data for each student struct Person person1; 1. Base Case: The condition under which the recursion stops. It
for (int i = 0; i < MAX_STUDENTS; i++) { ANS 7-- prevents infinite recursion and eventually terminates the
// Assigning values to the structure members
printf("Enter details for student %d:\n", i + 1); recursive calls.
strcpy([Link], "Alice");
printf("ID: "); #include <stdio.h> 2. Recursive Case: The part of the function where it calls itself with
[Link] = 30;
scanf("%d", &students[i].id); #include <string.h> a modified argument that progresses towards the base case.
[Link] = 5.5;
printf("Name: "); How Recursion Works
scanf("%s", students[i].name); int main() // Accessing and printing the values Consider a simple example of a recursive function to calculate the
printf("GPA: "); { printf("Name: %s\n", [Link]); factorial of a number:
scanf("%f", &students[i].gpa); char str[100], ch; printf("Age: %d\n", [Link]); int factorial(int n) {
} int i, len, j; printf("Height: %.2f\n", [Link]); if (n == 0) {
In this example, person1 is an instance of the Person structure. The dot operator is used return 1; // Base case
// Display the data printf("\n Please Enter any String : "); to assign values to name, age, and height and to access and print these values. } else {
printf("\nStudent details:\n"); gets(str); Example Usage in C return n * factorial(n - 1); // Recursive case
for (int i = 0; i < MAX_STUDENTS; i++) { Here's a complete example in C that demonstrates defining a structure, initializing its }
printf("Student %d:\n", i + 1); printf("\n Please Enter the Character that you want to Remove : "); members, and using the dot operator to access its members: }
printf("ID: %d\n", students[i].id); scanf("%c", &ch); #include <stdio.h> Here's how it works for factorial(3):
printf("Name: %s\n", students[i].name); #include <string.h> 1. factorial(3) calls factorial(2)
printf("GPA: %.2f\n\n", students[i].gpa); len = strlen(str); 2. factorial(2) calls factorial(1)
} struct Person { 3. factorial(1) calls factorial(0)
for(i = 0; i < len; i++) char name[50]; 4. factorial(0) returns 1 (base case)
return 0; { int age; 5. factorial(1) returns 1 * 1 = 1
} if(str[i] == ch) float height;
6. factorial(2) returns 2 * 1 = 2
{ };
7. factorial(3) returns 3 * 2 = 6
Pointer Arithmetic for(j = i; j < len; j++)
{
int main() { Applications of Recursion in Problem Solving
Pointer arithmetic involves operations on pointers to navigate through struct Person person1; Recursion is particularly useful for problems that can naturally be
memory. The most common pointer arithmetic operations are str[j] = str[j + 1];
divided into similar subproblems. Here are some common applications:
incrementing, decrementing, and adding or subtracting integers to/from } // Assigning values to the structure members
len--; 1. Mathematical Computations: Factorials, Fibonacci sequence,
pointers. strcpy([Link], "Alice");
i--; power functions, etc.
Example of Pointer Arithmetic [Link] = 30; 2. Data Structures: Traversal algorithms for trees and graphs (e.g.,
#include <stdio.h> } [Link] = 5.5; depth-first search).
}
printf("\n The Final String after Removing All Occurrences of '%c' = %s ", ch, // Accessing and printing the values 3. Divide and Conquer Algorithms: Merge sort, quicksort, binary
int main() { search.
int arr[5] = {10, 20, 30, 40, 50}; str); printf("Name: %s\n", [Link]);
4. Dynamic Programming: Overlapping subproblems can be solved
int *ptr = arr; // Pointer to the first element of the array printf("Age: %d\n", [Link]);
using recursion with memoization.
return 0; printf("Height: %.2f\n", [Link]);
5. Combinatorial Problems: Generating permutations,
// Increment pointer to point to the next element }
return 0; combinations, subsets, etc.
ptr++; 6. Backtracking: Solving puzzles and games (e.g., Sudoku, N-Queens
printf("Value at ptr: %d\n", *ptr); // 20 }
Summary problem).

// Add 2 to the pointer to skip to the 4th element

• Structure: A user-defined data type for grouping related variables of different Advantages and Disadvantages of Recursion
types. Advantages:
ptr += 2;
• Memory Storage: Allocates memory for each member, with possible padding for • Simplicity: Recursive solutions are often more straightforward
printf("Value at ptr: %d\n", *ptr); // 40
alignment. and easier to understand.
• Dot Operator: Used to access or modify the members of a structure. • Modularity: Recursion allows for elegant and modular code,
// Decrement pointer to point to the previous element Structures and the dot operator enable efficient organization and manipulation of
What are Pointers? breaking problems into smaller, manageable pieces.
ptr--; related data, enhancing code readability and maintainability.
Pointers are variables that store the memory addresses of other variables. Instead of Disadvantages:
printf("Value at ptr: %d\n", *ptr); // 30
holding a direct value, a pointer contains the address of a location in memory where • Performance: Recursive solutions can be less efficient in terms of
data is stored. time and space due to the overhead of repeated function calls
return 0; An array of structures in programming is a collection of structure variables, where each
}
Why are Pointers Important? and call stack usage.
element of the array is a separate instance of the structure. This allows for the
1. Efficient Memory Management: Pointers enable dynamic memory allocation, • Risk of Stack Overflow: Deep recursion can lead to stack
Usage in Linked List organization and management of multiple records or entities, each containing multiple
allowing efficient management of memory during runtime. overflow if the base case is not reached within a reasonable
Linked lists are dynamic data structures consisting of nodes where each fields of different types.
2. Array and String Manipulation: Pointers facilitate efficient traversal and Defining and Using an Array of Structures number of calls.
node contains a data field and a pointer to the next node. Pointer
manipulation of arrays and strings.
arithmetic is used to navigate through the list.
3. Function Arguments: Pointers allow functions to modify the actual arguments
Consider the Person structure from the previous example. Here is how you define and Summary
Here’s a basic implementation of a singly linked list in C: use an array of structures in C: Recursion is a powerful tool in programming for solving complex
passed to them, providing a way to return multiple values from functions. #include <stdio.h>
#include <stdio.h> problems by breaking them down into simpler subproblems. It is
4. Data Structures: Essential for implementing complex data structures like #include <string.h>
#include <stdlib.h> particularly useful in mathematical computations, data structure
linked lists, trees, and graphs.
5. Performance: Accessing data through pointers can be faster than using traversals, divide and conquer algorithms, dynamic programming,
// Define the structure for a node in the linked list struct Person {
indexed array access due to direct memory access. combinatorial problems, and backtracking. Understanding and
char name[50];
struct Node { effectively using recursion requires careful consideration of the base
int data;
Features of Pointers int age;
float height; case and ensuring that the problem moves towards the base case with
1. Dereferencing: Using the * operator to access the value at the memory
struct Node *next; each recursive call.
address stored in the pointer. };
};
int x = 10;
int *p = &x; int main() {
// Function to create a new node // Define an array of 3 Person structures Passing pointers to functions in C is a common practice, especially
struct Node* createNode(int data) { printf("%d", *p); // Outputs: 10
struct Person people[3]; when you need to modify the actual variables passed to the function
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node)); Pointer Arithmetic: Pointers can be incremented or decremented to point to
or when dealing with dynamic data structures. Here's a detailed
newNode->data = data; the next or previous memory location.
// Assigning values to the first element example demonstrating this concept:
newNode->next = NULL; int arr[3] = {10, 20, 30};
return newNode; int *p = arr;
strcpy(people[0].name, "Alice");
people[0].age = 30;
Example: Swapping Two Numbers Using
} printf("%d", *(p + 1)); // Outputs: 20 Pointers
people[0].height = 5.5;
Pointer to Pointer: Pointers can store the address of other pointers
Let's write a function to swap the values of two integers using pointers.
// Function to print the linked list int x = 10; // Assigning values to the second element Step-by-Step Explanation
void printList(struct Node *head) { int *p = &x; strcpy(people[1].name, "Bob"); 1. Function Definition: Define a function swap that takes two
struct Node *current = head; int **pp = &p; people[1].age = 25; pointers to integers as parameters.
while (current != NULL) { printf("%d", **pp); // Outputs: 10 people[1].height = 5.9; 2. Pointer Dereferencing: Use the dereferencing operator * to
printf("%d -> ", current->data); Null Pointers: A pointer that points to nothing (typically represented by the
access and modify the values pointed to by the pointers.
current = current->next; value 0 or NULL). // Assigning values to the third element
3. Calling the Function: Pass the addresses of the variables to the
} int *p = NULL; strcpy(people[2].name, "Charlie");
swap function using the address-of operator &.
printf("NULL\n"); Void Pointers: A generic pointer type that can point to any data type. people[2].age = 28;
void *ptr; people[2].height = 6.0; Code Example
} Here's the complete code:
int x = 10;
ptr = &x; // Accessing and printing the values #include <stdio.h>
int main() {
Pointers in Self-Referential Structures for(int i = 0; i < 3; i++) {
// Create nodes printf("Name: %s\n", people[i].name); // Function to swap the values of two integers
struct Node *head = createNode(10); Self-referential structures are structures that include pointers to instances of the
printf("Age: %d\n", people[i].age); void swap(int *a, int *b) {
head->next = createNode(20); same structure. This is a common technique used to build dynamic and complex data
printf("Height: %.2f\n", people[i].height); int temp = *a; // Dereference pointer a to get the value and store it
head->next->next = createNode(30); structures like linked lists, trees, and graphs.
} in temp
head->next->next->next = createNode(40); Example: Linked List Node
*a = *b; // Dereference pointer b and assign its value to the
A linked list is a series of nodes where each node contains data and a pointer to the
return 0; location pointed by a
// Print the linked list next node in the sequence.
} *b = temp; // Assign the value in temp to the location pointed by
printList(head); struct Node { Relationship Between an Array and a Pointer b
int data; In C and C++, arrays and pointers are closely related, though they are not the same. An }
return 0; struct Node *next; array name acts as a constant pointer to the first element of the array. Understanding
} }; this relationship is key to effectively working with arrays and pointers. int main() {
Array and Pointer Basics
Explanation int main() { 1. Array Name as a Pointer: The name of an array is a pointer to its first element.
int x = 5, y = 10;
1. Node Structure: Each node contains an integer data field and a // Creating nodes int arr[5];
pointer to the next node. printf("Before swap: x = %d, y = %d\n", x, y);
struct Node *head = NULL; int *ptr = arr; // Equivalent to int *ptr = &arr[0];
2. createNode Function: Allocates memory for a new node, sets its struct Node *second = NULL; Pointer Arithmetic: Pointers can be incremented and decremented to traverse an
data, and initializes the next pointer to NULL. // Call the swap function and pass the addresses of x and y
struct Node *third = NULL; array.
3. printList Function: Iterates through the linked list using the next int arr[5] = {1, 2, 3, 4, 5}; swap(&x, &y);
pointers and prints the data. // Allocating memory for nodes int *ptr = arr;
printf("After swap: x = %d, y = %d\n", x, y);
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node)); for(int i = 0; i < 5; i++) {
printf("%d ", *(ptr + i)); // Equivalent to printf("%d ", arr[i]); return 0;
third = (struct Node*)malloc(sizeof(struct Node));
} }
// Assigning data and linking nodes Array of Structures and Pointers: You can use pointers to traverse and manipulate an
head->data = 1; array of structures.
struct Person people[3];
head->next = second;
struct Person *p = people;
second->data = 2;
// Assign values using pointer
second->next = third; strcpy(p->name, "Alice");
p->age = 30;
third->data = 3; p->height = 5.5;
third->next = NULL;
p++; // Move pointer to the next structure
return 0;
} strcpy(p->name, "Bob");
In this example, each Node structure contains an integer data and a pointer next to p->age = 25;
another Node. This allows the creation of a dynamic sequence of nodes. p->height = 5.9;
Use Cases in Data Structures:
1. Linked Lists: Each node points to the next node, allowing dynamic insertion // Access and print using pointer
and deletion of elements. for(int i = 0; i < 3; i++) {
2. Trees: Each node can have pointers to its children, enabling hierarchical data printf("Name: %s\n", (people + i)->name);
representation. printf("Age: %d\n", (people + i)->age);
3. Graphs: Nodes may have pointers to other nodes, representing complex printf("Height: %.2f\n", (people + i)->height);
relationships. }