《数据结构》课程中哈夫曼编码教学案例研究
2020-11-10王彩霞
王彩霞
摘 要：哈夫曼编码是《数据结构》课程中二叉树的一个重要应用，也是该课程的重点和难点。文章对哈夫曼编码的课堂教学进行了介绍，在课程中，利用树的二叉链表结构及哈夫曼树的特点设计出了另一种哈夫曼编码方法，并给出算法设计方法及描述，同时与传统编码方法做比较分析。教学实践表明，学生对哈夫曼编码原理的理解及编码程序设计方法的掌握得到了显著提高。
关键词：教学案例;数据结构;哈夫曼编码
中图分类号：G642 文献标志码：A 文章编号：2096-000X（2020）31-0104-03
Abstract： Huffman coding is an important application of binary trees in the "Data Structure" course， and it is also the focus and difficulty of the course. This article introduces the classroom teaching of Huffman coding. In the course， another Huffman coding method is designed using the binary linked list structure of the tree and the characteristics of the Huffman tree， the algorithm design method and description are given， and at the same time， it is compared and analyzed with traditional coding methods. Teaching practice shows that students' understanding of Huffman coding principles and mastery of coding programming methods have been significantly improved.
Keywords： teaching case; data structure; Huffman coding
引言
《数据结构》[1]是一门典型的将理论转换为实践的计算机课程，在应用数学专业的课程体系中起着非常重要作用。如果学生在学习理论知识的过程中，能够持续运用不同的已学知识解决相同的问题[2]，举一反三，改造创新，那么理论和实践能力都能得到发展提高。在文中，笔者利用已学的一维数组及树的二叉链表结构，在传统哈夫曼编码方法基础上，给出了另一种哈夫曼树编码方法。教学结果显示，学生学习效率得到了大大提高，同時还激发了学生的上机编程热情。
一、数据结构设计
哈夫曼树采用二叉链表结构，每个结点包含指向左右孩子结点的指针，还包括用于存放该结点所在分支编码的域。n个叶子结点存放在一维数组中，每个数组元素包括两个域，一个存放叶子结点权值，一个是指向哈夫曼树叶子结点的指针。定义如下：
typedef struct Node{//哈夫曼树结点结构
char bit[MB];// MB为哈夫曼编码串最大长度
struct Node *lchild，*rchild;
} HuffmanTreeNode;
typedef struct{
int weight;
struct Node *Leaf;
} TreeLeaf;
TreeLeaf LeafNode[n];//叶子结点数组
二、哈夫曼树的构造设计
构造哈夫曼树前，先对n个叶子结点权值按升序排序，构造二叉树时避免多次循环查找最小和次小权值，只需从前往后依次取权值即可。
（一）算法思想
定义TreeLeaf结构的辅助数组NLNode[n-1]，构造哈夫曼树时生成的中间结点，按照生成的先后顺序依次加入到数组NLNode[n-1]中，则数组中的中间结点权值肯定是从小到大有序的。数组中Leaf域存放新生成的二叉树的根结点地址。用K统计数组NLNode[n-1]中插入结点的个数。算法描述如下：
1. 初始化数组NLNode，weight域置为MAX（MAX大于n个叶子结点权值之和），Leaf置为NULL。
2. 根据数组LeafNode中的n个权值，生成n棵只有叶子结点的二叉树，每个结点的bit域置“0”，二叉树根结点地址存放在与其权值相对应的Leaf域。
3. 置i=0，j=0，K=0，做以下操作：
（1）LeafNode[i].weight与NLNode[j].weight中取较小者赋给s1，Leaf域值赋给p1，并将其对应的数组下标增1。
（2）LeafNode[i].weight与NLNode[j]. weight中取较小者赋给s2，Leaf域值赋给p2，并将其对应的数组下标增1，p2所指结点的bit域置“1”。
（3）以p1，p2所指结点为左右子树构造一棵新的二叉树，根结点的权值为s1+s2，bit域置“0”。将新生成的二叉树根结点加入到数组NLNode中，K增1。
（4）当K 4. 当数组NLNode满时，哈夫曼树构造结束。 例如排好序的权值集W={2，3，4，4，6}，构造哈夫曼树过程如图1所示，根结点bit域值为“#”，不参与编码。 （a） （b） （c） （d） （e） 图1 哈夫曼树构造过程 （二）算法C语言[3]实现 void huffmantree（TreeLeaf *LeafNode，TreeLeaf *NLNode） { HuffmanTreeNode *p; int i; for（i=0;i NLNode[i].weight=MAX; NLNode[i].Leaf=NULL; } for（i=0;i p=（HuffmanTreeNode*）malloc（sizeof（Huffm anTreeNode））; if（！p） return; p->weight=LeafNode[i].weight; strcpy（p->bit，"0"）; p->lchild=p->rchild=NULL; LeafNode[i].Leaf=p; } int j=0，K=0，s1，s2;//s1，s2存放最小和次小权值 HuffmanTreeNode *p1，*p2; i=0; while（K if（i s1=LeafNode[i].weight; p1=LeafNode[i].Leaf; i++; } else{ s1=NLNode[j].weight; p1=NLNode[j].Leaf; j++; } if（i s2=LeafNode[i].weight; p2=LeafNode[i].Leaf; i++; } else{ s2=NLNode[j].weight; p2=NLNode[j].Leaf; j++; } strcpy（p2->bit，"1"）; p=（HuffmanTreeNode *）malloc（sizeof（Huf fmanTreeNode））; p->weight=NLNode[k].weight=s1+s2; strcpy（p->bit，"0"）; p->lchild=p1; p->rchild=p2; NLNode[k].Leaf=p;K++; } K--; strcpy（NLNode[K].Leaf->bit，"#"）;//樹的根结点不参与编码 return; } 三、哈夫曼编码设计 （一）算法思想 在数组NLNode中从后往前依次取除根结点外的所有中间结点的地址，对哈夫曼树从第二层起向下扫描各中间结点，求出叶子结点的哈夫曼编码。算法叙述如下： 1. 置j=n-3，取p= NLNode[j].Leaf。 2. 将p所指结点的bit域值加到p所指结点的左孩子及右孩子bit域值的前面，j减1。 3. 重复2.直到数组NLNode中所有中间结点执行完为止。 4. 各叶子结点的bit域符号串值就是其哈夫曼编码。 编码过程如图2所示。（a）中p首先指向权值为11的结点，将其bit域值“1”加到权值为5、6的结点bit域值的前面，则权值为5的结点的bit域值就是“10”，权值为6的结点的bit域值就是“11”;（b）（c）依次类推。最后得到各个叶子结点的权值。 （二）算法C语言实现 void huffmancode（TreeLeaf *LeafNode，TreeLeaf *NLNode） { int i，j; char *cd=（char*）malloc（MB *sizeof（char））; HuffmanTreeNode *p; for（j=n-3;j>-1;j--） { p=NLNode[j].Leaf; strcpy（cd，p->bit）; strcat（cd，p->lchild->bit）; strcpy（p->lchild->bit，cd）; strcpy（cd，p->bit）; strcat（cd，p->rchild->bit）; strcpy（p->rchild->bit，cd）; } printf（"＼n各权值的哈夫曼编码：＼n"）; for（i=0;i p=LeafNode[i].Leaf; printf（"%d： %s＼n"，p->weight，p->bit）; } free（cd）; return; } 四、结束语 《数据结构》课程中，传统的哈夫曼编码方法是在结构体数组上构造哈夫曼树，编码时从叶子结点向上到根结点逆向扫描2n-1个结点，时间复杂度为O（n2）。在本教学过程中，在传统编码方法基础上提出了另一种实现哈夫曼编码的方法，哈夫曼树采用二叉链表结构，求编码时从哈夫曼树第二层向下到叶子结点扫描，时间复杂度为O（n）。编码算法设计巧妙新颖，结构清晰简洁，这不但能拓展学生的算法设计思维，而且能提高学生的程序开发能力，在《数据结构》课程教学中有一定的参考价值。 参考文献： [1]严蔚敏，吴伟民.数据结构（C语言版）[M].清华大学出版社，2011. [2]鲍爱华，陈卫卫，等.基于“一题多解”的数据结构实践教学模式[J].计算机教育，2018（2）：119-123. [3]黄容，赵毅.C语言程序设计[M].清华大学出版社，2012.
