哈夫曼编码与译码课程设计.docx

哈夫曼编码与译码课程设计.docx

《哈夫曼编码与译码课程设计.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码与译码课程设计.docx（21页珍藏版）》请在冰点文库上搜索。

哈夫曼编码与译码课程设计

本科生课程设计论文

题目：

哈夫曼编码与译码

学生姓名：

学号：

专业：

班级：

指导教师：

2015年1月8日

内蒙古科技大学课程设计任务书

课程名称

数据结构与算法课程设计

设计题目

Huffman编码和译码

指导教师

时间

2015.1.5——2015.1.9

一、教学要求

1.掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力

2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能

3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力

4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风

二、设计资料及参数

每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。

Huffman编码和译码

根据给定的字符集和各字符的频率值，求出其中给定字符Huffman编码，并针对一段文本（定义在该字符集上）进行编码和译码，实现一个Huffman编码/译码系统。

要求设计类（或类模板）来描述Huffman树及其操作，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：

v求Huffman编码

v输入字符串，求出编码

v输入一段编码，实现译码

并设计主函数测试该类。

三、设计要求及成果

1.分析课程设计题目的要求

2.写出详细设计说明

3.编写程序代码，调试程序使其能正确运行

4.设计完成的软件要便于操作和使用

5.设计完成后提交课程设计报告

四、进度安排

资料查阅与讨论（1天）

系统分析（2天）

系统的开发与测试（5天）

编写课程设计说明书和验收（2天）

五、评分标准

1.根据平时上机考勤、表现和进度，教师将每天点名和检查

2.根据课程设计完成情况，必须有可运行的软件。

3.根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。

4.根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问

六、建议参考资料

1．《数据结构（C语言版）》严蔚敏、吴伟民主编清华大学出版社2004.11

2．《数据结构课程设计案例精编（用C/C++描述）》，李建学等编著，清华大学出版社2007.2

3.《数据结构:

用面向对象方法与C++语言描述》，殷人昆主编， 清华大学出版社2007

目录

第1章需求分析3

第2章总体设计3

第3章抽象数据类型定义4

3.1哈夫曼编码与译码抽象数据类型的设计4

第4章详细设计4

4.1工程视图4

4.2类图视图5

4.3函数的调用关系5

4.4主程序流程图6

4.5主要算法的流程图7

第5章测试9

第6章总结10

附录：

程序代码11

第1章需求分析

Huffman编码和译码

根据给定的字符集和各字符的频率值，求出其中给定字符Huffman编码，并针对一段文本（定义在该字符集上）进行编码和译码，实现一个Huffman编码/译码系统。

要求设计类（或类模板）来描述Huffman树及其操作，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：

求Huffman编码

输入字符串，求出编码

输入一段编码，实现译码

并设计主函数测试该类。

第2章总体设计

图2.1

主函数：

对输入的字符段进行存储，并对字符数和对应的权值（字符个数）进行统计存储。

哈夫曼树初始化函数：

对给定的字符数和权值，创建一棵哈夫曼树。

权值大小比较函数：

找到每次所给集合的最小值和次小值，并返回给哈夫曼树初始化函数。

哈夫曼树编码函数：

对创建的哈夫曼树，为左孩子的赋值为0，右孩子赋值为1，然后对叶子结点依次编码。

哈夫曼树译码函数：

对输入的01二进制数一一与叶子结点的编码依次比较匹配。

第3章抽象数据类型定义

3.1哈夫曼编码与译码抽象数据类型的设计

enumChild{none,lchild,rchild};//采用枚举，标记是左孩子还是右孩子

classelement//元素类

{

public:

//类的公有成员

elememt（）;//构造函数

voidchange（charl,char*c,intp,Childh,intw）//对对象进行修改操作

voidgetparent（intp）//对父结点的值进行修改操作

voidgeta（Childh）//对孩子结点进行修改操作

voidgetweight（intw）//对权值进行修改操作

intreturnweight（）//返回权值操作

friendvoidSelect（elementh[],intk,int*a,int*b）;//友元函数的声明

friendvoidHuffmanTreeCode（elementHT[]）;

friendvoidHuffmanTreeYima（elementhuff[],charcod[],intb）;

private:

//类的私有成员

charletter,*code;//letter为字符,*code指向编码字符串

intweight;//权值

intparent;//父结点

Childa;//为父结点的左孩子还是右孩子

};

第4章详细设计

4.1工程视图

图4.1工程视图

4.2类图视图

图4.2类图视图

4.3函数的调用关系

如下图：

图4.3函数调用关系图

4.4主程序流程图

4.5主要算法的流程图

图4.5.1哈夫曼编码函数

图4.5.2哈夫曼译码函数

第5章测试

图5.1哈夫曼编码与译码

第6章总结

这次课程设计写得比较仓促，程序许多处仍需要完善和修改。

写课程设计的过程中也暴露出自身的许多不足，比如对c++语言有许多遗忘，比如把算法思想付诸实际代码的能力仍然不足。

课程设计的过程也是对自己所学的知识回顾和检验的过程，在这期间不断遇到问题和解决问题也使我对所学过的知识有着更深层次的认识，编程能力也有很大的进步。

对于程序，不足之处是友元函数的定义使得类的封装性大大降低，程序的主函数不够简明，没有进一步细分函数的功能等。

附录：

程序代码

#include

#include

#include

#include

#include

constintLengh=1000;//最大长度为1000

charcoding[100];//存储二进制字符串

intn;//定义全局变量

ofstreamfile1（"编码.txt"）;;//创建编码保存文件

ofstreamfile2（"译码.txt"）;;//创建译码保存文件

enumChild{none,lchild,rchild};//采用枚举标记事左孩子还是右孩子

classelement

{

public:

elememt（）;

voidchange（charl,char*c,intp,Childh,intw）

{

code=c;

letter=l;

a=h;

weight=w;

parent=p;

}

voidgetparent（intp）

{

parent=p;

}

voidgeta（Childh）

{

a=h;

}

voidgetweight（intw）

{

weight=w;

}

intreturnweight（）

{

returnweight;

}

friendvoidSelect（elementh[],intk,int*a,int*b）;

friendvoidHuffmanTreeCode（elementHT[]）;

friendvoidHuffmanTreeYima（elementhuff[],charcod[],intb）;

private:

charletter,*code;//letter为字符,*code指向编码字符串

intweight;//权值域

intparent;//父结点序号

Childa;//为父结点的左孩子还是右孩子

};

voidSelect（elementh[],intk,int*a,int*b）;//寻找最小和次小节点的序号

voidInitHuffmanTree（elementhuffTree[],chart[],intw[]）//哈夫曼树的初始化

{

inti,m=2*n-1,s1,s2;//no+n2=n所以一要申请m个空间

for（i=0;i

{

huffTree[i].change（t[i],'\0',-1,none,w[i]）;

}

for（;i<=m;i++）//后m-n个结点置空

{

huffTree[i].change（'','\0',-1,none,0）;

}

for（i=n;i

{

Select（huffTree,i-1,&s1,&s2）;//在huffTree中找权值最小的两个结点s1,s2

huffTree[s1].getparent（i）;//将s1,s2合并，则s1,s2的双亲是i

huffTree[s2].getparent（i）;

huffTree[s1].geta（lchild）;//s1是左孩子

huffTree[s2].geta（rchild）;//s2是右孩子

huffTree[i].getweight（huffTree[s1].returnweight（）+huffTree[s2].returnweight（））;//s1,s2的双亲的权值为s1，s2权值之和

}

}

voidSelect（elementh[],intk,int*a,int*b）//寻找最小和次小节点的序号

{

inti;

intmin1=1000;//初始化最小结点和次小结点

intmin2=1000;

for（i=0;i<=k;i++）//找最小的结点序号

{

if（h[i].parent==-1&&h[i].weight

{

*a=i;//将i放入a中

min1=h[i].weight;//找到第一个最小结点

}

}

for（i=0;i<=k;i++）//找次小结点的序号

{

if（h[i].parent==-1&&（*a!

=i）&&h[i].weight

{

*b=i;

min2=h[i].weight;//找到次最小结点

}

}

}

voidHuffmanTreeCode（elementHT[]）//字符编码

{

inti;

char*temp;

temp=（char*）malloc（n*sizeof（char））;//分配n个字符空间

temp[n-1]='\0';//最后一个字符以后结束字符串

intp;

ints;

for（i=0;i

{

p=i;

s=n-1;//s为最后一个结点

while（HT[p].parent!

=-1）//从字符结点回溯,直至根结点

{

if（HT[p].a==lchild）//p指向的如果是左孩子

temp[--s]='0';//s位置字符为0

elseif（HT[p].a==rchild）//p指向的如果是右孩子

temp[--s]='1';//s位置字符为1

p=HT[p].parent;//回溯父结点

}

HT[i].code=（char*）malloc（（n-s）*sizeof（char））;//分配结点编码长度的内存空间

strcpy（HT[i].code,temp+s）;//将temp中从第s个位置开始，将编码拷贝到HT[i].code

printf（"%c",HT[i].letter）;

printf（":

"）;

printf（"%s\n",HT[i].code）;//打印出字符即对应的二进制字符串

file1<

"<

}

}

voidHuffmanTreeYima（elementhuff[],charcod[],intb）//译码

{

charsen[100];

chartemp[50];

charvoidstr[]="";//空白字符串

intt=0;ints=0;

intxx=0;

for（inti=0;i

{

temp[t++]=cod[i];//读取字符

temp[t]='\0';//有效字符串

for（intj=0;j

{

if（!

strcmp（huff[j].code,temp））//匹配成功

{

sen[s]=huff[j].letter;//将字符保存到sen中

s++;

xx+=t;

strcpy（temp,voidstr）;//将TEMP置空

t=0;//t置空

break;

}

}

}

if（t==0）//t如果被置空了，表示都匹配出来了，打印译码

{

sen[s]='\0';

cout<<"译码为:

"<

file2<

cout<

}

else//t如果没有被置空，源码无法被完全匹配

{cout<<"二进制源码有错！

从第"<

file2<<"二进制源码有错！

从第"<

}

}

voidmain（）

{

chara[Lengh],p;

inti,b[Lengh];

intsymbol=1;

intx;

intk;

if（!

file1）

{

cout<<"不能打开文件1!

";

return;

}

if（!

file2）

{

cout<<"不能打开文件2!

";

return;

}

cout<<"\t\t\t\t哈夫曼编码与译码\t\t\t\t"<

cout<<"编码：

"<

cout<<"请输入一句话进行初始编码：

";

charbuff[1024]={0};//零时存放输入的话

cin.getline（buff,1024）;//读入一行包括空格键，以回车键结束

intlen=strlen（buff）;

elementh[Lengh];

for（i=0;i

{

for（intj=0;j

{

if（a[j]==buff[i]）

{

b[j]=b[j]+1;

break;

}

}

if（j>=n）

{

a[n]=buff[i];

b[n]=1;

n++;

}

}

for（i=0;i

{

cout<<"字符：

"<<（char）a[i]<<"权值：

"<<（int）b[i]<

}

InitHuffmanTree（h,a,b）;//哈夫曼树的初始化

HuffmanTreeCode（h）;//编码

cout<<"译码：

"<

while

（1）

{

cout<<"请输入要译码的二进制字符串,输入'#'结束：

";

file2<<"二进制字符串:

";

x=1;

k=0;

symbol=1;

while（symbol）

{

cin>>p;

if（p!

='1'&&p!

='0'&&p!

='#'）//若存在其它字符，x设为0，表示输入的不是二进制

{

x=0;

}

coding[k]=p;

if（p=='#'）

symbol=0;//#号结束标志

else

file2<

k++;

}

if（x==1）

{

file2<

";

HuffmanTreeYima（h,coding,k-1）;//进行译码

file2<

}

else

{

cout<<"有非法字符！

"<

file2<

"<

}

cout<<"是否继续?

（Y/N）:

";

cin>>p;

if（p=='y'||p=='Y'）

continue;

else

break;

}

file1.close（）;

file2.close（）;

}........忽略此处.......