《数据结构与算法》huffman算法实现.docx

《《数据结构与算法》huffman算法实现.docx》由会员分享，可在线阅读，更多相关《《数据结构与算法》huffman算法实现.docx（2页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法huffman算法实现/ huffnian.cpp : Defines the entry point for the console application./#include stdafx.h#includc ,iostream.hM#include *string.hn#define n 4#define in 2*ntypedef struct unsigned int weight;unsigned int parent, Ichild, rchild;JHTNode;typedef HTNode HufTmanTreem;typedef struct char ch;

2、存放字符char bitsn+1J;存放编码位串JCodeNode;typedef CodeNode HuffnianCoden+l;void SelectMin(HuffmanTree T, int i, unsigned int *sl, unsigned int *s2)选取两个权值最小的结点 intj；unsigned int firstminecondmin;firstmin=secondmin=32767;for (j=l; ji; j+) 求最小值if (TjJ.parent=()&(T(jJ.weightfirstmin) (firstmin=Tj.weight;*sl=j；)

3、for (j=l; ji; j+) 求次小值if (Tj.parent =0) & (TjJ.weight!=firstmin) & (Tj.weight secondmin) secondmin=Tj.weight;*s2=j;return;/Selectmin void CrcateHufTmanTree(HufTmanTree T) 构造哈夫曼树，为其根结点int i;unsigned int si, s2;/ InitHummanTree(T); 将T0m中2n-l个结点的三个指针域和权值均设置为0； for (i=l; im; i+) Ti.parent=0; Ti.lchild=0

4、; Ti.rchild=0; Ti. weight：。;/ InputWeight(T); 读入n个结点的权值for (i=l; i=n; i+) coutvv”输入第vvivv”个权值=；cin(Ti.weight); for (i=n+l; im; i+) 构造哈夫曼树SelectMin(T, i,&sl,&s2);选取两个权值最小的结点TslJ.parent=i; Ts2.parent=i;Ti.lchild=sl; Ti.rchild=s2;Ti.weight=Tsl.weight+Ts2.weight;void CharSetHuffmaiiEiicoding(HuffmanTree

5、 T, HuffnianCode H)根据哈夫曼树T求哈夫曼编码表Hunsigned int c, p;inti;c指向T的孩子，p指向T的双亲char cdn+l;临时存放编码int start;指示编码在cd中的起始位置cdn=,0,;编码结束符for (i=l; i0) 直到上溯到 Tc是根为止cd-start=(Tp.Ichild=c)?左子树编码0,反之为 Tc=p; 继续回溯 strcpy(Hi.bits,&cdstart);/end for/CharSetHuffmanEnco(iingint main(int argc, char* argv)HuffmanTree Q;HuffmanCode CodingResult;int i;CreateHuffmanTree(Q);CharSetHuffmanEncoding(Q,CodingResult); for (i=l; i=n; i+) coutCodingResulti.ch* ；coutCodingResultil.bitsendl;)return 0;