1

很抱歉又一个关于 K&R 计划的问题打扰您。但是有些事情我也不清楚。下面的程序用于对 readlines 函数保存的行进行排序（它真的保存了它们吗？）为此，我们创建了一个指向这些行中的每一行的指针数组。

问题：[1] 为什么我们通过qsort(lineptr, 0, nlines-1);我的意思是 nlines-1 而不仅仅是 nlines ？

[2] 假设我输入了两行：

好极了

阿尔法

现在它们是从数组中指向的（我将进行可视化，所以不要因为看到括号中的字符而生气；））

*v[] == [lineptr[0] - 指向 bravo 的指针][lineptr[1] - 指向 alfa 的指针]

根据算法： lineptr[0] 是枢轴，所以我们交换它们；最后 = 0; 进入 for 循环：strcmp of - lineptr[1] 在词法上不小于 lineptr[0]；递增 i 已经完成，所以我们退出 for 循环。现在我们将 last = 0 与 left = 0 交换，所以什么也没有发生。它们已经就位。

但是，如果它们以相同的字母开头，例如。abravo 和 alfa，如果 qsort 仅在数组的索引上从左到右操作意味着不同的行数而不是检查字符串中的下一个字符，它将如何继续下一个字母。

请纠正我，因为所有这些指针都让我发疯。

整个代码：

#include <stdio.h>
#include <string.h>
#define MAXLINES 5000 /* max #lines to be sorted */
char *lineptr[MAXLINES]; /* pointers to text lines */
int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void qsort(char *lineptr[], int left, int right);
/* sort input lines */
main()
{
    int nlines;
    /* number of input lines read */
    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 /* max length of any input line */
int getline(char *, int);
char *alloc(int);
/* readlines: read input lines */
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'; /* delete newline */
            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]);
}

/* qsort: sort v[left]...v[right] into increasing order */
void qsort(char *v[], int left, int right)
{
    int i, last;
    void swap(char *v[], int i, int j);
    if (left >= right) /* do nothing if array contains */
        return;
    /* fewer than two elements */
    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);
}

提前感谢您的帮助

4

1 回答 1

2

strcmp比较两个字符串的字典顺序。这将负责使用整个字符串进行比较，而不仅仅是第一个字符。

并且该参数right采用最右边索引的索引进行排序。如果您有一个长度为 10 的数组，则第一个元素是 0，最后一个元素是 9（即 10 - 1，即right -1）。线索在 linefor (i = left+1; i <= right; i++)中，它将 i 从循环left+1到right包含两个值。

您调用了它qsort(lineptr, 0, nlines-1);，因此它将包括0数组的第一个（第一个）元素和nlines-1（最后一个）元素。

于 2012-08-15T11:00:31.060 回答