C语言K&R圣经笔记 5.6指针数组；指针的指针

5.6 指针数组；指针的指针

因为指针本身也是变量，所以它们也能像其他变量一样保存在数组里面。我们写个程序来说明，该程序将一些文本行按照字母顺序排列，算是 UNIX 程序 sort 的精简版本。

在第三章中，我们介绍了对一个整数数组进行排序的 Shell 排序函数，而在第四章中，我们用快速排序对其进行改进。同样的算法在这里也还能用，差异之处在于，现在我们要处理的是文本行，每行有不同的长度，而且文本行不像整数，没法用单个操作来比较或者移动。我们需要一种数据表示法，能够高效且方便地处理长度可变的文本行。

指针数组在这里就派上用场了。如果待排序的行是头尾相连地（end-to-end）保存在一个长字符数组里面，则每行都可以通过执行其首个字符的指针来访问。这些指针本身可以保存在一个数组里。将某两行的指针传递给 strcmp 就可以比较两行。当两个错序的行需要交换时，交换的是指针数组里面的指针，而不是文本行本身。

这就同时避免了移动文本行本身带来的两个孪生问题：复杂的内存管理，以及高额的开销。

排序过程很自然地分为三步：

读入所有的文本行

对其排序

按顺序打印

一如既往，最好是将程序拆分成与上面各步骤匹配的几个函数，再用主函数来控制这些函数。我们先聚焦于数据结构和输入输出，晚点再看排序步骤。

输入例程必须收集和保存每行的字符，并创建一个指向每行的指针数组。它还需要计算输入的行数，因为这个信息还需要用于排序和打印。由于输入函数只能处理有限数量的输入行，如果有太多输入时，它可以返回某些非法的行数，例如 -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);

/* 对输入行排序 */
int 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(n);

/* 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(n)) == NULL)
            return -1;
        else {
            line[len -1] = '\0';    /* 删除换行 */
            strcpy(p, line);
            lineptr[nlines++] = p;
        }
    return nlines;
}

/* writelines：输出行*/
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 个元素的数组，每个元素是一个指向 char 的指针。也就是说，lineptr[i] 是一个字符指针，而 *lineptr[i] 是它指向的字符，即所保存的第 i 个文本行的首字符。

由于 lineptr 本身也是数组名称，因此我们也能和前面的例子一样把它当作指针，这样 writelines 也能写成：

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

    while (nlines-- > 0)
        printf("%s\n", *lineptr++);
}

最初 *lineptr 指向第一行，当 nlines 递减时，lineptr 每次递增推进到下一行的指针。

搞定了输入输出，现在我们来做排序。需要对第四章的快速排序做些小改动：声明得修改；比较操作必须通过调用 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)    /* 若数组小于两个元素则什么都不用做  */
        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: 交换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 也是，因此它们可以互相拷贝。

练习5-7、重写 readlines 函数，将行保存到 main 提供的数组中，而不是调用 alloc 来维护内存空间。程序会快多少？