Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
TP_теория и практикум.doc
Скачиваний:
11
Добавлен:
20.08.2019
Размер:
862 Кб
Скачать
☆

Ссылочные типы (указатели)

Для работы с динамическими объектами используется ссылочный тип (или тип указатель). При этом в программе все действия над динамическими объектами описываются с помощью обыкновенных статических переменных. Но тип этих переменных – указатель (ссылочный тип). Это Pointer.

Тип Pointer – это фактически адрес хранения объекта.

Указатель может иметь значение адреса статической или динамической переменной. Особое значение указателя -<NIL>- - указатель, который указывает «в пустоту», в ничто.

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

В описании указателя P вводится тип T, на данные которого будет указатель P:

Type P=^T;

Множество значений типа P – неопределенное множество так называющихся идентифицирующихся величин (каждая из которых указывает на переменную типа T), в которое добавлено особое значение – Nil, которое ни на что не указывает.

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

Указатели служат средством для формирования сложных и одновременно гибких структур данных.

Для объявления указателя используется значок ^, который помещается перед типом:

Var P1: ^Integer;

P2: ^Integer;

Если, например, указатель (дадим ему имя Ptr) описан как

Var Ptr : P;

и ему было присвоено некоторое значение, то Ptr^ будет обозначать динамическую переменную.

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

Type P=^integer;

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

Имя в программе определение ссылочного типа, можно по общим правилам описать переменные этого типа. Ссылочные типы в описании переменных можно задавать как посредством идентификаторов, так и явно, например:

Пример. Type P= ^ integer;

Person = record

Word = 2 байта Name, SecondName, SurName: string [20],

0…65000 Sex: (Male, Female);

Speciality: word; {индекс специальности}

End; {of record}

Omen: ^ Person;

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

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

Type P= ^ Base;

Даже если тип Base еще не был описан. Однако в таком случае тип Base должен быть описан далее в такой же части описания типов:

Type P= ^ Base;

Base = record

X, Y: real

End; {of record}.

Реально значение ссылочных типов содержат адреса расположения в памяти конкретных значений базового типа. Для того, чтобы присвоить переменной ссылочного типа некоторое значение, можно воспользоваться операцией взятия указателя, которая строится из знака этой операции – символа @ (амперсант) и переменной любого типа.

Пример Var i: integer; {описание переменной}

P1: ^ integer;

…………….

P1: = @i; {указатель на целое}

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

P1: = I (P1 = адрес I)

J: = P1 (j= i)

P1

указатель

I

целое

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

Пример Var A: array [1..10] of integer;

Для этого примера конструкция @ A[i] имеет смысл «указателя на i-ое целое в массиве A» и может участвовать в присваивании:

P1:= @ A[i];

Ссылочные типы могут образовывать от любых типов, поэтому допустимо определение вида «указатель на указатель».

Пример type P= ^ integer;

P1 = ^ integer;

Var F: ^ P;

I: integer;

Здесь переменная F в качестве своих возможных значений имеет множество указателей, ссылающихся на указатели, которые, в свою очередь, ссылаются на целые значения. Рассмотрим присваивание:

P1: = @ A [i]; F: = P1?

F

указатель

P1

указатель

i

указатель

С реди всех возможных указателей в языке выделяется один специальный указатель, который «никуда не указывает». Это можно себе представить таким образом: в адресном пространстве оперативной памяти выделяется один адрес, в котором заведомо не может быть размещена никакая переменная. На это место в памяти и ссылается такой пустой или «нулевой» указатель, который обозначается служебным словом nil. Указатель nil считается константой, совместимый с любым ссылочным типом. Иными словами, это значение можно присваивать любому указательному типу. В качестве Nil используется значение .

Над значениями ссылочных типов допускаются две операции сравнения: на равенство и неравенство; эти операции проверяют, ссылаются ли два указатель на одно и тоже место в памяти, и обозначаются обычным образом – знаками «=» и «<>», например:

B: = P1 = P2; {B – логическая переменная}

……………….

If P1<> nil then…

Доступ переменной по указателю.

Пусть P1:= @i {указателю P1присвоить значение адреса i}

Для доступа к переменной i имеются две возможности:

  1. Использовать для доступа идентификатор i, например, i:= i+2. Этот оператор считывает текущее значение i и увеличивает его на 2.

  2. Воспользоваться адресом этой переменной, который содержится в P1. Для этого используется конструкция, которая называется разыменование.

Общее правило такое: для того, чтобы по указателю на переменную получить доступ к самой этой переменной, необходимо после переменной-указателя поставить знак ^.

P1^ означает адрес переменной, а выражение, на которое ссылается P1. Такая конструкция может находиться в любом контексте, в котором допустимо нахождении самой указуемой переменной. Поэтому операторы (в нашем случае) i:= i+2 и P1^:= P1^+2 полностью эквивалентный.

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

Разыменование допускается для любых ссылочных типов. Например, для переменной OneMam из примера допустимы конструкции:

OneMan^, BirthDay. Man: = Feb;

If OneMan^. Name = ‘Иван’ then…

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

Разыменование считается некорректным, если ссылочная переменная имеет значение nil. В этом случае не существует переменной, на которую ссылается указатель, поэтому операторы P1:=nil; P1^:=2;хотя и не приводят к аварийному прекращению выполнения, но являются недопустимыми.

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

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

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

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

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

Основные действия над динамическими переменными – создание и уничтожение реализуются в языке Паскаль стандартными процедурами New и Dispose.

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

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

  2. Переменной, переданной в параметре, присваивается указатель (адрес, отведенный области памяти) на отведенную область памяти.

Пример: type P= ^T;

Var Ptr: P;

Тогда обращение New (Ptr) приводит к созданию (размещению в памяти) новой переменной типаТ и присваиванию переменной Ptr соответствующего T динамического значения.

Пример: type Person = record

Name, SecondName, SurName: string [20];

Sex: (Male, Female);

Speciality: word;

End; {of record}

Var P: ^Person;

Begin New (P);

Этот фрагмент программы приведет к отведению в куче области памяти, достаточной для хранения записи типа Person, и присваиванию указателя на эту область переменной P. После этого доступ к созданной динамической переменной возможен только через указатель P:

P^. Name: =’Иван’;

P^. Sex: =Male;

Можно использовать процедуру New и в функционарной форме:

Type F = ^Person;

Var P: F;

Begin P: = New (F);

В связи с процедурой New возникает важная проблема – возможное исчерпание области памяти, отведенной для динамических переменных. Если при выполнении New выяснится, что для размещения новой переменной в куче не хватает памяти, то значение указателя, поданного в параметре, не изменится. При этом выполнение программы не прекратится и никаких сообщений выдано не будет, поэтому дальнейшая работа с неустановленным указателем может привести к непредсказуемым последствиям. Для повышения надежности программы следует проверять текущее состояние динамической памяти перед каждым обращением к New. Это можно сделать с помощью стандартной функции MaxAvail, которая возвращает максимальный размер непрерывного участка свободной памяти, пригодного для размещения динамической переменной.

Пример. Необходимо создать динамическую переменную типа Longint.

(0..232-1)

Техника отведения памяти:

Var Pl: ^ longint;

Begin if MaxAvail >=4 then

New (Pl)

Else writeln (‘исчерпана динамическая память’);

В этом фрагменте подразумевается, что переменная типа longint занимает в памяти 4 байта. В более общем случае для определения размера необходимой памяти можно воспользоваться стандартной функцией Sizeof.

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

Пример: if MaxAvail >= Sizeof (Person) then

P: = New (F);

Кроме функции MaxAvail в ЯПП есть функция MemAvail, которая возвращает суммарный размер всех свободных областей динамической памяти. Эти две функции дают разные результаты. Из-за произвольного характера отведения и освобождения памяти куча может представлять собой случайную последовательность свободных и занятых областей различных размеров. Функция MaxAvail определяет нб свободную область, функция MemAvail – общий объем свободных областей.

Для освобождения памяти, отведенной с помощью процедуры или функции New, используется стандартная процедура Dispose. Параметром этой процедуры должен быть указатель на динамическую переменную, причем эта переменная должна быть ранее размещена в куче посредством процедуры или функции New. Обращение Dispose (Ptr) приводит к уничтожению переменной, на которую указывает Ptr.

Пример: Var P: ^Person;

Begin New (P);

действия с указателем P

Dispose (P)

End.

Связные списки. Односвязные списки – связь в одну сторону. Это когда трудно или вообще невозможно предсказать число объектов, обрабатываемых программой, и поэтому традиционные структуры данных, например, массивы, для которых требуется заранее определить максимальное число элементов, неприменимы.

В подобных ситуациях используются динамические объекты.

Пример объявления указателей.

Type Vektor = Array [1..20] of real;

PV = ^Vektor; {указатель на заданный тип}

PL = ^List;

List = record

L11: String[22];

L12: Real;

L13: Array [1..6] of byte;

Next: PL

End; {of record}

Var X1: PV;

PI1, PI2: ^integer;

Chain: PL;

P1, P2: Pointer; {образует указатель, не связанный с типом}

Пример:

……

X1^[1]: = 1,23; {первому элементу массива X1 присвоить значение 1,23}

……

X1^[i+j*n]: = X1^[3+i]; {элементу N0- = i+j*n присвоить значение элемента

N0- = i+3}

PI1^: = 3; {целому числу, на которое указывает PI1, присвоить значение 3}

With chain^ do

Begin L11: = ‘abcdefg’; {полям записи, на которые указывает Chain,

L12: = 1e+23; присвоить соответствующие значения.

L13 [3]: = 5;

Chain: = Next

End; {with}

Если P является указателем на переменную типа T, то P^ - это сама переменная T.

(Var P: ^T).

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

Динамические переменные.

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

Пример: Type T = ^integer; означает, сто ссылочная переменная A

Var A: T; указывает на динамические объекты B: ^real целого типа, а ссылочная переменная B – на динамические объекты вещественного типа.

Ссылочной переменной может быть присвоено «пустое» значение адреса, обозначаемое служебным словом NIL. Оператор присваивания A: = NIL означает, что ссылочная переменная A не указывает ни на один динамический объект. Память под переменные A и B отводится на этапе трансляции.

Для порождения динамических объектов предназначена стандартная процедура New (A), где A – параметр ссылочного типа. После работы процедуры New (A) переменная A получает значение ссылки на порожденный объект. Чтобы получить доступ к динамически выделенной памяти, необходимо написать A^, что означает: « идти по адресу, хранящемуся в A.»

Пример. Var X, Y: ^Integer;

………………….

N ew (X);

X^: = 13;

Y: = X;

Writeln (Y^);

Writeln (X^+20);

Сначала динамически порождается объект целого типа. Это означает, что выделяется место в памяти, но ничего туда не заносится. При этом переменной ссылочного типа X присваивается значение адреса динамического объекта.

Оператор присваивания X^: = 13 заносит целое число 13 в динамическую переменную. Ссылочная переменная Y может содержать адрес любого объекта целого типа, поэтому правомеренный оператор присваивания Y: = X. Он заносит в переменную Y значение того же адреса, что хранится в переменной X. Первый оператор печати выведет целое число 13, а второй – число 33. Но при этом целочисленное значение, хранящееся в динамической переменной, не изменится.

Адрес

13

X

Адрес

Y

Для уничтожения динамических объектов служит стандартная процедура Dispose (X), где X – переменная ссылочного типа.

После окончания работы процедуры Dispose (X) ссылочной переменной X присваивается значение Nil, а память, занимаемая динамической переменной, освобождается.

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

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

Здесь рассматриваются пока только однонаправленные списки.

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

Type ссылка = ^элемент;

Данные = тип;

Элемент = record

C: ссылка;

D: данные;

End {of record};

Определив, таким образом ссылочный тип, можно, например, построить связанный однонаправленный список:

Нач.

C

D

C

D

C=

Nil

D

Указатель НАЧ. содержит ссылку на первый элемент списка. Каждый элемент списка содержит поле C – ссылку на следующий элемент, и поле D – поле данных, которое, в свою очередь, может быть достаточно сложной структурой. Поле ссылки последнего элемента списка содержит пустую ссылку (Nil).

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

C

D

C

D

C

D

п ред

A F B

На этом рисунке показано исключение из списка элемента F. Для этого адрес элемента B, который хранился в поле ссылки элемента F, записывается в поле ссылки элемента A, после чего элемент A будет указывать на B, а элемент F станет недоступным, так как на него никто не ссылается.

Пусть ПРЕД – переменная ссылочного типа, содержащая ссылку на элемент, предшествующий удаляемому. Тогда, чтобы осуществить операцию исключения, достаточно выполнить следующий оператор присваивания:

ПРЕД^. C: = ПРЕД^. C^. C

Правая часть оператора присваивания читается так: идти по ссылке, хранящейся в ПРЕД, взять ссылку из поля C, идти по ней, взять ссылку из поля C удаляемого элемента. Полученное ссылочное значение записывается в поле C элемента, предшествующего удаляемому.

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

C

D

C

D

C

D

C

D

ПОС

A F B

X

НОВ

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

НОВ^. C: = ПОС^. C;

ПОС^. C: = НОВ;

Первый оператор присваивания заносит в поле ссылки вставляемого элемента ссылочное значение, указывающее на элемент B и содержащееся ранее в F. Второй оператор записывает в поле ссылки элемента F ссылку на вставляемый элемент. ПОС НОВ

C = Nil

D

C = Nil

X

Для добавления в конец списка элемента X достаточно найти последний элемент списка (у него поле ссылки имеет значение Nil) и переслать в его поле ссылки указатель на добавляемый элемент. При этом поле ссылки добавляемого элемента должно содержать NIL. Эти действия реализуются операторами:

НОВ^. C: = Nil;

ПОС^. C: = НОВ;

Этот пример является частным случаем добавления элемента в список.

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

Н АЧ НАЧ

C

D

C

D

или при вставке нового элемента в начало списка

C

D

C

D

C

D

НАЧ

НАЧ

НОВ

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

Операция удаления реализуется одним оператором

НАЧ: = НАЧ^. C;

а операция вставки двумя операторами:

НОВ^. C: = НАЧ;

НАЧ: = НОВ.

П

Ответ

X^ = 12

Y^ = 7

ример 1
. Указать значения X^ и Y^ после выполнения следующих операторов:

Var X, Y: integer;

……

New (X);

X^: = 17;

New (Y);

Y^: = -5;

X^: = X^ + Y^;

Y^: = Y^ + 12;

если известно, что Var X, Y: ^integer;

Пример 2. Что будет напечатано?

Var X, Y: ^Char;

Ответ: AA.

………..

New (X);

X^ = ‘A’;

Write (X^);

Y: = X;

Writeln (Y);

Пример 3. Что будет выведено на печать?

Type A = ^Char;

B = Record S1: Char;

S2: A

End;

V

Ответ:

ABA

ar X: ^B;

Y: A;

………….

New (Y);

Y^: = ‘A’;

New (X);

X^.S1: = Succ (Y^);

X^.S2: = Y;

Writeln (Y^. X^.S1, X^.S2);

Пример 4. Известно, что

Type ссылка = ^Real;

Вектор = Array [1..50] of ссылка;

Var X: Вектор;

Считается, что все элементы массива X отличны от Nil, написать:

  1. Фрагмент программы для нахождения наибольшего из чисел, на которые ссылаются элементы массива X

I: Integer; M: Real;

……………

M: = X [1]^;

For I: = 2 to 50 do

If M<X [1]^ then M: = X [I]^;

…………………….

  1. Фрагмент программы, который переменной Neg присваивает значение первого элемента массива X, ссылающегося на отрицательное число, или Nil, если такого нет:

…………………..

I: Integer;

Pr: Boolean;

Neg: Ссылка;

…………….

Pr: = True;

Neg: = Nil;

I: = 1;

While Pr And (I<= 50) do

If X [I]^ < 0 then begin

Neg: = X [I];

Pr: = False

End

Else I: = I+1;

……………..

Пример 5. Дано описание переменных:

Var X, Y: ^Integer;

R: ^Char;

Какие операторы являются правильными, какие – нет и почему?

  1. X: = Y; - правильно

  2. Y: = R; - нет

  3. X: = Nil; - правильно

  4. R: = Nil; - нет

  5. If Y = X then X^: =21; - правильно

  6. If Y<X then Y^: = X; - нет

Пример 6. В программе определены следующие типы и переменные:

Type ссылка = ^элемент;

Элемент = Record след: ссылка

D: Integer

End;

Var Нач, C, B: Ссылка;

I: Integer;

Даны два фрагмента программы:

1 -вый фрагмент

………………

New(C);

Нач: = C;

For I: = 1 to 10 do

Begin New (B);

C^. След: = B;

C^. D: = I

C: = B

End;

………..

2 - фрагмент

………….

New(C);

Нач: = C;

With C^ do

For I: = 1 to 10 do

Begin New (B);

След: = B;

D: = I;

C: = B;

End;

………..

Будут ли одинаковы результаты? Результаты работы программ будут разные, так как в области действия оператора присоединения нельзя изменять элементы списка переменных – записей, указанные в заголовке.

Оператор C: = B недопустим, так как ссылочная переменная B изменяет значение на каждой итерации цикла.

Формирование списка с одновременным упорядочением его элементов по указанному признаку.

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

Использование списковых структур при решении подобных задач имеет определенные преимущества:

  • Исключает предварительное резервирование памяти,

  • Дает возможность сортировать (упорядочивать) список одновременно с вводом,

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

Program Spisok;

Type Nazv = Array [1..10] of Char;

Ssilka = ^Элемент;

Element = Record SS: Ssilka;

Dan: Nazv

End;

Var Kniga: Nazv;

Nach Tec, ob, овоч: Ssilka

I: Integer;

Begin

(*формирование 1 – ого элемента списка*)

New (Нач);

Readln;

Writeln (‘вводи первое название’);

For I: = 1 to 10 do

Read (Kniga [I]);

Readln;

Nach^.SS: = Nil;

Nach^.Dan: = Kniga;

(*формирование списка*)

While Kniga <> ‘ЯЯ..Я’ do

Begin Tek: = Nach;

New (ов);

Writeln (‘вводи очередное название’);

For I: = 1 to 10 do Read (Kniga [I]);

Readln;

(*поиск подходящего места*)

While (Tek <> Nil) And (Tek^.Dan < Kniga) do

Begin Овоч: = Tek; (*ссылка на передний элемент*)

Tek: = Tek^.SS (*переход к следующему элементу*)

End;

(*вставка нового элемента*)

ов^.SS: = Tek;

ов^.Dan: = Kniga;

If Tek = Nach then Nach: = ов

Else Овоч^.SS: = ов

End; (*конец формирования списка*)

(*вывод на терминал упорядоченного каталога книг*)

Writeln (‘Каталог учебников’);

Tek: = Nach

While Tek^.SS <> Nil do

Begin Writeln (Tek^.Dan);

Tek: = Tek^.CC

End;

End.

В начале программы формируется первый элемент списка и задается значение начального указателя Nach. Затем, пока не будет введено название учебника, состоящее из десяти букв Я, под каждое вводимое название динамически отводится место в памяти оператором New(ов), после чего просматривается список с самого начала до тех пор, пока не будет найдена соответствующая позиция для нового элемента или не будет достигнут конец списка.

В найденное место вставляется новый элемент списка. В конце программы упорядоченный список распечатывается.

Протокол работы программы:

Вводи первое название

Математика

Вводи очередное название

Алгебра

Вводи очередное название

Физика

Вводи очередное название

ЯЯ..Я

Каталог учебников

Алгебра

Математика

Физика

Пример. Различие между статическими и динамическими переменными.

  1. Var i, j: integer;

Begin j: = 5;

I: = j; i =5 и j =5 Статические переменные i и j

  1. Var i, j: ^integer;

B egin New(j); целая переменная размещена в памяти, а j – это

указатель на нее; значения у j нет

i: = j; оба указателя i и j указывают на одну и ту же

переменную

j ^: = 5; значение целой переменной равно 5

Указатели обычно используют для построения списковых структур данных.

Пример. Представление стеков. Каждый узел списка должен содержать по крайней мере два поля: одно – для хранения данных (Info), а второе – типа указатель, связь (Link).

TOP

Info

Link

T ype L1 = ^Mode;

Info

Link

Info

Link

Mode = Record

Info: char;

L ink: integer

End {of Mode};

Это описание стека.

Формирование стека:

Var Top, K: L1;

Ch: Char;

………….

Top: = Nil;

While Not EOF do

Begin read (Ch);

New (K);

K^.Link: = Top;

K^.Info: = Ch;

Top: = K

End;

Включение нового узла в стек:

Var Model: L1;

……………

read (ch);

New (Model);

Model.Link: = Top;

Model.Info: = Ch;

Top: = Model;

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]