Лекции по информатике - Статическая таблица

Пример реализации

Статическая таблица – это таблица, размер которой задается при её создании. Для данной структуры определим следующий набор допустимых операций:

Создание таблицы заданных размеров
Уничтожение таблицы
Доступ к размерам таблицы (операция наблюдатель)
Доступ к чтению элемента по индексу (операция наблюдатель)
Доступ к элементу для изменения (модификатор).

Данные операции являются необходимым минимумом для работы с таблицей. Теперь рассмотрим способы реализации внутренней структуры разрабатываемого типа. В поле памяти таблица будет занимать некоторую область, в которой будут храниться размеры таблицы, ёе элементы, а также некоторая дополнительная информация.

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

В памяти выделяется фиксированная область в виде двумерного массива, довольно больших размеров, заведомо превышающих размеры таблицы:
В памяти выделяется область статической памяти (одномерный вектор),

в которую последовательно записываются строки таблицы:

Данный способ лучше, но доступ более долгий и трудоемкий.
Этот способ является аналогом способа 2, но использует динамически выделенную память, то есть сначала задаются размеры таблицы, затем рассчитывается длина одномерного куска памяти и выделяется необходимое количество памяти в куче.
Недостаток способа №3 – это ограничение по памяти, то есть когда программа размещается в ОЗУ, ей соответствует некоторая область памяти, в которую записываются сначала все типизированные константы, а затем все глобальные переменные, данная область называется сегментом данных и имеет размер в 64Кб. То есть существует ограничение на размер структуры.

Способ №4 использует метод, позволяющий обойти это ограничение. Суть этого метода заключается в следующем : задается нетипизированный указатель на одномерный массив, элементами которого являются указатели на одномерные массивы, состоящие из элементов строк (столбцов) нашей таблицы.

Замечание: этот способ имеет более быстрый доступ к элементам таблицы и дает возможность создавать таблицы больших размеров.

Следующий модуль демонстрирует использование метода №3.

unit ATable;

{$N+} {подключение числового сопроцессора}

interface { интерфейсная часть }

type
  _Month = (jan,feb,mar,apr,may,jul,jun,avg,sep,oct,nov,dec);
  _Ind1 = _Month;  { тип столбца }
  _Ind2 = integer; { тип строки }
  _Elem = single; { тип элементов таблицы }
  Ptable = pointer; { нетипизированный указатель не таблицу }

procedure Create (var pt: Ptable; low1,high1: _Ind1;
                  low2,high2: _Ind2; x:_Elem);
{ процедура инициализации таблицы,
  low1,high1,low2,hihg2 - начальные и конечные значения индексов,
  pt – указатель на таблицу, х-элемент, которым изначально
  заполняется таблица }

procedure Destroy (var pt: Ptable);

function GetLow1 (pt: Ptable):_Ind1;
function GetLow2 ( pt : Ptable) :_Ind2;
function GetHigh1 ( pt : Ptable) :_Ind1;
function GetHigh2 ( pt : Ptable) :_Ind2;
{ Функции GetLow1,GetLow2,GetHigh1,GetHihg2 принимают в
  качестве параметра указатель на таблицу и возвращают
  начальные и конечные знечения индекса }

function Get ( pt:Ptable; i1 : _Ind1; i2 : _Ind2):_Elem; 
{ возвращает элемент (i1,i2) }
procedure Put ( pt:Ptable; i1 : _Ind1; i2 : _Ind2; 
x: _Elem); { записывает элемент(i1,i2) }

implementation { раздел описаний }

uses Crt;

type
  AT = Array[0..0] of _Elem; { одномерный массив }
  Pat = ^AT; { указатель на одномерный массив }

  Rep = record
    l1,h1: _Ind1;
    l2,h2: _Ind2;
    P: PAT;
    size1, size2: word;
  end;

  Prep = ^Rep; { указатель на запись, в которой находятся
                 все параметры таблицы }

procedure failure(n: byte); { внутренняя процедура 
                              обработки ошибок }
begin
  ClrScr;
  Writeln('Ошибка : ');
  case n of
    1: Writeln('недостаточно памяти для создания таблицы');
    2: Writeln('неверные границы при создании таблицы');
    3: Writeln('неверные индексы при доступе для чтения');
    4: Writeln(' неверные индексы при доступе для записи');
  end;
  Halt(1); { выход в операционную среду }
end;

procedure Create;
var
  v: Prep;
  k: longint;
begin
  if sizeof(Rep)>MaxAvail then
    failure(1); { проверка свободной памяти в куче }
  New(v); { освобождение места под запись Rep }
  if (Low1 > High1) or (low2 > high2) then
    failure(2); { проверка вводимых индексов }
  with v^ do
  begin
    l1:= low1;  { параметры таблицы }
    l2:= low2;  { параметры таблицы }
    h1:= high1; { параметры таблицы }
    h2:= high2; { параметры таблицы }
    size1:= ord(h1)-ord(l1)+1; { расчет длины строки }
    size2:= ord(h2)-ord(l2)+1; { расчет длины столбца }
    k:= longint(size1)*longint(size2)*sizeof(_Elem);
      { расчет памяти необходимой для таблицы }
    if (k>MaxAvail) or (k>65520) then failure(1);
      { проверка на возможность размещения таблицы в
        одном сегменте кучи }
    getmem(p,k); { выделение необходимой памяти для таблицы }
    for k:=1 to size1+size2-1 do
      P^[k]:= x; { заполнение таблицы элементом х }
  end;
  Pt:=v;
end;

procedure Destroy; { процедура уничтожения таблицы }
var
  k: longint;
begin
  with Prep(Pt)^ do
  begin
    k:= longint(size1)*longint(size2)*sizeof(_Elem);
    freemem(p,k); { освобождение памяти от таблицы }
    size1:= 0;
    size2:= 0;
    p:= nil;
    l1:= _Ind1(1);
    h1:= _ind1(0);
    l2:= _Ind2(1);
    h2:= _ind2(0);
  end;
  dispose(Prep(pt)) { освобождение памяти от всей структуры };
  Pt:= nil;
end;

function Get; { процедура просмотра элемента (i1,i2) }
var
  k: word;
begin
  with Prep(Pt)^ do
  begin
    if (i1<l1) or (i1>h1) or (i2<l2) or (i2>h2) then
      failure(3); { проверка индексов }
    k:= (ord(i1)-ord(l1))*size2 + (ord(i2)-ord(l2))*size1;
     { расчет местоположения элемента }
    Get:= P^[k]; { возвращение элемента }
  end;
end;

procedure Put; { процедура записи элемента }
var
  k: word;
begin
  with Prep(Pt)^ do
  begin
    if (i1<l1) or (i1>h1) or (i2<l2) or (i2<h2) then
      failure(4); { проверка индексов }
    k:= (ord(i1)-ord(l1))*size2 + (ord(i2)-ord(l2))*size1;
      { расчет местоположения элемента в массиве }
    P^[k] := x; { запись в массив }
  end;
end;

function GetLow1; { возвращает начальный индекс строки }
begin
  GetLow1:= PRep(Pt)^.l1;
end;

function GetLow2;
begin
  GetLow2:= PRep(Pt)^.l2;
end;

function GetHigh2;
begin
  GetHigh2:= PRep(Pt)^.h2;
end;

function GetHigh1;
begin
  GetHigh1:= PRep(Pt)^.h1;
end;

end.

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

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

Использование объектных средств

Во-первых, не нужно путать объектное программирование и объектно-ориентированное программирование(ООП). Первое является лишь частью такого общего понятия как ООП. ООП базируется на таких понятиях как инкапсуляция, наследование и полиморфизм. В смысл всех этих слов вам вникать пока не нужно, поэтому вы можете сразу их забыть.

В объектном программировании используется лишь понятие объекта. Что он из себя представляет? Подобно обыкновенной записи Record, объект содержит данные различных типов. Но в отличие от записи он может содержать процедуры и функции Паскаля для работы с полями объекта (эти функции и процедуры называют методами работы над объектом). Свойство объектов содержать и поля данных и подпрограммы их обработки называют инкапсуляцией.

Надо учесть, что желательно запрещать доступ к полям данных кроме как через методы этого объекта (иначе это считается плохим тоном). Правда, есть исключения (т.к. это ограничение иногда может существенно сказаться на эффективности программы и замедлить ее), поэтому иногда открывают доступ к полям. Перепишем модуль из прошлого параграфа с использованием объектного программирования:

unit ATable;

interface

{$N+}

type
  _Month = (jan,feb,mar,apr,may,jun,jul,aug,sep,oct,nov,dec);
  _ind1 = _Month;
  _ind2 = integer;
  _elem = single;
  PTab = ^CTab;

  CTab = object
  public
{ общеоступные поля данных и методы объекта, они могут
  свободно вызываться программистом в его программах }

    constructor Init(Low1,High1:_Ind1; Low2,High2:_Ind2; x:_elem);
    destructor Done; virtual;
    function GetLow1:_ind1;
    function GetLow2:_ind2;
    function GetHigh1:_ind1;
    function GetHigh2:_ind2;
    procedure Get(i1:_ind1; i2:_ind2;x:_elem);
    procedure put(i1:_ind1; i2:_ind2;x:_elem);

  private
{ эта директива в описании объекта открывает секцию
  описания скрытых полей и методов объекта.
  Перечисленные в этой секции элементы объекта "не видны"
  программисту вне этого модуля.
  Скрываются те поля и методы к которым
  программист (в его жеинтересах!) не должен иметь
  непосредственного доступа.
  В нашем примере он не может произвольно менять
  значения индексов и указатель на массив, т.к. это может
  привести к печальным последствиям (нарушению работы
  "Таблицы"). Кроме этого пользователь не может сам
  вызвать служебную процедуру Failure }

    procedure failure(n: word);
    l1, h1: _ind1;
    l2, h2: _ind2;
    size1, size2: word;
    p: pointer;
end;

implementation

{$Q+,R-}

uses crt; { подключаем библиотеку crt для пользования процедурой
            очистки экрана }

type
  al = array[0..0] of _elem; { тип-массив для хранения строк массива }
  pal = ^al; { указатель на строку массива }
  apal = array[0..0] of pal; { тип массив для хранения указателей
                               на строки массива }
  papal = ^apal; { указатель на apal, нужен в этой программе
                   исключительно для приведения типов, см.ниже }

procedure CTab.Failure;
{ Обратите внимание, что при описании методов имя метода дополняется
  спереди именем объекта, т.е. используется составное имя метода.
  Кроме этого список аргументов передаваемых подпрограмме можно
  здесь опускать }
begin
  ClrScr; { очистим экран, хотя надо ли это делать - вопрос весьма
            спорный, иногда надо видеть, что было на экране до того
            как программа выдала ошибку }
  writeln('Ошибка # ',n:1); { печатаем номер ошибки }
  case n of { расшифровываем код ошибки }
    1: writeln('Недостаточно памяти для инициализации таблицы');
    2: writeln('Неверные границы');
    3: writeln('Неверные индексы при чтении');
    4: writeln('Неверные индексы при записи');
  end;
  halt(1); { выходим мз программы }

{ можно улучшить эту процедуру, если она будет выводить метод
  объекта в котором возникла ошибка }
end;

constructor CTab.Init;
{ Конструктор - это особый вид процедур. Конструкторы
  предназначены для создания конкретного экземпляра объекта.
  Объет может иметь достаточно много конструкторов, например,
  можно создать конструктор копирования объета. Конкретная задача
  конструктора - заполнение полей объекта данными, подготовка его
  к работе }
var
  k: longint;
  i,j: word;
begin
{ проверим индексы на соответствие }
  if (Low1>High1) or (Low2>High2) then 
    Failure(2);
{ заполняем поля объекта }
  l1:= Low1;
  h1:= High1;
  size1:= ord(h1)-ord(l1)+1;
  l2:= Low2;
  h2:= High2;
  size2:= ord(h2)-ord(l2)+1;
{ делаем стандартные проверки на вмещение массива в сегмент }
  k:= longint(size1)*Sizeof(pal);
  if (k>65520) or (k>MaxAvail) then 
    Failure(1);
  GetMem(p,k); { выделяем память для массива указателей }
  k:= longint(size2)*Sizeof(_elem);
  if k>65520 then
    Failure(1);
{ выделяем память для size1 строк матрицы каждая размером, k-байт }
  for i:=0 to (size1-1) do  
  begin
    if k>MaxAvail then 
      Failure(1);
    GetMem(papal(p)^[i],k);
  end;
{ Заполняем матрицу элементом x }
  for i:=0 to (size1-1) do
    for j:=0 to (size2-1) do
       papal(p)^[i]^[j]:= x;
end;

destructor CTab.Done;
{ Деструктор нужен для уничтожения экземпляра объекта, вся память
  которую взяли в конструкторе, или во время работы должна быть
  возвращена в деструкторе }
var
  k: longint;
  i,j: word;
begin
{ освобождаем память }
  k:= size2*Sizeof(_elem);
  for i:=0 to (size1-1) do
    FreeMem(papal(p)^[i],k);
  k:=Size1*Sizeof(pal);
  FreeMem(p,k);
{ следующие операторы не обязательны и введены для того, чтобы
  объект смог при вызове его методов выдать ошибку }
  p:=nil;
  size1:=0;
  size2:=0;
  l1:=_ind1(1);
  h1:=_ind1(0);
  l2:=_ind2(1);
  h2:=_ind2(0);
end;

function CTab.GetLow1;
{ Функция возвращает нижнюю границу первого индекса }
begin
  GetLow1:= l1;
end;

function CTab.GetLow2;
{ Функция возвращает нижнюю границу второго индекса }
begin
  GetLow2:= l2;
end;

function CTab.GetHigh1;
{ Функция возвращает верхнюю границу первого индекса }
begin
  GetHigh1:= h1;
end;

function CTab.GetHigh2;
{ Функция возвращает верхнюю границу второго индекса }
begin
  GetHigh2:= h2;
end;

procedure CTab.Get;
{ Функция возвращает элемент }
begin
{ Проверяем индексы на принадлежность матрице }
  if (i1<l1) or (i1>h1) or (i2<l2) or (i2<h2) then
    Failure(3);
  x:= papal(p)^[ord(i1)-ord(l1)]^[ord(i2)-ord(l2)];
{ Т.к. p - нетипизированный указатель, то мы сначала приводим
  его к типу papal, а потом обращаемся к получившемуся оператору
  так, как будто это был бы указатель типа papal }
end;

procedure CTab.Put;
{ Функция кладет элемент в матрицу }
begin
{ Проверяем индексы на принадлежность матрице }
  if (i1<l1) or (i1>h1) or (i2<l2) or (i2<h2) then
    Failure(4);
  papal(p)^[ord(i1)-ord(l1)]^[ord(i2)-ord(l2)]:= x;
end;

begin
end.

197-577-902 ICQ-статус