c - 无链表的内存分配

Question

假设我有这个结构:

struct Book
{
   int book_id;
   struct Book *book_ptr;
};
/* navigation pointers */
struct Book *front;
struct Book *rear;

我想添加一本新的Book到我的内存中，所以我有这个函数:

void add_book() {
    struct Book *temp;  
    temp = (struct Book*)malloc(sizeof(struct Book));    
    temp->book_id = t;
    t++;    
    temp->book_ptr = NULL;       
    if (rear  ==  NULL)
    {
        front = temp;
        rear = temp;
    }
    else
    {
        rear->book_ptr = temp;
        rear = temp;
    }        
}

如果我想要我的书籍列表:

void see_all_the_books()
{
    struct Book *temp;     
    temp = front;    
    if (front  ==  NULL)
    {
        printf("> YOU HAVEN'T ADDED ANY BOOK YET\n");
    }
    while (temp)
    {
        printf("Book #%d\n", temp->book_id);
        temp = temp->book_ptr;
    }
}

相当简单，而且有效。 但是如果我不想使用链接列表怎么办？我想要做的是每次制作一本新书时将我的后指针移动一个格。

那么我的结构将是这样的:

struct Book
{
   int book_id;
};
/* navigation pointers */
struct Book *front;
struct Book *rear;

每次我想添加一本书时，我都需要将指针移动 1 block :

 void add_book() {
    struct Book *temp;
    temp = (struct Book*)malloc(sizeof(struct Book));

    temp->book_id = t;
    t++;

    if (rear  ==  NULL)
    {
        printf("Your FIRST book has been added\n");        
        front = temp; 
        rear = temp;
    }
    else
    {
        rear++;         // MOVED TO NEXT BLOCK
        rear = temp;    // OBVIOUSLY WRONG      
        printf("ANOTHER book has been added\n"); 
    }        
}

我需要在上一个代码中更改哪些内容？

Answer 1

在 add_book 中分配新的 struct Book 的方法引发了许多微妙的问题。这样做并没有什么问题，事实上这很常见，但是您必须注意如何将所需的参数传递给 add_book。要在 main() 中成功创建指针数组并使用 add_book 为添加的每本新书进行分配，您必须传递指针数组的地址 到 add_book 以在您需要更多指针时处理重新分配。您还需要一种方法来传递并跟踪已分配的指针数量和当前可用指针的最大数量。因此 add_book 的基本声明如下所示:

struct Book *add_book (struct Book ***book, int id, size_t *idx, size_t *nmax);

其中 ***book 是在 main() 中声明的指针数组的地址，id 是要分配的新值到 book_id，idx 是要添加的 struct Book 的当前索引，nmax 是可用指针的数量来填充。

注意:您将指向 idx 和 nmax 的指针传递给 add_book 函数。这允许您在 add_book 中增加/更改它们的值，同时在 main() 中获得更新的值。 add_book 的完整原型(prototype)可能如下所示:

struct Book *add_book (struct Book ***book, int id, size_t *idx, size_t *nmax)
{
    if (!book || !*book)   return NULL;

    size_t n = *idx;
    (*book)[*idx] = xcalloc (1, sizeof **book);

    (*book)[*idx]-> book_id = id;
    (*idx)++;

    if (*idx == *nmax) {    /* realloc if nmax reached, update nmax */
        void *tmp = realloc (*book, *nmax * 2 * sizeof tmp);
        if (!tmp) {
            fprintf (stderr, "%s() error: virtual memory exhausted.\n", __func__);
            return NULL;
        }
        *book = tmp;  /* use memset to initialize all new pointers NULL */
        memset (*book + *nmax, 0, *nmax * sizeof tmp);
        *nmax *= 2;
    }

    return (*book)[n];
}

注意:由于您将 Book 的地址传递给函数，因此必须取消引用 Book(即*book) 位于 add_book 中，以便正确使用指针数组。另请注意，xcalloc 只是一个错误检查函数，它调用 calloc 来防止因测试每次分配的 calloc 返回而导致逻辑困惑。

Windows 注意: Visual Studio 中的编译器不知道 __func__ 只是一个返回函数名称的宏。因此，如果您使用Visual Studio编译代码，只需将__func__替换为“函数名称”即可。

完整的示例会有所帮助。下面将使用指针数组来保存 struct Book 集合所需的所有部分放在一起。注意:在下面的示例中，最大图书数定义为 8，但给出了 10 book_id，强制重新分配 Book在 add_book 中，当 *idx == *nmax 时，*idx & *nmax = 8。

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

#define NBOOKS 8

struct Book {
    int book_id;
};

void *xcalloc (size_t n, size_t s);
struct Book *add_book (struct Book ***book, int id, size_t *idx, size_t *nmax);

int main (void) {

    size_t idx = 0;
    size_t nbooks = 0;
    size_t nmax = NBOOKS;
    int id = 0;
    struct Book **Book = NULL;

    /* create NBOOKS pointers to struct Book */
    Book = xcalloc (NBOOKS, sizeof *Book);

    /* read integer input from stdin */
    while (scanf ("%d", &id) == 1)
        add_book (&Book, id, &idx, &nmax);

    nbooks = idx;   /* save the number of books added */

    /* print the book_id for each book */
    for (idx = 0; idx < nbooks; idx++)
        printf ("  Book[%2zu] : %d\n", idx, Book[idx]->book_id);

    /* free all allocated memory */
    for (idx = 0; idx < nbooks; idx++)
        free (Book[idx]);
    free (Book);

    return 0;
}

/* add one struct Book to array of pointers to Book with book_id = 'id'
 * NOTE: since you must protect against writing beyond the last pointer 
 * you must pass the ADDRESS OF Book (the reason for ***) in the event a
 * realloc occurs. Otherwise the address of Book in main() will never
 * reflect the reallocation. (pointers to idx and nmax are passed so their
 * updated values are available in main() ).
 */
struct Book *add_book (struct Book ***book, int id, size_t *idx, size_t *nmax)
{
    if (!book || !*book)   return NULL;

    size_t n = *idx;
    (*book)[*idx] = xcalloc (1, sizeof **book);

    (*book)[*idx]-> book_id = id;
    (*idx)++;

    if (*idx == *nmax) {    /* realloc if nmax reached, update nmax */
        void *tmp = realloc (*book, *nmax * 2 * sizeof tmp);
        if (!tmp) {
            fprintf (stderr, "%s() error: virtual memory exhausted.\n", __func__);
            return NULL;
        }
        *book = tmp;  /* use memset to initialize all new pointers NULL */
        memset (*book + *nmax, 0, *nmax * sizeof tmp);
        *nmax *= 2;
    }

    return (*book)[n];
}


/** xcalloc allocates memory using calloc and validates the return.
 *  xcalloc allocates memory and reports an error if the value is
 *  null, returning a memory address only if the value is nonzero
 *  freeing the caller of validating within the body of code.
 */
void *xcalloc (size_t n, size_t s)
{
    register void *memptr = calloc (n, s);
    if (memptr == 0) {
        fprintf (stderr, "%s() error: virtual memory exhausted.\n", __func__);
        exit (EXIT_FAILURE);
    }

    return memptr;
}

样本输入(10 个整数)

$ cat dat/10int_nl.txt
8572
-2213
6434
16330
3034
12346
4855
16985
11250
1495

输出

$ ./bin/struct_book_simple <dat/10int_nl.txt
  Book[ 0] : 8572
  Book[ 1] : -2213
  Book[ 2] : 6434
  Book[ 3] : 16330
  Book[ 4] : 3034
  Book[ 5] : 12346
  Book[ 6] : 4855
  Book[ 7] : 16985
  Book[ 8] : 11250
  Book[ 9] : 1495

内存错误检查

$ valgrind ./bin/struct_book_simple <dat/10int_nl.txt
==9039== Memcheck, a memory error detector
==9039== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==9039== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==9039== Command: ./bin/struct_book_simple
==9039==
  Book[ 0] : 8572
 <snip>
  Book[ 9] : 1495
==9039==
==9039== HEAP SUMMARY:
==9039==     in use at exit: 0 bytes in 0 blocks
==9039==   total heap usage: 12 allocs, 12 frees, 272 bytes allocated
==9039==
==9039== All heap blocks were freed -- no leaks are possible
==9039==
==9039== For counts of detected and suppressed errors, rerun with: -v
==9039== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)