Примеры применений структур данных

[eugrita]

Тема вопроса: в помощь изучающим программирование
пояснить на конкретных примерах классов задач
применение к ним конкретных структур данных
как-то: cписков, очередей, деков, стеков,
деревьев , графов.
Если с деревьями и графами классы достаточно обширны
(графы - транспортны задачи, сетевые, марковские процессы и пр)
деревья (деревья синтаксического разбора, классификационные и пр)
то в отношении cписков, очередей, деков, стеков у меня несмотря на основательное
изучение в течение неск лет осталось неясность (видимо и у других тоже).
Ну хорошо, по-моему самой ходовой структурой из этих является стек.
Типовая задача: построение калькулятора разного уровня сложности
 (выражения со скобками, без скобок с/без функций) - основа алгоритм Дейкстры использующий стек.
То по поводу самого списка и его частных случаев - дек, очередь все спорно.
1)список или массив? (и то и другое свои преимущества и недостатки)
(обычно аргумент в динамический массив сложнее вставлять, зато легче доступ по индексу, в списки- наоборот.
Есть и 2 концепции реализации списка а)на базе указателя на член данных
б) как массив .
Людям изучающим программирование и информатику все таки неясно:
1) когда массив, когда список? Возможны оба варианта
2) в отношении очередей и деков - не вижу класса задач где удобно применять именно
эти а не другие структуры.
Ну очередь queue -только может при имитационном моделировании систем массового обслуживания (СМО)
 но и это достаточно специальный класс задая.
Нет чтоб как в математике: понятие, например интеграл и дифф.ур. применяется
практически в любой науке - физика, экономика, химия и пр.
Помогите с примерами пожалуйста.

[Sla]

хотел написать... даже написал... плюнул...
На безграмотно и не аккуратно написанный пост, не хочется отвечать.
Ведь вопрос требует осуждения, а что имеем на самом деле? Брошенная в сторону фраза с набором "специальных" терминов - стек, дек, очередь, граф.
Упоминание Дейсктра - к чему?

[Dimka]

Ничего не понял. Выбор структур определяется вовсе не классом задач, а классом методов решения задач.

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

И уж тем более не существует в математике классов задач типа "задачи, решаемые при помощи деревьев", классификация обычно строится по проблемам.

[eugrita]

Еще раз. Понимаю конечно, что есть альтернативные подходы к реализации алгоритма -
как-то со список / динамический массив .
Понимаю, что все изучавшие программирование серьезно в свое время проходили через школу типа
"сделай ручками список или стек или еще что" на примере конкретной задачи, например связать какую-то структуру в список , может и классы такие писали. Я тоже это делал
Таких людей я уважаю, только задачи на компьютерных практикумах обычно фиговые.
Например  типовая задача "база данных" студентов - массив структур реализовать в виде списка.
Сам реализовал, да только не могу себя убедить, а на фига список, когда с обычным динамическим массивом изящнее. Ну можно скидку на отсутствие поддержки STL в Pascal, Object Pascal, C
Но понимаю и других "белоручек", которым начхать на внутренние изучение структур типа список,
зато они работают на С++ в любой реализации, а там поддержка STL
и тот же самый список над которым потел реализатор БД студентов с STL делается буквально в 1 оператор
struct Stud {
             };
vector <stud > p, wS; //вот вам и динамический массив с доступом по индексу, т.е проще чем список
p.push_back(wS);// вставка в конец для стека
 p.Insert(i);//вставка в середину для списка
p.Remove(i);//удаление
извините, может синтаксис неточен, не в этом суть

Возникает иллюзия: а на фига все эти структуры данных если все так просто
"Выбор структур данных определяется не задачей а методом решения".
Конечно, любую задачу можно решать  разными методами - это не математика, где зачастую 1 метод. Но все таки, можно ли попытаться в выборе структур данных исходить не от метода,
а от задачи, навязывающей метод. т.е. я хочу если возможно получить
Пример конкретной  типовой задачи, понятной и школьникам  матем. школы, где алгоритм решения серьезно проще если основан на списке очереди  деке.
Т.е. задачи, где выбор технологии реализации - не прихоть программиста, а определяется спецификой задачи. (пусть даже это задача на нейросеть)
Кроме калькулятора я ничего не могу привести в пример.
Этот мой вопрос,  риторический и адресован скорее не программистам, а постановщикам задач с математической культурой и кругозором. Хотя конечно задачи решаемые программистами шире и не всегда в основе имеют математическую модель

[resource]

Конечно, любую задачу можно решать  разными методами - это не математика, где зачастую 1 метод. Но все таки, можно ли попытаться в выборе структур данных исходить не от метода, а от задачи.

Помоему эти два предложения явно противоречат друг другу. Да и если честно всё это выглядит крайне несуразно.

Лично мне это представляется примерно такой ситуацией. Надо мне попасть в другой город. Мне неминуемо придется сначала определиться насчет вида транспорта (то что здесь упоминается как метод). Например на поезде или на машие, а может вообще пешком. А уже потом покупать либо билет на поезд, либо бензин для авто, либо просто взять сухарей и одеть обувь полегче. Само по себе, то обстоятельство, что мне нужно переместиться в пространстве, никоим образом не даёт однозначного ответа на то, что мне для этого нужно, до тех пор пока я не выбиру способ/метод.

[eugrita]

В качестве конкретного алгоритма инициируемого задачей еще раз упомяну известный алгоритм Дейкстры
Разбор арифметического выражения:
Алг1. Вычисление арифметического выражения в постфиксной (польской) записи - использует стек и только стек.
(попробуйте именно эту задачу решать другим путем - если и решите - то на порядок сложнее. Недаром в промышленных калькуляторах используется аппаратно-реализованный стек.
Точно так же как разновидность
Алг.2 Преобразование арифметического выражения из обычной в польскую запись тоже - использует стек и только стек.
Точно так же
Алг.3 Одновременное преобразование вводимого в потоке арифметического выражения с одновременным преобразованием в польскую запись и вычислением результата (объединение Алг1. и Алг.2) использует 2 стека.
Вот вам пример такой всем понятной даже непрограммистам задачи. Сама задача - навязывает алгоритм решения с выбором стека.
Еще примеры будут???

[resource]

Алг.2 Преобразование арифметического выражения из обычной в польскую запись тоже - использует стек и только стек.

Это кто такое сказал? Где это написано?

[RXL]

Я бы сказал, что в разборе выражения больше подходит дерево. А стек к польской записи применим с другой стороны: сея запись заточена под стековую машину.

[resource]

Асолютно согласен с предыдущим оратором. Если перейти от голимой теории и полнейшей абстракции на уровень реального кода, то для реализации дерева имхо самой простой структурой в данном случае является многосвязный спискок. Это если конечно всё выражение должно храниться в памяти (возможно для каких-то манипуляций). А если нужно только вывести выражение на экран, то вообще ничего этого не надо, можно обойтись несколькими обычными переменными.

[Dimka]

Подтверждаю, что для разбора инфиксной записи используется дерево, а вычисление осуществляется обходом дерева в глубину. Список - это вырожденное дерево, состоящее из 1 ветви, а прохождение стека - это обход такого вырожденного дерева в глубину.

[resource]

Список - это вырожденное дерево, состоящее из 1 ветви

Ну если список многосвязный, то я так понимаю, что ветвей уже может быть сколько угодно

[Вад]

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

Под конкретной постановкой я имею в виду дополнительные ограничения, которые диктуют использование тех или иных структур. Это могут быть ограничения по ресурсам или требование "наиболее очевидного" (т.е. наиболее естественной структуры для представления тех или иных данных).

[Sla]

Господа отвечающие!
Я попрошу топикстартера оформить свой вопрос корректно, без лишних слов, аккуратно и с описанием существующей для него (топикстартера) проблемы дабы отделить бота от человека.

[eugrita]

Да. моя цель  - придумать задачи для школьников, чтобы там структуры данных были не с потолка взяты, а реально являлись наиболее эффективными при решении задачи в конкретной постановке. При этом  еще в качестве основного критерия выбора способа реализации алгоритма была  не личная прихоть программиста, а скажем оптимизация алгоритма по скорости или числу операций.
Тогда сразу ясно, что алгоритмы использующие много операций вставок/удаления в середину массива выгодней реализовать списком с указателями. А алгоритмы, в которых много выборок из разных мест (много обращений к массиву) по сравнению с операциями вставок/удаления в середину - те лучше динамическими массивами.
Да еще чтоб  при этом задачи являлись не надуманными упражнениями, как сплошь и рядом мы видим в практикумах, а по-возможности типовыми алгоритмами, используемыми в практике.

[Алексей++]

Тогда сразу ясно, что алгоритмы использующие много операций вставок/удаления в середину массива выгодней реализовать списком с указателями.

ну так прямо утверждать тоже нельзя, зависит от многого. Например, в std::vector (или в простом массиве с простыми элементами, которые можно побайтово копировать) вставка в середину даже проще, чем в список, но, конечно, выполнится заметно дольше, если объём данных велик. Зато сам массив займёт гораздо меньше памяти, чем список.
Всё это ИМХО выбирается на основе поставленной задачи и опыта - ничего универсального тут не придумаешь

Нужно рассказать школьникам о существующих типах массивов/контейнеров, затем расказать о их плюсах и минусах - чтобы было представление о последствиях выбора хранилища данных. Дальше всё зависит от учеников - либо они будут понимать, как это использовать и в какой ситуации, и к чему это приведёт, либо нет. А решение задач - это лишь "набивка" руки

[Антон (LogRus)]

Алексей1153++, поддерживаю. Что касается фразы которая тебя смутила, то я продолжу.

eugrita, цитата приведённая Алексеем показывает, что вы сами не до конца понимаете, чем придётся заплатить при выборе списка для данной конкретной задачи.
Список - это отсутствие быстрого доступа к элементам (доступа по индексу), последствия: лучше не сортировать и не искать. Естественно может быть список вам и пригодится, лично мне он пригодился всего пару раз, и то я добавлял/удалял элементы в конце/начале списка.
Думаю следует вас отправить к первоисточникам, т.е. Скотт Мейерс "Эффективное использование STL"

теперь конкретная задача:
1. 2*10^6 элементов, по 200 байт каждый. итого: примерно 400 мегабайт данных
2. необходимо производить быстрый поиск по различным критериям
3. периодически появляются новые элементы
4. старые элементы не удаляются
5. запрещено использовать контейнеры чувствительные к фрагментации памяти
6. запрещено перестраивать индексы

Внимание, вопрос: какие контейнеры вы будете использовать при реализации задачи (правда мне кажется пункты 4-6 слишком упростили задачу, ну да хрен с ними) ?

[resource]

Список - это отсутствие быстрого доступа к элементам (доступа по индексу), последствия: лучше не сортировать и не искать. Естественно может быть список вам и пригодится, лично мне он пригодился всего пару раз, и то я добавлял/удалял элементы в конце/начале списка.

А мне вот список (восновном двусвязный) пригождался очень много раз. Хорош он тогда, когда в какой-то функции получаешь указатель на сам элемент списка. Таким образом отпадает надобность в том, чтобы перебирать список. И главное конечно достоинство списка (двусвязного) в том, что можно легко добавлять элемент в любую позицию, равно как и удалять.

[Вад]

resource, добавление-удаление всё-таки на красно-чёрных деревьях в общем случае поприятнее будет: всё-таки, в список вставка в произвольное место занимает линейное время.

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

[resource]

Вад

когда в какой-то функции получаешь указатель на сам элемент списка. Таким образом отпадает надобность в том, чтобы перебирать список

Если же задача плоская - вставить элемент в 25ю (например) позицию, то согласен насчет линейного времени. Но с другой стороны, это всё равно лучше, чем вставка элемента в произвольную позицию массива (если эта позиция уже заполнена).

[Вад]

resource, я больше отвечал на вторую часть твоего высказывания А если вставка в список производится более частным образом, в заданном месте - тогда согласен. Скажем, слияние упорядоченных списков будет занимать всего лишь линейное время.

Вот и пример задачки - сортировка слиянием (merge sort) Хороша в случаях, когда объёмы сравниваемых данных большие - то есть, копирование стоит дорого.

[Антон (LogRus)]

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

[resource]

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

[Dimka]

resource, бинарное дерево (например, красно-чёрное) - тоже вполне реальный и конкретный способ организации данных.

[resource]

я вот могу спокойно сказать, к примеру, что "реализовал в программе дерево с помощью списка", а наоборот не могу сказать.

в общем от теорий уже дышать трудно становится. Покажите код что ли какой-нибудь (не обязательно свой).

[Вад]

Бинарное дерево - обычная рекурсивная структура. Такая же, кстати, как и список, только более ветвистая
Очень грубо:

Код:

template <typename ElemType>
struct Tree{
    Tree<ElemType> * left;
    Tree<ElemType> * right;
    ElemType value;
};

[Антон (LogRus)]

Вад, забыл указатель на корень

resource, вообще все  ассоциативные контейнеры (почти все угадай какие не деревья), это красно-чёрные деревья
и как я рассказывал Алексею в одном из топиков, эти контейнеры на самом деле 1 шаблонный класс, поведение которого немного меняется с помощью traits для получения уже финальной реализации

мы кстати отклонились от темы

[Алексей++]

битсет и вектор не деревянные )

[Антон (LogRus)]

а из ассоциативных ?

[Алексей++]

да я парочку знаю то ) Там их по списку туча, я не всё ещё пробовал

[Вад]

Вад, забыл указатель на корень

Умышленно Для "просто дерева" это не обязательно - ибо дополнительная сущность, оптимизирующая работу с деревом. В Лиспе, вон, и односвязные списки являются встроенным типом данных.