Algorithm and Data Structures Test 1
In-Depth Study Notes
---
1. Function Parameters and Return Types
Parameter Types:
1. Pass-by-Value:
- A copy of the argument is passed to the function.
- Changes to the parameter do not affect the original argument.
- Example:
```cpp
void func(int x) { x = 10; }
```
2. Pass-by-Reference:
- The function receives a reference to the original argument.
- Changes to the parameter affect the original argument.
- Example:
```cpp
void func(int &x) { x = 10; }
```
3. Pass-by-Const-Reference:
- The function receives a reference to the original argument but cannot modify it.
- Used for efficiency with large objects (e.g., std::string, std::vector).
- Example:
```cpp
void func(const int &x) { /* x cannot be modified */ }
```
Return Types:
1. Return-by-Value:
- A copy of the value is returned.
- Example:
```cpp
int func() { return 42; }
```
2. Return-by-Reference:
- A reference to the original value is returned.
- Allows modification of the original data.
- Example:
```cpp
int& func(int &x) { return x; }
```
3. Return-by-Const-Reference:
- A reference to the original value is returned, but it cannot be modified.
- Example:
```cpp
const int& func(const int &x) { return x; }
```
---
2. Enumeration Type
- Definition:
- An enum is a user-defined type that consists of a set of named constants.
- Example:
```cpp
enum Color { RED, GREEN, BLUE };
Color c = RED;
```
- Use Cases:
- Improve code readability by replacing magic numbers with meaningful names.
- Restrict a variable to a specific set of values.
---
3. Structs and Arrays of Structs
Struct Definition:
- A struct is a user-defined type that groups related data members.
- Example:
```cpp
struct Student {
string name;
int age;
double gpa;
};
```
Array of Structs:
- An array where each element is a struct.
- Example:
```cpp
Student students[100];
students[0].name = "Alice";
students[0].age = 20;
```
Operations:
- Read Data:
```cpp
for (int i = 0; i < 100; i++) {
cin >> students[i].name >> students[i].age >> students[i].gpa;
}
```
- Linear Search:
```cpp
for (int i = 0; i < 100; i++) {
if (students[i].name == "Alice") {
cout << "Found Alice!";
break;
}
}
```
- Sort Data:
```cpp
sort(students, students + 100, [](const Student &a, const Student &b) {
return a.gpa > b.gpa;
});
```
---
4. C++ Classes
Private vs Public:
- Private:
- Accessible only within the class or by friend functions/classes.
- Used for encapsulation and data hiding.
- Public:
- Accessible by anyone.
- Used for the class interface.
Constructors and Destructors:
- Constructor:
- Initializes objects.
- Example:
```cpp
class MyClass {
public:
MyClass() { cout << "Constructor called!"; }
};
```
- Destructor:
- Cleans up resources when an object is destroyed.
- Example:
```cpp
~MyClass() { cout << "Destructor called!"; }
```
Accessor and Mutator Methods:
- Accessor (Getter):
- Returns the value of a private member.
- Example:
```cpp
int getAge() const { return age; }
```
- Mutator (Setter):
- Modifies the value of a private member.
- Example:
```cpp
void setAge(int a) { age = a; }
```
Static Data and Methods:
- Static Data:
- Shared across all instances of the class.
- Example:
```cpp
static int count;
```
- Static Methods:
- Can only access static data.
- Example:
```cpp
static void printCount() { cout << count; }
```
---
5. Operator Overloading
Overloading as a Member Function:
- Example:
```cpp
class MyClass {
public:
MyClass operator+(const MyClass &other) {
MyClass result;
result.value = this->value + other.value;
return result;
}
};
```
Overloading as a Friend Function:
- Example:
```cpp
friend MyClass operator+(const MyClass &a, const MyClass &b);
```
Common Operators to Overload:
- ==, !=, <<, >>, [], ++, =, etc.
---
6. Pointers and Dynamic Memory Allocation
Pointer Basics:
- Declaration:
```cpp
int* ptr;
```
- Dereferencing:
```cpp
int x = 10;
int* ptr = &x;
cout << *ptr; // Output: 10
```
Dynamic Memory:
- Allocation:
```cpp
int* ptr = new int;
```
- Deallocation:
```cpp
delete ptr;
```
Memory Leaks:
- Occur when dynamically allocated memory is not deallocated.
- Avoid by ensuring every new has a corresponding delete.
---
7. Standard Template Library (STL)
Containers:
- Vector:
```cpp
vector<int> v = {1, 2, 3};
v.push_back(4);
```
- Deque:
```cpp
deque<int> d = {1, 2, 3};
d.push_front(0);
```
- List:
```cpp
list<int> l = {1, 2, 3};
l.push_back(4);
```
Iterators:
- Used to traverse containers.
- Example:
```cpp
for (auto it = v.begin(); it != v.end(); it++) {
cout << *it << " ";
}
```
Stack and Queue:
- Stack:
```cpp
stack<int> s;
s.push(1);
s.pop();
```
- Queue:
```cpp
queue<int> q;
q.push(1);
q.pop();
```
---
8. Templated Functions and Classes
Templated Function:
- Example:
```cpp
template <typename T>
T add(T a, T b) {
return a + b;
}
```
Templated Class:
- Example:
```cpp
template <typename T>
class MyClass {
public:
T value;
MyClass(T v) : value(v) {}
};
```
---
9. Conditional Compilation
- Used to include/exclude code based on conditions.
- Example:
```cpp
#ifndef MY_HEADER
#define MY_HEADER
// Code here
#endif
```
---
10. Common Pitfalls and Best Practices
- Memory Leaks:
- Always pair new with delete.
- Encapsulation:
- Use private members and provide public accessors/mutators.
- Const-Correctness:
- Use const to prevent unintended modifications.