🗊Презентация Векторы, списки, последовательности

Векторы, списки, последовательности АТД «Вектор» Расширяет «массив» Абстракция индекса – «разряд»

АТД «Вектор» 1 Пусть S — линейная последовательность из n элементов. Разряд элемента е последовательности S равен количеству элементов, находящихся в S перед е, то есть разряд первого элемента последовательности равен 0, а последнего — n-1. Очевидно, что разряд каждого элемента в S уникален. Абстракция «Вектор» заключается в том, что последовательность S не обязана быть массивом. Кроме того, «Вектор» – более динамическая структура, поскольку разряд элемента в S может меняться вследствие удаления и добавления новых элементов.

АТД «Вектор» 2 Основные методы: ElemAtRank(r): возвращает элемент S с разрядом r; если r<0 или r>п-1, где п — текущее число элементов, выдается сообщение об ошибке. Input: целое число; Output: объект. ReplaceAtRank(r,e): замещает объектом е элемент с разрядом r и возвращает замещаемый объект. Если r<0 или r>п-1, где п — текущее число элементов, выдается сообщение об ошибке. Input: целое число r и объект е; Output: объект. InsertAtRank(r,e): добавляет в S новый элемент е; если r<0 или r>п, где п — текущее число элементов, выдается сообщение об ошибке. Input: целое число r и объект е; Output: нет. RemoveAtRank(r): удаляет из S элемент с разрядом r; если r<0 или r>п-1, где п — текущее число элементов, выдается сообщение об ошибке. Input: целое число; Output: объект. стандартные методы Size() и IsEmpty()

Адаптация вектора для реализации дека

Реализация вектора с помощью массива

Реализация вектора на основе расширяемого массива (Имитация изменения размера массива)

Реализация вектора на основе расширяемого массива

АТД «Список» 1 В списке узлы «знают» друг о друге. Поэтому операции с параметрами-узлами быстрее, чем операции с индексами в массиве. Например: RemoveAtNode(v), InsertAfterNode(v,e) Абстракция узла – АТД «Позиция» GetElement(): возвращает элемент, хранящийся в данной позиции. Input: нет; Output: объект. SetElement(Object e): помещает элемент в позицию. Input: элемент; Output: нет

АТД «Список» - операции доступа по чтению First(): возвращает позицию первого элемента списка S; если список пуст, выдается сообщение об ошибке. Input: нет; Output: позиция. Last(): возвращает позицию последнего элемента списка S; если список пуст, выдается сообщение об ошибке. Input: нет; Output: позиция. IsFirst(р): возвращает логическое значение, показывающее, является ли данная позиция первой в списке. Input: позиция р; Output: логическое значение. IsLast(p): возвращает логическое значение, показывающее, является ли данная позиция последней в списке. Input: позиция р; Output: логическое значение. Before(p): возвращает позицию элемента S, который предшествует элементу позиции р; если р является первой позицией, выдается сообщение об ошибке. Input: позиция; Output: позиция. After(р): возвращает позицию элемента S, который следует за элементом позиции р; если р является последней позицией, выдается сообщение об ошибке. Input: позиция; Output: позиция.

АТД «Список» - модифицирующие операции ReplaceElement(p,e): замещает элемент в позиции р на е и возвращает элемент, который до этого был в позиции р. Input: позиция р и объект е; Output: объект. SwapElements(p,q): меняет местами элементы в позициях р и q таким образом, что элемент в позиции р перемещается в позицию q, а элемент, бывший в позиции q, перемещается в позицию р. Input: две позиции; Output: нет. InsertFirst(e): вставляет новый элемент е в S в качестве первого элемента списка. Input: объект е; Output: позиция вставленного элемента е. InsertLast(e): вставляет новый элемент е в S в качестве последнего элемента списка. Input: объект е; Output: позиция вставленного элемента е. InsertBefore(p, е): вставляет новый элемент е в S перед позицией р; если р является первой позицией, выдается сообщение об ошибке. Input: позиция р и объект е; Output: позиция вставленного элемента е. InsertAfter(p, e): вставляет новый элемент е в S после позиции р; если р является последней позицией, выдается сообщение об ошибке. Input: позиция р и объект е; Output: позиция вставленного элемента е. Remove(p): удаляет из S элемент в позиции р Input: позиция; Output: удаленный элемент.

Пример использования списка

Реализация АТД «Список» с помощью двусвязного списка – класс DNode class DNode : Position { private DNode prev, next; private Object element; // элемент, хранящийся в данной позиции public DNode(DNode newPrev, DNode newNext, Object elem) { prev = newPrev; next = newNext; element = elem; } public Object GetElement() { if ((prev == null) && (next == null)) throw new InvalidPositionException("Positionisnotinalist!"); return element; } public void SetElement(Object newElement) {element = newElement;} public DNode GetNext() { return next; } public DNode GetPrev() { return prev; } public void SetNext(DNode newNext) { next = newNext; } public void SetPrev(DNode newPrev) { prev = newPrev; } }

Реализация АТД «Список» с помощью двусвязного списка – операция InsertAfter Алгоритм InsertAfter(p, e): Создать новый узел v v.SetElement(e) // связать v с предшествующим узлом v.SetPrev(p) // связать v с последующим узлом v.SetNext(p.getNext()) // связывает ранее следовавший за р узел с v (p.GetNext()).SetPrev(v) // связывает р с новым последующим узпом v p.SetNext(v) return v { позиция элемента e }

Реализация АТД «Список» с помощью двусвязного списка – вспомогательный метод checkPosition protected DNode checkPosition(Position p) { if (p == null) throw new InvalidPositionException("Null Position passed to NodeList."); if (p == header) throw new InvalidPositionException("Header is not a valid position"); if (p == trailer) throw new InvalidPositionException("Trailer is not a valid position"); try { DNode temp = (DNode)p; if ((temp.GetPrev() == null) || (temp.GetNext() == null)) throw new InvalidPositionException("Position does not belong to a valid NodeList"); return temp; } catch (Exception e) { throw new InvalidPositionException("Position is of wrong type for this container."); } }

АТД «Последовательность» все методы векторов все методы списков два дополнительных «связующих» метода, которые обеспечивают переход между разрядами и позициями: AtRank(r): возвращает позицию элемента с разрядом r. Input: целое число; Output: позиция. RankOf(p): возвращает разряд элемента в позиции р. Input: позиция; Output: целое число.

АТД «Последовательность» – множественное наследование public interface Sequence : List, Vector { // Дополнительные "переходные" методы. Position AtRank(int rank); int RankOf(Position position); }

Реализация последовательности с помощью двусвязного списка все методы АТД «список» выполняются за O(1) время. Методы же АТД «вектор» реализованы менее эффективно. ElemAtRank(r) - поиск можно начать с ближайшего конца последовательности, время выполнения составит O(min(r+1, n-r)) - Аналогично - InsertAtRank(r, e) и RemoveAtRank(r)

Реализация последовательности с помощью двусвязного списка 1 public class NodeSequence : NodeList, Sequence { // проверяем, находится ли разряд в интервале [0,numElt-1]; protected void checkRank(int rank) // время O(1). { if (rank<0 || rank>=numElts) { String s = String.Format("Rank {0} is invalid for this sequence of {1} elements.", rank, numElts); throw new BoundaryViolationException(s); } public Position ElemAtRank (int rank) // время O(1) { DNode node; checkRank(rank); if (rank <= Size()/2) // просматриваем последовательность от начала { node = header.GetNext(); for (int i=0; i < rank; i++) node = node.GetNext(); } else // просматриваем последовательность с конца { node = trailer.GetPrev(); for(int i=1; i<Size()-rank; i++) node = node.GetPrev(); } return node; }

Реализация последовательности с помощью двусвязного списка 2 public void InsertAtRank (int rank, Object element) // время O(n) { if (rank == Size()) // в данном случае не выполняется checkRank InsertLast(element); else { checkRank(rank); InsertBefore(AtRank(rank), element); } } public Object RemoveAtRank (int rank) // время O(n) { checkRank(rank); return Remove(AtRank(rank)); } public Object ReplaceAtRank (int rank,Object element) //время O(n) { checkRank(rank); return ReplaceElement(AtRank(rank),element); } }

Сравнительный анализ различных реализаций последовательности

Векторы, списки, последовательности – иерархия интерфейсов Задача – оптимизация состава методов Введем обобщающее понятие «контейнер» («коллекция») и классификацию методов контейнеров: методы запросов возвращают информацию о контейнере; методы доступа возвращают элементы или позиции контейнера; методы обновления изменяют контейнер, добавляя, удаляя элементы или изменяя отношения между элементами. методы конструктора, создающие экземпляр контейнера.

Инспектирующие контейнеры В таких контейнерах, после их инициализации с помощью конструктора, разрешен доступ «только для чтения». Таким образом, элементы в них защищены от ошибочных или злонамеренных внешних попыток изменения.

Структура иерархии последовательностей

Итераторы – АТД «Итератор»