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

Шаблон очереди с приоритетом и вложенным классом - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Можно ли задать такие параметры, чтоб в функции произошла ошибка? http://www.cyberforum.ru/cpp-beginners/thread1499997.html
class TMatrix; class TVector { public: double x; double y; double z; TVector operator * (const TMatrix &Turn); TVector operator * ( double k ); };
C++ WinAPI Как завершить дочернее приложение если родительское было завершено? Ситуация такая. Есть родительское приложение. Оно создаёт дочерний процесс, с которым общается через сокет. Иногда случается, что родительское приложение падает (проблемы разработки или просто сбои). Так вот нужно чтобы дочернее приложение завершалось автоматически, если родительское было завершено, но как такое проделать я не знаю. Просто сигналом из сокета об отсутствии соединеия... http://www.cyberforum.ru/cpp-beginners/thread1499202.html
Написание драйвера для мобильного модема C++
Уважаемые форумчане, кто занимался написанием драйверов для 3g либо 4g usb модема? Можете подсказать, к каким данным мы имеем доступ, то есть конкретно интересует возможность вывести в систему данные о сети (Cell ID, LAC, C1, C2, CRO)? Насколько я знаю, мобильный телефон на основе параметра вышки C2 решает переключиться ли ему к другой базовой станции. Возможно ли получить подобные данные от...
Как посмотреть код ассемблера в Visual Studio 2012? Visual Studio
Есть код программы на C++. Как посмотреть коды ассемблера для этой программы в MS Visual Studio 2012? Добавлено через 3 часа 15 минут Нашёл. Когда запускаешь трассировку программы, нажать ПКМ и выбрать пункт меню Go To Disassembly.
C++ Удаление файлов: типы и способы http://www.cyberforum.ru/cpp-beginners/thread1498584.html
Здравствуйте. Подозреваю что существует несколько методов удаления файлов. Удаление без изменения области памяти в которой хранилось что то (до записи нового файла на это место) и удаление с перезаписью. Подскажите так ли это? Существуют только такие методы удаления? Что из себя представляет удаление без перезаписи (какие именно действия производит ОС?)? Существуют ли API для "полного...
C++ Выделение памяти с помощью new под объекты без вызова их конструкторов здравствуйте, корректен ли следующий код: myClass* pttr = static_cast<myClass*>(::operator new(5 * sizeof(myClass))); for (int i = 0; i < 5; i++){ new(pttr+i) myClass(); } ::operator new(2*sizeof(myClass),pttr + 5); for (int i = 0; i < 5; i++){ (pttr + i)->~myClass(); подробнее

Показать сообщение отдельно
Геомеханик
 Аватар для Геомеханик
517 / 324 / 253
Регистрация: 26.06.2015
Сообщений: 738
24.07.2015, 01:26     Шаблон очереди с приоритетом и вложенным классом
Цитата Сообщение от Lena86 Посмотреть сообщение
все вроде понятно, но реализовать на практике не могу
Существует 3-варианта наиболее оптимальными для создание приоритетной очереди, самое простое написать на базе бинарной куче, по-сложнее на базе Биномиальной куче и самое сложное это Фибоначчиева куча, так что по рассматривай их тоже как-нибудь на досуге.

Вот набросал на базе бинарной куче.
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <iostream>
#include <cstdlib>
 
//функтор по-умолчанию от наибольшего к меньшему
template<typename T>
struct pcmp {
    bool operator () (const T& a, const T& b)const{
        return (a > b);
    }
};
 
//приоритетная очредь на базе бинарной кучи
template<typename T, typename Cmp = pcmp<T> >
class pqueue {
private:
    T*     arr;
    size_t cnt;
    size_t mem;
    Cmp    cmp;
public:
    pqueue(void):arr(NULL),
                 cnt(0),
                 mem(16){}
    pqueue(const T* f, const T* l):arr(NULL),
                                   cnt(0),
                                   mem(16){
        this->copy(f, l);
    }
    ~pqueue(){
        this->clear();
    }
    pqueue(const pqueue&);
    pqueue& operator = (const pqueue&);
public:
    
    //добавление
    bool push(const T& val){    
        if(! this->_alloc_array(1))
            return false;
 
        arr[cnt++] = val;
        size_t   i = cnt - 1;
        size_t   p = (i - 1) >> 1;
        while((i > 0) && cmp(val, arr[p])){
            std::swap(arr[p], arr[i]);
            i = p;
            p = (p - 1) >> 1;
        }
        return true;
    }
 
    //удаление
    void pop(void){
        if(cnt > 0){
            arr[0] = arr[--cnt];
            this->heapify(0);
        }
        if(! cnt)
            this->clear();
    }
 
    //копирование массива
    bool copy(const T* f, const T* l){
        size_t num = (size_t)(l - f);
        cnt = 0;
        if(! this->_alloc_array(num))
            return false;
 
        T* p = arr;
        while(f != l)
            *p++ = *f++;
        cnt = num;
 
        for(size_t i = cnt >> 1; i > 0; --i) 
            this->heapify(i);
        this->heapify(0);
        return true;
    }
 
    //удаление всех
    void clear(void){
        if(arr != NULL)
            delete[] arr;
        arr = NULL;
        cnt = 0;
        mem = 16;
    }
 
    T& top(void) { return arr[0]; }
    T& top(void) const { return arr[0]; }
 
    size_t size(void) const {
        return cnt;
    }
 
    bool empty(void) const {
        return (cnt == 0);
    }
 
private:
    
    bool _alloc_array(size_t n){
        size_t tmem;
        if(arr == NULL){
            tmem = mem;
            if(n > tmem)
                tmem = n;
            arr = new (std::nothrow) T[tmem];
            if(arr == NULL)
                return false;
            mem = tmem;
        } else if((cnt + n) >= mem){
            tmem   = cnt + n + mem / 3;
            T* tmp = new (std::nothrow) T[tmem];
            if(tmp == NULL)
                return false;
 
            T* p = tmp;
            T* e = arr + cnt;
            for(T* i = arr; i != e; ++i)
                *p++ = *i;
 
            delete[] arr;
            arr = tmp;
            mem = tmem;
        }
        return true;
    }
 
    void heapify(size_t i){
        size_t li, ri, big;
 
        while(1) {
            li = (i << 1) + 1;
            ri = li + 1;
            if((li < cnt) && cmp(arr[li], arr[i]))
                big = li;
            else
                big = i;
 
            if((ri < cnt) && cmp(arr[ri], arr[big]))
                big = ri;
 
            if(big != i){
                std::swap(arr[big], arr[i]);
                i = big;
            }else
                break;
        }
    }
};
 
// от наименьшего к большему
struct intcmp {
    bool operator () (int a, int b)const{
        return (a < b);
    }
};
 
 
int main(void){
    pqueue<char> pch;
    for(int i = 0; i < 30; ++i)
        pch.push('A' + (char)(std::rand() % 26));   
        
    while(! pch.empty()){
        std::cout << pch.top();
        pch.pop();
    }
    std::cout << std::endl;
 
    //...
 
    int A[] = { 5, 2, 8, 6, 7, 1, 9, 3, 0, 4 };
    pqueue<int, intcmp> pq(A, A + sizeof(A)/sizeof(A[0]));
 
    while(! pq.empty()){
        std::cout << pq.top() << ' ';
        pq.pop();
    }
    return 0;
}
Результат работы кода
 
Текущее время: 18:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru