哈夫曼课程设计报告.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