开发者

Heap binary tree print method

In my assignment I know I am required to use my heap remove function which returns the variable to be printed. But the requirement in teh assignment is quite vague and I was curious if someone could give me a better explanation. I am quite confused as to how to use the second or third arguments I know some sorting is required and I need two for loops but after that I am lost. here is what the assignment says:

template <class T, class P> void print_list (vector<T>&, 
    const int, const int, P); 

This function retrieves items from a heap structure and prints them out on stdout. To retrieve a single item from the heap structure, it calls the remove function. The first argument to this function is a vector for the heap structure, the second argument is the allocated size of a printed item on stdout, the third argument is the maximum number of printed items on a single line, and the last argument is a predicate.

Here is my code:

#include "340.h"

#ifndef H_PROG7
#define H_PROG7

// data files

#define D1 "prog7.d1"
#define D2 "prog7.d2"
#define D3 "prog7.d3"

#define INT_SZ 4    // width of integer
#define FLT_SZ 7    // width of floating-pt number
#define STR_SZ 12   // width of string

#define INT_LN 15   // no of integers on single line
#define FLT_LN 9    // no of floating-pt nums on single line
#define STR_LN 5    // no of strings on single line

// function prototypes

template<class T,class P> void insert(vector<T>&, const T&, P);
template<class T,class P> T remove(vector<T>&, P);

template<class T,class P> void upheap(vector<T>&, int, P);
template<class T,class P> void downheap(vector<T>&, int, P);

template<class T,class P>
void get_list(vector<T>&, const char*, P);

template<class T,class P>
void print_list(vector<T>&, const int, const int, P);

template<class T, class P>
void get_list(vector<T>& v, const char* file, P func) {
ifstream inFile("file");
T data;

while(inFile >> data) {
  inFile >> data;
  insert(v, data, func);
}
}

template<class T, class P>
void insert(vector<T>& v, const T& data, P func) {
v.push_back( data );
upheap( v, v.size()-1, func );
}

template<class T,class P>
void upheap(vector<T>& v, int start, P func) {

while( start <= v.size()/2 )   {

  unsigned int parent = start / 2;

  if( parent - 1  <= v.size() && v[parent - 1] > v[parent] )
     parent = parent - 1;

  if( v[start] <= v[parent] )
     break;

  swap( v[start], v[parent] );
  start = parent;
}
}

template<class T,class P>
void downheap(vector<T>& v, int start, P func) {

while(start <= v.size()/2 )   {

  unsigned int child = 2 * start;

  if( child + 1 <= v.size() && v[child + 1] > v[child])
     child = child + 1;

  if( v[start] >= v[child] )
     break;

  swap( v[start], v[child] );
  start = child;
}
}

template<class T,class P>
T remove(vector<T>& v, P func) {
swap( v[0], v.back() );
T& item = v.back();

开发者_如何学Gov.pop_back();
downheap( v, 1, func );

return item;
}

template<class T,class P>
void print_list(vector<T>& v, const int size, const int line, P func) {

for(int i = 1; i < v.size(); i++) {
  cout << remove(v, func) << " ";
}
}

#endif


From what I can gather it looks like the 2nd parameter is the number of spaces one element in the list is allowed to take up when it's printed out. The 3rd parameter is the number of elements that are allowed to be printed on one line. In your print_list function, you will need to keep track of how many elements you've printed to determine if you need to go to the next line or not based on this parameter. Using both of these, you should be able to align your output nicely. You will need to look into how to do output formatting.

Eg. list = [1, 9, 14, 2000, 244, 777, 3, 98102, 88, 53, 14], size = 6, line = 3 Output:

     1     9    14
  2000   244   777
     3 98102    88
    53    14

Your last parameter is a predicate, which you don't seem to actually be using in any of your functions (a sign you're doing something wrong when you're not using a parameter at all). The predicate function parameter should be used to do something that is unique to the type T being passed in. For example, in print_list, it should be used to print a variable of type T. If you print an element the way you are currently doing, there is no guarantee that the type will get printed properly. Of course, it would work for basic types like int and double, but imagine a type with several different members. Think about how you would need to use this predicate in your other functions too - can you just compare objects with '<' or '>'?

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜