第四章

函数与程序结构

这一章要讲的内容为函数与程序结构，在之前的学习中，我们已经大量使用过函数，这一章将会更加详细地说明这一方面的内容

由于ANSI标准（C89）对于C的修改，现在C语言已经可以灵活处理一些情况了，比如说允许在声明函数的时候声明参数的类型，而为了使函数的声明与定义相适应，对于函数定义的语法也进行了修改

这里的声明参数也就是指：int getline(char s[]);中的char s[]

并且，如果参数的声明是恰当的，程序甚至可以自动对参数进行适当的强制类型转换

新的预处理器包含一组更完整的条件编译指令（一种通过宏参数创建带引号的字符串的方法），对宏扩展的过程也会更加严格

具体可以看这里 -> 补充内容

函数的基本知识

接下讲讲函数的基本知识，首先我们不妨抛出一个问题

假设我们想要编写一个程序，这个程序的功能是查找输入行内存在的指定的连续的字符，那我们要如何编写这个程序呢？

接下来的这一节都将围绕这个问题展开

引入

让我们明白一些事情，如果我们想实现一个功能，那么很明显我们可以将这些功能全部都写到main函数里面，但是，一般而言更好的做法是将这些功能分散在一个一个的函数里面，而后需要用到那些功能就直接引用这些函数即可

这样的一个好处是如果可以避免各个参数之间相互影响，这也是函数的意义所在

思考

接下来让我们思考如何编写这个程序

首先主要的逻辑便是检测行中是否有这一串字符串，如果匹配的话就返回第一个字符的位置

一开始的逻辑便是建立一个循环，如果当前这个字符串符合对应字符串，则继续检测下去；如果字符串不相同，则选择结束检测，跳转到下一个字符

具体代码

接下来给出核心的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int strindex(const char s[],const char target[]) {
    int i;

    for (i = 0;s[i] != '\0';++i) {
        int n = 0;
        for (int o = i;s[o] == target[n] && target[n] != '\0';++o,++n) {
            ;
        }
        if (target[n] == '\0') {
            return i + 1;
        }
    }
    return -1;
}

接下来开始分析这一块代码，其核心便是嵌套的for循环，第一个for循环的作用是逐个检查字符

而第二个for循环的作用是检查是否有跟目标语句相匹配的字符，如果第一个字符匹配，则继续检查下一个字符是否匹配，如果匹配则继续，如果不是则结束

这个思路有点类似于双指针的思路，指针A用于遍历整个数组，而指针B用于检查第一个字符相同后其他字符是否相同

这样做的好处是第一个指针永远不会被破坏，也就是说检查的顺序是不会被改变的，第一个指针永远按顺序检查，不会跳过任何一个元素

这里的i代表的是符合的第一个字母的位置

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#define MAXLINE 1000
char s[MAXLINE];

char target[] = "ould";

int getline1(char s[],int lim);
int strindex(const char s[],const char target[]);

int main() {
   while (getline1(s,MAXLINE) > 0) {
        int n = strindex(s,target);
        if (n > 0) {
            printf("%d",n);
        }
        else {
            printf("error");
        }
   }
}

int getline1(char s[],int lim) {
    int i,c = 0;

    for (i = 0;--lim > 0 && (c = getchar()) != EOF;++i) {
        s[i] = c;
    }
    return i;
}

int strindex(const char s[],const char target[]) {
    int i;

    for (i = 0;s[i] != '\0';++i) {
        int n = 0;
        for (int o = i;s[o] == target[n] && target[n] != '\0';++o,++n) {
            ;
        }
        if (target[n] == '\0') {
            return i + 1;
        }
    }
    return -1;
}

定义函数

在上面的代码中，我们使用了函数来简化整个程序，通过一定的分割，现在程序变得更加简洁和更容易明白

接下来我们讲讲如何定义一个函数：

1
2
返回值的类型 函数名称(参数声明表)
    声明和语句

在一些情况下，甚至可以省略成这样：

1
dummy(){}

这个函数不执行任何的操作（因为花括号内没有任何的语句），同时不返回任何值（因为花括号内部没有任何可以返回值的语句）

并且，这个函数也没有声明返回值的类型，在这种情况下，返回的值的类型为int

如果想要向调用者返回值，那么只需要通过return语句即可

例如：return 表达式;，结果就是返回表达式

如果return后面没有跟着表达式，那么就不返回值。在一些必要的时候，表达式会加上括号（可选）

返回非整型值的函数

接下来讲讲返回非整型数的函数，由于之前的函数返回的类型均为整型类型，这里返回的类型为非整型值

通过之前对函数定义的结构分析可得：

1
2
返回值的类型 函数名称(参数声明表)
    声明和语句

如果想要返回非整型值的函数（例如double），只需要在前面返回值的类型这一栏写上对应的类型即可

并且，在调用函数的时候如果该函数返回的是非整型值，那么需要在调用函数中显式声明调用的类型

在之前的例子中一直都没有显示声明是因为之前的函数返回的值都是整型数，所以并不需要显示声明（没写默认为int类型）

接下来通过一个例子来说明这一点

例子

这一节我们要写的例子为将字符串转换为浮点数

在这之前我们已经写过一个将字符串转换为整型数的函数（atoi），这次写的函数为atof

首先让我们先思考一下，要怎么去实现这个效果

思路

处理浮点数的难点有一个，就是小数点，如果可以处理好小数点，那么一般来讲其他部分就可以很好的处理完毕

那么要怎么处理呢，有人想到了如果检测到小数点就像Python一样用.append()加上去不就好了

但是.append()是Python有的方法，C里面并没有类似的表达，所以我们就得思考另一种方法了

我们不妨思考一下怎么样可以移动小数点

对，就是使用10的除法，只要把一个数除以10，那么便可以将小数点向左移动一个单位，但是具体要怎么操作呢

我们可以先把除去小数点后的数字写出来，比如说1.001我们可以先写成1001，之后再除以1000即可得到我们想要的数字

那么怎么知道要除多少个呢？我们可以在遇到小数点的时候开始计数，小数点之前不计数，小数点之后计数

这样，便可以写出下面的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
double atof(char s[]) {
    int i = 0,o = 0,power = 1;
    double t = 0;
    int sign = 1;

    for (i = 0;isspace(s[i]);++i) {
        ;
    }
    if (s[i] == '-') {
        sign = -1;
    }
    for (;s[i] != '.'&& s[i] != '\0';++i) {
        t = 10 * t + (s[i] - '0');
    }
    if (s[i] == '.') {
        ++i;
    }
    for (;s[i] != '\0';++i,++o) {
        t = 10 * t + (s[i] - '0');
        power *= 10;
    }
    return sign * t / power;
}

这个函数的原理正是上文所说的思路

外部变量

接下来讲讲外部变量

首先，C语言程序可以看成是一系列外部对象构成，这一系列的外部对象可能是变量，也有可能是函数

由于C语言不支持在一个函数内部定义其他函数，所以说函数本身是 “外部的”

如果一个外部变量拥有一个名字，那么无论在任何地方引用这个外部变量，其指向的地方都是同一个地方

由于这个特性，那么便可以实现各个函数之间通过外部变量来传递值的效果

接下来通过一个计算器的例子来说明这一个点

不过首先让我们科普一个点：逆波兰表示法

逆波兰表示法

什么是逆波兰表示法呢

简单来讲就是把所有的运算符放到数字的后面

例如：(1+2)*(3+4)

那么便可以这样写：1 2 + 3 4 + *

需要注意的是逆波兰表示法不需要圆括号，只需要知道每个运算符需要多少个操作数即可

接下来详细讲一下如何实现逆波兰计算器

首先我们需要声明一个点，在这个计算器里面，将会使用到栈的一些概念，比如说压入栈和弹出栈

接下来讲一下大体的思路

首先，我们需要明确我们输入的内容是什么，类似于10 20 +这种格式

接下来我们要思考如何去储存这些输入的信息

这里使用的是栈。首先先把元素压进栈中，之后想要的时候直接弹出栈即可

难点：将单个结果拼接成一整个数字压入栈

由于我们需要获取输入的数字，所以不可避免需要用到getchar()，而getchar()的特点就是一次只能获取一个字符

这样的话，如果我们输入的内容不是个位数的话，那么我们就没办法将一整个数字压入栈中了

那么要怎么解决这个问题呢？还记得我们之前的一个例子atof()吗，这个例子可以将输入的字符串转换为double类型

所以也就是说，如果我们可以将输入的字符先放进去一个数组中，之后通过atof()便可以转换为我们想要的类型了，在转换之后直接压入栈即可

简单来说是这样的

假设我们输入10，如果直接压入的话，会变成这样：val[0] = 1; val[1] = 0;

这很明显不符合我们的预期，于是我们可以先把这些压入一个临时的数组s，之后将这个数组通过atof进行转换

为什么可以这样？这就有关atof()的实质了，这也就是为什么会先讲atof()的原因

可以发现，通过转换之后返回的数字是一整个数字，而不是类似上面直接压入的情况

之后再将这个数字压入栈即可

难点：压入栈和弹出栈

接下来讲讲压入栈和弹出栈，要实现栈的功能，我们可以用一个数组来表示出栈：val

首先我们思考，如何压入？

稍微思考一下，便可以知道先往栈中填入一个数字，之后将下标递增便可以实现填入栈的效果

这里记得考虑一下边界的情况

1
2
3
4
5
6
7
8
9
10
void push(double s){
    // 我们这里将下标命名为 val_ptr
    // 第一个循环条件为方式溢出的情况出现，VALLINE为栈的最大长度
    if (val_ptr >= VALLINE){
        printf("ERROR:OUT OF VAL(push())");
    }
    else{
        val[val_ptr++] = s;
    }
}

可以看到，这里在压入栈的时候使用了后缀形式的自增运算符，这样可以自动将下标移动到下一个单位，简化了表达

同时因为这个的原因，上面的判断就必须为 >= 否则当等于边界时，下面的自增就会导致边界溢出

接下来是弹出栈

我们需要想想如何弹出，其实弹出栈说白了就是反过来提取出栈中的字符，所以我们可以这么写

1
2
3
4
5
6
7
8
9
double pop(){
    if (val_ptr <= 0){
        // 防止下标过小提取不到
        printf("ERROR:OUT OF VAL(pop())");
    }
    else{
        return val[--val_ptr];
    }
}

这里为什么要选择前缀形式的自减运算符呢？由于前面在压入栈的时候每次压入完都会增加下标，这里减掉才是最后一次压入时的下标

获取输入

接下来是怎么获取输入了，这里我们不妨思考一下一个点，如何让程序知道我们输入的数字是完整的，而不是一半的，换句话说就是如何让程序知道我们输入的数字是123456，而不是切成123和456

这里可以用到前瞻思想，所谓前瞻思想就是提前获取后一个输入来判断当下这个字符要怎么处理

举个例子：

我输入100 200 +

程序会将100的最后一个0压入临时数组s后检测后一个字符 ，由于检测到的结果是空格，不符合是数字的要求，那么程序就可以知道自己获取到的字符是完整的，可以去转换并压入栈了

但是这样就有一个问题，前瞻后的字符要怎么处理呢？这里便可以使用一个专门用于缓存的数组来存储这些字符

另外，在压入获取到的完整数字后，肯定是要回来重新压入其他的数字的（例如200），但是在这里我们还有一个被放在缓存数组中的元素，这个也是需要处理的

综上所述，我们的思路如下：

  1. 先查看缓存数组有没有东西，如果没有，那么则获取数字
  2. 如果缓存数组里面有东西，那么则使用缓存数组里面的东西

那么要怎么确定这个数组里面有没有东西呢？这里可以使用下标来表示有东西

假设下标butf为0，说明当前缓存数组里面没有元素

如果下标为1，说明这里已经存储了一个东西，需要先提取这个缓存的元素后再继续通过getchar()来获取输入

总体的代码如下：

1
2
3
4
5
6
7
8
9
int getch(){
    if (bufp < BUFLINE){
        // 同上，这里如果下标为0说明没有元素，直接获取输入
        return (bufp > 0) ? buf[--bufp] : getchar();
    }
    else{
        printf("元素过多")
    }
}

那么要怎么压入缓存呢？

其实道理跟上面弹出栈和压入栈的道理是差不多的

1
2
3
4
5
6
7
8
void ungetch(double nums){
    if (bufp >= BUFLINE){
        print("元素过多");
    }
    else{
        buf[bufp++] = nums;
    }
}

获取输入并进入临时数组

开始说明如何把获取到的输入转入临时的数组，以便后面转换为一个完整的数字

首先我们需要对一些可能会妨碍我们的东西进行排除，比如说输入的时候一不小心输入了一个空格

所以我们临时数组的第一个元素必须不为空格或退格符

1
2
3
4
while ((s[0] = c = getch()) == ' ' || c = '\t'){
    ;
}
// 这里的作用是当遇到空格的时候就继续存放元素，直到存放的元素不为空格为止

在确保第一个元素不为空格后，就可以开始存放字符了

首先先初始化下标i = 0;

之后开始遍历，压数字到临时数组，但我们需要知道后一个字符是不是不为数字

所以可以这么写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if (isdigit(c)){
    while (isdigit(s[++i] = c = getch())){
        ;
    }
}
if (c == '.'){
    while (isdigit(s[++i] = c = getch())){
        ;
    }
}
s[i] = '\0';
if (c != EOF){
    ungetch(c);
}
return NUMBER;

接下来开始解析这段代码，首先第一步是将小数点之前的所有数字都压进去临时数组

而下一步遇到小数点之后就继续压入小数点后面的数字

最后遇到空格就结算数字，返回标识符NUMBER，将数组丢给atof()处理

下一步继续，第一次由于之前的数字已经将空格存进了缓存数组，所以bufp大于0，先从缓存开始，但由于缓存为空格，所以会被跳过，直接到下一个非空格的字符

接下来的处理方法与第一个数字相同

然后就来将怎么处理符号了，由于符号不是数字，所以可以用isdigit()判断，为了不与小数点混淆，这里还要加上排除小数点的情况

于是还要加上这一段：

1
2
3
if (!isdigit(c) && c != '.'){
    return c;
}

直接返回这个符号，开始进入计算环节

main

接下来就是main的部分了

首先需要确保可以正常获取输入，并且遇到终止符的时候自动结束：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main(){
    double type;
    // 这里的getop指的就是上面的获取输入并存入临时数组
    while ((type = getop(s))){
        switch (type){
            case NUMBER:
                push(atof(s));
                break;
            case '+':
                push(pop() + pop());
                break;
        }
    }
}

这里暂时先实现加法的逻辑，之后减法的也是同理，但是需要注意一个点，由于这里栈弹出的是顶部的值，所以其实是最后压进去的被减数，这里要先用一个临时的变量来储存这个值，之后再用pop()减掉这个值即可

除法也是同理，同时要记得检测除数不为0

最后就是检测出\n输出的部分了，这也是经常遗漏的点

最后完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#define MAXLINE 1000
#define VALLINE 100
#define NUMBER '0'
int getop(char s[]);

// 压入栈
void push(double nums);

// 弹出栈
double pop(void);

char s[MAXLINE];
double val[VALLINE];
int val_ptr = 0;

int main() {
    // type:检测输入的变量
    int type;
    double op;
    int error_flag = 0;

    while ((type = getop(s)) != EOF) {
        switch (type) {
            case NUMBER:
                push(atof(s));
                error_flag = 0;
                // 这里将状态机设置为0的原因是防止遇到为0的时候仍保持为错误的状态，无法正常运行
                break;
            case '+':
                push(pop() + pop());
                break;
            case '-':
                op = pop();
                push(pop() - op);
                break;
            case '*':
                push(pop() * pop());
                break;
            case '/':
               op = pop();
                if (op != 0.0) {
                    push(pop() / op);
                }
                else {
                    printf("除数不能为零\n");
                    error_flag = 1;
                }
                break;
            case '\n':
                if (error_flag == 0) {
                    printf("%.8g\n",pop());
                }
                else {
                    error_flag = 0;
                }
                break;
            default:
                printf("ERROR2");
                break;
        }
    }
    return 0;
}
// 这里压成s后得先用atof转换，atof返回的值为double，所以这里得用double
void push(double nums) {
    if (val_ptr >= VALLINE) {
        printf("ERROR：OUT OF VAL(push)");
    }
    else {
        val[val_ptr++] = nums;
    }
}

double pop(){
    // 这里if判断的时候已经自减一次了，下面就不需要减了
    if (val_ptr <= 0) {
        printf("ERROR：OUT OF VAL(pop)");
        return 0.0;
    }
    else {
        return val[--val_ptr];
    }
}

// 核心部分

int getch();

int ungetch(int c);

int getop(char s[]) {
    int i,c;
    // 跳过空白符
    while ((s[0] = c = getch()) == ' ' || c == '\t') {
        ;
    }
    // 这里的作用是为了处理符号，因为不加这个的话字符串不完整，返回不了正常的字符串
    s[1] = '\0';
    // 处理符号
    i = 0;
    if (!isdigit(c) && c != '.') {
        return c;
    }
    if (isdigit(c)) {
        while (isdigit(s[++i] = c = getch())) {
            ;
        }
    }
    if (c == '.') {
        while (isdigit(s[++i] = c = getch())) {
            ;
        }
    }
    s[i] = '\0';
    if (c != EOF) {
        ungetch(c);
    }
    return NUMBER;
}

int bufp = 0;
#define BUFMAX 100
char buf[BUFMAX];

int getch() {
    if (bufp > BUFMAX) {
        printf("ERROR:OUT OF BUF");
    }
    else {
        return (bufp > 0 ) ? buf[--bufp] : getchar();
    }
}

int ungetch(int c) {
    if (bufp >= BUFMAX) {
        printf("ERROR:TO MANY CHAR");
    }
    else {
        buf[bufp++] = c;
    }
}

作用域规则

接下来讲讲作用域规则

首先第一个点，名字的作用域是这个程序中可以使用这个名字的部分，听起来有点绕，可以举个例子来说明一下

比如说我在一个函数开头声明了一个变量：

1
2
3
4
5
int func(void){
    int val;
    
    return val
}

那么这个变量val的作用域便是在这个函数里面，假如我在不同函数里面声明同样变量名的函数，由于他们的作用域是不同的（都在各自的函数里面），所以这两个变量是不会相互影响的

当然，函数的参数也是这个道理

另外，声明是有先后顺序的

我们拿上面的逆波兰计算器举个例子

假设我们稍微调一下声明的位置

1
2
3
4
5
6
7
8
9
10
11
int main(){

}
int op = 0;
double val[VALLINE];
void push(double s){

}
double pop(void){

}

通过这样修改，main{}便不可以使用下面的op，val这些后声明的东西

那么如果真的要使用该怎么办呢，只需要使用关键字extern即可

声明与定义

接下来讲讲这两者的区别，虽然看起来两者好像差不多，但是实际上是有蛮大差距的

假设我们把这两个语句放到所有函数的外面：

1
2
3
int op = 0;
double val[VALLINE];
// 这里其实也就是上面的样子

那么这两个语句会定义两个外部变量：op和val，并且为其分配存储单元，并且由于其为外部变量的原因，可以作为该源文件中其余部分的声明，也就是说其他部分可以直接使用这些变量而不用另外声明

而下面这两个语句：

1
2
extern int op;
extern double val[];

作用为声明两个外部变量，但请注意，由于只是声明，所以并没有建立变量和分配存储单元

同时观察到可以发现，在这个例子中val并没有声明长度，如果是定义的话，这里毫无疑问会报错，所以这里是声明，并没有分配储存单元

在一个源程序的所有源文件中，一个外部变量只能有一次定义，而其他文件可以使用extern关键字来访问这个变量

另外，外部变量的初始化只能出现在其定义中

拓展内容

这里讲一个拓展的内容，我们在上面的内容中已经知道了一个点，extern关键字用于声明，也就是说，这个关键字并没有分配存储单元（内存）的功能

也正因如此，extern是无法实现初始化的，为什么，因为初始化需要分配存储空间，也就意味着需要分配内存

而上文反复强调，extern仅用于声明，不具备该功能

也就是说，不可以用这个关键字来为变量赋值：

1
extern int s = 1;

这个例子是错误的，因为给整数s赋值，意味着分配了存储单元

头文件

接下来讲讲这方面的部分

我们打算把上面的逆波兰计算器拆分成多个部分，方便管理程序

由于我们这里涉及了多个函数与变量，所以要合理安排各个函数和变量存储的位置

这里我们的决定如下：

把main()放置在main.c当中

把getop()放置在getop.c当中

把push()和pop()放置在stack.c当中

把getch()和ungetch()放置在getch.c当中

把所有的外部变量放置在calc.h中，需要注意的是这里的后缀为 .h，所以在引用的时候需要使用#include指令

如果一个程序规模比较小，那么可以把这些函数中共享的部分放到一个头文件中，如果这个程序比较大，那么可能需要使用更多的头文件分为多个头文件

静态变量

接下来讲讲静态变量，这个里的关键点在于一个关键字static

这个关键字与extern一致，都是为了修饰变量，而这个关键字的作用是将变量的作用域限定在这个文件的剩余部分，也就是说，如果有其他文件想要访问这个被static修饰的变量，是无法成功访问的

那么有什么作用呢？

依旧以上面的逆波兰计算器作为例子：

在上面的例子中，我们使用到了两个函数：getch和ungetch，这两个函数使用了一些外部变量，分别是buf和bufp

如果我们不想让他的访问者（也就是使用这两个函数的getop）使用这两个变量的话，那么我们便是在这两个变量的前边加上static关键字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static int bufp = 0;
static char buf[BUFMAX];

int getch() {
    if (bufp > BUFMAX) {
        printf("ERROR:OUT OF BUF");
    }
    else {
        return (bufp > 0 ) ? buf[--bufp] : getchar();
    }
}

int ungetch(int c) {
    if (bufp >= BUFMAX) {
        printf("ERROR:TO MANY CHAR");
    }
    else {
        buf[bufp++] = c;
    }
}

在经过上面的声明之后，其他文件如果想使用相同的关键字，就不会对这两个关键字产生影响

同样的，这个关键字可以用于函数上面，如果使用这个关键字声明函数，那么也是只有这个文件中才可以使用这个函数

特殊操作：保存函数内部的变量

static关键字还有其他的用法——保留函数内的自由变量，如果你这样操作，那么这个自由变量并不会因为函数的结束而销毁，而是会一直保留直到程序结束(有点像闭包，但很可惜，C里面并没有这个概念)

寄存器变量

接下来讲讲寄存器变量

寄存器变量通过register关键字声明，一般来讲使用这个关键字声明的变量都是需要经常调用的变量

为什么？不妨来介绍一下这个关键字是干什么的

这个关键字的作用是将被修饰的变量放到寄存器中，可以让程序更小，执行速度更快

具体的结构如下：

1
register int a;

如果这个变量a在程序中被频繁使用，那么使用这个关键字可以在一定程度下加快运行速度

至于为什么？可以试着去阅读CSAPP中的有关章节

一些需要注意的点

虽然寄存器变量看起来好像挺好用的，但实际使用中，底部硬件环境的实际情况对于寄存器变量的使用会有一些限制

每个函数中只有很少的一部分变量可以放在寄存器中，并且只允许某些类型的变量

但如果寄存器变量过多，那也没什么，因为编译器可以忽略过量的或者是不支持的寄存器声明

这时候就有人说了：懂了，所以之后把所有变量都修饰为寄存器变量

这并不可以，因为即使说寄存器变量没有被存入寄存器中，他的地址也是不可以被访问的

换句话说，假设有个变量你需要访问他的地址，但是你却用限定词修饰他，那么便会出现问题

补充点

由于K&R的历史遗留问题，现在已经很少使用这个关键字了，为什么？因为大部分编译器都会帮你分配好，而且绝大多数情况做的比你还好

另外，为什么不能取地址，由于寄存器是在CPU里面的，并不是在内存里面

一般数据是存在内存里面的，所以就可以访问，而寄存器变量是存在CPU里面的寄存器，所以没有地址，没办法访问

程序块结构

C语言不同于其他的一些语言，它不允许在函数内部定义函数，但可以在函数内部定义变量

如果你在函数内部定义了一个参数，而函数外面也有一个参数，那么这两者并没有任何关系

例如：

1
2
3
4
5
int x, y;

void func(double x){
    double y;
}

在上面这个例子中，两个变量虽然为同名，但是两者是不相同的

一般而言，应尽量避免出现这种情况

初始化

接下来讲讲这方面的内容

首先先说明各种变量初始化的状态，如果不进行显式初始化的情况下，那么外部变量和静态变量都会被初始化为0

而自动变量和寄存器变量的值则没有任何意义（换句话就是无意义内容）

1
2
3
4
5
6
7
int a;
static b;
register c;

int func(){
    int d;
}

在上面这个例子中，外部变量a和静态变量b都会被初始化为0

而寄存器变量c和自动变量d，则会被赋值成一些没有任何意义的内容

在初始化的时候，你可以在变量名后面加上一个表达式：

1
int a = 1;

上面这个例子就将整数类型的a赋值为1

对于外部变量和静态变量来说，初始化表达式必须为常量表达式，并且只初始化一次（在程序执行前开始初始化）

而对于自动变量和寄存器变量来说，每次进入函数的时候都会进行一次初始化

并且，自动变量和寄存器变量可以不使用常量表达式，也就是说，在表达式中可以出现之前已经出现的值

一般来讲，变量声明的初始化表达式容易被忽略，并且距离可能比较远，所以一般采用显式的赋值语句

数组的初始化

数组的初始化是在声明的后面紧跟一个初始化表达式列表，初始化表达式列表用花括号括起来，每个表达式之间用逗号分割

如果选择省略数组的长度，那么编译器将把花括号的长度定为数组的长度

如果初始化表达式的数量比声明的数组长度短，那么对于外部变量、静态变量和自动变量来说，没有被初始化的元素为0

但如果初始化表达式的个数比数组元素要多，那么则会报错

不能一次将一个初始化表达式指定给多个数组元素，也不能跳过前面的数组元素而直接初始化后面的数组元素

如果为字符数组，则初始化的结构如下：

1
char s[] = "helloworld!";

本质上如下：

1
char s[] = {'h','e','l','l','o','w','o','r','l','d','!','\0'};

需要注意的一点是最后面必须得有一个\0作为结尾

历史遗留问题

由于K&R出版的时候使用的标准为ANSI C（C89）标准，所以便存在一些历史遗留问题

在上面的笔记中我们提到了一点：

也不能跳过前面的数组元素而直接初始化后面的数组元素

但事实上，C99标准补充了一个特性：制定初始化器

这个的作用便是跳过某一项来初始化

具体例子如下：

1
int arr[5] = {[0] = 10,[2] = 30,[4] = 50};

使用这种初始化的方式，数组arr如下

1
[10,0,30,0,50]

这样就成功解决了不能跳过初始化的问题

拓展内容：为什么有些变量没有初始化是0，而有些是无意义

外部变量和静态变量存储的位置是在数据段中，也就是说程序在启动的时候就会自动分配一次内存，而操作系统在加载程序的时候，会将那些没有被初始化的数据段清零，所以结果为0

而自动变量和寄存器变量存放的位置是在栈堆，每次在调用的时候就会临时分配，调用结束就销毁（这也就是为什么函数结束不会保存自动变量的原因）

加上栈堆的内存是复用的，所以就可能会保留上次留下的垃圾数据，所以初始值就是无意义的

递归

接下来讲讲递归的内容

首先，C语言的函数是可以递归调用的，换句话说就是可以在函数里面调用另一个函数，或者自己调用自己

在前面的itoa中有一个问题，那就是生成的数字是反向的，这就导致了必须得有将数组逆转的这个操作

而使用递归可以很好的解决这个问题

1
2
3
4
5
6
7
8
9
10
void printd(int n){
    if (n < 0){
        putchar('-');
        n = -n;
    }
    if (n / 10){
        printd(n / 10);
    }
    putchar(n % 10 + '0');
}

接下来通过一个实际的例子来说明一下：

假设我们输入的数字为-321

那么实际处理的过程如下：

由于输入的数是一个负数，所以先转换成负数，并且输出为321

之后由于除以10不等于0，则执行判断，判断内为一个递归的函数语句

于是传进去的数为32（这里由于类型为整数类型，所以会自动舍弃小数点的内容）

以此类推，直到最后的3 / 10为0，此时不满足判断条件，于是执行下一个语句：putchar()

结束后就退出到上一次的递归，也就是循环体内部，于是就接着执行下一个语句：putchar()

最后，最上面一层函数执行完成，结束函数的调用

也就打印出结果-321了

快速排序

递归的另一个使用场景是快速排序（Quick Sort），接下来将讲一下如何实现

这里使用的快速排序为原地快速排序，非原地的快速排序比较简单，大家可以自行实现

首先，快速排序的核心是将小于基准的元素放到基准的左边，而把大于基准的元素放到基准的右边

那么我们便可以思考，如何将元素放到这个元素该有的地方去

我们不妨将第一个数定为基准，之后创建两个指针，第一个指针称为check_ptr，用于检测元素是否大于基准

第二个指针称为target_ptr，用于找到基准的目标位置

接下来我们思考一下，如何才能找到这个目标位置呢？

找到目标位置，其实也就是让这个指针移动到他该移动到的地方，之后将基准所在的位置和指针所在的位置的那个值进行交换，那么基准就到达他应在的位置了

假设check_ptr所在的位置的元素比基准小，那么也就说明需要在基准所在的位置的左边空出一个位置给这个元素，所以这个时候target_ptr就得移动一个位置，既然移动了一个位置，所以就可以把那个小的元素交换一下位置，使其到达target_ptr的位置上来

为什么要这样，因为在最后基准会与target_ptr的元素交换位置，这样可以保证小的元素一直在基准的左边，也就实现了分区的功能

同理，如果check_ptr所在的位置元素比基准大，也就是说基准的右边需要有一个空间给这个元素，所以target_ptr保持不动即可

因为target_ptr每次移动会使得左边多一个位置，右边相应的少一个位置，除非左边位置需要加一个，否则不需要动target_ptr

实际例子

我们用一个实际的例子来说明这个过程：

现在需要排序的数组为{3,5,2,6,1,4}，为了减少最差情况出现的概率（时间复杂度为O(n$^2$)），我们这里把基准定为中间的值

也就是2（(0 + 5) / 2取整为），那么基准就是2（这里第一个2指的是位置，也就是s[2]，后面的2指的是实际的值）

接下来把基准放到第一个位置，得到数组为{2,5,3,6,1,4}

首先我们令check_ptr为1，对应的值为5（第一个元素是基准自己，所以不用比较）

接下来target_ptr为0，也就是第一个位置

那么开始排序，首先2 < 5，所以target_ptr不动，check_ptr增加1，比较下一个元素

之后3、6同理，直接来到1，由于2 > 1，此时便需要交换

首先先把target_ptr增加一个单位，表示发现有一个数字比基准小，接下来交换位置，得到数组：{2,1,3,6,5,4}

最后4同上面的3和6，到达边界，结束排序，基准与target_ptr的值交换位置，得到基准的目标位置：{1,2,3,6,5,4}

那么此时数组便分成了两部分，一部分比基准小：{1}，一部分比基准大：{3,6,5,4}

由于左边的数组不需要排序，那么就开始排序右边的数组

依旧，先计算出基准：((0+3) / 2取整为1)，那么基准就是6

将基准放到第一个值的位置：{6,3,5,4}

此时target_ptr为0（实际上这里为0只是为了好记，初始值应该与左边界位置是一样的）

check_ptr的值依旧为1，因为不需要检测自己是否大于自己

首先第一个数，6 > 3，那么target_ptr加一，并且与check_ptr交换位置

下一个是6 > 5，依旧，target_ptr加一，并且与check_ptr交换位置

最后一个同理

到达边界，target_ptr一共移动了三次，所以交换元素，得到数组为：{4,3,5}

同理，找基准，这里基准为3，所以交换位置得到：{3,4,5}

依旧比较，发现都小于，此时target_ptr的位置就在左边界，所以不用动

最后剩{4,5}，依旧选择交换，得到{5,4}

由于5 > 4，所以target_ptr加一，给小的数留出位置，同时与check_ptr交换位置，这里因为两个指针的位置都是相等的，变成了自己与自己交换，所以数组依旧为{5,4}

check_ptr到达边界，所以结束，基准与target_ptr的位置交换，得到{4,5}

这样排序就完成了：{1,2,3,4,5,6}

那么要怎么写呢？首先我们要明白上面的一些主要的操作，也就是交换位置，用位操作数也可以，这里选了临时变量的方案：

1
2
3
4
5
void swap(int v[], int i, int j) {
    int temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

其中i和j为target_ptr或者check_ptr都无所谓，因为本质为位置交换，谁是谁只会影响临时变量的值

在完成了这个之后，我们便可以开始写函数的主要内容了：

此处省略了大部分的内容，包括函数声明，main()等内容

1
2
3
void qsort(int v[], int left, int right) {
    // left和right是数组的左右边界
}

首先第一个点，我们得思考什么时候就不进行排序，也就是当数组的元素少于两个的时候就可以不排序了：

1
2
3
4
5
6
void qsort(int v[], int left, int right) {
    if(left >= right){
        return;
        // 返回值类型写的是void，所以直接这样填即可
    }
}

按照上面的操作，我们需要把基准移动到数组最前面的位置：

1
2
3
4
5
6
void qsort(int v[], int left, int right) {
    if (left >= right){
        return;
    }
    swap(v, left, (left + right) / 2);
}

接下来是比较元素并替换，上面也提到过了，如果check_ptr到达右边界，那么就可以结束

比较值的话，如果基准比check_ptr指着的值要大，那么便触发交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void qsort(int v[], int left, int right) {
    int check_ptr,target_ptr;

    if (left >= right){
        return;
    }
    swap(v, left, (left + right) / 2);
    target_ptr = left;
    for (check_ptr = left + 1; check_ptr <= right;++check_ptr){
        if (v[check_ptr] < v[left]){
            swap(v,++target_ptr,check_ptr);
        }
    }
}

完成后就是把基准移到正确的位置上了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void qsort(int v[], int left, int right) {
    int check_ptr,target_ptr;

    if (left >= right){
        return;
    }
    swap(v, left, (left + right) / 2);
    target_ptr = left;
    for (check_ptr = left + 1; check_ptr <= right;++check_ptr){
        if (v[check_ptr] < v[left]){
            swap(v,++target_ptr,check_ptr);
        }
    }
    swap(v, left,target_ptr);
}

完成后，就要对基准两边的数组进行排序了，那要怎么操作呢？还记得这一节叫什么吗，对！就是使用递归

那么要怎么使用呢？其实很简单，弄清楚边界即可

左边的数组右边界为基准所在位置减去一，右边的左边界为基准所在位置加一，那么怎么表示基准所在的位置呢？

还记得最后执行了什么操作吗？基准的位置其实也就是target_ptr

所以最后代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void qsort(int v[], int left, int right) {
    int check_ptr,target_ptr;

    if (left >= right){
        return;
    }
    swap(v, left, (left + right) / 2);
    target_ptr = left;
    for (check_ptr = left + 1; check_ptr <= right;++check_ptr){
        if (v[check_ptr] < v[left]){
            swap(v,++target_ptr,check_ptr);
        }
    }
    swap(v, left,target_ptr);
    qsort(v, left,target_ptr - 1);
    qsort(v, target_ptr + 1, right);
}

至此，我们便完成了快速排序

此处代码来自K&R原文

C预处理器

C语言通过预处理器实现了一些有趣的功能

从概念上讲，预处理器是编译的时候执行的第一个步骤。两个最常用的预处理器指令是#include和#define指令

接下来会依次介绍

文件包含

文件包含指令，也就是#include指令，这个指令的作用是，当使用这个语句的时候，使用的那一行便会被替换成文件内的内容

例如

1
#include <stdio.h>

那么这一行就会被替换为stdio.h文件内的内容

接下来讲讲使用方法，#include指令有两种使用方式：

1
#include <文件名>

和

1
#include "文件名"

这两种虽然都可以实现替换的功能，但具体的使用方法是不同的

第一种会通过相应的规则查找文件，这个规则同具体的实现有关

而第二种使用引号的就比较简单了，会在源文件所在位置查找文件，而如果查找不到文件，那么则会根据第一种的查找方法一样，使用相应的规则查找该文件

需要说明的一点是，使用#include包含的文件本身也可以有#include语句

那么这个语句有什么作用呢？假设我们有大量的#define语句，那么便可以将这些语句全部放到一个文件中后使用#include指令来引用

并且，我们可以在多个文件中使用这个命令，这样，就可以使得所有的文件有了相同的定义和变量声明，减少了错误的发生

关于“相应的规则”

在K&R里面有提到这么一句话：“则将根据相应的规则查找该文件”

这里的相应的规则是什么？接下来来简单介绍一下

首先，如果为尖括号的文件名的话，那么编译器会先去查找系统目录，看看是否有这个头文件，如果没有的话则会跑去环境变量指定的目录查找（这里不涉及使用参数的情况），如果都找不到，那么会直接报错

而引号类型的只是在尖括号类型的前面多了一步——查找源文件所在位置是否有该文件，如果找不到那么则会用尖括号的查找方式去查找

补充内容：头文件守卫

接下来将补充一个十分重要的点

首先，如果你在一个文件里面引用了另一个文件，还有一个写满了声明的头文件，而你引用的那另一个文件里面也有那个写满了声明的头文件

那会发生什么事情呢？

很遗憾，这样做会导致报错

为什么这样会报错？因为多次包含同一个头文件会导致重定义错误

那要怎么解决这个问题呢？很简单，只需要在那个头文件里面加上这么一个结构即可

1
2
3
4
#ifndef GUARD
#define GUARD
// 这里放声明
#endif

这样，就可以避免以上出现的问题

（不过现在有些IDE在创建头文件的时候会自动帮你加上头文件守卫，比如CLion）

宏替换

接下来讲讲宏替换的内容，首先宏替换所需要用到的命令为：#define

由于前文已经在多个地方讲到宏定义了，这里会讲的比较详细一点

首先宏定义的格式如下：

1
#define 名字 替换文本

宏替换的本质就是在编译一开始，把文件内所有与宏替换文本一致的名字全部换成后面的替换文本

一般来讲#define语句占一行，但如果需要多行的话，需要在换行的末尾加上一个\做到连续的效果

不过，替换文本不能对引号内部的文本进行替换

1
2
3
4
5
#define YES 1

int main(){
    printf("YES");
}

上面这种格式并不会触发文本替换，这一点需要注意

另外，文本替换并不局限于文本，也可以是语句：

1
#define FOREVER for(;;)

上面就定义了一个无限循环的语句

另外，#define是可以带参数的：

1
#define MAX(A,B) ((A) > (B) ? (A) : (B))

之后便可以在正文部分使用MAX(10,20)来比较两个数字的大小了

如果我们试着观察上面的MAX定义，可以发现一个点

如果两个参数不是具体的数字，而是表达式，则在使用的时候会计算两次：

1
2
MAX(a + b,c + d)
// 等价于：((a + b) > (c + d) ? (a + b) : (c + d))

那么，如果输入的是自增运算符呢？

结果是直接报错

为什么会出现这种情况，其实之前在讲自增运算符的时候也讲到了，在一个语句里面对同个元素多次使用自增运算符会导致未定义行为（UB）的情况出现

（此处引用了第二章的笔记）
什么是未定义行为呢？在C语言中，如果你在同个语句对单个变量进行多次修改，那么这个行为就是未定义的

也就是说C语言没有规定编译器要怎么做，不同的编译器对同一个未定义的语句可能有不同的结果

比如说上面这个例子：编译器可能先计算to[i++]，之后再计算s[i++]；也有可能反过来，先计算s[i++]，之后再计算to[i++]

另外，由于你不知道之后输入的东西到底是什么，所以为了保证运算顺序的正确，在宏定义的时候必须对参数加上括号来保证运算顺序的正确

在系统的头文件中，也可以发现一些宏

例如在stdio.h中，获取输入和执行输出的getchar()和putchar()便是宏

这样就可以避免处理字符调用函数所需的运行时开销

当然，你也可以取消宏定义，只需要使用#undef可以取消掉宏定义

由于形式参数不能用带引号的字符串替换，所以在模仿类似printf语句的时候会有一些困难

但是，如果在替换文本的参数中加上 #，那么在替换的时候会自动加上引号：

1
2
3
4
5
6
7
#define EXAMPLE(val) printf(#val" = %d\n",val)

int main(){
    EXAMPLE(20);
    // 等价于：printf("20" "= %d\n")
    // 其实也就是：printf("20 = 20\n")
}

在实际的参数中，每个双引号会被替换为\，而反斜杠会被替换为\，所以是个合法的字符串常量

还有另外一个预处理器运算符是##，如果两个参数用这个运算符连接起来，那么在实际中将会把前后两个参数连接起来

1
2
3
#define copy(fitst,last) first ## last

// 实际的结果为 firstlast

这个运算符的用法在于批量创建函数名

1
2
3
4
5
6
7
8
9
10
11
#define DEFINE_FUNC(type)\
void print_##type(type value){\
    printf("%"#type"\n",type);\
}

DEFINE_FUNC(int);

int main(){
    print_int(20);
    // 输出：20
}

条件包含

接下来讲讲条件包含，使用这个语句可以对预处理进行控制，换句话说你可以自己决定那些预处理要执行，那些不要执行

首先是#if语句

与正常的if语句一样，这里的#if同样是检测条件是否不满足为0，如果条件不为0，则执行下面的语句，否则就直接跳过

对应的，还有#else和#elif语句

上文的头文件守卫可以这么写：

1
2
3
4
#if !define(TEST)
#define TEST
// 对应的语句
#endif

两个我们经常用到的语句#ifdef和#ifndef便可以更加简洁的表示出这个功能：

1
2
3
4
#ifndef TEST
#define TEST
// 对应的语句
#endif