Stapelspeicher in C

[Kimi (Gast)]

Hallo,

ich brauche bitte dringend Hilfe bei dem Thema Stapelspeicher in C, um 
die anstehende Klausur zu schaffen (bin leider im letzten Versuch und 
nein ich studiere kein Info). Ich hoffe jemand ist so nett und hilft mir 
Schritt für Schritt?

1.) Geben Sie die Strukturen für den gegeben Stapel mit den Datentypen 
stack_t und frame_t an
[c]
typedef struct stack{
   frame_t *top;
   int size;
}stack_t;

typedef struct frame{
  frame_t *previous;
  double value;
}frame_t;

2.)
Implementieren Sie eine Funktion push, die ein Nutzdatenobjekt oben auf 
den Stapel "auflegt".
Nutzdaten werden als Zeiger an die Funktion ¨ubergeben und m¨ussen nicht 
erst allokiert
werden. Ist das Argument ein Nullzeiger, so nimmt die Funktion keine 
Ver¨anderungen am.
Hier ist eigentlich mein größtes Problem, ich weiß nicht wie der 
Prototyp der Funktion auszusehen hat. Ich denke mal ich muss hier was 
mit der Nutzdatenstruktur anfangen(void(frame_t *frame)?)

3.)Implementieren Sie eine Funktion double top(void), die den obersten 
Wert des Stapels liefert, ohne ihn zu entfernen. Ist der Stapel leer so 
wird 0 zurückgeliefert.

[Oliver S. (oliverso)]

Oh je...
Sowas wie void(frame_t *frame) als Antwort auf die Frage lässt 
befürchten, daß das tatsächlich deine letzte Klausur wird.

void push(double* Nutzdaten);
double Top(void);

Und bei allem nötigem Respekt, ich wette, daß die Lösungen dazu
A) in der Schulstunde
B) in den Hausaufgaben
C) im Netz

vorkommen.
Viel Glück.

Oliver

[Kimi (Gast)]

Ich wollte die Aufgabe nur verstehen, bis zur Klausur habe ich ja noch 
reichlich zeit (einen Monat). Und ich dachte jetzt schon anfangen kann 
gar nicht verkehrt sein. Okey danke, dass heißt wohl Nachhilfe suchen.

[Kimi (Gast)]

Und das sollte nicht die ganze Antwort sein bei 2., ich wollte nur 
wissen wie die Funktion als Prototyp aussieht.

[Linksammler (Gast)]

Dann schau dir die Aufgabenstellung nochmal genau an.

push soll auf einen bestehenen Stack (1. Parameter) ein neues Element 
(2. Parameter) legen. Kein Rückgabgewert erwähnt. Ich würde den Stack 
wieder zurückgebgen, ist aber egal, "void" tuts auch.

also:

void push(stack_t * wohin, frame_t * was) {
  if (!was) return;
  if (!wohin) return;
  was.previous=wohin.top;
  wohin.top=was;
  wohin.size++;
}

Wichtig zum Verständnis: Selber nachvollziehen, ganz altmodisch mit 
Bleistift und Papier, was jede dieser Anweisungen macht.
Dann findest du auch den Fehler. :)

[Oliver S. (oliverso)]

Linksammler schrieb:
> void push(stack_t * wohin, frame_t * was)

Ähem...

Besser nicht...

frame und frame_t sind die internen Datemstrukturen des Stacks, die 
haben draußen keinen zu interessieren. Die Daten sind vom Typ double.

Gepusht werden Daten, sonst nix. Die Funktion Push muß die dann in die 
internen Strukturen verpacken und einhängen.

Oliver

[Kimi (Gast)]

Vielen Dank.Muss ich davor nicht etwas allokiert haben, die 
Aufgabenstellung verwirrt mich.
Jetzt wüsste ich nicht was ich mit "was, wohin"ersetzen soll. Soll ich 
dann einfach etwas annehmen?

[Hans Ulli K. (Gast)]

Schau mal hier :

http://lernfunk.de/media/20202

direkt am Anfang

Und ja allozieren musst du.

[Kimi (Gast)]

Im Video ist es echt gut erklärt danke!

[Karl H. (kbuchegg)]

Kimi schrieb:
> Ich wollte die Aufgabe nur verstehen, bis zur Klausur habe ich ja noch
> reichlich zeit (einen Monat).

Das reicht nicht.
Was du da implementieren sollst, ist Stoff im 4. Semester 
Informatik-Studium (Vorlesung Datenstrukturen). Dir fehlen aber die 
Kentnisse, die du dir in den Semestern 1, 2, und 3 hättest aneignen 
sollen.

[Rolf M. (rmagnus)]

Oliver S. schrieb:
> Linksammler schrieb:
>> void push(stack_t * wohin, frame_t * was)
>
> Ähem...
>
> Besser nicht...

Hans Ulli Kroll schrieb:
> Und ja allozieren musst du.

Aufgabenstellung lesen!

Kimi schrieb:
> Nutzdaten werden als Zeiger an die Funktion ¨ubergeben und m¨ussen nicht
> erst allokiert werden.

[Hans Ulli K. (Gast)]

Rolf Magnus schrieb:
> Oliver S. schrieb:
>> Linksammler schrieb:
>>> void push(stack_t * wohin, frame_t * was)
>>
>> Ähem...
>>
>> Besser nicht...
>
> Hans Ulli Kroll schrieb:
>> Und ja allozieren musst du.
>
> Aufgabenstellung lesen!
>

Ich habe nicht geschrieben was.

Das jetzt die Nutzdaten schon alloziert sind sagt nicht aus das noch was 
anderes alloziert werden muss.
Oder denkst du der Stack liegt einfach so rum ??

[Rolf M. (rmagnus)]

Hans Ulli Kroll schrieb:
> Das jetzt die Nutzdaten schon alloziert sind sagt nicht aus das noch was
> anderes alloziert werden muss.

Du meinst, es wurde explizit darauf hingewiesen, daß man den einen 
double nicht dynamisch allokieren, aber trotzdem per Zeiger an die 
Funktion übergeben soll? Was sollte das denn bringen?

> Oder denkst du der Stack liegt einfach so rum ??

Ich vermute, daß das dynamische Speicherhandling hier ganz bewußt 
weggelassen werden soll. In einem real-world-Programm wäre das natürlich 
unsinnig, aber hier handelt es sich um eine Übungsaufgabe.

[Hans Ulli K. (Gast)]

Den double brauch ich ja nicht zu allozieren.

Ich muss aber meine Listobject, also frame_t allozieren, oder meinen die 
mit Nutzdatenobject das Listobjekt ??.

In real world würde das denn so aussehen

struct object {
        struct object *prev;
        void *item;
};

struct stack {
        struct object *top;
        int size;
};

void *push(struct stack *st, void *data);
void *top(struct stack *st);
void *pop(struct stack *st);
int stack_size(struct stack *st);

Beachte auch das hier

Kimi schrieb:
> 2.)
> Implementieren Sie eine Funktion push, die ein Nutzdatenobjekt oben auf
> den Stapel "auflegt".
> Nutzdaten werden als Zeiger an die Funktion ¨ubergeben und m¨ussen nicht
> erst allokiert
> werden. Ist das Argument ein Nullzeiger, so nimmt die Funktion keine
> Ver¨anderungen am.

Die Nutzdaten werden als Zeiger übergeben !

[Rolf M. (rmagnus)]

Hans Ulli Kroll schrieb:
> Den double brauch ich ja nicht zu allozieren.

Ja, eben. Warum sollte man das aber explizit erwähnen? Und warum sollte 
der double per Zeiger übergeben werden? Gibt keinen so richtigen Sinn, 
deshalb gehe ich davon aus, daß sich die Aussage

> Nutzdaten werden als Zeiger an die Funktion ¨ubergeben und m¨ussen nicht
> erst allokiert werden.

nicht darauf bezieht.

> Ich muss aber meine Listobject, also frame_t allozieren, oder meinen die
> mit Nutzdatenobject das Listobjekt ??.

Das dachte ich zumindest.

[Karl H. (kbuchegg)]

Hans Ulli Kroll schrieb:

> Die Nutzdaten werden als Zeiger übergeben !

Das ergibt im Zusammenhang mit dem vorgegebenen Datentyp 'double' keinen 
wirklichen Sinn. Ich denke hier ist 'Nutzdaten' synonym zu 
'Nutzdatenobjekt' zu sehen.

[Hans Ulli K. (Gast)]

So nochmal gelesen, die NUtzdaten der "double" wird per Zeiger 
übergeben.

Sample mit obigen Prototypen

int main (int argc, char **argv)
{
        double *nutzdaten;
        struct stack st;

        nutzdaten = malloc(sizeof(*nutzdaten));

        if (push(&st, nutzdaten) == NULL)
                pintf("stack push failed\n");

        /* Jetzt übergabe von NULL Pointer, der Stack soll sich nicht ändern */
        /*  Ist das Argument ein Nullzeiger, so nimmt die Funktion keine */
        /* Veräanderungen am.*/

        if (push(&st, NULL) == NULL)
              printf("stack push failed\n");


        return 0;
}

[Karl H. (kbuchegg)]

Karl Heinz schrieb:
> Hans Ulli Kroll schrieb:
>
>> Die Nutzdaten werden als Zeiger übergeben !
>
> Das ergibt im Zusammenhang mit dem vorgegebenen Datentyp 'double' keinen
> wirklichen Sinn. Ich denke hier ist 'Nutzdaten' synonym zu
> 'Nutzdatenobjekt' zu sehen.

Obwohl auch das nicht wirklich Sinn ergibt. Auf den einen malloc() im 
push() und den free() im pop() wärs auch nicht angekommen. Ganz im 
Gegenteil: das hätte es sogar vereinfacht ein vernünftiges Testprogramm 
zu schreiben.
Mit der Vorgabe des 'Ausserhalb-Allokierens' verkompliziert sich beim 
Aufrufer wieder alles.

[Hans Ulli K. (Gast)]

Weiter im Text ...

push und pop lasse ich mal aus, ds soll der Schüler machen.

void *top(struct stack *st)
{
        return st->top->item;
}

int stack_size(struct stack *st)
{
        return st->size;
}

Das einzige, was ich gerade vergessen habe:
Den Stack muss ich ausserhalb von main deklarieren !

struct stack st;

int main(int argc, char **argv)
{
         /* Der ganze Rest */
}

[Max H. (hartl192)]

Hans Ulli Kroll schrieb:
> Den Stack muss ich ausserhalb von main deklarieren !
Darf man fragen wieso?

[Hans Ulli K. (Gast)]

Wenn eine Variable in einer Funktion deklariert wird, dann wird diese 
auf dem Stack (CPU) abgelegt.

Der Wert, der Variablen ist nicht definiert.

Ausserhalb von main() sind diese NULL bzw. 0

Ich könnte es auch so machen

int main(int argc, char **)
{
        struct stack st;

        st.size = 0;
}

[Max H. (hartl192)]

Hans Ulli Kroll schrieb:
> Wenn eine Variable in einer Funktion deklariert wird, dann wird diese
> auf dem Stack (CPU) abgelegt.
und dort bleiben sie auch bis die Funktion beendet wird und wenn man 
einen Pointer darauf an eine Funktion übergibt kann man auch darauf 
zugreifen.

> Der Wert, der Variablen ist nicht definiert.
bis man etwas zuweist und wieso sollte man eine Variable verwenden wenn 
man nichts hineinspeichern will?

> Ausserhalb von main() sind diese NULL bzw. 0
Außerhalb der main ist das Programm zu ende, da interessiert es mich 
nicht mehr was in den Variablen stand und wenn doch würde ich sie 
irgendwie ausgeben.

[Martin (Gast)]

Das ist doch so einfach:

#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>

int push(char *text) {
        char foo[1024];
        sprintf(foo, "echo '%s' >> /tmp/test.log", text);
        system(foo);
        return 0;
}

int pop(char *text) {
        int n;
        FILE *foo;
        foo = popen("head -n 1 /tmp/test.log", "r");
        system("sed '1d' /tmp/test.log > /tmp/tmp.log");
        system("cp /tmp/tmp.log /tmp/test.log");
        n=fread(text, 1, 1024, foo);
        text[n]=0;
        fclose(foo);
        return 0;
}
int main() {
        char buffer[1025];
        push("hello world");
        push("hello world 1");
        push("hello world 2");
        push("hello world 3");
        pop(buffer);
        printf("%s", buffer);
        pop(buffer);
        printf("%s", buffer);
        pop(buffer);
        printf("%s", buffer);
        pop(buffer);
        printf("%s", buffer);
        return 0;
}

aber da gibt's noch viel elegantere Lösungen.
Ausserdem darf sich der Prof nicht beschweren, alles ist in C 
geschrieben.

[Rene H. (Gast)]

Meine Güte! Ihr seid ja eine Truppe.

Var a. : er ist ein Donnerstag Troll (meine Vermutung)
Var b. : google nach linked list und gut ist.

Es Grüsst,
René

[Hans Ulli K. (Gast)]

ROTFL

[Daniel A. (daniel-a)]

Eine Beispielimplementierung eines Stacks. Könnte hilfreich sein, 
beschränkt sich aber nicht auf double Werte.