Класс как тип данных. Поля и методы класса. Создание класса на основе структурного и объединяющего типов данных.

Временная сложность алгоритмов. Примеры алгоритмов с различной временной сложностью.

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

Примеры:

ñ Алгоритм быстрой сортировки имеет минимальную сложность порядка О(N*log2N) и максимальную сложность порядка О(N2)

void QuickSort (int a[], int L, int R)

{

int i =L; int j = R;

int x = a[(L + R)>>1];

do {

while (a[i]<x) i++;

while (a[j]>x) j--;

       if(i<=j) {

x = a[i];

a[i] = a[j];

j

] = x;

i++; j--;

}

}

 while (i<=j);

if (i<R) QuickSort(a,i,R);

 if (j>L) QuickSort(a,L,j);

}

ñ Анализ сортировки Шелла показывает, что порядок ее алгоритма O(N1.3). Это значительное улучшение по сравнению с «родительской» сортировкой простыми включениями, имеющей порядок O(N2).

       void ShellSort (int a[], int n)

        // Усовершенствованный метод включения

{

int x, k;

for (int h = n>>1; h>=1; h = 3*h/5) {

        k = h;

        for (int i = k; i<n; i++) {

                   x = a[i];

       int j = i-k;

while(j>=0 && a[j]>x) {

        a[j+k] = a[j];

j-=k;

        }

a[j+k] = x;

}

}

}

void InsertionSort (int a[], int n)

        // Простой метод включения

{

int x;

for (int i = 1; i<n; i++) {

x = a[i];

        int j = i-1;

while(j>=0 && a[j]>x) {

                    a[j+1] = a[j];

                    j--;

                    }

        a[j+1] = x;

}

}

Процедурное и объектно-ориентированное программирование. Основные концепции объектно-ориентированного программирования.

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

1. процедурно-ориентированное программирование,

2.  объектно-ориентированное программирование

Процедурно-ориентированное программирование:

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

Пример:

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

Объектно-ориентированное программирование:

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

Пример:

Картотека сотрудников компании создается в виде переменной класса, содержащего массив структур с записями о сотрудниках и процедуры его обработки. Эти процедуры не могут быть использованы для обработки каких-либо других массивов. Переменная класса называется также экземпляром класса или объектом.

Класс как тип данных. Поля и методы класса. Создание класса на основе структурного и объединяющего типов данных.

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

class employee

{

public:

char name[64];

long employee_id;

float salary;

void show_employee(void);

};

Функции, принадлежащие классу, принято называть методами класса. Данные, входящие в состав класса, называются полями класса.

Класс может быть определен с использованием служебного слова class.В этом случае все элементы класса по умолчанию являются закрытыми и для выделения открытых методов нужно использовать служебное слово public.Открытые методы класса обеспечивают внешний интерфейс его объектов, делая возможным их использование в программах.

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

4. Классы. Принцип инкапсуляции. Статус видимости элементов класса, управление видимостью.

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

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

ñ Статус видимости «открытый» означает, что элемент класса доступен для внешних обращений. По умолчанию все элементы класса, созданного на основе структуры, являются открытыми

ñ Статус видимости «закрытый» означает, что элемент класса доступен только для обращений из методов этого класса и недоступен для внешних обращений

ñ Статус видимости «защищенный» означает, что элемент класса доступен только для обращений из методов этого класса и методов классов-потомков

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

Например, пусть программист решил в классе TPoint запретить внешний доступ к координатам точки и разрешить внещний доступ к методам перемещения точки на плоскости, тогда можно построить описание класса как:

class TPoint

{

    private:

    int x,y;

    public:

    void movePoint(int newx, int newy); // Перенос точки

    void relmove (int dx, int dy); // Сдвиг точки

    int getx() {return x;};

    int gety() {return y;};

};

5. Конструкторы и деструкторы, создание объектов и инициализация полей.

При создании объектов класса выполняется инициализация их полей. Для этой цели в определение класса включают специальный метод, называемый конструктором.Такой метод имеет следующие отличия от остальных методов класса:

1.он должен иметь имя, совпадающее с именем класса

2.для него не задается тип возвращаемого значения

3.вызов конструктора осуществляется автоматически при создании объекта

Например, пусть программист решил в классе TPoint запретить внешний доступ к координатам точки и разрешить внещний доступ к методам перемещения точки на плоскости, тогда можно построить описание класса как:

class TPoint

{

    private:

    int x,y;

    public:

    void movePoint(int newx, int newy); // Перенос точки

    void relmove (int dx, int dy); // Сдвиг точки

    int getx() {return x;};

       int gety() {return y;};

    TPoint(int x0, int y0):x(x0), y(y0){};//Конструктор

};

В этом конструкторе все компоненты получают значения из списка инициализации, а тело конструктора представлено пустым состаным оператором.

Конструктор может быть включен программистом в определение класса.Такой конструктор может иметь формальные параметры, которые используются в качестве инициализирующих значений для полей класса . Класс может иметь несколько конструкторов с разными параметрами для разных видов инициализации, т.е. конструктор может быть перегружен. Конструктор существует для любого класса; если он не задан программистом, то он создается по умолчанию. Созданный по умолчанию конструктор не имеет параметров и присваивает полям объекта значения по умолчанию. Конструктор неявно вызывается всякий раз при определении объекта класса или создании его посредством операции new.

Вызов конструктора класса:

Например:

Employee c1;

Employee *c2 = new Employee;

В этих случаях вызывается конструктор по умолчанию.

Другой пример:

Employee c1(“”, 20,1000);

Employee *c2 = new Employee (“”, 20,1000);

В этих случаях вызывается конструктор, заданный программистом с указанием значений для инициализации полей .

Деструктор класса – это специальный метод, используемый для «деинициализации» объекта. Имя деструктора имеет вид:

~ имя_класса

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

1. когда объект выходит из области видимости;

2. когда объект, созданный операцией new, удаляется операцией delete

Деструктор не вызывается автоматически в двух других случаях:

1. когда выходит из области видимости объект, созданный операцией new ;

2. когда из области видимости выходит указатель на объект

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