C++ 构造哈夫曼树（非常棒的哦）

#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> using namespace std ; typedef struct { unsigned int weight; //结点权值 unsigned int parent,lchild,rchild; //结点的父指针，左右孩子指针 }HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树 typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表 HuffmanTree HT; //哈夫曼树HT HuffmanCode HC; //哈夫曼编码表HC unsigned int *w; //w存放叶子结点权值 char * source_code ;//source_code 存放原始码 void CreateHuffmanTree(HuffmanTree &,unsigned int*,int ); //生成一棵哈夫曼树 void HuffmanCoding(HuffmanTree,HuffmanCode &,int ); //对哈夫曼树进行编码 void PrintHuffmanCode(HuffmanCode,unsigned int*,int); //显示哈夫曼编码 void Select(HuffmanTree,int,int&,int&); //在数组中寻找权值最小的两个结点 int main() { int n,i; //n是哈夫曼树叶子结点数 char choose='y'; //用于选择程序是否退出 //程序解说 printf("本程序将演示构造哈夫曼树.\n"); printf("首先输入叶子结点数目.\n例如:2\n"); printf("然后输入原始码以及权值.\n"); printf("第1个原始码及其权值 :"); printf("a 5\n"); printf("第2个原始码及其权值 :"); printf("b 3\n"); printf("程序会构造一棵哈夫曼树并显示哈夫曼编码.\n"); cout<<"权值"<<" "<<"原始码"<<" "<<"哈夫曼编码"<<endl ; printf(" 5 a 1\n"); printf(" 3 b 0\n"); putchar('\n'); putchar('\n'); while(choose!='N'&&choose!='n') { printf("请输入叶子结点数目:"); scanf("%d",&n); //输入叶子结点数 if(n<=1) {printf("该数不合理!\n");continue;} w=(unsigned int*)malloc(n*sizeof(unsigned int)); //开辟空间存放权值 source_code = (char *)malloc(n*sizeof(char)); //开辟空间存放原始码 //printf("请输入各原始码以及权值 :\n"); for(i=0;i<n;i++) { printf("第%d个原始码及其权值 :",i+1); cin>>source_code[i]; //输入原始码 cin>>w[i]; //输入各叶子结点权值 } CreateHuffmanTree(HT,w,n); //生成哈夫曼树 HuffmanCoding(HT,HC,n); //进行哈夫曼编码 putchar('\n'); PrintHuffmanCode(HC,w,n); //显示哈夫曼编码 printf("哈夫曼树构造完毕，还要继续吗?(Y/N)"); scanf(" %c",&choose); } } 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) //建哈夫曼树 { //从HT[1...i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 Select(HT,i-1,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; //编码结束位置 for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //从叶子到根逆向求编码 if(HT[f].lchild==c) cd[--start]='0'; //若是左孩子编为'0' else cd[--start]='1'; //若是右孩子编为'1' HC[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间 strcpy(HC[i],&cd[start]); //将编码从cd复制到HC中 } free(cd); //释放工作空间 } void PrintHuffmanCode(HuffmanCode HC,unsigned int *w,int n) { //显示有n个叶子结点的哈夫曼树的编码表 int i; printf("哈夫曼编码如下 :\n"); putchar('\n'); cout<<"权值"<<" "<<"原始码"<<" "<<"哈夫曼编码"<<endl ; for(i=1;i<=n;i++) { printf(" %d",w[i-1]); printf(" %3c\t ",source_code[i-1]); puts(HC[i]); } printf("\n"); } void Select(HuffmanTree HT,int t,int&s1,int&s2) { //在HT[1...t]中选择parent不为0且权值最小的两个结点，其序号分别为s1和s2,s1存放最小的，s2存放次小的 int i = 0 ;//i ， j , k 都是计数器 int j = 0 ; int k = 0 ; int least = 0 ; // 最小的权根节点的编号 int second = 0 ; //次小权的根节点的编号 for(i = 1 ; i <= t ; i++ ) { if(HT[i].parent == 0) break ; } for(j = i+1 ; j <= t ; j++ ) { if(HT[j].parent == 0) break ; } if(HT[i].weight < HT[j].weight) { least = i ; second = j ; } else { least = j; second = i ; } for(k = j+1; k <= t ; k++) { if(HT[k].parent == 0 ) { if(HT[k].weight < HT[least].weight) //小于原来的最小的 { second = least ; least = k ; } //小于次小的，大于最小的 else if(HT[k].weight >= HT[least].weight && HT[k].weight <HT[second].weight ) second = k ; } } s1 = least ; s2 = second ; }