数据结构课程设计哈夫曼编码 

(1) 上交源程序：学生按照实验题目的具体要求所开发的所有源程序（应该放到一个文件夹中）； (2) 上交程序的说明文件：（保存在.txt中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明；

(3) 设计报告：（保存在word 文档中，文件名要求： 按照“姓名_学号_设计题目”起名，如文件名为“ 张三_XXX_赫夫曼编码 ”.doc。打印稿用A4纸）。 其中包括: ? 题目； ? 实验目的；

? 需求分析：在该部分中叙述实现的功能要求； ? 概要设计：

在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）； ? 详细设计

各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）。源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量、重点功能部分要加上清晰的程序注释； ? 调试分析

测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想；

? 总结：

总结可以包括 : 设计过程的收获、遇到问题及解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在设计过程中对《数据结构》课程的认识等内容。

（4）考核成绩评定标准：

本课程设计的评价由三部分组成，包括程序演示（50%），课程设计报告（30%），回答教师提问（20%）。

1．程序演示： ? 优 ? 良 ? 中

功能完善，全部测试正确，并且能够对局部进行完善。 功能完善，但测试欠缺。

功能基本完善，但程序尚有部分错误。 功能不完善，且程序错误较多，无法运行。

? 及格 完成内存中赫夫曼编码/译码，但不涉及文件操作。 ? 不及格

2．课程设计报告： 1．优 2．良

包括设计内容，设计思想，已经完成的任务及达到的目标，设计思路清晰、书写包括设计内容，设计思想，已经完成的任务及达到的目标，设计思路基本清晰、

条理清楚，源程序结构合理、清晰，注释说明完整，有对本次课程设计的心得体会。 书写条理基本清楚，源程序结构合理、清晰，注释说明基本完整，有对本次课程设计的心得

6

体会。 3．中

课程设计报告内容基本完整，思路较清晰，书写基本清楚，源程序结构尚可，有

注释说明但不完整。

4．及格 课程设计报告内容基本完整，思路较差，书写尚清楚。 5．不及格 课程设计报告内容不完整，书写没有条理。

3．回答教师提问： 1. 优 2. 良 3. 中

能回答教师提出的所有问题，并完全正确，思路清晰 基本能回答教师提出的所有问题，有些小错误

基本能回答教师提出的问题，少数问题回答错误或不清楚 基本不能回答教师提出的问题

4. 及格 能回答教师提出的问题，但较多问题回答错误或不能回答 5. 不及格

7

四、概要设计

1) 问题分析哈夫曼树的定义

1.哈夫曼树节点的数据类型定义为：

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（）函数。

2、void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函数，选出HT树到a为止，权值最小且parent为0的2个节点

2、 int main()

主函数： 利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.txt中读入）

对文件中的正文进行编码，然后将结果存入文件codefile.txt中。如果正文中没有要编码的字符，则键盘读入并存储到ToBeTran文件中。读入ToBeTran中将要编码的内容，将编码好的哈夫曼编码存储到CodeFile中。 3、Encoding

编码功能：对输入字符进行编码 4、Decoding

译码功能： 利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码，结果存入文件textfile.dat 中。

Print() 打印功能函数：输出哈夫曼树，字符，权值，以及它对应的编码。

5.主函数的简要说明，主函数主要设计的是一个分支语句，让用户挑选所实现的功能。 使用链树存储，然后分别调用统计频数函数，排序函数，建立哈夫曼函数，编码函数，译码函数来实现功能。

2)系统结构图（功能模块图）

8

五．程序说明

1）.哈夫曼编码/译码器源代码

#include #include #include #include #include

typedef struct{ //赫夫曼树的结构体 char ch; int weight; //权值 int parent,lchild,rchild; }htnode,*hfmtree;

typedef char **hfmcode;

void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函数，选出HT树到a为止，权值最小且parent为0的2个节

点

{

int i,j,x,y;

for(j=1;j<=a;++j){ if(HT[j].parent==0){ x=j; break; } }

for(i=j+1;i<=a;++i){ if(HT[i].weight

for(j=1;j<=a;++j) { if(HT[j].parent==0&&x!=j) { y=j; break; } }

for(i=j+1;i<=a;++i) { if(HT[i].weight

9

if(x>y){ *p1=y; *p2=x; } else { *p1=x; *p2=y; } }

void hfmcoding(hfmtree &HT,hfmcode &HC,int n) //构建赫夫曼树HT，并求出n个字符的赫夫曼编码HC { int i,start,c,f,m,w; int p1,p2; char *cd,z; if(n<=1){ return; } m=2*n-1; HT=(hfmtree)malloc((m+1)*sizeof(htnode)); for(i=1;i<=n;++i) //初始化n个叶子结点 { printf(\请输入第%d字符信息和权值：\ scanf(\ while(getchar()!='\\n') { continue; } HT[i].ch=z; HT[i].weight=w; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(;i<=m;++i) //初始化其余的结点 { HT[i].ch='0'; HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(i=n+1;i<=m;++i) //建立赫夫曼树 {

10