# 第三周周记：从组合类型到数据结构，正式踏入“结构化“世界
charc;};sizeof(union Data)取最大成员的大小。同一时刻只能"有效使用"一个成员，写了一个再读另一个得到的是重新解释的二进制位。
适用场景：需要用同一段内存表示不同类型数据时（比如硬件寄存器映射、类型标记的通用数据容器）。
1.4 枚举（enum）
枚举就是给一组整数常量起名字，提高可读性：
enumColor{RED,GREEN,BLUE};RED = 0, GREEN = 1, BLUE = 2（默认从0开始递增），也可以手动指定值。
比#define更好的地方在于：枚举有类型检查，调试时能看到符号名。
1.5 typedef——给类型起别名
typedef不是定义新类型，而是给已有类型起个"短名字"：
typedefunsignedlongulong;typedefstructStudent{charname[20];intage;}Student;// 以后可以写 Student 而不写 struct Student这周写链表代码时大量用到 typedef，比如：
typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;LinkList就是LNode*的别名，这样函数参数写LinkList L比写struct LNode *L简洁多了。
二、预处理与文件组织——编译之前的"魔法"（教案15）
2.1 预处理是什么
C代码从源文件到可执行文件，要经过预处理 → 编译 → 汇编 → 链接四个阶段。预处理发生在编译之前，由预处理器处理所有#开头的指令。
2.2 宏定义（#define）
无参宏——文本替换：
#definePI3.14159#defineMAX_SIZE100带参宏——注意括号陷阱：
#defineSQUARE(x)((x)*(x))如果不加括号，SQUARE(2+3)会变成2+3*2+3 = 11而不是25。这是宏最容易踩的坑。
带参宏和函数的区别：
- 宏是文本替换，没有类型检查、没有调用开销
- 函数有类型安全，但有函数调用开销
- 宏参数可能被多次求值（副作用问题）
2.3 条件编译
条件编译让同一份源码可以根据条件编译出不同版本：
#ifdefDEBUGprintf("调试信息: x = %d\n",x);#endif#ifVERSION>=2// V2功能#else// V1功能#endif常用指令：#ifdef、#ifndef、#if、#elif、#else、#endif
头文件防重复包含就是条件编译最经典的应用：
#ifndef__LIST_H__#define__LIST_H__// 头文件内容#endif2.4 文件包含（#include）
#include<stdio.h>// 系统头文件，在系统目录找#include"list.h"// 自定义头文件，先在当前目录找2.5 多文件组织
真正项目不会把所有代码写在一个.c里。标准做法是：
.h头文件：放声明（函数原型、结构体定义、宏定义、外部变量声明）.c源文件：放实现
编译时分别编译各.c文件，最后链接在一起。
三、数据结构概述与时间复杂度
3.1 什么是数据结构
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。说白了就是研究"数据怎么存、怎么组织"。
数据结构分两层：
- 逻辑结构：数据之间的逻辑关系（线性、树形、图状、集合）
- 物理结构（存储结构）：数据在计算机里怎么存（顺序存储、链式存储、索引存储、散列存储）
3.2 什么是算法
算法是解决特定问题求解步骤的描述，具有五个特性：
- 有穷性
- 确定性
- 可行性
- 输入（0个或多个）
- 输出（1个或多个）
3.3 时间复杂度——BigO表示法
衡量算法效率的标尺。用O(f(n))表示，n是问题规模。
推导规则：
- 用常数1取代所有加法常数
- 只保留最高阶项
- 最高阶项系数化为1
常见时间复杂度排序（从小到大）：
| 复杂度 | 名称 | 典型场景 |
|---|---|---|
| O(1) | 常数阶 | 数组下标访问 |
| O(log n) | 对数阶 | 二分查找 |
| O(n) | 线性阶 | 遍历数组 |
| O(n log n) | 线性对数阶 | 快速排序、归并排序 |
| O(n²) | 平方阶 | 冒泡排序、简单选择排序 |
| O(n³) | 立方阶 | 矩阵乘法 |
| O(2ⁿ) | 指数阶 | 汉诺塔递归 |
空间复杂度类似，衡量算法运行过程中额外占用的内存空间。
四、线性表——数据结构的第一个"正经"结构
4.1 线性表概念
线性表：n个具有相同特性的数据元素的有限序列。
特点：
- 第一个元素无前驱，最后一个元素无后继
- 中间元素有且仅有一个前驱和一个后继
- 元素之间是一对一的关系
4.2 顺序表
顺序表是线性表的顺序存储实现——用一段连续的内存空间依次存储数据元素。
静态分配：
#defineMaxSize50typedefstruct{intdata[MaxSize];intlength;}SqList;数组大小固定，编译时就确定，不能扩展。
动态分配：
typedefstruct{int*data;intMaxSize;intlength;}SeqList;用malloc动态申请内存，用realloc扩容，更灵活。
4.3 顺序表基本操作
- 插入（在第i个位置插入元素）：从最后一个元素开始往后挪，时间复杂度 O(n)
- 删除（删除第i个位置的元素）：从第i+1个元素开始往前挪，时间复杂度 O(n)
- 按位查找：直接下标访问，O(1)
- 按值查找：从头遍历，O(n)
- 判空：
length == 0 - 清空：
length = 0 - 遍历：for循环输出，O(n)
这周写了一道顺序表合并的练习题：把两个有序顺序表 A 和 B 合并成有序顺序表 C。用的是双指针归并的思想，时间复杂度 O(m+n)。
五、单链表
5.1 为什么需要链表
顺序表的优点是随机访问快（O(1)下标访问），但插入删除要大量移动元素。链表用链式存储解决了这个问题——元素可以散布在内存任意位置，用指针串起来。
5.2 单链表结构
typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;带头结点vs不带头结点：
- 带头结点的链表，头结点的
next指向第一个数据结点，这样插入/删除第一个位置的操作和其他位置统一，不用特殊处理头指针。 - 这周写的链表代码全部采用带头结点设计。
5.3 单链表基本操作
- 头插法建表：新结点插在头结点后面，结果和输入顺序相反
- 尾插法建表：新结点插在最后，结果和输入顺序一致
- 按位插入/删除：找到第 i-1 个结点，修改指针，O(n)
- 按值查找：从头遍历比较，O(n)
- 遍历输出：从头到尾走一遍，O(n)
- 求表长：遍历计数
- 销毁：逐个 free 结点
5.4 本周链表实战
这周我写了一个完整的带头结点链表操作程序，包含：
- 头插、尾插
- 头删、尾删（新增）
- 按位插入、按位删除、按位查找
- 按值查找
- 遍历、判空、清空、销毁
踩了一个坑：我用了两个结构体——HeadNode（存 size + next 指针）和LNode（存 data + next 指针），导致HeadNode*和LinkList（即LNode*）是不同类型，GCC 15 编译器报了-Wincompatible-pointer-types错误。修复方式是遍历时从L->next（第一个数据结点）开始，对第1个位置单独处理。
还写了三道数据结构编程题：
- 顺序表合并：双指针归并，A={1,3,5,7,9} + B={2,4,6,8,10} → C={1,2,…,10}
- 有序链表构建：输入10个无序整数，用插入排序思想构建升序链表
- 单链表就地逆置：用头插法把每个结点重新插到头结点后面，不额外开辟数据结点空间
六、本周收获与反思
知识体系搭建
这周最大的收获是完成了从"零散C语法"到"系统化数据结构"的过渡：
| 领域 | 本周内容 |
|---|---|
| C语言语法 | 结构体、联合体、枚举、typedef、内存对齐 |
| C语言工程 | 预处理（宏/条件编译）、多文件组织 |
| 数据结构基础 | 数据结构定义、算法定义、时间复杂度 |
| 线性表 | 顺序表（静态/动态）、单链表 |
踩坑总结
- 结构体类型不兼容：不同结构体指针不能直接赋值，即使成员一样。编译器是对的，类型安全很重要。
- 宏的括号陷阱：带参宏每个参数和整体都要加括号，不然运算优先级会出问题。
- 链表头结点的好处：统一了第一个位置的插入/删除逻辑，写代码时少很多 if-else。
下周计划
- 继续深入单链表操作（双向链表、循环链表）
- 开始学习栈和队列
- 多写代码，把每个操作都手写一