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

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


 

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

21722. МОДЕЛИ ОЦЕНКИ НАДЕЖНОСТИ ЭМС 117.5 KB
  Распределение экстремальных значений Пусть имеется случайная выборка объемом n взятая из бесконечной совокупности имеющей распределение Fx где х непрерывная случайная величина.1 Так как разрушение материала связано с существованием наиболее слабой точки в работах по теории надежности рассматривается распределение экстремальных значений. Здесь будет рассмотрено распределение наименьших значений однако этот подход может быть использован и при выводе распределений наибольших значений. Функция распределения наименьших значений функция...
21723. Модели надёжности установок с восстановлением 310 KB
  Модели надёжности установок с восстановлением При экспоненциальном законе распределения времени восстановления и времени между отказами для расчёта показателей надёжности установки с восстановлением пригоден математический аппарат марковских случайных процессов. Дискретный случайный процесс называется марковском если все вероятностные характеристики будущего протекания этого процесса при зависят лишь от того в каком состоянии этот процесс находился в настоящий момент времени и не зависят от того каким образом этот процесс протекал до...
21724. Общие принципы определения ущерба от нарушений электроснабжения 80 KB
  Общие принципы определения ущерба от нарушений электроснабжения Проблема оценки ущерба от нарушений электроснабжения вызываемых отказами электрооборудования возникает как при проектировании так и при эксплуатации энергетических объектов. При проектировании потребность в характеристике ущерба ощущается как правило когда определяется экономическая эффективность капитальных вложений при выборе вариантов технических и организационнохозяйственных решений влияющих на степень надежности электроснабжения потребителей. При эксплуатации...
21725. Технико-экономическая оценка последствий от нарушений электроснабжения объектов производственных систем 240 KB
  Техникоэкономическая оценка последствий от нарушений электроснабжения объектов производственных систем 8.1 Модель поведения участка производства при нарушениях его электроснабжения По характеру последствий все отказы участков производственной системы можно разделить на три группы: 1 не обесценивающие производственную продукцию; 2 частично обесценивающие; 3 полностью обесценивающие. В этом случае длительность простоя производственного участка соответствует длительности нарушения электроснабжения . Большинство нарушений электроснабжения...
21726. Накопители на жестких магнитных дисках 116 KB
  1 БУСД блок управления 3х фазным синхронным двигателем шпинделя; И инвертор; СД синхронный двигатель; БП блок питания; ВК внутренний контроллер БУП блок управления позиционированием головки; ОЗУ оперативное запоминающее устройство ВК; см сервометка; ДПГ датчик позиционирования головки. Кроме того он дает разрешение на выпуск головки при достижении минимальной скорости вращения. Для записи и считывания используются магнитные головки представляющие собой катушки индуктивности которые выполняются по тонкопленочной технологии....
21727. Устройства массовой памяти на сменных носителях 180 KB
  Устройства массовой памяти на сменных носителях Вопросы: Магнитооптические диски. Оптические диски CD DVD PD. Эти устройства подключаются к компьютеру с помощью следующих интерфейсов: АТА SCSI USB Наибольшей популярностью пользуются в настоящее время CD DVD и магнитооптические диски. Магнитооптические диски.
21728. Аудио система персонального компьютера 245.5 KB
  Собственно цифровые каналы звуковой карты проходят через интерфейсные схемы например MIDI от шины расширения до ЦАП и от АЦП обратно к шине. На этих картах располагается и порт традиционного MIDI. Интерфейс MIDI Цифровой интерфейс музыкальных инструментов MIDI Musical Instrument Digital Interface является последовательным асинхронным интерфейсом с частотой передачи 3125 Кбит с. В настоящее время интерфейс MIDI имеют и дорогие синтезаторы и дешевые музыкальные клавиатуры пригодные в качестве устройств ввода компьютера.
21729. Коммуникационные устройства 306.5 KB
  Обмен данными требуется для различных целей: передачи файлов совместного использования периферийных устройств например принтеров доступа к разнообразным информационным услугам Интернета и частных сетей приема и передачи факсимильных сообщений посылки сообщений на пейджеры и мобильные телефоны установление голосовой связи IPтелефония видеосвязи и даже совместных игр по сети. СОМпорт Последовательный интерфейс для передачи данных в одном направлении использует одну сигнальную линию по которой информационные биты передаются друг за...
21730. Беспроводные интерфейсы связи 575 KB
  Инфракрасный интерфейс IrDA 2. В беспроводных интерфейсах используются электромагнитные волны инфракрасного IrDA Infrared Data Association и радиочастотного Blue Tooth диапазонов. Инфракрасный интерфейс IrDA 1. Общая характеристика IrDA Применение излучателей и приемников инфракрасного ИК диапазона позволяет осуществлять беспроводную связь между парой устройств удаленных на расстояние нескольких метров.