Liste

k.A.

hallo,

wollt eine liste machen, die verschiedene structs zulaesst. hab das dann mit union so gemacht:

Code

typedef union dataelement {
    struct literalnode* literalNode;
    struct clausenode* clauseNode;
    struct graphnode* graphNode;
    struct variablenode* varNode;
} Data;


typedef struct list {
    union dataelement* data;
    struct list* next;
    struct list* previous;
} List;


List* addListElement(List* list, Data* element) {
    List* newList = (List *) calloc(1, sizeof (List));
    newList->data = element;
    if (list == NULL) {
        list = newList;
    } else {
        list->previous = newList;
        newList->next = list;
        list = newList;
    }


    return list;
}

Alles anzeigen

da die structs der union alle den selben speicher benuetzen, hab ich mire gedacht, ich kann einfach:

Code

List* alist;
VariableNode* var = bla;
alist = addListElement(alist, (Data*) var);

das funktioniert so nun aber leider nicht, dataelement bekommt zwar den pointer, aber nicht die 4 elemente der union.
Nun hab ich mir ueberlegt einfach:

Code

Data* data;
data->varNode = var;
alist = addListElement(alist, data);

da krieg ich aber leider segmentation fault, ganz wo anders (char array das fuers parsen genutz wird). Hab aber ausserdem nichts geaendert, und das hat zuerst funktioniert.

kann es sein dass ich fuer data auch ein malloc machen muss?
hab das hinzugefuegt und dann gehts, aber irgendwie kommt mir das wie speicherverschwendung vor. und der ist leider eher knapp.
gibts irgendeine moeglichkeit wie ich das sonst einfacher machen/haben kann (liste mit unterschiedlichen objecten)?

bin fuer alle tipps dankbar!

Plantschkuh!

Blitzantwort: Benutze (void *) statt dem ganzen union-Krempel.

k.A.

danke war sehr schnell, kenn mich aber leider nicht ganz aus. meinst du?

Code

löschen:
typedef union dataelement


typedef struct list {
    void* data;
    struct list* next;
    struct list* previous;
} List;


List* addListElement(List* list, void* element) {
    List* newList = (List *) calloc(1, sizeof (List));
    newList->data = element;
    if (list == NULL) {
        list = newList;
    } else {
        list->previous = newList;
        newList->next = list;
        list = newList;
    }


    return list;
}

Alles anzeigen

liste->data->.... gibt mir nun aber keine vorschläge mehr (autovervollständigung).
muss dann zuerst:
VarNode bla = (VarNode*)liste->data;
seh ich das richtig?

mtoman

Wenn du einen void* pointer hast, dann musst du nachher auf den korrekten Datentyp casten, ja.

Je nachdem was du zur Verfügung hast, könntest es auch mit einem Template versuchen.

Plantschkuh!

Zitat von k.A.

muss dann zuerst:
VarNode bla = (VarNode*)liste->data;
seh ich das richtig?

Ja. Wenn du dir sicher sein kannst, dass an dieser Stelle liste->data auf einen Knoten vom Typ VarNode zeigt. Du wirst dafür noch irgendeine Art von Datenelement mitschleppen müssen. Dafür gibt es in C mehr oder weniger obskure und fehleranfällige Techniken.

Zitat von mtoman

Je nachdem was du zur Verfügung hast, könntest es auch mit einem Template versuchen.

Ja, C++ wäre für solche Aufgaben sicher besser geeignet als C. (Andere Sprachen wären noch viel viel besser geeignet...)

k.A.

Zitat von Plantschkuh!

Ja. Wenn du dir sicher sein kannst, dass an dieser Stelle liste->data auf einen Knoten vom Typ VarNode zeigt. Du wirst dafür noch irgendeine Art von Datenelement mitschleppen müssen. Dafür gibt es in C mehr oder weniger obskure und fehleranfällige Techniken

was muss ich noch mitschleppen? wenn ich meine listen erstelle, weiss ich ja was ich hineingebe... und weiss dann auf was ich casten muss beim wiederherausnehmen. wird das so funktionieren oder sollte ich lieber für jedes struct eine eigene liste machen? oder vielleicht doch mit union wie vorher?

Zitat

Ja, C++ wäre für solche Aufgaben sicher besser geeignet als C. (Andere Sprachen wären noch viel viel besser geeignet...)

muss das ganze leider in c machen...

danke für die hilfe!

mtoman

Da wir in der HTL viel so Datenstrukturen in C ausprogrammiert haben, hab ich da mal nachgeschaut. Hier sind einige Code-Teile bezüglich Listen:
http://edvowww.htlwrn.ac.at/cgi-bin/progra…cgi/C/beispiele

Vielleicht findest da was Nützliches

Plantschkuh!

Zitat von k.A.

was muss ich noch mitschleppen? wenn ich meine listen erstelle, weiss ich ja was ich hineingebe... und weiss dann auf was ich casten muss beim wiederherausnehmen. wird das so funktionieren oder sollte ich lieber für jedes struct eine eigene liste machen?

OK, wenn in jeder Liste immer nur Knoten desselben Typs sind, dann kannst du einfach die Listen auseinanderhalten. Problematisch wäre es, wenn in einer Liste verschiedene Arten von Knoten sein könnten.

(Wenn in jeder Liste immer nur Knoten desselben Typs sind, dann kann man statt mit (void *) auch mit Makros arbeiten und hat strenges Typechecking. Manche Leute finden Makros aber doof.)

Zitat

oder vielleicht doch mit union wie vorher?

Bei unions mußt du auch wissen, auf welches Feld du zugreifen willst; das Problem ist dasselbe. Wenn du es bei einer union immer weißt, dann weißt du es bei (void *) auch.

tsp

Ich hab eine Liste mal so implementiert, dass ich eine Struktur "listNode" definiert habe, die ich dann in jeder enthaltenen Struktur an einer definierten Position eingefügt hab

Code

struct listNode {
   void* lpNext;
   void* lpPrev;
}


struct nodeTypeA {
    struct listNode listData;
    // etc.
}


struct nodeTypeB {
    struct listNode listData;
    // etc.
}

Alles anzeigen

die Zugriffsfunktionen haben dann jeweils einen Typecast der nodeTypeA bzw. nodeTypB auf listNode durchgeführt. Wenn eine Struktur in mehreren Listen vorhanden sein sollte, hab ich bei der initialisierung des List Roots einen unsigned long int Parameter übergeben, der den relativen Offset der listNode Datenstruktur in den jeweiligen Strukturen erhalten hat (per offsetof) hinzugefügt ...

Einziger Haken an so einer Implementierung ist natürlich, dass man sowohl mit den Positionen der Listen Navigationsdaten innerhalb des Objekts sehr leicht durcheinander kommt als auch durch Compiler Optimierungen böse Überraschungen erleben könnte ...

Plantschkuh!

Zitat von tsp

Einziger Haken an so einer Implementierung ist natürlich, dass man sowohl mit den Positionen der Listen Navigationsdaten innerhalb des Objekts sehr leicht durcheinander kommt

Tu das Gemeinsame am besten an den Anfang der Struktur, dann mußt du nicht mit Offsets rumtun. Der C-Standard garantiert, daß das Layout von Strukturen mit gleichen Anfangselementen in diesen Elementen identisch ist. Damit kannst du eben direkt (nodeTypeA *) und (nodeTypeB *) auf (listNode *) casten.

Zitat

als auch durch Compiler Optimierungen böse Überraschungen erleben könnte ...

Kann mir da grad kein plausibles Problem ausmalen.

tsp

Zitat von Plantschkuh!

Tu das Gemeinsame am besten an den Anfang der Struktur, dann mußt du nicht mit Offsets rumtun. Der C-Standard garantiert, daß das Layout von Strukturen mit gleichen Anfangselementen in diesen Elementen identisch ist. Damit kannst du eben direkt (nodeTypeA *) und (nodeTypeB *) auf (listNode *) casten.

Das ist dann solange möglich, solange jede Struktur nodeTypeA und nodeTypeB genau in einer einzelnen Liste liegt. Die Offsets waren bei mir dann notwendig, weil ich mehrere unterschiedliche Listen (bzw. mit einer ähnlichen Implementierung Bäume) hatte, in denen ein und die selbe Struktur indiziert wurde.

Zitat von Plantschkuh!

Kann mir da grad kein plausibles Problem ausmalen.

Wenn die Struktur (listNode) nicht in jeder Struktur (nodeTypeA, nodeTypeB) gerade am Anfang der Struktur liegt, kann es unter gewissen Umständen zu Problemen mit dem Packing der Strukturen bei der Optimierung kommen (wenn unterschiedliche Datentypen vor den jeweiligen listNode Strukturen liegen).

Aber stimmt prinzipiell das man das einfach dadurch umgehen kann, dass man die für die Listen bzw. Bäume notwendigen Strukturen einfach an den Anfang der Struktur schreibt

Jetzt mitmachen!