Verkettete Liste: verschiedene Objekte ablegen und deren Funktionen aufrufen

[stefan-tiger]

Hallo,

ich habe eine verkettete Liste programmiert und habe nun das Problem, dass die Daten-Elemente (=Objekte) in der Liste alle vom selben Typ sind.

Gibts eine elegante Möglichkeit verschiedene verschiedene Objekte in einer Liste anzusprechen?

Beispielsweise so (Pseudocode):

typedef struct { char data; } ObjektA_t;
typedef struct { int data; } ObjektB_t;
typedef struct { double data; } Objekt_C_t;

Zu ObjektA_t und ObjektB_t soll es jeweils eine Funktion process() und output() geben (z.B. processObejctA() usw.)
ObjektC_t soll nur eine process() aber keine output() Funktion haben.

Nun wären 2 Dinge zu lösen:

1. Einfügen von Objekten eines beliebigen Objekts in die verkettete Liste

2. Durchgehen der Liste und Aufrufen der entsprechenden process() und output() Funktionen

Hat hier jemand ne Idee?

Ich hab schon überlegt hier mit void-Pointern und Objekt-Typ-Kennungen (z.B. jedes strcut hat als erstes Element ein int welches den Objekttyp kennzeichnet; dann kann men in einem swicth-case entsprechen gecastet callen) zu arbeiten.
Das erscheint mir aber umständlich und unsauber.

Ich bräuchte hier soetwas wie ein Container der beliebige Objekte aufnehmen kann. Dann könnte man eine Liste mit Containern machen. Geht sowas?

Alternative wäre womöglich für jeden Objekt-Typ eine eigene Liste zu pflegen.

Das wäre aber auch schlecht da ich für jeden neuen Objekt-Typ eine weitere Liste pflegen müsste und auch die Aufrufstellen von process() und output() an allen Stellen im programm ergänzen müsste.

PS: in C++ würde ich warscheinlich 1. mit einer Basisklasse und 2. mit überladenen Memeber-Funktionen umsetzen.

Gruß Stefan

[Janjan]

Viel spaß mit der Void-Zeiger-Orgie.

Du erstellst ein Typedef für Output- und process-Funktionen, welche jeweils einen Void-Zeiger annehmen. Dort übergibst du immer deine Struktur, welche ebenfalls als Void-Zeiger gespeichert werden. Schön viel gecaste und sehr unsicher.

[noobLolo]

evtl. ist da auch was für dich dabei
http://www.c-plusplus.net/forum/viewtopic-var-t-is-258990.html

also ich finds ja schön aber das ist wie alles geschmacks sache

lg lolo

[pointercrash**]

stefan-tiger schrieb:

Ich hab schon überlegt hier mit void-Pointern und Objekt-Typ-Kennungen (z.B. jedes strcut hat als erstes Element ein int welches den Objekttyp kennzeichnet; dann kann men in einem swicth-case entsprechen gecastet callen) zu arbeiten.
Das erscheint mir aber umständlich und unsauber....
Das wäre aber auch schlecht da ich für jeden neuen Objekt-Typ eine weitere Liste pflegen müsste und auch die Aufrufstellen von process() und output() an allen Stellen im programm ergänzen müsste.

Ich weiß jetzt nicht, ob es genau das ist, was Du brauchst, aber Du kannst in einer Struct auch Funktionspointer unterbringen, Du mußt halt nur den Pointer beim Anlegen des Listenelements mit den richtigen Adressen der Methoden/Funktionen laden, die das Listenelement richtig bearbeiten.

Wenn man's mal gerafft hat, was man da tut, bleibt's auch übersichtlich.

[namespace invader]

stefan-tiger schrieb:

1. Einfügen von Objekten eines beliebigen Objekts in die verkettete Liste

Wenn es nicht ganz beliebige Objekte sind, z.B. durch eine Union im Listenknoten, die alle Möglichkeiten enthält.

Oder du definierst eine Struktur für den den gemeinsamen Teil aller Listenknoten als "Basisklasse", die dann am Anfang aller speziellen Listenknotenstrukturen steht. Funktionen, die nur allgemein was mit der Liste machen, arbeiten nur damit, während die speziellen Funktionen sich die Zeiger auf den richtigen Typ casten.

2. Durchgehen der Liste und Aufrufen der entsprechenden process() und output() Funktionen

Entweder die Listenknoten enthalten (außerhalb der Union, bzw. im gemeinsamen Teil) Zeiger auf die entsprechende Funktion, oder Zeiger auf eine irgendwo herumliegende vtable-Struktur, die unter anderem Zeiger auf die Funktionen enthält, oder irgendeine Kennzeichnung, mit der dann in entsprechenden Arrays die Funktionen gefunden werden.

[stefan-tiger]

Hallo zusammen,

danke für die Antworten. Ich habe nun eine Lösung umgesetzt die qusai eine Mischung aus fast alles ist was hier angedeuted wurde:

Hier die wichtigen Code-Stücke (sollten selbsterklärend sein, wenn nicht einfach nachfragen):

typedef enum {A,B} type_e;

typedef struct 
{   
  type_e objtype;
  void (*foo)(void); 
} ObjectA_t; 

typedef struct 
{   
  type_e objtype;
  void (*bar)(void); 
} ObjectB_t;

typedef struct Entry_t
{
  struct Entry_t *next;
  int data;
  void *obj;
} Entry_t;

...

void processList(Entry_t* list)
{
  do 
  {
    if(list->obj==0)
      return;

    type_e objtype = *((type_e*)(list->obj));

    if(objtype == A)
    {
      printf("objtype=A\n");
      ((ObjectA_t*)(list->obj))->foo();
    }
    else if(objtype == B)
    {
      printf("objtype=B\n");
      ((ObjectB_t*)(list->obj))->bar();
    }
    else   
    {
      printf("objtype unknown!\n");
    }

  list = list->next;
  } while(list != 0);

}
...

Vielleicht doch noch kurz eine Erläuterung: Das "..." bedeuted dass ich hier in meinem Programm Code habe um die verkettete Liste anzulegen und zu testen. Das ist uninteressat für das geschilderte Problem.
Hinweis: Meine Listen-Elemente sind diese "Entry_t"

Die Zentrale Funktion ist "processList". Jedes Objekt muss man Anfang den enum haben um den Objekt-Typ festzustellen. Dort wird dann entsprechend Verzweigt, sprich die void-Pointer gecastet.
(Null-Zeiger wird ignoriert; kein Objekt in Liste eingehängt)

Freu mich auch über Rückmeldungen.
Das ganze scheint zwar zu funktionieren, kommt mir aber etwas "unsauber" und sehr Fehleranfällig vor.

[noobLolo]

typedef struct 
{   
  type_e objtype;
  void (*foo)(void); 
} ObjectA_t; 

typedef struct 
{   
  type_e objtype;
  void (*bar)(void); 
} ObjectB_t;

wenn die structs vom aufbau her identisch sind kannst es dir schenken die zweimal anzulegen sondern weist einfach einen anderen functions pointer zu... damit fällt dann auch das objtype weg.

falls du dich jetzt fragst wie du denn erkennen sollst welchs obj du vor dir hast, dann schau dir einfach die functions pointer von foo oder bar an.

damit schenkst dir dann auch das if(){}else{}...

lg lolo

[stefan-tiger]

noobLolo schrieb:

...

wenn die structs vom aufbau her identisch sind kannst es dir schenken die zweimal anzulegen sondern weist einfach einen anderen functions pointer zu... damit fällt dann auch das objtype weg.

falls du dich jetzt fragst wie du denn erkennen sollst welchs obj du vor dir hast, dann schau dir einfach die functions pointer von foo oder bar an.

damit schenkst dir dann auch das if(){}else{}...

lg lolo

Hallo,

du hast recht in diesem Beispiel ist das mit den Object-s überflüssig, da diese sich sehr ähneln.

Das ist für mich ja auch gerader der Knackpunkt. Wenn ich in die verkettete Liste nur Ojekte gleichen Typs speichern wollte hätte ich alles in "Entry_t" gepackt und wäre fertig.

Das hier soll aber allgemeingültig sein, für völlig verschiedene Objekte und in der "processList()" können dann unterschidlich viele "Member-Funktionen" der Objects aufgerufen werden.

Beispielsweise kann man Objekte haben die Berechnet werden müssen und welche die dann noch Ausgegeben werden müssen. D.h. in meinem Beispiel würde ich bei Objekt A vll. die Berechnungs und die Ausgage-Funktion aufrufen, für B aber nur eine Berechnungsfunktion, weil B garkeine Ausgabe hat.

[noobLolo]

nimm trotzdem die adressen als ClassID also dann die adresse in "void *obj;"

lg lolo

[stefan-tiger]

noobLolo schrieb:

nimm trotzdem die adressen als ClassID also dann die adresse in "void *obj;"

lg lolo

Das geht nicht, weil ich ja viele Instanzen eines Objekts in der Liste haben kann.
Sprich ich kann z.B. 10x ObjektA_t in der Liste habe und 20x ObjektB_t. Ich weiss nicht wie ich hier die Adressen der Instanzen als Objekt-Typ-Kennung verwenden, gescheige denn "auslesen" könnte.

Vll. hab ich auch nicht verstanden was du gemeint hast?

[pointercrash**]

stefan-tiger schrieb:

noobLolo schrieb:

nimm trotzdem die adressen als ClassID also dann die adresse in "void *obj;"

lg lolo

Das geht nicht, weil ich ja viele Instanzen eines Objekts in der Liste haben kann.
Sprich ich kann z.B. 10x ObjektA_t in der Liste habe und 20x ObjektB_t. Ich weiss nicht wie ich hier die Adressen der Instanzen als Objekt-Typ-Kennung verwenden, gescheige denn "auslesen" könnte.

Vll. hab ich auch nicht verstanden was du gemeint hast?

Natürlich geht's, Du stehst Dir nur gerade gedanklich selbst im Weg.

typedef struct
{  
  int somedata;
  void (*anyvoidofvoidfunction)(void);
} Object_t;

Ist jetzt mal nur ein Typ; erst wenn Du Elemente anlegst, weist Du anyvoidofvoidfunction entweder foo() oder bar() zu. Welche Funktion Du da reinschreibst, typisiert nicht nur das Listenelement, sondern die Funktion sollte ja auch wissen, was sie mit den anderen Daten in der Liste anfangen kann.
Wenn Du es weitertreiben magst, kannst Du auch Funktionen definieren, die ihre eigene Struct als Argument auswerten. Das müßte ziemlich dran hinkommen, was Du vorhast.

[stefan-tiger]

pointercrash() schrieb:

...Natürlich geht's, Du stehst Dir nur gerade gedanklich selbst im Weg. ...

Hallo,

ich glaube du versuchst was zusammenzufassen was ich getrennt haben will.

Beispielsweise soll ObjektA eine Memberfunktion foo() haben und ObjektB eine Memberfunktion bar().

Die Funktion foo() muss also niemals mit Typen von ObjektB umgehen können!

Vll. wird es deutlicher was ich will, wenn man statt ObjektA,B das Beispiel ganz anders aufzieht, z.B. mit einem Objekt "Pferd" und einem Objekt "Sofa".
Die haben miteinander nichts zu tun, also gibt es hier auch nichts zusammenzufassen. Einzig beispielsweise eine Draw() Funktion würden beiden gemeinsam sein, falls das z.B. Objekte eines Spiels wären.

Wenn ich jetzt alle (Instanzen aller) Objekte zeichnen lassen will dann brauch ich eine "zeichne-alle-Objekte-in-Liste" Funktion.

[noobLolo]

void hello(){
  printf("hello");
}
void world(){
  printf("world");
}
.-diese structs sind statisch daher kannst die adresse zu den structures verwenden um den typ abzufragen, wie in dem beispiel das ich dir gepostet hab.
v
struct{
  type_e objtype;
  void (*foo)(void); 
} ObjectA = {
  0x1
  ,hello
};

struct{
  type_e objtype;
  void (*foo)(void); 
} ObjectB = {
  0x2
  ,world
};

typedef struct 
{   
  type_e objtype;
  void (*bar)(void); 
} ObjectB_t;

typedef struct Entry_t
{
  struct Entry_t *next;
  int data;
  void *obj;
} Entry_t;

...

void processList(Entry_t* list)
{
  do 
  {
    if(list->obj==0)
      return;

    Entry_t *objtype = list->obj;

    if(objtype == &ObjectA)
    {
      printf("objtype=A\n");
      ((ObjectA_t*)(list->obj))->foo();
    }
    else if(objtype == &ObjectB)
    {
      printf("objtype=B\n");
      ((ObjectB_t*)(list->obj))->bar();
    }
    else   
    {
      printf("objtype unknown!\n");
    }

  list = list->next;
  } while(list != 0);

}
...

hoffe das wird jetzt klarer was ich mein;)

[noobLolo]

ups "void *objtype = list->obj;" und in dem bsp. war das nicht dabei

lg lolo

[stefan-tiger]

Hallo noobLolo,

danke für deine Antwort.

Ich denke jetzt verstehe ich was du mit "Adresse als ID" nehmen gemeint hast bzw. ich habe das schon geahnt.

Diese Lösung ist mir allerdings zu unflexibel und hat wenn ich es richtig sehe einige Nachteile:

1. Du legst hier global Speicher an und initialisierst ihn gleich noch
2. Es gibt nur eine Instanz ObjektA
3. Du frägst die Adresse dieser Instanz ab

Warum möchte ich das nicht haben:

zu 1.: Wenn jemand garkein ObjektA angelgen möchte bekommt er doch eins untergeschoben
zu 2.: Es soll möglich sein viele Instanzen von ObjektA zu erzeugen
zu 3.: Ich müsste für jede Instanz von ObjektA die Adresse abfragen; das geht nicht weil ich nicht weiss wieviele ObjektA-Instanzen zur Laufzeit angelegt werden; zudem wäre es umständlich

Vll liege ich auch falsch und hab dein Code doch nicht ganz verstanden? Kannst du dein Beispiel bitte mal mit zwei weiteren, zur Laufzeit angelegten, Instanzen von ObjektA erweitern? Dann wird es warscheinlich noch deutlicher...

Danke.

[noobLolo]

Du legst hier global Speicher an und initialisierst ihn gleich noch

na klar so wie man das eben macht.

Es gibt nur eine Instanz ObjektA

naja das ist nur zum teil richtig, denn es gibt nur eine "classe A" von dieser klasse werden dann die objecte abgeleitet.

Du frägst die Adresse dieser Instanz ab

ich frage nicht die adresse der instanz sondern die adresse der classe ab das ist ein unterschied.

ich denke wir haben einfach unterschiedliche ansichten wie oop aussehen muß.

lg lolo

[Big Brother]

stefan-tiger schrieb:

Warum möchte ich das nicht haben:

zu 1.: Wenn jemand garkein ObjektA angelgen möchte bekommt er doch eins untergeschoben
zu 2.: Es soll möglich sein viele Instanzen von ObjektA zu erzeugen
zu 3.: Ich müsste für jede Instanz von ObjektA die Adresse abfragen; das geht nicht weil ich nicht weiss wieviele ObjektA-Instanzen zur Laufzeit angelegt werden; zudem wäre es umständlich

Ein dynamisch erzeugtes ObjektX muss mit Werten initialisiert werden, sonst ist die Abfrage eines Objekt-Typs bzw. ein Zugriff auf einen Funktionszeiger nicht möglich. Bei der Initialisierung kannst du diesem Objekt einen Funktionszeiger verpassen.

Haben alle Objekte ( Objekt1, ... , ObjektN ) als erstes Element einen Fuktionszeiger z.B.
void (*func_ptr)(void* object), kannst du dir eine Art Schablone erstellen:

typedef struct objectX ObjectX; 
struct objectX
{
     void (*func_ptr)(void* object);
};

Der Zeiger auf diese Schablone ist dein 'Universalschlüssel' für den Zugang zu den Funktionen der Objekte Objekt1, ... , ObjektN. Damit hast du einen Direktzugriff auf die Funktionen der zugehörigen Objekte, ohne einen Objekttyp abragen zu müssen. Guckst du:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>

typedef struct objectX ObjectX; 
typedef struct objectA ObjectA; 
typedef struct objectB ObjectB; 
typedef struct list List;

struct objectX
{
	void (*func_ptr)(void* object);
};

struct objectA
{
	void (*func_ptr)(void* object); 
	int value;
};

struct objectB
{
	void (*func_ptr)(void* object); 
	char buf[BUFSIZ];
};

struct list
{
	void* object;
	List* next;
};

void func_objectA ( void* object )
{
	ObjectA* p = object;
	printf ( "%d\n", p->value );
}

void func_objectB ( void* object )
{
	ObjectB* p = object;
	printf ( "%s\n", p->buf );
}

void init_objectA ( ObjectA* p )
{
	p->func_ptr = func_objectA, p->value = 707;
}

void init_objectB ( ObjectB* p )
{
	p->func_ptr = func_objectB, strncpy ( p->buf, "Hello World", sizeof(p->buf)-1 );
}

void process_list ( List* l )
{
	ObjectX* px;
	while ( l != NULL )
		px = l->object, px->func_ptr ( l->object ), l = l->next;
}

int main()
{
	List* L = calloc ( 2, sizeof ( *L ) );
	ObjectA* A = malloc ( sizeof( *A ) );
	ObjectB* B = malloc ( sizeof( *B ) );

	if ( errno ) { free ( A ), free ( B ), free ( L ); return 1; };

	init_objectA ( A ), init_objectB ( B );
	L[0].object = B, L[0].next = &L[1], L[1].object = A, L[1].next = NULL;
	process_list ( L );

	free ( A ), free ( B ), free ( L );
	return 0;
}

[noobLolo]

evtl. schaust dir mal in java script das prototype object und konzept an. wenn man verstanden hat was da passiert lässt sich oop auch easy in c umsetzen und man kommt nicht mit komischen vorstellungen daher die klassen structur und methoden in jede instanz mit reinzukopieren.

lg lolo

[stefan-tiger]

noobLolo schrieb:

...
naja das ist nur zum teil richtig, denn es gibt nur eine "classe A" von dieser klasse werden dann die objecte abgeleitet.
...
ich frage nicht die adresse der instanz sondern die adresse der classe ab das ist ein unterschied.

ich denke wir haben einfach unterschiedliche ansichten wie oop aussehen muß.

...

Korrigier mich wenn ich was falsches schreibe:
In deinem Code ist Klasse=Instanz und es gibt sie nur einmal. Und dieses eine mal ist auch noch zur Compile-Zeit und nicht zur Laufzeit angelegt.
Daher ist es in deinem Beispiel auch kein Problem die Adresse der "Klasse" abzufragen.

Ich möchte aber mehrere Instanzen zur Laufzeit anlegen.

Ich weiss nicht ob ich ein anderes Verständnis von OOP habe, aber in C ist für mich das was in C++ eine "class" ist ein "typedef struct".
Wichtig ist mir hierbei das "typedef", denn eine Klasse in C++ belegt an sich noch kein Speicher und kann nicht als "lebendes Objekt" vendendet werden, das wird erst mit einer Instanz möglich (oder nicht?).

[stefan-tiger]

Hallo Big Brother,

deinen ersten Satz verstehe ich nicht. Ist das ein Problem für Dich?
Für mich ist das kein Problem, da ich eine new-Funktion für meine Objekte schreibe in der das "malloc" gemacht wird und initialisiert wird.

Ansonsten kann ich dein Beispiel nachvollziehen, danke dafür.

Hierbei sind aber die Einschränkungen gegeben, dass

(a) alle Klassen diesen Funktionspointer haben müssen
(b) der Funktiinspointer im struct aller Klassen immer an der selben Stelle steht
(c) der Funktionspointer immer die selbe Signatur in allen Klassen haben muss

Der Vorteil dieser Lösung ist allerdings, dass es dem Basis-Klassen-Konzept von C++ näher kommt und dass die Implementierung zwischen der Liste und den Objekten besser getrennt ist.