Динамические структуры данных на Си: Введение. Список — простой вариант

[RekGRpth]

есть же стандартные списки на макросах https://man7.org/linux/man-pages/man7/queue.7.html

[dio4]

Я вам больше скажу что давно есть glib где есть все ))

[serg_meus]

Что? Вставка и удаление в список с поиском по элементам каждый раз? Вообще-то списки полезны тем, что можно всавлять и удалять элементы за константное время, а также перебрасывать элементы из одного списка в другой за константное время без аллокаций. У вас получился гибрид с корнями помидора и ботвой картофеля.

[HADGEHOGs]

Ну а как ты место вставки найдешь? У автора - вставка по индексу, что в принципе, бессмысленно. Автор как бэ задумывает упорядоченный индексный список, что бред само по себе.

[serg_meus]

Место вставки можно найти по указателю на элемент, после или перед которым нужно вставить. Авторский способ тоже имеет право на жизнь, он более безопасный (указатель может указывать на не пойми что, а индекс легко проверитъ), зато даёт доступ за O(N) вместо O(1).

[HADGEHOGs]

" Место вставки можно найти по указателю на элемент "

Как найти указатель на элемент?

[serg_meus]

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

[motoroller95]

Похоже на лабораторную студента, который не разобрался. В самом начале хорошая затравка на

решение будет ориентированно и оптимизировано на работу с большим объемом данных

а потом, как уже отметили выше, вставка/удаление за O(N), а так же в db_read вместо того чтобы просто отдать указатель на элемент его предварительно копируют в новый участок памяти. А что если мне изменить данные надо? read + delete + insert? окей, есть еще get_element но выглядит она как приватная. однако толку от нее 0, потому что все равно все работает через индексы. db_search ну отдайте вы указатель если нашли, но нет, сначала достаем индекс а потом то что уже выше писал.

Следующая статья: Динамические структуры данных на Си: Список - Продвинутая версия

вот бы базовую версию увидеть

[cyrox007]

Вы верно подметили, тогда я еще не понимал этих проблем. Что касается get_element, это не приватная функция. По сути, как я уже позже понял, я мог бы ее использовать и отдельно, получая элемент, делать с ним, что нужно, будь-то получение данных из него или удаление и тд. Но эту задачу я отдал на откуп двум специализированным функциям, избавив себя, тем самым, от копипасты.
Что касается изменение данных в элементе, ну такой задачи не предполагалось, хотя ее вполне можно было бы и реализовать, не отрицаю.
По вопросу копирования: я в функции db_read не копирую сам элемент, а копирую данные, хранящиеся в этом элементе.

[HADGEHOGs]

Это уныло.

Генерация списка - ну сгенерируйте 1000 элементов махом, выделив память под 1000*sizeof(TElement), потом пользуйтесь свободными. Ну и не генерят такие списки в продакшене, динамическая загрузка с диска.

Поиск - ну создавайте отсортированный список вставками в нужное место. Нужное место ищите бисекцией (кластерный индекс, короче). Или создайте B+ дерево поиска в дополнении к списку, в листах которого будут указатели на элементы списка.

Но все это уже есть.

Есть, есть, есть.

TList

TMap

[alex103]

А что не уныло?? (очередной чатбот для телеграмы?)

Ждём ваш список ( хм.. опять список???).. ))

[HADGEHOGs]

Ну, не уныло реализовать концепцию кластерного индекса, некластерного на b+ дереве, да еще со страницами данных на диски и их динамической загрузки и выгрузки.

Потом hash и merge join -ы.

Потом накопление статистики для выбора hash, nested или merge.

Вот это годно...

[JordanCpp]

Пропущены функции append и prepend, Сложность O(N), это сама суть использования списка. Что бы бороться с фрагментацией и кеш мисом, выделять память блоком, после чего из данного блока конструировать елементы списка. Вы как раз юзаете двухсвязный список. Тема конечно не раскрыта. Как то коцано подано. Списки реализованы в glibc, там и сортировка есть. На примере можно было прокомментировать код. Как раз из таких маленьких кирпичиков, и состоят программы. Списки, хеш таблицы и деревья.