没有链接列表的内存分配 [英] Memory Allocation without Linked List
问题描述
说我有这个结构:
struct Book
{
int book_id;
struct Book *book_ptr;
};
/* navigation pointers */
struct Book *front;
struct Book *rear;
，并且我想在内存中添加一个新的Book，因此我具有以下功能:
and I want to add a new Book to my memory, so I have this 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指针移动一格.
Fairly straightforward, and it works.
But what if I don't want to use Linked List. What I want to do is to move my rear pointer one block every time that I am making a new book.
然后我的结构将是这样的:
Then my struct would be something like this:
struct Book
{
int book_id;
};
/* navigation pointers */
struct Book *front;
struct Book *rear;
，每次我要添加Book时，我都需要将指针移动1个块:
and I need to move my pointer 1 block every time I want to add a Book:
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");
}
}
我需要在最后一个代码中更改什么?
What do I need to change in my last code?
推荐答案
在add_book中分配新的struct Book的方法引起了许多微妙的问题.这样做并没有错，实际上这很普遍，但是您必须小心如何将必需的参数传递给add_book.要在main()中成功创建一个指针数组并使用add_book为添加的每本新书分配，您必须将指针数组的地址传递给add_book来处理重新分配中的指针.如果您需要更多的指针.您还需要一种方法来传递并跟踪和已分配的指针的当前数量.因此，add_book的基本声明类似于:
There are a number of subtle issue raised by your approach of allocating a new struct Book in add_book. This is nothing wrong with doing it this way, in fact it is quite common, but you must take care how you pass the required parameters to add_book. To successfully create an array of pointers in main() and use add_book to allocate for each new book added, you must pass the address of your array of pointers to add_book to handle reallocation in the event you need more pointers. You also need a way to pass and keep track of the number of pointers you have allocated and the current maximum number of pointers available. Therefore a basic declaration for add_book would look something like:
struct Book *add_book (struct Book ***book, int id, size_t *idx, size_t *nmax);
其中***book是在main()中声明的指针数组的地址，id是要分配给book_id的新值，idx是struct Book要添加的当前索引，并且nmax是可填充的指针数.
Where ***book is the address of your array of pointers declared in main(), id is the new value to assign to book_id, idx is the current index for the struct Book to add and nmax is the number of pointers available to fill.
注意:您正在将指向idx和nmax的指针传递给add_book函数.这使您可以在add_book中增加/更改其值，同时在main()中具有可用的更新值. add_book的完整原型可能如下:
Note: you are passing a pointer to both idx and nmax to your add_book function. This allows you to increment/change their values in add_book while having thier updated values available in main(). A full prototye foradd_book could look like:
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返回时弄乱逻辑.
Note: since you passed the address of Book to the function, you must dereference Book (i.e. *book) in add_book in order to properly work with the array of pointers. Also note xcalloc is just an error checking function that calls calloc to prevent cluttering the logic with testing the return of calloc each allocation.
Windows注意: Visual Studio中的编译器不知道__func__仅仅是返回函数名称的宏.因此，如果您使用Visual Studio编译代码，只需将__func__替换为"function name".
Note for Windows: The compiler in visual studio does not know that __func__ is simply a macro to return the function name. So if you are using visual studio to compile the code, just replace __func__ with "function name".
完整的示例会有所帮助.下面将使用指针数组保存您的struct Book集合所需的所有部分放在一起.注意:在下面的示例中，最大图书数量被定义为8，但是当*idx == *nmax都位于*idx & *nmax = 8时，给出10 book_id强制在add_book中重新分配Book.
A full example will help. The following puts all the pieces together necessary to use an array of pointers to hold your collection of struct Book. Note: during the example below, the maximum number of books is defined as 8, but 10 book_id's are given forcing the reallocation of Book in add_book when *idx == *nmax where both *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)
这篇关于没有链接列表的内存分配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
