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

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

Войти
Регистрация
Восстановить пароль
 
via-82
0 / 0 / 0
Регистрация: 14.05.2013
Сообщений: 3
#1

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

14.05.2013, 07:10. Просмотров 485. Ответов 6
Метки нет (Все метки)

Всем добрый день.

Надо реализовать класс очереди с приоритетами.

Нашел информацию:
1. http://edu.nstu.ru/courses/saod/queue.htm (псевдокод)
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
//---------------------------------------------------------------------------
#ifndef _PQueue
#define _PQueue
//---------------------------------------------------------------------------
#include <iostream.h>
#include <malloc.h>
#include <fstream.h>
#include <windows.h>
 
template <class T> class PQueue{
        private:
                class QItem{
                        public:
                                T data;
                                int pr;
                                QItem(T d,int p){
                                        data = d;
                                        pr = p;
                                }
                };
                QItem *item;
            QItem **prqueue;                                                
            int N;
                int n;
        public:
            PQueue(int N0){                                                 
                N = N0;
                prqueue = new QItem*[N];
                        /*for (int i = 0; i < N; i++){
                                table[i] = new Node;
                        } */
                        n = 0;
            }
//----------------------------------------------------------------------------------------
            int Size(){
                        return n;
            }
//----------------------------------------------------------------------------------------
            int Size_max(){
                return N;
            }
//----------------------------------------------------------------------------------------
            void Enqueue(T d,int p){
                        /*if (n = Size_max()){
                                return NULL;//error "overflow"
                        }else{*/
                                QItem *temp;
                                item = new QItem(d, p);
                                prqueue[n] = item;
                                int i = n;
                                while ((i > 0) && (prqueue[i]->pr < prqueue[i/2]->pr)){
                                        temp = prqueue[i];
                                        prqueue[i] = prqueue[i/2];
                                        prqueue[i/2] = temp;
                                        i=i/2;
                                }
                        //}
                        n++;
                }
//----------------------------------------------------------------------------------------
            T Dequeue(){
                        T x;
                        QItem *temp;
                        if (n==0){
                                return NULL;//error "underflow"
                        }else{
                                item = prqueue[0];
                                x = item->data;
                                prqueue[0] = prqueue[n];
                                n--;
                                if(n==0){
                                        return x;
                                }
                                int i = 0,j;
                                while (i <= n/2){
                                        if ((2*i < n) && (prqueue[2*i+1]->pr < prqueue[2*i]->pr)){
                                                j = 2*i+1;
                                        }else  {
                                                j = 2*i;
                                        }
                                        if (prqueue[i]->pr > prqueue[j]->pr){
                                                temp = prqueue[i];
                                                prqueue[i] = prqueue[j];
                                                prqueue[j] = temp;
                                                i = j;
                                        }else{
                                                i = n;
                                        }
                                }
                                return x;
                        }
            }
//----------------------------------------------------------------------------------------
            bool Empty(){
                        if(n!=0){
                                return false;
                        }
                        return true;
            }
//----------------------------------------------------------------------------------------
            ~PQueue(){
                        delete [] prqueue;
                        prqueue = NULL;
 
            }
};
#endif


Вставка элементов проходит нормально, как и должно быть.
Но с получением элементов проблемы.

Подскажите где ошибка.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.05.2013, 07:10     Очередь с приоритетами
Посмотрите здесь:

Очередь с приоритетами - C++
Бьюсь над вопросом как вывести очередь на консоль в виде пирамиды/двоичного дерева? Очередь реализуется массивом целых чисел. Заранее...

Сумма массива с приоритетами - C++
Подскажите с чего начать решение задачи: Есть n предметов, нужно выбрать так, что бы общий вес был меньше 30кг, а цена - найбольшей. Ну и...

Ошибка в очереди с приоритетами - C++
Здравствуйте, не работает ни пуш, ни поп. Помогите найти ошибку) struct s_i { string s; size_t ind; s_i(string s_, size_t...

Высчитать значение выражения с приоритетами - C++
Дана строка символов, представляющих собой арифметическое выражение, содержащее только знаки +,-,*,/,(,) и строчные буквы английского...

Сформировать очередь по файлу целых чисел. Промоделировать очередь в супермаркете - C++
Сформировать очередь по файлу целых чисел. Промоделировать очередь в супермаркете. В каждый момент времени происходит одно из событий:...

Очередь (сделать очередь, чтобы добавляло, удаляло, читало. Не STL.) - C++
Помогите пожалуйста написать очередь. Есть Температура double и ее тип int ну и нужно сделать очередь, чтобы добавляло, удаляло, читало....

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
14.05.2013, 11:40     Очередь с приоритетами #2
замените строки 76-81 на это
C++
1
2
3
while ( ( j = 2 * i ) < n ) {
    if ( j + 1 < n && prqueue[ j + 1 ]->pr < prqueue[ j ]->pr )
        ++j;
via-82
0 / 0 / 0
Регистрация: 14.05.2013
Сообщений: 3
14.05.2013, 12:56  [ТС]     Очередь с приоритетами #3
Я еще допустил ошибку в 70 строке
C++
1
prqueue[0] = prqueue[n];
должно быть
C++
1
prqueue[0] = prqueue[n-1];
Okonenko Stanis
6 / 6 / 1
Регистрация: 06.02.2013
Сообщений: 71
14.05.2013, 15:43     Очередь с приоритетами #4
- ya_noob, Ваше условие while использует переменную j, а она выше по коду не инициализирована!?
C++
1
2
3
while ( ( j = 2 * i ) < n ) {
    if ( j + 1 < n && prqueue[ j + 1 ]->pr < prqueue[ j ]->pr )
        ++j;
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
14.05.2013, 17:42     Очередь с приоритетами #5
via-82, что-то я не доглядел раньше, у вас ошибка в логике. у каждого узла i потомками являются узлы i*2 и i*2+1. а ваша куча начинается с узла с индексом 0, а его потомками будут 0*2=0!!! и 0*2+1=1, т.е. узел 0 является своим же потомком. Ошибка. Исправляйте.


Okonenko Stanis, j инициализируется в условии цикла, так что всё норм.
Okonenko Stanis
6 / 6 / 1
Регистрация: 06.02.2013
Сообщений: 71
14.05.2013, 19:35     Очередь с приоритетами #6
- Простите за невнимательность! Не заметил! Думал (==), а там (=). Еще раз простите ...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.05.2013, 19:53     Очередь с приоритетами
Еще ссылки по теме:

Задача на очередь (вывод сообщения, что очередь пуста) - C++
Доброго дня! Есть задачка на очередь, которая работает нормально, только надо добавить код, чтобы выводил сообщение, что очередь пуста.....

Функция добавления и увеличения элемента из очереди с приоритетами - C++
У меня еще одна проблема:( нужно написать функцию добавления и увеличения элемента из очереди с приоритетами. При необходимости можно...

Построить класс для работы с очередью с приоритетами - C++
Построить класс для работы с очередью с приоритетами, содержащим информацию о поездах дальнего следования. Элемент списка содержит...

Создать очередь. Добавить элемент в очередь. Удалить элемент из очереди - C++
Нужно создать очередь. Добавить элемент в очередь. Удалить элемент из очереди. Вот моё &quot;творение&quot;. int main() { int...


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

Или воспользуйтесь поиском по форуму:
via-82
0 / 0 / 0
Регистрация: 14.05.2013
Сообщений: 3
14.05.2013, 19:53  [ТС]     Очередь с приоритетами #7
Кое-что
исправил
Кликните здесь для просмотра всего текста
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
//---------------------------------------------------------------------------
#ifndef _PQueue
#define _PQueue
//---------------------------------------------------------------------------
#include <iostream.h>
#include <malloc.h>
#include <fstream.h>
#include <windows.h>
 
template <class T> class PQueue{
        private:
                class QItem{
                        public:
                                T data;
                                int pr;
                                QItem(T d,int p){
                                        data = d;
                                        pr = p;
                                }
                };
                QItem *item;
            QItem **prqueue;                                                // aeiaie?. iannea iauaeoia
            int N;
                int n;
        public:
            PQueue(int N0){                                                 // eiino?oeoi? n ia?aiao?ii (?acia? i?a?aae)
                N = N0;
                prqueue = new QItem*[N];
                        n = -1;
            }
//----------------------------------------------------------------------------------------
            int Size(){
                        return n+1;
            }
//----------------------------------------------------------------------------------------
            int Size_max(){
                return N;
            }
//----------------------------------------------------------------------------------------
            void Enqueue(T d,int p){
                        QItem *temp;
                        item = new QItem(d, p);
                        n++;
                        prqueue[n] = item;
                        int i = n;
                        while ((i > 0) && (prqueue[i]->pr < prqueue[i/2]->pr)){
                                temp = prqueue[i];
                                prqueue[i] = prqueue[i/2];
                                prqueue[i/2] = temp;
                                i = i/2;
                        }
                }
//----------------------------------------------------------------------------------------
            T Dequeue(){
                        T x;
                        QItem *temp;
                        if (n == -1){
                                return NULL;
                        }else{
                                item = prqueue[0];
                                x = item->data;
                                prqueue[0] = prqueue[n];
                                n--;
                                if(n == -1){
                                        return x;
                                }
                                int i = 0,j;
                                while (i <= n/2){
                                        if ((2*i< n) && (prqueue[2*i+1]->pr < prqueue[i]->pr)){
                                                j = 2*i + 1;
                                        }else {
                                                j = 2*i + 2;
                                                if(j>n){
                                                        return x;
                                                }
                                        }
                                        if (prqueue[i]->pr > prqueue[j]->pr){
                                                temp = prqueue[i];
                                                prqueue[i] = prqueue[j];
                                                prqueue[j] = temp;
                                                i = j;
                                        }else{
                                                i = n;
                                        }
                                }
                                return x;
                        }
            }
//----------------------------------------------------------------------------------------
            bool Empty(){
                        if(n==-1){
                                return true;
                        }
                        return false;
            }
//----------------------------------------------------------------------------------------
            ~PQueue(){
                        delete [] prqueue;
                        prqueue = NULL;
 
            }
};
#endif


Но у меня закрались смутные сомнения, что алгоритм описанный в источниках вообще рабочий.

Кто-нибудь по данным источникам реализовал очередь с приоритетами.
Yandex
Объявления
14.05.2013, 19:53     Очередь с приоритетами
Ответ Создать тему
Опции темы

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