Инициализировать двумерный массив неизвестного размера

Question

У меня есть двумерный массив символов, например char aList[numStrings][maxLength]. в идеале, во время выполнения программы я хочу иметь возможность изменять содержимое списка, т. е. добавлять, изменять или удалять записи. Поскольку aList может быть изменен, я не хочу перекомпилировать мою программу после каждого такого изменения, чтобы изменить aList. Поэтому я хочу записать aList в текстовый файл в конце программы, а затем прочитать его обратно в aList в начале следующего запуска программы.

Однако я не знаю при запуске программы, каково значение numStrings. (Я не использую C99, поэтому я не могу использовать VLA и взять количество предыдущих строк из внешнего файла.) Я мог бы, конечно, установить numStrings на искусственно высокое значение, но это решает!

Есть ли способ заполнить aList, не зная значения numStrings? Я не думаю, что есть (я смотрел на связанные вопросы), но есть ли другой способ достижения того, что мне нужно?

Answer 1

Если вы действительно хотите иметь возможность удалять элементы из середины сетки (ваши вопросы по этому вопросу не ясны), вам понадобится некая многосвязная структура. Они часто используются для реализации разреженных массивов, поэтому вы, вероятно, можете найти один заранее созданный.

Я говорю о чем-то вроде этого:

+---+  
| A |  
+-|\+  
  | \  
  |  \  
  |   \  
  |    \
  |     +----+----+----+  
  |     | C0 | C1 | C2 | ...  
  |     +--|-+----+--|-+  
  |        |         |
  |        |         |  
+-V--+  +--V-+       | +----+
| R0 |->|a0,0|-------+>|a0,3|--> ...
+----+  +--|-+    +--V-+----+
| R1 |-----+----->|a1,2|--> ...
+----+     |      +--|-+
 ...       V         |
          ...        V
                    ...  

Где A - корневой узел объекта, C - массив указателей столбцов, R - массив указателей строк, и каждая ячейка указывает на своего следующего соседа как по своей строке, так и по столбцу. Предполагается, что все ячейки, не представленные явно, имеют некоторое значение по умолчанию (обычно NULL или 0).

Это простая идея, но довольно придирчивая реализация, с большим количеством шансов испортиться, поэтому используйте отлаженную библиотеку, если можете.

Answer 2

Вы можете использовать динамически размещенный массив. Используйте malloc(), чтобы сделать один, realloc(), чтобы изменить размер одного, и free(), когда вы закончите с ним. Но это уже было охвачено другим ответом .

Другая альтернатива - использовать связанный список . Таким образом, вам не нужно realloc() каждый раз, когда вы хотите расширить свой массив - realloc() может быть довольно дорогим, если ему нужно скопировать весь массив в новое место.

Answer 3

2D-массивы в стиле C в общем, простите, выглядят странно ... они выглядят простыми и полезными на бумаге, но реализация динамического управления памятью - обработка ошибок выделения и очистки / изменения размеров - часто довольно сложна в деталях.

Что вы можете сделать, это что-то вроде:

/*
 * Start with an array that can hold INITIAL_NUM elements of (char*).
 */
char **aList = (char**)malloc(INITIAL_NUM, sizeof(*aList));
int curIdx = 0, curListSz = INITIAL_NUM;

while (more_stuff_to_append) {
    /*
     * Still space in the existing list ? If not - resize
     */
    if (curIdx >= INITIAL_NUM) {
        curListSz += ALLOC_INCREMENT_FOR_ALIST;
        if ((aList = realloc(aList, curListSz * sizeof(*aList))) == NULL)
            error_and_yucky_cleanup("can't resize list, out of memory");
    }

    /*
     * Allocate a new element.
     * Note that if it's _known_ in advance that all elements
     * are the same size, then malloc'ing a big block and slicing
     * that into pieces is more efficient.
     */
    if ((aList[curIdx] = malloc(new_elem_size, sizeof(char)) == NULL)
        error_and_yucky_cleanup("out of memory");

    /*
     * put the contents into the new buffer, however that's done.
     */
    populate_new_entry(aList[curIdx]);
    curIdx++;
}

Большая проблема с этими подходами обычно состоит в том, что очистка грязная. Нужно пройти через массив и вызвать free () для каждого элемента, плюс дополнительный финальный элемент для очистки aList.

Если вы заранее знаете все размеры, можно выделить один блок памяти, который содержит как aList, так и все элементы. Это работает через что-то вроде:

#define LISTSZ(lst) (NUMSTRINGS_MAX * sizeof(*(lst)))
#define ELEMSZ(lst) (STRINGSIZE_MAX * sizeof(**(lst)))

char **aList = malloc(LISTSZ(aList) + NUMSTRINGS * ELEMSZ(aList));
char *curElem = ((char*)aList) + LISTSZ(aList));
int i;

for (i = 0; i < NUMSTRINGS_MAX; i++) {
    aList[i] = curElem;
    curElem += ELEMSZ(aList);
}

Преимущество этого в том, что очистка тривиальна - просто позвоните free((char*)aList);, и все закончится. Но вы больше не можете realloc(), так как это не вставит новый пробел в начале блока памяти (где хранится aList[]).

Эти вещи являются действительно вескими причинами для использования векторов C ++; по крайней мере C ++ выполняет очистку (например, при исключениях нехватки памяти) автоматически.

Answer 4

Если ваш план заключается в заполнении при чтении файла, вы можете сделать одну из двух вещей.

Либо сохраните количество строк в качестве первого элемента в файле, тогда предложение jgottula будет работать хорошо.

Или вы должны использовать массив? Вы можете прочитать их непосредственно в связанный список, а затем, закончив чтение, переместить их в массив и освободить связанный список.

Answer 5

Ситуация, которую вы описали, это то, для чего malloc - выделение блока памяти переменной длины.

Answer 6

Вы можете динамически распределять массив:

char **aList;
int i;

aList = malloc(sizeof(char *) * numStrings);

for (i = 0; i < numStrings; i++)
{
    aList[i] = malloc(maxLength);
}

Если по какой-либо причине вы можете использовать C ++ вместо C, вы всегда можете использовать вектор C ++:

std::vector<std::vector<char> > aList;