プログラミング言語 C
少しだけ 関数 read_lines の コードを チェック。
char *p, line[MAX_LEN];while )((len = get_line(line, MAX_LEN))( > 0)
if (n_lines >= maxlines || (p = malloc(len)) == NULL)
return -1;
else {
line[len - 1] = '\0';
strcpy(p, line);
line_ptr[n_lines++] = p;
}
「関数定義の 仮引数としては、char s[] と char *s は まったく 同一である (p121)」
のだから、ここで 宣言されている 配列 line も、ポインタの p と 同じように、strcpy の 引数として 呼び出しが 可能だ、と いうことになる。
strcpy(p, line);
それから、コードの ゴシックのところは、その基本の 骨組みは、関数 strdup の コードを 適用しているようだ (p173)。
char *strdup(char *s) /* make a duplicate of s */
{
char *p; p = (char *)malloc(strlen(s) + 1); /* + 1 for '\0' */
if ( p != NULL)
strcpy(p, s);
return p;
}
これで 入出力は かたづいたから、ソートへ 進もう。
クイックソートには やや変更が 必要である。 同様に swap ルーティンにも ほんの少しだが 変更が いる。
v = lineptr の 任意の要素は 文字ポインタだから、tmp も そうあるべきで、これにより 互いに copy 可能となる。(p134)
void q_sort(char *v[], int left, int right)
{
int i, last; /* do nothing if array contains fewer that two elements */
if (left >= right)
return;
/* move partition elem to v[0] */
swap(v, left, (left + right)/2);
last = left;
for (i = left + 1; i <= right; i++) /* partition */
if (strcmp(v[i], v[left]) < 0)
swap(v, ++last, i);
swap(v, left, last); /* restore partition elem */
/* The same process is then applied recursively
to the two subsets */
q_sort(v, left, last - 1);
q_sort(v, last + 1, right);
}
void swap(char *v[], int i, int j)
{
char *tmp;
tmp = v[i];
v[i] = v[j];
v[j] = tmp;
}
/* prim_sort.c */
#include
#include
#include #define MAX_LINES 5000 /* max # lines to be sorted */
#define MAX_LEN 1000 /* max length of any input line */
char *line_ptr[MAX_LINES];
int read_lines();
int get_line();
void write_lines();
void q_sort();
void swap();
/* primitive sort program */
main()
{
int n_lines; /* numbers of input lines read */
if )((n_lines = read_lines(line_ptr, MAX_LINES))( >= 0) {
q_sort(line_ptr, 0, n_lines - 1);
write_lines(line_ptr, n_lines);
return 0;
} else {
puts("error: input too big to sort");
return -1;
}
}
int read_lines(char *line_ptr[], int maxlines)
{
int len, n_lines;
char *p, line[MAX_LEN];
n_lines = 0;
while )((len = get_line(line, MAX_LEN))( > 0)
if (n_lines >= maxlines || (p = malloc(len)) == NULL)
return -1;
else {
line[len - 1] = '\0'; /* delete newline */
strcpy(p, line);
line_ptr[n_lines++] = p;
}
return n_lines;
}
int get_line(char s[], int limit)
{
int c, i;
for (i = 0; i < limit - 1 && (c = getchar()) != EOF && c != '\n'; ++i)
s[i] = c;
if (c == '\n') {
s[i] = c;
++i;
}
s[i] = '\0';
return i;
}
void write_lines(char *line_ptr[], int n_lines)
{
while (n_lines-- > 0)
printf("%s\n", *line_ptr++);
}
void q_sort(char *v[], int left, int right)
{
int i, last;
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);
q_sort(v, left, last - 1);
q_sort(v, last + 1, right);
}
void swap(char *v[], int i, int j)
{
char *tmp;
tmp = v[i];
v[i] = v[j];
v[j] = tmp;
}
コンパイルして、(ちょっと irregular だけど) code file で 確認。コマンド sort とも 比較してみる。
$cc -c prim_sort.c
$cc -o prim_sort prim_sort.o
$./prim_sort < prim_sort.c | less (q で 終了)
$sort prim_sort.c | less