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

数据结构与算法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;存放字符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; j<i; j+) 求最小值if (TjJ.parent=()&&(T(jJ.weight<firstmin) (firstmin=Tj.weight;*sl=j；)for (j=l; j<i; 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; i<m; i+) Ti.parent=0; Ti.lchild=0; Ti.rchild=0; Ti. weight：。;/ InputWeight(T); 读入n个结点的权值for (i=l; i<=n; i+) coutvv”输入第"vvivv”个权值="；cin»(Ti.weight); for (i=n+l; i<m; 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 T, HuffnianCode H)根据哈夫曼树T求哈夫曼编码表Hunsigned int c, p;inti;c指向T的孩子，p指向T的双亲char cdn+l;临时存放编码int start;指示编码在cd中的起始位置cdn=,0,;编码结束符for (i=l; i<=n; i+) (依次求叶结点的编码coutvv”输入第“ Wivv“个字符二"cin»Hi.ch;读入叶结点对应的待编码字符start=n;编码起始位置的初值c=i;从叶结点Ti开始回溯while (p=Tcl.parent)>0) 直到上溯到 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+) cout«CodingResulti.ch«*' "；cout«CodingResultil.bits«endl;)return 0;