🗊Презентация Динамические структуры данных

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Динамические структуры данных, слайд №1Динамические структуры данных, слайд №2Динамические структуры данных, слайд №3Динамические структуры данных, слайд №4Динамические структуры данных, слайд №5Динамические структуры данных, слайд №6Динамические структуры данных, слайд №7Динамические структуры данных, слайд №8Динамические структуры данных, слайд №9Динамические структуры данных, слайд №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) списка)
Описание слайда:
ЛОСС Линейный однонаправленный список имеет структуру FIRST – это внешний указатель, он указывает на первый элемент списка (где в ОЗУ размещается первый узел (node) списка)

Слайд 5


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

Слайд 6


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

Слайд 7


ЛОСС на паскале После введения функциональной спецификации структуры данных переходим к ее логическому описание на основе одного из ЯП, например на паскале Вводим тип указателя и тип узла Type link = ^node; node = record info : T; next : link; end; Var first, ptr : link; {описание внешнего и рабочего указателей}
Описание слайда:
ЛОСС на паскале После введения функциональной спецификации структуры данных переходим к ее логическому описание на основе одного из ЯП, например на паскале Вводим тип указателя и тип узла 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;
Описание слайда:
Логическое описание ЛОСС Создание списка – это есть описание внешнего указателя: 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;
Описание слайда:
Логическое описание ЛОСС Функция «Первый» - показать информационную часть первого узла 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;
Описание слайда:
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 (ptr^.next); ptr := ptr^.next; ptr^.info := data; ptr^.next := nil; end;
Описание слайда:
Формирование списка 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;
Описание слайда:
Procedure Delete_node(q:link); var ptr:link; begin ptr := q^.next; q^.next := ptr^.next; dispose(ptr); end;

Слайд 15


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

Слайд 16


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

Слайд 17


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

Слайд 18


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

Слайд 19


Очередь Очередью называется упорядоченный набор элементов, которые могут удаляться с одного ее конца (наз. Началом очереди), и помещаться в другой конец этого набора (наз. Концом очереди). Пришедший первым уходит первым – First In – First Out Логическое описание типа ОчередьТ строится аналогично ЛОССТ и стеку
Описание слайда:
Очередь Очередью называется упорядоченный набор элементов, которые могут удаляться с одного ее конца (наз. Началом очереди), и помещаться в другой конец этого набора (наз. Концом очереди). Пришедший первым уходит первым – 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, то этой записи поставим в соответствие левую вершину, в противном случае – правую.
Описание слайда:
Построение двоичного дерева Рассмотрим принцип построения дерева при занесении записей в таблицу. Пусть в первоначально пустую таблицу заносится последовательно поступающие записи с ключами 70, 60, 85, 87, 90, 45, 30, 88, 35, 20, 86. Если ключ следующей записи окажется меньше k, то этой записи поставим в соответствие левую вершину, в противном случае – правую.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию