110 lines
3.0 KiB
C
110 lines
3.0 KiB
C
#include <stdio.h>
|
|
|
|
/* array bounds */
|
|
#define MAXLINES 100
|
|
#define BUFF_SIZE (80 * MAXLINES)
|
|
|
|
int readlines(char *lines[], int maxlines, char *ln_buff, size_t lb_size);
|
|
void writelines(char *lines[], int n);
|
|
void qsort_string(char *v[], int left, int right);
|
|
|
|
/* sorts lines from stdin and prints them */
|
|
int main()
|
|
{
|
|
char *lines[MAXLINES];
|
|
char buffer[BUFF_SIZE];
|
|
|
|
int line_count = readlines(lines, MAXLINES, buffer, BUFF_SIZE);
|
|
if (line_count < 0) {
|
|
line_count = -line_count - 1;
|
|
printf("warning: buffer overflow occured, read %d lines\n", line_count);
|
|
} else if (line_count > MAXLINES) {
|
|
line_count = MAXLINES;
|
|
printf("warning: too many lines, read %d lines\n", line_count);
|
|
}
|
|
qsort_string(lines, 0, line_count-1);
|
|
writelines(lines, line_count);
|
|
return 0;
|
|
}
|
|
|
|
/* ---------- reading/printing functions */
|
|
#include <assert.h>
|
|
#include <ctype.h>
|
|
|
|
/* writelines: prints n lines */
|
|
void writelines(char *lines[], int n)
|
|
{
|
|
while (n--)
|
|
printf("%s\n", *lines++);
|
|
}
|
|
|
|
/* readlines: reads lines from input, writing them to ln_buff
|
|
* and line pointers to lines.
|
|
* returns number of lines read,
|
|
* -lines_read-1 < 0 on buffer overflow
|
|
* maxlines+1 on lines overflow */
|
|
int readlines(char *lines[], int maxlines, char *buffer, size_t buff_size)
|
|
{
|
|
assert(maxlines > 0);
|
|
char ** const fst_line = lines;
|
|
int c, not_empty = 0;
|
|
|
|
for (*lines = buffer; (c = getchar()) != EOF && buff_size; --buff_size) {
|
|
not_empty |= !isspace(c);
|
|
if (c == '\n') {
|
|
if (!not_empty) { /* skip empty lines */
|
|
buff_size += buffer - *lines;
|
|
buffer = *lines;
|
|
continue;
|
|
}
|
|
not_empty = 0;
|
|
*buffer++ = '\0';
|
|
if (!--maxlines)
|
|
break;
|
|
*++lines = buffer;
|
|
} else
|
|
*buffer++ = c;
|
|
}
|
|
/* ignore trailing whitespace and empty lines */
|
|
while (c != EOF && isspace(c))
|
|
c = getchar();
|
|
if (c != EOF && !buff_size) /* buffer overflow, return -lines_read-1 */
|
|
return fst_line - lines - 1;
|
|
if (c != EOF && !maxlines) /* lines overflow, return maxlines+1 */
|
|
return lines - fst_line + 2;
|
|
return lines - fst_line + not_empty;
|
|
}
|
|
|
|
/* ---------- string quicksort */
|
|
#include <string.h>
|
|
|
|
void swap(char *v[], int i, int j);
|
|
|
|
/* qsort_string: sort v[left]...v[right] into increasing order */
|
|
void qsort_string(char *v[], int left, int right)
|
|
{
|
|
int i, last;
|
|
|
|
if (left >= right) /* do nothing if array contains */
|
|
return; /* fewer than two elements */
|
|
swap(v, left, (left + right)/2); /* move partition elem */
|
|
last = left; /* to v[0] */
|
|
|
|
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 */
|
|
|
|
qsort_string(v, left, last-1);
|
|
qsort_string(v, last+1, right);
|
|
}
|
|
|
|
/* swap: swap v[i] and v[j] */
|
|
void swap(char *v[], int i, int j)
|
|
{
|
|
char *temp = v[i];
|
|
v[i] = v[j], v[j] = temp;
|
|
}
|
|
|
|
|