数据结构赫夫曼树.doc

实验目的进一步掌握二叉树的存储结构和相应算法掌握霍夫曼树树的创建和霍夫曼编码实验环境硬件:每个学生需配备计算机一台。操作系统:DOS或Windows软件:DOS或Windows操作系统+TurboC;实验要求要求采用二叉链表作为存贮结构,完成霍夫曼树的创建输出对应数据的霍夫曼编码,并求出平均编码长度实验内容现在某电报公司假设有10字符进行编码,这10个字符的使用频率如下表所示,请创建霍夫曼树。ABCDEFGHIJ1918**********编写函数求出A~J的霍夫曼编码。#include<>#include<>#include<>typedefchar*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].wei