Содержание
- 2. АТД «Вектор» 1 Пусть S — линейная последовательность из n элементов. Разряд элемента е последовательности S
- 3. АТД «Вектор» 2 Основные методы: ElemAtRank(r): возвращает элемент S с разрядом r; если r п-1, где
- 4. Адаптация вектора для реализации дека
- 5. Реализация вектора с помощью массива Недостатки: 1.InsertAtRank и RemoveAtRank выполняются за O(N) времени 2.Емкость вектора ограничена
- 6. Реализация вектора на основе расширяемого массива (Имитация изменения размера массива)
- 7. Реализация вектора на основе расширяемого массива public class ArrayVector : Vector { private Object[ ] a;
- 8. АТД «Список» 1 В списке узлы «знают» друг о друге. Поэтому операции с параметрами-узлами быстрее, чем
- 9. АТД «Список» - операции доступа по чтению First(): возвращает позицию первого элемента списка S; если список
- 10. АТД «Список» - модифицирующие операции ReplaceElement(p,e): замещает элемент в позиции р на е и возвращает элемент,
- 11. Пример использования списка
- 12. Реализация АТД «Список» с помощью двусвязного списка – класс DNode class DNode : Position { private
- 13. Реализация АТД «Список» с помощью двусвязного списка – операция InsertAfter Алгоритм InsertAfter(p, e): Создать новый узел
- 14. Реализация АТД «Список» с помощью двусвязного списка – вспомогательный метод checkPosition protected DNode checkPosition(Position p) {
- 15. АТД «Последовательность» все методы векторов все методы списков два дополнительных «связующих» метода, которые обеспечивают переход между
- 16. АТД «Последовательность» – множественное наследование public interface Sequence : List, Vector { // Дополнительные "переходные" методы.
- 17. Реализация последовательности с помощью двусвязного списка все методы АТД «список» выполняются за O(1) время. Методы же
- 18. Реализация последовательности с помощью двусвязного списка 1 public class NodeSequence : NodeList, Sequence { // проверяем,
- 19. Реализация последовательности с помощью двусвязного списка 2 public void InsertAtRank (int rank, Object element) // время
- 20. Сравнительный анализ различных реализаций последовательности Каждая из реализаций имеет свои преимущества и недостатки. Выбор того или
- 21. Векторы, списки, последовательности – иерархия интерфейсов Задача – оптимизация состава методов Введем обобщающее понятие «контейнер» («коллекция»)
- 22. Инспектирующие контейнеры В таких контейнерах, после их инициализации с помощью конструктора, разрешен доступ «только для чтения».
- 23. Структура иерархии последовательностей
- 25. Скачать презентацию