heffman

out< "please input the number of the nodes"<<endl cin>>nodesNum cout<<"pl

//------赫夫曼算法.h-----
//------赫夫曼算法的存储表示-----------
#include<iostream.h>
#include<malloc.h>
#include<stdlib.h>
#include"SqStack.h"
typedef struct{
	short weight;
	short parent ,lchild,rchild;
}HTNode,*HuffmanTree;           //动态分配数组存储赫夫曼树

//-------求赫夫曼编码的算法-----------
void HuffmanCoding(HuffmanTree &HT,int *w,int n){
	//w存放n个字符的权值（均大于0），构造赫夫曼树HT，并求出n个字符的赫夫曼编码表HC
	void Select(HuffmanTree HT,short n,short &s1,short &s2);
	if(n<=1) return;
	short m=2*n-1;        //有n个叶子结点的赫夫曼树共有2*n-1个结点
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用
    HuffmanTree p=&HT[1];
	for(int i=1;i<=n;++i,++p,++w) {
		p->weight=*w;p->parent=0;p->rchild=0;p->lchild=0;
	}
	for(i=n+1;i<=m;++i,++p){
        p->weight=0;p->parent=0;p->rchild=0;p->lchild=0;
	}
    //以上两个循环是初始化

	short s1;short s2;
	for(i=n+1;i<=m;i++){   //建赫夫曼树
		Select(HT,i-1,s1,s2);//从HT[1----i-1]中选择weight最小的两个结点，其序号分别为s1和s2
        HT[s1].parent=i;HT[s2].parent=i;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
		HT[i].lchild=s1;HT[i].rchild=s2;
	}

	//-----从叶子到根逆序求每个字符的赫夫曼编码-----
	
	SqStack CodeStack;
	InitStack(CodeStack);
	short e;
	for(i=1;i<=n;i++){
    	CodeStack.top=CodeStack.base;      //清空栈
		cout<<endl;
		cout<<"权值为 "<<HT[i].weight<<" 的结点的huffman编码为：";
		HTNode t=HT[i];
		for(short c=i;t.parent!=0;c=t.parent,t=HT[c]){
			if(HT[t.parent].lchild==c) Push(CodeStack,0);//如果是左孩子，编码为0
			 else Push(CodeStack,1);
		}
		while(!StackEmpty(CodeStack)){
			Pop(CodeStack,e);//将栈顶用e返回，并退栈 
			cout<<" "<<e;
		}//while
	}//for
}//HuffmanCoding

//--子函数Select,从HT[1----n]中选择weight最小的两个结点，其序号分别为s1和s2--
void Select(HuffmanTree HT,short n,short &s1,short &s2){
	//不妨使HT[s1].weight<=HT[s2].weight
	//s1和s2的初始化
	HT[0].weight=32767;s1=s2=0;//初始化
	for(short i=1;i<=n;i++){
		if(HT[i].parent==0){
			if(HT[i].weight<HT[s2].weight){
				if(HT[i].weight<HT[s1].weight){
					s2=s1;s1=i;
				}
			    else
				    s2=i;
			}
		}
	}//for
}