1.哈夫曼编码器
#include "stdio.h"#include "stdlib.h"#include "string.h" typedef struct{ char ch; unsigned int weight; unsigned int parent, lchild, rchild; } HTNode;//哈夫曼树类型定义(用一维数组表示) typedef HTNode HuffmanTree[100]; //假设树最多100个结点//存放哈夫曼编码的变量类型定义(用两维字符数组) typedef char HuffmanCode[100][100];//假设最多100个字符,每个字符编码最多100位 void select(HuffmanTree HT, unsigned int n, unsigned int *s1,unsigned int *s2) { unsigned int flag=1000;/*设一个权值最大值*/ unsigned int i,minweight; minweight=flag; for(i=1;i<=n;i++) {/*查找parent为0,权值最小的结点,把序号记入s1中*/ if(HT[i].parent==0 && HT[i].weight HT[i].weight=w[i-1]; HT[i].lchild=0; HT[i].rchild=0; HT[i].parent=0; } //初始化非叶结点 for(i=n+1; i<=m;++i) { HT[i].weight=0; HT[i].lchild=0; HT[i].rchild=0; HT[i].parent=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; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; }/*//////////////////////////////////////////////////////////////*//*从叶子到根求每个字符的哈夫曼编码*/ for(i=1;i<=n;++i)//对每个叶结点 { j=1;//计数,也作下标 parent=HT[i].parent;//求其父结点 child=i;//记下孩子结点 while(parent!=0)//不是树根 { if(HT[parent].lchild==child)//是父结点的左孩子? code[j]='0'; //编码为0 else //是右孩子 code[j]='1'; //编码为1 j++; child=parent;//新孩子 parent=HT[parent].parent;//新的父结点 } for(k=0;k 定义哈夫曼树与编码的存储结构与数据类型 typedef struct { char data;//节点值 int weight; //权重 int parent; //双亲节点 int lchild; //左孩子节点 int rchild; //右孩子节点 } HTNode; typedef struct { char cd[N]; //存放哈夫曼码 int start; } HCode; void CreateHT(HTNode ht[],int n) //创建哈夫曼树 void CreateHCode(HTNode ht[],HCode hcd[],int n) //根据哈夫曼树计算每个元素的哈夫曼编码 void DispHCode(HTNode ht[],HCode hcd[],int n) //输出每个元素的哈夫曼编码 原发布者:丁丁的23号 /*先根据位权构造一颗哈夫曼树,测试数据0.050.10.150.20.250.25,再从叶子结点到根结点编码。程序结果保存在out.dat中。*/#include#include#include#defineN6typedefstruct{doubleweight;intparent,lchild,rchild;}HuffmanTree;voidSelect(HuffmanTree*HT,inti,int*s1,int*s2){intn,T=0,T1;for(n=1;n<i;n++)if((HT[n].weight<=HT[T].weight)&&HT[n].parent==0)T=n;*s1=T;T1=T;T=0;for(n=1;n<i;n++){if(n==T1)continue;if((HT[n].weight<=HT[T].weight)&&HT[n].parent==0)T=n;}*s2=T;}voidHuffmanCoding(HuffmanTree*HT,char**HC,double*w,intn){intm,i,start;ints1,s2,f,c;char*cd;HuffmanTree*p;if(n<=1)return;m=2*n-1;HT[0].weight=10000;w++;for(p=HT+1,i=1;iweight=*w;p->lchild=0;p->rchild=0;p->parent=0;}for(;iweight=0;p->lchild=0;p->rchild=0;p->parent=0;}for(i=n+1;i<=m;++i){Select(HT,i,&s1,&s2);HT[s1].parent=i;HT[s2].parent=i; void HuffmanCoding(HuffmanCode HC[], int w[], int n) // w存放n个字符的权值(均>0),构造哈夫曼树HT, 并求出n个字符的哈夫曼编码HC { int i, j; char *cd; int start; if (n<=1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用 for (i=1; i<=n; i++) //初始化 { HT[i].weight=w[i-1]; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; HT[i].ch=0; } for (i=n+1; i<=m; i++) //初始化 { HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; HT[i].ch=0; } for (j=1,i=n+1; i<=m; i++,j++) // 建哈夫曼树 { Select(i-1); 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; HT[i].ch=j; } cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;++i) { start=n-1; HT[i].ch=i; for(unsigned int 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)); strcpy(HC[i],&cd[start]); } free(cd); } 存储结构 typedef struct { int weight; int parent, lchild, rchild; } HTNode ,*HuffmanTree; // 动态分配数组存储huffman树 算法设计 void createHuffmantree(){ ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode);// 动态分配数组存储huffman树,0号单元未用 // m:huffman 树中的结点数(m=2*n-1) for (i=1;i<=m;++i) ht[i].parent= ht[i]->lch= ht[i]->rch=0; for (i=1;i<=n;++i) ht[i].weight=w[i]; //初始化,w[i]:n个叶子的权值 for (i=n+1;i<=m,++i) { //建哈夫曼树 select(i-1),s1,s2); //在ht[k](1<=k<=i-1)中选择两个双亲域为零而权值取最小的结点 :s1和s2 ht[s1].parent= ht[s2].parent=i; ht[i].lch=s1; ht[i].rch=s2; ht[i].weight=ht[s1].weight + ht[s2].weight ; }; } #includestdio.h> #includestdlib.h> #includestring.h> #includemalloc.h> #define N 20 #define M 2*N-1 #define Min 1000 /*最小值*/ typedef struct { char ch; /*权值对应的字符*/ int weight; /*权值*/ int parent; /*双亲位置*/ int Lchild; /*左孩子位置*/ int Rchild; /*右孩子位置*/ }HTNode,Huffmantree[M+1]; char hc[N+1][N+1]; void OutputHuffmancode(Huffmantree ht, int n); void CrtHuffmancode(Huffmantree ht, int n); void OutputHuffmantree(Huffmantree ht,int n); void select(Huffmantree ht,int a,int *s1,int *s2) { int i; int c1=Min; int c2; for(i=1;i=a;i++) { if (ht.parent==0&&ht.weightc1) { *s1=i; c1=ht.weight; } } c2=Min; for(i=1;i=a;i++) { if (ht.parent==0&&(*s1!=i)&&c2>ht.weight) { *s2=i; c2=ht.weight; } } } void CrtHuffmantree(Huffmantree ht,int w[],char elem[],int n) { int i; int m; int s1,s2; m=2*n-1; ht=(HTNode *)malloc((m)*sizeof(HTNode)); for(i=1;i=n;i++) { ht.ch=elem[i-1]; ht.weight=w[i-1]; ht.parent=0; ht.Lchild=0; ht.Rchild=0; } for(i=n+1;i=m;i++) { ht.ch='\0'; ht.weight=0; ht.parent=0; ht.Lchild=0; ht.Rchild=0; } /*初始化完毕*/ for(i=n+1;i=m;i++) { select( ht,i-1,&s1,&s2); /*返回最小值和次小值的位置*/ ht.weight=ht[s1].weight+ht[s2].weight; ht[s1].parent=i; ht[s2].parent=i; ht.Lchild=s1; ht.Rchild=s2;/*建立树完毕*/ } OutputHuffmantree( ht,m); printf("now begin crthuffman code\n"); CrtHuffmancode( ht, n); printf("crthuffman code end\n"); OutputHuffmancode(ht, n); } void OutputHuffmantree(Huffmantree ht,int n) { int i; printf("\nnumber---weight---parent---Lchild---Rchild---huffman char\n \n"); for(i=1;i=n;i++) printf("%d\t%d\t%d\t%d\t%d\t%c\n",i,ht.weight,ht.parent,ht.Lchild,ht.Rchild,ht.ch); } void CrtHuffmancode(Huffmantree ht, int n) /*建立编码*/ { int i,c,p; int start; char *cd; cd=(char *) malloc((n+1)*sizeof(char)); memset(cd,'\0',sizeof(cd)); for(i=1;i=n;i++) { start=n; cd[start]='\0'; c=i; p=ht.parent; while(p!=0) { start--; if(ht[p].Lchild==c) cd[start]='0'; else cd[start]='1'; c=p; p=ht[p].parent; } //cd[start] = '\0'; printf("cd is %s\n start is %d\n", cd+start, start); sprintf(hc, "%s", cd+start); /*将已存在的编码复制到code中*/ } free(cd); } void OutputHuffmancode(Huffmantree ht,int n) { int i; printf("\nweight_char---weight---huffmancode\n \n"); for(i=1;i=n;i++) printf(" %c\t%4d\t%s\n",ht.ch,ht.weight,hc); } int main() { int n = 6;/*记录了权值个数*/ Huffmantree hfm; int w[] = {45,13,12,16,9,5}; char elem[] = {'a','b','c','d','e','f'}; CrtHuffmantree( hfm, w,elem, n); return 0; }。 转载请注明出处育才学习网 » ht的parent值怎么写2.哈夫曼树HT存储结构的初态和末态怎么写
3.哈夫曼编码的C语言源代码
4.写出构造完整的哈夫曼树的编码
5.如何用C语言建立一棵N层的完全二叉树,要求除根结点,其余的结束
6.C语言编写huffman编码(信息论基础教程里的上级作业)