C Vector / ArrayList / LinkedList

Question

Я делаю небольшую программу на C, и мне нужен какой-то вектор / ArrayList / LinkedList, но я работаю с C. Есть идеи, как я мог бы делать такие вещи в C?

Я хочу сохранить структуры, а затем добавить / удалить некоторые.

Answer 1

Использовать существующую реализацию. Есть миллиарды. Glib , вероятно, хорошее место для начала, или LibH .

Answer 2

Для массивов с изменяемыми размерами вы можете использовать malloc() и realloc(). Это позволяет вам зарезервировать (с malloc()) и изменить размер (с realloc()) определенного объема пространства в куче. Они используются так:

int* a = malloc(10 * sizeof(int));

if(a == NULL) {}     // malloc() was unable to allocate the memory, handle the
                     // error and DO NOT use this pointer anymore

// now you can treat a as a normal array of 10 ints:
a[4] = 51;

// suppose 10 ints aren't no more enough:
a = realloc(a, 20 * sizeof(int));

if(a == NULL) {}     // same thing as before

// here you have 20 ints, the previous 10 are still there
a[18] = a[4]

// don't forget to free the memory when you have finished:
free(a);

Просто замените int на ваш тип структуры. ;)

Answer 3

Я использовал ответ @ Конрада Мейера.Скачал последнюю библиотеку Glib с здесь и скомпилировал ее, используя это руководство.Для тестирования библиотек Glib я использовал этот тест.У вас могут быть ошибки при компиляции тестового кода. Это поможет вам решить вашу проблему.

Также я обнаружил, что в тестовом коде есть какая-то утечка памяти. Valgrind результат выполнения оригинального кода:

==20350== HEAP SUMMARY:
==20350==     in use at exit: 4,632 bytes in 12 blocks
==20350==   total heap usage: 12 allocs, 0 frees, 4,632 bytes allocated
==20350== 
==20350== LEAK SUMMARY:
==20350==    definitely lost: 0 bytes in 0 blocks
==20350==    indirectly lost: 0 bytes in 0 blocks
==20350==      possibly lost: 992 bytes in 4 blocks
==20350==    still reachable: 3,640 bytes in 8 blocks
==20350==         suppressed: 0 bytes in 0 blocks

Итак, я вставил одну строку в код:

#include <stdio.h>
#include <glib.h>

int main(int argc, char** argv) {
    GList* list = NULL;
    list = g_list_append(list, "Hello world!");
    printf("The first item is '%s'\n", (char *)g_list_first(list)->data);
    g_list_free(list);
    return 0;
}

Valgrind новые результаты:

==20310== HEAP SUMMARY:
==20310==     in use at exit: 4,632 bytes in 12 blocks
==20310==   total heap usage: 12 allocs, 0 frees, 4,632 bytes allocated
==20310== 
==20310== LEAK SUMMARY:
==20310==    definitely lost: 0 bytes in 0 blocks
==20310==    indirectly lost: 0 bytes in 0 blocks
==20310==      possibly lost: 0 bytes in 0 blocks
==20310==    still reachable: 4,632 bytes in 12 blocks
==20310==         suppressed: 0 bytes in 0 blocks

Этот ответ говорит о том, что нет необходимости беспокоиться о still reachable памяти.

Answer 4

C не поставляется в какой-либо форме стандартной коллекции (в отличие от языков более высокого уровня, таких как C ++ и Java), поэтому у вас остается несколько вариантов:

1. Использовать уже созданный созданныйкакой-то группой / каким-то отдельным человеком (как упомянуто выше)
2. Создайте свой собственный

Вам нужно будет подумать, что именно нужно для этой программы, чтобы определить, что вы используете.Из того, что вы просите, вы, вероятно, ищете один из двух вариантов:

1. Массив, который будет динамически увеличиваться при выделении.По сути, вам нужно указать, сколько элементов содержится в вашем массиве на данный момент.Если в какой-то момент во время вставки вы превысили максимальное количество элементов, вы должны создать новый массив, скопировать элементы в новый массив, вставить новый элемент и, наконец, удалить старый массив.Это имеет тенденцию быть более быстрым с точки зрения времени доступа (так как оно индексируется), но медленным и занимать память, если вы перераспределяете.См. Пример кода BlackBear.
2. Связанный список, который динамически увеличивается в зависимости от дизайна.См. Здесь: http://en.wikipedia.org/wiki/Linked_list#Singly-.2C_doubly-.2C_and_multiply-linked_lists. Это имеет главное преимущество, заключающееся в отсутствии дополнительного обслуживания в особом случае, но недостаток медленного доступа (смотрите на каждый элемент, пока не найдете нужный элемент).

См. Страницу Википедии для получения дополнительной информации о компромиссах между двумя типами структур данных.