2022年数据结构实验报告wzh .pdf

《2022年数据结构实验报告wzh .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构实验报告wzh .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验报告哈夫曼树的建立和编码器的实现题目： 哈夫曼树的建立和编码器的实现具体内容：先生成一棵哈夫曼树，再打印各字符对应的哈夫曼编码班级：通信工程0802 姓名 王增辉学号U200813021 完成日期2009.12.01 一、 需求分析本程序中，输入值的范围限定如下：字符的数目：限定为int 型。由于数值过大会引起输入及程序运行缓慢，我们约定数值书小于 40.若输入其它非法数值，则会过滤掉并提示输入合法字符，直至用户输入合法字符。#include / 所要引用的函数库#include #include #include typedef struct / 定义霍夫曼树的结点类型 char ch;

2、 int weight; int parent,lchild,rchild; HTNode,*HuffmanTree; typedef struct / 霍夫曼编码 char ch; char *chs; HuffmanCode; typedef struct / 由字符及权重构成的复合结构 char ch; int weight; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - sw; typedef struct / 霍夫曼

3、树以及霍夫曼编码构成的复合结构 HuffmanTree HT; HuffmanCode *HC; huf; void select(HTNode * HT,int n,int *n1,int *n2) / 在前 n 个数中选取parent 为零且最小的两个数，赋值给n1 n2 int n3,i=1; while(HTi.parent!=0) i+; *n1=i; i+; while(HTi.parent!=0) i+; *n2=i; if(HT*n1.weightHT*n2.weight) n3=*n1; *n1=*n2; *n2=n3; for(i+;i=n;i+) if(HTi.paren

4、t=0) if(HTi.weightHT*n1.weight) *n1=i; else if(HTi.weightHT*n2.weight) *n2=i; huf *HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,sw *w,int n,huf *HUF) / 霍夫曼编码 int m,i,s1,s2,start,c,f; HuffmanTree p; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - -

5、- - - char *cd; if(n=1) return 0; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT+1,i=1;iweight=w-weight; p-ch=w-ch; p-parent=0; p-lchild=0; p-rchild=0; for(;iweight=0; p-ch=0; p-parent=0; p-lchild=0; p-rchild=0; for(i=n+1;i=m;i+) select(HT,i-1,&s1,&s2); HTs1.parent=i; HTs2.parent=i; H

6、Ti.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; HC=(HuffmanCode *)malloc(n+1)*sizeof(char); cd=(char *)malloc(n*sizeof(char); cdn-1=0; for(i=1;iHT=HT; HUF-HC=HC; return HUF; char *convert(char *chars,char *chars1,HuffmanCode *hc,int n) char *p=chars; int i; strcpy(chars1,); while(*p

7、) i=1; while(hci.ch!=*p&i=n) i+; strcat(chars1,hci.chs); p+; printf( 字符转化为 :%sn,chars1); return chars1; void transcode(HuffmanTree ht,char *chars2,char*chars3) int i=1,p; char *q=chars2; char *r=chars3; while(hti.parent!=0) i+; p=i; while(*q) while(htp.lchild!=0 & *q) if(*q=0) 名师资料总结 - - -精品资料欢迎下载 -

8、 - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - p=htp.lchild; else p=htp.rchild; q+; if(htp.lchild=0) *r=htp.ch;r+; p=i; *r=0; printf( 原字符为 :); puts(chars3); void input(int *n,sw *w) int i,j,k; printf( 输入字符的数目：n); / 输入字符的数目j=scanf(%d,&k); while(!j) printf( 输入有误，

9、请输入数字n); fflush(stdin); printf( 输入字符的数目：n); fflush(stdin); j=scanf(%d,&k); *n=k; for(i=1;ich,&w-weight); int panduan(char ch ,sw *w,int n) int i; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - for(i=0;iHC; ht=HUF-HT; abc=convert(inchar,outchar,hc,n); transcode(ht,abc,outchar); getchar(); getchar(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -