Задолбал меня std::list, хочу свой список написать. Вот идеи по его устройству:
MyList *next; MyList *prev; T content;
тут next указывает на слудеющий элемент, prev — на прошлый. Держим указатель на текущий элемент. Добавление — malloc-ом выделяем память под новый элемент, инициализируем все егшо поля. Удаление — free на элемент, и сцепляем по next и prev соседние с ним элементы.
Фукнции о типу first, last, add_first, add_last, delete_first, delete_last, delete, empty, find — все это прилагается.
Как, нормально, или что-то я нерационально продумал?
Последние комментарии
-
OlegL, 17 декабря в 15:00 →
Перекличка
21
-
REDkiy, 8 июня 2023 года в 9:09 →
Как «замокать» файл для юниттеста в Python?
2
-
fhunter, 29 ноября 2022 года в 2:09 →
Проблема с NO_PUBKEY: как получить GPG-ключ и добавить его в базу apt?
6
-
Иванн, 9 апреля 2022 года в 8:31 →
Ассоциация РАСПО провела первое учредительное собрание
1
-
Kiri11.ADV1, 7 марта 2021 года в 12:01 →
Логи catalina.out в TomCat 9 в формате JSON
1
ecobeing.ru
Экология и вегетарианство на благо всем живым существам Планеты.
А что тут думать? List он и в Африке List!
То, что ты написал называется двухсвязанный список. По опредеоению list не имеет указателей на prev/next.
Добавлять интересно в середину списка. Надо разрывать связь между соседями и впердоливать новый элемент с правильными указателями туды и сюды… Я за это трояк получил на экзамене по программизму лет так дцать назад… Я принес кучу книг на экзамен, и сел на них. А меня пересадили, пришлось встать так, чтобы жопой смахнуть книги под парту (никто не заметил — сидение откидывающееся). И, лишенный источника знаний, я пролетел как фанера над Парижем… Как раз этот вопрос был — динамические списки в Паскале 360…
Good Luck,
UT
Не, мне тогда нужен двусвязный список.
Есь вот еще какое сомнение:
можно сделать бинарную вставку, тогда операция поиска в списке будет очень шустрая. Но есть два минуса:
1) Хранимый обьект должен иметь перегруженные операторы >=,<=.
2) Операция вставки занимает больше времени, чем просто добавление в конец/в начало.
Хотя я так подумал, лучше ввести какой-нить параметр шаблона типа bool, который указывает, бинарный или линейный алгоритм вставки/поиска. Т.к. мне в одном случае критична скорость поиска, а в другом — удаления и добавления.
да, я про это и говорю.
Интересно, сколько времени ты оттачивал умение листать страницы ягодицами и читать шоколадным глазом? По моему нереально с толстенных книг списывать. Я для таких дел юзаю шпоргалки-гармошки с отсканированным и уменьшенным текстом.
Реально списывать с чего угодно. Предмет моей особой гордости — экзамен по Алгебре, который я сдавал в кабинете профессора (после армии восстанавливался), один на один, сидя за его столом. Профессор сидел напротив и, не отрываясь, смотрел мне в глаза, а я при этом списывал с чужого конспекта, держа его на колене…
По Истории КПСС был у нас учебник, ласково называемый Кирпичем (за характерный цвет и массу в 2кг). Его проносили на экзамен в кармане, пришитом к внутренности пиджака. Одна девица уронила его на пол в процессе списывания. На вопрос препода, чтО здесь обрушилось, она смущенно ответила: «Промокашка упала…»
Эх, бля, молодость…
Америкосы приходят на экзамен в бейсбольных кепочках. На внутренность козырька они приклеивают шпаргалки. Или программируют калькуляторы. Я на всех тестах разрешаю пользоваться лекциями, ну его нафик…
Good Luck,
UT
гы, кирпич я и сам видел :)
Теперь по теме:
а что если мне вобще закольцевать список? Чем это черевато? Тогда нужно бдет держать тока указатель на текущий элемент (т.к. понятия «последний элемент» и «первый элемент» нету в принципе), и вставлять могу только после него. Хм, а это мысль :)
Дык, а как ты по нему лазить-то будешь? Так ты знаешь, если next == NULL, это конец списка, а если prev == NULL, то — начало. А здесь так и будешь по кругу ходить…
Good Luck,
UT
да без проблем! Сделаю элемент — затычку, у которого content = null. Он и будет концом списка :) А вставлять я буду перед текущим элементом.
Усложняешь… Вот и фальшивый элемент появился. А все ради чего? Вполне можно оптимизировать и бинарную вставку в список так, чтобы она не занимала много времени…
Good Luck,
UT
эх, вот что хначит, не сталкивался с логичесим программированием ;)
и эффективной работы со списками.
представим список в виде 2 ( ДВУХ ) указателей.
первый — указывает на начальный, первый элемент списка.
второй — указывает на последний элемент списка.
список — не важно какой, одно-, двусвязный.
операции добавления в начало, в конец — тривиальны.
Э, нет, батенька, так не выйдет… Ты хочешь, чтобы у всех элементов списка первый указатель был на первый элемент, а второй — на последний? А как же ты по нему бегать-то будешь? Как ты прочтешь содержимое второго элемента? На него ж ничего не указывает.
Надо так:
(NULL, content, &second), (&first, content, &third), … , (&next_to_last, content, NULL)
Сам список создается в программе одним элементом (переменной). К нему можно цеплять спереди или сзади. После добавления элемента, переменная указывает на текущий элемент, и её можно двигать.
Те списки, что в Лиспе, немного другие, но Лисп — язык высокого уровня, а разговор идет о низкоуровневой реализации высокоуровневых функций, так что функциональное программирование тут ни при чем.
Good Luck,
UT
нет. не хочу я этого говорить, что бы у всех элементов списка только и было, что указатель на первый и на последний элемент.. :)
списко пусть хоть одно-, хоть двусвязный будет
но, в функциях оперирования списком передавалась структура с двумя укзателями — на начальный и на конечный элемент списка.
А собстно, нафига? Дай ей, функции, текущий элемент, она сама найдет, где первый, где последний.
while(current->next != NULL)
{
current = *(current->next);
};
printf(«Found the last element! Aren’t I a doll?!\n»);
Good Luck,
UT
а то сам не знаешь, нафига.
с миллион элементов, и.. ;)) долго куколка твоя бегать будет.
Я тут почитал про списки и про реализацию и наткнулся на такую штуку как «Слоёный список».
Если тебе для быстрого поиска нужно для списка. Скорость поиска от O(lg(n)) до O(n).
см. http://algolist.manual.ru/ds/s_skl.php
Ладно, уговорили, кольцо нах, беру двунаправленный список, и пойнтер на первый/последний и текущий элемент.