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

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

Восстановить пароль Регистрация
 
Lena86
0 / 0 / 0
Регистрация: 22.08.2014
Сообщений: 80
21.07.2015, 00:55     Шаблон очереди с приоритетом и вложенным классом #1
Доброго времени суток. Задание создать шаблонный класс очереди с приоритетом плюс с вложенным классом.
Реализовать возможность добавления, извлечения, получения без извлечения элементов и очистку очереди.

все вроде понятно, но реализовать на практике не могу. написала горе-код, прошу помочь довести до ума

Header.h

C++
1
2
3
4
5
#pragma once
#include <iostream>
#include <string>
#include <time.h>
using namespace std;

Priority.h

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
#pragma once
#include "Header.h"
 
template <class T, class P>
class PriorityQueue
{
    class Size
    {
 
        int MaxQueueLength;
        int QueueLength;
 
        friend class PriorityQueue<T>;
    };
    
    T *Wait;
    T *Pri;
        
public:
    PriorityQueue(int s);   
    ~PriorityQueue();
 
    void Add(T a, T b);
    T Extract();
    bool IsEmpty();
    bool IsFull();
    T GetCount();
    void Show();
    void Clear();
 
};
 
template <class T, class P>
PriorityQueue<T>::PriorityQueue(int s)
{
    MaxQueueLength=s;
    Wait=new int[MaxQueueLength];
    Pri=new int[MaxQueueLength];
    QueueLength=0;
}
 
template <class T, class P>
PriorityQueue<T>::~PriorityQueue()
{
    delete[]Pri;
    delete[]Wait;
}
 
template <class T, class P>
void PriorityQueue<T>::Show()
{
    for(int i=0; i<QueueLength; i++)
    {
        cout<<Wait[i]<<"-"<<Pri[i]<<"\n"<<endl;
    }
}
 
template <class T, class P>
void PriorityQueue<T>::Clear()
{
    QueueLength=0;
}
 
template <class T, class P>
bool PriorityQueue<T>::IsEmpty()
{
    return QueueLength==0;
}
 
template <class T, class P>
bool PriorityQueue<T>::IsFull()
{
    return QueueLength==MaxQueueLength;
}
 
template <class T, class P>
T PriorityQueue<T>::GetCount()
{
    return QueueLength;
}
 
template <class T, class P>
void PriorityQueue<T>::Add(T a, T b)
{
    if(!IsFull())
    {
       Wait=a;
       Pri[QueueLength]=b;
       QueueLength++;
    }
}
 
template <class T, class P>
 T PriorityQueue<T>::Extract()
{
    if(!IsEmpty)
    {
    int max_pri=Pri[0];
    int pos_max_pri=0;
 
    for(int i=1; i<QueueLength;i++)
    {
        if(max_pri<Pri[i])
        {
            max_pri=Pri[i];
            pos_max_pri=i;
        }
        int temp1=Wait[pos_max_pri];
        int temp2=Pri[pos_max_pri];
 
        for(int i=pos_max_pri; i<QueueLength-1;i++)
        {
            Wait[i]=Wait[i+1];
            Pri[i]=Pri[i+1];
        }
        QueueLength--;
        return temp1;
    }
    }
    else return -1;
 
}


main.cpp

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include "Header.h"
#include "Priority.h"
 
void main()
{
    srand(time(0));
    PriorityQueue <int> QUP(25);
 
    for(int i=0;i<5;i++)
    {
    QUP.Add(rand()%100, rand()%12);
    }
 
    QUP.Show();
 
 
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.07.2015, 00:55     Шаблон очереди с приоритетом и вложенным классом
Посмотрите здесь:

Шаблон очереди C++
C++ Реализация в виде класса очереди с приоритетом.
Создать шаблон функции для построения очереди C++
C++ Как сделать шаблон, с параметром-классом - потомком определённого класса?
Шаблон очереди C++
шаблон очереди C++
C++ Шаблон очереди. В чем ошибка?
C++ Очередь с приоритетом. Элементы с наивысшим приоритетом ставятся в начало очереди, с наименьшим – в конец

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
egor2116
 Аватар для egor2116
337 / 368 / 42
Регистрация: 20.01.2013
Сообщений: 1,100
23.07.2015, 14:53     Шаблон очереди с приоритетом и вложенным классом #2
но реализовать на практике не могу
наверное как то так можно
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
#include <iostream>
#include <algorithm>
 
namespace cf{
 
    template<class Type>
    class PriorityQueue{
        private:
            struct Pair{
                public:
                    int priority;
                    Type value;
            };
            struct Compare{
                bool operator()(Pair & a, Pair & b){
                    return a.priority > b.priority;
                }
            };
            size_t maxSize;
            size_t nowSize;
            Pair * arr;
            Compare comp;
        public:
            PriorityQueue(){
                maxSize = 10;
                nowSize = 0;
                arr = new Pair[maxSize];
            }
            PriorityQueue(size_t s){
                maxSize = s;
                nowSize = 0;
                arr = new Pair[maxSize];
            }
            PriorityQueue(const PriorityQueue<Type> & source){
                maxSize = source.getMaxSize();
                arr = new Pair[maxSize];
                for(int i = 0; i < maxSize; ++i)
                    arr[i] = source.getData()[i];
                nowSize = maxSize - 1;
            }
            ~PriorityQueue(){
                delete [] arr;
            }
            size_t getMaxSize() const { return maxSize; }
            size_t getSize() const { return nowSize; }
            Pair * getData() const { return arr; }
            PriorityQueue & operator=(PriorityQueue<Type> & source){
                maxSize = source.getMaxSize();
                arr = new Pair[maxSize];
                for(int i = 0; i < maxSize; ++i)
                    arr[i] = source.getData()[i];
            }
            void add(Type val, int p){
                if(nowSize == maxSize - 1){
                    Pair * tempArr = new Pair[maxSize * 2];
                    for(int i = 0; i < maxSize; ++i)
                        tempArr[i] = arr[i];
                    delete [] arr;
                    arr = new Pair[maxSize * 2];
                    for(int i = 0; i < maxSize; ++i)
                        arr[i] = tempArr[i];
                    
                    arr[nowSize].value = val;
                    arr[nowSize].priority = p;
                    ++nowSize;
                    maxSize *= 2;
                    delete [] tempArr;
                }
                else{
                    arr[nowSize].value = val;
                    arr[nowSize].priority = p;
                    ++nowSize;
                    
                }
            }
            Type get(){
                if(nowSize){
                    std::sort(arr, arr + nowSize, comp);
                    return arr[nowSize - 1].value;
                }
                return Type();
            }
            Type pop(){
                if(arr){
                    std::sort(arr, arr + nowSize, comp);
                    --nowSize;
                    return arr[nowSize].value;
                }
                return Type();
            }
            void clear(){
                delete [] arr;
                nowSize = 0;
                maxSize = 10;
                arr = new Pair[maxSize];
            }
    };
}
 
int main()
{
   cf::PriorityQueue<int> q;
   q.add(11,12); // (значение, приоритет(чем меньше значение приоритета тем выше приоритет))
   q.add(10,1);
   q.add(12,2);
   q.add(13,3);
   q.add(14,4);
   q.add(15,5);
   q.add(16,6);
   q.add(17,7);
   q.add(18,8);
   q.add(19,9);
   q.add(20,10);
   q.add(21,11);  
   
   int val = q.get(); // взять без удаления
   std::cout << val << std::endl;
  
  for(int i = 0; i < q.getSize(); ++i){
        std::cout << q.getData()[i].value << " " << q.getData()[i].priority << std::endl;
   }
   
   val = 99999;
   val = q.pop(); // взять с удалением
   std::cout << val << std::endl;
  
  for(int i = 0; i < q.getSize(); ++i){
        std::cout << q.getData()[i].value << " " << q.getData()[i].priority << std::endl;
   }
   
   q.clear(); // очистка
   for(int i = 0; i < q.getSize(); ++i){
        std::cout << q.getData()[i].value << " " << q.getData()[i].priority << std::endl;
   }
 
    return 0;
}
Геомеханик
 Аватар для Геомеханик
517 / 324 / 253
Регистрация: 26.06.2015
Сообщений: 738
24.07.2015, 01:26     Шаблон очереди с приоритетом и вложенным классом #3
Цитата Сообщение от 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;
}
Результат работы кода
Yandex
Объявления
24.07.2015, 01:26     Шаблон очереди с приоритетом и вложенным классом
Ответ Создать тему
Опции темы

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