Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → C++ → Пріоритетна черга
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
Встановлення в чергу виконується підряд в кінець черги, зняття – за пріоритетом. Черга організована на масиві або списку.
Пріоритет – мінімальне значення числового параметра, при збігу параметра – LIFO.
Буду вдячна за допомогу)
Можливо більш логічно буде організувати обчислення місця додавання, залежно від приоритету?
Можливо більш логічно буде організувати обчислення місця додавання, залежно від приоритету?
мені, для початку,хоча б так її реалізувати
Не той розділ - не бачу жодного рядка на C чи C++. Тим більше, що ви не сказали, на чому саме пишете.
Не той розділ - не бачу жодного рядка на C чи C++. Тим більше, що ви не сказали, на чому саме пишете.
Я була б рада зрозуміти,як це реалізується на С++,тому і створила тему саме тут
Щоб зрозуміти, вам треба не тему створювати, а код писати. А то
Щоб зрозуміти, вам треба не тему створювати, а код писати. А то
Ось мій код,але,на жаль, моїх знань недостатньо,аби правильно реалізувати цю програму. Дякую,ви дуже допомогли.
#include <iostream>
#include <algorithm>
#include <cassert>
template<typename Type, std::size_t Size>
class min_priority_queue {
public:
min_priority_queue() : index(0) {}
void push(Type const& value) {
assert(index < Size);
container[index] = value;
std::push_heap(&container[0], &container[0] + ++index, std::greater<int>());
}
void pop() {
assert(index > 0);
std::pop_heap(&container[0], &container[0] + index--, std::greater<int>());
}
Type & top() {
assert(index > 0);
return container[0];
}
Type const& top() const {
assert(index > 0);
return container[0];
}
private:
Type container[Size];
std::size_t index;
};
int main() {
min_priority_queue<int, 10> queue;
queue.push(1);
std::cout << queue.top() << std::endl;
queue.push(2);
std::cout << queue.top() << std::endl;
queue.pop();
std::cout << queue.top() << std::endl;
queue.push(-1);
std::cout << queue.top() << std::endl;
queue.push(-3);
std::cout << queue.top() << std::endl;
queue.pop();
std::cout << queue.top() << std::endl;
queue.push(6);
std::cout << queue.top() << std::endl;
}Вітаю, ви вже навчилися працювати з гуглом. Ще допомога потрібна?
Вітаю, ви вже навчилися працювати з гуглом. Ще допомога потрібна?
Ваша? Пфф. Ні,дякую
Почитайте хоча б Боровского
Знається там є якась глава про пріоритетні черги
Почитайте хоча б Боровского
Знається там є якась глава про пріоритетні черги
Нісенітниця якась, чому б не почитати книги визнаних світових авторитетів. Цей Боровський,що спеціаліст з алгоритмів найвищого рівня? Нащо такі поради давати?
А хто встановлює титул "визнаний авторитет", як не читачі. Ви не можете бути впевнені, що якийсь автор не буде в майбутньому визнаним авторитетом.
Та і читати "невизнаних" не є гріхом і за це до тюрьми не саджають. Так що не бійтесь 
Встановлення в чергу виконується підряд в кінець черги, зняття – за пріоритетом. Черга організована на масиві або списку.
Пріоритет – мінімальне значення числового параметра, при збігу параметра – LIFO.
Буду вдячна за допомогу)
Допомога ще потрібна? Спробую допомогти з усим, крім готової програми (мені лінь її писати).
Що на даному етапі ви вмієте, а в чому ще треба розбиратися? Можете самостійно написати код для дій з однозв'язним списком (що для даної задачі, ІМНО, краще, ніж масив)? Пріоритетна черга відрізнятиметься від нього тим, що в вузлі буде ще одне поле для пріоритету:
typedef struct node
{
struct node *next;
int prio;
//тут має поле якогось типу, де зберігається значення елемента черги — наприклад, int value;
} NODEЦе вузол (у якому зберігається один елемент черги), а для організації черги треба зберігати вказівник на перший вузол. Також для швидкого додавання елементів зручно зберігати вказівник на кінець списку (це необов'язково, але інакше для цієї ж дії доведеться щоразу перебирати увесь список, що незовсім продуктивно).
typedef struct queue
{
NODE *first;
NODE **end; //Зверніть увагу: вказівник на вказівник
} QUEUE;При створенні черги first має отримати значення NULL, end буде вказівником на нього:
QUEUE *q=malloc(sizeof(QUEUE));
q->first=NULL;
q->end=&(q->first);Тоді вставка елемента в чергу виглядатиме так:
NODE* nd=malloc(sizeof(NODE));
nd->next=NULL;
nd->prio=якийсь_пріоритет;
nd->value=якесь_значення;
*(q->end)=nd;
q->end=&(nd->next);Тепер найважче — виймання елемента з урахуванням пріоритету:
//тут має бути перевірка: якщо q->first == NULL, вийняти елемент неможливо
NODE**curnode = &(q->first);
NODE** minnode=curnode;
//Пошук першого елемента з найменшим пріоритетом:
while(*curnode!=NULL)
{
if ((*curnode)->prio < (*minnode)->prio)
minnode=curnode;
curnode=&((*curnode)->next);
}
//Виймаємо знайдений елемент:
res = (*minnode)->value; //записуємо кудись його значення
NODE *tmp=*minnode;
*minnode=tmp->next;//видаляємо вузол із черги
free(tmp);//звільняємо пам'ять
//Мало не забув. Оскільки в нас іще є вказівник на вказівник на останній елемент черги,
//при вийманні кінцевого елемента слід подбати і про нього:
if(*minnode==NULL)
q->end=minnode;Лишається все це дописати й по-людському оформити. Якщо щось незрозуміло/не працює/виникли питання — звертайтесь.
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися