Nun wollen wir einen Stack programmieren. Was ist ein STACK? Nun das ist eigentlich ganz simpel zu erklären. Sie kenne bestimmt die Funktion bei fast jedem Programm Rückgängig "Löschen" oder Rückgängig "Dies und Jenes" oder die Funktion "UNDO". Es wird dabei immer der Vorgang den sie zuvor gemacht haben wieder Rückgängig gemacht. Dies ganze Prinzip funktioniert nach dem LIFO - Prinzip (Last In First Out). Das heißt den letzten Vorgang den sie gemacht haben können sie als erstes wieder Rückgängig machen. Ganz so wie bei einem Beamten der eine Stapel Papier zu bearbeiten hat und es kommen immer wieder neue hinzu. Das Papier das ganz unten liegt wird auch als letztes bearbeitet. Beginnen wir mit einem leichten Beispiel.

Sie besitzen eine Firma die Bücher verkauft und arbeiten am Abend die Bestellungen nach dem LIFO - Prinzip durch, also nach dem Motto : "Die Ersten werden die Letzten sein". Folgende Struktur haben wir....

struct bestellung{
                   int kundennummer;
                   char buchtitel[50];
                   float preis;
                   struct bestellung *next;
                  };

struct bestellung *anfang, *neu, *kill;

Als erstes benötigen wir eine Art Unterlage auf der wir alles Ablegen. Der Inhalt dieser Unterlage ist eine Art DUMMY. Hier die Funktion zum Initialisieren des Stapels.....

int stackinit()
{
 if((anfang=(struct bestellung *)malloc(sizeof(struct bestellung))) != NULL)
  {
   anfang->next = NULL;
   anfang->kundennummer = 0;
   strcpy(anfang->buchtitel,"dummy");
   anfang->preis = 0;
   return 1;
  }
 else
   return 0;
}

Zuerst benötigen wir Speicherplatz für unsere "Auflagefläche" für weiter Elemente. Anschließend übergeben wir der Adresse auf dem der Zeiger anfang zeigt die DUMMY - Werte...

Jetzt benötigen wir eine Funktion mit der wir ein Element oben auf dem Stapel legen können (push).....

int push(int kdnum, char *titel, float pr)
{
 if((neu=(struct bestellung *)malloc(sizeof(struct bestellung))) != NULL)
  {
   neu->kundennummer = kdnum;
   strcpy(neu->buchtitel,titel);
   neu->preis = pr;

   neu->next = anfang->next;
   anfang->next=neu;
   return 1;
  }
 else
   return 0;
}

Zuerst allokieren wir wieder Speicherplatz für unser neues Element was auf dem Stapel gelegt werden soll. Dann übergeben wir unserem neuen Element die Daten (kundennummer,titel,preis).

neu->next = anfang->next;

Jetzt zeigt der next - Zeiger unseres neuem Elementes auf die Adresse von anfang->next. Was der NULL - Zeiger wäre...

Anschließend zeigt unsere "Auflagefläche" der DUMMY auf das neue Element mit.....

anfang->next=neu;

Der nächste Aufruf der Funktion push(..) würde dann fertig folgendermaßen aussehen...

Merken sie sich das das 2.Element auf der Liste immer auf NULL zeigt, da es ja auch das letzte ist was von der Liste wieder entfernt wird und wir ja auch ein Überprüfung brauchen ab wann wir das letzte Element der Liste entfernt haben.

Jetzt brauchen wir nur noch eine Funktion zum löschen bzw. entfernen des obersten Elementes (pop)...

void pop()
{
 kill = anfang->next;
 anfang->next=kill->next;
 free(kill);
}

Das ganze funktioniert in 3 Schritten. Zuerst übergeben wir an unseren Zeiger kill die Adresse des obersten Elementes (anfang->next)....

Jetzt kommt genau die Zeile über die sehr viele stolpern und nicht mehr Durchblicken....

anfang->next=kill->next;

Aber dafür ist es nun mal ein Stapel oder? Wenn sie das oberste Element entfernen welches ist dann das nächste Element das oben liegt? Richtig eines darunter. Und so sieht es nach dieser Zeile aus ...

Jetzt können wir den Speicherplatz wieder freigeben....

free(kill);

Hierzu jetzt die Funktionen mit einer main-Funktion zum testen von push() und pop()....

/*Download:stack.c*/ #include <stdio.h> #include <stdlib.h> #include <string.h> struct bestellung{ int kundennummer; char buchtitel[50]; float preis; struct bestellung *next; }; struct bestellung *anfang, *neu, *kill; int stackinit() { if((anfang=(struct bestellung *)malloc(sizeof(struct bestellung))) != NULL) { anfang->next = NULL; anfang->kundennummer = 0; strcpy(anfang->buchtitel,"dummy"); anfang->preis = 0; return 1; } else return 0; } int push(int kdnum, char *titel, float pr) { if((neu=(struct bestellung *)malloc(sizeof(struct bestellung))) != NULL) { neu->kundennummer = kdnum; strcpy(neu->buchtitel,titel); neu->preis = pr; neu->next = anfang->next; anfang->next=neu; return 1; } else return 0; } void pop() { kill = anfang->next; anfang->next=kill->next; free(kill); } int main() { struct bestellung *bearbeitet; int nummer,wahl; char buchtit[50]; float preis; stackinit(); do{ printf("-1- Bestellung eingeben\n"); printf("-2- Bestellung abschicken\n"); printf("-3- Programmende\n\n"); printf("Ihre Auswahl : "); scanf("%d",&wahl); switch(wahl) { case 1 : printf("Kundennummer.....: "); scanf("%d",&nummer); fflush(stdin); printf("Buchtitel........: "); scanf("%s",buchtit); fflush(stdin); printf("Preis............: "); scanf("%f",&preis);fflush(stdin); push(nummer,buchtit,preis); break; case 2 : if((bearbeitet=anfang->next) != NULL) { printf("\nKunde: %d\nBuchtitel : %s\nPreis : %.2f\n", bearbeitet->kundennummer,bearbeitet->buchtitel, bearbeitet->preis); printf("->Bestellung abgelierfert.\n\n"); pop(); } else if(anfang->next==NULL) { printf("Es sind keine Bestellungen vorhanden\n"); exit (0); } break; case 3 : if(anfang->next != NULL) { printf("Es sind noch Bestellung zu bearbeiten!\n"); wahl=4; } break; case 4 : break; default: printf("Falsche Eingabe!!!\n"); break; } }while(wahl != 3); printf("\nProgrammende!!!\n"); return 0; }

Ich habe die Funktionen stackinit(), push() und pop() in unser Programm der Personalverwaltung eingebaut und als Funktion zum Rückgängigen Löschen verwendet. Hier der Gesamte Quellcode des Programms zum download (personal.c oder xpersonal.c).....

personal.c (Win/DOS)             xpersonal.c (LINUX)