软件技术基础

主要内容

• 结构类型
  • 结构类型的声明和结构变量的定义
  • 结构成员的引用（. 和 -> 运算符）
  • 结构数组和结构指针
  • 结构做函数参数与返回值
• 字段结构
• 联合类型
• 结构指针的应用：链表

结构

• 一些相关联的数据的集合
• 这些数据的类型可以相同，也可以不同
• 这些数据都称为结构的成员

struct stu { // 结构类型声明: 学生信息
    char name[20];      // 姓名
    float score;        // 成绩
};

struct planet { // 结构类型声明: 行星信息
    char name[16];      // 行星的名称
    double diameter;    // 行星直径的千米数
    int moons;          // 卫星数
};

结构类型示例：求两点距离

#include <stdio.h>
#include <math.h>

struct point {  // 点结构类型的声明
    int x;     // x坐标
    int y;     // y坐标
};

int main(void) {
    struct point a, b;  // 声明点结构变量
    double dx, dy, d;
    
    printf("输入两点的坐标：\n");
    scanf("%d%d%d%d", &a.x, &a.y, &b.x, &b.y);
    
    dx = b.x - a.x;
    dy = b.y - a.y;
    d = sqrt(dx * dx + dy * dy);  // 计算欧式距离
    
    printf("the distance is %f\n", d);  // 输出
    return 0;
}

double distance(struct point a1, struct point a2) {
    double dx, dy, d;
    dx = a2.x - a1.x;
    dy = a2.y - a1.y;
    d = sqrt(dx * dx + dy * dy);  // 计算距离
    return d;
}

#include<stdio.h>
#include<math.h>

struct point { // 点结构类型声明
    int	x;
    int y;
};

double distance(struct point, struct point); // 函数原型

int main(void) {	
    struct point a, b; // 声明点结构变量
    double dx, dy, d;
    printf("输入两点的坐标：\n");
    scanf("%d%d%d%d", &a.x, &a.y, &b.x, &b.y);
    d = distance(a, b);	                // 计算距离
    printf("the distance is %f\n", d);  // 输出
    return 0;
}

结构指针作为函数参数

double distance(struct point *p1, struct point *p2) {
    double dx, dy, d;
    dx = (*p2).x - (*p1).x;  // 等价于 p2->x - p1->x
    dy = p2->y - p1->y;
    d = sqrt(dx * dx + dy * dy);  // 计算距离
    return d;
}

结构成员访问: 结构指针->结构成员

• 结构类型的指针也可以作为
  • 函数的参数
  • 函数的返回值

#include<stdio.h>
#include<math.h>

struct point{ // 点结构类型的声明
    int x；
    int y;	
};

double distance(struct point *, struct point *); // 函数原型

int main(void) {	
    struct point a, b; // 声明点结构变量
    double dx, dy, d;
    printf("输入两点的坐标：\n");
    scanf("%d%d%d%d", &a.x, &a.y, &b.x, &b.y);
    d = distance(&a, &b);                 // 计算距离
    printf("the distance is %f\n", d);	  // 输出
    return 0;
}

参数传递方式比较

结构变量赋值

• 同类型的结构变量可以相互赋值。例如:

static struct point {
    int x;
    int y;
} a = {1, 2}, b;

b = a;                    // 合法，对应的各个成员赋值
b = {3, 5};               // 错误
b = (struct point){3, 5}; // 正确，C99复合文字：结构常量

• 若需要更强的可读性，则可以规范化封装 ……

结构变量初始化

struct point Point(int x, int y) {
    struct point temp;
    temp.x = x;
    temp.y = y;
    return temp;
}

#include<stdio.h>
#include<math.h>

struct point { // 点结构类型的声明
    int x;
    int y;
};

struct point Point(int, int);
double distance(struct point *, struct point *);

int main(void) {	
    struct point a, b; // 声明点结构变量
    double d;
    a = Point(0，0);
    b = Point(2，3);
    d = distance(&a，&b);
    printf("the distance is %f\n",d);
    return 0;
}

结构数组

设计一个能够描述学生成绩的结构类型，然后声明对应的结构数组，描述以下成绩表。

计算结构数组元素的个数

设有数组a，其元素个数可通过下述表达式获取:

sizeof(a) / sizeof(a[0])

在数组长度已知且不变化的场景中，建议提前为数组长度定义常量

#define STU_COUNT 3 // 宏定义长度

struct STUDENT stu[STU_COUNT] = {
    {1, "Tom", 'M', {2006,12,20}, 90,83,72,82},
    {2, "Nick", 'M', {2007,05,01}, 78,92,88,78},
    {3, "Sue", 'F', {2007,07,10}, 89,72,98,66}
};

显式标记数组末尾（类似字符串 '\0'）

#include <stdio.h>
#include <string.h>

typedef struct {
    int id;         // 用 -1 作为结尾值
    char name[20];
} Student;

// 遍历找结尾值计算长度
size_t get_stu_arr_len(const Student *arr) {
    size_t len = 0;
    // 遍历直到 id 为 -1（结尾）
    while (arr[len].id != -1) {
        len++;
    }
    return len;
}

int main() {
    // 初始化最后一个元素为结尾值（id=-1）
    Student stu_arr[] = {{1, "Alice"}, {2, "Bob"}, {3, "Charlie"}, {-1, ""}};
    printf("元素个数：%zu\n", get_stu_arr_len(stu_arr)); // 输出 3
    return 0;
}

利用 C99 变长数组（VLA）+ 指针运算（进阶）

#include <stdio.h>

typedef struct {
    int id;
    char name[20];
} Student;

int main() {
    Student stu_arr[] = {{1, "Alice"}, {2, "Bob"}, {3, "Charlie"}};
    // 数组末尾指针 - 数组起始指针 = 元素个数
    size_t len = (&stu_arr)[1] - stu_arr;
    printf("元素个数：%zu\n", len); // 输出 3
    return 0;
}

计算表达式的值

char u[] = "abcde";
char v[] = "xyz";
struct {
    int x;
    char *t;
} a[]={{1, u}, {10, v}}, *p = a;

结构数组做函数参数示例

例：输入商品信息（包括商品编码、名称、价格），分别按照价格和名称排序，并输出所有商品信息。

结构类型声明和相关函数原型

#include<stdio.h>
#define N 10

typedef struct {
    long code;           // 货物编码
    char name[20];       // 名称
    float price;         // 价格
} GOODS;

void input(GOODS *, int);        // 输入n件物品的信息
void display(GOODS *, int);      // 显示n件物品的信息
void sort(GOODS *, int, int (*)(const void *, const void *));  // 排序
int cmpbyName(const void *, const void *);     // 按名称比较
int cmpbyPrice(const void *, const void *);    // 按单价比较

结构数组函数实现

void input(GOODS *p, int n) {
    int i;
    for(i = 0; i < n; i++) {
        scanf("%ld", &p[i].code);
        scanf("%s", (p + i)->name);
        scanf("%f", &(p + i)->price);
    }
}

void display(GOODS *p, int n) {
    int i;
    for(i = 0; i < n; i++) {
        printf("%ld\t", (*(p + i)).code);
        printf("%s\t", (p + i)->name);
        printf("%f\n", p[i].price);
    }
}

使用回调函数排序

sort函数: 按函数指针fp指明的规则对n件物品排序

void sort(GOODS *p, int n, int (*fp)(const void *, const void *)) {
    int i, j;
    GOODS t;
    for(i = 0; i < n - 1; i++) {       // 冒泡法
        for(j = i + 1; j < n; j++) {
            if(fp(p + i, p + j)) {
                t = *(p + i);          // *(p+i) 等价于 p[i]
                *(p + i) = *(p + j);   // *(p+j) 等价于 p[j]
                *(p + j) = t;
            }
        }
    }
}

回调函数实现

int cmpbyPrice(const void *s, const void *t) {
    const GOODS *p1, *p2;
    p1 = (const GOODS *)s;
    p2 = (const GOODS *)t;
    if(p1->price < p2->price)   // 按价格降序
        return 1;
    else
        return 0;
}

int cmpbyName(const void *s, const void *t) {
    const GOODS *p1, *p2;
    p1 = (const GOODS *)s;
    p2 = (const GOODS *)t;
    return (strcmp(p1->name, p2->name) > 0);  // 按名称升序
}

主程序

int main() {
    GOODS g[N];    // 商品信息数组声明
    input(g, N);   // 输入商品信息
    display(g, N); // 显示商品信息
    sort(g, N, cmpbyName); // 按名称排序
    display(g,N);  // 显示排序后商品信息
    sort(g, N, cmpbyPrice); // 按价格排序
    display(g, N); // 显示排序后商品信息
    return 0;
}

联合类型

• 与结构类似，联合类型也是一种构造类型
• 结构变量：占据各自不同空间的各成员变量的集合
• 联合变量：占用同一内存空间的各成员变量的集合
• 联合特点：各成员共享存储

和结构类型比较

union chl {
    char c;
    short h;
    long l;
} v = {'9'};

&u = &u.c
   = &u.h
   = &u.l

联合所有成员从同一存储空间的边界（低地址）开始存放，所以联合各成员的地址和联合变量的地址是相同的，只是类型不同。

联合应用：分离高低字节

union {
    short n;     // 存放要进行分离的数据
    char a[2];   // n与数组a占的字节数相同
} test;

test.n = 0x1234;
low = test.a[0];   // 低字节数据, low = 0x34
high = test.a[1];  // 高字节数据, high = 0x12

联合应用：判断大小端

如何检查处理器是big-endian还是little-endian?

int checkCPUendian() {
    union {
        unsigned int a;
        unsigned char b;
    } c;
    c.a = 1;
    return (c.b == 1);  // return 1: little-endian, return 0: big-endian
}

联合体union的所有成员都从低地址开始存放，利用该特性就可以轻松确认CPU对内存是采用Little-endian还是Big-endian模式读写。

字段结构：以日期为例

struct date {
    unsigned short year  : 7;  // 年
    unsigned short month : 4;  // 月
    unsigned short day   : 5;  // 日
    //             字段名 : 字段宽
};

struct date today;  // today是date字段结构变量

字段结构引用

• 与结构完全相同: . 或 ->
• 字段就是一个小整数，可以出现在其它整数可以出现的任何地方
• 字段在参与运算时被自动转换为int或unsigned int类型的整数

    today.year  = 25; // 2025
    today.month = 12;
    today.day   = 02;

无名字段

struct {
    unsigned a: 4;
              : 2; // 无名字段"空穴"，用以填充
    unsigned b: 4;
} x;

字段的实用价值: 硬件寄存器映射

struct GPIO_Reg {
    unsigned pin0:1;  // 第0位状态
    unsigned pin1:1;  // 第1位状态
    unsigned     :2;  // 硬件保留位
    unsigned mode:2;  // 工作模式设置
};

• 精确匹配硬件布局：字段对应硬件寄存器的每一位
• 简化访问代码：直接访问字段，无需位操作宏
• 代码可读性强：字段名明确表达功能
• 防止误操作：自动屏蔽未使用位

字段的实用价值: 协议数据格式

struct TCP_Header {
    unsigned src_port:16;   // 源端口
    unsigned dst_port:16;   // 目标端口
    unsigned seq_num:32;    // 序列号
    unsigned ack_num:32;    // 确认号
    unsigned data_offset:4; // 数据偏移
    unsigned flags:12;      // 控制标志
};

• 协议精确实现：严格按协议规范定义字段宽度
• 自动打包/解包：编译器处理位级布局
• 减少手动位操作：避免易错的位运算
• 跨平台一致性：确保不同系统解析相同

字段的实用价值: 数据结构对齐控制

struct PackedData {
    unsigned sensor_a:5;  // 传感器A (5位)
    unsigned         :3;  // 填充到字节边界
    unsigned sensor_b:6;  // 传感器B (6位)
    unsigned         :2;  // 填充对齐
};

• 内存紧凑布局：精确控制字段间填充
• 优化存储效率：减少空洞，节约内存
• 强制对齐要求：使用:b强制字节/字对齐
• 传输优化：减少网络/存储空间占用

字段的实用价值: 标志位组合管理

struct FileFlags {
    unsigned read_only:1;   // 只读标志
    unsigned    hidden:1;   // 隐藏文件
    unsigned    system:1;   // 系统文件
    unsigned          :1;   // 保留位
    unsigned   archive:1;   // 归档标志
    unsigned          :3;   // 未来扩展
};

• 逻辑分组清晰：相关标志位集中管理
• 扩展性预留：未命名位为未来保留
• 代码自文档化：字段名即文档
• 内存最小化：多个标志仅用1字节

试一试字段结构与联合示例

如何访问16位字中的高低字节和各二进制位？

1. 定义8位宽的字段byte0, byte1
   • 表示一个16位字中的高/低字节
2. 定义1位宽的字段[b0-b15]
   • 表示一个16位字中的bit
3. 定义联合类型
   • 使1个short变量、2个byte字段与16个bit字段共享存储空间

#include <stdio.h>

struct w16_bytes {
    unsigned short byte0 : 8;   // byte0：低字节
    unsigned short byte1 : 8;   // byte1：高字节
};

struct w16_bits {
    unsigned short b0:1, b1:1, b2:1, b3:1, b4:1, b5:1, b6:1, b7:1,
                   b8:1, b9:1, b10:1, b11:1, b12:1, b13:1, b14:1, b15:1;
};

union w16 {  // i、byte、bit共享存储
    short i;
    struct w16_bytes byte;
    struct w16_bits bit;
};

使用及运行结果

int main(void) {
    union w16 w = {0};   // w.i为0
    
    w.bit.b9 = 1;        // 相当于byte1为2
    w.bit.b10 = 1;       // 相当于byte1为6
    w.byte.byte0 = 0x62;
    
    printf("w.i=0x%x\n", w.i);  // 按整型解释
    return 0;
}

使用及运行结果…

int main(void) {
    union w16 w = {0};   // w.i为0
    
    w.bit.b9 = 1;        // 相当于byte1为2
    w.bit.b10 = 1;       // 相当于byte1为6
    w.byte.byte0 = 0x62;
    
    printf("w.i=0x%x\n", w.i);  // 按整型解释
    return 0;
}

w.i=0x662

结构指针应用：链表

• 建立: 单链表、队列、栈
• 遍历: 列举、统计、查找
• 插入: 头、尾、指定位置
• 删除: 定位、删除、释放
• 归并: 定位链尾、更新指针
• 排序: 交换数据、变更链接

顺序存储 vs 链式存储

思考: 编辑文本时发生在字符数组上的事情…

启发: 火车车厢的编组调整…

C语言的动态存储分配函数

动态存储分配函数的原型声明在<stdlib.h>中

• void *malloc(size_t size);
• void *calloc(size_t n, size_t size);
• void *realloc(void *p_block, size_t size);
• void free(void *p_block);

size_t在<stdio.h>中定义

typedef unsigned size_t;

基本概念

• 链表是一种常用的动态数据结构，由一系列包含数据域和指针域的结点组成。
• 如果结点的指针域中只包含一个指针指向后一个结点，这种链表称为单向链表。

单向链表

• 头指针head: 存放一个地址，指向第一个元素
• 结点: 链表中的元素，为结构类型，包括
  • 数据域data，用户数据
  • 指针域next，下一结点的地址
• 链尾tail: 最后一个元素，指针域为NULL

链表结点的结构类型定义

struct intNode {
    int data;
    struct intNode *next;  // 指向该结构类型的指针
};

struct intNode *head;  // 头指针声明

自引用：在定义内部引用自己定义的结构类型

动态创建结点

head = (struct intNode *)malloc(sizeof(struct intNode));
head->data = 10;
head->next = (struct intNode *)malloc(sizeof(struct intNode));
head->next->data = 12;
head->next->next = NULL;

建立单向链表

• 用链表实现的经典数据结构
  • 先进后出链: 栈(Stack)
    • 结点的排列顺序和元素的输入顺序相反
  • 先进先出链: 队列(Queue)
    • 结点的排列顺序和元素的输入顺序相同

建立先进先出链表

用循环方式建立先进先出链表的步骤：

1. 声明头指针、尾指针struct intNode *head=NULL,*tail;

2. 创建第一个结点，包括:

   • 给第一个结点动态分配存储并使头指针指向它

     head=(struct intNode *)malloc(sizeof(struct intNode));
     

   • 给第一个结点的数据域中成员赋值head->data=x;
   • 使尾指针也指向第一个结点tail=head;

建立先进先出链表…

3. 循环建立后续结点
   • 如果没遇到结束标志，进行下列操作：
     • 给后继结点动态分配存储并使前驱结点的指针指向它。

     tail->next=(struct intNode *)malloc(sizeof(struct intNode));
     

     • 使尾指针指向新建立的后继结点tail=tail->next;
     • 给后继结点的数据域中成员赋值tail->data=x;
4. 给尾结点（最后一个结点）的指针赋NULL值tail->next=NULL;

struct intNode *createList() {
    struct intNode *head = NULL, *tail = NULL;
    int x;
    
    scanf("%d", &x);  // 输入第1个整数
    if(x) {           // 输入非空，若为0，结束输入
        head = (struct intNode *)malloc(sizeof(struct intNode));
        head->data = x;        // 对数据域赋值
        tail = head;           // tail指向第一个结点
        
        scanf("%d", &x);       // 输入第2个整数
        while(x) {             // 输入非空，若为0，结束输入
            tail->next = (struct intNode *)malloc(sizeof(struct intNode));
            tail = tail->next;       // tail指向新创建的结点
            tail->data = x;          // 向新创建的结点的数据域赋值
            scanf("%d", &x);         // 继续输入整数
        }
        tail->next = NULL;     // 对最后一个结点的指针域赋NULL值
    }
    return head;
}

输入: 10 12 3 4

调用函数建立链表

struct intNode *createList(void);     // 声明创建链表的函数
void printList(struct intNode *head); // 声明输出链表结点内容的函数

int main() {
    struct intNode *head = createList(); // 调用createList函数创建链表
    printList(head); // 输出链表结点内容
    return 0;
}

调用函数遍历链表

void printList(struct intNode *head) {
    struct intNode *p = head;  // 遍历指针p指向链头
    
    while(p != NULL) {         // p非空
        printf("%d\t", p->data);  // 输出结点数据域中成员的值(以制表符分隔)
        p = p->next;           // 遍历指针p指向下一结点
    }
}

int main() {
    // 1. 提示用户输入
    printf("请输入链表节点的整数（输入0结束）：\n");
    
    // 2. 调用createList创建链表，返回头指针
    struct intNode *listHead = createList();
    
    // 3. 遍历链表并输出内容
    printf("链表内容为：");
    printList(listHead);
    printf("\n");
    
    // 4. 注意！释放链表内存，避免内存泄漏
    struct intNode *current = listHead;
    while (current != NULL) {
        struct intNode *temp = current;  // 暂存当前节点
        current = current->next;         // 先移动指针
        free(temp);                      // 释放当前节点内存
    }
    
    return 0;
}

递归建立链表

struct intNode *createList() {
    struct intNode *head = NULL;
    int x;
    scanf("%d", &x);
    
    if(x == 0)  // 遇到结束标记，返回NULL
        return NULL;
    else {
        head = (struct intNode *)malloc(sizeof(struct intNode));                                 
        head->data = x;              // 对新创建结点的数据域赋值
        head->next = createList();   // 递归创建下一结点
        return head;                 // 返回链头地址
    }
}

统计链表结点数目

int countNodes(struct intNode *head) {
    struct intNode *p = head;
    int num = 0;
    while(p != NULL) {
        num++;
        p = p->next;
    }
    return num;
}

int countNodes_recursive(struct intNode *head) {
    struct intNode *p = head;
    if(p)
        return (1 + countNodes_recursive(p->next));
    else
        return 0;
}

查找结点

用递归法查找链表中数据成员值与形参n相同的结点。找到，返回该结点的地址，否则，返回NULL。

查找结点…

struct intNode *findNodes(struct intNode *head, int n) {
    struct intNode *p = head;
    
    if(p) {  // 链表非空，查找
        if(p->data == n)
            return p;  // 找到，返回该结点的地址
        else
            return (findNodes(p->next, n));  // 递归查找
    } else {
        return NULL;
    }
}

插入结点

插入位置

• 链头、链尾、链中

插入方式

• 作为插入点的新后继结点
• 作为插入点的新前驱结点

这里以前驱插入为例介绍

插入操作

• 链头:

  head = new;
  new->next = p;
  

• 链尾:

  new->next = NULL; // p
  last->next = new;
  

• 链中:

  new->next = p;
  last->next = new;
  

插入结点实现

#define LEN sizeof(struct intNode)

struct intNode *insertNode(struct intNode **hp, int x) {
    struct intNode *p, *last, *new;
    new = (struct intNode *)malloc(LEN);  // 创建一个新节点
    new->data = x;
    p = *hp; // 用于寻找插入位置
    
    while(p != NULL && x > p->data) { // 在升序链表中寻找
        last = p;
        p = p->next;
    }
    
    if(p == *hp) {  // 插入点是链头
        *hp = new;  // 新节点为链头
        new->next = p;
    } else if(p == NULL) {  // 插入点是链尾
        new->next = NULL;   // 新节点为链尾
        last->next = new;
    } else {  // 插入点是链中
        new->next = p;      // 新节点为p的前驱结点
        last->next = new;
    }
    
    return new;
}

删除结点

删除步骤

1. 查找被删结点
2. 改变连接关系
3. 释放存储空间

删除操作

• 链头: head = p->next;
• 非链头: last->next = p->next;
• 释放: free(p);

删除结点实现

int deleteNodes(struct intNode **hp, int n) {
    struct intNode *p, *last; // 用于寻找被删结点及其前驱结点
    p = *hp;                  // 遍历指针p指向链头

    while(p != NULL && p->data != n) {  // 查找成员值与n相等的结点
        last = p;      // last指向当前结点
        p = p->next;   // p指向下一结点
    }

    if(p == NULL)      // 没有符合条件的结点
        return 0;

    if(p == *hp)       // 被删结点是链头
        *hp = p->next;
    else               // 被删结点不是链头
        last->next = p->next;
    
    free(p);           // 释放被删结点的存储
    return 1;
}

归并链表

对于非空链表A、B，将链表B归并到链表A，指将链表A的链尾指向链表B的链头以形成一个新的链表。

归并过程

1. 遍历链表A找到其链尾
2. 将链表B的头指针值赋给链表A链尾的指针域

void conLists(struct intNode *a, struct intNode *b) {
    struct intNode *p = a;
    
    while(p->next != NULL) {
        p = p->next;
    }
    p->next = b;
}

链表排序

链表排序是指将链表的结点按指定数据域从小到大（升序）或从大到小（降序）的顺序连接

链表排序方法1：交换数据域

void sortList(struct intNode *head) {
    struct intNode *p1, *p2;
    int t;
    
    for(p1 = head; p1 != NULL; p1 = p1->next) {
        for(p2 = p1->next; p2 != NULL; p2 = p2->next) {
            if(p1->data > p2->data) {
                t = p1->data;           // 交换数据域
                p1->data = p2->data;
                p2->data = t;
            }
        }
    }
}

链表排序方法2：改变连接关系

if(p1->data > p2->data) {
    t = p2->next;
    prior1->next = p2;   // 分别顶替
    prior2->next = p1;
    p2->next = p1->next; // 交换后继
    p1->next = t;
    p2 = p1;             // 交换指向
    p1 = prior1->next;
}

高级链表类型

双向链表：

• 结点的指针域包含两个指针
• 一个指向前一个结点，另一个指向后一个结点

十字交叉链表：

• 结点的指针域包含两个指针
• 一个指向后一个结点，另一个指向另外一个链表

应用： 用十字交叉链表保存学生基本信息和成绩

双向链表

如果结点的指针域包含两个指针，且一个指向前一个结点，另一个指向后一个结点，这种链表称为双向链表。

十字交叉链表

如果结点的指针域包含两个指针，且一个指向后一个结点，另一个指向另外一个链表，这种链表称为十字交叉链表。

用十字交叉链表保存学生基本信息和成绩

学生基本信息表

学生学习成绩表

十字交叉链表结构

typedef struct score_tab {
    char num[5];           // 学号
    char course[20];       // 课程名称
    int score;             // 成绩
    struct score_tab *next; // 指向下一个课程成绩结点
} courses;

typedef struct student_tab {
    char num[5];           // 学号
    char name[10];         // 姓名
    char sex;              // 性别
    int age;               // 年龄
    char addr[30];         // 家庭住址
    char phone[12];        // 联系电话
    char *memo;            // 备注字段
    courses *head_score;   // 指向成绩链的头指针
    struct student_tab *next; // 指向下一个结点
} studs;

总结

• 结构是C语言中组织相关数据的重要方式
• 联合提供了共享内存的机制
• 字段结构用于位级数据操作
• 链表是动态数据结构的核心
• 掌握这些概念对于编写高效的C程序至关重要