猪脚说第八期

有关期中考试的强调

注意事项

• 期中考试时间为4月27日晚19:00-21:00，考试时间为2小时。
• 重视期中考试前的模拟考试，到时候助教会强调与提醒一些内容，请一定牢记。
• 编程题提交后可看到评测结果，如“完全正确”、“输出错误”等，但没有详细错误信息。
• 若提交后，发现并不是所有数据点都全对，并且judge平台显示很多warning，请一定逐条仔细查看，尽量都修改一下。有些时候，一道题的错因就在这些warning里，且一般主要问题都集中在自定义的非void型函数缺少返回值。
• 选填题目不确定的，就用本地IDE运行一下查看结果，如果是概念题不确定的可以暂时放一放，以编程题为主，毕竟编程题的分值很重。
• 请一定带上草稿纸、笔、大一上程设教材、大一下数据结构教材！！！到时候如果需要查询ASCII码表等内容时，可以直接在教材附录查询，不能上网！！！不能上网！！！不能上网！！！
• 对于编程题（共两道）：
  • 千万不要题目没读懂就急着敲代码！！！
  • 在题目中，尤其是红字标注的地方或者题面自身出现的注意事项，一定要牢记，避免写代码时忘记这些易错点，导致后续排坑浪费掉很多时间（相信大家都有过因为文件名写错或者输入输出方式写错而de好几个小时bug、浪费好几个小时的时间的经历吧）。
  • 建议大家读完题目之后，先简要思考一下该用什么数据结构，是数组？还是链表？链表是单向的？还是双向的？需不需要使用循环链表？
  • 大家考试时可以多在草稿纸上写一写，选填题目可以在草稿纸上推一推，编程题目可以在草稿纸上画一画流程图，这样也可以缓解考场上的紧张情绪。很多时候，题目的逻辑与解题思路清楚了，写代码也就不会东一句西一句。

复习要点

• 考试主要内容对应前三次作业范围，且不涉及文件输入输出，内容不多，重点在于字符串的处理以及线性表（包括数组和链表）。
• 考试题目类型为：选填共10道（每道0.5分）、编程题2道（第一题15分，第二题10分），共30分，考试得分将全额计入课程总评。
• 前三次作业的选填还有不太懂的地方抓紧时间弄懂，可以和同学讨论，也可以来问助教。
• 编程题一定是重点！！上机作业里的编程题一定要理解，只有对于每一种操作熟练掌握，才能提高代码的一次性正确率。我们也为大家提供了题解，题解中封装了不少常用操作，希望大家抽时间看看。
• 老师的授课ppt也是非常重要的，上面有很多基础概念，可以帮助大家做选填题；ppt上也有一些例题的代码，其中的思路和操作也值得大家学习。
• 平时我们发的资料与老师的授课ppt都汇总在北航云盘里了，我们也在bhpan里共享给了大家，有需要自取：
• https://bhpan.buaa.edu.cn:443/link/AE82D268627E33234B178D5416D2AF03

关于字符串

• 字符串的处理问题在前三次作业中从未缺席，同时也是我们一直在上机时或者课程群里重点强调的问题，我们针对字符串容易出现的bug也出了好多次猪脚说，也希望引起大家的重视。
• 作业中有关字符串处理的较复杂的编程题，一定要再看看，加深理解，以便在考场上尽快解决相关问题。
• 如果有些同学在考前想要做额外的题练练手，可以参考之前助教说给出的补充习题。
• 注意strcpy、strcat等函数的使用条件（包括内存区域不能重叠、源字符串必须以'\0'结尾等），如果考试时对于一些字符串处理库函数的细节不太清楚，可查阅《C程序设计引导》的第125页（如果大家还没有把这本书扔掉的话）。
• 注意**字符串结尾一定要有终止符'\0'**，或者在处理完字符串后，自己手动在末尾加上'\0'，或者初始化将字符输出全部赋值为'\0'。
• 再次强调\r\n的问题，有不少同学到现在还是会在这个点上犯错，字符串读入时一定要严谨处理，**实在不行就老老实实用gets()**，具体可见课程群聊天记录。
• 多总结一下平时在自己身上发生的或者向助教提问时助教提醒你的问题，在考试时尽量避免犯相同的错误。

关于线性表

• 前三次作业中出现的涉及链表的编程题，大家一定要理解并掌握！！！
• 链表的相关操作也是期中考试的考查重点，对于链表的基本操作可以再去复习一下。
• 不同的链表结构，例如双向链表、循环链表，它们的节点插入、删除等基本操作，在课件里也有，大家如果还有不清楚的地方，可以再把ppt的相关内容过一遍。
• 在考场上，如果不确定自己写的代码中的链表操作的正确性，不清楚应该先赋值哪个指针、后赋值哪个指针，建议在草稿纸上画图推算，通过画图来模拟链表的节点插入、删除等操作，可以使思路更清晰。
• 我们写的第三次作业题解中，第二题给出了链表操作的示例代码，里面的一些片段或许可以直接封装使用。
• 再次强调，链表操作涉及指针时，一定要注意是不是访问了空指针！！！

常见编译器警告与错误

• SIGSEGV：指针使用错误（使用之前一定要初始化以及判断是否访问到了空指针）、栈越界（递归调用时需要注意避免无限递归的存在）、数组访问越界等原因导致。
• SIGABRT：对一个指针执行连续free操作、free错误的地址、堆越界等原因导致。
• SIGFPE：算术错误，一般是因为在运算时发生了除以0的运算。
• Unused Variables：这个警告无关紧要，可以忽略。
• Function return with no value in non-void functions：这个问题一定要避免并解决！！！
• Uninitialized variables：一定要改！！！

一个奇怪的问题

同学们在 judge 平台上提交代码的时候，有没有好奇过这个细节？

诚然，我们只需要提交 .c 文件即可，想必把这个文件装入文件夹，将文件夹压缩成压缩包交上去，也是可行的。但是，显然不会有人多此一举，交一个仅含有一个文件的压缩包上去。所以很明显，压缩包对应着的，应该是含有多个文件的一个项目（Project）。

这时候问题就来了，C 语言项目长什么样呢？或许里面有多个 .c 文件，那还应该有什么呢？我们只实操过单个源代码文件的编译运行，多份源代码文件又要注意什么呢？如果我们把一个程序拆分成多个模块，编译器又要凭借什么把它们组织在一起呢？

我们不妨首先尝试探索，一份 main.c 文件应该怎么从逻辑上拆分成各个子模块。

• 头文件包含，这是我们调用一些函数所必须的，如printf malloc。

• 通过#define定义一些符号常量，有助于简化代码。

• 声明结构体、联合等自定义的复合数据类型。

• 声明函数原型。

  特别注意，函数原型的声明只是给编译器看的，只是为了让它识别“有这样一个函数”。编译过程顺序扫描文本，当编译器明白了有这么一个函数之后，在main中调用这个函数就是合法的，调用这个函数后具体怎么执行，靠的是main后面的函数定义，这就无需关心；不写函数原型声明而直接把函数定义在main前面是可行的，这样编译器在读到函数的时候不仅知道了函数的存在性，也知道了它的执行步骤，后续在main中调用自然是可以的，只是不写函数原型声明，直接把函数定义放在main前面不符合编程规范。

• 全局变量的定义。

• main函数。这是程序执行的入口。

• 其他函数的实现。

通过简单的思考我们可以发现，如果以函数为单位划分程序，则我们有如下两条原则

• main函数应该单独拎出来考虑，因为它体现着程序核心的逻辑，程序的运行从它开始、从它结束。
• 其他函数应该按照功能分组，如运算类函数一组，字符串操作类函数一组，链表操作类函数一组。

以往，我们把所有东西放在一个文件里，大家坦诚相见，在文件开头声明的struct A，可以被每一个函数知道是什么东西。试想如果按照上述的分组思路，把各个模块放进不同的文件里，struct A又要怎么处理呢？为了让每一个文件里的函数都知道struct A，难道要在每个文件的开头都声明一遍吗？

另一方面，我们考虑变量。局部变量，常见的有标记当前位置的pos，表示数据组数的n，用于循环的i和在程序的局部表示某种状态的flag等。事实上，这些变量的作用是服务于函数自身的实现，一个函数的局部变量和另一个函数的局部变量并无关联。全局变量则应该在程序全局共享，因为它们有可能是全局都要访问的某些核心数据结构 —— 比如，在一款音乐播放软件中，歌曲的下载、收藏和历史记录等都会涉及用户账户信息，则这个信息应该处在全局的位置被共享。问题又来了，如果一个程序由多个文件组成，一个全局变量应该定义在哪里呢？

以上描述主要想说明，从一个源代码文件过渡到多文件的项目是有必要且可行的，但存在很多困难，主要有两点：**(1) 如何对原有代码进行拆分；(2) 如何在各个文件间共享必要的信息**。

另一个奇怪的问题

悬赏

在你的计算机设备上找到printf函数的源代码，最先找到者请吃一学期疯狂星期四。

当然，在找之前，不妨先看看下面的文字。

首先给出printf的函数原型。

int printf(const char *fmt, ...);

这里的fmt参数就是格式串，后面的...是 C 的语法，表示可变参数列表（以后有机会可以介绍）。我们在fmt中指定要输出的内容，如果是普通字符则直接输出，如果是以%开头的某些特殊内容，则会到后面的参数中寻找并替换，当然也支持保留小数位数、左右对齐等更细节的格式。

同学们心安理得地用了这么久printf，有没有考虑过它是怎么实现的呢？似乎只要#include <stdio.h>，就能随心所欲地调用它了。然而，正因为它被调用得如此频繁，作为一个 C 库函数，它早已被打包成共享库，存在于系统文件之中，它的具体的 C 语言代码，是不在系统之中的。

共享库文件是一个二进制文件，其中包含着某些可运行但不可单独运行的代码。当我们编译出hello_world.exe 可执行文件并运行时，运行到printf("Helllo World\n");这行代码，系统会跳转去执行共享库中属于printf函数的代码，从而实现了库函数的调用。

那么，编译器在编译我们的 hello_world.c 文件时，又是如何知道printf的存在呢？答案其实就在<stdio.h>中，这个头文件（header）里，包含了printf的原型声明；编译器在预处理阶段，会在#include <stdio.h>这一句预处理指令的地方，原封不动地插入<stdio.h>的全部内容，显然这些内容中包括printf的声明，以及其他我们未用到的函数声明。于是，我们在main的前面有了printf函数的原型，在程序中也就可以调用了。

以前我们提到，**FILE类型是一个结构体，这个结构体及其别名的声明，同样位于<stdio.h>中**，于是我们也可以在包含了这个头文件之后，使用FILE类型。

<stdio.h>局部

<stdlib.h>局部

<string.h>局部

头文件

宏的定义与类型声明

有了这样的观念，我们就可以尝试编写自己的头文件了。当然，如果要使用头文件，我们最好在 IDE 中先新建一个项目，这个项目一般会默认有一个 main.c，然后我们在同一个目录（即文件夹，以后统称目录）下新建一个myheader.h。

实际上，头文件的后缀名是不重要的。C 的传统风格的头文件都是 .h 后缀，C++ 则另起炉灶。在 C++ 中，原有的 C 头文件基本兼容，名字都以 c 打头且没有后缀，如 <cstdio> <cstdlib> <cstring>，当然包含原有的 C 头文件也可以，因为它们都在系统之中。C++ 也有自己独有的头文件，如 <queue> <stack> <algorithm> <iostream>等。

// myheader.h

#include <stdio.h> 
  // 在自己的头文件中可以包含其他头文件
  // 这里我们要使用 FILE 类型，所以要包含 stdio.h

#define MAX_LEN 32
  // 在自己的头文件中可以定义宏
typedef struct {
    FILE *fp;
    int cnt;
    char content[MAX_LEN];
} Word;
  // 在自己的头文件中可以声明自定义复合数据类型

这样，如果我们要在 main.c 中使用MAX_LEN宏或Word类型，只需要在 main.c 开头包含myheader.h头文件即可：#include "myheader.h"。

头文件名可以用<>也可以用""括起来，区别在于：尖括号一般用于系统的头文件，在查找时会首先到系统的库中查找，找不到时才在项目目录中查找；双引号一般用于自定义头文件，会优先在当前项目中查找。

函数声明与实现

我们也可以在头文件中声明函数原型，在其他的源代码文件中实现该函数。

// 在 myheader.h 中插入
Word *create_word(char c);
// 这个函数创建一个 Word 结构体并返回其指针
// 将其中的文件指针设置为 NULL，cnt 设置为 0
// 将 content 数组填满字符 c

// 在项目中新建 myheader.c 源代码文件
#include "myheader.h" // 我们会用到其中的 Word 类型、MAX_LEN 宏
#include <stdlib.h>   // 我们在实现 create_word 时会用到 malloc 函数
Word *create_word(char c) {
    Word *p = (Word*)malloc(sizeof(Word));
    if (p == NULL) return NULL; // malloc 出错返回 NULL
    p->fp = NULL;
    p->cnt = 0;
    for (int i = 0; i < MAX_LEN; i++) p->content[i] = c;
    return p;
}

在 main.c 中可以测试，在项目中执行编译会把多个源代码文件联合起来编译，但只能有一个函数叫做main，它仍是程序的入口。

// main.c
#include <stdio.h>
#include "myheader.h"
int main() {
    Word *word = create_word('a');
    if (word != NULL) {
        word->content[MAX_LEN - 1] = '\0'; // 使之变成一个字符串
        if (word->fp == NULL) printf("word->fp is NULL\n");
        if (word->cnt == 0) printf("word->cnt is 0\n");
        printf("word->content: %s\n", word->content);
    }
    return 0;
}

全局变量

我们知道，在多数情况下，同一个变量是不能定义多次的，如

// main.c
int a;     // 全局变量 a
// int a;  // 再次定义全局的 a 就会出错
void main()
{
    int i = 0;  // 局部变量
    int a = 10; // 定义局部的 a 可以，此时无法在 main 中访问全局的 a
    // int i;   // 再次定义局部的 i 就会出错
    for (int i =0; i < 10; i++);
      // 这个 i 属于 for 循环，仅在循环内有效，这个 i 会屏蔽掉 main 的局部的 i
}

头文件解决全局变量问题的思路是，在头文件中声明某个全局变量的存在，在某一个源代码文件中的全局的位置定义该全局变量，在所有用到该全局变量的源代码文件中都应先包含头文件。例如

// myheader.h 中插入
extern int global;
// extern 关键字告诉编译器，我的程序中会有一个全局变量
// 它的类型是 int，名字叫 global
// 显然 extern 只是声明全局变量的存在，不能在此时初始化

// myheader.c 文件第一行插入
int global = 100;
// 在某一处定义了该全局变量

// main.c 的 main 函数中访问该全局变量
printf("global = %d\n", global);

静态变量和函数

考虑这样一个情形，现在需要开发一个银行管理系统，其中，存款、取款、查看余额等函数已经写好，实现在 bank.c 中，并且声明在 bank.h 中：

// bank.h
“账户”结构体声明
存款函数声明
取款函数声明
查看余额函数声明
添加账户函数声明
删除账号函数声明
// bank.c
存款函数实现
取款函数实现
查看余额函数实现
添加账户函数实现
删除账号函数实现

现在我们请人为我们在 main.c 中实现这个系统的图形界面，如点击某个按钮就可以查看余额等。试想，我们应该仅把 bank.h 文件交给对方，这样对方就能知道如何调用函数了。多个银行客户的信息应当存放在一个“账户”类型的结构体数组中，如果由对方在 main.c 中创建这个全局变量，则可以在 main.c 中任意地访问这个数组，直接操作银行客户的数据，这是我们不可接受的。

实际上，如果把这个数组当成全局变量，就必然会存在上述问题。我们希望在 bank.c 中的每一个函数内，都能访问该数组，但又不希望它被 main.c 访问，因为 main.c 只需要调用 bank.c 的函数并接收其返回值即可。这就需要 bank.c 中有一个仅属于该文件的、并且是全局性质的变量。

用static关键字修饰全局变量，则这个变量的全局性仅限于某一个文件。具体来说，在上述例子中，我们可以在 bank.c 的开头定义

static Account accounts[100];

这样，这个数组可以被 bank.c 中的每一个函数访问，但不能被其他文件的函数访问。我们可以把 bank.c 单独编译封装为一个模块，未来在 main.c 编写完毕后与之一同编译产生最终的可执行文件。main.c 请第三方人员编写，它们只需要根据头文件中的函数原型进行调用，而无法操作到客户账户的数据。

static关键字也可以用来修饰函数，被它修饰的函数仅在本文件内有效。

例如，我们之前实现过可变长数组的封装，其中的增删改查等函数是由用户调用的，但是，数组的生长函数应该由“增”函数自动调用，而不应该开放给用户，此时在 array.c 中就可以这么写

static void array_grow(array_t *arr) {
    // do something
}
void array_addtail(array_t *arr, int var) {
    // call array_grow
}

再比如，我们要用栈实现一个计算器并封装，我们希望调用方式是

printf("result: %d\n", calculate("3 + 4 * (5 / 2) - 1"));

则我们可以在 calculator.c 中组织

static int stack[105];
    // 静态的全局变量，仅在此文件中可以访问，main 不能直接操作它
static int top = -1;
    // 静态的全局变量，仅在此文件中可以访问，main 不能直接操作它

int calculate(const char *s) { 
    /* 计算表达式 s 的结果 */ 
    // 这个函数是给用户调用的
}

static int priority(char op) {
    /* 判断运算符优先级*/
    // 仅在本文件内有效，由 calculate 调用，以下四个函数同理
}
static int add(int a, int b) { return a + b; }
static int sub(int a, int b) { return a - b; }
static int mul(int a, int b) { return a * b; }
static int div(int a, int b) { return a / b; }

头文件保护符

声明重复多次是可以的，但是定义则不可以。很多情况下，一个头文件会在一个项目的多个文件中被重复包含多次，这很可能产生错误。事实上，考虑到#include的展开文本的本质，我们只希望头文件的内容在项目中仅被展开一次，这就需要用到头文件保护符。

#ifndef _NAME_H_ // 如果未定义标识符 _NAME_H_
#define _NAME_H_ // 则定义标识符 _NAME_H_
// 头文件正文
#endif           // 结束上述 if 判断
/* 三条预处理指令的逻辑:
  if not define xx {
      define xx
      extend contents
  } */

首先说明，这里的_NAME_H_只是惯用的写法，例如在<string.h>中就会用到_STRING_H_这个标识符。以上三条指令的直接翻译已经注释，当我们在项目中重复包含一个头文件时，预处理阶段第一次碰到这个头文件，发现_NAME_H_是未定义的（显然这么个奇奇怪怪的符号不太可能在之前被就你#define过），则判断条件成立，执行第二句#define语句，也就定义了这个符号，随后展开了头文件正文，结束条件判断。此后如果再碰到需要包含这个头文件的地方，会先判断_NAME_H_是否定义，结果是已经定义过了，则直接跳到#endif处，而不会再展开了。

头文件保护符加在头文件的头尾，是推荐使用的例行编码习惯。

实例演示

实现一个银行存款和查看余额模拟。项目中有 test.c(测试)，bank.c，bank.h 三个文件。

// bank.h
#ifndef _BANK_H_                // 头文件保护符，这是例行写法
#define _BANK_H_

#define ID_LENGTH 10  // 定义账户 ID 号最大长度
#define CNT_MAX 100   // 定义最多有 100 个账户

typedef struct {         // 声明账户类型
    char id[ID_LENGTH];  // 账户 ID 号
    int balance;         // 账户余额
} Account;

void add_account(char *id);     // 添加新账户
void save(char *id, int money); // 往账户 id 中存款 money
Account get_idx(int idx);       // 获取下标为 idx 的账户
int get_num();                  // 获取账户数量

#endif

// bank.c
#include "bank.h"
#include <string.h> // 要用到 strcmp 查找账户

static Account accounts[CNT_MAX]; // 静态的 Account 数组，仅本文件访问
static int cnt = 0;               // 账户数量计数

void add_account(char *id) {      // 在数组尾部添加元素
    strcpy(accounts[cnt].id, id);
    accounts[cnt].balance = 0;    // 初始化余额为 0
    cnt++;
}
void save(char *id, int money) {
    for (int i = 0; i < cnt; i++) {
        if (strcmp(id, accounts[i].id) == 0) { // 找到账户
            accounts[i].balance += money;      // 存款
            break;
        }
    }
}
Account get_idx(int idx) {
    return accounts[idx];
}
int get_num() {
    return cnt;
}

// test.c
#include <stdio.h>
#include "bank.h"

int main()
{
    // 【注意】main 中不能直接访问 bank.c 的那个 accounts
    //  请不要忽视这个权限问题，这是具有非凡意义的一个特性
    
    add_account("0001");
    add_account("0002");
    add_account("0003");
    save("0001", 10000);
    save("0001", 5000);
    save("0003", 4500);
    for (int i = 0; i < get_num(); i++) {
        Account a = get_idx(i);
        printf("[%s] balance: %d\n", a.id, a.balance);
    }
    return 0;
}

Author: diandian, Riccardo