张紫薇分析.doc

青岛工学院 《数据结构课程设计》报告书 题 目 哈夫曼编译码器的实现 学生姓名 郑文月 周凯华 张紫薇 指导教师 刘伟1 前言 1 2 课程设计编程涉及到的数据类型及说明。 2 3 课程设计的具体内容。 3 3.1哈弗曼树的建立 3．1．1选择parent为0且权值最小的两个根节点算法 3．1.2构造哈夫曼树 3.2哈弗曼编码 3.2.1哈夫曼编码算法 3.3功能框架图 4 重要功能函数的代码及其中文注解。 4 5程序的运行结果显示。.....................................5 6实践心得体会 8 1 前言 “数据结构”是计算机专业一门重要的的专业技术基础课程，是计算机专业的一门核心的关键课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容丰富。本课程的学习委后续课程的学习以及软件设计水平的提高打下良好基础。 [课程设计题目简介] 利用哈夫曼编码进行信息通信可大大提高信道利用率，缩短信息传输时间，降低传输成本。要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。对于双工信道（既可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。 [设计目的]?? ??设计一个哈弗曼编码、一码系统。对一个ASCII编码的文本文件中的字符进行哈弗曼编码，生成编码文件；反过来，可将编码文件译码还原为一个文本文件。 从文件中读入任意一片英文短文（文件为ASCII编码，扩展名为txt） typedef struct{ //赫夫曼树的结构体 char ch; int weight; //权值 int parent,lchild,rchild; }htnode,*hfmtree; 2．所实现的功能函数如下： （1）void hfmcoding(hfmtree HT,hfmcode HC,int n) 初始化哈夫曼树，处理InputHuffman(Huffman Hfm)函数得到的数据，按照哈夫曼规则建立2叉树。此函数块调用了Select（）void Select(hfmtree HT,int a,int *p1,int *p2) Select函数，选出HT树到a为止，权值最小且parent为0的2个节点 （3） int main() 主函数： 利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.txt中读入）对文件中的正文进行编码，然后将结果存入文件codefile.txt中。如果正文中没有要编码的字符，则键盘读入并存储到ToBeTran文件中。读入ToBeTran中将要编码的内容，将编码好的哈夫曼编码存储到CodeFile中。 （4）Encoding 编码功能：对输入字符进行编码 （5）Decoding 译码功能： 利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码，结果存入文件textfile.dat 中。 (6) Print() 打印功能函数：输出哈夫曼树，字符，权值，以及它对应的编码。 3 课程设计的具体内容。 3.1哈弗曼树的建立 3.1.1选择parent为0且权值最小的两个根节点算法 void selectmin(hfmt t,int i,int *p1,int *p2)//选中两个权值最小的函数 { long min1=999999; long min2=999999; int j; for(j=0;j=i;j++)//选择最小权值字符的下标返回 if(t[j].parent==-1) if(min1t[j].weight) { min1=t[j].weight; *p1=j; } for(j=0;j=i;j++)//选择次小权值字符的下标还回 if(t[j].parent==-1) if(min2t[j].weight j!=(*p1))//注意 j!=(*p1)) { min2=t[j].weight; *p2=j;