Приклад реалізації черги з пріоритетами для шаблонного класу у вигляді динамічного масиву
Перед вивченням даної теми рекомендується ознайомитись з наступною темою:
Зміст
- 1. Способи реалізації черги з пріоритетами
- 2. Приклад реалізації черги з пріоритетами для шаблонного класу у вигляді динамічного масиву
- 3. Результат виконання програми
- Зв’язані теми
Пошук на інших ресурсах:
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
⇑
Зв’язані теми
- Стек. Способи реалізації. Операції над стеком. Приклад реалізації стеку у вигляді динамічного масиву
- Черга. Способи реалізації черги. Представлення черги у вигляді динамічного масиву
⇑