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

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

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 pnil 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 qnil 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 in 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 qnil 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и следующего имени модуля. Для правильной работы среды Турбо Паскаля и возможности подключения средств, облегчающих разработку крупных программ, это имя должно совпадать с именем дискового файла, в который помещается исходный текст модуля. Если, например, имеем заголовок

unitGlobal;

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

uses

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

usesCRT, Graph, Global;

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

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

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

unitCmplx;

Interface

Type

complex = record

re, im : real

end;

ProcedureAddC (x, у : complex; varz : complex);

ProcedureMulC (x, у : complex; varz : complex);

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

UsesCmplx;

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

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

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

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

unitCmplx;

Interface

Type

complex = record

re, im : real;

end;

procedureAddC (x, у : complex; varz : complex);

Implementation

procedureAddC;

Begin

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

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

end;

End.

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

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

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

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

unitFileText;

Interface

procedurePrint (s : string);

Implementation

Var

f: text;

Const

name = 'output.txt';

procedurePrint;

Begin

WriteLn(f, s);

end;

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

Begin

Assign (f, name);

ReWrite(f);

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

End.

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

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

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

uses Global;

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

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

unitA; unitВ;

Interface interface

usesВ; usesА;

… …

Анатомо-фізіологічні особливості
Причини початок нац.визвольної боротьби під проводом Б.Хмельницького
Навантаження породи
ОСТРЫЕ РАССТРОЙСТВА ПИЩЕВАРЕНИЯ
Обов’язки і права практичного психолога
Облік операцій реалізації заставленого майна при неповерненні кредиту позичальником.
ПСИХИЧЕСКИЕ РАССТРОЙСТВА ПРИ ЧЕРЕПНО-МОЗГОВЫХ ТРАВМАХ
Особенности возмещения вреда, причиненного вследствие недостатков товаров, работ и услуг.
Предупредительные сигнальные знаки (ИСИ пп.74 – 78)
Правила установки высотомеров
Регуляция секреции кишечного сока
Договор как согласованное волеизъявление.
Зміст звіту
Ситали. властивості, Особливості використання.
Фізіологічна характеристика системи АВО крові. Умови сумісності крові донора і реципієнта. Проби, перед переливанням крові.
Объектом налогообложения сбором является фактический объем воды использующийся водопользователями, с учетом объема потерь воды в их системах водоснабжения.
У промисловості будівельних матеріалів
РОЛЬ БІБЛІОТЕКИ В СИСТЕМІ ІНФОРМАЦІЙНОГО ОБСЛУГОВУВАННЯ МОЛОДІ
Лекция 2. Парная линейная регрессия.
Завдання 4
Трудова мотивація — це процес вибору людиною обгрунтування свого способу участі в трудовій діяльності.
Введення-виведення, кероване перериваннями
Що подається у випарник
Главная Страница