ОБЩИЕ СВЕДЕНИЯ

ЛАБОРАТОРНАЯ РАБОТА №_19-20

Тема: РАЗРАБОТКА АЛГОРИТМОВ И ПРОГРАММ С ИСПОЛЬЗОВАНИЕМ ДИНАМИЧЕСКИХ СТРУКТУР ДАННЫХ.

Цель работы:Научить разрабатывать алгоритмы и программы с использованием динамических структур данных, закрепить теоретические знаний по теме.

Техническое обеспечение: ПЭВМ.

Программное обеспечение: ОС Windows, ИСР Turbo Pascal 7.0.

ОБЩИЕ СВЕДЕНИЯ

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

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

Линейная динамическая структура представляет собой изменяемую последовательность элементов:

· стеки – разрешено добавлять элементы только в конец и удалять только последние элементы. Принцип изменения содержимого стека часто формулируют так: «Последним пришел – первым ушел» (LIFO (Last-In, First-Out))

· очереди – разрешено добавлять элементы в конец, а удалять – из начала. Принцип: «Первым пришел – первым ушел» (FIFO (First-In, First-Out)).

· деки – разрешено добавлять и удалять элементы и с начала и с конца.

В древовидной структуре каждый элемент (вершина) ссылается на один или более элементов следующего уровня.

В сетевой структуре никаких ограничений на связи элементов не накладывается.

Для представления динамических структур используются списки.

Список– это структура, каждый элемент состоит из двух частей: информационной части, содержащей данные (x₁ , x₂ и т.д.) и адресной части, где хранятся указатели на следующие элементы списка (pp). В зависимости от количества полей в адресной части и порядка связывания элементов различают:

· Линейные односвязные списки – единственное адресное поле содержит адрес следующего элемента. Последний элемент списка имеет пустой указатель Nil. Связанный список такого типа называется однонаправленной цепочкой.

· Кольцевые односвязные списки – единственное адресное поле содержит адрес следующего элемента, а последний элемент ссылается на первый.

· Линейные двусвязные списки – каждый элемент содержит адреса предыдущего и последующих элементов, соответственно, первый элемент в качестве адреса предыдущего, а последний – в качестве адреса следующего элемента содержит nil.

· Кольцевые двусвязные списки – каждый элемент содержит адреса предыдущего и последующих элементов, причем первый элемент в качестве предыдущего содержит адрес последнего элемента, а последний элемент в качестве следующего – адрес первого элемента.