Настоящий динамический массив на Turbo Pascal

Доброго времени суток!

Если вы студент и вам надо срочно скатать — листайте вниз к программе

Данная тема не имеет ничего общего с реальностью, ведь язык Pascal никем не воспринимается всерьез, тем более Turbo Pascal. Однако он еще используется в обучающих целях в ВУЗах. И сегодня после написания лабораторки я обнаружил, что про динамический массив в интернете информации очень мало — не нашел ничего. (а надо было очень сильно)

Что необходимо знать

Тип – указатель

var Ptr : Pointer;

Тип Pointer предназначен для адреса ячейки памяти. Часто указатели используются для работы с динамической областью памяти, называемой кучей. Про устройство памяти в MS DOS(В которой работает Turbo Pascal ) можно почитать отдельно.

Для работы с динамической памятью в TP используются следующие процедуры (из тех, что нам нужны).

New,Dispose,GetMem,FreeMem.

Рассмотрим программу

Var
  IntPtr: ^integer;
Begin
  New(IntPtr);
  IntPtr^ := 10;
  writeln(IntPtr^*2);
  Dispose(IntPtr);
End.

В var мы создаем ссылку на переменную типа integer. Мы пока не выделили память под переменную типа integer, а выделили под адрес. Переходим к основной программе. Теперь выделяем память именно под переменную. Чтобы обратиться к значению переменной, надо использовать операцию разыменования (^). Чтобы проиллюстрировать работу, присвоим ей некоторое значение, а затем напечатаем ее значение, умноженное на два. После работы необходимо освободить память(она сама освободиться после завершения программы, но продемонстрировать работу все же надо).

Процедуры GetMem и FreeMem позволяют выделить память начиная с указанной ячейки, размером N байт, аналогично FreeMem освобождает N байт начиная с указанного адреса

GetMem( Ptr:Pointer, N:integer);
FreeMem( Ptr:Pointer, N:integer);

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

создадим массив из N (1-10 тысяч элементов в надежде, что элементов будет меньше), состоящий из указателей, затем нужному количеству адресов выделяется память под переменные (при помощи New() ).

У многих тут возникает вопрос: «А че? Всеж нормально, динамический» — нет. Вы сразу выделяете память под 10 000 адресов* (к слову у вас вряд ли то выйдет без дополнительных ухищрений), а это и так занимает много места, спрашивается – зачем?

А теперь все же покажу реализацию

program TrueDynamicArray;
type
    ElemType = integer;         //Наши элементы массива будут типа integer
    TElemType = ^Elemtype;      //Создаем тип ссылки на integer

    //Вспомогательная функция, реализующая последовательный доступ к памяти
    //Идем по одному до элемента с номером i и возвращаем его
    function getI( pa:TElemType;i:word):integer;
    var
       j:word;
    begin
        for j:=1 to i-1 do
            inc(pa);
        getI:=pa^; //Не забываем про разыменование
    end;

    //Вспомогательная функция, реализующая последовательный доступ к памяти
    //Идем по одному до элемента с номером i и устанавливаем его значение равным val
    procedure setI( pa:TElemType; i:word; val:ElemType);
    var
       j:word;
    begin
        for j:=1 to i-1 do
            inc(pa);
        pa^:=val;   //Не забываем про разыменование
    end;

var
   i,n:word; //i - счетчик; n - кол-во элементов массива
   arrayPtr: TElemType; //Указатель на первый элемент массива
begin
    readln(n); // Считываем n с консоли

    //Выделяем память под наши нужды начиная с ячейки arrayPtr 8*n байт
    getmem( arrayPtr, sizeof(ElemType)*n);

    for i:=1 to n do
      setI(arrayPtr, i, random(10));

    for i:=1 to n do
      write(getI(arrayPtr, i ):3);

    // Очищаем память начиная с ячейки arrayPtr 8*n байт
    freemem(arrayPtr,sizeof(elemType)*n);
end.

Давайте попробую объяснить, что тут происходит

Для начала определим наши типы, надеюсь тут все понятно. Напишем две функции. В них при помощи некоторой магии реализуем последовательный доступ к памяти. А конкретнее: параметр pa это указатель на тип ElemType. В данном случае это integer – 2 байта. То есть, если мы возьмем следующий за ним указатель, то он будет через 2 байта. Следующий указатель мы можем получить при помощи процедуры inc(). Это та самая маленькая магия, про которую многие не слышали, и я не нашел упоминания об этой возможности языка. Это тот самый последовательный доступ. А теперь дело за малым, мы перематываем i-1 раз и получаем адрес, по которому мы можем получить i-тый элемент массива. Для функции setI устанавливаем значение, а для getI возвращаем значение. Не забываем про операцию разыменование.

С описанием типов и процедур закончили и переходим к var, тут берем две переменные (подписаны в программе) word и один единственный указатель. Как видим у нас нет почти ограничений на размер массива – максимальное значение переменной N и максимальный размер кучи (64 Кбайт).

Основная программа

Введем какое-то N – длину массива, и выделяем под него память при помощи процедуры GetMem. Математика простая, нам нужно n элементов по m байт(m это размер переменной типа ElemType). Далее простой пример работы с данными, используя вышеописанных функций. И в конце очищаем память, руководствуясь той же логикой, что и при выделении памяти.

*если попробовать выполнить writeln(sizeof(Pointer));, то на экране вы увидите число 8, не готов утверждать, что указатель занимает 8 байт в памяти, но судя по всему это так.