长春大学课程设计(哈夫曼)

1、长 春 大 学课 程 设 计 说 明 书题目名称 哈夫曼编码/ 译码器 院（系） 计算机科学与技术 专业（班级） 网络五班 学生姓名 董迎顺 指导教师 朱德新 起止日期 2015.9.7-2015.9.11 目 录1.设计目的与任务12.算法设计32.1设计思想32.2设计表示33.用户手册44.测试数据及测试结果55.课程设计总结9程序清单91.设计目的与任务1.1设计目的：（1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计力；（2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；（3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；（4）

2、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所具备的科学的工作方法和作风。1.2 设计任务：设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。2.算法设计2.1设计思想（1）数据结构设计对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。 本程序定义了相应的结构体变量，包括weight权值，parent双亲结点，lchild左孩子，rchild右孩子。通过结构体构建哈夫曼树，实现哈夫曼的编码和译码功能。结构体变量如下：typedef struct/结构体 char data; i

3、nt weight; /权值 int parent;/双亲结点 int lchild;/左孩子 int rchild;右孩子 HTNode; HTNode ht80; 功能：该结构体储存相关数据包括输入的权值weight，构建哈夫曼树所需要的双亲parent，左孩子lchild，右孩子rchild。同时建立结构体数组HTNode ht80;typedef struct char cd30; /字符串 int start;HCode; HCode hcd80;功能：该结构体储存输入的字符。（2）算法设计 本程序在运行过程中用到的算法是哈弗曼算法，它是由n个带权叶子结点构成的所有二叉树中带权路径长

4、度最短的二叉树，根据给定的n个权值构成n棵二叉树的集合，其中每棵二叉树中只有一个带权weight的根结点，左右子树均空，选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和，即为哈夫曼树算法。本程序先定义结构体，通过创建哈弗曼树，对输入的字符进行编码和译码。2.2设计表示（1）函数调用关系图及其说明如下：哈夫曼编/译码器 主函数main（）初始化哈弗曼树CreateHT（）输入CodeInput（）显示哈夫曼树Shuchu（）哈夫曼编码CreateHCode（）保存save（） 结束exit（）（2）函数接口说明：函数中的参数均是

5、使用的全局变量的传递，因而在函数间进行传递的过程中比较简单，下面就将主要函数及他们之间的参数的关系列出如下：void CodeInput(int n,HTNode ht)/输入字符及权值 进行哈夫曼编码void CreateHCode( HTNode ht , HCode hcd , int n )/进行哈夫曼编码void CodeOutput( int n , HCode hcd )函数输出哈夫曼编码。void shuchu(HCode hcd , int n)/输出哈夫曼树void save( int n)/ 将其存入data.text文件中3.用户手册 点击运行程序，在弹出的窗口中，会提

6、示要输入的信息：（1）界面信息：显示5个选项，分别为1：输入哈夫曼树2：哈夫曼编码3：显示哈夫曼树4：哈夫曼权值存储5：退出。（2）操作：用户输入界面的1-5选项，若输入其他选项则提示（"输入有误 ! 请输入 <1 - 5>选项），程序分别调用相关函数。（3）用户需要输入哈夫曼树，程序会生成哈夫曼编码和哈夫曼树并显示在屏幕上，可以对哈夫曼权值保存。当退出时，选择5 直接退出。4.测试数据及测试结果测试数据如下：a s d f g h7 8 9 4 5 2程序运行结果如下:图1：菜单显示界面，选择操作类型。图2：选择1，输入哈夫曼树，先输入所有字符然后输入权值。图3：选择2

7、，输出哈夫曼编码。图4：选择3，显示哈夫曼树。图5：选择4，保存哈夫曼权值到"d:data.txt"。图6：选择5，退出程序。5.课程设计总结在这次课程设计过程中，遇到了很多困难，之前对哈夫曼算法不是很了解，在编写源代码时有很多知识都忘了，多次翻阅课本学习，网上查找相关资料，使得编写的效率很慢。调试程序的过程中，出现了很多错误，逐个分析每一个错误，我学到了很多东西，比如一些课上没有懂的知识，我通过实践搞懂了，而且通过此次的课程设计，让我更深入的理解数据结构，并且还运用了以前所学的有关C语言的知识，并且应用到我的程序中去，对哈夫曼树也有了更深的了解，并且真正会用这种算法了，通

8、过不断的改正错误，我的程序有了更高的质量。在编写的时候也犯了很多不该犯的错误，不过我及时纠正了，遗憾的是，我的程序功能不是很全，某些部分没有按照要求去做，说明我的编程能力有待提高。程序清单#include <stdio.h>#include <string.h>#include <stdlib.h>typedef struct/结构体 char data; int weight; /权值 int parent; /双亲结点 int lchild; /左孩子 int rchild; /右孩子 HTNode; HTNode ht80; typedef struc

9、t char cd30; int start; HCode; HCode hcd80; void CreateHT( HTNode ht , int n )/创建哈弗曼树 int i , k , lnode, rnode ;int min1 , min2 ; for ( i = 0 ; i < 2*n-1 ; i+ ) hti.parent = hti.lchild = hti.rchild = 0; for ( i = n ; i < 2*n-1 ; i+ ) min1 = min2 = 9999; lnode = rnode = 0; for ( k=0 ; k <= i

10、-1; k+) if ( htk.parent = 0) if (htk.weight < min1) min2 = min1;min1 = htk.weight;rnode = lnode; lnode = k; else if ( htk.weight < min2) min2 = htk.weight;rnode = k; htlnode.parent = i; htrnode.parent = i; hti.weight = htlnode.weight + htrnode.weight; hti.lchild = lnode;hti.rchild = rnode; voi

11、d CreateHCode( HTNode ht , HCode hcd , int n )/进行哈夫曼编码 int i , f , c; HCode hc;for( i = 0 ; i < n; i+) hc.start = n; c = i; f = hti.parent; while (f != 0) if( htf.lchild = c) hc.cdhc.start- = '0' else hc.cdhc.start- = '1' c=f ; f=htf.parent; hc.start+; hcdi = hc; void CodeInput(in

12、t n,HTNode ht)/输入字符及权值 进行哈夫曼编码 int i; char ch30; scanf( "%s" , ch ); for ( i=0 ; i<n ; i+ )scanf( "%ld" , &hti.weight );printf("*- n");void CodeOutput( int n , HCode hcd )/输出哈夫曼编码 int i , j ; printf (" 所有字符的哈弗曼编码为:"); for ( i = 0 ; i < n ; i+ ) for(

13、j=hcdi.start ; j<=n ; j+ ) printf( "%lc" , hcdi.cdj ); printf("n");for ( i=0 ; i<n ; i+ )printf( " 序号%d : " , i );for( j = hcdi.start ; j <= n ; j+ ) printf( "%lc" , hcdi.cdj ); printf( "n" ); void shuchu(HCode hcd , int n)/输出哈夫曼树int i; prin

14、tf("nHTi:t权值t双亲t左孩子t右孩子n"); for(i = 1;i<2*n;i+) /共打印（2*len-1）组 if(i <= n) printf("%2d:t %2d;t%2d,t %2d,t %2d.n",i,hti.weight,hti.parent,hti.lchild,hti.rchild); /打印代码相应的权值，双亲左右孩子 void save( int n)/ 将其存入data.text文件中int i ;FILE *fp;if( ( fp = fopen ( "d:data.txt" , &

15、quot;w" ) ) = NULL ) printf( " can't open this file ! " ) ;exit(0) ;elsefor ( i = 1 ; i <= n ; i+ )fprintf( fp , " %ld ", hti.weight );printf(" 保存文件成功 !");fclose (fp) ;void main()/主函数int num ,n,i;char flag ='y'while( flag = 'y' | flag = '

16、Y' ) system( "cls" );printf(" *n"); printf(" * 欢迎使用 哈夫曼编码系统 *n "); printf(" *n"); printf(" * 1. 生成哈夫曼树 *n");printf(" * 2. 哈夫曼编码 *n"); printf(" * 3. 显示哈夫曼树 *n");printf(" * 4.哈夫曼权值存储 *n");printf(" * 5. 退出 *n"

17、);printf(" *n");printf(" 请选择操作类型 ( 1 - 5 ) : " ); scanf( " %d" , &num );printf("*n");switch(num)case 1 : printf(" 请输入要输入的字符数量n为: ");if(scanf(" %ld", &n )&&(n!=0)printf("n 请输入 %d 个字符和 %d 个对应权值 <先将所有字符输入 再输对应权值> n:

18、" , n , n );CodeInput( n , ht );CreateHT( ht , n ); printf(" 对应的权值为 ： n"); for( i = 0 ; i < n ; i+ ) printf( " %d : %ld " , i , hti.weight );if(i+1) % 4 = 0)printf("n");printf("n*- n");break;case 2 : CreateHCode( ht , hcd , n ); CodeOutput( n , hcd ); printf("*");break;case 3 : printf("n");shuc