Информатика_Гуда

Глава 6. Алгоритмизация и программирование

Операции с указателями

Тип — это всегда два множества: множество значений и множество операций. Значениями переменных типа указатель являются адреса памяти. К указателям применимы операции отношения, их можно сравнивать (равны или неравны, но не меньше или больше). Указатели равны только в случае, если они ссылаются на один и тот же объект, то есть содержат один и тот же адрес.

Существует операция, которая возвращает указатель — адрес первого байта памяти, по которому записана переменная (любого типа) — это:

@<Имя переменной> или функция ADDR (<имя переменной>). Например, @x или ADDR(x).

Различают типизированные и нетипизированные указатели.

Нетипизированные указатели

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

Пример:

Пусть var p,r:pointer; x,y:integer; st:string;

а) p := @x; r := @st; тогда p <> r - true;

б) x := y; p := @x; r := @y; тогда p <> k - true; в) p := @x; r := @x; тогда p = r - true.

Пример «указатель на указатель»:

Type ip:^integer; Var a:ip; a1:^ip; x:integer;

Begin

a:=@x; a1:=@a; a1^^:=10; Writeln(x) {10}

End.

Типизированные указатели

Типизированные указатели содержат адрес, по которому записана переменная заранее определенного типа.

291

Информатика

Описываются они следующим образом: ^<идентификатор>;

Пример: Type ip=^integer; rp=^real; и т.д. Var a,b:ip; c:rp; d:pointer;

g:^byte; s:^string; a1,b1:^ip;

В Паскале все идентификаторы должны быть описаны перед использованием. Указатели являются единственным исключением. Базовый тип может быть объявлен и сразу после указателя.

Например: Type RecP=^spis; spis=record

fio:string[20];

number:byte;

End;

«Пустой» указатель

«Пустой» указатель — это постоянная указательного типа. Обозна- чается Nil. Выделяется один адрес, в котором заведомо не может быть размещена никакая переменная. На это место и ссылается «нулевой» или «пустой» указатель.

Указатель, которому присвоено значение Nil, не содержит в себе никакого адреса. Указатель Nil считается постоянным, совместимым с любымссылочным типом.Значит,егозначение можно присваивать любому указателю. Nil используют для инициализации указателя «пустым» зна- чением или когда его указание надо отменить. Это позволяет проверять значение указателя, прежде чем присвоить ему какое-либо значение.

6.13.2. Создание и уничтожение динамических переменных

Создание и удаление динамических переменных — это основные действия над динамическими переменными.

Типизированные объекты

NEW(x) — создает динамическую переменную, запрашивая в куче место для переменной соответствующего типа и возвращает адрес (х— переменная типа указатель).

Например: Type vec = array[1..5] of integer; Var

s:^vec;

292

Глава 6. Алгоритмизация и программирование

p,q:^real;

x:real;

. . . . . . .

New(p);

New(s);

Для задания значения переменной, на которую ссылается указатель, необходимо указать символ “”^’’ справа от указателя:

<Имя переменной>^ := <Значение>;

Примеры:

1.p^:=1.125; g:=p; write(g^); — будет напечатано число 1.125.

2.p:=@x; p^:= 10; — в результате в x окажется число 10.

3.s^[1]:= 3; for i:= 2 to 5 do s^[i]:=random;

Если переменная больше не нужна, то можем ее уничтожить, вернув память в кучу.

DISPOSE(x), x — типизированный указатель. Обычно используют для типизированных указателей.

Создание и уничтожение безтиповых объектов

В этом случае мы можем запросить у кучи любое заданное количе- ство байт и адрес начала этой области присвоить переменной типа pointer (но не байт одного сегмента).

GETMEM (p: pointer; size: word) — создает новую динамическую переменную заданного размера size и переменную-указатель на нее.

FREEMEM (p: pointer; size: word) — уничтожает динамическую переменную данного размера.

6.13.3. Примеры использования указателей

Объявление

Приобъявлениипеременнойтипа«указатель»выделяютсялишьячейки памяти для хранения собственно указателей. В начале работы программы эти ячейки пусты, конкретных адресов в них нет.

Примеры объявлений:

Type ip = ^integer;

293

Информатика

A = array[1..5] of byte; Var x,y:ip;

B:^byte;

R:^real;

Pa:^A;

p,q:pointer; Type preco=^struct;

Struct=record

C:char; n:integer; end; Var Pr:preco;

Выделение памяти

В результате выполнения процедур New и Getmem в ячейки перемен- ных-указателей записываются адреса, по которым будут располагаться данные соответствующих типов, и выделяется память по указанным адресам для хранения объектов, на которые ссылаются указатели:

New(x); New(y); New(B); New(R); New(Pa); New(Pr); Getmem (p, sizeof(real)); Getmem(q, sizeof(A));

Разыменование (занесение значений)

x^:=10; y^:=20; B^:=255; R^:=1.125; for i:=1 to 5 do Pa^[i]:=sqr(i); Pr^.c:=’$’; Pr^.n:= 1000;

Копирование значений

x^:= y^; R^:= B^;

Копирование адресов

x:=y;

Пусть в тексте программы имеется: var k:real; k := 625.5;

Тогда присвоение адреса переменной k указателям r и p будет выглядеть следующим образом: r:=@k; p:=@k;

Высвобождение памяти

Dispose(y); Dispose(x);

Freemem(p,sizeof(p));

Dispose(Pa); Dispose(Pr);

294

Глава 6. Алгоритмизация и программирование

Задание «нулевого» значения

new(x);

x:=nil;

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

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

6.14.1. Списки

K Линейный список — связанный список, в котором имеется адрес точки входа в список (обозначим его HEAD), а последний элемент указывает на Nil. В любую точку списка разрешается добавлять элемен- т(ы) и исключать любой элемент. Обе операции производятся с помощью перенастройки указателей и, соответственно, выделения памяти и занесения в него значения (в случае вставки элемента в список) или высвобождения памяти (в случае удаления из списка). П р и м е р линейного односвязного списка представлен на рис. 6.5.

HEAD – адрес первого элемента
Информационн	Информационн	Информационн	Информационн
ûå ïîëÿ	ûå ïîëÿ	ûå ïîëÿ	ûå ïîëÿ	Nil
Указатель	Указатель	Указатель	Указатель
Элемент 1	Элемент 2	Элемент 3	Элемент 4

Рис. 6.5

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

295

Информатика

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

Пример описания списка:

Type psp = ^tsp; tsp = Record

… {Поля любых типов}

…

next : psp End;

Алгоритмы работы со списками

I. Построение списка сводится к последовательному добавлению элементов в первоначально пустой список. На пустой список указывает пустой список (head = nil). Пусть требуется создать список слов, вводимых с клавиатуры. Последнее слово в списке — «end».

Type psp = ^tsp; tsp = Record

wd:string;

{В нашем примере информационное поле имеет тип string}

next:psp

end;

Var head,q,p:psp; sl:string;

Begin

New(p); head:=p; p^.next:=nil; Readln(sl); p^.wd:=sl;

While sl<>’end’ do Begin

Readln(sl); new(q); q^.wd:=sl; p^.next:=q; q^.next:=nil; p:=q

End;

End.

II.Просмотр и печать списка. Пусть требуется написать процедуру Print_Spisok печати элементов списка, созданного в алгоритме I.

Procedure Print_spisok; begin

p:= head;

296

Глава 6. Алгоритмизация и программирование

while p <> nil do begin

writeln((p^.wd); p := p^.next end

end;

III. Поиск элемента в списке. Определить, есть ли в списке (алгоритм I) слово «begin» и если есть, то сколько раз встречается. К описанию алгоритма I добавим: var k:integer;

…

Begin p:=head;

While p <> nil do Begin

If p^.wd = 'begin' then inc(k); p:=p^.next

End;

If k=0 then writeln('Такого элемента нет') Else writeln('Слово',sl,'встречается ',k,' раз') End;

IV. Удаление первого элемента списка. Необходимо 1) передвинуть указатель head на следующий элемент; 2) освободить память; 2) освободить память, занятую удаляемым элементом.

Begin

p:=head; head:=p^.next;

Dispose(p);

Print_Spisok

End;

V. Удаление последнего элемента списка. К разделу описаний алгоритма I добавим вспомогательную переменную q типа psp.

Begin

p := head; q := p^.next; While q^.next <> nil do Begin

p := q; q := q^.next End;

Dispose(p); p^.next := nil; Print_Spisok

End;

297

Информатика

VI. Вставка элемента в список. Пусть необходимо вставить в список (алгоритм I) новый элемент sl_new перед первым вхождением элемента sl_old, если sl_old входит в список. Добавим к разделу описаний алгоритма I описание переменных sl_new,sl_old : string; и fl:Boolean.

Begin

Write('Введите искомое слово'); readln(sl_old); Write('Введите новое слово'); readln(sl_new); Fl:=false; p:=head;

While (p<> nil) and not fl do

If p^.wd=sl_old then fl:=true else p:=p^.next; If fl then {Вставка элемента}

Begin

New(q); q^.wd:=sl_old; q^.next:=p^.next; p^.wd:=sl_new; p^.next:=q

End; Print_Spisok;

End;

6.14.2. Организация стека в динамической памяти

KСтек — линейный односвязный список, для которого разрешено добавлять или исключать элементы только с одного конца списка — «вершины» стека.

Принцип работы стека: «последним пришел — первым вышел».

Пример. Написать процедуры помещения элементов (целых чисел) в стек и извлечения их из стека.

Type pstack = ^element; element = record

	m: integer;
	next: pstack;
	End;
Var	p, st:pstack;
	{st — указатель на вершину стека}

i:integer;

k,n:integer;

Procedure put (n:integer);

{n— параметр-значение}

298

Глава 6. Алгоритмизация и программирование

Begin {Помещает значение в стек}

New(p); {выделение памяти под новый элемент} p^.m := n; {заносим в него информацию} p^.next := st; {указательная часть предшествующего

элемента указывает на вершину стека}

st:=p;

End;

Procedure get( var n: integer);

{извлекает элемент из стека; n — параметр-перемен- ная т. к. необходимо изменить значение n в основной программе}

Begin

p:=st; {запишем в р адрес вершины стека} n:=p^.m;

{в n — информационная часть верхнего элемента стека}

st:=p^.next;

{присваиваем вершине стека адрес следующего элемента}

Dispose(p);

end;

Begin {основная программа }

st:=nil; {вершина стека — «пустой» указатель, стек пуст}

Readln(k); {количество чисел}

For i:=1 to k do {вводим числа и помещаем в стек}

Begin

Readln(n); put(n) End;

. . . . . .

While st <> nil do {вывод элементов стека}

Begin

Get(n); writeln(n) End;

End.

6.14.3. Очередь

KОчередь — линейный односвязный список, для которого разрешены только два действия: извлечение элемента из начала очереди «головы» и добавление элемента в конец («хвост») очереди.

299

Информатика

Другими словами, в очереди элементы всегда добавляются в конец, а удаляются из начала. Принцип работы очереди: «первым пришел — первым вышел».

Пример. Создать очередь из произвольного числа компонентов. Извлечь и напечатать все элементы очереди.

Type pocher=^element; element=record

m: integer; next: pocher;

End;

Var no,ko,p:pocher;

{no — начало очереди, ko — конец очереди} n,k,i:integer;

Procedure putoch(n:integer);

{помещает значение в очередь}

Begin

New(p); {выделение памяти под новый элемент} p^.m:=n; {заносим в него информацию} p^.next:=ko;

{указательная часть ccылается на начало очереди} ko := p

End;

Procedure getoch(var n:integer);

{извлекает элемент из очереди}

Begin n:=p^.m;

{в n — информационная часть первого элемента оче- реди}

p:=no; {запишем в p адрес начала очереди} no:=p^.next;

{присваиваем началу очереди адрес следующего элемента}

Dispose(p);

End;

300