📄 ds6.5.3.htm
字号:
"Times New Roman"">和</span><span lang="EN-US">1</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">的序列便为该结点对应字符的编码，我们称之为哈夫曼编码。</span></font></b></p>
<p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US"><font size="5" color="#FFFFFF"><b>
</b></font></span><font size="5" color="#FFFFFF"><b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是电文的代码总长，所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码。</span></b></font></p>
<p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US"><font size="5" color="#FFFFFF"><b>
</b></font></span><font size="5" color="#FFFFFF"><b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，这样才能保证译码的唯一性。例如表</span><span lang="EN-US">6.2
(d)</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">的编码方案，字符</span><span lang="EN-US">A</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">的编码</span><span lang="EN-US">01</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">是字符</span><span lang="EN-US">B</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">的编码</span><span lang="EN-US">010</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">的前缀部分，这样对于代码串</span><span lang="EN-US">0101001</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，既是</span><span lang="EN-US">AAC</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">的代码，也是</span><span lang="EN-US">ABD</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">和</span><span lang="EN-US">BDA</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">的代码，因此，这样的编码不能保证译码的唯一性，我们称之为具有二义性的译码。</span></b></font></p>
<p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US"><font size="5" color="#FFFFFF"><b>
</b></font></span><font size="5" color="#FFFFFF"><b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">然而，采用哈夫曼树进行编码，则不会产生上述二义性问题。因为，在哈夫曼树中，每个字符结点都是叶结点，它们不可能在根结点到其它字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。</span></b></font></p>
<p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US"><font size="5" color="#FFFFFF"><b>
</b></font></span><font size="5" color="#FFFFFF"><b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">下面讨论实现哈夫曼编码的算法。实现哈夫曼编码的算法可分为两大部分：</span></b></font></p>
<p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US"><font size="5" color="#FFFFFF"><b>
</b></font></span><font size="5" color="#FFFFFF"><b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">（</span><span lang="EN-US">1</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">）构造哈夫曼树；</span></b></font></p>
<p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US"><font size="5" color="#FFFFFF"><b>
</b></font></span><font size="5" color="#FFFFFF"><b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">（</span><span lang="EN-US">2</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">）在哈夫曼树上求叶结点的编码。</span></b></font></p>
<font size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA" lang="EN-US">
</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的路径上各分支所组成的</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">0</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">，</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">1</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码。我们可以设置一结构数组</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">HuffCode</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">用来存放各字符的哈夫曼编码信息，数组元素的结构如下：</span></b></font>
<p align="center"><img border="0" src="ds6.5.7.gif" width="193" height="32"></p>
<p class="MsoNormal" style="text-indent:21.0pt;mso-char-indent-count:2.0;
mso-char-indent-size:10.5pt"><font size="5" color="#FFFFFF"><b><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">其中，分量</span><span lang="EN-US">bit</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">为一维数组，用来保存字符的哈夫曼编码，</span><span lang="EN-US">start</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">表示该编码在数组</span><span lang="EN-US">bit</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">中的开始位置。所以，对于第</span><span lang="EN-US">i</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">个字符，它的哈夫曼编码存放在</span><span lang="EN-US">HuffCode[i].bit</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">中的从</span><span lang="EN-US">HuffCode[i].start</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">到</span><span lang="EN-US">n</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">的分量上。</span></b></font></p>
<p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">哈夫曼编码算法描述如下。</span></font></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">#define MAXBIT
10<span style="mso-spacerun: yes"> </span></font></b></font></span><font color="#FFFFFF"><b><font size="5"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">定义哈夫曼编码的最大长度</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">*/</span></font></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">typedef struct
{</font></b></font></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">int bit[MAXBIT];</font></b></font></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">int start;</font></b></font></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">}HCodeType;</font></b></font></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">void
HaffmanCode ( )</font></b></font></span></p>
<p class="MsoNormal" style="text-indent: 21.0pt; margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b><span lang="EN-US">{</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">
/*</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">生成哈夫曼编码</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">*/</span></b></font></p>
<p class="MsoNormal" style="text-indent: 32.0pt; mso-char-indent-count: 3.05; mso-char-indent-size: 10.45pt; margin-top: 0; margin-bottom: 0"><span lang="EN-US"><font size="5" color="#FFFFFF"><b>HNodeType
HuffNode[MAXNODE];</b></font></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">HCodeType
HuffCode[MAXLEAF],cd;</font></b></font></span></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -