An important exam!

[Zael]

Greetings, I have an enormous problem and it needs to be solved, one way or another. I understand that much of you don't have time to write code on your own, so it would be selfish to expect served-plate. I beg for instruction or at least a direction. Thx

I have to make program using C:
It's about a tree, a simple hiearchy tree which consists of two things, directories and document.. It's not a binary tree, and in the console user is supposed to be asked about:
- creating a first subdirectory or document (First Child)
- creating the next subdirectory or document (Next brother)
- deleting directory or document
- listing the contents of directory
- function preorder

I started to search for help over the internet 2 weeks ago, but all I found was some C++ example which i don't understand. I also found examples of binary tree but they simply don't fit in our case. Any help would be appreciated. Sorry if I said something wrong, English is not my primary language..

[dargueta]

On the contrary, your English is very good. I never would've guessed. I too am working on something similar. From what you posted, it seems that you want to emulate the folder tree system that Windows uses, e.g. "C:\Windows\MyFolder" and "C:\Windows\File.txt" have the same parent directory, etc. So you want to create a structure that holds information for each level in the tree, and create a linked list from those:

Assume Document is a class that contains document data.
This creates a structure that holds two arrays: one of the next level of subfolders if any, and another of the documents in that folder. So, if a folder "F" had two folders called "A" and "B" and a text document called "text.txt" in it, there would be two elements in the subFolders array, and one in the documentsInThisFolder array. Note that if Document is a structure and not a class, then numberOfDocuments is just an array of Documents and not an array of pointer to Documents, and therefore should be declared "Document *documentsInThisFolder;".

struct Folder
{
    unsigned int numberOfSubFolders;
    Folder *subFolders;
    unsigned int numberOfDocuments;
    Document **documentsInThisFolder;
};

Using this format, you can create one base folder, and as many subfolders and documents as memory will allow. To add/delete folders and elements, I suggest that you make Folder and Document a class and provide functions to do this. Make sure that you free any memory or objects you allocate. Did that help?

[Zael]

First of all, thank you for answering...

You were correct about guessing the point of my exam. Anyway, it doesn't have to be so realistic. I decided to PrintScreen and example of an imagined tree. I just need few functions to define tree. You mentioned a linked list, and it really is a good solution. The think is I'm not supposed to create a text (document) as a structure. Perhaps it can simply be declared as a character array:

char Document[12] = "document.txt"; 

[WingedPanther]

You can actually use a binary tree to handle this. The data would contain: name, child pointer (if directory), brother pointer, directory flag. A node is a directory if the directory flag is set. The directory points to the first file/directory with the child pointer. The attached Jpg is an example of your directory as a binary tree.

[dargueta]

WingedPanther: If I understand you correctly, one would have to sort through a list of structures to find one document in the array of children, which contains both folders and documents. I think it'd be easier to keep them separate, i.e. faster to search through. Your idea does make things somewhat simpler, though.

[Zael]

I don't understand how is it possible to solve this problem with binary tree if it has to be possible that one folder can consist of many subfolders and documents (not only 2, which is the main idea of binary tree)???

I've been trying to do anything, and my time is running out if I knew anyone here In Zagreb (Croatia) I would already pay and try to understand the code on my own. As far as it goes, i'll get nowhere, and the teacher won't let me go on easy as it seams.. 2 weeks and I still got nowhere, sounds bad as hell. If someone could make this program for me, I would be mostly grateful.

Anyway thx for enormous help

[dargueta]

I think WingedPanther misunderstood something, because now that I think about it, a binary tree isn't the best approach. Forget about that. (Sorry, WP). Can I see what you have written so far? Maybe I can help you better then.

[Zael]

#include <stdlib.h>
#include <stdio.h>
#define MAXNODES 20      //Can be lowered or raised as desired
typedef int labeltype;
typedef int node;
 
typedef struct{
        labeltype label;
        node first_child, next_sibling;
} node_struct;
 
typedef struct{
      node_struct space[MAXNODES];
      node empty;
      } prost;
 
node INITIALIZE(prost *pr){
    int i;
    for (i=0;i<MAXNODES-1;i++){
        pr->space[i].next_sibling=i+1;
        }
    pr->space[MAXNODES-1].next_sibling=-1;
    return 0;
    }
 
node NEW_TREE(labeltype label, prost *pr){
    node temp;
    temp=pr->empty;
    pr->empty=pr->space[pr->empty].next_sibling;
    pr->space[temp].first_child=-1;
    pr->space[temp].next_sibling=-1;
    pr->space[temp].label=label;
    return temp;
}
 
node FIRST_CHILD(labeltype label, node parent, prost *pr){
    node temp;
    temp=pr->empty;
    pr->empty=pr->space[pr->empty].next_sibling;
    pr->space[parent].first_child=temp;
    pr->space[temp].first_child=-1;
    pr->space[temp].next_sibling=-1;
    pr->space[temp].label=label;
    return temp;
}
 
node NEXT_BROTHER(labeltype label, node brother, prost *pr){
    node temp;
    temp=pr->empty;
    pr->empty=pr->space[pr->empty].next_sibling;
    pr->space[brother].next_sibling=temp;
    pr->space[temp].first_child=-1;
    pr->space[temp].next_sibling=-1;
    pr->space[temp].label=label;
    }
 
int main(void){
 
// ????????
 
    system("pause");
    return 0;
    } 

The bad thing is it doesn't contain Main Function (is empty) but the functions are correctly written and can be used. I just needed several minutes to name the variables on the international level (Trust me, you don't wanna read Croatian code ). I'm not sure if this is going to help, but last 2-3 weeks I'm trying by modifying this code.

[dargueta]

Okay, so your problem is that you don't know how to add and remove folders, print out contents, etc.?

Issues with your code:
(1)NEXT_BROTHER doesn't return anything. What is it supposed to return?
(2)Your code is very unclear. Comments would be nice.

A few pointers:
(1) Constants are supposed to be in all caps, NOT function names. That makes reading your code confusing.
(2) Make your type names longer if need be to make them obvious as to their function. I like your typedefs, because that helps; just make your type names fuller. I don't know what prost means (Croatian?), but it'd really help if I did.
(3) "typedef struct" is unnecessary. Just do "struct <typename>".
(4) Encapsulate your nodes in a class so that the node pointer doesn't have to be passed in. It also makes for a much cleaner look to your code.

[dargueta]

Okay, here's what I have. There's a bug in here somewhere, but this is an example of what you might want your code to look like:

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <memory.h>
#include <string.h>
 
class Folder;
//linked list of folders for easy manipulation
struct FolderList
{
    FolderList  *previousFolder;
    Folder    *thisFolder;
    FolderList  *nextFolder;
};
//linked list of documents for easy manipulation
struct DocumentList
{
    DocumentList    *previousDocument;
    char            *thisDocument;
    DocumentList    *nextDocument;
};
 
//actual folder class
class Folder
{
private:
    char            *folderName;
    unsigned int    numberOfDocuments;
    DocumentList    documents;
    unsigned int    numberOfFolders;
    FolderList    folders;
    Folder      *parent;
protected:
    Folder(char *name,Folder *owner)
    {
        //copy the folder name
        folderName = _strdup(name);
        //copy folder owner
        parent = owner;
        //set the defaults--no docs, no subfolders
        numberOfDocuments = 0;
        numberOfFolders = 0;
        //set all pointers to null
        memset(&documents,NULL,sizeof(DocumentList));
        //set folder pointers to null
        folders.previousFolder = NULL;
        folders.nextFolder = NULL;
        folders.thisFolder = this;
    }
public:
    Folder(char *name)
    {
        //copy the folder name
        folderName = _strdup(name);
        parent = NULL;
        //set the defaults--no docs, no subfolders
        numberOfDocuments = 0;
        numberOfFolders = 0;
        //set all pointers to null
        memset(&documents,NULL,sizeof(DocumentList));
        //set folder pointers to null
        folders.previousFolder = NULL;
        folders.nextFolder = NULL;
        folders.thisFolder = this;
    }
    Folder(Folder *fol)
    {
        if(fol == NULL)
            //if the Folder passed in is invalid, then call the default constructor.
            Folder::Folder(NULL,NULL);
 
        FolderList *folderCopies = fol->getFolders();