- объект
- структура данных
- коллекция
- структура данных
- для хранения множества значений
- содержит в себе уникальные данные элементы
- каждое значение может встречаться лишь один раз
- содержит в себе уникальные данные элементы
- для хранения набора значений
- которые не имеют индексов или ключей
- но внутри они должны иметь порядок
- например, индекс в массиве,
- однако, множество абстрагирует нас от этой особенности реализации
- например, индекс в массиве,
Рубрика: Тип Данных
ВАЖНО
каждый отдельный элемент связного списка занимает отдельное место в памяти
каждый предыдущий элемент хранит ссылку на следующий элемент, который лежит в списке.
Плюсы
является то, что мы можем мгновенно добавлять в конец или в начало списка
связность заключается в том, что каждый предыдущий элемент списка содержит ссылку на следующий элемент в списке
Минусы
Чтобы получить какой-то элемент — нам с самого начала списка надо итерироваться и сравнивать
ОТЛИЧИЕ МАССИВ и СПИСКИ
Массивы используем там, где
- часто обращаемся к каким то данным
- не часто нужно изменять размер массива.
Списки используем там, где
- если редко обращаемся к каким-то данным
- часто его дополняем
ВАЖНО
- элементы всегда добавляются в конец структуры
- элементы всегда извлекаются из конца структуры
ПРИМЕР
стопка бумаги
- добавляем сверху
- забираем сверху
не важно
длительный этот путь или нет, а самое
главное
количество пройденных участков или существует ли путь
ЗАДАЧА
Найти путь из точки A в точку B за минимальное количество шагов
Процесс решения
задаём для каждой вершины название
создаём объект, который содержит вершины (содержит путь к точке B)
используется Cтруктура Данных «очередь»
- состоит из каких то элементов
- элементы всегда добавляются в конец структуры, а извлекаются из её начала
- тот кто пришел на кассу первым — уходит первым
- тот кто пришел на кассу последним — уходит последним
- FIFO — FIRST IN FIRST OUT
алгоритм поиска кратчайшего пути в графе
Важно
учитывается длинна пройденного ребра — вес
Задача
стартовая точка A
конечная точка G
A—B—F—G
| / |
| / |
| / |
| D |
| / |
| / |
|/ |
C——E
составляется таблица, на котором на первом этапе записываются значения тех вершин, в которые мы можем попасть из стартовой точки. Все остальные вершины являются не достижимыми и мы их помечаем знаком бесконечности.
На втором этапе мы помечаем эти (B и C) вершины как рассмотренные,
На третьем этапе мы рассматриваем вершины, на которые мы можем попасть из точек B и C и в таблице записываем значения из точки A до точек, которые мы достигаем из вершин B и С. Опять же помечаем эти точки, как уже рассмотренные.
На следующем этапе мы достигаем конечной точки G, но у нас происходит перерасчет (мы находим путь до F, до которого оказывается короче и перезаписываем значение в таблице).
И на следующем этапе мы проделываем тоже самое и находим самый оптимальный путь и узнаем, что из точки A в точку G мы можем добраться за пять условных единиц.