哈夫曼编码译码器源代码和报告

#include  
#include  
#include 
#include 
 
typedef int TElemType; 
using namespace std;
typedef struct 
{ 
	int weight; 
    int parentlchildrchild; 
}HTNode* HuffmanTree; 

typedef char **HuffmanCode;//定义Huffman编码表 

//-----------全局变量----------------------- 
HuffmanTree HT; 
HuffmanCode HC; 
int w[50]ijn; 
char z[50];  //字符数组 
int flag=0; 
int numb=0; 
//-----------------select函数---------------------------
void select（HuffmanTree tint iint &s1int &s2） 
{ // t[1..i]中权值最小的俩结点的序号为s1，s2 
      int j=1max=1000;
	  for（j=1;j<=i;j++）//寻找parent为0的节点，并将器parent赋为1
	  {
		  if（t[j].parent==0&&t[j].weight		  {
			  s1=j;
			  max=t[j].weight;
		  }
	  } 
	  t[s1].parent=1;
	  max=1000;
	  for（j=1;j<=i;j++）
	  {
		  if（t[j].parent==0&&t[j].weight          {
			  s2=j;
              max=t[j].weight;
		  }
	  }
}
// --------------算法6.12-------------------------- 
void HuffmanCoding（HuffmanTree &HTHuffmanCode &HCint *wint n） 
{ // w存放n个字符的权值（均>0）构造赫夫曼树HT并求出n个字符的赫夫曼编码HC 
	int mis1s2start; int cf; 
    HuffmanTree p;  char *cd;

    if（n<=1）  return;//检测结点数是否可以构成树 
    m=2*n-1; 
    HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））; // 0号单元未用 
    for（p=HT+1i=1;i<=n;++i++p++w） //HT[1..n]结点有权值
    { 
		p->weight=*w;  p->parent=0; 
		p->lchild=0;   p->rchild=0; 
	} 
    for（;i<=m;++i++p） //HT[n+1...m]结点权值为0
	{ 
		p->weight=0;  p->parent=0; 
		p->lchild=0;   p->rchild=0; 
	} 
	for（i=n+1;i<=m;++i） // 建赫夫曼树 
	{ // 在HT[1~i-1]中选择parent为0且weight最小的两个结点其序号分别为s1和s2 
		select（HTi-1s1s2）; 
        HT[s1].parent=HT[s2].parent=i; 
        HT[i].lchild=s1; 
        HT[i].rchild=s2; 
        HT[i].weight=HT[s1].weight+HT[s2].weight; 
    } 
    // -------------从叶子到根逆向求每个字符的赫夫曼编码 --------------
    HC=（HuffmanCode）malloc（（n+1）*sizeof（char*））; // 分配n个字符编码的头指针向量（[0]不用） 
    cd=（char*）malloc（n*sizeof（char））; // 分配求编码的工作空间 
    cd[n-1]=‘e‘; // 编码结束符 
    for（i=1;i<=n;i++） 
    { // 逐个字符求赫夫曼编码 
		start=n;//-1; // 编码结束符位置 
		for（c=if=HT[i].parent;f!=0;c=ff=HT[f].parent） 
		{	// 从叶子到根逆向求编码 
			if（HT[f].lchild==c） 
				cd[--start]=‘0‘; 
			else 
				cd[--start]=‘1‘; 
		}
     HC[i]=（char*）malloc（（n-start）*sizeof（char））; // 为第i个字符编码分配空间 
     strcpy（HC[i]&cd[start]）; // 从cd复制编码（串）到HC 
     } 
     free（cd）; // 释放工作空间 
} 
//--------------初始化赫夫曼链表--------------------------------- 
void Initialization（） 
{ 
	char s[10];
	cout<<“请输入字符集字符个数“;
	cin>>n;
	cout<<“请输入字符集及其权值:“;
	cin.getline（s1）;
	cin.getline（z30）;
	for（i=0;i	{
	   cin>>*（w+i）;	   
	}
    HuffmanCoding（HTHCwn）;
	
    //------------------------打印编码------------------------------------------- 
    cout<<“字符对应的编码为:“<    for（i=1;i<=n;i++） 
    { 
        cout<<*（z+i-1）<<‘ ‘; 
		puts（HC[i]）; //把p指向的字符串输出到终端 
    } 
    //--------------------------将赫夫曼编码写入文件------------------------ 
    cout<<“下面将赫夫曼编码写入文件“<