哈夫曼树的应用
《哈夫曼树的应用》
课程设计
学生姓名：蔡丽敏
学号：6103105003
专业班级：计算机科学与技术051班
指导教师：林振荣
二00八年十二月二十七日
目录
1.课程设计目的 (1)
2.课程设计题目设计和要求 (1)
3. 课程设计报告内容 (1)
4. 结论 (25)
5.参考书目 (25)
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. 印哈夫曼树(TreePrinting)。将已在内存中的哈夫曼树以直观的方式(树
或凹入表的形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
测试数据：
(1) 利用下述中的数据调试程序。
(2) 用下表给出的字符集和频度的计数据建立哈曼树,并实现以下报文的编码和
译码：“THIS PROGRAM IS MY FAVORITE”.。
字符 ^ A B C D E F G H I J K L 频数186 64 13 22 32 103 21 15 47 57 1 5 32
字符 M N O P Q R S T U V W X Y Z 频数20 57 63 15 1 48 51 80 23 8 18 1 16 1
3.课程设计报告内容
哈夫曼编码/译码
(一)、需求分析
1、利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（既可以双向传输
信息的信道），每端都需要一个完整的编/译码系统。本次设计就是为这样的信息
收发站写的一个哈夫曼的编/译码器。
本课程设计要求：
2、本演示程序中，用户可以输入键盘中的任意字符，长度为任意长，字符输入
顺序不限，且允许出现重码
3、演示程序以用户与计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据（可
虑去输入中的非法字符）和运算结果显示在其后。
4、本演示程序中，当用户选择的功能错误时，系统会输出相应的提示。
5、在本系统中，用户可以对任意长的字符串可进行编码/译码。
6、程序执行的命令包括：
1) 初始化(I) 2) 编码(E) 3) 译码(D)
4) 印代码文件(P) 5) 印哈夫曼树(T) 6) 退出(Q)
7、测试数据：
(1) 利用下述中的数据调试程序。
(2) 用下表给出的字符集和频度的计数据建立哈曼树,并实现以下报文的编码和
译码：“THIS PROGRAM IS MY FAVORITE”.。
字符 ^ A B C D E F G H I J K L 频数186 64 13 22 32 103 21 15 47 57 1 5 32
字符 M N O P Q R S T U V W X Y Z 频数20 57 63 15 1 48 51 80 23 8 18 1 16 1 (二)、概要设计
为实现上述程序功能，应以指针存储结点。为此，需要定义一个抽象数据类型。1. 抽象数据类型定义为：
ADT HuffmanTree{
数据对象：D={ai| ai∈CharSet,i=1,2,……,n, n≥0}
数据关系：R={< ai-1, ai > ai-1, ai∈D, ai-1基本操作P：
HuffmanTree(); 构造函数
~ HuffmanTree(); 析构函数
Initialization(int WeightNum);
操作结果：构造哈夫曼树。
Encoder()
初始条件：哈夫曼树已存在或者哈夫曼树已存到文件中。
操作结果：对字符串进行编码
Decoder();
初始条件：哈夫曼树已存在且已编码。
操作结果：对二进制串进行译码
Print()
初始条件：编码文件已存在。
操作结果：把已保存好的编码文件显示在屏幕
TreePrinting()
初始条件：哈夫曼树已存在。
操作结果：将已在内存中的哈夫曼树以直观的方式显示在终端上
2.本程序包含三个模块：
1)主程序模块：
void main(){
初始化；
do{
接受命令；
处理命令；
}while(“命令”=”退出”)
}
2)、建树模块——实现定义的抽象数据类型
3)、编/译码模块——实现字符串的编/译码
各模块之间的调用关系如下：
主程序模块
建树模块
编/译码模块
程序代码如下
// 程序名：HuffmanTree.h
// 程序功能：哈夫曼树类的头文件(并用其来实现编/译码)
// 作者：蔡丽敏
// 日期：2008.12.27
// 版本：1.0
//对应类实现文件: HuffmanTree.cpp
//对应主程序文件: main.cpp
1// 程序名：HuffmanTree.h
2// 程序功能：哈夫曼树类的头文件(并用其来实现编/译码)
3
4//对应类实现文件: HuffmanTree.cpp
5//对应主程序文件: main.cpp
6
7
8
9#include
10#include
11#include
12using namespace std;
13struct HuffmanNode //定义哈夫曼树各结点
14{
15 int weight; //存放结点的权值，假设只考虑处理权值为整数的情况
16 int parent; //记录结点父亲位置，-1表示为根结点，否则表示为非根结点
17 int lchild,rchild; //分别存放该结点的左、右孩子的所在单元的编号18};
19class HuffmanTree //建立哈夫曼树类
20{
21private:
22 HuffmanNode *Node; //哈夫曼树中结点的存储结构
23 char *Info; //用来保存各字符信息
24 int LeafNum; //树中的叶子结点总数
25public:
26 HuffmanTree(); //构造函数
27 ~HuffmanTree(); //析构函数
28 void Initialization(int WeightNum); //初始化函数：根据WeightNum
个权值建立一棵哈夫曼树
29 void Encoder(); //编码函数：利用构造好的哈夫曼树对字符进行编码
30 void Decoder(); //译码函数：对二进制串进行译码
31 void Print(); //印文件函数：把已保存好的编码文件显示在屏幕
32 void TreePrinting(); //印哈夫曼树函数：将已在内存中的哈夫曼树以直观的方式显示在终端上
33};
// 程序名：HuffmanTree.cpp
// 程序功能：实现哈夫曼树类的源文件(并用其来实现编/译码)
// 作者：蔡丽敏
// 日期：2008.12.27
// 版本：1.0
1#include"HuffmanTree.h"
2#include
3 using namespace std;
4
5/**//////////////////////////////////////////////////////////////// ///////////////
6// 构造函数
7// 函数功能：将结点指针初始化为NULL
8// 函数参数：无
9// 参数返回值：无
10HuffmanTree::HuffmanTree()
11{
12 Node=NULL; //将树结点初始化为空
13 Info=NULL; //将字符数组初始化为空
14 LeafNum=0; //将叶子数初始化为0
15}
16/**//////////////////////////////////////////////////////////////// ///////////////
17// 析构函数
18// 函数功能：将所有结点的空间释放
19// 函数参数：无
20// 参数返回值：无
21HuffmanTree::~HuffmanTree()
22{
23 delete[] Node; //释放结点空间
24 delete[] Info; //释放字符存储空间
25}
26/**//////////////////////////////////////////////////////////////// ///////////////
27// 初始化函数
28// 函数功能：从终端读入字符集大小n，以及n个字符和n个权值,
29// 建立哈夫曼树,并将它存放在文件hfmTree中.
30// 函数参数：int WeightNum表示代码个数
31// 参数返回值：无
32void HuffmanTree::Initialization(int WeightNum) //初始化
33{
34 int i,j,pos1,pos2,max1,max2; //
35
36 Node=new HuffmanNode[2*WeightNum-1]; //WeightNum权值对应的哈夫曼树中的结点总数为2*WeightNum-1个
37 //Info=new char[2*WeightNum-1];
38 Info=new char[WeightNum];
39 for(i=0;i 40 { 41 cout<<"请输入第"< 42 getchar(); //丢弃字符'\t'与'\n' 43 Info[i]=getchar(); //输入一个字符,主要是考虑输入空格而采用这种形式的 44 //cin>>Info[i]; 45 getchar(); 46 cout<<"请输入该字符的权值或频度"; 47 cin>>Node[i].weight; //输入权值 48 Node[i].parent=-1; //为根结点 49 Node[i].lchild=-1; //无左孩子 50 Node[i].rchild=-1; //无右孩子 51 } 52 53 for(i=WeightNum;i<2*WeightNum-1;i++) //表示需做WeightNum-1次合并 54 { 55 pos1=-1; 56 pos2=-1; //分别用来存放当前最小值和次小值的所在单元编号 57 max1=32767; //32767为整型数的最大值 58 max2=32767; //分别用来存放当前找到的最小值和次小值 59 60 for(j=0;j 61 if(Node[j].parent==-1) //是否为根结点 62 if(Node[j].weight 63 { 64 max2=max1; //原最小值变为次小值 65 max1=Node[j].weight; //存放最小值 66 pos2=pos1; //修改次小值所在单元编号 67 pos1=j; //修改最小值所在单元编号 68 } 69 else 70 if(Node[j].weight 71 { 72 max2=Node[j].weight; //存放次小值 73 pos2=j; //修改次小值所在的单元编号 74 } 75 //for 76 Node[pos1].parent=i; //修改父亲位置 77 Node[pos2].parent=i; 78 Node[i].lchild=pos1; //修改儿子位置 79 Node[i].rchild=pos2; 80 Node[i].parent=-1; //表示新结点应该是根结点 81 Node[i].weight=Node[pos1].weight+Node[pos2].weight; 82 } //for 83 LeafNum=WeightNum; 84 85 86 char ch; 87 cout<<"是否要替换原来文件(Y/N):"; 88 cin>>ch; 89 if(ch=='y'||ch=='Y') 90 { 91 ofstream fop; //以二进制方式打开hfmTree.dat文件，并当重新运行时覆盖原文件 92 fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc); 93 if(fop.fail()) //文件打开失败 94 cout<<"文件打开失败！\n"; 95 fop.write((char*)&WeightNum,sizeof(WeightNum)); //写入WeightNum 96 for(i=0;i 97 { 98 fop.write((char*)&Info[i],sizeof(Info[i])); 99 flush(cout); 100 } 101 for(i=0;i<2*WeightNum-1;i++) //把个节点内容写入文件 102 { 103 fop.write((char*)&Node[i],sizeof(Node[i])); 104 flush(cout); 105 } 106 fop.close(); //关闭文件 107 } 108 cout<<"哈夫曼树已构造完成。\n"; 109}//Initialization 110 111/**/////////////////////////////////////////////////////////////// //////////////// 112// 编码函数 113// 函数功能：利用已建立好的哈夫曼树（如不在内存，则从文件hfmTree 中读入）， 114// 对文件ToBeTran中的正文进行编码,然后将结果代码存(传输)到文件CodeFile中. 115// 函数参数：无 116// 参数返回值：无 117void HuffmanTree::Encoder() 118{ 119 if(Node==NULL) //哈夫曼树不在内存，从文件hfmTree中读入120 { 121 ifstream fip; //以二进制方式打开hfmTree.dat文件 122 fip.open("hfmTree.dat",ios::binary|ios::in); 123 if(fip.fail()) //文件打开失败 124 { 125 cout<<"文件打开失败！\n"; 126 return; //结束本函数 127 } 128 fip.read((char*)&LeafNum,sizeof(LeafNum)); //读取叶子数 129 Info=new char[LeafNum]; 130 Node=new HuffmanNode[2*LeafNum-1]; 131 for(int i=0;i 132 fip.read((char*)&Info[i],sizeof(Info[i])); 133 for(i=0;i<2*LeafNum-1;i++) //读取结点信息 134 fip.read((char*)&Node[i],sizeof(Node[i])); 135 } 136 137 char *Tree; //用于存储需编码内容 138 int i=0,num; 139 char Choose; //让用户选择读取文件或重新输入需编码内容140 cout<<"你要从文件中读取内容(1)，还是重新输入(2):"; 141 cin>>Choose; 142 if(Choose=='1') //读取文件ToBeTran.txt 143 { 144 ifstream fip1("ToBeTran.txt"); 145 if(fip1.fail()) //文件不存在 146 { 147 cout<<"文件打开失败!\n"; 148 return; //结束本函数 149 } 150 char ch; 151 int k=0; 152 while(fip1.get(ch)) 153 { 154 k++; //计算CodeFile中代码长度 155 } 156 fip1.close(); 157 158 Tree=new char[k+1]; 159 ifstream fip2("ToBeTran.txt"); 160 161 k=0; 162 while(fip2.get(ch)) 163 { 164 Tree[k]=ch; //读取文件内容，并存到Tree中 165 k++; 166 } 167 fip2.close(); 168 Tree[k]='\0'; //结束标志 169 cout<<"需编码内容为:"; 170 cout< 171 }//if(Choose=='1') 172 173 else //Choose!='1',重新输入 174 { 175 string tree; //用于输入需编码内容，由于string类对象可以输入任意长度， 176 //所以先利用这个对象输入，再转存在Tree中 177 178 cin.ignore(); 179 cout<<"请输入需要编码的内容(可输入任意长，结束时请按2下回车):\n"; 180 getline(cin,tree,'\n'); //输入任意长字符串， 181 //getline以回车('\n')作为结束符，第一次按回车表示字符串结束，第二次按回车才开始输出。 182 while(tree[i]!='\0') 183 i++; 184 num=i; //计算tree长度 185 i=0; 186 Tree=new char[num+1]; 187 while(tree[i]!='\0') //将tree中的字符转存到Tree中 188 { 189 Tree[i]=tree[i]; 190 i++; 191 } 192 Tree[i]='\0'; //结束标志符 193 } 194 195 ofstream fop("CodeFile.dat",ios::trunc); //存储编码后的代码,并覆盖原文件 196 i=0; 197 int k=0; 198 char *code; 199 code=new char[LeafNum]; //为所产生编码分配容量为LeafNum的存储空间 200 //因为不等长编码中最长的编码一定不会超过要求编码的字符个数 201 while(Tree[k]!='\0') //对每一个字符编码 202 { 203 int j,start=0; 204 for(i=0;i 205 if(Info[i]==Tree[k]) //求出该文字所在单元的编号 206 break; 207 j=i; 208 while(Node[j].parent!=-1) //结点j非树根 209 { 210 j=Node[j].parent; //非结点j的双亲结点 211 if(Node[j].lchild==i) //是左子树，则生成代码0 212 code[start++]='0'; 213 else //是右子树，则生成代码1 214 code[start++]='1';\ 215 i=j; 216 } 217 code[start]='\0'; //置串结束符 218 219 220 for(i=0;i 221 { 222 j=code[i]; 223 code[i]=code[start-i-1]; 224 code[start-i-1]=j; 225 } 226 i=0; 227 while(code[i]!='\0') //存储代码 228 { 229 fop< 230 i++; 231 } 232 k++; 233 } 234 fop.close(); 235 cout<<"已编码！且存到文件CodeFile.dat中！\n\n"; 236} //Encode 237 238/**/////////////////////////////////////////////////////////////// //////////////// 239// 译码函数 240// 函数功能：利用已建好的哈夫曼树,对传输到达的CodeFile中的数据代码进行译码, 241// 将译码结果存入文件TextFile中. 242// 函数参数：无 243// 参数返回值：无 244void HuffmanTree::Decoder() 245{ 246 int i=0,k=0; 247 int j=LeafNum*2-1-1; //表示从根结点开始往下搜索 248 char* BitStr; 249 250 ifstream fip1("CodeFile.dat"); //利用已建好的哈夫曼树将文件CodeFile中的代码进行译码 251 if(fip1.fail()) //文件打开失败，还未编码 252 { 253 cout<< "请先编码！\n"; 254 return; 255 } 256 cout<<"经译码,原内容为:"; 257 char ch; 258 while(fip1.get(ch)) 259 { 260 k++; //计算CodeFile中代码长度 261 } 262 fip1.close(); 263 264 BitStr=new char[k+1]; 265 ifstream fip2("CodeFile.dat"); 266 k=0; 267 while(fip2.get(ch)) 268 { 269 BitStr[k]=ch; //读取文件内容 270 k++; 271 } 272 fip2.close(); 273 BitStr[k]='\0'; //结束标志符 274 if(Node==NULL) //还未建哈夫曼树 275 { 276 cout<<"请先编码!\n"; 277 return; 278 } 279 ofstream fop("TextFile.dat"); //将字符形式的编码文件写入文件CodePrin中 280 while(BitStr[i]!='\0') 281 { 282 if(BitStr[i]=='0') 283 j=Node[j].lchild; //往左走 284 else 285 j=Node[j].rchild; //往右走 286 if(Node[j].rchild==-1) //到达叶子结点 287 { 288 cout< 289 j=LeafNum*2-1-1; //表示重新从根结点开始往下搜索 290 fop< 291 }//if、 292 i++; 293 }//while 294 fop.close(); 295 296 cout<<"\n译码成功且已存到文件TextFile.dat中！\n\n"; 297}//Decoder 298/**/////////////////////////////////////////////////////////////// //////////////// 299// 印文件代码函数 300// 函数功能：将文件CodeFile以紧凑格式显示在终端上， 301// 每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 302// 函数参数：无 303// 参数返回值：无 304void HuffmanTree::Print() 305{ 306 char ch; 307 int i=1; 308 ifstream fip("CodeFile.dat"); //读取文件 309 ofstream fop("CodePrin.dat"); //存储文件 310 if(fip.fail()) 311 { 312 cout<<"没有文件，请先编码！\n"; 313 314 return; 315 } 316 while(fip.get(ch)) 317 { 318 cout< 319 fop< 320 if(i==50) //每行输出50个字符 321 { 322 cout< 323 i=0; 324 } 325 i++; 326 } 327 cout< 328 fip.close(); //关闭CodeFile.dat文件 329 fop.close(); //关闭CodePrin.dat文件 330} 331/**/////////////////////////////////////////////////////////////// //////////////// 332// 印哈夫曼树函数 333// 函数功能：将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式)显示在终端上， 334// 同时将此字符形式的哈夫曼树写入文件TreePrint中。 335// 函数参数：无 336// 参数返回值：无 337void HuffmanTree::TreePrinting() 338{ 339 if(Node==NULL) //未建立哈夫曼树 340 { 341 cout<<"请先建立哈夫曼树！\n"; 342 return; 343 } 344 int i; 345 int j=0,k=LeafNum-1; 346 string *HC; 347 HC=new string[LeafNum]; //定义存储Huffman编码字符串数组 348 for (i=0;i 349 { 350 char *temp=new char[100]; //实验目的，本处没有求二叉树的深度，而采用固定长度的数组存储Huffman中间编码 351 int k=100; 352 int m=i; 353L1:if (Node[m].parent!=-1) //自定义跳转标签 354 { 355 if (Node[Node[m].parent].lchild==m) 356 { 357 temp[--k]='1'; 358 } 359 else 360 { 361 temp[--k]='0'; 362 } 363 m=Node[m].parent; 364 goto L1; //跳转到指定的标签L1 365 } 366 else 367 { 368 int n; 369 for (n=k;n<100;n++) 370 { 371 HC[i]=HC[i]+temp[n]; 372 } 373 } 374 cout< 375 } 376} 377 // 程序名：main.cpp // 程序功能：主函数源文件 // 作者：蔡丽敏 // 日期：2008.12.27 // 版本：1.0 // 主函数 //参数返回值：无 1// 程序名：main.cpp 2// 程序功能：主函数源文件 3 4#include"HuffmanTree.h" 5#include 6#include 7 8/**///////////////////////////////////////////////////////////////// ////////////// 9// 主函数 10//参数返回值：无 11 12int main() 13{ 14 15 cout<<"(I) 初始化;\n"; 16 cout<<"(E) 编码;\n"; 17 cout<<"(D) 译码;\n"; 18 cout<<"(P) 印代码文件;\n"; 19 cout<<"(T) 印哈夫曼树\n"; 20 cout<<"(Q) 退出\n\n"; 21 HuffmanTree huftree; //定义哈夫曼树对象 22 int weight; 23 char Choose; 24 while(1) 25 { 26 cout<<"请从清单中选择一个操作(不区分大小写):"; 27 cin>>Choose; 28 switch(Choose) 29 { 30 case 'I': 31 case 'i': 32 cout<<"请输入编码长度："; 33 cin>>weight; 34 huftree.Initialization(weight); //初始化哈夫曼树 35 break; 36 case 'E': 37 case 'e': 38 huftree.Encoder(); 39 break; 40 case 'D': 41 case 'd': 42 huftree.Decoder(); 43 break; 44 case 'P': 45 case 'p': 46 huftree.Print(); 47 break; 48 case 'T': 49 case 't': 50 huftree.TreePrinting(); 51 break; 52 case 'Q': 53 case 'q': 54 cout<<"\n ***********感谢使用本系统!***********\n\n"; 55 system("pause"); //暂停运行 56 return 0; 57 } 58 cout<<"(I) 初始化;\n"; 59 cout<<"(E) 编码;\n"; 60 cout<<"(D) 译码;\n"; 61 cout<<"(P) 印代码文件;\n"; 数据结构课程设计设计题目：哈夫曼树及其应用 学院：计算机科学与技术 专业：网络工程 班级：网络 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.求每个字符的哈夫曼编码并显示。 授课时间11.9 第17 次课 2007-07-18 哈夫曼树（Huffman树）是带权路径长度最小的二叉树。根据哈夫曼树的定义，一棵二叉树要使其带权路径长度最小，必须使权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。哈夫曼依据这一特点提出了哈夫曼算法，其基本思想是： ⑴初始化：由给定的n个权值{w1，w2，…，wn}构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合F＝{T1， T2，…，Tn}； ⑵选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点权值之和； ⑶删除与加入：在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中； ⑷重复⑵、⑶两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。 通过上述Huffman树的构造过程，我们可以得到如下要点： ⑴当有n个权值（相应的Huffman树中有n个叶子），共需合并n-1次； ⑵每合并一次产生一个分支结点，经过n-1次合并后得到的Huffman树中共有2n-1个结点，其中有n-1个分支结点； ⑶在Huffman树中只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点； ⑷算法要求选取根结点权值最小的两棵二叉树作为左右子树构造一棵新的二叉树，但并没有要求哪一棵作左子树，哪一棵作右子树，所以左右子树的顺序是任意的； ⑸对同一组权值可以构造出不同的huffman树，但是他们的带权路径长度相同。 在建立Huffman树的过程中有以下三种常见的错误： ⑴在合并中不是选取根结点权值最小的两棵二叉树（包括已合并的和未合并的），而是选取未合并的根结点权值最小的一棵二叉树与已经合并的二叉树合并，如图5-10所示。 ⑵每次都是在未合并的二叉树中选取根结点的权值最小的两棵子树，如图5-11所示。 ⑶有时没有严格按照哈夫曼算法也构造出带权路径长度与哈夫曼树相同的二叉树，但那只是巧合，没有规律性，而没有规律性的解法不利于用计算机进行处理。 计算机科学与技术学院数据结构实验报告 班级2014级计算机1班学号20144138021 姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期2016.1.5 一、实验目的 本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree.dat中。 2、编码。 利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入），对文件中的正文进行编码，然后将结果存入文件codefile.dat中。 3、译码。 利用已建好的哈夫曼树将文件codefile.dat中的代码进行译码，结果存入文件textfile.dat中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树， 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为： Typedef strcut { Int weight；/*结点权值*/ Int parent； Int lchild； Int rchild； }HNodeType； 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型： 承诺书 郑重声明：本人所呈交的课程设计是本人在导师指导下独立撰写并完成的，课程设计没有剽窃、抄袭、造假等违反学术道德、学术规范和侵权行为。本课程设计不包含任何其他个人或集体已经发表或撰写过的研究成果，如果引用则标识出了出处。对本课程设计的研究做出贡献的个人和集体，均已在文中以明确方式标明。 课程设计与资料若有不实之处，本人承担一切相关责任。特此声明。 签名： 年月日 目录 一．需求分析 (3) 1.问题描述 (3) 2.功能要求 (3) 二．系统总框图和功能模块说明.4 1.系统总框图 (4) 2.功能模块说明 (4) 2.功能模块说明 (4) 3.系统设计 (4) 3.1主要链表 (4) 3.2主要功能函数 (6) 3.3关键函数的流程图 (6) 4.系统调试： (9) 5.总结 (13) 6.源程序： (13) 一．需求分析 哈夫曼编/译码器 1.问题描述 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。 2.功能要求 I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。 E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。 T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。 目录 一、程序设计目的与要求 (3) 1.1程序设计目的 (3) 1.2程序设计要求 (3) 二、需求分析 (4) 三、概要设计 (4) 3.1哈夫曼树的构造过程 (4) 3.2译码过程是编码过程的逆过程 (5) 3.3 构造哈夫曼树和哈夫曼编码类的描述 (5) 四、详细设计 (6) 五、调试分析 (11) 5.1程序编译界面 (11) 5.2程序运行界面 (12) 六、测试结果 (13) 七、附录 (15) 7.1设计心得 (15) 7.2参考文献 (15) 一、程序设计的目的与要求 1.1程序设计目的 课程设计是《数据结构》课程教学必不可缺的一个重要环节，通过课程设计，使学生对整个课程的知识体系有较深入的理解，在运用本课程的知识解决实际问题方面得到锻炼，对锻炼学生的实践能力以及运用本课程的知识、方法解决更为复杂的实际问题有较好的启发和指导作用，从而为后续课程的学习，毕业设计环节以及将来的实际工作打好坚实的基础。本课程设计的目是： 1.培养学生将所学的算法知识应用于程序设计过程中，设计出运行效率更高的 程序； 2.了解数据的三种逻辑结构（线性结构、树结构、图结构）和四种存储结构（顺 序、链接、索引、散列）的基本特性和相互关系； 3.掌握算法知识，学会设计算法并对算法进行分析和评价。 1.2程序设计要求 在设计时严格按照题意独立进行设计，不得随意更改。要求熟悉C、C++等某一种高级程序设计语言。通过本课程的学习与实践，学生应做到： 1.掌握数据结构的基本概念和基本理论。 2.熟练掌握顺序表、链表、队列、栈、树以及二叉树、图等基本数据结构的设 计和分析。 3.熟练地掌握常用算法（递归、遍历、查找、排序）的知识。 4.能对所求解的问题进行分析，抽象出逻辑结构，选择合适的存储结构，定义 所需的运算，设计相应的算法。 5.对算法进行分析和评价。 实验六哈夫曼树的建立与操作 一、实验要求和实验内容 1、输入哈夫曼树叶子结点（信息和权值） 2、由叶子结点生成哈夫曼树内部结点 3、生成叶子结点的哈夫曼编码 4、显示哈夫曼树结点顺序表 二、详细代码（内包含了详细的注释）： #include cout<<"输入第"< 哈夫曼树描述文档 一、思路 通过一个argv[]数组存储从test文件中读取字母，然后利用ascal 码循环计算每个字母的权值，利用weight[]是否为零，确定叶子节点，节点个数为count，传入到构建哈夫曼树的子程序中，然后利用cd[]数组存储每一个叶子节点的哈夫曼代码.输出代码时，通过与argv[]数组的比对，扫描ht数组，进而读出所有的数据。 二、截图 三、代码 #include intrchild; }HTNode; typedefstruct { char cd[50]; int start; }HCode; using namespace std; int enter(char argv[])//进行读入操作 { fstream in; ofstream out; char c; int number=0;//字母个数置为0 in.open("test.txt",ios::in); //打开文件test.txt out.open ("code.txt",ios::trunc); //打开文件code.txt，如果不存在就新建一个，如果存在就清空 if(!in.eof()) in>>c; //从test.txt中读取一个字符存入c printf("原文本是:\n"); while(! in.eof()){ //文件不为空，循环读取一个字符 cout< 常熟理工学院微课教学比赛教学设计 1、课程基本信息 课程名称：哈夫曼树及应用所属课程：数据结构与算法 课程所属专业：软件工程适用专业：计算机类 选用教材：严蔚敏，吴伟明编著《数据结构（C语言版）》北京：清华大学出版社，2007 主讲人：周思林时长：15分钟 所属学校：常熟理工学院所属院系：计算机科学与工程学院 2.教学背景 《数据结构与算法》课程是计算机类专业的学科基础课程，本节微课“哈夫曼树及应用”属于数据结构课程中的“树与二叉树”章节中的重点及难点。 2.1《数据结构与算法》课程简介及特点 《数据结构与算法》课程是计算机类专业的学科基础课程，同时也是计算机类专业的核心课程。课程的主要目标是使学生理解和掌握基本数据结构的概念、经典算法的思想及实现方法，具备为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法的能力。数据结构与算法课程的学习也是复杂程序设计的训练过程，通过算法设计和实践，培养学生的数据抽象和复杂程序设计能力。 《数据结构与算法》课程由线性结构、树形结构、图状结构三种逻辑结构和查找、排序算法为主体，结合应用型本科院校特点，通过实践理解和掌握基本数据结构与算法，在实践中提高学生的专业素养和专业技能。 2.2本节微课课程特点 “树与二叉树——哈夫曼树及应用”是《数据结构与算法》课程中第六章“树与二叉树”的核心内容之一，同时也是该章节的教学难点。 本节微课采用案例驱动法进行教学，调动学生的学习积极性，引导学生发现问题、思考问题、解决问题，利用形象的多媒体动画展示案例的执行过程，将哈夫曼树及编码复杂的程序结构趣味化、形象化。由发送报文问题引入课程，循序渐进的介绍哈夫曼树的概念、逻辑特性、存储结构和算法实现，使学生掌握哈夫曼树及编码的基本概念和算法，提升学生的程序设计及逻辑思维能力。 3.教学设计 3.1教学目的 通过本节微课的学习，培养学生以下几个方面的能力： （1）理解哈夫曼树的应用范围和场景，并能灵活运用； （2）掌握哈夫曼树及编码的概念、求解算法基本思想，针对实例，能构造哈夫曼树，求解哈夫 嘉应学院计算机学院 实验报告 课程名称：数据结构课程设计 开课学期：2017-2018学年第2学期 班级： 指导老师： 实验题目：哈夫曼树 学号： 姓名： 上机时间： 一、实验目的 本实验的目的是通过对简单的哈夫曼编/译码系统的设计与实现来熟练掌握树形结构在实际问题中的应用。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高通信利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此试验即设计这样的一个简单的编/译码系统。系统应该具备如下的几个功能。 1、求出各个叶子节点的权重值 输入一个字符串，统计其中各个字母的个数和总的字母个数。 2、构造哈夫曼树 统计出的字母种类为叶子结点个数，每个字母个数为相应的权值，建立哈夫曼树。 3、打印哈弗曼树的功能模块 按照一定形式打印出哈夫曼树。 4、编码 利用已经建立好的哈夫曼树进行编码。 5、译码 根据编码规则对输入的代码进行翻译并将译码。 三、实验步骤 1、实验问题分析 （1）设计一个结构体数组保存字母的类型和个数。 { ; 字母的种类 ; 字母的个数 }; （2）在构造哈夫曼树时，设计一个结构体数组保存哈夫曼树中各结点 的信息，根据二叉树的性质可知，具有n个结点的哈夫曼树共有21个结点，所以数组大小设置为21,描述结点的数据类型为： { ; 权值 ; 双亲 ; 左孩子 ; 右孩子 }; []; 定义此类型的数组 （3）求哈夫曼编码，实质上是在已经建立的哈夫曼树中，从叶子结点开始，沿着结点的双亲链表域退回到根节点，每退回一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼值，由于一个字符的哈夫曼编码是从根结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码，所以设计如下的数据类型： 10; { []; 每个结点的哈夫曼编码 ; 开始位置 }; （4）设置全局变量。 s; 为输入的字符串 0; 记录输入的字符串中字母的种类，即叶子结点个数 0; 记录字符串中字母的总个数 []叶子结点类型 2、功能（函数）设计 （1）统计字母种类和个数模块 此模块的功能为从键盘接受一个字符串，统计字符串中字母种类即结 点个数，每种字母出现次数即各叶子结点的权值。全局变量s保存输 入的字符串，将种类和个数保存到[]中。 函数原型：（） 如输入的字符串是“”则显示如下。 ******************* 实践教学 ******************* 兰州理工大学 计算机与通信学院 2007年春季学期 算法与数据结构课程设计 题目：赫夫曼编译码器设计 专业班级：软件工程05－1班 姓名：张龙 学号：05350507 指导教师：王燕 成绩： 目录 摘要 (1) 前言 (2) 正文 (3) 1.采用类C语言定义相关的数据类型 (3) 2.各模块的伪码算法 (7) 3.函数的调用关系图 (13) 4.调试分析 (13) 5.测试结果 (14) 6.源程序（带注释） (14) 总结 (20) 参考文献 (20) 附件Ⅰ部分源程序代码 (21) 摘要 哈夫曼编译码器主要用于通信领域，能够实现数据的快速，有效的传输。它利用哈夫曼树对数据进行编码，形成前缀编码，实现数据的有效压缩存放。然后又通过某种遍历实现译码，从而达到快速远距离通信的目的。 关键词：哈夫曼树；前缀编码；译码 前言 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。通过该题目的设计过程，可以加深理解树及二叉树的逻辑结构、存储结构，掌握树及二叉树上基本运算的实现。进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。 正文 1.采用类c语言定义相关的数据类型 （1）结构体定义 typedef struct { int weight; char ch; int parent,lchild,rchild; }HTNode,*HuffmanTree; //动态分配数组存贮哈夫曼树。 typedef struct { char ch; char *chs; }HuffmanCode; typedef struct { char ch; int weight; }sw; typedef struct { HuffmanTree HT; HuffmanCode *HC; }huf;//哈夫曼树结构体。 从HT[i-1]选择parent为零且weight最小的两个节点，分别编号为n1,n2. （2）调用函数 1）在给定权值中选择权值最小的两个节点。 void select(HTNode * HT,int n,int *n1,int *n2) { int i=1; int n3; while(HT[i].parent!=0) i++; #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) { 专业基础实践报告 题目哈夫曼树及应用 起讫日期2008年6月30日至2008年7月11日所在院系软件学院 学生姓名专业计算机 班级学号 指导教师职称 所在单位软件学院 2008年7 月11 日 目录 一、任务及要求 (1) 二、总体设计 (3) 三、运行效果 (16) 四、总结 (22) 五、附录 (23) 参考文献 1.唐策善?《数据结构---用C语言描述》?高等教育出版社?1995 ?p50~p120 2.谭浩强?《C程序设计》?清华大学出版社? 2005 ? p330！p348 一、任务及要求 在本专业基础实践中，综合C语言程序设计、离散数学、数据结构等学过的 专业基础课程中的基本概念、基础知识和基本理论，进行软件设计的思想、方法 和过程的训练，提高综合素质和动手能力，达到加强专业基础知识理解程度和熟 练程度的目的。具体任务及要求如下： 1、任务 （1）给定一个包含10个以上字符的字符串，长度不少于100个字符，统计各个字符的概率，存放在数组中。 （2）根据上面统计的结果建立哈夫曼树。 （3）实现哈夫曼编码。 （4）实现哈夫曼译码。 （5）自己选做1～2个附加的任务。 2、要求 （1）算法中处理的数据要存放在文件中，实现文件的读写操作。 （2）设计程序中的各个C函数、画出模块图。 （3）程序的代码要规范、有详细的注释。 （4）按照指导教师给出的模板进行专业基础实践报告书写。 二、工作量 在2周（10个工作日）时间里，完成15-20个C函数，150-200行代码。并提交专业实践报告一份，字数不少于5000字（包括英文字符）。 三、计划安排 第1个工作日－第2个工作日：查找相关资料、书籍；确定逻辑结构并进行运算的 定义；选择存储结构并进行算法设计。 第3个工作日－第7个工作日：完成程序的编码，并且自己调试、测试。穿插进行 实践报告的撰写。 第8个工作日－第9个工作日：整理并完成专业基础实践报告，提交指导教师。第10个工作日：由教师检查软件测试效果、审阅实践报告，评定成绩。 指导教师签字： 2008年6月26日 数 据 结 构 实 验 报 告 （四） 姓名: 李 大 宝 学院：计算机学院 班级：软件 114班 实验四哈夫曼树及其的应用 一、实验目的 1．在二叉树基本操作的基础上，掌握对二叉树的一些其它操作的具体实现方法。 2.掌握构造哈夫曼树以及哈夫曼编码的方法。 3、熟练掌握哈夫曼树（最优二叉树）特征及其应用 二、实验内容 题目一、哈夫曼树和哈夫曼编码： 从终端输入若干个字符，统计（或指定）字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各字符进行哈夫曼编码。最后打印哈夫曼树和对应的哈夫曼编码。 设计要求： 哈夫曼殊和哈夫曼编码的存储表示参考教材事例。 /*定义常量和类型*/ #define MAX 1000000.00 //宏定义定义常量MAX typedef char* CHAR; //定义char* 类型的变量CHAR typedef double* DOUBLE; //定义double*类型的变量DOUBLE /* 定义赫夫曼树结点类型 */ typedef struct {double weight;//权值（字符频度）类型为double int parent,lchild,rchild;//左孩子右孩子双亲类型为int char s;//存放字符信息 }HTNode,*HuffmanTree; typedef char **HuffmanCode; //存放赫夫曼编码 在程序中构造六个子程序为 a)int freqchar(char *text,DOUBLE &b,CHAR &c) /*统计字符出现的频率*/ b)void createhtree(HuffmanTree &HT,double *w,char *str,int n) /*根据字符出现的频率建立哈夫曼树*/ c)void coding(HuffmanTree HT,HuffmanCode &HC,int n) /*对哈夫曼树进行编码*/ d)void printHTree(HuffmanTree &HT,int n,int deep) /*中序打印树*/ e)void Select(HuffmanTree &t,intn,int&s1,int &s2) /*选择出两个权值最小的*/ f)int Min(HuffmanTree t,int n) /******************************************/ /********* 哈夫曼树的编写与输出***********/ /******************************************/ /*用静态三叉链表实现哈夫曼树类型定义如下：*/ #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; } } 数据结构实验报告 专业: 班级: 姓名: 学号: 指导老师: 评分: 实验四哈夫曼树的建立及应用 一、实验目的 1、掌握哈夫曼树的基本概念及所有的存储结构。 2、掌握哈夫曼树的建立算法。 3、掌握哈夫曼树的应用（哈夫曼编码和译码）。 二、实习内容 1、给定权值5，29，7，8，14，23，3，11，建立哈夫 曼树，输出哈夫曼编码。 2、对上述给定的哈夫曼树及得到的哈夫曼编码，试输入一 串二 进制编码，输出它的哈夫曼译码。 三、算法描述 将建立哈夫曼树、实现哈夫曼编码、哈夫曼译码都定义成子函数的形式，然后在主函数中调用它们。 建立哈夫曼树时，将哈夫曼树的结构定义为一个结构型的一维数组，每个元素含有四项：权值，双亲，左孩子，右孩子。给定的权值可以从键盘输入，要输出所建立的哈夫曼树，只要输出表示哈夫曼树的一维数组中的全部元素即可。 要实现哈夫曼编码，只要在所建立的哈夫曼树上进行二进制编码：往左走，编码为0，往右走，编码为1，然后将从根结点到树叶中的所有0、1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码可以用一个结构型的一维数组保存，每个元素包含：编码、编码的开始位置、编码所对应的字符三项。 四、程序清单: #include int huff[100];//存储100个权值的数组 void Select(element huffTree[],int m) { int min,min2,i; min=min2=1000; for(i=0;i 课程设计 题目：哈夫曼编码器 院系： 专业班级： 学号： 学生姓名： 指导教师： 2014年1月2日 课程设计需求分析报告 一、分析问题和确定解决方案 1.分析问题 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统,为这样的信息收发站写一个哈夫曼的编/译码系统。 2.确定解决方案 设计建立带权的哈夫曼树，确定哈夫曼树的类与成员函数，以及各函数之间的调用关系，采用动态数组的存储结构存储所需要的数据，通过不同的函数来实现编码，译码以及打印二进制编码、哈夫曼树，把不同的数据存入不同的txt文件中，通过主函数调用来实现功能检测。 3.输入的形式和输入值的范围 手动或者从文本中读入数据的形式初始化哈夫曼树，从键盘中或者文件中读入数据，以字母A-Z代表结点，以自然数代表权值，字符串提示使用者所要执行的操作。 4.输出的形式 在显示器界面上或者以文本的形式来实现程序调试的输出。 5.程序所能达到的功能 (1)初始化。手动输入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件WritehfmTree中,输出哈夫曼树及各字符对应的编码存于WritehfmCode;从文本中读入字符，建立哈夫曼树存于ReadhfmTree, 输出哈夫曼树及各字符对应的编码存于ReadhfmCode. (2)编码。手动输入一串大写英文字符，该字符存于WriteToBeTron中，对字符进行编码并将它存于WriteCodeFile中；从文件中读取字符编码并存于ReadCodeFile中。 (3)印代码文件。将文件ReadCodeFile以紧凑格式显示在终端上，每行50个代码。同时将 摘要：哈夫曼树是带权路径长度（WPL）最小的二叉树，通过对哈夫曼算法的研究，提出一种求取哈夫曼树带权路径长度的计算方法和应用。 关键词：哈夫曼算法、二叉树、WPL、编码 1 引言： 哈夫曼树是一种特殊的二叉树，又称最优二叉树：假设有一组（无序）实数｛w1,w2,w3,w4,…,wm｝，现要构造一棵以wi（i=1，2，3，4…，m）为权的m个外部结点的扩充二叉树，使得带权的外部路径长度WPL最小。满足这一要求的扩充二叉树就称为哈夫曼树或最优二叉树。若l表示从根到第i个外部结点的路径长度，m为外部结点的个数，wi 为第i个外部结点的权值，则有WPL=∑wili（0 哈夫曼树的建立数据结构课程设计文档 班级： 小组组长: 成员： 指导老师： 第一章前言 数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。 通过此次课程设计主要达到以下目的： 一、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 二、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 三、提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 四、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。哈夫曼树及其应用(完美版)
哈夫曼树及其应用教案
哈夫曼树 实验报告
哈夫曼树
哈夫曼树
哈夫曼树的建立与操作
构建哈夫曼树及输出哈夫曼代码及算法思想
哈夫曼树及应用
数据结构课程设计-哈夫曼树
哈夫曼树
哈夫曼树建立、哈夫曼编码算法的实现
哈夫曼树及其应用
实验 四 哈夫曼树及其的应用
哈夫曼树的编写与输出
哈夫曼树的建立及应用
哈夫曼树课程设计报告(DOC)
哈夫曼算法的实现及应用
数据结构课程设计(赫夫曼树的建立)