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

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

Восстановить пароль Регистрация
 
via-82
0 / 0 / 0
Регистрация: 14.05.2013
Сообщений: 3
14.05.2013, 07:10     Очередь с приоритетами #1
Всем добрый день.

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

Нашел информацию:
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


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

Подскажите где ошибка.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
200 / 144 / 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
_
200 / 144 / 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++

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

Или воспользуйтесь поиском по форуму:
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     Очередь с приоритетами
Ответ Создать тему
Опции темы

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