数据结构课程设计实验报告赫夫曼编码3464278.docx

数据结构课程设计实验报告赫夫曼编码3464278.docx

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

数据结构课程设计实验报告赫夫曼编码3464278

（此文档为word格式，下载后您可任意编辑修改！

）

+

南京信息工程大学

数据结构课程设计

题目：

赫夫曼编码

院、系：

滨江学院

学科专业：

计算机科学与技术

学生：

学号：

指导教师：

王鹤蒙

2010年12月22日

目录

1课程设计的题目-----0

2课程设计的目的（设计要解决的问题）

3概要设计（函数划分、总体设计）----1

4详细设计（算法、流程图、程序）-----2

5调试结果--

6课程设计总结-----33

7心得体会

二课程设计的目的

<1>巩固构造赫夫曼树的算法。

<2>设计实验用程序实现赫夫曼树的构造。

<3>熟悉用先序、中序或后序的访问方法得到个叶子结点的赫夫曼编码。

三概要设计（函数划分、总体设计）

<一>总体设计

（1）输入一个字符串用结构体链表存储字符串中出现的不同字符及其出现的次数。

（2）定义赫夫曼数的结点结构体，把不同的字符及其在字符串中出现的次数作为叶子结点的元素及其权值，统计叶子结点的个数n，开辟可以存储2*n个结点的顺序表，来赫夫曼树的各个结点，然后按照一定的规则构造赫夫曼树。

（3）开辟一个可以存储叶子结点元素及指向存储其赫夫曼编码链表的指针的顺序表，然后从叶子结点开始向上访问，是左孩子的把“0”接进链表是右孩子的把“1”接进链表，直到根结点，然后把叶子结点的元素及存储其赫夫曼链表的头指针读入顺序表，直到把所有的叶子结点的元素及指向存储其赫夫曼编码链表的头指针读入顺序表，这样得到的赫夫曼编码是倒序的。

（4）从存储其叶子结点及指向存储其赫夫曼编码链表头指针的顺序表表头开始顺序访问各元素，在输出其赫夫曼编码之前，把链表中的编码顺序读入到等长的栈中，然后编码出栈就会得到顺序的赫夫曼编码，直到把所有的叶子结点都访问到。

（5）用一个字符型的指针指向字符串的第一个字符，从存储叶子结点元素及指向存储其赫夫曼编码链表的头指针的顺序表表头开始访问顺序表中的各元素，直到找到叶子结点的元素和当前字符相等就结束访输出赫夫曼编码，回到表头，指针后移，直到输出字符串的最后一个字符的赫夫曼编码，这样就得到输入字符串的赫夫曼编码。

<二>函数划分

该程序有一个主函数和多个子函数，主函数完成对子函数的调用，各子函数实现相应的功能。

子函数：

（1）结点的开辟。

（2）实现对输入字符串中出现的不同字符及其出现字数的信息记录。

（3）用叶子结点构造赫夫曼树。

（4）获得构造的赫夫曼树中所有叶子结点的元素及其赫夫曼编码。

（5）输出各叶子结点元素及其对应的赫夫曼编码。

（6）输出输入的字符串的赫夫曼编码。

（7）调用各子函数

四详细设计（算法、流程图、程序）

<一>算法

<1>创建存储叶子结点元素及其权值的链表

定义结构体node，其数据成员包括，字符型的元素a和整型元素b和指向node的next指针，来存储叶子结点的内容和权值。

定义三个指向node的指针head、p1、p2和字符指针n、t、,p2->b=r,p1->next=p2,p1=p2,n++,t回到字符串首；否则i++（i为整型，初始值为1）r=0，j=1；让t指向字符串第一个元素，当*t！

=‘\0’，如果*t==*n，r++，t++；让h指向字符串的第一个元素，当h！

=n时如果*,p2->b=r,p1->next=p2,p1=p2

;n++,当把最后一个结点连入链表中，p1->next=NULL,然后把p1=（起标记作用）、和指向左、右孩子及父母结点的指针lchild、rchild和parent。

定义指向node1的指针p0、p1、p2、p3、p4和整型的m、n、i、j、k1、k2，n=0、p=++，p=p->next，开辟可以存储2*n个node1的顺序表，让p0指向表头，p1=p0,p=-1,j=0,当j<2，如果j==0把‘‘1’赋给k1；否则把‘1’赋给k2；p2=p0，当p2！

=p1时，如果p2->sign==NULL并且m=p2->weight用break结束循环否则p2++；p2=p0，当p2！

=p时，如果m>=p2->weight并且p2->sign==NULL,把p2->weight赋给m，否则p2++；把p0赋给p2，当p2不等于p1时，如果m等于p2->weight并且p2->sign等于NULL，把‘1’赋给p2->sign,如果j=0，把p2赋给p1->lchild,p2->weight赋给p1->weight,p1赋给p2->parent,用break结束循环；如果j==1，则把p2赋给p1->rchild,p1->weight加p2->weight赋给p1->weight,p1赋给p2->parent,用break结束循环；如果j等于0，k1++，p2++；如果j等于1，k2++，p2++；j++；如果k1大于k2把p1->lchild赋给p3，p1->rchild赋给p4，p4赋给p1->lchild,p3赋给p1->rchild,p1->sign=

NULL,p1++,i++;然后p--，把p1->parent=NULL,p1++,把p0赋给p2，当p2不等于p时输出p2的各数据项，拍p2++；返回p0。

<3>获得各叶子结点的赫夫曼编码

定义只存储赫夫曼编码的结构体code，它的数据项有字符型的a（存储‘0’、‘1’编码）以及指向下一个结点的指针next。

定义结构体huffmancode，它的数据项有字符型a（存储叶子结点元素）、指向结构体code的指针head。

设指向node1的指针p1、p2、p4，指向huffmancode的指针l、l1和指向code的指针h、++，（n为整型，初始化为零），p2++；调用malloc函数开辟可以存储n+1个huffmancode结点的顺序表，让l指向该顺序表的表头，把l赋给l1，把p赋给p4，当p4->lchild和p4->rchild同时为NULL把p4赋给p1调用setcode（）函数开辟一个结点让h1指向该结点，把h1赋给l1->，p->++，+1个字符的栈，让base指向栈底，top=base,把h=p->（n为整型）p1=p0（p0为形参）当p1->a!

=NULL时，如果p1->a等于*p把p1->+1个字符的栈底，top=base，把p1->，如果n等于1，p=p->next,输出p->a和p->b,否则，以p为实参调用settree（p），将返回值赋给p1，以p1为实参调用gethuffmamcode（p1）函数，将返回值赋给p2（p2为指向huffmancode的指针），以p2为实参调用printhuffmancode（p1）函数，然后以a，p2为实参调用print（a，p2）函数。

coutdata（）函数的算法：

设指向node的指针p，把head->next赋给p，当p！

=NULL时n++，p=p->next;返回n。

<7>主函数

调用control（）函数。

<二>流程图

创建存储叶子结点元素及其权值的链表

开辟一个新的结点，让head指向它

p1=head

n=a

*n！

=‘\0’

n=

是

=a?

否

开辟新的结点，让p1指向它

i++

r=0

t=n

j=1

*t！

=‘\0’

t=a

*t=

是

=‘\0’？

否

*t！

=‘\0’

*t==*n

是

？

否

r++

r++

t++

t++

p2->a=*n

h=a

p2->b=r

p1->next=p2

*h==

是

*n？

否

p1=p2

n++

break

j++

h++

i==j？

是

否

开辟新结点，让p2指向它

p2->a=*n

p2->b=r

p1->next=p2

p1=p2

p1->next=NULL

p1=head->next

p1!

=NULL

输出p1->a

输出p1->a

返回head

setnode函数

开辟一个node结点，让p指向它

返回p

构造赫夫曼树

p=head->next

p！

=NULL

n++

p=p->next

p0=（listnode1）malloc（2*n*sizeof（node1））

p1=p0

p=head->next

p！

=NULL

p1->a=p->a

p1->weight=p->b

p1->lchildp1->rchildp1->parentp1->sign全置空

p1++

i=1

i<=n-1

j=0

j<2

是

j==0?

否

k1=1

k2=1

p2=p0

p2!

=p1

是

P2->sign==NULL?

否

m=p2->weight

p2++

break

p2=p0

p2!

=p1

m>=p2->weight

是

并且p2->sign==NULL?

否

m=p2->weight

p2++

p2=p0

p2!

=p1

m==p2->weight

是

并且p2->sign==NULL?

否

j==0?

是

p2->signj==0?

==1?

是

否

p1->lchild=p2p1->rchild=p2

p1->weightp1->weight+=k1++

=p2->weightp2-weight

k2++

p2->parentp2->parent

=p1

=p1

break

p2++

j++

k1>k2

是

?

否

p3=p1->lchild

p4=p1->rchild

p1->lchild=p4

p1->rchild=p3

p1->sign=NULL

p1++

i++

p1--

p1->parent=NULL

p1++

p2=p0

p2!

=p1

输出p2->ap2->weight

p2->lchildp2->parentp2->rchild

p2++

返回p0

<3>获得各叶子结点的赫夫曼编码

p2=p

p2=lchild==NULL&&p2->rchild==NULL

n++

p2++

l=（listhuffmancode）malloc（（n+1）*sizeof（huffmancode））

p4=p

p4->lchild==NULL&&p4->rchild==NULL

p1=p4

h1=setcode（）

l1->head=h1

P1->parent！

=NULL

是

p1=p1->parent->lchild?

否

开辟一个结点让h指向它

h->a=‘\0’

h1->next=h

h1=h

h->a=‘\0’

h1->next=h

h1=h

h1->next=NULL

l1->a=p4->a

l1++

l1->a=NULL

返回l

setcode函数

开辟一个code结点，让p指向该结点

返回p

<4>输出各叶子结点的赫夫曼编码

p=head1

p->a!

=NULL

h=h->head->next

h!

=NULL

n++

h=h->next

base=（char*）malloc（（n+1）*sizeof（char））

h=h->head->next

h!

=NULL

*top=h->a

top++

h=h->next

top--

top!

=base

输出*top

top--

输出*top

<5>输出字符串的赫夫曼编码

p2=p

*p2!

=‘\0’

*p2

p2++

*p!

=‘\0’

n=0

p1=p0

p1->a!

=NULL

p1->a==*p?

是

否

h=p1->head->next

p1++

h!

=NULL

n++

h=h->next

base=（char*）malloc（（n+1）*sizeof（char））

top=base

h=p1->head->next

h!

=NULL

*top=h->a

top++

h=h->next

--top

top!

=base

输出*top

break

p++

<6>control函数

输入a

p=getdata（a）

n=coutdata（p）

是

n==1?

否

p=p->next

p1=settree（p）

输出p->a和p->b

p2=gethuffmancode（p1）

printhuffmancode（p2）

print（a,p2）

countdata（）函数

p=head-next

p!

=NULL

n++

p=p->next

返回n

<7>主函数

调用control（）函数

程序的编译环境是Visualstudio2010

把统计叶子结点元素和权值的函数放在“计算权值.p;

}

listnodegetdata（char*a）*统计输入字符串中的不同字符及其出现的次数的函并且把统计出的数据，作为叶子结点的元素和权值*

{

listnode,*t,*=a;*n!

='\0';n++）

{

if（n==a）

{

p2=setnode（）;

for（t=n;*t!

='\0';t++）统计相同的字符在字符串中出现的次数

if（*t==*n）

r++;

p2->a=*n;

p2->b=r;

p1->next=p2;

p1=p2;

}

else

{

i++;

r=0;

j=1;

for（t=a;*t!

='\0';t++）

if（*t==*n）

r++;

for（;）

break;

else

j++;

}

if（i==j）

{

p2=setnode（）;调用setnode（）函数开辟结点

p2->a=*n;

p2->b=r;

p1->next=p2;

p1=p2;

}

}

}

p1->next=NULL;

cout<<"电文的长度为：

"<

cout<<""<

p1==0;

for（p=++;

returnn;

}

把构造赫夫曼树的函数放在头文件“构造赫夫曼树.;结点的权值和结点的标记

structnode1*parent,*lchild,*rchild;指向父母结点和左、右孩子的指针

}*listnode1;指向node1的指针

listnode1settree（listnode,i,j,k1,k2;

structnode1*p3,*p4;

n=0;

for（p=++;

p0=（listnode1）malloc（2*n*sizeof（node1））;开辟可以存储2n个赫夫曼树结点的顺序表

p1=p0;

for（p==NULL;

p1++;

}

for（i=1;i<=n-1;i++）

{

for（j=0;j<2;j++）

{

if（j==0）

k1=1;

elseif（j==1）k2=1;

for（p2=p0;p2!

=p1;p2++）

if（p2->sign==NULL）

{

m=p2->weight;

break;

}

for（p2=p0;p2!

=p1;p2++）

if（m>=p2->weight）

if（p2->sign==NULL）

m=p2->weight;

for（p2=p0;p2!

=p1;p2++）

{

if（m==p2->weight）

if（p2->sign==NULL）

{

p2->sign=1;

if（j==0）把先找到的权值最小的作为左孩子

{

p1->lchild=p2;

p1->weight=p2->weight;

p2->parent=p1;

}

elseif（j==1）把后找到的权值最小的最为右孩子

{

p1->rchild=p2;

p1->weight=p1->weight+p2->weight;

p2->parent=p1;

}

break;

}

if（j==0）

k1++;标记先找到的权值最小的结点在顺序表中的位置

elseif（j==1）

k2++;标记后找到的权值最小的结点在顺序表中的位置

}

}

if（k1>k2）*如果先找到的权值最小的结点在顺序表中的位置在后找到的后面

{则他们父母结点的左右孩子指针交换*

p3=p1->lchild;

p4=p1->rchild;

p1->lchild=p4;

p1->rchild=p3;

}

p1->sign=NULL;

p1++;

}

p1--;

p1->parent=NULL;

p1++;

p2=p0;

cout<<"叶子结点"<<"\t"<<"权值"<<"\t"<<"左孩子"<<"\t\t"<<"父母结点"<<"\t"<<"右孩子"<

while（p2!

=p1）

{

cout<a<<"\t\t"<weight<<"\t"<lchild<<"\t"<parent<<"\t"<rchild<

p2++;

}

cout<<""<

returnp0;

}

把叶子结点赫夫曼编码的获取的函数放在头文件“获得赫夫曼编码.p;

}

listhuffmancodegethuffmancode（listnode1p）把得到的叶子结点及其{赫夫曼编码存到顺序表中的函数

listnode1p1,p2,p4;

intn=0;

listhuffmancodel,l1;

listcode++;

l=（listhuffmancode）malloc（（n+1）*sizeof（+1个叶子结点信息的顺序表

l1=l;

for（p4=p;p4->lchild==NULL&&p4->rchild==NULL;p4++）

{

p1=p4;

l;

}

把输出赫夫曼编码的函数放在头文件““输出赫夫曼编码.;

char*base,*top;

cout<<"叶子结点"<<"\t"<<"权值"<

for（p==0;

++;

base=（char*）malloc（（n+1）*sizeof（char））;

top=base;

;

char*base,*top,*p2;

cout<<"电文内容：

";

for（p2=p;*p2!

='\0';p2++）

cout<<*p2;

cout<

cout<<"电文的赫夫曼编码：

";

for（;*p!

='\0';p++）

{

n=0;

for（p1=p0;p1->a!

=NULL;p1++）

if（p1->a==*p）

{

++;

base=（char*）malloc（（n+1）*sizeof（char））;

top=base;

;

cout<<"接受到的电文内容（不超过20个字符）：

";

cin>>a;

listnodep;

p=getdata（a）;

n=coutdata（p）;

if（n==1）如果只有一个叶子结点，说明该叶子结点就是根结点，无法构造赫夫曼树

{

p=p->next;

cout<<"该树只有一个叶子结点即根结点（根结点没有赫夫曼编码）>>"<

cout<<"根结点"<<"\t\t"<<"权值"<

cout<a<<"\t\t"<b<

cout<<""<

}

else

{

listnode1p1;

p1=settree（p）;

listhuffmancodep2;

p2=gethuffmancode（p1）;

printhuffmancode（p2）;

print（a,p2）;

}

cout<

}

主函数放在源文件“赫夫曼编码.cpp“中

#include

#include"控制函数.（）

{

control（）;调用control函数

}

五调试结果

六课程设计总结

本次课程设计的目的是：

把一个随机输入的字符串中不同字符作为叶子结点元素，把其在该字符串中出现的次数作为权值构造一个赫夫曼树，并得到各个叶子结点的赫夫曼编码和整个输入的字符串的赫夫曼编码。

在写代码前，首先，对问题进行了分析，明确了目标，列出了大的框架，然后逐渐细化，划分出不同的功能模块，由具体的子函数去实现，先在纸上编写代码，写好后进行了反复的逻辑推理，发现并解决逻辑问题，然后，上机调试，方法是：

一个一个功能模块分开进行调试，主要看调试的模块能否达到预期的结果，这样可以缩小排错的范围，便以纠错和提高编程的效率，当每个功能模块都调试好后，就把各个部分组合起来，再进行调试，主要检查各函数接口是否正确，当达到预期的结果，调试结束，编程部分完成，然后按实验要求完成实验报告。

由于写代码前做了充分的准备工作，所以写起代码来比较顺利，使编程的效率有不少的提高并且最终达到实验预期的结果。

七心得体会

每一次的课程设计对我来说都是一个不小的提高，哲学上说：

“实践是检验真理正确性的唯一标准”，尤其是学编程，自己不动手操作，只看书永远都编不出像Windows之类的东西，正如老师说的那样，课程设计非常锻炼人，每完成一个项目，不仅是知识体系的完善和知识的验证，更是编程技术的提升，当自己编的多了，就会开始摸索编程的捷径，想着用更高效的方法去完成一个个项目，就这样在一次次的锻炼中自己会从一个菜鸟迅速的成长，终将成为一个优秀的软件工程师。

一个成功的项目必须在写代码前，先要对课题有充分的思考和规划，否则即使完成了项目也会浪费很多的时间和精力，我认为科学合理的编程方法是我这次课程设计的最大收获。