Stacks, wie schreibt man es richtig in C?

[tdkpaul]

In Folge von Prüfungsvorbereitungen schaue ich mir gerade C Programme an (Listen, Suchen, Algorithmen) und versuche das Wichtigste "auswendig" zu lernen. Naja, ich verstehe schon was, aber das Einfachste macht mir schon Probleme. Ich würde dennoch gerne wissen, wie es korrekt in C aussehen würde.

Beispielweise ist in einer Probeklausur diese Header Datei gegeben.

http://pastie.org/private/g0azmddocs0rxdeqvtwt3g

daraufhin habe ich die Funktion versucht zu implementieren (ich habe es zum Verständnis kommentiert, wie es auch in Aufgabenstellung der Probeklausur steht):

http://pastie.org/private/lcwccsbl5fqhe0grmspmw

Ich bin mir sicher hier ist einiges falsch, aber weiß keinen weiteren Ansatz.

 

[Matthias Reitinger]

Ich bin mir sicher hier ist einiges falsch, aber weiß keinen weiteren Ansatz.

Allerdings. Du gehst anscheinend davon aus,…

• dass stack::cont ein Array von ints ist. Schau dir mal die Definition von struct stack an: dort gibt es überhaupt kein Feld namens cont.
• dass stack::topp ein Index in dieses Array ist. Der Typ dieses Feldes ist aber struct element *, also ein Zeiger auf eine Struktur.

Habt ihr einfach verkettete Listen behandelt? Denn dieser Stack ist nichts anderes als eine einfach verkettete Liste. Als kleine Starthilfe gebe ich dir mal Implementierungen von init und top:

void init(Stack *s) {
  s->topp = NULL;
}

int top(Stack *s) {
  // Achtung, bei einem leeren Stack ist das Verhalten hier undefiniert!
  return s->topp->cont;  
}

Schaffst du die anderen Operationen jetzt selbst?

Grüße,
Matthias

 

[tdkpaul]

Bin mir überhaupt nicht mehr sicher. Habe gerade Übungsaufgaben mit Listen, Baumstrukturen verstanden, aber hier bin ich gerade verwirrt.
So habe ich es nun:

void pop(Stack *s) {
	
	s->topp->cont[s->topp];
	(s->topp)--;
	
}

void push(Stack *s, int i) {
	
	(s->topp)++;	
	s->topp->cont = i;
	
}

 

[Matthias Reitinger]

Bin mir überhaupt nicht mehr sicher. Habe gerade Übungsaufgaben mit Listen, Baumstrukturen verstanden, aber hier bin ich gerade verwirrt.
So habe ich es nun:

void pop(Stack *s) {
	
	s->topp->cont[s->topp];
	(s->topp)--;
	
}

Welchen Datentyp besitzt s->topp->cont? Was für eine Auswirkung soll deiner Meinung nach die Zeile s->topp->cont[s->topp] haben? s->topp ist ein Zeiger. Was erwartest du dir davon, dass du ihn hier dekrementierst? Verweist der Zeiger danach auf einen gültigen (reservierten) Speicherbereich?

void push(Stack *s, int i) {
	
	(s->topp)++;	
	s->topp->cont = i;
	
}

Was erwartest du dir davon, dass du hier s->topp inkrementierst? Verweist der Zeiger danach auf einen gültigen (reservierten) Speicherbereich?

Ist dir aufgefallen, dass du den Strukturmember element::next überhaupt nicht verwendet hast? Was ist mit isEmpty passiert?

Du musst in push dynamisch Speicher für ein neues element reservieren und dieses als erstes Element in die einfach verkettete Liste einhängen. In pop hängst du das erste Element wieder aus und gibst den Speicher wieder frei.

\edit: Vielleicht trägt eine kleine „Zeichnung“ zum Verständnis bei. Einige Operationen und die Zustände der Datenstruktur:

init(s);

+- stack -+
| topp:  o-->NULL
+---------+

push(s, 1);

+-(stack)-+  +-(element)-+
| topp:  o-->| next:    o-->NULL
+---------+  | cont:  1  |
             +-----------+

push(s, 2);

+-(stack)-+  +-(element)-+  +-(element)-+
| topp:  o-->| next:    o-->| next:    o-->NULL
+---------+  | cont:  2  |  | cont:  1  |
             +-----------+  +-----------+

pop(s);

+-(stack)-+  +-(element)-+
| topp:  o-->| next:    o-->NULL
+---------+  | cont:  1  |
             +-----------+

Grüße,
Matthias

 

[Vereth]

Wenn du Listen verstehst, dann ist ein Stack einfach zu erklären. Ein Stack ist eine LIFO-Datenorganistion, Last-In-First-Out. Man kann es, wie oben gezeigt, als einfach verkettete Liste implementieren. Wenn ein Element gepusht wird, wird das neue Element an den Beginn der bisherigen Liste eingefügt. Beim Pop wird dieses entfernt, und dessen Nachfolger wird der neue Listenkopf.

 

[Anfänger92]

Hi,

Da deine Überschrift ja "Stacks, wie schreibt man es richtig in C? " ist, wollte ich nur mal erwähnen das Stacks eigentlich nicht als verkette Liste implementiert werden... Zumindest nicht so wie der Prozessor sie benutzt.

Normalerweise wird ein Speicherbereich erstellt und die ein Zeiger auf das Ende dieses Speicherbereichs gesetzt.
Wird ein Wert hinzugefügt, wird er an die Stelle geschrieben auf die der Zeiger zeigt und anschließend wird der Zeiger um die Größe des geschriebenen Wertes verringert.

Gruß
Anfänger

 

[Matthias Reitinger]

Da deine Überschrift ja "Stacks, wie schreibt man es richtig in C? " ist, wollte ich nur mal erwähnen das Stacks eigentlich nicht als verkette Liste implementiert werden... Zumindest nicht so wie der Prozessor sie benutzt.

Normalerweise wird ein Speicherbereich erstellt und die ein Zeiger auf das Ende dieses Speicherbereichs gesetzt.
Wird ein Wert hinzugefügt, wird er an die Stelle geschrieben auf die der Zeiger zeigt und anschließend wird der Zeiger um die Größe des geschriebenen Wertes verringert.

Das kommt ganz klar auf den konkreten Anwendungsfall an. Wenn man nicht oder nur schlecht abschätzen kann, wie „hoch“ der Stack maximal wird, ist eine Listenimplementierung praktischer. Diese Flexibilität muss man allerdings mit einem höheren Speicherverbrauch bezahlen. Bei einer Prüfungsfrage ist das aber sowieso egal. Wenn eine Implementierung mit Listen verlangt ist, bekommt man auf eine Implementierung mit Arrays keine Punkte.

Grüße,
Matthias

 

[Vereth]

Prinzipiell ist das richtig, was Anfänger92 schreibt, allerdings praktisch nur für Assembler. Allerdings ist das Padding zu beachten, vor allem dann, wenn Daten unterschiedlichen Typs gespeichert werden sollen. In einer Hochsprache wie C ist eine Listenimplementierung eigentlich der Normalfall.