第八章结构体

程序设计目录下载 Markdown

关键考点总览

结构体类型的定义格式（struct关键字、字段声明、分号结尾）
结构体变量的定义方式（三种形式）
结构体变量的初始化（大括号、字段顺序）
成员访问运算符 . 的使用
指针访问运算符 -> 的使用（及其与 * 和 . 的优先级关系）
结构体作为函数参数（值传递 vs 指针/引用传递）
链表的定义与节点结构
链表的四种基本操作：创建/添加、访问/查找、插入、删除
链表操作中的空指针检查

详细知识点

8.1 结构体的概念

定义/语法

结构体：自定义由一组相关数据构成的新的数据类型，用于保持数据的相关性。
[来源：第8章 p3，结构体的概念]

规则/规范

应将一个对象的所有信息项放在一起，保持数据的相关性。
[来源：第8章 p3，Notes]
二维数组不适合存储混合类型数据（如学号是字符串，成绩是整型）。
[来源：第8章 p3，Notes]

8.2 结构体类型的定义

定义/语法

结构体类型定义格式：
```
struct 结构体类型名 {
    字段声明;
};  // 注意分号
```
[来源：第8章 p4，结构体类型的定义]

示例：

struct studentT {
    char id[10];
    char name[10];
    int chinese;
    int math;
    int english;
};

[来源：第8章 p4]

规则/规范

字段名的作用域是该结构体内部。
[来源：第8章 p4]
字段可以是任意类型，包括其他自定义的结构体类型（嵌套）。
[来源：第8章 p4，Notes]

嵌套结构体示例：

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. 先定义类型，后定义变量：
```
studentT student1, students[10];
```
  [来源：第8章 p5]
2. 定义类型的同时定义变量：
```
struct studentT {
    // 字段...
} student1, students[10];
```
  [来源：第8章 p5，Notes]
3. 省略类型名，直接定义变量（匿名结构体）：
```
struct {
    // 字段...
} student1;
```
  [来源：第8章 p5，Notes]

执行逻辑

结构体对象整体占用一段连续内存；成员按声明顺序排列，但为了满足对齐要求，成员之间可能插入填充字节（padding），实际偏移由编译器决定。
[来源：第8章 p5]

8.4 结构体变量的使用

定义/语法

初始化结构体变量（定义时）：
```
studentT student1 = {"00315", "San Zhang", 98, 98, 99};
```
初始化时，所有字段内容放在大括号内，严格遵循定义时的顺序。
[来源：第8章 p6，Notes]

规则/规范

成员访问：使用 . 运算符访问结构体成员。
```
student1.chinese += 1;
```
[来源：第8章 p6]
嵌套结构体访问：使用多个 . 访问底层字段。
```
student1.birthday.year = 1997;
```
[来源：第8章 p6，Notes]
字符串字段赋值：若成员是 char[]（字符数组），数组本身不能用 = 直接赋值；可用 strcpy/strncpy（注意长度，避免越界），或更推荐将成员改为 std::string。
```
#include <cstring>
std::strncpy(student1.id, "00315", sizeof(student1.id) - 1);
student1.id[sizeof(student1.id) - 1] = '\0';  ```
[来源：第8章 p6]
```
同类型变量赋值：同一结构体类型的变量可以相互赋值，含义是对每个字段进行赋值。
```
student2 = student1;
```
[来源：第8章 p6]

易错点与辨析

⚠️ 默认情况下不同结构体类型的变量不能直接相互赋值；在 C++ 中若显式定义了转换/赋值运算符，则可通过转换实现。
[来源：第8章 p6，Notes]

8.5 结构体类型的指针

定义/语法

定义结构体指针：
```
studentT *sp = &student1;
```
[来源：第8章 p7]
通过指针访问成员的两种方式：
1. 使用 * 和 .（必须加括号）：
```
(*sp).chinese -= 2;
```
2. 使用 -> 运算符（推荐）：
```
sp->chinese -= 2;
```
[来源：第8章 p7]

规则/规范

. 运算符的优先级高于 *，所以 (*sp).chinese 必须加括号。
[来源：第8章 p7]
. 与 -> 的优先级相同（都属于后缀运算符，优先级高于一元 *）；sp->member 等价于 (*sp).member。
[来源：第8章 p7]
-> 的左操作数必须是指向结构体/类对象的指针；若是结构体对象本身（非指针），应使用 . 访问成员。
[来源：第8章 p7，Notes]

代码模式

动态分配结构体：

studentT *sp = new studentT;
strcpy(sp->id, "02342");
sp->chinese = 0;
// 使用完毕后释放
delete sp;

[来源：第8章 p7]

易错点与辨析

⚠️ 动态分配的结构体使用完毕后，要用 delete 释放内存，避免内存泄漏（长期累积可能导致内存耗尽）。
[来源：第8章 p7，Notes]

8.6 结构体作为函数参数

规则/规范

值传递：结构体变量作为形参时，实参的每个成员的值对应赋给形参的成员（复制）。
```
void print_student(studentT aStudent);
print_student(student1);
```
[来源：第8章 p8]

指针传递（推荐，节省开销）：

void print_student(studentT *aStudent);
print_student(&student1);

[来源：第8章 p8]

引用传递：也可使用引用来避免复制开销。
[来源：第8章 p8，Notes]

易错点与辨析

⚠️ 值传递会导致内存消耗大、复制过程耗时，尤其对于包含很多字段的结构体。
[来源：第8章 p8，Notes]

若担心通过指针/引用误修改实参，可将形参声明为指向 const 的指针或 const 引用，以只读方式访问：

void print_student(const studentT *aStudent);  // 指向 const 的指针
// 或（C++更常见）
void print_student(const studentT &aStudent);  // const 引用  ```
[来源：第8章 p8，Notes]

8.7 函数返回结构体

代码模式

直接返回结构体（使用临时变量）：

studentT GetStudentData() {
    studentT aStudent;
    // ...
    return aStudent;
}
studentT s1 = GetStudentData();

[来源：第8章 p9]

返回结构体指针（使用动态分配）：

studentT *GetStudentData() {
    studentT *aStudent = new studentT;
    // ...
    return aStudent;
}
studentT *s1 = GetStudentData();
// ...
delete s1;

[来源：第8章 p9]

8.8 链表的概念

定义/语法

链表：通过指针连接的链式数据结构，组成元素称为节点。
[来源：第8章 p10]
链表节点结构：一个字段存数据，一个字段存下游节点的内存地址。
```
struct linkNode {
    datatype data;
    linkNode *next;
};
```
[来源：第8章 p12]

规则/规范

数据字段可以是任意类型，包括自定义结构体类型。

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 创建/添加

代码模式

定义头指针并初始化为空：
```
linkNode *head = NULL;
```
[来源：第8章 p13]

头插法（新节点加到链表头）：

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 访问/查找

代码模式

遍历链表查找目标：

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 之后插入新节点：

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 所指结点，正确操作是：
```
T->next = S->next;
S->next = T;
```
答案：B
[来源：第8章 p17，习题1 答案B]

8.10.4 删除

代码模式

删除节点 p 之后的节点：

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]

代码模式

完整代码：

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]

执行逻辑

建立循环链表，头尾相连。
用 while (q->next != q) 判断链表是否只剩一个节点。
for 循环报数 m-1 次后，删除当前节点 q。
重复直到只剩一个节点。
[来源：第8章 p19，Notes]

本章总结（来自PPT）

结构体的作用：处理更复杂的数据。
[来源：第8章 p20，总结]
结构体的使用：
1. 定义类型
2. 定义变量
3. 链表
  [来源：第8章 p20，总结]
⚠️ 重要提醒：链表处理算法看上去一般都很简单，但是对细节的把握要求很高。细节没有处理好，经常把不应该改的地方给改掉了。要小心。
[来源：第8章 p20，Notes]

附：思考题

在动态内存管理中，假设系统可供分配的空间被组织成一个单链表，链表的每个节点表示一块可用空间，包括可用空间的起始和终止地址。初始时，链表只有一个节点，即整个空间的大小。当遇到一个 new 操作时，在链表中寻找一个大于 new 操作申请的空间节点。从这个节点中扣除所申请的空间。当遇到 delete 操作时，将归还的空间形成一个节点，连入链表。经过一段时间的运行，链表中的节点会越来越多。设计一个函数，完成碎片的重组工作。即将一系列连续的空闲空间组合成一块空闲空间。
[来源：第8章 p21，习题]

第八章 结构体

关键考点总览

详细知识点

8.1 结构体的概念

定义/语法

规则/规范

8.2 结构体类型的定义

定义/语法

规则/规范

8.3 定义结构体类型的变量

定义/语法

执行逻辑

8.4 结构体变量的使用

定义/语法

规则/规范

易错点与辨析

8.5 结构体类型的指针

定义/语法

规则/规范

代码模式

易错点与辨析

8.6 结构体作为函数参数

规则/规范

易错点与辨析

8.7 函数返回结构体

代码模式

8.8 链表的概念

定义/语法

规则/规范

链表 vs 数组对比

8.9 链表的种类

定义/语法

8.10 链表操作

8.10.1 创建/添加

代码模式

执行逻辑

8.10.2 访问/查找

代码模式

执行逻辑

8.10.3 插入

代码模式

易错点与辨析

例题结论

8.10.4 删除

代码模式

易错点与辨析

8.11 循环链表应用——约瑟夫环

定义/语法

代码模式

执行逻辑

本章总结（来自PPT）

附：思考题

第八章结构体