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

⇐ ПредыдущаяСтр 6 из 6

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

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

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

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

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

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

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

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

Данные могут быть:

- скалярными (не делятся на части);

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

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

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

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

б) разработаны подпрограммы для выполнения действий над элементами этих структур.

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

Замечание 1. В программировании есть понятие абстрактных типов данных (АТД) - в них абстрагируются от внутреннего представления данных. Таким абстрактным типом м.б., например, очередь. Ее можно задать так:

1) тип элемента (д.б. определен не уровне очереди);

2) операция добавления нового элемента в хвост очереди;

3) операция извлечения элемента (самого первого) из головы очереди;

4) номера (указатели) первого и последнего элементов очереди.

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

- типа элемента (надо будет при вызове указывать);

- внутреннего представления очереди (массив или список).

Для реализации АТД подходят Модули из Турбо-Паскаля (Free Pascal):

- реальный тип элемента м.б. описан в отдельном модуле (надо будет его подключать);

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

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

Замечание 2. АТД ≠ ООП (класс, объект). Дело в том, что концепция АТД не предусматривает наследования (предусматривается только сокрытие реализации и внутреннего представления). Только ООП позволяет построить иерархию родственных (похожих, но разных) типов (классов) с использованием наследования и полиморфизма (виртуальных методов). Соответственно в рамках ООП в качестве АТД могут рассматриваться:

- шаблоны (template) - есть целые библиотеки таких шаблонов (STL);

- интерфейсы (один класс может иметь несколько разных интерфейсов).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

запись сеть

таблица

список, стек одно поле связи

очередь

граф

дерево

нелинейные три поля

структуры данных связи

Замечания:

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

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

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

- как линейный список в динамической памяти (с указателем на голову).

⇐ Предыдущая 1 2 3 4 56