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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Lena86
0 / 0 / 0
Регистрация: 22.08.2014
Сообщений: 81
#1

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

21.07.2015, 00:55. Просмотров 396. Ответов 2
Метки нет (Все метки)

Доброго времени суток. Задание создать шаблонный класс очереди с приоритетом плюс с вложенным классом.
Реализовать возможность добавления, извлечения, получения без извлечения элементов и очистку очереди.

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

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();
 
 
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.07.2015, 00:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Шаблон очереди с приоритетом и вложенным классом (C++):

Очередь с приоритетом. Элементы с наивысшим приоритетом ставятся в начало очереди, с наименьшим – в конец - C++
Здравствуйте! имеется задание: создать очередь с приоритетом (у каждого элемента свой приоритет). Элементы с наивысшим приоритетом ставятся...

Очереди с приоритетом - C++
Написать функции для работы с очередями с приоритетом. Создание очереди из N элементов (N и значения самих элементов читать из...

Реализация в виде класса очереди с приоритетом. - C++
День добрый, возникла проблема с представлением требования от задачи: если разбирать по компонентом, то я понимаю что они из себя...

Как сделать шаблон, с параметром-классом - потомком определённого класса? - C++
Хочется сделать шаблон с параметром-классом, который обязан реализовывать определённый интерфейс. class IService { public: ...

Шаблон очереди - C++
По идеи должен создавать очередь как очередь в магазин когда первый в очереди уходит очередь сдвигается... (2 становиться первым). ...

Шаблон очереди - C++
Это шаблон очереди на списках. Посмотрите, пожалуйста, в чём ошибка: #include &lt;iostream&gt; using namespace std; template...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
egor2116
339 / 370 / 42
Регистрация: 20.01.2013
Сообщений: 1,123
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;
}
0
Геомеханик
622 / 429 / 310
Регистрация: 26.06.2015
Сообщений: 968
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;
}
Результат работы кода
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.07.2015, 01:26
Привет! Вот еще темы с ответами:

шаблон очереди - C++
// очередь.cpp: определяет точку входа для консольного приложения. // #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &quot;stdlib.h&quot; ...

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

Шаблон очереди. В чем ошибка? - C++
Здравствуйте. Помогите, пожалуйста, с программой на С++. Условие звучит так: Разработать шаблон класса для работы с двусторонней...

Создать шаблон функции для построения очереди - C++
Помогите, пожалуйста, сделать задачу: Реализовать шаблон функции для построения очереди и работы с ней(добавление, изменение,...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru