K&R 练习 5-13 如何让我的程序处理无限行输入

Question

练习 5-13。编写程序尾部，打印最后n行 其输入。默认情况下，n 设置为 10，但也可以是 由可选参数更改，以便

tail -n

打印最后 n 线。程序无论多么不合理都应该表现得合理 n 的输入或值。编写程序，使其发挥最佳效果 使用可用存储空间；行应按排序方式存储 5.6 节的程序，不是固定大小的二维数组。

这是我当前编写的代码：

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

int isint(char s[]);
int toint(char s[]);
int readlines(char *lineptr[], int no);
void writelines(char *lineptr[], int no);

#define MAXLINE 100

int main(int argc, char *argv[])
{
    int n = 10, nlines;
    char *lineptr[MAXLINE];

    while (--argc > 0) {
        if ((*++argv)[0] == '-' && isint(*argv) && toint(*argv) <= MAXLINE) {
            n = toint(*argv);
            break;
        }
        else
            printf("invalid argument %s\n", *argv);
    }

    printf("Printing %d line%s\n", n, n > 1 ? "s" : "");
    if ((nlines = readlines(lineptr, n)) >= 0) {
        writelines(lineptr, nlines);
        return 0;
    }
    else {
        printf("input too big too handle\n");
        return 1;
    }

    return 0;
}

int isint(char s[])
{
    while (*s == '-' || *s == '0')
        s++;
    if (isdigit(*s)) {
        while (*s != '\0')
            if (!isdigit(*s++))
                return 0;
        return 1;
    }
    else
        return 0;
}

int toint(char s[])
{
    while (*s == '-' || *s == '0')
        s++;
    return atoi(s);
}

#define MAXLEN 1000

int readlines(char *lineptr[], int no)
{
    char *alloc(int n, int no);
    int get_line(char *, int);
    void push(char *lineptr[], char *p, int len);

    int nlines, len, i;
    char *p, line[MAXLEN];

    for (i = 0; i < no; i++)
        lineptr[i] = NULL;

    nlines = 0;
    while ((len = get_line(line, MAXLEN)) > 0)
        if ((p = alloc(len, no)) == NULL) {
            return -1;
        } else {
            line[len-1] = '\0';
            strcpy(p, line);
            push(lineptr, p, no);
            nlines++;
        }
    return no < nlines ? no : nlines;
}

void writelines(char *lineptr[], int no)
{
    int i;
    
    for (i = 0; i < no; i++)
        if (lineptr[i] != NULL)
            printf("%s\n", lineptr[i]);
}

int get_line(char *line, int lim)
{
    int i, c;

    i = 0;
    while (--lim > 0 && (c = getchar()) != EOF && c != '\n')
        line[i++] = c;
    if (c == '\n')
        line[i++] = c;
    line[i] = '\0';

    return i;
}

void push(char *lineptr[], char *p, int no)
{
    void shift(int i)
    {
        if (i > 1)
            shift(i-1);
        lineptr[i-1] = lineptr[i];
    }

    shift(no-1);
    lineptr[no-1] = p;
}

static char allocbuf[MAXLINE][MAXLEN];
static int allocn = 0;

char *alloc(int n, int no)
{
    if (n < MAXLEN) {
        allocn++;
        return allocbuf[allocn%no];
    } else
        return NULL;
}

它可以处理无限数量的行作为输入，但它使用二维数组，这本书要求我像这样存储行：

#define ALLOCSIZE 10000

static char allocbuf[ALLOCSIZE];
static char *allocp = allocbuf;

char *alloc(int n)
{
    if (n <= ALLOCSIZE - (allocp - allocbuf)) {
        allocp += n;
        return allocp - n;
    } else
        return NULL;
}

void afree(char *p)
{
    if (p >= allocbuf && p < allocbuf + ALLOCSIZE)
        allocp = p;
}

这样我就无法用新行替换我存储的过时行。我可以将

allocbuf

分成多个 1000 个字符长的部分作为解决方案，但这本质上是一个手动二维数组并重新发明轮子，而不是书上要求我做的。我只能想到一些设计，而且这些设计真的很难实现。

Answer 1

看起来有点乱，但弄清楚了：

#define ALLOCSIZE MAXLINE * MAXLEN

static char allocbuf[ALLOCSIZE];
static int allocn = 0; /* the number of allocations */
static char *allocp = allocbuf;
static char *backallocp = allocbuf; /* the start of replaceable section of array */
static char *backallocpend = allocbuf - 1; /* the end of replaceable section of array */

char *alloc(int n, int no)
{
    int i;
    char *j;

    if (allocn%no == no - 1) {
        backallocp = allocbuf;
        backallocpend = allocbuf - 1;
    }
    if (allocn >= no) {
        while (allocn-no >= no)
            allocn -= no;
        for (i = 0; i < allocn%no; i++)
            while (*backallocpend++ != '\0');
                ;
    }

    if (n <= backallocpend - backallocp + 1) {
        backallocp += n;
        allocn++;
        return backallocp - n;
    } else if (n <= allocbuf + ALLOCSIZE - allocp) {
        allocp += n;
        allocn++;
        return allocp - n;
    } else
        return NULL;
}