存储管理中分区分配算法模拟.docVIP

成 绩 评 定 表 学生姓名 班级学号 专 业 计算机科学与技术 课程设计题目 1存储管理中分区分配算法的模拟 2已知二叉树的中序和先序序列，求后序序列 评 语 组长签字： 成绩 日期 2012 年12 月25日 课程设计任务书 学 院 信息科学与工程学院 专 业 计算机科学与技术 学生姓名 班级学号 课程设计题目 1存储管理中分区分配算法的模拟 2已知二叉树的中序和先序序列，求后序序列 实践教学要求与任务: 课程设计任务 当作业运行时，由操作系统将内存空间分配给作业。 已知二叉树的中序和先序序列，求后序序列 2 课程设计要求 1）分区管理是内存管理的一种方式，模拟分区分配算法采用最佳适应、最先适应等方式分配内存。选择不同的算法，对作业分配所需要的空间。当空间回收时，将空闲空间与被回收空间相连的部分连接成一块较大的空间。 2）完成需求分析，建立数学模型，编写程序，调试。 工作计划与进度安排: 第17周：设计任务分析和总体设计，软件算法和流程设计，软件编码实现。 第18周：软件总体调试，交课程设计报告、答辩、验收程序。 指导教师： 201 年 月 日 专业负责人： 201 年 月 日 学院教学副院长： 201 年 月 日 目 录 1 需求分析…………………………………………………… 4 1.1存储管理中分区分配算法的模拟…………………………4 1.2已知二叉树的中序和先序序列，求后序序列……………6 2 概要设计………………………………………………………4 2.1存储管理中分区分配算法的模拟…………………………4 2.1.1概述…………………………………………………4 2.1.2结构设计说明………………………………………4 2.1.3算法流程图…………………………………………6 2.2已知二叉树的中序和先序序列，求后序序列……………6 2.2.1概述…………………………………………………6 2.2.2结构说明……………………………………………6 2.2.3算法流程图…………………………………………7 3 详细设计………………………………………………………8 3.1存储管理中分区分配算法的模拟…………………………8 3.2已知二叉树的中序和先序序列，求后序序列……………12 4 调试分析………………………………………………………16 4.1存储管理中分区分配算法的模拟…………………………16 4.2已知二叉树的中序和先序序列，求后序序列……………19 5 课设总结………………………………………………………20 6 参考文献………………………………………………………21 1 需求分析概要设计 2.1.3算法流程图 选取部分核心流程图如下： 2.2已知二叉树的中序和先序序列，求后序序列 2.2.1概述 已知二叉树的前序后序遍历和中序遍历 求后序1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右 边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和 右边都为空，则根节点已经为叶子节点。 3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复 1、2、3 步，直到所有的节 点完成定位。 举例说明：假设前序遍历为 adbgcefh, 中序遍历为 dgbaechf 前序遍历是先访问根节点 ，然后再访问子树的，而中序遍历则先访问左子树再访问根节点 而中序遍历则先访问左子树再访问根节点 那么把前序的 a 取出来，然后查找 a 在中序遍历中的位置就得到 dgb a echf 然后查找 那么我们就知道 dgb 是左子树 echf 是右子树，因为数量要吻合 所以前序中相应的 dbg 是左子树 cefh 是右子树 然后就变成了一个递归的过程 3 详细设计 3.1存储管理中分区分配算法的模拟 程序： 1.有大小恰好合适的空闲块 if(p-data.state==Freep-data.size==request) { p-data.state=Busy; p-data.ID=ID; return OK; break; } 2.有空闲块能满足需求且有剩余 if(p-data.state==Freep-data.sizerequest) { temp-prior=p-prior; temp-next=p; temp-data.address=p-data.address; p-prior-next=temp; p-prior=temp; p-data