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]);

}

The function getline is from Section 1.9. The main new thing is the declaration for lineptr:

char *lineptr[MAXLINES]

says that lineptr is an array of MAXLINES elements, each element of which is a pointer to a char. That is, lineptr[i] is a character pointer, and *lineptr[i] is the character it points to, the first character of the i-th saved text line. Since lineptr is itself the name of an array, it can be treated as a pointer in the same manner as in our earlier examples, and writelines can be written instead as

/* writelines: write output lines */

void writelines(char *lineptr[], int nlines)

{

while (nlines-- > 0)

printf("%s\n", *lineptr++);

}

Initially, *lineptr points to the first line; each element advances it to the next line pointer while nlines is counted down. With input and output under control, we can proceed to sorting. The quicksort from Chapter 4 needs minor changes: the declarations have to be modified, and the comparison operation must be done by calling strcmp. The algorithm remains the same, which gives us some confidence that it will still work.

/* 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);

}

Similarly, the swap routine needs only trivial changes:

/* swap: interchange v[i] and v[j] */

void swap(char *v[], int i, int j)

{

char *temp;

temp = v[i];

v[i] = v[j];

v[j] = temp;

}

Since any individual element of v (alias lineptr) is a character pointer, temp must be also, so one can be copied to the other.

Exercise 5-7. Rewrite readlines to store lines in an array supplied by main, rather than calling alloc to maintain storage. How much faster is the program?