Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

Очередь с приоритетом - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Задача перебрать игру змейка и расписать комментариями до запятой http://www.cyberforum.ru/cpp-beginners/thread588439.html
Что успею до 6 июня. Задача до запятой расписать код и полностью изменить, потом зачёт. Может кому пригодится, Я же со своей стороны наивно надеюсь на помощь. Файл с дополнительными комментариями...
C++ Дана строка и файл с русским текстом Задание Дана строка и файл с русским текстом, зашифрованным по правилу, описанному в задании 7. Данная строка представляет собой первую расшифрованную строку текста. Расшифровать остальные строки и... http://www.cyberforum.ru/cpp-beginners/thread588423.html
Нужно оформить в виде функции C++
Есть две программы: #include <iostream> #include <conio.h> #include <stdlib.h> #include <ctime> #include <cmath> using namespace std; const int n=15; int main()
Координаты точки пересечения двух отрезков C++
День добрый уважаемые читатели форума. Разбираю задачу по расчету Координаты точки пересечения двух отрезков и столкнулся с проблемой. Выбивает подобные ошибки при компиляции Debug: Run-Time Check...
C++ Считать строки с файла, выравнивая их по центру, записать в другой файл http://www.cyberforum.ru/cpp-beginners/thread588372.html
Здравствуйте, прошу вас помочь, на носу экзамен, а я все ни как не могу решить задачу. Условие задачи таково: Составить программу, которая читает текст из разбитого на строки текстового файла, и...
C++ работа с файлами Здравствуйте! Написать программу, определяющую сумму "S=1/2+......+1/10," записывать S во внешний файл, закрыть файл, открыть файл и прочитать s #include<stdio.h> #include<conio.h> ... подробнее

Показать сообщение отдельно
gray_fox
What a waste!
1521 / 1226 / 70
Регистрация: 21.04.2012
Сообщений: 2,565
Завершенные тесты: 3
27.05.2012, 21:13
Очередь с приоритетом - очередь, где элементы каким-то образом упорядочены. В данном случае, если считать, что добавляем в начало очереди, а извлекаем из конца, массив внутри этой очереди должен быть отсортирован по убыванию (если я правильно понял про "постановку запросов"). Т.е. при top (доступ к последнему элементу) должен возвращатся минимальный элемент, при pop (удаление последнего) он удаляется из очереди, при push (добавление в очередь) свойство упорядоченности должно сохраняться. Как сделать? Проще всего при добавлении нового элемента (push) добавлять его в конец массива, а потом сортировать массив по убыванию. Посложнее: работать с массивом как с кучей, для этого в STL есть алгоритмы (push_heap, pop_heap и пр.).

Добавлено через 27 минут
Цитата Сообщение от gray_fox Посмотреть сообщение
массив внутри этой очереди должен быть отсортирован по убыванию
Здесь наврал, конечно, отсортирован не должен быть, просто первый(последний) элемент должен быть минимальным. Извиняюсь.

Добавлено через 4 минуты
Вот так это может выглядеть, со статическим массивом и алгоритмами из стл:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#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;
}
http://liveworkspace.org/code/d100202bfac5dc3a04b59b13fd1d49c5
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru