下载文档原格式
软件综合课程设计哈夫曼编码/译码器二叉排序树的实现二〇一四年六月二叉排序树的实现一、内容用顺序和二叉链表作存储结构1)以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；2)对二叉排序树T作中序遍历，输出结果；3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；二、程序代码#include <stdio.h>#include <stdlib.h>#define MAX 64 //规定树中结点的最大数目typedefstruct node{ //定义数据结构intltag,rtag; //表示child域指示该结点是否孩子char data; //记录结点的数据struct node *lchild; //记录左右孩子的指针struct node *rchild;}TBtree;TBtree *Que[MAX]; //建队，保存已输入的结点的地址TBtree *CreatTree(){ //建树函数，返回根指针charch;intfront,rear;TBtree *T,*s;T=NULL;front=1;rear=0; //置空二叉树printf("进行初始化，创建二叉树(按满二叉树序号顺序输入，中间的虚节点用\"@\"表示,\"#\"结束)\n");ch=getchar(); //输入第一个字符while(ch!='#') //判断是否为结束字符{s=NULL;if(ch!='@') //判断是否为虚结点{s=(TBtree *)malloc(sizeof(TBtree));s->data=ch;s->lchild=NULL;s->rchild=NULL;s->rtag=0;s->ltag=0;}rear++;Que[rear]=s; //将结点地址加入队列中if(rear==1)T=s; //输入为第一个结点为根结点else{if(s!=NULL&&Que[front]!=NULL) //孩子和双亲结点均不是虚结点{if(rear%2==0)Que[front]->lchild=s;elseQue[front]->rchild=s;}if(rear%2==1)front++;}ch=getchar();}return T;}void Inorder(TBtree *T) //中序遍历{if(T!=NULL){if(T->ltag!=1)Inorder(T->lchild);printf("%c→",T->data);if(T->rtag!=1)Inorder(T->rchild);}}TBtree *pre=NULL;void PreThread(TBtree *root) //中序线索化算法，函数实现{TBtree *p;p=root;if(p){PreThread(p->lchild);//线索化左子树if(pre&&pre->rtag==1)pre->rchild=p; //前驱结点后继线索化if(p->lchild==NULL){p->ltag=1;p->lchild=pre;}if(p->rchild==NULL) //后继结点前驱线索化p->rtag=1;pre=p;PreThread(p->rchild);}}void PrintIndex(TBtree *t) //输出线索{TBtree *f;f=t;if(f){if(f->ltag==1&&f->lchild==NULL&&f->rtag==1)printf("【%c】",f->data); //如果是第一个结点if(f->ltag==1&&f->lchild!=NULL)printf("%c→【%c】",f->lchild->data,f->data); //如果此结点有前驱就输出前驱和此结点if(f->ltag==1&&f->rtag==1&&f->rchild!=NULL)printf("→%c",f->rchild->data); //如果此结点有前驱也有后继，就输出后继else if(f->rtag==1&&f->rchild!=NULL)printf("【%c】→%c",f->data,f->rchild->data);//如果没有前驱，就输出此结点和后继printf("\n");if(f->ltag!=1)PrintIndex(f->lchild);if(f->rtag!=1)PrintIndex(f->rchild);}}TBtree *SearchChild(TBtree *point,charfindnode) //查找孩子结点函数{TBtree *point1,*point2;if(point!=NULL){if(point->data==findnode) return point;elseif(point->ltag!=1){point1=SearchChild(point->lchild,findnode);if(point1!=NULL)return point1;}if(point->rtag!=1){point2=SearchChild(point->rchild,findnode);if(point2!=NULL)return point2;}return NULL;}return NULL;}TBtree *SearchPre(TBtree *point,TBtree *child) //查找父亲结点函数{TBtree *point1,*point2;if(point!=NULL){if((point->ltag!=1&&point->lchild==child)||(point->rtag!=1&&point->rc hild==child)) return point;elseif(point->ltag!=1){point1=SearchPre(point->lchild,child);if(point1!=NULL)return point1;}if(point->rtag!=1){point2=SearchPre(point->rchild,child);if(point2!=NULL)return point2;}return NULL;}elsereturn NULL;}void Insert(TBtree *root){charch;char c;TBtree *p1,*child;printf("请输入要插入的结点的信息:");scanf("%c",&c);scanf("%c",&c);p1=(TBtree *)malloc(sizeof(TBtree)); //插入的结点信息p1->data=c;p1->lchild=NULL;p1->rchild=NULL;p1->rtag=0;p1->ltag=0;printf("输入查找的结点信息:");scanf("%c",&ch);scanf("%c",&ch);child=SearchChild(root,ch); //查孩子结点的地址if(child==NULL){printf("没有找到结点\n");return ;}else printf("发现结点%c\n",child->data);if(child->ltag==0) //当孩子结点有左孩子的时候{//p2=child;child=child->lchild;while(child->rchild&&child->rtag==0) //找到左子树下，最右结点child=child->rchild;printf("发现结点%c\n",child->data);p1->rchild=child->rchild; //后继化p1->rtag=1;child->rtag=0;child->rchild=p1; //连接p1->lchild=child; //前驱化p1->ltag=1;}else //当孩子结点没有左孩子的时候{p1->lchild=child->lchild; //前驱化child->ltag=0;p1->ltag=1;child->lchild=p1;p1->rchild=child;p1->rtag=1;}printf("\n插入结点操作已经完成，并同时完成了线索化的恢复\n");}voidDeleteNode(TBtree *t){TBtree *child,*pre,*s,*q;charch;printf("输入查找的结点信息:");ch=getchar();ch=getchar();child=SearchChild(t,ch);printf("发现结点:%c\n",child->data);printf("ltag=%d,rtag=%d\n",child->ltag,child->rtag);pre=SearchPre(t,child);printf("发现结点:%c\n",pre->data);if(NULL==child){printf("没有找到结点:");return;}system("pause");if(child==pre->lchild||child==pre) //是父亲结点的左孩子{if(1==child->ltag&&1==child->rtag)//孩子结点无左右{pre->lchild=child->lchild;pre->ltag=1;if(child->lchild!=NULL)if(child->lchild->rtag==1)child->lchild->rchild=pre;free(child);}else if(1!=child->ltag&&1==child->rtag)//孩子结点有左无右{pre->lchild=child->lchild;s=child->lchild;while(s->rchild&&s->rtag!=1)s=s->rchild;s->rchild=child->rchild;free(child);}else if(1==child->ltag&&1!=child->rtag)//孩子结点有右无左{pre->lchild=child->rchild;s=child->rchild;while(s->lchild&&s->ltag!=1) //查找左子树最左下点s=s->lchild;s->lchild=child->lchild;if(child->lchild!=NULL)if(child->lchild->rtag==1)child->lchild->rchild=pre;free(child);}else if(1!=child->ltag&&1!=child->rtag)//孩子结点左右都有 {pre->lchild=child->lchild;s=child->rchild;while(s->lchild&&s->ltag!=1)//右子树的左下s=s->lchild;q=child->lchild;while(q->rchild&&q->rtag!=1)//左子树的右下q=q->rchild;q->rchild=child->rchild;q->rtag=0;s->lchild=q;free(child);}}if(child==pre->rchild) //是父亲结点的右孩子{if(1==child->ltag&&1==child->rtag)//孩子结点无左右{pre->rchild=child->rchild;pre->rtag=1;if(child->rchild!=NULL)if(child->rchild->ltag==1)child->rchild->lchild=pre;free(child);}else if(1!=child->ltag&&1==child->rtag)//孩子结点有左无右{pre->rchild=child->lchild;s=child->lchild;while(s->rchild&&s->rtag!=1)s=s->rchild;s->rchild=child->rchild;if(child->rchild!=NULL)if(child->rchild->ltag==1)child->rchild->lchild=pre;free(child);}else if(1==child->ltag&&1!=child->rtag)//孩子结点有右无左{pre->rchild=child->rchild;s=child->rchild;while(s->lchild&&s->ltag!=1)s=s->lchild;s->lchild=child->lchild;free(child);}else if(1!=child->ltag&&1!=child->rtag)//孩子结点左右都有{pre->rchild=child->rchild;s=child->rchild;while(s->lchild&&s->ltag!=1)//右子树的左下s=s->lchild;q=child->lchild;while(q->rchild&&q->rtag!=1)//左子树的右下q=q->rchild;s->lchild=child->lchild;s->ltag=0;q->rchild=s;free(child);}}printf("\n删除结点操作已经完成，并同时完成了线索化的恢复\n");printf("find %c",child->data);return;}int main(void){TBtree *T;inti;T=CreatTree();printf("\n");i=1;while(i){printf("\t1.二叉树的线索化\n");printf("\t2.线索二叉树插入操作\n");printf("\t3.线索二叉树删除操作\n");printf("\t4.中序输出\n");printf("\t5.线索输出\n");printf("\t0.退出\n");printf("\t 请选择:");scanf("%d",&i);printf("\n");switch(i){case 1:PreThread(T);printf("\t已经实现二叉树的线索化\n");printf("\n");break;case 2:Insert(T);printf("\n");break;case 3:DeleteNode(T);printf("\n");break;case 4:Inorder(T);printf("\n");break;case 5:PrintIndex(T);break;case 0:exit(1);default:printf("error\n\t请继续选择:");}}return 0;}三．运行结果二叉树创建：二叉树线索化：线索二叉树插入结点：线索二叉树删除结点：四、设计总结通过这次设计，我懂得了学习的重要性，了解到理论知识与实践相结合的重要意义，学会了坚持、耐心和努力，这将为自己今后的学习和工作做出了最好的榜样。
目录一、系统开发的背景 (1)二、系统分析与设计 (1)（一）系统功能要求 (1)（二）系统模块结构设计 (2)三、系统的设计与实现 (2)（一）哈夫曼树的定义 (2)四、系统测试 (3)（一）测试MAIN_FORM()函数 (3)（二）测试VOID HFMCODING(HFMTREE &HT,HFMCODE &HC,INT N)函数，测试的结果 (4)（三）测试编码函数，测试结果如下 (4)（四）测试译码函数，测试结果如下 (4)（五）测试退出函数，测试结果如下 (5)五、总结（实验心得） (5)六、附件（源代码） (6)哈夫曼编译码一、系统开发的背景随着计算机的应用越来越普遍，它的应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。
为了确保能够更好的保存机密性文件、安全的传送某一个重要的东西，利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。
对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码器。
因此我为这样的信息收发站设计了一个简单的哈夫曼的编码/译码器。
二、系统分析与设计（一）系统功能要求一个完整的哈夫曼编码/译码器应具有以下功能：1、初始化：从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
2、编码：利用以建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
3、译码：利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
4、退出。
（二）系统模块结构设计通过对此功能的分析，哈夫曼编码/译码器的功能如图1所示。
哈夫曼编码/译码器1.初始化2.编码3.译码0.退出图1 哈夫曼编码/译码器的功能图通过上图的功能分析，把整个系统划分为4个模块：1、初始化，该模块主要实现：哈夫曼二叉树的定义以及哈夫曼二叉树的建立，借助函数void hfmcoding（）来实现；2、编码，该模块主要实现：把输入的字符和代码以二进制的形式存储起来，借助函数void hfmcoding（）来实现；3、译码，该模块主要实现：把以二进制形式存储起来的代码，转换成字符的形式并输出，借助函数来实现；4、退出。
山西大学计算机与信息技术学院实验报告姓名学号专业班级课程名称数据结构实验日期成绩指导教师批改日期实验名称哈夫曼编/译码器一、实验目的：为信息收发站写一个哈弗曼编码的编译系统。
二、实验内容:1、概要设计（1）抽象数据类型树的定义如下：ADT Tree {数据对象D:D是具有相同特性的数据元素的集合。
数据关系R:若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R={H},H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}≠Φ，则存在D-{root}的一个划分D1，D2，…，D m（m＞1），对任意j≠k （1≤j，k≤m）有D j∩D k=Φ,且对任意的i（1≤i≤m），唯一存在数据元素x i∈D i有<root,x i>∈H；（3）对应于D-{root}的划分，H-{<root,x1>，…，<root,x m>}有惟一的一个划分H1，H2，…，H m（m＞0），对任意j≠k（1≤j，k≤m）有H j∩H k=Φ,且对任意的i（1≤i≤m），H i是D i上的二元关系（D i，{H i}）是一棵符合本定义的树，称为根root的子树。
基本操作P:InitTree(&T)；操作结果：构造空树T。
DestroyTree(&T)；初始条件：树T存在。
操作结果：销毁树T。
CreateTree(&T，definition)；初始条件：definition给出树T的定义。
操作结果：按definition构造树T。
ClearTree(&T)；初始条件：树T存在。
操作结果：将树T清为空树。
TreeEmpty(T)；初始条件：树T存在。
操作结果：若T为空树，返回TREE，否则返回FALSE。
TreeDepth(T)；初始条件：树T存在。
操作结果：返回T的深度。
Root(T)；初始条件：树T存在。
具体介绍：在本课题中，我们在硬盘E盘中预先建立一个file1.txt文档，在里面编辑一篇文章(大写)。
然后运行程序，调用fileopen()函数读出该文章，显示在界面；再调用jsq()函数对该文章的字符种类进行统计，并对每个字符的出现次数进行统计，并且在界面上显示；然后以每个字符出现次数作为权值，调用ChuffmanTree()函数构建哈夫曼树；并调用print1()和print2()函数将哈夫曼的存储结构的初态和终态进行输出。
然后调用HuffmanEncoding()函数对哈夫曼树进行编码，调用coding()函数将编码写入文件；再调用decode()对编码进行译码，再输出至界面。
至此，整个工作就完成了。
测试数据：例如从文本中读到文章为：IAMASTUDENT。
则效果如下：IAMASTUDENT--------------------------------------HuffmanTree的初态:200010001000100010001000100020001000-000-000-000-000-000-000-000-000--------------------------------------字符A次数:2字符D次数:1字符E次数:1字符I次数:1字符M次数:1字符N次数:1字符S次数:1字符T次数:2字符U次数:1--------------------------------------HuffmanTree的终态:21300110001100011100111001120011200214001130021423215452156731691416810417111271713141101516--------------------------------------译码后的字符串:IAMASTUDENT********************************************************** Press any key to continue文档由风行播放器/暴风影音2014：/整理3系统（项目）设计(1)设计思路及方案本课题是用最优二叉树即哈夫曼树来实现哈夫曼编码译码器的功能。
《数据结构》课程设计目录1. 问题描述……………………………………………第 2页2. 系统设计……………………………………………第 2页3. 数据结构与算法描述………………………………第 5页4. 测试结果与分析……………………………………第 6页5. 总结 (10)6. 参考文献 (10)附录程序源代码 (11)课程设计题目1. 问题描述利用哈夫曼编码进行信息通信可大大提高信道利用率，缩短信息传输时间，降低传输成本。
要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。
对于双工信道（既可以双向传输信息的信道），每端都需要一个完整的编/译码系统。
试为这样的信息收发站写一个哈夫曼的编/译码系统。
2.1基本要求一个完整的系统应具有以下功能：1）I：初始化（Initialization）。
从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
输出哈夫曼树，及各字符对应的编码。
2）W：输入（Input）。
从终端读入需要编码的字符串s，将字符串s存入文件Tobetran.txt中。
3）E：编码（Encoding）与译码（Decoding）。
编码（Encoding）。
利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
译码（Decoding）。
利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
打印代码文件（Print）。
将文件CodeFile以紧凑格式显示在终端上，每行50个代码。
同时将此字符形式的编码写入文件CodePrint中。
4）T：打印哈夫曼树（Tree Printing）。
将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
5）Q：退出程序。
实验九哈夫曼编码-译码器实验十哈夫曼编/译码器一、实验目的(1)掌握哈夫曼树的构造和应用(2)利用哈夫曼方法及其编/译码技术实现对传输信息编码/译码系统二、实验内容[问题描述](设计性实验)哈夫曼树很易求出给定字符集及其概率(或频度)分布的最优前缀码。
哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。
该技术一般可将数据文件压缩掉20,至90,，其压缩效率取决于被压缩文件的特征。
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传送电文须预先编码，在接收须将传送来的数据进行译码。
请自行设计实现一个具有初始化、编码、译码、输入/输出等功能的哈夫曼码的编码/译码系统。
并实现以下报文的编码和译码:“this program is my favorite”。
[测试数据]某通信的电文字符集为26个英文字母及空格字符，其出现频度如下表所示:[实现提示]如何创建哈夫曼树及如何求得各结点对应的哈夫曼编码算法:参见ppt。
1、设计思想描述(1) 问题分析。
(2) 哈夫曼树中各结点的结构描述(提示:图示)。
(3) 哈夫曼树的存储结构描述(提示:分析采用顺序存储还是利用链式存储等)。
2、主要算法设计与实现[要求]1)、利用类模板来实现。
2)、类中各成员函数要求给出自行设计的算法步骤描述及主要设计思想。
3)、给出类中各成员函数算法设计实现。
4)、对自行设计的各算法进行评估(提示:时间复杂度、空间复杂度等)。
#include<iostream>#include<string>using namespace std;const int MAX = 1000;class HTree;class HTNode{friend class HTree;unsigned int weight;unsigned int parent, lchild, rchild; };class HuCode{friend class HTree;char *ch; //字符的编码char data;//被编码的字符};//动态分配数组存储哈夫曼编码表。
哈夫曼编码译码器实验报告实验名称：哈夫曼编码译码器实验一、实验目的：1.了解哈夫曼编码的原理和应用。
2.实现一个哈夫曼编码的编码和译码器。
3.掌握哈夫曼编码的编码和译码过程。
二、实验原理：哈夫曼编码是一种常用的可变长度编码，用于将字符映射到二进制编码。
根据字符出现的频率，建立一个哈夫曼树，出现频率高的字符编码短，出现频率低的字符编码长。
编码过程中，根据已建立的哈夫曼树，将字符替换为对应的二进制编码。
译码过程中，根据已建立的哈夫曼树，将二进制编码替换为对应的字符。
三、实验步骤：1.构建一个哈夫曼树，根据字符出现的频率排序。
频率高的字符在左子树，频率低的字符在右子树。
2.根据建立的哈夫曼树，生成字符对应的编码表，包括字符和对应的二进制编码。
3.输入一个字符串，根据编码表将字符串编码为二进制序列。
4.输入一个二进制序列，根据编码表将二进制序列译码为字符串。
5.比较编码前后字符串的内容，确保译码正确性。
四、实验结果：1.构建哈夫曼树：-字符出现频率：A(2)，B(5)，C(1)，D(3)，E(1) -构建的哈夫曼树如下：12/\/\69/\/\3345/\/\/\/\ABCDE2.生成编码表：-A:00-B:01-C:100-D:101-E:1103.编码过程：4.译码过程：5.比较编码前后字符串的内容，结果正确。
五、实验总结：通过本次实验，我了解了哈夫曼编码的原理和应用，并且实现了一个简单的哈夫曼编码的编码和译码器。
在实验过程中，我充分运用了数据结构中的树的知识，构建了一个哈夫曼树，并生成了编码表。
通过编码和译码过程，我进一步巩固了对树的遍历和节点查找的理解。
实验结果表明，本次哈夫曼编码的编码和译码过程正确无误。
在实验的过程中，我发现哈夫曼编码对于频率较高的字符具有较短的编码，从而实现了对字符串的高效压缩。
同时，哈夫曼编码还可以应用于数据传输和存储中，提高数据的传输效率和存储空间的利用率。
通过本次实验，我不仅掌握了哈夫曼编码的编码和译码过程，还深入了解了其实现原理和应用场景，加深了对数据结构和算法的理解和应用能力。
摘要随着计算机的普遍应用与日益发展,其应用早已不局限于简单的数值运算,而涉及到问题的分析,数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。
算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论,方法和技术基础。
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。
对于双工通信（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统，试设计一个哈夫曼编码系统。
关键词：Huffman编码树；编码；译码AbstractWith the widespread application and the development of computer, its application is not limited to a simple numerical computation, and relates to theproblem analysis, data structure design of the framework for the design and the shortest route of complicated non numerical processing and operation. The algorithm and data structure of learning for the future is the use of computer resources efficiently to develop computer programs non numerical treatment to lay a solid theoretical foundation, methods and techniques.The use of Huffman coding can greatly improve the communication channel utilization, reduce the information transmission time, lower transmission costs.However, this requires the sending end through a coding system for pre encoded data, at the receiving end of data from the decoding (Fu Yuan). Forduplex communication (which can be a two-way channel to transmit information),each side needs a complete encoding / decoding system, try to design a Huffman coding system.Keywords: Huffman coding tree; coding;decoding目录1概述 (1)1.1设计背景 (1)1.2问题分析 (1)1.3设计任务 (2)1.4总体结构 (2)2总体设计 (3)2.1总体设计思想、设计方案的选择 (3)2.1.1最优二叉树（Huffman树） (3)2.1.2构造哈夫曼树的步骤 (3)2.1.3数据结构的选择 (4)2.2结构设计 (4)2.2.1结构体存储表示 (4)2.2.2主函数模块 (4)2.2.3系统结构图 (5)3详细设计........................................... 错误！未定义书签。
3.1构造哈夫曼树.................................. 错误！未定义书签。
3.2哈夫曼编码................................... 错误！未定义书签。
4系统实现与测试 (9)4.1错误分析 (9)4.2运行结果 (9)5 总结 (12)参考文献 (13)致谢 (14)附录 (15)1概述1.1设计背景1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。
导师Robert M. Fano给他们的学期报告的题目是，寻找最有效的二进制编码。
由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。
由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。
哈夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。
哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。
哈夫曼压缩属于可变代码长度算法一族。
意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。
因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。
利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。
对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。
1.2问题分析哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。
它是一种变长的编码。
哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。
在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。
构造好哈夫曼树后，就可根据哈夫曼树进行编码。
然而怎样构造一棵哈夫曼树呢？最具有一般规律的构造方法就是哈夫曼算法。
字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。
只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。
显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。
分析此次设计，是关于实现利用哈夫曼算法编码和译码功能的问题，要求能重复地显示并处理以下项目，即构造哈夫曼树，编码及译码几项功能，直到选择退出为止。
本次设计就是为这样的一个哈夫曼的编/译码器。
1.3设计任务主要内容：设计一个利用哈夫曼算法的编码和译码系统，可以接收从键盘输入的字符集大小、字符和权值信息，创建哈夫曼树生成哈夫曼编码并能对其进行解码。
功能指标：1.使用二叉链表存储结构，主要功能有：建立哈夫曼树、利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件中的正文进行编码、对文件中的代码进行译码、显示输出等功能；2.用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”.表1.1 字符集和频度字符 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.4总体结构本程序主要分为3个模块：主模块，编码模块，译码模块。
主模块：程序的主体部分，分别调用各个模块，实现各项功能。
编码模块：对每个出现的字符进行编码。
译码模块：将已有编码译成字符，使之可以直接被读出。
2总体设计2.1总体设计思想、设计方案的选择哈夫曼编码所以能产生较短的码文，是因为哈夫曼树具有最小加权路径长度的二叉树。
如果叶结点的权值恰好是某个需编码的文本中各字符出现的次数，则编码后文本的长度就是该哈夫曼树的加权路径长度。
译码过程为自做向右逐一扫描码文，并从哈夫曼树的根开始，将扫到的二进制位串中的相邻位与哈夫曼树上标的0，1相匹配，以确定一条从根到叶子结点的路径，一旦到达叶子，则译出了一个字符。
再回到树根，从二进位串的下一位开始继续译码。
2.1.1 最优二叉树（Huffman 树）首先给出路径和路径长度的概念。
从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称作路径长度。
树的路径长度是从树根到每一结点的路径长度之和。
结点的带权路径长度为从该结点到树根之间的路径长度与节点上权的乘积。
树的带权路径长度为书中所有叶子结点的带权路径长度之和，通常记做∑==nk l w k k WPL 1。
那么假设有n 个权值},,{21n w w w ⋅⋅⋅，试构造一棵有n 个叶子结点的二叉树，每个叶子结点带权为i w ，则其中带权路径长度WPL 最小的二叉树称作最优二叉树或Huffman 树。
2.1.2构造哈夫曼树的步骤步骤如下：1、对给定的n 个权值{W1,W2,W3,...,Wi,...,Wn}构成n 棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti 中只有一个权值为Wi 的根结点，它的左右子树均为空。
（为方便在计算机上实现算法，一般还要求以Ti 的权值Wi 的升序排列。
）；2、选取左右子树：在F 中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
3、删除左右子树：从F 中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F 中。
4、重复2、3两步：重复2和3，直到集合F 中只有一棵二叉树为止。
2.1.3数据结构的选择为了建立哈夫曼树以及实现哈夫曼编码以及译码，因此我们选择了结点结构体，利用这一结构体，我们定义了一个结构体数组和一个树根指针，数组用来纪录输入数据的多少，树根指针用来连接哈夫曼树。
从程序中可以看到使用哈夫曼算法构造哈夫曼树过程，是从n棵知识一个根结点的树组成的森林开始的。
在算法执行中，哈夫曼树是由若干棵树组成的森林，通过不断地合并树，最后得到一棵哈夫曼树。
2.2结构设计2.2.1结构体存储表示typedef struct{char ch;unsigned int weight;unsigned int parent, lchild, rchild;}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树typedef char **HuffmanCode; //动态分配数组存储哈弗曼编2.2.2主函数模块在主函数实现过程，使用开关语句switch（）函数对函数的各模块调用，使得函数的运行效率大大提高，主函数实现功能用如下算法表示。
