哈夫曼树 C++算法

数据结构的哈夫曼树，能输入任意字符串，并计算出现频率，同时统计编码长度，可编码，可解码，能计算压缩比，可执行程序包括实验报告

#include
#include
#define max 100
char cha[max]string[max];
char Hcode[max-1][max];
struct huftree                                              //huffman节点存储结构
{
    int weight;
    int lchild;
	int rchild;
	int parent;
};
class Huff
{
public:
	void selectmin（huftree tree[]int k）;                   //权值最小的两个节点
    void huffman（huftree tree[]int *wint n）;              //生成huffman树
    void CreateTable（huftree tree[]char code[]int nint len[]int weight[]int length1）;     //生成哈夫曼编码
    void encode（int n）;                                     //将从键盘上接收的字符转变为哈夫曼编码
    void decode（char ch[]huftree tree[]int n）;            //将从键盘上接收的二进制码解码为字符
private:
	int min1;
	int min2;
};
void Huff::selectmin（huftree tree[]int k）                  //找出权值最小的两个节点
{
    int i;
    for （i=1;i<=k && tree[i].parent!=0 ;i++）; 
	min1=i;
    for （i=1;i<=k;i++）
        if （tree[i].parent==0 && tree[i].weight			min1=i;tree[i].weight=max;
    for （i=1;i<=k;i++）
        if （tree[i].parent==0 && i!=min1） 
			break; 
		min2=i;
    for （i=1;i<=k;i++）
        if （ tree[i].parent==0 && i!=min1 && tree[i].weight			min2=i;tree[i].weight=max;
}

void Huff::huffman（huftree tree[]int *wint n）              //生成huffman树
{  
	int mi;
    if （n<=1） return;
    m=2*n-1;
    for （i=1;i<=n;i++）
    { 
		tree[i].weight=w[i]; tree[i].parent=0;
        tree[i].lchild=0;    tree[i].rchild=0; 
	}
    for （i=n+1;i<=m;i++）
    { 
		tree[i].weight=0;   tree[i].parent=0;
        tree[i].lchild=0;   tree[i].rchild=0; 
	}
    for （i=n+1;i<=m;i++）
    {  
		selectmin（tree i-1）;
        tree[min1].parent=i;
        tree[min2].parent=i;
        tree[i].lchild=min1;
        tree[i].rchild=min2;     
        tree[i].weight =tree[min1]. weight+ tree[min2].weight;
     }
}
void Huff::CreateTable（huftree tree[]char code[]int nint len[]int weight[]int length1）   //生成哈夫曼编码
{
	int startcipm;
    code[n-1]=‘\0‘;
	float length2=0;
    cout<<“各字符的哈夫曼编码为:“<    for（i=1;i<=n;i++）
	{
	    m=0;
		start=n-1;
        for（c=ip=tree[i].parent;p!=0;c=pp=tree[p].parent）
		{
			if（tree[p].lchild==c）
				code[--start]=‘0‘;
            else 
				code[--start]=‘1‘;
			m++;
		}
        strcpy（Hcode[i]&code[start]）;
        cout<		len[i]=m;
	}		
	cout<    for（int j=0;j<=n;j++）
        length2+=len[j]*weight[j];
	length2=length2/8;
	cout<<“编码后字符串的大小为:“<	    <<“压缩比为：“<}

void Huff::encode（int n）                                  //将从键盘上接收的字符转变为哈夫曼编码
{
    cout<    for （int i=0;string[i]!=‘\0‘;i++）
    {
        for（int j=0;string[i]!=cha[j]&&j<=n;） j++;
        if （j<=n）  cout<    }
    cout<}

void Huff::decode（char ch[]huftree tree[]int n）         //将从键盘上接收的二进制码解码为字符
{
	int ijm;char b;
    m=2*n-1;
 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     233568  2010-12-23 23:50  ffffeeee\Debug\ffffeeee.exe

     文件     262088  2010-12-23 23:50  ffffeeee\Debug\ffffeeee.ilk

     文件     250324  2010-12-23 23:50  ffffeeee\Debug\ffffeeee.pch

     文件     443392  2010-12-23 23:50  ffffeeee\Debug\ffffeeee.pdb

     文件      18276  2010-12-23 23:50  ffffeeee\Debug\main.obj

     文件      41984  2010-12-27 20:41  ffffeeee\Debug\vc60.idb

     文件      61440  2010-12-23 23:50  ffffeeee\Debug\vc60.pdb

     文件       4304  2010-12-23 23:52  ffffeeee\ffffeeee.dsp

     文件        524  2010-12-23 23:49  ffffeeee\ffffeeee.dsw

     文件      41984  2010-12-27 20:42  ffffeeee\ffffeeee.ncb

     文件      53760  2010-12-27 20:42  ffffeeee\ffffeeee.opt

     文件        250  2010-12-27 20:41  ffffeeee\ffffeeee.plg

     文件       4694  2010-12-23 23:50  ffffeeee\main.cpp

     文件     162816  2010-12-23 19:07  ffffeeee\哈夫曼编（解）码器.doc

     目录          0  2010-12-23 23:50  ffffeeee\Debug

     目录          0  2010-12-27 20:42  ffffeeee

----------- ---------  ---------- -----  ----

              1579404                    16