演習5-14, 演習5-15, 演習5-16, 演習5-17 K&R プログラミング言語C
2010年02月16日
演習5-14
逆方向のソートを取り扱えるようにする。
my_qsort 関数に引数として reverse を追加し、比較の方向(<, >)を変化させる。
演習5-15
大文字・小文字の区別なしに比較できるようにする。
グローバル変数の fold を設定し、文字を比較する際に toupper で大文字に変換してから比較を行う。
演習5-16
文字、数字、空白についてのみ比較を行うようにする。
グローバル変数の dict_order を設定し、isalpha, isdigit, isspace で、文字、数字、空白以外をスキップして比較する。
演習5-17
フィールド単位で比較を行えるようにする。
フィールド比較関数の fieldcmp を定義し、グローバル変数 field_comp が 1 の場合は fieldcmp 関数を使い field_column_pos 番目のフィールドを比較する。
sort コマンドのコード
演習5-14 から 演習5-17 までを含んだ結果のコード
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #define MAXLINES 5000 /* ソートすべき最大の行数 */ #define MAXLEN 1000 /* 任意の入力行の最大長 */ #define ALLOCSIZE 50000 /* 使用可能な場所の大きさ */ char *lineptr[MAXLINES]; /* テキスト行へのポインタ */ char allocbuf[ALLOCSIZE]; /* alloc のための記憶場所 */ char *allocp = allocbuf; /* 次の空き位置(allocbuf の先頭アドレスを指して初期化) */ int numeric = 0; int reverse = 0; int fold = 0; int dict_order = 0; int field_comp = 0; int field_column_pos = 0; int my_getline(char *s, int max); int readlines(char *lineptr[], int nlines); void writelines (char *lineptr[], int nlines); char *alloc(int n); void my_qsort(void *v[], int left, int right, int (*comp)(void *, void *), int reverse); int comp_direction(int, int); int numcmp(char *, char *); int my_strcmp(char *, char *); int fieldcmp(char *, char *); int main(int argc, char *argv[]) { int nlines, c; while (--argc > 0 && (*++argv)[0] == '-') { while ((c = *++argv[0])) { switch (c) { case 'n': numeric = 1; break; case 'r': reverse = 1; break; case 'f': fold = 1; break; case 'd': dict_order = 1; break; case 'e': field_comp = 1; field_column_pos = atoi(++(*argv)); while (*++argv[0] != '\0') ; --argv[0]; break; default: fprintf(stderr, "sort : illegal option %c\n", c); exit(1); } } } if ((nlines = readlines(lineptr, MAXLINES)) >= 0) { my_qsort((void **)lineptr, 0, nlines-1, (int (*)(void *, void *)) (field_comp ? fieldcmp : (numeric ? numcmp : my_strcmp)), reverse); writelines(lineptr, nlines); return 0; } else { fprintf(stderr, "input too big to sort\n"); exit(1); } } /* my_qsort : v[left] ... v[right] を昇順にソートする */ void my_qsort(void *v[], int left, int right, int (*comp)(void *, void *), int reverse) { int i, last; void swap(void *v[], int, int); if (left >= right) /* 配列の要素が2つより少なければ、何もしない */ return; swap(v, left, (left + right)/2); last = left; for (i = left+1; i <= right; i++) if (comp_direction((*comp)(v[i], v[left]), reverse)) swap(v, ++last, i); swap(v, left, last); my_qsort(v, left, last-1, comp, reverse); my_qsort(v, left+1, right, comp, reverse); } int comp_direction(int comp_result, int reverse) { return (reverse > 0) ? (comp_result > 0) : (comp_result < 0); } /* numcmp : s1 と s2 を数値的に比較する */ int numcmp(char *s1, char *s2) { double v1, v2; v1 = atof(s1); v2 = atof(s2); if (v1 < v2) return -1; else if (v1 > v2) return 1; else return 0; } int my_strcmp(char *s1, char *s2) { if (dict_order > 0) { while (!isalpha(*s1) && !isdigit(*s1) && !isspace(*s1) && *s1) s1++; while (!isalpha(*s2) && !isdigit(*s2) && !isspace(*s2) && *s2) s2++; } while ((fold > 0) ? (toupper(*s1) == toupper(*s2)) : (*s1 == *s2)) { if (*s1 == '\0') return 0; s1++; s2++; if (dict_order > 0) { while (!isalpha(*s1) && !isdigit(*s1) && !isspace(*s1) && *s1) s1++; while (!isalpha(*s2) && !isdigit(*s2) && !isspace(*s2) && *s2) s2++; } } return (fold > 0) ? (toupper(*s1) - toupper(*s2)) : (*s1 - *s2); } int fieldcmp(char *s1, char *s2) { int i = 0; char p1[BUFSIZ]; char p2[BUFSIZ]; while (i < field_column_pos) { if (*s1 == ',' || *s1 == '\t') i++; if (*s1 == '\0') { fprintf(stderr, "error : too big %d than field column count\n", field_column_pos); exit(1); } s1++; } i = 0; while (*s1 != ',' && *s1 != '\0') p1[i++] = *s1++; p1[i] = '\0'; i = 0; while (i < field_column_pos) { if (*s2 == ',' || *s2 == '\t') i++; if (*s2 == '\0') { fprintf(stderr, "error : too big %d than field column count\n", field_column_pos); exit(1); } s2++; } i = 0; while (*s2 != ',' && *s2 != '\0') p2[i++] = *s2++; p2[i] = '\0'; return numeric ? numcmp(p1, p2) : strcmp(p1, p2); } /* swap */ void swap(void *v[], int i, int j) { void *temp; temp = v[i]; v[i] = v[j]; v[j] = temp; } /* my_getline : s に行を入れ、長さを返す */ int my_getline(char *s, int lim) { int c; char *ps; ps = s; while (--lim > 0 && (c = getchar()) != EOF && c != '\n') *s++ = c; if (c == '\n') *s++ = '\n'; *s = '\0'; return s - ps; } /* readlines : 入力行を読み込む */ int readlines(char *lineptr[], int maxlines) { int len, nlines; char *p, line[MAXLEN]; nlines = 0; while ((len = my_getline(line, MAXLEN)) > 0) { if (nlines >= maxlines || (p = alloc(len)) == 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]); } /* n 文字へのポインタを返す */ char *alloc(int n) { if (allocbuf + ALLOCSIZE - allocp >= n) { /* 入りきる */ allocp += n; return allocp - n; /* 古い p */ } else { /* 十分な空きがないとき */ return 0; /* 異常事態を表わす 0 、通常は NULL (stdio.h で定義) を使う */ } } /* p によって指される領域を解放する */ void afree(char *p) { if (p >= allocbuf && p < allocbuf + ALLOCSIZE) { allocp = p; } }
実行結果
$ cat numbers.csv 464, 8539, 9554 6398, 139, 239 912, 998, 1011 18, 512, 793 350, 30, 300 $ ./sort -e1 -n <numbers.csv 350, 30, 300 6398, 139, 239 18, 512, 793 912, 998, 1011 464, 8539, 9554 $ ./sort -e1 -nr <numbers.csv 464, 8539, 9554 912, 998, 1011 18, 512, 793 6398, 139, 239 350, 30, 300 $ ./sort -d <numbers.csv 18, 512, 793 350, 30, 300 464, 8539, 9554 6398, 139, 239 912, 998, 1011
プログラミング言語C 第2版 ANSI規格準拠
posted with amazlet at 09.11.27
B.W. カーニハン D.M. リッチー
共立出版
売り上げランキング: 9726
共立出版
売り上げランキング: 9726