C++,Visual C++,Теорія

C++. Приклад реалізації черги з пріоритетами для шаблонного класу у вигляді динамічного масиву




Приклад реалізації черги з пріоритетами для шаблонного класу у вигляді динамічного масиву

Перед вивченням даної теми рекомендується ознайомитись з наступною темою:

Зміст

Пошук на інших ресурсах:

1. Способи реалізації черги з пріоритетами

Черга з пріоритетами може бути реалізована одним з двох способів:

  • як черга з пріоритетним включенням (рисунок 1). При цьому способі елемент додається у чергу не в кінець а згідно з його пріоритетом. Витягується елемент звичайним способом – з початку черги;
  • як черга з пріоритетним виключенням (рисунок 2). При цьому способі елемент додається в кінець черги а витягується згідно з його пріоритетом. У випадку рівності пріоритетів, першим витягується той елемент, який був першим розміщений у черзі (елемент, що ближчий до початку черги).

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

Рисунок 1. Черга з пріоритетним включенням

 

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

Рисунок 2. Черга з пріоритетним виключенням

  ⇑

2. Приклад реалізації черги з пріоритетами для шаблонного класу у вигляді динамічного масиву
2.1. Загальний опис роботи програми

У прикладі оголошується клас QueueP, що реалізує чергу з пріоритетним включенням. Тобто, кожен новий елемент що додається в чергу займає своє місце в залежності від пріоритету. Витягування елементу здійснюється звичайним шляхом. Черга реалізована у вигляді динамічного масиву.

У класі QueueP оголошуються:

  • A – динамічний масив елементів типу T. Ці елементи утворюють чергу;
  • P – динамічний масив пріоритетів кожного елементу з масиву A. Елементу A[0] відповідає пріоритет P[0], елементу A[1] відповідає пріоритет P[1] і т.д. Кількість елементів в масивах A і P однакова;
  • count – поточна кількість елементів у черзі;
  • конструктор за замовчуванням QueueP();
  • конструктор копіювання QueueP(const QueueP&);
  • деструктор ~QueueP();
  • оператор копіювання operator=(const QueueP&);
  • функція Push(), що додає новий елемент в чергу;
  • функція Pop(), що витягує елемент з черги;
  • функція Clear() – реалізує очищення черги;
  • функція Count() – повертає кількість елементів у черзі.

За бажанням можна додати інші додаткові функції для роботи черги.

  ⇑




2.2. Вихідний код програми

Вихідний код програми, що реалізує клас QueueP наступний.

#include <iostream>
#include <new>
using namespace std;

// Черга з пріоритетами для типу T
template <typename T>
class QueueP
{
private:
  T* A; // динамічний масив елементів типу T
  int* P; // масив пріоритетів
  int count; // к-сть елементів у черзі

public:
  // конструктори
  // конструктор без параметрів
  QueueP() { count = 0; }

  // конструктор копіювання
  QueueP(const QueueP& _Q)
  {
    try {
      // спроба виділити пам'ять
      A = new T[_Q.count];
      P = new int[_Q.count];
    }
    catch (bad_alloc e)
    {
      // якщо пам'ять не виділилась то обробити помилку
      cout << e.what() << endl;
      count = 0;
      return;
    }

    // скопіювати _Q => *this
    count = _Q.count;

    // поелементне копіювання даних
    for (int i = 0; i < count; i++)
      A[i] = _Q.A[i];

    for (int i = 0; i < count; i++)
      P[i] = _Q.P[i];
  }

  // деструктор
  ~QueueP()
  {
    if (count > 0)
    {
      delete[] A;
      delete[] P;
    }
  }

  // оператор копіювання - щоб уникнути побітове копіювання
  QueueP operator=(const QueueP& _Q);

  // функція, що додає в чергу новий елемент
  void Push(T item, int priority);

  // функція, що витягує з черги перший елемент
  T Pop();

  // очищення черги
  void Clear()
  {
    if (count > 0)
    {
      delete[] A;
      delete[] P;
      count = 0;
    }
  }

  // повертає кількість елементів у черзі
  int Count()
  {
    return count;
  }

  // функція, що виводить чергу
  void Print(const char* objName);
};

// оператор копіювання
template <typename T>
QueueP<T> QueueP<T>::operator=(const QueueP& _Q)
{
  // 1. Звільнити пам'ять, яка була перед цим виділена для поточного об'єкту
  if (count > 0)
  {
    delete[] A;
    delete[] P;
    count = 0;
  }

  // 2. Спроба виділити новий фрагмент пам'яті
  try {
    A = new T[_Q.count];
    P = new int[_Q.count];
  }
  catch (bad_alloc e)
  {
    // якщо пам'ять не виділено, то вихід
    cout << e.what() << endl;
    return *this; // повернути пусту чергу
  }

  // 3. Якщо пам'ять виділено, то копіювання *this <= _Q
  count = _Q.count;

  // 4. Цикл копіювання даних
  for (int i = 0; i < count; i++)
  {
    A[i] = _Q.A[i];
    P[i] = _Q.P[i];
  }
  return *this;
}

// додає в чергу новий елемент item з пріоритетом priority
template <typename T>
void QueueP<T>::Push(T item, int priority)
{
  // 1. Створити новий масив-чергу та масив-пріоритет
  T* A2;
  int* P2;

  try {
    // спроба виділити пам'ять для нового масиву
    A2 = (T*)new T[count + 1];
    P2 = (int*)new int[count + 1];
  }
  catch (bad_alloc e)
  {
    // якщо пам'ять не виділено, то вихід
    cout << e.what() << endl;
    return;
  }

  // 2. Пошук позиції pos в масиві P згідно з пріоритетом priority
  int pos;

  if (count == 0)
    pos = 0;
  else
  {
    pos = 0;
    while (pos < count)
    {
      if (P[pos] < priority) break;
        pos++;
    }
  }

  // 3. Копіювання даних A2<=A; P2<=P
  // за формулою P = [0,1,...] + pos+1 + [pos+2,pos+3,...]
  // 3.1. Індекси масиву з номерами 0..pos
  for (int i = 0; i < pos; i++)
  {
    A2[i] = A[i];
    P2[i] = P[i];
  }

  // 3.2. Додати елемент в позиції pos
  A2[pos] = item;
  P2[pos] = priority;

  // 3.3. Елементи після позиції pos
  for (int i = pos + 1; i < count + 1; i++)
  {
    A2[i] = A[i - 1];
    P2[i] = P[i - 1];
  }

  // 4. Звільнити пам'ять, попередньо виділену для A та P
  if (count > 0)
  {
    delete[] A;
    delete[] P;
  }

  // 5. Перенаправити покажчики A->A2, P->P2
  A = A2;
  P = P2;

  // 6. Збільшити к-сть елементів у черзі на 1
  count++;
}

// Функція, що витягує з черги перший елемент
template <typename T>
T QueueP<T>::Pop()
{
  // 1. Перевірка
  if (count == 0)
    return 0;

  // 2. Оголосити тимчасові масиви
  T* A2;
  int* P2;

  // 3. Спроба виділити пам'ять для A2, P2
  try {
    A2 = new T[count - 1]; // на 1 елемент менше
    P2 = new int[count - 1];
  }
  catch (bad_alloc e)
  {
    // якщо пам'ять не виділено, то повернути 0 і вихід
    cout << e.what() << endl;
    return 0;
  }

  // 4. Запам'ятати перший елемент
  T item;
  item = A[0];

  // 5. Скопіювати дані з масивів A=>A2, P=>P2 без першого елементу
  for (int i = 0; i < count - 1; i++)
  {
    A2[i] = A[i + 1];
    P2[i] = P[i + 1];
  }

  // 6. Звільнити попередньо виділену пам'ять для A, P
  if (count > 0)
  {
    delete[] A;
    delete[] P;
  }

  // 7. Поправити к-сть елементів у черзі
  count--;

  // 8. Перенаправити покажчики A->A2, P->P2
  A = A2;
  P = P2;

  // 9. Повернути перший елемент черги
  return item;
}

// Функція, що виводить чергу на екран
template <typename T>
void QueueP<T>::Print(const char* objName)
{
  cout << "Object: " << objName << endl;
  for (int i = 0; i < count; i++)
    cout << A[i] << ":" << P[i] << "\t" << endl;
  cout << endl;
  cout << "---------------" << endl;
}

void main()
{
  QueueP<int> Q1;
  QueueP<int> Q2 = Q1;

  Q1.Push(15, 7);
  Q1.Push(18, 9);
  Q1.Push(18, 9);
  Q1.Push(18, 9);
  Q1.Push(1, 3);
  Q1.Push(8, 6);
  Q1.Push(11, 6);
  Q1.Push(4, 6);
  Q1.Print("Q1");

  int d;
  d = Q1.Pop();
  d = Q1.Pop();
  d = Q1.Pop();
  d = Q1.Pop();
  Q1.Print("Q1");
  cout << "d = " << d << endl;

  QueueP<int> Q3 = Q1; // конструктор копіювання
  Q3.Print("Q3");

  QueueP<int> Q4;
  Q4 = Q3 = Q1; // оператор присвоєння копіюванням
  Q4.Print("Q4");
  cout << "count = " << Q4.Count() << endl;

  Q4.Clear();
  Q4.Print("Q4");

  cout << "count = " << Q4.Count() << endl;
}

  ⇑

3. Результат виконання програми

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

Object: Q1
18:9
18:9
18:9
15:7
8:6
11:6
4:6
1:3

---------------
Object: Q1
8:6
11:6
4:6
1:3

---------------
d = 15
Object: Q3
8:6
11:6
4:6
1:3

---------------
Object: Q4
8:6
11:6
4:6
1:3

---------------
count = 4
Object: Q4

---------------
count = 0

  ⇑

Зв’язані теми

  ⇑