最优二叉树 c++ 数据结构

#include <stdio.h> #include <malloc.h> #include <string.h> #define MAX 999 typedef struct { unsigned int weight; //权值 unsigned int parent,lchild,rchild; //双亲，左孩子，右孩子 }HTNode,*HuffmanTree; typedef char** HuffmanCode; int min(HuffmanTree t,int i) //最小值 { int j,flag; unsigned int k = MAX; for(j=1;j<=i;j++) if(t[j].parent==0&&t[j].weight<k) { k=t[j].weight; flag = j; } t[flag].parent = 1; return flag; } void select(HuffmanTree h,int i,int &s1,int &s2) //找到两个最小的值 { int tmp; s1 = min(h,i); s2 = min(h,i); if(s1 > s2) { tmp = s1; s1 = s2; s2 = tmp; } } /*-------------------------------------------- *函数功能：构造哈夫曼树 --------------------------------------------*/ void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n,int &wpl) { int m,i,s1,s2; HuffmanTree p; if(n<=1) return; m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); 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[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } } /*-------------------------------------------- *函数功能：计算哈夫曼计算编码 --------------------------------------------*/ void find(HuffmanTree HT,HuffmanCode &HC,int *w,int n,int &wpl) { int i,start; unsigned int c,f; char* cd; HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); 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'; else cd[--start]='1'; } HC[i]=(char*)malloc((n-start)*sizeof(char)); wpl=wpl+(n-start-1)*HT[i].weight; strcpy(HC[i],&cd[start]); } free(cd); } /*-------------------------------------------- *函数功能：输出哈夫曼树 *由于存储结构问题，所以输出的是每个节点的 * 信息（双亲，左右孩子） --------------------------------------------*/ void DisplayTree(HuffmanTree tree,int Number) { for(int i=1;i<2*Number;i++) { printf("%5d",tree[i].weight); } printf("\n"); for(i=1;i<2*Number;i++) { printf("HufmTree[%2d].parent=%3d\n",i,tree[i].parent);//输出当前元素的parent值 printf("HufmTree[%2d].weight=%3d\n",i,tree[i].weight);//输出当前元素的weight值 printf("HufmTree[%2d].lchild=%3d\n",i,tree[i].lchild);//输出当前元素的lchild值 printf("HufmTree[%2d].rchild=%3d\n\n",i,tree[i].rchild);//输出当前元素的rchild值 } } /*-------------------------------------------- *函数功能： 交换左右子树 --------------------------------------------*/ void exchang(HuffmanTree tree,int Number) //交换所有二叉树的左右孩子 { for(int i=2*Number-1;i>=0;i--) { int temp=tree[i].lchild; tree[i].lchild=tree[i].rchild; tree[i].rchild=temp; } } int main() { HuffmanTree HT; HuffmanCode HC; int *w,n,i,wpl=0; printf("请输入权值的个数[>1]："); scanf("%d",&n); w=(int*)malloc(n*sizeof(int)); printf("请依次输入%d个权值[整型]：\n",n); for(i=0;i<=n-1;i++) scanf("%d",w+i); HuffmanCoding(HT,HC,w,n,wpl); //构造一棵树 //输出第一棵树 printf("输出第一棵最优二叉树：\n"); DisplayTree(HT,n); exchang(HT,n); //输出第二棵树 printf("输出第二棵最优二叉树：\n"); DisplayTree(HT,n); ///////////////******输出编码*******///////////////////////////// printf("第一棵最优二叉树的Huffman编码："); exchang(HT,n); find(HT,HC,w,n,wpl); for(i=1;i<=n;i++) printf("权值为%d的Huffman编码为：%s\n",HT[i].weight,HC[i]); printf("带权路径长度WPL=%d\n",wpl); printf("\n"); printf("第二棵最优二叉树的Huffman编码："); exchang(HT,n); find(HT,HC,w,n,wpl); for(i=1;i<=n;i++) printf("权值为%d的Huffman编码为：%s\n",HT[i].weight,HC[i]); printf("带权路径长度WPL=%d\n",wpl); ////////////////////////////////////////////////////////////////// return 0; }