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

Массив и очередь с приоритетом - C++

Восстановить пароль Регистрация
 
Razor32
0 / 0 / 0
Регистрация: 15.12.2010
Сообщений: 22
17.11.2012, 20:23     Массив и очередь с приоритетом #1
Здравствуйте! Помогите, пожалуйста, найти информацию(или объясните принцип работы) о реализации очереди с приоритетами через массив.

Хотелось бы понять: какую структуру создавать для работы с ней, как идет представление в памяти, и как пробежать от начала очереди до конца

Заранее спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.11.2012, 20:23     Массив и очередь с приоритетом
Посмотрите здесь:

Очередь с приоритетом C++
C++ очередь с приоритетом
C++ Очередь с приоритетом
Очередь с приоритетом C++
Очередь с приоритетом C++
C++ Очередь с приоритетом. Элементы с наивысшим приоритетом ставятся в начало очереди, с наименьшим – в конец
C++ Очередь с приоритетом
C++ Очередь с приоритетом

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
igorrr37
 Аватар для igorrr37
1593 / 1221 / 118
Регистрация: 21.12.2010
Сообщений: 1,868
Записей в блоге: 7
17.11.2012, 22:24     Массив и очередь с приоритетом #2
примерчик очереди с приоритетом на основе std::vector. Осталось написать свой контейнер (по типу std::vector), реализовать в нём методы push_back(), pop_back(), front(), begin(), end(), empty(), тип size_type и передать этой очереди.
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
 
template<typename T, typename Container = std::vector<T>>
class PriorityQueue
{
public:
    void push(T const& lhs)
    {
        con.push_back(lhs);
        std::push_heap(con.begin(), con.end());
    }
    void pop()
    {
        std::pop_heap(con.begin(), con.end());
        con.pop_back();
    }
    T const& top()const
    {
        return con.front();
    }
    typedef typename Container::size_type size_type;
    size_type size() const
    {
        return con.size();
    }
    bool empty() const
    {
        return con.empty();
    }
private:
    Container con;
};
 
int main()
{
    PriorityQueue<std::string> pq;
    pq.push("sd sd");
    pq.push("zz xx x");
    pq.push("ad,a");
    pq.push("wt wrr wf");
    while(!pq.empty())
    {
        std::cout << pq.top() << std::endl;
        pq.pop();
    }
    return 0;
}
Razor32
0 / 0 / 0
Регистрация: 15.12.2010
Сообщений: 22
18.11.2012, 00:47  [ТС]     Массив и очередь с приоритетом #3
Спасибо, но мне несколько не это надо. Мне хотелось бы увидеть пример структуры для организации это очереди. Мне нельзя использовать очереди из std. Например структура для очереди с приоритетами на основе односвязного списка выглядит так:

C++
1
2
3
4
5
6
struct SL
{
    int v;//значение
    int prior;//приоритет
    SL *next;//ссылка на следующий
};
Вот и мне надо нечто подобное, только реализация не на основе односвязного списка, а на основе массива. А вот цикл для того, чтобы пробежать от начала и до конца этой очереди. В классе хранится верхний элемент этой очереди.

C++
1
for(SL *temp=top;temp!=NULL;temp=temp->next)
Если не сложно, то скажите эти две вещи...
Yandex
Объявления
18.11.2012, 00:47     Массив и очередь с приоритетом
Ответ Создать тему
Опции темы

Текущее время: 23:46. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru