stapelspeicher.tex

\section{Anwendung: Verketette Listen}

Wir wenden das bisher gelernte nun auf sogenannte verkettete Listen an.
Es handelt sich dabei um eine Datenstruktur, die es erlauben soll einfach Listenelement an belibieger Position hinzu zu fügen oder zu löschen.
Das grundlegende Elemen ist folgendes \verb|struct|:
\begin{lstlisting}
struct list
{
  int data;
  struct list *next;
}
\end{lstlisting}
Es enthält einmal ein Datum, hier \verb|data| genannt, und einen Zeiger \verb|next| wieder auf ein \verb|struct list|. 
Dieser Zeiger soll auf das nächste Element in der Liste zeigen.
Das letzte Element soll damit auf \verb|NULL| zeigen.
Dies ist in Abbildung~\ref{verklist} dargestellt.
Man nennt dieses Konzept auch Stapelspeicher, weil man es sich wie den Stapel Papiere auf dem Schreibtisch vorstellen kann.
\begin{figure}[!ht]
% Generated with LaTeXDraw 2.0.8
% Sun Mar 05 19:02:52 CET 2017
% \usepackage[usenames,dvipsnames]{pstricks}
% \usepackage{epsfig}
% \usepackage{pst-grad} % For gradients
% \usepackage{pst-plot} % For axes
\scalebox{1} % Change this value to rescale the drawing.
{
\begin{pspicture}(0,0.)(16.0,4.)
\psframe[linewidth=0.04,dimen=outer](3.,1)(0.0,3.0)
\rput(1.2, 2.5){\texttt{element: 4}}
\rput(1.2, 2.0){\texttt{naechste}:} 
\rput(1.2, 1.5){\texttt{0x1b464c0}}
\rput(1.5, 0.5){\texttt{Adresse: 0x1b464a0}} 

\psline[linewidth=0.04cm](3.5,2.)(4.5,2.)
\psline[linewidth=0.04cm](4.25,2.5)(4.5,2)
\psline[linewidth=0.04cm](4.25,1.5)(4.5,2)
\psframe[linewidth=0.04,dimen=outer](8.,1)(5.0,3.0)
\rput(6.2, 2.5){\texttt{element: 6}}
\rput(6.2, 2.0){\texttt{naechste:}}
\rput(6.2, 1.5){\texttt{0x1b46480}}
\rput(6.2, 0.5){\texttt{0x1b464c0}}
\psline[linewidth=0.04cm](8.5,2.)(9.5,2.)
\psline[linewidth=0.04cm](9.25,2.5)(9.5,2)
\psline[linewidth=0.04cm](9.25,1.5)(9.5,2)

\psframe[linewidth=0.04,dimen=outer](13.,1)(10.0,3.0)
\rput(11.2, 2.5){\texttt{element: 8}}
\rput(11.2, 2.0){\texttt{naechste:}}
\rput(11.2, 1.5){\texttt{NULL}}
\rput(11.2, 0.5){\texttt{0x1b46480}}
\psline[linewidth=0.04cm](13.,2.)(14.,2.)
\psline[linewidth=0.04cm](13.75,2.5)(14.,2)
\psline[linewidth=0.04cm](13.75,1.5)(14.,2)
\rput(15, 2.){\texttt{\LARGE NULL}}
\end{pspicture} 
}
\caption{Einmal Verketette Liste\label{verklist}}
\end{figure}

Nun müssen wir Funktionen definieren, die Elemente im Stapelspeicher hinzufügen oder entfernen.
Üblicherweise definiert man die folgenden zwei Funktionen:
\begin{itemize}
\item \texttt{push()}: Füge ein Element im Stapelspeicher hinzu
\item \texttt{pop()} : Entferne das zuletzt gespeicherte Element
\end{itemize}
dargestellt in Abbildung~\ref{stapspeicher}.
Ein Stapelspeicher ist vom Typ \texttt{LIFO}: \texttt{L}ast \texttt{I}n \texttt{F}irst \texttt{O}ut.

\begin{figure}[!ht]
\begin{center}
% Generated with LaTeXDraw 2.0.8
% Sun Mar 05 20:17:29 CET 2017
% \usepackage[usenames,dvipsnames]{pstricks}
% \usepackage{epsfig}
% \usepackage{pst-grad} % For gradients
% \usepackage{pst-plot} % For axes
\scalebox{0.7} % Change this value to rescale the drawing.
{
\begin{pspicture}(0,-3)(12.0,3)
\psframe[linewidth=0.04,dimen=outer](3,3)(0.0,2)
\psframe[linewidth=0.04,dimen=outer](11.0,3)(8,2)
\pscustom[linewidth=0.04]
{
\newpath
\moveto(3.1,2.5)
%\lineto(7.5,1.5)
\curveto(3.3,2.5)(3.5,2.4)(4.5,1.7)
}
\rput(3.7, 2.8){\LARGE push}
\psline[linewidth=0.04cm](4.55,1.9)(4.5,1.7)
\psline[linewidth=0.04cm](4.4,1.6)(4.5,1.7)


\pscustom[linewidth=0.04]
{
\newpath
\moveto(7.5,2.5)
%\lineto(7.5,1.5)
\curveto(7.5,2.5)(6.8,2.5)(6.5,1.6)
}
\rput(6.7, 2.8){\LARGE pop}
\psline[linewidth=0.04cm](7.4,2.7)(7.5,2.5)
\psline[linewidth=0.04cm](7.4,2.3)(7.5,2.5)


\psframe[linewidth=0.04,dimen=outer](7,1.5)(4,0.5)
\psframe[linewidth=0.04,dimen=outer](7,0.2)(4,-0.8)
\psframe[linewidth=0.04,dimen=outer](7,-1.1)(4,-2.1)
\end{pspicture} 
}
\caption{Der Stapelspeicher\label{stapspeicher}}
\end{center}
\end{figure}

Für die einfachere Verwendung führen wir noch folgende Typdefinition durch
\begin{lstlisting}{list.h}
typedef struct list
{
  struct list *next;
  int data;
} list;
\end{lstlisting}
und fangen an, verschiedene Dateien zu verwenden.
Unsere Definition speichern wir in einer sogenannte \emph{header} Datei, die üblicherweise die Endung \texttt{.h} erhält.
Nun schreiben wir erst eine Funktion \verb|newlist|, die eine neue Liste erstellt und ein erstes Datum einfügt:
\begin{lstlisting}{newlist.c}
#include"list.h"

list *newlist(const int x)
{
  list *q = (list *)malloc(sizeof(list));
  if (q == NULL)
    {
      fprintf(stderr, "Error in Memory allocation\n");
      exit(1);
    }
  // Daten zuweisen
  q->data = x;
  // next zeigt auf NULL, da letztes und einziges Element
  q->next = NULL;
  return q;
}
\end{lstlisting}
und speichern sie in \texttt{newlist.c}.
Damit der von uns definierte Datentyp bekannt ist, müssen wir die header Datei \texttt{list.h} einbeziehen.
Der Rückgabewert dieser Funktion ist ein Zeiger auf das bisher einzige Listenelement.
Der Zeiger \verb|next| dieses Element zeigt auf \verb|NULL|, wie wir das definiert hatten.
Damit kann man jederzeit dieses Element als das letzte in der Liste idetifizieren.
Im wesentlich erzeugt \verb|newlist| ein neues Listenelement, bei dem \verb|next| auf \verb|NULL| zeigt.
Es sollte jetzt klar sein, wie man \verb|push| schreiben kann:
\begin{lstlisting}{push.c}
#include"list.h"

void push(const int x, list **first)
{
  list *temp = newlist(x); // erzeuge ein neues Element
  if ((*first) != NULL)
    { // existiert schon eine Liste?
      temp->next = (*first); // falls ja, setze den Zeiger
    }
  (*first) = temp; // temp ist das neue erste Element
  return;
}
\end{lstlisting}
die wir in der Datei \texttt{push.c} speichern.
\verb|pop| sollte dagegen das Datum des ersten Listenelements zurückgegen und dann das erste Listenlement löschen:
\begin{lstlisting}{pop.c}
#include"list.h"

int pop(list **first)
{
  if ((*first) == NULL)
    {
      fprintf(stderr, "Es gibt kein Element im Speicher\n");
      return 0;
    }
  int ret;
  ret = (*first)->data; // Extrahiere das Datum
  list *temp;
  temp = (*first)->next; // Setze den Zeiger auf das zweite Element
  free(*first); // Loesche das erste
  (*first) = temp; // das zweite ist jetzt das erste
  return ret; // Gib das Datum zurueck
}
\end{lstlisting}
Wenn das Stapelspeicher leer ist, wird eine Fehlermeldung ausgegeben.
Mit folgender Funktion kann die gesamte Liste ausgegeben werden:
\begin{lstlisting}{print_list.c}
#include<stdio.h>
#include"list.h"

void print_list(list *first)
{
  list *temp = (first); // existiert eine Liste?
  if (temp == NULL)
    {
      return;
    }
  while (1)
    {
      printf("%d ", temp->data); // momentanes Datum ausgeben
      temp = temp->next; // Zeiger auf das naechste Element setzen
      if (temp == NULL)
        { // Letztes Element erreicht
          break; // falls ja, Abbruch
        }
    }
  printf("\n");
}
\end{lstlisting}
Warum bekommen die Funktionen \verb|push| und \verb|pop| ein Element vom Typ \verb|list **| übergeben und die Funktion \verb|print_list| lediglich ein Element vom Typ \verb|list *|?
Es handelt sich wiederum um den Unterschied zwischen \emph{call by reference} and \emph{call by value}.
Die Funktion \verb|print_list| soll keine Änderungen an der Liste vornehmen.
Daher ist es ausreichend, das Objekt selbst übergeben zu bekommen.
\verb|push| und \verb|pop| aber sollen das erste Element der Liste verändern.
Deshalb ist hier \emph{call by reference} das effzienteste: Es wird direkt das Objekt selbst verändert, ohne das etwas hin- oder herkopiert werden müsste.

Mit all den Funktionsdefinitionen müssen wir die header Datei \texttt{list.h} nocheinmal modifizieren, damit die Prototypen der Funktionen auch in einem Hauptprogramm bekannt sind.
Wir fügen die Prototypen einfach hinzu:
\begin{lstlisting}{list.h}
typedef struct list
{
  struct list *next;
  int data;
} list;

list *newlist(const int x);
void push(const int x, list **first);
int pop(list **first);
void print_list(list *first);
\end{lstlisting}


Die Benutzung all dieser Funktionen wird mit folgendem Programm illustriert:
\begin{lstlisting}{main.c}
#include<stdlib.h>
#include"list.h"

int main()
{
  list *erste = NULL;
  push(2, &erste);
  print_list(erste);
  push(4, &erste);
  print_list(erste);
  push(6, &erste);
  print_list(erste);
  pop(&erste);
  print_list(erste);
  push(8, &erste);
  print_list(erste);
  pop(&erste);
  print_list(erste);
  return (0);
}
\end{lstlisting}
Die Übersetzung geht dann wie folgt:

\vspace*{0.5cm}
\begin{verbatim}
>$  gcc -std=c99 -Wall -pedantic push.c pop.c print_list.c newlist.c main.c \
     -o main.exe
\end{verbatim}
\vspace*{0.5cm}

\noindent Die Ausgabe dieses Programs sieht wie folgt aus:
\begin{verbatim}
2	
4 2
6 4 2	
4 2
8 4 2	
4 2
\end{verbatim}
Wie man sieht, bei Ausführung der ersten \texttt{pop} Anweisung wird das zuletzt hinzugefügte Element mit Datum $6$ aus der Liste entfernt.

Bisher ist noch nicht ersichtlich geworden, welchen Vorteil es haben kann den Quelltext auf verschiedene Dateien zu verteilen.
Obige Übersetzung kann auch wie folgt durchgeführt werden:

\vspace*{0.5cm}
\begin{verbatim}
>$  gcc -std=c99 -Wpedantic -c push.c -o push.o
>$  gcc -std=c99 -Wpedantic -c pop.c -o pop.o
>$  gcc -std=c99 -Wpedantic -c print_list.c -o print_list.o
>$  gcc -std=c99 -Wpedantic -c newlist.c -o newlist.o
>$  gcc -std=c99 -Wpedantic -c main.c -o main.o
>$  gcc -std=c99 push.o pop.o print_list.o newlist.o main.o -o main.exe
\end{verbatim}
\vspace*{0.5cm}

Der Parameter \texttt{-c} bewirkt, dass nur Maschinencode erzeugt wird, ohne eventuelle Referezen auf nur deklarierte Funktionen oder Variablen aufzulösen.
Dies geschieht dann erst in der letzten Zeile, die man \emph{linken} nennt.
Der große Vorteil dabei ist, dass wenn sich \texttt{push.c} ändert, nicht alles andere auch neu übersetzt werden muss, sondern nur das linken wiederholt werden muss.
Dies ist natürlich bei einem so kleinen Projekt wie unserem Beispiel kein richtiger Vorteil.
Aber bei einem großen Projekt mit mehreren hunderttausend Zeilen Code wird diese Trennung sehr wichtig.
\textbf{Bemerkung}: Diese Prozedur kann mit Hilfe von \texttt{make} oder verwandten Programmen automatisiert werden.
\endinput