Основы программирования — второй семестр 08-09; Михалкович С.С.; II часть — различия между версиями
Juliet (обсуждение | вклад) (→Динамические структуры данных) |
Admin (обсуждение | вклад) (→Доступ к памяти, имеющей другое внутреннее представление) |
||
(не показаны 64 промежуточные версии 11 участников) | |||
Строка 1: | Строка 1: | ||
− | + | [[Категория:Основы программирования]] | |
− | |||
== Указатели == | == Указатели == | ||
Строка 15: | Строка 14: | ||
# С помощью указателей можно создавать сложные '''структуры данных'''. | # С помощью указателей можно создавать сложные '''структуры данных'''. | ||
− | === | + | === Типы указателей === |
Указатели делятся на: | Указатели делятся на: | ||
* '''''Типизированные''''' (указывают на объект некоторого типа) <br />Имеют тип: <tt>'''^<тип>'''</tt> <br /><u>Пример</u>. <tt>^integer</tt> — указатель на integer | * '''''Типизированные''''' (указывают на объект некоторого типа) <br />Имеют тип: <tt>'''^<тип>'''</tt> <br /><u>Пример</u>. <tt>^integer</tt> — указатель на integer | ||
Строка 34: | Строка 33: | ||
end.</source> | end.</source> | ||
<tt>'''@'''</tt> — унарная операция '''взятия адреса''' | <tt>'''@'''</tt> — унарная операция '''взятия адреса''' | ||
− | + | ===Операция разадресации (разыменования)=== | |
<source lang="Pascal">var | <source lang="Pascal">var | ||
i: integer := 5; | i: integer := 5; | ||
Строка 50: | Строка 49: | ||
Тут надо вспомнить определение ссылки: | Тут надо вспомнить определение ссылки: | ||
<br />'''Ссылка''' — другое имя объекта. | <br />'''Ссылка''' — другое имя объекта. | ||
− | + | ===Нулевой указатель=== | |
Все глобальные ''неинициализированные'' указатели хранят специальное значение <tt>'''nil'''</tt>, что говорит о том, что они '''''никуда не указывают'''''. | Все глобальные ''неинициализированные'' указатели хранят специальное значение <tt>'''nil'''</tt>, что говорит о том, что они '''''никуда не указывают'''''. | ||
<br />Указатель, хранящий значение <tt>'''nil'''</tt> называется '''нулевым'''. | <br />Указатель, хранящий значение <tt>'''nil'''</tt> называется '''нулевым'''. | ||
Строка 64: | Строка 63: | ||
//попытка разыменовать нулевой указатель</source> | //попытка разыменовать нулевой указатель</source> | ||
Попытка разыменовать нулевой указатель приводит к '''''ошибке времени выполнения'''''. | Попытка разыменовать нулевой указатель приводит к '''''ошибке времени выполнения'''''. | ||
− | + | ===Бестиповые указатели=== | |
<source lang="Pascal">var | <source lang="Pascal">var | ||
p: pointer; | p: pointer; | ||
Строка 102: | Строка 101: | ||
end.</source> | end.</source> | ||
Запись | Запись | ||
− | ''' | + | ''тип''(''переменная'') |
показывает, что используется '''явное приведение типов'''. | показывает, что используется '''явное приведение типов'''. | ||
<span style="color: red">'''Внимание!''' Неконтролируемая ошибка!</span> | <span style="color: red">'''Внимание!''' Неконтролируемая ошибка!</span> | ||
<source lang="Pascal">type | <source lang="Pascal">type | ||
− | + | preal = ^real; | |
var | var | ||
i, j: integer; | i, j: integer; | ||
Строка 117: | Строка 116: | ||
end.</source> | end.</source> | ||
Область памяти, на которую указывает p трактуется как область, хранящее вещественное число (8 байт), и потому константа 3.14 записывается в эти 8 байт. Однако, переменная i занимает только 4 байта, поэтому затираются еще 4 соседних байта (в данном случае они принадлежат переменной j). | Область памяти, на которую указывает p трактуется как область, хранящее вещественное число (8 байт), и потому константа 3.14 записывается в эти 8 байт. Однако, переменная i занимает только 4 байта, поэтому затираются еще 4 соседних байта (в данном случае они принадлежат переменной j). | ||
− | |||
− | |||
− | type Rec = record | + | === Доступ к памяти, имеющей другое внутреннее представление === |
− | + | <source lang="Pascal">type | |
− | + | Rec = record | |
+ | b1, b2, b3, b4, b5, b6, b7, b8: byte; | ||
+ | end; | ||
− | var | + | PRecord = ^Rec; |
+ | |||
+ | var | ||
+ | r: real := 3.1415; | ||
+ | prec: ^Rec; | ||
begin | begin | ||
− | + | var temp : pointer := @r; | |
− | writeln( | + | prec := temp; |
+ | writeln(prec^.b1, ' ', prec^.b2, ' ', {..., } prec^.b8); | ||
end.</source> | end.</source> | ||
'''Замечание.''' Важно, что типы real и Rec имеют один размер. | '''Замечание.''' Важно, что типы real и Rec имеют один размер. | ||
+ | |||
+ | Другой способ сделать то же самое, но гораздо более безопасный - использовать класс System.BitConverter | ||
+ | <source lang="Delphi"> | ||
+ | uses System; | ||
+ | |||
+ | begin | ||
+ | foreach b: byte in BitConverter.GetBytes(1.0) do | ||
+ | write(b,' '); | ||
+ | end.</source> | ||
+ | |||
+ | === Неявные указатели в языке Pascal === | ||
+ | # <tt>procedure p('''var''' i: integer)</tt> <br />Для параметра-переменной при вызове на стек кладется не сама переменная, а указатель на неё. | ||
+ | # <tt>'''var''' pp: procedure(i: integer)</tt> <br />Для хранения процедурной переменной используется ячейка памяти, являющаяся указателем. | ||
+ | # '''var''' a: '''array of''' real; <br />Переменная типа динамический массив является указателем на данные массива, хранящиеся в динамической памяти. | ||
== Динамическая память == | == Динамическая память == | ||
Строка 138: | Строка 156: | ||
*'''Автоматическую''' <br />(память, занимаемая локальными данными, т.е. стек программы) | *'''Автоматическую''' <br />(память, занимаемая локальными данными, т.е. стек программы) | ||
*'''Динамическую''' <br />(память, выделяемая программе по специальному запросу) | *'''Динамическую''' <br />(память, выделяемая программе по специальному запросу) | ||
− | В | + | В дополнение к статической и автоматической памяти, которые фиксированы после запуска программы, программа может получать нефиксированное количество ''динамической'' памяти. Ограничения на объём выделяемой динамической памяти связаны лишь с настройками операционной системы и объемом оперативной памяти компьютера. |
<br />Основная проблема — явно выделенную динамическую память необходимо возвращать, иначе не хватит памяти другим программам. | <br />Основная проблема — явно выделенную динамическую память необходимо возвращать, иначе не хватит памяти другим программам. | ||
Строка 152: | Строка 170: | ||
p^ := 3; | p^ := 3; | ||
Dispose(p); //возвращает динамическую память, | Dispose(p); //возвращает динамическую память, | ||
− | //контролируемую указателем p, назад | + | //контролируемую указателем p, назад ОС |
end.</source> | end.</source> | ||
По окончании работы программы, вся затребованная программой динамическая память возвращается ОС. | По окончании работы программы, вся затребованная программой динамическая память возвращается ОС. | ||
− | <br />'''''Но лучше освобождать динамическую память явно!''''' | + | <br />'''''Но лучше освобождать динамическую память явно!''''' Иначе в процессе работы программы она может занимать большие объёмы (ещё не освобождённой) памяти, что вредит общей производительности системы. |
+ | |||
=== Ошибки при работе с динамической памятью === | === Ошибки при работе с динамической памятью === | ||
1. <source lang="Pascal">var p: pinteger; | 1. <source lang="Pascal">var p: pinteger; | ||
Строка 161: | Строка 180: | ||
p^ := 5; //ОШИБКА | p^ := 5; //ОШИБКА | ||
end.</source> | end.</source> | ||
− | Ошибка '''''разыменования нулевого указателя''''' (попытка использовать невыделенную динамическую память) | + | Ошибка '''''разыменования нулевого указателя''''' (попытка использовать невыделенную динамическую память). |
2. <source lang="Pascal">var p: pinteger; | 2. <source lang="Pascal">var p: pinteger; | ||
Строка 168: | Строка 187: | ||
New(p); //ОШИБКА | New(p); //ОШИБКА | ||
end.</source> | end.</source> | ||
− | '''''Утечка памяти''''' (память, которая выделилась в результате первого вызова <tt>New(p)</tt> принадлежит программе, но не контролируется никаким указателем. | + | '''''Утечка памяти''''' (память, которая выделилась в результате первого вызова <tt>New(p)</tt>, принадлежит программе, но не контролируется никаким указателем. |
− | + | 2a. <source lang="Pascal"> | |
+ | procedure q; | ||
+ | var p: pinteger; | ||
begin | begin | ||
− | + | New(p); | |
− | + | end; | |
− | end | ||
− | |||
− | |||
− | |||
begin | begin | ||
− | + | q; //ОШИБКА | |
− | |||
− | |||
− | |||
end.</source> | end.</source> | ||
− | + | Утечка памяти в подпрограмме: обычно если динамическая память выделяется в подпрограмме, то она должна в этой же подпрограмме возвращаться. Исключение составляют т.н. "создающие" п/п: | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | <source lang="Pascal"> | |
− | + | function CreateInteger: pinteger; | |
begin | begin | ||
− | + | New(Result); | |
− | + | end; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
begin | begin | ||
− | + | var p: pinteger := CreateInteger; | |
+ | p^ := 555; | ||
+ | Dispose(p); | ||
end.</source> | end.</source> | ||
− | + | Ответственность за удаление памяти, выделенной в подпрограмме, лежит на программисте, вызвавшем эту подпрограмму. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
+ | 3. <source lang="Pascal">var p: pinteger; | ||
begin | begin | ||
− | var | + | for var i:=1 to 1000000 do |
− | + | New(p); //ОШИБКА | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
end.</source> | end.</source> | ||
− | + | '''''Out of Memory''''' (очень большие утечки памяти, в результате которых динамическая память может «исчерпаться»). | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
+ | 4. <source lang="Pascal">var p: pinteger; | ||
begin | begin | ||
− | + | New(p); | |
− | + | p^ := 5; | |
+ | Dispose(p); | ||
+ | p^ := 7; //ОШИБКА | ||
end.</source> | end.</source> | ||
− | + | После вызова <tt>Dispose(p)</tt>, <tt>p</tt> называют '''''висячим указателем''''' (т.к. он указывает на недоступную более область памяти). | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |
Текущая версия на 10:29, 18 февраля 2013
Содержание
Указатели
Адрес
Оперативная память состоит из последовательный ячеек. Каждая ячейка имеет номер, называемый адресом.
В 32-битных системах можно адресовать 232 байт (<math>\approx \;</math> 4Гб) памяти, в 64-битных — 2 64 соответственно.
Переменная (или константа), хранящая адрес, называется указателем.
Для чего нужны указатели
Указатели повышают гибкость доступа к данным:
- Вместо самих данных можно хранить указатель на них. Это позволяет хранить данные в одном экземпляре и множество указателей на эти данные. Через разные указатели эти данные можно обновлять (пример — корпоративная БД).
- Указателю можно присвоить адрес другого объекта (вместо старого появился новый телефонный справочник).
- С помощью указателей можно создавать сложные структуры данных.
Типы указателей
Указатели делятся на:
- Типизированные (указывают на объект некоторого типа)
Имеют тип: ^<тип>
Пример. ^integer — указатель на integer - Бестиповые (хранят адрес ячейки памяти неизвестного типа)
Преимущество: могут хранить что угодно
Имеют тип: pointer
Пример кода.
var
i: integer := 5;
r: real := 6.14;
pi: ^integer;
pr: ^real;
begin
pi := @i;
pr := @r;
pi := @r; // ОШИБКА компиляции
end.
@ — унарная операция взятия адреса
Операция разадресации (разыменования)
var
i: integer := 5;
pi: ^integer;
begin
pi := @i;
pi^ := 8 - pi^;
writeln(i); // 3
end.
^ — операция разыменования
pi^ — то, на что указывает pi, т.е. другое имя i или ссылка на i.
Тут надо вспомнить определение ссылки:
Ссылка — другое имя объекта.
Нулевой указатель
Все глобальные неинициализированные указатели хранят специальное значение nil, что говорит о том, что они никуда не указывают.
Указатель, хранящий значение nil называется нулевым.
var
pi: ^integer; //указатель pi хранит значение nil
i: integer;
begin
pi := @i; //pi хранит адрес переменной i
pi := nil; //pi снова никуда не указывает
pi^ := 7; //ОШИБКА времени выполнения:
//попытка разыменовать нулевой указатель
Попытка разыменовать нулевой указатель приводит к ошибке времени выполнения.
Бестиповые указатели
var
p: pointer;
i: integer;
begin
p := @i;
end.
Бестиповому указателю можно присвоить адрес переменной любого типа, т.е. бестиповой указатель совместим по присваиванию с любым типовым указателем.
Попытка разыменовать бестиповой указатель приводит к ошибке компиляции. Т.е. он может только хранить адреса.
Оказывается, любой типизированный указатель совместим по присваиванию с бестиповым, т.е. следующий код верен:
var
pi: ^integer;
i: integer;
p: pointer;
begin
p := @i;
pi := p;
pi^ += 2;
end.
Вопрос. Нельзя ли интерпретировать память, на которую указывает p, как принадлежащую к определенному типу?
Ответ — да, можно. Вот как это сделать:
type
pinteger = ^integer;
var
i, j: integer;
p: pointer;
begin
p := @i;
pinteger(p)^ := 7; //используем явное приведение типа
writeln(i); // 7
end.
Запись
тип(переменная)
показывает, что используется явное приведение типов.
Внимание! Неконтролируемая ошибка!
type
preal = ^real;
var
i, j: integer;
p: pointer;
begin
p := @i;
preal(p)^ := 3.14; //ОШИБКА!
end.
Область памяти, на которую указывает p трактуется как область, хранящее вещественное число (8 байт), и потому константа 3.14 записывается в эти 8 байт. Однако, переменная i занимает только 4 байта, поэтому затираются еще 4 соседних байта (в данном случае они принадлежат переменной j).
Доступ к памяти, имеющей другое внутреннее представление
type
Rec = record
b1, b2, b3, b4, b5, b6, b7, b8: byte;
end;
PRecord = ^Rec;
var
r: real := 3.1415;
prec: ^Rec;
begin
var temp : pointer := @r;
prec := temp;
writeln(prec^.b1, ' ', prec^.b2, ' ', {..., } prec^.b8);
end.
Замечание. Важно, что типы real и Rec имеют один размер.
Другой способ сделать то же самое, но гораздо более безопасный - использовать класс System.BitConverter
uses System;
begin
foreach b: byte in BitConverter.GetBytes(1.0) do
write(b,' ');
end.
Неявные указатели в языке Pascal
- procedure p(var i: integer)
Для параметра-переменной при вызове на стек кладется не сама переменная, а указатель на неё. - var pp: procedure(i: integer)
Для хранения процедурной переменной используется ячейка памяти, являющаяся указателем. - var a: array of real;
Переменная типа динамический массив является указателем на данные массива, хранящиеся в динамической памяти.
Динамическая память
Особенности динамической памяти
Память, принадлежащая программе, делится на:
- Статическую
(память, занимаемая глобальными переменными и константами) - Автоматическую
(память, занимаемая локальными данными, т.е. стек программы) - Динамическую
(память, выделяемая программе по специальному запросу)
В дополнение к статической и автоматической памяти, которые фиксированы после запуска программы, программа может получать нефиксированное количество динамической памяти. Ограничения на объём выделяемой динамической памяти связаны лишь с настройками операционной системы и объемом оперативной памяти компьютера.
Основная проблема — явно выделенную динамическую память необходимо возвращать, иначе не хватит памяти другим программам.
Для явного выделения и освобождения динамической памяти используются процедуры:
- New
- Dispose
var
p: pinteger; //p никуда не указывает
begin
New(p); //в динамической памяти выделяется ячейка
//размером под один integer, и
//p начинает указывать на эту ячейку
p^ := 3;
Dispose(p); //возвращает динамическую память,
//контролируемую указателем p, назад ОС
end.
По окончании работы программы, вся затребованная программой динамическая память возвращается ОС.
Но лучше освобождать динамическую память явно! Иначе в процессе работы программы она может занимать большие объёмы (ещё не освобождённой) памяти, что вредит общей производительности системы.
Ошибки при работе с динамической памятью
1.var p: pinteger;
begin
p^ := 5; //ОШИБКА
end.
Ошибка разыменования нулевого указателя (попытка использовать невыделенную динамическую память).
2.var p: pinteger;
begin
New(p);
New(p); //ОШИБКА
end.
Утечка памяти (память, которая выделилась в результате первого вызова New(p), принадлежит программе, но не контролируется никаким указателем.
2a.procedure q;
var p: pinteger;
begin
New(p);
end;
begin
q; //ОШИБКА
end.
Утечка памяти в подпрограмме: обычно если динамическая память выделяется в подпрограмме, то она должна в этой же подпрограмме возвращаться. Исключение составляют т.н. "создающие" п/п:
function CreateInteger: pinteger;
begin
New(Result);
end;
begin
var p: pinteger := CreateInteger;
p^ := 555;
Dispose(p);
end.
Ответственность за удаление памяти, выделенной в подпрограмме, лежит на программисте, вызвавшем эту подпрограмму.
3.var p: pinteger;
begin
for var i:=1 to 1000000 do
New(p); //ОШИБКА
end.
Out of Memory (очень большие утечки памяти, в результате которых динамическая память может «исчерпаться»).
4.var p: pinteger;
begin
New(p);
p^ := 5;
Dispose(p);
p^ := 7; //ОШИБКА
end.
После вызова Dispose(p), p называют висячим указателем (т.к. он указывает на недоступную более область памяти).