1 Replies - 4100 Views - Last Post: 27 August 2015 - 10:30 AM

#1 lamentofking   User is offline

  • D.I.C Head

Reputation: 5
  • View blog
  • Posts: 233
  • Joined: 03-July 13

Tree Class for Virtual File System?

Posted 17 July 2014 - 06:39 PM


I need to simulate a Virtual File System in C++, which I will also give GUI functionality (in other words, I'll be using C++ CLI). I'm having a little trouble designing a class for such a task though...partly because the structure that I believe I need to use (Trees) isn't a class so there aren't any built-in header functions that I can use (unless I missed something and there are). The problem description follows below:


You are to simulate accessing a virtual file system.

First create three separate "drives" A, B, and C. Each is to have it's own
tree structure with directories and common files. Restrict the number of
files under each directory to no more than five. Each common file is to have
it's own i-node which need contain only filename, extension, and one line of
UNIQUE data (in lieu of a pointer to the data on "disk"). For simplicity,
do not make the depth of any directory tree exceed four levels.

On top of these file systems build a VFS that makes the three separate systems
appear as one big system. All user accesses should be via the VFS through
the v-nodes that are provided. The only functions that the VFS is to provide
is add a new file, delete a file, and "print"(show the one line of data) a
file. You must demonstrate all three operations and show the user's view of
the file structure, as well as, the actual file system structure before and
after each operation.

As before, all commands are to be entered via a GUI except that a data
file may be used to build the initial system (instead of entering the
pieces one file at a time).

So after reading the description I can see that the way to go would be to use Trees...partly because I see the word "node" in the description as well as directory tree. Now I did find some user-defined Binary Search Tree classes implemented around the internet but I couldn't use a BST because each node can only have up to 2 children and I need to be able to have up to five files(children) in a directory. So if a BST node struct is defined as follows:

template class <T>
struct Node
 T data
 Node* lhs
 Node* rhs

Then for a non-BST node struct can't I just add node pointers inside my struct for as many children I would need in each node? Is there any reason why I shouldn't do that? I didn't want to assume that a non-BST node struct was as simple as adding more pointers.

Is This A Good Question/Topic? 0
  • +

Replies To: Tree Class for Virtual File System?

#2 magicleon   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 13-August 15

Re: Tree Class for Virtual File System?

Posted 27 August 2015 - 10:30 AM

Yeah, it is. It's just adding more children nodes and having the proper functions to use them.
Nothing says you can't allow your tree to have five or more (or less) children.
You could have a class "node" with five pointers to "node" and so on.

Probably you have found only BST because (i'm supposing) it's the most efficient use for binary trees, because the computational cost for search (and insert too, i think) is log(n) (base 2).
Having a non binary tree causes a variation of it, but for the use you need i think it's good (actually i cannot think a way of implementing a directory tree with binary trees).
So you could have a 5 (N) children tree, no problem. You just have to build the proper methods to access the files. Other than that is a normal tree, of course!

I remind of a data structure that uses trees with more children (i can't remember what is at this time though...),

View Postmagicleon, on 27 August 2015 - 10:25 AM, said:

I remind of a data structure that uses trees with more children (i can't remember what is at this time though...)

I googled that. The data structure is the Pairing Heap.
Its uses are different for your needs, but hey, they exist!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1