Главная страница

230101_ВС_ЛР. Практикум для студентов всех форм обучения специальности 230101 Вычислительные машины, комплексы, системы и сети (8, 9 семестры)


Скачать 0.69 Mb.
НазваниеПрактикум для студентов всех форм обучения специальности 230101 Вычислительные машины, комплексы, системы и сети (8, 9 семестры)
Анкор230101_ВС_ЛР.doc
Дата20.04.2018
Размер0.69 Mb.
Формат файлаdoc
Имя файла230101_ВС_ЛР.doc
ТипПрактикум
#18302
страница5 из 9
1   2   3   4   5   6   7   8   9

Лабораторная работа №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 выполняется оператором:



Задание

  1. Составить программу, которая формирует стек, добавляет в него произвольное количество компонент, а затем читает все компоненты и выводит их на экран дисплея. В качестве данных взять строку символов. Ввод данных с клавиатуры дисплея, признак конца ввода строка символов END.

  2. Составить программу, которая формирует очередь, добавляет в нее произвольное количество компонент, а затем читает все компоненты и выводит их на экран дисплея. В качестве данных взять строку символов. Ввод данных с клавиатуры дисплея, признак

  3. Составить программу, которая формирует список, добавляет в него произвольное количество компонент, выполняет вставку и удаление компоненты по ключу, а затем читает и выводит весь список на экран дисплея. В качестве данных взять строку символов. Ввод данных с клавиатуры дисплея, признак конца ввода строка символов END.
1   2   3   4   5   6   7   8   9


написать администратору сайта