Объектно-ориентированное программирование - Учебное пособие (А.А. Хусаинов)

2.8. статические элементы класса

 

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

Пример. Определим класс строки, содержащий подпрограмму, возвращающую количество объектов этого класса, находящихся в области видимости. Определим статическую переменную many целого типа. Конструктор объекта будет увеличивать эту переменную на 1, а деструктор – уменьшать на 1. Распределение области памяти, занимаемой объектами класса, приведено на рис. 2.1.

 

Int many

- поле, содержащееся в каждом объекте

Объект

char *s

int

length

Объект

char *s

int

length

· · ·

Объект

char *s

int

length

- поля объектов, содержащие указатели на строки и длины строк

 

 

 

 

 

Подпись: Рис. 2.1. Распределение области памяти 

Приведём текст программы:

 

#include <iostream.h>

#include <conio.h>

#include <string.h>

 

class Vstring

   {

   // Закрытые элементы

               static int many;            // Количество объектов Vstring

               char *s;                                                // Строка

               int length;                                // Длина строки

   public: // Общедоступные элементы

               Vstring(char *text)      // Конструктор

                           {

                           length = strlen(text);   // Вычисление длины

                           s = new char[length+1];          // Выделение памяти

                           strcpy(s, text);             // Копирование строки

                           many++;                                  // Увеличение числа объектов

                           }

 

 

               ~Vstring()       // Деструктор

                           {

                           delete s;           // Освобождение памяти

                           many--;     // Уменьшение числа объектов

                           }

 

               static int Number() { return many; } // Статическая функция

 

               // Общая функция

               void get()

                           {

                           cout << s << ' ';

                           }

};

 

int Vstring::many = 0; // Установка начального числа объектов

 

void main()

   {

   clrscr();            // Очистка экрана

 

   cout << "Количество объектов Vstring: " << Vstring::Number() << ' ';

 

   Vstring u("12345");

   cout << "Количество объектов Vstring: " << Vstring::Number() << ' ';

 

   Vstring v("12345");

   cout << "Количество объектов Vstring: " << Vstring::Number() << ' ';

 

   cout << "Значение объекта v: ";

   v.get();

   cout << ' ';

 

   for(int i = 0; i < 3; i++)

               {

               cout<<"Количество объектов Vstring: "<<Vstring::Number()<<' ';

               Vstring v("12345");

               cout<<"Количество объектов Vstring: "<<Vstring::Number()<<' ';

               getch();

               }

   }

 

Результаты работы программы

 

   Количество объектов Vstring: 0

   Количество объектов Vstring: 1

   Количество объектов Vstring: 2

   Значение объекта v: 12345

 

   Количество объектов Vstring: 2

   Количество объектов Vstring: 3

   Количество объектов Vstring: 2

   Количество объектов Vstring: 3

   Количество объектов Vstring: 2

   Количество объектов Vstring: 3

 

2.9. Шаблоны функций

 

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

 

Type x, y, temp;

. . .

temp = x; x = y; y = temp;

 

будет работать для Type = int, для Type = double и для любого нового типа, определенного в программе с помощью класса. Логика алгоритма одинакова для всех типов данных. Эту ситуацию можно обобщить. Многие алгоритмы допускают отделение метода от данных. Программы, реализующие такие алгоритмы, можно отлаживать для данных одного типа, а затем применять для обработки данных других типов. Функции, реализующие эту возможность, называются параметризованными. Аргументы этих функций определяются с помощью ключевого слова template. Тип, который определяет это ключевое слово, называется шаблоном. Общая форма определения шаблона функции template приведена ниже:

 

   template <class T> прототип функции (аргументы)

               {

               тело функции;

               }

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

 

template <class Tswp> void swap(Tswp& x, Tswp& y)

   {

   Tswp temp;

   temp = x; x = y; y = temp;

   }

 

void main()

   {

   int a = 1, b = 2;

   double c = 1.1, d = 2.2;

   swap(a, b);       // Перестановка целых чисел

   swap(c, d); // Перестановка чисел с плавающей точкой

   }

 

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

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

 

template <class T>         // Ключевое слово и параметр

const T& Max(const T& a, const T& b)

   {

   return a>b? a:b;

   }

 

void main()

   {

   int i = 1, j = 2;

   float r = 1.1, s = 1.2;

   int k = Max(i, j);

   float t = Max(r, s);

   }

 

Параметризованные функции могут быть перегружены другими функциями, которые тоже могут быть параметризованы, например:

 

template <class T> const T& Max(const T&, const T&);

template <class T> const T& Max(const T*, int);

int Max(int, int);

 

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

 

const char* Max(const char* c, const char* d)

   {

   // Выполнить действия, специфичные для char*

   }

 

Пример. Параметризованная функция бинарного поиска в отсортированном массиве.

 

#include <iostream.h>

#include <conio.h>

template <class Type>

int binsearch(Type* x, int count, Type key)

   {

   int low, high, mid;       // Левый, правый и средний элементы

   low = 0; high = count - 1;

 

   while (low <= high)

               {

               mid = (low+high)/2;    // Вычисление середины массива

 

               if(key < x[mid]) high = mid - 1;          // Если нужный элемент

                                                                           // находится слева от середины

               else if(key > x[mid]) low = mid + 1;   // Если справа

               else return mid;           // Нашли

               }

 

   return -1;         // Не нашли

   }

 

void main()

   {

   clrscr();            // Очистка экрана

 

   int nums[] = {1, 2, 3, 5, 7, 11, 13, 17};           // Массив, в котором ищем

   cout << "5 находится на " << binsearch(nums, 8, 5)

   cout << " месте в массиве.";

 

   getch();            // Ожидание нажатия клавиши

   }

 

Результаты работы программы

 

5 находится на 3 месте в массиве.

 

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

 

#include <iostream.h>

#include <conio.h>

 

template <class Type>

void bubble (Type *x, int n)      // Сортировка методом пузырьков

   {

   int i, j;

   Type t;

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

               for(j = n-1; j >= i; --j)

                           {

                           if(x[j-1] > x[j])

                                       {

                                       t = x[j-1]; x[j-1] = x[j]; x[j] = t;

                                       }

                           }

   }

 

void main()

   {

   clrscr();            // Очистка экрана

 

   int i;

   int nums[] = {10, 12, 11, 3, 5, 12, 10};           // Исходный массив

   cout << "Исходный массив: ";

   for(i = 0; i < 7; i++) cout << nums[i] << "  ";

   cout << ' ';

   bubble (nums, 7);        // Сортировка

 

   cout << "Отсортированный массив: ";

   for(i = 0; i < 7; i++) cout << nums[i] << " ";

 

   getch();            // Ожидание нажатия клавиши

   }

 

Результаты работы программы

 

Исходный массив: 10 12 11 3 5 12 10

Отсортированный массив: 3 5 10 10 11 12 12

 

В неупакованном BCD-формате старшим байтом представляется знак, младшая цифра числа записывается как нулевой элемент массива, следующая цифра – первый элемент массива и т.д.

Например, число 123 представляется байтами:

 

a[0] = ‘3’, a[1] = ‘2’, a[2] = ‘1’, a[n-1] = ‘-’.

 

Здесь n – количество разрядов числа.

 

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

 

#include <iostream.h>

#include <string.h>

#include <conio.h>

template <class Type>

void bubble (Type *x, int n)      // Сортировка методом пузырьков

   {

   int i, j;

   Type t;

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

               for(j = n-1; j >= i; --j)

                           {

                           if(x[j-1] > x[j])

                                       {

                                       t = x[j-1]; x[j-1] = x[j]; x[j] = t;

                                       }

                           }

   }

 

// Класс BCD чисел

class Bcd

   {

   // Недоступные элементы класса

               static int n;      // Максимальный размер BCD чисел

               char *a;                        // Массив под BCD число

   public:

   // Общедоступные элементы класса

               // Перегрузка оператора =

               void operator = (char *b);

 

               // Перегрузка оператора >

               int operator > (Bcd x);

 

               void show();    // Вывод BCD числа на экран

   };

 

// Перегрузка оператора =

void Bcd::operator = (char *b)

   {

   int i;

   a = new char[n];          // Выделение памяти под BCD число

 

   for(i = 0; i < n; i++)

               a[i] = '0';                      // Инициализация его нулями

 

   i = strlen(b);                 // Определение длины присваиваемого числа

   int k = i - 1;                 // Запоминаем её

 

   // Копирование знака числа

   if(b[0] == '+' || b[0] == '-')

               {

               i--;

               a[n - 1] = b[0];

               }

   else a[n - 1] = '+';

 

   // Копирование самого числа

   for(int j = 0; j < i; j++) a[j] = b[k - j];

   }

 

// Перегрузка оператора >

int Bcd::operator > (Bcd x)

   {

   int i = 0;

   // Если первое число положительное,

   // а второе - отрицательное, то первое больше

   if(this->a[n-1] == '+' && x.a[n-1] == '-') return 1;

 

   // Если первое число отрицательное,

   // а второе - положительное, то первое меньше

   if(this->a[n-1] == '-' && x.a[n-1] == '+') return 0;

 

   // Сравнение по отдельным цифрам

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

               {

               if(this->a[n - 1 - i] > x.a[n - 1 - i])

                           {

                           if(x.a[n - 1] == '+') return 1;

                           else return 0;

                           }

               else if(this->a[n - 1 - i] < x.a[n - 1 - i])

                           {

                           if(x.a[n - 1] == '+') return 0;

                           else return 1;

                           }

               }

   return 0;

   }

 

// Вывод BCD числа на экран

void Bcd::show()

   {

   // Создание вспомогательной строки

   char *str;

   str = new char[n+1]; // Выделение под неё памяти

   str[0] = a[n-1]; // Копирование знака

   str[n] = '';                  // Постановка конечного нуля

 

   // Копирование цифр

   int i;

   for(i=n-2; i>=0; i--) str[n-i-1] = a[i];

 

   // Вывод строки на экран

   cout << str;

   delete str;        // Освобождение памяти

   }

Теперь вызываем параметризованную функцию для сортировки массива Bcd:

 

int Bcd::n = 15; // Максимальная длина BCD числа

 

void main()

   {

   clrscr();            // Очистка экрана

 

   Bcd x[10];       // Создание массива bcd чисел

   // Инициализация BCD чисел

   x[0] = "1234"; x[1] = "924";   x[2] = "-92";    x[3] = "0";

   x[4] = "-1";   x[5] = "10";  x[6] = "12";  x[7] = "1";

   x[8] = "-2";   x[9] = "12345";

 

   // Вывод неотсортированного массива

   cout << "Неотсортированные BCD числа: ";

   for(int i = 0; i < 10; i++)

               {

               x[i].show();

               cout << ' ';

               }

   bubble(x, 10);  // Сортировка методом пузырьков

 

   // Вывод отсортированного массива

   cout << "Отсортированные BCD числа: ";

   for(i = 0; i < 10; i++)

               {

               x[i].show();

               cout << ' ';

               }

 

   getch();            // Ожидание нажатия клавиши

   }

 

Результаты работы программы

 

Неотсортированные BCD числа:

+00000000001234

+00000000000924

-00000000000092

+00000000000000

-00000000000001

+00000000000010

+00000000000012

+00000000000001

-00000000000002

+00000000012345

Отсортированные BCD числа:

-00000000000092

-00000000000002

-00000000000001

+00000000000000

+00000000000001

+00000000000010

+00000000000012

+00000000000924

+00000000001234

+00000000012345

 

Пример. Рассмотрим параметризованную подпрограмму (функцию) сортировки методом выбора. Сначала находим наименьший элемент массива и переставляем  его с первым элементом. Затем из оставшихся элементов находим наименьший и переставляем его со вторым элементом и т.д. Для того чтобы не переставлять элемент сам с собой в том случае, когда он уже является наименьшим среди элементов подмассива, определим переменную exchange, которая будет равна 0, если перестановки не нужны. Получим следующую подпрограмму:

template <class Type>

void select(Type *x, int count)

{

   int i, j, k, exchange;

   Type t;

   for(i=0; i<count-1; i++)

   {

               exchange=0;

               k=i; t=x[i];

               for(j=i+1; j<count; j++)

               {

                           if(x[j]<t)

                           {

                                       k=j; t=x[j]; exchange=1;

}

}

if(exchange)

{

                           x[k]=x[i]; x[i]=t;

}

}

}

 

Вызов подпрограммы осуществляется слудующим образом :

 

int nums[] = {1, 3, 8, -1, 12, -1, 15};

Select(nums, 7);

 

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

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

 

#include <iostream.h>   //библиотека потокового ввода-вывода

#include <conio.h>        //библиотека консольного ввода-вывода

//параметризованная функция быстрой сортировки Хоара

template <class Type>

void qs(Type *a, int left, int right)

{

   int i, j;              //левая и правая границы массива

   Type x, y;

   i = left; j = right;

   x = a[(left+right)/2];  //определим "центр" массива

   do

   {

               //произведём поиск элементов для перестановки

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

               while(x<a[j] && j>left) j--;

               if(i<=j)

               {

                           //выполняем перестановку

                           y=a[i]; a[i]=a[j]; a[j]=y;

                           i++; j--;

               }

   }

   while(i<=j);

   if(left<j) qs(a, left, j);  //рекурсивный вызов для левой части

   if(i<right) qs(a, i, right);//рекурсивный вызов для правой части

}

//ос