数据结构程序设计作业——《哈夫曼编码》

《数据构造与算法》课程设计（/第二学期第20周）指引教师：王教师班级：计算机科学与技术（3）班学号：姓名：《数据构造与算法》课程设计目录一、前言1．摘要2．《数据构造与算法》课程设计任务书二、实验目三、题目--赫夫曼编码/译码器1．问题描述2．基本规定3．测试规定4．实现提示四、需求分析--详细规定五、概要设计六、程序阐明七、详细设计八、实验心得与体会前言1．摘要随着计算机普遍应用与日益发展，其应用早已不局限于简朴数值运算，而涉及到问题分析、数据构造框架设计以及设计最短路线等复杂非数值解决和操作。

算法与数据构造学习就是为后来运用计算机资源高效地开发非数值解决计算机程序打下坚实理论、办法和技术基本。

算法与数据构造旨在分析研究计算机加工数据对象特性，以便选取恰当数据构造和存储构造，从而使建立在其上解决问题算法达到最优。

数据构造是在整个计算机科学与技术领域上广泛被使用术语。

它用来反映一种数据内部构成，即一种数据由那些成分数据构成，以什么方式构成，呈什么构造。

数据构造有逻辑上数据构造和物理上数据构造之分。

逻辑上数据构造反映成分数据之间逻辑关系，而物理上数据构造反映成分数据在计算机内部存储安排。

数据构造是数据存在形式。

《数据构造》重要简介某些最惯用数据构造，阐明各种数据构造内在逻辑关系，讨论其在计算机中存储表达，以及在其上进行各种运算时实现算法，并对算法效率进行简朴分析和讨论。

数据构造是介于数学、计算机软件和计算机硬件之间一门计算机专业核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等重要基本，广泛应用于信息学、系统工程等各种领域。

学习数据构造是为了将实际问题中所涉及对象在计算机中表达出来并对它们进行解决。

通过课程设计可以提高学生思维能力，增进学生综合应用能力和专业素质提高。

2．《数据构造与算法》课程设计任务书《数据构造与算法》是计算机专业重要核心课程之一，在计算机专业学习过程中占有非常重要地位。

数据结构实验报告实验名称：实验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 编码表节点结构：struct HCode//编码表结构体{char data;//字符char code[100];//编码内容};示意图为：基本结构体记录字符和出现次数:struct node{int num;char data;};示意图为:2.关键算法分析(1).初始化:伪代码：1.输入需要编译的文本内容2.将输入的内容保存到数组str1中3.统计出现的字符数目,并且保存到变量count中4.统计出现的不同的字符，存到str2中，将str2的大小存到dif中时间复杂度O(n！)（2）.创建哈夫曼树算法伪代码：1.创建一个长度为2*n-1的三叉链表2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前n个结点的data域，并将对应结点的孩子域和双亲域赋为空3.从三叉链表的第n个结点开始，3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下标x,y。

Main.c文件如下#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include "Haffman.h"#define MaxBit 100void main(void){ Code *d;int i,j,n=26,m,weight[26]={0};char c,a=97;FILE *fp; //文本文件指针if((fp=fopen("data.txt","r"))==NULL){printf("无法打开此文件\n");exit(0); //中止程序}printf("待压缩的英文文本文件为:\n");while(!feof(fp)) //当扫描文件内容没有结束时{//读取字符并统计每个字符次数c=fgetc(fp);putchar(c);if(c>='a'||c<='z');c=c-32;for (i=65;i<=90;i++)if(c==i)weight[i-65]++ ;}fclose(fp);HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*n-1));Code *myHaffCode=(Code *)malloc(sizeof(Code)*n);Haffman(weight,n,myHaffTree);HaffmanCode(myHaffTree,n,myHaffCode);for(m=0;m<n;m++){printf("\nzimu=%c Weight=%d Code=",a++,myHaffCode[m].weight);for(j=myHaffCode[m].start;j<n;j++)printf("%d",myHaffCode[m].bit[j]);printf("\n");}}头文件Huffman.h如下#ifndef Haffman_H_INCLUDED#define Haffman_H_INCLUDED#define MaxN 300#define MaxValue 10000typedef struct{int weight; //权值int flag; //标记int parent; //双亲结点下标int leftChild; //左孩子下标int rightChild; //右孩子下标}HaffNode; //哈夫曼树的结点结构typedef struct{int bit[MaxN]; //数组int start; //编码的起始下标int weight; //字符的权值}Code; //哈弗曼编码的结构void Haffman(int weight[],int n,HaffNode haffTree[])//建立叶节点个数为n，权值数组为weight的哈弗曼树haffTree{int i,j,m1,m2,x1,x2;//哈夫曼树haffTree初始化，n个叶节点的二叉树共有2n-1个结点for(i=0;i<2*n-1;i++){if(i<n) haffTree[i].weight=weight[i];else haffTree[i].weight=0;haffTree[i].parent=-1;haffTree[i].flag=0;haffTree[i].leftChild=-1;haffTree[i].rightChild=-1;}//构造哈弗曼树的n-1个非叶节点for(i=0;i<n-1;i++){m1=m2=MaxValue;x1=x2=0;for(j=0;j<n+i;j++) //找出权值最小和次小的子树{if((haffTree[j].weight<m1) && (haffTree[j].flag==0)){m2=m1;x2=x1;m1=haffTree[j].weight;x1=j;}else if((haffTree[j].weight<m2) && (haffTree[j].flag==0)){m2=haffTree[j].weight;x2=j;}}//将找出两棵权值最小和次小的子树合并为一棵子树haffTree[x1].parent=n+i;haffTree[x2].parent=n+i;haffTree[x1].flag=1;haffTree[x2].flag=1;haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;haffTree[n+i].leftChild= x1;haffTree[n+i].rightChild=x2;}}void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[])//由n个结点的哈夫曼树构造哈弗曼编码{Code *cd=(Code *)malloc(sizeof(Code));int i,j,child,parent;//求n个叶节点的哈弗曼编码for(i=0;i<n;i++){cd->start=n-1; //不等长编码的最后一位n-1cd->weight=haffTree[i].weight; //取得编码对应权值child=i;parent=haffTree[child].parent;//由叶节点向上直到根节点while(parent!=-1){if(haffTree[parent].leftChild==child)cd->bit[cd->start]=0; //左孩子分支编码0elsecd->bit[cd->start]=1; //左孩子分支编码1cd->start--;child=parent;parent=haffTree[child].parent;}for(j=cd->start+1;j<n;j++)haffCode[i].bit[j]=cd->bit[j]; //保存每个叶节点编码haffCode[i].start=cd->start+1; //保存叶节点编码的起始位haffCode[i].weight=cd->weight; //保存编码对应权值}}#endif // HFM_H_INCLUDED。

学号数据结构课程设计设计说明书哈夫曼编码起止日期：2011年12月12 日至2011 年12月16日学生姓名班级成绩指导教师(签字)电子与信息工程系2011年12月16日一、设计目的 (3)二、设计要求 (3)三、设计内容 (3)一、需求分析 (3)1.构造哈夫曼树的方法如下： (3)2.程序实现的功能 (4)二、问题求解 (4)三、总体设计 (5)1.程序设计组成框图: (5)2.流程图： (6)四、详细设计 (6)1. 构造结点的结构体 (6)2. 构造哈夫曼树 (6)3. 求哈夫曼编码 (6)五、调试与测试 (7)1.测试过程中遇到的主要问题 (7)六、关键源程序清单和执行结果 (7)1.源代码： (7)2.执行结果： (10)四、参考文献 (11)天津城市建设学院课程设计任务书2011—2012学年第1学期电子与信息工程系软件工程专业班级课程设计名称：数据结构课程设计设计题目：哈夫曼编码完成期限：自2011 年12 月12 日至2011 年12 月16 日共 1 周设计依据、要求及主要内容（可另加附页）：一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。

二、设计要求（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。

凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；（4）认真编写课程设计报告。

三、设计内容一、需求分析1.构造哈夫曼编码的方法如下：第一步定义一个结点的结构体，包括结点的权值，结点的双亲结点，左孩子，右孩子。

并定义两个HTNode,*HuffmanTree为该类型的名字。

第二步创建一个Select函数用来选择结点较小的结点权值和下标。

数据结构设计性实验Huffman编码与译码学号姓名班级设计性实验—Huffman 编码与译码一．实验目的：在掌握相关基础知识的基础上，学会自己设计实验算法，熟练掌握Huffman 树的建立方法，Huffman 编码的方法，进而设计出Huffman 译码算法，并编程实现。

二．实验要求：在6学时以内，制作出能够实现基于26个英文字母的任意字符串的编译码。

写出技术工作报告并附源程序。

三．实验内容及任务：1．设字符集为26个英文字母，其出现频度如下表所示。

2．建Huffman 树； 3．利用所建Huffman 树对任一字符串文件进行编码——即设计一个Huffman 编码器；4．对任一字符串文件的编码进行译码——即设计一个Huffman 译码器。

实现步骤：1．数据存储结构设计； 2．操作模块设计； 3．建树算法设计； 4．编码器设计；5． 译码器设计；51 48 1 15 63 57 20 32 5 1频度z y x w v u t 字符11611882380频度p 21 f q15 g r 47 h s o n m l k j 字符 57 103 32 22 13 64 186 频度 i e d c b a 空格 字符四．分析以及算法描述1.分析问题1)首先学习二叉树的知识，了解二叉树的路径、权数以及带权路径长度计算。

2)认识霍夫曼树，了解霍夫曼树的定义，构造霍夫曼树构造算法①又给定的n个权值{w1，w2，w3，……，w n}构造根节点的二叉树，从而得到一个二叉树森林F={T1，T2，T3，……T n}。

②在二叉树森里选取根节点全职最小和此最小的两棵二叉树作为左右节点构造新的二叉树，此时新的二叉树的根节点权值为左右子树权值之和。

③在二叉树森林中删除作为新二叉树的根节点左右子树的两棵二叉树，将新的二叉树加入到二叉树森林F中。

④重复②和③，当二叉树森林F只剩下一棵二叉树时，这棵二叉树是所构造的霍夫曼树。

3)练习通过普通树来构造霍夫曼树。

目录目录 (1)1 课程设计的目的和意义 (3)2 需求分析 (5)3 系统设计 (6)（1)设计思路及方案 (6)（2)模块的设计及介绍 (6)(3)主要模块程序流程图 (9)4 系统实现 (14)（1）主调函数 (14)(2)建立HuffmanTree (14)(3）生成Huffman编码并写入文件 (18)（4)电文译码 (19)5 系统调试 (22)小结 (25)参考文献 (26)附录源程序 (27)1 课程设计的目的和意义在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。

哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。

树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0"码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1"的序列作为和各个对应的字符的编码，这就是哈夫曼编码。

通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。

电报通信是传递文字的二进制码形式的字符串。

但在信息传递时,总希望总长度尽可能最短，即采用最短码。

作为软件工程专业的学生，我们应该很好的掌握这门技术。

在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。

在课程设计过程中,我们每个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。

这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。

在课程设计过程中,我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。

更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见.同时,师生之间的互动也随之改善，我们可以通过具体的实例来从老师那学到更多的实用的知识。

数据结构课程设计报告题目：赫夫曼编码一、需求分析1. 问题描述利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。

对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。

试为这样的信息收发站编写一个赫夫曼码的编/译码系统。

2.基本要求一个完整的系统应具有以下功能：(1) I：初始化（Initialization）。

从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。

(2) E：编码（Encoding）。

利用已建好的赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

(3) D：译码（Decoding）。

利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。

(4) P：印代码文件（Print）。

将文件CodeFile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件CodePrin中。

(5) T：印赫夫曼树（Tree printing）。

将已在内存中的赫夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的赫夫曼树写入文件TreePrint 中。

3.测试要求(1) 已知某系统在通信联络中只可能出现八种字符，其频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，试设计赫夫曼编码。

(2) 用下表给出的字符集和频度的实际统计数据建立赫夫曼树，并实现以下报文的编码和译码：“THIS PROGRAME IS MY FA VORITE”。

4.实现提示(1) 编码结果以文本方式存储在文件Codefile中。

(2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。

数据结构哈夫曼编码实验报告数据结构哈夫曼编码实验报告实验背景哈夫曼编码是一种常用的数据压缩方法，通过使用变长编码来表示不同符号，将出现频率较高的符号用较短的编码表示，从而达到压缩数据的目的。

通过实现哈夫曼编码算法，我们能够更好地理解和掌握数据结构中的树形结构。

实验目的1. 理解哈夫曼编码的原理及实现过程。

2. 掌握数据结构中树的基本操作。

3. 进一步熟悉编程语言的使用。

实验过程1. 构建哈夫曼树首先，我们需要根据给定的字符频率表构建哈夫曼树。

哈夫曼树是一种特殊的二叉树，其叶子节点表示字符，而非叶子节点表示字符的编码。

构建哈夫曼树的过程如下：1. 根据给定的字符频率表，将每个字符视为一个节点，并按照频率从小到大的顺序排列。

2. 将频率最小的两个节点合并为一个新节点，并将其频率设置为两个节点的频率之和。

这个新节点成为新的子树的根节点。

3. 将新节点插入到原来的节点列表中，并继续按照频率从小到大的顺序排序。

4. 重复步骤2和步骤3，直到只剩下一个节点，这个节点即为哈夫曼树的根节点。

2. 哈夫曼编码表在构建完哈夫曼树后，我们需要根据哈夫曼树每个字符的哈夫曼编码表。

哈夫曼编码表是一个字典，用于存储每个字符对应的编码。

哈夫曼编码表的过程如下：1. 从哈夫曼树的根节点出发，遍历整个树。

2. 在遍历的过程中，维护一个路径，用于记录到达每个字符节点的路径，0表示左子树，1表示右子树。

3. 当到达一个字符节点时，将路径上的编码存储到哈夫曼编码表中对应的字符键下。

3. 压缩数据有了哈夫曼编码表后，我们可以使用哈夫曼编码对数据进行压缩。

将原本以字符表示的数据，转换为使用哈夫曼编码表示的二进制数据。

压缩数据的过程如下：1. 将待压缩的数据转换为对应的哈夫曼编码，将所有的编码连接成一个字符串。

2. 将该字符串表示的二进制数据存储到文件中，同时需要保存哈夫曼编码表以便解压时使用。

实验结果通过实验，我们成功实现了哈夫曼编码的构建和使用。

数据结构实验报告题目哈夫曼编码学生姓名王某某专业班级测控120X班学号U2012XXXXX1 问题描述输入一字符串，以字符串中各字符出现的频数为权值构造哈夫曼编码。

然后输入一0—1序列，根据生成的哈夫曼编码解码序列。

2 算法描述（1）哈夫曼树的表示设计哈夫曼树的结构体（htnode），其中包含权重、左右孩子、父母和要编码的字符。

用这个结构体（htnode）定义个哈夫曼数组（hfmt[]）。

迷宫定义如下：typedef struct{int weight;int lchild;int rchild;int parent;char key;}htnode;typedef htnode hfmt[MAXLEN];（2）对原始字符进行编码初始化哈夫曼树（inithfmt）。

从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。

并显示出每个字符的编码。

1.void inithfmt(hfmt t)//对结构体进行初始化2.void inputweight(hfmt t)//输入函数3.void selectmin(hfmt t,int i,int *p1,int *p2)//选中两个权值最小的函数4.void creathfmt(hfmt t)//创建哈夫曼树的函数5.void phfmnode(hfmt t)//对字符进行初始编码（3）对用户输入的字符进行编码void encoding(hfmt t)//对用户输入的电文进行编码{char r[1000];//用来存储输入的字符串int i,j;printf("\n\n请输入需要编码的字符:");gets(r);printf("编码结果为:");for(j=0;r[j]!='\0';j++)for(i=0;i<n;i++)if(r[j]==t[i].key)hfmtpath(t,i,j);printf("\n");}（4）对用户输入的字符进行编码void decoding(hfmt t)//对用户输入的密文进行译码{char r[100];int i,j,len;j=2*n-2;//j初始从树的根节点开始printf("\n\n请输入需要译码的字符串:"); gets(r);len=strlen(r);printf("译码的结果是:");for(i=0;i<len;i++){if(r[i]=='0'){j=t[j].lchild;if(t[j].lchild==-1){printf("%c",t[j].key);j=2*n-2;}}else if(r[i]=='1'){j=t[j].rchild;if(t[j].rchild==-1){printf("%c",t[j].key); j=2*n-2;}}}printf("\n\n");}3 程序设计流程图4 运行测试1.用户输入字符串，以回车键作为结束2.对字符统计打印统计结果、编码表和编码结果3.对一串数据解码4.统计编码前后的数据大小，计算压缩率5 实验收获代码编写完会有很多与预期不同的结果，耐心调试，修改代码，开始写代码的时候就认真的写，在调试时找出逻辑问题比较困难，做到一步到位。

一、问题描述1.用户输入字母及其对应的权值，生成哈夫曼树；2.通过最优编码的算法实现，生成字母对应的最优0、1编码;3.先序、中序、后序遍历哈夫曼树，并打印其权值。

二、方法思路1。

哈夫曼树算法的实现§存储结构定义＃define n 100 /＊叶子树*/#define m 2＊（n) –1 /* 结点总数＊/typedef struct ｛/＊结点型＊/double weight ; /* 权值＊/int lchild ；/* 左孩子链*/int rchild ；/* 右孩子链＊/int parent; /＊双亲链*/ 优点？｝HTNODE ；typedef HTNODE HuffmanT[ m ］;/＊huffman树的静态三叉链表表示＊/算法要点1）初始化：将T[0]，…T[m—1］共2n-1个结点的三个链域均置空（—1 ）,权值为0；2）输入权值：读入n 个叶子的权值存于T的前n 个单元T［0]，…T[n]，它们是n 个独立的根结点上的权值；3）合并：对森林中的二元树进行n—1次合并，所产生的新结点依次存放在T［i]（n〈=i<=m—1）。

每次合并分两步：(1) 在当前森林中的二元树T [0］，…T［i—1］所有结点中选取权值最小和次最小的两个根结点T[p1]和T[p2]作为合并对象，这里0<= p1，p2<= i –1;（2) 将根为T［p1]和T［p2］的两株二元树作为左、右子树合并为一株新二元树，新二元树的根结点为T[i］。

即T［p1］.parent =T［p2］.parent = i ,T［i］.lchild= p1, T［i]。

rchild=p2, T［i］.weight =T［p1]。

weight + T[p2].weight.2。

用huffman算法求字符集最优编码的算法:1) 使字符集中的每个字符对应一株只有叶结点的二叉树，叶的权值为对应字符的使用频率；2）利用huffman算法来构造一株huffman树；3) 对huffman树上的每个结点，左支附以0，右支附以1(或者相反），则从根到叶的路上的0、1序列就是相应字符的编码Huffman编码实现：存储结构typedef struct{char ch；//存储字符char bits[n+1］；//字符编码位串｝CodeNode;typedef CodeNode HuffmanCode[n］；HuffmanCode H;3。

数据结构哈夫曼编码实验报告数据结构实验报告----------1-实验目的----------本实验的目的是通过实现哈夫曼编码算法，加深对数据结构中树和堆的理解，以及掌握相关的编程技巧。

2-实验内容----------2-1 算法简介----------哈夫曼编码是一种无损压缩算法，通过根据字符出现的频率构建一颗二叉树，并将出现频率较高的字符编码为较短的二进制串，进而实现压缩的目的。

在本实验中，我们需要实现以下功能：●构建哈夫曼树●字符编码表●对给定的字符串进行编码●对给定的二进制串进行解码●实现压缩和解压缩功能2-2 数据结构----------在实现哈夫曼编码算法时，我们需要使用以下数据结构：●链表：用于存储字符出现的频率及对应的字符●堆：用于构建哈夫曼树●树：用于存储哈夫曼编码树●散列表或映射：用于存储字符的编码2-3 算法步骤----------1-统计字符的出现频率，并构建频率链表2-根据频率链表构建哈夫曼树3-字符的编码表4-对给定的字符串进行编码5-对给定的二进制串进行解码6-实现压缩和解压缩功能3-实验实现----------3-1 数据结构的设计----------在本实验中，我们将使用以下数据结构：●链表节点结构体：用于存储字符和频率●链表结构体：用于存储链表节点的头指针●堆节点结构体：用于存储字符和频率，并维护堆的结构●堆结构体：用于存储堆的根节点●树节点结构体：用于存储字符和编码，并维护哈夫曼树的结构●树结构体：用于存储哈夫曼树的根节点●散列表结构体：用于存储字符和对应的编码3-2 算法实现----------1-统计字符的出现频率并构建频率链表：遍历给定的字符串，统计字符的频率，并将字符频率按从小到大的顺序插入到频率链表中。

2-根据频率链表构建哈夫曼树：将频率链表的节点插入到堆中，并按照堆的定义调整堆的结构，直到堆中只有一个节点。

3-字符的编码表：遍历哈夫曼树，递归构造字符的编码表。

一、设计思想(一) 哈夫曼树的设计思想对于一组具有确定权值的叶子结点可以构造出多个具有不同带权路径长度的二叉树，其中具有最小带权路径长度的二叉树称作哈夫曼树或最优二叉树。

首先给定n个权值制造n个只含根结点的二叉树，得到一个二叉树林；再在这二叉树林里面找根结点的权值最小和次小的两棵树作成新的二叉树，其中新的二叉树的根结点的权值为左右子根结点权值之和；最后在二叉树林中把组合过的二叉树删除，再重复第二步，直到最后就剩一颗二叉树的时候得到的这棵二叉树就是哈夫曼树。

（二）哈夫曼编码与解码的设计思想在数据通讯中，经常要将传送的文字转换为二进制字符0和1组成的二进制串，称这个过程为编码。

与子相对的是解码或是译码，就是用与编码相同的方式将二进制串转换称编码前的文字的过程称作解码。

在这里是通过哈夫曼树实现编码与解码的，所以称作是哈夫曼编码与解码。

首先输入一个字符串，还有相应的在哈夫曼树里的权值，这样用哈夫曼树把字符串用二进制串代替它，这个过程要注意树和编码问题，其中树的问题在上面已经解决，主要看编码的问题，就是根据我们输入的字符串和权值建立相应的树模型，这一步完成那编码就已经完成了，最后打印就行了；然后就是解码，完成编码相应的解码就相对简单了，就是先找到在编码的时候建的那个模型树，将编码中的二进制串再根据权值转换为相应的字符串，这样一步步解码就行了。

以上就是通过用哈夫曼树进行哈夫曼编码与解码如何实现的主要设计思想。

二、算法流程图（一）哈夫曼树的流程图不是图1哈夫曼树的流程图（二）编码的流程图（三）解码的流程图哈夫曼编码与解码的实现- 3 -否三、源代码下面给出的是用中缀转后缀算法实现的程序的源代码：#include "stdio.h" #include "string.h" #define MAX 100/*定义常量*/struct HaffNode {int weight;/*权值*/ int parent;/*双亲结点下标*/char ch; int lchild; int rchild;}*myHaffTree; /*构造哈夫曼树*/struct Coding {char bit[MAX];/*定义数组*/char ch; int weight;/*字符的权值*/}*myHaffCode;/*定义结构体*/void Haffman(int n)/*定义哈夫曼函数*/{int i,j,x1,x2,s1,s2;for (i=n+1;i<=2*n-1;i++) /*树的初始化*/{s1=s2=10000;x1=x2=0;for (j=1;j<=i-1;j++) /*构造哈夫曼树的非叶子结点*/{if(myHaffTree[j].parent==0&&myHaffTree[j].weight<s1) /*分配左右结点*/ {s2=s1;x2=x1;s1=myHaffTree[j].weight;x1=j;}else if(myHaffTree[j].parent==0&&myHaffTree[j].weight<s2){s2=myHaffTree[j].weight;x2=j;}}myHaffTree[x1].parent=i;myHaffTree[x2].parent=i;myHaffTree[i].weight=s1+s2; /*左右子组合为新树*/myHaffTree[i].lchild=x1;myHaffTree[i].rchild=x2;}}void HaffmanCode(int n) /*构造n个结点哈夫曼编码*/{int start,c,f,i,j,k;char *cd;cd=(char *)malloc(n*sizeof(char));myHaffCode=(struct Coding *)malloc((n+1)*sizeof(struct Coding));cd[n-1]='\0';for(i=1;i<=n;++i) /*n个叶子结点的哈夫曼编码*/{start=n-1;for(c=i,f=myHaffTree[i].parent;f!=0;c=f,f=myHaffTree[f].parent)if(myHaffTree[f].lchild==c) cd[--start]='0';else cd[--start]='1';for(j=start,k=0;j<n;j++){myHaffCode[i].bit[k]=cd[j];k++;}myHaffCode[i].ch=myHaffTree[i].ch; /*取编码对应的权值*/ myHaffCode[i].weight=myHaffTree[i].weight;}哈夫曼编码与解码的实现free(cd);}Init() /*定义有返回值的函数*/ {int i,n,m;printf("please input the number of words:");scanf("%d",&n);m=2*n-1;myHaffTree=(struct HaffNode *)malloc(sizeof(struct HaffNode)*(m+1));for(i=1;i<=n;i++){printf("please input the word and the equal:");scanf("%s%d",&myHaffTree[i].ch,&myHaffTree[i].weight);myHaffTree[i].parent=0;myHaffTree[i].lchild=0;myHaffTree[i].rchild=0;}for(i=n+1;i<=m;i++){myHaffTree[i].ch ='#';myHaffTree[i].lchild=0;myHaffTree[i].parent=0;myHaffTree[i].rchild=0;myHaffTree[i].weight=0;}Haffman(n);HaffmanCode(n);for(i=1;i<=n;i++){printf("%c %d",myHaffCode[i].ch,myHaffCode[i].weight);printf("\n");}printf("init success!\n");return n;}void Caozuo_C(int m) /* 编码函数*/{int n,i,j;char string[50],*p;printf("please input the words：");scanf("%s",string);n=strlen(string); /*计算字符串长度*/for(i=1,p=string;i<=n;i++,p++) /*进行编码*/- 5 -{for(j=1;j<=m;j++)if(myHaffCode[j].ch==*p)printf("%s\n",myHaffCode[j].bit);}}void Caozuo_D(int n) /*解码函数*/{int i,c;char code[1000],*p;printf("please input the coding："); /*输入二进制编码*/ scanf("%s",code);for(p=code,c=2*n-1;*p!='\0';p++) /*进行解码*/{if(*p=='0') /*结束条件*/ {c=myHaffTree[c].lchild; /*赋值*/if(myHaffTree[c].lchild==0) /* 扫描*/{printf("%c",myHaffTree[c].ch);c=2*n-1;continue; /*结束*/}}else if(*p=='1'){c=myHaffTree[c].rchild;if(myHaffTree[c].lchild==0){printf("%c",myHaffTree[c].ch);c=2*n-1; /*赋值*/continue;}}}printf("\n");}void main(){int n;char char1; /*定义字符*/n=Init(); /*函数的调用*/哈夫曼编码与解码的实现printf("A.coding B.codeprinting C.exit\nplease input the process:\n");while(1){scanf("%c",&char1);if(char1=='c') /*判断字符*/break;switch(char1){case'A':Caozuo_C(n);break; /*执行编码操作*/case'B':Caozuo_D(n);break; /*执行解码操作*/case'C':;break;}}}四、运行结果（一）中缀转后缀算法的运行结果：- 7 -五、遇到的问题及解决这部分我主要遇到了如下三个问题，其内容与解决方法如下所列：问题1:刚开始不知道如何建一个好树，因为我开始试着建了几个二叉树，不知道什么原因运行的时候那编码总是不对，跟在草稿纸上自己画的那个二叉树总是不相符，就找原因。

(原创)数据结构课程设计报告学院：计算机科学与工程专业：计算机科学与技术班级：09级班学号：姓名：指导老师:时间: 2010年12月一、课程设计题目：1、哈夫曼编码的实现2、城市辖区地铁线路设计3、综合排序算法的比较二、小组成员：三、题目要求：1．哈夫曼编码的实现（1）打开若干篇英文文章，统计该文章中每个字符出现的次数，进一步统一各字符出现的概率。

（2）针对上述统计结果，对各字符实现哈夫曼编码（3）对任意文章，用哈夫曼编码对其进行编码（4）对任意文章，对收到的电文进行解码2．某城市要在其各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要合理安排地铁的建设路线。

（1）从包含各辖区的地图文件中读取辖区的名称和各辖区的直接距离（2）根据上述读入的信息，给出一种铺设地铁线路的解决方案。

使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。

（3）输出应该建设的地铁路线及所需要建设的总里程信息。

3．综合排序算法的比较各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概的执行时间。

试通过随机的数据比较各算法的关键字比较次数和关键字移动的次数。

（1）对以下各种常用的内部排序算法进行比较：直接插入排序，折半插入排序，二路归并排序，希尔排序，冒泡排序，快速排序，简单选择排序，堆排序，归并排序，基数排序。

（2）待排序的表长不少于100，要求采用随机数。

（3）至少要用5组不同的输入数据做比较：比较的次数为有关键字参加的比较次数和关键字移动的次数（4）改变数据量的大小，观察统计数据的变化情况。

（5）对试验统计数据进行分析。

对各类排序算法进行综合评价。

四、项目安排：1、小组内分工合作分工：xx负责哈夫曼编码的实现，zz负责城市辖区地铁线路设计，yy负责综合排序算法的比较。

合作：组内，组外进行交流，组长帮助解决组员的在项目过程中的困难，并控制进度。

五、完成自己的任务：任务：哈夫曼编码的实现1、思想实现流程图2、代码实现头文件define.h#ifndef _DEFINE_H_#define _DEFINE_H_#include <windows.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#define n 128typedef struct{int weight;int parent,lchild,rchild;}HuffmanTree; //哈夫曼树数据类型typedef struct{int ch;char codes[30];}coding; //哈夫曼编码数据存储typedef struct{int point;char codes[30]; //栈存}stack;extern void stat_file(HuffmanTree charer[256]); //统计字符频率extern void make_tree(HuffmanTree charer[256]); //构造哈夫曼树extern void make_code(HuffmanTree charer[256],coding inside[128]); //生成字符编码extern void article_code(coding inside[128]); //文章转码extern void decoding(HuffmanTree charer[256]); //文章解码#endif主函数：main.cpp#include "define.h"void main(){char choose;HuffmanTree charer[256];coding inside[128];printf("********************************************\n");printf(" 请选择\n");printf("*********** 1 刷新哈夫曼编码**********\n");printf("*********** 2 用统计频率编码**********\n");printf("*********** 3 任意文章编码**********\n");printf("*********** 4 任意文章解码**********\n");printf("*********** 0 退出本系统**********\n");printf("********************************************\n");do{fflush(stdin);scanf("%c",&choose); //暂时未加入未进行编码的判断switch(choose){case '1':memset(charer,0,256*sizeof(HuffmanTree));stat_file(charer);printf("请继续选择相应选项\n");break;case '2':make_tree(charer);memset(inside,0,128*sizeof(coding)); //先清空make_code(charer,inside);printf("请继续选择相应选项\n");break;case '3':article_code(inside);printf("请继续选择相应选项\n");break;case '4':decoding(charer); //如果只进行反编译，必须要输入相同的文章以建立哈夫曼树，printf("译码完毕!请打开根目录下的文件查看!\n"); //而之前翻译成代码时也要使用相同文章printf("请继续选择相应选项\n");break;case '0':MessageBox(NULL," 已退出系统!","提示",MB_OK);break;default: printf("对不起，您的操作错误，请重新输入编号！");}}while (choose!='0');}函数1：input_files.cpp#include "define.h"void stat_file(HuffmanTree charer[256]){FILE *fp;char choose;int i,looking;char path[30];loop: printf("请输入文件名:\n"); //设置循环点scanf("%s",path);if((fp=fopen(path,"r"))==NULL) //寻找文件{printf("文件不存在\n");goto loop;}for(i=0;1;i++) // 对应字符的数组元素++{looking=fgetc(fp);if(looking==EOF)break;charer[looking].weight++;}fflush(stdin);printf("继续增加文件???(y/n)?\n");scanf("%c",&choose); //选择if(choose == 'y')goto loop; //返回循环点fclose(fp); //关闭文件}函数2：make_tree.cpp#include "define.h"void make_tree(HuffmanTree charer[256]) //建树函数{int i,min1,min2;int k,j;int flag1=0,flag2=0;void prnt(HuffmanTree charer[256]); //输出到文件中，以后改进时可以直接从文件读取for(i=0;i<n-1;i++) //两重多组的循环，算法不太好，比较的次数递增{for(k=0;k<n+i;k++)if( charer[k].parent == 0) //找出第一个叶子作为最小值{min1=charer[k].weight;flag1=k;break;}for(j=k;j<n+i;j++){if(min1==0) //考虑0的情况，减少循环break;if(charer[j].weight < min1 && charer[j].parent == 0) //否则进行比较{min1=charer[j].weight;flag1=j;}}for(k=0;k<n+i;k++)if( charer[k].parent == 0 && k!=flag1) //找第二个叶子作为次小值{min2=charer[k].weight;flag2=k;break;}for(j=k;j<n+i;j++){if(min2==0)break;if(charer[j].weight < min2 && charer[j].parent == 0 && j!=flag1){min2=charer[j].weight;flag2=j;}}charer[n+i].weight=charer[flag1].weight+charer[flag2].weight; //关键步骤：最小值和次小值的相加并构成子树charer[n+i].rchild=flag1;charer[n+i].lchild=flag2;charer[flag1].parent=n+i;charer[flag2].parent=n+i;}prnt(charer); //顺便输出到文件中}void prnt(HuffmanTree charer[256]){FILE *fp;char sn[20]={"哈夫曼树的如下:"};char xinxi[5][7]={"序号","权值","双亲","左孩子","右孩子"};fp = fopen("HuffmanTree.txt","w+");fprintf(fp,"%s\n",sn);fprintf(fp,"%s\t%s\t%s\t%s\t%s\n",xinxi[0],xinxi[1],xinxi[2],xinxi[3],xinxi[4]);for(int i=0;i<255;i++)fprintf(fp,"%d\t%d\t%d\t%d\t%d\n",i,charer[i].weight,charer[i].parent,charer[i].lc hild,charer[i].rchild);fclose(fp);MessageBox(NULL," 哈夫曼树写入文件成功!","提示",MB_OK);system("HuffmanTree.txt");}函数4：produce_code.cppvoid make_code(HuffmanTree charer[256],coding inside[128]) //从哈夫曼树中生成字符编码{stack push_pop;int k,j;void prn(coding inside[128]); //把编码输出到文件中，共128个for(int i=0;i<128;i++){memset(&push_pop,0,1*sizeof(stack)); //栈存inside[i].ch=i;for(k=i,j=0;1; ) //下面可控制循环退出{if(charer[k].parent!=0) //从下往上找到根节点{if(charer[charer[k].parent].lchild==k) // 子根节点的左孩子编0，右孩子编1push_pop.codes[push_pop.point++]='0'; //压栈// push_pop.point++; // 把++直接放入括号，减少代码量if(charer[charer[k].parent].rchild==k)push_pop.codes[push_pop.point++]='1';// push_pop.point++;j=k;k=charer[k].parent;}else{/* if(charer[charer[j].parent].lchild==j){push_pop.codes[push_pop.point++]='0';// push_pop.point++;}if(charer[charer[j].parent].rchild==j){push_pop.codes[push_pop.point++]='1';// push_pop.point++;}*/break;}}for(k=0,j=push_pop.point;k<push_pop.point;) //从栈顶回取，所得编码存入所设数组inside[i].codes[k++]=push_pop.codes[--j];}prn(inside);}void prn(coding inside[128]){FILE *fp;char sn[20]={"编码的如下:"};char xinxi[3][5]={"序号","字符","编码"};fp = fopen("HuffmanCode.txt","w+");fprintf(fp,"%s\n",sn);fprintf(fp,"%s\t%s\t%s\n",xinxi[0],xinxi[1],xinxi[2]);for(int i=0;i<128;i++)fprintf(fp,"%d\t%c\t%s\n",i,inside[i].ch,inside[i].codes);fclose(fp);MessageBox(NULL," 编码写入文件成功!","提示",MB_OK);system("HuffmanCode.txt");}函数5：article_code.Cpp#include "define.h"void article_code(coding inside[128]){FILE *fp,*fq;char path[50];char ch=0;printf("请输入需要转码的文章名称：\n");scanf("%s",path);if((fp=fopen(path,"r"))==NULL) //寻找文件{MessageBox(NULL," 文件不存在!","提示",MB_OK);exit(1);}fq=fopen("article_code.txt","w+");for(int i=0;1;i++) //从文件读取字符，转换成编码写入文件中{ch=fgetc(fp);if(ch==EOF) //防止多读一次加入到中间比较好break;fprintf(fq,"%s",inside[ch].codes);}fclose(fp); //关闭文件fclose(fq);MessageBox(NULL," 文章转换完毕!","提示",MB_OK);system("article_code.txt");}函数6：decoding.cpp#include "define.h"void decoding(HuffmanTree charer[256]){FILE *fp,*fq; //文件指针，一个读取，一个写入char path[20];int k;char ch;loop: printf("请输入需要解码文件的路径:\n");scanf("%s",path);if((fp=fopen(path,"r"))==NULL) //寻找文件{printf("文件不存在,请确认路径是否正确! \n");goto loop;}fq=fopen("decoding.txt","w+");for(int i=0;1;i++) //从文件中读取编码，由根进行寻找{k=254;ch=fgetc(fp);if(ch==EOF)break;for(int j=0;1;j++){if(ch=='0') //左孩子，继续判断左孩子的左右孩子是否存在，{if(charer[charer[k].lchild].lchild==0 && charer[charer[k].lchild].rchild==0){fprintf(fq,"%c",charer[k].lchild);break;}k=charer[k].lchild; //非叶子节点，即刻转向孩子节点，并进行下一次判断ch=fgetc(fp);if(ch==EOF)break;continue; //读取下一个}if(ch=='1') //右孩子，继续判断右孩子的左右孩子是否存在，不存在即为叶子节点。

题目一: 哈夫曼编码与译码一、任务设计一个运用哈夫曼算法的编码和译码系统, 反复地显示并解决以下项目, 直到选择退出为止。

规定：1) 将权值数据存放在数据文献(文献名为data.txt, 位于执行程序的当前目录中) ；2) 初始化：键盘输入字符集记录字符权值、自定义26个字符和26个权值、记录文献中一篇英文文章中26个字母, 建立哈夫曼树；3) 编码: 运用建好的哈夫曼树生成哈夫曼编码；4) 输出编码（一方面实现屏幕输出, 然后实现文献输出）；5）译码（键盘接受编码进行译码、文献读入编码进行译码）；6) 界面优化设计。

二、流程图三、代码分解 //头文献 #include<stdio.h> #include<string.h> #include<stdlib.h> #include <conio.h> #define N 1000 #define M 2*N-1 #define MAXcode 6000 //函数声明void count(CHar &ch,HTNode ht[]);void editHCode(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]); //编码函数void printyima(HTNode ht[],HCode hcd[],int n,char bianma[]); //译码函数 void creatHT(HTNode ht[],int n);字符集记录符集记录权值 权值 至文献“哈夫曼树。

t xt” 菜单1.从键盘输入字符集进行编码2.从文献读入字符集进行编码1.从键盘输入编码进行译码2.从文献读入编码进行译码0.返回上级菜单 0.返回上级菜单void CreateHCode (HTNode ht[],HCode hcd[],int n);void DispHCode(HTNode ht[],HCode hcd[],int n);void input_key(CHar &ch);void input_file(CHar &ch);void input_cw(HTNode ht[]);void bianma1(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]); void bianma2(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]); void yima1(HTNode ht[],HCode hcd[],int n,char bianma[]);void yima2(HTNode ht[],HCode hcd[],int n,char bianma[]);void creat_cw();void bianmacaidan();void yimacaidan();void bianmayima();int caidan();//结构体typedef struct{char data;int parent;int weight;int lchild;int rchild;}HTNode;typedef struct{char cd[N];int start;}HCode;typedef struct{char s[N];int num;}CHar;CHar ch;HTNode ht[M];HCode hcd[N];//主函数int main(){int xh;while(1){system("color 1f"); //操作菜单背景颜色 xh=caidan(); //调用菜单函数switch(xh) //switch语句 {case 1:system("cls");creat_cw();break;case 2:system("cls");creatHT(ht,n);break;case 3:system("cls");CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);break;case 4:system("cls");bianmayima();break;case 0:system("cls");printf("\n\n\n\n\n\n\n\n\n\t\t\t\t感谢使用本系统!\n\n\n\n\n\n\n \t\t\t");exit(0);default:system("cls");putchar('\a');printf("\n\t\t输入有误, 请重新输入:\n");break;}}return 0;}//菜单函数int caidan() //菜单函数模块//{int xh;printf("\n\n\n");printf("\t\t 欢迎使用哈夫曼编码译码系统\n");printf("\t\t \n");printf("\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n");printf("\t\t*= =*\n");printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n");printf("\t\t*= 1.建立字符权值=*\n");printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n"); printf("\t\t*= 2.建立并输出哈夫曼树=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n"); printf("\t\t*= 3.生成并查看哈夫曼编码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n"); printf("\t\t*= 4.编码与译码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*= =*\n"); printf("\t\t*= 0.退出系统=*\n"); printf("\t\t*= =*\n"); printf("\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n"); printf("\n\t\t请输入序号进行选择:");scanf("%d", &xh);return xh; //返回从键盘接受的选项}void bianmayima(){int xh;while(1){printf("\n\n\n\n\n");printf("\t\t 编码与译码\n"); printf("\t\t \n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n");printf("\t\t*= 1.编码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 2.译码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 0.返回上级菜单=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\n\t\t请输入序号进行选择:");scanf("%d",&xh);switch(xh) //switch语句{case 1:system("cls");bianmacaidan();break;case 2:system("cls");yimacaidan();break;case 0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t输入有误, 请重新输入:\n");break;}}}void yimacaidan(){int xh;while(1){printf("\n\n\n\n\n");printf("\t\t 译码\n"); printf("\t\t \n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 1.键盘输入编码进行译码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 2.文献读入编码进行译码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 0.返回上级菜单=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\n\t\t请输入序号进行选择:");scanf("%d",&xh);switch(xh) //switch语句{case 1:system("cls");yima1(ht,hcd,n,bianma);break;case 2:system("cls");yima2(ht,hcd,n,bianma);break;case 0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t输入有误, 请重新输入:\n");break;}}}void bianmacaidan(){int xh;while(1){printf("\n\n\n\n\n");printf("\t\t 编码\n"); printf("\t\t \n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 1.键盘输入字符集编码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 2.文献读入文章编码=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 0.返回上级菜单=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\n\t\t请输入序号进行选择:");scanf("%d",&xh);switch(xh) //switch语句{case 1:system("cls");bianma1(ht,hcd,ch,n,bianma);break;case 2:system("cls");bianma2(ht,hcd,ch,n,bianma);break;case 0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t输入有误, 请重新输入:\n");break;}}}void creat_cw(){int xh2;while(1){printf("\n\n\n\n\n");printf("\t\t 建立字符权值\n"); printf("\t\t \n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 1.从键盘输入字符集进行记录=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 2.从文献读入字符集记录=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 3.自定义字符权值=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\t\t*= 0.返回上级菜单=*\n"); printf("\t\t*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*\n"); printf("\n\t\t请输入序号进行选择:");scanf("%d",&xh2);switch(xh2) //switch语句{case 1:system("cls");input_key(ch);break;case 2:system("cls");input_file(ch);break;case 3:system("cls");input_cw(ht);break;case 0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t输入有误, 请重新输入:\n");break;}}}//建立字符权值模块void input_key(CHar &ch){int i,j=0;char st[N];printf("请输入字符集（以‘#’结束）:\n");for(i=0;i<N;i++){scanf("%c",&st[i]);if(st[i]=='#'){st[i]='\0';break;}}strcpy(ch.s,st);count(ch,ht);printf("按任意键返回!");getch();system("cls");return;}void input_file(CHar &ch){int i;FILE*fp;char filename[20];printf("请输入要打开的文献名(*.txt):");scanf("%s",&filename);if((fp=fopen(filename,"r"))==NULL){printf("\n\t\t文献打开失败");return;}for(i=0;!feof(fp);i++){fread(&ch.s[i],sizeof(char),1,fp);}printf("读入成功!\n");printf("文献中的字符集为:%s\n",ch.s);fclose(fp);count(ch,ht);printf("按任意键返回!");getch();system("cls");return;}void input_cw(HTNode ht[]){int i,w,s,j;char a;printf("要输入的字符总个数是？:");scanf("%d",&s);n=s;printf("请输入字符及其权值:\n");for(i=0;i<s;i++){printf("请输入第%d个字母:",i+1);scanf("%s",&a);ht[i].data=a;printf("请输入其权值:");scanf("%d",&w);ht[i].weight=w;}FILE *fp;if((fp=fopen("data.txt","w"))==0){printf("\n\t\t文献打开失败");return;}printf("\n定义权值成功!\n\n");printf("各字符及其权值为:\n\n");fprintf(fp,"各字符及其权值为:\n");printf(" 字符\t权值");fprintf(fp," 字符\t权值");for(j=0;j<i;j++){ printf("\n");fprintf(fp,"\n");printf(" %-8c%-8d",ht[j].data,ht[j].weight);fprintf(fp," %-8c%-8d%",ht[j].data,ht[j].weight); }printf("\n");printf("\n字符权值已输出至文献“data.txt”！");fclose(fp);printf("输入完毕, 按任意键返回！");getch();system("cls");return;}//记录字符权值函数void count(CHar &ch,HTNode ht[]){int i,j,m=0;char c[N];int sum[N]={0};for(i=0;ch.s[i]!='\0';i++){for(j=0;j<m;j++)if(ch.s[i]==c[j]||(c[j]>='a'&&c[j]<='z'&&ch.s[i]+32==c[j])) break;if(j<m)sum[j]++;else{if(ch.s[i]>='A'&&ch.s[i]<='Z')c[j]=ch.s[i]+32;else c[j]=ch.s[i];sum[j]++;m++;}}for(i=0;i<m;i++){ht[i].data=c[i];ht[i].weight=sum[i];}n=m;FILE *fp;if((fp=fopen("data.txt","w"))==0) {printf("\n\t\t文献打开失败"); return;}printf("\n记录权值成功!\n\n"); printf("各字符及其权值为:\n\n"); fprintf(fp,"各字符及其权值为:\n"); printf(" 字符\t权值");fprintf(fp," 字符\t权值");for(j=0;j<m;j++){ printf("\n");fprintf(fp,"\n");printf(" %-8c%-8d",ht[j].data,ht[j].weight);fprintf(fp," %-8c%-8d%",ht[j].data,ht[j].weight);}printf("\n");printf("\n字符权值已输出至文献“data.txt”！");fclose(fp);}//构造哈夫曼树void creatHT(HTNode ht[],int n){FILE *fp;if((fp=fopen("哈夫曼树.txt","w"))==0){printf("\n\t\t文献打开失败");return;}int i,j,k,lnode,rnode;int min1,min2;for (i=0;i<2*n-1;i++)ht[i].parent=ht[i].lchild=ht[i].rchild=-1;for (i=n;i<2*n-1;i++){min1=min2=32767;lnode=rnode=-1;for(k=0;k<=i-1;k++)if(ht[k].parent==-1){if (ht[k].weight<min1){min2=min1;rnode=lnode;min1=ht[k].weight;lnode=k;}else if(ht[k].weight<min2){min2=ht[k].weight;rnode=k;}}ht[lnode].parent=i;ht[rnode].parent=i;ht[i].weight=ht[lnode].weight+ht[rnode].weight;ht[i].lchild=lnode;ht[i].rchild=rnode;}printf("建立huffman树成功!\n");printf("输出huffman树:\n");fprintf(fp,"输出huffman树:\n");printf("\t字符\t权值\t父节点\t 左子节点\t右子节点");fprintf(fp,"\t字符\t权值\t父节点\t 左子节点\t右子节点");for(j=1;j<i;j++){ printf("\n");fprintf(fp,"\n");printf("\t %-8c%-8d%-10d%-14d%-10d",ht[j].data,ht[j].weight,ht[j].parent,ht[i]. lchild,ht[j].rchild);fprintf(fp,"\t %-8c%-8d%-10d%-14d%-10d",ht[j].data,ht[j].weight,ht[j].parent,h t[i].lchild,ht[j].rchild);}printf("\n");printf("哈夫曼树已输出至文献“哈夫曼树.txt”！按任意键返回!");fclose(fp);getch();system("cls");return;}//生成哈夫曼编码void CreateHCode (HTNode ht[],HCode hcd[],int n){int i,f,c,j=0;HCode hc;for(i=0;i<n;i++){hc.start=n;c=i;hc.cd[hc.start--]='0';f=ht[i].parent;while(f!=-1){if (ht[f].lchild==c)hc.cd[hc.start--]='0';elsehc.cd[hc.start--]='1';c=f;f=ht[f].parent;}hc.start++;for(j=0;j<hc.start;j++)hc.cd[j]=' ';hcd[i]=hc;}}void DispHCode(HTNode ht[],HCode hcd[],int n) {FILE *fp;if((fp=fopen("哈夫曼编码.txt","w"))==0){printf("\n\t\t文献打开失败");return;}int i,k;int sum=0,m=0,j;printf("输出字符哈夫曼编码:\n"); fputs("输出字符哈夫曼编码:\n",fp); for (i=0;i<n;i++){j=0;printf("%c:\t",ht[i].data);fprintf(fp,"\n%c:\t",ht[i].data);for (k=hcd[i].start;k<=n;k++){printf("%c",hcd[i].cd[k]);j++;fprintf(fp,"%c",hcd[i].cd[k]); }m+=ht[i].weight;sum+=ht[i].weight*j;printf("\n");}printf("\n哈夫曼编码已保存至文献“哈夫曼编码.txt!按任意键返回！”");fclose(fp);getch();system("cls");}//编码函数void bianma1(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]){int i;char str[N];printf("请输入要编码的字符集（以‘#’结束）:\n");for(i=0;i<N;i++){scanf("%c",&str[i]);if(str[i]=='#'){str[i]='\0';break;}}strcpy(ch.s,str);ch.num=strlen(str);editHCode(ht,hcd,ch,n,bianma);getch();system("cls");}void bianma2(HTNode ht[],HCode hcd[],CHar &ch,int n,char bianma[]) {int i;FILE*fp;char filename[20];printf("请输入要打开的文献名(*.txt):");scanf("%s",&filename);if((fp=fopen(filename,"r"))==NULL){printf("\n\t\t文献打开失败");return;}for(i=0;!feof(fp);i++){fread(&ch.s[i],sizeof(char),1,fp);}ch.num=strlen(ch.s);printf("\n读入成功!\n");printf("文献中的字符集为:\n%s",ch.s);fclose(fp);editHCode(ht,hcd,ch,n,bianma);system("cls");return;}//译码函数void yima1(HTNode ht[],HCode hcd[],int n,char bianma[]) {int i;char code[MAXcode];printf("请输入编码进行译码（以‘#’结束）:\n");for(i=0;i<MAXcode;i++){scanf("%c",&code[i]);if(code[i]=='#'){code[i]='\0';break;}}strcpy(bianma,code);printyima(ht,hcd,n,bianma);printf("\n译码完毕！按任意键返回!");getch();system("cls");return;}void yima2(HTNode ht[],HCode hcd[],int n,char bianma[]) {int i;FILE*fp;char filename[20];printf("请输入要打开的文献名(*.txt):");scanf("%s",&filename);if((fp=fopen(filename,"r"))==NULL){printf("\n\t\t文献打开失败");return;}for(i=0;!feof(fp);i++){fread(&bianma[i],sizeof(char),1,fp);}printf("读入成功!\n");printf("文献中的编码是:%s\n",bianma);printyima(ht,hcd,n,bianma);printf("\n译码完毕！按任意键返回!");getch();system("cls");}四、调试结果主菜单建立字符权值选择2.从文献读入字符进行记录输入测试文献名“cs.txt”输出个字符权值建立哈夫曼树并输出至文献生成哈夫曼编码并保存至文献编码选择2.从文献读入字符集编码编码结果保存至文献译码选择2.从文献读入编码, 读入上一步的编码译码完毕, 返回！退出系统。

数据结构课程设计报告实验二哈夫曼编码目录一．问题描述及分析p11．问题描述p12．需求分析p1 二．功能模块及数据结构描述p11．数据结构描述 p1 2．模块描述 p2三．主要算法流程描述p21．编码流程图 p3 2．译码流程图 p4四．使用说明p5 五．调试分析说明p6一．问题描述及分析1．问题描述设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件（后缀名.cod）；反过来，可将一个编码文件还原为一个文本文件(.txt)。

2．需求分析（1）输入一个待压缩的文本文件名，统计文本文件中各字符的个数作为权值，生成哈夫曼树；（2）将文本文件利用哈夫曼树进行编码，生成编码文件（后缀名cod）；（3）输入一个待解压的压缩文件名称，并利用相应的哈夫曼树将编码序列译码；（4）显示指定的编码文件和文本文件；3．运行要求.Windows xp/2003.VC++6.0(或以上)运行库二．功能模块及数据结构描述1．数据结构描述typedef struct{long weight;long lchild,rchild,parent;}hfmt;hfmt t[2*256-1];存放哈夫曼树结构体，weight为节点权值，lchild，rchild为节点的左右孩子在向量中的下标(为叶节点时，两值为：-1)，parent为节点的双亲在向量中的下标(用来区别根与非根节点，值为-1与非-1)。

typedef struct{char bits[256];long s;}hfmcc;hfmcc cc[256];存放哈夫曼编码结构体，s用来指示编码在位串bits[n]中的起始位置。

2．模块描述图2.1 系统函数copy函数：根据s的值在位串bits[n]中提取有效编码位数。

HFM函数：对读入的节点权值，生成哈夫曼树。

HFMBM函数：对生成的哈夫曼树进行零一编码，对应于原文件字符。

三．主要算法流程描述1．编码流程图图2.2 编码流程图2．译码流程图图2.3 译码流程图四．使用说明图2.4 生成的文件本软件默认生成的编码文件名为：a.cod默认生成的译码文件名为：b.txt执行提示：输入所要编码的文本文件。

题目哈夫曼编码问题的设计和实现课程名称数据结构课程设计院（系、部、中心）专业班级学生姓名学号设计地点指导教师设计起止时间：2008 年6月2日至2008 年6月 6 日目录1 问题描述 (2)1.1 题目内容 (2)1.2 基本要求 (3)1.3 测试数据 (3)2 需求分析 (3)2.1 程序的基本功能 (3)2.2 输入值、输出值以及输入输出形式 (3)2.3 各个模块的功能要求 (4)3 概要设计 (4)3.1 所需的ADT，每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义） (4)3.2 主程序流程以及模块调用关系 (5)3.3 各个模块的算法设计说明 (5)4 详细设计 (8)4.1 数据类型 (8)4.2 函数调用 (9)5 各个算法实现的源程序 (9)6 调试分析 (12)7 使用说明 (12)8 测试结果 (13)9 源程序 (13)1 问题描述1.1 题目内容哈夫曼编码问题的设计和实现输入一个英文字符串，对该字符串中各字符个数进行统计取得各字符的出现次数；以其出现次数作为关键字建立哈夫曼树并进行编码，最后输出各个字符对应的码值。

1.2 基本要求要求：设计存储结构、基本算法（主要采用程序流程图体现）；完成基本算法的实现代码；设计测试输入数据对程序进行测试，分析输出结果数据、算法的时间复杂度分析，如有改进算法则提出算法的改进方法。

1.3 测试数据测试数据三组：AAAABBBCCD(判断连续的字符串是否可行)AABBAABCDC(判断间段的字符串是否可行)AAAA BBBCCD(判断含空格的字符串是否可行)2 需求分析2.1 程序的基本功能该程序大体上有两个功能：1．输入任何一个字符串后，该程序能统计不同字符串的个数，并以不同字符串的个数作为权值。

2．已知不同字母的权值，以该权值作为叶结点，构造一棵带权路径最小的树，对该树从叶结点到根结点路径分支遍历，经过一个分支就得到一位夫曼编码值。

数据结构哈夫曼编码器课程设计报告哈夫曼编码器课程设计报告设计目标：本课程设计的目标是实现一个哈夫曼编码器，能够实现对给定文本文件进行压缩和解压缩操作。

通过使用哈夫曼编码，可以使文本文件的大小大幅度减小，从而节约存储空间。

设计原理及实现方法：本设计主要包括以下几个步骤：1、文本文件的读取：首先需要从外部文件中读取待压缩的文本文件，读取过程可以通过使用文件输入流进行操作。

读取的文本内容将用于构建哈夫曼树和编码表。

2、构建哈夫曼树：哈夫曼树是通过给定文本中的字符出现频率来构建的，出现频率更高的字符将拥有更短的编码。

构建哈夫曼树的过程可以通过使用优先队列和二叉树来实现。

3、编码表：在构建哈夫曼树的过程中，每个字符都会有一个唯一的编码。

根据哈夫曼树的特性，左子树的编码为0，右子树的编码为1，根据这个规则可以通过遍历哈夫曼树来编码表。

4、压缩文本文件：在编码表后，可以利用编码表来对文本文件进行压缩操作。

遍历文本文件中的每个字符，通过编码表将字符转换为对应的哈夫曼编码，并将编码存储在一个压缩文件中。

5、解压缩文本文件：解压缩操作是压缩操作的逆过程。

根据编码表将压缩文件中的哈夫曼编码逐个解码为字符，并将解码后的字符写入解压缩文件中。

附件说明：本文档的附件包括以下内容：1、源代码文件：- HuffmanEncoder：java：包含了哈夫曼编码器的主要实现代码。

- Mn：java：包含了测试哈夫曼编码器的主函数。

2、示例文本文件：- input：txt：用于测试的示例文本文件。

法律名词及注释：本文档中涉及的法律名词及注释如下：1、哈夫曼编码：用于数据压缩的一种编码方式，旨在通过减少字符的编码长度来节省存储空间。

2、压缩：将原始文件经过编码转换为较短的文件，从而减小存储空间的占用。

3、解压缩：将压缩文件经过解码转换为原始文件，恢复原始文件的过程。

全文结束。