数据结构赫夫曼树2.doc

1、 实验目的1. 进一步掌握二叉树的存储结构和相应算法2. 掌握霍夫曼树树的创建和霍夫曼编码2、 实验环境1. 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows2. 软件：DOS或Windows操作系统+TurboC;3、 实验要求1. 要求采用二叉链表作为存贮结构，完成霍夫曼树的创建2. 输出对应数据的霍夫曼编码，并求出平均编码长度4、 实验内容1. 现在某电报公司假设有10字符进行编码，这10个字符的使用频率如下表所示，请创建霍夫曼树。ABCDEFGHIJ1918161412864212. 编写函数求出AJ的霍夫曼编码。#include #include #include typedef char* HuffmanCode;typedef struct char data; unsigned int weight ; unsigned int parent, LChild,RChild ; HTNode, * HuffmanTree; /选出权值最小的两个/void select(HuffmanTree *ht,int n, int *s1, int *s2)int i; int min1=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;void CrtHuffmanTree(HuffmanTree *ht , int n) /* w存放已知的n个权值，构造哈夫曼树ht */ int m,i,w; int s1,s2;char c; 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; /中序输出哈夫曼树叶子节点/void outputHuffman(HuffmanTree HT, int m) if(m!=0) outputHuffman(HT,HTm.LChild); if(!HTm.LChild&!HTm.RChild)printf(%ct, HTm.data); outputHuffman(HT,HTm.RChild); /*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n) char *cd; int i; unsigned int c; int start; int p; hc=(HuffmanCode *)malloc(n+1)*sizeof(char *); /*分配n个编码的头指针*/ cd=(char * )malloc(n * sizeof(char ); /*分配求当前编码的工作空间*/ cdn-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*/ else cd-start=1; /*右分支标1*/ hci=(char *)malloc(n-start)*sizeof(char); /*为第i个编码分配空间*/ strcpy(hci,&cdstart); free(cd); for(i=1;i=n;i+) printf(%c编码为%sn,(*ht)i.data,hci);/ 主函数/void main() HuffmanTree HT; HuffmanCode HC; int n; int m; printf(输入叶子节点的个数: ); scanf(%d,&n);