Содержание
- 2. Простой Индексированный список Связный и двусвязный список Списки
- 3. Добавление элемента в начало/конец/внутрь Перемещение элемента вперед/назад Удаление элемента Выборка диапазона элементов (с/по) Поиск предыдущего/следующего элемента
- 4. Добавление: Находится нужный индекс и делается вставка с пересчетом индексов последующих элементов списка Перемещение: Старый индекс
- 5. Удаление: Изменяем индексы последующих элементов после удаляемого Выборка диапазона: Запрос элементов с индексами между индексами крайних
- 6. Преимущества: Простота выборок Простота хранения Недостатки: Изменение списка требует небольшой обработки остальных элементов Варианты: Индекс может
- 7. Добавление в начало: Во вставляемом элементе указываем на первый и помечаем его первым Добавление в конец:
- 8. Перемещение: Находим предыдущий элемент от перемещаемого В найденном элементе указываем на следующий элемент из перемещаемого Если
- 9. Выборка диапазона: В цикле начиная с начала диапазона по одному выбираем следующий элемент пока не конец
- 10. Преимущества: Относительная простота изменения списка Недостатки: Сложная навигация по списку и выборки Варианты: Связующим полем может
- 11. Смежные вершины (Adjacency List) Материализованный путь (Materialized Path) Вложенные множества (Nested Set) Деревья
- 12. Добавление узла Перемещение узла Удаление узла Выборка пути от узла до корня Выборка ветки дерева Выборка
- 13. Добавление: По аналогии со связным списком Перемещение: Удаление из связного списка Вставка в связный список Удаление:
- 14. Выборка пути от узла до корня В цикле выбираем родителя текущего узла, затем родителя делаем текущим
- 15. Выборка конечных узлов: Выбираем текущим узел корня дерева Ищем всех, у кого являемся родителем Если не
- 16. Выборка уровня дерева: Выбираем текущим узел корня дерева Если достигнут нужный уровень, то добавляем узел в
- 17. Преимущества: Простота хранения Простота изменения Недостатки: Сложность работы с ветками Сложность работы с уровнями Сложность определения
- 18. Добавление: Находим место и путь в дереве для вставки В добавляемом узле указывается полный путь Перемещение:
- 19. Выборка пути от узла до корня Выбираем те узлы дерева, в которых полный путь является началом
- 20. Выборка конечных узлов: Выбрать те узлы, по которым не найдется узлов с полным путем начинающимся с
- 21. Преимущества: Простота работы с ветками Простота определения принадлежности к родителям/детям Недостатки: Сложность работы с уровнями Небольшая
- 22. Добавление: Пересчет узлов дерева находящихся правее добавляемого узла Перемещение: Пересчет узлов дерева находящихся между начальной позицией
- 23. Выборка пути от узла до корня Выбираем те узлы дерева, у которых правое число больше правого
- 24. Выборка конечных узлов: Выбрать те узлы, у которых разница между левым и правым числом равна 1
- 25. Преимущества: Простота работы с ветками Простота определения принадлежности к родителям/детям Недостатки: Сложность работы с уровнями Сложность
- 26. Список ребер Графы
- 27. Добавление вершины/ребра Перемещение вершины/ребра Удаление вершины/ребра Получение всех вершин/ребер родителей Получение всех вершин/ребер потомков Поиск пути
- 28. Добавление: Добавление ребер ведущих к и из вершины Перемещение: Удаление ребер ведущих к и из перемещаемой
- 29. Получение родителей: Находим вершины приводящие к текущей вершине, включаем их в список просмотренных вершин В цикле
- 30. Получение потомков: Находим вершины выводящие из текущей вершины, включаем их в список просмотренных вершин В цикле
- 31. Получение пути: Аналогично процессу получения родителей для начальной вершины, но ищем до получения конечной вершины Или
- 32. Преимущества: Простота ведения Недостатки: Сложность поиска пути Сложность поиска родителей и потомков Варианты: Список достижимости Графы.
- 33. Графы. Список достижимости
- 34. Добавление: Добавление ребра Добавление всех путей ведущих по этому ребру Перемещение: Удаление ребра с зависимыми путями
- 35. Получение родителе: Выбрать все «ребра» и их вершины по которым достижима заданная вершина Получение потомков: Выбрать
- 36. Преимущества: Пути строятся при ведении графа Простота навигации по графу Недостатки: Небольшая сложность ведения графа Графы.
- 38. Скачать презентацию