[C] dynamische array of struct

[ajvdvegt]

Even een (waarschijnlijk heel simpel) vraagje: Ik moet een dynamische array maken met daarin mijn eigen structures. Mijn probleem is: hoe declareer je die? Een (dynamische) array-of-int declareer ik zo:

code:

int *array;

En 1 instantie van mijn struct zo:

code:

my_struct_s *struct;

Een dynamische array met elementen van het type my_struct_s zou dan toch dit worden:

code:

my_struct_s **array;

Maar hoe reserveer ik dan geheugen voor die dingen en hoe indexeer ik ze?
Iets als

code:

array[0] = (my_struct_s *) malloc(sizeof(my_struct_s));

geeft een segfault.

Ik gebruik nu als 'work-around' deze declaratie:

code:

my_struct_s *array[1];

En dan behandel ik die array toch maar als dynamische (dwz ik reserveer geheugen e.d.) Dat werkt wel, maar 'hoort' het ook zo?
(Het moet trouwens met gcc gecompileerd worden, mocht dat wat uitmaken)

[The End]

code:

my_struct_s **array;
*array = malloc(sizeof(my_struct_s)*aantalstructs);
(*array)[i].blablabla = 1;

zoiets...

[Verwijderd]

Ik weet dat het in C++ zo moet:

my_struct *array[MAX_VAL];

...geheugen vrijmaken:

array[8]=new my_struct;

...en vrijgeven:

delete array[8];

Althans, zo doe ik dat normaal. Ik zorg gewoon dat MAX_VAL een waarde heeft, die ik zeker niet zal overschrijden...
Maar zoals ik zei, dat is C++. Ik weet niet of je het daar ook over hebt...

[Verwijderd]

Na het aanmaken van de array met malloc kan je dan overigens met realloc een ander aantal elementen in de array kwijt. Dan is tie zo dynamisch als het maar moet

[curry684]

Je hele insteek klopt niet... 1 instantie van de struct declareer je als volgt:

code:

my_struct_s struct;

Wat jij declareert is enkel een pointer.

Hieruit volgt voor een dynamische array van structs:

code:

my_struct_s* structs;

structs      = malloc(sizeof(my_struct_s) * amount);
structs[20].value = 684;

[ajvdvegt]

Excuses, ik had m'n probleem te ver versimpeld. Ik wil een struct definieren met een array van (andere) structs daarin:

code:

typedef struct node {
  int max;
  boolean has_sub_nodes;
  struct node *small;
  struct node *big;
} node_t;

typedef struct {
  int count;
  node_t *tree[1];
} treelist_t;

int main (){
  treelist_t list;

  list = (treelist_t *) malloc (sizeof(treelist_t));
  list->count = 1;
  list->tree[0] = (node_t *) malloc(sizeof(node_t));
  list->tree[0]->max=3;
  list->tree[0]->small = (node_t *) malloc(sizeof(node_t));
  list->tree[0]->big = (node_t *) malloc(sizeof(node_t));
  list->tree[0]->has_sub_nodes = 1;
  ...
  free(list->tree[0]->big);
  free(list->tree[0]->small);
  free(list->tree[0]);
  free(list);

  return 0;
}

Nu kan ik e.e.a. zo benaderen:

code:

  list->count;
  printf("%d\n", list->tree[0]->max);
  list->tree[0]->small->max = 2;

En ik vind het prima als ik slechts een pointer definieer, dat scheelt toch weer het kopieeren van gegevens als ik ze als parameter gebruik?

In ieder geval werkt wat ik nu heb staan, enkel moet ik bij de declaratie van "list" dit opgeven:

code:

list = (treelist_t *) malloc (2*sizeof(treelist_t));

Ik reserveer dus teveel geheugen, waardoor ik wat 'speel ruimte' heb voor andere geheugen fouten, maar dat is niet echt de oplossing.
Als ik malloc goed aan het werk heb lukt realloc ook wel (die gebruik ik al vor list->tree[1] e.d.). En een MAXVAL constante is geen optie, want de array omvang kan tussen 2 en 1024 liggen (vandaar ook de vraag dynamische arrays ).

[curry684]

Op vrijdag 26 april 2002 16:52 schreef ajvdvegt het volgende:
Excuses, ik had m'n probleem te ver versimpeld. Ik wil een struct definieren met een array van (andere) structs daarin:

Aha dus je wil gewoon botweg een nested tree. Wat niets aan je probleem verandert (!!!) want het is niets anders dan dat: nested, en dus hetzelfde probleem als een platte dynamische array maar dan toevallig in elkaar gefrot. Not a single difference to be found...

En ik vind het prima als ik slechts een pointer definieer, dat scheelt toch weer het kopieeren van gegevens als ik ze als parameter gebruik?

Uhmmmmmmmmm ik twijfel als ik dit lees of je het concept pointers en declaraties wel 100% doorhebt. Het doorgeven van een struct by-pointer kan ook als volgt met de address-of operator oftewel de ampersand:

code:

void DoSomething(TreeNode* p_TreeNode)
{
p_TreeNode->Elements... etc.
}

int main()
{
TreeNode     l_MyTreeNode;

DoSomething(&l_MyTreeNode);
}

Maar volgens mij heb je gewoon nog weinig idee over hoe je een tree opzet... toch?

Sowieso heb je overigens die has_sub_nodes property niet nodig daar dat automatisch volgt uit het al of niet NULL zijn van je beide subnodelists (indien goed opgezet

De beste manier imho:

code:

struct TreeNode
{
// Zut

TreeNode*    m_First;
TreeNode*    m_Last;
TreeNode*    m_Previous;
TreeNode*    m_Next;
};

Hiermee vorm je een nested linked list die add-to-tail, add-to-head en probleemloze by-pointer recursies toestaat, wat volgens mij exact je bedoeling is, EN je hebt niet het geemmer met dynamische pointerarrays.

[Verwijderd]

Op zaterdag 27 april 2002 01:37 schreef curry684 het volgende:
De beste manier imho:

code:

struct TreeNode
{
// Zut

TreeNode*    m_First;
TreeNode*    m_Last;
TreeNode*    m_Previous;
TreeNode*    m_Next;
};

Hiermee vorm je een nested linked list die add-to-tail, add-to-head en probleemloze by-pointer recursies toestaat, wat volgens mij exact je bedoeling is, EN je hebt niet het geemmer met dynamische pointerarrays.

Als je add-to-head/tail doet moet je vervolgens alle treeNodes updaten. Ik vind het moier als je gewoon een linkedlist idee gebruikt, dus:

code:

struct TreeNode
{
// Zut

TreeNode*    m_Previous;
TreeNode*    m_Next;
};

En dan while (tree->m_Previous) tree = tree->m_Previous; om bij de eerste te komen, en m_Next voor de laatste... Dat scheelt weer wat zut. .

[Soultaker]

Op zaterdag 27 april 2002 09:54 schreef beelzebubu het volgende:
Als je add-to-head/tail doet moet je vervolgens alle treeNodes updaten. Ik vind het moier als je gewoon een linkedlist idee gebruikt

...

En dan while (tree->m_Previous) tree = tree->m_Previous; om bij de eerste te komen, en m_Next voor de laatste...

Maak 'm dan cyclisch, dan kun je in constante tijd elementen aan 't begin en 't eind toevoegen. (Zonder while-lusje dus).

[Verwijderd]

Op zaterdag 27 april 2002 14:48 schreef Soultaker het volgende:
Maak 'm dan cyclisch, dan kun je in constante tijd elementen aan 't begin en 't eind toevoegen. (Zonder while-lusje dus).

.

Dan zit er geen volgorde meer in welke de eerste is en welke de laatste...

Of snap ik je nu verkeerd? .

[.oisyn]

Op zaterdag 27 april 2002 16:20 schreef beelzebubu het volgende:

[..]

.

Dan zit er geen volgorde meer in welke de eerste is en welke de laatste...

Of snap ik je nu verkeerd? .

nou de volgorde blijft hetzelfde, maar het begin en eindpunt is niet meer bekend... of tenminste, tree->m_Next wijst naar de laatste, maar als je een willekeurige node hebt kun je vandaar uit niet de eerste of laatste vinden.

Maar het punt is nou juist dat het laatste element weer naar de eerste wijst, dus als tree->m_Next de laatste is, dan is tree->m_Next->m_Next de eerste

[Soultaker]

Op zaterdag 27 april 2002 16:34 schreef .oisyn het volgende:
nou de volgorde blijft hetzelfde, maar het begin en eindpunt is niet meer bekend...

Nee, ook dat is niet waar. Het begin- en eindpunt ligt nog steeds vast. In elke 'schakel' hou ik een pointer bij naar het volgende en vorige element, maar dan cyclisch: het volgende element van het laatste element is het eerste element, het vorige element van het eerste element is het laatste element:

code:

        | pointer naar eerste element
        |
        v
Normaal:
        1 -> <- 2 -> <- 3

Cyclisch:
... 3 -> <- 1 -> <- 2 -> <- 3 -> <- 1 ...

Net zoals in de niet-cyclische variant, werk ik met een pointer die het eerste element aanwijst. Ik kan dus altijd een eerste en een laatste element (dit is het element met het eerste element als volgende) aanwijzen en de volgorde is ook behouden. Ik kan nu echter wel efficient elementen invoegen aan het begin, omdat ik een enkele stap naar het laatste element kan springen (dat is immers het vorige element van het eerste element).

Ik vermoed dat dit niet de meest heldere uitleg is die ik ooit heb geschreven, maar ik hoop dat het idee toch duidelijk is.

[.oisyn]

Op zaterdag 27 april 2002 18:19 schreef Soultaker iets

let ook even op het stukje: maar als je een willekeurige node hebt kun je vandaar uit niet de eerste of laatste vinden.

[ACM]

Op zaterdag 27 april 2002 18:19 schreef Soultaker het volgende:
Cyclisch:

Kan je dan niet beter een variant maken waarvan de root-node (of whatever) zowel de eerste als de laatste aanwijst. En verder elke node alleen "links en rechts" aanwijst. Zodat je even snel voorwaarts als achterwaarts kan zoeken in je lijst EN je altijd de eerste en laatste weet? (Het is sowieso vrij lastig als je de root-node kwijtraakt, dus dat moet je toch wel voorkomen )

Imho is cyclisch niet echt jouw 2e voorbeeld, maar je eerste met dien verstande dat punt 3 weer naar 1 wijst (en andersom).

[Soultaker]

Op zaterdag 27 april 2002 18:23 schreef .oisyn het volgende:
let ook even op het stukje: maar als je een willekeurige node hebt kun je vandaar uit niet de eerste of laatste vinden.

En in welke situatie vormt dit dan een probleem? Meestal geef je alleen de pointer naar de eerste node mee en niet een willekeurige node. Als je toch een willekeurige node meegeeft, kun je ook wel de eerste node meegeven om te weten waar het begin zit. Ik kan me echter niet herinneren dit ooit nodig gehad te hebben.

Op zaterdag 27 april 2002 18:23 schreef ACM het volgende:
Kan je dan niet beter een variant maken waarvan de root-node (of whatever) zowel de eerste als de laatste aanwijst. En verder elke node alleen "links en rechts" aanwijst. Zodat je even snel voorwaarts als achterwaarts kan zoeken in je lijst EN je altijd de eerste en laatste weet? (Het is sowieso vrij lastig als je de root-node kwijtraakt, dus dat moet je toch wel voorkomen )

Dat snap ik niet helemaal. Wat is een root-node dan? In de tot nu toe gegeven mogelijkheden zijn alle nodes gelijk.

Imho is cyclisch niet echt jouw 2e voorbeeld, maar je eerste met dien verstande dat punt 3 weer naar 1 wijst (en andersom).

Eigenlijk snap ik dit ook niet =) Het eerste voorbeeld is niet cyclisch, het tweede wel. In het eerste geval zijn punt 1 en 3 niet verbonden, in het tweede wel.

[ACM]

Op zaterdag 27 april 2002 18:31 schreef Soultaker het volgende:
Dat snap ik niet helemaal. Wat is een root-node dan? In de tot nu toe gegeven mogelijkheden zijn alle nodes gelijk.

Mja, ergens hou je bij dat je een lijst hebt (zou een leuke bug zijn als je dat vergeet ). Dat "bijhouden" zou je als de root-node kunnen zien.

Eigenlijk snap ik dit ook niet =) Het eerste voorbeeld is niet cyclisch, het tweede wel. In het eerste geval zijn punt 1 en 3 niet verbonden, in het tweede wel.

Aargh, misschien dat ik es beter moet lezen

[Soultaker]

Op zaterdag 27 april 2002 18:35 schreef ACM het volgende:
Mja, ergens hou je bij dat je een lijst hebt (zou een leuke bug zijn als je dat vergeet ). Dat "bijhouden" zou je als de root-node kunnen zien.

Een of andere struct die de rest 'omvat' dus zegmaar? Tja, dat zou je inderdaad kunnen doen, maar het lijkt me hier geen toegevoegde waarde bieden. Wat je daar wel weer handig in op zou kunnen slaan, is het aantal elementen in je lijst.

[ajvdvegt]

Op zaterdag 27 april 2002 19:04 schreef Soultaker het volgende:

[..]

Een of andere struct die de rest 'omvat' dus zegmaar? Tja, dat zou je inderdaad kunnen doen, maar het lijkt me hier geen toegevoegde waarde bieden. Wat je daar wel weer handig in op zou kunnen slaan, is het aantal elementen in je lijst.

Het weekend is voorbij, dus daar ben ik weer.... Ten eerste: ik heb het concept van pointers e.d. niet helemaal door, dat klopt. Ik ben Delphi gewend, en daar heb je geeen 'last' van pointers als je er niet zelf om gaat vragen

Ten tweede was het idee dat ik een bijzondere vorm van een linked-list ga maken, namelijk een boom (een 2-3-boom om precies te zijn, maar dat doet er even niet toe). Elke node houdt nu ook al een verwijzing naar zijn 'kinderen' en zijn 'parent' bij, en de node zonder parent is de root van de boom. (ik heb ook een functie gemaakt die me vanaf een willekeurige node op zoek gaat naar de root door steeds de parent te volgen).
Elk element in mijn array (treelist_t in mijn code) is dus de root van een boom.

Een cyclische oplossing voor de lijst van bomen is trouwens niet handig, ik wil ze graag kunnen indexeren.

Als ik ook de laatste foutjes er uit heb zal ik de code hier wel posten, om mijn idee helder te krijgen (die posting zal zeer waarschijnlijk enkel een uitbreiding van mijn eerdere post zijn trouwens).

[.oisyn]

Op zaterdag 27 april 2002 18:31 schreef Soultaker het volgende:

[..]

En in welke situatie vormt dit dan een probleem? Meestal geef je alleen de pointer naar de eerste node mee en niet een willekeurige node. Als je toch een willekeurige node meegeeft, kun je ook wel de eerste node meegeven om te weten waar het begin zit. Ik kan me echter niet herinneren dit ooit nodig gehad te hebben.

ho ho, ik heb nooit gezegd dat dat een probleem vormde, ik lichtte het gewoon toe voor beelzebubu

[curry684]

Op zaterdag 27 april 2002 09:54 schreef beelzebubu het volgende:
Als je add-to-head/tail doet moet je vervolgens alle treeNodes updaten. Ik vind het moier als je gewoon een linkedlist idee gebruikt, dus:

code:

struct TreeNode
{
// Zut

TreeNode*    m_Previous;
TreeNode*    m_Next;
};

En dan while (tree->m_Previous) tree = tree->m_Previous; om bij de eerste te komen, en m_Next voor de laatste... Dat scheelt weer wat zut. .

Uhm waarom quote je nu exact mijn code minus het gedeelte wat het een tree maakt?!?

Het idee is dat je een AddChildToTail kunt doen als volgt:

code:

l_NewNode->m_Previous = l_Parent->m_Last;
if(l_Parent->m_Last)
  l_Parent->m_Last->m_Next = l_NewNode;
else
  l_Parent->m_First   = l_NewNode;
l_Parent->m_Last       = l_NewNode;

Ongeveer (notepad de gekste...)