+ -
当前位置:首页 → 问答吧 → C++中建立霍夫曼树,重载<符号的问题

C++中建立霍夫曼树,重载<符号的问题

时间:2011-12-26

来源:互联网

全部代码如下:
#include"BinaryTree.h"//霍夫曼类定义
#include"MinHeap.h"
template<class T>
class Huffman
{friend BinaryTree<int>HuffmanTree(T [],int);
public:
Huffman(void){}
~Huffman(void){}
operator T()const{return weight;}
//private:
BinaryTree<int>tree;
T weight;
};

template<class T>
BinaryTree<int>HuffmanTree(T a[],int n)//建立霍夫曼树
{
Huffman<T>*w=new Huffman<T>[n+1];
BinaryTree<int>z,zero;
for(int i=1;i<=n;i++)
{
z.MakeTree(i,zero,zero);
w[i].weight=a[i-1];
w[i].tree=z;
}
MinHeap<Huffman<T>>H(1);
H.Initialize(w,n,n-1);
Huffman<T>x,y;
for(int i=1;i<n;i++)
{
H.DeleteMin(x);
H.DeleteMin(y);
z.MakeTree(0,x.tree,y.tree);
x.weight+=y.weight ;x.tree=z;
H.Insert(x);
}
H.DeleteMin(x);
H.Deactivate();
delete []w;
return x.tree;
}



#pragma once//二叉树的类定义部分
#include<iostream>
using namespace std;
template<class T>
class BinaryTreeNode
{
public:
BinaryTreeNode(const T&e,BinaryTreeNode<T>*l,BinaryTreeNode<T>*r);
~BinaryTreeNode<T>();
template<class T>
friend void pre(BinaryTreeNode<T>*);
private:
T data;
BinaryTreeNode<T>*leftchild;
BinaryTreeNode<T>*rightchild;
};
template<class T>
void pre(BinaryTreeNode<T>*t)
{
if(t)
{
cout<<t->data<<" ";
pre(t->leftchild);
pre(t->rightchild);
}
}

template<class T>
BinaryTreeNode<T>::BinaryTreeNode(const T&e,BinaryTreeNode<T>*l,BinaryTreeNode<T>*r)
{
data=e;
leftchild=l;
rightchild=r;
}
template<class T>
BinaryTreeNode<T>::~BinaryTreeNode()
{
}
template<class T>
class BinaryTree
{
public:
BinaryTree(void);
~BinaryTree(void);
void MakeTree(const T&e,BinaryTree<T>&l,BinaryTree<T>&r);
  void PreOrder(BinaryTree<T>&);
private:
BinaryTreeNode<T>*root;//根节点
};
template<class T>
BinaryTree<T>::BinaryTree()
{
root=0;
}
template<class T>
BinaryTree<T>::~BinaryTree()
{
}
template<class T>
void BinaryTree<T>::PreOrder(BinaryTree<T>&x)
{
BinaryTreeNode<T>*t;
t=x.root;
pre(t);
}
template<class T>
void BinaryTree<T>::MakeTree(const T&e,BinaryTree<T>&l,BinaryTree<T>&r)
{
root=new BinaryTreeNode<T>(e,l.root ,r.root);
l.root=r.root=0;
}




//最小堆的定义;其中OutOfBouds()的定义未给出
#include "OutOfBounds.h"
#include"Huffman.h"
#include<iostream>
#include<stdlib.h>
using namespace std;
template<class T> 
class MinHeap 

public: 
MinHeap(int MinHeapSize = 10); 
~MinHeap() {delete [] heap;} 
int Size() const {return CurrentSize;} 
T Min() 
{
if (CurrentSize == 0) 
throw OutOfBounds(); 
return heap[1];

MinHeap<T>& Insert(const T& x); 
MinHeap<T>& DeleteMin(T& x); 
void Initialize(T a[], int size, int ArraySize); 
void Deactivate() {heap = 0;} 
void Output() const; 
friend bool operator<(Huffman<int>&x1,Huffman<int>&x2);
private: 
int CurrentSize, MaxSize; 
T *heap; 
}; 
template<class T>
bool operator<(Huffman<T>&x1,Huffman<T>&x2)
{
return x1.weight<x2.weight;
}
template<class T> 
MinHeap<T>::MinHeap(int MinHeapSize) 

MaxSize = MinHeapSize; 
heap = new T[MaxSize+1]; 
CurrentSize = 0; 


template<class T> 
MinHeap<T>& MinHeap<T>::Insert(const T& x) 

if (CurrentSize == MaxSize) 
{
cout<<"溢出!"<<endl;
system("pause");
}
//为x寻找应插入的位置 
//i从新的叶节点开始,并沿着树上升 
int i = ++CurrentSize; 
while (i != 1 && x < heap[i/2])  

heap[i] = heap[i/2]; // 将元素下移 
i /= 2; // 移向父节点 

heap[i] = x; 

return *this; 


template<class T> 
MinHeap<T>& MinHeap<T>::DeleteMin(T& x) 

if (CurrentSize == 0) 
throw OutOfBounds(); 

x = heap[1]; 

T y = heap[CurrentSize--]; //最后一个元素 

// 从根开始, 为y寻找合适的位置 
int i = 1, // 堆的当前节点 
ci = 2; // i的子节点 

while (ci <= CurrentSize)  

// 使heap[ci] 是i较小的子节点 
if (ci < CurrentSize  
&& heap[ci] > heap[ci+1])  
ci++; 

// 能把y放入heap[i]吗? 
if (y <= heap[ci])  
break; // 能 

// 不能 
heap[i] = heap[ci]; // 子节点上移 
i = ci; // 下移一层 
ci *= 2; 


heap[i] = y; 

return *this; 


template<class T> 
void MinHeap<T>::Initialize(T a[], int size, int ArraySize) 
{ //size为数组a的元素的个数,ArraySize为数组从a[1]算起的元素个数
delete [] heap; 
heap=new T[size+1];
for(int i=1;i<=size;i++)
heap[i]=a[i];
CurrentSize = size; 
MaxSize = ArraySize; 

// 产生一个最小堆 
for (int i = CurrentSize/2; i >= 1; i--)  

T y = heap[i]; // 子树的根 

// 寻找放置y的位置 
int c = 2*i; // c 的父节点是y的目标位置 

while (c <= CurrentSize)  

// 使heap[c]是较小的子节点 
if (c < CurrentSize && 
heap[c] > heap[c+1]) c++; 

// 能把y放入heap[c/2]吗? 
if (y <= heap[c]) break; // 能 
// 不能 
heap[c/2] = heap[c]; // 子节点上移 
c *= 2; // 下移一层 

heap[c/2] = y; 



template<class T> 
void MinHeap<T>::Output() const 

cout << "The " << CurrentSize 
<< " elements are"<< endl; 
for (int i = 1; i <= CurrentSize; i++) 
cout << heap[i] << " "; 
cout << endl; 
}  
//主函数,用来测试的
#include "stdafx.h"
#include"Huffman.h"
#include"BinaryTree.h"
int _tmain(int argc, _TCHAR* argv[])
{
int a[4]={4,3,2,1};
MinHeap<int>b(1);
BinaryTree<int>temp1,temp2;
temp1=HuffmanTree(a,4);
temp2.PreOrder(temp1);
return 0;
}


所有的类实现均写在类定义中。在建立霍夫曼树的时候,存在一个最小堆的初始化,但是在初始化中 ,由于T为Huffman类型,因而存在一个<符号的重载,但是当我在最小堆中添加一个友元函数:friend bool operator<(Huffman<T>&x1,Huffman<T>&x2),然后写出函数的实现,这里存在一个问题,就是里面的T还是不可知,也就是weight的类型不已知,相当于重载了半天,还是不知道如何比较,但是如果我把这个函数定义中的T改成int之后,编译器编译不过。求高手指点,这个重载函数到底该如何去写,写在那个类中。

作者: chuand_dao   发布时间: 2011-12-26

这个估计没几个人答得出来

作者: lantingyaoyi   发布时间: 2011-12-26

我看看有没有人能够回答出来啊

作者: lantingyaoyi   发布时间: 2011-12-26

就这样写没错,在使用
weitemplate<class T> bool operator<(Huffman<T>&x1,Huffman<T>&x2)
这个函数之前,将 weight 的数据类型T的 < 操作符实现就行了

作者: seucs   发布时间: 2011-12-26

请问这个具体的实现怎么去写,怎么定义啊,我现在都快被这个问题崩溃了,就因为这个问题,整个程序都停滞不前,拜托帮帮忙啊!
引用 3 楼 seucs 的回复:
就这样写没错,在使用
weitemplate<class T> bool operator<(Huffman<T>&amp;x1,Huffman<T>&amp;x2)
这个函数之前,将 weight 的数据类型T的 < 操作符实现就行了

作者: chuand_dao   发布时间: 2011-12-26

热门下载

更多