Для того, чтобы лучше понять специфику динамически выделяемой памяти, рассмотрим сначала ее "антипод" - память, распределяемую статически.
Такое выделение памяти используется всякий раз при var. Каждая переменная обладает двумя атрибутами:
var a: integer;
При
Лучшая иллюстрация = сегмент ) и только затем номер строки, считая от начала этой страницы ( = смещение ).
Для обращения к статически заданной переменной можно использовать как ее var, так и ее физический
Например, "
Для того чтобы хранить (цифровые)
При
var <имя_указателя>: ^<тип_адресуемой_переменной>;
Например:
var p: ^integer; q: ^real; s: ^array[1..10] of byte;
Кроме того, существуют универсальные
var <имя_указателя>: pointer;
Физический addr(<имя_переменной>):<указатель> или @<имя_переменной>.
В зависимости от значения {$T}, результатом операции @ будет либо {$T+} ), тип которого будет определен в соответствии с типом использованной переменной, либо {$T-} ).
Результат функции addr() совместим с
p:= addr(x); {x: real; p: ^byte)
Для того чтобы воспользоваться значением, хранящимся по некоторому ^ называется
<имя_указателя>^
Результатом операции ^ является значение, хранящееся по указанному
Из-за вольностей, допускаемых процедурой addr(), при
const a: array[1..3] of char ='ААА'; {код(А)=128 или 01000000}
var p: ^word;
begin p:= addr(a);
writeln(p^)
end
на экран будет выведено 32896, что в 01000000.01000000 (точкой помечена граница двух байтов). Иными словами, коды двух первых букв оказались слитыми в значение типа word.
Замечание: Операции @ и ^ являются взаимно обратными, то есть для любой переменной a и для любого типизированного p верны следующие равенства:
@(p^)= p и (@a)^ = a
Для
p:= q; {p: ^integer; q: ^byte}
Обойти эти ограничения позволяет универсальность
{p: ^integer; q: ^byte; t: pointer}
t:= q;
p:= t;
У
p:= nil;
Замечание: Если
Для = и <>.
Две переменные, описанные как
Для разнотипных
if p = q then writeln('yes'); {p: ^byte; q: ^integer}
вызовет ошибку уже на этапе компиляции.
Однако сравнивать
Поскольку к любой переменной можно обратиться двояко - по var, то в процессе компиляции у нее появится и
Задумаемся теперь: а если у переменной есть
Итак, пусть у некоторой переменной нет
"Безымянные" переменные отличаются от "нормальных" переменных:
var.Для выделения памяти служит стандартная процедура new():
new(<имя_указателя>);
Эта процедура ищет в незанятой памяти подходящий по размеру кусок и, "застолбив" это место для безымянной new() создает
Например, если переменная p была описана как integer -переменную, то процедура new(p) выделит два байта; под real -переменную необходимо выделить четыре байта и т.д.
Для того чтобы выделить память, на которую будет указывать нетипизированный getmem(p: , которая выделит столько байт свободной памяти, сколько указано в переменной size.
Для уничтожения
dispose(<имя_типизир_указателя>).
Процедура p.
В результате
dispose(p); p:= nil;
Для того чтобы освободить память, на которую указывает нетипизированный freemem(p: , которая освободит в памяти столько байтов (начиная с указанного в переменной p size.
Если для каждой
Следовательно, нужно сделать так, чтобы место под хранение
Списки применяются, например, в таких ситуациях:
Итак, каждый элемент создаваемого списка должен содержать:
integer, real, array, record и т.п.;Приведем примеры различных
Сначала мы рассмотрим только самый простой случай:
(рис 10.1) Примеры списочных структурЛогичнее всего было бы дать этой структуре такое
type element_spiska = record znachenie : integer; next_element : ^element_spiska; end;
Однако этот вариант невозможен по правилам языка
type ukazatel = ^element_spiska; element_spiska = record znachenie : integer; next_element : ukazatel; end;
Обратите внимание: это единственный случай, когда компилятор согласится принять использование структуры ( element_spiska ) до ее
Замечание: Кажется, что гораздо более естественным было бы отнести поле next_element к типу ukazatel. Однако неудобства, которые непременно возникнут из-за
В качестве примера приведем
| a) | type ukazatel = ^elem_spiska;
elem_spiska = record
znach : integer;
sled : ukazatel;
end;
|
|
| b) | type point = ^element_spiska; list = record znachenie : integer; sled : point pred : point; end; |
|
| с) | type point = ^tree;
tree = record
data : integer;
left_sibling : point;
right_sibling: point;
end;
|
|
| d) | ( |
type uk_versh = ^versh; uk_duga = ^duga; vershina = record nomer : integer; sled_versh : uk_versh; spisok_dug : uk_duga; end; duga = record konec_dugi : uk_versh; sled_duga : uk_duga; end; |
Для того чтобы сохранить информацию обо всем списке, достаточно только одной переменной -
Например:
var head,p,q: uk_spisok;
Но, вообще говоря, нет никаких специальных правил, которые обязали бы программиста давать выделенным head, tree_root и start.
Если есть
p |
- |
p^ |
- запись из нескольких полей, хранящаяся по p ; |
p^.znachenie |
- значение первого поля этой записи; |
p^.next_element |
- значение второго поля этой записи, являющееся |
p^.next_element^.znachenie |
- значение, хранящееся в первом поле элемента списка, следующего за тем, на который указывает р. |
(рис 10.2) Правила обращения к элементам списка
Предположим, что есть некоторый набор значений (например, в файле), которые необходимо записать в создаваемый
Мы приведем здесь обе программы, позволив себе для краткости опустить
var head,p: ukazatel; f: text;
begin
...
head:= nil;
while not eof(f) do
begin
new(p);
read(f,p^.znach);
p^.next:= head;
head:= p;
end;
end.
|
 (рис 10.3) Очередной шаг процесса генерации списка "от хвоста к голове" |
var head,p,q: ukazatel; f: text;
begin
...
if eof(f)
then head:= nil
else begin
new(head); {головной элемент создается отдельно}
read(f,head^.znach);
head^.next:= nil;
q:= head;
while not eof(f) do
begin
new(p);
read(f,p^.znach);
p^.next:= nil;
q^.next:= p;
q:= q^.next;
end;
end;
end.
|
 (рис 10.4) Очередной шаг процесса генерации списка "от головы к хвосту" |
Для того чтобы распечатать значения, хранящиеся в элементах линейного односвязного списка, заданного
p:= head; {начать просмотр с головы списка}
while p<>nil do
begin
writeln(p^.znach);
p:= p^.next; {переход к следующему элементу списка}
end;
Замечание: Для того чтобы во время работы со списком не произошло выхода за его пределы, любой список обязательно должен оканчиваться "нулевым"
Для того чтобы при удалении элемента из середины списка не терялась целостность всей структуры, необходимо при поиске удаляемого элемента "остановиться" за один шаг до него: в тот момент, когда следующий за текущим элемент должен быть удален (см. рис. 10.5):
p:= head; {начать с головы списка}
while p^.next^.zhach<>х do p:= p^.next; {поиск}
q:= p^.next; {удаляемый элемент}
p^.next:= q^.next; {связка "через один"}
dispose(q); {освобождение памяти}
Разницу между структурой статической (массив) и структурой динамической (список) очень доступно проиллюстрировал Никлаус Вирт в своей книге "Алгоритмы и структуры данных". Мы позволим себе позаимствовать оттуда, хотя и не дословно, красивый пример.
Представим обычную очередь у прилавка в магазине. Первый покупатель - это тот, кто в данную минуту стоит непосредственно возле прилавка; следующий за ним - второй, за вторым - третий и т.д. Покупатели занумерованы строго в порядке следования, и вновь пришедшие встают в хвост. В принципе, взглянув на очередь, всегда можно сказать, кто за кем стоит. А что происходит, если один из покупателей желает покинуть очередь? Хвост тут же сдвигается: каждый человек делает шаг вперед, чтобы очередь не утратила целостности. Если же, наоборот, некто желает встроиться в середину очереди (невзирая на крики "А вас тут не стояло!"), то задним приходится пятиться, чтобы освободить ему место. Точно так же ведут себя элементы линейного массива.
Теперь возьмем другую очередь: в приемной у зубного врача. Во-первых, посетители уже не привязаны так жестко к линии прилавка: они сидят в креслах, расположенных там и сям, где только нашлось удобное место. Во-вторых, каждому вновь пришедшему нет необходимости знать, кто в этой очереди первый, а кто второй: достаточно лишь выяснить, кто последний. И вовсе не обязательно садиться рядом с последним пациентом: вновь пришедший может занять любое свободное кресло в приемной. А если у кого-то вдруг перестали болеть зубы и он радостно уходит из очереди, то "стоявшему" за ним достаточно спросить: - "А вы за кем занимали?" При этом физического перемещения пациентов в пространстве не происходит. Аналогично, если вдруг появляется пациент с талончиком на более раннее время, "задние" пропускают его вперед, не сдвигаясь со своих кресел. Именно так ведут себя и элементы динамических
На рис. 10.5 приведены четыре примера перестройки односвязных списков. Пунктирами изображены
Приведем фрагменты программ, решающих первую и третью задачи:
{- голову списка обрабатываем отдельно -}
while (head<>nil)and(head^.znach =0)do
begin p:= head;
head:= head^.next;
dispose(p);
end;
{- середина и конец списка обрабатываются вместе -}
p:= head;
while p^.next <> nil do
if p^.next^.znach = 0
then begin q:= p^.next;
p^.next:= p^.next^.next;
dispose(q);
end
else
p:= p^.next;
p:= head^.next; head^.next:= p^.next; p^.next:= p^.next^.next; head^.next^.next:= p;
(рис 10.5) Примеры перестройки односвязных списков
Для того, чтобы лучше понять специфику динамически выделяемой памяти, рассмотрим сначала ее "антипод" - память, распределяемую статически.
Такое выделение памяти используется всякий раз при var. Каждая переменная обладает двумя атрибутами:
var a: integer;
При
Лучшая иллюстрация = сегмент ) и только затем номер строки, считая от начала этой страницы ( = смещение ).
Для обращения к статически заданной переменной можно использовать как ее var, так и ее физический
Например, "
Для того чтобы хранить (цифровые)
При
var <имя_указателя>: ^<тип_адресуемой_переменной>;
Например:
var p: ^integer; q: ^real; s: ^array[1..10] of byte;
Кроме того, существуют универсальные
var <имя_указателя>: pointer;
Физический addr(<имя_переменной>):<указатель> или @<имя_переменной>.
В зависимости от значения {$T}, результатом операции @ будет либо {$T+} ), тип которого будет определен в соответствии с типом использованной переменной, либо {$T-} ).
Результат функции addr() совместим с
p:= addr(x); {x: real; p: ^byte)
Для того чтобы воспользоваться значением, хранящимся по некоторому ^ называется
<имя_указателя>^
Результатом операции ^ является значение, хранящееся по указанному
Из-за вольностей, допускаемых процедурой addr(), при
const a: array[1..3] of char ='ААА'; {код(А)=128 или 01000000}
var p: ^word;
begin p:= addr(a);
writeln(p^)
end
на экран будет выведено 32896, что в 01000000.01000000 (точкой помечена граница двух байтов). Иными словами, коды двух первых букв оказались слитыми в значение типа word.
Замечание: Операции @ и ^ являются взаимно обратными, то есть для любой переменной a и для любого типизированного p верны следующие равенства:
@(p^)= p и (@a)^ = a
Для
p:= q; {p: ^integer; q: ^byte}
Обойти эти ограничения позволяет универсальность
{p: ^integer; q: ^byte; t: pointer}
t:= q;
p:= t;
У
p:= nil;
Замечание: Если
Для = и <>.
Две переменные, описанные как
Для разнотипных
if p = q then writeln('yes'); {p: ^byte; q: ^integer}
вызовет ошибку уже на этапе компиляции.
Однако сравнивать
Поскольку к любой переменной можно обратиться двояко - по var, то в процессе компиляции у нее появится и
Задумаемся теперь: а если у переменной есть
Итак, пусть у некоторой переменной нет
"Безымянные" переменные отличаются от "нормальных" переменных:
var.Для выделения памяти служит стандартная процедура new():
new(<имя_указателя>);
Эта процедура ищет в незанятой памяти подходящий по размеру кусок и, "застолбив" это место для безымянной new() создает
Например, если переменная p была описана как integer -переменную, то процедура new(p) выделит два байта; под real -переменную необходимо выделить четыре байта и т.д.
Для того чтобы выделить память, на которую будет указывать нетипизированный getmem(p: , которая выделит столько байт свободной памяти, сколько указано в переменной size.
Для уничтожения
dispose(<имя_типизир_указателя>).
Процедура p.
В результате
dispose(p); p:= nil;
Для того чтобы освободить память, на которую указывает нетипизированный freemem(p: , которая освободит в памяти столько байтов (начиная с указанного в переменной p size.
Если для каждой
Следовательно, нужно сделать так, чтобы место под хранение
Списки применяются, например, в таких ситуациях:
Итак, каждый элемент создаваемого списка должен содержать:
integer, real, array, record и т.п.;Приведем примеры различных
Сначала мы рассмотрим только самый простой случай:
(рис 10.1) Примеры списочных структурЛогичнее всего было бы дать этой структуре такое
type element_spiska = record znachenie : integer; next_element : ^element_spiska; end;
Однако этот вариант невозможен по правилам языка
type ukazatel = ^element_spiska; element_spiska = record znachenie : integer; next_element : ukazatel; end;
Обратите внимание: это единственный случай, когда компилятор согласится принять использование структуры ( element_spiska ) до ее
Замечание: Кажется, что гораздо более естественным было бы отнести поле next_element к типу ukazatel. Однако неудобства, которые непременно возникнут из-за
В качестве примера приведем
| a) | type ukazatel = ^elem_spiska;
elem_spiska = record
znach : integer;
sled : ukazatel;
end;
|
|
| b) | type point = ^element_spiska; list = record znachenie : integer; sled : point pred : point; end; |
|
| с) | type point = ^tree;
tree = record
data : integer;
left_sibling : point;
right_sibling: point;
end;
|
|
| d) | ( |
type uk_versh = ^versh; uk_duga = ^duga; vershina = record nomer : integer; sled_versh : uk_versh; spisok_dug : uk_duga; end; duga = record konec_dugi : uk_versh; sled_duga : uk_duga; end; |
Для того чтобы сохранить информацию обо всем списке, достаточно только одной переменной -
Например:
var head,p,q: uk_spisok;
Но, вообще говоря, нет никаких специальных правил, которые обязали бы программиста давать выделенным head, tree_root и start.
Если есть
p |
- |
p^ |
- запись из нескольких полей, хранящаяся по p ; |
p^.znachenie |
- значение первого поля этой записи; |
p^.next_element |
- значение второго поля этой записи, являющееся |
p^.next_element^.znachenie |
- значение, хранящееся в первом поле элемента списка, следующего за тем, на который указывает р. |
(рис 10.2) Правила обращения к элементам списка
Предположим, что есть некоторый набор значений (например, в файле), которые необходимо записать в создаваемый
Мы приведем здесь обе программы, позволив себе для краткости опустить
var head,p: ukazatel; f: text;
begin
...
head:= nil;
while not eof(f) do
begin
new(p);
read(f,p^.znach);
p^.next:= head;
head:= p;
end;
end.
|
(рис 10.3) Очередной шаг процесса генерации списка "от хвоста к голове" |
var head,p,q: ukazatel; f: text;
begin
...
if eof(f)
then head:= nil
else begin
new(head); {головной элемент создается отдельно}
read(f,head^.znach);
head^.next:= nil;
q:= head;
while not eof(f) do
begin
new(p);
read(f,p^.znach);
p^.next:= nil;
q^.next:= p;
q:= q^.next;
end;
end;
end.
|
(рис 10.4) Очередной шаг процесса генерации списка "от головы к хвосту" |
Для того чтобы распечатать значения, хранящиеся в элементах линейного односвязного списка, заданного
p:= head; {начать просмотр с головы списка}
while p<>nil do
begin
writeln(p^.znach);
p:= p^.next; {переход к следующему элементу списка}
end;
Замечание: Для того чтобы во время работы со списком не произошло выхода за его пределы, любой список обязательно должен оканчиваться "нулевым"
Для того чтобы при удалении элемента из середины списка не терялась целостность всей структуры, необходимо при поиске удаляемого элемента "остановиться" за один шаг до него: в тот момент, когда следующий за текущим элемент должен быть удален (см. рис. 10.5):
p:= head; {начать с головы списка}
while p^.next^.zhach<>х do p:= p^.next; {поиск}
q:= p^.next; {удаляемый элемент}
p^.next:= q^.next; {связка "через один"}
dispose(q); {освобождение памяти}
Разницу между структурой статической (массив) и структурой динамической (список) очень доступно проиллюстрировал Никлаус Вирт в своей книге "Алгоритмы и структуры данных". Мы позволим себе позаимствовать оттуда, хотя и не дословно, красивый пример.
Представим обычную очередь у прилавка в магазине. Первый покупатель - это тот, кто в данную минуту стоит непосредственно возле прилавка; следующий за ним - второй, за вторым - третий и т.д. Покупатели занумерованы строго в порядке следования, и вновь пришедшие встают в хвост. В принципе, взглянув на очередь, всегда можно сказать, кто за кем стоит. А что происходит, если один из покупателей желает покинуть очередь? Хвост тут же сдвигается: каждый человек делает шаг вперед, чтобы очередь не утратила целостности. Если же, наоборот, некто желает встроиться в середину очереди (невзирая на крики "А вас тут не стояло!"), то задним приходится пятиться, чтобы освободить ему место. Точно так же ведут себя элементы линейного массива.
Теперь возьмем другую очередь: в приемной у зубного врача. Во-первых, посетители уже не привязаны так жестко к линии прилавка: они сидят в креслах, расположенных там и сям, где только нашлось удобное место. Во-вторых, каждому вновь пришедшему нет необходимости знать, кто в этой очереди первый, а кто второй: достаточно лишь выяснить, кто последний. И вовсе не обязательно садиться рядом с последним пациентом: вновь пришедший может занять любое свободное кресло в приемной. А если у кого-то вдруг перестали болеть зубы и он радостно уходит из очереди, то "стоявшему" за ним достаточно спросить: - "А вы за кем занимали?" При этом физического перемещения пациентов в пространстве не происходит. Аналогично, если вдруг появляется пациент с талончиком на более раннее время, "задние" пропускают его вперед, не сдвигаясь со своих кресел. Именно так ведут себя и элементы динамических
На рис. 10.5 приведены четыре примера перестройки односвязных списков. Пунктирами изображены
Приведем фрагменты программ, решающих первую и третью задачи:
{- голову списка обрабатываем отдельно -}
while (head<>nil)and(head^.znach =0)do
begin p:= head;
head:= head^.next;
dispose(p);
end;
{- середина и конец списка обрабатываются вместе -}
p:= head;
while p^.next <> nil do
if p^.next^.znach = 0
then begin q:= p^.next;
p^.next:= p^.next^.next;
dispose(q);
end
else
p:= p^.next;
p:= head^.next; head^.next:= p^.next; p^.next:= p^.next^.next; head^.next^.next:= p;
(рис 10.5) Примеры перестройки односвязных списков
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.