网站大量收购独家精品文档,联系QQ:2885784924

贵州民族学院数据结构课件 第十一章.ppt

贵州民族学院数据结构课件 第十一章.ppt

  1. 1、本文档共34页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第十一章 树形结构的其他应用 第11章 树形结构的应用 11.1 哈夫曼树 11. 2 堆排序 11. 3 决策树 11. 4 博弈树 11.1 Huffman树 主要内容: 什么是Huffman树 Huffman树的构造方法 Huffman树的两个应用: 字符编码 判定问题 11. 1 哈夫曼树(Huffman)——最优二叉树 带权路径长度最短的二叉树 定义 路径:从树中一个结点到另一个结点之间的分支构成这两个结点间的路径 路径长度:路径上的分支数 树的路径长度:从树根到每一个结点的路径长度之和 二叉树的带权路径长度:树中所有带权结点的路径长度之和 Huffman树 设有n个权值{w1,w2, …,wn},构造一棵有n个叶子结点的二叉树,每个叶子的权值为wi,则wpl最小的二叉树称Huffman树 构造Huffman树的方法(Huffman算法) 构造Huffman树步骤 根据给定的n个权值{w1,w2,……wn},构造n棵只有根结点的二叉树,令其权值为wj 在森林中选取两棵结点权值最小的树作左右子树,构造一棵新的二叉树,置新二叉树根结点权值为其左右子树根结点权值之和 从森林中删除这两棵树,同时将新得到的二叉树加入森林中 重复上述两步,直到森林只含一棵树为止,这棵树即Huffman树 C语言描述的算法 void huffman(int n, int w[ ], HNode t[ ]) //数组w用于是已知的权值集合,数组t存放结果——Huffman树 { int i,j,k,x1,x2,m1,m2; //x1,x2分别存放左、右子子树的下标,m1,m2存放当前最小的两个权值 for(i=1;i(2*n);i++) // 初始化结果数组 { t[i].pa=0;t[i].lc=0;t[i].rc=0; if(i=n) t[i].data=w[i]; else t[i].data=0; } for(i=1;in;i++) //找最小的两个权值m1,m2,并用它们作为左右子树构造新的二叉树 { m1=MAX;m2=MAX; //MAX代表∞ x1=0;x2=0; for(j=1;j(n+i);j++) { if((t[j].datam1)(t[j].pa==0)) { m2=m1; x2=x1; m1=t[j].data; x1=j; } // if else if((t[j].datam2)(t[j].pa==0)) { m2=t[j].data; x2=j; } // else } // for(j) // 构造子树,根结点存于t[n+i]中 k=n+i; t[x1].pa=k; t[x2].pa=k; t[k].data=m1+m2; t[k].lc=x1; t[k].rc=x2; } //for(i) } //huffman 11. 2 堆排序 堆的定义:n个元素的序列(k1,k2,…,kn),当且仅当满足下列关系时 称之为堆 堆排序: 将无序序列建成一个堆,得到关键字最小(或最大)的记录; 输出堆顶的最小(大)值后,对剩余的n-1个元素调整成一个堆,则可得到n个元素的次小值; 重复执行上两步,得到一个有序序列, 堆排序需解决的两个问题: 如何由一个无序序列建成一个堆? 如何在输出堆顶元素之后,调整剩余元素,使之成为一个新的堆? 第二个问题解决方法——筛选 方法(最小堆): 输出堆顶元素之后,以堆中最后一个元素替代之; 然后将根结点值与左、右子树的根结点值进行比较,并与其中小者进行交换 对交换过的子树的根,重复上一步操作,直至叶子结点,得到新的堆 称这个从堆顶至叶子的调整过程为“筛选” 算法描述 typedef struct { int key; //排序码域 int link; //指针域 ··· ···; //其他域 }RcdType; //记录类型 typedef RcdType Rcdlist[M+1]; //用顺序表存放记录 int sift(Rcdlist r, int k, int n) { int i,j; RcdType x; i=k; x=r[i]; j=2*i; while(j=n) { if((jn){r[j].keyr[j+

您可能关注的文档

文档评论(0)

ormition + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档