C语言——数据结构相关

1. 高级宏定义

1.1 不带参数的宏定义

1	#define PI 3.14

为了和普通变量区分，宏的名字通常约定是全部由大写字母组成
宏定义只是进行简单的替换，编译器不会对宏定义检查语法错误，检查出来也是替换之后的代码报错
宏定义的作用域是从定义的位置开始到整个程序结束

可以用 #undef 来终止宏定义的作用域

#include <stdio.h>

#define PI 3.14

int main(void) {
    int r;
    float s;
    scanf("%d", &r);
#undef PI // 结束 PI 宏的作用
    s = PI * r * r;
    printf("S = %.2f\n", s);

    return 0;
}

宏定义允许嵌套

#include <stdio.h>

#define R  6371
#define PI 3.14
#define V  PI * R * R * R * 4 / 3

int main(void) {
    printf("地球的体积大约是：%.2f\n", V);

    return 0;
}

1.2 带参数的宏定义

1	#define MAX(x, y) (((x) > (y)) ? (x) : (y))

#include <stdio.h>

#define MAX(x, y) (((x) > (y)) ? (x) : (y))

int main(void) {
    int a, b;

    printf("请输入两个数：");
    scanf("%d%d", &a, &b);
    printf("%d 较大\n", MAX(a, b)); // MAX(a,b) ，b前面少一个空格也可以正常执行，此时编译器将其正确理解为带参数的宏

    return 0;
}

之所以加那么多括号是为了防止宏定义无脑替换后，执行结果出现意想不到的错误。下面给出一个替换后计算错误的例子：

#include <stdio.h>

#define SQUARE(x) x * x

int main(void) {
    int x;

    printf("请输入一个整数：");
    scanf("%d", &x);

    printf("%d 的平方是： %d\n", x, SQUARE(x));
    printf("%d 的平方是： %d\n", x+1, SQUARE(x+1)); // x + 1 * x + 1 = 11

    return 0;
}

为了避免出错，一定不要吝啬你的括号：

1	#define SQUARE(x) ((x) * (x))

1.3 宏定义的特殊应用

# 和 ## 是两个预处理运算符。

在带参数的宏定义中，# 运算符后面应该跟一个参数，预处理器会把这个参数转换为一个字符串。

#include <stdio.h>

#define STR(s) # s

int main(void) {
    printf("%s\n", STR(Awellfrog));

    return 0;
}

#include <stdio.h>

#define STR(s) # s

int main(void) {
    printf(STR(Hello    %s num = %d), STR(Awellfrog), 520); // 中间很长的空格会被合并为 1 个

    return 0;
}

## 运算符被称为记号连接运算符，可以使用 ## 运算符连接两个参数

#include <stdio.h>

#define TOGETHER(x, y) x ## y

int main(void) {
    printf("%d\n", TOGETHER(5, 20));

    return 0;
}

可变参数

之前在进阶知识（一）中学习了如何让函数支持可变参数，带参数的宏定义也是使用可变参数的：
1
#define SHOWLIST(...) printf(# __VA_ARGS__)

其中 ... 表示使用可变参数， __VA_ARGS__ 在预处理中被实际的参数集所替换。

#include <stdio.h>

#define SHOWLIST(...) printf(# __VA_ARGS__)

int main(void) {
    SHOWLIST(Awellfrog, 520, 3.14\n);

    return 0;
}

#include <stdio.h>

#define PRINT(format, ...) printf(# format, ##__VA_ARGS__)

int main(void) {
    PRINT(num = %d\n, 520);
    PRINT(Hello Awellfrog!\n); // ## 之后可以为空

    return 0;
}

2. 内联函数

即在函数之前加 inline ，该函数将被在调用出展开。

先看一个带参数的宏定义：

#include <stdio.h>

#define SQUARE(x) ((x) * (x))

int main(void) {
    int i = 1;

    while (i <= 100) {
        printf("%d 的平方是 %d\n", i, SQUARE(i++)); // ((i++) * (i++))
    }

    return 0;
}

可以看到结果是错误的，由于展开之后是 ((i++) * (i++)) 在打印结果之前 i++ 了两次，于是打印时 i = 3 ，且计算过程是 (1) * (2) 。由此观之，宏定义很容易出现错误，于是 inline 内联函数就有了用武之地。

直接使用函数，需要在用到时分配空间，效率较低。

如果使用带参数的宏定义，则直接替换至代码段中，函数调用效率提高了。

但是带参数的宏定义很容易出错，所以使用内联函数将函数直接替换至调用处，解决函数调用的效率问题。不过编译时间有所加长。

内联函数虽然节省了函数调用的时间消耗，但由于每一个函数出现的地方都要进行替换，因此增加了代码编译的时间。另外，并不是所有的函数都能够变成内联函数。
现在的编译器也很聪明,就算你不写 inline ，它也会自动将一些函数优化成内联函数。
总结：编译器比你更了解哪些函数应该内联哪些不能内联,所以这个知识点你只需要知道就好…

3. 结构体

为了区分结构体和常量、变量，结构体名称通常第一个字母大写。
结构体被声明时并不占用内存空间，只有定义一个结构体变量时才会分配内存空间。

初始化结构体变量的两种方法（假设结构体已经申明好了）：

方法一：直接按顺序赋值

struct Student stu = {
	"番茄元",
	21,
	180,c
	"awellfrog"
}；

方法二：用对每个成员赋值

struct Student stu = {
	.name = "番茄元",
	.age = 21,
	.height = 180,
	.website = "awellfrog.cc"
}
// 或只初始化部分
struct Student stu = {
	.name = "番茄元",
	.website = "awellfrog.cc"
}

算一算

算一算下面的程序执行结果是多少？

#include <stdio.h>

int main(void) {
    struct Au {
        char a;
        int b;
        char c;
    } au = {'x', 520, 'o'};

    printf("size of au = %d\n", sizeof(au));

    return 0;
}

按理说两个 char 一个 int 一共是 6 个字节，但是结果却显示 12 个字节。这是由于编译器将结构体内的数据进行了对齐操作，使得取数更快。

上面这种情况下，按照 int 的 4 字节对齐。

如果调整初始化的位置，将得到不一样的结果：

#include <stdio.h>

int main(void) {
    struct Au {
        char a;
        char c; // 此处做出位置调整
        int b;
    } au = {'x', 'o', 520};

    printf("size of au = %d\n", sizeof(au));

    return 0;
}

结构体嵌套

#include <stdio.h>

struct Date {
    int year;
    int month;
    int day;
};

struct Book {
    char title[128];
    char author[45];
    float price;
    struct Date date; // 结构体嵌套
} book = {
        "《带你学C带你飞》",
        "小甲鱼",
        48.8,
        {2023, 2, 25}
};

int main(void) {
    printf("书名：%s\n", book.title);
    printf("作者：%s\n", book.author);
    printf("售价：%.2f\n", book.price);
    printf("出版日期：%d-%d-%d\n", book.date.year, book.date.month, book.date.day); // 嵌套结构体的使用

    return 0;
}

4. 结构体数组和结构体指针

结构体数组

结构体数组有两种定义方式：

声明结构体的时候定义

1
2
3

struct 结构体名称 {
	结构体成员;
} 数组名[长度];

先声明一个结构体类型（比如上面的 Book），在用此类型定义一个结构体数组
1
2
3
4
struct 结构体名称 {
结构体成员;
};
struct 结构体名称数组名[长度];

结构体指针

1 2	struct Book *pt; pt = &book; // 与数组不同，结构体的地址必须用取址符获取

通过结构体指针访问结构体成员有两种方法：

(*结构体指针).成员名

int main(void) {
    struct Book *pt;
    pt = &book;

    printf("书名：%s\n", (*pt).title);
    printf("作者：%s\n", (*pt).author);
    printf("售价：%.2f\n", (*pt).price);
    printf("出版日期：%d-%d-%d\n", (*pt).date.year, (*pt).date.month, (*pt).date.day);

    return 0;
}

结构体指针->成员名

int main(void) {
    struct Book *pt;
    pt = &book;

    printf("书名：%s\n", pt->title);
    printf("作者：%s\n", pt->author);
    printf("售价：%.2f\n", pt->price);
    printf("出版日期：%d-%d-%d\n", pt->date.year, pt->date.month, pt->date.day);

    return 0;
}

两个结构体变量之间是可以直接赋值的

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    struct Test {
        int x;
        int y;
    } t1, t2;

    t1.x = 1;
    t1.y = 2;

    t2 = t1;

    printf("t2.x = %d, t2.y = %d\n", t2.x, t2.y);

    return 0;
}

传递结构体参数

#include <stdio.h>

struct Date {
    int year;
    int month;
    int day;
};

struct Book {
    char title[128];
    char author[45];
    float price;
    struct Date date;
} book = {
        "《带你学C带你飞》",
        "小甲鱼",
        48.8,
        {2023, 2, 25}
};

struct Book getInput(struct Book);

struct Book getInput(struct Book book) { // 将结构体作为参数传递
    printf("请输入书名：");
    scanf("%s", book.title);
    printf("请输入作者：");
    scanf("%s", book.author);
    printf("请输入售价：");
    scanf("%f", &book.price);
    printf("请输入出版日期：");
    scanf("%d-%d-%d", &book.date.year, &book.date.month, &book.date.day);

    return book;
}

void printBook(struct Book);

void printBook(struct Book book) {
    printf("书名：%s\n", book.title);
    printf("作者：%s\n", book.author);
    printf("售价：%.2f\n", book.price);
    printf("出版日期：%d-%d-%d\n", book.date.year, book.date.month, book.date.day);
}

int main(void) {
    struct Book b1, b2;

    printf("请录入第一本书的信息...\n");
    b1 = getInput(b1);
    putchar('\n');
    printf("请录入第二本书的信息...\n");
    b2 = getInput(b2);

    printf("\n\n录入完毕，开始打印验证：\n\n");

    printf("打印第一本书的信息...\n");
    printBook(b1);
    putchar('\n');
    printf("打印第二本书的信息...\n");
    printBook(b2);
    return 0;
}

由于第一个日期输入没有按照格式 2017-1-1 输入，而是输入为 2017.1.1 所以 b1 中日期 2017 被接收，月和日随机生成，而 .1.1 被当作下一个书名的输入。b2 按照 2023-2-25 输入，正常执行。

直接传递结构体，传输速度慢，改用指针传递结构体参数，执行效率更高。

#include <stdio.h>

struct Date {
    int year;
    int month;
    int day;
};

struct Book {
    char title[128];
    char author[45];
    float price;
    struct Date date;
} book = {
        "《带你学C带你飞》",
        "小甲鱼",
        48.8,
        {2023, 2, 25}
};

void getInput(struct Book *);

void getInput(struct Book *book) {
    printf("请输入书名：");
    scanf("%s", book->title);
    printf("请输入作者：");
    scanf("%s", book->author);
    printf("请输入售价：");
    scanf("%f", &book->price);
    printf("请输入出版日期：");
    scanf("%d-%d-%d", &book->date.year, &book->date.month, &book->date.day);
}

void printBook(struct Book *);
void printBook(struct Book *book) {
    printf("书名：%s\n", book->title);
    printf("作者：%s\n", book->author);
    printf("售价：%.2f\n", book->price);
    printf("出版日期：%d-%d-%d\n", book->date.year, book->date.month, book->date.day);
}

int main(void) {
    struct Book b1, b2;

    printf("请录入第一本书的信息...\n");
    getInput(&b1); // 直接传递结构体的地址
    putchar('\n');
    printf("请录入第二本书的信息...\n");
    getInput(&b2);

    printf("\n\n录入完毕，开始打印验证：\n\n");

    printf("打印第一本书的信息...\n");
    printBook(&b1);
    putchar('\n');
    printf("打印第二本书的信息...\n");
    printBook(&b2);
    return 0;
}

动态申请结构体

使用 malloc 函数为结构体分配存储空间

#include <stdio.h>
#include <stdlib.h>

struct Date {
    int year;
    int month;
    int day;
};

struct Book {
    char title[128];
    char author[45];
    float price;
    struct Date date;
} book = {
        "《带你学C带你飞》",
        "小甲鱼",
        48.8,
        {2023, 2, 25}
};

void getInput(struct Book *);

void getInput(struct Book *book) {
    printf("请输入书名：");
    scanf("%s", book->title);
    printf("请输入作者：");
    scanf("%s", book->author);
    printf("请输入售价：");
    scanf("%f", &book->price);
    printf("请输入出版日期：");
    scanf("%d-%d-%d", &book->date.year, &book->date.month, &book->date.day);
}

void printBook(struct Book *);
void printBook(struct Book *book) {
    printf("书名：%s\n", book->title);
    printf("作者：%s\n", book->author);
    printf("售价：%.2f\n", book->price);
    printf("出版日期：%d-%d-%d\n", book->date.year, book->date.month, book->date.day);
}

int main(void) {
    struct Book *b1, *b2;

    b1 = (struct Book *)malloc(sizeof(struct Book));
    b2 = (struct Book *)malloc(sizeof(struct Book));
    if (b1 == NULL || b2 == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }

    printf("请录入第一本书的信息...\n");
    getInput(b1); // 直接传递结构体的地址
    putchar('\n');
    printf("请录入第二本书的信息...\n");
    getInput(b2);

    printf("\n\n录入完毕，开始打印验证：\n\n");

    printf("打印第一本书的信息...\n");
    printBook(b1);
    putchar('\n');
    printf("打印第二本书的信息...\n");
    printBook(b2);
    return 0;
}

5. 内存碎片

如下图，从连续内存中分别申请两块内存，如果 A 被释放，第三次申请的内存空间比 12kb 大，所以原来 A 所在的内存空间就变成了内存碎片，或者说内存垃圾。

程序中调用 malloc 函数需要从应用层切换到内核层，再利用 windows 分配内存，分配完之后再返回应用层，时间开销较大。可以使用建立内存池的方法来节省内存分配时间的开销，并将内存碎片利用起来。

内存池

当用户申请内存块时，优先在内存池查看有没有可用内存垃圾（碎片），如果有直接使用该部分内存即可，不用再调用malloc 去内存中分配。

当用户释放空间时，先查看内存池是否用空闲空间，如果有就将该释放的内存块放入内存池中称为垃圾，供下一次分配使用。

内存池的简单实现：

使用单链表来维护一个简单地内存池
只需要将没有用的内存空间地址一次用一个单链表记录下来，当再次需要的时候，从这个单链表中获取即可。

6. typedef

6.1 基础部分

可以用作起别名，作用类似宏定义

#include <stdio.h>

typedef int INTEGER;
typedef int* PTRINT;

int main(void) {
    INTEGER a = 520;
    PTRINT b, c;

    b = &a;
    c = b;

    printf("addr of a = %p, c = %p\n", &a, c);

    return 0;
}

可以将一个名称定义为多个名称：

1	typedef int INTEGER, *PTRINT;

运行结果和上面的代码相同。

但是如果使用宏定义，则可能出现问题：

1 2	typedef int INTEGER; #define PTRINT int*

报错了，原因是 PTRINT b, c; 被宏定义替换后是 int * b, c; b 是指针，c 是整形。

宏定义只是单纯的替换，而 typedef 是一种对类型的封装。

用在结构体上，可以省略反复写 struct 的过程

#include <stdio.h>
#include <stdlib.h>

typedef struct Data {
    int year;
    int month;
    int  day;
} DATE, *PDATE;

int main(void) {
    PDATE date; // 结构体指针

    date = (PDATE)malloc(sizeof(DATE)); // 给结构体指针分配内存空间
    if (date == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }

    date->year = 2023;
    date->month = 2;
    date->day = 25;

    return 0;
}

6.2 较为恐怖的申明（恐怖，但是常用）

指向大小为 3 的数组的指针

#include <stdio.h>

typedef int (*PTR_TO_ARRAY)[3];

int main(void) {
    int array[3] = {1, 2, 3};
    PTR_TO_ARRAY ptr_to_array = &array;

    int i;
    for (i = 0; i < 3; i++) {
        printf("%d\n", (*ptr_to_array)[i]);
    }

    return 0;
}

指向函数的指针

#include <stdio.h>

typedef int (*PTR_TO_FUNC)(void); // 指向参数为空，返回类型为 int 的函数指针

int func(void) {
    return 520;
}

int main(void) {
    PTR_TO_FUNC ptr_to_func = &func;

    printf("%d\n", (*ptr_to_func)());

    return 0;
}

一个指针数组，数组的每个值都指向一个参数为 int 返回值为 int 的函数

#include <stdio.h>

typedef int *(*PTR_TO_FUNC)(int);

int *funA(int num) {
    printf("%d\t", num);
    return &num; // 此处执行完后，num 的内存被释放，该地址没有意义，只是为了测试程序
}

int *funB(int num) {
    printf("%d\t", num);
    return &num; // 此处执行完后，num 的内存被释放，该地址没有意义，只是为了测试程序
}

int *funC(int num) {
    printf("%d\t", num);
    return &num; // 此处执行完后，num 的内存被释放，该地址没有意义，只是为了测试程序
}

int main(void) {
    PTR_TO_FUNC array[3] = {&funA, &funB, &funC};
    int i;

    for (i = 0; i < 3; i++) {
        printf("addr of num: %p\n", (*array[i])(i));
    }

    return 0;
}

可以看到由于返回局部变量地址，被编译器警告。同时可以看到三个函数地址是相同的，这证明了每次调用后前一个函数的内存释放，并分配给下一个函数。

函数指针的嵌套

1 2	int calc(int ()(int, int), int, int); int (select(char))(int, int);

可以利用 typedef 简写为：

typedef int (*PTR_TO_FUN)(int, int);

int calc(PTR_TO_FUN, int, int);
TPR_TO_FUN select(char);

7. 共用体

所有成员共享同一个内存地址！

union 共用体名称 {
	共用体成员1;
	共用体成员2;
	...
};

定义方式

和结构体定义方式类似：

union data {
	int i;
	char ch;
	float f;
};
union data a, b, c;

初始化方式

union data {
	int i;
	char ch;
	float f;
};

union data a = {520}; // 共用体只能初始化中的一个成员，默认初始化第一个成员
union data b = a; // 可以用一个共用体给另一个共用体赋值
union data c = {.ch = 'C'}; // C99 新增特性，指定初始化成员

根据下面的例子来分析共用体的特点：

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

union Test {
    int i;
    double pi;
    char str[10];
};

int main(void) {
    union Test test;

    test.i = 520;
    test.pi = 3.14;
    strcpy(test.str, "awellfrog.cc");

    printf("addr of test.i: %p\n", &test.i);
    printf("addr of test.pi: %p\n", &test.pi);
    printf("addr of test.str: %p\n", &test.str);

    printf("test.i: %d\n", test.i);
    printf("test.pi: %.2f\n", test.pi);
    printf("test.str: %s\n", test.str);

    printf("sizeof(test) = %d\n", sizeof(test));

    return 0;
}

可以看到，共用体的三个成员共享一个内存地址
共用体只有最后一个赋值的成员结果正确，其他被覆盖
公用体的大小并不单纯按照最大成员内存来分配（str[10] 最大，占用 10 个字节，但是 test 实际占用 16 个字节。），还和内存的对齐方式有关。

8. 枚举类型

使用枚举类型，便于一些使用连续值作为判据的分支：

#include <stdio.h>
#include <time.h>

int main(void) {
    enum Week {sun, mon, tue, wed, thu, fri, sat};
    enum Week today;
    struct tm *p;
    time_t t;

    time(&t);
    p = localtime(&t);

    today = p->tm_wday; // 获取今天是周几
    printf("today : %d\n", today);

    switch(today) {
        case mon :
        case tue :
        case wed :
        case thu :
            printf("疯狂星期四！\n");
            break;
        case fri :
            printf("没有女朋友，只能学习！\n");
            break;
        case sat :
            printf("没有女朋友，只能学习！\n");
            break;
        case sun :
        default:
            printf("error!\n");
    }

    return 0;
}

枚举类型都是前一个值 +1 ：

#include <stdio.h>

int main(void) {
    enum Color {red = 10, green, blue};
    enum Color rgb;

    for (rgb = red; rgb <= blue; rgb++) {
        printf("rgb is %d\n", rgb);
    }

    return 0;
}

如果从中间赋值：（赋值的量为所赋值，其余均为前一个 +1 ）：

#include <stdio.h>

int main(void) {
    enum Color {red, green, blue = 10, yellow};
    enum Color rgb;

    printf("red is %d\n", red);
    printf("green is %d\n", green);
    printf("blue is %d\n", blue);
    printf("yellow is %d\n", yellow);

    return 0;
}

枚举常量定义后，其值不能修改，否则报错。

9. 位域

单片机（Microcontrollers）是一种集成电路芯片，是采用超大规模集成电路技术把具有数据处理能力的中央处理器CPU、随机存储器RAM、只读存储器ROM、多种 I/O 口和中断系统、定时器/计数器等功能（可能还包括显示驱动电路、脉宽调制电路、模拟多路转换器、A/D转换器等电路）集成到一块硅片上构成的一个小而完善的微型计算机系统，在工业控制领域广泛应用。

在单片机这种内存寸土寸金的设备上，如果用一个 int 来存放 bool 值，就显得有些浪费了，可以使用位域，将一个字节拆开来用。

位域，又称位段、位字段

位域的使用方法：

使用位域的做法是在结构体定义时，在结构体成员后面使用冒号（:）和数字来表示该成员所占的位数。

#include <stdio.h>

int main(void) {
    struct Test {
        unsigned int a : 1;
        unsigned int b : 1;
        unsigned int c : 2;
    };

    struct Test test;
    test.a = 0;
    test.b = 1;
    test.c = 2;

    printf("a = %d, b = %d, c = %d\n", test.a, test.b, test.c);
    printf("size of test = %d\n", sizeof(test));

    return 0;
}

由于 test.c 的位域为 2 bit，所以可以表示 2（10），如果位域设为 1 bit 则仅能存储低位：

 struct Test {
    unsigned int a : 1;
    unsigned int b : 1;
    unsigned int c : 1; // 修改位域为 1 bit
};

可以看到编译器提示赋值超过位域可表示的范围了。

如果不使用位域，则该结构体占用 12 个字节

域的长度必须小于其类型的比特大小

超过 32 bit 则报错，并且结构体的大小根据位域的大小不同而变化。

struct Test {
    unsigned int a : 32;
    unsigned int b : 16;
    unsigned int c : 16;
};

内存的基本单位是字节，而位域是字节的一部分，所以位域不能取址。