zane@ddsw1.MCS.COM (Sameer Parekh) (08/13/90)
I need help creating a linked list in C.
I have a structure by type of:
struct dir
{
int number;
char *name;
struct dir *ptr[30]
}
where number is the number of elements in ptr
name is a character string referring to the name of the directory
ptr is an array of pointers to structures like this one.
I am making a directory tree.
the array is a list of pointers to the directories in that directory.
I have decided that the follwing method is the most economical:
I used ls -R >files
grep ./ files >directories
this lists all the directories (I started from /)
then I converted the directoried file, say of 1700 lines
into an array of structures of the type:
struct entries
{
int number;
char *name;
}
each element in the array refers to one line of the directories file
I will show an example of the directories file:
./dir:
./dir/element:
./dir/element/wow:
./dir/lick:
./hello:
./hello/item:
this would make 6 structures of type entries.
they would be
number name
0 "/dir"
1 "/element"
2 "/wow"
1 "/lick"
0 "/hello"
1 "/item"
I need to convert this into the structure of type directories.
You can see that the numbers can only go up by one at a time.
and they can go down by alot
(from infinity to 0 actually)
From the entries structures we can recreate the original file directories.
You can do this by seeing...oh 0 is dir, so that is a beggining one.
./dir:
1 is element that is a next one
./dir/element:
2 is wow so that come next
./dir/element/wow:
1 is lick so it must go down some, dir is that 1
./dir/lick:
0 is hello it must go down more
./hello:
1 is item, it goes up so it must be in hello
./hello/item:
I want to make a tree out of this, like a binary
tree, but with more than 2 children)
(rather a variable children amount)
How do I make this structure?
I will make a next post with my source code, I must comment my source code
some more.
Thanks.
----------------Here is the Source Code -----------------------------------
/*******************************************************************
* Tree - this function displays the tree of the UNIX system
********************************************************************/
#include<stdio.h>
#define NAME "directories"
typedef struct /* This is the linked list structure */
{
char *name;
int number;
DIRECTORY ptr[30];
} DIRECTORY;
struct cond_dir /* This is the structure for the flat list */
{
char *name
int level
};
/*******************************************************************************
showtree - display the tree in an interactive format
*****************************************************************************/
/* This is a recursive function */
showtree(dir)
DIRECTORY *dir /* A pointer to a tree element */
{
int counter;
int choice;
while(1); /* Infinite loop */
{
printf("Now branched to %s\n", dir -> name);
if (dir -> number == 0) /* If there are no children for this element */
{
printf("No more levels to go down\n");
return;
}
for (counter = 0; counter < number; counter++) /* Print children */
printf("%2d. %s\n", counter, (dir -> ptr[counter]) -> name);
printf("%2d. Go back a level (Quit if at lowest)", number);
badchoice:
printf("Choose one/n"); /* Choose a child (or back one/quit) */
if ((scanf("%d", &choice) != 1) || /* If choice is bad */
(choice < 0) || /* Out of range */
(choice > number)) /* Not a good entry */
goto badchoice; /* Rechoose */
if (choice == number) /* If quit/goback */
break;
showtree(dir -> ptr[choice]); /* Go down one more level chosen */
}
}
/************************************************************************
* readin - this puts all the dir names into the dir array
*************************************************************************/
int readin(dirs)
char **dirs; /* Pointer to an array of pointers to strings, these are */
/* the the strings in the "directories" file */
{
FILE *inputfile; /* inputfile, pointer to stream of type FILE */
int counter;
if (( inputfile = fopen(NAME, "r")) == NULL) /* Open file, check for error */
{ /* Print error */
printf("The file directories has not been created\n");
printf("You must do ls -R >files\n");
printf("Then grep ./ files >directories\n");
return;
}
/* Get all the lines, check for errors (If error, stop) */
for(counter = 0; counter + 1; counter++)
if (fgets(dirs[counter], 1000, inputfile) == NULL)
break;
fclose(inputfile); /* Close file */
return(counter); /* Return the amount of entries found */
}
/**********************************************************************
* countslashes - count all the slashes in the dir string
**********************************************************************/
int countslashes(string)
char *string; /* pointer to a string */
{
int counter;
int slash_no = 0;
for(counter = 0; counter + 1; counter++) /* Check each char in the string */
{ /* Infinite incrementing loop */
if (string[counter] = '/') /* A slash found, add one to count */
slash_no++;
if (string[counter] = '\0') /* End of string, break from loop */
break;
}
return(slash_no); /* Return number of slashes */
}
/**********************************************************************
* lastentry - convert the : to a null character and position the pointer
* on the last / in the dir string
***********************************************************************/
lastentry(string, slash_no);
char *string; /* The big dir string */
int slash_no; /* Number of slashes */
{
int counter;
int slashes = 0; /* Slashes counted */
for(counter = 0; counter + 1; counter++); /* Look at every character */
{
if (string[counter] = ':') /* If it is ':' */
{
string[counter] = '\0'; /* Convert to null */
break;
}
}
for(counter = 0; counter + 1; counter++); /* Look for last slash */
{
if (string[counter] = '/') /* Count a slash */
slashes++;
if (slashes == slash_no) /* if IS last slash (compare with slash_no) */
break;
}
return(&string[counter]); /* Return a new pointer to the last slash */
}
/**********************************************************************
* setup - convert the strings into a structure with dir level and dir name
***************************************************************************/
setup(number, entries, dirs);
int number; /* Number of items in the array of dirs */
struct cond_dir **entries; /* The flat set of structures */
char **dirs; /* the flat list */
{
int counter;
int slash_no;
for(counter = 0; counter < number; counter++); /* Reposition pointers so */
dirs[counter]++; /* initial . is gone */
for(counter = 0; counter < number; counter++); /* convert into the flat */
{ /* structure */
slash_no = countslashes(dirs[counter]); /* Countslashes */
entries[counter] -> number = slash_no - 1; /* Put slash_no - 1 */
/* in as level number */
entries[counter] -> name = lastentry(dirs[counter], slash_no);
} /* ^^^ put name into structure */
}
/**********************************************************************
* maketree - this is the main function for the maketree it is only run
* many times, this is recursive
**********************************************************************/
DIRECTORY *maketree(number, entries, lastnum)
int number, lastnum;
struct cond_dir **entries;
/* This is the function I don't know how to make */
{
main() /* MAIN */
{
char *dirs[2000];
struct cond_dir **entries;
int number;
DIRECTORY *root;
number = readin(dirs); /* Get all the dirs */
entries = malloc(number); /* allocate memory for entries */
setup(number, entries, dirs); /* put dir lines into entries */
root = maketree(number, entries, -1); /* create the tree */
showtree(root); /* show the tree */
}
--
________________________________________________________________
| Sameer Parekh | "If I claim to be the wise man |
| zane@ddsw1.MCS.COM | it is because I do not know" |
~~~~~~~~~~~~~~~~~~~~~~~| -"Wayward Son" |