I. In-Class Exercises

Programming Exercises

1. Reverse Student Information Output: L2191
2. Coordinate Sorting: L2192
3. Buying Greeting Cards: L2193

II. Knowledge Summary

✨ Core Concepts of Structs and Unions

In C++, a struct is a user-defined data type that can combine different types of data together.

Structs provide a convenient way to handle data related to real-world entities, such as students, books, coordinate points, etc. Structs can contain member variables (data) and member functions (methods). Although similar to classes, structs are typically used for simple data aggregation, and in competitive programming we usually do not use member functions.

✨ Defining a Struct

A struct is defined using the struct keyword, followed by the struct name and a set of member variables enclosed in curly braces {}, ending with a semicolon.

Key points when defining a struct:

1. Struct names are generally written with the first letter capitalized
2. Member variables represent the specific data to be stored and can be any basic data type or other structs
3. The struct definition must end with a semicolon
4. Struct definitions are generally placed outside the main function

Below are examples of defining structs that contain only basic data types, arrays, and struct arrays:

1#include <iostream>
2using namespace std;
3
4struct Person{
5    string name; // name
6    int age; // age
7    double height; // height
8    double weight; // weight
9};

1#include <iostream>
2using namespace std;
3
4struct Transcript{
5    string class_id; // class ID
6    int scores[100]; // scores array
7};

1#include <iostream>
2using namespace std;
3
4struct Person{
5    string name; // name
6    int age; // age
7    double height; // height
8    double weight; // weight
9};
10
11struct Group{
12    int group_id;
13    Person persons[100];
14};

✨ Using Structs

A struct is a custom data type, so we simply use it as a data type. To access member variables of a struct variable, use the . operator.

Struct Variables

Defining a variable with a custom struct is no different from defining a variable with a basic data type — simply replace the basic data type keyword with the custom struct name.

Below are two ways to define and initialize struct variables:

1#include <iostream>
2using namespace std;
3
4struct Point {
5    int x;
6    int y;
7};
8
9int main() {
10    // Define a Point variable p1, assign values using the . operator
11    Point p1;
12    p1.x = 3;
13    p1.y = 6;
14
15    // Define a Point variable p2, initialize using an initializer list
16    // Note: this method can only initialize basic data type members
17    Point p2 = {10, 20}; // list initialization
18
19    cout << "Point p1: (" << p1.x << ", " << p1.y << ")" << endl;
20    cout << "Point p2: (" << p2.x << ", " << p2.y << ")" << endl;
21
22    return 0;
23}

1#include <iostream>
2using namespace std;
3
4// Define the Point struct
5// Define a Point variable p1 without initialization
6// Define a Point variable p2, initialized using list initialization
7// p1 and p2 defined here are global variables
8struct Point {
9    int x;
10    int y;
11}p1, p2{4, 8};
12
13int main() {
14    // p1 and p2 can be used directly in the main function
15    p1.x = 3;
16    p1.y = 6;
17
18    cout << "Point p1: (" << p1.x << ", " << p1.y << ")" << endl;
19    cout << "Point p2: (" << p2.x << ", " << p2.y << ")" << endl;
20
21    return 0;
22}

Struct Arrays

Defining an array with a custom struct is no different from defining an array with a basic data type — simply replace the basic data type keyword with the custom struct name.

1#include <iostream>
2using namespace std;
3
4struct Point {
5    int x;
6    int y;
7};
8
9// Define an array p of type Point
10Point p[1000];
11
12int main() {
13    // Assign values to the struct array p
14    for (int i = 0; i < 1000; ++i) {
15        p[i].x = i;
16        p[i].y = i;
17    }
18
19    return 0;
20}

Structs and Functions

You can pass custom struct variables as arguments to functions, and you can also have a function return a custom struct type.

1#include <iostream>
2using namespace std;
3
4struct Point {
5    int x;
6    int y;
7};
8
9// Print the member variables of a Point variable
10void printPoint(Point p) {
11    cout << "Point: (" << p.x << ", " << p.y << ")" << endl;
12}
13
14// Create a Point variable
15Point createPoint(int x, int y) {
16    Point p;
17    p.x = x;
18    p.y = y;
19    return p;
20}
21
22int main() {
23    Point p1 = createPoint(10, 20);
24    printPoint(p1);
25
26    return 0;
27}

✨ Union Concepts

In C++, a union is a user-defined data type, similar to a struct, but with a different memory management approach. All members of a union share the same memory, meaning that at any given time, a union can only store the value of one member. Unions are primarily used in scenarios that require efficient memory usage.

Unions are commonly used in the following scenarios:

• Saving memory space: Unions can efficiently store different types of data where memory conservation is needed
• Handling multiple data types: When you need to handle multiple data types but only need one at a time, unions are an effective solution

✨ Defining a Union

A union is defined using the union keyword, followed by the union name and a set of member variables enclosed in curly braces {}, ending with a semicolon.

Key points when defining a union:

1. Union names are generally written with the first letter capitalized
2. Member variables represent the specific data to be stored and can be any basic data type
3. The union definition must end with a semicolon
4. Union definitions are generally placed outside the main function

1#include <iostream>
2using namespace std;
3
4union Data {
5    int i;
6    float f;
7    char c;
8};
9
10int main() {
11    Data data;
12
13    data.i = 10;
14    cout << "data.i: " << data.i << endl;
15
16    data.f = 3.14;
17    cout << "data.f: " << data.f << endl;
18
19    data.c = 'a';
20    cout << "data.c: " << data.c << endl;
21
22    // Note: accessing other members now will yield undefined results
23    cout << "data.i: " << data.i << endl;
24
25    return 0;
26}

✨ Using Unions

Unions are used in essentially the same way as structs. You can use an initializer list to initialize a union variable.

1#include <iostream>
2using namespace std;
3
4union Data {
5    int i;
6    float f;
7    char c;
8};
9
10int main() {
11    Data data = {10}; // initialize the integer member
12
13    cout << "data.i: " << data.i << endl;
14
15    data = {3.14f}; // initialize the float member
16    cout << "data.f: " << data.f << endl;
17
18    data = {'a'}; // initialize the character member
19    cout << "data.c: " << data.c << endl;
20
21    return 0;
22}

✨ Anonymous Unions

In certain cases, unions can be anonymous, meaning they have no name. Members of an anonymous union belong directly to the enclosing scope and can be used inside a struct.

1#include <iostream>
2using namespace std;
3
4struct Test {
5    union {
6        int i;
7        float f;
8    };
9
10    void print() {
11        cout << "i: " << i << ", f: " << f << endl;
12    }
13};
14
15int main() {
16    Test t;
17    t.i = 10;
18    t.print();
19
20    t.f = 3.14f;
21    t.print();
22
23    return 0;
24}

✨ Execution Examples for Structs and Unions

The following memory diagrams illustrate how structs and unions work.

Example 1: Memory Layout of a Struct

1struct Student {
2    char name[10];   // 10 bytes
3    int age;         // 4 bytes
4    double score;    // 8 bytes
5};
6
7Student s = {"Tom", 15, 92.5};

Struct members are arranged sequentially in memory, each with its own storage space:

1Memory address (illustration):
2+----------+------+----------+
3|  name    | age  |  score   |
4| "Tom"    |  15  |  92.5    |
5| [10 bytes]|[4 bytes]| [8 bytes]|
6+----------+------+----------+

The total size of a struct >= the sum of all member sizes (it may be larger due to memory alignment).

Example 2: Memory Layout of a Union

1union Data {
2    int i;      // 4 bytes
3    float f;    // 4 bytes
4    char c;     // 1 byte
5};
6
7Data d;

All members of a union share the same memory, and the size equals the size of the largest member:

Memory address (illustration):
+----------------+
| i / f / c      |
| shared [4 bytes]|
+----------------+

d.i = 10;    -> memory stores integer 10
d.f = 3.14;  -> memory is overwritten with float 3.14; d.i is now meaningless
d.c = 'A';   -> memory is overwritten with character 'A'; d.i and d.f are now meaningless

Example 3: Defining, Assigning, and Sorting a Struct Array

1struct Student {
2    string name;
3    int score;
4};
5
6Student stu[3];
7
8// Read in 3 students' information
9for (int i = 0; i < 3; ++i) {
10    cin >> stu[i].name >> stu[i].score;
11}

Assuming the input is Alice 85, Bob 92, Charlie 78, the memory storage state is:

stu[0]: name="Alice",   score=85
stu[1]: name="Bob",     score=92
stu[2]: name="Charlie", score=78

After sorting by score in descending order using sort:

stu[0]: name="Bob",     score=92
stu[1]: name="Alice",   score=85
stu[2]: name="Charlie", score=78

✨ Problem-Solving Steps for Structs and Unions

General steps for solving problems using structs:

1. Analyze the data: Determine what information needs to be stored and what fields each piece of information contains (e.g., a student has a name, age, score, etc.)
2. Define the struct: Use struct outside the main function to define the struct with all required member variables
3. Define a struct array: Define a struct array large enough based on the data size
4. Read the data: Use loops and the . operator to read each struct's member variables
5. Process the data: Perform calculations, sorting, etc. as required (when sorting, you need to write a cmp function)
6. Output the result: Use the . operator to access member variables and output them

Typical application example — sorting student information by requirement:

1#include <bits/stdc++.h>
2using namespace std;
3
4struct Student {
5    string name;
6    int score;
7};
8
9bool cmp(Student a, Student b) {
10    return a.score > b.score; // sort by score in descending order
11}
12
13Student stu[1005];
14
15int main() {
16    int n;
17    cin >> n;
18    for (int i = 0; i < n; ++i) {
19        cin >> stu[i].name >> stu[i].score;
20    }
21    sort(stu, stu + n, cmp);
22    for (int i = 0; i < n; ++i) {
23        cout << stu[i].name << " " << stu[i].score << endl;
24    }
25    return 0;
26}

✨ Common Mistakes with Structs and Unions

1. Forgetting the semicolon at the end of a struct definition: struct Point { int x; int y; } must have a ; at the end, otherwise a compilation error occurs
2. Defining a struct inside the main function: Structs should be defined outside the main function (at global scope), otherwise they cannot be used in other functions
3. Confusing . and ->: Use . to access members with a struct variable (e.g., stu.name), and use -> to access members with a struct pointer (e.g., ptr->name). At this stage, we primarily use the . operator
4. Using multiple union members simultaneously: A union can only store one member's value at a time. After assigning a value to one member, reading other members yields meaningless results
5. Defining large struct arrays inside the main function causing stack overflow: When struct arrays are large (e.g., more than 10,000 elements), they should be defined as global variables, otherwise the program may crash due to insufficient stack space

✨ Union Precautions

Pay special attention to the following when using unions:

• Only one member's value can be stored at a time: Since all members share the same memory, only one member can hold valid data at any given moment
• Avoid accessing undefined behavior: If you access other members after assigning a value to one member, undefined behavior occurs because those members' values have been overwritten

III. Homework

Knowledge Quiz

• Structs and Unions - Quiz## Programming Exercises

1. Queuing: L2194
2. Birthday Sorting: L2195