Учебные материалы к элективным курсам по информатике дляклассов, выпуск 1 (стр. 2 )

В Паскале применяются различные способы передачи параметров процедурам и функциям. Это может быть передача значений, когда при вызове процедуры или функции в памяти отводятся области для данных, используемых этой структурой. В эти области записываются значения переменных, переданные при вызове процедуры или функции. Другим способом передачи параметров является передача переменных. При описании процедуры или функции перед этими параметрами ставится слово 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.

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

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

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

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

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

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

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

Type

list=^element;

element=record

inf:string[20];

next:list

end;

Здесь тип list – является указателем на переменные типа element. Тип element определяет структуру элемента списка, состоящую из информационного поля inf и поля-указателя на следующий элемент next.

Опишем несколько статических переменных типа list, которые будем использовать для того, чтобы зафиксировать первый и последний элементы, а также как вспомогательные:

Var a, b,c:list;

Создадим первый элемент списка и зафиксируем его переменной a – начало списка, переменная b пусть указывает на конец списка:

new(a);

b:=a;

a^.inf:=’perviy’;

a^.next:=nil;

Последняя команда показывает, что элемент является последним, поскольку указатель на следующий элемент – поле next, устанавливается пустым – nil. Добавим к списку еще один элемент, следующий за первым:

new(b^.next);

b:=b^.next;

b^.inf:=’vtoroy’;

b^.next:=nil;

Вторая команда в этой серии выполняет сдвиг указателя b на следующий элемент списка (на него был установлен указатель текущего элемента).

Теперь вставим еще один элемент списка между первым и вторым, для этого используем переменную c:

new(c);

c^.inf:=’poltora’;

c^.next:=a^.next;

a^.next:=c;

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

Добавим элемент в начало списка:

new(c);

c^.inf:=’nulevoy’;

c^.next:=a;

a:=c;

Таким образом, мы рассмотрели операции добавления элемента в начало и в конец списка, а также вставку нового элемента между двумя соседними. Кроме того, выяснили, что для движения по списку можно выполнять операции вида b:=b^.next.

Описанные выше структуру данных и операции над ней можно применить при решении следующей задачи.

Задача 1. В текстовом файле содержатся значения вещественных чисел. Сформировать и распечатать список этих значений в порядке их возрастания.

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

Программа	Комментарии
program sortlist;
uses crt;
Type	Описание типов данных
list=^element;
element=record
fn:real;
next:list
end;
Var
f:text;	Описание файловой переменной
a, b,c:list;	Описание переменных
n:real;
begin
clrscr;	Очистка экрана
assign(f,'infile1.txt');	Отождествление файловой переменной с файлом
reset(f);	Открытие файла
readln(f, n);	Чтение первого значения
new(b);	Создание первого элемента списка
c:=b;
b^.next:=nil;
b^.fn:=n;
while not eof(f) do	Чтение данных пока файл не закончился
begin
readln(f, n);
b:=c;	b-установлен на начало списка
new(a);	Создание элемента для включения в список
a^.fn:=n;
if n>c^.fn then	Проверка позиции нового элемента
begin
a^.next:=b;	Добавление элемента в начало списка
c:=a
end
else
begin
while (b^.next^.fn>n)and(b^.next<>nil) do	Пока не найдена позиция или список не кончился
b:=b^.next;	Двигаемся по списку
a^.next:=b^.next;	Вставляем новый элемент в найденную для
b^.next:=a	него позицию
end
end;
b:=c;	b-установлен на начало списка
while b<>nil do	Пока список не закончился
begin
writeln(b^.fn:10:2);	Печатаем значение элемента
b:=b^.next	Переходим к следующему элементу
end
end.

Замкнутые списки