PTA Huffman Codes 思路分析及具体实现 v1.0

#PTA Huffman Codes 思路分析及具体实现 v1.0| 来源: 网络整理| 查看: 265

PTA 7-9 Huffman Codes 思路分析及具体实现一、前导1. 写在前面2. 需要掌握的知识3. 题目信息二、解题思路分析1. 题意理解2. 思路分析（重点）三、具体实现1. 弯路和bug2. 代码框架（重点）2.1 采用的数据结构（重点）2.2 程序主体框架2.3 各分支函数（重点） 3. 完整编码四、参考

一、前导

目前只做到了AC ( ╯□╰ )，代码质量惨不忍睹 21.10.13 ：对代码进行了优化

1. 写在前面写博客的原因非常简单：好记性不如烂笔头。已经屡次被现实教育，虽然现在AC，如果下次再遇到，很可能重头开始其次，对思路和走过的坑(遇到的bug)进行系统性梳理，有利于自己成长，AC并不是终点，而是另一个起点和大家分享 2. 需要掌握的知识这道题难度不小，如果对下面的知识点不熟悉，建议延后做Huffman树：具备最小WPL；满足前缀编码；没有节点为1的子树前缀编码：任何一个字符的编码都不是其他字符编码的前缀堆：这里的堆不是堆栈，而是一种特殊的数据结构，堆按照优先级排序，堆顶的元素是最小的(小顶堆)或最大的(大顶堆)，可以通过数组存储，通过完全二叉树表示。编程能力：堆、树其他：建堆和建Huffman树代码量都挺大，有很多大神在未建树的情况下也AC啦注意，本文介绍的是通过建Huffman树解决问题的方法，代码量还是蛮大的，如果说好处：那就是结合实际编码熟悉堆和哈夫曼树 3. 题目信息

题目来源：PTA / 拼题A 题目地址：https://pintia.cn/problem-sets/16/problems/671

二、解题思路分析 1. 题意理解输入数据 //如下是输入数据 3 //需要编码的字符个数 a 1 b 1 c 2 //字符及其出现的频率 1 //提交编码的人数 a 00 //提交的编码 b 01 //提交的编码 c 1 //提交的编码输出数据符合要求打印Yes，不符合输出No：print in each line either “Yes” if the student’s submission is correct, or “No” if not题意对学生提交的编码进行判定，若wpl最小且编码正确(满足前缀编码的要求)，打印 Yes，否则打印 No 2. 思路分析（重点）依据题意，围绕两点进行编码即可满足题目的判定要求：（1）提交的编码WPL(Weighted Path Length of Tree)是最小的（2）各字符编码满足前缀编码的要求。不需要考虑节点为1的判定条件。思考：如果一棵树wpl最小且满足前缀码要求，它有节点为1的子树吗？答：进行反证。假设存在子树为1的节点，该树的WPL最小且满足前缀编码的要求。首先，子树为1的节点不能存储数据，否则会破坏前缀编码要求。其次，数据一定存储在其下方的叶节点上，若拿掉子树为1的节点（确实可拿掉），WPL会减少，这个和 WPL最小矛盾。 Alt

另外需要注意：Huffman树的WPL最小，但WPL最小的树不一定是Huffman树。只要WPL最小且满足前缀编码要求的学生答案都是正确的。如何计算出最小WPL？如何确保编码满足前缀编码的需求？三、具体实现 1. 弯路和bug 我一开始老想将元素(就是a 1 b 1 中的a,b )也通过结构体记录下来，最后发现完全没有必要，结构体中只存储频率即可。为什么不用记录元素？ WPL计算和前缀编码判定都是通过频率进行的，和元素没有任何关系。而且元素的顺序前后都是一致的。我一开始思维始终局限在堆中的元素只能是int char 等单个元素，其实堆中的元素也可以是结构体，比如：树注意别遗漏检查编码相同的异常情况，即 a b的编码结果都是 00检查完一位学生后，需要恢复默认值 2. 代码框架（重点）

代码框架是我们容易忽视的内容，我们往往喜欢最快时间开始编码。其实就像盖房子，需要先画图纸然后再施工一样。程序也需要进行概要设计(框架)，再进行详细设计(Code)。需要先想好采用的数据结构及需要的函数

2.1 采用的数据结构（重点）

使用小顶堆的目的是为了创建Huffman树，每次从堆中取出两个频率最小的Huffman树，通过这两个Huffman树建一棵二叉树，然后将新建的树再插回小顶堆中。然后重复，上述操作需要执行N-1次(共N个元素)，最后形成一棵Huffman树

typedef struct TreeNode *HuffmanTree; struct TreeNode { int Weight; HuffmanTree Left,Right; };//Huffman树的结构 typedef struct HeapNode *MinHeap; struct HeapNode { HuffmanTree *HTree; int Size; };//堆结构，堆由一棵棵的Huffman树组成 2.2 程序主体框架

个人认为这个习惯很重要，先完成程序的大体框架并理清思路（详设）

程序伪码描述 int main() { 1.创建一个空的最小堆; 2.接收录入的数据并创建一棵棵Huffman树，将这一棵棵树插入创建的最小堆中 3.通过最小堆创建一棵Huffman树 4.通过Huffman树得到wpl 5.处理学生录入的数据：（1）计算其wpl，和得到的wpl比对（2）判定是否满足前缀码要求 6.打印判断结果 return 0; } 2.3 各分支函数（重点） MinHeap CreatMinHeap(int n); //创建一个空堆 void InsertMinHeap(MinHeap H,HuffmanTree HTree ); //将元素插入到最小堆中 HuffmanTree DeleteMin(MinHeap H); HuffmanTree Huffman(MinHeap H); int WPL(HuffmanTree HTree,int depth); bool Judge(HuffmanTree HTree,bool value,bool end); CreatMinHeap() ：创建空堆。需要注意2点：（1）堆里存储的是一棵棵Huffman树，通过Weight进行排序；（2）设定好哨兵，也就是数组的0号 MinHeap CreatMinHeap(int n) { MinHeap H; H=(MinHeap)malloc(sizeof(struct HeapNode)); H->Size=0; H->HTree=(HuffmanTree*)malloc(sizeof(struct TreeNode)*(n+1)); //n棵Huffman树 + 1个哨兵 HuffmanTree tmp; //tmp是哨兵，其Weight是最小值 tmp=(HuffmanTree)malloc(sizeof(struct TreeNode)); tmp->Left=NULL; tmp->Right=NULL; tmp->Weight=-1; H->HTree[Guard]=tmp; return H; } InsertMinHeap()：将一棵棵Huffman树插入到堆中，形成小顶堆。栗子：对于输入 a 1 b 1 c 2，可以把频率 1 1 2 看成三棵单节点的Huffman树 void InsertMinHeap(MinHeap H,HuffmanTree HTree) { int i = ++H->Size; for(; HTree->Weight HTree[i/2]->Weight ; i=i/2 ) { H->HTree[i]=H->HTree[i/2]; //堆中的元素是一棵棵的树，按频率进行排列。堆可以看作是一棵完全二叉树 } H->HTree[i]=HTree; return; } DeleteMin()：目的是为了取出最小频率的子树，被Huffman()函数调用。Delete本身很简单，取出顶部的元素即可(数组序号是1)，编码难点是对剩余的元素进行调整，以便取出元素后剩余的元素仍然是小顶堆 HuffmanTree DeleteMin(MinHeap H) { HuffmanTree HTree; HTree=H->HTree[Top]; H->HTree[Top]=H->HTree[H->Size--]; int father,child; HuffmanTree tmp; father=Top; child=2*father; while(child Size) //说明有儿子 { if( child+1 Size && H->HTree[child+1]->Weight HTree[child]->Weight ) child++; if(H->HTree[child]->Weight HTree[father]->Weight) { tmp=H->HTree[father]; H->HTree[father]=H->HTree[child]; H->HTree[child]=tmp; father=child; child=2*father; } else break; } return HTree; } Huffman()：根据输入创建一棵Huffman树，为后续计算WPL打基础。创建Huffman树完全模拟Huffman树的建树过程，每次从集合中取出两棵频率最低的树，合并后放回原集合，然后重复N-1次(小顶堆共N个元素) HuffmanTree Huffman(MinHeap H) { int i; HuffmanTree T; int loop = H->Size; for(i=1; iSize一直再变啊，需要固定住 { T=(HuffmanTree)malloc(sizeof(struct TreeNode)); T->Left=DeleteMin(H); T->Right=DeleteMin(H); T->Weight=T->Left->Weight + T->Right->Weight; InsertMinHeap(H,T); } T=DeleteMin(H); return T; } WPL()：计算自己创建的Huffman树的wpl值，用于和学生提交的进行比对。通过递归实现比较容易 int WPL(HuffmanTree T,int depth) { if(!T->Left && !T->Right) return (T->Weight*depth); else //由于是二叉树，一定有两个子树 { return (WPL(T->Left,depth+1) + WPL(T->Right,depth+1)); //depth++就是错的 why？ } } Judge(string a,string b)：判定学生的编码是否满足前缀编码（不存在二义性） 21.10.13：编码不存在二义性，就是不能出现如下情况：001 0011 前者被后者包含或 011 01 后者被前者包含 bool Judge(string a, string b) { for (int i = 0; i //A 1 B 1 C 1 D 3 E 3 F 6 G 6 int Freq;//为什么不记录A B C 只记录频率1 1 1? 因为根据哈夫曼树的特点，待计算WPL的结点都位于叶结点（知道出现频率就可以了） HuffmanTree Left; HuffmanTree Right; }; MinHeap CreateEmptyHeap(int N); void InsertHeap(MinHeap MHeap, HuffmanTree HTree); HuffmanTree DeleteHeap(MinHeap MHeap); //从小顶堆中取出最小的Huffman树 HuffmanTree ConstructHuffman(MinHeap MHeap); //依次取出两个Huffman树，合并后插入原堆中，重复，直到Size=1; int CalcWPL(HuffmanTree Tree,int Height); bool Judge(string a, string b); int main() { int N; cin >> N; MinHeap MHeap = CreateEmptyHeap(N); int* a = new int[N]; //存储所有元素出现的频率计算WPL会用上 char Symbol; int Freq; for (int i = 0; i int StuWPL = 0; for (int i = 0; i for (int i = 0; i if (!Tree->Left && !Tree->Right) //叶结点就是待计算的结点 return Tree->Freq * Height; else return CalcWPL(Tree->Left, Height + 1) + CalcWPL(Tree->Right, Height + 1); } HuffmanTree DeleteHeap(MinHeap MHeap) { HuffmanTree Tree = MHeap->HTree[1];//取出最小的Huffman树的index=1 , 0 is Guard //将剩余的元素再次调整为最小堆 MHeap->HTree[1] = MHeap->HTree[MHeap->Size--]; int Parent = 1, Child = Parent * 2; while (Child Size) { if ((Child + 1 Size) && (MHeap->HTree[Child + 1]->Freq HTree[Child]->Freq)) Child++; HuffmanTree Tmp; if (MHeap->HTree[Child]->Freq HTree[Parent]->Freq) { Tmp = MHeap->HTree[Parent]; MHeap->HTree[Parent] = MHeap->HTree[Child]; MHeap->HTree[Child] = Tmp; Parent = Child; Child = Parent * 2; } else break; } return Tree; } HuffmanTree ConstructHuffman(MinHeap MHeap) { int Loop = MHeap->Size - 1; HuffmanTree Tree01, Tree02,Tree; for (int i = 0; i int i = ++MHeap->Size; //在堆中可能的插入位置 while (HTree->Freq HTree[i/2]->Freq) //调整为小顶堆 { MHeap->HTree[i] = MHeap->HTree[i/2]; i /= 2; } MHeap->HTree[i] = HTree; return ; } MinHeap CreateEmptyHeap(int N) { MinHeap MHeap; MHeap = new struct Heap; MHeap->Size = 0; MHeap->HTree = new HuffmanTree[N + 1]; //0是哨兵 + N个元素 HuffmanTree Guard = new struct TreeNode;//哨兵 Guard->Freq = -1; Guard->Left = Guard->Right = NULL; MHeap->HTree[MHeap->Size] = Guard; //哨兵不算正式元素，因此 MHeap->HTree[MHeap->Size++] = Guard 是错误的; return MHeap; } /* 0.数据结构：（1）通过结构体存储堆、堆由一棵棵哈夫曼树构成（2）根据Huffman树的特点，待统计WPL的结点都处于叶结点 1.构建Huffman树：（1）最小堆（由一颗颗树构成）（2）每次取出两个最小的树->处理后放回最小堆->再取出两个最小的...直到全部取出（3）取出意味着堆删除元素，插入意味堆新增元素 2.构建完毕，统计WPL 3.判定：（1）最小编码长度应该相同（2）编码不存在二义性,即不能出现如下情况：001 0011 前者被后者包含或 011 01 后者被前者包含 */

之前的AC代码

#include #include #include #include using namespace std; #define Top 1 #define Guard 0 //7 A 1 B 1 C 1 D 3 E 3 F 6 G 6 #define Max 100 typedef char ElementType; //不记录元素，只记录频率试试 typedef struct TreeNode *HuffmanTree; struct TreeNode { int Weight; HuffmanTree Left,Right; }; typedef struct HeapNode *MinHeap; struct HeapNode { HuffmanTree *HTree; int Size; }; HuffmanTree DeleteMin(MinHeap H); void InsertMinHeap(MinHeap H,HuffmanTree HTree ); MinHeap CreatMinHeap(int n); HuffmanTree Huffman(MinHeap H); void PrintTree(HuffmanTree T); void PrintHeap(MinHeap H); int WPL(HuffmanTree HTree,int depth); bool Judge(HuffmanTree HTree,bool value,bool end); int main() { int n; cin>>n; MinHeap H; H=CreatMinHeap(n); ElementType data; int freq; HuffmanTree HTree; int a[n]; for(int i=0;i for(int j=0;j tmp=code[k]-'0'; if(k== (strlen(code)-1) ) end=1; flag=Judge(Judge_Tree,tmp,end); if(tmp==0) { //cout //bool flag==1; if(value==0 && !HTree->Left && end!=1) // { //coutRight=NULL; //bug no defalut value HTree->Left=T; //HTree=HTree->Left; return true; } if(value==0 && !HTree->Left && end==1) { //coutRight=NULL; HTree->Left=T; //HTree=HTree->Left; return true; } if(value==0 && HTree->Left && end!=1) { //cout if(HTree->Left->Weight==1) { //cout //cout //coutRight=NULL; HTree->Right=T; //HTree=HTree->Right; return true; } if(value==1 && HTree->Right && end!=1) { //HTree=HTree->Right; //cout if(HTree->Right->Weight==1) { //cout //cout return (WPL(T->Left,depth+1) + WPL(T->Right,depth+1)); //depth++就是错的 why？ } //return wpl; } void PrintHeap(MinHeap H) { for(int i=1;iSize;i++) coutWeight x=q.front(); coutRight->Weight); if(x->Left) { q.push(x->Left); } if(x->Right) { q.push(x->Right); } //T=T->Left } return; } HuffmanTree DeleteMin(MinHeap H) { //coutSize--]; int father,child; HuffmanTree tmp; father=Top; child=2*father; while(child Size) //说明有儿子 { if( child+1 Size && H->HTree[child+1]->Weight HTree[child]->Weight ) child++; if(H->HTree[child]->Weight HTree[father]->Weight) { tmp=H->HTree[father]; H->HTree[father]=H->HTree[child]; H->HTree[child]=tmp; father=child; child=2*father; } else break; } //H->Frequent[H->Size--]; return HTree; } HuffmanTree Huffman(MinHeap H) { int i; HuffmanTree T; int loop = H->Size; for(i=1; iSize一直再变啊，需要固定住 { T=(HuffmanTree)malloc(sizeof(struct TreeNode)); T->Left=DeleteMin(H); //bug? //PrintTree(T->Left); T->Right=DeleteMin(H); //PrintTree(T->Right); T->Weight=T->Left->Weight + T->Right->Weight; InsertMinHeap(H,T); //bug? } T=DeleteMin(H); //cout H->HTree[i]=H->HTree[i/2]; //堆中的元素是一棵棵的树，按频率进行排列。堆完全二叉树 } H->HTree[i]=HTree; return; } MinHeap CreatMinHeap(int n) { //coutRight=NULL; tmp->Weight=-1; H->HTree[Guard]=tmp; return H; } 四、参考浙大陈越、何钦铭老师主讲的数据结构: http://www.icourse163.org/learn/ZJU-93001?tid=1459700443#/learn/content?type=detail&id=1235254062.

【本文地址】

公司简介

联系我们