4. Stack zur Verwaltung beliebiger Datentypen programmieren

Stack zur Verwaltung beliebiger Datentypen programmieren

  • ?

    Hallo zusammen 🙂

    Ich mache derzeit von der Uni aus einen C-Kurs und habe u.a. die Aufgabe, einen Stack zu implementieren, der Objekte von einem beliebigen Datentyp verwalten kann (d.h. ein Benutzer soll "beliebige" Objekte in den Stack einlesen können).

    Den Stack für einen fest vorgegebenen Datentyp (int) zu programmieren, ist mir mittlerweile (denke ich) gelungen. Wie geht es nun aber für einen beliebigen Datentyp? Wie funktioniert insbesondere das Einlesen (und Ausgeben) beliebiger Datentypen? Ich hatte zuerst an Makros gedacht, aber die funktionieren in scanf bzw printf nicht...

    Im folgenden mal zwei kleine Ausschnitte aus meinem Code für einen int-Stack... ich wäre euch sehr dankbar, wenn ihr mir einen Hinweis geben könntet, wie ich das verallgemeinern könnte:

    Strukturdefinition:

    typedef struct elementstr
{
   int data ;   // int (Datentyp kommt spaeter auch in push und pop vor)						
   struct elementstr* next ;
} element ;

    Ein- und Ausgabe innerhalb von main:

    int buffer ;       // int
scanf ( "%d" , &buffer ) ;   // %d
printf ( "Eingegeben wurde: %d" , buffer ) ; // %d
    0
  • Mod

    Kira Cauchy schrieb:

    Ich hatte zuerst an Makros gedacht, aber die funktionieren in scanf bzw printf nicht...

    Doch klar gehen Makros mit printf und scanf zusammen:

    #define DATENTYP int;
#define PRINTF_FORMAT "%d"

DATENTYP daten;
printf("Die Daten: " FORMAT "\n", daten);

    Ich frag mich jedoch, wieso dein Stack Ein- und Aisgabefunktionen haben soll. Das gehört da vom Desing her nicht rein. Und der Nutzercode (d.h. der Code, der den Stack benutzt) kennt ja selber den Datentyp.

    Allgemein hast du in C zwei brauchbare und einen guten Weg, um Datentypen und Funktionen zu abstrahieren. Die brauchbaren Methoden:
    1. Makroorgien und weitere Präprozessortricks
    2. Alles mit void* und Funktionszeigern machen
    Und die gute Methode:
    3. Nicht C dafür benutzen :p . C ist leider ziemlich die am schlechteste Wahl unter den verbreiteten Sprachen um damit Datentypen zu abstrahieren.

    Ich sehe natürlich ein, dass 3. hier nicht in Frage kommt, daher wirst du wohl zu 1. greifen müssen. Viel Spaß beim Makroen.

    0
  • C

    Kira Cauchy schrieb:

    ...
    Wie geht es nun aber für einen beliebigen Datentyp?
    ...
    Im folgenden mal zwei kleine Ausschnitte aus meinem Code für einen int-Stack... ich wäre euch sehr dankbar, wenn ihr mir einen Hinweis geben könntet, wie ich das verallgemeinern könnte:

    Strukturdefinition:

    typedef struct elementstr
{
   int data ;   // int (Datentyp kommt spaeter auch in push und pop vor)                       
   struct elementstr* next ;
} element ;

    In C lässt sich so ein Stack gaaaanz wunderbar realisieren, denn:
    ein void* lässt sich ohne Cast in einen Zeiger beliebigen Datentyps umwandeln und umgekehrt. Das ist eine saubere Sache, es sind keine hässlichen Frickelmakros nötig.
    Verallgemeinern lässt sich das so, guckst du:

    typedef struct tagStack 
{
	void** p;
	size_t stack_index, buffer_count;
} stack_t;

    Kira Cauchy schrieb:

    Wie funktioniert insbesondere das Einlesen (und Ausgeben) beliebiger Datentypen?

    Mit entsprechenden Push-/Pop-Funktionen.

    int push ( stack_t* s, void* e );
void* pop ( stack_t* s );

    Du liest einen void* ein und gibst einen void* zurück. Fertig.
    Das ist Abstraktion in vollkommener Vollendung.
    Um das Handling mit den Datentypen hat sich der aufrufende Code zu kümmern.
    Ich wüsste nicht, warum C eine schlechte (geschweige denn die schlechteste) Wahl für diese Aufgabe sein
    sollte und eine Notwendigkeit für Funktionszeiger in einem C-Stackmodul sehe ich nicht.

    0
  • ?

    Ich hatte es bereits mit void-Zeigern versucht, mich dabei aber ziemlich verzettelt. Heute mittag hab ich dann SeppJs Tipp gelesen und es damit versucht, was dann nach längerem Probieren auch geklappt hat.
    Euch beiden vielen Dank für die Mühe. 🙂

    0

  • Dein Lehrer will wahrscheinlich auf void* hinaus.
    Ich halte diese Aufgabenstellung aber zu schwierig für Anfänger.
    Man kann auch Makros mit generischen Aktionen kombinieren:

    /* eigener Testtyp (neben double und string s.u.) */
typedef struct {
char name[20];
int alter;
char geschlecht;
} Person;

/* Aktionen für jeden Typ */
void f_double(double*d) { printf("%f\n",*d); }
void f_string(char*d) { puts(d); }
void f_struct(Person*d) { printf("%s %d %c\n",d->name,d->alter,d->geschlecht); }

/* anonymer Stackelement-Typ */
typedef struct {
void (*f)();
void *d;
} Eintrag;

/* Aktionen für den Stack */
enum{PUSH,POP,PRINTALL};

/* unser Stack-Typ */
typedef struct{
Eintrag (*work)();
int i;
Eintrag eintrag[100];
} Stack;

#define CALL(x) x.f(x.d)
#define doublePUSH(s,p) s.work(&s,PUSH,p,f_double)
#define stringPUSH(s,p) s.work(&s,PUSH,p,f_string)
#define structPUSH(s,p) s.work(&s,PUSH,p,f_struct)
#define DOStack(s,e) s.work(&s,e)

/* alle Stackoperationen in einer Funktion zusammengefasst */
Eintrag work(Stack *this,int e,void*p,void(*f)())
{
  switch(e){
  case POP: return this->eintrag[--this->i];
  case PUSH: { Eintrag e={f,p}; this->eintrag[this->i++]=e;break; }
  case PRINTALL: { int i=this->i; while(i--) CALL(this->eintrag[i]);}
  }
}

int main()
{
  int i;
  Eintrag eintrag;

  /* Testdaten mit 3 unterschiedlichen Typen bereitstellen */
  double d[]={1,2,3};
  char *s[]={"s1","s2","s3"};
  Person p[]={{"schmidt",47,'m'},{"meier",11,'w'},{"lehmann",12,'m'}};

  /* unser Stack-Objekt */
  Stack stack={work};

  /* Testdaten mit ihren unterschiedlichen Typen in EINEN Stack packen (eigentliche Aufgabe) */
  for(i=0;i<3;++i)
    doublePUSH(stack,&d[i]),stringPUSH(stack,s[i]),structPUSH(stack,&p[i]);

  /* Kontrollausgabe: gesamter Stackinhalt */
  DOStack(stack,PRINTALL);

  /* Stack einzeln wieder abräumen und dabei jedes Element nochmal kontrollausgeben */
  for(i=0;i<9;++i)
    eintrag=DOStack(stack,POP),CALL(eintrag);

  return 0;
}

    http://ideone.com/oGH0d1

    0
Anmelden zum Antworten