使用 realloc() 将数组的大小加倍

Question

以下是我的程序节选

void insert(int *pq,int key){
      if(MS==N){
           pq=(int*)realloc(pq,sizeof(int)*MS*2);
           MS*=2;
      }
      pq[++N]=INT_MIN;
      increase_key(pq,N,key); 
}

int* priority_queue(){
     int *heap=(int*)malloc(sizeof(int)*10);
     MS=10;
     return heap;
}

在插入函数中重新分配内存时出现此错误。我想在数组完全填满后将其大小加倍。

(gdb) n
46             pq=(int*)realloc(pq,sizeof(int)*MS*2);
(gdb) n
*** Error in `/home/akhileshydv/Documents/Cprog/a.out': realloc(): invalid next size: 0x0000000000602010 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x777e5)[0x7ffff7a847e5]
/lib/x86_64-linux-gnu/libc.so.6(+0x834aa)[0x7ffff7a904aa]
/lib/x86_64-linux-gnu/libc.so.6(+0x85ba9)[0x7ffff7a92ba9]
/lib/x86_64-linux-gnu/libc.so.6(realloc+0x22f)[0x7ffff7a918ef]
/home/akhileshydv/Documents/Cprog/a.out[0x4007d5]
/home/akhileshydv/Documents/Cprog/a.out[0x4005e8]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7ffff7a2d830]
/home/akhileshydv/Documents/Cprog/a.out[0x4004e9]
======= Memory map: ========
00400000-00401000 r-xp 00000000 08:09 3414051                            /home/akhileshydv/Documents/Cprog/a.out
00600000-00601000 r--p 00000000 08:09 3414051                            /home/akhileshydv/Documents/Cprog/a.out
00601000-00602000 rw-p 00001000 08:09 3414051                            /home/akhileshydv/Documents/Cprog/a.out
00602000-00623000 rw-p 00000000 00:00 0                                  [heap]
7ffff0000000-7ffff0021000 rw-p 00000000 00:00 0 
7ffff0021000-7ffff4000000 ---p 00000000 00:00 0 
7ffff77f7000-7ffff780d000 r-xp 00000000 08:09 3936807                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7ffff780d000-7ffff7a0c000 ---p 00016000 08:09 3936807                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7ffff7a0c000-7ffff7a0d000 rw-p 00015000 08:09 3936807                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7ffff7a0d000-7ffff7bcd000 r-xp 00000000 08:09 3938830                    /lib/x86_64-linux-gnu/libc-2.23.so
7ffff7bcd000-7ffff7dcd000 ---p 001c0000 08:09 3938830                    /lib/x86_64-linux-gnu/libc-2.23.so
7ffff7dcd000-7ffff7dd1000 r--p 001c0000 08:09 3938830                    /lib/x86_64-linux-gnu/libc-2.23.so
7ffff7dd1000-7ffff7dd3000 rw-p 001c4000 08:09 3938830                    /lib/x86_64-linux-gnu/libc-2.23.so
7ffff7dd3000-7ffff7dd7000 rw-p 00000000 00:00 0 
7ffff7dd7000-7ffff7dfd000 r-xp 00000000 08:09 3938808                    /lib/x86_64-linux-gnu/ld-2.23.so
7ffff7fdb000-7ffff7fde000 rw-p 00000000 00:00 0 
7ffff7ff5000-7ffff7ff8000 rw-p 00000000 00:00 0 
7ffff7ff8000-7ffff7ffa000 r--p 00000000 00:00 0                          [vvar]
7ffff7ffa000-7ffff7ffc000 r-xp 00000000 00:00 0                          [vdso]
7ffff7ffc000-7ffff7ffd000 r--p 00025000 08:09 3938808                    /lib/x86_64-linux-gnu/ld-2.23.so
7ffff7ffd000-7ffff7ffe000 rw-p 00026000 08:09 3938808                    /lib/x86_64-linux-gnu/ld-2.23.so
7ffff7ffe000-7ffff7fff000 rw-p 00000000 00:00 0 
7ffffffde000-7ffffffff000 rw-p 00000000 00:00 0                          [stack]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]

Program received signal SIGABRT, Aborted.
0x00007ffff7a42428 in __GI_raise (sig=sig@entry=6)
    at ../sysdeps/unix/sysv/linux/raise.c:54
54  ../sysdeps/unix/sysv/linux/raise.c: No such file or directory.

为什么会出现这个错误？请提出任何解决方案。

编辑：我已按照评论部分的建议将 'pq' 变量设置为全局变量，但问题仍然存在。

void priority_queue(){
     pq=malloc(sizeof(int)*10);
     MS=10;
}

void insert(int key){
      if(MS==N){
           pq=realloc(pq,sizeof(int)*MS*2);
           MS*=2;
      }
      pq[++N]=INT_MIN;
      increase_key(N,key); 
}

Answer 1

如果 N 以 -1 开头，那么您应该尝试：

void insert(int key){
      if(MS==N+1){
           pq=realloc(pq,sizeof(int)*MS*2);
           MS*=2;
      }
      pq[++N]=INT_MIN;
      increase_key(N,key); 
}

但我同意从0开始会更好

Answer 2

几个问题：

您需要在 insert 函数中对 pq 进行额外级别的间接访问 - 如果您使用 realloc 更新值，[= 的新值12=] 不会在调用 insert 的函数中更新。
永远不要将 realloc 的结果直接分配给原始指针 - 如果 realloc 失败，它将 return NULL，并且你'最终会丢失对先前分配的内存的引用，从而导致内存泄漏。将结果分配给一个临时变量，检查临时变量以确保 realloc 成功，然后更新您的原始指针和大小变量。
如果您打算让 N 成为 *pq 中 下一个可用元素 的索引，那么您应该更新它作为 N++，而不是 ++N。如果您使用 ++N，那么 N 是 最后写入的元素 的索引（并且您跳过元素 0，并且您冒着索引一个超过最后一个元素的风险数组）。根据 insert 函数的编写方式，您似乎打算让 N 表示 *pq 中的下一个可用元素，因此您应该将其更新为 N++。
不要转换 malloc/calloc/realloc 的结果 - 如果你的编译器报错，那么你正在编译这段代码 作为 C++，而不是 C。如果您打算将此代码编译为 作为 C++，那么您根本不应该使用 malloc，而是 vector 或其他一些标准容器。如果您打算将此代码编译为 作为 C，则丢失 malloc 和 realloc 上的强制转换并仔细检查您的编译器设置。

综合起来：

void insert(int **pq, int key){
      if(MS == N) {
           int *tmp = realloc(*pq, sizeof **pq * MS * 2); // sizeof **pq == sizeof (int)
           if (tmp)
           {
             *pq = tmp;
             MS *= 2;
           }
           else
           {
             // realloc failed, original buffer is still intact.  Handle
             // as appropriate.
           }
      }
      (*pq)[N++] = INT_MIN; // parens are required here
      increase_key(*pq, N, key); // assuming increase_key does not need to modify pq
}

你可以这样称呼它：

int *q = malloc( sizeof *q * INITIAL_NUMBER_OF_ELEMENTS );
...
insert( &q, keyval );

使用 realloc() 将数组的大小加倍

doubling the size of array with realloc()

c

memory

realloc