Шпаргалка по "Программированию и компьютерам"

1. Применение  шаблонов для повторного использования алгоритмов

 Многие алгоритмы  не зависят от типов данных, с  которыми они работают (классический пример — сортировка). Естественно возникает желание параметризовать алгоритм таким образом, чтобы его можно было использовать для различных типов данных. В C++ есть мощное средство параметризации — шаблоны. Существуют шаблоны функций и шаблоны классов. С помощью шаблона функции можно определить алгоритм, который будет применяться к данным различных типов, а конкретный тип данных передается функции в виде параметра на этапе компиляции. Компилятор автоматически генерирует правильный код, соответствующий переданному типу. Таким образом, создается функция, которая автоматически перегружает сама себя.

 Формат  простейшей функции-шаблона:

 template <class Type> заголовок

 { /* тело функции */}

 Вместо  слова Туре может использоваться произвольное имя.

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

 template<class A, class В, int i> void f(){ ... }

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

 template <class Type>

 void sort(Type *b, int n){

 Type а; //буферная переменная для обмена элементов

 for (int i = 0; i<n-l; i++)

   for (int j = i + 1; j<n; j++) if (b[j] < b[i]) 

     {а = b[i]; b[i] = b[j]; b[j] = a;}

 }

 Главная функция программы, вызывающей эту  функцию-шаблон, может иметь вид:

 #include <iostream.h>

  template <class Type> void sort(Type *b, int n);

 int main(){

 const int n = 20;

 int i,  b[n];

 for (i = 0;  i<n; i++) cin >> b[i];

 sort<int>(b, n); // Сортировка массива целочисленных чисел

 for (i  = 0;  i<n;  i++) cout << b[i] <<  '   ';

 cout << endl ;

 double a[] = {0.22,  117,  -0.08,  0.21, 42.5};

 sort<double>(a, 5); // Сортировка массива вещественных чисел

 for (i  = 0;  i<n;  i++) cout << a[i] <<  '   ';

 return 0; }

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

 Пример  явного задания аргументов шаблона  при вызове:

 template<class X, class Y, class Z> void f(Y, Z);

 void g(){

 f<int, char*, double>("Vasia", 3.0);

 f<int, char*>("Vasia", 3.0); // Z определяется как double

 f<int>("Vasia", 3.0); // Y определяется как char*, a Z - как double

 f (”Vasia", 3.0);  // ошибка: Х определить невозможно

 }

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

 Как и обычные функции, шаблоны функций  могут быть перегружены как с помощью шаблонов, так и обычными функциями.

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

 void sort<char>(char *b, int n){

 ...    // Тело специализированного варианта  функции

 }

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

 2. Принципы ООП. 

 Примеры реализации данных принципов  в языках программирования.

 Основные  принципы: инкапсуляция (поддержка  АТД), наследование, полиморфизм.

 1. Инкапсуляция и  поддержка АТД.

 Инкапсуляция  – объединение данных с функциями  их обработки в сочетании со скрытием ненужной для использования информации. Инкапсуляция повышает степень абстракции. АТД (абстрактный тип данных) определяет некоторый набор свойств в виде пассивных полей данных и методов обработки этих данных. Экземпляр АТД – объект. Любой АТД должен обеспечивать следующие возможности

1. Определять тип, позволяющий другим модулям определять переменные этого типа, создавая реальное представление этого типа в памяти.
2. Иметь операции для манипулирования с объектами этого типа.

 Инкапсуляция  позволяет изменить реализацию АТД  без модификации основной части программы (клиентов типа) и наоборот. Часто программы-клиенты не могут непосредственно изменять данные-члены типа, что повышает надежность ПО.

   В современных языках программирования появились специальные средства для создания АТД. В С++ этими средствами являются классы и структуры. Данные класса называются полями, а функции класса – методами. Поля и методы называются элементами класса. Описание класса в первом приближении выглядит так:

 class <имя> {

    [private:]

        <описание скрытых элементов>

    [public:]

        <описание доступных элементов>

 };

 Элементы, описанные после служебного слова  private, видимы только внутри класса (по умолчанию). После спецификатора public описывается интерфейс класса.

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

 Возможность обращения к элементам классов  регулируется с помощью ключей доступа  private, protected и public:

 class <имя> : [private | protected | public] <имя_базового_класса>

 { тело класса };

 Кроме того, управления доступом введен дополнительный спецификатор protected, который предоставляет доступ производным классам к элементам, но запрещает доступ другим клиентам типа. Правила использования ключей и спецификаторов доступа приведены в таблице:

 3. Полиморфизм – возможность использовать в различных классах иерархии одно имя для обозначения сходных по смыслу действий (замещать методами потомка методов родителя с теми же именами и параметрами). Цель – обеспечить более легкое расширение программных систем при их разработке и поддержке.

 В языке  С++ реализация полиморфизма непосредственно  связана с использованием механизма  позднего связывания.

 Рассмотрим  пример:

 class CShape {public: void Draw( ); …};

 class CCircle : public CShape {public: void Draw( ); …};

 …

 main(){

    CShape* s;

    s = new Ccircle;

    s->Draw( );

 }

 В данном примере будет вызван метод Draw класса CShape, т.к. функция Draw является статически связанной. Этот процесс называется ранним связыванием (связывание происходит на этапе компиляции). Механизм позднего связывания обеспечивает связывание с методом на этапе выполнения по адресу объекта. Этот механизм реализован с помощью виртуальных методов. Для определения виртуального метода используется спецификатор virtual в базовом классе:

 class CShape {public: virtual void Draw( ); …}; 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 3. Реализация полиморфизма

 в объектно-ориентированных  языках программирования. Примеры.

 Полиморфизм – возможность использовать в различных классах иерархии одно имя для обозначения сходных по смыслу действий (замещать методами потомка методов родителя с теми же именами и параметрами). Цель – обеспечить более легкое расширение программных систем при их разработке и поддержке.

 В языке  С++ реализация полиморфизма непосредственно связана с использованием механизма позднего связывания.

 Рассмотрим  пример:

 class CShape {public: void Draw( ); …};

 class CCircle : public CShape {public: void Draw( ); …};

 …

 main(){

    CShape* s;

    s = new Ccircle;

    s->Draw( );

 }

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

1. Компилятор устанавливает тип объекта, вызвавшего метод.
2. Ищет метод в пределах типа объекта. Если метод найден, то происходит вызов метода, иначе 3.
3. Компилятор начинает двигаться вверх по иерархии классов.

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

 class CShape {public: virtual void Draw( ); …};

 Если  в классе вводится описание виртуального метода, то он должен быть определен  хотя бы как чисто виртуальный. Чисто  виртуальный метод содержит признак = 0 вместо тела, например: