Su栏杆插件:C++编程题

/////////////////MinHeap.h

#include <iostream.h>

template<class T>
class MinHeap
{
public:
MinHeap(int maxheapsize = 10);
~MinHeap(){delete []heap;}
int Size() const{return currentsize;}
T Max(){if(currentsize) return heap[1];}
MinHeap<T>& Insert(const T& x);
MinHeap<T>& DeleteMin(T &x);
void Initialize(T x[], int size, int ArraySize);
void Deactivate();
void output(T a[],int n);/////////////////////
private:
int currentsize, maxsize;
T *heap;
};

template <class T>
void MinHeap<T>::output(T a[],int n)
{
for(int i = 1; i <= n; i++)
cout << a[i] << " ";
cout << endl;
}

template <class T>
MinHeap<T>::MinHeap(int maxheapsize)
{
maxsize = maxheapsize;
heap = new T[maxsize + 1];
currentsize = 0;
}

template<class T>
MinHeap<T>& MinHeap<T>::Insert(const T& x)
{
if(currentsize == maxsize)
{
return *this;
}
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)
{
cout<<"Empty heap!"<<endl;
return *this;
}

x = heap[1];

T y = heap[currentsize--];
int i = 1,
ci = 2;
while(ci <= currentsize)
{
if(ci < currentsize && heap[ci] > heap[ci + 1])
{
ci++;
}
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 x[], int size, int ArraySize)
{
delete []heap;
heap = x;
currentsize = size;
maxsize = ArraySize;

for(int i = currentsize / 2; i >= 1; i--)
{
T y = heap[i];
int c = 2 * i;
while(c <= currentsize)
{
if(c < currentsize && heap[c] > heap[c + 1])
c++;
if(y <= heap[c])
break;
heap[c / 2] = heap[c];
c *= 2;
}
heap[c / 2] = y;
}
}

template<class T>
void MinHeap<T>::Deactivate()
{
heap = 0;
}
/////////////////////////huffmantree.h
#include "binarytree.h"
#include "MinHeap.h"

#define len 10

template<class T>
class Huffman
{
friend BinaryTree<int> HuffmanTree(T [], int);
public:
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(a[i], zero, zero);
w[i].weight = a[i];
w[i].tree = z;
}

MinHeap< Huffman<T> > H(1);
H.Initialize(w,n,n);

Huffman<T> x, y;
for (i = 1; i < n; i++)
{
H.DeleteMin(x); H.DeleteMin(y);
z.MakeTree(x+y, x.tree, y.tree);
x.weight += y.weight; x.tree = z;
H.Insert(x);
}
H.DeleteMin(x);
H.Deactivate();
delete [] w;
return x.tree;
}

void HuffmanEncode(BinaryTree<int> &t, int n)
{
int code[len];
int i = 0,k = 0;
BinaryTreeNode<int> *node = t.root;

code[i++] = 0;
while(k < n)
{
if(node->LeftChild && !node->LeftChild->visited)
{
node->LeftChild->visited = true;
code[i++] = 0;
node = node->LeftChild;
}
else if(node->RightChild && !node->RightChild->visited)
{
node->RightChild->visited = true;
code[i++] = 1;
node = node->RightChild;
}
else if(!(node->LeftChild || node->RightChild))
{
cout<<node->data<<"\t:";
for(int j = 1; j < i; j++)
cout<<code[j]<<" ";
cout<<endl;

k++;
node = node->Parent;
if(i < 1)
break;
i-=1;
}
else
{
node = node->Parent;
if(i < 1)
break;
i-=1;
}
}
}
///////////////////binarytree.h
template <class T> class BinaryTree;

template <class T>
class BinaryTreeNode
{
friend void Visit( BinaryTreeNode<T> *);
friend void InOrder( BinaryTreeNode<T> *);
friend void PreOrder( BinaryTreeNode<T> *);
friend void PostOrder( BinaryTreeNode<T> *);
friend void LevelOrder( BinaryTreeNode<T> *);
friend void main(void);
friend class BinaryTree<T>;
friend BinaryTree<int> HuffmanTree(T a[], int n);
friend void HuffmanEncode(BinaryTree<int> &t, int n);

public:
BinaryTreeNode() { LeftChild = RightChild = 0; visited = false;
Parent = 0;}
BinaryTreeNode( const T& e){ data = e; LeftChild = RightChild = 0;
Parent = 0; visited = false;}
BinaryTreeNode( const T& e, BinaryTreeNode *l, BinaryTreeNode
*r)
{data = e; LeftChild = l; RightChild = r;
if(l) l->Parent = this; if(r) r->Parent = this; visited =
false;}
private:
T data;
BinaryTreeNode<T> *Parent,//parent/////////////////////////////
*LeftChild, // left subtree
*RightChild; // right subtree
bool
visited;///////////////////////////////////////////////////////
};

template<class T>
class BinaryTree
{
friend BinaryTree<int> HuffmanTree(T a[], int n);
friend void HuffmanEncode(BinaryTree<int> &t, int n);

public:
BinaryTree() {root = 0;};
~BinaryTree(){};
bool IsEmpty() const
{ return ( (root) ? false : true ); }
bool Root(T& x) const;
void MakeTree( const T& element, BinaryTree<T>& left,
BinaryTree<T>& right );
void BreakTree(T& element, BinaryTree<T>& left,
BinaryTree<T>& right );
void PreOrder( void(*Visit) (BinaryTreeNode<T> *u) )
{PreOrder(Visit, root);}
void InOrder(void(*Visit)(BinaryTreeNode<T> *u))
{InOrder(Visit, root);}
void PostOrder(void(*Visit)(BinaryTreeNode<T> *u))
{PostOrder(Visit, root);}
void PreOutput() {PreOrder(Output, root); cout << endl;}
void InOutput() {InOrder(Output, root); cout << endl;}
void PostOutput() {PostOrder(Output, root); cout << endl;}
void Delete() {PostOrder(Free, root); root = 0;}

private:
BinaryTreeNode<T> *root;
void PreOrder(void(*Visit)(BinaryTreeNode<T> *u),
BinaryTreeNode<T> *t);
void InOrder(void(*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T>
*t);
void PostOrder(void(*Visit)(BinaryTreeNode<T> *u),
BinaryTreeNode<T> *t);
static void Free(BinaryTreeNode<T> *t) { delete t; }
static void Output(BinaryTreeNode<T> *t)
{ cout << t->data << " "; }
};

template<class T>
bool BinaryTree<T>::Root(T& x) const
{
if (root) {x = root->data;
return true;}
else
return false;
}

template<class T>
void BinaryTree<T>::MakeTree(const T& element,

BinaryTree<T>& left, BinaryTree<T>& right)
{
root = new BinaryTreeNode<T> (element, left.root, right.root);
left.root = right.root = 0;
}

template<class T>
void BinaryTree<T>::BreakTree(T& element,BinaryTree<T>& left, BinaryTree<T>&
right)
{
if (!root) throw BadInput();

element = root->data;
left.root = root->LeftChild;
right.root = root->RightChild;
delete root;
root = 0;
}

template<class T>
void BinaryTree<T>::PreOrder( void(*Visit)(BinaryTreeNode<T>
*u),BinaryTreeNode<T> *t)
{
if (t)
{
Visit(t);
PreOrder(Visit, t->LeftChild);
PreOrder(Visit, t->RightChild);
}
}

template<class T>
void BinaryTree<T>::InOrder( void(*Visit)(BinaryTreeNode<T>
*u),BinaryTreeNode<T> *t)
{
if (t)
{
InOrder(Visit, t->LeftChild);
Visit(t);
InOrder(Visit, t->RightChild);
}
}

template<class T>
void BinaryTree<T>::PostOrder( void(*Visit)(BinaryTreeNode<T>
*u),BinaryTreeNode<T> *t)
{
if (t)
{
PostOrder(Visit, t->LeftChild);
PostOrder(Visit, t->RightChild);
Visit(t);
}
}
///////////////.cpp
#include <iostream.h>
#include <stdio.h>
#include "huffmantree.h"

void main()
{
int weight, i = 1, num,*a;
cout<<"num:"<<endl;
cin >> num;
a = new int[num+1];
a[0] = 0;
cout<<"array"<<endl;
while(i <= num && cin >> weight)
{
if(weight == 0) break;
a[i++] = weight;
}

cout<<endl;
BinaryTree<int> huffman ;
huffman = HuffmanTree(a, i - 1);
HuffmanEncode(huffman, i - 1);
huffman.PreOutput();
}