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:

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

[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]

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

[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:

[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]