哈夫曼树的建立及哈弗曼编码的构造

哈夫曼树的建立及哈弗曼编码的构造 《数据结构》课程设计报告 完成日期: 2012-07-11 \ 目录 1 实验目的 ?????????????????????????????????????????????3 2 问题描述 ?????????????????????????????????????????????3 3算法的思想与算法实现步骤?????????????????????????? 3 4 程序核心代码及主要设计 ????????????????????????? ?????4 4.1哈夫曼树节点的数据类型定义: ?????????????????????4 4.2初始化哈夫曼树„„???…???????…????????…????????5 4.3选权值最小函数 ???????????????????????????????????5 4.4创建哈夫曼树的函数: ?????????????????????????????6 4.5打印输出哈夫曼树，字符，权值，以及它对应的编码:??6 4.6 编码的重要哈夫曼树路径递归算法:??????????????????7 4.7对字符进行初始编码:????????????????????????…????7 4.8 encoding 编码功能:对输入字符进行编码?????????????7 4.9对输入的字符进行解码:????????????????????????…????8 4.10 主函数体???????????????????????…????????????????9 5 程序运行结果 ???????????????????----??????????????????10 6. 实验????????????????????????????????????????????13 2 1. 实验目的 掌握哈夫曼树的建立及哈夫曼编码的生成方法;首先输入字符和对应的权值，打印输出哈夫曼树和字符的编码;然后输入一字符串，对其进行编码;最后输入由0、1组成的字符串，实现对其的译码～ 2. 问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。 用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVORITE”。 字符 空格 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 3. 算法的思想与算法实现步骤 1)主要思想: 根据给定的字符和其中每个字符的频度,构造哈夫曼树,并输出字符集中每个字符的哈夫曼编码.将给定的字符串根据其哈夫曼编码进行编码,并进行相应的译码. 2) 基本框架: 函数名 属性 功能 inithfmt(hfmt t) t[i].weight=0;t[i].lchild= -1; 对结构体htnode 初始化， t[i].rchild= -1; t[i].parent= -1; 实现父子结点的初始值 inputweight(hfmt t)/ int w;//w权值char k;//字符 自定义输入函数，输入对 t[i].key=k; t[i].weight=w; 应的字符和权值。 selectmin(hfmt t,int long min1=999999; 每次选权值最小、次小的i,int *p1,int *p2) long min2=999999; 结点使之成为新结点。 t[i].lchild=p1;t[i].rchild=p2; creathfmt(hfmt t) t[i].weight=t[p1].weight+t[p2].创建哈夫曼树的函数 weight; printhfmt(hfmt t) printf("\t\t权值\t父母\t左孩打印哈夫曼树 子\t右孩子\t字符\t"); hfmtpath(hfmt t,int hfmtpath(t,i,j);if(t[b].lchild==a哈夫曼树编码路径的递i,int j) ) printf("0");else printf("1"); 归算法. 3 phfmnode(hfmt t) printf("\t\t%c\t",t[i].key,t[i].we对字符进行初始编码 ight); hfmtpath(t,i,j); encoding(hfmt t) if(r[j]==t[i].key)hfmtpath(t,i,j); 对输入的电文进行编码 decoding(hfmt t) j=2*n-2;//j从树的根节点开始 对用户输入的密文进行 int main() hfmt ht; char flag; 主菜单输出 3)系统结构图(功能模块图) 4.程序核心代码及主要设计 1.哈夫曼树节点的数据类型定义: 代码: typedef struct { int weight; int lchild; int rchild; int parent; char key; }htnode; 2、void inithfmt(hfmt t)初始化哈夫曼树，处理 inputweight(hfmt t) 函数得到的数据，按照哈夫曼规则建立2叉树。此函数块调用了selectmin()函数。 代码: void inithfmt(hfmt t)//对结构体进行初始化 { int i; printf("\n请输入要设置的叶子结点个数n="); scanf("%d",&n); getchar(); for(i=0;i<2*n-1;i++)//对结构体进行初始化 { t[i].weight=0; t[i].lchild=-1; 4 t[i].rchild=-1; t[i].parent=-1; } printf("\n");} void inputweight(hfmt t)//输入函数 { int w;//w表示权值 int i; char k;//k表示获取的字符 for(i=0;it[j].weight) { min1=t[j].weight; *p1=j; } 5 for(j=0;j<=i;j++)//选择次小权值字符的下标还回 if(t[j].parent==-1) if(min2>t[j].weight && j!=(*p1))//注意 j!=(*p1)) { min2=t[j].weight; *p2=j; } } 4、创建哈夫曼树的函数 代码: void creathfmt(hfmt t)// { int i,p1,p2; inithfmt(t); inputweight(t); for(i=n;i<2*n-1;i++) { 1,&p1,&p2); selectmin(t,i- t[p1].parent=i; t[p2].parent=i; t[i].lchild=p1; t[i].rchild=p2; t[i].weight=t[p1].weight+t[p2].weight; }} 5、打印输出哈夫曼树，字符，权值，以及它对应的编码 代码: void printhfmt(hfmt t) { int i; printf(" *******由哈夫曼编码建立的图表结构如下:*******\n"); printf("\t\t权值\t父母\t左孩子\t右孩子\t字符\t"); for(i=0;i<2*n-1;i++) { printf("\n"); printf("\t\t%d\t%d\t%d\t%d\t%c",t[i].weight,t[i].parent,t[i].lchild,t 6 [i].rchild,t[i].key); } printf("\n\n"); } 6、编码的重要哈夫曼树路径递归算法 代码: void hfmtpath(hfmt t,int i,int j) { int a,b; a=i; b=j=t[i].parent; if(t[j].parent!=-1) { i=j; hfmtpath(t,i,j); } if(t[b].lchild==a) printf("0"); else printf("1");} 7、对字符进行初始编码 代码: void phfmnode(hfmt t)// { int i,j,a; printf(" ***所得哈夫曼编码为***\n"); for(i=0;i心得体会

决胜全面小康心得体会学党史心得下载党史学习心得下载军训心得免费下载党史学习心得下载