Динамические структуры данных
ЛОСС
ЛОСС
ЛОСС
ЛОСС
ЛОСС на паскале
Логическое описание ЛОСС
Логическое описание ЛОСС
Логическое описание ЛОСС
Формирование списка
Стек
Стек
Функциональная спецификация
Логическое описание
Очередь
Очередь
Дек
Деревья
Деревья
Деревья (терминология)
Двоичное дерево
Двоичное дерево
Двоичное дерево (логическое описание)
Построение двоичного дерева
248.00K
Categories: programmingprogramming informaticsinformatics

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

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 (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, то этой записи поставим в
соответствие левую вершину, в противном
случае – правую.
English     Русский Rules