Динамический список в ANSI C?

Question

Прав ли я, думая, что единственный способ создать список, который увеличивается во время выполнения в C, это использовать связанный список?

Answer 1

Вы можете использовать комбинацию malloc и realloc. Сначала инициализировать массив C (malloc) и увеличить его (realloc). Однако вам не захочется увеличивать его на 1 элемент за раз, если вы делаете много вставок. Лучше всего разработать схему, позволяющую увеличивать список по мере необходимости (т.е. добавлять 10 элементов каждый раз, когда размер списка достигает выделенного размера).

Answer 2

Связанный список является одним из способов. Он имеет O(1) вставку (если вы уже находитесь в точке вставки) и удаление, но O(n) n поиск элементов.

Изменение размера динамически распределенного массива с помощью malloc - другое. Он имеет O(1) n поиск элементов, но вставка O(n) (из-за необходимости копировать все более поздние элементы после точки вставки и, возможно, все элементы в realloc) и удаление.

Если вы действительно беспокоитесь о производительности обеих этих операций, я бы выбрал какую-то самобалансирующуюся древовидную структуру. Вы можете, конечно, достичь O(log n) для поиска, вставки и удаления. И для всех практических целей, если объекты находятся в основной памяти, log n ограничен 32 или 64 и O(log n) может также быть O(1).

Answer 3

взгляните на utlist и utarray . utlist - это в основном связанный список, а utarray - макрос malloc / realloc. Вы можете легко сделать их встроенными функциями.

Answer 4

Я составил список, используя malloc и realloc, которые могут динамически расти. У меня нет самого последнего кода, доступного в данный момент, но вот некоторый (неполный, но функциональный) код, который я написал некоторое время назад для управления динамическими, универсальными списками в C.

#include<stdbool.h>

struct empty_list_key{
    int offest;
    struct empty_list_key* next;
};

typedef struct list_t{
    int CURRENT_POSITION; //position of the array cursor.
    int BLOCK_SIZE; //size of data type
    int SIZE;
    void** data;
    struct empty_list_key* empty_keys;
}list_t;

list_t* init_list(int size, int blocksize){
    if(size < 0){
        return NULL;
    }
    list_t *list = malloc(sizeof(list_t));
    if(list == NULL){
        return NULL;
    }
    list->CURRENT_POSITION = 0;
    list->BLOCK_SIZE = blocksize;
    list->SIZE = size;
    list->data = malloc(sizeof(void*) * size);
    if(list->data == NULL){
        free(list);
        return NULL;
    }
    if(size > 0){
        int i;
        struct empty_list_key* empty_key;
        empty_key = malloc(sizeof(struct empty_list_key));
        //TODO: Check for NULL. If NULL, cleanup everything and return.
        empty_key->offest = 0;
        if(size > 1){
            for(i = 1; i < size; i++){
                empty_key->next = malloc(sizeof(struct empty_list_key));
                //TODO: Check for NULL. If NULL, cleanup everything and return.
                empty_key = empty_key->next;
                empty_key->offest = i;
            }
        }
    }else{
        list->empty_keys = NULL;
    }
    return list;
}

void delete_list(list_t* list){
    free(list->data);
    free(list);
}

bool list_set(list_t* list, int pos, void* value){
    if(pos < list->SIZE && pos >= 0){
        list->data[pos] = value;
        return true;
    }else{
        return false;
    }
}
bool list_unset(list_t* list, int pos){
    if(pos < list->SIZE && pos >= 0){
        free(list->data[sizeof(void*) * pos]);
        list->data[pos] = NULL;
        struct empty_list_key* empty_key = malloc(sizeof(struct empty_list_key));
        if(empty_key == NULL){
            return false;
        }

        //insert empty key at beginning of empty keys linked list.
        empty_key->offest = pos;
        empty_key->next = list->empty_keys;
        list->empty_keys = empty_key;
        return true;
    }else{
        return false;
    }
}

void* list_get(list_t* list, int pos){
    if(pos < list->SIZE && pos >= 0){
        return list->data[pos];
    }else{
        return NULL;
    }
}

bool list_push(list_t* list,void* value){
    void** tmp = realloc(list->data,(sizeof(void*) * list->SIZE) + sizeof(void*));
    if(tmp == NULL){
        return false;
    }else{
        list->data = tmp;
        list->SIZE ++;
        list_set(list,list->SIZE-1,value);
        return true;
    }
}

void* list_pop(list_t* list){
    void* value = list_get(list,list->SIZE-1);
    void** tmp = realloc(list->data,(sizeof(void*) * (list->SIZE ) ));
    if(tmp == NULL){
        return NULL;
    }else{
        list->SIZE --;
        list->data = tmp;
        return value;
    }
}

int list_size(list_t* list){
    return list->SIZE;
}

bool list_add(list_t* list, void* value){
    if(list->empty_keys == NULL){
        return list_push(list,value);
    }else{
        int offset = list->empty_keys->offest;
        struct empty_list_key* empty_key = list->empty_keys->next;
        free(list->empty_keys);
        list->empty_keys = empty_key;
        return list_set(list,offset,value);
    }
}

bool list_remove(list_t* list, int pos){
    struct empty_list_key* empty_key = malloc(sizeof(struct empty_list_key));
    if(empty_key == NULL)   return false;

    if(list_unset(list,pos)){
        empty_key->offest = pos;
        empty_key->next = list->empty_keys;
        list->empty_keys = empty_key;
        return true;
    }else{
        return false;
    }
}