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