pointersarrays.tex

\section{Felder und Zeiger}

Wir haben bisher zwar schon die \verb|scanf| Funktion benutzt, aber noch nicht erklärt, wie sie funktioniert.
Oder, genauer gesagt, wir haben noch nichts dazu gesagt, was \verb|&n| eigentlich bedeutet.
Der Rest von \verb|scanf| sollte eigentlich von der Benutzung von \verb|printf| klar sein.

Um das verstehen zu können, muss man sich zunächst noch einmal ins Gedächtnis rufen, das eine Variable im Prinzip aus zwei Dingen besteht:
Einerseits dem Typ der Variablen und andererseits der Speicheradresse, unter der ein Wert abgelegt wird.
Über den Typ der Variablen weiß ich, wie viele Bits im Speicher belegt sind, und wenn man die Anfangsadresse für das erste Bit kennt, dann kann die gesamte Anzahl an Bits auslesen und entsprechend dem Typ interpretieren.
C erlaubt Zugriff sowohl auf den Wert einer Variablen, als auch auf die Adresse, an der der Wert abgelegt ist.
Unterschieden wird zwischen den beiden mit dem \verb|&| Operator.
Für eine Variable \verb|n| repräsentiert \verb|n| den Wert und \verb|&n| die Speicheradresse.
Bei \verb|&n| spricht man auch von Zeiger (\emph{pointer}) und bei \verb|&| vom Adressoperator.

Die Funktion \verb|scanf| verlangt nun als zweites Argument einen Zeiger.
Der Typ wird in der Zeichenkette angegeben, so dass die Funktion unter der Adresse, die mit \verb|&| angegeben wird, den Wert ablegen kann.

Da Zeiger in C eine sehr wichtige Rolle spielt, gibt es für sie spezielle Datentypen:
\begin{lstlisting}
int n = 3; // eine Variable vom Typ int
int *address; // eine Variable vom Typ Zeiger auf int
address = &n; // address zeigt auf n
*address = 5; // *address representiert den Wert, der unter der Adresse address
              // gespeichert ist. man spricht von dereferenzieren
n == 5; // ist jetzt wahr.
\end{lstlisting}
Genauso gibt es einen Typ Zeiger auf \verb|double|, nämlich \verb|double*| und so weiter.
\begin{myblock}{Definition \texttt{Zeiger}}
Ein Zeiger ist eine Variable, die eine Adresse zusammen mit einem Datentyp speichert.
\end{myblock}
Um die Nützlichkeit von Zeigern zu veranschaulichen, führen wir zunächst Funktionen ein.
Eine Funktion kenne wir schon, das ist \verb|main|.
Eine beliebige Funktion wird nun über einen Namen, einen Rückgabewert und Eingangsparameter definiert.
Im folgenden Beispiel definieren wir eine Funktion, die zwei Parameter \verb|a, b| übergeben bekommt und diese um eins erhöht.
Anschließend sollen diese beiden neuen Werte zurückgegeben werden.
Die Funktion hat aber nur einen Rückgabewert.

Ein Weg, um dieses Problem zu lösen, ist das sogenannte \emph{call by reference}.
Was \textbf{nicht} funktioniert ist das folgende:
\begin{lstlisting}
#include <stdio.h>
// einfache Funktion um a,b um 1 zu erhoehen
void increment(int a, int b)
{
  a++;
  b++;
  return;
}

int main()
{
  int a = 2, b = 3;
  int ret = 0;
  printf("Wert vor der Funktion a=%d, b=%d\n", a, b);
  ret = increment(a, b); // die Variablen in unserem Block werden
                         // nicht veraendert!
  printf("Wert nach der Funktion a=%d, b=%d\n", a, b);
  return ret;
}
\end{lstlisting}
Der Grund ist, dass in der Funktion \verb|increment| neue Variablen \verb|a|, \verb|b| angelegt werden, die nur in der Funktion selbst sichtbar sind.
Sie haben also nichts mit den Variablen \verb|a|, \verb|b| in der Funktion \verb|main| gemein, außer dem Namen.
Man spricht hier von \emph{call by value}, da die Variablen \verb|a, b| in der Funktion \verb|increment| mit den Werten der Variablen aus \verb|main| initialisiert werden.
Deswegen liefern die \verb|printf| Aufrufe in den Zeilen 12 und 15 das gleiche Ergebnis.
Denn die Variablen \verb|a|, \verb|b| in \verb|main| wurden nicht verändert.

Bei \emph{call by reference} wird an Stelle des Wertes die Adresse übergeben.
\begin{lstlisting}
#include <stdio.h>
// einfache Funktion um a,b um 1 zu erhoehen
void increment(int *a, int *b)
{
  (*a)++;
  (*b)++;
  return;
}

int main()
{
  int a = 2, b = 3;
  int ret = 0;
  printf("Wert vor der Funktion a=%d, b=%d\n", a, b);
  ret = increment(&a, &b); // die Variablen in unserem Block werden
                           // direkt veraendert!
  printf("Wert nach der Funktion a=%d, b=%d\n", a, b);
  return ret;
}
\end{lstlisting}
Die Funktion bekommt also zwei Parameter vom Typ \verb|int*|, also Zeiger auf \verb|int|.
Dann wird mit dem Dereferenzierungsoperator \verb|*| der Wert, der unter den beiden Adressen gespeichert ist, um eins erhöht.
Das geschieht unter der Annahme, dass dort eine Variable vom Typ \verb|int| abgelegt ist.
Damit werden also direkt die Werte der Variable \verb|a, b| in \verb|main| verändert.

Zeiger kann man genau wie andere Variablen nutzen (womit auch klar ist, dass man auch Zeiger auf Zeiger definieren kann).
Folgendes Beispiel illustriert die Nutzung noch einmal, wobei \verb|NULL| der Nullzeiger ist:
\begin{lstlisting}
#include <stdio.h>

int main()
{
  int q = 10;
  int *p = NULL;
  p = &q;
  printf("Der Wert an der Adresse p ist:%d\n", *p);
  return 0;
}
\end{lstlisting}
In der fünften Zeile haben wir eine Variable vom Typ \verb|int| deklariert und mit dem Wert 10 initialisiert, in der sechsten Zeile eine Variable vom Typ \verb|int*|, die mit dem \verb|NULL| Zeiger initialisiert wurde.
In der siebten Zeile wird dann \verb|p| auf die Adresse von \verb|q| gesetzt.
Damit liefert die Dereferenzierung von \verb|p|, also \verb|*p|, den Wert von \verb|q|.
Dies ist in Abbildung \ref{pointfig} illustriert.
Zeigern dürfen nur gültige Adressen zugewiesen werden.
Dies kann allerdings, bis auf Ausnahmen, nicht vom Compiler überprüft werden.
Wenn doch keine gültige Adresse zugewiesen wurde, bekommt man bei Dereferenzierung den \emph{segmentation fault} als Laufzeitfehler.
Dieser Quelltext weist sehr wahrscheinlich eine ungültige Adresse zu:
\begin{lstlisting}
int *p = 42;
\end{lstlisting}
Allerdings wird im diesen Fall der Compiler sehr wahrscheinlich\footnote{Hängt leider vom Compiler ab.} eine Warnung geben, denn 42 ist vom Typ \verb|int|, und nicht vom Typ \verb|int*|.
GCC 6.3.1 gibt folgendes aus:
\begin{verbatim}
int-ptr.c:7:14: Warnung: Initialisierung erzeugt Zeiger 
           von Ganzzahl ohne Typkonvertierung [-Wint-conversion]
     int *p = 42;
              ^~
\end{verbatim}
Wenn der Compiler sich hier nicht beschwert, sollte man die Dokumentation studieren, um heraus zu finden, wie man diesen Typ von Warnung anschalten kann, oder, wenn das nicht möglich ist, den Compiler wechseln.



\begin{figure}[!ht]
\centering
% Generated with LaTeXDraw 2.0.8
% Thu Feb 23 15:10:59 CET 2017
% \usepackage[usenames,dvipsnames]{pstricks}
% \usepackage{epsfig}
% \usepackage{pst-grad} % For gradients
% \usepackage{pst-plot} % For axes
\scalebox{0.5} % Change this value to rescale the drawing.
{
\begin{pspicture}(0,-8.856719)(29.2,8.8767185)
%\usefont{T1}{ptm}{m}{n}
%\rput(3.9903126,-0.7267187){0x7ffc5a48eb88}
%\usefont{T1}{ptm}{m}{n}
%\rput(16.572031,-0.7267187){0x7ffc5a4860aa}
%\usefont{T1}{ptm}{m}{n}
\psframe[linewidth=0.04,dimen=outer](29.2,-1.8367188)(0.0,-5.6367188)
%\psframe[linewidth=0.04,dimen=outer](2.6,-6.436719)(0.2,-8.636719)
%\psframe[linewidth=0.04,dimen=outer](4.8,-6.436719)(2.6,-8.636719)
\psline[linewidth=0.04cm](4.9,-1.8367188)(4.9,-5.6367188)
\psline[linewidth=0.04cm](9.6,-1.8367188)(9.6,-5.6367188)
\psline[linewidth=0.04cm](15.0,-1.8367188)(15.0,-5.6367188)
\psline[linewidth=0.04cm](21.0,-1.8367188)(21.0,-5.6367188)
\psline[linewidth=0.04cm](26.0,-1.8367188)(26.0,-5.6367188)
%\usefont{T1}{ptm}{m}{n}
\rput(1.5,-2.8){\LARGE Typ:\texttt{int *}}
\rput(1.5,-3.9){\LARGE Name: p}

%\usefont{T1}{ptm}{m}{n}
\rput(22.6,-2.8){\LARGE Typ: \texttt{int}}
%\usefont{T1}{ptm}{m}{n}
\rput(22.6,-3.9){\LARGE Name: q}
%\usefont{T1}{ptm}{m}{n}
\rput(22.6,-4.9){\LARGE Wert: 10}
\rput(2.5,-4.9){{\LARGE Wert:} \large 0x7ffc5a48eb88}

%\usefont{T1}{ptm}{m}{n}
\rput(2.2,-6){\large Adresse 0x7ffc5a481188}

\rput(22.9,-6){\large 0x7ffc5a48eb88}
%\rput(3.6267188,-4.67185){0x7ffc5a48eb88}
\pscustom[linewidth=0.04]
{
\newpath
\moveto(5.0,-1.4)
%\lineto(7.5,1.5)
\curveto(10.,1.)(15.1,4.)(22.,-1.4)
}
\psline[linewidth=0.04cm](21.5,-1.6)(22,-1.4)
\psline[linewidth=0.04cm](21.7,-0.8)(22,-1.4)


\pscustom[linewidth=0.04]
{
\newpath
\moveto(5.0,-6.3)
%\lineto(7.5,1.5)
\curveto(10.,-7.)(15.1,-9)(22.,-6.3)
}
\psline[linewidth=0.04cm](5.5,-5.7)(5,-6.3)
\psline[linewidth=0.04cm](5.4,-6.9)(5,-6.3)

%\usefont{T1}{ptm}{m}{n}
\rput(13.5,-6.5){\LARGE *p liefert den Wert von q}
%\usefont{T1}{ptm}{m}{n}
\rput(12.,-0.5){\LARGE \&q liefert den Wert von p}
\end{pspicture}
}
%\usefont{T1}{ptm}{m}{n}
\rput(3.7720314,-5.826719){0x7ffc5a4860aa}
%\usefont{T1}{ptm}{m}{n}
\rput(3.5867188,-3.3267188){Name: p}
%\usefont{T1}{ptm}{m}{n}
\rput(3.3267188,-4.19267187){Wert:}
%\usefont{T1}{ptm}{m}{n}
\caption{\label{pointfig} Illustration Zeiger.}
\end{figure}

Zeiger sind in C doppelt wichtig, denn das wichtige Konstrukt von Feldern wird mit Hilfe von Zeigern realisiert.
Für unser Sortierbeispiel möchten wir beispielsweise nicht $n$ Variablen mit verschiedenen Namen \verb|a1|, \verb|a2|, ... deklarieren.
Das wäre nicht nur ästetisch unschön, sondern auch extrem unpraktisch.
Wie sollte man diese Variablennamen zum Beispiel in einer Schleife in Abhängigkeit von der Schleifenvariablen ansprechen?
Deshalb stellt C Felder, sogenannte \emph{arrays} zur Verfügung.
Normalweise wenn wir Zahlen sortieren möchten, möchten wir nicht jede Zahl, als
ein einzige Variable definieren. Für diesem Fall gibt uns die Sprache die Arrays
als Struktur. Die Arrays bestehen aus mehreren nacheinanderstehenden elementaren
Variablen mit den gleichen Datatypen. Für Indizierung verwendet man
die eckige Klammern.

\begin{myblock}{Definition \texttt{Array}}
    Ein Array ist eine Sammlung von Datenelementen vom gleichen Typ. Die
    Indizierung des Arrays geschieht mit positiven ganzen Zahlen von 0 bis
    Länge $N$ des Arrays minus eins, also $[0, N)$.
\end{myblock}

Die Länge des Arrays muss zur Zeit der Übersetzung (Kompilierung) bekannt sein.
Im Beispiel sieht das wie folgt aus:
\begin{lstlisting}
#include <stdio.h>

int main()
{
  const int n = 4;
  int array1[] = {1, 2, 3, 4}; // Deklaration und Initialisierung
  int array2[n]; // Deklaration, nicht initialisiert
  array2[0] = 1; // Zuweisung einzelner Elemente
  array2[1] = 2;
  array2[2] = 3;
  array2[3] = 4;
  return 0;
}
\end{lstlisting}
Hierbei wurden zwei \texttt{int} Arrays erzeugt.
Beide haben die Länge 4.
Die Länge des zweiten Arrays wurde mithilfe einer konstanten Variablen angegeben.
Alternativ kann man auch direkt 4 schreiben.
Auf die einzelnen Elemente des Arrays wird mit Hilfe des \verb|[]| Operators zugegriffen.
Man beachte, dass die Indizes bei $0$ anfangen, und bis $3$, also Länge des Arrays minus 1, laufen.

Die Benutzung von Arrays wird in folgendem Beispiel illustriert:
\begin{myexampleprogram}{Beispiel: Berechnung des Mittelwerts und der Varianz}
  Die Berechnung des Mittelwerts einer Datenreihe ist ein gutes Beispiel für die Benutzung von Arrays.
  Nehmen wir an, wir haben die folgend Daten gegeben:
\begin{lstlisting}
double data[] = {1.3, 2.4, 5.3, 2.4, 6.7, 3.5, 6.9, 1.3, 1.4, 4.5,
                 5.5, 5.3, 6.7, 2.1, 2.4, 3.3, 7.9, 0.3, 3.3, 1.5};
\end{lstlisting}
  und wir wollen den Mittelwert dieser Daten berechnen.
  Folgendes Program übernimmt diese Aufgabe:
\begin{lstlisting}
#include <stdio.h>

int main()
{
  const int size = 20;
  double data[] = {1.3, 2.4, 5.3, 2.4, 6.7, 3.5, 6.9, 1.3, 1.4, 4.5,
                   5.5, 5.3, 6.7, 2.1, 2.4, 3.3, 7.9, 0.3, 3.3, 1.5};

  // initialisiere mean zu 0
  double mean = 0.;
  for (int i = 0; i < size; i++)
    {
      mean += data[i];
    }
  mean /= (double)size;
  printf("Der Mittelwert ist %e\n", mean);
  return (0);
}
\end{lstlisting}
  Für die Varianz müssen wir auch noch die Quadrate aufsummieren.
  Wir modifizieren dafür die Schleife wie folgt:
\begin{lstlisting}
double mean = 0., xsq = 0.;
for (int i = 0; i < size; i++)
  {
    mean += data[i];
    xsq += data[i] * data[i];
  }
mean /= (double)size;
\end{lstlisting}
  Die Varianz können wir dann wie folgt berechnen und ausgeben:
\begin{lstlisting}
double var = xsq / (double)size - mean * mean;
printf("Die Varianz ist %e\n", var);
\end{lstlisting}
\end{myexampleprogram}
An dieser Stelle können wir jetzt auch die möglichen Parameter der Funktion \verb|main| einführen.
Die ist nämlich allgemein wie folgt definiert:
\begin{lstlisting}
int main(int argc, char *argv[])
{
  return (0);
}
\end{lstlisting}
An der Kommandozeile kann man dem Programm Parameter mitgeben.
Die Funktion \verb|main| erhält diese in Form einer Zeichkette.
Leerzeichen in dieser Zeichenkette werden als Trennzeichen interpretiert, so dass die Zeichenkette \verb|argc| Wörter enthält.
Das erste Wort ist immer der Name der Programms.
Die Wörter werden in \verb|argv| gespeichert.
Also, zum Bespiel
\begin{verbatim}
  ./main.exe 3 hallo
\end{verbatim}
liefert \verb|argc=3|, und \verb|argv[0] = "./main.exe"|, \verb|argv[1] = "3"| und \verb|argv[2] = "hallo"|.
\newpage
\begin{myexampleprogram}{Beispiel: \texttt{Näherung von $\pi$}}
  In diesem Beispiel berechnen wir $\pi$ näherungsweise.
  Dafür verwenden wir folgende Integraldarstellung von $\pi$:
  \begin{equation}
    \pi=4\cdot \int_{0}^{1} \mathrm{d}x \dfrac{1}{1+x^2}
  \end{equation}
  Das Integral berechnen wir numerisch, indem wir die Fläche unterhalb der Kurve als eine Summe abschätzen.
  Dabei bedienen wir uns der sogenannten Trapez-Regel.
  Wir teilen das Interval $[0,1]$ in $N$ gleichlange Unterintervalle auf.
  Den jeweilige linke Punkt des Intervals nennen wir $x_i$, $i=0,...,N$, wobei $x_n-x_{n-1}=\Delta=\mathrm{const}$.
  Auf jedem Unterintervall approximieren wir die Funktion linear, wie in folgender Abbildung dargestellt ist:
  \vspace{-5cm}
  \begin{center}
    %\begin{minipage}
    \includegraphics[width=.8\linewidth]{trapez1.ps}
%    \caption{Funktion $\drac{1}{1+x^2}$ und der Trapez-Regel\label{trapezrul}}
  \end{center}
  \vspace{-6cm}
  In unserem Fall sind die Punkte wie folgt gegeben
  \begin{displaymath}
    x_i = i/N\,,\qquad i = 0, ..., N-1\,.
  \end{displaymath}

  % TODO Put a proper bounding box!

  Definieren wir folgende Funktion
  \[
  f(x) = \frac{1}{1+x^2}\,,
  \]
  so können wir wie folgt über die Teilergebnisse summieren:
  \begin{equation}
    \int_{0}^{1} \mathrm{d}x \dfrac{1}{1+x^2}\approx \sum_{i=0}^{N-1}\frac{1}{2N}[f(x_i)+f(x_{i+1})]
  \end{equation}
  Hier ist der entsprechende C Quelltext, der Arrays benutzt:
\begin{lstlisting}
#include <stdio.h>
const int MAX = 10000;

int main()
{
  int N = 0;
  double f[MAX], x[MAX]; // double arrays der Laenge MAX
  scanf("%d", &N);
  // Pruefe die Eingabe
  if (N >= MAX)
    {
      printf("Fehler, zu vielen Stuetzstellen\n");
      return (-1);
    }
  if (N < 0)
    {
      printf("N muss groesser als 0 sein!\n");
      return (-2);
    }
  for (int i = 0; i < N; ++i)
    {
      x[i] = (double)i / (double)N;
      f[i] = 1. / (1 + x[i] * x[i]);
    }
  double summe = 0.;
  for (int i = 0; i < N - 1; ++i)
    {
      summe += (f[i] + f[i + 1]);
    }
  summe += f[N - 1] + 0.5; // Randterm
  printf("Die Naeherung von pi ist =%e\n", 2. / N * summe);
  return (0);
}
\end{lstlisting}
  Neben der Benutzung von Arrays, haben wir noch ein weiteres neues Konzept eingeführt.
  Bei der Division von $i/N$, beide vom Typ \verb|int|, in Zeile $10$ haben wir einen expliziten \emph{cast} nach \verb|double| durchgeführt, damit keine Division ganzer Zahlen durchgeführt wird.

  Dieses Beispiel hätten wir natürlich auch ohne Arrays durchführen können, aber es illustriert deren Benutzung.
\end{myexampleprogram}

Zum Indexoperator \verb|[]| ist es sehr wichtig zu wissen, dass dabei nicht überprüft wird, ob der Index größer ist, als die Länge des Arrays.
Folgendes geht also im Prinzip
\begin{lstlisting}
int list[5];
int i = 5;
list[i] = 3;
\end{lstlisting}
und wird vom Compiler übersetzt.
Im besten Fall erhält man dann bei der Ausführung dieses Codes einen \emph{segmentation fault}.
Im schlechtesten Fall ist \verb|list[5]| Speicher, auf den das Programm zugreifen kann.
Dann erhält man keinen Laufzeitfehler und modifiziert ungewollt Speicher, den man nicht modifizieren will.
Dies kann zu sehr seltsamem Verhalten des Programms führen, und das Finden eines solchen Fehlers ist sehr schwierig.
Deshalb sollte man Indizierungen immer mit großer Sorgfalt überprüfen.

\subsection{Zeichenketten oder Strings}

In C gibt es keinen elementaren Datentyp für Zeichenketten, sogenannte \emph{strings}.
Zeichenkette werden mit Hilfe von Arrays abgebildet.
Ein Zeichen kann in einer Variablen vom Typ \verb|char| gespeichert werden, siehe ASCII Zeichensatz.\footnote{%
    Die Größe des Datentyps \texttt{char} ist immer ein Byte, also 8 Bit.
    Eigentlich hätte man diesen Typ \texttt{byte} nennen sollen. Es können $2^8
    = 256$ verschiedene Zeichen gespeichert werden. Dies reicht für Englisch
    und ein paar Steuerzeichen, jedoch nicht für alle Sprachen dieser Welt. Der
    ASCII Zeichensatz nutzt die ersten 128 Zustände (also die ersten 7 Bit) für
    das im Englischen genutzte Alphabet. Die restlichen 128 Zustände werden
    abhängig vom  \emph{Encoding} interpretiert. Für Deutsch kann man
    \texttt{latin-1} nutzen. Je nach Encoding wird ein Zeichen mit Wert 204
    interpretiert. Ist das Encoding nicht die richtige, erscheinen die Umlaute
    nicht korrekt und scheinbar willkürliche Zeichen stehen an ihrer Stelle.
    Sprachen, die mehr als 128 verschiedene Zeichen brauche, können im oberen
    Teil von ASCII überhaupt nicht dargestellt werden. Die Einsicht, dass es
    mehr als 256 verschiedene Zeichen gibt, wurde im Unicode Standard
    manifestiert. Die Konsequenz ist jedoch, dass jetzt mehr als ein Byte pro
    Zeichen benötigt wird. UTF-8 ist inzwischen das Standard-Encoding, sodass
    beliebig viele verschiedene Zeichen in einer Textdatei genutzt werden
    können. Der Preis ist jedoch, dass ein Buchstabe jetzt beliebig viele Byte
    (meist eins) nutzt. Da hier der Fokus allerdings auf Numerischen Methoden
    liegt, wird nicht weiter auf die vielfältigen Probleme mit Encodings
    eingegangen.
}
Eine Zeichenkette kann also durch eine Array von Elementen vom Typ \verb|char| erzeugt werden.
Das Ende einer Zeichenkette wird durch das Zeichen \verb|\0| angegeben.
Im nächsten Beispiel lesen wir eine Zeichenkette von der Standardeingabe ein, bis wir das Zeichen für das Ende des Strings finden und testen, ob die Kette eine Zahl enthält:
\begin{lstlisting}
#include <stdio.h>
const int MAX_LENGTH = 1000;

int main()
{
  char string[MAX_LENGTH];
  int i = 0;
  int ergebnis = 0;
  scanf("%s", string);
  while (1)
    {
      if (string[i] == '\0' || i == MAX_LENGTH)
        break;
      if ((string[i] >= '0') && (string[i] <= '9'))
        {
          ergebnis = 1;
          break;
        }
      i++;
    }
  if (ergebnis)
    printf("Der String %s enthaelt mindestens eine Zahl\n", string);
  else
    printf("Der String enthaelt keine Zahlen\n");
  return 0;
}
\end{lstlisting}
Es wird zunächst eine Zeichenkette über die Tastatur eingelesen.
Offensichtlich ist \verb|string| ohne den Indexoperator \verb|[]| vom Typ \verb|char*|, also Zeiger auf \verb|char|.
Dann nutzen wir eine \verb|while| Schleife mit konstant wahrem logischem Ausdruck.
Die Schleife wird dann mit \verb|break| abgebrochen, wenn das Endstring-Zeichen gefunden wurde.
In der Schleife wird dann jedes Element der Kette darauf überprüft, ob es eine Zahl ist.
Dementsprechend wird die Variable \verb|ergebnis| gesetzt.

Vielleicht ist es Ihnen schon aufgefallen, aber der obige Beispielquelltext ist nicht sauber programmiert.
Der Grund ist die Tatsache, dass wir die Länge des eingelesenen Strings nicht überprüfen, und damit nicht wissen, ob die maximale Länge überschritten wurde, oder nicht.
Es kommt zu einem sogenannten \emph{buffer overflow}.
Im besten Fall bekommt man bei einem zu langen Array einen Laufzeitfehler.
Im schlechtesten Fall kann man allerdings in Speicher schreiben, der dafür nicht vorgesehen ist. Dies ist schnell eine Sicherheitslücke.
Es sollte also auf jeden Fall eine solche Überprüfung vorgenommen werden!

\subsubsection{\texttt{sprintf} und \texttt{snprintf}}

Die Manipulation von Zeichenketten ist oft ein wichtiger Bestandteil eines Programms, zum Beispiel um Ausgabedateinamen abh\"{a}ngig vom Wert einer Variable zu machen.

Hierf\"{u}r stehen in C die beiden Funktionen \texttt{sprintf} aund \texttt{snprintf} zur Verf\"{u}gung, welche wie das schon kennengelernte \texttt{printf} funktioniern.
Im Gegensatz zu \texttt{printf}, schreiben diese Funktionen jedoch direkt in eine sich im Speicher befindliche Zeichenkette.

\begin{lstlisting}
#include <stdio.h>
const int MAX_LENGTH = 1000;
const int SHORT_LENGTH = 50;

int main()
{
  char string[MAX_LENGTH];
  const int i = 42;
  sprintf(string, "The Answer to the Ultimate Question of Life, The Universe, and Everything is %d.\n\n", i);
  printf("%s", string);
  
  int rval;
  char short_string[SHORT_LENGTH];
  
  rval = snprintf(short_string, SHORT_LENGTH-1, "This is a test string.\n\n");
  if(rval >= SHORT_LENGTH) 
    printf("snprintf: The string was not completely written!\n");
  else 
    printf("snprintf: wrote %d characters\n", rval);
  printf("%s",short_string);
  
  /* ueberlange Zeichenkette wird in short_string geschrieben, Rueckgaberwert wird ueberprueft */
  rval = snprintf(short_string, SHORT_LENGTH-1, "The Answer to the Ultimate Question of Life, The Universe, and Everything is %d.\n", i);
  if(rval >= SHORT_LENGTH) 
    printf("snprintf: The string was not completely written!\n");
  
  printf("%s\n\n",short_string);
  
  // ACHTUNG: hier wird fremder Speicher ueberschrieben 
  sprintf(short_string, "The Answer to the Ultimate Question of Life, The Universe, and Everything is %d.\n", i);
  printf("%s",short_string); 
  
  return 0;
}
\end{lstlisting}

Ebenso wie bei \texttt{scanf}, besteht jedoch die Gefahr eines buffer overflows, wenn mit \texttt{sprintf} mehr Zeichen geschrieben werden, als eigentlich allokiert wurden.
Dies resultiert im schlimmsten Fall \emph{nicht} in einem Programmabsturz sondern darin, dass irgendeine Speicherstelle überschrieben wird.

Es ist deshalb Vorsicht geboten und \texttt{snprintf} sollte \texttt{sprintf} vorgezogen werden, da ersteres es erlaubt, die L\"{a}nge der geschriebenen Zeichenkette zu beschr\"{a}nken.
Desweiteren kann man durch \"{U}berpr\"{u}fung des R\"{u}ckgabewertes der Funktion feststellen, ob die Zeichenkette in den vorhandenen Speicher gepasst hat und so direkt auf den Fehler reagieren.

\noindent Ausgabe:
\begin{verbatim}
$ ./test
The Answer to the Ultimate Question of Life, The Universe, and Everything is 42.

snprintf: wrote 24 characters
This is a test string.

snprintf: The string was not completely written!
The Answer to the Ultimate Question of Life, The

The Answer to the Ultimate Question of Life, The Universe, and Everything is 42.
\end{verbatim}


\subsection{Zeigerarithmetik}

Man kann auch eine Zeichenkette initialisieren:
\begin{lstlisting}
#include <stdio.h>
int main()
{
  char string[] = {'H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', '\0'};
  char *pointer = NULL;
  pointer = &string[6];
  printf("Das siebte Zeichen im String ist %c\n", *pointer);
  return (0);
}
\end{lstlisting}
und dann mit \verb|pointer| auf einzelne Elemente der Zeichenkette zugreifen.
Das ist nicht nur ein alternativer Weg, um auf die Elemente eines Arrays zuzugreifen.
C stellt Zeiger intern als ganze Zahlen dar und auf jedem Zeigertyp sind auch arithmetische Operationen definiert.
Beispielsweise ist folgendes in C korrekter Quelltext:
\begin{lstlisting}
int list[5];
int *plist = NULL;
plist = list; // aequivalent zu plist = &list[0];
for (int i = 0; i < 5; i++)
  {
    *plist = i;
    plist++; // aequivalent zu plist = plist + 1; oder plist += 1;
  }
\end{lstlisting}
Mit unserer bisherigen Kenntnis des Operators \verb|++| würden wir erwarten, dass der Wert von \verb|plist| um eins erhöht wird.
Das ist im Prinzip auch richtig, allerdings findet die Erhöhung in Einheiten der Länge des Typs, auf den der Zeiger zeigt.
Und damit zeigt \verb|plist++| auf das nächste Element in der Liste \verb|list|.
Denn C reserviert für \verb|int list[5];| einen zusammenhängenden Speicherbereich der fünffachen Länge von \verb|int|.
\verb|list|, ohne den Indexoperator, ist selbst vom Typ \verb|int*|, und zeigt auf den Anfang dieses Speicherbereichs.
\verb|list[3]| ist dann äquivalent zu folgender Dereferenzierung: \verb|*(list + 3)|.
Und damit weißt obiger Beispielcode dem $i$ten Element von \verb|list| den Wert $i$ zu.
Genauso kann man den Indexoperator für Zeiger verwenden.
Im obigen Beispiel hätten wir auch
\begin{lstlisting}
int list[5];
int *plist = NULL;
plist = list; // equivalent zu plist = &list[0];
for (int i = 0; i < 5; i++)
  {
    plist[i] = i;
  }
\end{lstlisting}
schreiben können.
Im folgenden Beispiel finden sich einige der möglichen arithmetischen Operationen für Zeiger:
\begin{lstlisting}
#include <stdio.h>

int main()
{
  int sqnum[] = {1, 4, 9, 16, 25, 36, 49};
  int *pointer;
  int *pointer2;
  pointer = sqnum;
  pointer++;
  printf("Nach der Inkrementierung des Zeigers %d\n", *pointer);
  pointer--;
  printf("Nach der Dekrementierung des Zeigers %d\n", *pointer);
  pointer += 2;
  printf("Nach dem Hinzufuegen von 2 zum Zeiger %d\n", *pointer);
  pointer -= 2;
  printf("Nach dem Subtrahieren von 2 vom Zeiger %d\n", *pointer);
  ++pointer;
  pointer2 = &sqnum[4];
  printf("Zwischen pointer2 und pointer gibt es %ld Elemente\n",
         pointer2 - pointer);
  return (0);
}
\end{lstlisting}
Überlegen Sie sich, was obiges Programm als Ausgabe erzeugen wird, bevor Sie diesen Quelltext übersetzen und ausführen lassen.
Die \verb|++| Operation auf einen Zeiger vom Typ \verb|int| ist in Abbildung~\ref{pointinc} illustriert.

\begin{figure}[!ht]
  \centering
  % Generated with LaTeXDraw 2.0.8
  % Sun Feb 26 08:55:41 CET 2017
  % \usepackage[usenames,dvipsnames]{pstricks}
  % \usepackage{epsfig}
  % \usepackage{pst-grad} % For gradients
  % \usepackage{pst-plot} % For axes
  \scalebox{0.5} % Change this value to rescale the drawing.
           {
             \begin{pspicture}(0,-2.6)(33.6,2.62)

               \pscustom[linewidth=0.04]
                        {
                          \newpath
                          \moveto(4.5,0.5)
                          %\lineto(7.5,1.5)
                          \curveto(4.5,1.5)(9.0,3.)(13.5,0.5)
                        }
                        \psline[linewidth=0.04cm](12.9,1.2)(13.5,0.5)
                        \psline[linewidth=0.04cm](12.8,0.6)(13.5,0.5)

                        \rput(8.5,2.4){\LARGE *Pointer}


                        \psframe[linewidth=0.04,dimen=outer]( 3,-0.8)( 0.,-2.6)
                        \rput(4.5,-2.9){0x7ffc3fa500aa}
                        \rput(4.5,-1.49){0x7ffc3fa5bd20}
                        \rput(4.5,0.0){\LARGE Pointer}

                        \psframe[linewidth=0.04,dimen=outer]( 6,-0.8)( 3.,-2.6)
                        \psframe[linewidth=0.04,dimen=outer]( 9,-0.8)( 6.,-2.6)
                        \psframe[linewidth=0.04,dimen=outer](12,-0.8)( 9.,-2.6)
                        \rput(13.5,-1.49){\LARGE 1}
                        \psframe[linewidth=0.04,dimen=outer](15,-0.8)(12.,-2.6)
                        \rput(13.5,-2.9){0x7ffc3fa5bd20}
                        \rput(13.5,0.0){\LARGE sqnum[0]}


                        \rput(16.5,-1.49){\LARGE 4}
                        \psframe[linewidth=0.04,dimen=outer](18,-0.8)(15.,-2.6)
                        \rput(16.5,-2.9){0x7ffc3fa5bd24}
                        \rput(16.5,0.0){\LARGE sqnum[1]}


                        \rput(19.5,-1.49){\LARGE 9}
                        \psframe[linewidth=0.04,dimen=outer](21,-0.8)(18.,-2.6)
                        \rput(19.5,-2.9){0x7ffc3fa5bd28}
                        \rput(19.5,0.0){\LARGE sqnum[2]}


                        \rput(22.5,-1.49){\LARGE 16}
                        \psframe[linewidth=0.04,dimen=outer](24,-0.8)(21.,-2.6)
                        \rput(22.5,-2.9){0x7ffc3fa5bd32}
                        \rput(22.5,0.0){\LARGE sqnum[3]}
             \end{pspicture}
           }

           \vspace{1cm}
           \scalebox{0.5}{
             \begin{pspicture}(0,-2.6)(33.6,2.62)

               \pscustom[linewidth=0.04]
                        {
                          \newpath
                          \moveto(4.5,0.5)
                          %\lineto(7.5,1.5)
                          \curveto(4.5,1.5)(11.5,3.)(16.5,0.5)
                        }
                        \psline[linewidth=0.04cm](16.3,1.2)(16.5,0.5)
                        \psline[linewidth=0.04cm](15.5,0.6)(16.5,0.5)
                        \rput(8.5,2.4){\LARGE *Pointer}


                        \psframe[linewidth=0.04,dimen=outer]( 3,-0.8)( 0.,-2.6)
                        \rput(4.5,-2.9){0x7ffc3fa500aa}
                        \rput(4.5,-1.49){0x7ffc3fa5bd24}
                        \rput(4.5,0.0){\LARGE Pointer}

                        \psframe[linewidth=0.04,dimen=outer]( 6,-0.8)( 3.,-2.6)
                        \psframe[linewidth=0.04,dimen=outer]( 9,-0.8)( 6.,-2.6)
                        \psframe[linewidth=0.04,dimen=outer](12,-0.8)( 9.,-2.6)
                        \rput(13.5,-1.49){\LARGE 1}
                        \psframe[linewidth=0.04,dimen=outer](15,-0.8)(12.,-2.6)
                        \rput(13.5,-2.9){0x7ffc3fa5bd20}
                        \rput(13.5,0.0){\LARGE sqnum[0]}


                        \rput(16.5,-1.49){\LARGE 4}
                        \psframe[linewidth=0.04,dimen=outer](18,-0.8)(15.,-2.6)
                        \rput(16.5,-2.9){0x7ffc3fa5bd24}
                        \rput(16.5,0.0){\LARGE sqnum[1]}


                        \rput(19.5,-1.49){\LARGE 9}
                        \psframe[linewidth=0.04,dimen=outer](21,-0.8)(18.,-2.6)
                        \rput(19.5,-2.9){0x7ffc3fa5bd28}
                        \rput(19.5,0.0){\LARGE sqnum[2]}


                        \rput(22.5,-1.49){\LARGE 16}
                        \psframe[linewidth=0.04,dimen=outer](24,-0.8)(21.,-2.6)
                        \rput(22.5,-2.9){0x7ffc3fa5bd32}
                        \rput(22.5,0.0){\LARGE sqnum[3]}

             \end{pspicture}
           }
           \caption{\label{pointinc} Illustration zur Inkrementieren eines Zeigers von Typ int. Oben vor der Inkrementierung, unten nach der Inkrementierung.}
\end{figure}

An dieser Stelle müssen wir auf einen möglichen Fehler hinweisen.
Folgender Quelltext wird vom Compiler anstandslos übersetzt
\begin{lstlisting}
int main()
{
  int list[5]; // int array
  double *plist = (double *)list; // explizit cast
  *(plist + 1) = 3;
  return 0;
}
\end{lstlisting}
Wenn man Zeile $3$ durch
\begin{lstlisting}
double *plist = list; // without cast
\end{lstlisting}
übersetzen das die meisten Compiler auch noch, hoffentlich wenigstens mit einer Warnung.
Was ist problematisch an obigen Code:
\verb|plist + 1| zeigt nicht auf das zweite Element in \verb|list|.
Denn die Länge von \verb|double| und \verb|int| ist nicht identisch.
Da \verb|plist| vom Typ Zeiger auf \verb|double| ist, bedeutet \verb|plist + 1| dass die entsprechende Adresse um die Länge von \verb|double| erhöht wird.
Damit ist aber der Speicherbereicht von \verb|list| nicht mehr als \verb|int| interpretierbar.
Obiger Code wird also undefiniertes Verhalten nach sich ziehen!

Zusammenfassend können wir also die Elemente eines Arrays auf zwei verschiedene Arten und Weisen indizieren
\begin{enumerate}
\item mit dem Indexoperator \verb|[]|.
\item mit arithmetischen Operationen.
\end{enumerate}
Wie schon gesagt, intern behandelt C ein Array quasi als einen Zeiger.
Es gibt aber wichtige Unterschiede.
Wenn \verb|array| als Array deklariert ist, so darf man dessen Adresse nicht verändern.
Folgendes Beispiel erläutert dies:
\begin{lstlisting}
#include <stdio.h>
int main()
{
  int *pointer;
  int array[] = {1, 4, 9, 16, 25, 36, 49, 64};
  int i = 2;
  pointer = array; // pointer zeigt auf &array[0]
  printf("Die Werte sind identisch: %d %d\n", array[i], *(pointer + i));
  pointer++; // sinnvoll
  array++; // nicht erlaubt!
  array = pointer; // nicht erlaubt!
  return 0;
}
\end{lstlisting}
Abschließend diskutieren wir noch eine Subtilität für den Fall von Arrays für den Typ \verb|char|.
Dafür betrachten wir folgenden Beispielcode:
\begin{lstlisting}
int main()
{
  char *pointer = "Hello world";
  pointer[1] = 'a'; // uebersetzt, fuehrt aber zu einem segmentation fault!
  return 0;
}
\end{lstlisting}
In der dritten Zeile wird versucht, das zweite Element von \verb|pointer| auf das Zeichen \verb|a| zu setzen.
Obwohl dieser Quelltext vom Compiler übersetzt wird, wird es bei der Ausführung zu einem \emph{segmentation fault} kommen.
Das liegt daran, dass \verb|pointer| auf einen Bereich im Speicher zeigt, der nicht verändert werden darf.
Die Zeichenkette \verb|"Hello world"| wird zur Zeit der Übersetzung in einem Speicherbereich abgelegt, der nur gelesen werden darf.
Deswegen darf er dann nicht mehr verändert werden.

\endinput