ein Kapitel zurück                                           ein Kapitel weiter

Kommen wir nun zu Gegenteiligen Prinzip von zuvor. Mit dem Stapel haben wir das LIFO - Prinzip (Last In First out) kennen gelernt. Nun wollen wir das FIFO - Prinzip (First In First out). So sollte es eigentlich auch sein. Wer zuerst kommt malt zuerst. Das ganze können sich sich als Schlange vorstellen. Beim einfügen ist das 1.Element immer der Kopf, das 2. eins hinter dem Kopf usw. Und wenn sie nun auf diese Schlange zugreifen greifen sie automatisch auf das 1. Eingefügte Element. Wir wollen das Prinzip mal nutzen ein Programm zu schreiben. Kennen sie das wenn sie beim Arzt im Wartezimmer warten müssen bekommen sie doch so ein kleines Zettelchen mit einer Nummer. Dann warten sie bis an der dämlichen Wand so ein Kasten die selbe Nummer wie auf Ihren Zettel zeigt. Wir wollen jetzt ein Programm schreiben das in der Reihenfolge wie die Patienten kommen auch so drankommen.

Zuerst benötigen wir wieder eine Funktion zum Initialisieren der Schlange... 

int schlange_init()
{
 if((dummy=(struct reservierung *)malloc(sizeof(struct reservierung))) != NULL)
  {
   strcpy(dummy->name,"dummy");
   strcpy(dummy->vorname,"dummy");
   dummy->rnummer=0;

   dummy->previous=NULL;
   return 1;
  }
 else
  {
   fprintf(stderr,"Konnte keinen Speicher reservieren!!\n");
   return 0;
  }
}

Auch hier benutzten wir wieder einen DUMMY. Dieser zeigt dann auf immer auf den Anfang der Schlange. Zuerst reservieren wir einen Speicherplatz für unseren DUMMY und geben irgendwas ein. Unser previous - Zeiger zeigt somit am Anfang logischerweise wieder auf NULL ....


FIFO Schlangen


Als nächstes brauchen wir ein Funktion die ein neues Element immer ans Ende der Schlange hängt.... 

int put(struct reservierung *neu)
{
 struct reservierung *zeiger;
/*Ist es das 1.Element in der Schlange ?*/
 if(dummy->previous == NULL)
  { /*Es ist das 1. Element*/
   dummy->previous=neu;
   neu->previous=NULL;
   return 1;
  }
/*Es ist nicht das 1. Element*/
 else
  {
   zeiger=dummy;
/*Wir suchen das Ende der Schlange*/
   while(zeiger->previous != NULL)
      zeiger=zeiger->previous;

   zeiger->previous=neu;
   neu->previous=NULL;
   return 1;
  }
}

Als erstes überprüfen wir ob unser Aufhänger oder Anfang der Schlange hinter sich ein Element besitzt. Was am Anfang auch nicht der Fall sein wird. Falls nicht fügen wir unser neues Element mittels... 

dummy->previous=neu;

...hinter unserem Aufhänger. Und unser neues Element zeigt hinter sich momentan noch auf gar nichts...


Schlange FIFO


Falls unser dummy schon hinter sich auf ein Element zeigt suchen wir mittels... 

zeiger=dummy;
while(zeiger->previous != NULL)
    zeiger=zeiger->previous;

..bis unser zeiger->previous auf das Ende der Schlange zeigt. Anschließend hängen wir nach dem selben Schema, wie es schon mit dem ersten Element der Liste passiert ist, ans Ende der Liste. Ich denke mal die Funktion stellt eigentlich keine Schwierigkeit dar. Als nächstes benötigen wir noch eine Funktion, um das eingefügte Element in der Liste wieder zu entfernen und das 2. Element somit zum 1. zu machen..... 

void get()
{
 struct reservierung *zeiger;
/*Ist überhaupt etwas in der Schlange?*/
 if(dummy->previous != NULL)
  { /*Es ist...!*/
   zeiger=dummy->previous;
   dummy->previous=zeiger->previous;
   free(zeiger);
  }
 else
    fprintf(stderr,"Es sind keine Patienten im Wartezimmer.....\n");
}

Zuerst müssen wir überprüfen ob überhaupt ein Nachfolger von dummy vorhanden ist. Falls nicht ist die Liste leer. Ist die Liste nicht leer, dann lassen wir einen Zeiger auf das 1. Element der Liste zeigen .... 

zeiger=dummy->previous;



Schlange FIFO


Bevor wir das 1.Element auf das unser Zeiger zeiger zeigt mit free(zeiger) freigeben müssen wir noch eine Zeile Code einfügen damit das "noch" 2.Element zum 1. Element in der Liste wird.... 

dummy->previous=zeiger->previous;




Schlange FIFO




free(zeiger);


Schlange FIFO


Somit hätten wir alle Funktionen einer Schlange durch. Jetzt folgt nur noch schnell ein Demonstrations-Programm das unsere neu gelernte Funktionen einsetzt... 

/*Download:schlange.c*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct reservierung {
                      char name[20];
                      char vorname[20];
                      int rnummer;
                      struct reservierung *previous;
                    };

struct reservierung *dummy;
static int nummer = 1;


int schlange_init()
{
 if((dummy=(struct reservierung *)malloc(sizeof(struct reservierung))) != NULL)
  {
   strcpy(dummy->name,"dummy");
   strcpy(dummy->vorname,"dummy");
   dummy->rnummer=0;

   dummy->previous=NULL;
   return 1;
  }
 else
  {
   fprintf(stderr,"Konnte keinen Speicher reservieren!!\n");
   return 0;
  }
}

/*Wir hängen ein neues Element ans Ende der Schlange*/
int put(struct reservierung *neu)
{
 struct reservierung *zeiger;
/*Ist es das 1.Element in der Schlange ?*/
 if(dummy->previous == NULL)
  { /*Es ist das 1. Element*/
   dummy->previous=neu;
   neu->previous=NULL;
   return 1;
  }
/*Es ist nicht das 1. Element*/
 else
  {
   zeiger=dummy;
/*Wir suchen das Ende der Schlange*/
   while(zeiger->previous != NULL)
       zeiger=zeiger->previous;

   zeiger->previous=neu;
   neu->previous=NULL;
   return 1;
  }
}

/*Wir benötige das 1.Element der Liste das wir auch als 1. Eingegeben haben*/
void get()
{
 struct reservierung *zeiger;
/*Ist überhaupt etwas in der Schlange?*/
 if(dummy->previous != NULL)
  { /*Es ist...!*/
   zeiger=dummy->previous;
   dummy->previous=zeiger->previous;
   free(zeiger);
  }
 else
   fprintf(stderr,"Es sind keine Patienten im Wartezimmer.....\n");
}

void eingabe()
{
 struct reservierung *neu;
 char n[20],vn[20];
 int tisch;

 if((neu=(struct reservierung *)malloc(sizeof(struct reservierung))) != NULL)
  {
   printf("Name.....: ");
   strcpy(neu->name,(gets(n)));fflush(stdin);
   printf("Vorname..: ");
   strcpy(neu->vorname,(gets(vn)));fflush(stdin);
   printf("Nummer...: ");
   printf("%d\n",neu->rnummer = nummer++);
   neu->previous=NULL;
   put(neu);
  }
}

void ausgabe()
{
 if(dummy->previous != NULL)
  {
   printf("\n%s, %s Nummer.: %d \n\n",
   dummy->previous->name,dummy->previous->vorname,
   dummy->previous->rnummer);
   get();
  }
 else
   printf("Keine Patienten im Wartezimmer vorhanden!!!\n");
}


int main()
{
 int wahl;

 schlange_init();

 do {
      printf("-1- Reservierung eingeben\n");
      printf("-2- Nächster Patient\n");
      printf("-3- Programmende\n\n");
      printf("Ihre Wahl : ");
      scanf("%d",&wahl);
      fflush(stdin);

      switch(wahl)
       {
         case 1 : eingabe();
                      break;
         case 2 : ausgabe();
                       break;
         case 3 : if(dummy->previous != NULL)
                       {
                        printf("Es sind noch Patienten im Wartezimmer!!!\n");
                        wahl=4;
                        }
                      break;
         case 4 : break;
         default: printf("Falsche Eingabe!!\n\n");
       }
     }while(wahl != 3);
 printf("\n\n\t\tProgrammende\n");
 return 0;
}

Hiermit schließen wir vorerst mal mit dem Kapitel "verkettete Listen". Später werden wir nochmals auf diese Thema zurückgreifen müssen. Nämlich wenn es um binäre Bäume geht. Aber dafür benötigen wir zuerst mal Kenntnisse in Rekursionen.

ein Kapitel zurück          nach oben           ein Kapitel weiter


© 2001,2002 Jürgen Wolf