/*先根据位权构造一颗哈夫曼树，测试数据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;
4.写出构造完整的哈夫曼树的编码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);
}
5.如何用C语言建立一棵N层的完全二叉树,要求除根结点,其余的结束存储结构
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 ;
};
}
6.C语言编写huffman编码（信息论基础教程里的上级作业）#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; } 。