模拟文件目录系统-CatalogTree

使用树结构实现一个简单文件目录系统的模拟程序

数据结构：目录树CatalogTree

代码地址:Tcoder-l3est/DataStructureCourseProject: 山东大学数据结构课设 (github.com)

基础数据结构

使用的数据结构是

带父节点指针的二叉树—兄弟链表

每个节点是一个目录项，每个叶节点是一个文件（也有可能是空目录）。

示意图

结点结构

struct Node
{
	Node* parent;//每个节点都要记录父节点
	Node* LeftChild;//只记录第一个孩子
	Node* sibiling;//平级向后连
	int file_type;//0文件 1目录
	string file_name;//文件或者目录名字
	ll fnum;//子文件数目
	ll file_size;//该文件大小
	
	//针对目录文件来说的
	ll all_mx;//目录配额 和 后代配额
	ll son_used;//所有的孩子占的大小

	char power;//权限

	Node(int type, string fname, ll size = 0) {
		file_type = type; file_size = size;
		fnum = 0;
		parent = NULL; LeftChild = NULL;
		sibiling = NULL;
		file_name = fname;
		all_mx = 0;
		son_used = 0;
		power = 'p';//r是管理员权限
	}
	~Node() {  }
	bool pre_add_size(ll size) {//预分配 文件
		if (all_mx && son_used + size > all_mx)
			return false;
		return true;
	}
	void add_size(ll size) {//预分配成功才进入这个
		son_used += size;
	}
	void get_size() {
		if (file_type == 0) {
			cout <<"文件大小: "<<file_size<<"\n";//文件
		}
		else
		{
			cout << "目录配额大小: " << all_mx << " 使用了 " << son_used << "\n";
		}
		
	}
	bool set_size(ll all) {//分配一个配额 只对目录有用
		if (all < son_used) return false;

		return true;
	}

};

定义指针指向父节点、左孩子、兄弟节点

定义文件或者目录名字，以及类型

针对目录文件：实现带配额的也就是模拟磁盘大小的功能，添加了目录配额**$all\_mx$**

以及所有孩子占的磁盘大小 $son\_used$

**$power$**实现角色的权限控制

树结构

class CatalogTree
{
private:
	Node* root;
	Node* CurNode;//当前位置
	char my_power;
public:
	CatalogTree();
	~CatalogTree() { delete root; };

	string outname;
	string inname;
	ifstream ffin;
	ofstream ffout;
	int put_flag;//输出在cmd 还是 file
	
	//基础
	void dir();//列出当前目录下的所有子目录和文件项
	void cd();//累出当前目录的绝对路径
	void cd_recur(Node* now);
	void cd_back();//当前目录变为当前目录的父目录。
	void cdstr(string& str);//当前目录变为STR所表示路径的目录
	void mkdir(string& str);//在当前目录下创建一个子目录str，如果存在则不进行任何操作
	void mkfile(string& str);//在当前目录下创建一个文件，若存在不进行。
	void delet(string& str);//删除当前目录下名字为STR的目录或者文件，如果不存在，不进行操作
	void deletenode(Node* now);
	void save(string& str);//将从根节点开始的目录树结构保存到文件中
	void save_recur(ofstream& fout, Node* now, int depth);//递归保存
	void load(string& str);//从文件STR中读取之前保存的目录树结构，并且根据其重新建立当前的目录树
	void load_recur(ifstream& fin, int depth);
	void read_data(int num);
	
	//size
	void mkfile_size(string& str, ll size);//make file with 大小限制  str相对路径
	void setdir_size(ll all_mx);//给当前 原有的 目录文件设置配额
	void remove_size(string& str);//删除文件或者目录
	
	//其他
	void cd_root();//回到root
	void mkdir_p(string& str);//自行创建多层目录
	void put_size() { CurNode->get_size(); }//获取当前目录的配额

   //权限
	void _r() { my_power = 'r'; }
	void _p() { my_power = 'p'; }
	void mkdir_r(string& str);//创建带权限的目录
	void mkfile_r(string& str);//创建带权限的文件
	void delet_r(string& str);
	
	
    //拓展文件操作
	//剪切
	void mv_a2b(string &a,string &b);//从a移动到b
	//复制
	void cp_a2b(string& a, string& b);//把当前目录下的a 复制到b下 b下不能有重名的
	void cp_r(Node *t);//递归拷贝节点
};

私有成员

​ 包括根节点、定义了一个$CurNode$来表示当前正在哪个目录下，哪个节点中，以及一个my_power 来检查处于文件系统的角色的权限是什么样的。

公有成员

​ $outname、inname$是用来输入输出的，配合$ffin和ffout$使用，$pu{t}_{f}lag$是决定输出在$cmd$ 还是$ file$

---

实现了以下指令：

基础

• dir —— 列出当前目录下的所有子目录与文件项，所有文件项后加*表示“这是一个文件”，没有则不输出；

• cd —— 列出当前目录的绝对路径。

• cd .. —— 当前目录变为当前目录的父目录 。

• cd str —— 当前目录变为 str 所表示路径的目录。

• mkdir str ——在(当前目录下)创建一个子目录(名为 str)，若存在则不进行任何操作。

• mkfile str ——在(当前目录下)创建一个文件(名为 str) ，若存在则不进行任何操作。

• delete str ——删除(当前目录下)名为 str 的目录或文件，若不存在则不进行任何操作。

• save str—— 将从根节点开始的目录树结构保存到文件(名为str)中。

• load str —— 从名为的文件str中读取之前保存的目录树结构，并根据其重新建立当前目录树，并进行后续操作

• quit —— 退出程序

拓展

权限操作:

• -r —— 系统权限变为root

• -p—— 系统权限变为p

• mkdir-r—— 创建一个权限为R的目录

• -mkfile-r str—— 当前目录下创建一个名为str目录，权限为r

• -delete-r str—— 以root权限,删除当前目录下名为str的目录或文件

配额操作:

• mkfile-s str—— 在当前下创建大小为size,名为str的文件

• Q size—— 在当前下创建大小为size,名为str的文件

• remove str—— 删除绝对路径str最后一个文件以及目录

• show—— 展示当前目录的配额大小以及使用情况或文件的大小

文件操作:

• mv a b—— 把当前路径下的a剪切到绝对路径b下

• cp a b—— 把当前路径下的a复制到绝对路径b下

其他操作:

• mkdir-m str—— 根据输入的str绝对路径，生成多级目录(类似于touch)

---

部分实现思路

基础

void dir()的设计思路：

列出当前目录下的所有子目录和文件项,只需要对当前路径的子节点扫描一遍输出即可。void cd()的设计思路：

列出当前目录的绝对路径,需要递归实现，首先迭代到根节点，开始输出文件名称，之后递归回来，就完成了路径的输出！

void cd_back()的设计思路：

进入当前路径的父节点即可实现后退操作。

Void cdstr(string& str)的设计思路：

当前目录变为STR所表示路径的目录,首先判断是绝对路径还是相对路径，绝对路径从根开始进入即可，相对路径返回父节点后再进入就行。

void mkfile/mkdir(string& str)的设计思路：

当前目录下创建一个目录或者文件节点，只需要先检查是否已经存在该种目录或者文件，如果没有则新建节点，设置大小后，插入即可。

void delet(string& str)的设计思路：

删除当前目录下名字为STR的目录或者文件，如果不存在，不进行操作.

先扫描找到该节点，之后如果是文件直接删除并且修改指针，如果是目录就递归删除，所有子目录子文件.

void save(string& str)的设计思路：

将从根节点开始的目录树结构保存到文件中,借鉴windows里面 tree命令，进行递归存储，即从根节点开始，如果有目录就进入目录递归保存，根据不同的level 前面加不同个’|’ 来标志，如果是目录则储存为 |后加’-’表示为目录.

最后保存CUR表示当前节点，之后存END表示结束标识符

下图是windows Tree命令 以及 模拟的Tree命令

void load(string& str)的设计思路：

从文件读入 把目录树建立起来,与load思路相同，最后要设置curnode扫描节点,读到cur设置curnode，读到end停止。

拓展

文件操作拓展

void mv_a2b(string &a,string &b)的设计思路:

​ 进行剪切文件的操作,传入当前目录下的一个文件或者目录a 然后绝对路径b，把a移动到b下面，如果是根则不能移动，如果有权限不符合的则直接返回权限不够。文件可以直接移动，目录递归移动，不需要删除源节点，只需要对指针进行修改。

一定要拒绝父节点 剪切到子节点的操作！

void cp_a2b(string& a, string& b) 的设计思路:

​ 进行文件的复制操作，把当前目录下的a 复制到b下 b下不能有重名的，文件直接复制，目录递归复制，如果是根则不能复制，如果有权限不符合的则直接返回权限不够，最后不能简单修改指针，不然会导致紊乱，必须要新建节点。

权限拓展

void mkdir_r/mkfie_r(string& str)的设计思路:

创建一个权限为r（root）的目录、文件，如果当前权限不为r则无法删除 或者进行其他操作。

void delet_r(string& str)的设计思路：

利用以管理员身份删除对应文件或者目录。

配额拓展

void mkfile_size(string& str, ll size)设计思路：

在当前路径下创建一个大小为size的文件，需要检查是否满足文件大小配额要求，所以需要检查当前目录结构是否有足够的空间。其次检查是否有重复文件。建立完成之后，加入该文件并且修改对应的目录的配额剩余。

void setdir_size(ll all_mx)思路：

给当前 原有的 目录文件设置配额,必须要满足当前文件是目录文件并且分配的配额大小满足最小的文件限制，否则就分配不成功。

void remove_size(string& str)设计思路：

先检查删除的是文件还是目录，文件的话直接删除，并且修改目录的配额即可。

如果是目录，则需要修改父目录的配额，并且递归删除所有文件、目录。

其他拓展

void cd_root()的设计思路:

回到根目录

void mkdir_p(string& str)的设计思路:

对于输入的绝对路径，如果走到了现在目录的最后一个目录仍有路径没有走完，则自动创建对应的目录，自动实现多层目录的访问以及补全。

void put_size()

获取当前目录的配额

---

分析

时间复杂度

对于从根向下进行搜索的操作的复杂度都是平均O(logn)，最差O（n）即一个链表的情况。

对于递归的操作则是O(n) 因为要对所有节点进行操作。

要修改父目录的配额，并且递归删除所有文件、目录。

其他拓展

void cd_root()的设计思路:

回到根目录

void mkdir_p(string& str)的设计思路:

对于输入的绝对路径，如果走到了现在目录的最后一个目录仍有路径没有走完，则自动创建对应的目录，自动实现多层目录的访问以及补全。

void put_size()

获取当前目录的配额

---