从头学C(6): 指针和数组

2014-01-06 约 16821 字预计阅读 34 分钟

指针是一种保存变量地址的变量。在C语言中，指针的使用非常广泛，因为使用指针通常可以生成更高效、更紧凑的代码。

指针和goto语句一样，会导致程序难以理解，因此需要谨慎的使用指针。

第五章指针与数组

ANSI C的一个重要变化是，它明确了操作指针的规则，并使用类型void*代替char*作为通用指针的类型。

5.1 指针与地址

通过一个简单示意图来看下内存如何存储数据的。

一般机器都有一系列连续编号/编址的存储单元，这些存储单元可以单个操作，也可以连续成组的操作。而机器的一个字节可以存放一个char类型的数据，两个相邻字节存储单元可存放一个short类型的数据，四个相邻字节存储单元可存储一个long类型的数据。

指针是能够存放一个地址的一组存储单元（在32位机器上通常是4个字节，在64位机器上通常是8个字节）。

假如c是一个char类型变量，p是一个指向c的指针，那么可用下图来表示它们的关系：

一元运算符&用于取一个对象的地址。我们称p是一个指向c的指针，实际上是把c的地址赋给变量p，如下列语句：

p = &c;

要注意：地址运算符&只能用于内存中的对象，即变量与数组元素，它不能作用于表达式、常量或register类型的变量。

与取对象地址相对应的是，一元运算符*是间接寻址或间接引用运算符。它作用于指针时，是访问指针所指向的对象。

下面这段代码详细说明了关于&和*运算符的使用，以及如何声明指针：

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

ip = &x;    /* 取变量 x 的地址赋给ip，ip 现在指向变量 x */
y = *ip;    /* 取 ip 所指向的单元的值，赋给变量 y， y = 1 */
*ip = 0;    /* 将 ip 所指向的单元的值修改为 0，即将变量 x 的值改为 0 */
ip = &z[0]; /* ip 指向数组 z 的第一个单元，即 z[0] */

可以看到指针的声明是int *ip，该声明是为了便于记忆，表明表达式*ip的结果是int类型。基于同样的原因，对函数的声明也可以采用这种方式，例如：

double *dp, atof(char *);

其中*dp和atof(s) 的值都是double类型，其atof的参数是一个指向char类型的指针。

细心的同学应该注意到了，指针只能指向某种特定类型的对象，比如int、double，也就是说每个指针都必须指向某种特定的数据类型。（当然指向void类型的指针是个例外，后面我们会看到它的特性）

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

y = *ip + 1;

是把ip指向的对象的值取出来并加1，再讲结果赋给y。

另外，

*ip += 1;

是将ip指向的对象的值加1，等价于：

++*ip;

和

(*ip)++;

语句(*ip)++中的圆括号不能省略，否则该表达式的实际结果是对ip进行加1运算。这是因为类似*和++这样的一元运算符遵循从右到左的结合顺序，所以我们建议即使是类似++*p的语句，最好也都显式的加上圆括号，以强调语句执行的意图，即 ++(*p)。

最后，指针作为变量，是可以在程序中直接使用的，不必通过间接引用的方法。比如，如果iq是另一个指向int类型的指针，那么下列语句

iq = ip;

是将ip的值（ip所指向单元的地址）拷贝到iq中，这样指针iq也将指向ip所指向的对象。

5.2 指针与函数参数

C语言中函数调用是以传值的方式将参数值传递给被调函数的，也就是说传递的是变量的值，而不是变量本身，因此被调函数不能修改主调函数中的变量的值。

但有了指针之后，这便不是个问题了。来看一个排序时，交换两个元素顺序的例子：

void swap(int x, int y)   /* Wrong!!! */
{
    int temp;

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

以上是个错误的例子，调用swap(a, b)并不能达到我们想要的结果，因为这个 swap()函数仅仅只是交换了a和b的副本的值，并没有将主调函数中的a和b的值调换。

解决办法是，将a和b的地址（也就是指针）作为参数传递给swap函数：

void swap(int *px, int *py)  /* interchange *px and *py */
{
    int temp;

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

调用swap(&a, &b)来实现a和b的值调换，因为通过指向a和指向b的指针，我们是间接地访问a和b的内存存储单元。通过下面这个图，可以看出实际变量与指针参数的关系：

指针参数使得被调函数能够访问和修改主调函数中对象的值。

再来看一个getint函数的例子。getint()接受自由格式的输入，并执行转换，将输入的字符流分解成整数，且每次调用得到一个整数。而且getint()需要返回转换后得到的整数，且在到达输入结尾时要返回文件结束标记。

设计思路是：将标识是否到达文件结尾的状态作为getint函数的返回值，同时，利用一个指针参数存储转换后得到的整数，并传回给主调函数。

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

#include <ctype.h>

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

/* getint: get next integer from input into *pn */
int getint(int *pn)
{
    int c, sign;

    while(isspace(c = getch()))   /* skip white space */
        ;   
    if(!isdigit(c) && c != EOF && c != '+' && c != '-') {
        ungetch(c);     /* it is not a number */
        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;
}

*pn始终作为一个普通的整型变量使用。其中还利用getch和ungetch函数，保证getint能确定读到的是一个完整整数且不影响下一次整数的读取。

这时，我们利用下面的循环语句调用getint函数，来给一个int类型数组赋值：

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

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

这里必须将array[n]的地址传递给函数getint，否则getint()将无法把转换得到的整数传回给主调函数。

5.3 指针与数组

指针和数组的关系密不可分，通过数组下标所能完成的任何操作都可以通过指针来实现，而且一般用指针编写的程序比用数组下标编写的程序执行速度快，虽然用指针实现的程序要更难理解一些……

int a[10];

上方表达式定义了一个长度为10的数组a，也就是定义了一个由10个对象组成的集合，并且这10个对象存在相邻的内存区域中，名字是a[0]、a[1]、……、a[9]，如下图：

对应的a[i]表示数组的第i个元素（数组的下标是从 0 开始算的）。

int *pa;

上方表达式说明pa是一个指向整型对象的指针，那么赋值语句：

pa = &a[0];

是将指针pa指向数组a的第 0 个元素，示意图如下：

那么访问*pa便是访问数组元素a[0]的值，比如我们可以用x = *pa来将a[0]的值复制到变量x中。

如果pa指向数组的某个元素，那么根据指针运算的定义，我们得知：

指针pa + 1指向下一个元素，以此类推pa + i将指向pa所指向的数组元素之后的第i个元素；
指针pa – 1指向前一个元素，类似pa – i指向pa所指向的数组元素之前的第i个元素。

因此，如果pa指向a[0]，那么*(pa+1)引用的是数组元素a[1]的值，同理pa + i是数组元素a[i]的内存地址，*(pa + i)是引用数组元素a[i]的值。

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

由于数组名所代表的是该数组最开始的第0个元素的地址，所以下方两个表达式是等价的：

pa = &a[0];
//等价于
pa = a;

对数组元素a[i]的引用也可以写成*(a+i)或*(pa+i)这种形式。在访问数组元素a[i]时，C语言实际上也是先将其转换为*(a+i)的形式，再进行求值，所以我们也可以得出这样的结论：&a[i]和a+i的含义是相同的，pa[i]和*(pa+i)也是等价的。

简而言之，一个通过数组和下标实现的表达式可以等价地通过指针和偏移量实现。

但数组名和指针有一个不同的地方要注意是：指针是一个变量，因此语句pa = a和pa++都是合法的，但数组名不是变量，类似a = pa以及a++是非法的语句。

当把数组名以参数形式传递给一个函数时，实际传递的是该数组的第 0 个元素的地址，在被调函数中，该参数是一个局部变量，因此数组名参数必须是一个指针。

来看下面这个计算一个字符串长度的strlen函数：

/* strlen: retrun length of string s */
int strlen(char *s) 
{
    int n;

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

s是一个指针，因此执行自增运算是合法的。s++操作并不会影响到主调函数传递过来的字符串，它仅仅是对改指针在strlen函数中的副本进行自增运算，所以类似：

strlen("hello, world"); /* string constant */
strlen(array);          /* char array[100] */
strlen(ptr);            /* char *ptr */

都可以正确被执行。

在函数定义中，形式参数char s[]等价于char *s，我们更习惯于第二种方式（更直观的说明该参数是一个指针）。

除了把第1个元素的地址传递给函数，显然我们也可以把任意一个元素的地址传递给函数，比如：f(&a[2])等价于f(a+2)，都是把a[2]的地址传递给函数f，函数f的声明可以是：

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

或者

f(int *arr) { ... }

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

如果确信相应的元素存在，也可以通过下标直接访问数组第一个元素之前的元素。类似arr[-1]、arr[-2]这样的表达式在语法上是合法的。

但是请注意：引用数组边界以外的对象是非法的！编译器不一定能检查出此类错误，但程序运行时可能带来会导致未定义的行为。

5.4 地址算术运算

如果p是一个指向数组中某个元素的指针，对p进行增量运算（比如p = p + i）可以使其指向p当前所指向的元素之后的第i个元素。这类运算可以说是指针或地址算术运算中最简单的形式了。

C语言的地址算术运算方法是一致且有规律的，将指针、数组、地址的算术运算集成在一起，也是C语言的一大优点。为了说明这一点，来看一个简单但并不完善的存储分配程序（之所以说是不完善的，因为对于连续的alloc函数调用，在释放时必须以相反的顺序依次调用afree函数）：

#define ALLOCSIZE 10000 /* size of available space */

static char allocbuf[ALLOCSIZE];  /* storage for alloc */
static char *allocp = allocbuf;   /* next free position */
char *alloc(int n)      /* return pointer to n characters */
{
    if( allocbuf + ALLOCSIZE - allocp >= n) { /* it fits */
        allocp += n;
        return allocp - n; /* old p */
    } else
        return 0;
}

void afree(char *p)     /* free storage pointed to p */
{
    if(p >= allocbuf && p < allocbuf + ALLOCSIZE)
        allocp = p;
}

函数alloc(n)返回一个指向n个连续字符存储单元的指针，函数afree(p)释放已分配的存储空间，以便后续重用。

程序开始位置定义了一个外部变量allocbuf（占10000个char类型存储空间的字符数组，作为“内存分配池”，当然这并不是严格意义上的内存池），作为alloc和afree的私有数组，该变量也是被声明为static类型，使其对外不可见。

使用指针aloocp来指向allocbuf中的下一个空闲单元，而且在程序的开始位置被初始化了，使其指向allocbuf的起始地址（即&allocbuf[0]）。通常，对指针有意义的初始化只能是0或者是表示地址的表达式（而且一定要是在此前已定义的具有适当类型的数据的地址）。

在alloc函数中，通过if条件判断allocbuf中是否还有足够的空间分配，如果有，则返回分配的空间的首地址；如果没有足够的空间，则返回 0。

C语言保证，0 永远不是有效的数据地址，因此，返回值 0 可以用来表示申请空间失败。

指针与整数之间不能相互转换，但 0 是唯一的例外，常量0可以赋给指针，指针也可以和0进行比较。很多地方都会用符号常量NULL代替常量0，更清晰地说明常量0是指针的一个特殊值。

在alloc和afree函数中，都有if条件判断，对指针进行了比较和加减的算术运算，总结下来有这么几个特点：

如果指针p和q指向同一个数组的成员，他们之间可以进行类似于==、!=、<、>=的关系比较运算。如果p指向的数组元素位置在q指向的数组元素位置之后，则p > q。
如果指针p和q指向不同的数组的成员，它们之间的算术或比较运算时没有定义的。
任何指针与 0 进行==或!=的比较运算是有意义的，用于表明指针是否有效。
指针可以和整数进行相加或相减运算。

关于指针和整数的相加/相减运算，需要特别说明是，

结构p + n指向p当前所指对象之后的第n个对象的地址，无论指针p指向的对象是何种类型，该结论都成立。
p指向的对象的长度取决于p的声明，例如，int类型占 4 个字节的存储空间，对应的n将按 4 的倍数来计算，如p + 2意味着地址 + 8。

指针的减法和加法类似，所以表达式allocbuf + ALLOCSIZE – allocp表示allocbuf中空闲的存储空间。利用这个结论，我们可以写出另一个版本的strlen函数：

/* strlen: return length of string s */
int strlen(char *s) 
{
    char *p = s;

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

指针p指向字符串s的第一个字符，通过while循环检查字符串中的每个字符，每执行一次p++，p就指向下一个字符，直到遇见字符串结束符'\0'，因此p - s表示已经检查过的字符数，即字符串长度。

指针的算术运算具有一致性：如果处理的数据类型比char型或int型占据更多的存储空间，如float类型，并且p是一个指向float类型的指针，那么在执行p++后，p将指向下一个浮点数的地址。

所有的指针运算都会自动考虑它所指向的对象的长度。

合法的指针运算包括：

相同类型指针之间的赋值运算；
指针同整数之间的加法/减法运算；
指向相同数组中元素的两个指针间的减法或比较运算；（注意加法是非法的）
将指针赋值为0，或指针与0之间的比较运算。

其他所有形式的指针运算都是非法的，例如：

两个指针间的加法、乘法、除法、移位、屏蔽运算；
指针同float或double类型之间的加法运算；
不经强制类型转换，在不同类型指针之间进行直接赋值。

5.5 字符指针与函数

字符串常量是一个字符数组，例如："I am a string"，以空字符'\0'结尾，所以字符串常量占据的存储单元数比双引号内的字符数要多1个。

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

printf("hello, world\n");

实际上printf函数接受的是一个指向字符数组第一个字符的指针，通过字符指针来访问该字符串。也就是，字符串常量可以通过一个指向其第一个元素的指针访问。

字符串常量还用来初始化指针变量。例如我们声明一个指针：

char *pmessage;

那么语句：

pmessage = "now is the time";

将把该字符串常量第一个字符的地址赋给pmessage，也就是说pmessage将指向该字符串常量。

要注意的是：该过程并没进行字符串的复制，而仅仅是指针指向特定对象的操作。

C语言没有提供将整个字符串作为一个整体进行处理的运算符！

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

char amessage[] = "now is the time";    /* 定义了一个数组 */
char *pmessage  = "now is the time";    /* 定义了一个指针 */

amessage是一个只能存放初始化字符串以及空字符'\0'的一维数组。数组中单个字符可以进行修改，且amessage始终指向同一个存储位置。

pmessage是一个指针，其初值指向一个字符串常量，后续可以被修改以指向其他地址，但如果试图修改字符串的内容，结果是未定义的。

通过一个最简单的例子来看字符指针与字符数组的差异：

#include <stdio.h>

int main()
{
    char *pa = "hello";
    char pb[] = "world";

    pa[0] = '1';    /* 非法操作 */
    pa[1] = '1';    /* 非法操作 */

    pb[0] = '2';    /* 合法操作 */
    pb[1] = '2';    /* 合法操作 */

    printf("pa = %s\n", pa);
    printf("pb = %s\n", pb);

    return 0;
}

该程序编译可以通过，但运行时会报“Segmentation fault”。把第 8、 9 行注释掉，程序就运行正常了。

通过几个不同版本的字符串拷贝函数strcpy（把指针t所指向的字符串复制到指针s所指向的存储单元）来看下字符指针和字符数组的使用方法。

注意：如果使用语句s = t来实现，其实只是把s指向t所指的同一个存储位置而已，并没有进行字符的复制。

第一个版本，通过字符数组的方法实现：

/* strcpy: copy t to s; array subscript version */
void strcpy(char *s, char *t)
{
    int i;

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

为了便于比较，第二个版本通过字符指针的方式实现：

/* strcpy: copy t to s; pointer version */
void strcpy(char *s, char *t) 
{
    while((*s = *t)  != '\0') {
        s++;
        t++;
    }   
}

两种方法都可以实现同样的功能，因为参数是通过值传递的，所以在strcpy函数中可以以任何方式使用参数s和t。

然而，经验丰富的程序员会用更精炼的语句写出strcpy函数：

/* strcpy: copy t to s; pointer version 2 */
void strcpy(char *s, char *t) 
{
    while((*s++ = *t++)  != '\0')
        ;   
}

表达式*t++是执行自增运算之前t所指向的字符，在读取该字符之后，自增运算符才会使t指向下一个字符。

表达式*s++也是同样的过程，在执行自增运算之前，t所指向的字符被拷贝到s所指向的存储单元，然后s才指向想一个存储单元。另外，当前拷贝到s所指向单元的字符会进行一个判断，是否为字符串结束符'\0'。

我们应该注意到，上例的字符串结束符'\0'判断是多余的，因为我们还只需判断表达式(*s++ = *t++)是否为0即可，所以，更精炼的程序是：

/* strcpy: copy t to s; pointer version 3 */
void strcpy(char *s, char *t)
{
    while(*s++ = *t++)
        ;
}

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

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

第一个版本，通过字符数组实现：

/* strcmp: retrun <0 if s<t, 0 if s==t, >0 if s>t*/
int strcmp(char *s, char *t) 
{
    int i;
    for(i = 0; s[i] == t[]; i++)
        if(s[i] == '\0')
            return 0;
    return s[i] - t[i];
}

下面是指针方式实现的：

/* strcmp: retrun <0 if s<t, 0 if s==t, >0 if s>t*/
int strcmp(char *s, char *t) 
{
    for( ; *s == *t; s++, t++)
        if(*s == '\0')
            return 0;
    return *s - *t; 
}

++和--既可作为前缀运算符，也可作为后缀运算符，所以可以和*按照其他方式组合使用。比如表达式*--p是在读取指针p所指的字符之前，先对p执行自减运算，即读取的是p前一个存储位置的字符。

事实上，下面的两个表达式：

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

是进栈和出栈的标准用法。

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

由于指针本身也是变量，所以它们可以像其他变量一样存储在数组中，同时，指针也可以指向其他指针。

【指针数组】

在前面第3章中我们曾写过一个针对整数数组的Shell排序函数，并在第4章里面通过一个快速排序函数进行了改进。现在我们想让这个排序算法支持对一个由多个文本行组成的集合进行排序，但由于C语言无法在单个运算中完成字符串的比较或移动操作，因此如果想要对多行文本进行排序，我们就需要一个更高效、方便地处理可变长度文本行的数据表示方法。

引入指针数组（数组中每个元素都是一个指针）来处理这类问题：

考虑到每个文本行都可以通过指向它的第一个字符的指针来访问，我们可以将这些指针本身存储在一个数组中。
在进行文本行的比较时，只需将指向这两个文本行的指针传递给strcmp函数即可。
当需要调换两个文本行的次序时，实际上交换指针数组中与这两个文本行相对应的指针即可，而不用移动文本行。

显然，只移动指针要比移动文本行更节省存储空间以及系统计算开销，效率更高。

排序过程主要包含 3 个步骤：

读取所有文本行：
1. 读取并保存每个文本行的全部字符，并建立一个指向这些文本行的指针的数组；
2. 统计文本行的行数（排序和打印的过程会用到）；
3. 读取文本行的函数只能处理有限行的文本，如果行数过多而无法处理，需返回某个用于表示非法行数的数值，如 -1。
对文本行进行排序：在里面通过调用 strcmp 函数完成文本行的比较运算，而递归算法本身依然是有效的，则不用修改。
按次序打印文本行：按指针数组的次序依次打印数组的每个元素所指向的字符串

最好的程序结构当然是将以上各步骤以子函数实现，在主函数中进行调用和控制。完整的实现代码如下：

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

#define MAXLINES 1000     /* max lines to be sorted */

char *lineptr[MAXLINES];  /* pointers to next lines */

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

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

/* sort input lines */
int main()
{
    int nlines;     /* number of input lines read */

    if((nlines = readlines(lineptr, MAXLINES)) >= 0 ) {
        printf("**********  before sort ********** \n");
        writelines(lineptr, nlines);
        printf("********************************** \n");

        qsort(lineptr, 0, nlines-1);

        printf("**********  after  sort ********** \n");
        writelines(lineptr, nlines);
        printf("********************************** \n");
        return 0;
    } else {
        printf("ERROR: input too big to sort\n");
        return 1;       
    }
}

#define MAXLEN 1000     /* max length of any input line */

/* my_getline: read a line into s, return length */
int my_getline(char s[], int lim)
{
    int c, i = 0;

    while(--lim > 0 && (c=getchar()) != EOF && c != '\n')
        s[i++] = c;
    if(c == '\n')
        s[i++] = c;
    s[i] = '\0';
    return i;
}

#define ALLOCSIZE (MAXLEN * MAXLINES)
static char allocbuf[ALLOCSIZE];  /* storage for alloc */
static char *allocp = allocbuf;   /* next free position */
/* alloc: return pointer to n characters */
char *alloc(int n)      /* return pointer to n characters */
{
    if( allocbuf + ALLOCSIZE - allocp >= n) { /* it fits */
        allocp += n;
        return allocp - n; /* old p */
    } else
        return 0;
}

/* my_strcpy: copy t to s; pointer version 3 */
void my_strcpy(char *s, char *t)
{
    while(*s++ = *t++)
        ;
}

/* readlines: read input lines */
int readlines(char *lineptr[], int maxlines)
{
    int len, nlines;
    char *p, line[MAXLEN];

    nlines = 0;
    while((len = my_getline(line, MAXLEN)) > 0) {
        if(nlines >= maxlines || (p = alloc(len)) == NULL)
            return -1;
        else {
            line[len-1] = '\0';     /* delete the '\n' */
            my_strcpy(p, line);
            lineptr[nlines++] = p;
        }
    }
    return nlines;
}

/* writelines: write output lines */
void writelines(char *lineptr[], int nlines)
{
    int i;

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

/* swap: interchange v[i] and v[j] */
void swap(char *v[], int i, int j)
{
    char *temp;

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

/* my_strcmp: retrun <0 if s<t, 0 if s==t, >0 if s>t*/
int my_strcmp(char *s, char *t)
{
    for( ; *s == *t; s++, t++)
        if(*s == '\0')
            return 0;
    return *s - *t;
}

/* qsort: sort v[left]...v[right] into increasing order */
void qsort(char *v[], int left, int right)
{
    int i, last;

    if(left >= right)  /* do nothing if array contains*/
        return;
    swap(v, left, (left + right)/2);
    last = left;
    for(i = left+1; i <= right; i++)
        if(my_strcmp(v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

第 6 行是指针数组lineptr的声明，它表明lineptr是一个具有MAXLINES个元素的一维数组，而且数组中的每个元素都是一个指向char类型对象的指针。即lineptr[i]是一个字符指针，而*lineptr[i]是该指针指向的第i个文本行的首字符。

第 51 行我们用了一个一维字符数组char allocbuf[ALLOCSIZE]来存储所有的文本行，通过alloc函数从中分配空间给新输入的字符串，并将这个分配得到的地址赋给指针数组对应的元素。

由于lineptr本身是一个数组名，因此也可以和之前的例子一样将其作为指针使用，第 90 行的writelines函数可以改写成：

void writelines(char *lineptr[], int nlines)
{
    while(nlines-- > 0)
        printf("%s\n", *lineptr++);
}

此处的参数lineptr是可以进行自增运算的。while循环开始执行时，*lineptr指向第一行文本，每一次自增运算都将使*lineptr指向下一个行文本。

还要注意第38行、71行、90行、99行、118行函数的形式参数中都是形如：

char *v[]

表明传递的参数是一个指针数组。

最后，由于getline函数、strcmp函数以及strcpy函数会和标准库的中库函数冲突，因此这里均加了my_前缀以示区分。

【指向指针的指针】

指向指针的指针变量是一个指针变量指向另一个指针变量。其声明格式是：

类型标识符 **指针变量名

比如：

int **ppa;
char **ppc;

通过一个简单的例子来理解什么是指向指针的指针。

#include <stdio.h>

int main()
{
    int a = 8;
    int *pa = &a;
    int **ppa = &pa;

    printf("a     = 0x%x\n", a);
    printf("&a    = 0x%x\n", &a);
    printf("pa    = 0x%x\n", pa);
    printf("*pa   = 0x%x\n", *pa);
    printf("&pa   = 0x%x\n", &pa);
    printf("ppa   = 0x%x\n", ppa);
    printf("&ppa  = 0x%x\n", &ppa);
    printf("*ppa  = 0x%x\n", *ppa);
    printf("**ppa = 0x%x\n", **ppa);

    return 0;
}

在我的电脑上运行结果是：（在其他电脑上运行的结果不可能完全一样，但其中的逻辑是一样的）

a     = 0x8
&a    = 0xdd54e7fc
pa    = 0xdd54e7fc
*pa   = 0x8
&pa   = 0xdd54e7f0
ppa   = 0xdd54e7f0
&ppa  = 0xdd54e7e8
*ppa  = 0xdd54e7fc
**ppa = 0x8

根据结果我们可以画出内存分布及指针的指向关系：

很形象地说明了三者之间的关系。另外，

直接通过变量名访问变量值，是直接访问，如直接使用 a。
通过指针访问它所指向的变量的值，是间接访问，也叫单级间址，如 *pa。
通过指向指针的指针访问变量值，是间接的间接访问，也叫二级间址，如 **ppa。

不过要注意：通过**ppa访问a是合法的，但int **ppa = &&a的定义是非法的，&&并不能取地址的地址。

5.7 多维数组

C语言提供的多维数组是类似矩阵的结构，虽然实际上用的不像指针数组那么频繁。

来看一个日期转换的问题。给定一个具体日期 “x年x月x日”，要计算这一天是这一年的第几天；相反的，已知某一天在某一年是第几天，要计算出这一天是几月几号。

我们用函数day_of_year来解决第一个问题。显然，输入参数有三个：年、月、日，返回参数只有一个：第几天。

用函数month_day来解决第二个问题，输入参数有两个：年、第几天，返回参数有两个：月、日。我们可以把两个返回参数用指针的方式传递回主调函数。

我们知道闰年的 2 月有 29 天，而非闰年的 2 月只有 28 天，而其他月份的天数不尽相同，所以，将每个月的天数存放在一个二维数组中（类似一张表，供函数查询），以方便循环计算。

完整的代码如下：

#include <stdio.h>

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: set day of year from month & day */
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: set month, day from day of year */
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;
}

int main()
{
    int month, day;
    printf("days of 2012-11-29: %d\n", day_of_year(2012, 11, 29));
    printf("days of 2014-11-29: %d\n", day_of_year(2014, 11, 29));
    month_day(2014, 100, &month, &day);
    printf("2014 100th day: month = %d, day = %d\n", month, day);

    return 0;
}

根据闰年的规则“四年一闰，百年不闰，四百年再闰”，使用变量leap来表明是否为闰年，并将leap作为daytab的下标，以对应闰年和非闰年的每月天数数组。

二维数组daytab实际上是一种特殊的一维数组，可以把它看成是它的每个元素也是一个一维数组（比如，daytab中有2个含13个char型元素的一维数组），因此数组的下标写法是：

daytab[i][j]

而不能写成：

daytab[i,j]

数组中的元素按行存储，可以用花括号括起来的初值表进行初始化，二维数组的每一行由相应的子列表进行初始化。从程序的第 3 ~ 6 行我们可以看出daytab是如何定义并被初始化的。其中第一列元素被设置为 0，是为了对应月份 1 ~ 12，而不是 0 ~ 11。（如果你想节省存储空间，当然也可以用 0 ~ 11，不过在程序中需要相应的调整数组下标和月份的对应关系）

如果将二维数组作为参数传递给函数，那么在函数的参数声明中必须指明数组的列数（数组的行数没有太大关系），因为函数调用时传递的是一个指针，它指向由行向量构成的一维数组，其中每个行向量是具有 13 个整型元素的一维数组。

因此如果将数组daytab作为参数传递给函数f时，则f的声明应该写成下列形式：

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

或者

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

由于数组的行数无关紧要，因此该声明还可以写成：

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

这种形式参数表明该参数是一个指针，它指向具有13个整型元素的一维数组。其中圆括号不能省略，因为方括号[ ]的运算符优先级高于*，如果去掉圆括号，声明变成：

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

这种形式参数表明该参数是一个指针数组，该数组有13个元素，其中每个元素都是一个指向整型对象的指针。

一般来说，除了数组的第一维下标可以不指定大小，其余各维都必须明确指定大小。

5.8 指针数组的初始化

之前通过排序的例子，我们学习了指针数组的使用，如何声明指针数组，如何将lineptr[i]指向正确的字符串等等，但我们还并未看到指针数组应该如何初始化。

现在来看一个month_name(n)函数的例子，它返回一个指向第n个月名字的字符串的指针，如果n是个非法值，也需返回一个含有错误提示的字符串的指针。

#include <stdio.h>

/* month_name: return name of n-th month */
char *month_name(int n)
{
    static char *name[] = { 
        "Illegal month",
        "January",      "February",     "March",
        "April",        "May",          "June",
        "July",         "August",       "September",
        "October",      "November",     "December"
    };
    if(n < 0 || n > 12 )
        return name[0];
    else
        return name[n];
}

int main()
{
    int i;

    for(i = 0; i < 13; i++)
        printf("[%d]\t%s\n", i, month_name(i));
}

可以看到，指针数组的初始化语法和前面所讲的其他类型对象的初始化语法非常类似。name的声明和之前的lineptr的声明相同，是一个一维数组，且数组中每个元素都是一个字符指针。

指针数组name的初始化是通过一个字符串列表实现的，列表中的每个字符串赋值给数组相应位置的元素。第i个字符串的所有字符存储在存储器的某个位置，而name[i]中存放的便是这个字符串第一个字符的地址。

声明中没有指明name的长度，因为编译器在进行编译的时候会对初值个数（也就是字符串列表中的字符串个数）进行统计，并将这个数字填入数组的长度。

5.9 指针与多维数组

如果不多加注意，是很容易混淆二维数组和指针数组的。

请看如下定义：

int a[10][20];    /* 定义了一个二维数组 */
int *b[10];       /* 定义了一个指针数组 */

从语法角度来说，a[3][4]和b[3][4]对一个int对象的合法访问，然而：

a是一个真正的二维数组，它被分配了200个int类型长度的存储空间。通过常规的矩阵下标计算公式20 * row + col（其中row表示行，col表示列）可以计算元素a[row][col]的位置；
对b来说，该定义仅仅分配了10个指针，并没有初始化，在使用它们之前必须先进行显式的初始化（如静态初始化或通过代码初始化）。

假如b的每个元素都指向一个具有20个元素的数组，那么编译器需要为它分配200个int类型长度的存储空间，以及10个指针的存储空间。但是b的每个元素不一定需要都指向一个具有20个元素的数组，所以我们可以看到指针数组的一个优势在于：数组的每一个行长度可以不同。

事实上，指针数组用的比较频繁的就是用于存放不同长度的字符串，比如上一节的month_name。

接下来我们结合变量定义和图形化描述，来对指针数组和二维数组进行一个直观的比较。先看指针数组的定义和图形描述：

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

以下是二维数组的定义和图形描述：

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

可以看到，尽管二维数组中有的字符串不满15个字符，但它们仍然占据着15个char类型的存储空间。

5.10 命令行参数

之前我们所看到的main函数都是不带任何参数的，但就像普通的函数调用一样，在支持C语言的环境中，其实可以在程序开始执行的时候将一些参数传递给主函数main，这些参数我们称为命令行参数。

调用主函数main时，它有两个参数：

第一个参数（称为argc，用于参数计数）的值表示运行程序时命令行中参数的个数；
第二个参数（称为argv，用于参数向量）是一个指向字符串数组的指针，其中每个字符串对应一个参数。

【示例：echo 打印程序】

在Linux的bash环境下，有个最简单的例子：echo程序，它将命令行参数在屏幕上显示出来，其中命令行中各个参数用空格隔开。比如命令：

$ echo hello, world

将在屏幕上打印以下字符串：

hello, world

C语言约定，argv[0]的值是启动该程序的程序名，因此argc的值至少为1。

因此如果 argc 等于 1，说明程序名后面没有命令行参数。

在上面echo的例子中，argc的值为3，argv[0]、argv[1]、argv[2]的值分别是“echo”、“hello,”、”world”，即可选参数的是argv[1] ~ argv[argc – 1]。另外，ANSI 标准要求argv[argc]的值必须为一个空指针。参数的图形描述如下：

./command_line_arguments.jpg — echo的命令行参数

若把argv看成一个字符指针数组，我们可以写出第一个版本的echo函数：

#include <stdio.h>

/* echo command-line arguments; 1st version */
int 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是一个指向指针数组的指针，所以也可以通过指针而非数组下标的方式处理命令行参数。若把argv看成是一个指向char类型的指针的指针，我们可以写出第二个版本的echo程序：

#include <stdio.h>

/* echo command-line arguments; 2nd version */
int main(int argc, char *argv[])
{
    while(--argc)
        printf("%s%s", *++argv, (argc > 1) ? " ": "");
    printf("\n");
    return 0;
}

其中argv是一个指向参数字符串数组起始位置的指针，自增运算（++argv）将使得它一开始指向argv[1]而不是argv[0]。

另外上面的printf语句也可以写成：

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

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

【示例：find 查找字符串程序】

在4.1节中我们写了一个查找指定字符串的例子，但是该程序将需要查找的字符串在代码中“固定”了，这种程序通用性太低了。这个需要查找的字符串可以以命令行参数的形式传递给主程序，因此我们可以来实现一个类似Linux中grep命令的程序。

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

int my_getline(char *line, int max);

/* find: print lines that match pattern from 1st arg */
int main(int argc, char *argv[])
{
    char line[MAXLINE];
    int found = 0;

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

/* my_getline: read a line into s, return length */
int my_getline(char s[], int lim)
{
    int c, i = 0;

    while(--lim > 0 && (c=getchar()) != EOF && c != '\n')
        s[i++] = c;
    if(c == '\n')
        s[i++] = c;
    s[i] = '\0';
    return i;
}

其中的strstr(s, t)是标准库函数，它返回一个指针，该指针指向字符串t在字符串s中第一次出现的位置；如果字符串t没有在s中出现，则返回空指针（即NULL）。

【示例：支持选项参数的 find 程序】

在 Linux 系统的 bash 环境下，命令的执行可以搭配一些以-为开头的选项作为参数。比如 ls -l、echo -n hello, world等等。同样我们也可以改进上面的find程序，比如使用-x（代表“除……之外”）表示打印所有与模式不匹配的文本行，用-n（代表“行号”）表示打印行号，则下面命令：

find -x -n 模式

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

熟悉Linux的朋友应该知道，类似-x、-n这样的可选参数应该被允许以任意次序出现，而且有时还会允许可选参数可以组合使用，比如：

find -nx 模式

改进之后的程序如下：

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

int my_getline(char *line, int max);

/* find: print lines that match pattern from 1st arg */
int 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(my_getline(line, MAXLINE) > 0) {
            lineno++;
            if((strstr(line, *argv) != NULL) != except) {
                if(number)
                    printf("%ld:", lineno);
                printf("%s", line);
                found++;
            }
        }
    }
    return found;
}

/* my_getline: read a line into s, return length */
int my_getline(char s[], int lim)
{
    int c, i = 0;

    while(--lim > 0 && (c=getchar()) != EOF && c != '\n')
        s[i++] = c;
    if(c == '\n')
        s[i++] = c;
    s[i] = '\0';
    return i;
}

注意，程序的第 14 行中，*++argv是一个指向参数字符串的指针，因此(*++argv)[0]是该字符串的第一个字符（另一种有效形式是**++argv）。而由于[ ]与操作数的结合优先级比*和++高，所以上述表达式必须使用圆括号，否则编译器会把该表达式认为是*++(argv[0])。

在程序的第 15 行中，我们使用了*++argv[0]（其实就是上面所说的*++(argv[0])表达式）来对字符串中的单个字符进行遍历，它是对指针argv[0]进行自增运算。

实际中一般不会使用比这更复杂的指针表达式。

5.11 指向函数的指针

在C语言中，函数本身不是变量，但函数也是有地址的，可以定义指向函数的指针。这种类型的指针可以被赋值、存放在数组中、传递给函数以及作为函数的返回值等等。

通过修改之前的qsort排序函数，来看下指向函数的指针的用法。在给定可选参数-n的情况下，程序将按照数值大小而非字典顺序对输入行进行排序。

排序的过程不外乎以下 3 个部分：

比较函数：判断任意两个对象之间的次序；
交换函数：颠倒两个对象的次序；
排序算法：保证所有对象都按正确次序排列；

排序算法和比较函数、交换函数、具体对象都无关，所以我们可以在排序算法中调用不同的比较和交换函数，实现不同的排序方式。

strcmp函数是按字典顺序比较两个输入行，我们还需要一个按数值大小比较两个输入行，并返回和strcmp相同的比较结果的函数——numcmp函数。

最后，我们需要将指向对应比较函数的指针传递给qsort函数。

参考之前的代码，新的程序如下：

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

#define MAXLINES 1000     /* max lines to be sorted */
char *lineptr[MAXLINES];  /* pointers to next lines */

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

void my_qsort(void *lineptr[], int left, int right, int(*comp)(void *, void *));

int numcmp(char *, char *); 

/* sort input lines */
int main(int argc, char *argv[])
{
    int nlines;     /* number of input lines read */
    int numeric = 0; /* 1 if numeric sort */

    if(argc > 1 && my_strcmp(argv[1], "-n") == 0)
            numeric = 1;
    if((nlines = readlines(lineptr, MAXLINES)) >= 0) {
        printf("**********  before sort ********** \n");
        writelines(lineptr, nlines);
        printf("********************************** \n");

        my_qsort((void**) lineptr, 0, nlines -1, (int (*)(void*,void*))(numeric ? numcmp : my_strcmp));

        printf("**********  after  sort ********** \n");
        writelines(lineptr, nlines);
        printf("********************************** \n");
        return 0;
    } else {
        printf("input too big to sort\n");
        return 1;
}
}

#define MAXLEN 1000     /* max length of any input line */

/* my_getline: read a line into s, return length */
int my_getline(char s[], int lim)
{
    int c, i = 0;

    while(--lim > 0 && (c=getchar()) != EOF && c != '\n')
        s[i++] = c;
    if(c == '\n')
        s[i++] = c;
    s[i] = '\0';
    return i;
}

#define ALLOCSIZE (MAXLEN * MAXLINES)
static char allocbuf[ALLOCSIZE];  /* storage for alloc */
static char *allocp = allocbuf;   /* next free position */
/* alloc: return pointer to n characters */
char *alloc(int n)      /* return pointer to n characters */
{
    if( allocbuf + ALLOCSIZE - allocp >= n) { /* it fits */
        allocp += n;
        return allocp - n; /* old p */
    } else
        return 0;
}

/* my_strcpy: copy t to s; pointer version 3 */
void my_strcpy(char *s, char *t)
{
    while(*s++ = *t++)
        ;
}

/* readlines: read input lines */
int readlines(char *lineptr[], int maxlines)
{
    int len, nlines;
    char *p, line[MAXLEN];

    nlines = 0;
    while((len = my_getline(line, MAXLEN)) > 0) {
        if(nlines >= maxlines || (p = alloc(len)) == NULL)
            return -1;
        else {
            line[len-1] = '\0';     /* delete the '\n' */
            my_strcpy(p, line);
            lineptr[nlines++] = p;
        }
    }
    return nlines;
}

/* writelines: write output lines */
void writelines(char *lineptr[], int nlines)
{
    while(nlines-- > 0)
        printf("%s\n", *lineptr++);
}

/* swap: interchange v[i] and v[j] */
void swap(void *v[], int i, int j)
{
    void *temp;

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

/* numcmp: compare s1 and s2 numerically */
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;
}

/* my_strcmp: retrun <0 if s<t, 0 if s==t, >0 if s>t*/
int my_strcmp(char *s, char *t)
{
    for( ; *s == *t; s++, t++) {
        if(*s == '\0')
            return 0;
    }
    return *s - *t;
}

/* my_qsort: sort v[left]...v[right] into increasing order */
void my_qsort(void *v[], int left, int right, int (*comp)(void *, void *))
{
    int i, last;

    if(left >= right)       /* do nothing if array contains */
        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);
    my_qsort(v, left, last-1, comp);
    my_qsort(v, last+1, right, comp);
}

备注：由于qsort函数与stdlib.h中的标准库函数qsort冲突，因此这里改成了my_qsort函数名。

在程序第28行调用qsort函数的语句中，strcmp和numcmp是函数地址，所以不需要在他们前面加上取地址运算符& （PS：数组名前面也不需要加&是同样的道理）。

程序第11行是qsort函数的原型，从声明中我们可以看到它的参数列表包含：一个指针数组、两个整型数、一个带有两个指针参数的函数。其中指针数组参数的类型是通用指针类型void *。由于任何类型的的指针都可以转换为void *类型，并且在将它转换回原来的类型时不会丢失信息，因此调用qsort函数时可以将参数强制转换为void *类型。

仔细看下qsort函数的第四个参数声明：

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

程序第145行使用如下语句调用comp函数：

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

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

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

其中的圆括号不能省略，如果省略了圆括号，则变成了：

int *comp(void *, void *)    /* 错误 */

这里表明comp是一个函数，该函数返回一个指向int类型的指针，这显然不是我们原本设计该函数的初衷。

程序第112行的numcmp函数中，通过调用atof计算字符串对应的数值，再进行数值大小的比较。

程序第102行的swap函数和之前所编写的swap函数有个不一样的地方是，它的参数声明为void *类型，保持与qsort函数中的参数类型一致。

5.12 复杂声明

C 语言常常因为声明的语法问题而饱受批评，尤其是当涉及到函数指针的语法。尽管 C 语言的语法努力使声明和使用保持一致，但很多复杂的声明，还是会让人一头雾水。原因在于，C语言的声明不能单纯地从左至右阅读，而且使用了太多的圆括号。

先从两个声明的对比来看：

int *f();       /* f: function returning pointer to int */
int (*pf)();    /* pf: pointer to function returning int */

前者是一个函数，返回值是一个指向int类型数据的指针；
后者是一个函数指针，返回值是int类型数据，其中由于*运算符的优先级低于圆括号( )，所以必须使用圆括号以保证正确的结合顺序。

虽然实际中很少会用到过于复杂的声明，但是懂得如何去理解、使用这些复杂声明还是非常重要的。通过typedef进行简单的步骤合成，是一种办法，这个我们在后面的章节会学习到。

现在，我们通过一个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: functiong 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 是基于声明符的语法编写的（需要参考原书《The C Programming Language》的附录 A 的第 8.5 节说明）。语法形式是：

declarator:
    pointer opt direct-declarator
direct-declarator:
    identifier
    (declarator)
    direct-declarator[constant-expression opt]
    direct-declarator(parameter-type-list)
    direct-declarator(identifier-list opt)
pointer:
    * type-qualifier-list opt
    * type-qualifier-list opt pointer
type-qualifier-list:
    type-qualifier
    type-qualifier-list type-qualifier

备注：opt表示位于其前面的标识符是可选的意思。

简单来说，声明符declarator就是前面可能带有多个*号的direct-declarator。而direct-declarator可以是identifier名字、由一对圆括号括起来的declarator、后面跟有一对圆括号的direct-declarator、后面紧跟着用方括号括起来的表示可选长度的direct-declarator。

利用该语法来对 C 语言的声明进行分析。例如：

(*pfa[])()

一步步分析下来：

pfa将被识别为是一个identifier，从而被认为是一个direct-declarator。
于是pfa[]也是一个direct-declarator。
接着，*pfa[]被识别为一个declarator，因此判定(*pfa[])是一个direct-declarator。
最后，(*pfa[])()会被识别为一个direct-declarator，因此也是一个declarator。

下图是对应的语法分析树（其中declarator缩写为dcl，direct-declarator缩写为dir-dcl）：

程序 dcl 的完整代码如下：

#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;            /* type of last token */
char token[MAXTOKEN];     /* last token string */
char name[MAXTOKEN];      /* identifier name */
char datatype[MAXTOKEN];  /* data type = char, int, etc. */
char out[1000];

/* convert declaration to words */
int main()
{
    while(gettoken() != EOF) {  /* 1st token on line */
        strcpy(datatype, token);  /* is the datatype */
        out[0] = '\0';
        dcl();          /* parse rest of line */
        if(tokentype != '\n')
            printf("syntax error\n");
        printf("%s: %s %s\n", name, out, datatype);
    }
    return 0;
}

/* dcl: parse a declarator */
void dcl(void)
{
    int ns;

    for(ns = 0; gettoken() == '*'; )  /*count *'s */
        ns++;
    dirdcl();
    while(ns-- > 0)
        strcat(out, " pointer to");
}

/* dirdcl: parse a direct declarator */
void dirdcl(void)
{
    int type;

    if(tokentype == '(') {  /* ( dcl ) */
        dcl();
        if(tokentype != ')')
            printf("error: missing )\n");
    } else if(tokentype == NAME) {    /* variable 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");
        }
    }
}

/* return next 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;
}

备注：该程序旨在说明问题，并未做到尽善尽美，所以对dcl有很多限制，比如只能处理类似于char或int这样的简单数据类型，而无法处理函数中的形式参数类型或类似于const这样的限定符。它也不能处理带有不必要空格的情况。如果感兴趣，大家可以再完善一下。

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

函数gettoken用来略过空格和制表符，以查找下一个记号（token）。该记号可以是一个名字、一对圆括号、包含一个数字的一对方括号、不包含数字的一对方括号，或是其他任何单个字符。

函数getch和ungetch可以参考前面章节中的getch_ungetch.c文件。

既然有了可以将C语言声明转换为文字描述的dcl程序，那么相应的，我们再来看一个将文字描述转换为对应C语言声明的undcl程序。

为了简化程序的输入，我们将“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: convert word descriptions to declarations */
int 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;
}

至此，我们第五章关于指针和数组的学习就告一段落了，更多的细节还需我们在实际编程中慢慢掌握，下一节我们将开始学习第六章结构体。

目录