qhfmtree.cpp

哈夫曼树结构运算

//#include<conio.h>
//#include<string.h>
//#include<stdio.h>//
//#include<stdlib.h>
#include<fstream.h>

#define N 26
#define maxsize 200
#define maxval 100

struct HFMTreenode
{ 
	float weight;
    int  parent,lchild,rchild;
    char ch;
};
struct  HFMcode
{ 
	char bits[N];
    int  start;
    char ch;
};
class HFMTree
{
    private:
		HFMTreenode *tree;
		HFMcode *code;
	public:
		HFMTree();
		~HFMTree();
		bool CreatHFMTree(LPCTSTR fn);/*读词频盘,生成HFMTree*/
		void CreatHFMCode();/*生成HFMCode*/
		void PrintHFMTree(CString &m_strout);/*打印HFMTree的字符编码表*/
		void String_Code(LPCTSTR strin,CString &strout);/*读入字符串,转化为编码*/
		int  Code_String(LPCTSTR strin,CString &strout);/*读入编码,转化为字符串*/

};
/////////////////////////////////////////////////////////////////////////////
HFMTree::HFMTree()
{
    tree=NULL;
	code=NULL;
}
/////////////////////////////////////////////////////////////////////////////
HFMTree::~HFMTree()
{
	if(tree!=NULL)
        delete []tree;
	if(code!=NULL)
        delete []code;
}
/////////////////////////////////////////////////////////////////////////////
bool HFMTree::CreatHFMTree(LPCTSTR fn)//读词频盘,生成HFMTree
{
	if(tree!=NULL)
        delete []tree;
	if(code!=NULL)
        delete []code;
    ifstream fin;
    fin.open(fn);
    if(!fin)  
	{ 
		return false; 
	}
	int n;
	fin>>n;
	if(n<=0)
		return false;
    tree=new HFMTreenode[2*n];
    code=new HFMcode[n+1];
    int i,j,p1,p2;
    float min1,min2;
    for (i=0;i<2*n;i++)//初始化HFMTree
    { 
		tree[i].parent=0;
		tree[i].lchild=0;
		tree[i].rchild=0;
		tree[i].weight=0; 
	}
    tree[0].lchild=tree[0].rchild=n;
    for(i=1;i<=n;i++) //读入n个字符及权值
    {
		fin>>tree[i].ch>>tree[i].weight;
    }
    fin.close();
    for(i=n+1;i<2*n;i++)
    {
		p1=p2=0;
		min1=min2=maxval;
		for (j=1;j<i;j++)
			if (tree[j].parent==0)
		if (tree[j].weight<min1)
		{
		    min2=min1;
		    min1=tree[j].weight;
		    p2=p1;
		    p1=j;
		}
		else
		{
		    if (tree[j].weight<min2)
		    {
				min2=tree[j].weight;
				p2=j;
		    }
		}
		tree[p1].parent=tree[p2].parent=i;
		tree[i].lchild=p1;
		tree[i].rchild=p2;
		tree[i].weight=tree[p1].weight+tree[p2].weight;
    }
    return true;
}
/////////////////////////////////////////////////////////////////////////////
void HFMTree::CreatHFMCode()//生成HFMCode
{
   	if((tree==NULL)||(code==NULL))
        return;
    int i,p,c,n;
    HFMcode cd;
    n=tree[0].lchild;
    for (i=1;i<=n;i++)
    {
		cd.start=n;
		cd.ch=tree[i].ch;
		c=i;
		p=tree[i].parent;
		while (p!=0)
		{
			cd.start--;
			if (tree[p].lchild==c)    cd.bits[cd.start]='0';
			if (tree[p].rchild==c)    cd.bits[cd.start]='1';
			c=p;
			p=tree[p].parent;
		}
		code[i]=cd;
    }
    return;
}
/////////////////////////////////////////////////////////////////////////////
void HFMTree::PrintHFMTree(CString &m_strout)//打印HFMTree的字符编码表
{
   	if((tree==NULL)||(code==NULL))
        return;
    int i,j,n;
    n=tree[0].lchild;
	CString str;
    m_strout="Huffman树的字符编码表\r\n";
    m_strout+="┏━━┳━━┯━━┳━━┯━━┯━━┳━━━━━━━━┓\r\n";
    m_strout+="┃序号┃字符│权重┃双亲│左孩│右孩┃      编码      ┃\r\n";
    m_strout+="┣━━╋━━┿━━╋━━┿━━┿━━╋━━━━━━━━┫\r\n";
//    str.Format("┃  0 ┃    │树头┃    │ %2d │ %2d ┃                ┃\r\n",n,n);
//	m_strout+=str;
//    m_strout+="┣━━╋━━┿━━╋━━┿━━┿━━╋━━━━━━━━┫\r\n";
    for (i=1;i<=n;i++)
    {
		str.Format("┃ %2d ┃  %c │%4.2f┃ %2d │    │    ┃",
			        i,tree[i].ch,tree[i].weight,tree[i].parent);
    	m_strout+=str;
		for(j=code[i].start;j<n;j++)
		{
			str.Format("%c",code[i].bits[j]);
        	m_strout+=str;
		}
		for (;j<16+code[i].start;j++)
			m_strout+=" ";
		m_strout+="┃\r\n";
    }
    m_strout+="┣━━╋━━┿━━╋━━┿━━┿━━╋━━━━━━━━┛\r\n";
    for(i=n+1;i<2*n;i++)
    {
		str.Format("┃ %2d ┃    │%4.2f┃ %2d │ %2d │ %2d ┃\n",
		            i,tree[i].weight,tree[i].parent,tree[i].lchild,tree[i].rchild);
       	m_strout+=str;
		m_strout+="\r\n";
    }
    m_strout+="┗━━┻━━┷━━┻━━┷━━┷━━┛\r\n";
    return;
}
/////////////////////////////////////////////////////////////////////////////
void HFMTree::String_Code(LPCTSTR strin,CString &strout)//读入字符串,转化为编码
{
   	if((tree==NULL)||(code==NULL))
        return;
    int ci=0,i,j,n,k=0,cols=1;
    n=tree[0].lchild;
	char c;
	CString str;
    c=tolower(strin[ci++]);//tolower
	strout="";
    while(c!=NULL&&k<=maxsize)
    {
		k++;
		if(c>='a'&&c<='z')
		{
			for(i=1;i<=n;i++)
			{
				if(code[i].ch==c)
				{
					for(j=code[i].start;j<n;j++)
					{
						str.Format("%c",code[i].bits[j]);
						strout+=str;
						if(cols<40)
							cols++;
						else
						{
							cols=1;
							strout+="\r\n";
						}
					}
					break;
				}
			}
		}
		else
		{
            c=tolower(strin[ci++]);//tolower
			continue;
		}
        c=tolower(strin[ci++]);//tolower
	}
    return;
}
/////////////////////////////////////////////////////////////////////////////
int HFMTree::Code_String(LPCTSTR strin,CString &strout)//读入编码,转化为字符串
{
   	if((tree==NULL)||(code==NULL))
        return 0;
    int ci=0,i,n,cols=1;;
    char ch;
    n=tree[0].lchild;
	CString str;
	strout="";
    i=2*n-1;
    ch=strin[ci++];
    while(ch!=NULL)
    {
		if(ch=='0')
			i=tree[i].lchild;
		else if(ch=='1')
			i=tree[i].rchild;
		else
		{
            ch=strin[ci++];
			continue;
		}
		if(tree[i].lchild==0)
		{
			str.Format("%c",tree[i].ch);
    		strout+=str;
			if(cols<40)
				cols++;
			else
			{
				cols=1;
				strout+="\r\n";
			}
			i=2*n-1;
		}
        ch=strin[ci++];
    }
    if(tree[i].lchild!=0&&i!=2*n-1)
		strout+="(************________-_______)******";
    return 1;
}
/////////////////////////////////////////////////////////////////////////////