Serendip

Web Studio

演習5-7

読み込んだ各行文字列を保存するのに alloc の代わりに配列を引数として渡す。
lineptr には配列内の各行文字列の先頭になる配列要素のポインタを保存していく。

buf_lines : |h|e|l|l|o|\0|w|o|r|l|d|\0|f|r|o|m| ...
lineptr   :  ^            ^            ^

プログラムの実行速度は、ほとんど変化がわからなかった。

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

#define MAXLINES 5000 /* ソートすべき最大の行数 */
#define MAXLEN 1000 /* 任意の入力行の最大長 */

char *lineptr[MAXLINES]; /* テキスト行へのポインタ */
int my_getline(char*, int);
int readlines(char *lineptr[], int nlines, char *buf_lines);
void writelines(char *lineptr[], int nlines);
void qsort(char *lineptr[], int left, int right);

/* 入力行をソートする */
int main(void)
{
    int nlines; /* 読み込まれた入力行の数 */
    char buf_lines[MAXLINES * MAXLEN]; /* 読み込んだ文字の保存場所 */
    clock_t t1, t2;

    t1 = clock();
    if ((nlines = readlines(lineptr, MAXLINES, buf_lines)) >= 0) {
        qsort(lineptr, 0, nlines - 1);
        writelines(lineptr, nlines);
        t2 = clock();
        printf("%f\n", (double) (t2 - t1) / CLOCKS_PER_SEC);
        return 0;
    } else {
        printf("nlines => %d\n", nlines);
        printf("error: input too big to sort\n");
        return 1;
    }
}

/* readlines : 入力行を読み込む */
int readlines(char *lineptr[], int maxlines, char *buf_lines)
{
    int i, len, nlines;
    char line[MAXLEN];

    i = nlines = 0;
    while ((len = my_getline(line, MAXLEN)) > 0)
        if (nlines >= maxlines)
            return -1;
        else {
            line[len-1] = '\0'; /* 改行を消す */
            strcpy(&buf_lines[i], line);
            lineptr[nlines++] = &buf_lines[i];
            i += len;
        }
    return nlines;
}

/* writelines : 出力行を書き出す */
void writelines(char *lineptr[], int nlines)
{
    int i;

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

int my_getline(char *s, int lim)
{
    int c, i;

    for (i = 0; i<lim-1 && (c=getchar()) != EOF && c!='\n'; ++i)
        *(s+i) = c;
    if (c == '\n') {
        *(s+i) = c;
        ++i;
    }
    *(s+i) = '\0';
    return i;
}

/* 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)  /* 配列の要素が2より*/
        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;
}

プログラミング言語C 第2版 ANSI規格準拠

posted with amazlet at 09.11.27

B.W. カーニハン D.M. リッチー
共立出版
売り上げランキング: 9726

Amazon.co.jp で詳細を見る