燕山大学数学建模第二讲剖析.ppt

* 1952年，Huffman提出了一个构造最优二叉树的精巧算法，被人们称为Huffman算法。 哈夫曼树（最优二叉树）的构造 哈夫曼树(最优二叉树)的构造 * Huffman算法思想： 1. 将权值为w1, w2, ..., wn的n个叶子构成一个具有n棵树的森林： 2. 从森林F中选取根权值最小的两棵树，分别作为左子树和右子树，再新添一个结点做为根，合并成一棵新的二叉树，新二叉树根的权值等于左、右子树根权值之和。 3. 重复2，直到F中只剩下一棵树为止，这棵树就是所求的Huffman树。 w1 w2 w3 wn F＝ … 哈夫曼树的构造 * a 6 b 1 f 4 c 5 d 4 e 2 e 2 b 1 3 哈夫曼树的构造 * a 6 f 4 c 5 d 4 d 4 e 2 b 1 3 e 2 b 1 3 7 哈夫曼树的构造 * a 6 f 4 c 5 d 4 e 2 b 1 3 7 c 5 f 4 9 哈夫曼树的构造 顾客到银行办理业务，首先需拿号并 排队等候，当空闲窗口叫号时，按排 队顺序去办理业务，业务办理完毕， 离开银行。 模型四--银行业务办理 如何模拟银行排队办理业务的过程？ 业务过程 请拿号 窗口1 窗口2 窗口3 模型四--银行业务办理 业务过程 请拿号 窗口1 窗口2 窗口3 1号 模型四--银行业务办理 业务过程 请拿号 窗口1 窗口2 窗口3 1号 2号 模型四--银行业务办理 业务过程 请拿号 窗口1 窗口2 窗口3 3号 2号 服务特点：队头顾客出队办理业务,新到顾客站到队尾；先到顾客先拿号，先获得服务 模型四--银行业务办理 模拟需解决三个问题: 数据及其关系？ 如何存储？ 过程中数据上的操作？ 数据：拿号的顾客，线性关系 存储：用顺序表来实现 操作：入队、出队 （a1,a2,a3,a4……） 模型四--银行业务办理 分析问题 解决方案 顺序表存储 ElemType elem[MAXSIZE]; 新的问题： 如何保证总是队头元素出队、新顾客排在队尾， 即先来顾客先获得服务？ 解决办法： 对顺序表插入删除位置做限制 （a1,a2,a3,a4……） 模型四--银行业务办理 0 1 2 3 4 5 6 7 a1 a2 a3 a4 rear front maxsize a5 顺序队列 指在队尾元素的 下一个位置 指在队头元素位置 0 1 2 3 4 5 6 7 a5 a7 a6 a8 rear front maxsize 假上溢 rear==maxsize rear － front maxsize a9 还有空间，我要入队！ 队空条件：front==rear 队列长度：rear－front 入队操作：rear＋＋ 出队操作：front＋＋ 队满条件： 真上溢 rear==maxsize rear－front==maxsize 顺序队列 0 1 2 3 4 5 6 7 rear a5 a7 a6 a8 front a9 假上溢问题的解决方案一： 当rear达到上界时，队列整体左移, 将空闲空间移至右侧，继续接纳元素入队。 缺点：需要移动元素 进来吧 顺序队列 0 1 2 3 4 5 6 7 rear a5 a7 a6 a8 front a9 假上溢问题的解决方案二： 允许rearfront，即当rear达到上界而有入队请求时，rear回到下界位置。这就是循环队列的思想。 顺序队列 0 6 5 4 3 2 1 7 front rear 入队、出队方向 初态 循环队列 0 6 5 4 3 2 1 7 front 入队、出队方向 a1 a6 a5 a4 a3 a2 rear a1,a2,a3,a4,a5,a6入队 循环队列 0 6 5 4 3 2 1 7 入队、出队方向 a6 a5 rear front a1,a2,a3,a4出队 a1 a2 a3 a4 循环队列 0 6 5 4 3 2 1 7 入队、出队方向 a9 a6 a5 rear front a7 a8 a7,a8,a9入队 循环队列 入队： if(rearmaxsize-1) rear ++; else rear=0; 这个if语句可等价地写成: rear=(rear+1) mod maxsize 出队： if(frontmaxsize-1) front++; else front=0; 这个if语句可等价地写成: front=(front+1) mod maxsize 循