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

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

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

Дописать прогу Priority Queue class используя heap для хранения данных - C++

19.04.2013, 09:41. Просмотров 599. Ответов 0
Метки нет (Все метки)

Помогите, пожалуйста, дописать программу Priority Queue class используя heap для хранения данных:
мне нужно даписать все не законченные member functions of the PriorityQueue class, таким образом чтобы класс
использовал heap, чтобы хранить и восстанавливать елементы.
Особенно не обходимо завершить следующие функции:
- PriorityQueue()
- insert()
- get_front()
- print_tree()
- is_leaf()
- parent_index()
- parent_priority()
- big_child_priority()
- swap_with_parent().

Heap использует массив фиксированного размера, что бы хранить данные.

Головной файл:
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
#ifndef PQUEUE_H
#define PQUEUE_H
#include <cstdlib> // Provides size_t
 
    class PriorityQueue
    {
    public:
        // TYPEDEF and MEMBER CONSTANT
        typedef double Item;
        static const size_t CAPACITY = 5000;
        // CONSTRUCTOR
        PriorityQueue( );
        // MODIFICATION MEMBER FUNCTIONS
        void insert(const Item& entry, unsigned int priority);
        Item get_front( );
        // CONSTANT MEMBER FUNCTIONS
        size_t size( ) const { return many_items; }
        bool is_empty( ) const { return (many_items == 0); }
        // MEMBER FUNCTION FOR DEBUGGING
        void print_tree(const char message[ ] = "", size_t i = 0) const;
    private:
        // STRUCT DEFINITION to store information about one item in the pqueue
        struct OneItemInfo
        {
            Item data;
            unsigned int priority;
        };
        // PRIVATE MEMBER VARIABLES
        OneItemInfo heap[CAPACITY];
        size_t many_items;
        // PRIVATE HELPER FUNCTIONS -- see pqueue2.cxx for documentation
        bool is_leaf(size_t i) const;
        size_t parent_index(size_t i) const;
        unsigned int parent_priority(size_t i) const;
        size_t big_child_index(size_t i) const;
        unsigned int big_child_priority(size_t i) const;
        void swap_with_parent(size_t i);
    };
 
#endif
file implementation:
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
#include <cassert>    // Provides assert function
#include <iostream>  // Provides cin, cout
#include <iomanip>   // Provides setw
#include <cmath>      // Provides log2
#include "pqueue2.h"
using namespace std;
 
PriorityQueue::PriorityQueue( )
{
    // Здесь необходима помощь
}
 
void PriorityQueue::insert(const Item& entry, unsigned int priority)
{
    //// Здесь необходима помощь
}
 
PriorityQueue::Item PriorityQueue::get_front( )
{
    // // Здесь необходима помощь
}
 
bool PriorityQueue::is_leaf(size_t i) const
// Precondition: (i < many_items)
// Postcondition: If heap[i] has no children in the heap, then the function
// returns true. Otherwise the function returns false.
{
    // To be completed by the student
}
 
size_t PriorityQueue::parent_index(size_t i) const
// Precondition: (i > 0) && (i < many_items)
// Postcondition: The return value is the index of the parent of heap[i].
{
    // // Здесь необходима помощь
}
 
unsigned int PriorityQueue::parent_priority(size_t i) const
// Precondition: (i > 0) && (i < many_items)
// Postcondition: The return value is the priority of the parent of heap[i].
{
    // // Здесь необходима помощь
}
 
size_t PriorityQueue::big_child_index(size_t i) const
// Precondition: !is_leaf(i)
// Postcondition: The return value is the index of one of heap[i]'s children.
// This is the child with the larger priority.
{
    // // Здесь необходима помощь
}
 
unsigned int PriorityQueue::big_child_priority(size_t i) const
// Precondition: !is_leaf(i)
// Postcondition: The return value heap[big_child_index(i)].priority
{
    //// Здесь необходима помощь
}
 
void PriorityQueue::swap_with_parent(size_t i)
// Precondition: (i > 0) && (i < many_items)
// Postcondition: heap[i] has been swapped with heap[parent_index(i)]
{
    // // Здесь необходима помощь
}
 
void PriorityQueue::print_tree(const char message[ ], size_t i) const
// Postcondition: If the message is non-empty, then that has been written
// to cout. After the message, the portion of the heap with root at node
// node i has been written to the screen. Each node's data is indented
// 4*d, where d is the depth of the node.
// NOTE: The default argument for message is the empty string, and the
// default argument for i is zero. For example, to print the entire
// tree of a PriorityQueue p, with a message of "The tree:", you can call:
//     p.print_tree("The tree:");
// This call uses i=0, which prints the whole tree.
{
    // Здесь необходима помощь
}
Тест программа:
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
#include <cctype>     // Provides toupper
#include <iostream>  // Provides cout and cin
#include <cstdlib>    // Provides EXIT_SUCCESS and size_t
#include "pqueue2.h"   // Implemented using a heap
using namespace std;
 
// PROTOTYPES for functions used by this test program:
void print_menu( );
char get_user_command( );
int get_number(const char message[ ]);
void add_multiple_entries(PriorityQueue &q);
 
int main( )
{
    PriorityQueue test;
    char choice;
    cout << "CSC-161 Lesson Ten Test Program" << endl << endl;
    do
    {
        print_menu( );
        choice = toupper(get_user_command( ));
        switch (choice)
        {
            case 'E':
                if (test.is_empty( ))
                    cout << "The Priority Queue is empty." << endl;
                else
                    cout << "The Priority Queue is not empty." << endl;
                break;
            case 'G':
                if (!test.is_empty( ))
                    cout << "Front item is: " << test.get_front( ) << endl;
                else
                    cout << "There is no current item." << endl;
                break;
            case 'I':
                test.insert(get_number("Please enter the next item: "),
                    (unsigned int) get_number("The item's priority: "));
                break;
            case 'M':
                add_multiple_entries(test);
                break;
            case 'P':
                test.print_tree("Contents of heap:");
                break;
            case 'S': 
                cout << "The size is " << test.size( ) << endl;
                break;
            case 'X': 
                if (test.is_empty( ))
                    cout << "The Priority Queue is empty." << endl;
                else
                    while(!test.is_empty())
                        cout << "Value: " << test.get_front() << endl;
                break;
            case 'Q': 
                break;
            default:  
                cout << choice << " is an invalid choice." << endl;
        }
    }
    while ((choice != 'Q'));
    return EXIT_SUCCESS;
}
 
void print_menu( )
{
    cout << endl; 
    cout << "The following choices are available: " << endl;
    cout << " E   Print the result from the is_empty( ) function" << endl;
    cout << " G   Print the result from the get_front( ) function" << endl;
    cout << " I   Insert a new item with the insert(...) function" << endl;
    cout << " M   Add multiple items with varying priorities " << endl;
    cout << " P   Print the internal heap using the print_tree(...) function" << endl;
    cout << " S   Print the result from the size( ) function" << endl;
    cout << " X   Extract and print values in priority order" << endl;
    cout << " Q   Quit this test program" << endl;
}
 
char get_user_command( )
{
    char command;
    cout << "\nEnter choice: ";
    cin >> command; 
    return command;
}
 
int get_number(const char message[ ])
{
    int result;
    cout << message;
    cin  >> result;
    return result;
}
void add_multiple_entries(PriorityQueue &thisQueue)
{
    thisQueue.insert(100, 10);
    thisQueue.insert(200, 10);
    thisQueue.insert(300, 5);
    thisQueue.insert(400, 5);
    thisQueue.insert(500, 20);
    thisQueue.insert(600, 20);
    thisQueue.insert(700, 20);
    thisQueue.insert(800, 10);
    thisQueue.insert(900, 10);
    return;
}
Добавлено через 5 минут
пойдёт ли такое выполнение PriorityQueue????

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
class PriorityQueue
{
   Object data[];
   int maxItems,
       numberOfItems;
   
   public PriorityQueue(int size)
   {
      maxItems = size;
      data = new Object[maxItems];
      numberOfItems = 0;
   }
   
   public boolean isEmpty()
   {
      return numberOfItems == 0;
   }
   
   public void insert(Object item)
   {
      int position = numberOfItems-1;
      while (position >= 0 && data[position].pValue >= item.pValue)
      {
         data[position+1] = data[position];
         --position;
      }
      data[position+1] = item;
      ++numberOfItems;
   }
   
   public Object delete()
   {
      --numberOfItems;
      return data[numberOfItems];
   }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.04.2013, 09:41     Дописать прогу Priority Queue class используя heap для хранения данных
Посмотрите здесь:
C++ Разработать программу формирования списка кандидатов, участвующих в выборах мэра (priority queue) - C++
Реализуйте класс для хранения ФИО и номера телефона человека, класс для хранения даты рождения человека, а также класс для хранения ФИО и почтового ад C++
дописать прогу C++
C++ Стек для хранения данных
C++ дописать прогу на си++ двум мас
C++ Подскажите контейнер для хранения данных
Класс для хранения массива данных C++
помогите дописать прогу по двум мас C++
C++ Как организовать массив для хранения данных?
Выделение памяти для хранения массива данных C++
Структуры данных для хранения и работы с матрицами C++
C++ Работа со структурой для хранения данных о ноутбуках

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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