专业课程设计方案报告哈夫曼编码.doc

学 号：

课 程 设 计

题 目
哈夫曼编码
学 院
计算机科学与技术
专 业
计算机科学与技术
班 级

姓 名

指引教师

年
07
月
02
日

课程设计任务书

学生姓名： 拉巴珠久 专业班级： 计算机0806
指引教师： 姚寒冰 工作单位： 计算机科学系
题 目： 哈夫曼编码
初始条件：
输入一段英文字符，试为该文中每个字符编制相应哈夫曼码。
（1）I：初始化（Initialization）。对输入一段英文中每个字符记录其权值，建立哈夫曼树；
（2）E：编码（Encoding）。运用已建好哈夫曼树，对每个字符进行编码。
（3）D：译码（Decoding）。运用已建好每个编码，对输入一种由0、1构成序列进行译码；
（4）P：印代码文献（Print）。将每个字符编哈夫曼码和译码成果显示在终端上。
测试用例见题集p149。
规定完毕重要任务：（涉及课程设计工作量及其技术规定，以及阐明书撰写等详细规定）
课程设计报告按学校规定格式用A4纸打印（书写），并应包括如下内容：
1、问题描述
简述题目要解决问题是什么。
2、设计
存储构造设计、重要算法设计（用类C语言或用框图描述）、测试用例设计；
3、调试报告
调试过程中遇到问题是如何解决；对设计和编码讨论和分析。
4、经验和体会（涉及对算法改进设想）
5、附源程序清单和运营成果。源程序要加注释。如果题目规定了测试数据，则运营成果要包括这些测试数据和运营输出，
6、设计报告、程序不得互相抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。
时间安排：
1、第18周（6月28日至7月2日）完毕。
2、7月2 日08：30到计算中心检查程序、交课程设计报告、源程序（CD盘）。
指引教师签名： 年 月 日
系主任（或责任教师）签名： 年 月 日

目录
1 设计题目 1
2 问题描述 1
3.1数据构造设计 1
3.2重要算法设计 3
3.3测试用例设计 6
4调试报告 7
5结束语 7
六、课程设计参照资料 8
附录 9
F1 源代码 9
F2 运营成果 16

哈夫曼编码
1 设计题目
哈夫曼编码
2 问题描述
输入一段英文字符，试为该文中每个字符编制相应哈夫曼码。
（1）I：初始化（Initialization）。对输入一段英文中每个字符记录其权值，建立哈夫曼树；
（2）E：编码（Encoding）。运用已建好哈夫曼树，对每个字符进行编码。
（3）D：译码（Decoding）。运用已建好每个编码，对输入一种由0、1构成序列进行译码；
（4）P：印代码文献（Print）。将每个字符编哈夫曼码和译码成果显示在终端上。
3．设计
3.1数据构造设计
抽象数据类型二叉树定义如下：
ADT BinaryTree{
数据对象D：D是具备相似特性数据元素集合。
数据关系R：
基本操作P：
InitBiTree（&T）；
操作成果：构造空二叉树T。
DestroyBiTree（&T）；
初始条件：二叉树T存在。
操作成果：销毁二叉树T。
CreateBiTree（&T，definition）；
初始条件：definition给出二叉树T定义。
操作成果：按definition构造二叉树T。
ClearBiTree（&T）；
初始条件：二叉树T存在。
操作成果：将二叉树T清为空树。
BiTreeEmpty（T）；
初始条件：二叉树T存在。
操作成果：若T为空二叉树。则返回TRUE，否则FALSE。
BiTreeDepth（T）；
初始条件：二叉树T存在。
操作成果：返回T深度。
Root（T）；
初始条件：二叉树T存在。
操作成果：返回T根。
Value（T，e）；
初始条件：二叉树T存在，e是T中某个结点。
操作成果：返回e值。
Assign（T，&e，value）；
初始条件：二叉树T存在，e是T中某个结点。
操作成果：结点e赋值为value。
Parent（T，e）；
初始条件：二叉树T存在，e是T 中某个结点。
操作成果：若e是T非根结点，则返回它双亲，否则返回“空”。
DeleteChild（T，p，LR）；
初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。
操作成果：依照LR为0或1，删除T中p所指结点左或右子树。
InsertChild（T，p，LR，c）；
初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。
操作成果：依照LR为0或1，插入c为T中p所指结点左或右子树。P所指结点原有左或右子树则成为c右子树。}
3.2重要算法设计
程序中一共定义了一种构造体和三个函数如下：
struct Huffman//定义指向结点构造体
{
int weight;//权值
int parent,lchild,rchild;//爸爸结点和左右结点位置
};

void select(Huffman * ht,int i,int & s1,int & s2)
{//选取权值较小两个作为新叶子结点，用于huffman构造。
int j,k;
k=s1;
for(j=0;j<i+1;j++)
if(s1!=j&&j!=s2&&ht[j].parent==0)
{
s1=j;break;
}
for(j=0;j<i+1;j++)
if(s2!=j&&s1!=j&&j!=k&&ht[j].parent==0)
{
s2=j;break;
}
for(j=1;j<=i;j++)
if(ht[j].weight<ht[s1].weight&&ht[j].parent==0)s1=j;
if(s1==s2)
{
for(j=0;j<i+1;j++)
if(s2!=j&&s1!=j&&j!=k&&ht[j].parent==0)
{
s2=j;break;
}
}
for(j=0;j<=i;j++)
if(ht[j].weight<ht[s2].weight&&ht[j].parent==0&&j!=s1) s2=j;

}

void Huffmancoding(Huffman * ht,char * *&hc,int k)
{//对haffman进行编码
int m,s1=0,s2=0,start,c,i,f,j;
char * cd;
m=2*k-1;
for(i=k;i<m;i++)//构建huffman树
{
select(ht,i-1,s1,s2);//调用select函数
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;
}
for(i=0;i<=k-1;i++)//对每个叶子结点进行编码
{
cd=new char[k];
hc[i]=" ";
for(j=0;j<k;j++)
cd[j]=' ';
start=k-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]=&cd[start+1];

}

}
void frequency(int * & w,char str[100],int * & c,int n,int & k)
{//涵数用于记录输入字符权w（浮现次数）。
int i,j,m;
for(i=0;i<n;i++)
{
if(i==0){c[0]=0;continue;}
for(j=0;j<i;j++)
if(str[j]==str[i]){c[i]=c[j];break;}
if(j= =i){c[i]=++k;}
}
for(j=0;j<=k;j++)
{
for(m=0;m<n;m++)
if(c[m]= =j)w[j]++;
}

}

3.3测试用例设计
已知某系统在通信联系中只也许浮现八种字符，其概率分别为0.05；0.29；0.07；0.08；0.14；0.23；0.03；0.11,试设计哈夫曼编码。
设权w=（5，29；7；8；14；23；3；11），n=8，则m=15，构造哈夫曼树。如下图：

23
11
14
5
3
7
8
29
0
1
1
1
0
0
0
1
1
0
0
0

1
1

哈夫曼编码：
1
2
3
4
5
6
7
8

0110

10

1110

1111

110

00

0111

010

4调试报告
程序调试：
（1.）当01序列解码成字符串时，要注意与否与已得出字符串编码匹配，如果不匹配，就把它背面01序列截掉，不进行解码。
(2.) &表达函数参数是按地址传递，当函数有各种返回值而无法用return实现时，普通使用这种。例如：void frequency(int * & w,char str[100],int * & c,int n,int & k)

5结束语
经验和体会：
通过一种星期努力，总算把课程设计给完毕了，这是一种坚苦而又漫长过程。是啊，读了那么近年书，课程设计可是第一次。看着劳动成果，很欣慰！通过这次课程设计之后我觉得自己对书上知识掌握有很大欠缺，看了题目都不懂得怎么下手，一点头绪都没有，之后自己认真看了一遍书上知识，查阅了某些网上资料，我能纯熟掌握了二叉树，然后在此基本上掌握理解haffman树和编码，熟知了二叉树性质。可是这点小进展远远不够，这只是一种小小开始，只能程序大概轮廓可以写出来了。但是有诸多细节和特殊状况没法写上去，例如：用于huffman构造；用于对haffman进行编码；用于记录输入字符权w（浮现次数）；实现这些程序不懂得该怎么写。日后通过同窗协助和指引慢慢地程序里用到函数通过哪些语句来实现它，那些核心函数如何把它们有机结合起来等等，总之，在同窗多次指引下一种完整程序写出来了，我也努力地去读懂它，发现自己隐约读懂了它！
真正收获更多是思想上，让我结识程序复杂，自己微局限性道，“学无止境”头一次结识这样深刻，察觉自己局限性。在这次编程中，同窗帮了我诸多，我一种人是不能完毕。查书，查资料，请教同窗过程就是我提高过程，总之，通过这次课程设计，我发现程序设计最重要就是上机实践，此前只是看书，觉得看懂了，但是真正到机子上写程序时感觉无从下手，没有什么头绪，也许就是由于事实上机操作太少了，后来需要在这方面好好地加强了。后来学习生活真要踏踏实实，自己计算机生涯必然是坎坷，信心受挫了。

六、课程设计参照资料
[1]《数据构造（STL框架）》，王晓东编著，清华大学出版社，出版或修订时间：9月
[2]《数据构造(C语言版)》，严蔚敏，吴伟民编著，出版社：清华大学出版社，出版或修订时间：1997年4月
[3]《数据构造习题集(C语言版)》，严蔚敏，吴伟民，米宁编著，清华大学出版社，出版或修订时间：1999年2月

起草人：杨克俭
-6-22

附录
F1 源代码
#include <iostream>
using namespace std;

struct Huffman//定义指向结点构造体
{
int weight;//权值
int parent,lchild,rchild;//爸爸结点和左右结点位置
};

void select(Huffman * ht,int i,int & s1,int & s2)
{//选取权值较小两个作为新叶子结点，用于huffman构造。
int j,k;
k=s1;
for(j=0;j<i+1;j++)
if(s1!=j&&j!=s2&&ht[j].parent==0)
{
s1=j;break;
}
for(j=0;j<i+1;j++)
if(s2!=j&&s1!=j&&j!=k&&ht[j].parent==0)
{
s2=j;break;
}
for(j=1;j<=i;j++)
if(ht[j].weight<ht[s1].weight&&ht[j].parent==0)s1=j;
if(s1==s2)
{
for(j=0;j<i+1;j++)
if(s2!=j&&s1!=j&&j!=k&&ht[j].parent==0)
{
s2=j;break;
}
}
for(j=0;j<=i;j++)
if(ht[j].weight<ht[s2].weight&&ht[j].parent==0&&j!=s1) s2=j;

}

void Huffmancoding(Huffman * ht,char * *&hc,int k)
{//对haffman进行编码
int m,s1=0,s2=0,start,c,i,f,j;
char * cd;
m=2*k-1;
for(i=k;i<m;i++)//构建huffman树
{
select(ht,i-1,s1,s2);//调用select函数
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;
}
for(i=0;i<=k-1;i++)//对每个叶子结点进行编码
{
cd=new char[k];
hc[i]=" ";
for(j=0;j<k;j++)
cd[j]=' ';
start=k-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]=&cd[start+1];

}

}
void frequency(int * & w,char str[100],int * & c,int n,int & k)
{//涵数用于记录输入字符权w（浮现次数）。
int i,j,m;
for(i=0;i<n;i++)
{
if(i==0){c[0]=0;continue;}
for(j=0;j<i;j++)
if(str[j]==str[i]){c[i]=c[j];break;}
if(j= =i){c[i]=++k;}
}
for(j=0;j<=k;j++)
{
for(m=0;m<n;m++)
if(c[m]= =j)w[j]++;
}

}
int main()
{
int i=0,m,j,n=0,k=0,l,r=0,t;
int * w,* c;
char * *hc;
char str[100],str1[100];
Huffman * ht;//定义需要使用变量

for(i=0;i<100;i++){str[i]=' ';str1[i]=' ';}

cout<<"请输入需要编码字符串："<<endl;
cin>>str;
i=0;
while(str[i]!=' '){n++;i++;}
n--;//while循环记录输入字符串中字符数;

c=new int [n];
for(i=0;i<n;i++)c[i]=0;
w=new int [n];
for(i=0;i<n;i++)w[i]=0;//对c和w分派初值；

frequency(w,str,c,n,k);

m=2*n-1;//计算总结点数

ht=new Huffman[m];
hc=new char*[n*sizeof(char*)];

for(i=0;i<=k;i++)//代表叶子结点数
{
ht[i].weight=w[i];
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
}
for(;i<m;i++)
{
ht[i].weight=ht[i].parent=ht[i].lchild=ht[i].rchild=0;
}
k++;

Huffmancoding(ht,hc,k);
cout<<"各字符及其相应编码为："<<endl;

for(i=0;i<n;i++)
{
for(l=0;l<i;l++)
{
if(c[i]==c[l])break;
}
if(l==i)
{
cout<<str[i];
for(j=0;j<n;j++)
{
if(hc[c[i]][j]!='0'&&hc[c[i]][j]!='1')break;
else cout<<' '<<hc[c[i]][j];
}
cout<<endl;
}
}
cout<<"您输入字符串编码为:"<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(hc[c[i]][j]!='0'&&hc[c[i]][j]!='1')break;
else cout<<hc[c[i]][j];
}
}

cout<<endl;//前面就是调用上面定义函数来实现
i=0;
cout<<"请输入需要译码字符串:"<<endl;
cin>>str1;
m=0;
while(str1[i]!=' '){m++;i++;}
m--;
j=0;
cout<<"译码后为："<<endl;
while(j<k)
{
for(l=0,i=r;l<k,i<=m;i++,l++)
{

if(hc[j][l]!='0'&&hc[j][l]!='1')
{
r=i;
for(t=0;t<n;t++)
if(c[t]==j){cout<<str[t];break;}
j=0;
break;
}
if(str1[i]!=hc[j][l]){j++;break;}
}
if((i==m)&&(hc[j][l]=='0'||hc[j][l]=='1'))cout<<"但最后"<<i-r<<"个字符无法译码。"<<endl;
if(i==m)break;
}

cout<<endl;

return 0;

}

F2 运营成果

本科生课程设计成绩评估表
班级：计算机0806　 姓名：拉巴珠久　 学号：1
序号
评分项目
满分
实得分
1
学习态度认真、遵守纪律
20

2
设计成果
40

3
设计报告规范（涉及设计图、设计代码）
40

总得分/级别

评语：

注：优（90－100分）、良（80－89分）、中（70－79分）、及格（60－69分）、60分如下为不及格。

　　　　　　　　　　　　　　　　　　指引教师签名：
　　　　　　　　　　　　　　　　　　 年 月　 日