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

Нажмите для полного просмотра!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Векторы, списки, последовательности. Доклад-сообщение содержит 24 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 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п-1, где п — текущее число элементов, выдается сообщение об ошибке. Input: целое число r и объект е; Output: объект. InsertAtRank(r,e): добавляет в S новый элемент е; если rп, где п — текущее число элементов, выдается сообщение об ошибке. Input: целое число r и объект е; Output: нет. RemoveAtRank(r): удаляет из S элемент с разрядом r; если rп-1, где п — текущее число элементов, выдается сообщение об ошибке. Input: целое число; Output: объект. стандартные методы Size() и IsEmpty()

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

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

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

Описание слайда:

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