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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Программка из 4 главы книги Страуструпа принципы и практика - не работает http://www.cyberforum.ru/cpp-beginners/thread1502246.html
В общем в 4 главе в подпункте векторы на странице 152 имеется вот такой код: #include <iostream> #include <conio.h> #include "std_lib_facilities.h" #include <clocale> int main() { setlocale (LC_ALL, "Russian");
C++ NullReferenceException через некоторое время Написал простенькую программу. Получает дескриптор окна, в таймере проверяет цвет пикселя на экране и если все верно, то отправляет через PostMessage() сообщения WM_LBUTTONDOWN и WM_LBUTTONDOWN. Некоторое время программа работает нормально, а потом вылетает ошибка NullReferenceException. Пишу на С++ с использованием функций WinAPI. Заметил что при работе программы постоянно увеличивается объем... http://www.cyberforum.ru/cpp-beginners/thread1502239.html
Утечка памяти (решение СЛАУ методом Крамера, матрицы, malloc) C++
Раньше программировал на C#/Java (а как следствие и расхлябанность по отношению к памяти), сейчас пытаюсь осилить C++. Более-менее понял как работают указатели и malloc/calloc/строки. Попробовал закрепить полученные знания на практике - написать программу без vector<>'ов, которая решала бы СЛАУ методом Крамера. Результат налицо - несколько утечек памяти, битый час уже разбираю код и никак не...
Порядок инициализации членов класса C++
Здравствуйте форумчане. Столкнулся с проблемой. Не могу найти доходчивой статьи на данный вопрос про инициалиазцию членов в классе. Прошу вас доходчиво ответить на этот вопрос.
C++ Работа в теле конструктора http://www.cyberforum.ru/cpp-beginners/thread1502172.html
constructor Account::Account(int initialBalance) { if (initialBalance >= 0) balance = initialBalance; if (initialBalance <= 0) { balance = 0; cout << "Incorrect value!\n" << endl; }
C++ Класс "Животное" Задача такова: нужно написать класс, условно говоря, "животное" со свойствами:имя, возраст и голос. И внутри класса конструктор и метод, который выводит эту инфу на экран в стиле "такое-то животное зовут так-то и блаблабла". Собственно проблема возникла с тем, что информация задается в параметре, и у меня никак не получается ее вывести. Если спросить у пользователя эти же данные и сохранить... подробнее

Показать сообщение отдельно
Геомеханик
618 / 425 / 309
Регистрация: 26.06.2015
Сообщений: 960
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;
}
Результат работы кода
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru