#include<iostream.h>
#include<stdio.h>
const int DefaultSize=30;
class code
{
public:
char keymark;//编码字符
int key;//权值
};
class element
{
friend class binTree;
public:
element():leftchild(NULL),rightchild(NULL),parent(NULL),mark(0){};
code data;// 保存本结点的使用频度和其它数据。
int mark;
element *leftchild,*rightchild,*parent;
};
class binTree//单个元素的二叉树数
{
public:
binTree(){ root=new element;}
binTree(binTree &bt1,binTree &bt2)//
{
root=new element;
root->leftchild =bt1.root;
root->rightchild=bt2.root;
root->data.key=bt1.root->data.key+bt2.root->data.key;
bt1.root->parent=bt2.root->parent=root; /**/
}
element *root;
};
class minHeap//最小堆的类声明，也即是排序二叉树（最小为根）
{
public:
minHeap(){heap=NULL;};
minHeap(int maxsize);
void makeMinHeap(binTree a[],int n);
~minHeap(){ delete[] heap;}
int insert(binTree x);//插入堆中
int removeMin(binTree &x);//删除堆顶的最小元素
int isEmpty(){ return currentsize==0;};//判断是否为空
int isFull(){return currentsize==maxheapsize;};//判断是否已满
//void makeEmpty();//清空堆
private:
binTree *heap;//存放堆中元素的数组
int currentsize;//单前元素的个数
int maxheapsize;//堆中元素的最大个数
void filterDown(int start,int end);//从i到m自顶向下进行调整为最小堆
void filterUp(int end);//从i到0自底向上进行调整为最小堆
};
minHeap::minHeap (int maxsize)//构造函数
{
maxheapsize=maxsize;
heap=new binTree[maxheapsize];
currentsize=0;
}
void minHeap::makeMinHeap (binTree arr[],int n)
{
maxheapsize=n;
heap =new binTree[maxheapsize];
for(int i=0;i<n;i++)
{
heap[i].root=arr[i].root;
}
currentsize=n;
int currentPos =(currentsize-1)/2;//找最初调整位置：最后的分支结点
while (currentPos>=0)
{
filterDown(currentPos,currentsize-1); //向下调整成最小堆
currentPos--;//再向前换一个分支结点
}
}
void minHeap::filterDown(int start,int end)//指定开始、结尾，向下调整成最小堆
{
int i=start;
int j=2*i+1;//左子女标号，i+1为有子女标号
binTree temp=heap[i];
while (j<=end)
{
if (j<end&&heap[j].root->data.key>heap[j+1].root->data.key) j++;//一次比较，让j指向两子女中的最小者
if (temp.root->data.key<heap[j].root->data.key) break; //二次比较
else
{
heap[i]=heap[j];
i =j;
j = 2*i+1;//并不马上将temp放入下层
} // while end
heap[i]=temp;
}
};
void minHeap::filterUp(int start)//指定开始向上调整成最小堆
{
int j=start;
int i=(j-1)/2;
binTree temp=heap[j];
while(j>0)
{
if(heap[i].root->data.key<=temp.root->data.key) break;
else
{
heap[j]=heap[i];
j=i;
i=(i-1)/2;
}
heap[j]=temp;
}
}
int minHeap::insert(binTree x)//插入一棵二叉树
{
if(currentsize==maxheapsize)
{
cout<<"heap is full!"<<endl;
return 0;
}
heap[currentsize]=x;
filterUp(currentsize);//插入后，要调整
currentsize++;
return 1;
}
int minHeap::removeMin(binTree &x)//删除最小元素
{
if(!currentsize)
{
cout<<"Heap is empty!"<<endl;
return 0;
}
x=heap[0];
heap[0]=heap[currentsize-1];//把最后的放到最前面来
currentsize--;
filterDown(0,currentsize-1);//然后调整
}
binTree * HuffmanTree ( code *fr,int n)//构造huffman树
{
binTree *newtree=NULL;
binTree first, second;
minHeap hp;
if(n>DefaultSize)
{
cerr<<"Size n"<<n<<"exceed the Boundary of Array"<<endl;
return NULL;
}
binTree Node[DefaultSize];
for(int i=0;i<n;i++)
{
Node[i].root->data=fr[i];
Node[i].root->leftchild=Node[i].root->rightchild=NULL;
}
hp.makeMinHeap(Node,n);// 建立具有 n 个结点最小化堆。数组名为Node。
for (i=0; i<n-1; i++ )
{
hp.removeMin(first); //从森林中找出根结点最小的两棵数
hp.removeMin(second);//合并成一棵新树，然后把两棵树从森林中去掉
newtree=new binTree(first,second);
hp.insert (*newtree); //把新树插入森林中
}return newtree;
}
#include<iostream.h>
#include"huffman.h"
class huffcode//存放字符及相应的编码
{
public:
char keyc;
char hufc[30];
};
huffcode * coding(binTree *tree,int L)//编码程序
{
huffcode *hc=new huffcode[L];
element *current=tree->root;
element *currentFront=current;//currentFront用于指向当前结点的父母
int j=0;
for(int i=0;i<L;i++)
{
j=0;
currentFront=current=tree->root;
while(1)
{
if(current->leftchild->mark==0)//mark等于0说明当前结点的左子树的叶子还没有扫描完，继续扫描
{
//cout<<"current->data.key="<<current->data.key<<endl;
hc[i].hufc[j]='0';//记下路径，往左为0，往右为1
j++;
if(current->leftchild->leftchild==NULL)
{
hc[i].hufc[j]='/0';
hc[i].keyc=current->leftchild->data.keymark;
current->leftchild->mark=1;
break;
}
currentFront=current;
current=current->leftchild;
}
if(current->leftchild->mark==1)//mark等于0说明当前结点的左子树的叶子已经扫描完，扫描右子树
{
//cout<<"current->data.key="<<current->data.key<<endl;
hc[i].hufc[j]='1';//记下路径，往左为0，往右为1
j++;
if(current->rightchild->leftchild==NULL)
{
hc[i].hufc[j]='/0';
hc[i].keyc=current->rightchild->data.keymark;
current->rightchild->mark=1;
current->mark=1;
while((currentFront->leftchild->mark==1)&&(currentFront->rightchild->mark==1))//扫描完当前结点的右子树，需要往上标记mark
{
currentFront->mark=1;
if(currentFront==tree->root) break;
if(currentFront->parent->parent!=NULL)
{
//cout<<currentFront->data.key<<endl;
currentFront=currentFront->parent;
}
else
break;
}/**/
break;
}
currentFront=current;//指向当前结点的父母
current=current->rightchild;
}
}
}
return hc;
}
void decode(binTree *tree,char c[])//解码程序
{
element *current=tree->root;
for(int i=0;i<strlen(c);i++)
{
if(c[i]=='0') current=current->leftchild;//如果是0，指向左子女
else
{
if(c[i]=='1') current=current->rightchild;//如果是1，指向左子女
else
cout<<"你输入的报文有误!报文必须由二进制位组成!";//不能出现0，1以外的字符，否则警告
}
if(current->leftchild==NULL)//到达叶子，则译出一个字符
{
cout<<current->data.keymark;
current=tree->root;
}
}
}
#include<string.h>
#include"coding_decode.h"
const charSize=1000;
void main()
{
char c[30];
cout<<"请输入编码报文中可能出现的字符，以对其生成编码(出现频率最高的在前面)"<<endl;
//cout<<"请输入编码报文中可能出现的字符以及该字符出现频率权值，以对其生成编码"<<endl;
gets(c);
int L=strlen(c);
code *cipher=new code[L];
for(int i=0;i<L;i++)
{
cipher[i].key=L-i-1;
cipher[i].keymark=c[i];
}
binTree *NewTree=HuffmanTree(cipher,L);
huffcode *hf=coding(NewTree,L);
cout<<"编码字符"<<'/t'<<"对应编码"<<endl;
for(i=0;i<L;i++)
{
cout<<" "<<hf[i].keyc<<'/t'<<'/t'<<hf[i].hufc<<endl;
}
int r;
cout<<endl<<"对报文Huffman编码,请输入'1'"<<endl
<<"对报文Huffman解码,输入'2'"<<endl<<"退出,输入'0':";
cin>>r;
while(r)
{
if(r==1)
{
cout<<"请输入要编码的报文内容："<<endl;
char ch[charSize];
gets(ch);
int mark=0;
cout<<"该报文的编码是:";
for(i=0;i<strlen(ch);i++)
{
for(int j=0;j<L;j++)
{
if(ch[i]==hf[j].keyc)
{
cout<<hf[j].hufc;
mark=1;
}
}
if(mark==0) cout<<"你输入的报文内容中有非编码的字符!";
}
}
if(r==2)
{
cout<<"请输入要解码的报文："<<endl;
char chr[charSize];
gets(chr);
cout<<"该报文经解码后是:";
decode(NewTree,chr);
}
cout<<endl<<"对报文进行Huffman编码,请输入'1'"<<endl
<<"对报文进行Huffman解码,输入'2'"<<endl<<"退出,输入'0':";
cin>>r;
}
}