I want to implement a simulation of a filesystem in C using a modified BST. Init

ID: 3664475 • Letter: I

Question

I want to implement a simulation of a filesystem in C using a modified BST. Initially, the filesystem is setup with a Owner(User name) and a root node: "yourname/root/." For simplicities sake, a file or a directory node will be the same struct (I have left, right, previous node pointers in the struct as well as a char pointer to the name of the file or directory, the first character of which indicates whether its a file 'F' or directory 'D.') The modified binary tree will look like this:

I would like to maintain alphabetized order and have anything above root inaccessible. So essentially after the simulation is set up (the user name node and root and created and linked), the goal is to be able to give UNIX-based terminal commands to create files and directories, and have them all insert, remove, copy, etc correctly based on the given command (mkdir <dirname>, ls (list all the files and directories in a given directory alphabetically), cp <fileordir1> <fileordir2>, etc.) I'm having a lot of trouble setting my pointers and alphabetically inserting nodes (files or dirs), as well as hard-copying a whole directory to a different location. Any help on this implementation? It is essentially a binary search tree where the directories are just linked lists (right pointers) to files and directories. If I can just get to the point where I can create nodes arranged alphabetically (as inserted, according to the pwd) and in the structure like the picture I think I can go from there. I previously posted with an incorrect picture of how the filesystem should look.

O User Node Root D = Directory F = File

Explanation / Answer

Implementation of structure depicted in the picture

struct TreeNode{
char data;
struct TreeNode *firstChild;
struct TreeNode *nextSibling;
};

Node* newNode(char ch)
{
TreeNode *tmp = new TreeNode();
tmp->data = ch;
tmp->firstChild = tmp->nextSibling = NULL;
return tmp;
}

TreeNode *root = newNode('U'); // user node
root->firstChild = newNode('R'); // root
root->firstChild->nextSibling = newNode('D'); // first D
root->firstChild->nextSibling->firstChild = newNode('D'); // child of first D

Maintaining Alphabetical Order during insertion

void insertAtSameLevel(char data)
{
if(!root) { root = new TreeNode(data); return; }

Node* insertIterator = root;
Node* parent = 0; // to store previous node
bool inserted = false;

while(insertIterator)
{
parent = insertIterator; // previous node stored in parent
if(data < insertIterator->data){
TreeNode *tmp = newNode(data);
tmp->nextSibling = parent->nextSibling->nextSibling;
parent->nextSibling = tmp;
inserted = true;
break;
}
}
if(!inserted){
TreeNode *tmp = newNode(data);
insertIterator->nextSibling = tmp;
}
}

Above function can be modified to handle more cases of insertion.

Based on the diagram given above. I am not able to understand how have you planned to track the file names. Thus the above code handles only the character associated with them.

Please comment on the solution if you have any query.

Navigate

I want to implement a simulation of a filesystem in C using a modified BST. Init

I want to implement dependent drop-down feature on a web page in my website cont

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

I want to implement a simulation of a filesystem in C using a modified BST. Init

Question

Explanation / Answer

Related Questions

Navigate