230101_ВС_ЛР. Практикум для студентов всех форм обучения специальности 230101 Вычислительные машины, комплексы, системы и сети (8, 9 семестры)
 Скачать 0.69 Mb.
|
Лабораторная работа №4Тема работы: "Динамические структуры данных" Краткий справочный материал и примеры Структурированные типы данных, такие, как массивы, множества, записи, представляют собой статические структуры, так как их размеры неизменны в течение всего времени выполнения программы. Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. Такие структуры данных называются динамическими, к ним относятся стеки, очереди, списки, деревья и другие. Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти ЭВМ и увеличивает время решения задач. Каждая компонента любой динамической структуры представляет собой запись, содержащую по крайней мере два поля: одно поле типа указатель, а второе для размещения данных. В общем случае запись может содержать не один, а несколько укзателей и несколько полей данных. Поле данных может быть переменной, массивом, множеством или записью. Для дальнейшего рассмотрения представим отдельную компоненту в виде:  где поле p - указатель; поле D - данные. Описание этой компоненты дадим следующим образом: type Pointer = ^Comp; Comp = record D:T; pNext:Pointer end; Здесь T - тип данных. Рассмотрим основные правила работы с динамическими структурами данных типа стек, очередь и список, базируясь на приведенное описание компоненты. Стеки Стеком называется динамическая структура данных, добавление компоненты в которую и исключение компоненты из которой производится из одного конца, называемого вершиной стека. Стек работает по принципу LIFO (Last-In, First-Out) - поступивший последним обслуживается первым. Обычно над стеками выполняется три операции: 1. начальное формирование стека (запись первой компоненты); 2. добавление компоненты в стек; 3. выборка компоненты (удаление). Для формирования стека и работы с ним необходимо иметь две переменные типа указатель, первая из которых определяет вершину стека, а вторая вспомогательная. Пусть описание этих переменных имеет вид: var pTop, pAux: Pointer; где pTop - указатель вершины стека, pAux - вспомогательный указатель. Начальное формирование стека выполняется следующими операторами:  Последний оператор или группа операторов записывает содержимое поля данных первой компоненты. Добавление компоненты в стек призводится с использованием вспомогательного указателя:  Добавление последующих компонент производится аналогично. Рассмотрим процесс выборки компонент из стека. Пусть к моменту начала выборки стек содержит три компоненты:  Первый оператор или группа операторов осуществляет чтение данных из компоненты вершины стека. Второй оператор изменяет значение указателя вершины стека:  Как видно из рисунка, при чтении компонента удаляется из стека. Очереди Очередью называется динамическая структура данных, добавление компоненты в которую производится в один конец, а выборка осуществляется с другого конца. Очередь работает по принципу FIFO (First-In, First-Out) - поступивший первым обслуживается первым. Для формирования очереди и работы с ней необходимо иметь три переменные типа указатель, первая из которых определяет начало очереди, вторая конец очереди, третья вспомогательная. Описание компоненты очереди и переменных типа указатель дадим следующим образом: Type PComp=^Comp; Comp=record D:T; pNext:PComp end; var pBegin, pEnd, pAux: PComp; где pBegin - указатель начала очереди, pEnd - указатель конца очереди, pAux - вспомогательный указатель. Тип Т определяет тип данных компоненты очереди. Начальное формирование очереди выполняется следующими операторами:  Добавление компоненты в очередь производится в конец очереди:  Добавление последующих компонент производится аналогично. Выборка компоненты из очереди осуществляется из начала очереди, одновременно компонента исключается из очереди. Пусть в памяти ЭВМ сформирована очередь, состоящая из трех элементов:  Выборка компоненты выполняется следующими операторами:  Линейные списки В стеки или очереди компоненты можно добавлять только в какой либо один конец структуры данных, это относится и к извлечению компонент. Связный (линейный) список является структурой данных, в произвольно выбранное место которого могут включаться данные, а также изыматься оттуда. Каждая компонента списка определяется ключом. Обычно ключ либо число, либо строка символов. Ключ располагается в поле данных компоненты, он может занимать как отдельное поле записи, так и быть частью поля записи. Основные отличия связного списка от стека и очереди следующие: • для чтения доступна любая компонента списка; • новые компоненты можно добавлять в любое место списка; • при чтении компонента не удаляется из списка. Над списками выполняются следующие операции: • начальное формирование списка (запись первой компоненты); • добавление компоненты в конец списка; • чтение компоненты с заданным ключом; • вставка компоненты в заданное место списка (обычно после компоненты с заданным ключом); • исключение компоненты с заданным ключом из списка. Для формирования списка и работы с ним необходимо иметь пять переменных типа указатель, первая из которых определяет начало списка, вторая конец списка, остальные вспомогательные. Описание компоненты списка и переменных типа указатель дадим следующим образом: Type PComp= ^Comp; Comp= record D:T; pNext:PComp end; var pBegin, pEnd, pCKey, pPreComp, pAux: PComp; где pBegin - указатель начала списка, pEnd - указатель конца списка, pCKey, pPreComp, pAux - вспомогательные указатели. Начальное формирование списка, добавление компонент в конец списка выполняется так же, как и при формировании очереди.  Для чтения и вставки компоненты по ключу необходимо выполнить поиск компоненты с заданным ключом: pCKey:=pBegin; while (pCKey<>NIL) and (Key<>pCKey^.D) DO pCKey:=pCKey^.pNext; Здесь Key - ключ, тип которого совпадает с типом данных компоненты. После выполнения этих операторов указатель pСKey будет определять компоненту с заданным ключом или такая компонента не будет найдена. Пусть pCKey определяет компоненту с заданным ключом. Вставка новой компоненты выполняется следующими операторами:  Для удаления компоненты с заданным ключом необходимо при поиске нужной компоненты помнить адрес предшествующей: pCKey:=pBegin; while (pCKey<>NIL) and (Key<>pCKey^.D) do begin pPreComp:=pCKey; pCKey:=pCKey^.pNext end; Здесь указатель pCKey определяет компоненту с заданным ключом, указатель pPreComp содержит адрес предыдущей компоненты. Удаление компоненты с ключом Key выполняется оператором:  Задание
|