Структуры данных и эффективность алгоритмов. 4
 Скачать 2.32 Mb.
|
Типы данных и структуры данных.Тип данных определяется парой:
Семейство типов данных обычно задается парой:
В (процедурных) языках программирования в состав базовых типов данных обычно входят: числовые (целые и вещественные), символьный и логический типы данных, а также указательный тип данных, который имеет особый статус в наборе базовых. Базовые типы – предопределенные. В частности для них предопределены основные операции, в число которых обычно входят:
В состав операций конструирования новых типов данных входят конструкторы типов (описатели типов) обычно следующих видов: массивов, записей (структур), а также (последовательных) файлов, у которых в различных (процедурных) языках программирования может быть специфически различный статус. Конструкторы типов занимают фундаментальное положение в языках программирования, они являются базовой основой для создания (конструирования) сложных структур данных13. Структурные (составные) типы данных – это типы данных, определенные с помощью набора операций конструирования, значениями которых являются наборы данных, связанных в соответствии со способом конструирования (группировки). Значения структурных типов состоят из компонентов (ранее определенных типов), поэтому для таких типов данных особый статус имеют предопределенные операции:
Как ранее уже отмечалось, структура данных - это набор данных, связанных специальным образом. С определенной точки зрения «структуры данных» можно трактовать как значения структурных типов, хотя с близкой несколько иной точки зрения, возможно правильнее, трактовать как хранилища данных (переменные) структурного типа. Хотя понятие «структура данных» (прежде всего) означает определенный способ организации взаимосвязей между компонентами (и способ представления этих взаимосвязей), но по существу подразумевает и набор операций для работы с ее компонентами. Новый этап в развитии понятия «тип данных» связан со становлением и утверждением в методологии и практике программирования понятий «абстрактный тип данных» и «объекты и классы». И в теории и в методологии программирования ещё много злободневных вопросов по этим понятиям, но в практике разработки программного обеспечения и собственно программирования эти понятия уже занимают значимое положение.
Абстрактным принято называть тип данных, в явном виде не имеющийся в языке программирования, в этом смысле это понятие относительное - тип данных, отсутствующий в одном языке программирования, может присутствовать в другом. Абстрактный тип данных (АТД) определяется независимо от способа его реализации:
Использование АТД может быть ограничено этапом разработки программного обеспечения, но для его явного использования в программе надо иметь его реализацию на основе уже имеющихся (и ранее реализованных) типов данных в языке программирования:
АТД не является предопределенным в языке программирования, и даже более того – операции конструирования таких типов, предопределенные в языке, перекладывают на разработчика-программиста вопрос о способе представления значений такого типа и реализации операций со значениями этого типа. А потому, для таких типов данных вопрос о выборе определений и способов реализации операций вида конструктор (значений и хранилищ данных) такого типа, селектор и модификатор компонентов (значений и хранилищ данных) такого типа возлагается на разработчика-программиста. В концепции АТД особый статус имеют понятия интерфейс, открытый пользователю, и реализация, скрытая от него. Особая роль этих понятий в концепции АТД связана с основополагающим положением о независимости понятия АТД от способа его реализации. В современных «практических языках программирования» для конструирования АТД обычно используется предопределенная операция конструирования типов class, которая дает разработчику-программисту не только средства группировки данных и операций (с этими данными) в единое целое, но и средства инкапсуляции, наследования и полиморфизма для управления способами конструирования и доступа к таким данным. Отметим, что класс описывает одну возможную реализацию АТД, отображение класса в АТД выражается функцией абстракции, но обратное отношение, обычно, не является функциональным, реализаций одного и того же АТД может быть несколько. В исследованиях по абстрактным типам данных уже на раннем этапе была осознана важная роль понятия «параметризация типа». Действительно, например АТД «Стек» не зависит от типа элементов стека, но реализовать этот АТД указанием на «элементы какого-то одинакового типа» невозможно. В язык программирования Ada соответствующие средства конструирования параметризованных типов данных были включены изначально, а в современных «практических языках программирования» какие средства появились только со времен появления разработки по STL-библиотеке [9]. На сегодня понятие «обобщенное программирование» занимает значимое положение в практическом программировании благодаря включению в «практические языки программирования» средств конструирования параметризованных типов данных (шаблоны, template, generic). Всё вышесказанное означает, что с методологической и теоретической точки зрения необходимо более детальное точное определение понятия «абстрактный тип данных». В теории понятие «абстрактный тип данных» обычно определяется как многосортная (многоосновная) алгебраическая система, в которой дополнительно к множеству возможных значений (носителю) и набору операций над такими значениями выделены понятия:
На такой основе можно рассматривать абстрактные типы данных с единой целостной логико-алгебраической точки зрения, включая вопросы о конструкторах (типов и значений), селекторах и модификаторах свойств для объектов такого типа [10; 11; 12]. Понятия «структура данных» и «абстрактный тип данных» в чем-то очень близкие. Можно конечно считать, что эти понятия - просто два взгляда на одно и то же. Способ представления значений АТД всегда основан на некоторой структуре данных, менее или более сложной, и реализация операций с такими значениями естественно зависит от этой выбранной структуры данных. С другой стороны, заинтересовавшую нас структуру данных при большом желании мы всегда можем оформить как АТД. Но все же мы будем различать эти два понятия, учитывая:
К абстрактным типам данных прежде всего естественно относятся математические базовые алгебраические системы – последовательности, множества, отношения и отображения (функциональные отношения, функции) [11; 12]. Но в программировании на переднем плане не исследование общих свойств этих математических понятий, а возможности их использования в разработке моделей решения задач предметной области, алгоритмов решения этих задач и эффективной реализации разработанных алгоритмов. А потому в программировании в виде АТД обычно оформляются с одной стороны ограниченные варианты этих базовых алгебраических систем, а с другой стороны расширенные специализированными наборами операций, представляющими прагматический интерес с точки зрения области применения. |