Проблема с динамическим массивом

Question

Я написал кусок кода для обработки динамических массивов.Идея состояла в том, чтобы использовать массив указателей структуры, где последний член массива - NULL.Небольшая вариация кода, который я написал, приведена ниже (с использованием целых чисел, а не структур).

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

void list_add(int **list, int* value) {
   for(int i = 0; true; i++) {
      if(list[i] == NULL) {
         list = realloc(list, (i+2) * sizeof(int*));
         list[i] = value;
         list[i+1] = NULL;
         break;
      }
   }
}

void list_init(int **list) {
   int* x;
   for(int i = 0; i < 100; i++) {
      x = malloc(sizeof(int));
      *x = i;
      list_add(list, x);
   }
}

int main() {
   int** l = malloc(sizeof(int*));
   l[0] = NULL;
   list_init(l);
}

Во время отладки я обнаружил, что в список добавляются только первые 3 целых числа.Я не могу понять, почему это происходит.Есть идеи?

Answer 1

Проблема в том, что вызов realloc() в list_add() потенциально освобождает блок памяти *list и выделяет другой. list_add обновляет свой указатель list, но не возвращает обновленный указатель вызывающей стороне, list_init(); list_init() Указатель list потенциально является указателем на недавно освобожденный блок памяти.

Чтобы исправить этот код, list_add() и list_init() должны иметь возможность "вернуть" обновленный указатель list:

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

void list_add(int ***p_list, int *value) {
   int **list = *p_list;
   int i;
   for(i = 0; true; i++) {
      if(list[i] == NULL) {
         list = realloc(list, (i+2) * sizeof(int*));
         list[i] = value;
         list[i+1] = NULL;
         break;
      }
   }
   *p_list = list;
}

void list_init(int ***p_list) {
   int **list = *p_list;
   int *x;
   int i;
   for(i = 0; i < 100; i++) {
      x = malloc(sizeof(int));
      *x = i;
      list_add(&list, x);
   }
   *p_list = list;
}

int main() {
   int **list = malloc(sizeof(int*));
   list[0] = NULL;
   list_init(&list);

   int **l = list;
   for (; *l != NULL; ++l) {
      printf("%d\n", **l);
   }
}

http://codepad.org/iGcSaJOR

Answer 2

EDIT

В этом случае динамические массивы, как вы сказали, не улучшат ничего, код только усложнит. Для каждого добавления целого числа вы использовали realloc, пытаясь агрессивно сэкономить память, но это займет больше времени при выполнении. Почему бы не выделить блок памяти, зарезервированный для массива, и для отражения динамического символа поместите массив в структуру с последним индексом, а когда вы добавите что-либо, добавьте его в последнее место и увеличьте счетчик. Когда этот блок заполнен, вы можете связать другой блок, чтобы он указывал на другой.

typedef struct _dyna_arr
{
  my_type data_arr[MAX_LEN];
  int n;
  struct _dyna_arr *next block;
};

Поэтому вы ведете связанный список из нескольких массивов. Размер MAX_LEN можно исправить, что подходит для приложения, которое поможет уменьшить внутреннюю фрагментацию.

* старый ответ удален *