《算法与数据结构》实验指导书(12)

《算法与数据结构》实验指导书

PrintHuffmanCode(HC,w,n); //显示哈夫曼编码 printf("哈夫曼树构造完毕，还要继续吗?(Y/N)"); scanf(" %c",&j); } }

void CreateHuffmanTree(HuffmanTree &HT,unsigned int *w,int n) {//w存放n个结点的权值，将构造一棵哈夫曼树HT int i,m; int s1,s2;

HuffmanTree p; if(n<=1) return;

m=2*n-1; //n个叶子结点的哈夫曼树，有2*n-1个结点

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //开辟2*n各结点空间，0号单元不用 for(p=HT+1,i=1;i<=n;++i,++p,++w) //进行初始化 {p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; }

for(;i<=m;++i,++p) {p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; }

for(i=n+1;i<=m;++i) //建哈夫曼树 {Select(HT,i-1,s1,s2);

//从HT[1...i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 HT[s1].parent=i; HT[s2].parent=i; //修改s1和s2结点的父指针parent HT[i].lchild=s1; HT[i].rchild=s2; //修改i结点的左右孩子指针 HT[i].weight=HT[s1].weight+HT[s2].weight; //修改权值 } }

void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n)

{//将有n个叶子结点的哈夫曼树HT进行编码， 所编的码存放在HC中 //方法是从叶子到根逆向求每个叶子结点的哈夫曼编码 int i,c,f,start; char *cd;

HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); //分配n个编码的头指针向量 cd=(char *)malloc(n*sizeof(char)); //开辟一个求编码的工作空间 cd[n-1]='\0'; //编码结束符

for(i=1;i<=n;++i) //逐个地求哈夫曼编码 {start=n-1; //编码结束位置