c - C 中的 Arraylist 在重新分配时失败

Question

我正在尝试使用以下代码在 C 中构建一个数组列表

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

// Declaration of ArrayList structure
typedef struct ArrayList {
  int length, capacity;
  int *items;
} ArrayList;

// Create a new ArrayList
ArrayList *newList() {
  int *items = malloc(4 * sizeof(int));
  ArrayList *list = malloc(sizeof(ArrayList));
  list->length = 0;
  list->capacity = 4;
  list->items = items;
  return list;
}

// Check and expand list if neccessary
void check(ArrayList *list) {
  printf("Check called (%d, %d)\n", list->length, list->capacity);
  if (list->length >= list->capacity) {
    printf("Expanding\n");
    list->capacity = list->capacity * 2;
    printf("Reallocating\n");
    list->items = realloc(list->items, list->capacity);
    if (list->items == NULL) {
      printf("realloc failed\n");
      exit(1);
    }
  }
}

// Add a value to the ArrayList
void add(ArrayList *list, int n) {
  check(list);
  list->items[list->length] = n;
  list->length++;
}

// Print the list
void printList(ArrayList *list) {
  for (int i=0; i<list->length; i++) {
    if (i > 0) printf(", ");
    printf("%d", list->items[i]);
  }
  printf("\n");
}

int main () {
  ArrayList *list = newList();
  for (int i = 0; i < 20; i++) {
    add(list, i);
  }
  printList(list);
}

当数组已满时，检查函数将按其应有的方式被调用。但是，第二次调用 check 函数时，程序在调用 realloc 时失败，并出现以下错误:

*** Error in `./test': realloc(): invalid next size: 0x0000000001d3c010 ***
Aborted (core dumped)

每次程序运行时大小都会变化。

我读到此错误是由损坏的堆引起的，这通常是由指针在某处出错引起的。但是，我看不出这个例子的问题出在哪里。任何帮助将不胜感激。

Answer 1

您正在重新分配列表->项目。 realloc() 函数有 2 个参数 第一个参数是void指针，指向之前分配的内存块，第二个参数表示需要重新分配的字节数。

在您的代码中，您仅添加了容量...bt，它不是。您必须添加带有容量的 int 大小...因为它只需要 (size ) int 字节... 然后就可以正常工作了

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

// Declaration of ArrayList structure
typedef struct ArrayList {
    int length, capacity;
    int *items;
} ArrayList;
int i;
// Create a new ArrayList
ArrayList *newList() {
    int *items = malloc(4 * sizeof(int));
    ArrayList *list = malloc(sizeof(ArrayList));
    list->length = 0;
    list->capacity = 4;
    list->items = items;
    return list;
}

// Check and expand list if neccessary
void check(ArrayList *list) {
    printf("Check called (%d, %d)\n", list->length, list->capacity);
    if (list->length >= list->capacity) {
        printf("Expanding\n");
        list->capacity = list->capacity * 2;
        printf("Reallocating\n");
        list->items = realloc(list->items, list->capacity * sizeof(int));
        if (list->items == NULL) {
            printf("realloc failed\n");
            exit(1);
        }
    }
}

// Add a value to the ArrayList
void add(ArrayList *list, int n) {
    check(list);
    list->items[list->length] = n;
    list->length++;
}

// Print the list
void printList(ArrayList *list) {
    for (i=0; i<list->length; i++) {
        if (i > 0) printf(", ");
        printf("%d", list->items[i]);
    }
    printf("\n");
}

int main () {
    ArrayList *list = newList();
    for ( i = 0; i < 20; i++) {
        add(list, i);
    }
    printList(list);
}