Программа и учебные материалы элективного курса по информатике для учащихся 10-11 классов «Построение структур данных с применением динамических переменных и указателей» (стр. 2 )

Name:string;

Rost:integer;

Date:integer

End;

Mass=array [1..20] of anket;

Var

A:anket;

D:mass;

Begin

…………………..

a. name:='Сидоров';

d[8].rost:=123;

d[3]:=a;

a. date:=12;

…………………..

end.

В приведенном примере описана запись, содержащая 3 поля и массив, состоящий из таких же записей. Показаны правила обращения к компонентам массива записей и записи.

Способы адресации данных

В электронных вычислительных машинах данные хранятся в памяти. Есть различные виды памяти: постоянная (ПЗУ) и оперативная (ОЗУ), внутренняя и внешняя, есть собственная память процессоров – регистры, кроме того, в архитектуре современных процессоров присутствует КЭШ-память, используемая для оптимизации выполнения вычислительных процессов. Существуют также и разные способы обращения к данным, хранящимся в памяти: последовательный и произвольный. Программисты, решая задачи, используют для размещения данных те ресурсы, которые необходимы в каждом конкретном случае. Однако в любой программе, есть данные, размещаемые в ОЗУ, такими данными являются переменные и константы.

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

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

Прямая адресация

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

В этом случае для работы с данными можно использовать команды процессора поддерживающие прямую адресацию памяти.

Например, скопировать слово, хранящееся по адресу памяти, указанному в регистре (1) процессора в область с адресом, указанным в регистре (2) процессора[2].

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

Итак, прямая адресация является самым простым и распространенным способом организации доступа к данным в оперативной памяти компьютера.

Индексная адресация

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

Например, считать в регистр (1) процессора слово, расположенное по адресу, вычисляемому по значению, указанному в регистре (2) процессора, с учетом индексного смещения указанного в инструкции.

Приведенная ниже таблица иллюстрирует размещение в памяти массива A, состоящего из элементов некоторого базового типа и записи Z, состоящей из полей N, R, K.

Элемент	Смещение	Адрес памяти
A[1]	0*(длина базового типа)	Начальный адрес A+0
A[2]	1*(длина базового типа)	Начальный адрес A+длина базового типа
A[3]	2*(длина базового типа)	Начальный адрес A+2*(длина базового типа)
……………	………………………….	…………………………….
Z. N	0	Начальный адрес Z+0
Z. R	длина N	Начальный адрес Z+длина N
Z. K	длина N+длина R	Начальный адрес Z+длина N+длина R

Косвенная адресация

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

Рассмотрим пример. Фрагмент описания процедуры выглядит так:

Procedure primer (var C:integer);

Begin

………………

C:=11

end;

Вызов процедуры из программы осуществляется следующим образом:

……………………

B:=34;

primer(B);

writeln(B);

……………………

В этом случае будет напечатано число 11.

Приведенная ниже таблица иллюстрирует передачу переменной B в качестве фактического параметра процедуры вместо формального параметра C.

Адрес памяти	Значение в памяти	Комментарии
Адрес места хранения адреса формальной переменной С	Адрес переменной B	Адрес переменной B, переданной в качестве фактического параметра
…………………	………………….	……………………
Адрес переменной B	34	Значение переменной B до вызова процедуры primer
Адрес переменной B	11	Значение переменной B после выполнения процедуры primer

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

Динамические переменные и указатели

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

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

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

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

Динамическая переменная создается специальной процедурой (new) параметром которой является переменная типа указатель.

Описание переменной – указателя имеет следующий вид:

Type

<имя типа - указателя>=^<имя типа - переменной>;

Пример

Type

Uk=^integer; {Описан указатель на динамическую переменную целого типа}

Var

Dp:uk; {описана переменная – указатель}

Begin

New(Dp); {в памяти создана переменная целого типа и связана с переменной – указателем}

Dp^:=30; {динамической переменной присвоено значение}

Dp:=nil; {переменная - указатель получила значение пустой указатель, показывающее, что она не связана ни с какой переменной}

End.

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

Применение динамических переменных и указателей к построению структур данных

Связные списки

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

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

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