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

 virtual void Draw( ) = 0;

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

 Виртуальный механизм работает только при использовании  указателей или ссылок на объекты.

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

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

 4. Реализация наследования

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

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

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

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

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

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

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

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

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

 Рассмотрим  правила наследования различных  методов.

 Конструкторы, деструкторы и операции присваивания не наследуются.

 Порядок вызова конструкторов определяется следующими правилами

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

 Правила наследования деструкторов

1. Если деструктор не описан в подклассе, то он формируется по умолчанию и вызывает деструкторы всех базовых классов.
2. Деструкторы вызываются в следующем порядке: деструктор класса, деструкторы элементов класса, деструктор базового класса.

 Простым называется наследование, при котором  производный класс имеет одного родителя. Множественное наследование означает, что класс имеет несколько  базовых классов. Если в базовых  классах есть одноименные элементы, то однозначно на них ссылаться можно только через разрешение области видимости. Например:

 class A {… public: int GetVal();};

 class B {… public: int GetVal();};

 class C : public A, public B {…};

 main{

    C c;

    int v = c.A::GetVal();

    int w = c.B::GetVal();

    …} 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 5. Реализация абстрактных  структур данных  в программировании: список, стек, дерево.

 Пример  реализации списка.

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

 template <class Data> class CList

 {

   class Node {

      public:

         Data d;

         Node *next, *prev;

         Node() { next = NULL; prev = NULL;}

   } *head, *tail;

   public:

     CList(){head = NULL; tail = NULL;}

     ~CList();

     void push_front(Data d);

     void push_back(Data d);

     Node* find(Data d);

     Node* insert(Data key, Data d);

     bool remove(Data key);

     void print();

 };

Также на основе односвязного списка можно  сформировать структуру Стека. Отличаться она будет тем, что удаление (pop) и вставка (push) идет только с одного конца списка (вершины, а противоположный конец - основание) (структура типа LIFO).  Для него определены операции: показать элемент вершины, пуст ли стек, кол-во элементов.

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

 template <class Type>

   class Stack

  { private:

    Type* stk_ptr;

    int max_len;

    int top;

  public:

   Stack (int size);  //конструктор

   Stack ();             // конструктор по умолчанию 

   Stack (const Stack<Type> &L);    //конструктор  копирования

   ~Stack();                // деструктор

   void push(Type element);// основные операции

   void pop ();

   Type stacktop();

   int showtop(){return top;};

   bool empty();

 //перегрузка  операции слож-я двух стеков (+)        

   Stack<Type>& operator + (Stack<Type> &L);

   bool operator > (Stack<Type> &L);                    // перегрузка операции >

   Type* info(){return stk_ptr;};

   };

 Деревья – иерархическая структура хранения данных чаще применяемая для организации  быстрого и эффективного поиска. Каждый элемент – вершина. Самая верхняя вершина – корень. Вершины не имеют подвершин – листья. Вершина порождает вершины стоящие ниже по иерархии – потомки (сама родительская). Вершины с общей родительской вершиной – братья. Глубина – кол-во узлов на самом длинном пути от корневой вершины до листовой. Степень узла – максимальное число вершин которое может породить узел.  Бинарное дерево – мах две вершины. Есть сбалансированные деревья (имеют поддеревья с один глубиной), несбалансированные, полные (не имеет длинных тонких ветвей), упорядоченные (поддеревья каждого узла образуют упорядоченное множество). Чаще всего используют бинарное дерево, а все остальные приводятся к нему по принципу: левый ребенок – правый сосед.