Что такое списки вообще и в частности стеки, очереди, деки я понимаю. Но вот что-то не найду определения - что такое сегментированные списки и как с ними работать. В разных статьях по динамическим структурам ничего не встречается. Предположу только что в отличие от так сказать традиционных списков в сегментированных память выделяется/освобождается не для отдельных узлов списка, а сразу под целый "сегмент", в котором будут несколько узлов. А как тогда узлы располагаются внутри сегмента?Также каждый узел хранит указатель на соседний или просто без указателей, как массив? А как тогда добавлять/удалять первый узел в сегменте, если весь сегмент заполнен?
Это смесь массива со связанным списком. Пример: выделяем страницу (4096 байт) под массив указателей - 1024 указателя получится. Используем только 1023 указателя, а последний указатель укажет на следующую такую страницу из 1024 указателей. Конечно, будут нужны некоторые сервисные переменные: сколько указателей занято, чтобы можно было удалять и видеть когда нужен следующий сегмент. Недостатки: трудно делать бинарный поиск - он требует линейности массива.
А как в таком случае добавлять элемент в начало списка, если в первой странице занят первый указатель?
Не получится, наверное... такие списки годятся только для не сортированных элементов. Кстати, чтобы избежать дефрагментации и больших затрат памяти, можно использовать простой стандартный связный список. Только для выделения элементов списка использовать сегменты. Например, выделить сразу 1024 узла списка одним куском памяти, и потом брать из этого сегмента узлы и присоединять к списку или отсоединять от него. Не хватает узлов - ещё 1024 выделить.
Ну и для добавления элемента в начало списка можно найти решение, например, аполнять списко не всесь сразу, но допустим на 75%, и добавлять нужный элемент, сдвигая списко на 1 или несколько позиций!
> аполнять списко не всесь сразу, но допустим на 75% Нах? Выделяем еще одну ноду, в последний ее элемент сохраняем что хотели, ставим новую ноду как корень, и связываем ее с оригинальным корнем.
У меня есть два класса Heap и List (их писал другой человек). Я пытаюсь разобраться на их основе что собственно представляют эти сегментированные списки. Пока что общей картины для чего нужны все эти структуры и переменные мне не понятно. Heap - отвечает за все выделение памяти сегментами. List - сегментированный список должен быть. List осуществляет обычные функции - добавление элемента, удаление элемента с начала, удаление с конца. Память List берет только через функции Heap. List будет служить как базовый класс, на его основе потом можно создавать разные списки. Так вот как я пока понимаю всю работу. При инициализации List создается объект класса Heap, который по умолчанию создает один сегмент размером 64 кб Допустим я буду добавлять элементы следующего вида в список: struct article { char * word; char * desc; }; Метод add списка вызывает get_mem из Heap для получения памяти. Heap выделяет ее из сегмента. Т.е. из тех 64 кб что выделили для начала. Мне непонятна схема как будут размещаться элементы вот в этом Heap. Должны ли элементы указывать друг на друга? И вообще память под строки word и desc тоже берется из того же сегмента что и под сами элементы? Далее идут сами файлы. Код (Text): //----------------------------------------------------------- // HEAP.H // #define SEGMENTSIZE 65539 #define SEGMENTCOUNT 1024 class Heap { public: Heap(int _segment_size = SEGMENTSIZE); { segment_size = _segment_size; current = 0; } ~Heap() { delete_segments(); } void* get_mem(int size); void free_mem (void *); private: struct Segment_def { bool used; int size; void* offset; }; struct Segment { void* data; Segment* prev; Segment_def[SEGMENTCOUNT] descriptor; int descriptor_count; }; int make_segment(); void delete_segments(); int segment_size; segment* current; }; //----------------------------------------------------------- // LIST.H // #include "heap.h" #define LISTSIZE 64 class List { public: List(int _element_size, int _element_count = LISTSIZE); ~List(); void* get(int pos); void add(void* data); // returns and deletes elements void take_first(void* store); void take_last(void* store); void take(int pos, void* store); int count(); bool error(); { return error; } // true if error in last operation private: struct Segment { void* data; Segment* prev; Segment* next; }; Segment* first; Segment* last; int first_index; int last_index; int element_size; int element_count; bool error; void new_segment(); void delete_segment(Segment* seg); }; //-----------------------------------------------------------
