数据结构论文

数据结构论文

目录

一、题目：实验题7.6 ..................................................................................................................... 2 二、实验原理： ............................................................................................................................... 2

2.1赫夫曼树的构造: ................................................................................................................ 2

2.1.1哈夫曼树的算法 ...................................................................................................... 3 2.2哈夫曼编码:........................................................................................................................ 3

2.2.1哈夫曼编码的算法 .................................................................................................. 4

三、设计思想 ................................................................................................................................... 5

3.1概述 ..................................................................................................................................... 5 3.2思路 ..................................................................................................................................... 6 3.3程序流程图 ......................................................................................................................... 7 四、 实现算法如下： ..................................................................................................................... 9

4.1定义存储结构和类型 ........................................................................................................ 9 4.2哈夫曼树生成函数 ............................................................................................................ 9 4.3哈夫曼编码函数 .............................................................................................................. 10 4.4哈夫曼译码函数 .............................................................................................................. 10 4.5主函数 .............................................................................................................................. 11 4.6仿真过程及结果 .............................................................................................................. 11 五、实验总结 ................................................................................................................................. 12

一、题目：实验题7.6

设计一个程序exp7-6.cpp，构造一棵哈夫曼树，输出对应的哈夫曼编码和平均长度。并用下表所示的数据进行验证。

表7.8 单词及出现的频度

单词 出现频度 he 195 The 1192 is 190 of 677 at 181 a 541 on 174 to 518 for 157 and 462 His 138 in 450 are 124 that 242 be 123

任务：首先要构造一个哈夫曼树，然后进行哈夫曼编码 要求：可以建立函数输入二叉树，实现赫夫曼树的编码和译码系统，重复地显示并处理编码/解码功能，直到选择退出为止。

二、实验原理：

2.1赫夫曼树的构造:

假设有n个权值，则构造出的赫夫曼树有n个叶子结点。n个权值分别为w1,w2,………wn,则赫夫曼树构造规则为： <1>将w1,w2,…….wn,看成有n棵树的森林。

<2>在森林中选出两个根结点最小的树合并，作为一棵新树的左右子书，且新树根结点权值为左右子树根结点权值之和。 <3>从森林中删除选取的两棵树，并将新树加入森林。 <4>重复2和3步骤，直到森林中只剩一棵树为止。 现举例如下：

7 5 2 4 18 11 6 7 11 7 5 7 5 6 5 2 4 2 4 2 4

2.1.1哈夫曼树的算法

void CreateHT(HTNode ht[],int n) //调用输入的数组ht[],和节点数n {

int i,k,lnode,rnode; int min1,min2;

for (i=0;i<2*n-1;i++)

ht[i].parent=ht[i].lchild=ht[i].rchild=-1; //所有结点的相关域置初值-1 for (i=n;i<2*n-1;i++) //构造哈夫曼树 {

min1=min2=32767; //int的范围是-32768—32767

lnode=rnode=-1; //lnode和rnode记录最小权值的两个结点位置 for (k=0;k<=i-1;k++) { if (ht[k].parent==-1) //只在尚未构造二叉树的结点中查找 {

if (ht[k].weight

min2=min1;rnode=lnode; min1=ht[k].weight;lnode=k; }

else if (ht[k].weight

min2=ht[k].weight;rnode=k; } } }

ht[lnode].parent=i;ht[rnode].parent=i; //两个最小节点的父节点是i ht[i].weight=ht[lnode].weight+ht[rnode].weight; //两个最小节点的父节点权值为两个最小节点权值之和

ht[i].lchild=lnode;ht[i].rchild=rnode; //父节点的左节点和右节点 } }

2.2哈夫曼编码:

构造方法如下：

设需要编码的字符集合为{d1，d2,.....，dn}各个字符在电文中出现的次数集合为{w1，w2，.......，wn}，以d1，d2，.........，dn作为叶子节点，以w1，w2，........，wn作为各个叶子节点的权值构造一颗哈夫曼树，规定哈夫曼树中的左分支为0，右分支为1，则从根节点到每个叶子节点所经过的分支对应的0和1组成的序列便为该节点对应字符的编码，即哈夫曼编码。 2.2.1哈夫曼编码的算法

void CreateHCode(HTNode ht[],HCode hcd[],int n) {

int i,f,c; HCode hc;

for (i=0;i

hc.start=n;c=i; f=ht[i].parent;

while (f!=-1) //循序直到树根结点结束循环 {

if (ht[f].lchild==c) //处理左孩子结点 hc.cd[hc.start--]='0';

else //处理右孩子结点 hc.cd[hc.start--]='1'; c=f;f=ht[f].parent; }

hc.start++; //start指向哈夫曼编码hc.cd[]中最开始字符 hcd[i]=hc; } }

void DispHCode(HTNode ht[],HCode hcd[],int n) //输出哈夫曼编码的列表 {

int i,k;

printf(\ 输出哈夫曼编码:\\n\

for (i=0;i

for (k=hcd[i].start;k<=n;k++) //输出所有data中数据的编码 {