《数据结构与算法》

实验报告

实验名称      哈夫曼树实现      

学    院  信息与通信工程学院      

年级专业 20级智能科学与技术      

姓    名   孙成                  

学    号   20203101694            

指导教师   冯思玲                

开 课 时 间2020 至 2021 学年第  二  学期

实验报告正文

实验目的

使用C语言实现哈夫曼树

实验内容及要求

1、问题描述

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。构造哈夫曼树时，首先将由n个字符形成的n个叶子结点存放到数组HuffNode的前n个分量中，然后根据哈夫曼方法的基本思想，不断将两个较小的子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HuffNode数组中的前n个分量的后面。通俗的来讲，哈弗曼树就是一种广泛应用的二叉树，哈弗曼树可以用来构造最优编码，用于信息的传输，压缩等方面哈弗曼树也可以理解为，最小二叉树，最优二叉树。

2、主要数据类型与变量

struct BTreeNode  

{  

   ElemType data;  

   struct BTreeNode* left;  

   struct BTreeNode* right;  

};  

3、算法或程序模块

3、求哈夫曼树的带权路径长度  

ElemType WeightPathLength(struct BTreeNode* FBT, int len)//len初始为0  

{  

   if (FBT == NULL) //空树返回0  

       return 0;  

   else  

   {  

       if (FBT->left == NULL && FBT->right == NULL)//访问到叶子结点  

           return FBT->data * len;  

       else //访问到非叶子结点，进行递归调用，返回左右子树的带权路径长度之和，len递增  

           return WeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);  

   }  

}  

 

//4、哈夫曼编码（可以根据哈夫曼树带权路径长度的算法基础上进行修改）  

void HuffManCoding(struct BTreeNode* FBT, int len)//len初始值为0  

{  

   static int a[10];//定义静态数组a，保存每个叶子的编码，数组长度至少是树深度减一  

   if (FBT != NULL)//访问到叶子结点时输出其保存在数组a中的0和1序列编码  

   {  

       if (FBT->left == NULL && FBT->right == NULL)  

       {  

           int i;  

           printf("结点权值为%d的编码：", FBT->data);  

           for (i = 0; i < len; i++)  

               printf("%d", a[i]);  

           printf("\n");  

       }  

       else//访问到非叶子结点时分别向左右子树递归调用，并把分支上的0、1编码保存到数组a  

       {   //的对应元素中，向下深入一层时len值增1  

           a[len] = 0;  

           HuffManCoding(FBT->left, len + 1);  

           a[len] = 1;  

           HuffManCoding(FBT->right, len + 1);  

       }  

   }  

}  

测试

方案

从键盘输入待构造的哈夫曼树中带权叶子结点数n：6

从键盘输入6个整数作为权值：3 9 5 12 6 15

结果

总结与讨论

通过不断地调试，实现了最终的稳定运行结果

附：程序源代码

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. typedef int ElemType;  
4. struct BTreeNode  
5. {  
6.    ElemType data;  
7.    struct BTreeNode* left;  
8.    struct BTreeNode* right;  
9. };  
10.  
11. //1、输出二叉树，可在前序遍历的基础上修改。采用广义表格式，元素类型为int  
12. void PrintBTree_int(struct BTreeNode* BT)  
13. {  
14.    if (BT != NULL)  
15.    {  
16.        printf("%d", BT->data); //输出根结点的值  
17.        if (BT->left != NULL || BT->right != NULL)  
18.        {  
19.            printf("(");  
20.            PrintBTree_int(BT->left); //输出左子树  
21.            if (BT->right != NULL)  
22.                printf(",");  
23.            PrintBTree_int(BT->right); //输出右子树  
24.            printf(")");  
25.        }  
26.    }  
27. }  
28.  
29. //2、根据数组 a 中 n 个权值建立一棵哈夫曼树，返回树根指针  
30. struct BTreeNode* CreateHuffman(ElemType a[], int n)  
31. {  
32.    int i, j;  
33.    struct BTreeNode **b, *q;  
34.    b = malloc(n*sizeof(struct BTreeNode));  
35.    for (i = 0; i < n; i++) //初始化b指针数组，使每个指针元素指向a数组中对应的元素结点  
36.    {  
37.        b[i] = malloc(sizeof(struct BTreeNode));  
38.        b[i]->data = a[i];  
39.        b[i]->left = b[i]->right = NULL;  
40.    }  
41.    for (i = 1; i < n; i++)//进行 n-1 次循环建立哈夫曼树  
42.    {  
43.        //k1表示森林中具有最小权值的树根结点的下标，k2为次最小的下标  
44.        int k1 = -1, k2;  
45.        for (j = 0; j < n; j++)//让k1初始指向森林中第一棵树，k2指向第二棵  
46.        {  
47.            if (b[j] != NULL && k1 == -1)  
48.            {  
49.                k1 = j;  
50.                continue;  
51.            }  
52.            if (b[j] != NULL)  
53.            {  
54.                k2 = j;  
55.                break;  
56.            }  
57.        }  
58.        for (j = k2; j < n; j++)//从当前森林中求出最小权值树和次最小  
59.        {  
60.            if (b[j] != NULL)  
61.            {  
62.                if (b[j]->data < b[k1]->data)  
63.                {  
64.                    k2 = k1;  
65.                    k1 = j;  
66.                }  
67.                else if (b[j]->data < b[k2]->data)  
68.                    k2 = j;  
69.            }  
70.        }  
71.        //由最小权值树和次最小权值树建立一棵新树，q指向树根结点  
72.        q = malloc(sizeof(struct BTreeNode));  
73.        q->data = b[k1]->data + b[k2]->data;  
74.        q->left = b[k1];  
75.        q->right = b[k2];  
76.  
77.        b[k1] = q;//将指向新树的指针赋给b指针数组中k1位置  
78.        b[k2] = NULL;//k2位置为空  
79.    }  
80.    free(b); //删除动态建立的数组b  
81.    return q; //返回整个哈夫曼树的树根指针  
82. }  
83.  
84. //3、求哈夫曼树的带权路径长度  
85. ElemType WeightPathLength(struct BTreeNode* FBT, int len)//len初始为0  
86. {  
87.    if (FBT == NULL) //空树返回0  
88.        return 0;  
89.    else  
90.    {  
91.        if (FBT->left == NULL && FBT->right == NULL)//访问到叶子结点  
92.            return FBT->data * len;  
93.        else //访问到非叶子结点，进行递归调用，返回左右子树的带权路径长度之和，len递增  
94.            return WeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);  
95.    }  
96. }  
97.  
98. //4、哈夫曼编码（可以根据哈夫曼树带权路径长度的算法基础上进行修改）  
99. void HuffManCoding(struct BTreeNode* FBT, int len)//len初始值为0  
100. {  
101.    static int a[10];//定义静态数组a，保存每个叶子的编码，数组长度至少是树深度减一  
102.    if (FBT != NULL)//访问到叶子结点时输出其保存在数组a中的0和1序列编码  
103.    {  
104.        if (FBT->left == NULL && FBT->right == NULL)  
105.        {  
106.            int i;  
107.            printf("结点权值为%d的编码：", FBT->data);  
108.            for (i = 0; i < len; i++)  
109.                printf("%d", a[i]);  
110.            printf("\n");  
111.        }  
112.        else//访问到非叶子结点时分别向左右子树递归调用，并把分支上的0、1编码保存到数组a  
113.        {   //的对应元素中，向下深入一层时len值增1  
114.            a[len] = 0;  
115.            HuffManCoding(FBT->left, len + 1);  
116.            a[len] = 1;  
117.            HuffManCoding(FBT->right, len + 1);  
118.        }  
119.    }  
120. }  
121.  
122. //主函数  
123. void main()  
124. {  
125.    int n, i;  
126.    ElemType* a;  
127.    struct BTreeNode* fbt;  
128.    printf("从键盘输入待构造的哈夫曼树中带权叶子结点数n：");  
129.    while(1)  
130.    {  
131.        scanf("%d", &n);  
132.        if (n > 1)  
133.            break;  
134.        else  
135.            printf("重输n值：");  
136.    }  
137.    a = malloc(n*sizeof(ElemType));  
138.    printf("从键盘输入%d个整数作为权值：", n);  
139.    for (i = 0; i < n; i++)  
140.        scanf(" %d", &a[i]);  
141.    fbt = CreateHuffman(a, n);  
142.    printf("广义表形式的哈夫曼树：");  
143.    PrintBTree_int(fbt);  
144.    printf("\n");  
145.    printf("哈夫曼树的带权路径长度：");  
146.    printf("%d\n", WeightPathLength(fbt, 0));  
147.    printf("树中每个叶子结点的哈夫曼编码：\n");  
148.    HuffManCoding(fbt, 0);  
149. }  
150.