Anfängerfrage: Stack programmieren - Compilerfehler
-
Hallo,
mein Wissensstand in C ist sehr gering, Java liegt mir schon eher.
Für alle die mich jetzt noch nicht weggeklickt haben: Ich versuche grad mit Hilfe eines ergoogelten Stück Codes eben ein Stack (realisiert mit einem Array) zu schreiben, mit den grundlegenenden Funktionen pop(), push(), top(),.. An sich verstehe ich auch was im Code steht, aber mein Compiler gibt mir ne Fehlermeldung aus, und ich verstehe einfach nicht warum
#include <stdlib.h> #include <stdio.h> struct StackElement{ StackElement* next; char* data; };5 C:\Users\xx\Desktop\C\2.2\mains.c syntax error before "StackElement"
5 C:\Users\xx\Desktop\C\2.2\mains.c [Warning] no semicolon at end of struct or union
7 C:\Users\xx\Desktop\C\2.2\mains.c syntax error before '}' token
10 C:\Users\xx\Desktop\C\2.2\mains.c syntax error before "StackElement"
...
..
.Eigentlich find ich proggen sehr interessant, aber bei dem Prof inkl seinem miesen Script macht das echt kein Spaß
Hoffe jemand hilft mir weiter.
Grüße
-
Das muss wahrhaftig ein mieses Skript sein, denn korrekt müsste es
struct StackElement* next;
lauten.
-
Athar schrieb:
Das muss wahrhaftig ein mieses Skript sein
Nagut, aber der Teil war irgendwo im Internet aufgefischt
Wie dem auch sei, das war der Fehler, ein paar weitere konnte ich sogar selbstständig beheben
Vielen Dank für die schnelle Hilfe!!
-
normal macht man sowas ohne "StackElement* next;"
lg lolo
-
Eigentlich seh ich das genauso.. ist ja keine LinkedList?!
Ich würde eher eine Variable mit der Anzahl gespeicherter Elemente deklarieren, aber da bin ich in C wohl eher out. Vermutlich nimmt man einen Zeiger der...?
-
geht beides aber zusätzlich zum zeiger, einen teil des speichers solltest dir per malloc besorgen falls die maximalanzahl vorher noch nicht fest steht und dann bei bedarf mit realloc vergrößern...
lg lolo
-
Eine linked list als unterliegende Datenstruktur für einen Stack macht durchaus Sinn, da so Einfüge- und Löschoperationen am Anfang und am Ende in konstanter Zeit ablaufen können.
-
@Athar also mein stack kennt nur push() und pop() und die macht der in O(1)
lg lolo
-
Athar schrieb:
Eine linked list als unterliegende Datenstruktur für einen Stack macht durchaus Sinn, da so Einfüge- und Löschoperationen in der Mitte in konstanter Zeit ablaufen können.
ftfy. Das wäre dann aber freilich kein Stack mehr.
noobLolo schrieb:
also mein stack kennt nur push() und pop() und die macht der in O(1)
Und push() in o(x), wenn vergrössert werden muss. Wie bestimmt man x?
-
Eine Liste (richtig) implementiert hat mit Stackfunktionalität auch nur O(1) bei push() und pop().
-
Janjan schrieb:
Eine Liste (richtig) implementiert hat mit Stackfunktionalität auch nur O(1) bei push() und pop().
Richtig. Aber nur für grosse Werte von 1.
-
Janjan schrieb:
Eine Liste (richtig) implementiert hat mit Stackfunktionalität auch nur O(1) bei push() und pop().
ja aber dafür in diesem speziellen fall mit 2 zeigern pro element den doppelten speicher verbrauch.
mngbd schrieb:
Und push() in o(x), wenn vergrössert werden muss. Wie bestimmt man x?
keine ahnung
evtl. könnte man ja statt realloc einfach das letzte element des stacks mit einem neuen stack kaskadieren, sozusagen das beste aus beiden welten
lg lolo
-
noobLolo schrieb:
Janjan schrieb:
Eine Liste (richtig) implementiert hat mit Stackfunktionalität auch nur O(1) bei push() und pop().
ja aber dafür in diesem speziellen fall mit 2 zeigern pro element den doppelten speicher verbrauch.
sollten es nicht 3/2 mehr speicher verbrauch sein
-
Es ist grob n mehr Speicher. Denn jedes Element hat einen Zeiger auf sein Nachfoler. Bei einem üblichen Stack hat man nur einen Zeiger überhaupt.
-
Ich gehe davon aus, dass die linked list über ihren head und tail Buch führt und dass sie doppelt verkettet ist.
Der zusätzliche Zeiger kann durch Eigenheiten des Speichermanagement zu genau 0% mehr Speicherverbrauch führen. Einfach ausprobieren.
-
Athar schrieb:
Der zusätzliche Zeiger kann durch Eigenheiten des Speichermanagement zu genau 0% mehr Speicherverbrauch führen. Einfach ausprobieren.
bist du zauberer oder wie willst das machen
lg lolo
-
noobLolo schrieb:
bist du zauberer oder wie willst das machen
Nö, aber Speicher wird meist in Vielfachen von 8 bytes angefordert.
Mein
struct Node { Node* prev; Node* next; int value; };sind also 12 bytes + 4 bytes Verwaltungsaufschlag = 16 bytes.
Und ohne prev habe ich 8 bytes + 4 bytes = 12 bytes, aufgerundet auch 16 bytes.Kommt aber wie gesagt aufs System an. Anderswo kann der Overhead 8 bytes betragen und je nach Größe des Knotens schneidest du mit prev dann die nächsten 8 bytes an.