课程设计--哈夫曼编码-译码器（树的应用）.doc

哈夫曼编码/译码器（树的应用） 1) 基本要求： 系统应具有以下功能： （1） 构造哈夫曼树及哈夫曼编码：从终端读入字符集大小n、n个字符及n个对应权值，建立哈夫曼树；利用已经建好的哈夫曼树求每个叶结点的哈夫曼编码，并保存； （2） 编码：利用已构造的哈夫曼编码对“明文”文件中正文进行编码，然后将结果“密文”存入文件中； （3） 译码：将“密文”文件中的0、1代码序列进行译码； （4） 打印哈夫曼编码； （5） 打印“明文”和对应的“密文”文件。 2) 提示分析 采用静态链表作为哈夫曼树的存储结构（参照书中结构）。 在microsoft visual c++环境下能运行无错误的源代码...不用太复杂，希望能有注解，注解OK运行OK会在追加最高财富值。高手帮帮忙，剩没几天了唉译码部分茫然啊includeiostream #includefstream #includeiomanip #includestdlib.h using namespace std; # define MaxN 100//初始设定的最大结点数 # define MaxC 1000//最大编码长度 # define ImpossibleWeight 10000//结点不可能达到的权值 # define n 26//字符集的个数 //-----------哈夫曼树的结点结构类型定义----------- typedef struct //定义哈夫曼树各结点 { int weight;//权值 int parent;//双亲结点下标 int lchild;//左孩子结点下标 int rchild;//右孩子结点下标 }HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树 typedef char**HuffmanCode;//动态分配数组存储哈夫曼编码表 //-------全局变量-------- HuffmanTree HT; HuffmanCode HC; int *w;//权值数组 //const int n=26;//字符集的个数 char *info;//字符值数组 int flag=0;//初始化标记 //********************************************************************** //初始化函数 //函数功能： 从终端读入字符集大小n , 以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中 //函数参数： //向量HT的前n个分量表示叶子结点，最后一个分量表示根结点，各字符的编码长度不等，所以按实际长度动态分配空间 void Select(HuffmanTree t,int i,int s1,int s2) { //s1为最小的两个值中序号最小的那个 int j; int k=ImpossibleWeight;//k的初值为不可能达到的最大权值 for(j=1;j=i;j++) { if(t[j].weightkt[j].parent==0) {k=t[j].weight; s1=j;} } t[s1].parent=1; k=ImpossibleWeight; for(j=1;j=i;j++) { if(t[j].weightkt[j].parent==0) {k=t[j].weight; s2=j;} } t[s2].parent=1; } void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int num)//w存放n个字符的权值（均0），构造哈夫曼树HT，并求出n个字符的哈弗曼编码HC { int i,m,c,s1,s2,start,f; HuffmanTree p; char* cd; if(num=1) return; m=2*num-1;//m为结点数，一棵有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用 //--------初始化哈弗曼树------- for(p=HT+1,i=1;i=num;i++,p++,w++) { p-weight=*w; p-parent=0; p-lchild=0; p-