数据结构之赫夫曼编码

会计学1数据结构之赫夫曼编码上节复习二叉树的存储结构顺序存储，把普通二叉树补全为完全二叉树，再按层次遍历顺序保存链式存储，二叉链 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 、三叉链表掌握存储结构的画图 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 二叉树的四种遍历：前序、中序、后序，采用递归嵌套方式层次遍历，从上往下，从左到右，把二叉树的链式存储转化为数组存储第1页/共25页3已知二叉树结构如图所示，求求先、中、后序遍历结果画出顺序存储和链式存储结果练习adebfgchijk第2页/共25页46.6赫夫曼树最优二叉树赫夫曼树又称为最优树，是一类带权路径长度最短的树树的路径和路径长度路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径路径长度：路径上的分支数目树的路径长度：从树根到每个结点的路径长度之和树路径长度为：2*1+3*2+1*3=11ADBFCGE第3页/共25页56.6赫夫曼树最优二叉树带权路径长度：从结点到树根之间的路径长度与结点上权的乘积树的带权路径长度(WPL)：树中所有叶子结点的带权路径长度之和WPL=2*5+3*3+2*4=27ADBFCGE5３４第4页/共25页66.6赫夫曼树最优二叉树具有n个叶子结点(每个结点的权值为wi)的二叉树不止一棵，但在所有的这些二叉树中，必定存在一棵WPL值最小的树，称这棵树为Huffman树(或称最优树)如图是权值分别为2、3、6、7，具有4个叶子结点的二叉树236736726723(a)(b)(c)具有相同叶子结点，不同带权路径长度的二叉树第5页/共25页76.6赫夫曼树最优二叉树它们的带权路径长度分别为：(a)WPL=22+32+62+72=36(b)WPL=21+32+63+73=47(c)WPL=71+62+23+33=34其中(c)的WPL值最小，称这棵树为最优二叉树或Huffman树第6页/共25页86.6赫夫曼树最优二叉树赫夫曼树的简单应用——百分制转五级制将0～100分转变为不及格、及格、中等、良好、优良五个级别普通方法用四次判断语句不同成绩的分布规律构造赫夫曼树，通过赫夫曼树进行判定，大大减少判断次数构造二叉树的思路：把分布比例数作为叶子权值，每个结点包含一个判断，把高权值结点放在路径短的地方，低权值放在路径长的地方第7页/共25页96.6赫夫曼树最优二叉树赫夫曼树的简单应用——百分制转五级制将0～100分转变为不及格、及格、中等、良好、优良五个级别分数的分布比例为：第8页/共25页106.6赫夫曼树最优二叉树赫夫曼树的简单应用——百分制转五级制采用普通方法用四次判断语句若有10000个输入数据，根据分数分布比例需要31500次80%以上数据需要经过3次以上的比较才能得到结果第9页/共25页116.6赫夫曼树最优二叉树赫夫曼树的简单应用——百分制转五级制把高比例数据先做比较，程序调整如下，第10页/共25页126.6赫夫曼树最优二叉树赫夫曼树的简单应用——百分制转五级制改进方法中每个比较有包含两次判断，再做细化，得到如下的判定树10000个输入数据需要22000次判断第11页/共25页136.6赫夫曼树最优二叉树赫夫曼树的简单应用——百分制转五级制以5、15、40、30和10为权值，构造一颗有5个叶子的赫夫曼树，也就得到同样的这颗二叉树第12页/共25页146.6赫夫曼树赫夫曼树的构造在Huffman树中，权值最大的结点离根最近，权值最小的结点离根最远构造算法根据给定的n个权值(w1,w2,…,wn)构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带树为Ti的根结点在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右子树权值之和在F中删除这两棵树，同时将新得到的二叉树加入F中重复2,3，直到F只含一棵树为止第13页/共25页156.6赫夫曼树赫夫曼树的构造举例F:{7}{5}{2}{4}F:{7}{5}{6}F:{7}{11}7524初始合并{2}{4}75246F:{18}1175246合并{5}{6}5合并{7}{11}27461118第14页/共25页166.6赫夫曼树赫夫曼编码通过赫夫曼树把电文缩短，减少传送时间编码前GOOD_G设给出一段报文：GOOD_GOOD_GOOD_GOOOOOOOO_OFF字符集合是{O,G,_,D,F}，各个字符出现的频度(次数)是W＝{15,4,4,3,2}。若给每个字符以等长编码O:000G:001_:010D:011F:100则总编码长度为(15+4+4+3+2)*3=84.第15页/共25页176.6赫夫曼树赫夫曼编码编码后若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。各字符{O,G,_,D,F}出现概率为{15/28,4/28,4/28,3/28,2/28},化整为{15,4,4,3,2}各字符出现概率[取整数]为{15,4,4,3,2}如果规定，Huffman树的左子树小于右子树，则可构成右图所示Huffman树415423G_FDO第16页/共25页186.6赫夫曼树赫夫曼编码编码后令左孩子分支为编码‘0’，右孩子分支为编码‘1’将根结点到叶子结点路径上的分支编码，组合起来，作为该字符的Huffman码，则可得到：　O:1_:011G:010D:001F:00041542300001111G_FDO第17页/共25页196.6赫夫曼树赫夫曼编码则总编码长度为15*1+(2+3+4+4)*3=54<84Huffman是一种前缀编码，解码时不会混淆，如GOOD编码为：0101100141542300001111G_FDO第18页/共25页20已知字符A、B、C、D、E、F，对应权值为13、4、22、38、6、17，若进行赫夫曼编码，请完成以下要求：构建赫夫曼树，要求左孩子权值不大于右孩子权值写出每个字符对应的编码，分支编码对应0或1对以下三个编码串进行解码，若解码异常则直接输出error01010011101，110101，010011011练习第19页/共25页216.6赫夫曼树赫夫曼编码赫夫曼树的实现typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;第20页/共25页226.6赫夫曼树赫夫曼编码赫夫曼树的实现voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用for(i=1;i<=n;i++){//初始化HT[i].weight=w[i-1];HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}//endforfor(i=n+1;i<=m;i++){//初始化HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}//endfor第21页/共25页236.6赫夫曼树赫夫曼编码赫夫曼树的实现for(i=n+1;i<=m;i++){//建哈夫曼树//在HT[1..i-1]中选择parent为0且weight最小的两个结点，//其序号分别为s1和s2。Select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}//endfor第22页/共25页246.6赫夫曼树赫夫曼编码赫夫曼树的实现//---从叶子到根逆向求每个字符的哈夫曼编码---cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间cd[n-1]='\0';//编码结束符。for(i=1;i<=n;++i){//逐个字符求哈夫曼编码start=n-1;//编码结束符位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(HC[i],&cd[start]);//从cd复制编码(串)到HC}free(cd);//释放工作空间}//endfunction第23页/共25页256.6赫夫曼树赫夫曼解码算法 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 定义指针p指向赫夫曼树结点，实际是记录结点数组的下标定义指针i指向编码串，定义ch逐个取编码串的字符初始化：读入编码串，设置p指向根结点，i为0执行以下循环：取编码串的第i个字符放入ch如果ch是字符0，表示往左孩子移动，则p跳转到右孩子如果ch是字符1，表示往右孩子移动，则p跳转到右孩子如果ch非0非1，表示编码串有错误，输出error表示解码失败检查p指向的结点是否为叶子如果是叶子，输出解码，p跳回根节点如果不是叶子，设置ch为3继续循环，一直到编码串末尾循环执行完后，如果ch值为3，输出解码失败，否则成功结束第24页/共25页