C++. Контрольная работа. Приложение типа ConsoleApplication. Шаблонный класс CArray — массив данных произвольного типа

Контрольная работа. Приложение типа ConsoleApplication. Шаблонный класс CArray — массив данных произвольного типа

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


Содержание


Условие задачи

Разработать шаблонный класс CArray — массив данных произвольного типа T и тесты, демонстрирующие работу с этим классом. Память для массива данных выделяется динамически.

Должны быть реализованы следующие методы:

  • конструктор по умолчанию;
  • конструктор копирования;
  • деструктор;
  • метод push_back(T _value) добавляющий элемент _value в конец массива;
  • метод erase(int _index) который удаляет элемент из массива по заданному индексу _index;
  • метод insert(int _index) который вставляет элемент в массив по заданному индексу _index;
  • метод size() возвращающий размер массива;
  • метод clear() который очищает массив;
  • операторная функция operator[](), которая перегружает оператор [] индексирования элементов массива и возвращает значение элемента массива по заданному индексу;
  • метод print(), предназначенный для вывода содержимого массива на экран.

Решение должно демонстрировать работу класса при помощи следующих тестов:

  • Работа с числами (int)
    • 1.1. Добавление в цикле 20 случайных чисел в диапазоне от 0 до 100
    • 1.2. Сортировка полученного набора чисел по возрастанию
    • 1.3. Удаление каждого второго элемента в массиве
    • 1.4. Вставка 10 случайных чисел в диапазоне от 0 до 100 на случайные позиции
    • 1.5. Очистка контейнера
  • Работа с объектами (std::string)
    • 2.1. Добавление в цикле 15 случайно выбранных слов, состоящих из латинских букв нижнего регистра
    • 2.2. Сортировка полученного набора слов по возрастанию
    • 2.3. Удаление каждого слова, которое включает в себя любую из букв a, b, c, d, e
    • 2.4. Вставка трех случайно выбранных слов на случайные позиции

   


Выполнение

1. Текст программы

Реализация программы типа Console Application имеет следующий вид.

// Задача о шаблонном классе
#include <iostream>
#include <new>
#include <vector>
#include <time.h>
using namespace std;
template <typename T>

class CArray
{
public:
  // конструктор по умолчанию
  CArray()
  {
    count = 0;
  }

  // конструктор копирования - обязателен
  CArray(const CArray& _A)
  {
    try {
      // попытка выделить память для массива типа T
      A = new T[_A.count];
      count = _A.count;

      for (int i = 0; i < count; i++)
        A[i] = _A.A[i];
    }
    catch (bad_alloc e)
    {
      count = 0;
      cout << "Error. Cannot allocate memory." << endl;
      cout << e.what() << endl;
    }
  }

  // оператор копирования
  CArray& operator=(const CArray& _A)
  {
    // освободить предварительно выделенную память
    if (count > 0)
      delete[] A;

    // выделить память по новому
    try {
      A = new T[_A.count];
      count = _A.count;

      for (int i = 0; i < count; i++)
        A[i] = _A.A[i];
    }
    catch (bad_alloc e)
    {
      count = 0;
      cout << "Error. Cannot allocate memory." << endl;
      cout << e.what() << endl;
    }
    return *this;
  }

  // деструктор
  ~CArray()
  {
    // освободить предварительно выделенную память
    if (count > 0)
      delete[] A;
  }

  // добавить элемент в конец массива
  void push_back(T value)
  {
    T* A2; // дополнительный указатель на массив

    // попытка выделить память
    try {
      A2 = new T[count + 1];

      // если память выделена, то увеличить на 1 число элементов
      count++;

      // скопировать массив A в массив A2
      for (int i = 0; i < count - 1; i++)
        A2[i] = A[i];

      // добавить элемент value
      A2[count - 1] = value;

      // освободить память, выделенную под массив A
      if ((count - 1) > 0)
        delete[] A;

      // перенаправить указатель A на массив A2
      A = A2;
    }
    catch (bad_alloc e)
    {
      cout << "Error. Cannot allocate memory." << endl;
      cout << e.what() << endl;
    }
  }

  // метод, который виводит массив A - нужен для тестирования
  void print()
  {
    cout << "Array A: " << endl;

    if (!count)
    {
      cout << "Array is empty." << endl;
      return;
    }

    for (int i = 0; i < count; i++)
      cout << A[i] << " ";
    cout << endl;
  }

  // добавить элемент в массив по заданному индексу
  void insert(int _index, const T& _value)
  {
    // проверка на корректность индекса
    if (!CheckIndex(_index))
    {
      cout << "Error. Bad index. ";
      return;
    }

    T* A2;
    A2 = Alloc(count + 1); // попытка выделить память
    if (A2 == nullptr)
    {
      cout << "Error. Method insert(). Cannot allocate memory." << endl;
      return;
    }

    // копирование A в A2 до позиции _index
    for (int i = 0; i < _index; i++)
      A2[i] = A[i];

    // вставка в позиции _index
    A2[_index] = _value;

    // копирование A в A2 после позиции _index
    for (int i = _index + 1; i < count + 1; i++)
      A2[i] = A[i - 1];

    // освободить предварительно выделенную пам'ять для массива A
    if (count > 1)
      delete[] A;

    count++; // увеличить количество элементов массива на 1

    // перенаправить указатель A на массив A2
    A = A2;
  }

  // метод erase() - удаляет элемент из массива по заданному индексу _index
  void erase(int _index)
  {
    // проверка, корректен ли индекс
    if (!CheckIndex(_index))
    {
      cout << "Bad index." << endl;
      return;
    }

    // цикл удаления из массива элемента в позиции _index
    for (int i = _index; i < count - 1; i++)
      A[i] = A[i + 1];

    count--; // уменьшить количество элементов массива на 1

    // перераспределить память
    T* A2 = Alloc(count); // выделить память по новому

    // скопировать A в A2
    for (int i = 0; i < count; i++)
      A2[i] = A[i];

    // освободить память, выделенную для массива A
    if (count > 0)
      delete[] A;

    // перенаправить указатель A на A2
    A = A2;
  }

  // метод, возвращающий размер массива
  int size()
  {
    return count;
  }

  // метод, очищающий массив
  void clear()
  {
    if (count > 0)
    {
      delete[] A;
      count = 0;
    }
  }

  // операторная функция operator[], перегружает оператор индексирования массива
  T& operator[](int _index)
  {
    if (CheckIndex(_index))
      return A[_index];
    else
    {
      T value = 0;
      cout << "Bad index." << endl;
      return value;
    }
  }

protected:
  T* A; // массив данных
  int count; // количество элементов в массиве

  // внутренний метод, который проверяет, есть ли значение индекса в допустимых пределах
  // возвращает true, если индекс _index корректен
  bool CheckIndex(int _index)
  {
    if ((_index < 0) || (_index >= count))
      return false;
    return true;
  }

  // метод, выделяющий память для массива типа T,
  // метод возвращает указатель на выделеный массив
  T* Alloc(int _count)
  {
    T* A2 = nullptr;

    try {
      A2 = new T[_count];
    }
    catch (bad_alloc e)
    {
      cout << e.what() << endl;
      return nullptr;
    }
    return A2; // вернуть указатель на выделенный фрагмент
  }
};

// Тесты для демонстрации работы класса
// 1.1. Добавить в цикле 20 случайных чисел в диапазоне от 0 до 100
void Test_1_1(CArray<int>& A)
{
  int i, number;

  cout << "Test 1.1. Form the array with 20 random numbers." << endl;

  srand(time(NULL));
  for (i = 0;i < 20;i++)
  {
    // сформировать случайное число от 0 до 100
    number = rand() % 100;

    // добавить число в конец массива
    A.push_back(number);
  }
}

// 1.2. Упорядочивание набора чисел по возрастанию
void Test_1_2(CArray<int>& A)
{
  int i, j;
  int t;

  cout << "Test 1.2. Sorting the array." << endl;

  // сортировка методом вставки
  for (i=0; i<A.size()-1; i++)
    for (j=i; j>=0; j--)
      if (A[j] > A[j + 1])
      {
        t = A[j];
        A[j] = A[j + 1];
        A[j + 1] = t;
      }
}

// 1.3. Удаление каждого второго элемента
void Test_1_3(CArray<int>& A)
{
  CArray<int> B; // новый масив

  cout << "Test 1.3. Deleting every secont item." << endl;

  B.clear();
  for (int i = 0; i < A.size();i++)
  {
    if (i % 2 == 1)
      B.push_back(A[i]);
  }
  A = B;
}

// 1.4. Вставка 10 случайных чисел в диапазоне от 0 до 100 на случайные позиции
void Test_1_4(CArray<int>& A)
{
  int i;
  int number, pos;
  int t;

  cout << "Test 1.4. Inserting 10 random numbers to random positions" << endl;

  // привязаться к текущему времени при генерировании случайных чисел
  srand(time(NULL));

  t = 0; // переменная, определяющая количество добавленных чисел
  for (i = 0; i < 10; i++)
  {
    number = rand() % 100; // случайное число
    pos = rand() % (10 + t); // случайная позиция (0..10+t)
    A.insert(pos, number);
    t++; // количество добавленных чисел
  }
}

// 1.5. Очистка контейнера
void Test_1_5(CArray<int>& A)
{
  cout << "Test 1.5. Clear the array." << endl;
  A.clear();
}

// Демонстрация работи класса с числами int
void DemoInt()
{
  CArray<int> A; // массив, который должен быть протестирован

  // Тест 1.1
  Test_1_1(A);
  A.print(); // вывести массив на экран

  // Тест 1.2
  Test_1_2(A);
  A.print();

  // Тест 1.3
  Test_1_3(A);
  A.print();

  // Тест 1.4
  Test_1_4(A);
  A.print();

  // Тест 1.5
  Test_1_5(A);
  A.print();
}

// 2. Работа с объектами (std::string)
// 2.1. Добавление в цикле 15 случайно выбранных слов, состоящих из латинських букв в нижнем регистре
void Test_2_1(CArray<string>& A)
{
  int i, j;
  int len; // длина слова
  string word;
  char symbol;

  cout << "Test 2.1. Adding 15 new words." << endl;
  srand(time(NULL));

  // цикл формирования слов
  for (i = 0; i < 15; i++)
  {
    len = rand() % 6 + 1; // случайная длина слова от 1 до 6

    // сформировать случайное слово
    word = "";
    for (j = 0;j < len;j++)
    {
      // получить случайный символ
      symbol = 'a' + rand() % ((int)'z' - (int)'a' + 1);
      word += symbol; // добавить символ к слову
    }
    A.push_back(word); // добавить случайное слово в массив
  }
}

// 2.2. Упорядочивание набора слов по возрастанию
void Test_2_2(CArray<string>& A)
{
  int i, j;
  string t;

  cout << "Test 2.2. Sorting words." << endl;

  // сортировка методом вставки
  for (i = 0;i < A.size() - 1;i++)
  {
    for (j=i; j>=0; j--)
      if (A[j] > A[j + 1])
      {
        t = A[j];
        A[j] = A[j + 1];
        A[j + 1] = t;
      }
  }
}

// 2.3. Удаление каждого слова, включающего в себя любую из букв a,b,c,d,e
void Test_2_3(CArray<string>& A)
{
  // дополнительные переменные
  int i, j;
  string word;
  CArray<string> B;
  bool f_delete;

  cout << "Test 2.3. Deleting words wit characters a..z " << endl;

  // цикл создания нового массива B, который не содержит слов
  for (i = 0; i < A.size(); i++)
  {
    word = A[i];
    f_delete = false;
    for (j=0; j<word.length(); j++)
      if (('a' <= word[j]) && (word[j] <= 'e')) // если символ в пределах 'a'..'e'
    {
      f_delete = true; // то можна удалять
      break;
    }

    // добавить слово в масив B, которое не содержит 'a'..'e'
    if (!f_delete)
      B.push_back(word);
  }
  A = B; // скопировать массив B в A
}

// 2.4. Вставка 3-х новых случайных слов на случайные позиции
void Test_2_4(CArray<string>& A)
{
  int i, j;
  int len; // случайная длина случайного слова
  string word; // случайное слово
  char symbol; // случайный символ
  int position; // случайная позиция (0, 1, ...)
  int t; // количество добавленных слов

  cout << "Test 2.4. Inserting 3 new random words to random positions" << endl;

  // привязка к таймеру при формировании случайных слов
  srand(time(NULL));

  // Цикл добавления случайных слов
  for (i = 0, t = 0; i < 3; i++, t++)
  {
    // взять случайную позицию
    position = rand() % (A.size() + t);

    // взять случайную длину слова 1..6
    len = rand() % 6 + 1;

    // сгенерировать случайное слово
    word = "";

    for (j = 0; j < len; j++)
    {
      // сформировать случайный символ
      symbol = 'a' + rand() % ((int)'z' - (int)'a' + 1);
      word += symbol; // добавить символ к слову
    }

    // вставить случайное слово word в случайную позицию position
    A.insert(position, word);
  }
}

// Метод, демонстрирующий работу с объектами std::string
void DemoString()
{
  CArray<string> A; // объявить массив слов для тестирования

  Test_2_1(A);
  A.print();

  Test_2_2(A);
  A.print();

  Test_2_3(A);
  A.print();

  Test_2_4(A);
  A.print();
}

int main()
{
  DemoInt();
  DemoString();
}

   

2. Результат работы программы
Test 1.1. Form the array with 20 random numbers.
Array A:
40 55 83 90 71 0 38 98 15 49 44 69 74 82 84 90 88 14 93 10
Test 1.2. Sorting the array.
Array A:
0 10 14 15 38 40 44 49 55 69 71 74 82 83 84 88 90 90 93 98
Test 1.3. Deleting every secont item.
Array A:
10 15 40 49 69 74 83 88 90 98
Test 1.4. Inserting 10 random numbers to random positions
Array A:
10 15 38 93 84 40 83 71 49 69 40 88 74 74 83 15 88 90 44 98
Test 1.5. Clear the array.
Array A:
Array is empty.
Test 2.1. Adding 15 new words.
Array A:
txkhs crt paqkm shcni wgagcv ye jlww rayr qtjc usd bprcx s yvd pwxb jobx
Test 2.2. Sorting words.
Array A:
bprcx crt jlww jobx paqkm pwxb qtjc rayr s shcni txkhs usd wgagcv ye yvd
Test 2.3. Deleting words wit characters a..z
Array A:
jlww s txkhs
Test 2.4. Inserting 3 new random words to random positions
Array A:
jlww acrtk xk s qkm txkhs

   

3. Объяснение к программе
3.1. Вызов функций для тестирования работы класса

Из функции main() вызываются функции DemoInt() и DemoString(). Каждая из функций вызывает соответствующий тест.

Функция DemoInt() вызывает тесты для типа int. Каждый тест оформлен в виде отдельной функции: Test_1_1(), Test_1_2(), Test_1_3(), Test_1_4(), Test_1_5(). Каждая из тестируемых функций получает входным параметром ссылку на массив типа int

CArray<int>& A

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



Функция DemoString() вызывает тесты для класса std::string. Класс string реализован в пространстве имен std и предназначен для работы со строками символов типа char*. Класс содержит ряд методов для работы со строками символов. Каждый тест для типа string оформлен в виде отдельной функции: Test_2_1(), Test_2_2(), Test_2_3(), Test_2_4(). Как и в случае с типом int, любая из функций получает входным параметром ссылку на массив типа string

CArray<string>& A

В каждой тестируемой функции изменяется входной массив (передача массива по ссылке).

   

3.2. Почему в классе реализован конструктор копирования и оператор копирования?

В классе CArray объявляется динамический массив A обобщенного типа T. Фактически, объявляется указатель A на тип T

T* A; // массив данных

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

   

3.3. Особенности выделения памяти в операторе new

В классе в разных функциях происходит выделение памяти с помощью оператора new. Существует риск, что память может не выделиться. В этом случае, система генерирует исключение (exception). Для того, чтобы выполнение программы не прекращалось, а выводилось соответствующее сообщение, вызов оператора new взят в блок try…catch как показано ниже

...
try {
  // попытка выделить память для массива типа T
  A = new T[_A.count];
  count = _A.count;

  for (int i = 0; i < count; i++)
    A[i] = _A.A[i];
}
catch (bad_alloc e)
{
  count = 0;
  cout << "Error. Cannot allocate memory." << endl;
  cout << e.what() << endl;
}
...

Как видно из кода, в блоке catch перехватывается исключение типа bad_alloc. bad_alloc – это класс, который описывает исключительную ситуацию в случае, когда память оператором new не выделилась. Класс bad_alloc унаследован из класса exception и есть частью иерархии классов, которые описывают исключения в C++.

   

3.4. Освобождение памяти в классе оператором delete[]

Поскольку, память для массива A выделяется как для массива (а не одиночного элемента)

A = new T[count]

то освобождать ее нужно оператором

delete[] A;

Если бы память выделялась как для одиночного элемента, то вместо delete[] нужно было использовать delete.



   

3.5. Дополнительные внутренние функции класса

В классе, в разделе private реализованы следующие дополнительные внутренние функции

  • CheckIndex() – проверяет, находится ли индекс массива A в допустимых границах;
  • Alloc() – возвращает указатель на выделенный участок памяти заданного размера _count, который есть входным параметром.

Эти функции вызываются несколько раз в разных методах класса.

   

3.6. Особенности генерирования случайных чисел. Функции srand(), time(), rand()

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

  • srand() – устанавливает стартовое число для функции rand(). На основе этого числа будет формироваться последовательность случайных чисел функцией rand();
  • rand() – возвращает целочисленное случайное число (генерирует случайное число);
  • time() – функция из библиотеки time.h.

Функция time() с параметром NULL

time(NULL)

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

Функция time() вложена как параметр в функции srand()

srand(time(NULL));

Функция srand() устанавливает стартовое число, которое будет использоваться как основа генерирования последовательности случайных чисел функцией rand().

Значит, объединение функций srand(), time(), rand() разрешает при каждом вызове генерировать различные последовательности чисел.

   


Связанные темы