本文共 2271 字，大约阅读时间需要 7 分钟。

Huffman

#include 
   
    #include 
    
     #include 
     
      #include
      
       using namespace std;typedef struct{	char data;//存放字符 	int weight;//存放字符出现次数 	int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef char **HuffmanCode;void Select(HuffmanTree HT,int len,int &s1,int &s2){	int i,min1=0x3f3f3f3f,min2=0x3f3f3f3f;//先赋予最大值	for(i=1;i<=len;i++)	{		if(HT[i].weight
       
        0){	    	HT[i].data=char(j+97);//存储小写字母 	    	HT[i].weight=pl[j];	    	i++;		}	//	cin>>HT[i].weight;  	/*――――――――――初始化工作结束，下面开始创建赫夫曼树――――――――――*/ 	for(i=n+1;i<=m;++i) 	{  	//通过n-1次的选择、删除、合并来创建赫夫曼树		Select(HT,i-1,s1,s2);		//在HT[k](1≤k≤i-1)中选择两个其双亲域为0且权值最小的结点,		// 并返回它们在HT中的序号s1和s2		HT[s1].parent=i; 			HT[s2].parent=i;   		//得到新结点i，从森林中删除s1，s2，将s1和s2的双亲域由0改为i		HT[i].lchild=s1;   		HT[i].rchild=s2 ;							//s1,s2分别作为i的左右孩子		HT[i].weight=HT[s1].weight+HT[s2].weight; 	//i 的权值为左右孩子权值之和	}												//for}	void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n){	//从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表HC中	int i,start,c,f;	HC=new char*[n+1];         						//分配n个字符编码的头指针矢量	char *cd=new char[n];							//分配临时存放编码的动态数组空间	cd[n-1]='\0';                            		//编码结束符	for(i=1;i<=n;++i)	{                      							//逐个字符求赫夫曼编码		start=n-1;                          		//start开始时指向最后，即编码结束符位置		c=i; 		f=HT[i].parent;                 			//f指向结点c的双亲结点		while(f!=0)		{                          					//从叶子结点开始向上回溯，直到根结点			--start;                          		//回溯一次start向前指一个位置			if(HT[f].lchild==c)  				cd[start]='0';						//结点c是f的左孩子，则生成代码0			else 				cd[start]='1';                 		//结点c是f的右孩子，则生成代码1			c=f; 			f=HT[f].parent;             			//继续向上回溯		}                                  			//求出第i个字符的编码      		HC[i]=new char[n-start];         			// 为第i 个字符编码分配空间		strcpy(HC[i], &cd[start]);        			//将求得的编码从临时空间cd复制到HC的当前行中	}	cout<
        <
         
          ='A')&(ch<='Z')) pl[ch-65]++; else pl[ch-97]++; } fclose(in);}int main(){ HuffmanTree HT; HuffmanCode HC; //要求 SourceFile.txt中只出现字母（不允许有空格及其他字符） char f1[]={"SourceFile.txt"}; char f2[]={"Code.txt"}; char f3[]={"ResultFile.txt"}; int pl[26]={0}; TongJi(f1,pl); //统计出现次数不为0的数组元素个数 int n=0; for(int j=0;j<26;j++){ if(pl[j]>0) n++; } CreatHuffmanTree(HT,pl,n); CreatHuffmanCode(HT,HC,n); WriteCode(HT,HC,f2,n); WriteResult(HT,HC,f1,f3,n); return 0;}