数据结构赫夫曼树2

1、实验目的1.进一步掌握二叉树的存储结构和相应算法2.掌握霍夫曼树树的创建和霍夫曼编码2、实验环境1.硬件：每个学生需配备计算机一台。操作系统：DOS或Windows2.软件：DOS或Windows操作系统+TurboC;3、实验要求1.要求采用二叉链表作为存贮结构，完成霍夫曼树的创建2.输出对应数据的霍夫曼编码，并求出平均编码长度4、实验内容1.现在某电报公司假设有10字符进行编码，这10个字符的使用频率如下表所示，请创建霍夫曼树。ABCDEFGHIJ1918161412864212.编写函数求出A~J的霍夫曼编码。#includestdio.h#includestdlib.h#includestring.htypedefchar*HuffmanCode;typedefstruct{chardata;unsignedintweight;unsignedintparent,LChild,RChild;}HTNode,*HuffmanTree;//选出权值最小的两个//voidselect(HuffmanTree*ht,intn,int*s1,int*s2){inti;intmin1=0,min2=0;(*ht)[min1].weight=(*ht)[min2].weight=101;for(i=1;i=n;i++){if((*ht)[i].weight(*ht)[min1].weight&&(*ht)[i].parent==0)min1=i;}for(i=1;i=n;i++){if((*ht)[i].weight(*ht)[min2].weight&&(*ht)[i].parent==0&&min1!=i)min2=i;}*s1=min2;*s2=min1;}voidCrtHuffmanTree(HuffmanTree*ht,intn){/*w存放已知的n个权值，构造哈夫曼树ht*/intm,i,w;ints1,s2;charc;m=2*n-1;*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));/*0号单元未使用*/printf(输入字符及权重:\n);for(i=1;i=n;i++){/*1-n号放叶子结点，初始化*/fflush(stdin);scanf(%c%d,&c,&w);(*ht)[i].data=c;(*ht)[i].weight=w;(*ht)[i].LChild=0;(*ht)[i].parent=0;(*ht)[i].RChild=0;}for(i=n+1;i=m;i++){(*ht)[i].weight=0;(*ht)[i].LChild=0;(*ht)[i].parent=0;(*ht)[i].RChild=0;}/*非叶子结点初始化*//*创建非叶子结点,建哈夫曼树*/for(i=n+1;i=m;i++){/*在(*ht)[1]~(*ht)[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;}}//中序输出哈夫曼树叶子节点//voidoutputHuffman(HuffmanTreeHT,intm){if(m!=0){outputHuffman(HT,HT[m].LChild);if(!HT[m].LChild&&!HT[m].RChild)printf(%c\t,HT[m].data);outputHuffman(HT,HT[m].RChild);}}/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/voidCrtHuffmanCode(HuffmanTree*ht,HuffmanCode*hc,intn){char*cd;inti;unsignedintc;intstart;intp;hc=(HuffmanCode*)malloc((n+1)*sizeof(char*));/*分配n个编码的头指针*/cd=(char*)malloc(n*sizeof(char));/*分配求当前编码的工作空间*/cd[n-1]='\0';/*从右向左逐位存放编码，首先存放编码结束符*/for(i=1;i=n;i++)/*求n个叶子结点对应的哈夫曼编码*/{start=n-1;/*初始化编码起始指针*/for(c=i,p=(*ht)[i].parent;p!=0;c=p,p=(*ht)[p].parent)/*从叶子到根结点求编码*/if((*ht)[p].LChild==c)cd[--start]='0';/*左分支标0*/elsecd[--start]='1';/*右分支标1*/hc[i]=(char*)malloc((n-start)*sizeof(char));/*为第i个编码分配空间*/strcpy(hc[i],&cd[start]);}free(cd);for(i=1;i=n;i++)printf(%c编码为%s\n,(*ht)[i].data,hc[i]);}//主函数//voidmain(){HuffmanTreeHT;HuffmanCodeHC;intn;intm;printf(输入叶子节点的个数:);scanf(%d,&n);CrtHuffmanTree(&HT,n);m=2*n-1;printf(中序输出哈夫曼树叶子节点：\n);outputHuffman(HT,m);printf(\n);CrtHuffmanCode(&HT,&HC,n);}五、实验结果