哈夫曼课程设计报告.doc

数据结构课程设计报告 第 PAGE 13页 一 需求分析 随着人们生活水平的提高，科学的进步和通信技术的发展，人们在进行通信的同时要求做到信息交流的必威体育官网网址性和快速，准确性，尤其实在军事和高端科技方面。 为了解决上面所提出的问题，实现该目的，设计出了一种快速可靠的编码方式，即哈夫曼编码。 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。 对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。 象这样一个完整的系统应具有以下功能：（1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件哈夫曼树中。（2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件哈夫曼树文件中读入），对所输入的编码字符串中的正文进行编码，然后将结果存入编码文件（CodeFile）中。（3）D：译码（Decoding）。利用已建好的哈夫曼树将编码文件（CodeFile）中的代码进行译码，结果存入文件中进行保存。（4）P：印代码文件（Print）。将文件编码文件（CodeFile）以紧凑格式显示在终端上，计算好每行多少个代码，尽量使界面友好，清晰。同时将此字符形式的编码文件写入文件CodePrin中。（5）T：打印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件中保存好。 二 概要设计 所使用的数据结构： 本程序哈夫曼树的构造采用二叉链表作为存储结构 抽象数据类型定义： typedef struct //huffman树存储结构 { unsigned int wei; int lch,rch,parent; }hufftree; 三 详细设计 一．主函数 #includehead.h void main() { int m,a=0,n=0; Huffmantree HT; char choice; while(choice!=q) { printf(\n******************************\n); printf( 欢迎使用赫夫曼编码解码系统\n); printf(******************************\n); printf((1)要初始化赫夫曼链表请输入i\n); printf((2)要编码请输入e\n); printf((3)要译码请输入d\n); printf((4)要打印编码请输入p\n); printf((5)要打印赫夫曼树请输入t\n); printf((6)要退出系统请输入q\n); printf(\n如果没有初始化链表，请先初始化赫夫曼链表,输入i:); scanf(%s,choice); switch(choice) { case i: Initialition(HT,m);n=m; break; //初始化，从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存入文件hfmtree中 case e: Encoding(); break; case d: Decoding(HT,m); break; case p: Print(); break; case t: Treeprinting(HT,m,n); break; case q: a=1; break; } } } 二．头文件 #includestdio.h #includemalloc.h #includestring.h typedef struct{ char a[20]; char c;//待编码的字符 int weight; int parent,lchild,rchild; }HTNode,*Huffmantree; typedef struct Node{ char c[20];//用以存放编码 char a;//用以存放待编码的字符 int weight;//用以存放权重 struct Node *next; }Node; void select(Huffmantree HT,int n,int *s1,int *s2); voi