📄 6_13.htm
字号:
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=gb_2312-80">
<META NAME="Generator" CONTENT="Microsoft Word 97">
<TITLE>第 2 章 线性表</TITLE>
</HEAD>
<BODY>
<B><FONT SIZE=3><P ALIGN="JUSTIFY">13. </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>求哈夫曼树及哈夫曼编码算法</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> void</B> HuffmanCoding ( HuffmanTree <B>&</B>HT, HuffmanCode <B>&</B>HC, <B>int</B> *w, int n ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B></FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> // <I>w</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>存放</FONT><FONT SIZE=3> <I>n</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>个字符的权值（均＞</FONT><FONT SIZE=3>0</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>），构造哈夫曼树</FONT><FONT SIZE=3> <I>HT</I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>，并求出</FONT><FONT SIZE=3> <I>n</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>个字符的哈夫曼编码</FONT><FONT SIZE=3> <I>HC</I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>。</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> <B>if </B> ( n <= 1 ) <B>return</B>;</P>
<P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> m = 2 * n - 1</P>
<P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> HT = ( HuffmanTree ) <B>malloc</B> ( ( m+1 ) * <B>sizeof</B> ( HTNode ) );</P>
<P ALIGN="JUSTIFY"> // </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>分配</FONT><FONT SIZE=3> <I>m</I>+1 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>个哈夫曼树结点的存储空间，</FONT><FONT SIZE=3>0 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>号单元未用，</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> <B>for</B> ( p = HT+1, i = 1; i <= n; ++i, ++p, ++w )</P>
<P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>*p = { *w, 0, 0, 0 };		</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>					</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>初始化</FONT><FONT SIZE=3> <I>HT</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的前</FONT><FONT SIZE=3> <I>n</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>个</FONT><FONT SIZE=3> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>分量</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> <B>for</B> ( ; i <= m; ++i, ++p )</P>
<P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>*p = { 0, 0, 0, 0 };		</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>					</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>初始化</FONT><FONT SIZE=3> <I>HT</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的后</FONT><FONT SIZE=3> <I>m</I>-<I>n</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>个</FONT><FONT SIZE=3> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>分量</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> <B>for</B> ( i = n + 1; i <= m; ++i ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{				</B></FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>构造哈夫曼树。</P><DIR>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">Select ( HT, i-1, s1, s2 );</P></DIR>
<P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>在</FONT><FONT SIZE=3> <I>HT</I> [1 .. <I>i</I>-1] </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>中选择</FONT><FONT SIZE=3> <I>parent</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>为</FONT><FONT SIZE=3> 0 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>且</FONT><FONT SIZE=3> <I>weight</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>最小的两个结点，</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>		</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>其序号分别为</FONT><FONT SIZE=3> <I>s</I>1 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>和</FONT><FONT SIZE=3> <I>s</I>2</P>
<P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>HT [s1].parent = i;	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>HT [s2].parent = i;</P>
<P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>HT [i].lchild = s1;		HT [i].rchild = s2;</P>
<P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>HT [i].weight = HT [s1].weight + HT [s2].weight;</P>
<P ALIGN="JUSTIFY"> </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</FONT><FONT SIZE=3> </B>// for </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> // </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>下面从叶子结点到根结点逆向求每个字符的哈夫曼编码</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> HC = ( HuffmanCode ) <B>malloc</B> ( ( n+1 ) * <B>sizeof</B> ( char * ) );</P>
<P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> // </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>分配</FONT><FONT SIZE=3> <I>n</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>个字符编码的头指针向量，</FONT><FONT SIZE=3>0 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>号单元未用</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> cd = ( char * ) <B>malloc</B> ( n * <B>sizeof</B> ( char ) );</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>		</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>分配求编码的工作空间</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> cd [n-1] = <FONT FACE="Symbol">²</FONT>
</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>\</FONT><FONT SIZE=3>0<FONT FACE="Symbol">²</FONT>
;			</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>					</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>编码结束符</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> <B>for</B> ( i = 1; i <= n; ++i ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</B>					</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>逐个字符求哈夫曼编码</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>start = n –1;			</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>					</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>编码结束符位置</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><B><FONT SIZE=3>for</B> ( c = i, f = HT [i].parent; f <B>!</B>= 0; c = f, f = HT [f].parent )</P>
<P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>从叶子到根逆向求编码</P>
<P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3> <B>if</B> ( HT [f].lchild = = c ) cd [--start] = <FONT FACE="Symbol">²</FONT>
0<FONT FACE="Symbol">²</FONT>
;</P>
<P ALIGN="JUSTIFY">	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> <B>else</B> cd [--start] = <FONT FACE="Symbol">²</FONT>
1<FONT FACE="Symbol">²</FONT>
;</P>
<P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>HC [i] = ( char * ) <B>malloc</B> ( ( n-start ) * <B>sizeof </B>( char ) );</P>
<P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>为第</FONT><FONT SIZE=3> <I>i</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>个字符编码分配空间，</FONT><I><FONT SIZE=3>n</I>-<I>start</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>为第</FONT><FONT SIZE=3> <I>i</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>个字符的编码长。</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>Strcpy ( HC [i], <B>&</B>cd [start] );</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>					</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>从</FONT><FONT SIZE=3> <I>cd</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>复制编码（串）到</FONT><FONT SIZE=3> <I>HC</P>
</I><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</B></FONT><FONT SIZE=3> // for </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> <B>free</B> ( cd );				</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>					</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>释放工作空间</P>
</FONT><B><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</B></FONT><FONT SIZE=3> // HuffmanCoding</P></FONT></BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -