Слайд 2
АТД «Вектор» 1
Пусть S — линейная последовательность из
n элементов. Разряд элемента е последовательности S равен количеству
элементов, находящихся в S перед е, то есть разряд первого элемента последовательности равен 0, а последнего — n-1. Очевидно, что разряд каждого элемента в S уникален.
Абстракция «Вектор» заключается в том, что последовательность S не обязана быть массивом.
Кроме того, «Вектор» – более динамическая структура, поскольку разряд элемента в S может меняться вследствие удаления и добавления новых элементов.
Слайд 3
АТД «Вектор» 2
Основные методы:
ElemAtRank(r): возвращает элемент S с
разрядом r; если 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()
Слайд 4
Адаптация вектора для реализации дека
Слайд 5
Реализация вектора с помощью массива
Недостатки:
1.InsertAtRank и RemoveAtRank
выполняются за O(N) времени
2.Емкость вектора ограничена фиксированным размером массива
Слайд 6
Реализация вектора на основе расширяемого массива (Имитация изменения
размера массива)
Слайд 7
Реализация вектора на основе расширяемого массива
public class ArrayVector
: Vector
{ private Object[ ] a;
private
int capacity =16; /* емкость вектора*/ private int size = 0; /* текущий размер*/
public ArrayVector() { a = new Object[capacity]; } //время O(1)
public Object ElemAtRank(int r) { return a[r]; } //время O(1)
public int Size() { return size; }
public bool IsEmpty() { return (size == 0); }
public Object ReplaceAtRank(int r, Object e) { Object temp = a[r]; return temp; } //время O(1)
public Object RemoveAtRank(int r) // время O(N)
{ Object temp = a[r];
for (int i=r; i size--; return temp;
}
public void InsertAtRank(int r, Object e) // время O(N)
{ if (size == capacity) // переполнение
{ capacity *= 2; Object[ ] b = new Object[capacity];
for (int i=0; i a = b;
}
for (int i=size-1; i>=r; i--) a[i+1] = a[i];
a[r] = e; size++;
}
}
Слайд 8
АТД «Список» 1
В списке узлы «знают» друг о
друге. Поэтому операции с параметрами-узлами быстрее, чем операции с
индексами в массиве.
Например: RemoveAtNode(v), InsertAfterNode(v,e)
Абстракция узла – АТД «Позиция»
GetElement(): возвращает элемент, хранящийся в данной позиции.
Input: нет; Output: объект.
SetElement(Object e): помещает элемент в позицию.
Input: элемент; Output: нет
Слайд 9
АТД «Список» - операции доступа по чтению
First(): возвращает
позицию первого элемента списка S; если список пуст, выдается
сообщение об ошибке.
Input: нет; Output: позиция.
Last(): возвращает позицию последнего элемента списка S; если список пуст, выдается сообщение об ошибке.
Input: нет; Output: позиция.
IsFirst(р): возвращает логическое значение, показывающее, является ли данная позиция первой в списке. Input: позиция р; Output: логическое значение.
IsLast(p): возвращает логическое значение, показывающее, является ли данная позиция последней в списке.
Input: позиция р; Output: логическое значение.
Before(p): возвращает позицию элемента S, который предшествует элементу позиции р; если р является первой позицией, выдается сообщение об ошибке.
Input: позиция; Output: позиция.
After(р): возвращает позицию элемента S, который следует за элементом позиции р; если р является последней позицией, выдается сообщение об ошибке. Input: позиция; Output: позиция.
Слайд 10
АТД «Список» - модифицирующие операции
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: удаленный элемент.
Слайд 12
Реализация АТД «Список» с помощью двусвязного списка –
класс 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; }
}
Слайд 13
Реализация АТД «Список» с помощью двусвязного списка –
операция 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 }
Слайд 14
Реализация АТД «Список» с помощью двусвязного списка –
вспомогательный метод 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.");
}
}
Слайд 15
АТД «Последовательность»
все методы векторов
все методы списков
два
дополнительных «связующих» метода, которые обеспечивают переход между разрядами и
позициями:
AtRank(r): возвращает позицию элемента с разрядом r.
Input: целое число; Output: позиция.
RankOf(p): возвращает разряд элемента в позиции р.
Input: позиция; Output: целое число.
Слайд 16
АТД «Последовательность» – множественное наследование
public interface Sequence :
List, Vector
{ // Дополнительные "переходные" методы.
Position
AtRank(int rank);
int RankOf(Position position);
}
Слайд 17
Реализация последовательности с помощью двусвязного списка
все методы АТД
«список» выполняются за O(1) время.
Методы же АТД «вектор» реализованы
менее эффективно.
ElemAtRank(r) - поиск можно начать с ближайшего конца последовательности, время выполнения составит O(min(r+1, n-r))
- Аналогично - InsertAtRank(r, e) и RemoveAtRank(r)
Слайд 18
Реализация последовательности с помощью двусвязного списка 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 }
return node;
}
Слайд 19
Реализация последовательности с помощью двусвязного списка 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);
}
}
Слайд 20
Сравнительный анализ различных реализаций последовательности
Каждая из реализаций имеет
свои преимущества и недостатки. Выбор того или иного способа
обусловлен конкретными требованиями приложения. Поскольку структура АТД «последовательность» не зависит от конкретных условий реализации, применяется наиболее соответствующая реализация с минимальными изменениями в программе.
Слайд 21
Векторы, списки, последовательности – иерархия интерфейсов
Задача – оптимизация
состава методов
Введем обобщающее понятие «контейнер» («коллекция») и классификацию методов
контейнеров:
методы запросов возвращают информацию о контейнере;
методы доступа возвращают элементы или позиции контейнера;
методы обновления изменяют контейнер, добавляя, удаляя элементы или изменяя отношения между элементами.
методы конструктора, создающие экземпляр контейнера.
Слайд 22
Инспектирующие контейнеры
В таких контейнерах, после их инициализации с
помощью конструктора, разрешен доступ «только для чтения». Таким образом,
элементы в них защищены от ошибочных или злонамеренных внешних попыток изменения.
Слайд 23
Структура иерархии последовательностей
