huffmantree(哈夫曼树)C语言,用结构数组实现
废话不多说直接看代码,有什么对于哈夫曼树的疑问直接去百度就行了,这里就不啰嗦了:
- #include<stdio.h>
- #define N 5
- #define M 2*N-1
- typedef struct huffmantree
- {
- int weight;
- int parent;
- int lchild;
- int rchild;
- int ownplase; //每个带权值的节点的位置//
- }huffmantree; //一般清空下,第0号元素不用//
- void Inittree(huffmantree T[]) //初始化全部值赋值为0//
- {
- for(int i=0;i<M+1;i++)
- {
- T[i].weight=0;
- T[i].parent=0;
- T[i].lchild=0;
- T[i].rchild=0;
- }
- for(int j=1;j<M+1;j++) //节点从1开始//
- {
- T[j].ownplase=j;
- }
- }
- void createdhuffmantree(huffmantree T[]) //输入前N项的权值//
- {
- for(int i=1;i<N+1;i++)
- {
- scanf("%%d",&T[i].weight);
- }
- }
- void select(huffmantree T[],int n,int m) //n是开始,m是结束//
- {
- int i,j,e;
- for(i=n;i<m;i++) //冒泡排序将权值从小到达排序,为后面的huffman选取最小组合减小筛选时间//
- {
- for(j=n;j<m;j++)
- {
- if(T[i].weight<T[j].weight) //交换就要交换所有值//
- {
- e=T[i].weight;
- T[i].weight=T[j].weight;
- T[j].weight=e;
- e=T[i].ownplase;
- T[i].ownplase=T[j].ownplase;
- T[j].ownplase=e;
- e=T[i].lchild;
- T[i].lchild=T[j].lchild;
- T[j].lchild=e;
- e=T[i].rchild;
- T[i].rchild=T[j].rchild;
- T[j].rchild=e;
- e=T[i].parent;
- T[i].parent=T[j].parent;
- T[j].parent=e;
- }
- }
- }
- }
- void judgehuffmantree(huffmantree T[])
- {
- int e,flag,n,m;
- n=1;
- m=N+1;
- flag=1;
- while(flag)
- {
- select(T,n,m);
- T[n].parent=T[m].ownplase;
- T[n+1].parent=T[m].ownplase;
- T[m].weight=T[n].weight+T[n+1].weight; //开始修改后N个节点的权值//
- T[m].lchild=T[n].ownplase; //赋值给左孩子,次序无所谓 //
- T[m].rchild=T[n+1].ownplase; //赋值给右孩子//
- m++;
- n+=2;
- if(n!=m)
- {
- flag=1;
- }else{
- flag=0;
- }
- }
- T[M].parent=NULL;
- }
- void printhuffmantree(huffmantree T[])
- {
- printf("wgight parent lchild rchild
");
- for(int i=1;i<M+1;i++)
- {
- for(int j=1;j<M+1;j++)
- {
- if(T[j].ownplase==i)
- {
- printf("%%-6d %%-6d %%-6d %%-6d
",T[j].weight,T[j].parent,T[j].lchild,T[j].rchild);
- }
- }
- }
- }
- int main()
- {
- huffmantree T[M+1];
- Inittree(T);
- printf("请输入哈夫曼树的前N项权值:
");
- createdhuffmantree(T);
- judgehuffmantree(T);
- int MPL=0; //计算该huffmantree的MPL//
- for(int i=1;i<M;i++)
- {
- MPL=MPL+T[i].weight;
- }
- printf("此huffmantree的MPL=%%d
",MPL);
- printhuffmantree(T);
- return 0;
- }
给大家加一个例子:
question:Please input 5 trees with weights(5.7.3.2.8) from the keyboard and print huffman table。
推荐阅读