从头学C(5): 函数与程序结构
对于代码的易读性、程序结构的清晰等方面，函数都发挥着重要的作用。它可以把大的计算任务分解成若干个较小的任务，同时还可以做到代码复用，隐藏操作细节，大大降低程序修改的难度。
可以说，C语言程序一般都是由许多小的函数组成，而不是少量庞大的函数组成。
第四章 函数与程序结构
4.1 函数的基本结构
在前面的章节中，我们已经学习了函数的一些基本知识。比如目前C语言允许在声明函数时同时声明参数的类型，这样编译器就有可能检测出声明与定义类型不一致等等错误；如果参数声明得当，程序还可以自动进行强制类型转换。
首先来设计一个程序：给定多行字符串，从里面查找包含特定“模式”或特定“字符串”的行，并将找到的这些行打印出来。
因此，我们可以将程序按如下思路设计：
while(还有未处理的行)
if(该行包含指定的字符串)
打印该行
虽然我们可以把所有代码都放到主程序main中，但更合适的做法是将上面三部分都设计成一个独立的函数，这样的程序结构显然更清晰简洁，而且这三个独立的函数还可提供给其他程序进行复用，方便开发其他类似的程序。
“还有未处理的行”可以用函数getline()来实现，这个函数可以从第一章中拿来借鉴。
“该行包含指定的字符串”用函数strindex(s,t)来实现，需要我们自己来编写。该函数返回字符串t在字符串s中出现的起始位置或索引(index)。当s不包含t时，程序返回 -1，因此可以用这个值来表示失败的情况。
“打印该行”可以直接用printf()函数实现，这个函数我们前面已经用了很多次了。
有了思路，程序实现就应该是下面这个样子了：
#include <stdio.h>
#define MAXLINE 1000 /* maximum input line length */
int my_getline(char line[], int max);
int strindex(char source[], char searchfor[]);
char pattern[] = "ould"; /* pattern to search for */
/* find all lines matching pattern */
main()
{
char line[MAXLINE];
int found = 0;
while (my_getline(line, MAXLINE) > 0)
if (strindex(line, pattern) >= 0) {
printf("%s", line);
found ++;
}
return found;
}
/* my_getline: get line into s, return length */
int my_getline(char s[], int lim)
{
int c, i;
i = 0;
while (--lim > 0 && (c=getchar()) != EOF && c != '\n')
s[i++] = c;
if (c == '\n')
s[i++] = c;
s[i] = '\0';
return i;
}
/* strindex: return index of t in s, -1 if none */
int strindex(char s[], char t[])
{
int i, j, k;
for (i = 0; s[i] != '\0'; i++) {
for (j=i, k=0; t[k]!='\0' && s[j]==t[k]; j++, k++)
;
if (k > 0 && t[k] == '\0')
return i;
}
return -1;
}
函数的定义形式：
返回值类型 函数名(参数声明列表)
{
声明和语句
}
以上除了函数名，其他部分都可以省略。
如果省略了“返回值类型”，则默认返回值类型是
int。
被调用的函数通过return语句向调用者返回值，return后面可以跟任何表达式：
return 表达式;
有几个地方要注意：
- 必要时，表达式会被转换为函数声明的返回值类型；
- 调用函数也可以忽略返回值；
return语句中的表达式也可以忽略（如果return语句后面没有表达式，函数将不会向调用者返回任何值）。
上面的main函数返回了一个状态，即匹配的行数，该返回值可以给调用本程序的环境使用。
4.2 返回非整型值的函数
函数的返回值并非只有void或int型。
【返回值为 double 的 atof() 函数】
来看个atof(s)函数，该函数用于把字符串s转换为相应的双精度浮点数。
标准库
<stdlib.h>中包含了类似功能的atof()函数）。
#include <stdio.h>
#include <ctype.h>
#define MAXLINE 100
double atof(char []);
int my_getline(char line[], int max);
/* rudimentary calculator */
int main()
{
double sum;
char line[MAXLINE];
sum = 0;
while (my_getline(line, MAXLINE) > 0)
printf("\t%g\n", sum += atof(line));
return 0;
}
/* atof: convert string s to double */
double atof(char s[])
{
double val, power;
int i, sign;
for (i = 0; isspace(s[i]); i++) /* skip white space */
;
sign = (s[i] == '-') ? -1 : 1;
if (s[i] == '+' || s[i] == '-')
i++;
for (val = 0.0; isdigit(s[i]); i++)
val = 10.0 * val + (s[i] - '0');
if (s[i] == '.')
i++;
for (power = 1.0; isdigit(s[i]); i++) {
val = 10.0 * val + (s[i] - '0');
power *= 10;
}
return sign * val / power;
}
/* my_getline: get line into s, return length */
int my_getline(char s[], int lim)
{
int c, i;
i = 0;
while (--lim > 0 && (c=getchar()) != EOF && c != '\n')
s[i++] = c;
if (c == '\n')
s[i++] = c;
s[i] = '\0';
return i;
}
显然atof()函数的返回值应当是double型，因此，我们在程序的开头位置就显式的声明了函数的返回值是double，且有一个 char []类型的参数。而在atof()函数定义的地方，我们也是与函数声明保持了相同的返回值类型和参数类型。
需要特别说明的是：atof()函数的声明和定义必须一致。这是因为：
- 如果
atof()函数和调用它的主函数main()在同一个源文件中编译，并且声明与定义的类型不一致，则编译器能检测到该错误； - 如果
atof()函数是单独编译，那这种函数声明与定义不匹配的错误，就无法被检测出来。这种情况下，atof()返回double结果，而main()却将返回值当成int型处理，最后的结果将毫无意义。
实际编程中，恰恰是第 2 种情况更容易发生……
【参数为空的函数声明】
如果函数声明中不包含参数，例如：
double atof();
则编译器不会对atof()函数的参数做任何假设，同时关闭所有的参数检查。对空参数列表的这种特殊处理是为了使新的编译器能编译比较老的C语言程序。
不过在新的C语言程序中，我们提倡的是：如果函数带参数，则要声明它们；如果不带参数，则使用
void声明。
【基于 atof() 的 atoi() 函数】
在正确声明的函数atof基础上，我们可以利用它快速编写函数atoi（将字符串转化为int类型）：
/* atoi: convert string s to integer using atof */
int atoi(char s[])
{
double atof(char s[]);
return (int) atof(s);
}
其中atof(s)的值在返回前，进行了强制类型转换，转换成了int类型（和atoi函数的返回值类型一致）。
如果把上面的return语句改成：
return atof(s);
那么由于atoi函数的返回值类型是int型，因此atof(s)的返回值double类型会被自动转换为int类型值，这种操作可能会丢失信息。某些编译器可能会对此给出警告信息。（前者由于显式的进行了类型转换，明确所要进行的转换操作，因此不会出现警告信息）
4.3 外部变量
C语言不允许在函数中定义其他函数，可以认为函数都是“外部的”。那么，外部变量和函数具有相同的性质：通过同一个名字对外部变量的引用实际上都是引用了同一个对象（标准中把这一性质称为外部链接）。
由于这个性质，在不同函数之间，可以利用外部变量进行数据交换，而不是通过调用函数时传递参数来实现。显然，当需要交换的数据比较复杂时，直接使用外部变量要比传递一长串参数更方便、有效。
外部变量的另一个好处是：它比内部变量具有更大的作用域和更长的生存期。我们已经知道，自动变量只能在函数内部使用（从其所在的函数被调用时变量开始存在，在函数退出时变量消失），而外部变量是永久存在的（它们的值在一次函数调用到下一次函数调用之间保持不变，这也是为什么外部变量可以作为共享数据，给不同函数使用的原因）。
下面通过一个更复杂的例子来说明。目标是编写一个具有加、减、乘、除四则运算功能的计算器程序，为了方便实现，使用逆波兰表示法代替普通的中缀表达式。
在逆波兰表示法中，所有运算符都跟在操作数后面。比如：
中缀表达式：(1 - 2) * (4 + 5)
逆波兰表示法： 1 2 - 4 5 + *
逆波兰表示法是不需要括号的，只需知道每个操作符需要几个操作数就不会引起歧义。
书本中的程序使用到了栈的概念。计算器程序的流程大致是：
- 当操作数到达时，压入栈中；
- 当运算符到达时，从栈中弹出相应数量的操作数（比如二元运算符需要用到两个操作数，就需要依次弹出两个操作数），然后进行运算，将结果再压入栈中；
- 依此类推……；
- 当到达输入行的末尾时，说明计算已完成，把栈顶的值弹出并打印，便是最终结果。
程序的设计如下：
while(下一个运算符或操作数不是文件结束符EOF)
if(是操作数)
将该数压入栈中
else if(是运算符)
弹出所需数目的操作数
计算结果
将结果压入栈中
else if(是换行符)
弹出并打印栈顶的值
else
出错
从流程分析，栈的弹出和压入操作我们可以设计成独立的函数，另外还需要一个读取下一个运算符或操作数的独立函数。
对main来说，它并不关心栈的具体细节（比如栈存放在哪？），只需要知道数据可以push进去，再pop出来即可。因此可以把栈及相关信息放在外部变量中，只供push和pop函数访问，而不会被main函数访问。
这里我们把该程序分割成了 4 个源文件。依次是
- main.c
#include <stdio.h>
#include <stdlib.h> /* for atof() */
#define MAXOP 100 /* max size of operand or operator */
#define NUMBER '0' /* signal that a number was found */
extern int getop(char []);
extern void push(double);
extern double pop(void);
/* reverse Polish calculator */
int main()
{
int type;
double op2;
char s[MAXOP];
printf("please input the calculation expression: ");
while ((type = getop(s)) != EOF) {
switch (type) {
case NUMBER:
push(atof(s));
break;
case '+':
push(pop() + pop());
break;
case '*':
push(pop() * pop());
break;
case '-':
op2 = pop();
push(pop() - op2);
break;
case '/':
op2 = pop();
if (op2 != 0.0)
push(pop() / op2);
else
printf("error: zero divisor\n");
break;
case '\n':
printf("output = %.8g\n", pop());
break;
default:
printf("error: unknown command %s\n", s);
break;
}
}
return 0;
}
对于加法和乘法，操作数的弹出顺序无关紧要；但对于减法和除法，运算符左右操作数必须要注意。因此上面的程序是先将右操作数弹出到一个临时变量中，再弹出左操作数进行运算，而不是采用类似下面的这种做法：
push(pop() - pop()); /* 错误 */
因为在上面这个函数调用中，并没有定义两个 pop 调用的求值次序。
- pop_push.c
#include <stdio.h>
#define MAXVAL 100 /* maximum depth of val stack */
int sp = 0; /* next free stack position */
double val[MAXVAL]; /* value stack */
/* push: push f onto value stack */
void push(double f)
{
if (sp < MAXVAL)
val[sp++] = f;
else
printf("error: stack full, can't push %g\n", f);
}
/* pop: pop and return top value from stack */
double pop(void)
{
if (sp > 0)
return val[--sp];
else {
printf("error: stack empty\n");
return 0.0;
}
}
push和pop函数都要用到共享的栈和栈顶指针，因此这两个变量放在了函数外部，定义成外部变量。而同时main函数并不关心栈的引用以及栈顶指针sp的信息，因此将栈的细节放在这个源文件中，对main函数而言，它们是隐藏的（我们会在下一节中分析这个）。
- getop.c
#include <stdio.h>
#include <ctype.h>
#define NUMBER '0' /* signal that a number was found */
extern int getch(void);
extern int ungetch(int);
/* getop: get next character or numeric operand */
int getop(char s[])
{
int i, c;
while ((s[0] = c = getch()) == ' ' || c == '\t')
;
s[1] = '\0';
if (!isdigit(c) && c!= '.')
return c; /* not a number */
i = 0;
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;
}
这个函数比较简单，获取操作数时包含了对浮点数的支持。
- getch_ungetch.c
#include <stdio.h>
#define BUFSIZE 100
char buf[BUFSIZE]; /* buffer for ungetch */
int bufp = 0; /* next free position in buf */
/* get a (possibly pushed-back) character */
int getch(void)
{
return (bufp > 0) ? buf[--bufp] : getchar();
}
/* push character back on input */
void ungetch(int c)
{
if (bufp >= BUFSIZE)
printf("ungetch: too many characters\n");
else
buf[bufp++] = c;
}
getch和ungetch函数主要是因为程序不能确定一个操作数是否读完（比如1.2需要读 3 个字符），因此需要预先读取下一个字符来判断是否读取完整了。而正是由于预先读取了下一个字符，会导致下一轮读取操作数会出现异常，因此需要将这个预先读取的下一个字符再放回原来的缓冲区中，以供下一轮的读取操作。
由于缓冲区和下标变量是供getch和ungetch共享的，所以它们也是被定义成了外部变量。
最后，编译命令如下：
gcc main.c pop_push.c getop.c getch_ungetch.c
执行编译后的程序，并输入上面的逆波兰表达式，可以得到下面的结果：
please input the calculation expression: 1 2 - 4 5 + *
output = -9
4.4 作用域规则
名字的作用域是指程序中可以使用该名字的部分。
对于在函数开头位置声明的自动变量（局部变量）来说，它的作用域是声明该变量名的函数。所以，不同函数内声明的同名变量之间是没有任何关系的。包括函数的参数，也可以把它看做是局部变量。
对于外部变量或函数，它们的作用域是从声明它的地方开始，到其所在的（待编译的）源文件的末尾结束。
如果在同一个源文件中，按如下顺序依次定义：
main() {......}
int sp = 0;
double val[MAXVAL];
void push(double f) {......}
double pop() {......}
那么push和pop函数可以直接访问变量sp和val[MAXVAL]，但是main既不可以访问这两个变量，也不能访问push和pop。
而在上一节中，因为变量sp和val[MAXVAL]都是在pop_push.c中定义的外部变量（它们的作用域也仅限于pop_push.c），main.c 没有声明这两个变量，因此main函数不能访问这两个变量。
当然，可以通过在main.c中使用关键字extern来声明这两个变量，则main函数便可访问这两个变量了。（虽然我们可以这么做，但如前所说，栈的细节我们在main函数中并不关注）
声明和定义的概念一定要区分开：
- 变量声明用于说明变量的属性（主要是变量类型）；
- 变量定义除了说明变量的属性，还将引起存储器的空间分配。
如果将下列语句放在所有函数外部：
int sp;
double val[MAXVAL];
那么这两条语句将定义外部变量sp和val，并为它们分配存储单元，同时作为该源文件中其余部分的变量声明。
而下面这两条语句：
extern int sp;
extern double val[];
则为源文件的其余部分声明了一个int型变量及一个double数组类型的外部变量val（数组长度在其他地方定义），但这两条语句也仅仅也只是声明而已，并没有为它们建立变量或分配存储空间。
另外还需要注意的地方是：
- 在一个程序的所有源文件中，一个外部变量只能在某个文件中被定义一次，其他文件可以通过
extern声明访问它们； - 外部变量的定义中必须指定数据长度，但
extern声明可以不用指定具体长度； - 外部变量的初始化只能出现在其定义中。
4.5 头文件
在《4.3 外部变量》章节中，我们将计算器的程序分割成了多个文件，这么做一方面是程序可以对main函数隐藏很多实现的细节，另一方面也是考虑到在实际的程序中，它们各个部分可能分别来自单独编译的库（模块化开发）。
然而我们需要在main.c以及getop.c中使用extern关键字对外部函数进行声明，以保证能正常调用。对简单程序来说，这个不是问题，但对于大型程序，尤其涉及到很多的源文件的时候，这种方式做起来就非常麻烦了。
所以，我们来看下头文件是如何实现在多个源文件之间实现定义和声明共享的。
我们可以把共享的部分（包括函数和变量）集中起来，放在一个额外的副本（也就是头文件 .h）中，而在其他需要使用到这些共享部分的源文件（.c）中通过 #include 指令把这个头文件包含进来。这样只需要一个统一的头文件，既保证程序的正确性，也降低开发/修改程序的难度。
因此，上一节的计算器程序可以改成：
- my_header.h
#define NUMBER '0'
void push(double);
double pop(void);
int getop(char []);
int getch(void);
void ungetch(int);
- main.c
#include <stdio.h>
#include <stdlib.h>
#include "my_header.h"
#define MAXOP 100
main() {
... ...
}
- pop_push.c
#include <stdio.h>
#include "my_header.h"
#define MAXVAL 100
int sp = 0;
double val[MAXVAL];
void push(double) {
... ...
}
double pop(void) {
... ...
}
- getop.c
#include <stdio.h>
#include <ctype.h>
#include "my_header.h"
getop() {
... ...
}
- getch_ungetch.c
#include <stdio.h>
#define BUFSIZE 100
char buf[BUFSIZE];
int bufp = 0;
int getch(void) {
... ...
}
void ungetch(int) {
.. ...
}
其中getch_ungetch.c中由于没有涉及到需要共享的部分，因此没有包含该头文件。
一方面，我们希望每个文件只能访问它完成任务所需的信息，另一方面现实中维护较多的头文件是件很麻烦的事，所以我们可以得出的结论是：
- 对于简单的、不涉及到太多源文件的小程序，可以不用头文件；
- 对于中等规模的程序，最好只用一个头文件存放各部分需要共享的对象；
- 更大型的程序需要更多的头文件，我们需要恰当的组织它们，使程序结构不至于出现混乱。
4.6 静态变量
通过static关键字声明外部变量与函数，可以将其后声明的对象的作用域强制限定为被编译源文件的剩余部分。
【static声明外部变量】
基于之前的getch_ungetch.c，我们修改如下所示：
static char buf[BUFSIZE]; /* buffer for ungetch */
static int bufp = 0; /* next free position in buf */
int getch(void) { ... }
void ungetch(int) { ... }
那么其他getch_ungetch.c以外的函数就不能访问buf和bufp这两个函数了。这样即使同一程序中的其他源文件中定义了同名的变量，也不会引起冲突，因为用static修饰的变量和其他文件中的同名变量已经不是同一个变量了。
同样 pop_push.c中的外部变量sp和val，也可以用static来修饰，因为它们也是栈操作的专用数据，不需要开放给其他函数。
【static声明函数】
static也可以用来声明函数。通常情况下，函数名字是可以全局访问的，对整个程序的各个部分而言都是可见的。
而如果把函数声明为static类型，则该函数仅对该函数声明所在的源文件可见，其他文件的函数无法调用该函数。
【static声明局部变量】
当一个函数内的局部变量用static声明时，并不能改变该变量的作用域（仍然是只能在该函数内部使用，其他函数无法访问），但与局部变量不同之处在于：局部变量在函数调用结束后就消失了，但静态局部变量则一直存在，即本次函数调用结束后，变量依然存在，下次再调用本函数时，其变量的值依然有效。
换句话说，
static类型的局部变量是一种只能在其声明所在函数中使用，但一直占据存储空间的变量。
4.7 寄存器变量
register声明用于告诉编译器：它所声明的变量在程序中使用频率较高，希望将该变量放在机器的寄存器中，这样可以使程序更小、执行速度更快。然而，编译器可以忽略此选项……
register 的声明只适用于两种情况。
一种是局部变量，形式如下：
register int x;
register char c;
另一种是函数的形式参数，形式如下：
func(register unsigned n, register long n)
{
register int i;
... ...
}
实际使用中，底层硬件环境的实际情况对寄存器变量的使用会有一些限制（不同的机器对寄存器的数量和类型的具体限制很有可能是不同的）。
虽然每个函数中只有很少量、而且只允许某些类型的变量可以保存在寄存器中。然而，大量的寄存器声明其实并没有什么害处，因为编译器可以自动忽略过量或不支持的寄存器变量声明。
最后要提到的一点是：无论寄存器变量实际上是否存放在寄存器中，用
register声明的变量的地址是不可访问的。这一点会在下一章指针和数组的学习中认识的。
4.8 程序块结构
虽然C语言不允许在函数内部定义新的函数，但可以允许在函数内部以程序块结构的形式定义变量。
变量的声明、定义除了可以紧跟在函数开始的花括号之后，也可以紧跟在任何其他标识的复合语句开始的花括号之后。
以这种方式声明的变量其作用域就是对应的花括号的范围之内，因此可以隐藏程序块之外的与之同名的变量。
在下面这个程序中，
if (n > 0) {
int i; /* declare a new i */
for (i = 0; i < n; i++)
... ...
}
变量i的作用域是if语句的真分支，这个i与程序块外声明的i无关。每次进入程序块时，在程序内声明及初始化的局部变量都将被初始化（静态变量只在第一次进入程序块时被初始化一次）。
自动变量（包括形式参数）也可以隐藏与之同名的外部变量与函数。比如：
int x;
int y;
f(double x)
{
double y;
}
两个同名变量x之间没有任何关系，两个y也是如此。
不过，最后还要强调一句的是，我们应该尽量避免出现变量名隐藏外部作用域中同名变量的情况，因为这个很容易引起混淆和错误。
4.9 初始化
前面多次提到了“初始化”的概念，这节我们对各种存储类的初始化规则做一个总结。
在不显式初始化的情况下，
- 外部变量和静态变量都将被初始化为
0； - 而自动变量和寄存器变量的初值则没有定义（即无用的信息）。
定义标量变量时，可以在变量名后紧跟一个等号和一个表达式来初始化该变量：
int x = 1;
char squota = '\'';
long day = 1000L * 60 * 60 * 24L; /* milliseconds/day */
对于外部变量、静态变量来说，初始化表达式必须是常量表达式，且只初始化一次（严格来说是在程序开始执行前进行初始化）。
对于自动变量、寄存器变量来说，初始化表达式可以不是常量表达式（可以包含任意在此表达式之前已经定义的值，或者函数调用），而且在每次进入函数或程序块时，都会被初始化。
自动变量的初始化等效于简写的赋值语句，比如可以用下面这种形式：
int binsearch(int x, int v[], int n)
{
int low = 0;
int high = n - 1;
int mid;
}
代替原来的：
int binsearch(int x, int v[], int n)
{
int low, high, mid;
low = 0;
high = n - 1;
}
数组的初始化可以在声明的后面紧跟一个初始化表达式列表。初始化表达式列表用花括号括起来，内部各表达式用逗号分隔，例如：
int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
当数组长度省略时，编译器会把初始化列表中的表达式个数作为数组长度（上例为12）。
如果声明数组时指定了数组长度，
- 若表达式列表中的表达式个数小于数组长度，则对外部变量、静态变量、自动变量来说，没有初始化表达式的元素将被初始化为0；
- 若表达式列表中的表达式个数大于数组长度，这是错误的，编译器会报错。
字符数组的初始化比较特殊，它接受一个字符串形式的表达式序列：
char pattern[] = "ould";
其实等价于：
char pattern[] = {'o', 'u', 'l', 'd', '\0'};
特别提醒，此处的数组长度为5，因为要一个额外的空间存放字符串结束符'\0'。
4.10 递归
C语言中的函数可以递归调用，即函数可以直接或间接的调用自身。
考虑一个“将整数以字符串形式打印”的问题。数字的生成是反序的，即先生成低位数字，后生成高位数字。但打印过程是反序的，先打印高位数字。有2种解决办法：
- 将生成的各位数字依次存储到一个数组中，再以相反的顺序依次打印，与之前
itoa函数的处理方式类似； - 使用递归函数，调用它自身先打印高位的数字（见以下参考代码）。
#include <stdio.h>
/* printd: print n in decimal */
void printd(int n)
{
if (n < 0) {
putchar('-');
n = -n;
}
if (n / 10)
printd(n / 10);
putchar(n % 10 + '0');
}
int main()
{
printd(123456);
printf("\n");
printd(-123456);
printf("\n");
}
每次调用printd函数时，都会得到一个不同的参数。第一次调用printd(123456)把 参数12345传给第二次调用，紧接着参数1234传给第三次调用……，最后一次调用参数1传给printd()函数，然后打印1，返回到倒数第二次调用，之前传给它的参数是 12，因此打印2，依次返回……函数结束。
另一个比较好说明递归的例子是快速排序。
快速排序算法由 C.A.R. Hoare于1962年发明。给定一个数组，从中选择一个元素，以该元素为界将其他元素划分成两个子集，一个子集中所有元素都小于该元素，另一个子集中所有元素都大于或等于该元素。对这样的两个子集递归执行，当某个子集中的元素个数小于2时，这个子集就不再需要递归执行了。
实现起来的代码是：
#include <stdio.h>
/* swap: interchange v[i] and v[j] */
void swap(int v[], int i, int j)
{
int temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
/* qsort: sort v[left]...v[right] into increasing order */
void qsort(int v[], int left, int right)
{
int i, last;
if (left >= right) /* do nothing if array contains */
return; /* fewer than two elements */
swap(v, left, (left + right)/2); /* move partition elem*/
last = left; /* to v[0] */
for (i = left + 1; i <= right; i++) /* partition */
if (v[i] < v[left])
swap(v, ++last, i);
swap(v, left, last); /* restore partitioin elem*/
qsort(v, left, last-1);
qsort(v, last+1, right);
}
int main()
{
int i;
int a[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1,};
printf("before:\t");
for (i = 0; i < 10; i++)
printf("%d ", a[i]);
printf("\n");
qsort(a, 0, 9);
printf("after:\t");
for (i = 0; i < 10; i++)
printf("%d ", a[i]);
printf("\n");
return 0;
}
虽然递归的代码看上去很紧凑，但是递归的执行速度并不快，也并不节省存储器的开销，因为递归调用过程中，必须在某个地方维护一个存储处理值的栈。
4.11 C预处理器
从概念上讲，预处理器是编译过程中单独执行的第一个步骤。最常用的两个预处理器指令我们前面已经见过很多次了，分别是：
#include指令用于在编译期间把指定文件的内容包含进当前文件中；#define指令用任意字符序列替代一个标记。
接下来，我们还会看到预处理器的一些其他特性，如条件编译、带参数的宏。
4.11.1 文件包含
文件包含指令（即#include）使得处理大量#define指令以及声明更加方便。
任何形如：
#include <文件名>
或者
#include "文件名"
的行都会被替换为“文件名”所指定的文件里的内容。
若文件名用双引号括起来，则在源文件所在位置查找该文件；若文件名用尖括号括起来，则根据相应的规则查找该文件，这个规则同具体的实现有关，大多情况下会去标准库中查找。
源文件的开始位置通常会包含多个#include指令，用来包含常见的#define语句和extern声明，或者从头文件中访问库函数的函数原型声明（比如<stdio.h>）
在大型程序中，#include指令是将所有声明捆绑在一起的好办法，保证所有包含同一个文件的源文件都具有相同的定义和变量声明，可以避免一些不必要的错误。显然，如果被包含的文件里内容发生了变化，那么所有包含该文件的源文件都必须重新编译。
4.11.2 宏替换
宏定义的形式：
#define 名字 替换文本
后续所有出现“名字”记号的地方，都将用“替换文本”代替（用双引号括起来的字符串不是记号，比如定义了一个名字为YES的宏，那么在printf(“YES”)中并不会被替换）。
其中“名字”的命名方式与普通变量相同，“替换文本”可以是任意字符串。
通常#define只占一行，“替换文本”就是该指令行尾部的所有剩余内容；但 #define 也可以占多行，不过需要在待续的行末尾加上反斜杠\。
#define定义的名字，其作用域从其定义点开始，到被编译的源文件末尾结束。
替换文本可以是任意的，例如：
#define forever for(;;) //为无限循环定义了一个新名字：forever
宏定义也可以带参数，这样对不同的宏调用使用不同的替换文本。例如：
#define max(A, B) ((A) > (B) ? (A) : (B)) //定义了一个带参数的 max 宏
max宏看起来很像函数调用，但它实际上是直接将替换文本插入到代码中，“形式参数”A和B在每次宏调用的时候都会被替换成对应的“实际参数”。因此语句：
x = max(p+q, r+s);
会被替换为：
x = ((p+q) > (r+s) ? (p+q) : (r+s));
上述max宏还存在缺陷，因为作为参数的表达式会重复计算两遍，所以你可以预想得到，如果是max(i++, j++)调用会出现什么问题。
max宏的替换文本中，A和B的圆括号不能去掉，你可以试着把圆括号去掉之后，看看max(p+q, r+s)替换后的文本会怎么样。所以必须要注意，适当使用圆括号，可以保证计算次序的正确性。
通过#undef指令取消名字的宏定义，这样做可以保证后续的调用是函数调用而不是宏调用：
#undef max
int max(int x, int y) { ... }
形式参数不能用带引号的字符串替换。如果在替换文本中，参数名以# 为前缀则结果将被扩展为由实际参数替换该参数的带引号字符串。比如写一个调试打印宏：
#define dprint(expr) printf(#expr " = %g\n", expr);
当调用dprint(x/y)时，该宏被扩展为：
printf("x/y" " = %g\n", x/y);
等价于：
printf("x/y = %g\n", x/y);
在实际参数中，每个双引号"都将被替换为 \"，反斜杠\被替换为\\，因此替换后的字符串是合法的字符串常量。
另外，预处理器运算符##为宏扩展提供了一种连接实际参数的手段。如果替换文本中的参数与##相邻，则该参数将被实际参数替换， ##及其前后的空白符将被删除，对替换后的结果重新扫描。例如：
#define paste(front, back) front ## back
当宏调用paste(name, 123)时，将建立记号name123。
4.11.3 条件包含
使用条件语句，可以实现对预处理本身进行控制。这种条件语句的值是在预处理执行的过程中进行计算的，是源代码在编译过程中根据条件值的不同，选择性地包含不同代码。
#if语句对其后的常量整型表达式（不能包含sizeof、类型转换运算符、enum常量）进行求值，如果不为0（即为真），则包含其后的各行，直到遇到#else、#elif或#endif语句为止。
在#if语句中可以使用表达式defined(名字)，该表达式的规则是：如果“名字”已经定义了，其值为 1 ；否则为 0。
例如，在hdr.h中，
#if !defined(HDR)
#define HDR
/* hdr.h 中的所有代码 */
#endif
这种方式可以保证hdr.h文件的内容只被包含一次。如果多个头文件能够一致地使用这种方式，那么，每个头文件都可以将它所依赖的任何头文件包含进来，用户不必考虑和处理头文件之间的各种依赖关系。
C语言专门定义了两个预处理语句#ifdef和#ifndef，它们用来测试某个名字是否已经定义。所以上面的例子可以改写成：
#ifndef HDR
#define HDR
/* hdr.h 中的所有代码 */
#endif
最后，下面这个例子演示了测试系统变量，再根据变量确定包含哪个头文件：
#if SYSTEM == SYSV
#define HDR "sysv.h"
#elif SYSTEM == BSD
#define HDR "bsd.h"
#elif SYSTEM == MSDOS
#define HDR "msdos.h"
#else
#define HDR "default.h"
#endif
#include HDR