Динамические структуры данных - презентация, доклад, проект скачать

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

Динамические структуры данных, слайд №10

Динамические структуры данных, слайд №11

Динамические структуры данных, слайд №12

Динамические структуры данных, слайд №13

Динамические структуры данных, слайд №14

Динамические структуры данных, слайд №15

Динамические структуры данных, слайд №16

Динамические структуры данных, слайд №17

Динамические структуры данных, слайд №18

Динамические структуры данных, слайд №19

Динамические структуры данных, слайд №20

Динамические структуры данных, слайд №21

Динамические структуры данных, слайд №22

Динамические структуры данных, слайд №23

Динамические структуры данных, слайд №24

Динамические структуры данных, слайд №25

Динамические структуры данных, слайд №26

Динамические структуры данных, слайд №27

Динамические структуры данных, слайд №28

Содержание ▲

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

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

Слайд 1

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

Динамические структуры данных

Слайд 2

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

ЛОСС Линейный однонаправленный связанный список – динамическая структура, в которой данные представляются в виде цепочки. Основная идея такого способа представления данных – элементы структуры данных распределяются в памяти ЭВМ в произвольном месте, но с указанием того места, где находится следующий за ним элемент.

Слайд 3

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

ЛОСС Такой способ представления данных имеет преимущество перед использованием статического массива данных или записи, поскольку обеспечивает быстрое выполнение операций вставки и удаления элемента данных. Кроме того, память, отводимая для хранения вектора может использоваться весьма неэффективно

Слайд 4

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

ЛОСС Линейный однонаправленный список имеет структуру FIRST – это внешний указатель, он указывает на первый элемент списка (где в ОЗУ размещается первый узел (node) списка)

Слайд 5

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

Каждый элемент списка содержит два поля: поле информации (info) и поле адреса следующего узла (указатель next). Поле следующего адреса последнего элемента содержит пустую ссылку nil Если список пустой, то first имеет значение nil

Слайд 6

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

ЛОСС Определим функциональную спецификацию структуры данных ЛОССТ: (в информационной части узла info находятся данные типа T): Создать_список: → ЛОССТ Список_пуст: ЛОССТ → лог Добавить: ЛОССТ х Т → ЛОССТ Удалить: ЛОССТ → ЛОССТ х Т Первый: ЛОССТ → Т

Слайд 7

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

ЛОСС на паскале После введения функциональной спецификации структуры данных переходим к ее логическому описание на основе одного из ЯП, например на паскале Вводим тип указателя и тип узла Type link = ^node; node = record info : T; next : link; end; Var first, ptr : link; {описание внешнего и рабочего указателей}

Слайд 8

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

Логическое описание ЛОСС Создание списка – это есть описание внешнего указателя: var first:link; Проверка списка на пустоту Function empty(first : link) : boolean; begin empty := (first = nil); end;

Слайд 9

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

Логическое описание ЛОСС Функция «Первый» - показать информационную часть первого узла Function show_first(first : link) : T; begin if not empty(first) then show_first := first^.info else writeln(‘Нет первого узла’) end;

Слайд 10

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

Логическое описание ЛОСС Функция «Добавить» - добавить узел в ЛОССТ

Слайд 11

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

Procedure Add_node(var q:link; data:T); var ptr:link; begin new(ptr); ptr^.info := data; ptr^.next := q^.next; q^.next := ptr; end;

Слайд 12

$Формирование списка Read(data); {читаются данные типа Т} New(first); first^.info := data; first^.next := nil; ptr := first; While do begin...$

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

Формирование списка Read(data); {читаются данные типа Т} New(first); first^.info := data; first^.next := nil; ptr := first; While do begin read(data); new (ptr^.next); ptr := ptr^.next; ptr^.info := data; ptr^.next := nil; end;

Слайд 13

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

Удаление узла из списка производится следующим образом

Слайд 14

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

Procedure Delete_node(q:link); var ptr:link; begin ptr := q^.next; q^.next := ptr^.next; dispose(ptr); end;

Слайд 15

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

Стек Стек – упорядоченный набор элементов, в котором размещение новых и удаление существующих элементов производится только с одного его конца, называемого вершиной стека В стеке последний размещенный элемент удаляется первым – First In - Last Out

Слайд 16

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

Стек Стек применяется при синтаксическом анализе текста, выполняемом в трансляторах ЯП , при вызове рекурсивной функции или процедуры

Слайд 17

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

Функциональная спецификация Для структуры данных СТЕКТ можно ввести следующую спецификацию Создание_стека: → СТЕКТ Стек_пуст: СТЕКТ → лог Засылка: Т х СТЕКТ → СТЕКТ Выборка: СТЕКТ → Т х СТЕКТ Последний: СТЕКТ → Т

Слайд 18

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

Логическое описание Логическое описание стека осуществляется теми же средствами, что и ЛОСС.

Слайд 19

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

Очередь Очередью называется упорядоченный набор элементов, которые могут удаляться с одного ее конца (наз. Началом очереди), и помещаться в другой конец этого набора (наз. Концом очереди). Пришедший первым уходит первым – First In – First Out Логическое описание типа ОчередьТ строится аналогично ЛОССТ и стеку

Слайд 20

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

Очередь Динамическая структура данных ОчередьТ используется при моделировании реальных очередей и при организации работы ОС ЭВМ

Слайд 21

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

Дек Дек – это очередь с двойным доступом, в которой разрешено прибавление и удаление с обоих концов очереди.

Слайд 22

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

Деревья Деревья наилучшим образом приспособлены для решения задач искусственного интеллекта и синтаксического анализа текста. Примеры применения: программа игры в шашки или шахматы, докозательство теоремы, анализ зрительных или звуковых образов

Слайд 23

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

Деревья Деревом типа Т называется структура данных, которая образована данным типа Т, называемым корнем дерева, и конечным, возможно пустым множеством с переменным числом элементов – деревьев типа Т, называемых поддеревьями этого дерева (рекурсивное определение)

Слайд 24

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

Деревья (терминология) Лист – это корень поддерева, не имеющего, в свою очередь, поддеревьев Вершина – это корень подерева. Кореь и листья дерева являются особыми вершинами Вершина связана с каждым из своих поддеревьев ветвью

Слайд 25

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

Двоичное дерево Двоичным деревом типа Т называют структуру, которая либо пуста либо образована: - данным типа Т, называемым корнем двоичного дерева - двоичным деревом типа Т, называемым левым поддеревом двоичного дерева - двоичным деревом типа Т, называемым правым поддеревом двоичного дерева

Слайд 26

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

Двоичное дерево Функциональная спецификация ДДТ: Создание_дерева : → ДДТ Дерево_пусто : ДДТ → лог Чтение_корня : ДДТ → Т Слева : ДДТ → ДДТ Справа : ДДТ → ДДТ Построение Т х ДДТ Х ДДТ → ДДТ

Слайд 27

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

Двоичное дерево (логическое описание) При представлении данных в виде двоичного дерева будем считать, что каждое звено (вершина дерева) будет записью, содержащей четыре поля: ключ записи, ссылка на левое поддерево, ссылка на правое поддерево и информационная часть.

Слайд 28

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

Построение двоичного дерева Рассмотрим принцип построения дерева при занесении записей в таблицу. Пусть в первоначально пустую таблицу заносится последовательно поступающие записи с ключами 70, 60, 85, 87, 90, 45, 30, 88, 35, 20, 86. Если ключ следующей записи окажется меньше k, то этой записи поставим в соответствие левую вершину, в противном случае – правую.