Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Сформируем список целых чисел упорядоченный по неубыванию, т.е. каждый следующий элемент списка должен быть больше или равен предыдущему.
Для решения этой задачи рассмотрим основные части алгоритма, который мы будем воплощать в программе.
После ввода очередного числа с клавиатуры определяем его место в списке. Заметим, что при этом элемент может быть вставлен либо в начало списка, либо в конец его, либо во внутрь. Первый и второй случаи мы уже рассмотрели выше. Остановимся на третьем случае.
Для того чтобы вставить в список элемент со значением Digit между двумя элементами, нужно найти эти элементы и запомнить их адреса (первый адрес – в переменной dx, второй – в рх), после чего установить новые связи с переменной, в которой хранится значение Digit.
Графически это можно представить так:
Операторы, выполняющие данную задачу будут следующими:
New(x);
x^.Data:= Digit;
px^.Next:= x;
x^.Next:= dx;
Приведем процедуру InsInto, которая ищет место в списке и вставляет элемент, переданный ей как параметр. В результате сразу получается упорядоченный список. Адрес первого элемента списка хранится в глобальной переменной Head.
Procedure InsInto(Digit: integer; Var Head: Ukazatel);
Var
dx, px, x: Ukazatel;
Begin
New(x);
x^.Data:= Digit;
x^.Next:= Nil;
if Head = Nil
then {Если список пуст, то вставляем первый элемент}
Head:= x
else
{Если список не пуст, то просматриваем его до тех пор, пока не отыщется подходящее место для x^ или не закончится список}
Begin
dx:= Head;
px:= Head;
while (px<>Nil) and (px^.Data<=Digit) do
Begin
dx:= px;
px:=px^.Next;
End;
if px=Nil
then {Пройден весь список}
dx^.Next:= x {Элемент добавляется в конец списка}
else {Пройден не весь список}
Begin
x^.Next:= px;
if px=Head
then
Head:= x {Вставляем в начало списка}
else
dx^.Next:= x; {Вставляем внутрь списка}
End;
End;
End;
Стек и очередь. Назначение, варианты реализации и примеры применения.
Структурированные типы данных, такие, как массивы, множества, записи, представляют собой статические структуры, так как их размеры неизменны в течение всего времени выполнения программы. Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. Такие структуры данных называются динамическими, к ним относятся стеки, очереди, списки, деревья и другие. Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти ЭВМ и увеличивает время решения задач.
Каждая компонента любой динамической структуры представляет собой запись, содержащую по крайней мере два поля: одно поле типа указатель, а второе - для размещения данных. В общем случае запись может содержать не один, а несколько укзателей и несколько полей данных. Поле данных может быть переменной, массивом, множеством или записью. Для дальнейшего рассмотрения представим отдельную компоненту в виде:
где поле p - указатель;
поле D - данные.
Описание этой компоненты дадим следующим образом:
type
Pointer = ^Comp;
Comp = record
D:T;
pNext:Pointer
end;
здесь T - тип данных.
Рассмотрим основные правила работы с динамическими структурами данных типа стек, очередь и список, базируясь на приведенное описание компоненты.
Стеки
Стеком называется динамическая структура данных, добавление компоненты в которую и исключение компоненты из которой производится из одного конца, называемого вершиной стека. Стек работает по принципу
LIFO (Last-In, First-Out)
поступивший последним, обслуживается первым.
Обычно над стеками выполняется три операции:
Для формирования стека и работы с ним необходимо иметь две переменные типа указатель, первая из которых определяет вершину стека, а вторая - вспомогательная. Пусть описание этих переменных имеет вид:
var pTop, pAux: Pointer;
где pTop - указатель вершины стека;
pAux - вспомогательный указатель.
Начальное формирование стека выполняется следующими операторами:
Последний оператор или группа операторов записывает содержимое поля данных первой компоненты.
Добавление компоненты в стек призводится с использованием вспомогательного указателя:
Добавление последующих компонент производится аналогично.
Рассмотрим процесс выборки компонент из стека. Пусть к моменту начала выборки стек содержит три компоненты:
Первый оператор или группа операторов осуществляет чтение данных из компоненты - вершины стека. Второй оператор изменяет значение указателя вершины стека:
Как видно из рисунка, при чтении компонента удаляется из стека.
Пример. Составить программу, которая формирует стек, добавляет в него произвольное количество компонент, а затем читает все компоненты и выводит их на экран дисплея, В качестве данных взять строку символов. Ввод данных - с клавиатуры дисплея, признак конца ввода - строка символов END.
Очереди
Очередью называется динамическая структура данных, добавление компоненты в которую производится в один конец, а выборка осуществляется с другого конца. Очередь работает по принципу:
FIFO (First-In, First-Out)
поступивший первым, обслуживается первым.
Для формирования очереди и работы с ней необходимо иметь три переменные типа указатель, первая из которых определяет начало очереди, вторая - конец очереди, третья - вспомогательная.
Описание компоненты очереди и переменных типа указатель дадим следующим образом:
type
PComp=^Comp;
Comp=record
D:T;
pNext:PComp
end;
var
pBegin, pEnd, pAux: PComp;
где pBegin - указатель начала очереди, pEnd - указатель конца очереди, pAux - вспомогательный указатель.
Тип Т определяет тип данных компоненты очереди.
Дата публикования: 2015-02-03; Прочитано: 226 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!