Основы программирования — второй семестр 08-09; Михалкович С.С.; II часть — различия между версиями
(→Шаблоны классов: Пример приведен в соответствие с тем, что было на лекции, а не с личными предпочтениями составителя конспекта.) |
Juliet (обсуждение | вклад) (→Динамические структуры данных) |
||
Строка 304: | Строка 304: | ||
Их основная проблема — фиксированный размер, определяемый на этапе компиляции. | Их основная проблема — фиксированный размер, определяемый на этапе компиляции. | ||
<br />Решением проблемы являются '''динамические структуры данных'''. Они строятся из '''узлов''', которые, в свою очередь, состоят из '''''данных''''' и '''''узлов связи'''''. | <br />Решением проблемы являются '''динамические структуры данных'''. Они строятся из '''узлов''', которые, в свою очередь, состоят из '''''данных''''' и '''''узлов связи'''''. | ||
+ | |||
+ | Рассмотрим такой пример: | ||
<source lang="Pascal">type | <source lang="Pascal">type | ||
Node<DataType> = class | Node<DataType> = class | ||
Строка 320: | Строка 322: | ||
// p начал указывать на эту динамическую память | // p начал указывать на эту динамическую память | ||
end.</source> | end.</source> | ||
− | |||
− | |||
− | |||
=== Виды списков === | === Виды списков === | ||
− | # Линейный односвязный список | + | # ''Линейный односвязный список''<br>[[Изображение:Линейный_односвязный_список.png]] |
− | # Циклический односвязный список | + | # ''Циклический односвязный список''<br>[[Изображение:Циклический_односвязный_список.png]] |
− | # Двусвязный линейный список | + | # ''Двусвязный линейный список''<br> [[Изображение:Двусвязный_линейный_список.png|Двусвязный_линейный_список.png]] |
− | # Циклический двусвязный список | + | # ''Циклический двусвязный список''<br>[[Изображение:Циклический_двусвязный_список.png]] |
− | |||
=== Односвязные линейные списки === | === Односвязные линейные списки === | ||
− | + | <source lang="Pascal">type | |
− | <source lang="Pascal"> | + | Node<DataType> = class |
− | + | data: DataType; | |
− | data:DataType; | + | next: Node<DataType>; |
− | next:Node <DataType>; | + | |
− | constructor (d:DataType;n:Node <DataType>); | + | constructor (d: DataType; n: Node<DataType>); |
− | + | begin | |
− | + | data := d; | |
− | + | naxt := n; | |
− | |||
end; | end; | ||
− | + | end; | |
− | Стандартные операции с односвязными линейными списками | + | begin |
− | * Вставка элемента в начало <br> [[Изображение:Добавление_элемента_в_начало_линейного_односвязного_списка.gif]] | + | {Пусть у нас есть указатель на начало списка:} |
− | * Удаление элемента из начала <br> [[Изображение:Удаление начального элемента.gif]] | + | var head: Node<char>; |
− | * Вставка после текущего <br> [[Изображение:Вставка элемента после текущего.gif]] | + | // инициализация head</source> |
− | * Удаление после текущего <br> [[Изображение:Удаление после текущего.gif]] | + | |
− | * Проход по списку <br> [[Изображение:Проход_по_списку.gif]] | + | <xh4>Стандартные операции с односвязными линейными списками</xh4> |
+ | * '''''Вставка элемента в начало''''' <br> [[Изображение:Добавление_элемента_в_начало_линейного_односвязного_списка.gif]] <br /> При многократной вставке в начало элементы располагаются в ''обратном порядке''. | ||
+ | * '''''Удаление элемента из начала''''' <br> [[Изображение:Удаление начального элемента.gif]] <br />Если изначально список пуст, произойдет ошибка<span style="color: red"> "попытка разыменования нулевого указателя"</span>. Эту ситуацию надо предусмотреть: | ||
+ | <source lang="Pascal">if head <> nil then | ||
+ | head := head.next;</source> | ||
+ | * '''''Вставка элемента после текущего''''' <br> [[Изображение:Вставка элемента после текущего.gif]] <br />Если <tt>cur</tt> никуда не указывает, произойдет ошибка. Предусмотрим эту ситуацию: | ||
+ | <source lang="Pascal">if cur <> nil then | ||
+ | cur.next := new Node<char>('d', cur.next);</source> | ||
+ | Заметим также, что если <tt>cur</tt> указывает на последний элемент списка, ошибки не произойдет (фактически, будет произведена ''вставка в конец списка''). | ||
+ | * '''''Удаление элемента после текущего''''' <br> [[Изображение:Удаление после текущего.gif]] <br />Для того, чтобы не произошло ошибки разыменования нулевого указателя, необходимо, чтобы <tt>cur</tt> не был последним элементом, т.к. разыменование происходит дважды (<tt>'''cur.'''next</tt> и <tt>'''cur.next.'''next</tt>). Эту ситуацию также надо предусмотреть: | ||
+ | <source lang="Pascal">if (cur <> nil) and (cur.next <> nil) then | ||
+ | cur.next := cur.next.next;</source> | ||
+ | * '''''Проход по списку''''' <br> [[Изображение:Проход_по_списку.gif]] | ||
+ | <source lang="Pascal"></source> | ||
+ | <xh4>Примеры использования</xh4> | ||
===Двусвязные линейные списки=== | ===Двусвязные линейные списки=== | ||
− | + | <xh4></xh4><source lang="Pascal"></source> | |
Стандартные операции с двусвязными линейными списками | Стандартные операции с двусвязными линейными списками | ||
* Инициализация | * Инициализация |
Версия 22:04, 6 марта 2009
Лекция 3
Содержание
Указатели
Адрес
Оперативная память состоит из последовательный ячеек. Каждая ячейка имеет номер, называемый адресом.
В 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.
@ — унарная операция взятия адреса <xh4>Операция разадресации (разыменования)</xh4>
var
i: integer := 5;
pi: ^integer;
begin
pi := @i;
pi^ := 8 - pi^;
writeln(i); // 3
end.
^ — операция разыменования
pi^ — то, на что указывает pi, т.е. другое имя i или ссылка на i.
Тут надо вспомнить определение ссылки:
Ссылка — другое имя объекта.
<xh4>Нулевой указатель</xh4>
Все глобальные неинициализированные указатели хранят специальное значение nil, что говорит о том, что они никуда не указывают.
Указатель, хранящий значение nil называется нулевым.
var
pi: ^integer; //указатель pi хранит значение nil
i: integer;
begin
pi := @i; //pi хранит адрес переменной i
pi := nil; //pi снова никуда не указывает
pi^ := 7; //ОШИБКА времени выполнения:
//попытка разыменовать нулевой указатель
Попытка разыменовать нулевой указатель приводит к ошибке времени выполнения. <xh4>Бестиповые указатели</xh4>
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
pinteger = ^integer;
var
i, j: integer;
p: pointer;
begin
p := @i;
preal(p)^ := 3.14; //ОШИБКА!
end.
Область памяти, на которую указывает p трактуется как область, хранящее вещественное число (8 байт), и потому константа 3.14 записывается в эти 8 байт. Однако, переменная i занимает только 4 байта, поэтому затираются еще 4 соседних байта (в данном случае они принадлежат переменной j).
Доступ к памяти, имеющей другое внутреннее представление
var r: real := 3.1415;
type Rec = record
b1, b2, b3, b4, b5, b6, b7, b8: byte;
end;
var pr: ^Rec;
begin
pr := pointer(@r); //Явное приведение типа
writeln(pr^.b1, ' ', pr^.b2, ' ', ..., pr^.b8);
end.
Замечание. Важно, что типы real и Rec имеют один размер.
Динамическая память
Особенности динамической памяти
Память, принадлежащая программе, делится на:
- Статическую
(память, занимаемая глобальными переменными и константами) - Автоматическую
(память, занимаемая локальными данными, т.е. стек программы) - Динамическую
(память, выделяемая программе по специальному запросу)
В отличие от статической и автоматической памяти, которые фиксированы после запуска программы, программа еще может получать любое количество динамической памяти, ограниченное лишь объемом оперативной памяти.
Основная проблема — явно выделенную динамическую память необходимо возвращать, иначе не хватит памяти другим программам.
Для явного выделения и освобождения динамической памяти используются процедуры:
- 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) принадлежит программе, но не контролируется никаким указателем.
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 называют висячим указателем (т.к. он указывает на недоступную более область памяти)
Неявные указатели в языке Pascal
- procedure p(var i: integer)
Для параметра-переменной при вызове на стек кладется не сама переменная, а указатель на неё. - var pp: procedure(i: integer)
Для хранения процедурной переменной используется ячейка памяти, являющаяся указателем. - var a: array of real;
Переменная типа динамический массив является указателем на данные массива, хранящиеся в динамической памяти.
Введение в классы
От записей к классам
Рассмотрим запись студент:
type
Student = record
name: string;
age: integer;
procedure Init(n: string; a: integer);
begin
name := n;
age := a;
end;
procedure Print;
begin
writelnFormat('Имя: {0} Возраст: {1}',
name, age);
end;
end;
var
s: student;
begin
s.Init('Иванов', 18);
end.
Когда мы описываем переменную типа Student, она кладется на программный стек.
А вот так выглядит класс Student:
type
Student = class
name: string;
age: integer;
constructor Create(n: string; a: integer);
begin
name := n;
age := a;
end;
procedure Print;
begin
writelnFormat('Имя: {0} Возраст: {1}',
name, age);
end;
end;
var
s: student;
begin
s := New Student('Иванов', 18);
end.
Переменная типа класс является указателем. Для выделения динамической памяти под объект класса Student используется вызов специального метода, называемого конструктором (New Student(<имя>, <возраст>)).
Лекция 4
Шаблоны классов
type
Point<T> = class
x, y: T;
constructor(_x, _y: T);
begin
x := _x;
y := _y;
end;
end;
begin
var p1 : Point<real>;
var p2 : Point<integer>;
p1 := new Point<real>(2.3, 5.7);
p2 := new Point<integer>(2, 7);
p1.x := 2;
p2.x := 1.5; // ошибка компиляции, т.к.
// тип поля x объекта класса Point<integer> (integer)
// не совместим по присваиваиванию с вещественным типом real
//можем пользоваться автоопределением типов:
var p3 := new Point<real>(3.14, 7.9);
end.
Тип Point<T> называют обощенным типом.
Теперь рассмотрим присваивание объектов класса:
var p11 := new Point<real>(0, 1.5);
var p12 := new Point<real>(2.3, 5);
p11 := p12; // происходит присваивание ссылок:
// p11 теперь указывает на тот же объект, что и p12;
// область памяти, на которую до этого указывал p11 более недоступна
var p2 := new Point<integer>(5, 7);
p11 := p2; // ошибка
// типы объектов не совпадают
При присваивании же друг другу записей, происходит копирование самих записей.
Сборка мусора
(Garbage collection)
Мусор — любые ненужные объекты.
Под ненужными понимаются объекты, которые занимают память, но недоступны в программе.
Сборка мусора — процесс освобождения памяти, занятой ненужными объектами.
Обычно, сборка мусора запускается при нехватке места в памяти. Это позволяет не заботиться об утечках памяти, т.к. все выделенное — освободится. (При этом, от всех остальных ошибок мы не застрахованы!!!)
Главный недостаток механизма сборки мусора — во время сборки выполнение программы приостанавливается.
Динамические структуры данных
Введение
Сейчас структуры данных занимают в программировании все более важную позицию.
Мы уже знаем такие структуры, как:
- массивы (подразумеваем статические)
- записи
Их основная проблема — фиксированный размер, определяемый на этапе компиляции.
Решением проблемы являются динамические структуры данных. Они строятся из узлов, которые, в свою очередь, состоят из данных и узлов связи.
Рассмотрим такой пример:
type
Node<DataType> = class
data: DataType;
next: Node<DataType>;
constructor (d: DataType; n: Node<DataType>);
begin
data := d;
naxt := n;
end;
end;
begin
var p := new Node<char>('!', nil); // под объект класса Node<char> выделилась динамическая память;
// p начал указывать на эту динамическую память
end.
Виды списков
- Линейный односвязный список
- Циклический односвязный список
- Двусвязный линейный список
- Циклический двусвязный список
Односвязные линейные списки
type
Node<DataType> = class
data: DataType;
next: Node<DataType>;
constructor (d: DataType; n: Node<DataType>);
begin
data := d;
naxt := n;
end;
end;
begin
{Пусть у нас есть указатель на начало списка:}
var head: Node<char>;
// инициализация head
<xh4>Стандартные операции с односвязными линейными списками</xh4>
- Вставка элемента в начало
При многократной вставке в начало элементы располагаются в обратном порядке. - Удаление элемента из начала
Если изначально список пуст, произойдет ошибка "попытка разыменования нулевого указателя". Эту ситуацию надо предусмотреть:
if head <> nil then
head := head.next;
- Вставка элемента после текущего
Если cur никуда не указывает, произойдет ошибка. Предусмотрим эту ситуацию:
if cur <> nil then
cur.next := new Node<char>('d', cur.next);
Заметим также, что если cur указывает на последний элемент списка, ошибки не произойдет (фактически, будет произведена вставка в конец списка).
- Удаление элемента после текущего
Для того, чтобы не произошло ошибки разыменования нулевого указателя, необходимо, чтобы cur не был последним элементом, т.к. разыменование происходит дважды (cur.next и cur.next.next). Эту ситуацию также надо предусмотреть:
if (cur <> nil) and (cur.next <> nil) then
cur.next := cur.next.next;
<xh4>Примеры использования</xh4>
Двусвязные линейные списки
<xh4></xh4>Стандартные операции с двусвязными линейными списками
- Инициализация
- Добавление в начало, конец
- Удаление из начала, конца
- Вставка элемента перед текущим, после текущего
- Удаление текущего
- Объединение двух списков
Помещение операций по работе со списком внутрь класса