C语言大作业(基于哈夫曼树的压缩程序)
2009级《高级语言程序设计》大作业上机报告
题目:基于哈弗曼算法的压缩
参与人员：
【姓名】【学号】
[问题定义] 压缩机解压的实现
[开发工具]DEV-C++
[数据结构]
struct head
{
unsigned char b; /*记录字符在数组中的位置*/
long count; /*字符出现频率（权值）*/
long parent,lch,rch; /*定义哈夫曼树指针变量*/
char bits[256]; /*定义存储哈夫曼编码的数组*/
}
header[512],tmp;
tmp 用于交换值
header[512] 用于储存数据
filename[255] 用于储存文件地址
[算法描述]
本程序是基于哈弗曼编码的程序
主要分为两个函数：压缩函数 void compress()
解压函数 void uncompress()
主要流程如下
[算法描述] main函数
compress()函数
压缩算法 1打开文件
2逐个读取文件的ASCII 码，储存在c ，统计频率 fread(&c,1,1,ifp)
；
header[c].count++;
3每个哈夫曼码值及其对应的ASCII 码存放在一维数组header[i]中 if(header[i].count!=0) header[i].b=(unsigned char)i; 4据频率（权值）大小，对结点进行排序 5构建哈曼树，亚此选择权值最小的入树 6计算权值大小
7从文件开始将字符编码每8各编入一个字节，剩下超过4位再编入下一个， 少于4位，则放入新字节
uncompress()函数
解压算法
1读取原文件长度，对文件进行定位
fread(&flength,sizeof(long),1,ifp);
2取原文件字符的权值
p=(long)c;
3将f转换为二进制表示的字符串
itoa(f,buf,2);
4据哈夫曼编码的长短，对结点进行排序
5根据哈夫曼编码的长短，对结点进行排序
6通过哈夫曼编码的长短，依次解码，从原来的位存储还原到字节存储7在单字节内对相应位置补0
8从压缩文件中的按位存储还原到按字节存储字符；字符位置不改变
程序调试情况1主界面
2解压测试
原文件
压缩
压缩得到的文件
解压测试
解压后的文件
错误测试
文件不存在
参考书籍：
《数据结构》李春葆著清华大学出版社
程序源代码https://www.sodocs.net/doc/7e15379601.html,/question/7777030.html?si=3
哈夫曼树及其应用(完美版)
数据结构课程设计设计题目：哈夫曼树及其应用 学院：计算机科学与技术 专业：网络工程 班级：网络 131 学号：1308060312 学生姓名：谢进 指导教师：叶洁 2015年7 月12 日
设计目的： 赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。 1、熟悉树的二叉树的存储结构及其特点。 2、掌握建立哈夫曼树和哈夫曼编码的方法。 设计内容： 欲发一封内容为AABBCAB ……(共长 100 字符,字符包括A 、B 、C 、D 、E 、F六种字符)，分别输入六种字符在报文中出现的次数（次数总和为100），对这六种字符进行哈夫曼编码。 设计要求： 对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，∑WiLi 恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵赫夫曼树，此构造过程称为赫夫曼编码。设计实现的功能： 1.以二叉链表存储， 2.建立哈夫曼树； 3.求每个字符的哈夫曼编码并显示。
哈工大c语言 练习题
求用户输入得两个数得商,程序运行时,以如下格式输入数据: Iｎpｕt twｏiｎｔegｅrs:42↙ 请改正程序中得错误,使它能得出正确得结果。 ＃includｅ＜stdｉo、h> main() { ｉｎｔａ, b, ｃ; prinｔｆ(＂Ｉnpｕt two inｔegers:"); scanf(＂％d,%d",&a, ＆b); ｃ= a＼b; pｒiｎtf("Theｑｕotient oｆａandｂｉｓ:%d", c); ｝ ＃ｉｎclude〈ｓtdio.h> iｎt maｉｎ() ｛ ?inｔa,b,c; pｒｉｎｔf("Iｎpuｔｔwｏinｔegers:＂); ｓcanf (＂%ｄ%d＂,&a,＆b); ?c=a/ｂ; printｆ(”Ｔhe qｕotient of a aｎd b ｉｓ:%d＼n”,c); ?ｒeturn ０; } 使用ｃonｓt常量定义圆周率pi=3、14159,编程从键盘输入圆得半径r,计算并输出圆得周长与面积。输出得数据保留两位小数点。输入格式要求:”％lf" 提示信息:”Inpｕt r:” 输出格式要求: "pｒintf ＷITHOUT widｔh or precision ｓｐecｉｆicatioｎｓ:\ｎ" "cirｃumfｅreｎce = %ｆ, aｒea= ％f\n”＂pｒｉntf WITＨwidth aｎd prｅｃisｉon specificatiｏnｓ:\ｎ＂ ＂cｉｒcumfｅrence＝％7、2f, ａrea = %7。2f\n” 程序运行示例如下: Iｎput r:５。３ printf WITHOUT ｗidth ｏr precision speciｆications: cｉｒｃumferenｃe ＝３3、3０0854,are ａ=８８.247２６3 pｒinｔf WITＨwiｄｔｈａnd preciｓion ｓpecifiｃａtiｏｎs: ｃircｕmfｅrｅnce = 33。3０, ａｒｅa = 88、２5 ＃inｃｌude〈stdiｏ。h> ｉnt main() ｛ const doｕble PI=３.14159; ｄｏuble r; priｎtf(”Inｐuｔr:"); sｃａnf(＂%lf”, &ｒ); ｐｒiｎtｆ("pｒintf WＩTHＯUT wiｄth oｒpｒecｉｓiｏn spｅｃifｉｃatｉｏn ｓ:\n＂); pｒｉｎtf(＂ｃｉrcumｆerenｃe = ％f, ａreａ= ％f\n＂,2＊ＰI＊r,ＰI＊r*r); printｆ("ｐrintf WITＨｗｉｄth and precisioｎspecifications:\n”); ?prｉnｔf("cirｃumｆｅrence＝%７.2ｆ, area ＝％7、2f\n",2＊PＩ＊r,PＩ*ｒ＊ｒ); return 0; ｝ 写一个程序,将接收得华氏温度转换为对应得摄氏温度。程序应显示如下得提示信息: Please inｐuｔｆahｒ: 然后输入一个十进制数并回车,然后程序以合适得消息形式输出转换后得华氏温度。程序使用如下得公式完成转换:摄氏温度＝ 5.0 ＊(华氏温度–32.0)/ ９.０ 输入格式要求:"％lf" 提示信息:＂Pleaｓｅinput faｈr: ” 输出格式要求:"Ｔhｅｃelｓis: %.2f＂ #inｃlude ＜stdio。ｈ〉 ＃includｅ＜stdliｂ.h＞ iｎt main() { ｄoｕblｅf; douｂｌe c; prinｔｆ(”Ｐｌease iｎput fahr: "); scａnf(＂%lf",&f); c=５、０*(f-３2.0)/9.0; prinｔf("Tｈｅcｅｌs is: %、2f”,c);
哈夫曼树的建立与操作
实验六哈夫曼树的建立与操作 一、实验要求和实验内容 1、输入哈夫曼树叶子结点（信息和权值） 2、由叶子结点生成哈夫曼树内部结点 3、生成叶子结点的哈夫曼编码 4、显示哈夫曼树结点顺序表 二、详细代码（内包含了详细的注释）： #include
cout<<"输入第"<
哈工大C语言实验题
Q308.(10分)第5章实验2：体型判断。 医务工作者经广泛的调查和统计分析，根据身高与体重因素给出了以下按“体指数”进行体型判断的方法。体指数计算公式是： t = w /(h*h) 其中：t是体指数；w是体重，其单位为千克；h是身高，其单位为米。根据给定的体指数t计算公式，可判断你的体重属于何种类型： 当t<18 时，为低体重； 当18≤t<25 时，为正常体重； 当25≤t<27 时，为超重体重； 当t≥27 时，为肥胖。 ****输入提示信息格式："Please enter h,w:\n" ****输入数据格式要求："%f,%f"（先读入身高，再读入体重，身高以米读入，体重以千克读入） ****输出数据格式要求: 当t<18 时，输出："Lower weight!\n" 当18≤t<25 时，输出："Standard weight!\n"
当25≤t<27 时，输出："Higher weight!\n" 当t≥27 时，输出："Too fat!\n" #include
哈夫曼树 实验报告
计算机科学与技术学院数据结构实验报告 班级2014级计算机1班学号20144138021 姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期2016.1.5 一、实验目的 本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree.dat中。 2、编码。 利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入），对文件中的正文进行编码，然后将结果存入文件codefile.dat中。 3、译码。 利用已建好的哈夫曼树将文件codefile.dat中的代码进行译码，结果存入文件textfile.dat中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树， 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为： Typedef strcut { Int weight；/*结点权值*/ Int parent； Int lchild； Int rchild； }HNodeType； 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型：
实验四 哈夫曼树的建立
09级信管专业01班学号0902011392012年5月25日 姓名黄涛指导老师杨明欣 实验名称哈夫曼树的建立 一、实验目的： 1．理解哈夫曼树及其应用。 2．掌握生成哈夫曼树的算法。 二、实验内容： 哈夫曼树，即最优树，是带权路径长度最短的树。有着广泛的应用。在解决某些判定问题上，及字符编码上，有着重要的价值。 构造一棵哈夫曼树，哈夫曼最早给出了算法，称为哈夫曼算法： （1）根据给定的N个权值W1，W2，W3，……，Wn ，构成N棵二叉树的集合F= T1，T2，T3，……，Tn ，其中每棵二叉树T1只有一个带权为WI的根结点，其左右子树均空。 （2）在F中选出两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的权值为其左右子树上的根结点的权值之和。 （3）在F中删除这两棵树，同时将新得到的加到F之中。重复（2）和（3），直至F 中只剩一个为止。 三、程序流程图
四、程序代码 #include"stdio.h" #define LEN sizeof(struct HTnode) int i,l,n,w=0,c,start,a1,a2,f; struct HTnode {unsigned int weight; unsigned int parent,lchild,rchild; }*p,*HT; typedef char **Huffmancode; Huffmancode HC; char *cd; select() {int k=1,j,flag=0; while((HT+k)->parent!=0) k++; for(j=k+1;j<=n;j++,flag=0) {if((HT+j)->parent!=0) flag=1; if((HT+j)->weight==0) flag=1; if(!flag) {if((HT+j)->weight<(HT+k)->weight) k=j;} } return(k); } main() {printf("\n赫夫曼树的建立:\n"); printf("请输入权值(叶子)数目:"); scanf("%d",&l); while(l<1) {printf("输入错误,请重新输入权值数目:"); scanf("%d",&l); } if(l==1) printf("\n只有一个权值,无须建立赫夫曼树!"); else {n=2*l-1; HT=(struct HTnode*)malloc((n+1)*LEN); printf("请按对应顺序输入权值(输入一权值,键入一回
哈工大C语言课程设计
H a r b i n I n s t i t u t e o f T e c h n o l o g y 课程设计说明书（论文） 课程名称：C语言课程设计 设计题目：音乐程序与波特图 院系：航天学院控制科学与工程系 班级： 设计者： 学号： 指导教师： 设计时间： 哈尔滨工业大学教务处 哈尔滨工业大学课程设计任务书
题目一 1.1题目详细描述： 播放音乐程序，实现了自选音乐曲目和直接使用键盘弹奏，而且可以在曲目播放结束后循环选择乐曲。 1.2程序设计思路及流程图： 1.3 #include
C0=262,D0=296,E0=330,F0=349,G0=392,A0=440,B0=494, C1=523,D1=587,E1=659,F1=698,G1=784,A1=880,B1=988, C2=1047,D2=1175,E2=1319,F2=1397,G2=1568,A2=1760,B2=1976,S=10 }; typedef enum NOTES SONG; SONG song1[]={C0,N4+N2,E0,N4,G0,N2,G0,N2,A0,N1,G0,N1,E0,N4+N2, C0,N4,G0,N1/3,G0,N1/3,G0,N1/3,E0,N1,C0,N1,G10,N1/3,G10,N1/3, G10,N1/3,G10,N1/3,G10,N1/3,G10,N1/3,C0,N1,END,END}; SONG song2[]={A0,N2,B0,N2,C1,N1+N2,B0,N2,C1,N1,E1,N1,B0,N1+N1,S,N1,E0,N1, A0,N1+N2,G0,N2,A0,N1,C1,N1,G0,N1+N1,S,N1,E0,N2,E0,N2,F0, N1+N2,E0,N2,F0,N1,C0,N1,E0,N1+N1,S,N1,C1,N2,C1,N2,B0,N1+N2,370, N2,F0,N1,B0,N1,B0,N1+N2,S,N1,A0,N2,B0,N2,C1,N1+N2,B0,N2,C1,N1, E1,N1,B0,N1+N2,END,END}; int main() { int m,n,c=1; char b='y'; while(b=='y') { printf("Hello,what do you want to do by this program?\n"); printf("1.Listen to music.-------Press 1\n"); printf("2.Play music by yourself.-------Press 2\n"); scanf("%d",&m); while(m!=1&&m!=2&&m!=3) /*选择方式*/ { printf("You typed wrong!Do not push me around.:(\n"); scanf("%d",&m); } if(m==1) { printf("I have two musics,choose one!(Press 1/2)\n"); scanf("%d",&n); while(n!=1&&n!=2) { printf("You typed wrong!Do not push me around.:(\n"); scanf("%d",&n); } playmusic(n,&c); } else if(m==2) { typemusic(); } getchar(); printf("Do you want to continue?(y/n)\n"); scanf("%c",&b);
哈夫曼树
目录 一、程序设计目的与要求 (3) 1.1程序设计目的 (3) 1.2程序设计要求 (3) 二、需求分析 (4) 三、概要设计 (4) 3.1哈夫曼树的构造过程 (4) 3.2译码过程是编码过程的逆过程 (5) 3.3 构造哈夫曼树和哈夫曼编码类的描述 (5) 四、详细设计 (6) 五、调试分析 (11) 5.1程序编译界面 (11) 5.2程序运行界面 (12) 六、测试结果 (13) 七、附录 (15) 7.1设计心得 (15) 7.2参考文献 (15)
一、程序设计的目的与要求 1.1程序设计目的 课程设计是《数据结构》课程教学必不可缺的一个重要环节，通过课程设计，使学生对整个课程的知识体系有较深入的理解，在运用本课程的知识解决实际问题方面得到锻炼，对锻炼学生的实践能力以及运用本课程的知识、方法解决更为复杂的实际问题有较好的启发和指导作用，从而为后续课程的学习，毕业设计环节以及将来的实际工作打好坚实的基础。本课程设计的目是： 1.培养学生将所学的算法知识应用于程序设计过程中，设计出运行效率更高的 程序； 2.了解数据的三种逻辑结构（线性结构、树结构、图结构）和四种存储结构（顺 序、链接、索引、散列）的基本特性和相互关系； 3.掌握算法知识，学会设计算法并对算法进行分析和评价。 1.2程序设计要求 在设计时严格按照题意独立进行设计，不得随意更改。要求熟悉C、C++等某一种高级程序设计语言。通过本课程的学习与实践，学生应做到： 1.掌握数据结构的基本概念和基本理论。 2.熟练掌握顺序表、链表、队列、栈、树以及二叉树、图等基本数据结构的设 计和分析。 3.熟练地掌握常用算法（递归、遍历、查找、排序）的知识。 4.能对所求解的问题进行分析，抽象出逻辑结构，选择合适的存储结构，定义 所需的运算，设计相应的算法。 5.对算法进行分析和评价。
数据结构哈夫曼树的实现
#include
哈工大c语言 练习题
求用户输入的两个数的商，程序运行时，以如下格式输入数据： Input two integers:4 2↙ 请改正程序中的错误，使它能得出正确的结果。 #include <> main() { int a, b, c; printf("Input two integers:"); scanf("%d,%d", &a, &b); c = a\b; 、 printf("The quotient of a and b is :%d", c); } # include <> int main () { int a,b,c; printf ("Input two integers:"); scanf ("%d %d",&a,&b); c=a/b; printf ("The quotient of a and b is :%d\n",c); > return 0; } 使用const常量定义圆周率pi=，编程从键盘输入圆的半径r，计算并输出圆的周长和面积。输出的数据保留两位小数点。 输入格式要求："%lf" 提示信息："Input r:" 输出格式要求： "printf WITHOUT width or precision specifications:\n" "circumference = %f, area = %f\n" "printf WITH width and precision specifications:\n" ~ "circumference = %, area = %\n" 程序运行示例如下： Input r:printf WITHOUT width or precision specifications: circumference = , area = printf WITH width and precision specifications: circumference = , area = #include <> int main() ~ { const double PI=; double r; printf("Input r:"); scanf("%lf", &r); printf("printf WITHOUT width or precision specifications:\n"); printf("circumference = %f, area = %f\n",2*PI*r,PI*r*r); printf("printf WITH width and precision specifications:\n"); printf("circumference = %, area = %\n",2*PI*r,PI*r*r); return 0; | } 写一个程序，将接收的华氏温度转换为对应的摄氏温度。程序应显示如下的提示信息: Please input fahr: 然后输入一个十进制数并回车，然后程序以合适的消息形式输出转换后的华氏温度。程序使用如下的公式完成转换：摄氏温度= *（华氏温度–）/ 输入格式要求："%lf" 提示信息："Please input fahr: " 输出格式要求："The cels is: %.2f" #include <> | #include <> int main() { double f; double c;
构建哈夫曼树及输出哈夫曼代码及算法思想
哈夫曼树描述文档 一、思路 通过一个argv[]数组存储从test文件中读取字母，然后利用ascal 码循环计算每个字母的权值，利用weight[]是否为零，确定叶子节点，节点个数为count，传入到构建哈夫曼树的子程序中，然后利用cd[]数组存储每一个叶子节点的哈夫曼代码.输出代码时，通过与argv[]数组的比对，扫描ht数组，进而读出所有的数据。 二、截图 三、代码 #include
intrchild; }HTNode; typedefstruct { char cd[50]; int start; }HCode; using namespace std; int enter(char argv[])//进行读入操作 { fstream in; ofstream out; char c; int number=0;//字母个数置为0 in.open("test.txt",ios::in); //打开文件test.txt out.open ("code.txt",ios::trunc); //打开文件code.txt，如果不存在就新建一个，如果存在就清空 if(!in.eof()) in>>c; //从test.txt中读取一个字符存入c printf("原文本是:\n"); while(! in.eof()){ //文件不为空，循环读取一个字符 cout<
哈夫曼树的实验报告1
一、需求分析 1、本演示程序实现Haffman编/译码器的作用，目的是为信息收发站提供一个编/译系统， 从而使信息收发站利用Haffman编码进行通讯，力求达到提高信道利用率，缩短时间，降低成本等目标。系统要实现的两个基本功能就是：①对需要传送的数据预先编码； ②对从接收端接收的数据进行译码； 2、本演示程序需要在终端上读入n个字符（字符型）及其权值（整形），用于建立Huffman 树,存储在文件hfmanTree.txt中；如果用户觉得不够清晰还可以打印以凹入表形式显示的Huffman树； 3、本演示程序根据建好的Huffman树，对文件的文本进行编码，结果存入文件CodeFile 中；然后利用建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中；最后在屏幕上显示代码（每行50个），同时显示对CodeFile中代码翻译后的结果； 4、本演示程序将综合使用C++和C语言； 5、测试数据： (1)教材例6-2中数据：8个字符，概率分别是0.05，0.29，0.07，0.08，0.14，0.23，0.03， 0.11，可将其的权值看为5，29，7，8，14，23，3，11 (2)用下表给出的字符集和频度的实际统计数据建立Haffman树，并实现以下报文的编码和 一、概要设计 1、设定哈夫曼树的抽象数据类型定义 ADT Huffmantree{ 数据对象：D={a i| a i∈Charset,i=1,2,3,……n,n≥0} 数据关系：R1＝{< a i-1, a i >| a i-1, a i∈D, i=2,3,……n} 基本操作： Initialization(&HT，&HC,w，n,ch) 操作结果：根据n个字符及其它们的权值w[i],建立Huffman树HT,用字符数组ch[i]作为中间存储变量，最后字符编码存到HC中； Encodeing(n) 操作结果：根据建好的Huffman树，对文件进行编码，编码结果存入到文件CodeFile 中 Decodeing(HT,n) 操作结果：根据已经编译好的包含n个字符的Huffman树HT，将文件的代码进行翻译，结果存入文件TextFile中 } ADT Huffmantree
哈夫曼树
******************* 实践教学 ******************* 兰州理工大学 计算机与通信学院 2007年春季学期 算法与数据结构课程设计 题目：赫夫曼编译码器设计 专业班级：软件工程05－1班 姓名：张龙 学号：05350507 指导教师：王燕 成绩：
目录 摘要 (1) 前言 (2) 正文 (3) 1.采用类C语言定义相关的数据类型 (3) 2.各模块的伪码算法 (7) 3.函数的调用关系图 (13) 4.调试分析 (13) 5.测试结果 (14) 6.源程序（带注释） (14) 总结 (20) 参考文献 (20) 附件Ⅰ部分源程序代码 (21)
摘要 哈夫曼编译码器主要用于通信领域，能够实现数据的快速，有效的传输。它利用哈夫曼树对数据进行编码，形成前缀编码，实现数据的有效压缩存放。然后又通过某种遍历实现译码，从而达到快速远距离通信的目的。 关键词：哈夫曼树；前缀编码；译码
前言 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。通过该题目的设计过程，可以加深理解树及二叉树的逻辑结构、存储结构，掌握树及二叉树上基本运算的实现。进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。
正文 1.采用类c语言定义相关的数据类型 （1）结构体定义 typedef struct { int weight; char ch; int parent,lchild,rchild; }HTNode,*HuffmanTree; //动态分配数组存贮哈夫曼树。 typedef struct { char ch; char *chs; }HuffmanCode; typedef struct { char ch; int weight; }sw; typedef struct { HuffmanTree HT; HuffmanCode *HC; }huf;//哈夫曼树结构体。 从HT[i-1]选择parent为零且weight最小的两个节点，分别编号为n1,n2. （2）调用函数 1）在给定权值中选择权值最小的两个节点。 void select(HTNode * HT,int n,int *n1,int *n2) { int i=1; int n3; while(HT[i].parent!=0) i++;
哈夫曼树及应用
常熟理工学院微课教学比赛教学设计 1、课程基本信息 课程名称：哈夫曼树及应用所属课程：数据结构与算法 课程所属专业：软件工程适用专业：计算机类 选用教材：严蔚敏，吴伟明编著《数据结构（C语言版）》北京：清华大学出版社，2007 主讲人：周思林时长：15分钟 所属学校：常熟理工学院所属院系：计算机科学与工程学院 2.教学背景 《数据结构与算法》课程是计算机类专业的学科基础课程，本节微课“哈夫曼树及应用”属于数据结构课程中的“树与二叉树”章节中的重点及难点。 2.1《数据结构与算法》课程简介及特点 《数据结构与算法》课程是计算机类专业的学科基础课程，同时也是计算机类专业的核心课程。课程的主要目标是使学生理解和掌握基本数据结构的概念、经典算法的思想及实现方法，具备为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法的能力。数据结构与算法课程的学习也是复杂程序设计的训练过程，通过算法设计和实践，培养学生的数据抽象和复杂程序设计能力。 《数据结构与算法》课程由线性结构、树形结构、图状结构三种逻辑结构和查找、排序算法为主体，结合应用型本科院校特点，通过实践理解和掌握基本数据结构与算法，在实践中提高学生的专业素养和专业技能。 2.2本节微课课程特点 “树与二叉树——哈夫曼树及应用”是《数据结构与算法》课程中第六章“树与二叉树”的核心内容之一，同时也是该章节的教学难点。 本节微课采用案例驱动法进行教学，调动学生的学习积极性，引导学生发现问题、思考问题、解决问题，利用形象的多媒体动画展示案例的执行过程，将哈夫曼树及编码复杂的程序结构趣味化、形象化。由发送报文问题引入课程，循序渐进的介绍哈夫曼树的概念、逻辑特性、存储结构和算法实现，使学生掌握哈夫曼树及编码的基本概念和算法，提升学生的程序设计及逻辑思维能力。 3.教学设计 3.1教学目的 通过本节微课的学习，培养学生以下几个方面的能力： （1）理解哈夫曼树的应用范围和场景，并能灵活运用； （2）掌握哈夫曼树及编码的概念、求解算法基本思想，针对实例，能构造哈夫曼树，求解哈夫
哈夫曼树建立、哈夫曼编码算法的实现
#include
if((*ht)[i].weight < (*ht)[min].weight) min = i; } } *s2 = min; } void CrtHuffmanTree(HuffmanTree *ht , int *w, int n) { /* w存放已知的n个权值，构造哈夫曼树ht */ int m,i; int s1,s2; m=2*n-1; *ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/ for(i=1;i<=n;i++) {/*1-n号放叶子结点，初始化*/ (*ht)[i].weight = w[i]; (*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; } /*非叶子结点初始化*/ /* ------------初始化完毕！对应算法步骤1---------*/ 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) {
哈夫曼树课程设计报告(DOC)
课程设计 题目：哈夫曼编码器 院系： 专业班级： 学号： 学生姓名： 指导教师： 2014年1月2日
课程设计需求分析报告 一、分析问题和确定解决方案 1.分析问题 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统,为这样的信息收发站写一个哈夫曼的编/译码系统。 2.确定解决方案 设计建立带权的哈夫曼树，确定哈夫曼树的类与成员函数，以及各函数之间的调用关系，采用动态数组的存储结构存储所需要的数据，通过不同的函数来实现编码，译码以及打印二进制编码、哈夫曼树，把不同的数据存入不同的txt文件中，通过主函数调用来实现功能检测。 3.输入的形式和输入值的范围 手动或者从文本中读入数据的形式初始化哈夫曼树，从键盘中或者文件中读入数据，以字母A-Z代表结点，以自然数代表权值，字符串提示使用者所要执行的操作。 4.输出的形式 在显示器界面上或者以文本的形式来实现程序调试的输出。 5.程序所能达到的功能 (1)初始化。手动输入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件WritehfmTree中,输出哈夫曼树及各字符对应的编码存于WritehfmCode;从文本中读入字符，建立哈夫曼树存于ReadhfmTree, 输出哈夫曼树及各字符对应的编码存于ReadhfmCode. (2)编码。手动输入一串大写英文字符，该字符存于WriteToBeTron中，对字符进行编码并将它存于WriteCodeFile中；从文件中读取字符编码并存于ReadCodeFile中。 (3)印代码文件。将文件ReadCodeFile以紧凑格式显示在终端上，每行50个代码。同时将
哈夫曼算法的实现及应用
摘要：哈夫曼树是带权路径长度（WPL）最小的二叉树，通过对哈夫曼算法的研究，提出一种求取哈夫曼树带权路径长度的计算方法和应用。 关键词：哈夫曼算法、二叉树、WPL、编码 1 引言： 哈夫曼树是一种特殊的二叉树，又称最优二叉树：假设有一组（无序）实数｛w1,w2,w3,w4,…,wm｝，现要构造一棵以wi（i=1，2，3，4…，m）为权的m个外部结点的扩充二叉树，使得带权的外部路径长度WPL最小。满足这一要求的扩充二叉树就称为哈夫曼树或最优二叉树。若l表示从根到第i个外部结点的路径长度，m为外部结点的个数，wi 为第i个外部结点的权值，则有WPL=∑wili（0