Основы программирования — второй семестр 08-09; Михалкович С.С.; II часть

Материал из Вики ИТ мехмата ЮФУ
Версия от 20:11, 6 марта 2009; Juliet (обсуждение | вклад) (→‎Введение в классы)

Перейти к: навигация, поиск

Лекция 3

Указатели

Адрес

Оперативная память состоит из последовательный ячеек. Каждая ячейка имеет номер, называемый адресом.
В 32-битных системах можно адресовать 232 байт (<math>\approx \;</math> 4Гб) памяти, в 64-битных — 2 64 соответственно.

Переменная (или константа), хранящая адрес, называется указателем.

Для чего нужны указатели

Указатели повышают гибкость доступа к данным:

  1. Вместо самих данных можно хранить указатель на них. Это позволяет хранить данные в одном экземпляре и множество указателей на эти данные. Через разные указатели эти данные можно обновлять (пример — корпоративная БД).
  2. Указателю можно присвоить адрес другого объекта (вместо старого появился новый телефонный справочник).
  3. С помощью указателей можно создавать сложные структуры данных.

Подробнее об указателях

Указатели делятся на:

  • Типизированные (указывают на объект некоторого типа)
    Имеют тип: ^<тип>
    Пример. ^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

  1. procedure p(var i: integer)
    Для параметра-переменной при вызове на стек кладется не сама переменная, а указатель на неё.
  2. var pp: procedure(i: integer)
    Для хранения процедурной переменной используется ячейка памяти, являющаяся указателем.
  3. 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(xx, yy: T);
    begin
      x := xx;
      y := yy;
    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;   // ошибка
             // типы объектов не совпадают

При присваивании же друг другу записей, происходит копирование самих записей. <xh4></xh4> 



Решение проблемы освобождения памяти, занимаемой объектами классов: сборка мусора (.NET, Java).

Управляемая динамическая память и ее возврат. Отсутствие утечки памяти.



Динамические структуры данных. Списки


Виды списков:



  1.  Линейный односвязный список.
    Линейный односвязный список.png
    2. 

  2.  Циклический односвязный список.
    Циклический односвязный список.png
    3. 

  3.  Двусвязный линейный список.
     Двусвязный_линейный_список.png
    4. 

  4.  Циклический двусвязный список. 
    Циклический двусвязный список.png


Односвязные линейные списки


Класс узла списка (шаблонный):



type Node <DataType> = class
    data:DataType;
    next:Node <DataType>;
    constructor (d:DataType;n:Node <DataType>);
        begin
        data:=d;
        next:=n;
        end;
    end;


Стандартные операции с односвязными линейными списками:



  •  Вставка элемента в начало 
     Добавление элемента в начало линейного односвязного списка.gif
    • 

  •  Удаление элемента из начала 
     Удаление начального элемента.gif
    • 

  •  Вставка после текущего 
     Вставка элемента после текущего.gif
    • 

  •  Удаление после текущего 
     Удаление после текущего.gif
    • 

  •  Проход по списку 
     Проход по списку.gif


Двусвязные линейные списки


Стандартные операции с двусвязными линейными списками



  •  Инициализация
    • 

  •  Добавление в начало, конец
    • 

  •  Удаление из начала, конца
    • 

  •  Вставка элемента перед текущим, после текущего
    • 

  •  Удаление текущего
    • 

  •  Объединение двух списков


Помещение операций по работе со списком внутрь класса







Источник — «http://it.mmcs.sfedu.ru/_wiki/index.php?title=Основы_программирования_—_второй_семестр_08-09;_Михалкович_С.С.;_II_часть&oldid=1088»