Абстрактные типы данных Май 20101

Основные вопросы Определение типа и поколения языков программирования Понятия абстракции и абстрактного типа данных Понятие инкапсуляции и ее преимущества Спецификация и реализация абстрактного типа данных Реализация абстрактных типов в С++ Май 20102

Определение типа Тип данных - множество с операциями (алгебра), учитывающая следующее: – если дан новый тип, то можно описывать и инициализировать переменные этого типа; – если дана переменная некоторого типа, то можно определить и изменить ее текущее значение; – если даны два значения определенного типа, то можно сравнить их, по крайней мере на равенство или неравенство; – описание типа дает некоторую интерпретацию определяемым синтаксисом языка символам, которые вводятся для обозначения констант. Если два типа отличаются по любым из перечисленных факторов, то такие типы считаются разными Май 20103

Поколения языков Первое поколение - языки с минимальными возможностями типизации – Предоставляют лишь средства для описания переменных простых типов и массивов; никаких новых типов вводить нельзя. – Фортран, Алгол-60. Второе поколение – языки, предоставляющие программисту основные конструкторы типов: массивы, записи, объединения – ПЛ/1, Алгол-68, Паскаль, С – Тип рассматривается как множество значений, получаемых из базисных множеств с помощью конструкторов. – Все операции над типами данных предопределенные определяемые языком, а не программистом. – Новые типы могут получать имена, но с ними нельзя связывать новых, специально вводимых операций. Третье поколение – языки, предоставляющие программисту средства определения абстрактных типов данных – С++, C#, Java – Типы понимаются как множества с операциями. Май 20104

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

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

Определение абстрактного типа данных Абстрактный тип данных это способ определения некоторого понятия в виде класса объектов с некоторыми свойствами и операциями. Понятие абстрактного типа данных это, по существу, аналог определения в математике, где новые понятия образуются из некоторых исходных объединением их в одно целое, имеющее новый статус, новое имя. Так как свойства обычно выражаются в терминах операций, то абстрактный тип данных часто отождествляют с соответствующим множеством операций. Например: – определение понятия стека в терминах операций "втолкнуть элемент в стек", " создать новый стек", "выдать верхний элемент" и т.д. В языке программирования такое определение оформляется как специальная синтаксическая конструкция, называемая в разных языках капсулой, модулем, кластером, классом, пакетом, формой и т.д. Май 20107

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

Спецификация и реализация Объявление абстрактного типа данных состоит из двух частей – Спецификация – предназначается для сопряжения абстрактного типа данных с внешней средой. Содержит описание операций, которые могут быть выполнены над типом. – Реализация – раскрывает семантику операций, инкапсулируя ее от внешней среды. Май 20109

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

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

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

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

Преимущества инкапсуляции (5) Упрощение процесса отладки. – Ограниченный доступ к капсуле исключает влияние ошибок во внешней среде на его функционирование. Поэтому программу можно строить последовательно, по очереди подключая каждую капсулу. После присоединения капсулы можно считать, что все появившиеся новые ошибки содержатся в этой капсуле, а не в уже отлаженных. Другими словами, границы капсулы препятствуют распространению ошибок по всей программе. Май

Преимущества инкапсуляции (6) Упрощение модификации программы. – Более вероятно, что те места программы, в которых потребуется произвести изменения, окажутся расположенными близко друг от друга. Май

Критерии, которым должны удовлетворять спецификации Точность Понятность Конструктивность Мощность Минимальность Модифицируемость Май

Реализация абстрактного типа данных Включает в себя конкретное описание объектов определяемого типа и реализацию операций этого типа. Объекты описываются в терминах простых или составных типов или ранее определенных абстрактных типов. Реализация операций состоит в описании подпрограмм, выполняющих необходимые действия с указанными объектами. Май

Абстрактные типы данных в С++ (1) Абстрактные типы данных в С++ создаются с помощи синтаксической конструкции называемой «классом». Предназначение понятия класса состоит в том, чтобы предоставить программисту инструмент для создания новых типов, столь же удобных в обращении сколь и встроенные типы. В идеале тип, определяемый пользователем, способом использования не должен отличаться от встроенных типов, только способом создания. Как правило, программу, в которой создаются типы, хорошо отвечающие понятиям приложения, понять легче, чем программу, в которой это не делается. Хорошо выбранные типы, определяемые пользователем, делают программу более четкой и короткой. Использование классов позволяет компилятору обнаруживать недопустимые использования объектов, которые в противном случае останутся необнаруженными до тестирования программы. Май

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

Состав класса Внутренние переменные класса называются атрибутами. Доступ к объектам класса может ограничиваться набором функций, которые описаны как часть этого класса. Такие функции называются методами. Объекты класса создаются и инициализируются методами, специально для этой цели описанными. Эти методы называются конструкторами. Метод может быть специальным образом описан для "очистки" каждого классового объекта при его уничтожении. Такой метод называется деструктором. Май

Пример использования структуры для реализации понятия даты struct date { int month; int day; int year; }; date today; void set_date(date*, int, int, int); void next_date(date*); void print_date(date*); //... Май

Спецификация класса в С++ class имя_класса{ модификатор_доступа: [атрибуты] [методы] модификатор_доступа: [атрибуты] [методы] … }; Май

Пример использования класса для реализации понятия даты class date{ private: int month, day, year; public: void set(int, int, int); void get(int*, int*, int*); void next(); void print(); }; Май

Модификаторы доступа private public protected Май

Работа с классом date d1; data *d2 = new date; d1.set(5,5,2005); d2->set(6,6,2006); d1.next(); d2->print(); d1. year = 2007;// ошибка delete d2; Май

Реализация класса void date::print() { printf(%i.%i.%i, this->day, this->month,year); } Май

Разделение спецификации и реализации date.h class date{ private: int month, day, year; public: void set(int, int, int); void get(int*, int*, int*); void next(); void print(); }; date.cpp #include date.h void date::print() { printf(%i.%i.%i,day, month,year); } … Май

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

Создание и использование конструктора class date{ private: int month, day, year; public: date(int day, int month, int year); date(char *str); // дата в строковом представлении date(int day); // месяц и год сегодняшние … }; … date d1; // ошибка date d2(5,5,2005), d4( ); date *d3 = new date(6,6,2006); Май

Деструктор Определяемый пользователем тип чаще имеет, чем не имеет, конструктор, который обеспечивает надлежащую инициализацию. Для многих типов также требуется обратное действие, деструктор, чтобы обеспечить соответствующую очистку объектов этого типа. Имя деструктора для класса X есть ~X() ("дополнение конструктора"). В частности, многие типы используют некоторый объем памяти из динамической памяти, который выделяется конструктором и освобождается деструктором. Деструктор вызывается когда переменная выходит из области видимости (для класса памяти auto) или при использовании оператора delete. Май

Пример деструктора class char_stack{ private: int size; char* top; char* s; public: char_stack(int sz) { top=s=new char[size=sz]; } ~char_stack(){ delete[] s; } // деструктор void push(char c) { *top++ = c; } char pop() { return *--top;} }; Май

Inline При программировании с использованием классов очень часто используется много маленьких функций. Это может страшно понизить эффективность, потому что стоимость вызова функции (хотя и вовсе не высокая по сравнению с другими языками) все равно намного выше, чем пара ссылок по памяти, необходимая для тела функции. Чтобы справиться с этой проблемой, был разработан аппарат inline- функций. Метод, определенный (а не просто описанная) в описании класса, считается inline. Это значит, что при компиляции программы вызов функции будет заменен на подстановку ее тела в место вызова. Май

Ссылки на себя Указатель на объект, для которого вызван метод, является скрытым параметром метода. На этот неявный параметр можно ссылаться явно как на this. При ссылке на атрибуты использование this излишне. Главным образом this используется при написании методов, которые манипулируют непосредственно указателями. Май