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

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


 

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

32525. БЛОЧНО-МОДУЛЬНАЯ СТРУКТУРА ДЕЯТЕЛЬНОСТИ УЧАЩЕГОСЯ В ТЕХНОЛОГИИ ПРМЕНЕНИЯ ПРОГРАММНЫХ СРЕДСТВ 41 KB
  ППС и методика их использования БЛОЧНОМОДУЛЬНАЯ СТРУКТУРА ДЕЯТЕЛЬНОСТИ УЧАЩЕГОСЯ В ТЕХНОЛОГИИ ПРМЕНЕНИЯ ПРОГРАММНЫХ СРЕДСТВ. Блочномодульная структура деятельности учащегося в технологии применения ПС Необходимо отметить два направления к которым ведет использование средств информационных технологий. Усложнение технических средств влечет за собой обогащение форм деятельности. Можно утверждать что внедрение средств новых информационных технологий влияет на духовную эмоциональную коммутативную и деятельностную сферы жизни человека.
32526. КРИТЕРИИ ЭФЕКТИВНОСТИ ТЕХНОЛОГИИ ПРИМЕНЕНИЯ ПРОГРАММНЫХ СРЕДСТВ 37.5 KB
  Технология применения ПС в учебном процессе имеет специфику в том что в качестве основного средства обучения используются программные средства это частнодидактическая технология имеющая приложения для всех общеобразовательных дисциплин в школе. В качестве критериев оценки технологии применения ПС отобраны следующие: 1 критерии среды обучения оценивались по соответствию педагогическим условиям реализации технологии применения ПС эмоциональному фону урока и общению между учителем и учащимися; 2 критерии эффективности программных средств...
32527. РОЛЬ И МЕСТО ИНФОРМАТИЗАЦИИ ПРОЦЕССА ОБУЧЕНИЯ В ШКОЛЕ. СВЯЗИ МЕТОДИКИ ПРЕПОДАВАНИЯ ИНФОРМАТИКИ С ДРУГИМИ ПРЕДМЕТАМИ 69.5 KB
  СВЯЗИ МЕТОДИКИ ПРЕПОДАВАНИЯ ИНФОРМАТИКИ С ДРУГИМИ ПРЕДМЕТАМИ Роль и место информатизации процесса обучения в школе В стандартах по информатике [11] были определены следующие педагогические функции образовательной области связанной с информатикой: Формирование основ научного мировоззрения. В современной психологии отмечается значительное влияние изучения информатики и использования компьютеров в обучении на развитие у школьников теоретического творческого мышления а также формирование нового типа мышления так называемого операционного...
32528. ДИАЛЕКТИЧЕСКИЙ ХАРАКТЕР ВНЕДРЕНИЯ СРЕДСТВ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ В УЧЕБНЫЙ ПРОЦЕСС. ВНЕШНИЕ И ВНУТРЕННИЕ ФАКТОРЫ ИЗМЕНЕНИЙ ТЕХНОЛОГИЙ ОБУЧЕНИЯ С ИСПОЛЬЗОВАНИЕМ СРЕДСТВ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ 61 KB
  ВНЕШНИЕ И ВНУТРЕННИЕ ФАКТОРЫ ИЗМЕНЕНИЙ ТЕХНОЛОГИЙ ОБУЧЕНИЯ С ИСПОЛЬЗОВАНИЕМ СРЕДСТВ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ. Чтобы осознать влияние средств информационных технологий на процесс обучения необходимо выявить движущие силы педагогического процесса в условиях применения программных средств необходимо вскрыть диалектический характер развития педагогических технологий при использовании программных средств. Влияние программных средств информационных технологий на диалектические закономерности процесса обучения Влияние СИТ на существующие...
32529. ОБЩЕДИДАКТИЧЕСКИЕ ПРИНЦИПЫ ИСПОЛЬЗОВАНИЯ ПРОГРАММНЫХ СРЕДСТВ В УЧЕБНОМ ПРОЦЕССЕ. ЧАСТНО_МЕТОДИЧЕСКИЕ ПРИНЦИПЫ, ОТРАЖАЮЩИЕ ОСОБЕННОСТИ ПРИМЕНЕНИЯ ПРОГРАММНЫХ СРЕДСТВ В УЧЕБНОМ ПРОЦЕССЕ 54 KB
  ЧАСТНО_МЕТОДИЧЕСКИЕ ПРИНЦИПЫ ОТРАЖАЮЩИЕ ОСОБЕННОСТИ ПРИМЕНЕНИЯ ПРОГРАММНЫХ СРЕДСТВ В УЧЕБНОМ ПРОЦЕССЕ Дидактические принципы применения программных средств в процессе обучения Общедидактические принципы использовании ПС в процессе обучения. Для достижения стабильных и высоких результатов в обучении педагог должен следовать принципам обучения основным нормативным положениям которыми следует руководствоваться чтобы обучение было эффективным. Для совершенствования психологических характеристик учащихся существуют специальные развивающие...
32530. ИСПОЛЬЗОВАНИЕ ЭЛЕКТРОННЫХ ТАБЛИЦ В ДЕЯТЕЛЬНОСТИ УЧИТЕЛЯ-ПРЕДМЕТНИКА 1.2 MB
  ППС и методика их использования ИСПОЛЬЗОВАНИЕ ЭЛЕКТРОННЫХ ТАБЛИЦ В ДЕЯТЕЛЬНОСТИ УЧИТЕЛЯПРЕДМЕТНИКА Использование электронных таблиц на уроках физики: Законы отражения и преломления света Рисованные объекты. Или угол падения равен углу преломления или угол преломления равен углу отражения или вообще все углы равны или наоборот между ними разница в 90 градусов. Но вот отразится и преломится свет в точке падения обозначенной буквой S совсем не так как указывают ему направления SB и SC поскольку проведены они с нарушением обоих...
32531. ИСПОЛЬЗОВАНИЕ ВЕКТОРНЫХ ГРАФИЧЕСКИХ РЕДАКТОРОВ НА УРОКАХ ГЕОМЕТРИИ 378 KB
  Паркет называется правильным если он составлен из равных правильных многоугольников.3 Примеры правильных паркетов дают заполнения плоскости: а квадратами рисунок 1; б равносторонними треугольниками рисунок 2; в правильными шестиугольниками рисунок 3. Докажем что других правильных паркетов не существует. Действительно углы правильного гаугольника равны 180 Заполним таблицу состоящую из углов  правильных n угольников.
32532. ИСПОЛЬЗОВАНИЕ ЭЛЕКТРОННЫХ ТАБЛИЦ В ДЕЯТЕЛЬНОСТИ УЧИТЕЛЯ-ПРЕДМЕТНИКА 1.5 MB
  Для отображения даты подходящей будет ориентация текста под углом в 90 градусов для всей третьей строки и горизонтальное и вертикальное выравнивание по центру а для ячейки S3 ещё и с переносом по словам. Вообще полученный список имеет смысл запомнить на будущее поскольку он наверное потребуется ещё не раз и в других таблицах связанных с классом. Поскольку сдвиг будет производиться вертикально вниз то во всех фигурирующих в формуле адресах цифровая составляющая увеличится на единицу для следующей строки затем ещё на единицу для...
32533. Использование графического редактора для решения задач на разрезание 351 KB
  Рассмотрим линии разбивающие фигуру Ф на части из которых можно составить фигуру Ф' и кроме того линии разбивающие фигуру Ф на части из которых можно составить фигуру Ф . Те и другие линии разбивают фигуру Ф на более мелкие части из которых можно составить как фигуру Ф' так и Ф . Доказанная теорема позволяет в принципе разрезать один из двух равновеликих многоугольников на части и сложить из них другой многоугольник. Фигура будет разрезана на две части вдоль прямой линии.