+ Reply to Thread
Page 1 of 2
1 2 LastLast
Results 1 to 10 of 13

Thread: An important exam!

  1. #1
    Newbie Zael is an unknown quantity at this point Zael's Avatar
    Join Date
    Jan 2008
    Posts
    13

    An important exam!

    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..

  2. #2
    Code Warrior dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta's Avatar
    Join Date
    Oct 2007
    Age
    19
    Posts
    2,842
    Blog Entries
    8
    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;".

    Code:
    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?

  3. #3
    Newbie Zael is an unknown quantity at this point Zael's Avatar
    Join Date
    Jan 2008
    Posts
    13
    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:

    [HIGHLIGHT="C"]char Document[12] = "document.txt";[/HIGHLIGHT]


  4. #4
    Super Moderator WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther has much to be proud of WingedPanther's Avatar
    Join Date
    Jul 2006
    Age
    36
    Posts
    11,680
    Blog Entries
    57
    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.
    Attached Thumbnails An important exam!-treefolder.jpeg  
    CodeCall Blog | CodeCall Wiki | Shareware
    Programming is a branch of mathematics.
    My CodeCall Blog | My Personal Blog

  5. #5
    Code Warrior dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta's Avatar
    Join Date
    Oct 2007
    Age
    19
    Posts
    2,842
    Blog Entries
    8
    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.

  6. #6
    Newbie Zael is an unknown quantity at this point Zael's Avatar
    Join Date
    Jan 2008
    Posts
    13
    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

  7. #7
    Code Warrior dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta's Avatar
    Join Date
    Oct 2007
    Age
    19
    Posts
    2,842
    Blog Entries
    8
    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.
    Last edited by dargueta; 01-21-2008 at 02:00 PM.

  8. #8
    Newbie Zael is an unknown quantity at this point Zael's Avatar
    Join Date
    Jan 2008
    Posts
    13
    [HIGHLIGHT="C"]#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;
    }[/HIGHLIGHT]

    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.
    Last edited by Zael; 01-21-2008 at 02:28 PM. Reason: Renaming some variables..

  9. #9
    Code Warrior dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta's Avatar
    Join Date
    Oct 2007
    Age
    19
    Posts
    2,842
    Blog Entries
    8
    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.
    Last edited by dargueta; 01-21-2008 at 05:02 PM. Reason: Added another tip

  10. #10
    Code Warrior dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta has much to be proud of dargueta's Avatar
    Join Date
    Oct 2007
    Age
    19
    Posts
    2,842
    Blog Entries
    8
    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:

    [HIGHLIGHT="C"]
    #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();
    DocumentList *documentCopies = fol->getDocuments();
    parent = fol->getParent();

    if(folderCopies != NULL)
    //copy the first pointer in to establish the link
    memcpy(&folders,folderCopies,sizeof(FolderList));
    else
    //if tehre are no folders, then just set all pointers to NULL.
    memset(&folders,NULL,sizeof(FolderList));

    folderName = fol->getName();
    numberOfDocuments = fol->getNumberOfDocuments();
    numberOfFolders = fol->getNumberOfFolders();
    }
    ~Folder(void)
    {
    //traverse the list of folders and delete them all
    FolderList *currFolder = &folders;
    //since the nextFolder member will be NULL on the last folder, that's when we stop.
    while(currFolder != NULL)
    {
    delete currFolder->thisFolder;
    currFolder = currFolder->nextFolder;
    }
    //now do the same for documents.
    DocumentList *currDocument = &documents;
    while(currDocument != NULL)
    {
    delete currDocument->thisDocument;
    currDocument = currDocument->nextDocument;
    }
    }
    /////////////////////////////////
    bool createDocument(char *name)
    {
    //check to make sure that there isn't a document by that name already.
    DocumentList *doc = getDocument(name);
    if(doc == NULL)
    {
    //if not, then add a new document
    doc = &documents;
    //traverse the list until we get to the end.
    while(doc->nextDocument != NULL)
    doc = doc->nextDocument;
    //allocate a new document and add it to the last link
    doc->nextDocument = (DocumentList *)malloc(sizeof(DocumentList));
    //if this happens, then we're out of memory. return false.
    if(doc->nextDocument == NULL)
    return false;
    //otherwise, the new document has been created, so we'll copy the name in.
    doc->nextDocument->thisDocument = _strdup(name);
    //set up the links
    doc->nextDocument->previousDocument = doc;
    doc->nextDocument->nextDocument = NULL;
    //increment document counter
    ++numberOfDocuments;
    //return true because the document was successfully created.
    return true;
    }
    else
    //document exists, return false
    return false;
    }
    bool deleteDocument(char *name)
    {
    //if the document is found
    DocumentList *doc = getDocument(name);
    if(doc != NULL)
    {
    //break the previous link and assign it to the next one
    doc->previousDocument->nextDocument = doc->nextDocument;
    //break the next link and assign it to the previous one
    doc->nextDocument->previousDocument = doc->previousDocument;
    //deallocate the document name
    free(doc->thisDocument);
    //decrement number of documents
    --numberOfDocuments;
    //document successfully deleted, return true.
    return true;
    }
    else
    //document not found, return false
    return false;
    }
    bool createFolder(char *name)
    {
    //check to make sure that there isn't a folder by that name already.
    FolderList *fol = getFolder(name);
    if(fol == NULL)
    {
    //if not, then add a new folder
    fol = &folders;
    //traverse the list until we get to the end.
    while(fol->nextFolder != NULL)
    fol = fol->nextFolder;
    //allocate a new folder and add it to the last link
    fol->nextFolder = (FolderList *)malloc(sizeof(FolderList));
    //if this happens, then we're out of memory. return false.
    if(fol->nextFolder == NULL)
    return false;
    //otherwise, the new folder has been created, so we'll copy the name in.
    fol->nextFolder->thisFolder = new Folder(name,this);
    //set up the links
    fol->nextFolder->previousFolder = fol;
    fol->nextFolder->nextFolder = NULL;
    //increment folder counter
    ++numberOfFolders;
    //return true because the folder was successfully created.
    return true;
    }
    else
    //folder exists, return false
    return false;
    }
    bool deleteFolder(char *name)
    {
    //if the document is found
    FolderList *fol = getFolder(name);
    if(fol != NULL)
    {
    //break the previous link and assign it to the next one
    fol->previousFolder->nextFolder = fol->nextFolder;
    //break the next link and assign it to the previous one
    fol->nextFolder->previousFolder = fol->previousFolder;
    //deallocate the document name
    delete fol->thisFolder;
    //decrement number of folders
    --numberOfFolders;
    //folder successfully deleted, return true.
    return true;
    }
    else
    //folder not found, return false
    return false;
    }
    char *getName(void)
    {
    if(folderName == NULL)
    return NULL;
    else
    //return a copy so user can't alter original
    return _strdup(folderName);
    }
    bool setName(char *name)
    {
    if(name == NULL)
    return false;
    else
    {
    folderName = _strdup(name);
    return true;
    }
    }
    unsigned int getNumberOfDocuments(void)
    {
    return numberOfDocuments;
    }
    unsigned int getNumberOfFolders(void)
    {
    return numberOfFolders;
    }
    char *findDocument(char *name)
    {
    DocumentList *doc = getDocument(name);
    if(doc == NULL)
    return NULL;
    else
    return _strdup(doc->thisDocument);
    }
    Folder *findFolder(char *name)
    {
    FolderList *fol = getFolder(name);
    if(fol == NULL)
    return NULL;
    else
    return fol->thisFolder;
    }
    FolderList *getFolders(void)
    {
    FolderList *newList = (FolderList *)malloc(sizeof(FolderList));
    FolderList *currFolder,*topOfNewList;
    //if malloc() failed, return a null immediately.
    if(newList == NULL)
    return NULL;
    newList->previousFolder = NULL;
    //now traverse the list, creating new copies of each item.
    currFolder = &folders;
    topOfNewList = newList;
    while(currFolder != NULL)
    {
    newList->thisFolder = new Folder(folders.thisFolder);
    if(currFolder->nextFolder != NULL)
    {
    newList->nextFolder = (FolderList *)malloc(sizeof(FolderList));
    newList->nextFolder->previousFolder = newList;
    newList = newList->nextFolder;
    currFolder = currFolder->nextFolder;
    }
    else
    break;
    }
    //return the first element in the linked list
    return topOfNewList;
    }
    DocumentList *getDocuments(void)
    {
    DocumentList *newList = (DocumentList *)malloc(sizeof(DocumentList));
    DocumentList *currDocument,*topOfNewList;
    //if malloc() failed, return a null immediately.
    if(newList == NULL)
    return NULL;
    newList->previousDocument = NULL;
    //now traverse the list, creating new copies of each item.
    currDocument = &documents;
    topOfNewList = newList;
    while(currDocument != NULL)
    {
    newList->thisDocument = _strdup(documents.thisDocument);
    if(currDocument->nextDocument != NULL)
    {
    newList->nextDocument = (DocumentList *)malloc(sizeof(DocumentList));
    newList->nextDocument->previousDocument = newList;
    newList = newList->nextDocument;
    currDocument = currDocument->nextDocument;
    }
    else
    break;
    }
    //return the first element in the linked list
    return topOfNewList;
    }
    Folder *getParentFolder(void)
    {
    return new Folder(parent);
    }
    char *getAbsolutePath(void)
    {
    unsigned int sizeOfParentPath, sizeOfThisPath;
    char *parentPath,*thisPath;

    if(parent != NULL)
    parentPath = parent->getAbsolutePath();
    else
    return NULL;
    //get size
    if(parentPath != NULL)
    sizeOfParentPath = strlen(parentPath);
    else
    sizeOfParentPath = 0;

    if(folderName != NULL)
    sizeOfThisPath = strlen(folderName);
    else
    sizeOfThisPath = 0;
    //declare new buffer for string
    thisPath = (char *)calloc(sizeOfParentPath+sizeOfThisPath + 2,sizeof(char));
    //if out of memory, return NULL
    if(thisPath == NULL)
    //change this to NULL when finished debugging--some weird memory error occurs.
    return "ERROR-OUT OF MEMORY";
    //otherwise, copy the paths
    memset(thisPath,NULL,sizeOfParentPath+sizeOfThisPa th + 2);
    memcpy(thisPath,parentPath,sizeOfParentPath);
    strcat(thisPath,folderName);
    strcat(thisPath,"\\");
    return thisPath;
    }
    protected:
    /*
    Since these three functions return direct links to the protected data,
    users outside the class could call one of these functions and get
    access to the document or folder data, then modify it as they want.
    That's why these are private--there are more secure versions that are
    public that can be called by the users; they're called findDocument()
    findFolder(), and getParentFolder(). They return only single instances
    of the data, not the linked list.
    */
    DocumentList *getDocument(char *name)
    {
    DocumentList *currDocument = &documents;
    //traverse the list
    while(currDocument != NULL)
    {
    if(currDocument->thisDocument == NULL)
    break;
    //use a string comparison on the file names
    if(strcmp(currDocument->thisDocument,name) == 0)
    //if the names match, then return the current document
    return currDocument;
    currDocument = currDocument->nextDocument;
    }
    //if you get here, then the document wasn't found.
    return NULL;
    }
    FolderList *getFolder(char *name)
    {
    FolderList *currFolder = &folders;
    //traverse the list
    while(currFolder != NULL)
    {
    if(currFolder->thisFolder == NULL)
    break;
    //use a string comparison on the folder names
    char *temp = currFolder->thisFolder->getName();
    if(strcmp(temp,name) == 0)
    //if the names match, then return the current folder
    return currFolder;
    //deallocate the copy of the folder name so we don't have memory leaks.
    if(temp != NULL)
    {
    free(temp);
    temp = NULL;
    }
    currFolder = currFolder->nextFolder;
    }
    //if you get here, then the folder wasn't found.
    return NULL;
    }

    Folder *getParent(void)
    {
    return parent;
    }
    };
    [/HIGHLIGHT]
    Last edited by dargueta; 01-21-2008 at 05:02 PM. Reason: Fixed ugly formatting

+ Reply to Thread
Page 1 of 2
1 2 LastLast

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

     

Similar Threads

  1. I got estonian exam today!
    By Jaan in forum The Lounge
    Replies: 4
    Last Post: 06-09-2007, 07:31 AM
  2. Exam objectives.
    By sania21 in forum Java Help
    Replies: 2
    Last Post: 05-22-2007, 12:01 AM
  3. Why are comments important?
    By Sionofdarkness in forum Java Help
    Replies: 10
    Last Post: 07-29-2006, 11:32 AM

Bookmarks

Bookmarks

     
        Algorithms and Data Structures

        Java tutorials

        Algorithms Forum

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts