C程序设计语言-第5章指针与数组

C程序设计语言系列文章链接：

第5章指针与数组

指针是一种保存变量地址的变量。在C语言中，指针的使用非常广泛，原因之一是，指针常常是表达某个计算的唯一途径，另一个原因是，同其他方法比较起来，使用指针通常可以生成更高效、更紧凑的代码。指针与数组之间的关系十分密切，我们将在本章中讨论它们之间的关系，并探讨如何使用这种关系。

指针和goto语句一样，会导致程序难以理解。如果使用者粗心，指针很容易就指向了错误的地方。但是，如果谨慎地使用指针，便可以利用它写出简单、清晰的程序。在本章中我们将尽力说明这一点。

ANSI C的一个最重要的变化是，它明确地制定了操纵指针的规则。事实上，这些规则已经被很多优秀的程序设计人员和编译器所采纳。此外，ANSI C使用类型void*（指向void的指针）代替char *作为通用指针的类型。

5.1 指针与地址

首先，我们通过一个简单的示意图来说明内存是如何组织的。通常的机器都有一系列连续编号或编址的存储单元，这些存储单元可以单个进行操纵，也可以以连续成组的方式操纵。通常情况下，机器的一个字节可以存放一个char类型的数据，两个相邻的字节存储单元可存储一个short（短整型）类型的数据，而4个相邻的字节存储单元可存储一个long（长整型）类型的数据。指针是能够存放一个地址的一组存储单元（通常是两个或4个字节或8个字节）。因此，如果c的类型是char，并且p是指向c的指针，则可用图5-1表示它们之间的关系：

图 5-1

          +---->---------+
        p:|            c:|
    +--+--+--+           v
···[·][·][·][·]···[ ][ ][·][ ]···

一元运算符&可用于取一个对象的地址，因此，下列语句：

p = &c;

将把c的地址赋值给变量p，我们称p为“指向”c的指针。地址运算符&只能应用于内存中的对象，即变量与数组元素。它不能作用于表达式、常量或register类型的变量。

一元运算符*是间接寻址或间接引用运算符。当它作用于指针时，将访问指针所指向的对象。我们在这里假定x与y是整数，而ip是指向int类型的指针。下面的代码段说明了如何在程序中声明指针以及如何使用运算符&和*：

int x = 1, y = 2, z[10];
int *ip;      /* ip是指向int类型的指针 */

ip = &x;      /* ip现在指向x */
y = *ip;      /* y的值现在为1 */
*ip = 0;      /* x的值现在为0 */
ip = &z[0];   /* ip现在指向z[0] */

变量x、y与z的声明方式我们已经在前面的章节中见到过。我们来看指针ip的声明，如下所示：

int *ip;

这样声明是为了便于记忆。该声明语句表明表达式*ip的结果是int类型。这种声明变量的语法与声明该变量所在表达式的语法类似。同样的原因，对函数的声明也可以采用这种方式。例如，声明

double *dp, atof(char *);

表明，在表达式中，*dp和atof(s)的值都是double类型，且atof的参数是一个指向char类型的指针。

我们应该注意，指针只能指向某种特定类型的对象，也就是说，每个指针都必须指向某种特定的数据类型。（一个例外情况是指向void类型的指针可以存放指向任何类型的指针，但它不能间接引用其自身。我们将在5.11节中详细讨论该问题）。

如果指针ip指向整型变量x，那么在x可以出现的任何上下文中都可以使用*ip，因此，语句

*ip = *ip + 10;

将把*ip的值增加10。

一元运算符*和&的优先级比算术运算符的优先级高，因此，赋值语句

y = *ip + 1

将把*ip指向的对象的值取出并加1，然后再将结果赋值给y，而下列赋值语句：

*ip += 1

则将ip指向的对象的值加1，它等同于

++*ip

或

(*ip)++

语句的执行结果。语句(*ip)++中的圆括号是必需的，否则，该表达式将对ip进行加一运算，而不是对ip指向的对象进行加一运算，这是因为，类似于*和++这样的一元运算符遵循从右至左的结合顺序。

最后说明一点，由于指针也是变量，所以在程序中可以直接使用，而不必通过间接引用的方法使用。例如，如果iq是另一个指向整型的指针，那么语句

iq = ip

将把ip中的值拷贝到iq中，这样，指针iq也将指向ip指向的对象。

5.2 指针与函数参数

由于C语言是以传值的方式将参数值传递给被调用函数，因此，被调用函数不能直接修改主调函数中变量的值。例如，排序函数可能会使用一个名为swap的函数来交换两个次序颠倒的元素。但是，如果将swap函数定义为下列形式：

void swap(int x, int y) {
    int temp;

    temp = x;
    x = y;
    y = temp;
}

则下列语句无法达到该目的：

swap(a, b);

这是因为，由于参数传递采用传值方式，因此上述的swap函数不会影响到调用它的例程中的参数a和b的值。该函数仅仅交换了a和b的副本的值。

那么，如何实现我们的目标呢？可以使主调程序将指向所要交换的变量的指针传递给被调用函数，即：

swap(&a, &b);

由于一元运算符&用来取变量的地址，这样&a就是一个指向变量a的指针。swap函数的所有参数都声明为指针，并且通过这些指针来间接访问它们指向的操作数。

void swap(int *px, int *py) { /* 交换*px和*py */
    int temp;

    temp = *px;
    *px = *py;
    *py = temp;
}

我们通过图5-2进行说明。

图 5-2

        在主调函数中：
           +-------+
           |a:[ ]<-+---+
           |b:[ ]<-+-+ |
           +-------+ | |
                     | |
in the swap function:^ ^
           +-------+ | |
           |px:[ ]-+-|-+
           |py:[ ]-+-+
           +-------+

指针参数使得被调用函数能够访问和修改主调函数中对象的值。我们来看这样一个例子：函数getint接受自由格式的输入，并执行转换，将输入的字符流分解成整数，且每次调用得到一个整数。getint需要返回转换后得到的整数，并且，在到达输入结尾时要返回文件结束标记。这些值必须通过不同的方式返回。EOF（文件结束标记）可以用任何值表示，当然也可用一个输入的整数表示。

可以这样设计该函数：将标记是否到达文件结尾的状态作为getint函数的返回值，同时，使用一个指针参数存储转换后得到的整数并传回给主调函数。函数scanf的实现就采用了这种方法，具体细节请参见7.4节。

下面的循环语句调用getint函数给一个整型数组赋值：

int n, array[SIZE], getint(int *);

for (n = 0; n < SIZE && getint(&array[n]) != EOF; n++)
    ;

每次调用getint时，输入流中的下一个整数将被赋值给数组元素array[n]，同时，n的值将增加1。请注意，这里必须将array[n]的地址传递给函数getint，否则函数getint将无法把转换得到的整数传回给调用者。

该版本的getint函数在到达文件结尾时返回EOF，当下一个输入不是数字时返回0，当输入中包含一个有意义的数字时返回一个正值。

#include <ctype.h>

int getch(void);
void ungetch(int);

/* getint函数：将输入中的下一个整型数赋值给*pn */
int getint(int *pn) {
    int c, sign;

    while (isspace(c = getch()))   /* 跳过空白符 */
        ;
    if (!isdigit(c) && c != EOF && c != '+' && c != '-') {
        ungetch(c);     /* 输入不是一个数字 */
        return 0;
    }
    sign = (c == '-') ? -1 : 1;
    if (c == '+' || c == '-')
        c = getch();
    for (*pn = 0; isdigit(c); c = getch())
        *pn = 10 * *pn + (c - '0');
    *pn *= sign;
    if (c != EOF)
        ungetch(c);
    return c;
}

在getint函数中，*pn始终作为一个普通的整型变量使用。其中还使用了getch和ungetch两个函数（参见4.3节），借助这两个函数，函数getint必须读入的一个多余字符就可以重新写回到输入中。

练习5-1 在上面的例子中，如果符号+或-的后面紧跟的不是数字，getint函数将把符号视为数字0的有效表达方式。修改该函数，将这种形式的+或-符号重新写回到输入流中。

练习5-2 模仿函数getint的实现方法，编写一个读取浮点数的函数getfloat。getfloat函数的返回值应该是什么类型？

5.3 指针与数组

在C语言中，指针和数组之间的关系十分密切，因此，在接下来的部分中，我们将同时讨论指针与数组。通过数组下标所能完成的任何操作都可以通过指针来实现。一般来说，用指针编写的程序比用数组下标编写的程序执行速度快，但另一方面，用指针实现的程序理解起来稍微困难一些。

声明

int a[10];

定义了一个长度为10的数组a。换句话说，它定义了一个由10个对象组成的集合，这10个对象存储在相邻的内存区域中，名字分别为a[0]、a[1]、…、a[9]（参见图5-3）

图5-3

a: [  ][  ][  ][  ][  ][  ][  ][  ][  ][  ]
   a[0]a[1]                            a[9]

a[i]表示该数组的第i个元素。如果pa的声明为

int *pa;

则说明它是一个指向整型对象的指针，那么，赋值语句

pa = &a[0];

则可以将指针pa指向数组a的第0个元素，也就是说，pa的值为数组元素a[0]的地址（参见图5-4）。

图5-4

pa:
 [· ]--+
       |
       v
   a: [  ][  ][  ][  ][  ][  ][  ][  ][  ][  ]
      a[0]

这样，赋值语句

x = *pa;

将把数组元素a[0]中的内容复制到变量x中。

如果pa指向数组中的某个特定元素，那么，根据指针运算的定义，pa+1将指向下一个元素，pa+i将指向pa所指向数组元素之后的第i个元素，而pa-i将指向pa所指向数组元素之前的第i个元素。因此，如果指针pa指向a[0]，那么*(pa+1)引用的是数组元素a[1]的内容，pa+i是数组元素a[i]的地址，*(pa+i)引用的是数组元素a[i]的内容（参见图5-5）。

图5-5

          pa+1 pa+2
pa:         |   |
 [· ]---+   |   |
        |   |   |
        v   v   v
    a: [  ][  ][  ][  ][  ][  ][  ][  ][  ][  ]
       a[0]

无论数组a中元素的类型或数组长度是什么，上面的结论都成立。“指针加1”就意味着，pa+1指向pa所指向的对象的下一个对象。相应地，pa+i指向pa所指向的对象之后的第i个对象。

下标和指针运算之间具有密切的对应关系。根据定义，数组类型的变量或表达式的值是该数组第0个元素的地址。执行赋值语句

pa = &a[0];

后，pa和a具有相同的值。因为数组名所代表的就是该数组最开始的一个元素的地址，所以，赋值语句pa=&a[0]也可以写成下列形式：

pa = a;

对数组元素a[i]的引用也可以写成*(a+i)这种形式。对第一次接触这种写法的人来说，可能会觉得很奇怪。在计算数组元素a[i]的值时，C语言实际上先将其转换为*(a+i)的形式，然后再进行求值，因此在程序中这两种形式是等价的。如果对这两种等价的表示形式分别施加地址运算符&，便可以得出这样的结论：&a[i]和a+i的含义也是相同的。a+i是a之后第i个元素的地址。相应地，如果pa是一个指针，那么，在表达式中也可以在它的后面加下标。pa[i]与*(pa+i)是等价的。简而言之，一个通过数组和下标实现的表达式可等价地通过指针和偏移量实现。

但是，我们必须记住，数组名和指针之间有一个不同之处。指针是一个变量，因此，在C语言中，语句pa=a和pa++都是合法的。但数组名不是变量，因此类似于a=pa和a++形式的语法是非法的。

当把数组名传递给一个函数时，实际上传递的是该数组第一个元素的地址。在被调用函数中，该参数是一个局部变量，因此，数组名参数必须是一个指针，也就是一个存储地址值的变量。我们可以利用该特性编写strlen函数的另一个版本，该函数用于计算一个字符串的长度。

/* strlen函数：返回字符串s的长度 */
int strlen(char *s) {
    int n;

    for (n = 0; *s != '\0'; s++)
        n++;
    return n;
}

因为s是一个指针，所以对其执行自增运算是合法的。执行s++运算不会影响到strlen函数的调用者中的字符串，它仅对该指针在strlen函数中的私有副本进行自增运算。因此，类似于下面这样的函数调用：

1
2
3

strlen("hello, world");    /* 字符串常量 */
strlen(array);             /* 字符数组array有100个元素 */
strlen(ptr);               /* ptr是一个指向char类型对象的指针 */

都可以正确地执行。

在函数定义中，形式参数

char s[];

和

char *s;

是等价的。我们通常更习惯于使用后一种形式，因为它比前者更直观地表明了该参数是一个指针。如果将数组名传递给函数，函数可以根据情况判定是按照数组处理还是按照指针处理，随后根据相应的方式操作该参数。为了直观且恰当地描述函数，在函数中甚至可以同时使用数组和指针这两种表示方法。

也可以将指向子数组起始位置的指针传递给函数，这样，就将数组的一部分传递给了函数。例如，如果a是一个数组，那么下面两个函数调用

f(&a[2])

与

f(a+2)

都将把起始于a[2]的子数组的地址传递给函数f。在函数f中，参数的声明形式可以为

f(int arr[]) {...}

或

f(int *arr) {...}

对于函数f来说，它并不关心所引用的是否只是一个更大数组的部分元素。

如果确信相应的元素存在，也可以通过下标访问数组第一个元素之前的元素。类似于p[-1]、p[-2]这样的表达式在语法上都是合法的，它们分别引用位于p[0]之前的两个元素。当然，引用数组边界之外的对象是非法的。

5.4 地址算术运算

如果p是一个指向数组中某个元素的指针，那么p++将对p进行自增运算并指向下一个元素，而p+=i将对p进行加i的增量运算，使其指向指针p当前所指向的元素之后的第i个元素。这类运算是指针或地址算术运算中最简单的形式。

C语言中的地址算术运算方法是一致且有规律的，将指针、数组和地址的算术运算集成在一起是该语言的一大优点。为了说明这一点，我们来看一个不完善的存储分配程序。它由两个函数组成。第一个函数alloc(n)返回一个指向n个连续字符存储单元的指针，alloc函数的调用者可利用该指针存储字符序列。第二个函数afree(p)释放已分配的存储空间，以便以后重用。之所以说这两个函数是“不完善的”，是因为对afree函数的调用次序必须与调用alloc函数的次序相反。换句话说，alloc与afree以栈的方式（即后进先出的列表）进行存储空间的管理。标准库中提供了具有类似功能的函数malloc和free，它们没有上述限制，我们将在8.7节中说明如何实现这些函数。

最容易的实现方法是让alloc函数对一个大字符数组allocbuf中的空间进行分配。该数组是alloc和afree两个函数私有的数组。由于函数alloc和afree处理的对象是指针而不是数组下标，因此，其他函数无需知道该数组的名字，这样，可以在包含alloc和afree的源文件中将该数组声明为static类型，使得它对外不可见。实际实现时，该数组甚至可以没有名字，它可以通过调用malloc函数或向操作系统申请一个指向无名存储块的指针获得。

allocbuf中的空间使用状况也是我们需要了解的信息。我们使用指针allocp指向allocbuf中的下一个空闲单元。当调用alloc申请n个字符的空间时，alloc检查allocbuf数组中有没有足够的剩余空间。如果有足够的空闲空间，则alloc返回allocp的当前值（即空闲块的开始位置），然后将allocp加n以使它指向下一个空闲区域。如果空闲空间不够，则alloc返回0。如果p在allocbuf的边界之内，则afree(p)仅仅只是将allocp的值设置为p（参见图5-6）。

图5-6

调用alloc之前:
                            allocp:
                               v
     allocbuf: [  ][    ][][  ][                  ]
               <--used--------><------free-------->
调用alloc之后:
                                    allocp:
                                       v
     allocbuf: [  ][    ][][  ][      ][          ]
               <--used----------------><--free---->

#define ALLOCSIZE 10000  /* 可用空间大小 */

static char allocbuf[ALLOCSIZE];   /* alloc使用的存储区 */

static char *allocp = allocbuf;    /* 下一个空闲位置 */

char *alloc(int n) {         /* 返回指向n个字符的指针 */
    if (allocbuf + ALLOCSIZE - allocp >= n) {  /* 有足够的空闲空间 */
        allocp += n;
        return allocp - n;   /* 分配前的指针p */
    } else           /* 空闲空间不够 */
        return 0;
}

void afree(char *p) {        /* 释放p指向的存储区 */
    if (p >= allocbuf && p < allocbuf + ALLOCSIZE)
        allocp = p;
}

一般情况下，同其他类型的变量一样，指针也可以初始化。通常，对指针有意义的初始化只能是0或者是表示地址的表达式，对后者来说，表达式所代表的地址必须是在此前已定义的具有适当类型的数据的地址。例如，声明

static char *allocp = allocbuf;

将allocp定义为字符类型指针，并把它初始化为allocbuf的起始地址，该起始地址是程序执行时的下一个空闲位置。上述语句也可以写成下列形式：

static char *allocp = &allocbuf[0];

这是因为该数组名实际上就是数组第0个元素的地址。

下列if测试语句：

if (allocbuf + ALLOCSIZE - allocp >= n) { /* 有足够的空闲空间 */

检查是否有足够的空闲空间以满足n个字符的存储空间请求。如果空闲空间足够，则分配存储空间后allocp的新值至多比allocbuf的尾端地址大1。如果存储空间的申请可以满足，alloc将返回一个指向所需大小的字符块首地址的指针（注意函数本身的声明）。如果申请无法满足，alloc必须返回某种形式的信号以说明没有足够的空闲空间可供分配。C语言保证，0永远不是有效的数据地址，因此，返回值0可用来表示发生了异常事件。在本例中，返回值0表示没有足够的空闲空间可供分配。

指针与整数之间不能相互转换，但0是唯一的例外：常量0可以赋值给指针，指针也可以和常量0进行比较。程序中经常用符号常量NULL代替常量0，这样便于更清晰地说明常量0是指针的一个特殊值。符号常量NULL定义在标准头文件<stddef.h>中。我们在后面部分经常会用到NULL。

类似于

if (allocbuf + ALLOCSIZE - allocp >= n) { /* 有足够的空闲空间 */

以及

if (p >= allocbuf && p < allocbuf + ALLOCSIZE)

的条件测试语句表明指针算术运算有以下几个重要特点。首先，在某些情况下对指针可以进行比较运算。例如，如果指针p和q指向同一个数组的成员，那么它们之间就可以进行类似于==、!=、<、>=的关系比较运算。如果p指向的数组元素的位置在q指向的数组元素位置之前，那么关系表达式:

p < q

的值为真（true）。任何指针与0进行相等或不等的比较运算都有意义。但是，指向不同数组的元素的指针之间的算术或比较运算没有定义。（这里有一个特例：指针的算术运算中可使用数组最后一个元素的下一个元素的地址。）

其次，我们从前面可以看到，指针可以和整数进行相加或相减运算。例如，结构

p + n

表示指针p当前指向的对象之后第n个对象的地址。无论指针p指向的对象是何种类型，上述结论都成立。在计算p+n时，n将根据p指向的对象的长度按比例缩放，而p指向的对象的长度则取决于p的声明。例如，如果int类型占4个字节的存储空间，那么在int类型的计算中，对应的n将按4的倍数来计算。

指针的减法运算也是有意义的：如果p和q指向同一数组中的元素，且p<q，那么q-p+1就是位于p和q指向的元素之间的元素的数目。我们由此可以编写出函数strlen的另一个版本，如下所示：

/* strlen函数： 返回字符串s的长度 */
int strlen(char *s) {
    char *p = s;

    while(*p != '\0')
        p++;
    return p - s;
}

在上述程序段的声明中，指针p被初始化为指向s，即指向该字符串的第一个字符。while循环语句将依次检查字符串中的每个字符，直到遇到标识字符数组结尾的字符'\0'为止。由于p是指向字符的指针，所以每执行一次p++，p就将指向下一个字符的地址，p-s则表示已经检查过的字符数，即字符串的长度。（字符串中的字符数有可能超过int类型所能表示的最大范围。头文件<stddef.h>中定义的类型ptrdiff_t足以表示两个指针之间的带符号差值。但是，我们在这里使用size_t作为函数strlen的返回值类型，这样可以与标准库中的函数版本相匹配。size_t是由运算符sizeof返回的无符号整型。）

指针的算术运算具有一致性：如果处理的数据类型是比字符型占据更多存储空间的浮点类型，并且p是一个指向浮点类型的指针，那么在执行p++后，p将指向下一个浮点数的地址。因此，只需要将alloc和afree函数中所有的char类型替换为float类型，就可以得到一个适用于浮点类型而非字符型的内存分配函数。所有的指针运算都会自动考虑它所指向的对象的长度。

有效的指针运算包括相同类型指针之间的赋值运算：指针同整型之间的加法或减法运算；指向相同数组中元素的两个指针间的减法或比较运算；将指针赋值为0或指针与0之间的比较运算。其他所有形式的指针运算都是非法的，例如两个指针间的加法、乘法、除法、移位或屏蔽运算；指针同float或double类型之间的加法运算；不经强制类型转换而直接将指向一种类型对象的指针赋值给指向另一种类型对象的指针的运算（两个指针之一是void *类型的情况除外）。

5.5 字符指针与函数

字符串常量是一个字符数组，例如：

“I am a string”

在字符串的内部表示中，字符数组以空字符'\0'结尾，所以，程序可以通过检查空字符找到字符数组的结尾。字符串常量占据的存储单元数也因此比双引号内的字符数大1。

字符串常量最常见的用法也许是作为函数参数，例如：

printf("hello, world\n");

当类似于这样的一个字符串出现在程序中时，实际上是通过字符指针访问该字符串的。在上述语句中，printf接收的是一个指向字符数组第一个字符的指针。也就是说，字符串常量可通过一个指向其第一个元素的指针访问。

除了作为函数参数外，字符串常量还有其他用法。假定指针pmessage的声明如下：

char *pmessage;

那么，语句

pmessage = "now is the time";

将把一个指向该字符数组的指针赋值给pmessage。该过程并没有进行字符串的复制，而只是涉及到指针的操作。C语言没有提供将整个字符串作为一个整体进行处理的运算符。

下面两个定义之间有很大的差别：

char amessage[] = "now is the time";   /* 定义一个数组，amessage在栈上 */
char *pmessage = "now is the time";    /* 定义一个指针，now is the time\0在常量区，pmessage在栈上 */

- amessage数组的数据存储在栈上，其内容是可以被修改的，就不会出现运行时错误
- pmessage指针指向常量字符串(位于常量区)，常量字符串的内容是不可以被修改的，会出现运行时错误

程序的内存分配：
1. 栈区(stack): 由编译器自动分配释放，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
2. 堆区(heap): 一般由程序员分配释放，若程序员不释放，程序结束时可能由OS回收。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表
3. 全局区(static)，也叫静态区:  全局变量和静态变量的存储是放在一块的，程序结束后由OS释放。它分为全局初始化区，和全局未初始化区，这两块内存区是挨在一起的
4. 常量区：常量字符串就是放在这里的，程序结束后由OS释放
5. 代码区：存放函数体的二进制代码

// main.c
int a = 0; 全局初始化区
char *p1;  全局未初始化区
main() {
	int b; 栈
	char s[] = "abc"; 栈
	char *p2; 栈
	char *p3 = "123456";  123456\0在常量区，p3在栈上
	static int c = 0;   全局(静态)初始化区
	p1 = (char *)malloc(10);  分配得到的10个字节的区域就在堆区
}

上述声明中，amessage是一个仅仅足以存放初始化字符串以及空字符'\0'的一维数组。数组中的单个字符可以进行修改，但amessage始终指向同一个存储位置。另一方面，pmessage是一个指针，其初值指向一个字符串常量，之后它可以被修改以指向其他地址，但如果试图修改字符串的内容，结果是没有定义的（参见图5-7）。

图 5-7

amessage: [now is the time\0]
pmessage: [· ]----->[now is the time\0]

为了更进一步地讨论指针和数组其他方面的问题，下面以标准库中两个有用的函数为例来研究它们的不同实现版本。第一个函数strcpy(s,t)把指针t指向的字符串复制到指针s指向的位置。如果使用语句s=t实现该功能，其实质上只是拷贝了指针，而并没有复制字符。为了进行字符的复制，这里使用了一个循环语句。strcpy函数的第1个版本是通过数组方法实现的，如下所示：

/* strcpy函数：将指针t指向的字符串复制到指针s指向的位置；使用数组下标实现的版本 */
void strcpy(char *s, char *t) {
    int i;

    i = 0;
    while((s[i] = t[i]) != '\0')
        i++;
}

为了进行比较，下面是用指针方法实现的strcpy函数：

/* strcpy函数：将指针t指向的字符串复制到指针s指向的位置；使用指针方式实现的版本1 */
void strcpy(char *s, char *t) {
    while((*s = *t) != '\0') {
        s++;
        t++;
    }
}

因为参数是通过值传递的，所以在strcpy函数中可以以任何方式使用参数s和t。在此，s和t是方便地进行了初始化的指针，循环每执行一次，它们就沿着相应的数组前进一个字符，直到将t中的结束符’\0’复制到s为止。

实际上，strcpy函数并不会按照上面的这些方式编写。经验丰富的程序员更喜欢将它编写成下列形式：

/* strcpy函数：将指针t指向的字符串复制到指针s指向的位置；使用指针方式实现的版本2 */
void strcpy(char *s, char *t) {
    while ((*s++ = *t++) != '\0')
        ;
}

在该版本中，s和t的自增运算放到了循环的测试部分中。表达式*t++的值是执行自增运算之前t所指向的字符。后缀运算符++表示在读取该字符之后才改变t的值。同样的道理，在s执行自增运算之前，字符就被存储到了指针s指向的旧位置。该字符值同时也用来和空字符'\0'进行比较运算，以控制循环的执行。最后的结果是依次将t指向的字符复制到s指向的位置，直到遇到结束符’\0’为止（同时也复制该结束符）。

为了更进一步地精炼程序，我们注意到，表达式同'\0'的比较是多余的，因为只需要判断表达式的值是否为0即可。因此，该函数可进一步写成下列形式：

/* strcpy函数：将指针t指向的字符串复制到指针s指向的位置；使用指针方式实现的版本3 */
void strcpy(char *s, char *t) {
    while (*s++ = *t++)
        ;
}

该函数初看起来不太容易理解，但这种表示方法是很有好处的，我们应该掌握这种方法，C语言程序中经常会采用这种写法。

标准库(<string.h>)中提供的函数strcpy把目标字符串作为函数值返回。

我们研究的第二个函数是字符串比较函数strcmp(s,t)。该函数比较字符串s和t，并且根据s按照字典顺序小于、等于或大于t的结果分别返回负整数、0或正整数。该返回值是s和t由前向后逐字符比较时遇到的第一个不相等字符处的字符的差值。

/* strcmp函数：根据s按照字典顺序小于、等于或大于t的结果分别返回负整数、0或正整数 */
int strcmp(char *s, char *t) {
    int i;

    for (i=0; s[i] == t[i]; i++)
        if (s[i] == '\0')
            return 0;
    return s[i] - t[i];
}

下面是用指针方式实现的strcmp函数：

/* strcmp函数：根据s按照字典顺序小于、等于或大于t的结果分别返回负整数、0或正整数 */
int strcmp(char *s, char *t) {
    for (; *s == *t; s++, t++)
        if (*s == '\0')
            return 0;
    return *s - *t;
}

由于++和--既可以作为前缀运算符，也可以作为后缀运算符，所以还可以将运算符*与运算符++和--按照其他方式组合使用，但这些用法并不多见。例如，下列表达式

*--p

在读取指针p指向的字符之前先对p执行自减运算。事实上，下面的两个表达式：

1
2

*p++ = val;    /* 将val压入栈 */
val = *--p;    /* 将栈顶元素弹出到val中 */

是进栈和出栈的标准用法。更详细的信息，请参见4.3节。

头文件<string.h>中包含本节提到的函数的声明，另外还包含标准库中其他一些字符串处理函数的声明。

练习5-3 用指针方式实现第2章中的函数strcat。函数strcat(s,t)将t指向的字符串复制到s指向的字符串的尾部。

练习5-4 编写函数strend(s,t)。如果字符串t出现在字符串s的尾部，该函数返回1；否则返回0。

练习5-5 实现库函数strncpy、strncat和strncmp，它们最多对参数字符串中的前n个字符进行操作。例如，函数strncpy(s,t,n)将t中最多前n个字符复制到s中。更详细的说明请参见附录B。

练习5-6 采用指针而非数组索引方式改写前面章节和练习中的某些程序，例如getLine（第1、4章），atoi、itoa以及它们的变体形式（第2、3、4章），reverse（第3章），strindex、getop（第4章）等等。

5.6 指针数组以及指向指针的指针

由于指针本身也是变量，所以它们也可以像其他变量一样存储在数组中。下面通过编写UNIX程序sort的一个简化版本说明这一点。该程序按字母顺序对由文本行组成的集合进行排序。

我们在第3章中曾描述过一个用于对整型数组中的元素进行排序的Shell排序函数，并在第4章中用快速排序算法对它进行了改进。这些排序算法在此仍然是有效的，但是，现在处理的是长度不一的文本行，并且，与整数不同的是，它们不能在单个运算中完成比较或移动操作。我们需要一个能够高效、方便地处理可变长度文本行的数据表示方法。

我们引入指针数组处理这种问题。待排序的每个文本行可通过指向它的第一个字符的指针来访问，这些指针本身可以存储在一个数组中。这样，将指向两个文本行的指针传递给函数strcmp就可实现对这两个文本行的比较。当交换次序颠倒的两个文本行时，实际上交换的是指针数组中与这两个文本行相对应的指针，而不是这两个文本行本身（参见图5-8）。

图 5-8
                            +----------------------+
[· ]---->[defghi]       [· ]+  +--->[defghi]       |
[· ]---->[jklmnopqrst]  [· ]---+  +->[jklmnopqrst] |
[· ]---->[abc]          [· ]------+  +->[abc]      |
                                     +-<-----------+

这种实现方法消除了因移动文本行本身所带来的复杂的存储管理和巨大的开销这两个孪生问题。

排序过程包含下列3个步骤：

读取所有输入行
对文本行进行排序
按次序打印文本行

通常情况下，最好将程序划分成若干个与问题的自然划分相一致的函数，并通过主函数控制其他函数的执行。关于对文本行排序这一步，我们稍后再做说明，现在主要考虑数据结构以及输入和输出函数。

输入函数必须收集和保存每个文本行中的字符，并建立一个指向这些文本行的指针的数组。它同时还必须统计输入的行数，因为在排序和打印时要用到这一信息。由于输入函数只能处理有限数目的输入行，所以在输入行数过多而超过限定的最大行数时，该函数返回某个用于表示非法行数的数值，例如-1。

输出函数只需要按照指针数组中的次序依次打印这些文本行即可。

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

#define MAXLINES 5000      /* 进行排序的最大文本行数 */

char *lineptr[MAXLINES];   /* 指向文本行的指针数组 */

int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);

void qsort(char *lineptr[], int left, int right);

/* 对输入的文本行进行排序 */
main() {
    int nlines;     /* 读取的输入行数目 */

    if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
        qsort(lineptr, 0, nlines-1);
        writelines(lineptr, nlines);
        return 0;
    } else {
        printf("error: input too big to sort\n");
        return 1;
    }
}

#define MAXLEN 1000     /* 每个输入文本行的最大长度 */
int getLine(char *, int);
char *alloc(int);

/* readlines函数：读取输入行 */
int readlines(char *lineptr[], int maxlines) {
    int len, nlines;
    char *p, line[MAXLEN];
    nlines = 0;
    while((len = getLine(line, MAXLEN)) > 0)
        if (nlines >= maxlines || (p = alloc(len)) == NULL)
            return -1;
        else {
            line[len-1] = '\0';   /* 删除换行符 */
            strcpy(p, line);
            lineptr[nlines++] = p;
        }
    return nlines;
}

/* writeline函数：写输出行 */
void writelines(char *lineptr[], int nlines) {
    int i;

    for (i = 0; i < nlines; i++)
        printf("%s\n", lineptr[i]);
}

有关函数getLine的详细信息参见1.9节。

在该例子中，指针数组lineptr的声明是新出现的重要概念：

char *lineptr[MAXLINES]

它表示lineptr是一个具有MAXLINES个元素的一维数组，其中数组的每个元素是一个指向字符类型对象的指针。也就是说，lineptr[i]是一个字符指针，而*lineptr[i]是该指针指向的第i个文本行的首字符。

由于lineptr本身是一个数组名，因此，可按照前面例子中相同的方法将其作为指针使用，这样，writelines函数可以改写为：

/* writelines函数：写输出行 */
void writelines(char *lineptr[], int nlines) {
    while(nlines-- > 0)
        printf("%s\n", *lineptr++);
}

循环开始执行时，*lineptr指向第一行，每执行一次自增运算都使得*lineptr指向下一行，同时对nlines进行自减运算。

在明确了输入和输出函数的实现方法之后，下面便可以着手考虑文本行的排序问题了。在这里需要对第4章的快速排序函数做一些小改动：首先，需要修改该函数的声明部分；其次，需要调用strcmp函数完成文本行的比较运算。但排序算法在这里仍然有效，不需要做任何改动。

/* qsort函数：按递增顺序对v[left]...v[right]进行排序 */
void qsort(char *v[], int left, int right) {
    int i, last;
    void swap(char *v[], int i, int j);

    if (left >= right)    /* 如果数组元素的个数小于2，则返回 */
        return;
    swap(v, left, (left + right)/2);
    last = left;
    for (i = left+1; i <= right; i++)
        if (strcmp(v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

同样，swap函数也只需要做一些很小的改动：

/* swap函数：交换v[i]和v[j] */
void swap(char *v[], int i, int j) {
    char *temp;

    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

因为v（别名为lineptr）的所有元素都是字符指针，并且temp也必须是字符指针，因此temp与v的任意元素之间可以互相复制。

练习5-7 重写函数readlines，将输入的文本行存储到由main函数提供的一个数组中，而不是存储到调用alloc分配的存储空间中。该函数的运算速度比改写前快多少？

5.7 多维数组

C语言提供了类似于矩阵的多维数组，但实际上它们并不像指针数组使用得那样广泛。本节将对多维数组的特性进行介绍。

我们考虑一个日期转换的问题：把某月某日这种日期表示形式转换为某年中第几天的表示形式，反之亦然。例如，3月1日是非闰年的第60天，是闰年的第61天。在这里，我们定义下列两个函数以进行日期转换：函数day_of_year将某月某日的日期表示形式转换为某一年中第几天的表示形式，函数month_day则执行相反的转换。因为后一个函数要返回两个值，所以在函数month_day中，月和日这两个参数使用指针的形式。例如，下列语句：

month_day(1988, 60, &m, &d)

将把m的值设置为2，把d的值设置为29（2月29日）。

这些函数都要用到一张记录每月天数的表（如“9月有30天”等）。对闰年和非闰年来说，每个月的天数不同，所以，将这些天数分别存放在一个二维数组的两行中比在计算过程中判断2月有多个天更容易。该数组以及执行日期转换的函数如下所示：

static char daytab[2][13] = {
    {0,31,28,31,30,31,30,31,31,30,31,30,31},
    {0,31,29,31,30,31,30,31,31,30,31,30,31},
};

/* day_of_year函数：将某月某日的日期表示形式转换为某年中某几天的表示形式 */
int day_of_year(int year, int month, int day) {
    int i, leap;

    leap = year%4 == 0 && year%100 != 0 || year%400 == 0;
    for (i = 1; i < month; i++)
        day += daytab[leap][i];
    return day;
}

/* month_day函数：将某年中第几天的日期表示形式转换为某月某日的表示形式 */
void month_day(int year, int yearday, int *pmonth, int *pday) {
    int i, leap;

    leap = year%4 == 0 && year%100 != 0 || year%400 == 0;
    for (i = 1; yearday > daytab[leap][i]; i++)
        yearday -= daytab[leap][i];
    *pmonth = i;
    *pday = yearday;
}

我们在前面的章节中曾讲过，逻辑表达式的算术运算值只可能是0（为假时）或者1（为真时）。因此，在本例中，可以将逻辑表达式leap用作数组daytab的下标。

数组daytab必须在函数day_of_year和month_day的外部进行声明，这样，这两个函数都可以使用该数组。这里之所以将daytab的元素声明为char类型，是为了说明在char类型的变量中存放较小的非字符整数也是合法的。

到目前为止，daytab是我们遇到的第一个二维数组。在C语言中，二维数组实际上是一种特殊的一维数组，它的每个元素也是一维数组。因此，数组下标应该写成

daytab[i][j] /* [行][列] */

而不能写成

daytab[i,j] /* 错误的形式 */

除了表示方式的区别外，C语言中二维数组的使用方式和其他语言一样。数组元素按行存储，因此，当按存储顺序访问数组时，最右边的数组下标（即列）变化得最快。类似行式存储的关系型数据库表，查询某行比查询某列要快得多。列式存储和行式存储在存储上没有区别，只是在逻辑上将行与列调换了。

数组可以用花括号括起来的初值表进行初始化，二维数组的每一行由相应的子列表进行初始化。在本例中，我们将数组daytab的第一列元素设置为0，这样，月份的值为1~12，而不是0~11。由于在这里存储空间并不是主要问题，所以这种处理方式比在程序中调整数组的下标更加直观。

如果将二维数组作为参数传递给函数，那么在函数的参数声明中必须指明数组的列数。数组的行数没有太大关系，因为前面已经讲过，函数调用时传递的是一个指针，它指向由行向量构成的一维数组，其中每个行向量是具有13个整型元素的一维数组。在该例子中，传递给函数的是一个指向很多对象的指针，其中每个对象是由13个整型元素构成的一维数组。因此，如果将数组daytab作为参数传递给函数f，那么f的声明应该写成下列形式：

f(int daytab[2][13]) {...}

也可以写成

f(int daytab[][13]) {...}

因为数组的行数无关紧要，所以，该声明还可以写成

f(int (*daytab)[13]) {...}

这种声明形式表明参数是一个指针，它指向具有13个整型元素的一维数组。因为方括号[]的优先级高于*的优先级，所以上述声明中必须使用圆括号。如果去掉括号，则声明变成

int *daytab[13]

这相当于声明了一个数组，该数组有13个元素，其中每个元素都是一个指向整型对象的指针。一般来说，除数组的第一维（下标）可以不指定大小外，其余各维都必须明确指定大小。

我们将在5.12节中进一步讨论更复杂的声明。

练习5-8 函数day_of_year和month_day中没有进行错误检查，请解决该问题。

5.8 指针数组的初始化

考虑这样一个问题：编写一个函数month_name(n)，它返回一个指向第n个月名字的字符串的指针。这是内部static类型数组的一种理想的应用。month_name函数中包含一个私有的字符串数组，当它被调用时，返回一个指向正确元素的指针。本节将说明如何初始化该名字数组。

指针数组的初始化语法和前面所讲的其他类型对象的初始化语法类似：

/* month_name函数：返回第n个月份的名字 */
char *month_name(int n) {
    static char *name[] = {
        "Illegal month",
        "January", "February", "March",
        "April", "May", "June",
        "July", "August", "September",
        "October", "November", "December"
    };
    return (n < 1 || n > 12) ? name[0] : name[n];
}

其中，name的声明与排序例子中lineptr的声明相同，是一个一维数组，数组的元素为字符指针。name数组的初始化通过一个字符串列表实现，列表中的每个字符串赋值给数组相应位置的元素。第i个字符串的所有字符存储在存储器中的某个位置，指向它的指针存储在name[i]中。由于上述声明中没有指明数组name的长度，因此，编译器编译时将对初值个数进行统计，并将这一准确数字填入数组的长度。

5.9 指针与多维数组

对于C语言的初学者来说，很容易混淆二维数组与指针数组之间的区别，比如上面例子中的name。假如有下面两个定义：

1
2

int a[10][20];
int *b[10];

那么，从语法角度讲，a[3][4]和b[3][4]都是对一个int对象的合法引用。但a是一个真正的二维数组，它分配了200个int类型长度的存储空间，并且通过常规的矩阵下标计算公式 20 x row + col（其中，row表示行，col表示列）计算得到元素a[row][col]的位置。但是，对b来说，该定义仅仅分配了10个指针，并且没有对它们初始化，它们的初始化必须以显式的方式进行，比如静态初始化或通过代码初始化。假定b的每个元素都指向一个具有20个元素的数组，那么编译器就要为它分配200个int类型长度的存储空间以及10个指针的存储空间。指针数组的一个重要优点在于，数组的每一行长度可以不同，也就是说，b的每个元素不必都指向一个具有20个元素的向量，某些元素可以指向具有2个元素的向量，某些元素可以指向具有50个元素的向量，而某些元素可以不指向任何向量。

尽管我们在上面的讨论中都是借助于整型进行讨论，但到目前为止，指针数组最频繁的用处是存放具有不同长度的字符串，比如函数month_name中的情况。结合下面的声明和图形化描述，我们可以做一个比较。下面是指针数组的声明和图形化描述（参见图5-9）：

图5-9

char *name[] = { "Illegal month", "Jan", "Feb", "Mar" };

    name:
     [· ]---->[Illegal month\0]
     [· ]---->[Jan\0]
     [· ]---->[Feb\0]
     [· ]---->[Mar\0]

下面是二维数组的声明和图形化描述（参见图5-10）：

图5-10

char aname[][15] = { "Illegal month", "Jan", "Feb", "Mar" };

   aname:
     [Illegal month\0 Jan\0               Feb\0               Mar\0     ]
      0               15                  30                  45

练习5-9 用指针方式代替数组下标方式改写函数day_of_year和month_day。

5.10 命令行参数

在支持C语言的环境中，可以在程序开始执行时将命令行参数传递给程序。调用主函数main时，它带有两个参数。第一个参数（习惯上称为argc，用于参数计数）的值表示运行程序时命令行中参数的数目；第二个参数（称为argv，用于参数向量）是一个指向字符串数组的指针，其中每个字符串对应一个参数。我们通常用多级指针处理这些字符串。

最简单的例子是程序echo，它将命令行参数回显在屏幕上的一行中，其中命令行中各参数之间用空格隔开。也就是说，命令：

echo hello, world

将打印下列输出：

hello, world

按照C语言的约定，argv[0]的值是启动该程序的程序名，因此argc的值至少为1。如果argc的值为1，则说明程序名后面没有命令行参数。在上面的例子中，argc的值为3，argv[0]、argv[1]和argv[2]的值分别为"echo"、“hello,“以及"world”。第一个可选参数为argv[1]，而最后一个可选参数为argv[argc-1]。另外，ANSI标准要求argv[argc]的值必须为一空指针（参见图5-11）。

图 5-11
argv:
   [· ]--->[· ]---->[echo\0]
           [· ]---->[hello,\0]
           [· ]---->[world\0]
           [0 ]

程序echo的第一个版本将argv看成是一个字符指针数组：

#include <stdio.h>

/* 回显程序命令行参数：版本1 */
main(int argc, char *argv[]) {
    int i;

    for (i = 1; i < argc; i++)
        printf("%s%s", argv[i], (i < argc -1) ? " " : "");
    printf("\n");
    return 0;
}

因为argv是一个指向指针数组的指针，所以，可以通过指针而非数组下标的方式处理命令行参数。echo程序的第二个版本是在对argv进行自增运算、对argc进行自减运算的基础上实现的，其中argv是一个指向char类型的指针的指针：

#include <stdio.h>

/* 回显程序命令行参数：版本2 */
main(int argc, char *argv[]) {
    while (--argc > 0)
        printf("%s%s", *++argv, (argc > 1) ? " " : "");
    printf("\n");
    return 0;
}

因为argv是一个指向参数字符串数组起始位置的指针，所以，自增运算(++argv)将使得它在最开始指向argv[1]而非argv[0]。每执行一次自增运算，就使得argv指向下一个参数，*argv就是指向那个参数的指针。与此同时，argc执行自增运算，当它变成0时，就完成了所有参数的打印。

也可以将printf语句写成下列形式：

printf((argc > 1) ? "%s " : "%s", *++argv);

这就说明，printf的格式化参数也可以是表达式。

我们来看第二个例子。在该例子中，我们将增强4.1节中模式查找程序的功能。在4.1节中，我们将查找模式内置到程序中了，这种解决方法显然不能令人满意。下面我们来仿效UNIX程序grep的实现方法改写模式查找程序，通过命令行的第一个参数指定待匹配的模式。

#include <stdio.h>
#include <string.h>
#define MAXLINE 1000

int getLine(char *line, int max);

/* find函数：打印与第一个参数指定的模式匹配的行 */
main(int argc, char *argv[]) {
    char line[MAXLINE];
    int found = 0;

    if (argc != 2)
        printf("Usage: find pattern\n");
    else
        while(getLine(line, MAXLINE) > 0)
            if (strstr(line, argv[1]) != NULL) {
                printf("%s", line);
                found++;
            }
    return found;
}

标准库函数strstr(s,t)返回一个指针，该指针指向字符串t在字符串s中第一次出现的位置；如果字符串t没有在字符串s中出现，函数返回NULL（空指针）。该函数声明在头文件<string.h>中。

为了更进一步地解释指针结构，我们来改进模式查找程序。假定允许程序带两个可选参数。其中一个参数表示“打印除匹配模式之外的所有行”，另一个参数表示“每个打印的文本行前面加上相应的行号”。

UNIX系统中的C语言程序有一个公共的约定：以负号开头的参数表示一个可选标志或参数。假定用-x（代表“除……之外”）表示打印所有与模式不匹配的文本行，用-n（代表“行号”）表示打印行号，那么下列命令：

find -x -n 模式

将打印所有与模式不匹配的行，并在每个打印行的前面加上行号。

可选参数应该允许以任意次序出现，同时，程序的其余部分应该与命令行中参数的数目无关。此外，如果可选参数能够组合使用，将会给使用者带来更大的方便，比如：

find -nx 模式

改写后的模式查找程序如下所示：

#include <stdio.h>
#include <string.h>
#define MAXLINE  1000

int getLine(char *line, int max);

/* find函数：打印所有与第一个参数指定的模式相匹配的行 */
main(int argc, char *argv[]) {
    char line[MAXLINE];
    long lineno = 0;
    int c, except = 0, number = 0, found = 0;

    while(--argc > 0 && (*++argv)[0] == '-')
        while (c = *++argv[0])
            switch(c) {
            case 'x':
                except = 1;
                break;
            case 'n':
                number = 1;
                break;
            default:
                printf("find: illegal option %c\n", c);
                argc = 0;
                found = -1;
                break;
            }
    if (argc != 1)
        printf("Usage: find -x -n pattern\n");
    else
        while(getLine(line, MAXLINE) > 0) {
            lineno++;
            if ((strstr(line, *argv) != NULL) != except) {
                if (number)
                    printf("%ld:", lineno);
                printf("%s", line);
                found++;
            }
        }
    return found;
}

在处理每个可选参数之前，argc执行自减运算，argv执行自增运算。循环语句结束时，如果没有错误，则argc的值表示还没有处理的参数数目，而argv则指向这些未处理参数中的第一个参数。因此，这时argc的值应为1，而*argv应该指向模式。注意，*++argv是一个指向参数字符串的指针，因此(*++argv)[0]是它的第一个字符（另一种有效形式是**++argv）。因此[]与操作数的结合优先级比*和++高，所以在上述表达式中必须使用圆括号，否则编译器将会把该表达式当做*++(argv[0])。实际上，我们在内层循环中就使用了表达式*++argv[0]，其目的是遍历一个特定的参数串。在内层循环中，表达式*++argv[0]对之指针argv[0]进行了自增运算。

很少有人使用比这更复杂的指针表达式。如果遇到这种情况，可以将它们分为两步或三步来理解，这样会更直观一些。

练习5-10 编写程序expr，以计算从命令行输入的逆波兰表达式的值，其中每个运算符或操作数用一个单独的参数表示。例如，命令

expr 2 3 4 + *

将计算表达式2x(3+4)的值。

练习5-11 修改程序entab和detab（第1章练习中编写的函数），使它们接受一组作为参数的制表符停止位。如果启动程序时不带参数，则使用默认的制表符停止位设置。

练习5-12 对程序entab和detab的功能做一些扩充，以接受下列缩写的命令：

entab -m +n

表示制表符从第m列开始，每隔n列停止。选择（对使用者而言）比较方便的默认行为。

练习5-13 编写程序tail，将其输入中的最后n行打印出来。默认情况下，n的值为10，但可通过一个可选参数改变n的值，因此，命令

tail -n

将打印其输入的最后n行。无论输入或n的值是否合理，该程序都应该能正常运行。编写的程序要充分地利用存储空间；输入行的存储方式应该同5.6节中排序程序的存储方式一样，而不采用固定长度的二维数组。

5.11 指向函数的指针

在C语言中，函数本身不是变量，但可以定义指向函数的指针。这种类型的指针可以被赋值、存放在数组中、传递给函数以及作为函数的返回值等等。为了说明指向函数的指针的用法，我们接下来将修改本章前面的排序函数，在给定可选参数-n的情况下，该函数将按数值大小而非字典顺序对输入行进行排序。

排序程序通常包括3部分：判断任何两个对象之间次序的比较操作、颠倒对象次序的交换操作、一个用于比较和交换对象直到所有对象都按正确次序排序的排序算法。由于排序算法与比较、交换操作无关，因此，通过在排序算法中调用不同的比较和交换函数，便可以实现按照不同的标准排序。这就是我们的新版本排序函数所采用的方法。

我们在前面讲过，函数strcmp按字典顺序比较两个输入行。在这里，我们还需要一个以数值为基础来比较两个输入行，并返回与strcmp同样的比较结果的函数numcmp。这些函数在main之前声明，并且，指向恰当函数的指针将被传递给qsort函数。在这里，参数的出错处理并不是问题的重点，我们将主要考虑指向函数的指针问题。

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

#define MAXLINES 5000       /* 待排序的最大行数 */
char *lineptr[MAXLINES];    /* 指向文本行的指针 */

int readline(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);

void qsort(void *lineptr[], int left, int right,
           int (*comp)(void *, void *));
int numcmp(char *, char *);

/* 对输入的文本行进行排序 */
main(int argc, char *argv[]) {
    int nlines;               /* 读入的输入行数 */
    int numberic = 0;         /* 若进行数值排序，则numberic的值为1 */

    if (argc > 1 && strcmp(argv[1], "-n") == 0)
        numeric = 1;
    if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
        qsort((void **) lineptr, 0, nlines-1,
          (int (*)(void*,void*))(numeric ? numcmp : strcmp));
        writelines(lineptr, nlines);
        return 0;
    } else {
        printf("input too big to sort\n");
        return 1;
    }
}

在调用函数qsort的语句中，strcmp和numcmp是函数的地址。因为它们是函数，所以前面不需要加上取地址运算符&。

改写后的qsort函数能够处理任何数据类型，而不仅仅限于字符串。从函数qsort的原型可以看出，它的参数表包括一个指针数组、两个整数和一个有两个指针参数的函数。其中，指针数组参数的类型为通用指针类型void *。由于任何类型的指针都可以转换为void *类型，并且在将它转换回原来的类型时不会丢失信息，所以，调用qsort函数时可以将参数强制转换为void *类型。比较函数的参数也要执行这种类型的转换。这种转换通常不会影响到数据的实际表示，但要确保编译器不会报错。

/* qsort函数：以递增顺序对v[left]...v[right]进行排序 */
void qsort(void *v[], int left, int right,
           int (*comp)(void *, void *)) {
    int i, last;
    void swap(void *v[], int, int);

    if (left >= right)   /* 如果数组元素个数小于2，则不执行任何操作 */
        return;
    swap(v, left, (left + right)/2);
    last = left;

    for (i = left+1; i <= right; i++)
        if ((*comp)(v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    qsort(v, left, last-1, comp);
    qsort(v, last+1, right, comp);
}

我们仔细研究一下其中的声明。qsort函数的第四个参数声明如下：

int (*comp)(void *, void *)

它声明comp是一个指向函数的指针，该函数具有两个void *类型的参数，其返回值类型为int。

在下列语句中：

if ((*comp)(v[i], v[left]) < 0)

comp的使用和其声明是一致的，comp是一个指向指针的指针，*comp代表一个函数。下列语句是对该函数进行调用：

(*comp)(v[i], v[left])

其中的圆括号是必须的，这样才能够保证其中的各个部分正确结合。如果没有括号，例如写成下面的形式：

int *comp(void *, void *) /* 错误的写法 */

则表明comp是一个函数，该函数返回一个指向int类型的指针，这同我们的本意显然有很大的差别。

我们在前面讲过函数strcmp，它用于比较两个字符串。这里介绍的函数numcmp也是比较两个字符串，但它通过调用atof计算字符串对应的数值，然后在此基础上进行比较：

#include <stdlib.h>

/* numcmp函数：按数值顺序比较字符串s1和s2 */
int numcmp(char *s1, char *s2) {
    double v1, v2;

    v1 = atof(s1);
    v2 = atof(s2);
    if (v1 < v2)
        return -1;
    else if (v1 > v2)
        return 1;
    else
        return 0;
}

交换两个指针的swap函数和本章前面所述的swap函数相同，但它的参数声明为void *类型。

void swap(void *v[], int i, int j) {
    void *temp;

    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

还可以将其他一些选项增加到排序程序中，有些可以作为较难的练习。

练习5-14 修改排序程序，使它能处理-r标记。该标记表明，以逆序（递减）方式排序。要保证-r和-n能够组合在一起使用。

练习5-15 增加选项-f，使得排序过程不考虑字母大小写之间的区别。例如，比较a和A时认为它们相等。

练习5-16 增加选项-d（代表目录顺序）。该选型表明，只对字母、数字和空格进行比较。要保证该选项可以和-f组合在一起使用。

练习5-17 增加字段处理功能，以使得排序程序可以根据行内的不同字段进行排序，每个字段按照一个单独的选项集合进行排序。（在对本书索引进行排序时，索引条码使用了-df选项，而对页码排序时使用了-n选项。）

5.12 复杂声明

C语言常常因为声明的语法问题而受到人们的批评，特别是涉及到函数指针的语法。C语言的语法力图使声明和使用相一致。对于简单的情况，C语言的做法是很有效的，但是，如果情况比较复杂，则容易让人混淆，原因在于，C语言的声明不能从左至右阅读，而且使用了太多的圆括号。我们来看下面所示的两个声明：

int *f(); /* f: 是一个函数，它返回一个指向int类型的指针 */

以及

int (*pf)(); /* pf: 是一个指向函数的指针，该函数返回一个int类型的对象 */

它们之间的含义差别说明： *是一个前缀运算符，其优先级低于()，所以，声明中必须使用圆括号以保证正确的结合顺序。

尽管实际中很少用到过于复杂的声明，但是，懂得如何理解甚至如何使用这些复杂的声明是很重要的。如何创建复杂的声明呢？一种比较好的方法是，使用typedef通过简单的步骤合成，这种方法我们将在6.7节中讨论。这里介绍另一种方法。接下来讲述的两个程序就使用这种方法：一个程序用于将正确的C语言声明转换为文字描述，另一个程序完成相反的转换。文字描述是从左至右阅读的。

第一个程序dcl复杂一些。它将C语言的声明转换为文字描述，比如：

char **argv
    argv:  pointer to pointer to char
int (*daytab)[13]
    daytab:  pointer to array[13] of int
int *daytab[13]
    daytab:  array[13] of pointer to int
void *comp()
    comp:  function returning pointer to void
void (*comp)()
    comp:  pointer to function returning void
char (*(*x())[])()
    x:  function returning pointer to array[] of
    pointer to function returning char
char (*(*x[3])())[5]
    x:  array[3] of pointer to function returning
    pointer to array[5] of char

程序dcl是基于声明符的语法编写的。附录A以及8.5节将对声明符的语法进行详细的描述。下面是其简化的语法形式：

dcl:         前面带有可选的*的direct-dcl
direct-dcl:  name
             (dcl)
             direct-dcl()
             direct-dcl[ 可选的长度 ]

简而言之，声明符dcl就是前面可能带有多个*的direct-dcl。direct-dcl可以是name、由一对圆括号括起来的dcl、后面跟有一对圆括号的direct-dcl、后面跟有用方括号括起来的表示可选长度的direct-dcl。

该语法可用来对C语言的声明进行分析。例如，考虑下面的声明符：

(*pfa[])()

按照该语法分析，pfa将被识别为一个name，从而被认为是一个direct-dcl。于是，pfa[]也是一个direct-dcl。接着，*pfa[]被识别为一个dcl，因此，判定(*pfa[])是一个direct-dcl。再接着，(*pfa[])()被识别为一个direct-dcl，因此也是一个dcl。可以用图5-12所示的语法分析树来说明分析的过程（其中direct-dcl缩写为dir-dcl）。

图 5-12

(   *   pfa   []    )    ()
|   |    |     |    |     |
|   |  name    |    |     |
|   |    |     |    |     |
|   |  dir-dcl |    |     |
|   |    |     |    |     |
|   |  dir-dcl-+    |     |
|   |    |          |     |
|   +---dcl         |     |
|        |          |     |
+------dir-dcl------+     |
         |                |
       dir-dcl------------+
         |
        dcl

程序dcl的核心是两个函数：dcl与dirdcl，它们根据声明符的语法对声明进行分析。因为语法是递归定义的，所以在识别一个声明的组成部分时，这两个函数是相互递归调用的。我们称该函数是一个递归下降语法分析程序。

/* dcl函数：对一个声明符进行语法分析 */
void dcl(void) {
    int ns;

    for (ns = 0; gettoken() == '*';)   /* 统计字符*的个数 */
        ns++;
    dirdcl();
    while (ns-- > 0)
        strcat(out, " pointer to");
}
/* dirdcl函数：分析一个直接声 */
void dirdcl(void) {
    int type;

    if (tokentype == '(' ) {        /* 形式为(dcl)  */
        dcl();
        if (tokentype != ')' )
            printf("error: missing )\n");
    } else if (tokentype == NAME)    /* 变量名 */
        strcpy(name, token);
    else
        printf("error: expected name or (dcl)\n");
    while ((type=gettoken()) == PARENS || type == BRACKETS)
        if (type == PARENS)
            strcat(out, " function returning");
        else {
            strcat(out, " array");
            strcat(out, token);
            strcat(out, " of");
        }
}

该程序的目的旨在说明问题，并不想做得尽善尽美，所以对dcl有很多限制。它只能处理类似于char或int这样的简单数据类型，而无法处理函数中的参数类型或类似于const这样的限定符。它不能处理带有不必要空格的情况。由于没有完备的出错处理，因此它也无法处理无效的声明。这些方面的改进留给读者做练习。

下面是该程序的全局变量和主程序：

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

#define MAXTOKEN  100

enum { NAME, PARENS, BRACKETS };

void dcl(void);
void dirdcl(void);
int gettoken(void);
int tokentype;            /* 最后一个记号的类型 */
char token[MAXTOKEN];     /* 最后一个记号字符串 */
char name[MAXTOKEN];      /* 标识符名 */
char datatype[MAXTOKEN];  /* 数据类型为char、int 等 */
char out[1000];           /* 输出串 */

main() {    /* 将声明转换为文字描述 */
    while (gettoken() != EOF) {  /* 该行的第一个记号是数据类型 */
        strcpy(datatype, token);
        out[0] = '\0';
        dcl();      /* 分析该行的其余部分 */
        if (tokentype != '\n')
            printf("syntax error\n");
        printf("%s: %s %s\n", name, out, datatype);
    }
    return 0;
}

函数gettoken用来跳过空格与制表符，与查找输入中的下一个记号。“记号”（token）可以是一个名字，一对圆括号，可能包含一个数字的一对方括号，也可以是其他任何单个字符。

int gettoken(void) {     /* 返回下一个标记 */
    int c, getch(void);
    void ungetch(int);
    char *p = token;

    while ((c = getch()) == ' ' || c == '\t')
        ;
    if (c == '(') {
        if ((c = getch()) == ')') {
            strcpy(token, "()");
            return tokentype = PARENS;
        } else {
            ungetch(c);
            return tokentype = '(';
        }
    } else if (c == '[') {
        for (*p++ = c; (*p++ = getch()) != ']'; )
            ;
        *p = '\0';
        return tokentype = BRACKETS;
    } else if (isalpha(c)) {
        for (*p++ = c; isalnum(c = getch()); )
            *p++ = c;
        *p = '\0';
        ungetch(c);
        return tokentype = NAME;
    } else
        return tokentype = c;
}

有关函数getch和ungetch的说明，参见第4章。

如果不在乎生成多余的圆括号，另一个方向的转换要更容易一些。为了简化程序的输入，我们将“x is a function returning a pointer to an array of pointers to functions returning char” （x是一个函数，它返回一个指针，该指针指向一个一维数组，该一维数组的元素为指针，这些指针分别指向多个函数，这些函数的返回值为char类型）的描述用下列形式表示：

x () * [] * () char

程序undcl将把该形式转换为：

char (*(*x())[])()

由于对输入的语法进行了简化，所以可以重用上面定义的gettoken函数。undcl和dcl使用相同的外部变量。

/* undcl函数：将文字描述转换为声明 */
main() {
    int type;
    char temp[MAXTOKEN];

    while (gettoken() != EOF) {
        strcpy(out, token);
        while((type = gettoken()) != '\n')
            if (type == PARENS || type == BRACKETS)
                strcat(out, token);
            else if (type == '*') {
                sprintf(temp, "(*%s)", out);
                strcpy(out, temp);
            } else if (type == NAME) {
                sprintf(temp, "%s %s", token, out);
                strcpy(out, temp);
            } else
                printf("invalid input at %s\n", token);
        printf("%s\n", out);
    }
    return 0;
}

练习5-18 修改dcl程序，是它能够处理输入中的错误。

练习5-19 修改undcl程序，使它在把文字描述转换为声明的过程中不会生成多余的圆括号。

练习5-20 扩展dcl程序的功能，使它能够处理包含其他成分的声明，例如带有函数参数类型的声明、带有类似于const限定符的声明等。

专题: C程序设计语言

本文发表于 2022-09-13，最后修改于 2022-09-13。

本站永久域名「 jiavvc.top 」，也可搜索「后浪笔记一零二四」找到我。

上一篇 « C程序设计语言-第6章结构下一篇 » C程序设计语言-第4章函数与程序结构