struct Store {
char info;
Store *next;
}
void set(Store *store, char info) {
Store tmp = new Store();
tmp->info = info;
tmp->next = store;
store = tmp;
}
char get(Store *store) {
char info = store->info;
Store tmp = store;
store = store->next;
delete tmp;
return info;
}
обсуждение двухсвязнного списка порядка LIFO
Цитата: OlgaKr
ничего не получается, просто логика стэка осуществляется при помощи списка.
если я работаю со стеком то сначала делаю техн часть вопроса (про беру:p )
а при решении конкретной задачи уже не думаю как реализован стек а просто им пользуюсь через парочку описаных функций
в общем мы отвлеклись от темы:)
ps про lifo это у меня склероз)))) там last конечно
pps а стек можно и без двухсвязного...
зачем хранить столько никому не нужных ссылок
А зачем нужен вообще двусвязный список?
Как сейчас помню, на 1 курсе нас заставляли стек организовывать с помощью односвязного списка, чтобы сэкономить память.
Предлагаю так.
Как сейчас помню, на 1 курсе нас заставляли стек организовывать с помощью односвязного списка, чтобы сэкономить память.
Код:
Предлагаю так.
Не знаю, это прихоть препода)))так что тут уже никуда не денешься...За пример спасибо..
Цитата: WandM
А зачем нужен вообще двусвязный список?
Зачем нужно его давать на экзамене, или зачем нужна в программировании эта структура?
Цитата: Zorkus
Зачем нужно его давать на экзамене, или зачем нужна в программировании эта структура?
зачем он нужен для стека я думаю имелось ввиду
вообще говоря для реализации стека он не нужен:)
хватит и однонаправленного
Цитата:
Зачем нужно его давать на экзамене, или зачем нужна в программировании эта структура?
Для решения данной задачи :).
Цитата: WandM
Для решения данной задачи :).
Имхо, хороший препод не ограничивает студента в выборе инструмента. Пусть говорит, что делать, а уж как - это без него разберемся, а вот если не сумеем - тогда и спросим (самый типичный в нашем универе пример - это когда требуют написать диалоговое приложение строго на WinAPI, и ругаются, что работаем медленно:)).
2OlgaKr - а почему не рекомендуешь Шилдта? Мне кажется, вполне приличный базовый курс.
Цитата: Zorkus
Имхо, хороший препод не ограничивает студента в выборе инструмента.
ну это уже зависит от поставленной задачи
[QUOTE=Zorkus]А зачем нужен вообще двусвязный список?Зачем нужно его давать на экзамене, или зачем нужна в программировании эта структура? [/QUOTE]
Двусвязные списки нужны для того, чтобы иметь возможность удалять элемент списка не только концов, но и из середины.А сами двусвязные списки используються например для реализации разряженых матриц в виде триплетов.
Двусвязные списки нужны для того, чтобы иметь возможность удалять элемент списка не только концов, но и из середины.А сами двусвязные списки используються например для реализации разряженых матриц в виде триплетов.
[QUOTE='Frosty;164317']Двусвязные списки нужны для того, чтобы иметь возможность удалять элемент списка не только концов, но и из середины.[/QUOTE]
а кто вам мешает удалять из середины однонаправленного? )
не нужно говорить что удобнее и тп
зависит от конкретной задачи
а кто вам мешает удалять из середины однонаправленного? )
не нужно говорить что удобнее и тп
зависит от конкретной задачи
[QUOTE=nilbog]а кто вам мешает удалять из середины однонаправленного? )[/QUOTE]
Однонаправленный список для этого не предназначен просто).
З.Ы. Насчет невозможно я погарячился конечно, но то, что это неоправдано то точно)
Однонаправленный список для этого не предназначен просто).
З.Ы. Насчет невозможно я погарячился конечно, но то, что это неоправдано то точно)
Цитата: nilbog
а кто вам мешает удалять из середины однонаправленного? )
не нужно говорить что удобнее и тп
зависит от конкретной задачи
не нужно говорить что удобнее и тп
зависит от конкретной задачи
Да, это зависит от задачи. От задачи реализации стека. Так как одно из основных свойств списка - это быстрый поиск нужного элемента, то в этом случае удобнее использовать двусвязный списк. Именно удобнее. Удобнее тем, что проходить список можно с любого конца. Это, в отличии от односвязного, у которого обнаруживается линейная зависимость времени поиска от размера T(n) = n, дает определенный выигрыш в скорости.
Некоторые реализации двусвязных списков, содержат указатель не только на первый и последний элементы, но и на средний, тем самым еще более уменьшая время нахождения нужного элемента. Можно использовать двусвязные кольцевые списки с плавающим окном. Тут уже имеют смысл "статистические данные" обращения к списку.
[QUOTE=Lerkin]Так как одно из основных свойств списка - это быстрый поиск нужного элемента, то в этом случае удобнее использовать двусвязный списк. [/QUOTE]
Если и нужен быстрый поиск, то уж использовать двусвязные списки я не буду. В любом случае порядок будет n, обусловленный последовательным доступом.
А мне бы хотелось log(n).
[QUOTE=Lerkin]Удобнее тем, что проходить список можно с любого конца. Это, в отличии от односвязного, у которого обнаруживается линейная зависимость времени поиска от размера T(n) = n, дает определенный выигрыш в скорости.[/QUOTE]Неа.)
Вот такой список при поиске по ключу 46, ты наверное на базе анализа концевых элементов решишь искать с головы(45) и те придеться весь список просматреть и никакого выигрыша.
45 45,1 45,2 45,3 45,4 45,5 46 30
Если и нужен быстрый поиск, то уж использовать двусвязные списки я не буду. В любом случае порядок будет n, обусловленный последовательным доступом.
А мне бы хотелось log(n).
[QUOTE=Lerkin]Удобнее тем, что проходить список можно с любого конца. Это, в отличии от односвязного, у которого обнаруживается линейная зависимость времени поиска от размера T(n) = n, дает определенный выигрыш в скорости.[/QUOTE]Неа.)
Вот такой список при поиске по ключу 46, ты наверное на базе анализа концевых элементов решишь искать с головы(45) и те придеться весь список просматреть и никакого выигрыша.
45 45,1 45,2 45,3 45,4 45,5 46 30
[QUOTE='Frosty;164467']
А мне бы хотелось log(n).
[/QUOTE]
эт врядли получится так просто
хотябы 1.45log(n)
и то это то тяжеловато получить
А мне бы хотелось log(n).
[/QUOTE]
эт врядли получится так просто
хотябы 1.45log(n)
и то это то тяжеловато получить
Тогда b-tree использовать. Но проигрыш по скорости будет в добавлении элементов.
[QUOTE=nilbog]эт врядли получится так просто
хотябы 1.45log(n)
и то это то тяжеловато получить[/QUOTE]
Бинарный поиск.
Поиск делением пополам.
Смысл один в основе бинарное дерево.
хотябы 1.45log(n)
и то это то тяжеловато получить[/QUOTE]
Бинарный поиск.
Поиск делением пополам.
Смысл один в основе бинарное дерево.
2Lerkin не думаю что это так критично
я могу ошибаться и забыть но оценка log(n+1) будет для совершенного дерева ( а его вы не из любого кол-ва вершин построите)
а если брать авл дерево то там будет около 1.4log(n) сложность
вставка сложнее но искать быстро :)
ps а вообще к списку и стеку это все отношения не имеет
а если брать авл дерево то там будет около 1.4log(n) сложность
вставка сложнее но искать быстро :)
ps а вообще к списку и стеку это все отношения не имеет
Точно. Локанично и правда.
Цитата: nilbog
...
ps а вообще к списку и стеку это все отношения не имеет
ps а вообще к списку и стеку это все отношения не имеет
Краткий списочек структур данных. :)
Насчет идеального дерева - для идеализации существует балансировка. Красно-черное дерево, например. Если нужна структрура с минимальным временем поиска - используйте хэш-таблицу.