Векторы, списки, последовательности

Сентябрь 7, 2022

Главная
Алгебра
Векторы, списки, последовательности

Содержание

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. Скачать презентацию

Слайд 2

АТД «Вектор» 1
Пусть S — линейная последовательность из n элементов. Разряд

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

Слайд 3

АТД «Вектор» 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()

Слайд 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: удаленный элемент.

Слайд 11

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

Слайд 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