1

K＆Rプログラムについてさらに別の質問をしてご迷惑をおかけして申し訳ありません。しかし、やはりいくつかのことが私にはわかりません。以下のプログラムは、readlines関数によって保存された行をソートするために使用されます（実際に保存されていますか？）そのために、これらの各行を指すポインターの配列を作成します。

質問：[1]なぜ私たちはqsort(lineptr, 0, nlines-1);nlinesだけでなくnlines-1を意味するのですか？

[2]2行入力したとします。

ブラボー

アルファ

現在、それらは配列からポイントされています（視覚化を行うので、角かっこで囲まれた文字を見て怒ってはいけません;））

* v [] ==[lineptr[0]-ブラボーへのポインター][lineptr[1]-アルファへのポインター]

アルゴリズムによると、lineptr [0]がピボットであるため、それらを交換します。最後=0; forループに入る：-lineptr[1]のstrcmpはlineptr[0]より字句的に小さくありません。iのインクリメントはすでに終了しているため、forループを終了します。ここで、last=0をleft=0と交換するので、何も起こりません。それらはすでに配置されています。

しかし、それらが同じ文字で始まる場合はどうなりますか。abravoとalfa、qsortが配列のインデックスを左から右にのみ操作する場合、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辞書式順序について2つの文字列を比較します。これにより、最初の文字だけでなく、文字列全体を比較に使用できるようになります。

そして、パラメータrightは、ソートする右端のインデックスのインデックスを取ります。長さ10の配列がある場合、最初の要素は0で、最後の要素は9です（つまり、10-1、つまりright -1）。手がかりは、for (i = left+1; i <= right; i++)iをループして両方の値left+1を含める行にあります。right

あなたはそれを呼んだqsort(lineptr, 0, nlines-1);ので、それは0配列のth（最初の）要素とnlines-1（最後の）要素を含みます。

于 2012-08-15T11:00:31.060 に答える