Динамические списковые структуры

 

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

 

Type

link = ^zap;

dan =…;

zap = record;

pole1: link;

pole2: dan;

end;

 

Var

p: link;

 

link – это указатель на область памяти для записи переменных типа zap.

Тип zap оказывается записью, где имеются поля, содержащие информацию (типа dan) и одно поле pole1 типа link, т.е. указатель. Указатель указывает на следующую запись того же самого типа.

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

Образуется последовательность следующего вида (рис. 5):

 

 

Рис. 5. Последовательность записей в динамическом списке

 

Для заполнения полей можно использовать операторы присваивания:

 

pul^.имя поля:= значение;

 

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

Type

link = ^zap;

zap = record;

pole1: link;

pole2:integer;

end;

 

Var

z, p: link;

Begin

{Запись чисел}

z:=nil;

for k:=1 to 5 do

Begin

new(p);

p^.pole2:=k;

p^.pole1:=z;

z:=p;

end;

{Считывание в обратном порядке}

for k:=1 to 5 do

Begin

WriteLn(p^.pole2);

p:=p^.pole1;

end;

End.

 

Считывание чисел также можно осуществить следующим образом:

 

while p<> nil do

Begin

WriteLn(p^.pole2);

p:=p^.pole1;

end;

 

Пример. Построить список, элементы которого содержат квадраты чисел 1,2, …, n.

 

Type

cc=^zap;

zap = record;

pl1: integer;

pl2: cc;

end;

 

Var

p,q: cc;

i,n: integer;

 

Begin

WriteLn(‘введите n’);

ReadLn(n);

p:=nil;

for i:=n downto 1 do

Begin

New(q);

q^.pl1:=sqr(i);

q^.pl2:=p;

p:=q;

end;

q:=p;

while q<> nil do

Begin

Write(q^.pl1);

q:=q^.pl2;

end;

Dispose(p);

Dispose(q); }

End.

 

Пример. Построить список, состоящий из нечетного количества целых чисел. Вывести число, занимающее в данной последовательности центральную позицию.

Type

ck=^tip;

tip= record

inf: integer;

cled: ck;

end;

 

Var

p,q: ck;

i,j: integer;

 

Begin

p:=nil;

WriteLn(‘Введите нечетное количество целых чисел’, j);

for i:=1 to j do

Begin

New(q);

Read(q^.inf);

q^.cled:=p;

p=q;

end;

for i:=1 to j div 2 do

q:=q^.cled;

WriteLn(q^.inf);

End.

Пример. Построить список, состоящий из записей, содержащих сведения о студенте: ФИО, экзаменационные оценки по физике, математике и программированию.

Вывести список на экран в виде таблицы и подсчитать средний балл.

 

uses Crt;

Type

pst=^st;

 

st=record

fio: string[20];

math: integer;

phys: integer;

prog: integer;

pt: pst;

end;

 

Var

q, p: pst;

i, j, n: integer;

d: real;

 

Begin

ClrScr;

Write(‘Введите число записей’);

ReadLn(n);

p:=nil;

for i:=1 to n do

Begin

New(q);

WriteLn(‘Введите ФИО’);

ReadLn(q^.fio);

WriteLn(‘Введите оценку по математике’);

ReadLn(q^.math);

WriteLn(‘Введите оценку по физике’);

ReadLn(q^.phys);

WriteLn(‘Введите оценку по программированию’);

ReadLn(q^.prog);

q^.pt:=p;

p:=q;

end;

q:=p;

WriteLn;

for j:=1 to 56 do

Write(‘-‘);

WriteLn;

WriteLn(‘| fio stud | math | phys | prog | sr. ball |’);

for j:=1 to 56 do

Write('-');

WriteLn;

for i:=1 to n do

Begin

d:=(q^.math + q^.phys + q^.prog)/3;

WriteLn(‘| ‘, q^.fio:20, ‘ | ‘, q^.math:4, ‘ | ‘,q^.phys:4, ‘ |

‘,q^.prog:4, ‘ | ‘, d:8:2,’ |’);

q:=q^.pt;

end;

for j:=1 to 56 do

Write(‘-‘);

WriteLn;

Dispose(p);

Dispose(q);

ReadLn;

End.

Альтернативный вариант предыдущей программы, но список выводится в правильном порядке.

uses Crt;

Type

pst=^st;

st= record

fio: string[20];

math: integer;

phys: integer;

prog: integer;

pt: pst;

end;

 

Var

nach, q, p: pst;

i,j,n: integer;

d: real;

 

Begin

ClrScr;

Write(‘Введите число записей’);

ReadLn(n);

New(q);

for i:=1 to n do

Begin

q^.pt:=nil;

if i = 1 then nach:=q;

WriteLn(‘Введите ФИО’);

ReadLn(q^.fio);

WriteLn(‘Введите оценку по математике’);

ReadLn(q^.math);

WriteLn(‘Введите оценку по физике’);

ReadLn(q^.phys);

WriteLn(‘Введите оценку по программированию’);

ReadLn(q^.prog);

p:=q;

New(q);

if i<>n then p^.pt:=q

Else

Dispose(q);

end;

WriteLn;

for j:=1 to 56 do

Write(‘-‘);

WriteLn;

WriteLn(‘| fio stud | math | phys | prog | sr. ball |’);

for j:=1 to 56 do

Write(‘-‘);

WriteLn;

q:=nach;

while q<> nil do

Begin

d:= (q^.math + q^.phys + q^.prog)/3;

WriteLn(‘| ‘, q^.fio:20, ‘ | ‘, q^.math:4, ‘ | ‘,q^.phys:4,

‘ | ‘,q^.prog:4, ‘ | ‘, d:8:2,’ |’);

q:=q^.pt;

end;

for j:=1 to 56 do

Write(‘-‘);

WriteLn;

Dispose(p);

Dispose(q);

ReadLn;

end.

 

Использование модулей

 

Модуль –это автономно компилируемая программная единица, включающая в себя различные компоненты раздела описаний (типы, константы, переменные, процедуры и функции) и, возможно, некоторые исполняемые операторы инициирующей части. В модулях явным образом выделяется некоторая «видимая» интерфейсная часть, в которой сконцентрированы описания глобальных типов, констант и переменных, а также приводятся заголовки глобальных процедур и функций. Появление объектов в интерфейсной части делает их доступными для других модулей основной программы. Тела процедур и функций располагаются в исполняемой части модуля, которая может быть скрыта от пользователя.

Модули представляют собой прекрасный инструмент для разработки библиотек прикладных программ и мощное средство модульного программирования. Важная особенность модулей заключается в том, что компилятор Турб Паскаля размещает их программный код в отдельном сегменте памяти. Максимальная длина сегмента не может превышать 64 Кбайта, однако количеств одновременно используемых модулей ограничивается лишь доступной памятью, что дает возможность создавать весьма крупные программы.

 

Структура модуля

Модуль имеет следующую структуру:

unit <имя>;

Interface

<интерфейсная часть>

Implementation

<исполняемая часть>

Begin

<инициирующая часть>

End.

Здесь unit – зарезервированное слово (единица),начинающее заголовок модуля;

<имя> – имя модуля (правильный идентификатор);

interface – зарезервированное слово (интерфейс),начинающее интерфейсную часть модуля;

implementation – зарезервированное слово (выполнение),начинающее исполняемую часть;

begin – зарезервированное слово; начинает инициирующую часть модуля; конструкция begin<инициирующая часть> необязательна;

end — зарезервированное слово — признак конца модуля.

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

Заголовок модуля.

Заголовок модуля состоит из зарезервированного слова unit и следующего имени модуля. Для правильной работы среды Турбо Паскаля и возможности подключения средств, облегчающих разработку крупных программ, это имя должно совпадать с именем дискового файла, в который помещается исходный текст модуля. Если, например, имеем заголовок

unit Global;

то исходный текст соответствующего модуля должен размещаться в дисковом файле global.pas. Имя модуля служит для его связи с другими модулями и основной программой. Эта связь устанавливается специальным предложением

uses <список модулей>

Здесь uses – зарезервированное слово (использует); < список модулей > –список модулей, с которыми устанавливается связь; элементами списка являются имена модулей, отделяемые друг от друга запятыми, например:

uses CRT, Graph, Global;

Если объявление uses используется, оно должно открывать раздел описаний основной программы. Модули могут использовать другие модули. Предложение uses в модулях может следовать либо сразу за зарезервированным словом interface, либо сразу за словом implementation, либо, наконец, и там, и там (т.е. допускаются два объявления uses ).

Интерфейсная часть.

Интерфейсная часть открывается зарезервированным словом interface. В этой части содержатся объявления всех глобальных объектов модуля (типов, констант, переменных и подпрограмм), которые должны стать доступными основной программе и/или другим модулям. При объявлении глобальных подпрограмм в интерфейсной части указывается только их заголовок, например:

unit Cmplx;

Interface

Type

complex = record

re, im: real

end;

Procedure AddC (x, у: complex; var z: complex);

Procedure MulC (x, у: complex; var z: complex);

 

Если теперь в основной программе написать предложение

Uses Cmplx;

то в программе станут доступными тип complex и две процедуры – AddC и MulC из модуля Cmplx.

Исполняемая часть.

Исполняемая часть начинается зарезервированным словом implemetation и содержит описания подпрограмм, объявленных в интерфейсной части. В ней могут объявляться локальные для модуля объекты – вспомогательные типы, константы, переменные и блоки, а также метки, если они используются в инициирующей части.

Описанию подпрограммы, объявленной в интерфейсной части модуля, в исполняемой части должен предшествовать заголовок, в котором можно опускать список формальных переменных (и тип результата для функции), так как они уже описаны в интерфейсной части. Но если заголовок подпрограмм приводится в полном виде, т.е. со списком формальных параметров и объявлением результата, он должен совпадать с заголовком, объявленным в интерфейсной части, например:

unit Cmplx;

Interface

Type

complex = record

re, im: real;

end;

procedure AddC (x, у: complex; var z: complex);

Implementation

procedure AddC;

Begin

z.re:= x.re + y.re;

z.im:= x.im + у.im;

end;

End.

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

Инициализирующая часть.

Инициализирующая часть завершает модуль. Она может отсутствовать вместе с начинающим ее словом begin или быть пустой – тогда за begin сразу следует признак конца модуля (слово end и следующая за ним точка).

В инициализирующей части размещаются исполняемые операторы, содержащие некоторый фрагмент программы. Эти операторы исполняются до передачи управления основной программе и обычно используются для подготовки ее к работе. Например, в них могут инициализироваться переменные, открываться нужные файлы и т.п.:

unit FileText;

Interface

procedure Print (s: string);

Implementation

Var

f: text;

Const

name = 'output.txt';

procedure Print;

Begin

WriteLn(f, s);

end;

{ Начало инициирующей части: }

Begin

Assign (f, name);

ReWrite(f);

{ Конец инициирующей части }

End.

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

Компиляция модулей.

При компиляции модуля или основной программы все упоминающиеся в предложении uses модули должны быть предварительно откомпилированы, и результаты компиляции помещены в одноименные файлы с расширением tpu (Turbo Pascal Unit). Например:

uses Global;

Если в программе (модуле) имеется такое предложение, то на диске должен находиться файл global.tpu. Данные файл создается автоматически при компиляции модуля global.

Подключение модулей к основной программе и их возможная компиляция осуществляются в порядке их объявления в предложении uses. При переходе к очередному модулю система предварительно отыскивает все модули, на которые он ссылается. Ссылки модулей друг на друга могут образовывать древовидную структуру любой сложности, однако запрещается явное или косвенное обращение модуля к самому себе. Например, недопустимы следующие объявления:

unit A; unit В;

Interface interface

uses В; uses А;

… …