哈夫曼树c++实现代码
哈夫曼树及其应用(完美版)
数据结构课程设计设计题目：哈夫曼树及其应用 学院：计算机科学与技术 专业：网络工程 班级：网络 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.求每个字符的哈夫曼编码并显示。
实验六 哈夫曼树及哈夫曼编码
#include 数据结构课程设计设计题目：哈夫曼树编码译码 目录 第一章需求分析 (1) 第二章设计要求 (1) 第三章概要设计 (2) （1）其主要流程图如图1-1所示。 (3) （2）设计包含的几个方面 (4) 第四章详细设计 (4) （1）①哈夫曼树的存储结构描述为： (4) （2）哈弗曼编码 (5) （3）哈弗曼译码 (7) （4）主函数 (8) （5）显示部分源程序： (8) 第五章调试结果 (10) 第六章心得体会 (12) 第七章参考文献 (12) 附录： (12) 在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈弗曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。 第二章设计要求 对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，∑WiLi 恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。设计实现的功能： (1) 哈夫曼树的建立； (2) 哈夫曼编码的生成； (3) 编码文件的译码。 目录 一、摘要 (3) 二、题目 (3) 三、实验目的 (3) 四、实验原理 (3) 五、需求分析 (4) 5.1实验要求 (4) 5.2实验内容 (4) 六、概要设计 (4) 6.1所实现的功能函数 (4) 6.2主函数 (5) 6.3 系统结构图 (6) 七、详细设计和编码 (6) 八、运行结果 (12) 九、总结 (15) 9.1调试分析 (15) 9.2 心得体会 (15) 参考文献 (16) 一、摘要 二、题目 哈夫曼树的编码与译码 三、实验目的 （1）熟悉对哈夫曼的应用以及构造方法，熟悉对树的构造方式的应用； （2）进一步掌握哈夫曼树的含义； （3）掌握哈夫曼树的结构特征，以及各种存储结构的特点以及使用范围； （4）熟练掌握哈夫曼树的建立和哈夫曼编码方法； （5）提高分析问题、解决问题的能力，进一步巩固数据结构各种原理与方法； （6）掌握一种计算机语言，可以进行数据算法的设计。 四、实验原理 哈夫曼（Huffman）编码属于长度可变的编码类，是哈夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成哈夫曼编码算法基于一种称为“编码树”（coding tree）的技术。算法步骤如下： （1）初始化，根据富豪概率的大小按由大到小顺序对符号进行排序； （2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和； （3）重复第（2）步，直到形成一个符号为止（树），其概率最后等于1； （4）从编码树的根开始回溯到原始的符号，并将每一下分支赋值1，上分支赋值0； 译码的过程是分解电文中字符串，从根出发，按字符“0”或者“1”确定找做孩 子或右孩子，直至叶子节点，便求得该子串相应的字符。 数据结构实验报告 实验名称：实验3——哈夫曼编码 学生姓名： 班级： 班内序号： 学号： 日期：2013年11月24日 1．实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个 字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每 个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的 字符串输出。 4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译 码，并输出译码结果。 5、打印(Print)：以直观的方式打印赫夫曼树（选作） 6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼 编码的压缩效果。 2. 程序分析 2.1存储结构： struct HNode { char c;//存字符内容 int weight; int lchild, rchild, parent; }; struct HCode { char data; char code[100]; }; //字符及其编码结构 class Huffman { private: HNode* huffTree; //Huffman树 HCode* HCodeTable; //Huffman编码表 public: Huffman(void); void CreateHTree(int a[], int n); //创建huffman树 void CreateCodeTable(char b[], int n); //创建编码表 void Encode(char *s, string *d); //编码 void Decode(char *s, char *d); //解码 void differ(char *,int n); char str2[100];//数组中不同的字符组成的串 int dif;//str2[]的大小 ~Huffman(void); }; 结点结构为如下所示： 三叉树的节点结构： struct HNode//哈夫曼树结点的结构体 { int weight;//结点权值 int parent;//双亲指针 int lchild;//左孩子指针 int rchild;//右孩子指针 char data;//字符 }; 示意图为： int weight int parent int lchild int rchild Char c 编码表节点结构： 实验四哈夫曼树与哈夫曼编码 一、实验目的 1、使学生熟练掌握哈夫曼树的生成算法。 2、熟练掌握哈夫曼编码的方法。 二、实验内容 [问题描述] 已知n个字符在原文中出现的频率，求它们的哈夫曼编码。[基本要求] 1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffman 树。（具体算法可参见教材P147的算法6.12） 2. 编码：根据建立的Huffman树，求每个字符的Huffman 编码。 对给定的待编码字符序列进行编码。 [选作内容] １. 译码：利用已经建立好的Huffman树，对上面的编码结果译码。 译码的过程是分解电文中的字符串，从根结点出发，按字符’0’和’1’确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。 4. 打印 Huffman树。 ［测试数据］ 利用教材P.148 例6－2中的数据调试程序。可设8种符号分别为A,B,C,D,E,F,G,H。编/译码序列为“CFBABBFHGH”(也可自己设定数据进行测试)。 三、算法设计 1、主要思想：******************赫夫曼树的构造 ********************** (1) 由给定的 n 个权值{w1, w2, …, wn}，构造具有 n 棵二 叉树的森林 F ={T1, T2, …, Tn }，其中每棵二叉树 Ti 只有一个带权为 wi 的根结点, 其左、右子树均为空。 (2) 在 F 中选取两棵根结点的权值最小的二叉树, 作为 左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 (3)在 F 中删去这两棵二叉树, 把新的二叉树加入F。 (4)重复(2)和(3), 直到 F 中仅剩下一棵树为止。 ****************************霍夫曼编码***************************** 主要用途是实现数据压缩。由于赫夫曼树中没有度为1的节点，则一棵有n个叶子结点的赫夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数 组中。由于在构成赫夫曼树之后，为求编码需从叶子结点出发走一条从叶子到根的路径；而为译码需从根出发走一条从根到叶子的路径。则对每个结点而言，既须知双亲的信息，又需知孩子结点的信息。 2、本程序包含三个模块 1）主函数 Int main() { 先输入结点总数； 分别输入各个结点； 调用建立哈夫曼树函数； 调用编码函数读入建立的哈夫曼树进行编码 } 3、元素类型、结点类型和指针类型 typedef struct //定义新数据类型即结点结构 #include float m1,m2; char ch,sh; FILE *fp; char filename[30]; printf("请给新文件命名:"); scanf("%s",filename); fp=fopen(filename,"w+"); n=10; float sum[10]={0}; for(i=1; i<=num; i++) { ch=rand()%10; sum[ch]++; printf("%c",ch+'0'); fprintf(fp,"%c",ch+'0');// fclose(fp); } fflush(stdin); printf("\n\n\n\n\t\t以上就是产生的所有随机数!\n\n"); printf("\t\t按回车键继续!"); scanf("%c",&sh); system("cls"); printf("\n\n\n\n\n\n\n\n\n\t\t***************** ****************************\n"); printf("\t\t* 接下来为你计算各个数字权值（请稍等）! *\n"); printf("\t\t********************************* ************"); Sleep(4*1000); fflush(stdin); //scanf("%c",&sh); system("cls"); printf("\n\n\n\n\n\n\n\n\n\t\t计算完毕!"); scanf("%c",&sh); system("cls"); printf("\t\t各数字权值如下:\n"); for(i=0;i 实验三树的应用 一.实验题目： 树的应用——哈夫曼编码 二.实验内容： 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。 要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码。 三、程序源代码: #include 中南大学 数据结构课程设计报告 题目哈夫曼编译器 学生姓名孙毅 指导教师杨希 学院信息科学与工程学院 专业班级信息安全1401班 二○一六年十一月 目录 一、课程设计目的 (3) 二、课程设计的内容 (3) 2.1、问题描述 (3) 2.2、基本要求 (3) 三、问题描述，解决的方法 (3) 3.1从键盘读入字符集大小n , 以及n个字符和权值，建立哈夫曼树。 (3) 3.2利用已建好的哈夫曼树对文件正文进行编码，将结果存入相关文件中。5 3.3利用已建好的哈夫曼树将编码文件中的代码进行译码，结果存入文件中。 (6) 3.4输出代码文件，以紧凑格式显示。 (7) 3.5以直观的方式输出哈夫曼树，同时将此字符形式的哈夫曼树写入文件中。 (7) 四、程序模块功能，程序设计组成框图、流程图 (8) 4.1程序模块功能 (8) 4.2程序设计框图 (8) 4.3流程图 (9) 五、调试与测试。调试方法，测试结果的分析与讨论，遇到的主要问题及采取的解决措施。 (10) 5.1调试方面 (10) 5.2测试结果方面 (10) 六、测试结果，用几组测试数据进行测试算法设计的正确性 (10) 6.1第一组数据如下 (10) 6.2第二组测试数据如下： (14) 七、本次课程设计的心得体会 (16) 八、附录：源程序清单 (17) 一、课程设计目的 数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术基础，实践性强，课程设计是加强学生实践能力的一个重要手段。课程设计要求学生在完成程序设计的同时能够写出规范的设计报告，培养学生分析问题、解决问题，提高学生软件设计能力。 二、课程设计的内容 哈夫曼编译器 2.1、问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码。对于双向传输信息的信道，每端都需要一个完整的编译码系统。为这样的信息收发站编写哈夫曼编译系统。 2.2、基本要求 (1)从键盘读入字符集大小n , 以及n个字符和权值，建立哈夫曼树。 (2)利用已建好的哈夫曼树对文件正文进行编码，将结果存入相关文件中。 (3)利用已建好的哈夫曼树将编码文件中的代码进行译码，结果存入文件中。 (4)输出代码文件，以紧凑格式显示。 (5)以直观的方式输出哈夫曼树，同时将此字符形式的哈夫曼树写入文件中。 三、问题描述，解决的方法 3.1从键盘读入字符集大小n , 以及n个字符和权值，建立哈夫曼树。 a.首先设计一个结构体，成员有权值、左右儿子、以及字符本身，再设计一个输入函数，函数中要求输入字符集大小n，以及这n个字符和他们各自对应的权值。 #include 霍夫曼编码 霍夫曼编码(Huffman Coding)是一种编码方法，霍夫曼编码是可变字长编码(VLC)的一种。1952年，David A. Huffman在麻省理工攻读博士时所提出一种编码方法，并发表于《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。 该方法完全依据字符出现概率来构造异字头的平均长度最短的 码字，有时称之为最佳编码，一般就叫作Huffman编码。 在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。1951年，霍夫曼和他 在MIT信息论的同学需要选择是完成学期报告还是期末考试。 导师Robert M. Fano给他们的学期报告的题目是，查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者克劳德·香农共同研究过类似编码的导师。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。 霍夫曼（Huffman）编码是一种统计编码。属于无损（lossless）压缩编码。 以霍夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 ←根据给定数据集中各元素所出现的频率来压缩数据的 一种统计压缩编码方法。这些元素(如字母)出现的次数越 多，其编码的位数就越少。 ←广泛用在JPEG, MPEG, H.2X等各种信息编码标准中。霍夫曼编码的步骤 霍夫曼编码的具体步骤如下： １）将信源符号的概率按减小的顺序排队。 ２）把两个最小的概率相加，并继续这一步骤，始终将较高的概率分支放在上部，直到最后变成概率１。 3）将每对组合的上边一个指定为1，下边一个指定为0（或相反）。４）画出由概率１处到每个信源符号的路径，顺序记下沿路径的０和１，所得就是该符号的霍夫曼码字。 信源熵的定义： 概率空间中每个事件所含有的自信息量的数学期望称信源熵或简称熵(entropy)，记为： 例：现有一个由5个不同符号组成的30个符号的字 符串：BABACACADADABBCBABEBEDDABEEEBB 计算 (1) 该字符串的霍夫曼码 (2) 该字符串的熵 (3) 该字符串的平均码长 /******************************************/ /********* 哈夫曼树的编写与输出***********/ /******************************************/ /*用静态三叉链表实现哈夫曼树类型定义如下：*/ #define N 20 #define M 2*N-1 typedef struct { int weight; int parent; int LChild; int RChild; } HTNode,HuffmanTree[M+1]; /*select函数主体程序代码*/ void select(HuffmanTree ht,int j,& s1,& s2 ) { int i,k; int n=0; HuffmanTree rt; for(k=0;k<=j;k++) { if(ht[k].parent ==0) { rt[k]=ht[k]; n=n+1; } } for(k=0;k int m; m=2*n-1; for(i=n+1;i<=m;i++) { ht[i]={0,0,0,0}; } /*--------初始化完毕，对应算法步鄹(1)---------*/ for(i=n+1;i<=m;i++) { int s1,s2; select(ht,i-1,&s1,$s2); ht[i].weight=ht[s1].weight +ht[s2].weight ; ht[s1].parent=i;ht[s2].parent=i; ht[i].LChild=s1;ht[i].RChild=s2; } } #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) { 1.问题描述 哈弗曼树的编码与译码 —功能：实现对任何类型文件的压缩与解码 —输入：源文件，压缩文件 —输出：解码正确性判定，统计压缩率、编码与解码速度 —要求：使用边编码边统计符号概率的方法（自适应Huffman编码）和事先统计概率的方法（静态Huffman编码） 2.1程序清单 程序书签： 1.main函数 2.压缩函数 3.select函数 4.encode函数 5.解压函数 #include long weight; //权值 unsigned char ch;//字符 int parent,lchild,rchild; char code[256];//编码的位数最多为256位int CodeLength;//编码长度 }hfmnode[512]; void compress(); void uncompress(); //主函数 void main() { int choice; printf("请选择1~3：\n"); printf("1.压缩文件\n"); printf("2.解压文件\n"); printf("3.退出！\n"); scanf("%d",&choice); if(choice==1)compress(); else if(choice==2)uncompress(); else if(choice==3)return; else printf("输入错误！"); } 一、需求分析 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 //注意：在输入n个权值时，每输入一个权值都要按一个回车键 #include"iostream" #include"stdlib.h" #include"stdio.h" #include"malloc.h" #include"string.h" using namespace std; #define UNIT_MAX 65535 typedef struct TNode { int parent; unsigned int weight; unsigned int lchild; unsigned int rchild; } *HuffmanTree, HTNode; typedef char **HuffmanCode; int select(HuffmanTree t, int i)//返回根节点中权值最小的树的根节点的序号函数select（）调用{ int j; int find=0; int k = UNIT_MAX;//取K为不小于可能的值 for (j = 1; j < i; j++) //在t数组的前i-1个数组元素中寻找一个parent值为0且权值最小的if ((int)t[j].weight < k && t[j].parent == 0) { k = t[j].weight; find=j; } t[find].parent = 1; return find; } char** HuffmanCoding(HTNode HT[], char* HC[], int w[], int n) { //w存放n个字符的权值的一维数组，n为叶子个数；构造哈夫曼树HT；HC数组用以存放求得的n个字符的编码 int m, i, s1, s2, start; int c, f; HuffmanTree p; char* cd; m = 2 * n - 1; //n即为叶子数n0,由二叉树性质,n0=n2+1,故树中结点数为*n-1 for (i = 1, p = HT + 1; i <= n; ++i, ++p, ++w) {//n个叶子结点赋初值，n个叶子最初为n个根结点，p指向HT[1],HT[0]不用(*p).weight = *w; (*p).parent = 0; (*p).lchild = 0; (*p).rchild = 0; } for (i=n+1; i <= m; i++, p++) //n-1个附加的父亲结点赋初值 { (*p).weight = 0; (*p).parent = 0; (*p).lchild = 0; (*p).rchild = 0; 实验四哈夫曼树与哈夫曼编码 一、实验内容 [问题描述] 已知n个字符在原文中出现的频率，求它们的哈夫曼编码。[基本要求] 1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffman 树。（具体算法可参见教材P147的算法6.12） 2. 编码：根据建立的Huffman树，求每个字符的Huffman 编码。 对给定的待编码字符序列进行编码。 二、概要设计 算法设计： 要是实现哈夫曼树的操作，首先创建一个哈夫曼树，在创建哈夫曼树的时候，对哈夫曼树的叶子和非叶子结点进行初始化，而在建立哈夫曼树时，最难的该是选择权值最小的两个顶点，然后两个结点的权值和作为新的权值，再选择两个权值最小的作为新的两个结点创建一个小的二叉树的子树；创建哈夫曼树后，进行编码，在编码过程中，先找到根，然后遍历，左孩子用0标记，右孩子用1标记，最后将编码好的哈夫曼树进行输出，就可以知道哈夫曼树的编码了。 流程图： 算法： 模块： 在分析了实验要求和算法分析之后，将程序分为四个功能函数，分别如下： 首先建立一个哈夫曼树和哈夫曼编码的存储表示： typedef struct { int weight; int parent,lchild,rchild; char elem; }HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树 typedef char **HuffmanCode;//动态分配数组存储赫夫曼编码表CrtHuffmanTree(HuffmanTree *ht , int *w, int n)：w存放n个字符的权值，构造哈夫曼树HT。先将叶子初始化，再将非叶子结点初始化，然后构造哈夫曼树。 构造哈夫曼树： for(i=n+1;i<=m;++i) {//在HT[1……i]选择parent为0且weight最小的两个Select(HT,i-1,&s1,&s2); 1）内容： 利用 Huffman 编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低 传输成本。但是，这要求在发送端通过一个编码系统对待传数据进行预先编码，在 接收端进行解码。对于双工信道（即可以双向传输信息的信道），每端都需要一个 完整的编/解码系统。 2）要求： 一个完整的huffman编解码系统应该具有以下功能： 初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建 立Huffman 树，并将它存入hfmTree 中。 编码（Encoding）。利用已经建好的Huffman树（如果不在内存，则应从文件hfmTree 中读取），对文件ToBeTran中的正文进行编码，然后将结果存入文件hfmTree中读取），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 解码（Decoding）。利用已经建立好的Huffman树将文件CodeFile中的代码进行解码， 结果存入TextFile中。 打印代码文件（Print）。将文件CodeFile以紧凑的格式显示在终端上，每行 50 个 代码。同时将此字符形式的编码文件写入文件CodePrint中。 打印Huffman树（Tree Printing）。将已经在内存中的Huffman树以直观的形式（树或者凹入的形式）显示在终端上，同时将此字符形式的Huffman 树写入文件TreePrint中。 3) 测试数据: 用下表给出的字符集和频度的实际统计数据建立Huffman树，并对以下报文进行编码和译码：“THIS PROGRAM IS MY FAVORITE”。 完整代码如下： #include 常熟理工学院微课教学比赛教学设计 1、课程基本信息 课程名称：哈夫曼树及应用所属课程：数据结构与算法 课程所属专业：软件工程适用专业：计算机类 选用教材：严蔚敏，吴伟明编著《数据结构（C语言版）》北京：清华大学出版社，2007 主讲人：周思林时长：15分钟 所属学校：常熟理工学院所属院系：计算机科学与工程学院 2.教学背景 《数据结构与算法》课程是计算机类专业的学科基础课程，本节微课“哈夫曼树及应用”属于数据结构课程中的“树与二叉树”章节中的重点及难点。 2.1《数据结构与算法》课程简介及特点 《数据结构与算法》课程是计算机类专业的学科基础课程，同时也是计算机类专业的核心课程。课程的主要目标是使学生理解和掌握基本数据结构的概念、经典算法的思想及实现方法，具备为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法的能力。数据结构与算法课程的学习也是复杂程序设计的训练过程，通过算法设计和实践，培养学生的数据抽象和复杂程序设计能力。 《数据结构与算法》课程由线性结构、树形结构、图状结构三种逻辑结构和查找、排序算法为主体，结合应用型本科院校特点，通过实践理解和掌握基本数据结构与算法，在实践中提高学生的专业素养和专业技能。 2.2本节微课课程特点 “树与二叉树——哈夫曼树及应用”是《数据结构与算法》课程中第六章“树与二叉树”的核心内容之一，同时也是该章节的教学难点。 本节微课采用案例驱动法进行教学，调动学生的学习积极性，引导学生发现问题、思考问题、解决问题，利用形象的多媒体动画展示案例的执行过程，将哈夫曼树及编码复杂的程序结构趣味化、形象化。由发送报文问题引入课程，循序渐进的介绍哈夫曼树的概念、逻辑特性、存储结构和算法实现，使学生掌握哈夫曼树及编码的基本概念和算法，提升学生的程序设计及逻辑思维能力。 3.教学设计 3.1教学目的 通过本节微课的学习，培养学生以下几个方面的能力： （1）理解哈夫曼树的应用范围和场景，并能灵活运用； （2）掌握哈夫曼树及编码的概念、求解算法基本思想，针对实例，能构造哈夫曼树，求解哈夫哈夫曼树编码译码实验报告(DOC)
哈夫曼树的编码与译码
北邮数据结构实验3哈夫曼编码
实验四 哈夫曼树与哈夫曼编码
哈夫曼树源代码
哈夫曼编码算法实现完整版
数据结构课设报告+哈夫曼编译器+C语言+源码
数据结构哈夫曼树的实现
霍夫曼编码
哈夫曼树的编写与输出
哈夫曼树建立、哈夫曼编码算法的实现
哈夫曼树与文件解压压缩C言代码
哈夫曼树的实验报告1
(在VC++上调试通过)哈夫曼树编码上机实验
实验四 哈夫曼树与哈夫曼编码
哈夫曼编解码 完整c程序代码
哈夫曼树及应用
相关文档
- 哈夫曼编解码 完整c程序代码
- 实验6：哈夫曼树及哈夫曼编码的算法实现 - 副本
- 哈夫曼编解码 完整c程序代码
- 构造哈夫曼树并求哈夫曼编码的算法实现
- 哈夫曼编码和译码系统(附源代码)
- 哈夫曼树编码译码实验报告(DOC)
- 哈夫曼树和哈夫曼编码(数据结构程序设计)
- 哈夫曼树构造编码译码源程序
- 哈夫曼编码译码器源代码
- 赫夫曼树实验报告材料(含源程序)
- 哈夫曼树与文件解压压缩C言代码
- 霍夫曼编码+详细源代码及注释
- 数据结构哈夫曼编码(源代码)
- 哈夫曼树编码实验报告
- 基于哈夫曼树与哈夫曼编码的数据压缩
- 哈夫曼树的构造及其在信息编码中的应用
- 哈夫曼树编码译码源代码及测试文件
- 哈夫曼树编码实验报告
- 霍夫曼编码(含源程序)
- 数据结构课设报告+哈夫曼编译器+C语言+源码