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之后,编译器编译不过。求高手指点,这个重载函数到底该如何去写,写在那个类中。
#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的 < 操作符实现就行了
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>&x1,Huffman<T>&x2)
这个函数之前,将 weight 的数据类型T的 < 操作符实现就行了
就这样写没错,在使用
weitemplate<class T> bool operator<(Huffman<T>&x1,Huffman<T>&x2)
这个函数之前,将 weight 的数据类型T的 < 操作符实现就行了
作者: chuand_dao 发布时间: 2011-12-26
相关阅读 更多
热门阅读
-
office 2019专业增强版最新2021版激活秘钥/序列号/激活码推荐 附激活工具
阅读:74
-
如何安装mysql8.0
阅读:31
-
Word快速设置标题样式步骤详解
阅读:28
-
20+道必知必会的Vue面试题(附答案解析)
阅读:37
-
HTML如何制作表单
阅读:22
-
百词斩可以改天数吗?当然可以,4个步骤轻松修改天数!
阅读:31
-
ET文件格式和XLS格式文件之间如何转化?
阅读:24
-
react和vue的区别及优缺点是什么
阅读:121
-
支付宝人脸识别如何关闭?
阅读:21
-
腾讯微云怎么修改照片或视频备份路径?
阅读:28