Информатика и информационные технологии

Размещаются динамические переменные в динамической области памяти (heap-области). Динамическая переменная не указывается  явно в описаниях переменных, и  к ней нельзя обратиться по имени. Доступ к таким переменным осуществляется с помощью указателей и ссылок.

Ссылочный тип (указатель) определяет множество значений, которые указывают  на динамические переменные определенного  типа, называемого базовым типом. Переменная ссылочного типа содержит адрес динамической переменной в памяти. Если базовый тип является еще не описанным идентификатором, то он должен быть описан в той же самой части описания типов, что и тип-указатель.

Зарезервированное слово nil обозначает константу со значением указателя, которая ни на что не указывает.

Приведем пример описания динамических переменных.

var p1, p2 : ^real;

p3, p4 : ^integer;

…

2. Работа с динамической памятью. Нетипизированные указатели

Процедуры и  функции работы с динамической памятью

1. Процедура New(var p: Pointer).

Выделяет место в динамической области памяти для размещения динамической переменной р^Л, и ее адрес присваивает указателю р.

2. Процедура Dispose(varp: Pointer).

Освобождает участок памяти, выделенный для размещения динамической переменной процедурой New, и значение указателя р становится неопределенным.

3. Процедура GetMem(varp: Pointer; size: Word).

Выделяет участок памяти в heap-области, присваивает адрес его начала указателю р, размер участка в  байтах задается параметром size.

4. Процедура FreeMem(var p: Pointer; size: Word).

Освобождает участок памяти, адрес  начала которого определен указателем р, а размер – параметром size. Значение указателя р становится неопределенным.

5. Процедура Mark(var p: Pointer)

Записывает в указатель р адрес начала участка свободной динамической памяти на момент ее вызова.

6. Процедура Release(var p: Pointer)

Освобождает участок динамической памяти, начиная с адреса, записанного  в указатель р процедурой Mark, т. е. очищает ту динамическую память, которая была занята после вызова процедуры Mark.

7. Функция MaxAvaikLongint

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

8. Функция MemAvaikLongint

Возвращает полный объем свободной  динамической памяти в байтах.

9. Вспомогательная функция SizeOf(X):Word

Возвращает объем в байтах, занимаемый X, причем X может быть либо именем переменной любого типа, либо именем типа.

Встроенный тип Pointer обозначает нетипизированный указатель, т. е. указатель, который не указывает ни на какой определенный тип. Переменные типа Pointer могут быть разыменованы: указание символа ^ после такой переменной вызывает появление ошибки.

Как и значение, обозначаемое словом nil, значения типа Pointer совместимы со всеми  другими типами указателей.

 

 

 

 

ЛЕКЦИЯ № 8. Абстрактные структуры данных

 

1. Абстрактные структуры данных

Структурированные типы данных, такие  как массивы, множества, записи, представляют собой статические структуры, так  как их размеры неизменны в  течение всего времени выполнения программы.

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

Описание динамических структур с  помощью массивов, записей и файлов приводит к неэкономному использованию памяти ЭВМ и увеличивает время решения задач.

Каждая компонента любой динамической структуры представляет собой запись, содержащую, по крайней мере, два  поля: одно поле типа «указатель», а  второе – для размещения данных. В общем случае запись может содержать не один, а несколько указателей и несколько полей данных. Поле данных может быть переменной, массивом, множеством или записью.

Если в указующей части содержится адрес одного элемента списка, то список называется однонаправленным (или односвязным). Если же он содержит две компоненты, то двусвязным. Над списками можно проводить различные операции, например:

1) добавление элемента к списку;

2) удаление элемента из списка с заданным ключом;

3) поиск элемента с заданным значением ключевого поля;

4) сортировка элементов списка;

5) деление списка на два и более списков;

6) объединение двух и более списков в один;

7) другие операции.

Однако, как правило, необходимости  во всех операциях при решении  различных задач не возникает. Поэтому в зависимости от основных операций, которые необходимо применить, существуют различные виды списков. Наиболее популярные из них – это стек и очередь.

2. Стеки

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

Обычно над стеками выполняется  три операции:

1) начальное формирование стека (запись первой компоненты);

2) добавление компоненты в стек;

3) выборка компоненты (удаление).

Для формирования стека и работы с ним необходимо иметь две  переменные типа «указатель», первая из которых определяет вершину стека, а вторая – вспомогательная.

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

Program STACK;

uses Crt;

type

Alfa = String[10];

PComp = ^Comp;

Comp = Record

sD : Alfa;

pNext : PComp

end;

var

pTop : PComp;

sC : Alfa;

Procedure CreateStack(var pTop : PComp; var sC : Alfa);

begin

New(pTop);

pTop^.pNext := NIL;

pTop^.sD := sC;

end;

Procedure AddComp(var pTop : PComp; var sC : Alfa);

var pAux : PComp;

begin

NEW(pAux);

pAux^.pNext := pTop;

pTop := pAux;

pTop^.sD := sC;

end;

Procedure DelComp(var pTop : PComp; var sC : ALFA);

begin

sC := pTop^.sD;

pTop := pTop^.pNext;

end;

begin

Clrscr;

writeln(' ВВЕДИ СТРОКУ ');

readln(sC);

CreateStack(pTop, sC);

repeat

writeln(' ВВЕДИ СТРОКУ ');

readln(sC);

AddComp(pTop, sC);

until sC = 'END';

writeln('****** ВЫВОД РЕЗУЛbТАТОВ ******');

repeat

DelComp(pTop, sC);

writeln(sC);

until pTop = NIL;

end.

3. Очереди

Очередью называется динамическая структура данных, добавление компоненты в которую производится в один конец, а выборка осуществляется с другого конца. Очередь работает по принципу FIFO (First-In, First-Out) – «Поступивший первым, обслуживается первым».

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

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

Program QUEUE;

uses Crt;

type

Alfa = String[10];

PComp = ^Comp;

Comp = record

sD : Alfa;

pNext : PComp;

end;

var

pBegin, pEnd : PComp;

sC : Alfa;

Procedure CreateQueue(var pBegin,pEnd:PComp; var sC:Alfa);

begin

New(pBegin);

pBegin^.pNext := NIL;

pBegin^.sD := sC;

pEnd := pBegin;

end;

Procedure AddQueue(var pEnd : PComp; var sC : Alfa);

var pAux : PComp;

begin

New(pAux);

pAux^.pNext := NIL;

pEnd^.pNext := pAux;

pEnd := pAux;

pEnd^.sD := sC;

end;

Procedure DelQueue(var pBegin : PComp; var sC : Alfa);

begin

sC := pBegin^.sD;

pBegin := pBegin^.pNext;

end;

begin

Clrscr;

writeln(' ВВЕДИ СТРОКУ ');

readln(sC);

CreateQueue(pBegin, pEnd, sC);

repeat

writeln(' ВВЕДИ СТРОКУ ');

readln(sC);

AddQueue(pEnd, sC);

until sC = 'END';

writeln(' ***** ВЫВОД РЕЗУЛbТАТОВ *****');

repeat

DelQueue(pBegin, sC);

writeln(sC);

until pBegin = NIL;

end.

 

 

 

 

ЛЕКЦИЯ № 9. Древовидные структуры данных

 

1. Древовидные структуры данных

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

Если использовать рекурсивное определение, предложенное Н. Виртом, то древовидная структура данных с базовым типом t – это либо пустая структура, либо узел типа t, с которым связано конечное множество древовидных структур с базовым типом t, называемых поддеревьями.

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

Если узел у находится непосредственно  под узлом х, то узел у называется непосредственным потомком узла х, а  х – непосредственным предком  узла у, т. е., если узел х находится на i-ом уровне, то соответственно узел у находится на (i + 1) – ом уровне.

Максимальный уровень узла дерева называется высотой или глубиной дерева. Предка не имеет только один узел дерева – его корень.

Узлы дерева, у которых не имеется  потомков, называются терминальными узлами (или листами дерева). Все остальные узлы называются внутренними узлами. Количество непосредственных потомков узла определяет степень этого узла, а максимально возможная степень узла в данном дереве определяет степень дерева.

Предков и потомков нельзя поменять местами, т. е. связь исходного и порожденного действует только в одном направлении.

Если пройти от корня дерева к некоторому конкретному  узлу, то количество ветвей дерева, которое  при этом будет пройдено, называется длиной пути для этого узла. Если все ветви (узлы) у дерева упорядочены, то дерево называется упорядоченным.

Частным случаем  древовидных структур являются бинарные деревья. Это деревья, в которых  каждый потомок имеет не более  двух потомков, называемых левым и  правым поддеревьями. Таким образом, бинарное дерево – это древовидная структура, степень которой равна двум.

Упорядоченность бинарного дерева определяется по следующему правилу: каждому узлу соответствует  свое ключевое поле, и для каждого  узла значение ключа больше всех ключей в его левом поддереве и меньше всех ключей в его правом поддереве.

Дерево, степень  которого больше двух, называется сильноветвящимся.

2. Операции над деревьями

Далее будем рассматривать все  операции применительно к бинарным деревьям.

I. Построение  дерева

Приведем алгоритм построения упорядоченного дерева.

1. Если дерево пусто, то данные переносятся в корень дерева. Если же дерево не пусто, то осуществляется спуск по одной из его ветвей таким образом, чтобы упорядоченность дерева не нарушалась. В результате новый узел становится очередным листом дерева.

2. Чтобы добавить узел в уже существующее дерево, можно воспользоваться вышеприведенным алгоритмом.

3. При удалении узла из дерева следует быть внимательным. Если удаляемый узел является листом, или же имеет только одного потомка, то операция проста. Если же удаляемый узел имеет двух потомков, то необходимо будет найти узел среди его потомков, который можно будет поставить на его место. Это нужно в силу требования упорядоченности дерева.

Можно поступить  таким образом: поменять удаляемый узел местами с узлом, имеющем самое большое значение ключа в левом поддереве, или с узлом, имеющем самое малое значение ключа в правом поддереве, а затем удалить искомый узел как лист.

II. Поиск узла  с заданным значением ключевого поля

При осуществлении этой операции необходимо совершить обход дерева. Необходимо учитывать различные формы записи дерева: префиксную, инфиксную и  постфиксную.

Возникает вопрос: каким образом представить узлы дерева, чтобы было наиболее удобно работать с ними? Можно представлять дерево с помощью массива, где каждый узел описывается величиной комбинированного типа, у которой информационное поле символьного типа и два поля ссылочного типа. Но это не совсем удобно, так как деревья имеют большое количество узлов, заранее не определенное. Поэтому лучше всего при описании дерева использовать динамические переменные. Тогда каждый узел представляется величиной одного типа, которая содержит описание заданного количества информационных полей, а количество соответствующих полей должно быть равно степени дерева. Логично отсутствие потомков определять ссьшкой nil. Тогда на языке Pascal описание бинарного дерева может выглядеть следующим образом: