结构体、表查找与联合

从“一条记录的哪些事实必须一起成立”开始

若一个坐标由 x、y 两个数共同表达，把它们放进同一个

结构体， 函数就能接收和返回完整坐标，而不是依赖两个容易错配的平行参数。结构体的首要价值是建立数据关系与不变量，节省几个填充字节只是经过测量后才考虑的实现问题。

struct Point {
    int x;
    int y;
};
 
struct Point translate(struct Point point, int dx, int dy)
{
    point.x += dx;
    point.y += dy;
    return point;
}
 
int point_equal(struct Point left, struct Point right)
{
    return left.x == right.x && left.y == right.y;
}

结构参数按值传递，函数修改的是副本；结构返回值与同类型结构赋值会复制结构的值。C 没有内建结构相等运算，因此应逐成员比较。不能用 memcmp 代替值相等：填充字节可能取不同的未指定值，某些成员类型也可能存在不同对象表示却表示相同值。

结构体基础：标准保证到哪里

对非位域成员，C 保证后声明成员的地址更高，并保证第一个成员之前没有填充；实现可以在成员之间与结构尾部加入

填充。 标准不保证“偏移是成员大小的整数倍”，也不保证 int 是四字节。对齐要求与类型大小是两个概念，具体数值由实现和 ABI 决定。

应在目标编译器上用 sizeof 检查对象大小，用标准头 <stddef.h> 的 offsetof 检查成员偏移。_Alignof 是 C11 才加入的工具，不属于 K&R 所处的 ANSI C90 边界；若项目使用现代 C，可以额外报告它，但仍不能把一次结果写成跨平台协议。

#include <stddef.h>
#include <stdio.h>
 
struct Record {
    char state;
    long id;
    char grade;
};
 
int main(void)
{
    printf("size=%lu state=%lu id=%lu grade=%lu\n",
           (unsigned long)sizeof(struct Record),
           (unsigned long)offsetof(struct Record, state),
           (unsigned long)offsetof(struct Record, id),
           (unsigned long)offsetof(struct Record, grade));
    return 0;
}

这段程序只报告当前实现，不预言输出。调整成员顺序有时能缩小结构数组，但它也会改变 ABI、调试可读性、缓存访问顺序和外部接口。先确认结构不是公开二进制接口或持久化格式，再用真实对象数量与访问模式测量；“永远按大小降序排列”不是通用规则。

结构体与函数：值、借用和修改

结构可以作为函数参数和返回值，也可以整体赋值；数组不能整体赋值，这正是二者的重要差异。小结构按值传递往往最清楚：输入不会被修改，返回值表达新状态。若函数需要原地更新大型结构，可接收指针，并让 const struct Config * 表达只读借用。

指针参数还必须说明是否可为空、对象由谁拥有、借用持续多久，以及失败时是否保留原值。struct Job * 本身不表达这些协议。调用 worker->state 等价于 (*worker).state，只减少括号，不会自动做空指针检查或生命周期管理。

结构赋值是浅层成员复制：若成员含指针，复制的是地址值而非所指对象。两个副本可能共享同一缓冲，释放与修改责任必须另行定义。若结构拥有动态资源，应提供初始化、复制或转移、销毁操作，并让失败路径恢复明确状态。

先预测：两个结构逐成员都相等时，memcmp 是否一定返回 0？不一定。成员间与尾部填充不属于字段值，结构复制以外的构造路径可能留下不同字节；值比较应按成员定义。

结构体数组与指针步长

结构体数组 适合表达固定数量或连续存储的同类记录。records + 1 前进一个完整 struct Record，不是前进到下一个成员；尾部填充会成为数组元素步长的一部分，使每个后继元素满足实现所需对齐。

#include <stddef.h>
 
struct Score {
    const char *name;
    int value;
};
 
const struct Score *best_score(const struct Score scores[], size_t count)
{
    const struct Score *best;
    size_t index;
 
    if (count == 0)
        return NULL;
    best = &scores[0];
    for (index = 1; index < count; ++index)
        if (scores[index].value > best->value)
            best = &scores[index];
    return best;
}

数组形参仍会调整为指针，所以函数必须另收 count；返回的

结构体指针 借用原数组中的元素，数组失效后也随之失效。若调用者需要独立结果，应返回结构值或执行深复制，不能保存悬空指针。

自引用结构：递归形状必须间接表示

链表节点需要指向同类型的后继。结构标签 struct Entry 在定义完成前已经能标识该类型，因此成员可写 struct Entry *next；指针自身大小已知。直接写 struct Entry child 会要求对象包含一个同样对象、后者又包含同样对象，尺寸无限，因而不成立。

自引用结构 只描述形状，不描述资源责任。链是否允许环、键是否唯一、节点由表拥有还是调用者借出、删除后谁释放字符串，都要成为操作不变量。

表查找：哈希只缩小候选范围

K&R 用自引用节点构造符号表。下面的

哈希表 采用分离链：相同桶中的节点由 next 串联。查找先计算稳定桶号，再用 strcmp 确认键；哈希相同不表示键相同。

#include <string.h>
 
#define BUCKET_COUNT 17
 
struct Entry {
    const char *key;
    const char *value;
    struct Entry *next;
};
 
static struct Entry *table[BUCKET_COUNT];
 
static unsigned hash_text(const char *text)
{
    unsigned hash = 0;
    while (*text != '\0') {
        hash = 31U * hash + (unsigned char)*text;
        ++text;
    }
    return hash % BUCKET_COUNT;
}
 
const struct Entry *lookup(const char *key)
{
    const struct Entry *entry;
    unsigned bucket = hash_text(key);
 
    for (entry = table[bucket]; entry != NULL; entry = entry->next)
        if (strcmp(entry->key, key) == 0)
            return entry;
    return NULL;
}

这里的

表查找 要求 key 是非空、已终止字符串，表中节点和键在调用期间有效。插入还要决定重复键是覆盖、拒绝还是保留多值；若复制键和值，分配任一步失败都要释放已取得资源且不破坏旧表。销毁要遍历每个桶与每条链，恰好释放一次拥有的对象。

哈希函数中的 (unsigned char)*text 避免当普通 char 为有符号且字符值为负时，把符号扩展混进哈希。桶数 17 只是示例，不是性能保证；负载因子、键分布、扩容策略和攻击输入都影响复杂度。正确性检查应覆盖空桶、首节点命中、链尾命中、碰撞未命中和重复插入。

typedef：缩短名字但不隐藏协议

typedef 可以把复杂声明分层。例如 typedef struct Entry Entry; 允许后续写 Entry *next，而 typedef int (*Compare)(const void *, const void *); 给函数指针声明命名。它改善可读性，却不会创建运行时对象、不会分配内存，也不会让两个本来相同的整数别名获得类型安全隔离。

是否隐藏 struct 关键字取决于接口风格。公开不透明类型常在头文件只声明 typedef struct Table Table;，把完整成员放进实现文件；调用者只能通过函数维护不变量。若调用者需要栈上大小或直接访问成员，定义就必须可见，也意味着布局成为更强的兼容负担。

不要用别名掩盖指针性质，例如 typedef char *String; 会让 const String 表示“常量指针”，而不是“指向 const char 的指针”，容易误读。对所有权敏感的接口，显式 char *、const char * 通常更清楚。

联合：共享存储需要判别标签

联合 的大小足以容纳最大成员并满足各成员对齐，但不保证数值恰好等于最大 sizeof；实现仍可能加入填充。联合适合表示互斥变体，但存储本身不会记录当前写入哪一项，所以可移植程序通常配合枚举形成 标签联合。

enum ValueKind {
    VALUE_INTEGER,
    VALUE_REAL,
    VALUE_TEXT
};
 
struct Value {
    enum ValueKind kind;
    union {
        long integer;
        double real;
        const char *text;
    } data;
};
 
int value_as_real(const struct Value *value, double *result)
{
    if (value == NULL || result == NULL)
        return 0;
    if (value->kind == VALUE_REAL) {
        *result = value->data.real;
        return 1;
    }
    if (value->kind == VALUE_INTEGER) {
        *result = (double)value->data.integer;
        return 1;
    }
    return 0;
}

构造函数应同时设置 kind 和对应成员；读取先检查标签。把一个成员写入后任意读取另一个成员，不应作为通用类型转换、序列化或浮点位检查手段。不同 C 标准与具体实现对跨成员读取有细节规则，线格式仍必须显式编码。

位域：值宽度不是可移植位布局

位域 可写 unsigned int ready : 1; 或 unsigned int mode : 3;，用于表达有限宽度状态。不能取得位域地址，因为它不是可独立寻址的对象；赋入超出可表示范围的值也不能当作统一跨平台截断协议。

位域的高低位方向、是否跨分配单元、单元边界和对齐具有实现相关性，允许的基础类型也受语言版本与实现影响。因此，直接把位域结构覆盖到网络包或硬件寄存器上不具可移植性。可移植边界应读取无符号整数或字节，再用掩码与移位提取协议规定的位。

#define FLAG_READY 0x01U
#define MODE_MASK  0x0eU
#define MODE_SHIFT 1
 
int packet_ready(unsigned char flags)
{
    return (flags & FLAG_READY) != 0;
}
 
unsigned packet_mode(unsigned char flags)
{
    return ((unsigned)flags & MODE_MASK) >> MODE_SHIFT;
}

这段代码把协议位号写在掩码中，不依赖位域排列。若硬件供应商明确规定编译器、ABI 和寄存器头文件，位域可作为受控环境的便捷接口，但应把这种依赖记录并用目标测试验证，而不是宣传为 ISO C 保证。

对外格式：逐字段编码而非转储对象

结构对象表示包含实现选择的大小、填充、对齐、整数宽度和字节序。把 fwrite(&record, sizeof record, 1, file) 或网络 send 当成稳定格式，会把本机 ABI 泄漏到文件。#pragma pack(1) 不是 ISO C 功能，可能产生低效或故障的未对齐访问，也没有解决整数宽度、字节序、版本演进和联合活动成员问题。

稳定格式应逐字段规定：字段编号与含义、固定或变长宽度、字节序、有效范围、字符串编码、缺失字段、版本和校验。解码先检查输入长度再组合数值，遇到未知标签与超范围长度时失败，不让半初始化对象进入业务层。内存结构可以按访问效率演进，编码器保持兼容层。

小结

• 结构体把相关成员组成值；声明顺序有标准保证，具体偏移、对齐与填充由实现决定
• 结构可赋值、传参和返回；含指针的结构复制地址而非资源，值相等应逐成员定义
• 结构体数组以 sizeof 为步长；自引用结构通过指针表达链表、树与哈希碰撞链
• 哈希只选择候选桶，表查找仍要比较完整键，并维护重复键、所有权与销毁不变量
• typedef 是别名；联合共享存储需标签约束活动成员；位域布局不能替代可移植协议
• 文件和网络格式应逐字段编码，不能依赖对象转储或 #pragma pack