堆二叉树打印方法

Question

在我的作业中，我知道我需要使用堆删除函数，该函数返回要打印的变量。但作业中的要求相当模糊，我很好奇是否有人能给我更好的解释。我对如何使用第二个或第三个参数感到非常困惑，我知道需要进行一些排序，并且我需要两个 for 循环，但之后我迷失了。作业内容如下：

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

该函数从堆结构中检索项目并将其打印在标准输出上。为了从堆结构中检索单个项目，它调用remove函数。该函数的第一个参数是堆结构的向量，第二个参数是 stdout 上打印项目的分配大小，第三个参数是单行上打印项目的最大数量，最后一个参数是谓词。

这是我的代码：

#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();

v.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

Answer 1

据我所知，第二个参数似乎是列表中的一个元素在打印出来时允许占用的空格数。第三个参数是允许在一行上打印的元素数量。在 print_list 函数中，您需要跟踪已打印的元素数量，以确定是否需要根据此参数转到下一行。使用这两者，您应该能够很好地调整输出。您将需要研究如何进行输出格式化。

例如。列表 = [1, 9, 14, 2000, 244, 777, 3, 98102, 88, 53, 14]，大小 = 6，行 = 3
输出：

     1     9    14
  2000   244   777
     3 98102    88
    53    14

你的最后一个参数是一个谓词，你似乎没有在任何函数中实际使用它（当你根本不使用参数时，这表明你做错了什么）。谓词函数参数应该用来做一些对于传入的类型 T 来说是唯一的事情。例如，在 print_list 中，它应该用来打印 T 类型的变量。如果您按照当前的方式打印一个元素，不保证该类型能够正确打印。当然，它适用于 int 和 double 等基本类型，但想象一下具有多个不同成员的类型。考虑一下您将如何在其他函数中使用此谓词 - 您可以仅将对象与 '<' 进行比较吗或“>”？