C程序设计语言 5-7

练习5-7 重写readlines，将输入的文本行存储到由main函数提供的一个数组中，而不是存储到调用alloc分配的存储空间中。该函数的运行速度比改写前快多少？ 

#include <stdio.h>
#include <string.h>#define MAXLINES 5000
#define MAXLEN 1000char *lineptr[MAXLINES];
int readlines(char *lineptr[], char *allocation, int maxlines);
void writelines(char *lineptr[], int nlines);
void qsort(char *lineptr[], int left, int right);int main() {int nlines;char line[MAXLEN], *p;char allocation[10000];printf("Please input passage:\n");if ((nlines = readlines(lineptr, allocation, MAXLINES)) >= 0) {qsort(lineptr, 0, nlines - 1);writelines(lineptr, nlines);return 0;}else {printf("error: input too big to sort\n");return 1;}
}int getline(char *, int);int readlines(char *lineptr[], char *allocation, int maxlines) {int len, nlines, total_len;char *p, line[MAXLEN];nlines = 0;total_len = 0;while ((len = getline(line, MAXLEN)) > 0)if (nlines >= maxlines)return -1;else {line[len - 1] = '\0';strcpy(allocation + total_len, line);lineptr[nlines++] = allocation + total_len;total_len += len;}return nlines;
}void writelines(char *lineptr[], int nlines) {int i;for (i = 0; i < nlines; i++)printf("%s\n", lineptr[i]);return;
}int 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;
}void qsort(char *v[], int left, int right) {int i, last;void swap(char *v[], int i, int j);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);qsort(v, left, last - 1);qsort(v, last + 1, right);return;
}void swap(char *v[], int i, int j) {char *temp;temp = v[i];v[i] = v[j];v[j] = temp;return;
}

运行速度没有算，但如果仍是使用字符串指针存放每一行文本的首地址的话，速度应该是差不多的。因为都是对文本行首地址的遍历。

附上书上源代码：

#include <stdio.h>
#include <string.h>#define MAXLINES 5000char *lineptr[MAXLINES];
int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void qsort(char *lineptr[], int left, int right);int main() {int nlines;printf("Please input passage:\n");if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {qsort(lineptr, 0, nlines - 1);writelines(lineptr, nlines);return 0;}else {printf("error: input too big to sort\n");return 1;}
}#define MAXLEN 1000
int getline(char *, int);
char *alloc(int);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';strcpy(p, line);lineptr[nlines++] = p;}return nlines;
}void writelines(char *lineptr[], int nlines) {int i;for (i = 0; i < nlines; i++)printf("%s\n", lineptr[i]);return;
}int 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;
}#define ALLOCSIZE 10000static char allocbuf[ALLOCSIZE];
static char *allocp = allocbuf;char *alloc(int n) {if (allocbuf + ALLOCSIZE - allocp >= n) {allocp += n;return allocp - n;}else return 0;
}void qsort(char *v[], int left, int right) {int i, last;void swap(char *v[], int i, int j);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);qsort(v, left, last - 1);qsort(v, last + 1, right);return;
}void swap(char *v[], int i, int j) {char *temp;temp = v[i];v[i] = v[j];v[j] = temp;return;
}