课程设计哈夫曼编码编程实现.docx

课程设计哈夫曼编码编程实现.docx

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

课程设计哈夫曼编码编程实现

湖南科技学院

课程设计报告

课程名称：

数据结构课程设计

课程设计题目：

哈夫曼编码编程实现

系：

数学与计算科学系

专业：

信息与计算科学

年级、班：

姓名：

学号：

指导教师：

职称：

讲师

2011年12月

课程设计课题：

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本，试设计一个哈夫曼编码系统。

功能要求：

从键盘输入一段报文（如"whatdidyoudothatmadeyousohappy"）或从文档中读取，输出这段报文的哈夫曼编码。

课题分析：

由课题的要求，在编程中要实现字符统计、哈夫曼树的建立及该树的哈夫曼编码的读取。

这三者顺序进行。

实现思路

1、字符统计：

字符统计是为了计算出字符的频数，以之构成哈夫曼树叶子结点的权。

在实现中，本人采用一个链表表示字符的统计信息。

并把所有字符关联到一起。

这个链表在后面称为承载统计字符链表。

在链表中的结点是一个结构体。

structinformation_node

{

charch;

intfrequency;

structinformation_node*next;

}*head0;

其中ch用来记录相应的字符。

frequency用来记录字符出现的字符的频数，最后用来构成哈夫曼树叶子结点的权重。

以head0来指向该链表。

其中，本人在这个链表中的表头的结点，本人不用作统计字符的记录。

而以其表头结点的frequancy来记录该链表中字符和数。

便于后面的函数实现。

voidstatistics（）

{

charch;

while（（ch=cin.get（））!

='#'）//从输入流中断获取字符

if（!

find_record（ch））//如果在承载字符的链表中以有那个字符，就不记录。

退回调用函//数。

recording（ch）;//如果在承载字符的链表中没那个字符，就向那个链表插入一个结点//来记录那个字符。

else

count（ch）;//由于有该字符，向承载统计字符链表中就该字符结点的个数记录项加1.

}

2、构建哈夫曼树：

在构建哈夫曼树就用其构建的方法，即哈夫曼树中树从叶子结点开始建立。

每次由无父结点的结点中选出两个权重最小的两结点，把它们的权重之和来构建一个新结点的权重，并且用那两个结点要记录它们的父结点就是那个新结点。

再重复如上的操作，直到最后的树的建成。

而哈夫曼编码的读取，可用树的遍历的方法。

这里，本人用树的双亲表示法来表示树的结构。

创建了2*n-1哈夫曼树结点空间，给存储哈夫曼树结点的那个空间的前n个空间输入n个结点值，这n个结点是叶子结点（其中n是统计的不同字符各数）。

它们的相关数据来自承载统计字符链表中的相应数据，一个叶子结点，就要读取一个承载统计字符链表的一个结点的数据。

而剩余的空间用来存放其它的结点，因为一棵哈夫曼树如果有n个叶子结点，那么这棵树总共有2*n-1个结点。

叶子结点以输入，那就是存在如何构树的问题了，本人采用双亲表示法来表示树的结点。

在每个结点是一个结构体类型。

structhuffman_number_node

{

charch;

intdata;

intparent;

intleft_child;

intright_child;

}*head;

ch为字符。

data用来记录权重。

parent用来记录该结点的位置，如果其无父结点，其值为-1，left_child来记录其左子结点的位置，无左子树，就记录为0。

ritht_child用来记录右子结点的位置。

如果无右子结点就把它记录为0。

最后用head来指向那个存储空间。

这样就能很好的指把所有的结点关联起来，构成一棵树。

利用构成哈夫曼树的方法，来构成一棵哈夫树。

enter_huffman_values（n）;//哈夫曼树叶子结点的输入

creat_huffman_tree（number,n）;//创建哈夫曼树

3、从哈夫曼树中读哈夫曼编码：

本人采用从以叶子结点开始，来读哈夫曼码元。

读的方法是从叶子结点开始，然后就顺着叶子结点所记录的父结点。

访问其父结点。

在父结点中记录其是左子树，就向栈中输入码元0.否则是1.如此继续下去，直到访问到根结点。

这时，这个叶子结点的哈夫曼编码就可由前面读取码元的反向打印得来。

在前面读码元中，本人用一个栈来存放读到的0与1.这样栈的输出结果就是那上叶子结点的哈夫编码。

编程代码实现及详尽解释

main.cpp

#include

#include

#include

#include

#include

usingnamespacestd;

boolfind_record（charcha）;//找出已存入的字符

voidrecording（charch）;//插入新字符

voidparticular_recording（charch）;//判断字符是否在承载不同的字符的链表中出现与否。

voidstatistics（void）;//字符频数统计的入口函数。

voidinitialization_of_head（void）;//初始化一个以后用于字符输入的链表头结点,给它空间。

intenter_huffman_values（intn）;//哈夫曼树叶子结点的输入

voidcreat_huffman_tree（intnumber,intn）;//创建哈夫曼树

voidgo_further_read（structhuffman_number_node*pointer）;//从树中读相应字符的哈夫编码

voidreading_code（）;//打印相应字符的哈夫编码

voidread_huffman_code（void）;//读相应字符哈夫编码的入口函数

voidread_file（void）;//从文件中读取字符

voidview（void）;//用于是从文件中读取字符还是从键盘。

structinformation_node

{

charch;

intfrequency;

structinformation_node*next;

}*head0;

//这是一个用来构建统计字符链表结点类型的结构体。

其中ch用来记录相应的字符。

frequency用来记录字符出现的字符的频数，最后用来构成哈夫曼树叶子结点的权重。

structhuffman_number_node

{

charch;

intdata;

intparent;

intleft_child;

intright_child;

}*head

;//这个用来构建哈夫曼树结点的类型。

ch为字符。

data用来记录权重。

parent用来记//录该结点的位置，如果其无父结点，其值为-1，left_child来记录其左子结点的位置，无左子树，就记录为0。

ritht_child用来记录右子结点的位置。

如果无右子结点就把它记录为0。

structstack_data

{

intone_zeros;

};

structstack

{

structstack_data*base;

structstack_data*top;

}stack_operate;//建立一个栈来存放huffmancode

intmain（void）

{

initialization_of_head（）;//初始化承载不同字符及其频数的链表的表头结点。

view（）;

intn=head0->frequency;//把完成统计后，承载字符的链表中的总字符个数赋值给一个整//数n,用以做参数传递，完成后面函数的功能。

enter_huffman_values（n）;//该函数的主要功能性就是，创建要构建的树的所有的结点空间//并把叶子结点赋值。

creat_huffman_tree（n,n）;//在上函数完成叶子结点的输入的基础上创建哈夫曼树。

cout<

cout<

read_huffman_code（）;//把哈夫曼编码打印出来

cout<

system（"pause"）;

return0;

}

voidview（void）

{

cout<<"**************************************************"<

cout<<"1、fromthefilereadingcharacters"<

cout<<"2、fromthekeyboardreadingcharacters"<

cout<<"pleaseselectthecorrespondingoption."<

intselect_number;

cin>>select_number;

switch（select_number）

{

case1:

read_file（）;system（"cls"）;break;

case2:

statistics（）;system（"cls"）;break;

default:

exit（0）;

}

}

voidread_huffman_code（void）//打印哈夫曼编码

{

cout<<"displayhuffmancodeinfollowing"<

structhuffman_number_node*pointer1=head;//用pointer来访问哈夫曼树。

for（inti=0;ifrequency;i++）

//这个循环中访问存储空间中的前head0->frequency个叶子结点。

并输出各叶子结点的

ch数据项与huffmancode.

{

if（pointer1->ch!

=''&&pointer1->ch!

='\n'）

//由于字符中可能会出现空格与换行符，于它们的ch数据项的显示特殊化处理。

cout<ch<<'=';//如果，ch数据项不是空格与换行符，就直接打印。

else

{

if（pointer1->ch==''）//是空格符就用（ablandspace）来代替显示

{

cout<<"（ablandspace）"<<'=';

}

else

cout<<"（linefeed）"<<'=';//如果是换行符，就用（linefeed）来代替显示

}

go_further_read（pointer1）;//进入读取相就字符的huffmancode.

cout<<'\t'<<'\t';

pointer1++;

if（（i+1）%2==0）cout<

}

}

voidgo_further_read（structhuffman_number_node*pointer）

//这个函数中以叶子结点开始，来读哈夫曼码元。

读的方法是从叶子结点开始，然后就顺着叶子结点所记录的父结点。

访问其父结点。

在父结点中记录其是左子树，就向栈中输入码元0.否则是1.如此继续下去，直到访问到根结点

{

stack_operate.base=newstructstack_data[head0->frequency];

//创建一个栈来存储相就的哈夫曼编码

structhuffman_number_node*pointer1=pointer,*pointer2;

//辅助访问指针pointer1与pointer2

stack_operate.top=stack_operate.base;//初始化栈。

while（pointer1->parent!

=-1）

//由于输入结点数据时，根结点的parent项记录为-1,这是循环条件用来判断是否访问到根结点

{

pointer2=head+（pointer1->parent-1）;//pointer2指向pointer1的父结点。

if（（pointer1-head+1）==pointer2->left_child）//判断pointer1是父结点的左子结点还是右子结点。

{

stack_operate.top->one_zeros=0;//是左子结点就向栈中输入0

stack_operate.top++;

}

else

{

stack_operate.top->one_zeros=1;//是右子结点就向栈中输入1

stack_operate.top++;

}

pointer1=pointer2;

}

reading_code（）;//进入读栈函数

}

voidreading_code（）//用栈的读取方法读取码元就那个字符的哈夫曼编码。

{

structstack_data*pointer;

for（;stack_operate.top-stack_operate.base>0;stack_operate.top--）

{

pointer=stack_operate.top-1;

cout<one_zeros;

}

}

intenter_huffman_values（intn）

{

head=newstructhuffman_number_node[2*n-1];

//由于哈夫曼树中，有n个叶子结点，哈夫曼树就应有2*n-1个结点。

于是就创建2*n-1个空间来用于存放相应的结点数据并把该空间的地址给head.

structhuffman_number_node*pointer=head;

//创建一个同哈夫曼树结点同类型的指针，用来向那个空间输入相应的数据。

structinformation_node*pointer1=head0->next;

//创建一个访问承载统计字符链表的指针。

for（inti=0;i

//用循环来给存储哈夫曼树结点的那个空间的前n个空间输入n个结点值，这n个结点是叶子结点。

它们的相关数据来自承载统计字符链表中的相应数据，一个叶子结点，就要读取一个承载统计字符链表的一个结点的数据。

{

pointer->ch=pointer1->ch;

//这个叶子结点读取一个承载统计字符链表的一个结点的字符数据项。

pointer->data=pointer1->frequency;

//这个叶子结点继续读取承载统计字符链表那个结点的字符个数统计数据项。

pointer->parent=-1;

//由于还没有构成哈夫曼树，所以把该叶子结点的父结点的位置记为-1.父结点的位置指的是其父结点所在结点存储空间的位置，存储空间的第一个结点位置为1.

pointer->left_child=0;

//以0来表示，该结点没有左子结点。

如果有的话，就是其左子结点的存储空间位置。

pointer->right_child=0;//同上，只是这里是右子结点。

pointer++;

pointer1=pointer1->next;

}

for（inti=n;i<2*n-1;i++）//这个部分是把存储空间的其它没有存储数据的空间初始化。

{

pointer->ch='#';

pointer->parent=-1;

pointer->left_child=0;

pointer->right_child=0;

pointer++;

}

returnn;

}

boolfind_record（charcha）//找出已存入的字符

{

structinformation_node*pointer;

//创建一个同承载字符链表的结点同类型的指针，用于访问那个链表。

if（head0->frequency==0）returnfalse;

//如果还没那个链表中还没有字符的插入，就向调用函数返回没有这个字符的记录。

else

{

pointer=head0->next;

//如果链表中有字符，就用pointer来访问查找，把查找的开始位置告诉pointer.

for（inti=0;ifrequency;i++）

//这里就用到链表表头中的字符总数记录，来判断要访问多少个结点。

{

if（pointer->ch==cha）

//判断访问到的结点是不是有要查找的字符。

有就向调用函数回答是。

{

pointer->frequency+=1;//由于有该字符，就向该字符的个数记录项加1.

returntrue;

}

pointer=pointer->next;

}

returnfalse;//最后还是没找到就，向调用函数返回否。

}

}

voidrecording（charch）//插入新字符

{

structinformation_node*pointer=head0;

//创建一个与承载统计字符的链表的表头结点同类型的指针并指向那个头结点。

while（pointer->next!

=NULL）

//循环的方式来找到承载统计字符的链表的表尾结点。

用以插入一个新的结点，来存储新的结点。

pointer=pointer->next;

head0->frequency+=1;

//由于，插入在承载统计字符的链表中插入了一个新的结点，也就是有了一个新的字符，那就在其表结点的字符统计中加1.

pointer->next=newstructinformation_node;//创建新的结点，用以记录新的字符。

pointer->next->ch=ch;

pointer->next->frequency=1;//同时，记录这个字符的个数以有了一个。

pointer->next->next=NULL;//把这个表尾的结点的指针域赋为NULL，用于以后的判断。

}

voidparticular_recording（charch）//判断字符是否在承载不同的字符的链表中出现与否。

{

if（find_record（ch）==true）;

//如果在承载字符的链表中以有那个字符，就不记录。

退回调用函数。

else

recording（ch）;

//如果在承载字符的链表中没那个字符，就向那个链表插入一个结点来记录那个字符。

}

voidstatistics（）//字符频数统计的入口函数。

{

charch;

cout<<"ifyouwanttocomputestatisticaldataaboutthenumberofletters,pleaseenterlettersthenenter'#'endenter"<

while（（ch=cin.get（））!

='#'）//从输入流中断获取字符，直到碰到字符'#'为止。

particular_recording（ch）;//深入进入统计。

}

voidread_file（）//从文件中读取字符。

{

ifstreaminfile（"data.txt",ios:

:

in）;

if（!

infile）

{

cout<<"openerror!

";

exit（0）;

}

charch;

while（（ch=infile.get（））!

=EOF）

particular_recording（ch）;

infile.close（）;

}

voidinitialization_of_head（void）//初始化一个以后用于字符输入的链表头结点,给它空间。

{

head0=newstructinformation_node;

head0->ch='#';

head0->frequency=0;//这个是用于记录链表中字符的总个数，给该链表加入一个字符，它就加1.

head0->next=NULL;

}

voidcreat_huffman_tree（intnumber,intn）//构造哈夫曼树。

{

if（number<2*n-1）//判断录入数据树的结点是否小于2*n-1

{

intm;

structhuffman_number_node*pointer=head,*pointer1,*pointer2;

//创建的pointer用来访问树结点存储空间.pointer1,pointer2用于分别指向存储空间中结点的data数据项最小与次之的两个结点，并且这两个结点parent数据项无父结点记录的。

data是记录字符的权重，也就是由统计部分统计出的相应字符在输入的字符集中的频数。

intmin=0,sec=0,maximum;

//定义min用来指出pointer1指向的结点在存储空间的位置。

初始为0。

定义sec用来指出pointer2指向的结点在存储空间的位置。

初始为0。

申明maximun,是为的存min与sec中的最大的值。

while（（min==0||sec==0）&&（（pointer-head）

//这个循环中是为了找出前两个无父结点记录的结点，分别用pointer1与pointer2来指向。

其中pointer1指向data数据项是最小的那个结点。

这个循环的条件中,都要min与sec不为0。

也就是说要pointer1与pointer2都要有指向，前两个结点找出。

（pointer-head）

它们的数据项ch。

//不为'#'.

{

if（pointer->parent==-1&&min==0）

//如果第一次找到满足条件的结点。

就第一个用pointer1来指向，与min记录位置。

{

min=pointer-head+1;

pointer1=pointer;

}

else

{

if（pointer->parent==-1&&sec==0）//找到第二个满足条件的结点。

{

if（pointer1->data>pointer->data）

//如果这个结点的data数据项与第一个结点的data数据项要小，就用pointer1指向这个数据项，而pointer2指向第一个。

{

sec=min;

pointer2=pointer1;

pointer1=pointer;

min=pointer-head+1;

}

else//否则，就用pointer指向这个结点，同sec记录该结点的位置。

{

sec=pointer-head+1;

pointer2=pointer;

}

}

}

pointer++;

}

if（sec>min）

{

maximum=sec;

}

else

{

max