动态分配大小未知的字符串

Question

我必须names从输入中获取已知数量的名称作为一个字符串,每个字符串用空格分隔,我必须为每个字符串获取名称的字符串数组动态分配内存,

    char** names;
    char ch;
    names = malloc(N*sizeof(char*); /*N is defined*/

    for(i=0; i<N; i++) {

现在我必须为每个字符串分配而不使用定义的数字:

    i=0, j=0;
    while ((ch=getchar) != '\n') {
         while (ch != ' ') {
              names[i][j++] = ch;
         }
         if (ch == ' ') {
              names[i][j] = '\0';
              i++}}
    if (ch == '\n')
         names[i][j] = '\0';

Answer 1

这是如何处理动态分配和重新分配以存储未知数量的字符串的经典问题.(在保存到数组之前,将每个字符串分成单独的标记)需要详细了解此过程,因为它将作为几乎任何其他情况下读取未知数量值的基础(无论是它们是结构,花车,人物等......).

您可以使用许多不同类型的数据结构,列表,树等,但基本方法是创建一个指向类型指针的数组(在这种情况下类型为char),然后在读取数据时为每个指针分配空间,填充数据和分配新内存块的起始地址.指向指针的指针的简写只是双指针(例如char **array;,如果你愿意,技术上指向指针指向char或指向char的指针)

为未知行数分配内存的一般且有效的方法是首先分配合理预期的指针数(每个预期令牌为1).这比realloc为添加到阵列的每个标记调用和重新分配整个集合要高效得多.在这里,您只需保留一个计数器,该计数器会添加到您的数组中的令牌数量,当您达到原始分配限制时,您只需重新分配两倍于当前指针数量的指针.请注意,您可以自由添加您选择的任何增量.您每次只需添加固定金额,或者您可以使用原始的一些缩放倍数 - 这取决于您.重新分配到当前的两倍只是标准方案之一.

什么是" 合理预期的指针数量？ "这不是确切的数字.你只想对你所期望的令牌数进行有根据的猜测,并将其用作分配指针的初始数.如果你只想到100,你不会想要分配10,000个指针.这将是非常浪费的.重新分配将解决任何不足,因此只需粗略猜测即可.如果你真的不知道,然后分配一些合理的数字,说64还是128等等.你可以简单地声明限制为您的代码的开头恒定,所以很容易调整.例如:

#declare MAXPTR 128

或使用匿名完成相同的事情 enum

enum { MAXPTR = 128 };

在最初分配指针时,作为重新分配的一部分,您可以通过将每个指针设置为来获益NULL.这对于原始分配很容易实现.只需使用calloc而不是malloc.在重新分配时,它要求您设置分配给的所有新指针NULL.它提供的好处是第一个NULL充当哨兵,指示你的有效指针停止的点.只要您确保至少有一个NULL保留为哨兵,您可以在不知道精确指针数量的情况下进行迭代.例如:

size_t i = 0;
while (array[i]) {
    ... do your stuff ...
}

完成使用分配的内存后,您需要确保释放内存.在一段简单的代码中,内存在退出时释放,养成跟踪分配的内存并在不再需要时释放内存的习惯.

对于此特定任务,您需要将一行未知数量的字符读入内存,然后将该字符串标记(分离)为标记.getline将读取并分配足以容纳任何大小字符串的内存.您可以使用任何其他输入函数执行相同的操作,您只需自己编写重复检查和重新分配的代码.如果getline可用(它在每个现代编译器中),请使用它.然后,只需将输入分为带有或的标记.然后,您将要复制每个标记以将每个标记保留在其自己的内存块中,并将该位置分配给您的标记数组.以下是一个简短的例子.strtokstrsep

示例中包括几个用于打开文件,分配和重新分配的辅助函数.他们所做的只是简单的错误检查,这有助于保持代码的主体清洁和可读.查看示例,如果您有任何疑问,请告诉我.

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

#define MAXL  64    /* initial number of pointers  */

/* simple helper/error check functions */
FILE *xfopen (const char *fn, const char *mode);
void *xcalloc (size_t n, size_t s);
void *xrealloc_dp (void *ptr, size_t *n);

int main (int argc, char **argv) {

    char **array = NULL;
    char *line = NULL;
    size_t i, idx = 0, maxl = MAXL, n = 0;
    ssize_t nchr = 0;
    FILE *fp = argc > 1 ? xfopen (argv[1], "r") : stdin;

    array = xcalloc (maxl, sizeof *array);    /* allocate maxl pointers */

    while ((nchr = getline (&line, &n, fp)) != -1)
    {
        while (nchr > 0 && (line[nchr-1] == '\r' || line[nchr-1] == '\n'))
            line[--nchr] = 0; /* strip carriage return or newline   */

        char *p = line;  /* pointer to use with strtok */
        for (p = strtok (line, " \n"); p; p = strtok (NULL, " \n")) {

            array[idx++] = strdup (p);  /* allocate & copy  */

            /* check limit reached  - reallocate */
            if (idx == maxl) array = xrealloc_dp (array, &maxl);
        }
    }
    free (line);  /* free memory allocated by getline */
    if (fp != stdin) fclose (fp);

    for (i = 0; i < idx; i++)  /* print all tokens */
        printf (" array[%2zu] : %s\n", i, array[i]);

    for (i = 0; i < idx; i++)  /* free all memory  */
        free (array[i]);
    free (array);

    return 0;
}

/* fopen with error checking */
FILE *xfopen (const char *fn, const char *mode)
{
    FILE *fp = fopen (fn, mode);

    if (!fp) {
        fprintf (stderr, "xfopen() error: file open failed '%s'.\n", fn);
        // return NULL;
        exit (EXIT_FAILURE);
    }

    return fp;
}

/* simple calloc with error checking */
void *xcalloc (size_t n, size_t s)
{
    void *memptr = calloc (n, s);
    if (memptr == 0) {
        fprintf (stderr, "xcalloc() error: virtual memory exhausted.\n");
        exit (EXIT_FAILURE);
    }

    return memptr;
}

/*  realloc array of pointers ('memptr') to twice current
 *  number of pointer ('*nptrs'). Note: 'nptrs' is a pointer
 *  to the current number so that its updated value is preserved.
 *  no pointer size is required as it is known (simply the size
 *  of a pointer
 */
void *xrealloc_dp (void *ptr, size_t *n)
{
    void **p = ptr;
    void *tmp = realloc (p, 2 * *n * sizeof tmp);
    if (!tmp) {
        fprintf (stderr, "%s() error: virtual memory exhausted.\n", __func__);
        exit (EXIT_FAILURE);
    }
    p = tmp;
    memset (p + *n, 0, *n * sizeof tmp); /* set new pointers NULL */
    *n *= 2;

    return p;
}

输入文件

$ cat dat/captnjack.txt
This is a tale
Of Captain Jack Sparrow
A Pirate So Brave
On the Seven Seas.

产量

$ ./bin/getline_strtok <dat/captnjack.txt
 array[ 0] : This
 array[ 1] : is
 array[ 2] : a
 array[ 3] : tale
 array[ 4] : Of
 array[ 5] : Captain
 array[ 6] : Jack
 array[ 7] : Sparrow
 array[ 8] : A
 array[ 9] : Pirate
 array[10] : So
 array[11] : Brave
 array[12] : On
 array[13] : the
 array[14] : Seven
 array[15] : Seas.

内存/错误检查

在你的动态分配内存的任何代码中,你有2个责任关于任何分配的内存块:(1)总是保留一个指向内存块起始地址的指针,所以,(2)它可以在没有时被释放需要更久.您必须使用内存错误检查程序,以确保您没有在已分配的内存块之外/之外写入,并确认已释放已分配的所有内存.对于Linux valgrind来说是正常的选择.有许多微妙的方法来滥用可能导致实际问题的内存块,没有理由不这样做.每个平台都有类似的记忆检查器.它们都很简单易用.只需通过它运行您的程序.

$ valgrind ./bin/getline_strtok <dat/captnjack.txt
==26284== Memcheck, a memory error detector
==26284== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==26284== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==26284== Command: ./bin/getline_strtok
==26284==
 array[ 0] : This
 array[ 1] : is
<snip>
 array[14] : Seven
 array[15] : Seas.
==26284==
==26284== HEAP SUMMARY:
==26284==     in use at exit: 0 bytes in 0 blocks
==26284==   total heap usage: 18 allocs, 18 frees, 708 bytes allocated
==26284==
==26284== All heap blocks were freed -- no leaks are possible
==26284==
==26284== For counts of detected and suppressed errors, rerun with: -v
==26284== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)

您每次要确认的是" 释放所有堆块 - 不可能泄漏 "和" 错误摘要:0个上下文中的0个错误 ".