2010-11-04 249 views
1

在我的任务中,我知道我需要使用我的堆删除功能,它返回要打印的变量。但是这项任务的要求很模糊,我很好奇,如果有人能给我一个更好的解释。我很困惑如何使用第二个或第三个参数我知道一些排序是必需的,我需要两个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 
+0

对不起,我不明白。需要更多细节。顺便说一下,'stdout'是用于C - 在C++中,你使用'cout'。 – 2010-11-04 00:47:37

+0

@steve Townsend只是添加了我的代码,希望能够澄清一些事情。 – rajh2504 2010-11-04 01:19:25

回答

0

从我可以收集它看起来像第二个参数是空间列表中的一个元素时,允许它打印出来占用数量。第三个参数是允许在一行上打印的元素的数量。在你的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这样的基本类型,但想象一下包含几个不同成员的类型。想一想如何在其他功能中使用这个谓词 - 你能比较一下“<”还是“>”?