多级层次结构：
 
是从使用语言的角度，基于程序员与计算机系统对话中所采用的语言结构和语义划分。
 
现代计算机系统的层次结构分为六级：
 
 
多级层次结构中（机器—语言）
 
M5: 应用语言机器 – 应用语言 
 M4: 高级语言机器 – 高级语言 
 M3: 操作系统机器 – 作业控制语言 
 M2: 汇编语言机器 – 汇编语言 
 M1: 传统机器 – 机器指令系统 
 M0: 微程序机器 – 微指令系统
 
 
编译与解释的区别：
 
编译（compile）：全部N+1级指令–>N级指令 
 解释（translation）：一条N+1级指令 –> 一串N级指令
 
编译为整体行为，效率高，可以优化，与平台有关 
 例如：C，C++,Fortran等
 
解释为局部行为，不优化，效率低，与平台无关 
 例如:basic,perl,shell等
 
编译+解释： 
 例如：java，编译->bytecode->解释执行
 
说明： 
 M0用硬件，M1用固件，其他用软件
 
固件（Firmware）:指存储在计算机ROM和其他集成电路中的系统软件，固件不能随便改变。
 
低层语言功能简单，高层语言功能复杂。
 
虚拟机器：用软件为主实现的机器，例如java虚拟机

一、课程设计的内容
 本课程设计要求设计一个模拟的多用户多级目录的文件系统。通过具体的文件存储空间的管理、文件的物理结构、目录结构和文件操作的实现，加深对文件系统内部功能和实现过程的理解。
 二、课程设计的要求与数据
 1． 在内存中开辟一个虚拟磁盘空间作为文件存储器，在其上实现一个多用户多目录的文件系统。
 2． 文件物理结构可采用显式链接或其他方法。
 3． 磁盘空闲空间的管理可选择位示图或其他方法。如果采用位示图来管理文件存储空间，并采用显式链接分配方式，则可以将位示图合并到FAT中。
 4． 文件目录结构采用多用户多级目录结构，每个目录项包含文件名、物理地址、长度等信息，还可以通过目录项实现对文件的读和写的保护。目录组织方式可以不使用索引结点的方式，但使用索引结点，则难度系数为1.2。
 5． 设计一个较实用的用户界面，方便用户使用。要求提供以下相关文件操作：
 （1）具有login (用户登录)
 （2）系统初始化（建文件卷、提供登录模块）
 （3）文件的创建： create
 （4）文件的打开：open
 （5）文件的读：read
 （6）文件的写：write
 （7）文件关闭：close
 （8）删除文件：delete
 （9）创建目录（建立子目录）：mkdir
 （10）改变当前目录：cd
 （11）列出文件目录：dir
 （12）退出：logout
 
 
一、设计思想说明
 
1.1设计环境
 a、编程语言：C++
 b、开发环境：DEV
 c、操作系统：windows 10
 
1.2 设计思想
 1.2.1整体思路
 本次课程设计是一个模拟的多用户多级目录的文件系统，可以支持多用户注册、登录、注销，支持多级目录，文件按名存取，支持文件的增删查改，使用FAT显示链接保存文件在磁盘的分配，使用位示图保存磁盘块的使用情况。
 整个项目主要内容分为三个模块的开发：一是用户模块，二是文件模块，三是磁盘模块。
 1.2.2 用户模块
 用户模块内容主要包括初始化建立管理员账号、注册账号、登录验证、退出登录、删除账号、打印所有用户等功能。
 使用账号头指针admin将所有的账号链接起来，为所有的用户创建一个同名用户文件夹，该账号下的所有文件操作都在该文件夹下执行。
 用户指针保存用户名、用户密码、指向下一个用户的指针和指向账号文件夹的指针。
 1.2.3 文件模块
 文件模块内容主要包括创建文件（文件夹或文件）、创建文件的索引结点、进入文件夹、读文件、写文件、删除文件、删除文件夹、回退到上一个文件、打印所有目录、打印当前文件夹目录等功能。
 采用树形结构目录存储文件目录，并使用孩子兄弟链表法存储表示。
 定义一个账号文件夹头指针admin_folder，所有的用户文件夹都存储在该文件夹下，其是一个实际不存在的文件夹。即admin_folder->child结点指向第一个用户文件夹root，root的brother指向其他用户文件夹。
 定义一个当前文件夹指针now_folder，用来指向当前所在的文件夹。
 树形文件目录中保存文件名、文件类型、和索引结点，索引结点中保存文件大小、文件在磁盘中的第一个盘块号等具体文件信息。
 1.2.4 磁盘模块
 磁盘模块主要保存初始化磁盘、初始化FAT表、在FAT中查找空闲盘块、打印位示图等功能。
 FAT表中保存当前盘块号、下一个盘块号和位示图，物理盘中保存磁盘块号、块大小和存储内容。
 用一个block[block_count]数组模拟磁盘，建立一个等大的fat[block_count]数组保存FAT。
 
二、系统结构
 
2.1 结构联系
 系统大体分为三层，最顶层是用户层，包含对账号的操作等功能，只有登录了之后才能进行文件层的文件操作，每个用户账号都拥有一个用户文件夹。
 文件层可以进行对文件的操作，比如创建和读写删等操作，但不允许删除根目录用户文件夹，树形文件目录中仅保存文件名和索引节点。
 物理层中存储磁盘的使用情况和文件内容，使用FAT显示链接将文件链接起来，通过FAT表查找到文件在磁盘的块号，在磁盘块中读出文件的内容。
 

 
 
三、数据结构的说明
 
3.1 user_management
 typedef struct mfd { // 主文件目录，存储用户文件夹
 string username; //用户名
 string password; //用户密码
 struct mfd next; //指向下一个用户的指针
 TSD link; //指向该用户的文件目录指针
 }MFD;
 3.2 file_management
 typedef struct tsd { //树形文件目录 
 string name;
 short type; //文件类型，文件夹或者文件
 struct tsd father; //父节点指针
 struct tsd child; //孩子节点
 struct tsd* brother; //兄弟节点
 INDEXES* indexes; //索引结点
 }TSD;
 
typedef struct indexes{ //索引结点
 short capabilities; //访问权
 int size; //占用空间
 int first_block; //文件物理地址（盘块号）
 }INDEXES;
 
3.3 disk_management
 typedef struct fat { //文件分配表
 bool bitmap; //位示图
 int id; //当前盘块号
 int next_id; //下一个盘块号
 }FAT;
 
typedef struct block { //磁盘
 int id; //物理块号||盘块号
 unsigned int s_BLOCK_SIZE; 
 string content; //存储内容
 }BLOCK;
 
四、算法流程图
 
 
五、主要函数列表
 
 
六、 测试与分析
 
1.初始界面
 
 2. 文件夹的创建和进入文件夹
 
 3.创建文件和对文件的读写和删除文件
 
 
 
返回上一层目录和删除文件夹
 
 
 
打印目录
 
 
 
打印位示图
 
 
 
七、 用户使用说明
 
本系统内置一个管理员账号root，密码root，在初始界面登录或者进行账号管理。
 登录系统后可以按照提示进行文件操作
 create [file name] 创建文件
 read [file name] 读文件
 write [file name] 写文件
 delete [file name] 删除文件
 mkdir [dir name] 创建子文件夹
 cd [dir name] 进入子文件夹
 rd [dir name] 删除文件夹
 dir 打印当前目录下文件
 dir_all 打印所有文件
 show 打印位示图
 retreat 回退到上一级文件夹
 logout 退出登录
 help 提示
 
在账号管理时，可以按照提示输入对应的数字来选择操作
 
 
八、附录
 

之前做过一个多级ListView的多级目录结构，终于有闲时间来分享了。先看效果图吧： 
 
 
常规做法
 
　　ListView为多级的显示方式，与此类似的有文件系统、省市区分级等等，类似于B树。 
 　　其数据结构一般如下可能： 
 　　A. 通过索引连接树的节点，主要特点如下： 
 　　某一点通过索引将所有点联系，类似于链表，任何两点间没有直接关系，如果要得到某个点需要算法和当前表/总表来遍历。存储效率高/内存占用少但遍历较耗时。 
 　　 
 　　 
 　　B. 直接连接树的节点，主要特点如下： 
 　　某一点通过实体类联系所有点，类似于多个数组，任何两点之间都有关系，任何一点都是一个树，如果需要得到某个点，只需要通过算法遍历subLayer/parentLayer即可。占用额外内存但遍历快速（只需要从当前节点开始遍历，不需要节点字典）。 
 　　
核心代码 
 　　 
 　　树结构的核心算法主要是查找了吧。大学的时候做过一个双向带权图的公交网络。 
 　　如果采用做法A，那么主要代码如下（偷懒一下，就用递归吧）： 
 　　 
 　　1.查找子节点：
 
    /**
     * @param node      当前节点
     */
    public static List<Node> getAllChilds(Node node, List<Node> checkCollection) {
        List<Node> allChildNode = new ArrayList<>();
        if (null != node) {
            List<String> childid = node.getSubLayerIds();
            if (null != childid)
                for (String id : childid) {
                    Node child  = LeftNodeUtil.getNodeById(id, checkCollection);
                    if (null != child) {
                        if (null != allChildNode) {
                            allChildNode.add(child);
                        }
                    }
                    if (null != child && !child.isLeaf()) {
                        getAllChilds(child, allChildNode, checkCollection);
                    }
                }
            else {
                LogManage.e("OneMapActivity", "节点未找到，为空！");
            }
        }
        return allChildNode;
    }
 
    /**
     * @param node 当前节点
     * @param checkCollection 节点字典
     */
    public static List<Node> getAllParent(Node node,  List<Node> checkCollection) {
        List<Node> allParentIds = new ArrayList<>();
        if(null != node) {
            String parentId = node.getParentLayerId();
            Node pNode = getNodeById(parentId, checkCollection);
            if (null != pNode)
                allParentIds.add(pNode);
            if (null != parentId && null != pNode && !Constants.TOP_NODE_ID.equalsIgnoreCase(parentId)) {
                getAllParent(pNode, allParentIds, checkCollection);
            }
        }
        return allParentIds;
    }
 
public static Node getNodeById(String id, List<Node> list) {
        Node id_Node = null;
        for (Node node : list) {
            if (null != id)
                if (id.equalsIgnoreCase(node.getId())) {
                    id_Node = node;
                    break;
                }
        }
        return id_Node;
    }
 
 
　　到此OK，这就是多级ListView/RecycleView的实现了。（示例代码只是修改原有代码，可能有小问题，Copy&Past的同学请注意一下）

文件目录结构：单级、两级、多级(树形)和无环图目录结构
 
与文件管理系统和文件集合相关联的是文件目录，它包含有关文件的信息，包括属性、 位置和所有权等，这些信息主要是由操作系统进行管理。首先我们来看目录管理的基本要求: 从用户的角度看，目录在用户（应用程序）所需要的文件名和文件之间提供一种映射，所以目录管理要实现“按名存取”；目录存取的效率直接影响到系统的性能，所以要提高对目录的检索速度；在共享系统中，目录还需要提供用于控制访问文件的信息。此外，文件允许重名也是用户的合理和必然要求，目录管理通过树形结构来解决和实现。
 
文件控制块和索引结点
 
同进程管理一样，为实现目录管理，操作系统中引入了文件控制块的数据结构。
 
1) 文件控制块。
 
文件控制块(FCB)是用来存放控制文件需要的各种信息的数据结构，以实现“按名存取”。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。为了创建一个新文件，系统将分配一个FCB并存放在文件目录中，成为目录项。

 FCB主要包含以下信息：
 
基本信息，如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。
存取控制信息，如文件存取权限等。
使用信息，如文件建立时间、修改时间等。
2) 索引结点。
 
在检索目录文件的过程中，只用到了文件名，仅当找到一个目录项（查找文件名与目录项中文件名匹配）时，才需要从该目录项中读出该文件的物理地址。也就是说，在检索目录时，文件的其他描述信息不会用到，也不需调入内存。因此，有的系统（如UNIX，见表）釆用了文件名和文件描述信息分开的方法，文件描述信息单独形成一个称为索引结点的数据结构，简称为 i 结点。在文件目录中的每个目录项仅由文件名和指向该文件所对应的i结点的指针构成。
  
 

  UNIX的文件目录结构
 
文件名
索引结点编号
文件名1
 
文件名2
 
 
 
 
 

 一个FCB的大小是64字节，盘块大小是1KB，则在每个盘块中可以存放16个FCB（注意，FCB必须连续存放）。而在UNIX系统中一个目录项仅占16字节，其中14字节是文件名，2字节是 i 结点指针。在1KB的盘块中可存放64个目录项。这样，可使查找文件时平均启动磁盘次数减少到原来的1/4，大大节省了系统开销。

 存放在磁盘上的索引结点称为磁盘索引结点，UNIX中的每个文件都有一个唯一的磁盘索引结点，主要包括以下几个方面：
 
文件主标识符，拥有该文件的个人或小组的标识符。
文件类型，包括普通文件、目录文件或特别文件。
文件存取权限，各类用户对该文件的存取权限。
文件物理地址，每个索引结点中含有13个地址项，即 iaddr(0) ~ iaddr(12)，它们以直接或间接方式给出数据文件所在盘块的编号。
文件长度，以字节为单位。
文件链接计数，在本文件系统中所有指向该文件的文件名的指针计数。
文件存取时间，本文件最近被进程存取的时间、最近被修改的时间以及索引结点最‘ 近被修改的时间。
文件被打开时，磁盘索引结点复制到内存的索引结点中，以便于使用。在内存索引结点中又增加了以下内容：
索引结点编号，用于标识内存索引结点。
状态，指示i结点是否上锁或被修改。
访问计数，每当有一进程要访问此i结点时，计数加1，访问结束减1。
逻辑设备号，文件所属文件系统的逻辑设备号。
链接指针，设置分别指向空闲链表和散列队列的指针。
在理解一个文件系统的需求前，我们首先来考虑在目录这个层次上所需要执行的操作，这有助于后面文件系统的整体理解。
 
搜索：当用户使用一个文件时，需要搜索目录，以找到该文件的对应目录项。
创建文件：当创建一个新文件时，需要在目录中增加一个目录项。
删除文件：当删除一个文件时，需要在目录中删除相应的目录项。
显示目录：用户可以请求显示目录的内容，如显示该用户目录中的所有文件及属性。
修改目录：某些文件属性保存在目录中，因而这些属性的变化需要改变相应的目录项。

 操作时，考虑以下几种目录结构：
 
1) 单级目录结构。
 
在整个文件系统中只建立一张目录表，每个文件占一个目录项，如图所示。
 
 
当访问一个文件时，先按文件名在该目录中查找到相应的FCB，经合法性检查后执行相应的操作。当建立一个新文件时，必须先检索所有目录项以确保没有“重名”的情况，然后在该目录中增设一项，把FCB的全部信息保存在该项中。当删除一个文件时，先从该目录中找到该文件的目录项，回收该文件所占用的存储空间，然后再清除该目录项。

 单级目录结构实现了 “按名存取”，但是存在查找速度慢、文件不允许重名、不便于文件共享等缺点，而且对于多用户的操作系统显然是不适用的。
 
2) 两级目录结构。
 
单级目录很容易造成文件名称的混淆，可以考虑釆用两级方案，将文件目录分成主文件目录(Master File Directory, MFD)和用户文件目录（User File Directory, UFD)两级，如图所示。
 
 
主文件目录项记录用户名及相应用户文件目录所在的存储位置。用户文件目录项记录该用户文件的FCB信息。当某用户欲对其文件进行访问时，只需搜索该用户对应的UFD，这既解决了不同用户文件的“重名”问题，也在一定程度上保证了文件的安全。

 两级目录结构可以解决多用户之间的文件重名问题，文件系统可以在目录上实现访问限制。但是两级目录结构缺乏灵活性，不能对文件分类。
 
3) 多级目录结构（树形目录结构)。
 
将两级目录结构的层次关系加以推广，就形成了多级目录结构，即树形目录结构，如图所示。

 用户要访问某个文件时用文件的路径名标识文件，文件路径名是个字符串，由从根目录出发到所找文件的通路上的所有目录名与数据文件名用分隔符链接起来而成。从根目录出发的路径称绝对路径。当层次较多时，每次从根目录查询浪费时间，于是加入了当前目录，进程对各文件的访问都是相对于当前目录进行的。当用户要访问某个文件时，使用相对路径标识文件，相对路径由从当前目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成。
 
 
上图是Linux操作系统的目录结构，“/dev/hda”就是一个绝对路径。若当前目录为 “/bin”，则“./ls”就是一个相对路径，其中.符号表示当前工作目录。

 通常，每个用户都有各自的“当前目录”,登录后自动进入该用户的“当前目录”。操作系统提供一条专门的系统调用，供用户随时改变“当前目录”。例如，UNIX系统中， “/etc/passwd”文件就包含有用户登录时默认的“当前目录”，可用cd命令改变“当前目录”。

 树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是，在树形目录中查找一个文件，需要按路径名逐级访问中间结点，这就增加了磁盘访问次数，无疑将影响查询速度。
 
4) 无环图目录结构。
 
树形目录结构可便于实现文件分类，但不便于实现文件共享，为此在树形目录结构的基础上增加了一些指向同一结点的有向边，使整个目录成为一个有向无环图。引入无环图目录结构是为了实现文件共享，如图4-6所示。

 当某用户要求删除一个共享结点时，若系统只是简单地将它删除，当另一共享用户需要访问时，却无法找到这个文件而发生错误。为此可以为每个共享结点设置一个共享计数器，每当图中增加对该结点的共享链时，计数器加 1;每当某用户提出删除该结点时，计数器减1。仅当共享计数器为0时，才真正删除该结点，否则仅删除请求用户的共享链。
  
 

 图4-6  图形目录结构
 

 共享文件（或目录）不同于文件拷贝（副本）。如果有两个文件拷贝，每个程序员看到的是拷贝而不是原件；但如果一个文件被修改，那么另一个程序员的拷贝不会有改变。对于共享文件，只存在一个真正文件，任何改变都会为其他用户所见。

 无环图目录结构方便实现了文件的共享,但使得系统的管理变得更加复杂。