Понятие типа объекта в программе. Концепция типа данных

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

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

Концепция типа данных определяет, что тип данных характеризуется:

- множеством значений (состояний) данных;

- множеством допустимых операций над данными;

- внутренним представлением данных в памяти.

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

Первоначально моделью объекта может служить его название, т.е. некоторое имя. Первоначально тип объекта может указываться в терминах предметной области.

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

Структура данных, которая рассматривается на логическом уровне, т.е. без учёта её представления в памяти (или устройствах) ЭВМ, называется абстрактной (или логической) структурой данных (СД).

ЭВМ может обрабатывать только такую структуру данных, которая каким-либо способом представлена (размещена) в устройстве памяти, т.е. имеет физическое представление. Такая СД, обрабатываемая и представляемая в памяти (и в устройствах) ЭВМ называется внутренней (физической) СД, структурой памяти или структурой хранения.

Представление определенной структуры данных в памяти ЭВМ называется структурой хранения. Различия между структурой данных и соответствующей структурой хранения часто не учитывается, что приводит к снижению эффективности представления данных и затрудняет разработчику использовать свои средства и ресурсы.

К структурам хранения обычно относят следующие:

- вектор (набор ячеек памяти одного размера, которые располагаются в памяти строго последовательно);

- список (линейный однонаправленный) (набор элементов хранения, каждый из которых состоит из двух полей – поле данных+ поле указателя);

- сети (каждый элемент имеет несколько указателей) (структура данных, состящая из элементов хранения, каждый их которых содержит поле данных + два или более полей указателей).

К структурам данных обычно относят следующие:

- последовательность (строка) (хранится в виде вектора);

- массив (хранится в виде вектора);

- запись (хранится в виде нескольких векторов разного размера);

- стек (хранится в статической памяти в виде вектора + указатель стека или хранится в динамической памяти в виде списка);

- очередь (хранится в виде списка и двух указателей – на начало и на хвост);

- таблица (хранится в статической памяти в виде вектора или в динамической памяти в виде списка);

- дерево (отображаются в памяти сетями);

- граф (отображаются в памяти сетями).

Структуры данныхСтруктуры хранения

последовательность вектор

массив список

запись сеть

таблица

стек

очередь

граф

дерево

Замечания:

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

2) Обычно существует много возможных структур хранения для одной структуры данных. Например, структуру данных СТЕК можно хранить:

- как массив в статической памяти;

- как список в динамической памяти.

ОСНОВЫ ПАСКАЛЯ

1. Структура (состав) языка

В состав языка включается обычно три составляющие: алфавит, синтаксис и семантика. Кроме того в составе синтаксиса выделяют еще так называемую лексическую структуру языка.

Алфавит – это фиксированный для данного языка набор основных символов, из которого будут строиться все основные конструкции языка. Алфавит задается перечислением всех допустимых символов.

Синтаксис задаёт (содержит) правила (для человека) образования допустимых (правильных) для данного языка конструкций и правила образования программы из этих конструкций. Синтаксис описывается с использованием специальных искусственных языков – аналитических (БНФ) и графических (синтаксические диаграммы). Например, определение «арабские цифры» имеет вид:

или Арабские цифры::= 0 | 1 | 2 | 3 | 4 | … | 9

Описание синтаксиса на графическом языке Описание синтаксиса на аналитическом языке

Семантика – правила (для компилятора) толкования конструкций языка (с точки зрения возможности вычисления результата).

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

Var

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

i: integer;

r: real;

begin

r:= 1.25;

i:= r;

end.

Задаётся семантика, в отличии от синтаксиса, не формально (т.е. не на искусственном языке), а посредством неформальных описаний на естественном языке.