哈夫曼树课程设计样本.doc

资料内容仅供您学习参考，如有不当之处，请联系改正或者删除。

中南林业科技大学
课程设计报告

设计名称: 数据结构课程设计
姓 名: 王昆 学 号: 4282
专业班级: 级软件工程
系 ( 院) : 计算机与信息工程学院
设计时间: ~ 第二学期
设计地点: 电子信息楼 机房

成绩:
指导教师评语:

签名:
年 月 日

1．课程设计目的
1、 训练学生灵活应用所学数据结构知识, 独立完成问题分析, 结合数据结构理论知识, 编写程序求解指定问题。
2.初步掌握软件开发过程的问题分析、 系统设计、 程序编码、 测试等基本方法和技能;
3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力;
4.训练用系统的观点和软件开发一般规范进行软件开发, 巩固、 深化学生的理论知识, 提高编程水平, 并在此过程中培养她们严谨的科学态度和良好的工作作风。
2．课程设计任务与要求:
任务
. 哈夫曼树应用
功能:
(1) 从终端读入字符集大小n, 以及n个字符和n个权值, 建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树
以直观的方式( 比如树) 显示在终端上;
(2) 利用已经建好的哈夫曼树( 如不在内存, 则从文件htmTree中读入) , 对文件ToBeTran中的正文进行编码, 然后将结果存
入文件Cod eFile中, 并输出结果, 将文件CodeFile以紧凑格式先是在终端上, 每行50个代码。同时将此字符形式的
编码文件写入文件CodePrint中。
(3) 利用已建好的哈夫曼树将文件CodeFile中的代码进行译码, 结果存入文件TextFile中, 并输出结果。
分步实施:
1） 初步完成总体设计, 搭好框架, 确定人机对话的界面, 确定函数个数;
2） 完成最低要求: 完成功能1;
3） 进一步要求: 完成功能2和3。有兴趣的同学能够自己扩充系统功能。

要求:
1、 在处理每个题目时, 要求从分析题目的需求入手, 按设计抽象数据类型、 构思算法、 经过设计实现抽象数据类型、 编制上机程序和上机调试等若干步骤完成题目, 最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数, 加大代码的重用率。
2、 设计的题目要求达到一定工作量( 300行以上代码) , 并具有一定的深度和难度。
3、 程序设计语言推荐使用C/C++, 程序书写规范, 源程序需加必要的注释;
4、 每位同学需提交可独立运行的程序;
5 、 每位同学需独立提交设计报告书( 每人一份) , 要求编排格式统一、 规范、 内容充实, 不少于10页( 代码不算) ;
6、 课程设计实践作为培养学生动手能力的一种手段, 单独考核

3．课程设计说明书
一 需求分析
要求用到数据结构课上学到的线性表的知识, 因此就要充分而清晰的理解关于线性表的知识。
要求实现的基本功能很简单, 只有删除和插入, 增加功能也不过是加上修改。这些在数据结构课上已经讲过, 只要能够理解关于线性表的几个相关的基本算法就能够了。
问题是将输入的信息保存入文件和从文件输出。这里基本是自学的内容, 而且要考虑到是否要自行选择保存的磁盘。
综上, 做这个课题, 要具备的知识就是线性表的基本算法, 文件的保存和读取算法, 必要的C或者C++知识( 本次我将使用C实现) , 以及丰富的程序调适经验。

。
二 概要设计
程序流程图

图 1
三 详细设计
1、 哈夫曼树结点结构定义
struct hfmnode
{
char nValue;//节点值
int weight;//权值
int pnIndex;//父结点下标
int lchildIndex,rchildIndex;//左右孩子的结点下标
};

哈夫曼树类定义
class huffmanTree{
public:
void code(char nvalue[],int w[],int n); //对叶子结点编码
void decode(char nvalue[],char hfmcode[],int n);//对叶子结点译码
void Output(huffmanTree ht,int n);//输出哈夫曼树
//private:
hfmnode hfmNode[ ];//用数组存储哈夫曼结点
void creatHfmTree(char nvalue[],int w[],int n);//创立哈夫曼树
void select(int pos,int &nodeOne,int &nodeTwo);//查询最小的两个结点
};
2、 主要函数及相关功能
1 在数组hfmNode中从O开始到pos位置, 查找哈夫曼树外的权值最小的两个结点的位置
void huffmanTree::select(int pos,int &nodeOne,int &nodeTwo)
2 创立哈夫曼树, nvalue是结点值, w是权值, n是叶子结点的个数
void huffmanTree::creatHfmTree(char nvalue[],int w[],int n)
3 求哈夫曼树的编码 nvalue是结点值数组, w是权值数组 n是叶子结点的个数
void huffmanTree::code(char nvalue[],int w[],int n)
4 哈夫曼译码 nvalue为结点值数组 hfmcode为哈夫曼编码, n个叶子结点
void huffmanTree::decode(char nvalue[],char hfmcode[],int n)
5 检查输入的字符值是否合法
bool isChar(const string& str)

6 输出哈夫曼树, 字符, 权值, 以及它对应的编码
void huffmanTree::Output(huffmanTree ht,int n)

3、 源程序
#include<iostream>
using namespace std;

struct hfmnode//哈夫曼树结点结构定义
{
char nValue;//节点值
int weight;//权值
int pnIndex;//父结点下标
int lchildIndex,rchildIndex;//左右孩子的结点下标
};

class huffmanTree//哈夫曼树类定义
{
public:
void code(char nvalue[],int w[],int n); //对叶子结点编码
void decode(char nvalue[],char hfmcode[],int n);//对叶子结点译码
void Output(huffmanTree ht,int n);//输出哈夫曼树
//private:
hfmnode hfmNode[ ];//用数组存储哈夫曼结点
void creatHfmTree(char nvalue[],int w[],int n);//创立哈夫曼树
void select(int pos,int &nodeOne,int &nodeTwo);//查询最小的两个结点

};

//在数组hfmNode中从O开始到pos位置, 查找哈夫曼树外的权值最小的两个结点的位置
void huffmanTree::select(int pos,int &nodeOne,int &nodeTwo)
{
long w1,w2;
w1=w2=88888;
for(int i=0;i<=pos;i++)
{
if(hfmNode[i].pnIndex==0)

if(hfmNode[i].weight<w1)
{
w1=hfmNode[i].weight;
nodeOne=i;
}
}
for(int j=0;j<=pos;j++)
{
if(hfmNode[j].pnIndex==0)
if(hfmNode[j].weight<w2&&nodeOne!=j)
{
w2=hfmNode[j].weight;
nodeTwo=j;
}
}
}

//创立哈夫曼树, nvalue是结点值, w是权值, n是叶子结点的个数
void huffmanTree::creatHfmTree(char nvalue[],int w[],int n)
{
int pos;
for(pos=1;pos<=n;pos++)
{
hfmNode[pos].nValue=nvalue[pos-1];//结点值
hfmNode[pos].weight=w[pos-1];//权值
hfmNode[pos].pnIndex=hfmNode[pos].lchildIndex=hfmNode[pos].rchildIndex=0;
}
//设置数组hfmNode中的其它结点
for(pos=n+1;pos<=2*n-1;pos++)
{
int nodeOne,nodeTwo;
select(pos-1,nodeOne,nodeTwo);
hfmNode[nodeOne].pnIndex=hfmNode[nodeTwo].pnIndex=pos;//把hfmNode[nodeOne]和hfmNode[nodeTwo]两个结点加入哈夫曼树, 设置她们的父结点位置为pos
hfmNode[pos].lchildIndex=nodeOne;//设置pos结点的左孩子为nodeOne
hfmNode[pos].rchildIndex=nodeTwo;//设置pos结点的右孩子为nodeTwo
hfmNode[pos].weight=hfmNode[nodeOne].weight+hfmNode[nodeTwo].weight;//设置pos结点的权值为左右孩子权值的和
hfmNode[pos].pnIndex=0; //pos父结点为0

}
}

//求哈夫曼树的编码 nvalue是结点值数组, w是权值数组 n是叶子结点的个数
void huffmanTree::code(char nvalue[],int w[],int n)
{
creatHfmTree(nvalue,w,n);
int i,j,c,f;
int start;
char *cd;
cd=new char[n];//用于存储哈夫曼编码的动态空间
cd[n-1]='\0';//编码结束符

cout<<" 结点值 编码"<<endl;
for(i=1;i<=n;i++)//逐个字符求哈夫曼编码
{
start=n-1; //编码结束符位置
for(c=i,f=hfmNode[i].pnIndex;f!=0;c=f,f=hfmNode[f].pnIndex)//从叶子到根逆向求编码
{
if(hfmNode[f].lchildIndex==c)
cd[--start]='0';
else
cd[--start]='1';
}
cout<<" "<<nvalue[i-1]<<" ";
for(j=start;j<n;j++)
cout<<cd[j];
cout<<endl;
}
delete []cd;//释放空间
}

///哈夫曼译码 nvalue为结点值数组 hfmcode为哈夫曼编码, n个叶子结点
void huffmanTree::decode(char nvalue[],char hfmcode[],int n)
{
int i,f;
char c;
for(i=0;i<strlen(hfmcode);)//从根节点往下走的叶子结点
{
//左0右1
for(f=2*n-1;hfmNode[f].lchildIndex!=0&&hfmNode[f].rchildIndex!=0;)
{
c=hfmcode[i];
if(c=='1')
{
f=hfmNode[f].rchildIndex;
i++;
}
else
{
f=hfmNode[f].lchildIndex;
i++;
}

}
cout<<hfmNode[f].nValue;//输出找到的叶子结点
}
cout<<endl;//换行
}
////////检查输入的字符值是否合法
bool isChar(const string& str)
{
int i ;
for(i = 0; i != str.length(); i++)
{
if(!isdigit(str[i]))
{
continue;
}
else
return false;
}
return true;
}

/////////////////////////////////OUTPUT ***********OUTPUT output*****************
void huffmanTree::Output(huffmanTree ht,int n)
//输出哈夫曼树,
{
cout<<"哈夫曼树储存结构模拟: "<<endl;
cout<<"hfmNode weight pnIndex lchildIndex rchildIndex"<<endl;
for(int i=1;i<=2*n-1;i++)
// cout<<i<<" "<<hfmNode[i].weight<<" "<<hfmNode[i].pnIndex<<" "<<hfmNode[i].lchildIndex<<" "<<hfmNode[i].rchildIndex<<endl;
printf("%4d%12d%10d%14d%16d\n",i,hfmNode[i].weight,hfmNode[i].pnIndex,hfmNode[i].lchildIndex,hfmNode[i].rchildIndex);

}
//*************---Main---*************//

//**************---======************//
void main()
{
// int i=1;
// while(i=1)
{
cout<<" "<<endl;
cout<<" *****************--构造哈夫曼树--******************"<<endl;
int n=5;//字符和权值个数
cout<<"请输入字符集大小n: "<<endl;
cin>>n;
char str['n'];
// str[n-1]='\0';
char g;
char str2[ ];//存储哈夫曼编码
int w[26];
huffmanTree obj;

cout<<"请输入"<<n<<"个字符值: "<<endl<<endl;
cin>>str;
//输入字符不合法
while(isChar(str)==0||strlen(str)!=n)
{
cout<<endl;
cout<<"输入错误, 请重新输入"<<endl;
cin>>str;
}
////////////////////////////////////////////

// Output();
//////////////////////////////////////////////

// int n=strlen(str);
cout<<endl;
gocd: cout<<"输入对应权值: "<<endl;
for(int i=0;i<n;i++)
cin>>w[i];
cout<<endl;
int m;
while(1)
{
cout<<"请选择输入0或1: "<<endl;
cout<<"***0、 模拟输出哈夫曼树***"<<endl;
cout<<"***1、 进行编码***********"<<endl;
cout<<"***2、 进行译码***********"<<endl;

cin>>m;

switch(m)
{
case 0:
{
obj.creatHfmTree(str,w,n);
obj.Output(obj,n);///////////////////////////////////////////OUTput
cout<<endl;
}break;
case 1:
{
cout<<"各节点编码如下: "<<endl;
obj.code(str,w,n);
cout<<endl;

}break;
case 2: break;
default:cout<<"很抱歉, 输入错误! 请重新输入: "<<endl;
}
if(m==2)
break;
}

godc: cout<<endl<<"请输入要译码的二进制0、 1串: "<<endl<<endl;
cin>>str2;
cout<<endl;
cout<<"译码结果如下: "<<endl<<endl;
obj.decode(str,str2,n);

cout<<endl;

cout<<endl;
cout<<"是否继续译码(Y/N)?"<<endl;
getchar();
g=getchar();
if(g=='Y')
goto godc;//继续译码
cout<<"是否继续编码(Y/N)?"<<endl;
getchar();
g=getchar();
if(g=='Y')
goto gocd;//继续编码

}

}

四 设计与调试分析
从上面的程序能够看出, 有些地方时没有办法限制的, 比如说输入整型变量的时候, 没有办法限制其不能输入字符型。
在调试的过程中所遇到的问题很多。

五 用户手册
1 本程序能够在vc++5.0和vc++6.0 的环境下运行。
2 在vc中创立一个工程, 将源程序复制到.cpp中, 编译链接就能够。
3 选择编译、 运行以后会出现运行界面, 选择相应的选项, 根据提示即可进行演示。界面如下:

4、 请如数字符集大小n,就是要求用户输入哈夫曼树叶子结点的个数

六 测试成果

测试结束
八.课程设计心得
我相信经过短短几天除了吃饭, 睡觉, 上课就天天坐在电脑面前编程, 那编程水平没有提高是绝对不可能的, 让你每天24小时有18个小时是坐在电脑面前编程, 我相信, 你一定会成为一出类拔萃的程序员。设计心得, 时间太短, 忙不过来, 同时要设计的东西太多, 这个和知识学的不精也有关系, 如果给充分的时间, 我相信没有什么解决不了的! 谢谢老师的指导!