# 第八章 结构体 > Arietids Learn · 个人课程复习笔记 > 在线阅读：https://learn.arietids.net/courses/programming/chapter-08/ ## 关键考点总览 1. 结构体类型的定义格式（struct关键字、字段声明、分号结尾） 2. 结构体变量的定义方式（三种形式） 3. 结构体变量的初始化（大括号、字段顺序） 4. 成员访问运算符 `.` 的使用 5. 指针访问运算符 `->` 的使用（及其与 `*` 和 `.` 的优先级关系） 6. 结构体作为函数参数（值传递 vs 指针/引用传递） 7. 链表的定义与节点结构 8. 链表的四种基本操作：创建/添加、访问/查找、插入、删除 9. 链表操作中的空指针检查 ## 详细知识点 ### 8.1 结构体的概念 #### 定义/语法 - **结构体**：自定义由一组相关数据构成的新的数据类型，用于保持数据的相关性。 [来源：第8章 p3，结构体的概念] #### 规则/规范 - 应将一个对象的所有信息项放在一起，保持数据的相关性。 [来源：第8章 p3，Notes] - 二维数组不适合存储混合类型数据（如学号是字符串，成绩是整型）。 [来源：第8章 p3，Notes] --- ### 8.2 结构体类型的定义 #### 定义/语法 - **结构体类型定义格式**： ```cpp struct 结构体类型名 { 字段声明; }; // 注意分号 ``` [来源：第8章 p4，结构体类型的定义] - **示例**： ```cpp struct studentT { char id[10]; char name[10]; int chinese; int math; int english; }; ``` [来源：第8章 p4] #### 规则/规范 - 字段名的作用域是该结构体内部。 [来源：第8章 p4] - 字段可以是**任意类型**，包括其他自定义的结构体类型（嵌套）。 [来源：第8章 p4，Notes] - **嵌套结构体示例**： ```cpp struct date { int year; int month; int day; }; struct studentT { char id[10]; char name[10]; date birthday; // 嵌套使用自定义类型 int chinese; int math; int english; }; ``` [来源：第8章 p4] --- ### 8.3 定义结构体类型的变量 #### 定义/语法 - **定义结构体变量的三种方式**： 1. **先定义类型，后定义变量**： ```cpp studentT student1, students[10]; ``` [来源：第8章 p5] 2. **定义类型的同时定义变量**： ```cpp struct studentT { // 字段... } student1, students[10]; ``` [来源：第8章 p5，Notes] 3. **省略类型名，直接定义变量**（匿名结构体）： ```cpp struct { // 字段... } student1; ``` [来源：第8章 p5，Notes] #### 执行逻辑 - 结构体对象整体占用一段**连续内存**；成员按声明顺序排列，但为了满足**对齐**要求，成员之间可能插入**填充字节（padding）**，实际偏移由编译器决定。 [来源：第8章 p5] --- ### 8.4 结构体变量的使用 #### 定义/语法 - **初始化结构体变量**（定义时）： ```cpp studentT student1 = {"00315", "San Zhang", 98, 98, 99}; ``` 初始化时，所有字段内容放在大括号内，**严格遵循定义时的顺序**。 [来源：第8章 p6，Notes] #### 规则/规范 - **成员访问**：使用 `.` 运算符访问结构体成员。 ```cpp student1.chinese += 1; ``` [来源：第8章 p6] - **嵌套结构体访问**：使用多个 `.` 访问底层字段。 ```cpp student1.birthday.year = 1997; ``` [来源：第8章 p6，Notes] - **字符串字段赋值**：若成员是 `char[]`（字符数组），数组本身不能用 `=` 直接赋值；可用 `strcpy/strncpy`（注意长度，避免越界），或更推荐将成员改为 `std::string`。 ```cpp #include std::strncpy(student1.id, "00315", sizeof(student1.id) - 1); student1.id[sizeof(student1.id) - 1] = '\0'; ``` [来源：第8章 p6] - **同类型变量赋值**：同一结构体类型的变量可以相互赋值，含义是对每个字段进行赋值。 ```cpp student2 = student1; ``` [来源：第8章 p6] #### 易错点与辨析 - ⚠️ **默认情况下**不同结构体类型的变量不能直接相互赋值；在 C++ 中若显式定义了转换/赋值运算符，则可通过转换实现。 [来源：第8章 p6，Notes] --- ### 8.5 结构体类型的指针 #### 定义/语法 - **定义结构体指针**： ```cpp studentT *sp = &student1; ``` [来源：第8章 p7] - **通过指针访问成员的两种方式**： 1. **使用 `*` 和 `.`**（必须加括号）： ```cpp (*sp).chinese -= 2; ``` 2. **使用 `->` 运算符**（推荐）： ```cpp sp->chinese -= 2; ``` [来源：第8章 p7] #### 规则/规范 - `.` 运算符的优先级**高于** `*`，所以 `(*sp).chinese` 必须加括号。 [来源：第8章 p7] - `.` 与 `->` 的优先级相同（都属于**后缀运算符**，优先级高于一元 `*`）；`sp->member` 等价于 `(*sp).member`。 [来源：第8章 p7] - `->` 的左操作数必须是**指向结构体/类对象的指针**；若是结构体对象本身（非指针），应使用 `.` 访问成员。 [来源：第8章 p7，Notes] #### 代码模式 - **动态分配结构体**： ```cpp studentT *sp = new studentT; strcpy(sp->id, "02342"); sp->chinese = 0; // 使用完毕后释放 delete sp; ``` [来源：第8章 p7] #### 易错点与辨析 - ⚠️ 动态分配的结构体使用完毕后，要用 `delete` 释放内存，**避免内存泄漏**（长期累积可能导致内存耗尽）。 [来源：第8章 p7，Notes] --- ### 8.6 结构体作为函数参数 #### 规则/规范 - **值传递**：结构体变量作为形参时，实参的每个成员的值对应赋给形参的成员（复制）。 ```cpp void print_student(studentT aStudent); print_student(student1); ``` [来源：第8章 p8] - **指针传递**（推荐，节省开销）： ```cpp void print_student(studentT *aStudent); print_student(&student1); ``` [来源：第8章 p8] - **引用传递**：也可使用引用来避免复制开销。 [来源：第8章 p8，Notes] #### 易错点与辨析 - ⚠️ 值传递会导致内存消耗大、复制过程耗时，尤其对于包含很多字段的结构体。 [来源：第8章 p8，Notes] - 若担心通过指针/引用误修改实参，可将形参声明为**指向 const 的指针**或 **const 引用**，以只读方式访问： ```cpp void print_student(const studentT *aStudent); // 指向 const 的指针 // 或（C++更常见） void print_student(const studentT &aStudent); // const 引用 ``` [来源：第8章 p8，Notes] --- ### 8.7 函数返回结构体 #### 代码模式 - **直接返回结构体**（使用临时变量）： ```cpp studentT GetStudentData() { studentT aStudent; // ... return aStudent; } studentT s1 = GetStudentData(); ``` [来源：第8章 p9] - **返回结构体指针**（使用动态分配）： ```cpp studentT *GetStudentData() { studentT *aStudent = new studentT; // ... return aStudent; } studentT *s1 = GetStudentData(); // ... delete s1; ``` [来源：第8章 p9] --- ### 8.8 链表的概念 #### 定义/语法 - **链表**：通过指针连接的链式数据结构，组成元素称为**节点**。 [来源：第8章 p10] - **链表节点结构**：一个字段存数据，一个字段存下游节点的内存地址。 ```cpp struct linkNode { datatype data; linkNode *next; }; ``` [来源：第8章 p12] #### 规则/规范 - 数据字段可以是**任意类型**，包括自定义结构体类型。 ```cpp struct linkNode { int score; linkNode *next; }; // 或 struct linkNode { studentT aStudent; linkNode *next; }; ``` [来源：第8章 p12] #### 链表 vs 数组对比 | 特性 | 数组 | 链表 | |------|------|------| | 内存空间 | 紧凑，全部用于存数据 | 每个节点还需存指针，更消耗内存 | | 大小 | 需预先设定 | 可随时添加或删除 | | 适用场景 | 固定大小数据 | 动态变化的数据（如系统任务分配） | [来源：第8章 p10，Notes] --- ### 8.9 链表的种类 #### 定义/语法 - **单链表**：每个节点只有一个指向下游的指针。 - **双链表**：每个节点有两个指针，分别指向上游和下游。 - **单循环链表**：单链表的最后一个节点指向第一个节点，形成闭环。 - **双循环链表**：双链表的首尾相连，形成闭环。 [来源：第8章 p11] --- ### 8.10 链表操作 #### 8.10.1 创建/添加 ##### 代码模式 - **定义头指针并初始化为空**： ```cpp linkNode *head = NULL; ``` [来源：第8章 p13] - **头插法**（新节点加到链表头）： ```cpp linkNode *aNode; aNode = new linkNode; aNode->next = NULL; cin >> aNode->score; aNode->next = head; // 新节点指向原头节点 head = aNode; // 头指针指向新节点 ``` [来源：第8章 p13] ##### 执行逻辑 - 头指针 `head` 指向首个元素的位置，作为整个链表的入口。 [来源：第8章 p13，Notes] - 末位添加也可以，但需要额外定义一个指针来追踪尾部。 [来源：第8章 p13，Notes] --- #### 8.10.2 访问/查找 ##### 代码模式 - **遍历链表查找目标**： ```cpp linkNode *p; p = head; int target = 48; while (p) { if (p->score == target) break; p = p->next; } ``` [来源：第8章 p14] ##### 执行逻辑 - 定义访问指针，初始化为头指针。 - 用 `while` 循环检查当前节点，若不是目标则移动到下游，直到找到或遍历完毕。 [来源：第8章 p14，Notes] --- #### 8.10.3 插入 ##### 代码模式 - **在节点 p 之后插入新节点**： ```cpp if (p) { // 假设 p 已指向目标结点（p != nullptr） linkNode *aNode = new linkNode; cin >> aNode->score; aNode->next = p->next; // 新节点指向 p 的下游 p->next = aNode; // p 指向新节点 } ``` [来源：第8章 p15] ##### 易错点与辨析 - ⚠️ 插入前必须检查 `p` 是否为空指针，用 `if(p)` 排除非法情况。 [来源：第8章 p15，Notes] ##### 例题结论 - **【习题答案】** 在单链表中，若 S 所指结点不是最后结点，在 S 之后插入 T 所指结点，正确操作是： ```cpp T->next = S->next; S->next = T; ``` **答案：B** [来源：第8章 p17，习题1 答案B] --- #### 8.10.4 删除 ##### 代码模式 - **删除节点 p 之后的节点**： ```cpp if (p && p->next) { // 假设 p 已指向目标结点 linkNode *aNode = p->next; // aNode 指向要删除的结点 p->next = aNode->next; // 绕过被删结点 delete aNode; // 释放被删结点 } ``` [来源：第8章 p16] ##### 易错点与辨析 - ⚠️ 删除前必须检查 `p` 和 `p->next` 是否为空，用 `if(p && p->next)` 排除非法情况。 [来源：第8章 p16，Notes] --- ### 8.11 循环链表应用——约瑟夫环 #### 定义/语法 - **约瑟夫环问题**：n 个人围成一圈，从第一个人开始报数 1、2、3...，凡报到 m 者退出圈子，然后从下一个人重新从 1 报数，直到只剩最后一个人，求他的序号。 [来源：第8章 p18] - **示例（编号从 0 开始）**：当 n=5，m=3 时，出圈顺序为 2, 0, 4, 1，最后剩下 3。 [来源：第8章 p18] #### 代码模式 - **完整代码**： ```cpp struct Node { int data; Node *next; }; int main() { Node *head, *p, *q; int n, i, m; // 输入n和m cout << "\ninput n and m:"; cin >> n >> m; // 建立循环链表 head = p = new Node; p->data = 0; for (i = 1; i < n; ++i) { q = new Node; q->data = i; p->next = q; p = q; } p->next = head; // 头尾相连，形成循环 // 删除过程 q = head; while (q->next != q) { // 只要还剩不止一个结点 for (i = 0; i < m - 1; ++i) { // 报数 p = q; q = p->next; } p->next = q->next; // 绕过节点q cout << q->data << '\t'; // 显示被删者编号 delete q; // 回收被删者空间 q = p->next; // q指向下一次报1的节点 } // 打印结果 cout << "\n最后剩下：" << q->data << endl; delete q; // 释放最后一个结点 return 0; } ``` [来源：第8章 p19] ##### 执行逻辑 1. 建立循环链表，头尾相连。 2. 用 `while (q->next != q)` 判断链表是否只剩一个节点。 3. `for` 循环报数 m-1 次后，删除当前节点 q。 4. 重复直到只剩一个节点。 [来源：第8章 p19，Notes] --- ## 本章总结（来自PPT） - **结构体的作用**：处理更复杂的数据。 [来源：第8章 p20，总结] - **结构体的使用**： 1. 定义类型 2. 定义变量 3. 链表 [来源：第8章 p20，总结] - ⚠️ **重要提醒**：链表处理算法看上去一般都很简单，但是对细节的把握要求很高。细节没有处理好，经常把不应该改的地方给改掉了。**要小心**。 [来源：第8章 p20，Notes] --- ## 附：思考题 在动态内存管理中，假设系统可供分配的空间被组织成一个单链表，链表的每个节点表示一块可用空间，包括可用空间的起始和终止地址。初始时，链表只有一个节点，即整个空间的大小。当遇到一个 `new` 操作时，在链表中寻找一个大于 `new` 操作申请的空间节点。从这个节点中扣除所申请的空间。当遇到 `delete` 操作时，将归还的空间形成一个节点，连入链表。经过一段时间的运行，链表中的节点会越来越多。设计一个函数，完成碎片的重组工作。即将一系列连续的空闲空间组合成一块空闲空间。 [来源：第8章 p21，习题]