数据结构课程设计解读.ppt

数据结构课程设计 哈夫曼编/译码器----问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输预先编码，在接收端将传来的数据进行译码。对于双工通道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。 哈夫曼编/译码器----基本要求 一个完整的系统应具有以下功能： 初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。 编码。利用已建好的哈夫曼树，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 译码。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。 以下为选做： 印代码文件（Print）.将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 印哈夫曼树（Treeprinting）.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint 中 测试数据见：《数据结构题集》P149 实验报告：参见同上P75 哈夫曼编/译码器----最低要求 字符集8个，频度见课本P148的例6-2的频度，建立哈夫曼树。 8个字符的哈夫曼编码屏幕输出 哈夫曼编/译码器----算法分析 例6-2 已知某系统在通信联络中只可能出现八种字符， 其频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11， 试设计哈夫曼编码。 12 2 15 58 0 0 12 14 0 0 10 7 4 3 12 15 0 0 13 23 0 0 11 11 9 8 13 19 7 1 11 8 0 0 9 3 0 0 9 5 0 0 14 29 14 13 0 100 11 6 15 42 10 5 14 29 0 0 10 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 weight parent lchild rchild 0 0 0 - 0 0 0 14 0 0 0 7 0 0 0 - 0 0 0 23 0 0 0 11 0 0 0 - 0 0 0 - 0 0 0 3 0 0 0 5 0 0 0 29 0 0 0 - 0 0 0 - 0 0 0 - 0 0 0 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 weight parent lchild rchild HT初态 HT终态 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 0 1 2 3 4 5 6 7 8 哈夫曼编码HC 算法分析 typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; Type char **HuffmanCode; void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n){ if( n=1 ) return; m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT,i=1;i=n;++i,++p,++w) *p={*w,0,0,0}; for(;i=m;++i,++p) *p={*w,0,0,0}; for(i=n+1;i=m;++i){ 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; } 算法分析 算法分析 //从叶子到根逆向求每个字符的赫夫曼编码 HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); cd=(char*)malloc(n*sizeof