计算机科学与工程学院
集中性实践教学计划书
（ 20## — 20## 学年第 二 学期）
课程名称： 数据结构与算法课程设计
专 业： 计算机科学与技术
软件工程、网络工程
班 级：计算机科学与技术091-6
软件工程091-4
网络工程091-4
课程负责人： 李锡祚、王玲芬、李威
指导教师分配情况：
教学起止周：第 1 至 3 教学周
第二篇：《数据结构与算法分析》课程设计报告
《数据结构与算法分析》课程设计报告
课题名称： 哈夫曼编码
课题设计人（学号）： 胡宗鹏 0943041310
指导教师： 朱宏
评阅成绩：
评阅意见：
提交报告时间：2010 年 12 月 14 日
课程名称：数据结构与算法分析 学生姓名：胡宗鹏 学生学号：0943041310
哈夫曼编码
计算机科学与技术 专业
学生 胡宗鹏 指导老师 朱宏
[摘要] 通信中，可以采用0,1的不同排列来表示不同的字符，称为二进制编码。而哈夫曼树在数据编码中的应用，是数据的最小冗余编码问题，它是数据压缩学的基础。若每个字符出现的频率相同，则可以采用等长的二进制编码，若频率不同，则可以采用不等长的二进编码，频率较大的采用位数较少的编码，频率较小的字符采用位数较多的编码，这样可以使字符的整体编码长度最小，这就是最小冗余编码的问题。 而哈夫曼编码就是一种不等长的二进制编码，且哈夫曼树是一种最优二叉树，它的编码也是一种最优编码，在哈夫曼树中，规定往左编码为0，往右编码为1，则得到叶子结点编码为从根结点到叶子结点中所有路径中0和1的顺序排列。
关键词：哈夫曼树
-1-
课程名称：数据结构与算法分析 学生姓名：胡宗鹏 学生学号：0943041310
课程设计目的
1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理
论知识，编写程序求解指定问题。
2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法
和技能；
3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理
论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作
作风。
课程设计任务与要求：
哈夫曼树应用
功能：
(1)从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；
(2)利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。
(3)利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。
分步实施：
1） 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；
2） 完成最低要求：完成功能1；
3） 进一步要求：完成功能2和3。有兴趣的同学可以自己扩充系统功能。
要求：1）界面友好，函数功能要划分好
2）总体设计应画一流程图
3）程序要加必要的注释
4） 要提供程序测试方案
5） 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序
是没有价值的。
哈弗曼函数
1.主菜单窗口
-2-
课程名称：数据结构与算法分析 学生姓名：胡宗鹏 学生学号：0943041310
2.建立哈夫曼树
3．利用哈夫曼树进行编码
-3-
课程名称：数据结构与算法分析 学生姓名：胡宗鹏 学生学号：0943041310
4.利用哈夫曼树进行译码
课程设计心得：
经过几个星期的奋战，终于完成了课程设计，感觉又进一步了解了数据库这门课程，各个知识点都加强了。也许个中滋味只有我才能体会，说实在的，刚上这门课程的时候，兴趣并不是很大，而且还出现过作业迟交的情况，而现在，我似乎突然找到了方向，认真的学习这门课。
回顾这次课程设计，使我感慨颇多。的确，从理论到实践，在整整两星期的日子里，学到很多很多的的东西，同时不仅可以巩固学过的知识，而且学到
-4-
课程名称：数据结构与算法分析 学生姓名：胡宗鹏 学生学号：0943041310
了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，从而提高自己的实际动手编程能力和独立思考的能力。运动会计分系统，比较复杂，经过很长时间的书写，总算尝到了胜利的“滋味”
在细节的认识上，我们在开发程序的时候，在之前就要知道自己想要的效果，然后把需要实现的功能在纸上列出来，后比如要用几个函数来实现几个功能，整体需要几个模块来搭建，这些工作都是要在未动工之前就得做好的准备工作，编程要的是有整体的思想加细心。这次的课程设计收获颇多，最大的认识到了要想高效设计出想要的东西不仅要熟悉的掌握所学知识，还要学会充分利用现有资源。
在这之前，总以为自己编程方面还很差，现在才觉得，只要努力了，就会有收获，就会得到回报
参考文献
百度文库 哈夫曼函数
详细设计（源程序）
哈弗曼函数
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
char filename[20]; //文件名
FILE *fp; //指向文件的指针
//定义结构体
typedef struct
{
int weight;
char ch;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
//动态分配数组存储哈夫曼树
typedef struct
{
-5-
课程名称：数据结构与算法分析 学生姓名：胡宗鹏 学生学号：0943041310
char ch;
char *chs;
}HuffmanCode;//动态分配数组存储哈夫曼编码表
typedef struct
{
char ch;
int weight;
}sw;//定义节点
typedef struct
{
HuffmanTree HT;
HuffmanCode *HC;
}huf; //哈夫曼树结构体
//在HT[1..i-1]选择parent为0且weight最小的两个节点，其序号分别为n1,n2。
void select(HTNode * HT,int n,int *n1,int *n2)
{
int i=1; int n3;
while(HT[i].parent!=0)
i++;
*n1=i;
i++;
while(HT[i].parent!=0) i++;
*n2=i;
if(HT[*n1].weight<HT[*n2].weight)
{ n3=*n1;*n1=*n2;*n2=n3;}
for(i++;i<=n;i++)
{
if(HT[i].parent==0)
{ if(HT[i].weight<HT[*n1].weight)
*n1=i;
else if(HT[i].weight<HT[*n2].weight)
*n2=i;
}
}
}
huf * HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,sw *w,int n,huf *HUF)
//w存放n个字符的权值（均>0）,构造哈夫曼树HT,并求出n个字符的哈 -6-
课程名称：数据结构与算法分析 学生姓名：胡宗鹏 学生学号：0943041310
夫曼编码HC。
{
int m,i,s1,s2,start,c,f;
HuffmanTree p;
char *cd;
if(n<=1) return 0;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用
for(p=HT+1,i=1;i<=n;i++,p++,w++)
{p->weight=w->weight;p->ch=w->ch;p->parent=0;p->lchild=0;p->rchild=0;} for(;i<=m;i++,p++)
{p->weight=0;p->ch='^';p->parent=0;p->lchild=0;p->rchild=0;}
for(i=n+1;i<=m;i++) //建哈夫曼树
{
select(HT,i-1,&s1,&s2);
HT[s1].parent=i;HT[s2].parent=i;
HT[i].lchild=s1;HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
HC=(HuffmanCode *)malloc((n+1)*sizeof(char));//分配n个字符编码的头指针向量
cd=(char *)malloc(n*sizeof(char));//分配求编码的工作空间
cd[n-1]='\0';
for(i=1;i<=n;i++)
{ start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码
if(HT[f].lchild==c)cd[--start]='0';
else cd[--start]='1';
HC[i].ch=HT[i].ch;
HC[i].chs=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间
strcpy(HC[i].chs,&cd[start]);
printf("%c %-10s\n",HC[i].ch,HC[i].chs);
}
HUF->HT=HT;
HUF->HC=HC;
return HUF;
}
void input(int *n,sw *w)
-7-
课程名称：数据结构与算法分析 学生姓名：胡宗鹏 学生学号：0943041310
{
int i;
//输入要编码的字符数量
printf("输入用于编码的字符数量:");
scanf("%d",n);
for(i=1;i<=*n;i++,w++)
{printf("输入字符和权值:",i);
fflush(stdin);
//输入字符和权值
scanf("%c%d",&w->ch,&w->weight);
}
}
void writeFile(char filename[20]) //文件存储函数 用于保存数据到文件
{
if((fp=fopen(filename,"w+"))==NULL)
{
printf("\n 保存失败\n");
exit(0);
}
else printf("\n 保存成功 \n");
fclose(fp);
}
void readFile(char filename[20]) //文件读取函数 用于打开已有的数据文件
{
if((fp=fopen(filename,"r+"))==NULL)
{
printf("\n 读取失败\n");
exit(0);
}
else printf("\n 读取成功\n");
fclose(fp);
}
//编码
char * convert(char *chars,char *chars1,HuffmanCode *hc,int n)
{
char *p=chars; int i;
-8-
课程名称：数据结构与算法分析 学生姓名：胡宗鹏 学生学号：0943041310
strcpy(chars1,""); while(*p) { i=1; while(hc[i].ch!=*p&&i<=n) i++; strcat(chars1,hc[i].chs); p++; } writeFile("CodeFile"); printf("编码结果存入文件CodeFile中\n"); printf("编码后为:\n"); puts(chars1); if(sizeof(chars1)==50) printf("\n"); return chars1; } //译码 void transcode(HuffmanTree ht,char *chars2,char*chars3) { int i=1,p; char *q=chars2;char *r=chars3; while(ht[i].parent!=0) i++; p=i; while(*q) { while(ht[p].lchild!=0 && *q) { if(*q=='0') p=ht[p].lchild; else p=ht[p].rchild; q++; } if(ht[p].lchild==0) {*r=ht[p].ch;r++;} p=i; } *r='\0'; printf("译码后为:\n"); puts(chars3); } //主函数 void main() -9-
课程名称：数据结构与算法分析 学生姓名：胡宗鹏 学生学号：0943041310
{HTNode HT;
HuffmanCode HC,*hc;
HuffmanTree ht;
huf *HUF,huf2;
int n;
sw w[40];
char ch,inchar[500],outchar[1000];
char *abc;
char *p=inchar;
int m,flag=1; // m用于控制菜单的选择项 flag用于控制菜单弹出 while(flag)
{
printf("%53s\n"," 哈夫曼树应用 "); printf("
********************MENU*********************\n\n");
printf("\t\t1>建立哈夫曼树 2>利用哈夫曼树进行编码 \n");
printf("\t\t3>利用哈夫曼树进行译码 4>退出 \n");
printf("
*********************************************\n");
printf("请选择1---4(请先建立哈夫曼树后再进行后续操作)\n");
scanf("%d",&m);
switch(m)
{ case 1:
{
input(&n,w);
HUF=HuffmanCoding(&HT,&HC,w,n,&huf2);
writeFile("hfmTree");
printf("数据存入文件hfmTree中\n\n");
}
break;
case 2:
{printf("\n创建一个用来编码的原文件\n");
printf("请输入添加到原文件的字符序列，并以#结束\n(注意只能为建立哈夫曼树时用到的字符，且不能有空格): \n");
fflush(stdin);//清除流,解决输入干扰
ch=getchar();
while(ch!='#')
{*p=ch;
-10-
课程名称：数据结构与算法分析 学生姓名：胡宗鹏 学生学号：0943041310
p++;
ch=getchar();
}
*p='\0';
hc=HUF->HC;
ht=HUF->HT;
writeFile("ToBeTran");
printf("数据保存为文件ToBeTran\n");
printf("\n对文件ToBeTran中的代码进行编码\n\n");
readFile("ToBeTran");
abc=convert(inchar,outchar,hc,n);
writeFile("CodePrint");
printf("编码结果以紧凑格式显示在终端后存入文件CodePrint中\n");
}
break;
case 3:
{
printf("\n对文件CodeFile中的代码进行译码\n");
readFile("CodeFile");
transcode(ht,abc,outchar);
writeFile("TextFile");
printf("译码结果存入文件TextFile中\n");
}
break;
case 4:
exit(0);
default:
printf("请输入数字1---4\n");
}
}
}
-11-