模拟文件系统多级.doc

多级文件目录管理 实训报告 --FileManager 院别：计算机学院 姓名：LDY 学号xxxxx 班级：计Y11x 广西科技大学大学 计算机学院 Creation time: 2013-1-8 17:44:25 目录 1实验目的 2 2实验内容 2 2.1实验题目：树状多级文件目录管理系统 2 2.2实验要求：功能实现 2 3设计分析 3 3.1数据结构分析：树形目录的存储、删除及树的显示 3 3.2 数据结构定义 7 3.3 功能分析和函数定义 10 4 功能总览 15 4.1 功能总览 15 4.2主要功能 15 5 实训总结 19 5.1 所遇困难 19 5.2 心得体会 20 1实验目的 本次实训的总体目的在于通过系统的编程训练，培养学生编写一个具有一定难度的小型系统的能力，培养学生从编写单个程序，实现单个程序功能到进行系统开发，整体调试的能力。从知识点的角度来说，目的在于通过本实训项目，让学生对链表或二叉树这一重要数据结构的运用更加熟练。 2实验内容 2.1实验题目：树状多级文件目录管理系统 本次实训的题目是树状多级文件目录管理系统。要求利用数据结构的知识，采用链表的形式或通过将树转换为二叉树的概念，采用孩子兄弟二叉树的方式实现文件目录系统。不容许采用数据库实现文件管理。每个树结点表示一个，成员基本信息，具体属性自行确定。firstchild域和nextsibling 域。 - - - - -树的二叉链表(孩子-兄弟)存储表示- - - - - typedef struct CSNode { ElemType data; struct CSNode *firstchild, * nextsibling; }CSNode, *CSTree; 图3.1树的孩子兄弟表示方法实例 图3.2 是图3.1 中的树的孩子兄弟链表。利用这种存储结构便于实现各种树的操作。首先易于实现找结点孩子等的操作。例如:若要访问结点x 的第i 个孩子，则只要先从firstchild 域找到第1 个孩子结点，然后沿着孩子结点的nextsbling 域连续走i-1 步，便可找到x 的第i 个孩子. 当然，如果为每个结点增设一个PA RENT 域，则同样能方便地实现PARENT(T ， x) 操作。 图3.2 图3.1的孩子兄弟表示 3.1.2基于二叉表的操作：新建、删除和显示等 ·新建(父目录指针为函数参数) ·目录为空，在父目录的左孩子新建节点 ·目录不为空，在父目录下的最后兄弟(最后创建时间)新建节点挂在最后兄弟右兄弟上。 图3.3 孩子兄弟存储：新建文件夹/文件数字表示创建顺序 实现：传递上级目录节点(父节点)，判断父节点左孩子是否为空，为空则生成左孩子，不为空，则沿着左孩子的右兄弟寻找(将右兄弟作为链表移动到最后一个节点)，直到遇到为最后兄弟，生成一个右兄弟挂在最后兄弟上。 ·删除(销毁) ·单个文件，直接删除节点，释放内存 ·文件夹，删除文件夹下内容，注意要释放内存。 图3.4 孩子兄弟存储：删除文件夹/文件 实现：传递上级目录节点(父节点)，判断父节点左孩子是否为空，为空时不用处理，不为空时用提供的名字(其它信息)，在右兄弟组成的链表中(只看该目录下右指针相连的节点)寻找到要删除节点。 以父目录指针的左孩子指针为链表第一个节点遍历，有两种情况： 1第一个节点恰是删除节点 判断该节点左孩子指针是否为空，为空则说明这是文件或文件夹下无内容，直接删除（释放内存），将右指针挂到父目录左孩子上。 2第二个节点不是删除节点 继续往该节点右指针遍历，找到节点后判断该节点左孩子指针是否为空，为空则说明这是文件或文件夹下无内容，直接删除（释放内存），将右指针挂到上一个节点上。 补充文件夹删除方法：采用后序删除，将删除节点的指针传递到递归后序删除函数，能将其下节点全部释放内存，最后将本身删除。(注意保存该节点的上一个兄弟和下一个兄弟，如果有) ·显示：主要是二叉树的遍历问题 引例：于下图的一棵孩子兄弟二叉树 图3.5 二叉树的显示 树形式表示 图3.6 图3.5形成的树 ·层次显示：给出文件夹节点，遍历该节点右兄弟连接形成的单链表 ·第一层次(根目录层次，无分支情况)：给出根节点，左孩子节点作为该目录下第一个文件夹/文件，沿着其找遍右兄弟，直到不存在右兄弟为止(NULL) ·第二层次(上图中，有三种分支)：对于对于根目录下每个兄弟节点分别作为根节点，若存在左孩子，重新找遍节点下的右兄弟，直到找不到为止 ·第三层次：同上 ···· 注意：应当是每次都只能显示一个层次中某一目录(一个文件夹)下全部内容 实现：给出一个文件夹作为目录根节点，判断其是否存在左孩子，存在则沿着左孩子的右兄弟链