9740

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

Лекция

Информатика, кибернетика и программирование

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

Русский

2013-03-15

62 KB

6 чел.

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

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

ДИНАМИЧЕСКИЕ ПЕРЕМЕННЫЕ

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

TYPE T=^INTEGER;

VAR A:T;

 B:^REAL;

означает, что ссылочная переменная А указывает на динамические объекты целого типа, а ссылочная переменная В - на динамические объекты вещественного типа.

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

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

VAR X,Y: ^INTEGER;

...

NEW(X); X^: = 13; Y: = X;

WRITELN(Y^); WRITELN(X^+20);

...

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

Рис. 1

Для уничтожения динамических объектов служит стандартная процедура DISPOSE(X), где X - переменная ссылочного типа. После окончания работы процедуры ссылочной переменной X присваивается значение NIL, а память, занимаемая динамической переменной, освобождается.

{Sample code for the New and Dispose procedures.}

type

 Str18 = string[18];

var

 P: ^Str18;

begin

 New(P);

 P^ := 'Now you see it...';

 writeln(p^);

 Dispose(P);  { Now you don't... }

end.

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

Описанные выше указатели связаны с некоторым типом данных. Поэтому их называют типизированными указателями.

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

var

р:   Pointer;

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

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

var

pI1,pI2:^Integer;

pR: ^Real;

p:  Pointer;

то присваивание

pIl   := pI2;

вполне допустимо, в то время как

pIl   := pR;

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

p := pR;

pIl := р;

и тем самым достичь нужного результата.

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

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

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

TYPE  my_pointer=^element;

  data = my_data_type;

  element = RECORD

    C: my_pointer;

    D: data

  END;

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

Рис. 2

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

Рис. 3.

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

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

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

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

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

Рис.  4

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

HOB^.C: = ПOC^.C;

ПОС^.C:=HOB

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

Рис. 5

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

Эти действия реализуются операторами

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

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

Рис. 6

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

Операция удаления реализуется одним оператором НАЧ: = НАЧ^.С, а операция вставки - двумя операторами: НОВ^.С: = НАЧ; НАЧ: = НОВ.


 

А также другие работы, которые могут Вас заинтересовать

37335. ВВЕДЕНИЕ В ЭКСПЕРТНЫЕ СИСТЕМЫ 6.59 MB
  Эти изменения стали возможными благодаря двум основным факторам: выделению в алгоритме программы некоторой универсальной части логического вывода и отделению ее от части зависящей от предметной области базы знанийрис. При этом производится преимущественно символьная обработка содержимого базы знаний. Экспертная система это компьютерная программа которая моделирует рассуждения человекаэксперта в некоторой определенной области и использует для этого базу знаний содержащую факты и правила об этой области и некоторую процедуру...
37336. Проблемы экономической безопасности России в условиях перехода к рынку 99 KB
  Общее понятие экономической безопасности и характеристики основных ее показателей. Экономика России с точки зрения экономической безопасности. Пути обеспечения экономической безопасности России.
37337. ОБЩАЯ ЭЛЕКТРОТЕХНИКА И ЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА 1.61 MB
  Частота колебаний напряжения Герц f [Hg] f [ Гц ] 9.Примеры выделения из третьей строки рабочего стола источника постоянного напряжения 12 V и элемента обозначающего соединение с корпусом. показан процесс выделения двух важнейших элементов любой электрической схемы: источника постоянного напряжения – 12V и знака заземления которые необходимы для построения делителя напряжения на резисторах. показан дальнейший процесс построения схемы...
37338. ЭЛЕКТРОТЕХНИКА И ЭЛЕКТРОНИКА, ОБЩАЯ ЭЛЕКТРОТЕХНИКА И ЭЛЕКТРОНИКА 831.5 KB
  В РЕЗУЛЬТАТЕ ИЗУЧЕНИЯ ДИСЦИПЛИНЫ СТУДЕНТ ДОЛЖЕН: ЗНАТЬ: теорию электромагнитных полей и электрических цепей; назначение и принцип действия трансформаторов; принципы построения автогенераторов и усилителей на транзисторах; принципы построения выпрямителей на полупроводниковых диодах; принципы построения электроприводов управляемых микроконтроллерами; принципы работы средства измерения электрических и неэлектрических параметров технологических процессов; назначение и особенности построения интегральных...
37339. Системы управления 2.98 MB
  Методология исследования систем управления Раздел 2. Концептуальные основы исследования систем управления Раздел 3. Система управления как объект исследования Раздел 4. Логический аппарат исследования систем управления Раздел 5.
37340. М.В. Шиловского, «Полнейшая самоотверженная преданность науки» 27.5 KB
  Но в его жизненном пути более всего меня привлекает то чего не хватает самому в первую очередь конечно трудолюбия невероятной трудоспособности практических навыков по обработке научного материала научной продуктивности и неординарности мысли но главное все таки усердия самоотверженности и возможности всего себя посвятить науке. Но главное что я понял это тот факт что он был истинным патриотом своей Родины и как мог двигал и российскую науку и дело развития Сибирской.
37343. Реализация проблемно-целевых программ в таможенном деле 4.83 MB
  Федеральная целевая программа развития ТС на 1996-1997 годы и на период до 2000 года 11 Целевые программы модернизации таможенной службы. Для таможенной системы внедрение прогрессивных технологий таможенного контроля является одним из приоритетных направлений. Созданная материальная база кадровые и финансовые возможности позволяют говорить о реализации в таможенной системе сложнейшей задачи завершении...