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

2024-01-09 00:19:36

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 来维护内存空间。程序会快多少?

文章来源:https://blog.csdn.net/baluzju/article/details/135110439
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。