c - N-ary tree functions with stdin (makenode, insert) -

i've tried code following functions

typedef struct node{     char *name;     int n;  //number of kids     struct node **kids;     int dtype; // composite or basic     union data{         double price; //for basic         char *quantity; //for composite     }data; }node;  void create_kid(node **parent){     if(*parent == null){         (*parent) = malloc(sizeof(node));         (*parent)->n = 0;         (*parent)->kids = null;     }else{         (*parent)->n += 1;         (*parent)->kids = realloc((*parent)->kids, ((*parent)->n)*(sizeof(node)));         (*parent)->kids[(*parent)->n - 1] = malloc(sizeof(node));         (*parent)->kids[(*parent)->n - 1]->n = 0;         (*parent)->kids[(*parent)->n - 1]->kids = null;     } }  void insert_c(node *node, char *str){         node->name = malloc(max);         node->name = str;         node->dtype = composite; }  void insert_b(node *node, char *str){         node->name = malloc(max);         node->name = str;         node->dtype = basic; } 

to make such n-ary tree out of input this

bike(2*wheel(rim[60.0 ],         2*axle,         spoke[120.],         hub(2*gear[25.],axle(5*bolt[0.1], 7 * nut[.15]))),     frame(rearframe [175.00],         1*frontframe (fork[22.5] ,axle, 2 *handle[10.]))) 

i aware of other representation of n-ary tree, includes *siblings, , *firstkid, believe **kids representation more suitable case. i'd ask few things.

firstly, there wrong functions? appropriate build n-ary tree?

secondly, if got functions right, cannot construct tree input. example, according input, function calls must functions if read 1 word @ time:

create_kid(&tree); insert_c(tree, "bike"); create_kid(&tree); insert_c(tree->kids[0], "wheel"); create_kid(&(tree->kids[0])); insert_c(tree->kids[0]->kids[0], "rim"); . . . create_kid(&tree); insert_c(tree->kids[1], "frame"); . . 

if tree formed in way, need go higher depth lower depth, nut frame example. believe there must easier way, maybe recursive approach. there way can recursion?

petty things first:

if same instance of axle node located @ various locations in "tree", n-ary tree not n-ary tree longer. graph. if axle, contained bike, cyclic graph.

you notice difference when implementing that. need reference count or in graph decide when free node. in real n-ary tree, not need each node occurs once in tree.

administrative things next:

you decide use array of pointers data structure contain children (kids) of node. such, in order reduce complexity of code, idea create (dynamic) array of pointers first step. benefits: tree code not burdened dynamic array code , can unit test , maybe re-use dynamic array of pointers other project.

i knocked sample pointer array implementation (which not tested) show principle.

to code shown here bit more "user friendly - first includes used, out of way:

#include <crtdbg.h> // windows specific - helps find memory leaks. #include <stdint.h> #include <stdlib.h> #include <string.h> #include <assert.h> 

now array of pointers implementation:

typedef struct pointerarray_tag {     void**data;     size_t capacity;     size_t size; } pointerarray_t;  void pointerarrayinitialize(pointerarray_t *array) {     array->data = null;     array->capacity = 0;     array->size = 0; }  int pointerarrayreserve(pointerarray_t *array, size_t capacity) {     if (array->capacity < capacity)     {         void **newdata = (void**)realloc(array->data, capacity * sizeof(void*));         if (null != newdata)         {             array->data = newdata;             array->capacity = capacity;             return 1; // 1 = "true" in c , indicates success.         }         return 0; // 0 = "false" in c , indicates failure...     }     else     {         return 1;     } } typedef void (*pointerarrayelementfree_t)(void *element);  int pointerarrayresize(pointerarray_t *array, size_t newsize, void* value, pointerarrayelementfree_t elementfree) {     if (null == array) return 0;     if (null == elementfree) return 0;      if (newsize < array->size)     {         (size_t index = newsize; index < array->size; index++)         {             elementfree(array->data[index]);         }         array->size = newsize;         return 1;     }     else if (newsize > array->size)     {         size_t oldsize = array->size;         if (pointerarrayreserve(array, newsize))         {             (size_t index = oldsize; index < newsize; index++)             {                 array->data[index] = value;             }             array->size = newsize;             return 1;         }         return 0; // reserve() failed, function failed.     }     else         return 1; // oldsize == newsize - nothing do. }  int pointerarrayinitializewithcapacity(pointerarray_t *array, size_t initialcapacity) {     pointerarrayinitialize(array);     return pointerarrayreserve(array, initialcapacity); }  int pointerarraypushback(pointerarray_t *array, void*element) {     if (pointerarrayreserve(array, array->size + 1))     {         array->data[array->size] = element;         array->size++;         return 1;     }     return 0; }  int pointerarrayclear(pointerarray_t *array, pointerarrayelementfree_t elementfree) {     if (null == elementfree) return 0;     if (null == array) return 0;      (size_t index = 0; index < array->size; index++)     {         elementfree(array->data[index]);         array->data[index] = null;     }     array->size = 0;     return 1; }  int pointerarrayuninitialize(pointerarray_t *array, pointerarrayelementfree_t elementfree) {     if (pointerarrayclear(array, elementfree))     {         free(array->data);         array->data = null;         array->capacity = 0;         return 1;     }     return 0; } 

nothing special here. dynamic array of void pointers usual operations.

next, while not 100% fitting problem (i felt cost me more time letter), n-ary tree implementation. stated above not ready function graph.

also, took liberty assume form of grammar along line:

<material> ::= <count> <name> <size>             |  <count> <name> 

parsing production, parser first find number (e.g. 2 wheels), name of material (wheel), optionally measurements (e.g. nuts[0.15]).

the alternative grammar closer question harder handle later on when ast used application , overly complicated:

<material> ::= <count> <name> <size>             | <count> <name>             | <name>             | <name> <size> 

this hints if have influence on grammar of input text, improve some.

so, here componenttree code, has above mentioned constraints.

enum nodecontenttype {     empty = 0 ,   number = 1 ,   name = 2 };  typedef struct nodecontent_tag {     nodecontenttype type;     union     {         float number;         char *name;     }; } nodecontent_t;  typedef struct componentnode_tag {     nodecontent_t content;     componentnode_tag * parent;     pointerarray_t children; } componentnode_t;  void componentnodefree(componentnode_t *node) {     // clean heap based in nodecontent_t.     switch (node->content.type)     {     case name:         free(node->content.name);         node->content.name = null;         node->content.type = empty;         break;     default:         // nothing do.         break;     }      // free children below node recursively.     pointerarrayuninitialize(&node->children, (pointerarrayelementfree_t)componentnodefree);     free(node); } typedef struct componenttree_tag {     componentnode_t root; } componenttree_t;  void componenttreeinitialize(componenttree_t *tree) {     tree->root.content.type = empty;     pointerarrayinitialize(&tree->root.children);     tree->root.parent = null; }  componentnode_t *componenttreeroot(componenttree_t *tree) {     return &tree->root; }  void componenttreeclear(componenttree_t *tree) {     if (null != tree)     {         pointerarrayclear(&tree->root.children,(pointerarrayelementfree_t)componentnodefree);     } }  void componenttreeuninitialize(componenttree_t *tree) {     if (null != tree)     {         pointerarrayuninitialize(&tree->root.children, (pointerarrayelementfree_t)componentnodefree);     } }  componentnode_t *componenttreecreateemptynode() {     componentnode_t *node = (componentnode_t*)malloc(sizeof(componentnode_t));     if (null != node)     {         node->content.type = empty;         node->parent = null;         pointerarrayinitialize(&node->children);     }     return node; }  componentnode_t *componenttreecreatenamenode(const char *name) {     componentnode_t *node = (componentnode_t*)malloc(sizeof(componentnode_t));     if (null != node)     {         node->content.type = name;         node->content.name = _strdup(name);         assert(null != node->content.name);          if (null == node->content.name)         {             free(node);             return null;         }         node->parent = null;         pointerarrayinitialize(&node->children);     }     return node; }  componentnode_t *componenttreecreatenumbernode(float number) {     componentnode_t *node = (componentnode_t*)malloc(sizeof(componentnode_t));     if (null != node)     {         node->content.type = number;         node->content.number = number;         node->parent = null;         pointerarrayinitialize(&node->children);     }     return node; }   int componenttreejoin(componenttree_t *tree, componentnode_t *where, componentnode_t *child) {     if (null == child) return 0;     if (null != child->parent) return 0; // in tree.     if (null == tree) return 0;     if (null == where)     {         = &tree->root;     }     child->parent = where;     return pointerarraypushback(&where->children, child); } 

it might bit funny @ first glance componenttree_t *tree parameter exists in componenttreejoin(). rather, compoenenttreecreatexxxnode() functions should have well. why? because later on wants have function componenttree_t *componenttreefromnode(componentnode_t *node) or componentnode_t *componenttreegetroot(componentnode_t *node).

last not least, manual assembly of tree (incomplete, answer length):

int _tmain(int argc, _tchar* argv[]) {     componenttree_t biketree;     componenttreeinitialize(&biketree);     componentnode_t * nutsize = componenttreecreatenumbernode(0.15f);     componentnode_t * nut = componenttreecreatenamenode("nut");     componenttreejoin(&biketree, nut, nutsize);     componentnode_t *nutcount = componenttreecreatenumbernode(7.0f);     componenttreejoin(&biketree, nutcount, nut);     componentnode_t * boltsize = componenttreecreatenumbernode(0.1f);     componentnode_t * bolt = componenttreecreatenamenode("bolt");     componenttreejoin(&biketree, bolt, boltsize);     componentnode_t * boltcount = componenttreecreatenumbernode(5.0f);     componenttreejoin(&biketree, boltcount, bolt);     componentnode_t * axle = componenttreecreatenamenode("axle");     componenttreejoin(&biketree, axle, nutcount);     componenttreejoin(&biketree, axle, boltcount);     componentnode_t *axlecount = componenttreecreatenumbernode(1.0f);     componenttreejoin(&biketree, axlecount, axle);     componentnode_t *gearsize = componenttreecreatenumbernode(25.0f);     componentnode_t *gear = componenttreecreatenamenode("gear");     componenttreejoin(&biketree, gear, gearsize);     componentnode_t *gearcount = componenttreecreatenumbernode(2.0f);     componenttreejoin(&biketree, gearcount, gear);     componentnode_t *hub = componenttreecreatenamenode("hub");     componenttreejoin(&biketree, hub, gearcount);     componenttreejoin(&biketree, hub, axlecount);     componentnode_t *hubcount = componenttreecreatenumbernode(1.0f);     componenttreejoin(&biketree, hubcount, hub);     componentnode_t * spokesize = componenttreecreatenumbernode(120.0f);     componentnode_t * spoke = componenttreecreatenamenode("spoke");     componenttreejoin(&biketree, spoke, spokesize);     componentnode_t * spokecount = componenttreecreatenumbernode(1.0f);     componenttreejoin(&biketree, spokecount, spoke);     componentnode_t * axle1 = componenttreecreatenamenode("axle");     componentnode_t * axle1count = componenttreecreatenumbernode(2.0f);     componenttreejoin(&biketree, axle1count, axle1);     // ...     componentnode_t * wheel = componenttreecreatenamenode("wheel");     componenttreejoin(&biketree, wheel, axle1count);     componenttreejoin(&biketree, wheel, spokecount);     componenttreejoin(&biketree, wheel, hubcount);     componentnode_t * wheelcount = componenttreecreatenumbernode(2.0f);     componenttreejoin(&biketree, wheelcount, wheel);     componentnode_t *bike = componenttreecreatenamenode("bike");     componenttreejoin(&biketree, bike, wheelcount);     componentnode_t *bikecount = componenttreecreatenumbernode(1.0f);     componenttreejoin(&biketree, bikecount, bike);     // .. frame branch omitted ..      componenttreejoin(&biketree, null, bikecount);     componenttreeuninitialize(&biketree);      _crtdumpmemoryleaks();     return 0; } 

summary:

• if supposed graph, not n-ary tree, chose wrong terms.
• the dynamic array code mixed tree implementation make code less testable , readable.
• if dynamic array of pointers kids-list used or singly linked list not fundamental. list better suited, since nodes in example input have 1 child anyway , difference marginal. current implementation of array not saving amount of heap operations (but could, if default capacity not programmed 0 maybe 1 or 2 or opportune value).
• the main() code shows how tree constructed in not order parser traversing input text produce. (i went right left instead of 100% left right).
• the code shown here not treat number of material items member of node produces number node on top of material name node. can need not beneficial depends on how grammar defined , on type of parser etc. , case. how ast looks driven parser decisions made.