nixp.ru v3.0

29 мая 2017,
понедельник,
10:35:07 MSK

DevOps с компанией «Флант»
Longobard написал 13 февраля 2005 года в 14:21 (409 просмотров) Ведет себя как мужчина; открыл 291 тему в форуме, оставил 2499 комментариев на сайте.

Задолбал меня 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 — все это прилагается.

Как, нормально, или что-то я нерационально продумал?

myst

А что тут думать? List он и в Африке List!

decvar

То, что ты написал называется двухсвязанный список. По опредеоению list не имеет указателей на prev/next.

Uncle Theodore

Добавлять интересно в середину списка. Надо разрывать связь между соседями и впердоливать новый элемент с правильными указателями туды и сюды… Я за это трояк получил на экзамене по программизму лет так дцать назад… Я принес кучу книг на экзамен, и сел на них. А меня пересадили, пришлось встать так, чтобы жопой смахнуть книги под парту (никто не заметил — сидение откидывающееся). И, лишенный источника знаний, я пролетел как фанера над Парижем… Как раз этот вопрос был — динамические списки в Паскале 360…

Good Luck,

UT

Longobard

Не, мне тогда нужен двусвязный список.

Есь вот еще какое сомнение:

можно сделать бинарную вставку, тогда операция поиска в списке будет очень шустрая. Но есть два минуса:

1) Хранимый обьект должен иметь перегруженные операторы >=,<=.

2) Операция вставки занимает больше времени, чем просто добавление в конец/в начало.

Хотя я так подумал, лучше ввести какой-нить параметр шаблона типа bool, который указывает, бинарный или линейный алгоритм вставки/поиска. Т.к. мне в одном случае критична скорость поиска, а в другом — удаления и добавления.

Longobard
Uncle Theodore
Добавлять интересно в середину списка. Надо разрывать связь между соседями и впердоливать новый элемент с правильными указателями туды и сюды…

да, я про это и говорю.

Я за это трояк получил на экзамене по программизму лет так дцать назад… Я принес кучу книг на экзамен, и сел на них. А меня пересадили, пришлось встать так, чтобы жопой смахнуть книги под парту (никто не заметил — сидение откидывающееся). И, лишенный источника знаний, я пролетел как фанера над Парижем… Как раз этот вопрос был — динамические списки в Паскале 360…

Интересно, сколько времени ты оттачивал умение листать страницы ягодицами и читать шоколадным глазом? По моему нереально с толстенных книг списывать. Я для таких дел юзаю шпоргалки-гармошки с отсканированным и уменьшенным текстом.

Uncle Theodore

Реально списывать с чего угодно. Предмет моей особой гордости — экзамен по Алгебре, который я сдавал в кабинете профессора (после армии восстанавливался), один на один, сидя за его столом. Профессор сидел напротив и, не отрываясь, смотрел мне в глаза, а я при этом списывал с чужого конспекта, держа его на колене…

По Истории КПСС был у нас учебник, ласково называемый Кирпичем (за характерный цвет и массу в 2кг). Его проносили на экзамен в кармане, пришитом к внутренности пиджака. Одна девица уронила его на пол в процессе списывания. На вопрос препода, чтО здесь обрушилось, она смущенно ответила: «Промокашка упала…»

Эх, бля, молодость…

Америкосы приходят на экзамен в бейсбольных кепочках. На внутренность козырька они приклеивают шпаргалки. Или программируют калькуляторы. Я на всех тестах разрешаю пользоваться лекциями, ну его нафик…

Good Luck,

UT

Longobard

гы, кирпич я и сам видел :)

Теперь по теме:

а что если мне вобще закольцевать список? Чем это черевато? Тогда нужно бдет держать тока указатель на текущий элемент (т.к. понятия «последний элемент» и «первый элемент» нету в принципе), и вставлять могу только после него. Хм, а это мысль :)

Uncle Theodore
LONGOBARD
а что если мне вобще закольцевать список? Чем это черевато? Тогда нужно бдет держать тока указатель на текущий элемент (т.к. понятия «последний элемент» и «первый элемент» нету в принципе), и вставлять могу только после него. Хм, а это мысль :)

Дык, а как ты по нему лазить-то будешь? Так ты знаешь, если next == NULL, это конец списка, а если prev == NULL, то — начало. А здесь так и будешь по кругу ходить…

Good Luck,

UT

Longobard
Uncle Theodore
Дык, а как ты по нему лазить-то будешь? Так ты знаешь, если next == NULL, это конец списка, а если prev == NULL, то — начало. А здесь так и будешь по кругу ходить…

Good Luck,

UT

да без проблем! Сделаю элемент — затычку, у которого content = null. Он и будет концом списка :) А вставлять я буду перед текущим элементом.

Uncle Theodore
LONGOBARD
да без проблем! Сделаю элемент — затычку, у которого content = null. Он и будет концом списка :) А вставлять я буду перед текущим элементом.

Усложняешь… Вот и фальшивый элемент появился. А все ради чего? Вполне можно оптимизировать и бинарную вставку в список так, чтобы она не занимала много времени…

Good Luck,

UT

Genie

эх, вот что хначит, не сталкивался с логичесим программированием ;)

и эффективной работы со списками.

представим список в виде 2 ( ДВУХ ) указателей.

первый — указывает на начальный, первый элемент списка.

второй — указывает на последний элемент списка.

список — не важно какой, одно-, двусвязный.

операции добавления в начало, в конец — тривиальны.

Uncle Theodore
Genie
эх, вот что хначит, не сталкивался с логичесим программированием ;)

и эффективной работы со списками.

представим список в виде 2 ( ДВУХ ) указателей.

первый — указывает на начальный, первый элемент списка.

второй — указывает на последний элемент списка.

список — не важно какой, одно-, двусвязный.

операции добавления в начало, в конец — тривиальны.

Э, нет, батенька, так не выйдет… Ты хочешь, чтобы у всех элементов списка первый указатель был на первый элемент, а второй — на последний? А как же ты по нему бегать-то будешь? Как ты прочтешь содержимое второго элемента? На него ж ничего не указывает.

Надо так:

(NULL, content, &second), (&first, content, &third), … , (&next_to_last, content, NULL)

Сам список создается в программе одним элементом (переменной). К нему можно цеплять спереди или сзади. После добавления элемента, переменная указывает на текущий элемент, и её можно двигать.

Те списки, что в Лиспе, немного другие, но Лисп — язык высокого уровня, а разговор идет о низкоуровневой реализации высокоуровневых функций, так что функциональное программирование тут ни при чем.

Good Luck,

UT

Genie
Э, нет, батенька, так не выйдет… Ты хочешь, чтобы у всех элементов списка первый указатель был на первый элемент, а второй — на последний? А как же ты по нему бегать-то будешь? Как ты прочтешь содержимое второго элемента? На него ж ничего не указывает.

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

списко пусть хоть одно-, хоть двусвязный будет

но, в функциях оперирования списком передавалась структура с двумя укзателями — на начальный и на конечный элемент списка.

Uncle Theodore
Genie
но, в функциях оперирования списком передавалась структура с двумя укзателями — на начальный и на конечный элемент списка.

А собстно, нафига? Дай ей, функции, текущий элемент, она сама найдет, где первый, где последний.

while(current->next != NULL)

{

current = *(current->next);

};

printf(«Found the last element! Aren’t I a doll?!\n»);

Good Luck,

UT

Genie
А собстно, нафига? Дай ей, функции, текущий элемент, она сама найдет, где первый, где последний.

а то сам не знаешь, нафига.

с миллион элементов, и.. ;)) долго куколка твоя бегать будет.

iliya

Я тут почитал про списки и про реализацию и наткнулся на такую штуку как «Слоёный список».

Если тебе для быстрого поиска нужно для списка. Скорость поиска от O(lg(n)) до O(n).

см. http://algolist.manual.ru/ds/s_skl.php

Longobard

Ладно, уговорили, кольцо нах, беру двунаправленный список, и пойнтер на первый/последний и текущий элемент.