没有链接列表的内存分配

说我有这个结构:

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

我想在我的记忆中添加一Book ,所以我有这个function:

 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; } } 

如果我想要一份我的Books清单:

 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; } } 

相当简单,它的工作原理。 但是 ,如果我不想使用链接列表,该怎么办? 我想要做的是每次我正在制作新书时将我的rear指针移动一个块。

然后我的结构将是这样的:

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

每次我想添加一Book时,我需要移动指针1块:

  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"); } } 

我在上一段代码中需要更改什么?

您在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); 

其中***bookmain()声明的指针数组的地址, id是分配给book_id的新值, idx是要添加的struct Book的当前索引, nmax是可填充的指针数。

注意:您将指向idxnmax的指针传递给add_book函数。 这允许您在add_book增加/更改它们的值,同时在main()提供更新的值。 add_book的完整add_book可能如下所示:

 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地址传递给函数,因此必须在add_book中取消引用Book (即*book )才能正确使用指针数组。 另请注意, xcalloc只是一个错误检查函数,它调用calloc以防止在每次分配时测试calloc返回的逻辑混乱。

Windows注意事项: visual studio中的编译器不知道__func__只是一个返回函数名称的宏。 因此,如果您使用visual studio编译代码,只需将__func__替换为"function name"

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

 #include  #include  #include  #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; } 

Sampe输入(10 int)

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

产量

 $ ./bin/struct_book_simple  

内存错误检查

 $ valgrind ./bin/struct_book_simple  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) 

您需要创建一个指针数组,每个指针都指向一本书。 它将需要在您的代码中进行一些更改,因为不再需要前后。

 int maxbooks = somenumber; Struct book *books= malloc(maxbooks*sizeof(struct book)); int numbooks = 0; addbook() { (books+numbooks)->book_id = t; numbooks++; }