文件系统[HDU-1413]

文件系统 HDU-1413 HDU 2006-5 Programming Contest

https://vjudge.net/problem/HDU-1413
时间限制 1000ms 内存限制 32MB

这道题主要是直观上给出一个简单文件系统的树状印象，其实还是属于简单的数据结构题，做的话构造一棵根目录为根节点的有向树就可以。不外乎要注意一些细节上的处理。

我这里把文件和目录分开来处理了，对于这个问题而言是较为简单的做法，但是实际的文件系统实现可能是将目录也看作特殊的文件进行处理。而且文件表在磁盘上的存储方式并非简单的树，因为一个文件必须要考虑到充分利用磁盘空间，也就是一个文件可能存储在磁盘的不同位置上。这个树只是一个分区内文件的逻辑结构。鉴于现在还没学习操作系统课程，不好作深入探讨，只能就此打住。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<set>
  4 #include<map>
  5 #include<string>
  6 using namespace std;
  7 struct folder
  8 {
  9     string name;
 10     map<string, folder*> folders;
 11     folder * parent;
 12     set<string> files;
 13     folder()
 14     {
 15         parent = NULL;
 16     }
 17     folder(string & fn, folder * pnt)
 18     {
 19         name = fn;
 20         parent = pnt;
 21     }
 22 };
 23 folder * init()
 24 {
 25     return new folder;
 26 }
 27 folder * newfolder(folder * curfolder, string & fname)
 28 {
 29     if (fname == ".." || fname == "\")
 30         return NULL;
 31     map<string, folder*>::iterator it = curfolder->folders.find(fname);
 32     if (it != curfolder->folders.end())
 33         return NULL;
 34     folder * tmpfld = new folder(fname, curfolder);
 35     curfolder->folders.insert(pair<string, folder *>(fname, tmpfld));
 36     return tmpfld;
 37 }
 38 folder * delfolder(folder * curfolder, string & fname)
 39 {
 40     map<string, folder*>::iterator it = curfolder->folders.find(fname);
 41     if (it == curfolder->folders.end())
 42         return NULL;            //not found
 43     folder * fld = it->second;
 44     if (!fld->files.empty() || !fld->folders.empty())
 45         return NULL;            //has sub folders or files
 46     delete it->second;
 47     curfolder->folders.erase(it);
 48     return curfolder;
 49 }
 50 folder * gotodir(folder * root, folder * cur, string &fname)
 51 {
 52     if (fname == "\")
 53         return root;
 54     if (fname == "..")
 55     {
 56         if (root == cur)
 57             return root;
 58         else
 59             return cur->parent;
 60     }
 61     map<string, folder*>::iterator it = cur->folders.find(fname);
 62     if (it == cur->folders.end())
 63         return NULL;            //not found
 64     else
 65         return it->second;
 66 }
 67 int newfile(folder * curfolder, string & fname)
 68 {
 69     set<string>::iterator it = curfolder->files.find(fname);
 70     if (it != curfolder->files.end())
 71         return -1;
 72     curfolder->files.insert(fname);
 73     return 0;
 74 }
 75 int delfile(folder * curfolder, string & fname)
 76 {
 77     set<string>::iterator it = curfolder->files.find(fname);
 78     if (it == curfolder->files.end())
 79         return -1;
 80     curfolder->files.erase(it);
 81     return 0;
 82 }
 83 int main()
 84 {
 85     folder * root = init();
 86     folder * current = root;
 87     string op;
 88     while (cin >> op)
 89     {
 90         string fname;
 91         cin >> fname;
 92         if (op == "CD")
 93         {
 94             folder * tmpresult = gotodir(root, current, fname);
 95             if (tmpresult == NULL)
 96                 cout << "no such directory" << endl;
 97             else
 98             {
 99                 cout << "success" << endl;
100                 current = tmpresult;
101             }
102         }
103         else if (op == "MD")
104         {
105             if (newfolder(current, fname) == NULL)
106                 cout << "directory already exist" << endl;
107             else
108                 cout << "success" << endl;
109         }
110         else if (op == "RD")
111         {
112             if (delfolder(current, fname) == NULL)
113                 cout << "can not delete the directory" << endl;
114             else
115                 cout << "success" << endl;
116         }
117         else if (op == "CREATE")
118         {
119             if (newfile(current, fname) == -1)
120                 cout << "file already exist" << endl;
121             else
122                 cout << "success" << endl;
123         }
124         else if (op == "DELETE")
125         {
126             if (delfile(current, fname) == -1)
127                 cout << "no such file" << endl;
128             else
129                 cout << "success" << endl;
130         }
131     }
132     return 0;
133 }