哈夫曼树应用数据结构课程设计报告


数结构
课程设计报告


设计题目：哈夫曼树应



专 业 ： 软件工程
班 级 ： 软件
学 生 ：
学 号 ：
指导教师 ：
起止时间 ：20110704—20110708





2011 年 春季 学期


目 录
．具体务 …2
1功……………………………………………………………………………2
2分步实施………………………………………………………………………2
3求……………………………………………………………………………2
二．哈夫曼编码 2
1问题描述 2
2基求 3
3实现提示 3
三．设计流程图 4
1建立哈夫曼树…………………………………………………………………4
2编码……………………………………………………………………………5
3译码……………………………………………………………………………6
4程序…………………………………………………………………………7
四．设计概 8
1问题哈夫曼定义8
2实现功函数………………………………………………………8
3功模块………………………………………………………………………8
五．源程序 9
六．调试分析 15
七．心体会 18
八．参考文献 18


















务
题目：哈夫曼树应
1功：
1．终端读入字符集nn字符n权值建立哈夫曼树存文件hfmTree中已存中哈夫曼树直观方式（树）显示终端
2．利已建哈夫曼树（存文件htmTree中读入）文件ToBeTran中正文进行
编码然结果存入文件CodeFile中输出结果文件CodeFile紧凑格式先终端行50代码时字符形式编码文件写入文件CodePrint中
3．利已建哈夫曼树文件CodeFile中代码进行译码结果存入文件TextFile中输出结果

2分步实施：
1） 初步完成总体设计搭框架确定机话界面确定函数数
2） 完成低求：完成功1
3） 进步求：完成功23兴趣学扩充系统功
3求：
1）界面友函数功划分
2）总体设计应画流程图
3）程序加必注释
4） 提供程序测试方案
5） 程序定起测试宁功少运行起运行程序没价值

二哈夫曼编码
1 问题描述
利赫夫曼编码进行通信提高信道利率缩短信息传输时间降低传输成求发送端通编码系统传输数预先编码接收端传数进行译码（复原）双工信道（双传输信息信道）端需完整编译码系统试样信息收发站编写赫夫曼码编译码系统
2 基求
完整系统应具功：
(1) I：初始化（Initialization）终端读入字符集nn字符n权值建立赫夫曼树存文件hfmTree中
(2) E：编码（Encoding）利已建赫夫曼树（存文件hfmTree中读入）文件ToBeTran中正文进行编码然结果存入文件CodeFile中
(3) D：译码（Decoding）利已建赫夫曼树文件CodeFile中代码进行译码结果存入文件Textfile中
3 实现提示
(1) 编码结果文方式存储文件Codefile中
(2) 户界面设计菜单方式：显示述功符号加Q表示退出运行Quit请户键入选择功符功执行完毕显示菜单直某次户选择Q止
(3) 程序次执行程中第次执行I DC命令赫夫曼树已存必读入次执行中定执行I命令文件hfmTree早已建
三设计流程图
建立哈夫曼树：

开始
n<1
Renturn 0
m2*n1
i1iWhile(getchar()n
输入字符权值
HT[i]chz
HT[i]weightw
HT[i]parent0
HT[i]lchild0
HT[i]rchild0



编码：

开始
cd[start]1

i1istartn1
cd[start]0
cIfHT[i]parent f0fHT[f]parent
HT[f]childl
结束

译码：
开始
Lk

output_file
coutcant open file
Return 1
Coutcan’t open file
Strcmp(H[i]hlchild0
结束
i1i
while(h[k]0)

j0j
K0

h[j]＼0
输出译码


程序：
开始
main
建立哈夫曼树
choiceI||choiceI
结束
编码

return 0
choiceE||choicee
choiceD||choiced
choiceQ||choiceq
编码




四概设计
1）问题哈夫曼定义：
1哈夫曼树节点数类型定义：
typedef struct{ 赫夫曼树结构体
char ch
int weight 权值
int parentlchildrchild
}htnode*hfmtree
2）实现功函数
1void hfmcoding(hfmtree &HThfmcode &HCint n)初始化哈夫曼树处理InputHuffman(Huffman Hfm)函数数哈夫曼规建立2叉树函数块调Select（）函数
2void Select(hfmtree &HTint aint *p1int *p2) Select函数选出HT树a止权值parent02节点
3 int main()
函数： 利已建哈夫曼树（存文件hfmtreetxt中读入）
文件中正文进行编码然结果存入文件codefiletxt中果正文中没编码字符键盘读入存储ToBeTran文件中读入ToBeTran中编码容编码哈夫曼编码存储CodeFile中
4Encoding
编码功：输入字符进行编码
5Decoding
译码功： 利已建哈夫曼树文件codefiletxt中代码进行译码结果存入文件textfiledat 中
Print() 印功函数：输出哈夫曼树字符权值应编码
6函数简说明函数设计分支语句户挑选实现功
链树存储然分调统计频数函数排序函数建立哈夫曼函数编码函数译码函数实现功
3）功模块：
哈夫曼编码译码器
初始化哈夫曼树
编码
译码
印哈夫曼树
印编码






五源程序
#include
#include
#include
#include
#include
typedef struct{ 哈夫曼树结构体
char ch
int weight 权值
int parentlchildrchild
}htnode*hfmtree
typedef char **hfmcode

void Select(hfmtree &HTint aint *p1int *p2) Select函数选出HT树a止权值parent02节点
{
int ijxy
for(j1j if(HT[j]parent0){
xj
break
}
}
for(ij+1i if(HT[i]weight xi 选出节点
}
}
for(j1j if(HT[j]parent0&&xj)
{
yj
break
}
}
for(ij+1i {
if(HT[i]weight {
yi 选出次节点
}
}
if(x>y){
*p1y
*p2x
}
else
{
*p1x
*p2y
}
}
void hfmcoding(hfmtree &HThfmcode &HCint n) 构建哈夫曼树HT求出n字符哈夫曼编码HC
{
int istartcfmw
int p1p2
char *cdz
if(n<1){
return
}
m2*n1
HT(hfmtree)malloc((m+1)*sizeof(htnode))
for(i1i {
printf(请输入第d字符信息权值：i)
scanf(cd&z&w)
while(getchar()＇＼n＇)
{
continue
}
HT[i]chz
HT[i]weightw
HT[i]parent0
HT[i]lchild0
HT[i]rchild0
}

for(i {
HT[i]ch＇0＇
HT[i]weight0
HT[i]parent0
HT[i]lchild0
HT[i]rchild0
}
for(in+1i {
Select(HTi1&p1&p2)
HT[p1]parentiHT[p2]parenti
HT[i]lchildp1HT[i]rchildp2
HT[i]weightHT[p1]weight+HT[p2]weight
}

HC(hfmcode)malloc((n+1)*sizeof(char *))
cd(char *)malloc(n*sizeof(char))
cd[n1]＇＼0＇

for(i1i {
startn1
for(cifHT[i]parentf0cffHT[f]parent)
{
if(HT[f]lchildc)
{
cd[start]＇0＇
}
else
{
cd[start]＇1＇
}
}

HC[i](char*)malloc((nstart)*sizeof(char))
strcpy(HC[i]&cd[start])
}
free(cd)
}


int main(){
char code[100]h[100]hl[100]
int nijkl
ifstream input_file 文件输入输出流
ofstream output_file
char choicestr[100]
hfmtree HT
hfmcode HC
cout<<＼n
cout<< <<软件092班<< <<姓名张耀飞<< <<学号：3090921040＼n
while(choice＇Q＇&&choice＇q＇) choice值qQ时循环
{
cout<< <<*************************哈夫曼编码译码器*************************＼n
cout<< < cout<<请输入您操作步骤：
cin>>choice
if(choice＇I＇||choice＇i＇) 初始化赫夫曼树
{
cout<<请输入字符数：
cin>>n
hfmcoding(HTHCn)
for(i1i {
cout< }
output_fileopen(hfmTreetxt)
if(output_file){
cout< return 1
}
for(i1i {
output_file<<(< }
output_fileclose()
cout<<哈夫曼树已创建完毕已放入hfmTreetxt文件中< }
else if(choice＇E＇||choice＇e＇) 进行编码字符放入ToBeTrantxt码值放入CodeFiletxt中
{
printf(请输入字符：)
gets(str)
output_fileopen(ToBeTreetxt)
if(output_file)
{
cout< return 1
}
output_file< output_fileclose()
output_fileopen(CodeFiletxt)
if(output_file){
cout< return 1
}
for(i0i for(j0j {
if(HT[j]chstr[i])
{
output_file< break
}
}
}
output_fileclose()
cout<<＼n
cout<<编码完毕已存入CodeFiletxt文件＼n
input_fileopen(CodeFiletxt) CodeFiletxt中读入编码输出终端
if(input_file)
{
cout< return 1
}
input_file>>code
cout<<编码码值：< input_fileclose()
}
else if(choice＇D＇||choice＇d＇) 读入CodeFiletxt中编码进行译码译出字符放入Textfiletxt中
{
input_fileopen(CodeFiletxt)
if(input_file){
cout< return 1
}
input_file>>h
input_fileclose()
output_fileopen(Textfiletxt)
if(output_file)
{
cout< return 1
}
k0
while(h[k]＇＼0＇) 先编码中前字符编码相较然移
{
for(i1i lk
for(j0j hl[j]h[l]
}
hl[j]＇＼0＇
if(strcmp(HC[i]hl)0)
{
output_file< kk+strlen(HC[i])
break
}
}
}
output_fileclose()
input_fileopen(Textfiletxt)
if(input_file){
cout< return 1
}
input_file>>h
cout< input_fileclose()
cout<<译码结束字符已存入Textfiletxt文件中< }
else if(choice＇Q＇||choice＇q＇) 退出程序
{
exit(0)
}
else 果选选项外户重新选择
{
cout<<您没输入正确步骤请重新输入< }
cout< }
return 0
}
六调试分析



编码



译码


退出




七实验心体会

课程设计中编写源代码调试中出现少错误遇麻烦困难调试中错误终找出错误修改正确够执行程序中通分析学：
定义头文件时少写头文件肯定会出错没定义引相关头文件必定调试通
执行译码操作时知什原总编译二进制数编译成字符连接号连接起序直接放起视觉效果遗憾哈夫曼编码译码器没老师求样完成编文件功设计失败处

通次数结构课程设计学课没懂知识求哈夫曼树哈夫曼编码译码算法更加深刻解更巩固课堂中学关哈夫曼编码知识真正学会种算法求解算法时问题加思索做首先先概解接着详细分析步做前否处理相似问题步骤必定会利做出
次课程设计编辑中犯应错误设计统计字符合时忘记应该样保存数文件操作生疏断分析明确改正错误疏漏程序更高质量
八．参考文献：

[1 ] 　谭浩强 C 程序设计(第二版) [M] 北京清华学出版社1999 161 163
[2 ] 　谭浩强张基温唐永炎 C 语言程序设计教程(第二版) [M] 北京高等教育出版社1998 113 115
[3 ] 　严蔚敏吴伟民 数结构(C 语言版) [M] 北京清华学出版社2002 55 58
[4] 　李士峰张谢华孙清滇 ActiveX文档技术VB 程序设计网络课件制作中应 [5 ] 　王　颖王正洲 汉诺塔问题迭代算法实现分析[J ] 合肥联合学学报1999




考核成绩评定：






























签字：
年 月 日
西an 理 工 学

文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档