1

Тема: Пріоритетна черга

Встановлення в чергу виконується підряд в кінець черги, зняття – за пріоритетом. Черга організована на масиві або списку.
Пріоритет – мінімальне значення числового параметра, при збігу параметра – LIFO.
Буду вдячна за допомогу)

2

Re: Пріоритетна черга

Можливо більш логічно буде організувати обчислення місця додавання, залежно від приоритету?

Подякували: burlakad1

3

Re: Пріоритетна черга

yarko написав:

Можливо більш логічно буде організувати обчислення місця додавання, залежно від приоритету?

мені, для початку,хоча б так її реалізувати

4

Re: Пріоритетна черга

Не той розділ - не бачу жодного рядка на C чи C++. Тим більше, що ви не сказали, на чому саме пишете.

5

Re: Пріоритетна черга

koala написав:

Не той розділ - не бачу жодного рядка на C чи C++. Тим більше, що ви не сказали, на чому саме пишете.

Я була б рада зрозуміти,як це реалізується на С++,тому і створила тему саме тут

6

Re: Пріоритетна черга

Щоб зрозуміти, вам треба не тему створювати, а код писати. А то
http://s018.radikal.ru/i504/1305/4e/128b3beefcef.jpg

7 Востаннє редагувалося burlakad (21.04.2015 17:17:33)

Re: Пріоритетна черга

koala написав:

Щоб зрозуміти, вам треба не тему створювати, а код писати. А то
http://s018.radikal.ru/i504/1305/4e/128b3beefcef.jpg

Ось мій код,але,на жаль, моїх знань недостатньо,аби правильно реалізувати цю програму. Дякую,ви дуже допомогли.

#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;
}

8

Re: Пріоритетна черга

Вітаю, ви вже навчилися працювати з гуглом. Ще допомога потрібна?

9

Re: Пріоритетна черга

koala написав:

Вітаю, ви вже навчилися працювати з гуглом. Ще допомога потрібна?

Ваша? Пфф. Ні,дякую

10

Re: Пріоритетна черга

Це не воно - Купа?

11

Re: Пріоритетна черга

Почитайте хоча б Боровского
Знається там є якась глава про пріоритетні черги

12 Востаннє редагувалося Yola (22.04.2015 13:00:35)

Re: Пріоритетна черга

yarko написав:

Почитайте хоча б Боровского
Знається там є якась глава про пріоритетні черги

Нісенітниця якась, чому б не почитати книги визнаних світових авторитетів. Цей Боровський,що спеціаліст з алгоритмів найвищого рівня? Нащо такі поради давати?

13

Re: Пріоритетна черга

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

14 Востаннє редагувалося P.Y. (23.04.2015 06:35:05)

Re: Пріоритетна черга

burlakad написав:

Встановлення в чергу виконується підряд в кінець черги, зняття – за пріоритетом. Черга організована на масиві або списку.
Пріоритет – мінімальне значення числового параметра, при збігу параметра – 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;

Лишається все це дописати й по-людському оформити. Якщо щось незрозуміло/не працює/виникли питання — звертайтесь.