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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ комментарии к программе http://www.cyberforum.ru/cpp-beginners/thread842303.html
можно написать построчные комментарии к программе? #include <stdio.h> #include <conio.h> #include <math.h> #include <iostream.h> struct jurnal { char njurnal; char izdatel;
C++ операторы if else Здравствуйте. Только начал работать на СИ++ Написал программу Выводит ошибку. те кто с СИ++ на Ты, помогите пожалуйста http://www.cyberforum.ru/cpp-beginners/thread842300.html
C++ Есть ли смысл в privet конструкторах и деструкторах?
Ну собственно вопрос в шапке...:)
Оператор delete C++
Вчера заметил, но ответа в сети так и не нашел: int *i = new int(5); cout << *i << endl; delete i; int p = *i; cout << p << endl; Выводит: 5 0. Но если использовать, например, массивы - то можно будет скопировать все содержимое после удаления. Что делает delete? Просто информирует систему о том, что блок памяти больше не используется?
C++ Разносторонний тупоугольный треугольник http://www.cyberforum.ru/cpp-beginners/thread842247.html
Задали задачу, не знаю как решить(. Введите 3 числа. Если они могут быть длинами сторон разностороннего тупоугольного треугольника, выведите их в порядке возрастания и вычислите площадь полученного треугольника. Помогите на С++ пожалуйста!!!!!!!!!!!
C++ Одномерные массивы (Получить x1y1+...+xsys, где x1,...,xp) Задание: Даны действительные числа r1,...,r17, среди которых заведомо есть как отрицательные, так и неотрицательные. Получить x1y1+...+xsys, где x1,...,xp - отрицательные члены последовательности r1,...,r17, взятые в порядке их следования, y1,...,yq - неотрицательные члены, взятые в обратном порядке, s=min(p,q). Написал код, но с ошибками... Прошу помочь! Заранее спасибо! #include... подробнее

Показать сообщение отдельно
cats2013
1 / 1 / 0
Регистрация: 14.04.2013
Сообщений: 17
19.04.2013, 09:41     Дописать прогу Priority Queue class используя heap для хранения данных
Помогите, пожалуйста, дописать программу 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];
   }
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 14:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru