《数据结构课程设计》赫夫曼编码实验报告Word文档下载推荐.docx

《数据结构课程设计》赫夫曼编码实验报告Word文档下载推荐.docx

《《数据结构课程设计》赫夫曼编码实验报告Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《《数据结构课程设计》赫夫曼编码实验报告Word文档下载推荐.docx（20页珍藏版）》请在冰点文库上搜索。

每个模块的功能。

voidmain（）

voidHufffmanEncoding（HuffmanTreeHT,HuffmanCodeHC）//编码部分

char*decode（HuffmanCodeHc）//译码

void ChuffmanTree（HuffmanTree HT,HuffmanCode HC,intcnt[],charstr[]）//生成Huffman树

voidselect（HufmanTreeHT,intk,int&

s1,int&

s2）//找寻parent

为0,权最小的两个节点

开始

进行相应的操作

输出结果

结束

其流程图如下：

构

对

程

造

字

编

序

赫

符

码

结

夫

串

束

曼

译

退

树

出

四、详细设计

4.1赫夫曼树的建立

由赫夫曼算法的定义可知，初始森林中共有n 棵只含根节点的二叉树。

算法的第二步是：

将当前森林中的两颗根节点的二叉树，合并成一颗新的二叉树；

每合并一次，森林中就减少一棵树，产生一个新节点。

显然要进行n-1 次合并，所以共产生n-1 个新节点，它们都是具有两个孩子分支结点。

由此可知，最新求得的赫夫曼树中一共有2n-1个结点，其中n个结点是初始森林的n个孤立结点。

并且赫夫曼树中没有度数为1的分支结点。

我们可用一个大小为2n-1的一维数组来存储赫夫曼树中的结点。

因此，赫夫曼树的存储结构描述为：

#definen100#definem2*n-1typedefstruct{intweight;

intlchild,rchild,parent;

}HTNode;

T

typedefHTNodeHuffmanTree[m+1];

第i个结点权值

否

i=num?

是

第i个根结点

i=2*num-1?

是创建赫夫曼树

输出字符统计情

4.1.1选择选择parent为0且权值最小的两个根结点的算法

voidselect（HuffmanTreeT,intk,int*s1,int*s2）

{//在HT[1……k]中选择parent为0且权值最小的两个根结点，其

序号分别为S1和S2

inti,j;

intmin1=100;

for（i=1;

i<

=k;

i++）//查找s1

if（T[i].weight<

min1&

&

T[i].parent==0）

{

j=i;

min1=T[i].weight;

}

*s1=j;

min1=32767;

for（i=1;

i++）//查找s2,不和s1相同

T[i].parent==0&

i!

=（*s1））

min1=T[i].weight;

*s2=j;

4.1.2统计字符串中字符的种类以及各类字符的个数

假设电子文件字符串全是大写字母，那么该算法的实现思想是：

先定义一个含有26个元素的临时整型数组，用来存储各种字母出现的次数。

应为大写字母的ASCII码与整数1~26个元素之间相差64，因此在算法中使用字母减去64作为统计数组的下标对号入座，无须循环判断来实现，从而提高了效率；

另外，要求出电文字符串中有多少种字符，并保存这些字符以供编码时使用。

统计和保存都比较容易，用一个循环来判断先前统计好的各类字符个数的数组元素是否为零，若不为零，则将其值存入一个数组对应的元素中，同时将其对应的字符也存入另一个数组元素中。

具体实现如下：

intjsq（char*s,intcnt[],charstr[]）

//统计各字符串中各种字母的个数以及字符的种类

char*p;

inti,j,k;

inttemp[27];

=26;

i++）temp[i]=0;

for（p=s;

*p!

='

\0'

;

p++）

{//统计各种字符个数if（*p>

A'

&

*p<

Z'

）{k=*p-64;

temp[k]++;

}j=0;

for（i=1,j=0;

i++）//统计有多少种字符

if（temp[i]!

=0）{j++;

str[j]=i+64;

// 将对应的数组送到数组中

cnt[j]=temp[i];

// 存入对应数组的权值

returnj;

4.1.3构造赫夫曼树

void ChuffmanTree（HuffmanTree HT,HuffmanCode HC,intcnt[],charstr[]）

{//构造赫夫曼树HTinti,s1,s2;

=2*num-1;

i++）//初始化HT，左右孩子，双亲，权值都为0

{HT[i].lchild=0;

HT[i].rchild=0;

HT[i].parent=0;

HT[i].weight=0;

=num;

i++）//输入num个叶节点的权值

HT[i].weight=cnt[i];

for（i=num+1;

i++）//从numd后面开始新建结点存放新生成的父节点

select（HT,i-1,&

s1,&

s2）;

//在HT[1……i-1]中选择parent为0且权值最小的两个根结点，其序号分别为s1和s2HT[s1].parent=i;

HT[s2].parent=i;

//将s1和s2的parent赋值HT[i].lchild=s1;

HT[i].rchild=s2;

//新结点的左右孩子HT[i].weight=HT[s1].weight+HT[s2].weight;

//新结点的权值

for（i=0;

i++）//输入字符集中的字符

HC[i].ch=str[i];

i=1;

while（i<

=num）

printf（"

字符%c,次数为:

%d\n"

HC[i].ch,cnt[i++]）;

4.2赫夫曼编码

要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据设计要求和实际需要定义的类型如下：

typedefstruct{charch;

charbits[n+1];

intstart;

}CodeNode;

typedefCodeNodeHuffmanCode[n];

4.2.1赫夫曼编码算法

voidHuffmanEncoding（HuffmanTreeHT,HuffmanCodeHC）

{//根据赫夫曼树HT求赫夫曼编码表ＨＣ

intc,p,i;

charcd[n];

intstart;

cd[num]='

i++）

start=num;

c=i;

while（（p=HT[c].parent）>

0）//直至上诉到ht[c]是树根为止

{//若HT[c]是HT[p]的孩子，则生成0；

否则生成代码1cd[--start]=（HT[p].lchild==c）?

'

0'

:

'

1'

:

c=p;

}//endofwhilestrcpy（HC[i].bits,&

cd[start]）;

HC[i].len=num-start;

4.2.2建立正文的编码文件

建立编码文件的基本思想是：

将要编码的字符串中的字符逐一与预先生成赫夫曼树时保保存的字符编码对照表进行比较，找到之后，对该字符的编码写入代码文件，直至所有字符处理完毕为止。

具体算法如下：

viod coding（huffmanCodeHC,char*str）

FILE*fp;

fp=fopen（“codefile.tex”,”w”）;

while（*str）{//对电文中字符逐一生成编码并写入文件for（i=1;

if（HC[i].ch==*str）{for（j=0;

j<

=HC[i].len;

j++）fputc（HC[i].bits[j],fp）;

break;

}str++;

fclose（fp）;

4.3代码文件的译码

译码的基本思想是:

读文件中编码，并与生成的赫夫曼编码表比较，遇到相等时，即取出其对应的字符存入一个新串中。

Char* decode（HuffmanCode HC）

{//代码文件codefile.tex译码

charstr[254];

char*p;

staticcharcd[n+1]inti,j,k=0,cjs;

fp=fopen（“codefile.tex”,”r”）;

while（!

feof（fp））

{cjs=0;

for（i=0;

=num&

cjs==0&

!

feof（fp）;

cd[i]=‘’；

cd[i+1]='

cd[i]=fgetc（fp）;

for（j=1;

j++）if（strcmp（HC[i].bits,cd）==0）

str[k]=HC[j].ch;

k++;

cjs=1;

break;

str[k]='

p=str;

returnp;

五、运行与测试

运行结果为

六、总结与心得

本次编写过程中出现了较多的问题，比如开始对赫夫曼树的理解不是很清楚，导致在编写过程中某些代码错误而没能及时修改，在最后进行修改时遇到了较多的麻烦。

但是经过这次对赫夫曼树的学习后，我了解到赫夫曼编码（HuffmanCoding）是一种编码方式，以赫夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据的无损耗压缩。

总之受益匪浅。

参考文献

【1】《数据结构》严蔚敏.清华大学出版社.

【2】《数据结构课程设计》苏仕华.极械工业出版社.

【3】《程序设计》谭浩强.清华大学出版社.

附录

#include<

stdio.h>

#include<

string.h>

#definen100//叶子结点数

#definem2*n-1//赫夫曼树种的结点总数

typedefstruct{charch;

charbits[9];

//存放编码位串

intlen;

//编码长度

typedefCodeNodeHuffmanCode[n+1];

typedefstruct{

intweight;

//权值

//左右孩子及双亲指针

//树中的结点类型

//0号单元不可用

intnum;

//字母类型的个数

{//在HT[1……k]中选择parent为0且权值最小的两个根结点，其序号分别为

S1和S2

for（p=s;

voidChuffmanTree（HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[]）

//在HT[1……i-1]中选择parent为0且权值最小的两个根结点，其序号分别为s1和s2

HT[s1].parent=i;

voidHuffmanEncoding（HuffmanTreeHT,HuffmanCodeHC）

{//根据赫夫曼树HT求赫夫曼编码表HC

intc,p,i,j;

//c和p分别指示T中孩子和双亲的位置

charcd[n];

//临时存放编码串

//指示编码在cd中的起始位置cd[num]='

//最后一位放上串结束符for（i=1;

//初始位置

//从叶子节点T[i]开始上溯while（（p=HT[c].parent）>

0）//直至上溯到HT[c]是树根为止

{//若T[c]是T[p]的做孩子，则生成0；

否则生成代码1

cd[--start]=（HT[p].lchild==c）?

//cd 数组用来存放每一个字母对应的01编码，

}//while 结束

strcpy（HC[i].bits,&

//将cd数组中德01代码复制到i结点中

HC[i].len=num-start;

}//for 结束

voidcoding（HuffmanCodeHC,char*str）

fp=fopen（"

codefile.txt"

"

w"

）;

while（*str）{for（i=1;

i++）if（HC[i].ch==*str）{

for（j=0;

HC[i].len;

j++）{

fputc（HC[i].bits[j],fp）;

str++;

char*decode（HuffmanCodeHC）

{//代码文件coodfile.txt的译码*菡枫*FILE*fp;

charstr[254];

//假设原文本文件不超过254个字符

staticcharcd[n+1];

inti,j,k=0,cjs;

r"

//读文件

while（!

{cjs=0;

num&

cjs==0&

!

cd[i]='

j++）

if（strcmp（HC[j].bits,cd）==0）// 查找所有的字母的对应的编码，如果有相同的则将该字母放入str中

k++;

cjs=1;

p=str;

voidmain（）{

charst[254],*s,str[27];

intcn[27];

HuffmanTreeHT;

HuffmanCodeHC;

输入需要编码的字符串（假设均为大写字母）:

\n"

gets（st）;

num=jsq（st,cn,str）;

//统计字符的种类及各类字符出现的频率ChuffmanTree（HT,HC,cn,str）;

//建立赫夫曼树HuffmanEncoding（HT,HC）;

//生成赫夫曼编码coding（HC,st）;

//建立电文赫夫曼编码文件

s=decode（HC）;

//读编码文件译码printf（"

译码后的字符串:

printf（"

%s\n"

s）;