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.б) необходимо переопределять не указатель предыдущего элемента, как в рассмотренных выше примерах, а значение начального указателя.

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


 

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

21441. Замечания по поводу классификации точек покоя 340.5 KB
  Следовательно при достаточно большом t точки траекторий начальные значения которых находятся в любой окрестности начала координат попадают в сколь угодно малую окрестность начала координат а при неограниченно приближаются к началу координат т. точки расположенные в начальный момент в окрестности начала координат при возрастании t покидают любую заданную окрестность начала координат т. Если существует дифференцируемая функция называемая функцией Ляпунова удовлетворяющая в окрестности начала координат условиям: 1 причем...
21442. Исследование на устойчивость по первому приближению 209.5 KB
  Напомним что исследование на устойчивость точки покоя системы 1 эквивалентно исследованию на устойчивость некоторого решения системы дифференциальных уравнений 2 т. при правые части системы 1 обращаются в нуль:. Будем исследовать на устойчивость точку покоя линейной системы 5 называемой системой уравнений первого приближения для системы 4. система 1 стационарна в первом приближении то исследование на...
21443. Дифференциальные уравнения с частными производными первого порядка 170 KB
  Линейным неоднородным уравнением или квазилинейным уравнением I порядка в частных производных называется уравнение вида: . 2 Это уравнение линейно относительно производных но может быть нелинейным относительно неизвестной функции Z. Если а коэффициенты Xi не зависят от z то уравнение 2 называется линейным однородным.
21444. Дифференциальные уравнения векторных линий 218 KB
  Выделим из двухпараметрического семейства векторных линий называемых характеристиками уравнения 3 или 6 предыдущей лекции PxyzQxyz=Rxyz3 6 произвольным способом однопараметрическое семейство устанавливая какуюнибудь произвольную непрерывную зависимость между параметрами С1 и С2 . Тем самым найден интеграл квазилинейного уравнения 3 предыдущей лекции зависящий от произвольной функции. Если требуется найти не произвольную векторную поверхность поля а поверхность проходящую через заданную линию...
21445. Приведение матрицы линейного оператора к канонической (жордановой) форме 623.5 KB
  Вектор называется присоединенным вектором оператора соответствующим собственному значению если для некоторого целого выполняются соотношения . Иными словами если присоединенный вектор порядка то вектор является собственным вектором оператора . Существует базис 1 образованный из собственных и присоединенных векторов оператора в котором действие оператора дается следующими соотношениями:...
21446. Обыкновенные дифференциальные уравнения 438.5 KB
  Функция называется решением (или интегралом) д.у., если она раз непрерывно дифференцируема на некотором интервале и при удовлетворяет уравнению. Процесс нахождения решения д.у. называется его интегрированием...
21447. Линейные дифференциальные уравнения I порядка 299.5 KB
  Линейным дифференциальным уравнением I порядка называется уравнение I порядка линейное относительно неизвестной функции и её производной. Если то уравнение 1 называется линейным однородным. В соответствии с этим методом в формуле 2 полагают тогда: Подставляем полученное соотношение в уравнение 1 будем иметь: или откуда интегрируя находим следовательно . Интегрируем соответствующее однородное уравнение т.
21448. Нормальные системы дифференциальных уравнений. Условие Липшица 267 KB
  Условие Липшица. Говорят что функция удовлетворяет условию Липшица в некотором интервале [b] если существует такое число 0 что для. Так функция удовлетворяет условию Липшица в окрестности x=0 но её производная в точке x=0 имеет разрыв. Если функция нескольких переменных удовлетворяет условию Липшица по каждой из этих переменных в соответствующем диапазоне их изменения т.
21449. Теорема о дифференцируемости решений дифференциальных уравнений. Особые точки 463.5 KB
  Особые точки. Теорема: если в окрестности точки функция имеет непрерывные производные до mого порядка включительно то решение уравнения 1 удовлетворяющее начальному условию в некоторой окрестности точки имеет непрерывные производные до m1 порядка включительно. Подставляя в уравнение 1 получим тождество...