Лекции по программированию на Паскале. Часть 5

36. Д И Н А М И Ч Е С К И Е П Е Р Е М Е Н Н Ы Е Статической переменной (статически размещенной) называется описан-ная явным образом в программе переменная, обращение к ней осуществля-ется по имени. Место в памяти для размещения статических переменныхопределяется при компиляции программы. В отличие от таких статических переменных в программах, написанныхна языке ПАСКАЛЬ, могут быть созданы динамические переменные. Основ-ное свойство динамических переменных заключается в том, что они соз-даются и память для них выделяется во время выполнения программы.Размещаются динамические переменные в динамической области памяти(heap - области). Динамическая переменная не указывается явно в описаниях переменныхи к ней нельзя обратиться по имени. Доступ к таким переменным осу-ществляется с помощью указателей и ссылок. Работа с динамической областью памяти в TURBO PASCAL реализуется спомощью процедур и функций New, Dispose, GetMem, FreeMem, Mark,Release, MaxAvail, MemAvail, SizeOf. Процедура New(var p: Pointer) выделяет место в динамической об-ласти памяти для размещения динамической переменной p^ и ее адресприсваивает указателю p. Процедура Dispose(var p: Pointer) освобождает участок памяти,выделенный для размещения динамической переменной процедурой New, изначение указателя p становится неопределенным. Проуедура GetMem(var p: Pointer; size: Word) выделяет участокпамяти в heap - области, присваивает адрес его начала указателю p,размер участка в байтах задается параметром size. Процедура FreeMem(var p: Pointer; size: Word) освобождает учас-ток памяти, адрес начала которого определен указателем p, а размер -параметром size. Значение указателя p становится неопределенным. Процедура Mark(var p: Pointer) записывает в указатель p адресначала участка свободной динамической памяти на момент ее вызова. Процедура Release(var p: Pointer) освобождает участок динамичес-кой памяти, начиная с адреса, записанного в указатель p процедуройMark, то-есть, очищает ту динамическую память, которая была занятапосле вызова процедуры Mark. Функция MaxAvail: Longint возвращает длину в байтах самого длинно-го свободного участка динамической памяти. Функция MemAvail: Longint полный объем свободной динамической па-мяти в байтах. Вспомогательная функция SizeOf(X): Word возвращает объем в бай-тах, занимаемый X, причем X может быть либо именем переменной любоготипа, либо именем типа. Рассмотрим некоторые примеры работы с указателями. var p1, p2: ^Integer; Здесь p1 и p2 - указатели или пременные ссылочного типа. p1:=NIL; p2:=NIL; После выполнения этих операторов присваивания указатели p1 и p2 небудут ссылаться ни на какой конкретный объект. New(p1); New(p2); Процедура New(p1) выполняет следующие действия: -в памяти ЭВМ выделяется участок для размещения величины целоготипа; -адрес этого участка присваивается переменной p1: г===== г===== ¦ *--¦--------->¦ ¦ L=====- L=====- p1 p1^ Аналогично, процедура New(p2) обеспечит выделение участка памяти,адрес которого будет записан в p2: г===== г===== ¦ *--¦--------->¦ ¦ L=====- L=====- p2 p2^ После выполнения операторов присваивания p1^:=2; p2^:=4; в выделенные участки памяти будут записаны значения 2 и 4 соответ-ственно: г===== г===== ¦ *--¦--------->¦ 2 ¦ L=====- L=====- p1 p1^ г===== г===== ¦ *--¦--------->¦ 4 ¦ L=====- L=====- p2 p2^ В результате выполнения оператора присваивания p1^:=p2^; в участок памяти, на который ссылается указатель p1, будет записанозначение 4: г===== г===== ¦ *--¦--------->¦ 4 ¦ L=====- L=====- p1 p1^ г===== г===== ¦ *--¦--------->¦ 4 ¦ L=====- L=====- p2 p2^ После выполнения оператора присваивания p2:=p1; оба указателя будут содержать адрес первого участка памяти: г===== г===== ¦ *--¦--------->¦ 4 ¦ L=====- --->L=====- p1 ¦ p1^ p2^ ¦ г===== ¦ ¦ *--¦------- L=====- p2 Переменные p1^, p2^ являются динамическими, так как память для нихвыделяется в процессе выполнения программы с помощью процедуры New. Динамические переменные могут входить в состав выражений, напри-мер: p1^:=p1^+8; Write('p1^=',p1^:3); Пример. В результате выполнения программы: Program DemoPointer; var p1,p2,p3:^Integer; begin p1:=NIL; p2:=NIL; p3:=NIL; New(p1); New(p2); New(p3); p1^:=2; p2^:=4; p3^:=p1^+Sqr(p2^); writeln('p1^=',p1^:3,' p2^=',p2^:3,' p3^=',p3^:3); p1:=p2; writeln('p1^=',p1^:3,' p2^=',p2^:3) end. на экран дисплея будут выведены результаты: p1^= 2 p2^= 4 p3^= 18p1^= 4 p2^= 4 37. Д И Н А М И Ч Е С К И Е С Т Р У К Т У Р ЫД А Н Н Ы Х Структурированные типы данных, такие, как массивы, множества, за-писи, представляют собой статические структуры, так как их размерынеизменны в течение всего времени выполнения программы. Часто требуется, чтобы структуры данных меняли свои размеры в ходерешения задачи. Такие структуры данных называются динамическими, кним относятся стеки, очереди, списки, деревья и другие. Описание ди-намических структур с помощью массивов, записей и файлов приводит кнеэкономному использованию памяти ЭВМ и увеличивает время решения за-дач. Каждая компонента любой динамической структуры представляет собойзапись, содержащую по крайней мере два поля: одно поле типа указа-тель, а второе - для размещения данных. В общем случае запись можетсодержать не один, а несколько укзателей и несколько полей данных.Поле данных может быть переменной, массивом, множеством или записью. Для дальнейшего рассмотрения представим отдельную компоненту в ви-де: г===== ¦ D ¦ ¦=====¦ ¦ p ¦ L=====-где поле p - указатель; поле D - данные. Описание этой компоненты дадим следующим образом: type Pointer = ^Comp; Comp = record D:T; pNext:Pointer end; здесь T - тип данных. Рассмотрим основные правила работы с динамическими структурамиданных типа стек, очередь и список, базируясь на приведенное описаниекомпоненты. 38. С Т Е К И Стеком называется динамическая структура данных, добавление компо-ненты в которую и исключение компоненты из которой производится изодного конца, называемого вершиной стека. Стек работает по принципу LIFO (Last-In, First-Out) - поступивший последним, обслуживается первым. Обычно над стеками выполняется три операции: -начальное формирование стека (запись первой компоненты); -добавление компоненты в стек; -выборка компоненты (удаление). Для формирования стека и работы с ним необходимо иметь две пере-менные типа указатель, первая из которых определяет вершину стека, авторая - вспомогательная. Пусть описание этих переменных имеет вид: var pTop, pAux: Pointer; где pTop - указатель вершины стека; pAux - вспомогательный указатель. Начальное формирование стека выполняется следующими операторами: г===== г===== New(pTop); ¦ *--¦--- ¦ ¦ L=====- ¦ ¦=====¦ pTop L-->¦ ¦ L=====- г===== г===== pTop^.pNext:=NIL; ¦ *--¦--- ¦ ¦ L=====- ¦ ¦=====¦ pTop L-->¦ NIL ¦ L=====- г===== г===== pTop^.D:=D1; ¦ *--¦--- ¦ D1 ¦ L=====- ¦ ¦=====¦ pTop L-->¦ NIL ¦ L=====- Последний оператор или группа операторов записывает содержимоеполя данных первой компоненты. Добавление компоненты в стек призводится с использованием вспо-могательного указателя: г===== г===== г===== New(pAux); ¦ *--¦--- ¦ ¦ ----¦--* ¦ L=====- ¦ ¦=====¦ ¦ L=====- pTop ¦ ¦ ¦<--- pAux ¦ L=====- ¦ ¦ г===== ¦ ¦ D1 ¦ ¦ ¦=====¦ L-->¦ NIL ¦ L=====- г===== г===== г===== pAux^.pNext:=pTop; ¦ *--¦--- ¦ ¦ ----¦--* ¦ L=====- ¦ ¦=====¦<--- L=====- pTop ¦ ¦ *--¦- pAux ¦ L=====- ¦ ¦ ¦ ¦ г===== ¦ ¦ ¦ D1 ¦ ¦ ¦ ¦=====¦ ¦ L-->¦ NIL ¦<- L=====- г===== г===== г===== pTop:=pAux; ¦ *--¦--- ¦ ¦ ----¦--* ¦ L=====- ¦ ¦=====¦<--- L=====- pTop L-->¦ *--¦- pAux L=====- ¦ ¦ г===== ¦ ¦ D1 ¦ ¦ ¦=====¦ ¦ ¦ NIL ¦<- L=====- г===== г===== pTop^.D:=D2; ¦ *--¦--- ¦ D2 ¦ L=====- ¦ ¦=====¦ pTop L-->¦ *--¦- L=====- ¦ ¦ г===== ¦ ¦ D1 ¦ ¦ ¦=====¦ ¦ ¦ NIL ¦<- L=====- Добавление последующих компонент производится аналогично. Рассмотрим процесс выборки компонент из стека. Пусть к моменту на-чала выборки стек содержит три компоненты: г===== г===== ¦ *--¦--- ¦ D3 ¦ L=====- ¦ ¦=====¦ pTop L-->¦ *--¦- L=====- ¦ ¦ г===== ¦ ¦ D2 ¦ ¦ ¦=====¦ ¦ --¦--* ¦<- ¦ L=====- ¦ ¦ г===== ¦ ¦ D1 ¦ ¦ ¦=====¦ L>¦ NIL ¦ L=====- Первый оператор или группа операторов осуществляет чтение данныхиз компоненты - вершины стека. Второй оператор изменяет значение ука-зателя вершины стека: г===== г===== D3:=pTop^.D; ¦ *--¦--- ¦ D3 ¦ pTop:=pTop^.pNext; L=====- ¦ ¦=====¦ pTop ¦ ¦ ¦ ¦ L=====- ¦ ¦ г===== ¦ ¦ D2 ¦ ¦ ¦=====¦ L-->¦ *--¦- L=====- ¦ ¦ г===== ¦ ¦ D1 ¦ ¦ ¦=====¦ ¦ ¦ NIL ¦<- L=====- Как видно из рисунка, при чтении компонента удаляется из стека. Пример. Составить программу, которая формирует стек, добавляет внего произвольное количество компонент, а затем читает все компонентыи выводит их на экран дисплея, В качестве данных взять строку симво-лов. Ввод данных - с клавиатуры дисплея, признак конца ввода - строкасимволов 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('****** ВЫВОД РЕЗУЛЬТАТОВ ******'); repeat DelComp(pTop,sC); writeln(sC); until pTop = NIL end. 39. О Ч Е Р Е Д И Очередью называется динамическая структура данных, добавление ком-поненты в которую производится в один конец, а выборка осуществляетсяс другого конца. Очередь работает по принципу: FIFO (First-In, First-Out) - поступивший первым, обслуживается первым. Для формирования очереди и работы с ней необходимо иметь три пере-менные типа указатель, первая из которых определяет начало очереди,вторая - конец очереди, третья - вспомогательная. Описание компоненты очереди и переменных типа указатель дадим сле-дующим образом: type PComp=^Comp; Comp=record D:T; pNext:PComp end; var pBegin, pEnd, pAux: PComp; где pBegin - указатель начала очереди, pEnd - указатель конца очере-ди, pAux - вспомогательный указатель. Тип Т определяет тип данных компоненты очереди. Начальное формирование очереди выполняется следующими операторами: г===== г===== г===== New(pBegin); ¦ *--¦--- ¦ ¦ ¦ ¦ L=====- ¦ ¦=====¦ L=====- pBegin L-->¦ ¦ pEnd L=====- г===== г===== г===== pBegin^.pNext:=NIL; ¦ *--¦--- ¦ ¦ ¦ ¦ L=====- ¦ ¦=====¦ L=====- pBegin L-->¦ NIL ¦ pEnd L=====- г===== г===== г===== pBegin^.D:=D1; ¦ *--¦--- ¦ D1 ¦ ¦ ¦ L=====- ¦ ¦=====¦ L=====- pBegin L-->¦ NIL ¦ pEnd L=====- г===== г===== г===== pEnd:=pBegin; ¦ *--¦--- ¦ D1 ¦ ----¦--* ¦ L=====- ¦ ¦=====¦ ¦ L=====- pBegin L-->¦ NIL ¦<--- pEnd L=====- Добавление компоненты в очередь производится в конец очереди: New(pAux); г===== г===== г===== г===== г=====¦ *--¦--- ¦ D1 ¦ ----¦--* ¦ ¦ ¦ ----¦--* ¦L=====- ¦ ¦=====¦ ¦ L=====- ¦=====¦ ¦ L=====-pBegin L-->¦ NIL ¦<--- pEnd ¦ ¦<--- pAux L=====- L=====- pAux^.pNext:=NIL; г===== г===== г===== г===== г=====¦ *--¦--- ¦ D1 ¦ ----¦--* ¦ ¦ ¦ ----¦--* ¦L=====- ¦ ¦=====¦ ¦ L=====- ¦=====¦ ¦ L=====-pBegin L-->¦ NIL ¦<--- pEnd ¦ NIL ¦<--- pAux L=====- L=====- pBegin^.pNext:=pAux; г===== г===== г===== г===== г=====¦ *--¦--- ¦ D1 ¦ ----¦--* ¦ ¦ ¦ ----¦--* ¦L=====- ¦ ¦=====¦ ¦ L=====- ¦=====¦ ¦ L=====-pBegin L-->¦ * ¦<--- pEnd ¦ NIL ¦<--- pAux L=====- L=====- ¦ ^ ¦ ¦ L---------------------------- pEnd:=pAux; г===== г===== г===== г===== г=====¦ *--¦--- ¦ D1 ¦ ¦ *--¦--- ¦ ¦ ----¦--* ¦L=====- ¦ ¦=====¦ L=====- ¦ ¦=====¦ ¦ L=====-pBegin L-->¦ * ¦ pEnd L-->¦ NIL ¦<--- pAux L=====- L=====- ¦ ^ ¦ ¦ L---------------------------- pEnd^.D:=D2; г===== г===== г===== г=====¦ *--¦--- ¦ D1 ¦ ¦ D2 ¦ ----¦--* ¦L=====- ¦ ¦=====¦ ¦=====¦ ¦ L=====-pBegin L-->¦ *--¦-------------------->¦ NIL ¦<--- pEnd L=====- L=====- Добавление последующих компонент производится аналогично. Выборка компоненты из очереди осуществляется из начала очереди,одновременно компонента исключается из очереди. Пусть в памяти ЭВМсформирована очередь, состоящая из трех элементов: г===== г===== г===== г===== г=====¦ *--¦--- ¦ D1 ¦ ¦ D2 ¦ ¦ D3 ¦ ----¦--* ¦L=====- ¦ ¦=====¦ ¦=====¦ ¦=====¦ ¦ L=====-pBegin L-->¦ *--¦------>¦ *--¦------>¦ NIL ¦<--- pEnd L=====- L=====- L=====- Выборка компоненты выполняется следующими операторами: D1:=pBegin^.D; pBegin:=pBegin^.pNext; г===== г===== г===== г===== г=====¦ *--¦--- ¦ D1 ¦ ¦ D2 ¦ ¦ D3 ¦ ----¦--* ¦L=====- ¦ ¦=====¦ ¦=====¦ ¦=====¦ ¦ L=====-pBegin ¦ ¦ ¦ --->¦ *--¦------>¦ NIL ¦<--- pEnd ¦ L=====- ¦ L=====- L=====- ¦ ¦ L-------------- Пример. Составить программу, которая формирует очередь, добавляетв нее произвольное количество компонент, а затем читает все компонен-ты и выводит их на экран дисплея. В качестве данных взять строку сим-волов. Ввод данных - с клавиатуры дисплея, признак конца ввода -строка символов 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(' ***** ВЫВОД РЕЗУЛЬТАТОВ *****'); repeat DelQueue(pBegin,sC); writeln(sC); until pBegin=NIL end.