C++复习：结构体、链表与指针解析

"C++语言中的链表、指针、深度优先搜索(DFS)和广度优先搜索(BFS)以及结构体的使用" 本讲座重点复习了C++编程语言中的几个核心概念，包括链表、指针、两种重要的图遍历算法DFS和BFS，以及结构体的定义和应用。下面是对这些知识点的详细解释： ### 链表 链表是一种数据结构，它不像数组那样连续存储元素，而是通过节点间的指针链接来组织数据。每个节点包含两部分：数据域和指针域，指针域指向下一个节点。链表分为单链表、双向链表和循环链表等类型，其中单链表每个节点只有一个指向后继节点的指针。 ### 指针 在C++中，指针是变量的地址，它可以用来间接访问和修改存储在特定地址的值。指针可以被声明、初始化、赋值和解引用。指针在处理链表、动态内存分配和函数参数传递等方面有着重要作用。 ### DFS（深度优先搜索） DFS是一种用于遍历或搜索树或图的算法。它从根节点开始，沿着树的深度方向往下走，尽可能深地搜索子树。如果当前节点的所有边都已被探索过，则回溯到上一个节点，继续探索其他分支。DFS可以使用递归或栈来实现。 ### BFS（广度优先搜索） BFS是另一种图遍历算法，它从根节点开始，逐层访问所有节点。BFS首先访问离起点最近的节点，然后访问相邻节点，接着再访问这些相邻节点的相邻节点，以此类推。BFS通常使用队列来存储待访问的节点。 ### 结构体 结构体是C++中的复合数据类型，允许我们将多个不同类型的数据组合成一个单一的实体。在结构体中，我们可以定义变量、成员函数，以及初始化和操作这些成员的方法。 #### 结构体定义 - **定义结构体类型的同时定义变量**： ```cpp struct Student { string name; int chinese, math; int total; } a[110]; ``` - **先定义结构体类型，再定义变量**： ```cpp struct Student { string name; int chinese, math; int total; }; Student a[110]; ``` #### 结构体变量特点 - 可以整体操作，如`swap(a[j], a[j+1])` - 成员访问便捷，如`cin >> a[i].name;` - 初始化类似数组，如`student op = {"gaoxiang", 89, 90, 179};` #### 结构体成员调用 - 通过`结构体变量名.成员名`进行成员访问，如`cin >> a[i].name;` - 成员函数调用：`结构体变量名.成员函数();` - 成员函数默认接收结构体变量的引用作为参数 ### 示例题目解析 题目要求读入N个学生的信息（姓名、语文、数学成绩），根据总分排序并输出。首先，可以使用结构体`Student`来存储学生信息，然后利用DFS或BFS（在这个问题中并不适用）来处理数据，最后依据总分进行排序。以下是一个可能的解决方案： ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; struct Student { string name; int chinese, math, total; }; bool compareStudent(const Student &s1, const Student &s2) { if (s1.total == s2.total) return s1.chinese > s2.chinese; // 如果总分相同，按照语文成绩排序 return s1.total > s2.total; // 总分越高，排名越前 } int main() { int N; cin >> N; vector<Student> students(N); for (int i = 0; i < N; ++i) { cin >> students[i].name >> students[i].chinese >> students[i].math; students[i].total = students[i].chinese + students[i].math; } sort(students.begin(), students.end(), compareStudent); for (const auto &s : students) cout << s.name << " " << s.chinese << " " << s.math << " " << s.total << endl; return 0; } ``` 这个程序首先读入学生信息，将学生信息存储在`Student`类型的`vector`中，然后使用`sort`函数对学生成绩进行排序，最后逐个输出排序后的学生信息。