一生一芯学习记录（E 阶段）（一） ​

在学习完如何用门电路搭建出CPU之后，在E阶段将会学习一些有关现代处理器设计所需要的知识，包括C语言和Verilog硬件描述语言以及Linux系统等等。由于本阶段内容很多，将会分成多个记录。

E1 C语言程序设计 ​

在本章中，需要学习Linux C编程一站式学习中的第1~9章，第11~16章，第21章，第23~25章，以及第26章第1节。在这一章中，各小节编号按照书中的编号，因此会出现编号不连续的情况。

第1章：程序的基本概念 ​

一、程序和编程语言 ​

程序由一系列指令组成，指令是指示计算机做某种运算的命令，通常包括以下几类：

• 输入：从键盘、文件或者其它设备获取数据。
• 输出：把数据显示到屏幕，或者存入一个文件，或者发送到其他设备。
• 基本运算：执行最基本的数学运算（加减乘除）和数据存取。
• 测试和分支：测试某个条件，然后根据不同的测试结果执行不同的后续指令。
• 循环：重复执行一系列操作。

编写程序可以说就是这样一个过程：把复杂的任务分解成子任务，把子任务再分解成更简单的任务，层层分解，直到最后简单得可以用以上指令来完成。

习题1：解释执行的语言相比编译执行的语言有什么优缺点？

解释执行的语言由于需要按照每行代码解释执行，效率相比编译执行的语言较低，但是解释执行的语言不需要将代码翻译成机器指令后再运行，因此具有良好的平台无关性。

三、程序的调试 ​

区分清楚程序中的Bug分为哪几类：

• 编译时错误：编译器只能翻译语法正确的程序，否则将编译失败，无法生成可执行文件。
• 运行时错误：编译器检查不出来这类错误，仍然可以生成可执行文件，但在运行时会出错而导致程序崩溃。
• 逻辑错误和语义错误

第2章：常量、变量和表达式 ​

一、继续Hello World ​

C标准规定的转义字符

转义序列	对应字符
\'	单引号’
\"	双引号"
\?	问号?
\\	反斜线\
\a	响铃
\b	退格
\f	分页符
\n	换行
\r	回车
\t	水平制表符
\v	垂直制表符

二、常量 ​

常量是程序中最基本的元素，有字符常量、整数常量、浮点数常量和枚举常量。

字符常量要用单引号括起来，例如'}'，注意单引号只能括一个字符而不能像双引号那样括一串字符

printf中的这个字符串称为格式化字符串，它规定了后面几个数据以何种格式插入到这个字符串中，%号后面加个字母c、d、f在printf中分别解释成字符型、整型和浮点型的转换说明，分别用后面的三个常量来替换它们，也就是说它们只是在格式化字符串中占个位置，并不出现在最终的打印结果中，这种用法通常叫做占位符。

习题1：总结前面介绍的转义序列的规律，想想在printf的格式化字符串中怎么表示一个%字符？写个小程序试验一下。

两种写法，一种是直接将%当作格式化字符串的一部分，另一种则是将%当作一个字符型的常量，利用占位符进行输出。

printf("输出一个%号：%c\n",'%');
printf("输出一个%号：%");

三、变量 ​

给变量起名有一定限制，C语言规定必须以字母或下划线_开头，后面可以跟若干字母、数字、下划线，但不能有其它字符。其实这个规则不仅适用于变量名，也适用于所有可以由程序员起名的语法元素，例如以后要讲的函数名、宏定义、结构体成员名等，在C语言中这些统称为标识符。

在C语言中有些单词有特殊意义，不允许用作标识符，这些单词称为关键字或保留字。通常用于编程的文本编辑器都会高亮显示这些关键字，所以只要小心一点通常不会误用作标识符。

还有一点要注意，一般来说应避免使用以下划线开头的标识符，以下划线开头的标识符只要不和C语言关键字冲突的都是合法的，但是往往被编译器用作一些功能扩展，C标准库也定义了很多以下划线开头的标识符，所以除非你对编译器和C标准库特别清楚，一般应避免使用这些标识符，以免造成命名冲突。

四、赋值 ​

注意变量一定要先声明后使用。另外，变量声明中的类型表明这个变量代表多大的一块存储空间，这样编译器才知道如何读写这块存储空间。

总结一下：定义一个变量，就是分配一块存储空间并给它命名；给一个变量赋值，就是把一个值保存到这块存储空间中。变量的定义和赋值也可以一步完成，这称为变量的初始化。

注意，初始化是一种特殊的声明，而不是一种赋值语句。

五、表达式 ​

如果一个表达式中出现多个等号，不是从左到右计算而是从右到左计算。同样优先级的运算符是从左到右计算还是从右到左计算称为运算符的结合性。

有的表达式既可以做左值又可以做右值，而有的表达式只能做右值。

习题1：假设变量x和n是两个正整数，我们知道x/n这个表达式的结果要取Floor，例如x是17，n是4，则结果是4。如果希望结果是Ceiling应该怎么写表达式呢？例如x是17，n是4，则结果是5；x是16，n是4，则结果是4。

如果希望结果是Ceiling可以将表达式写为((x-1)/n)+1。假设x=an+b，若b=0，则(x-1)/n=a-1，表达式的值为a；若b>0，则(x-1)/n=a，表达式的值为a+1，符合Ceiling。

六、字符类型与字符编码 ​

之前我们说“整型”是指int型，而现在我们知道char型本质上就是整数，只不过取值范围比int型小，所以以后我们把char型和int型统称为整数类型或简称整型。

字符也可以用ASCII码转义序列表示，这种转义序列由\加上1~3个八进制数字组成，或者由\x或大写\X加上1~2个十六进制数字组成，可以用在字符常量或字符串字面值中。

第3章：简单函数 ​

一、数学函数 ​

头文件中声明了我们程序中使用的库函数，根据先声明后使用的原则，要使用printf函数必须包含stdio.h，要使用数学函数必须包含math.h，如果什么库函数都不使用就不必包含任何头文件。

使用math.h中声明的库函数还有一点特殊之处，gcc命令行必须加-lm选项，因为数学函数位于libm.so库文件中（这些库文件通常位于/lib目录下），-lm选项告诉编译器，我们程序中用到的数学函数要到这个库文件里找。

二、自定义函数 ​

只有分配存储空间的变量声明才叫变量定义，其实函数也是一样，编译器只有见到函数定义才会生成指令，而指令在程序运行时当然也要占存储空间。那么没有函数体的函数声明有什么用呢？它为编译器提供了有用的信息，编译器在翻译代码的过程中，只有见到函数原型（不管带不带函数体）之后才知道这个函数的名字、参数类型和返回值，这样碰到函数调用时才知道怎么生成相应的指令，所以函数原型必须出现在函数调用之前，这也是遵循“先声明后使用”的原则。

三、形参和实参 ​

下面我们定义一个带参数的函数，我们需要在函数定义中指明参数的个数和每个参数的类型，定义参数就像定义变量一样，需要为每个参数指明类型，参数的命名也要遵循标识符命名规则。需要注意的是，定义变量时可以把相同类型的变量列在一起，而定义参数却不可以。

记住这条基本原理：形参相当于函数中定义的变量，调用函数传递参数的过程相当于定义形参变量并且用实参的值来初始化。

习题1：定义一个函数increment，它的作用是把传进来的参数加1。例如：

c

void increment(int x)
{
	x = x + 1;
}

int main(void)
{
	int i = 1, j = 2;
	increment(i); /* i now becomes 2 */
	increment(j); /* j now becomes 3 */
	return 0;
}

我们在main函数中调用increment增加变量i和j的值，这样能奏效吗？为什么？

不能奏效，因为main函数中的i和j和increment函数中的参数是不同的变量，只是将i和j的值赋给了increment函数中的参数x，无法影响main函数中i和j的值。

习题2：如果在一个程序中调用了printf函数却不包含头文件，编译时会报警告：warning: incompatible implicit declaration of built-in function ‘printf’。请分析错误原因。

由于函数需要先声明再调用，printf函数的声明在头文件中，直接调用printf函数而不包含头文件相当于没有对printf函数进行声明，因此编译时会报警告。

四、全局变量、局部变量和作用域 ​

我们把函数中定义的变量称为局部变量，由于形参相当于函数中定义的变量，所以形参也是一种局部变量。在这里“局部”有两层含义：

• 一个函数中定义的变量不能被另一个函数使用。
• 每次调用函数时局部变量都表示不同的存储空间。局部变量在每次函数调用时分配存储空间，在每次函数返回时释放存储空间。

与局部变量的概念相对的是全局变量，全局变量定义在所有的函数体之外，它们在程序开始运行时分配存储空间，在程序结束时释放存储空间，在任何函数中都可以访问全局变量。

正因为全局变量在任何函数中都可以访问，所以在程序运行过程中全局变量被读写的顺序从源代码中是看不出来的，源代码的书写顺序并不能反映函数的调用顺序。程序出现了Bug往往就是因为在某个不起眼的地方对全局变量的读写顺序不正确，如果代码规模很大，这种错误是很难找到的。而对局部变量的访问不仅局限在一个函数内部，而且局限在一次函数调用之中，从函数的源代码很容易看出访问的先后顺序是怎样的，所以比较容易找到Bug。因此，虽然全局变量用起来很方便，但一定要慎用，能用函数传参代替的就不要用全局变量。

注意一点：局部变量可以用类型相符的任意表达式来初始化，而全局变量只能用常量表达式初始化。

如果全局变量在定义时不初始化则初始值是0，如果局部变量在定义时不初始化则初始值是不确定的。所以，局部变量在使用之前一定要先赋值。

虽然在一个函数体中可以声明另一个函数，但不能定义另一个函数，C语言不允许嵌套定义函数。

第4章：分支语句 ​

一、if语句 ​

在C语言中，任何允许出现语句的地方既可以是由;号结尾的一条语句，也可以是由{}括起来的若干条语句或声明组成的语句块，语句块和上一章介绍的函数体的语法相同。注意语句块的}后面不需要加;号。如果}后面加了;号，则这个;号本身又是一条新的语句了，在C语言中一个单独的;号表示一条空语句。

习题1：以下程序段编译能通过，执行也不出错，但是执行结果不正确，请分析一下哪里错了。还有，既然错了为什么编译能通过呢？

c

int x = -1;
if (x > 0);
	printf("x is positive.\n");

因为if (x > 0)后面多了一个;，;作为一个空语句，语法上没有问题，因此编译可以通过，但是程序经过判断后不执行空语句，从而执行printf语句，执行过程没有问题，但是执行结果出现错误。

二、if/else语句 ​

%运算符的结果总是与被除数同号。

C语言规定，else总是和它上面最近的一个if配对。

浮点型的精度有限，不适合用==运算符做精确比较。

习题1：写两个表达式分别取整型变量x的个位和十位。

g = x % 10;				个位
s = (x / 10) % 10;		十位

习题2：写一个函数，参数是整型变量x，功能是打印x的个位和十位。

void print_gs(int x)
{
    int g,s;
    g = x % 10;
    s = (x / 10) % 10;
    printf("%d的个位是%d，十位是%d",x,g,s);
}

三、布尔代数 ​

目前为止介绍的这些运算符的优先级顺序是：!高于* / %，高于+ -，高于> < >= <=，高于== !=，高于&&，高于||，高于=。写一个控制表达式很可能同时用到这些运算符中的多个，如果记不清楚运算符的优先级一定要多套括号。

习题1：把代码段

c

if (x > 0 && x < 10);
else
	printf("x is out of range.\n");

改写成下面这种形式，____应该怎么填？

c

if (____ || ____)
	printf("x is out of range.\n");

应该填入x <= 0 || x >= 10。

习题2：把代码段

c

if (x > 0)
	printf("Test OK!\n");
else if (x <= 0 && y > 0)
	printf("Test OK!\n");
else
	printf("Test failed!\n");

改写成下面这种形式，____应该怎么填？

c

if (____ && ____)
	printf("Test failed!\n");
else
	printf("Test OK!\n");

应该填入x <= 0 && y <= 0。

习题3：有这样一段代码：

c

if (x > 1 && y != 1) {
	...
} else if (x < 1 && y != 1) {
	...
} else {
	...
}

要进入最后一个else，x和y需要满足条件____ || ____。这里应该怎么填？

x和y需要满足：x == 1 || y == 1。

习题4：以下哪一个if判断条件是多余的可以去掉？这里所谓的“多余”是指，某种情况下如果本来应该打印Test OK!，去掉这个多余条件后仍然打印Test OK!，如果本来应该打印Test failed!，去掉这个多余条件后仍然打印Test failed!。

c

if (x<3 && y>3)
	printf("Test OK!\n");
else if (x>=3 && y>=3)
	printf("Test OK!\n");
else if (z>3 && x>=3)
	printf("Test OK!\n");
else if (z<=3 && y>=3)
	printf("Test OK!\n");
else
	printf("Test failed!\n");

if (x>=3 && y>=3)这个判断条件是多余的。

四、switch语句 ​

使用switch语句要注意几点：

• case后面跟表达式的必须是常量表达式，这个值和全局变量的初始值一样必须在编译时计算出来。
• “if/else语句”讲过浮点型不适合做精确比较，所以C语言规定case后面跟的必须是整型常量表达式。
• 进入case后如果没有遇到break语句就会一直往下执行，后面其它case或default分支的语句也会被执行到，直到遇到break，或者执行到整个switch语句块的末尾。通常每个case后面都要加上break语句，但有时会故意不加break来利用这个特性。

第5章：深入理解函数 ​

一、return语句 ​

函数的返回值应该这样理解：函数返回一个值相当于定义一个和返回值类型相同的临时变量并用return后面的表达式来初始化。

函数的返回值不是左值，或者说函数调用表达式不能做左值。

习题1：编写一个布尔函数int is_leap_year(int year)，判断参数year是不是闰年。如果某年份能被4整除，但不能被100整除，那么这一年就是闰年，此外，能被400整除的年份也是闰年。

编写的布尔函数如下：

int is_leap_year(int year)
{
    if(((year % 4 == 0) && (year % 100 != 0))|| (year % 400 == 0))
    return 1;
    else return 0;
}

习题2：编写一个函数double myround(double x)，输入一个小数，将它四舍五入。例如myround(-3.51)的值是-4.0，myround(4.49)的值是4.0。可以调用math.h中的库函数ceil和floor实现这个函数。

编写的函数如下：

double myround(double x)
{
    if(x >= 0.0){
        if((x - floor(x)) >= 0.5)return ceil(x);
        else return floor(x);
    }
    else {
        if((x - floor(x)) > 0.5 )return ceil(x);
        else return floor(x);
    }
}

二、增量式开发 ​

尽可能复用（Reuse）以前写的代码，避免写重复的代码。封装就是为了复用，把解决各种小问题的代码封装成函数，在解决第一个大问题时可以用这些函数，在解决第二个大问题时可以复用这些函数。

解决问题的过程是把大的问题分成小的问题，小的问题再分成更小的问题，这个过程在代码中的体现就是函数的分层设计。

三、递归 ​

随着函数调用的层层深入，存储空间的一端逐渐增长，然后随着函数调用的层层返回，存储空间的这一端又逐渐缩短，并且每次访问参数和局部变量时只能访问这一端的存储单元，而不能访问内部的存储单元。具有这种性质的数据结构称为堆栈或栈（Stack），随着函数调用和返回而不断变化的这一端称为栈顶，每个函数调用的参数和局部变量的存储空间称为一个栈帧（Stack Frame）。操作系统为程序的运行预留了一块栈空间，函数调用时就在这个栈空间里分配栈帧，函数返回时就释放栈帧。

写递归函数时一定要记得写Base Case，否则即使递推关系正确，整个函数也不正确。

习题1：编写递归函数求两个正整数a和b的最大公约数（GCD，Greatest Common Divisor），使用Euclid算法：

1、如果a除以b能整除，则最大公约数是b。

2、否则，最大公约数等于b和a%b的最大公约数。

Euclid算法是很容易证明的，请读者自己证明一下为什么这么算就能算出最大公约数。最后，修改你的程序使之适用于所有整数，而不仅仅是正整数。

两个正整数的递归函数如下：

int GCD(int a, int b)
{
    int result;
    if(a % b == 0)result = b;
    else result = GCD(b,a%b);
    return result;
}

严格的证明方法建议直接百度，接下来修改程序：

int GCD(int a, int b)
{
    int result;
    a = abs(a);
    b = abs(b);
    if(a % b == 0)result = b;
    else result = GCD(b,a%b);
    return result;
}

习题2：编写递归函数求Fibonacci数列的第n项，这个数列是这样定义的：
fib(0)=1
fib(1)=1
fib(n)=fib(n-1)+fib(n-2)

编写的递归函数如下：

int fib(int n)
{
    int result;
    if(n == 0)result = 1;
    else if (n == 1)result = 1;
    else result = fib(n-1) + fib(n-2);
    return result;
}

第6章：循环语句 ​

一、while语句 ​

如果控制表达式的值为真，子语句就被执行，然后再次测试控制表达式的值，如果还是真，就把子语句再执行一遍，再测试控制表达式的值…这种控制流程称为循环，子语句称为循环体。如果某次测试控制表达式的值为假，就跳出循环执行后面的return语句，如果第一次测试控制表达式的值就是假，那么直接跳到return语句，循环体一次都不执行。

给变量多次赋值时要格外小心，在代码中多次读写同一变量应该以一种一致的方式进行。所谓“一致的方式”是说应该有一套统一的规则，规定在一段代码中哪里会对某个变量赋值、哪里会读取它的值。

习题1：用循环解决“递归”的所有习题，体会递归和循环这两种不同的思路。

首先解决求两个正整数的最大公约数问题，至于推广到整数范围则只需要利用绝对值函数将a和b全部变成正整数即可，程序如下：

int GCD(int a,int b)
{
    int result;
    while(a % b != 0)
    {
        int x;
        x = a;
        a = b;
        b = x%b;
    }
    result = b;
    return result;
}

接下来利用循环求Fibonacci数列的第n项，程序如下：

int fib(int n)
{
    int a0 = 1;
    int a1 = 1;
    int i = 2;
    int result;
    while(i != (n + 1))
    {
        result = a0 + a1;
        a0 = a1;
        a1 = result;
        i = i + 1;
    }
    return result;
}

习题2：编写程序数一下1到100的所有整数中出现多少次9。在写程序之前先把这些问题考虑清楚：

• 这个问题中的循环变量是什么？
• 这个问题中的累加器是什么？用加法还是用乘法累积？
• 在“if/else语句”的习题1写过取一个整数的个位和十位的表达式，这两个表达式怎样用到程序中？

在给出具体程序之前先分析一下题目，首先循环变量是从1到100的所有整数，加法累积我们所数出来的9，至于判断有多少个，则需要利用之前写的取整数的个位和十位的表达式进行判断。分析清楚之后给出程序如下：

int main(void){
    int i = 1;
    int n = 0;
    while (i <= 100)
    {
        if((i % 10) == 9)n = n + 1;
        if((i/10)%10 == 9)n = n + 1;
        i = i + 1;
    }
    printf("一共有%d个9",n);
    return 0;
}

二、do/while语句 ​

while语句先测试控制表达式的值再执行循环体，而do/while语句先执行循环体再测试控制表达式的值。如果控制表达式的值一开始就是假，while语句的循环体一次都不执行，而do/while语句的循环体仍然要执行一次再跳出循环。其实只要有while循环就足够了，do/while循环和后面要讲的for循环都可以改写成while循环，只不过有些情况下用do/while或for循环写起来更简便，代码更易读。

三、for语句 ​

++i这个表达式相当于i = i + 1，++称为前缀自增运算符，类似地，--称为前缀自减运算符，--i相当于i = i - 1。如果把++i这个表达式看作一个函数调用，除了传入一个参数返回一个值（等于参数值加1）之外，还产生一个Side Effect，就是把变量i的值增加了1。

++和--运算符也可以用在变量后面，例如i++和i--，为了和前缀运算符区别，这两个运算符称为后缀自增运算符和后缀自减运算符。如果把i++这个表达式看作一个函数调用，传入一个参数返回一个值，返回值就等于参数值（而不是参数值加1），此外也产生一个Side Effect，就是把变量i的值增加了1，它和++i的区别就在于返回值不同。同理，--i返回减1之后的值，而i--返回减1之前的值，但这两个表达式都产生同样的Side Effect，就是把变量i的值减了1。

四、break和continue语句 ​

在“switch语句”中我们见到了break语句的一种用法，用来跳出switch语句块，这个语句也可以用来跳出循环体。continue语句也会终止当前循环，和break语句不同的是，continue语句终止当前循环后又回到循环体的开头准备执行下一次循环。对于while循环和do/while循环，执行continue语句之后测试控制表达式，如果值为真则继续执行下一次循环；对于for循环，执行continue语句之后首先计算控制表达式3，然后测试控制表达式2，如果值为真则继续执行下一次循环。

习题1：求素数这个程序只是为了说明break和continue的用法才这么写的，其实完全可以不用break和continue，请读者修改一下控制流程，去掉break和continue而保持功能不变。

修改控制流程后的代码如下：

int is_prime(int n)
{
    int i;
    if(n == 1)return 0;
    for(i = 2;i < n;i++)
    {
        if((n % i) == 0)return 0;
    }
    return 1;
}

int main(void){
    int i;
    int x;
    for(i = 1;i <= 100;i++)
    {
        if(is_prime(i))printf("%d是素数\n",i);
    }
    return 0;
}

习题2：上一节讲过怎样把for循环改写成等价的while循环，但也提到如果循环体中有continue语句这两种形式就不等价了，想一想为什么不等价了？

由于在for循环的循环体中存在continue的话，执行控制表达式3后然后测试控制表达式2，而在while循环中则直接测试控制表达式，会导致死循环。

五、嵌套循环 ​

在有多层循环或switch嵌套的情况下，break只能跳出最内层的循环或switch，continue也只能终止最内层循环并回到该循环的开头。

习题1：上面打印的小九九有一半数据是重复的，因为8*9和9*8的结果一样。请修改程序打印这样的小九九：

  1	
  2   4	
  3   6   9	
  4   8   12  16	
  5   10  15  20  25	
  6   12  18  24  30  36	
  7   14  21  28  35  42  49	
  8   16  24  32  40  48  56  64	
  9   18  27  36  45  54  63  72  81

修改代码如下：

#include <stdio.h>

int main(void){
	int i, j;
	for (i=1; i<=9; i++) {
		for (j=1; j<=i; j++)
			printf("%d\t", i*j);
		printf("\n");
	}
	return 0;
}

习题2：编写函数diamond打印一个菱形。如果调用diamond(3, '*')则打印：

      *
  *   *   *
      *

如果调用diamond(5, '+')则打印：

          +
      +   +   +
  +   +   +   +   +
      +   +   +
          +

如果用偶数做参数则打印错误提示。

具体思路是先打印前(n+1)/2行，每行先打印符号前的空格，之后打印符号和符号后的空格，按照数量写出数列的通项，之后按照同样的思路打印剩余的行，编写的函数如下：

void diamond(int n,char a)
{
    int i,j;
    if(n%2 == 0)printf("error");
    else
    {
        int k = (n+1)/2;
        for(i=1; i<=k; i++)
        {

            for(j=1; j<=(k-i); j++)printf("\t");
            for(j=1; j<=(2*i-1); j++)printf("%c\t",a);
            printf("\n");
        }
        for(i=k+1; i<=n; i++)
        {
            for(j=1; j<=(i-k); j++)printf("\t");
            for(j=1; j<=(4*k-1-2*i); j++)printf("%c\t",a);
            printf("\n");
        }
    }
}

六、goto语句和标号 ​

滥用goto语句会使程序的控制流程非常复杂，可读性很差。

通常goto语句只用于这种场合，一个函数中任何地方出现了错误条件都可以立即跳转到函数末尾做出错处理（例如释放先前分配的资源、恢复先前改动过的全局变量等），处理完之后函数返回。比较用goto和不用goto的两种写法，用goto语句还是方便很多。但是除此之外，在任何其它场合都不要轻易考虑使用goto语句。

第7章：结构体 ​

一、复合类型与结构体 ​

如果用实部和虚部表示一个复数，我们可以写成由两个double型组成的结构体：

c

struct complex_struct {
	double x, y;
};

这一句定义了标识符complex_struct（同样遵循标识符的命名规则），这种标识符在C语言中称为Tag，struct complex_struct { double x, y; }整个可以看作一个类型名，就像int或double一样，只不过它是一个复合类型，如果用这个类型名来定义变量，可以这样写：

c

struct complex_struct {
	double x, y;
} z1, z2;

这样z1和z2就是两个变量名，变量定义后面带个;号是我们早就习惯的。但即使像先前的例子那样只定义了complex_struct这个Tag而不定义变量，}后面的;号也不能少。这点一定要注意，类型定义也是一种声明，声明都要以;号结尾，结构体类型定义的}后面少;号是初学者常犯的错误。不管是用上面两种形式的哪一种定义了complex_struct这个Tag，以后都可以直接用struct complex_struct来代替类型名了。例如可以这样定义另外两个复数变量：

c

struct complex_struct z3, z4;

如果在定义结构体类型的同时定义了变量，也可以不必写Tag，例如：

c

struct {
	double x, y;
} z1, z2;

但这样就没办法再次引用这个结构体类型了，因为它没有名字。每个复数变量都有两个成员x和y，可以用.运算符来访问，这两个成员的存储空间是相邻的，合在一起组成复数变量的存储空间。

z1必须是局部变量才能用另一个变量x的值来初始化它的成员，如果是全局变量就只能用常量表达式来初始化。

结构体类型用在表达式中有很多限制，不像基本类型那么自由，比如+ - * /等算术运算符和&& || !等逻辑运算符都不能作用于结构体类型，if语句、while语句中的控制表达式的值也不能是结构体类型。严格来说，可以做算术运算的类型称为算术类型，算术类型包括整型和浮点型。可以表示零和非零，可以参与逻辑与、或、非运算或者做控制表达式的类型称为标量类型，标量类型包括算术类型和以后要讲的指针类型。

二、数据抽象 ​

在我们的复数运算程序中，复数有可能用直角坐标或极坐标来表示，我们把这个有可能变动的因素提取出来组成复数存储表示层：real_part、img_part、magnitude、angle、make_from_real_img、make_from_mag_ang。这一层看到的数据是结构体的两个成员x和y，或者r和A，如果改变了结构体的实现就要改变这一层函数的实现，但函数接口不改变，因此调用这一层函数接口的复数运算层也不需要改变。复数运算层看到的数据只是一个抽象的“复数”的概念，知道它有直角坐标和极坐标，可以调用复数存储表示层的函数得到这些座标。再往上看，其它使用复数运算的程序看到的数据是一个更为抽象的“复数”的概念，只知道它是一个数，像整数、小数一样可以加减乘除，甚至连它有直角坐标和极坐标也不需要知道。

习题1：在本节的基础上实现一个打印复数的函数，打印的格式是x+yi，如果实部或虚部为0则省略，例如：1.0、-2.0i、-1.0+2.0i、1.0-2.0i。最后编写一个main函数测试本节的所有代码。想一想这个打印函数应该属于上图中的哪一层？

首先这个打印函数属于复数运算层，只需要知道有实部和虚部就可以完成打印的任务。因此打印函数如下：

void print_complex(struct complex_struct z)
{
    if(img_part(z) == 0)printf("%f",real_part(z));
    else if(real_part(z) == 0)printf("%fi",img_part(z));
    else if(img_part(z)>0)printf("%f+%fi",real_part(z),img_part(z));
    else printf("%f%fi",real_part(z),img_part(z));
}

测试的main函数为：

int main(void){
	struct complex_struct z1 = {1.0, -2.0};
    struct complex_struct z2 = {2.0, 3.0};
    struct complex_struct z3 = add_complex(z1,z2);
    struct complex_struct z4 = sub_complex(z1,z2);
    struct complex_struct z5 = mul_complex(z1,z2);
    struct complex_struct z6 = div_complex(z1,z2);

    double m = magnitude(z1);
    double a = angle(z1);

    struct complex_struct z7 = make_from_mag_ang(m,a);

    printf("z1 = ");
    print_complex(z1);
    printf("z2 = ");
    print_complex(z2);
    printf("z3 = ");
    print_complex(z3);
    printf("z4 = ");
    print_complex(z4);
    printf("z5 = ");
    print_complex(z5);
    printf("z6 = ");
    print_complex(z6);
    printf("z7 = ");
    print_complex(z7);

	return 0;
}

习题2：实现一个用分子分母的格式来表示有理数的结构体rational以及相关的函数，rational结构体之间可以做加减乘除运算，运算的结果仍然是rational。测试代码如下：

c

int main(void)
{
	struct rational a = make_rational(1, 8); /* a=1/8 */
	struct rational b = make_rational(-1, 8); /* b=-1/8 */
	print_rational(add_rational(a, b));
	print_rational(sub_rational(a, b));
	print_rational(mul_rational(a, b));
	print_rational(div_rational(a, b));

	return 0;
}

注意要约分为最简分数，例如1/8和-1/8相减的打印结果应该是1/4而不是2/8，可以利用“递归”练习题中的Euclid算法来约分。在动手编程之前先思考一下这个问题实现了什么样的数据抽象，抽象层应该由哪些函数组成。

根据分数的运算法则，可以对分数抽象为由分子和分母组成的结构体，对加减乘除运算函数来说只需要知道分数的分子和分母就可以完成运算，约分则用Euclid算法得出分子分母的最大公约数后将分子分母都除以这个最大公约数即可。相关函数代码如下：

struct rational {
        int x,y;
};

struct rational make_rational(int x, int y) {
        struct rational z;
        z.x = x;
        z.y = y;
        return z;
}

int GCD(int a, int b)
{
    int result;
    a = abs(a);
    b = abs(b);
    if(a % b == 0)result = b;
    else result = GCD(b,a%b);
    return result;
}

struct rational add_rational(struct rational z1, struct rational z2) {
        struct rational z;
        int g;
        z.x = z1.x*z2.y + z1.y*z2.x;
        z.y = z1.y*z2.y;
        g = GCD(z.x,z.y);
        z.x = z.x/g;
        z.y = z.y/g;
        
        return z;
}

struct rational sub_rational(struct rational z1, struct rational z2) {
        struct rational z;
        int g;
        z.x = z1.x*z2.y - z1.y*z2.x;
        z.y = z1.y*z2.y;
        g = GCD(z.x,z.y);
        z.x = z.x/g;
        z.y = z.y/g;
        
        return z;
}

struct rational mul_rational(struct rational z1, struct rational z2) {
        struct rational z;
        int g;
        z.x = z1.x*z2.x;
        z.y = z1.y*z2.y;
        g = GCD(z.x,z.y);
        z.x = z.x/g;
        z.y = z.y/g;
        
        return z;
}

struct rational div_rational(struct rational z1, struct rational z2) {
        struct rational z;
        int g;
        z.x = z1.x*z2.y;
        z.y = z1.y*z2.x;
        g = GCD(z.x,z.y);
        z.x = z.x/g;
        z.y = z.y/g;
        
        return z;
}

void print_rational(struct rational z) {
    if(z.x == 0)printf("%d\n",z.x);
    else if(z.x == -z.y)printf("%d\n",-1);
    else if(z.x == z.y)printf("%d\n",1);
    else printf("%d/%d\n",z.x,z.y);
}

三、数据类型标志 ​

c

enum coordinate_type { RECTANGULAR, POLAR };
struct complex_struct {
	enum coordinate_type t;
	double a, b;
};

enum关键字的作用和struct关键字类似，把coordinate_type这个标识符定义为一个Tag，struct complex_struct表示一个结构体类型，而enum coordinate_type表示一个枚举类型。枚举类型的成员是常量，它们的值由编译器自动分配，例如定义了上面的枚举类型之后，RECTANGULAR就表示常量0，POLAR表示常量1。

习题1：本节只给出了make_from_real_img和make_from_mag_ang函数的实现，请读者自己实现real_part、img_part、magnitude、angle这些函数。

只需要根据不同的存储类型选择对应的计算方式即可完成函数的实现，函数如下：

double real_part(struct complex_struct z)
{
	if(z.t == 0)return z.a;
    else return z.a * cos(z.b);
}

double img_part(struct complex_struct z)
{
	if(z.t == 0)return z.b;
    else return z.a * sin(z.b);
}

double magnitude(struct complex_struct z)
{
	if(z.t == 0)return sqrt(z.a * z.a + z.b * z.b);
    else return z.a;
}

double angle(struct complex_struct z)
{
	if(z.t == 0)return atan2(z.b, z.a);
    else return z.b;

}

习题2：编译运行下面这段程序：

c

#include <stdio.h>

enum coordinate_type { RECTANGULAR = 1, POLAR };

int main(void)
{
	int RECTANGULAR;
	printf("%d %d\n", RECTANGULAR, POLAR);
	return 0;
}

结果是什么？并解释一下为什么是这样的结果。

结果是32764 0，由于枚举的成员名和变量名在同一命名空间中，因此不能再对RECTANGULAR赋予int类型，否则会导致命名冲突。

四、嵌套结构体 ​

结构体也是一种递归定义：结构体的成员具有某种数据类型，而结构体本身也是一种数据类型。换句话说，结构体的成员可以是另一个结构体，即结构体可以嵌套定义。

第8章：数组 ​

一、数组的基本概念 ​

数组也是一种复合数据类型，它由一系列相同类型的元素组成。

到目前为止我们学习了五种后缀运算符：后缀++、后缀--、结构体取成员.、数组取下标[]、函数调用()。还学习了五种单目运算符（或者叫前缀运算符）：前缀++、前缀--、正号+、负号-、逻辑非!。在C语言中后缀运算符的优先级最高，单目运算符的优先级仅次于后缀运算符，比其它运算符的优先级都高，

数组下标也可以是表达式，但表达式的值必须是整型的。

数组和结构体虽然有很多相似之处，但也有一个显著的不同：数组不能相互赋值或初始化。既然不能相互赋值，也就不能用数组类型作为函数的参数或返回值。

对于数组类型有一条特殊规则：数组类型做右值使用时，自动转换成指向数组首元素的指针。

习题1：编写一个程序，定义两个类型和长度都相同的数组，将其中一个数组的所有元素拷贝给另一个。既然数组不能直接赋值，想想应该怎么实现。

可以利用循环的方式，分别拷贝每个数值给另一个数组，程序如下：

#include <stdio.h>

int main(void)
{
	int a[5] = {4,3,2,1,0};
    int b[5] = {};
    int i;
    for(i = 0; i < 5; i++)
    {
        b[i] = a[i];
    };
    for(i = 0; i < 5; i++)
        printf("%d\n",b[i]);
    
    return 0;
}

二、数组应用实例：统计随机数 ​

注意，虽然include和define在预处理指示中有特殊含义，但它们并不是C语言的关键字，换句话说，它们也可以用作标识符，例如声明int include;或者void define(int);。在预处理阶段，如果一行以#号开头，后面跟include或define，预处理器就认为这是一条预处理指示，除此之外出现在其它地方的include或define预处理器并不关心，只是当成普通标识符交给编译阶段去处理。

我们只要把#define N的值改为100000，就相当于把整个程序中所有用到N的地方都改为100000了。如果我们不这么写，而是在定义数组时直接写成int a[20];，在每个循环中也直接使用20这个值，这称为硬编码。如果原来的代码是硬编码的，那么一旦需要把20改成100000就非常麻烦，你需要找遍整个代码，判断哪些20表示这个数组的长度就改为100000，哪些20表示别的数量则不做改动，如果代码很长，这是很容易出错的。所以，写代码时应尽可能避免硬编码。

习题1：用rand函数生成[10,20]之间的随机整数，表达式应该怎么写？

首先给出表达式，之后进行分析。

void gen_random(int upper_bound,int downer_bound)
{
	int i;
	for (i = 0; i < N; i++)
		a[i] = (rand() % (upper_bound-downer_bound + 1) ) + downer_bound;
}

表达式中upper_bound等于20，downer_bound等于10，由于取随机整数包含上限，rand函数对上下限之差+1取余得到0-10，加上下限即为所求随机数的区间。

三、数组应用实例：直方图 ​

C标准库允许我们自己指定一个初值，然后在此基础上生成伪随机数，这个初值称为Seed，可以用srand函数指定Seed。通常我们通过别的途径得到一个不确定的数作为Seed，然后传给srand。

习题1：补完本节直方图程序的main函数，以可视化的形式打印直方图。例如上一节统计20个随机数的结果是：

0  1  2  3  4  5  6  7  8  9

*  *  *  *     *  *  *     *
*     *  *     *  *  *     *
      *  *        *
                  *
                  *

在打印之前利用循环找到所有数字中出现的最大次数，即为循环打印*的最大行数，打印过程首先在第一行打印0-9，之后按行打印*，利用循环判断每个数出现的次数是否大于当前所打印的行数，每行打印完打印一个换行符。补完后的main函数如下：

int main(void)
{
	int i, j, histogram[10] = {0};
    int max = 0;

	gen_random(10);
    printf("\n");
	for (i = 0; i < N; i++)
		histogram[a[i]]++;
    for (i = 0; i < 10; i++){
        if(max < histogram[i])max = histogram[i];
    }
	for (i = 0; i < 10; i++)printf("%d\t",i);
    printf("\n");
    printf("\n");
    for (i = 1; i <= max; i++){
        for (j = 0; j < 10; j++){
            if(i <= histogram[j])printf("*\t");
            else printf("\t");
        }
        printf("\n");
    }
}

习题2：定义一个数组，编程打印它的全排列。比如定义：

c

#define N 3
int a[N] = { 1, 2, 3 };

则运行结果是：

$ ./a.out
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 2 1 
3 1 2 
1 2 3

程序的主要思路是：

• 第1个数换到最前面来（本来就在最前面），准备打印1xx，再对后两个数2和3做全排列。

• 把第2个数换到最前面来，准备打印2xx，再对后两个数1和3做全排列。

• 把第3个数换到最前面来，准备打印3xx，再对后两个数1和2做全排列。

可见这是一个递归的过程，把对整个序列做全排列的问题归结为对它的子序列做全排列的问题，注意我没有描述Base Case怎么处理，你需要自己想。你的程序要具有通用性，如果改变了N和数组a的定义（比如改成4个数的数组），其它代码不需要修改就可以做4个数的全排列（共24种排列）。

完成了上述要求之后再考虑第二个问题：如果再定义一个常量M表示从N个数中取几个数做排列（N == M时表示全排列），原来的程序应该怎么改？

最后再考虑第三个问题：如果要求从N个数中取M个数做组合而不是做排列，就不能用原来的递归过程了，想想组合的递归过程应该怎么描述，编程实现它。

先考虑第一个问题，按照思路，停止递归即交换数组的最后两个数，分别打印出来，打印后需要将数组返回到之前的顺序，否则下一次递归会在错误的顺序进行，导致出现排列出现重复或缺少。递归过程则是开始时将一个数提到最前面，然后对剩余的数进行递归，具体实现则是将这个数存起来，然后将这个数左边的数右移一位，最后将这个数放在第一位，形成一个新的数组，进行下一步的递归，当然，每次递归所选择的这个数的范围逐渐减小。而且递归后按照相反的过程将数组变回原状。程序如下：

#include <stdio.h>

#define N 4

int a[N] = {1,2,3,4};

void full_permutation(int n)
{
    int i,j,x;
    if(n == 2){
        for(i = 0; i < N; i++)printf("%d ",a[i]);
        printf("\n");
        x = a[N-2];
        a[N-2] = a[N-1];
        a[N-1] = x;
        for(i = 0; i < N; i++)printf("%d ",a[i]);
        printf("\n");
        x = a[N-2];
        a[N-2] = a[N-1];
        a[N-1] = x;
    }
    else {
        for(i = N-n; i < N; i++){
            x = a[i];
            for(j = i; j > N-n; j--){
                a[j] = a[j-1];
            }
            a[N-n] = x;
            full_permutation(n-1);
            x = a[N-n];
            for(j = N-n; j < i; j++ ){
                a[j] = a[j+1];
            }
            a[i] = x;
        }

    }
}

int main(void)
{
    full_permutation(N);

    return 0;
}

接下来考虑第二个问题，要完成从N个数中选M个数进行排列，需要对递归的截止条件进行修改，即之前的截止条件为将最后两个数交换位置，现在修改截止条件为固定了M个数后截止，不管数组此时后面还有几个数没有进行排列，其余部分则只是修改循环的开始条件即可。修改后的程序如下：

#include <stdio.h>

#define N 4
#define M 2

int a[N] = {1,2,3,4};


void full_permutation(int m)
{
    int i,j,x;
    if(m == 0){
        for(i = 0; i < M; i++)printf("%d ",a[i]);
        printf("\n");
    }
    else {
        for(i = M-m; i < N; i++){
            x = a[i];
            for(j = i; j > M-m; j--){
                a[j] = a[j-1];
            }
            a[M-m] = x;
            full_permutation(m-1);
            x = a[M-m];
            for(j = M-m; j < i; j++ ){
                a[j] = a[j+1];
            }
            a[i] = x;
        }

    }
}

int main(void)
{
    full_permutation(M);

    return 0;
}

最后考虑组合逻辑，需要定义一个全局变量j用来存储每次递归的起始位置，比如第一次选择了a[0]，那么下一次递归选择要从a[1]开始。当然递归结束后还要将j回退到之前的数据。 将每次选择的数存入另一个数组，最后将这个数组打印输出即可。程序如下：

#include <stdio.h>

#define N 4
#define M 3

int a[N] = {1,2,3,4};
int b[M];
int j = 0;

void combination(int m)
{
    int i,x;
    if(m == 0){
        for(i = 0; i < M; i++)printf("%d ",b[i]);
        printf("\n");
    }
    else {
        for(i = j; i <= N-m; i++)
        {
            x = j;
            j = i + 1;
            b[M-m] = a[i];
            combination(m-1);
            j = x;
        }
    }
}

int main(void)
{
    combination(M);

    return 0;
}

四、字符串 ​

字符串可以看作一个数组，它的每个元素是字符型的，注意每个字符末尾都有一个字符'\0'做结束符，这里的\0是ASCII码的八进制表示，也就是ASCII码为0的Null字符，在C语言中这种字符串也称为以零结尾的字符串。数组元素可以通过数组名加下标的方式访问，而字符串字面值也可以像数组名一样使用，可以加下标访问其中的字符。但是通过下标修改其中的字符却是不允许的。字符串字面值还有一点和数组名类似，做右值使用时自动转换成指向首元素的指针。

如果用于初始化的字符串字面值比数组还长，则数组str只包含字符串的前10个字符，不包含Null字符，这种情况编译器会给出警告。如果要用一个字符串字面值准确地初始化一个字符数组，最好的办法是不指定数组的长度，让编译器自己计算。

有一种情况需要特别注意，如果用于初始化的字符串字面值比数组刚好长出一个Null字符的长度，则数组str不包含Null字符，并且编译器不会给出警告。

补充一点，printf函数的格式化字符串中可以用%s表示字符串的占位符。printf会从数组str的开头一直打印到Null字符为止，Null字符本身是Non-printable字符，不打印。这其实是一个危险的信号：如果数组str中没有Null字符，那么printf函数就会访问数组越界，后果可能会很诡异：有时候打印出乱码，有时候看起来没错误，有时候引起程序崩溃。

五、多维数组 ​

就像结构体可以嵌套一样，数组也可以嵌套，一个数组的元素可以是另外一个数组，这样就构成了多维数组。例如定义并初始化一个二维数组：

c

int a[3][2] = { 1, 2, 3, 4, 5 };

多维数组也可以像嵌套结构体一样用嵌套Initializer初始化，例如上面的二维数组也可以这样初始化：

c

int a[][2] = { { 1, 2 },
                { 3, 4 },
                { 5, } };

注意，除了第一维的长度可以由编译器自动计算而不需要指定，其余各维都必须明确指定长度。利用C99的新特性也可以做Memberwise Initialization，例如：

c

int a[3][2] = { [0][1] = 9, [2][1] = 8 };

如果是多维字符数组，也可以嵌套使用字符串字面值做Initializer。

和printf类似，scanf也可以用%c、%f、%s等转换说明。如果在传给scanf的第一个参数中用%d、%f或%c表示读入一个整数、浮点数或字符，则第二个参数的形式应该是&运算符加相应类型的变量名，表示读进来的数保存到这个变量中，&运算符的作用是得到一个指针类型；如果在第一个参数中用%s读入一个字符串，则第二个参数应该是数组名，数组名前面不加&，因为数组类型做右值时自动转换成指针类型。

第9章：代码风格 ​

本章我们以内核的代码风格为基础来讲解好的编码风格都有哪些规定，这些规定的Rationale是什么。我只是以Linux内核为例来讲解编码风格的概念，并没有说内核编码风格就一定是最好的编码风格，但Linux内核项目如此成功，就足以说明它的编码风格是最好的C语言编码风格之一了。

一、缩进和空格 ​

基本上所有的C代码风格对于空白字符的规定都差不多，主要有以下几条。

• 关键字if、while、for与其后的控制表达式的(括号之间插入一个空格分隔，但括号内的表达式应紧贴括号。
• 双目运算符的两侧各插入一个空格分隔，单目运算符和操作数之间不加空格。
• 后缀运算符和操作数之间也不加空格，例如取结构体成员s.a、函数调用foo(arg1)、取数组成员a[i]。
• ,号和;号之后要加空格，这是英文的书写习惯。
• 以上关于双目运算符和后缀运算符的规则并没有严格要求，有时候为了突出优先级也可以写得更紧凑一些。
• 由于UNIX系统标准的字符终端是24行80列的，接近或大于80个字符的较长语句要折行写，折行后用空格和上面的表达式或参数对齐。
• 较长的字符串可以断成多个字符串然后分行书写。C编译器会自动把相邻的多个字符串接在一起。
• 有的人喜欢在变量定义语句中用Tab字符，使变量名对齐，这样看起来很美观。内核代码风格关于缩进的规则有以下几条。
  • 要用缩进体现出语句块的层次关系，使用Tab字符缩进，不能用空格代替Tab。在标准的字符终端上一个Tab看起来是8个空格的宽度，如果你的文本编辑器可以设置Tab的显示宽度是几个空格，建议也设成8，这样大的缩进使代码看起来非常清晰。如果有的行用空格做缩进，有的行用Tab做缩进，甚至空格和Tab混用，那么一旦改变了文本编辑器的Tab显示宽度就会看起来非常混乱，所以内核代码风格规定只能用Tab做缩进，不能用空格代替Tab。
  • if/else、while、do/while、for、switch这些可以带语句块的语句，语句块的{或}应该和关键字写在同一行，用空格隔开，而不是单独占一行。
  • 函数定义的{和}单独占一行，这一点和语句块的规定不同。
  • switch和语句块里的case、default对齐写，也就是说语句块里的case、default标号相对于switch不往里缩进，但标号下的语句要往里缩进。用于goto语句的自定义标号应该顶头写不缩进，而不管标号下的语句缩进到第几层。
  • 代码中每个逻辑段落之间应该用一个空行分隔开。例如每个函数定义之间应该插入一个空行，头文件、全局变量定义和函数定义之间也应该插入空行。
  • 一个函数的语句列表如果很长，也可以根据相关性分成若干组，用空行分隔。这条规定不是严格要求，通常把变量定义组成一组，后面加空行，return语句之前加空行。

二、注释 ​

单行注释应采用/*␣comment␣*/的形式，用空格把界定符和文字分开。多行注释最常见的是这种形式：

/*
␣*␣Multi-line
␣*␣comment
␣*/

使用注释的场合主要有以下几种。

• 整个源文件的顶部注释。说明此模块的相关信息，例如文件名、作者和版本历史等，顶头写不缩进。
• 函数注释。说明此函数的功能、参数、返回值、错误码等，写在函数定义上侧，和此函数定义之间不留空行，顶头写不缩进。
• 相对独立的语句组注释。对这一组语句做特别说明，写在语句组上侧，和此语句组之间不留空行，与当前语句组的缩进一致。
• 代码行右侧的简短注释。对当前代码行做特别说明，一般为单行注释，和代码之间至少用一个空格隔开，一个源文件中所有的右侧注释最好能上下对齐。
• 复杂的结构体定义比函数更需要注释。
• 复杂的宏定义和变量声明也需要注释。

三、标识符命名 ​

标识符命名应遵循以下原则：

• 标识符命名要清晰明了，可以使用完整的单词和易于理解的缩写。短的单词可以通过去元音形成缩写，较长的单词可以取单词的头几个字母形成缩写。
• 内核编码风格规定变量、函数和类型采用全小写加下划线的方式命名，常量（比如宏定义和枚举常量）采用全大写加下划线的方式命名。
• 全局变量和全局函数的命名一定要详细，不惜多用几个单词多写几个下划线，因为它们在整个项目的许多源文件中都会用到，必须让使用者明确这个变量或函数是干什么用的。局部变量和只在一个源文件中调用的内部函数的命名可以简略一些，但不能太短。尽量不要使用单个字母做变量名，只有一个例外：用i、j、k做循环变量是可以的。

四、函数 ​

每个函数都应该设计得尽可能简单，简单的函数才容易维护。应遵循以下原则：

• 实现一个函数只是为了做好一件事情，不要把函数设计成用途广泛、面面俱到的，这样的函数肯定会超长，而且往往不可重用，维护困难。
• 函数内部的缩进层次不宜过多，一般以少于4层为宜。如果缩进层次太多就说明设计得太复杂了，应考虑分割成更小的函数来调用。
• 函数不要写得太长，建议在24行的标准终端上不超过两屏，太长会造成阅读困难，如果一个函数超过两屏就应该考虑分割函数了。特别说明，如果一个函数在概念上是简单的，只是长度很长，这倒没关系。例如函数由一个大的switch组成，其中有非常多的case，这是可以的，因为各case分支互不影响，整个函数的复杂度只等于其中一个case的复杂度，这种情况很常见。
• 执行函数就是执行一个动作，函数名通常应包含动词。
• 比较重要的函数定义上侧必须加注释，说明此函数的功能、参数、返回值、错误码等。
• 另一种度量函数复杂度的办法是看有多少个局部变量，5到10个局部变量已经很多了，再多就很难维护了，应该考虑分割成多个函数。

五、indent工具 ​

indent工具可以把代码格式化成某种风格，-kr选项表示K&R风格，-i8表示缩进8个空格的长度。如果没有指定-nut选项，则每8个缩进空格会自动用一个Tab代替。美中不足的是没有添加适当的空行，因为indent工具也不知道哪几行代码在逻辑上是一组的，空行还是要自己动手添，当然原有的空行肯定不会被indent删去的。

第11章：排序与查找 ​

一、算法的概念 ​

算法是将一组输入转化成一组输出的一系列计算步骤，其中每个步骤必须能在有限时间内完成。算法是用来解决一类计算问题的，注意是一类问题，而不是一个特定的问题。

二、插入排序 ​

插入排序算法类似于玩扑克时抓牌的过程，玩家每拿到一张牌都要插入到手中已有的牌里，使之从小到大排好序。

编程对一个数组进行插入排序也是同样道理，但和插入扑克牌有一点不同，不可能在两个相邻的存储单元之间再插入一个单元，因此要将插入点之后的数据依次往后移动一个单元。排序算法如下：

c

#include <stdio.h>

#define LEN 5
int a[LEN] = { 10, 5, 2, 4, 7 };

void insertion_sort(void)
{
	int i, j, key;
	for (j = 1; j < LEN; j++) {
		printf("%d, %d, %d, %d, %d\n",
		       a[0], a[1], a[2], a[3], a[4]);
		key = a[j];
		i = j - 1;
 		while (i >= 0 && a[i] > key) {
			a[i+1] = a[i];
			i--;
		}
		a[i+1] = key;
	}
	printf("%d, %d, %d, %d, %d\n",
	       a[0], a[1], a[2], a[3], a[4]);
}

int main(void)
{
	insertion_sort();
	return 0;
}

三、算法的时间复杂度分析 ​

解决同一个问题可以有很多种算法，比较评价算法的好坏，一个重要的标准就是算法的时间复杂度。

在分析算法的时间复杂度时，我们更关心最坏情况而不是最好情况，理由如下：

• 最坏情况给出了算法执行时间的上界，我们可以确信，无论给什么输入，算法的执行时间都不会超过这个上界，这样为比较和分析提供了便利。
• 对于某些算法，最坏情况是最常发生的情况。
• 虽然最坏情况是一种悲观估计，但是对于很多问题，平均情况和最坏情况的时间复杂度差不多，比如插入排序这个例子，平均情况和最坏情况的时间复杂度都是输入长度n的二次函数。

n的最高次指数是最主要的决定因素，常数项、低次幂项和系数都是次要的。如果同一个问题可以用两种算法解决，其中一种算法的时间复杂度为线性函数，另一种算法的时间复杂度为二次函数，当问题的输入长度n足够大时，前者明显优于后者。因此我们可以用一种更粗略的方式表示算法的时间复杂度，把系数和低次幂项都省去，线性函数记作 $\Theta(n)$，二次函数记作 $\Theta(n^2)$。$\Theta(g(n))$ 表示和 $g(n)$ 同一量级的一类函数，例如所有的二次函数 $f(n)$ 都和 $g(n)=n^2$ 属于同一量级，都可以用 $\Theta(n^2)$ 来表示，甚至有些不是二次函数的也和 $n^2$ 属于同一量级，例如 $2n^2+3lgn$。

几种常见的时间复杂度函数按数量级从小到大的顺序依次是：$\Theta(\lg n)$，$\Theta(\sqrt{n})$，$\Theta(n)$，$\Theta(n\lg n)$，$\Theta(n^2)$，$\Theta(n^3)$，$\Theta(2^n)$，$\Theta(n!)$。其中，$\lg n$ 通常表示以 10 为底 $n$ 的对数，但对于 $\Theta$-notation 来说，$\Theta(\lg n)$ 和 $\Theta(\log_2 n)$ 并无区别，在算法分析中 $\lg n$ 通常表示以 2 为底 $n$ 的对数。

除了 $\Theta$-notation 之外，表示算法的时间复杂度常用的还有一种 Big-O notation。我们知道插入排序在最坏情况和平均情况下时间复杂度是 $\Theta(n^2)$，在最好情况下是 $\Theta(n)$，数量级比 $\Theta(n^2)$ 要小，那么总结起来在各种情况下插入排序的时间复杂度是 $O(n^2)$。$\Theta$ 的含义和“等于”类似，而大 $O$ 的含义和“小于等于”类似。

四、归并排序 ​

归并排序的步骤如下：

• Divide: 把长度为n的输入序列分成两个长度为n/2的子序列。
• Conquer: 对这两个子序列分别采用归并排序。
• Combine: 将两个排序好的子序列合并成一个最终的排序序列。

在描述归并排序的步骤时又调用了归并排序本身，可见这是一个递归的过程。

c

#include <stdio.h>

#define LEN 8
int a[LEN] = { 5, 2, 4, 7, 1, 3, 2, 6 };

void merge(int start, int mid, int end)
{
	int n1 = mid - start + 1;
	int n2 = end - mid;
	int left[n1], right[n2];
	int i, j, k;

	for (i = 0; i < n1; i++) /* left holds a[start..mid] */
		left[i] = a[start+i];
	for (j = 0; j < n2; j++) /* right holds a[mid+1..end] */
		right[j] = a[mid+1+j];

	i = j = 0;
	k = start;
	while (i < n1 && j < n2)
		if (left[i] < right[j])
			a[k++] = left[i++];
		else
			a[k++] = right[j++];

	while (i < n1) /* left[] is not exhausted */
		a[k++] = left[i++];
	while (j < n2) /* right[] is not exhausted */
		a[k++] = right[j++];
}

void sort(int start, int end)
{
	int mid;
	if (start < end) {
		mid = (start + end) / 2;
		printf("sort (%d-%d, %d-%d) %d %d %d %d %d %d %d %d\n", 
		       start, mid, mid+1, end, 
		       a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]);
		sort(start, mid);
		sort(mid+1, end);
		merge(start, mid, end);
		printf("merge (%d-%d, %d-%d) to %d %d %d %d %d %d %d %d\n", 
		       start, mid, mid+1, end, 
		       a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]);
	}
}

int main(void)
{
	sort(0, LEN-1);
	return 0;
}

首先分析merge函数的时间复杂度。在merge函数中演示了C99的新特性———可变长数组，当然也可以避免使用这一特性，比如把left和right都按最大长度LEN分配。不管用哪种办法，定义数组并分配存储空间的执行时间都可以看作常数，与数组的长度无关，常数用 $\Theta$-notation 记作 $\Theta(1)$。设子序列a[start..mid]的长度为n1，子序列a[mid+1..end]的长度为n2，a[start..end]的总长度为 $n=n1+n2$，则前两个for循环的执行时间是 $\Theta(n1+n2)$，也就是 $\Theta(n)$，后面三个while循环合在一起看，每走一次循环就会在最终的排序序列中确定一个元素，最终的排序序列共有n个元素，所以执行时间也是 $\Theta(n)$。两个 $\Theta(n)$ 再加上若干常数项，merge函数总的执行时间仍是 $\Theta(n)$，其中 $n=end-start+1$。

然后分析 sort 函数的时间复杂度：

• 当输入长度 n = 1，即 start == end 时，if 条件不成立，执行时间为常数 O(1)。
• 当输入长度 n > 1 时：

总的执行时间 = 2 × 输入长度为 n/2 的 sort 函数的执行时间 + merge 函数的执行时间 O(n)。

设输入长度为 n 的 sort 函数的执行时间为 $T(n)$，综上所述：

$$T(n) = \begin{cases} \Theta(1) & \text{if } n = 1, \\[6pt] 2T(n/2) + \Theta(n) & \text{if } n > 1. \end{cases}$$

这是一个递推公式，我们需要消去符号右侧的 $T(n)$，把 $T(n)$ 写成 n 的函数。

其实符合一定条件的递推的展开有数学公式可以套，这里我们略去严格的数学证明，只是从直观上看一下这个递推公式的结果。

当 n = 1 时可以设 $T(1) = c_1$，当 n > 1 时可以设 $T(n) = 2T(n/2) + c_2n$。我们取 $c_1$ 和 $c_2$ 中较大的一个设为 $c$，把原来的公式改为：

$$T(n) = \begin{cases} c & \text{if } n = 1, \\[6pt] 2T(n/2) + cn & \text{if } n > 1. \end{cases}$$

这样计算的结果应该是 $T(n)$ 的上界。

下面我们把 $T(n/2)$ 展开成 $2T(n/4) + cn/2$，然后再把 $T(n/4)$ 进一步展开，直到最后全部变成 $T(1) = c$。 把所有的项加起来就是总的执行时间。这是一个树状结构，每一层的和都是 $cn$，共有 $lgn+1$ 层，因此总的执行时间是 $cnlgn+cn$，相比 $nlgn$ 来说，$cn$ 项可以忽略，因此 $T(n)$ 的上界是 $\Theta(nlgn)$。

和插入排序的平均情况相比归并排序更快一些，虽然merge函数的步骤较多，引入了较大的常数、系数和低次项，但是对于较大的输入长度n，这些都不是主要因素，归并排序的时间复杂度是 $\Theta(nlgn)$，而插入排序的平均情况是 $\Theta(n^2)$，这就决定了归并排序是更快的算法。

当然，并不是所有情况下归并排序都优于插入排序，在数据本身基本有序的情况下，插入排序的时间复杂度可以降低为 $\Theta(n)$。

习题1：快速排序是另外一种采用分而治之策略的排序算法，在平均情况下的时间复杂度也是 $\Theta(nlgn)$，但比归并排序有更小的时间常数。它的基本思想是这样的：

c

int partition(int start, int end)
{
	从a[start..end]中选取一个pivot元素（比如选a[start]为pivot）;
	在一个循环中移动a[start..end]的数据，将a[start..end]分成两半，
	使a[start..mid-1]比pivot元素小，a[mid+1..end]比pivot元素大，而a[mid]就是pivot元素;
	return mid;
}

void quicksort(int start, int end)
{
	int mid;
	if (end > start) {
		mid = partition(start, end);
		quicksort(start, mid-1);
		quicksort(mid+1, end);
	}
}

请补完partition函数，这个函数有多种写法，请选择时间常数尽可能小的实现方法。想想快速排序在最好和最坏情况下的时间复杂度是多少？

首先给出补充后的partition函数，之后分析时间复杂度。

int partition(int start, int end)
{
    int i = start;
    int pivot = a[start];
    int tmp;
    int j;

    for (j = start + 1; j <= end; j++){
        if (a[j] < pivot){
            i++;
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }

    tmp = a[i];
    a[i] = a[start];
    a[start] = tmp;
    
    return i;
}

在快速排序中，最好的情况是每次都将数组分成均等的两部分，则类似于归并排序，时间复杂度为 $\Theta(nlgn)$；最坏的情况则是每次都将数组分成一组有n个数，另一组没有数，在这种条件下 $T(n)=T(n-1)+\Theta(n)$，展开后得到时间复杂度为 $\Theta(n^2)$。

五、线性查找 ​

习题1：实现一个算法，在一组随机排列的数中找出最小的一个。你能想到的最直观的算法一定是 $\Theta(n)$ 的，想想有没有比 $\Theta(n)$ 更快的算法？

实现的算法如下：

#include <stdio.h>

#define LEN 8
int a[LEN] = { 5, 2, 4, 7, 1, 3, 2, 6 };

int min(int start, int end )
{
    int i;
    int min = a[start];
    for (i = start + 1; i <= end; i++){
        if (a[i] < min)min = a[i];
    }
    return min;
}

int main()
{
    int x;
    x = min(0,7);
    printf("数组中最小的数是：%d\n",x);

    return 0;
}

很容易的可以得到这个算法的时间复杂度是 $\Theta(n)$，但是有没有更快的算法呢？实际上，由于要从整个数组中找出最小的那一个，一定需要遍历整个数组，因此没有比 $\Theta(n)$ 更快的算法了。

习题2：在一组随机排列的数中找出第二小的，这个问题比上一个稍复杂，你能不能想出 $\Theta(n)$ 的算法？

当然可以，最简单的思路就是第一次遍历找出最小值，第二次遍历找到第二小值，时间复杂度是 $\Theta(n)$，接下来给出一个更快的算法，虽然时间复杂度同样是 $\Theta(n)$，但是只需要一次遍历。

#include <stdio.h>

#define LEN 8
int a[LEN] = { 5, 2, 4, 7, 1, 3, 2, 6 };

int second_min(int start, int end )
{
    int i;
    int min = a[start];
    int second_min = a[start];
    for (i = start + 1; i <= end; i++){
        if (a[i] < min){
            second_min = min;
            min = a[i];
        }
        if (a[i] < second_min && a[i] > min)second_min = a[i];
    }
    return second_min;
}

int main()
{
    int x,y;
    x = second_min(0,7);
    printf("数组中第二小的数是：%d\n",x);

    return 0;
}

习题3：进一步泛化，在一组随机排列的数中找出第k小的，这个元素称为k-th Order Statistic。能想到的最直观的算法肯定是先把这些数排序然后取第k个，时间复杂度和排序算法相同，可以是 $\Theta(nlgn)$。这个问题虽然比前两个问题复杂，但它也有平均情况下时间复杂度是 $\Theta(n)$ 的算法，将上一节习题1的快速排序算法稍加修改就可以解决这个问题：

c

/* 从start到end之间找出第k小的元素 */
int order_statistic(int start, int end, int k)
{
	用partition函数把序列分成两半，中间的pivot元素是序列中的第i个;
	if (k == i)
		返回找到的元素;
	else if (k > i)
		从后半部分找出第k-i小的元素并返回;
	else
		从前半部分找出第k小的元素并返回;
}

请编程实现这个算法。

算法的实现如下：

#include <stdio.h>

#define LEN 8
int a[LEN] = { 5, 2, 4, 7, 1, 3, 8, 6 };

int partition(int start, int end)
{
    int i = start;
    int pivot = a[start];
    int tmp;
    int j;

    for (j = start + 1; j <= end; j++){
        if (a[j] < pivot){
            i++;
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }

    tmp = a[i];
    a[i] = a[start];
    a[start] = tmp;
    
    return i;
}

int order_statistic(int start, int end, int k)
{
	int i;
    int pos;
    i = partition(start,end);
    pos = i - start + 1;
    if (k == pos)return a[i];
    else if (k > pos){
        return order_statistic(i + 1, end, k - pos);
    }
    else return order_statistic(start, i - 1, k);
}

int main()
{
    int x,y;
    x = order_statistic(0,7,4);
    printf("数组中第4小的数是：%d\n",x);

    return 0;
}

六、折半查找 ​

如果不是从一组随机的序列里查找，而是从一组排好序的序列里找出某个元素的位置，则可以有更快的算法：

c

#include <stdio.h>

#define LEN 8
int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 };

int binarysearch(int number)
{
	int mid, start = 0, end = LEN - 1;

	while (start <= end) {
		mid = (start + end) / 2;
		if (a[mid] < number)
			start = mid + 1;
		else if (a[mid] > number)
			end = mid - 1;
		else
			return mid;
	}
	return -1;
}

int main(void)
{
	printf("%d\n", binarysearch(5));
	return 0;
}

由于这个序列已经从小到大排好序了，每次取中间的元素和待查找的元素比较，如果中间的元素比待查找的元素小，就说明“如果待查找的元素存在，一定位于序列的后半部分”，这样可以把搜索范围缩小到后半部分，然后再次使用这种算法迭代。这种“每次将搜索范围缩小一半”的思想称为折半查找。思考一下，这个算法的时间复杂度是多少？

这个算法最好的情况是在第一次寻找时就找到了待查找的元素，则时间复杂度是 $\Theta(1)$；如果考虑最坏的情况，即需要一直将数组折半查找，这种情况下的时间复杂度是 $\Theta(lgn)$。

assert是头文件assert.h中的一个宏定义，执行到assert(is_sorted())这句时，如果is_sorted()返回值为真，则当什么事都没发生过，继续往下执行，如果is_sorted()返回值为假（例如把数组的排列顺序改一改），则报错退出程序。在代码中适当的地方使用断言（Assertion）可以有效地帮助我们测试程序。测试代码只在开发和调试时有用，如果正式发布（Release）的软件也要运行这些测试代码就会严重影响性能了，如果在包含assert.h之前定义一个NDEBUG宏（表示No Debug），就可以禁用assert.h中的assert宏定义，这样代码中的所有assert测试都不起作用了。

#define NDEBUG
#include <stdio.h>
#include <assert.h>
...

注意NDEBUG和我们以前使用的宏定义有点不同，例如#define N 20将N定义为20，在预处理时把代码中所有的标识符N替换成20，而#define NDEBUG把NDEBUG定义为空，在预处理时把代码中所有的标识符NDEBUG替换成空。这样的宏定义主要是为了用#ifdef等预处理指示测试它定义过没有，而不是为了做替换，所以定义成什么值都无所谓，一般定义成空就足够了。还有另一种办法，不必修改源文件，在编译命令行加上选项-DNDEBUG就相当于在源文件开头定义了NDEBUG宏。

习题1：本节的折半查找算法有一个特点：如果待查找的元素在数组中有多个则返回其中任意一个，以本节定义的数组int a[8] = { 1, 2, 2, 2, 5, 6, 8, 9 };为例，如果调用binarysearch(2)则返回3，即a[3]，而有些场合下要求这样的查找返回a[1]，也就是说，如果待查找的元素在数组中有多个则返回第一个。请修改折半查找算法实现这一特性。

最简单的想法即当找到一个元素后，记录它的位置后向左继续寻找，直到循环结束，则最后记录的位置即需要返回的位置。

#include <stdio.h>

#define LEN 8
int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 };

int binarysearch(int number)
{
	int mid, start = 0, end = LEN - 1;
    int result = -1;

	while (start <= end) {
		mid = (start + end) / 2;
		if (a[mid] < number)
			start = mid + 1;
		else if (a[mid] > number)
			end = mid - 1;
		else {
            result = mid;
            end = mid - 1;
            }
    };
	
	return result;
}

int main(void)
{
	printf("%d\n", binarysearch(2));
	return 0;
}

习题2：编写一个函数double mysqrt(double y);求y的正平方根，参数y是正实数。我们用折半查找来找这个平方根，在从0到y之间必定有一个取值是y的平方根，如果我们查找的数x比y的平方根小，则 $x^2<y$，如果我们查找的数x比y的平方根大，则 $x^2>y$，我们可以据此缩小查找范围，当我们查找的数足够准确时（比如满足 $|x^2-y|<0.001$），就可以认为找到了y的平方根。思考一下这个算法需要迭代多少次？迭代次数的多少由什么因素决定？

首先题目实际思路稍微有一点问题，因为当y<1的时候，y的正平方根实际大于y，因此此时0到1之间必定有一个取值是y的平方根。而且由于浮点数的精度问题，终止条件应该设为固定循环若干周期。这个算法的迭代次数与y的大小和定义的精度有关，且成对数关系。实现的程序如下：

#include <stdio.h>

double mysqrt(double y)
{
    double x;
    double start,end,mid;
    int i;

    start = 0;
    end = (y > 1 ? y : 1);

    for (i = 0; i < 1000; i++){
        x = (start + end) / 2;
		if (x * x - y > 0.001)
			end = x;
		else if (x * x - y < -0.001)
			start = x;
		else
			return x;            
    }
    return x;
}

int main(){
    double result;
    result = mysqrt(0.25);
    printf("%f\n",result);

    return 0;
}

习题3：编写一个函数double mypow(double x, int n);求x的n次方，参数n是正整数。最简单的算法是：

c

double product = 1;
for (i = 0; i < n; i++)
	product *= x;

这个算法的时间复杂度是 $\Theta(n)$。其实有更好的办法，比如mypow(x, 8)，第一次循环算出 $x \cdot x=x^2$，第二次循环算出 $x^2 \cdot x^2=x^4$，第三次循环算出 $x^4 \cdot x^4=x^8$。这样只需要三次循环，时间复杂度是 $\Theta(lgn)$。思考一下如果n不是2的整数次幂应该怎么处理。请分别用递归和循环实现这个算法。

首先是递归版的程序，如果是偶数，每次将n拆成一半进行递归计算；如果n是奇数，则再额外乘以一个x。

#include <stdio.h>

double mypow(double x, int n)
{
    double result;
    double half;

    if (n == 0){
        return 1;
    }
    else if (n % 2 == 0){
        half = mypow(x,n/2);
        result = half * half;
        return result;
    }
    else if (n % 2 != 0){
        half = mypow(x,(n-1)/2);
        result = x * half * half;
        return result;
    }
    return 0;
}

int main()
{
    double result;
    result = mypow(2,5);
    printf("%f",result);
}

接下来用循环实现，在循环中，判断幂指数是否为偶数，若是偶数，将x变为 $x^2$，之后将n折半，如果是奇数，则让结果乘以x后同样将n折半。由于C语言中n/2默认取下限，所以无论n是奇数还是偶数都不会出现问题。

#include <stdio.h>

double mypow(double x, int n)
{
    double result = 1;
    
    while (n > 0){
        if(n % 2 == 1){
            result = result * x;
        }
        x = x * x;
        n = n/2;
    }
    return result;
}

int main()
{
    double result;
    result = mypow(2,5);
    printf("%f",result);
}

第12章：栈与队列 ​

一、数据结构的概念 ​

数据结构（Data Structure）是数据的组织方式。程序中用到的数据都不是孤立的，而是有相互联系的，根据访问数据的需求不同，同样的数据可以有多种不同的组织方式。以前学过的复合类型也可以看作数据的组织方式，把同一类型的数据组织成数组，或者把描述同一对象的各成员组织成结构体。数据的组织方式包含了存储方式和访问方式这两层意思，二者是紧密联系的。例如，数组的各元素是一个挨一个存储的，并且每个元素的大小相同，因此数组可以提供按下标访问的方式，结构体的各成员也是一个挨一个存储的，但是每个成员的大小不同，所以只能用.运算符加成员名来访问，而不能按下标访问。

二、堆栈 ​

堆栈是一组元素的集合，类似于数组，不同之处在于，数组可以按下标随机访问，这次访问a[5]下次可以访问a[1]，但是堆栈的访问规则被限制为Push和Pop两种操作，Push（入栈或压栈）向栈顶添加元素，Pop（出栈或弹出）则取出当前栈顶的元素，也就是说，只能访问栈顶元素而不能访问栈中其它元素。如果所有元素的类型相同，堆栈的存储也可以用数组来实现，访问操作可以通过函数接口提供。看以下的示例程序。

c

#include <stdio.h>
 
char stack[512];
int top = 0;

void push(char c)
{
	stack[top++] = c;
}

char pop(void)
{
	return stack[--top];
}

int is_empty(void)
{
	return top == 0;
}

int main(void)
{
	push('a');
	push('b');
	push('c');
	
	while(!is_empty())
		putchar(pop());
	putchar('\n');

	return 0;
}

数组stack是堆栈的存储空间，变量top总是保存数组中栈顶的下一个元素的下标，我们说“top总是指向栈顶的下一个元素”，或者把top叫做栈顶指针（Pointer）。 Pop操作的语义是取出栈顶元素，但上例的实现其实并没有清除原来的栈顶元素，只是把top指针移动了一下，原来的栈顶元素仍然存在那里，这就足够了，因为此后通过Push和Pop操作不可能再访问到已经取出的元素，下次Push操作就会覆盖它。putchar函数的作用是把一个字符打印到屏幕上，和printf的%c作用相同。布尔函数is_empty的作用是防止Pop操作访问越界。这里我们预留了足够大的栈空间（512个元素），其实严格来说Push操作之前也应该检查栈是否满了。

在main函数中，入栈的顺序是'a'、'b'、'c'，而出栈打印的顺序却是'c'、'b'、'a'，最后入栈的'c'最早出来，因此堆栈这种数据结构的特点可以概括为LIFO（Last In First Out，后进先出）。我们也可以写一个递归函数做倒序打印，利用函数调用的栈帧实现后进先出：

c

#include <stdio.h>
#define LEN 3

char buf[LEN]={'a', 'b', 'c'};

void print_backward(int pos)
{
     if(pos == LEN)
	       return;
     print_backward(pos+1);
     putchar(buf[pos]);
}

int main(void)
{
     print_backward(0);
     putchar('\n');
     
     return 0;
}

三、深度优先搜索 ​

每次探索完各个方向相邻的点之后，取其中一个相邻的点走下去，一直走到无路可走了再退回来，取另一个相邻的点再走下去。这称为深度优先搜索（DFS，Depth First Search）。

有什么样的数据结构就决定了可以用什么样的算法。从DFS算法的过程可以看出，虽然每个点的前趋只有一个，后继却不止一个，如果我们为每个点只保存一个后继，则无法保证这个后继指向正确的路线。设计算法和设计数据结构这两件工作是紧密联系的。

习题1：修改本节的程序，要求从起点到终点正向打印路线。你能想到几种办法？

首先第一种方法比较简单，本节给出的程序是倒着走的同时进行打印，当然我们也可以定义一个数组，用于存储p的行动轨迹，之后倒序打印即可。修改后的整个程序如下，程序中保留了本节最初的代码，用于比较倒序打印的结果是否正确。

#include <stdio.h>

#define MAX_ROW 5
#define MAX_COL 5

struct point { int row, col; } stack[512];
int top = 0;

struct point path[512];
int i = 0;
int j;

void push(struct point p)
{
	stack[top++] = p;
}

struct point pop(void)
{
	return stack[--top];
}

int is_empty(void)
{
	return top == 0;
}

int maze[MAX_ROW][MAX_COL] = {
	0, 1, 0, 0, 0,
	0, 1, 0, 1, 0,
	0, 0, 0, 0, 0,
	0, 1, 1, 1, 0,
	0, 0, 0, 1, 0,
};

void print_maze(void)
{
	int i, j;
	for (i = 0; i < MAX_ROW; i++) {
		for (j = 0; j < MAX_COL; j++)
			printf("%d ", maze[i][j]);
		putchar('\n');
	}
	printf("*********\n");
}

struct point predecessor[MAX_ROW][MAX_COL] = {
	{{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
	{{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
	{{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
	{{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
	{{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
};

void visit(int row, int col, struct point pre)
{
	struct point visit_point = { row, col };
	maze[row][col] = 2;
	predecessor[row][col] = pre;
	push(visit_point);
}

int main(void)
{
	struct point p = { 0, 0 };

	maze[p.row][p.col] = 2;
	push(p);	
	
	while (!is_empty()) {
		p = pop();
		if (p.row == MAX_ROW - 1  /* goal */
		    && p.col == MAX_COL - 1)
			break;
		if (p.col+1 < MAX_COL     /* right */
		    && maze[p.row][p.col+1] == 0)
			visit(p.row, p.col+1, p);
		if (p.row+1 < MAX_ROW     /* down */
		    && maze[p.row+1][p.col] == 0)
			visit(p.row+1, p.col, p);
		if (p.col-1 >= 0          /* left */
		    && maze[p.row][p.col-1] == 0)
			visit(p.row, p.col-1, p);
		if (p.row-1 >= 0          /* up */
		    && maze[p.row-1][p.col] == 0)
			visit(p.row-1, p.col, p);
		print_maze();
	}
	if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) {
		printf("(%d, %d)\n", p.row, p.col);
		while (predecessor[p.row][p.col].row != -1) {
            path[i] = p;
			p = predecessor[p.row][p.col];
			printf("(%d, %d)\n", p.row, p.col);
            i++;
		}
        printf("\n");
        for (j = i; j >= 0; j--){
            printf("(%d, %d)\n", path[j].row, path[j].col);
        }
	} else
		printf("No path!\n");

	return 0;
}