Skip to content
Snippets Groups Projects
Select Git revision
  • 9f7d724a85529aa0d74a523aef2519af61a7d7e9
  • main default protected
2 results

01-typ.ipynb

Blame
  • hp-2020.tex 223.61 KiB
    % hp-2018ws.pdf - Lecture Notes on Applied Computer Sciences
    % Copyright (C) 2012, 2013, 2015, 2016, 2018  Peter Gerwinski
    %
    % This document is free software: you can redistribute it and/or
    % modify it either under the terms of the Creative Commons
    % Attribution-ShareAlike 3.0 License, or under the terms of the
    % GNU General Public License as published by the Free Software
    % Foundation, either version 3 of the License, or (at your option)
    % any later version.
    %
    % This document is distributed in the hope that it will be useful,
    % but WITHOUT ANY WARRANTY; without even the implied warranty of
    % MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    % GNU General Public License for more details.
    %
    % You should have received a copy of the GNU General Public License
    % along with this document.  If not, see <http://www.gnu.org/licenses/>.
    %
    % You should have received a copy of the Creative Commons
    % Attribution-ShareAlike 3.0 Unported License along with this
    % document.  If not, see <http://creativecommons.org/licenses/>.
    
    \documentclass[a4paper]{article}
    
    \usepackage{pgscript}
    \usepackage{pdftricks}
    \usepackage{rotating}
    \usepackage{amsfonts}
    \usepackage[helvet]{sfmath}
    \usepackage{tikz}
    
    \newcommand{\name}[1]{\textsc{#1}}
    \newcommand{\ccbysanp}{CC-by-sa (Version 3.0, nicht portiert)}
    \newcommand{\fdl}{GNU FDL (Version 1.2 oder höher)}
    \newcommand{\mylicense}{CC-by-sa (Version 3.0) oder GNU GPL (Version 3 oder höher)}
    \newcommand{\pd}{gemeinfrei -- \emph{public domain}}
    
    \newcommand{\underconstruction}{%
      \begin{minipage}{6cm}
        \begin{center}
          \includegraphics[width=2cm]{Zeichen_123.pdf}
    
          Dieser Abschnitt ist\\
          noch nicht fertig.
        \end{center}
      \end{minipage}}
    
    \makeatletter
      \newcommand{\figurecaptionraw}[2]{%
        \def\n{\hfill\break}
        \refstepcounter{figure}%
        \addcontentsline{lof}{figure}%
          {\protect\numberline{\hspace{-1.5em}Abb.~\thefigure}{\ignorespaces #1}}%
        \begingroup
          \def\n{\break}
          \@makecaption{\csname fnum@figure\endcsname}{\ignorespaces #1}\par
        \endgroup
        \addtocontents{lof}{\begingroup\leftskip3.8em #2\par\endgroup}
      }
    \makeatother
    \newcommand{\figurecaptionurl}[5]{%
      \figurecaptionraw{#1}{Quelle: \protect\url{#2},\protect\\abgerufen am #3\protect\\Autor: #4\protect\\Lizenz: #5}}
    \newcommand{\figurecaptionurlurl}[5]{%
      \figurecaptionraw{#1}{Quelle: \protect\url{#2},\protect\\abgerufen am #3\protect\\Autor: \protect\url{#4}\protect\\Lizenz: #5}}
    \newcommand{\figurecaptionself}[1]{\figurecaptionraw{#1}{Quelle/Autor: selbst erstellt\protect\\Lizenz: \mylicense}}
    
    \begin{psinputs}
      \usepackage{pgscript}
      \usepackage{pstricks,pst-grad,pst-node,pst-plot}
      \psset{unit=1cm}
    \end{psinputs}
    
    \begin{document}
      \thispagestyle{empty}
      \makebox(0,0.0105)[tl]{\includegraphics[scale=1.008]{logo-hochschule-bochum-cvh-text-v2.pdf}}\hfill
      \makebox(0,0)[tr]{\includegraphics[scale=0.7]{logo-hochschule-bochum.pdf}}%
      \vfill
      \begin{center}
        {\Huge\textbf{Hardwarenahe Programmierung}\par}
        \vspace{2cm}
        {\large Wintersemester 2019/20\\[\medskipamount]
        Prof.~Dr.~rer.~nat.~Peter Gerwinski}
      \end{center}
      \vfill
    
      \clearpage
    
      \begingroup
    
        \setlength{\leftskip}{3cm}
    
        \strut\vfill
    
        Stand: 11.\ Januar 2020
    
        Soweit nicht anders angegeben:\\
        Text und Bilder: Copyright \copyright\ 2012, 2013, 2015, 2016, 2018, 2020\quad Peter Gerwinski\\
        Lizenz: \mylicense
    
        Sie können dieses Skript
        einschließlich Vortragsfolien, Beispielprogramme und sonstiger Lehrmaterialien
        unter \url{https://gitlab.cvh-server.de/pgerwinski/hp} herunterladen.
    
      \endgroup
    
      \clearpage
    
      \tableofcontents
    
      \clearpage
    
      \section{Einführung}
    
      \subsection{Was ist hardwarenahe Programmierung?}
    
    %  Die angewandte Informatik befaßt sich mit der Praxis der Programmierung von Computern.
    %  Sie vermittelt zwischen den Fachgebieten der Rechnertechnik
    %  ("`Wie funktioniert ein Computer?"') und der Softwaretechnik (Theorie des Programmierens).
    
      In der Programmierung steht "`hardwarenah"'
      für maximale Kontrolle des Programmierers über das genaue Verhalten der Hardware.
      Im Gegensatz zur abstrakten Programmierung,
      in der man als Programmierer in einer für Menschen möglichst komfortablen Weise
      das gewünschte Verhalten des Computers beschreibt
      und des den Programmierwerkzeugen überläßt,
      auf welche Weise genau der Computer dies umsetzt,
      geht es in der hardwarenahen Programmierung darum,
      das Verhalten des Prozessors und jeder einzelnen Speicherzelle genau zu kennen.
      
      \begin{center}
        \begin{pdfpic}
          \begin{pspicture}(-5,0)(12,12)
            \small
            \psset{unit=0.5cm}
            \psline[arrows=<->](-1,0)(-1,22)
            \rput(-1.3,0){\makebox(0,0)[br]{\textbf{gegenständlich}}}
            \rput(-1.3,22){\makebox(0,0)[tr]{\textbf{abstrakt}}}
            \rput(-1.3,2){\makebox(0,0)[r]{Elektromagnetismus, Halbleiter}}
            \rput(-1.3,4){\makebox(0,0)[r]{Elektronische Bauelemente}}
            \rput(-1.3,6){\makebox(0,0)[r]{Logik-Schaltkreise}}
            \rput(-1.3,8){\makebox(0,0)[r]{Prozessoren}}
            \rput(-1.3,9){\makebox(0,0)[r]{Maschinensprache}}
            \rput(-1.3,10){\makebox(0,0)[r]{Assembler}}
            \rput(-1.3,11){\makebox(0,0)[r]{Ein-/Ausgabe}}
            \rput(-1.3,12.35){\makebox(0,0)[r]{\textbf{hardwarenahe Programmierung} (z.\,B.\ in C)}}
            \rput(-1.3,14){\makebox(0,0)[r]{\shortstack[r]{abstrahierende Programmierung\\(z.\,B.\ in C++, Java)}}}
    %          \rput(-1.3,15){\makebox(0,0)[r]{Programmierung}}
            \rput(-1.3,16){\makebox(0,0)[r]{Algorithmen, Datenstrukturen, Software-Entwurf}}
            \rput(-1.3,17){\makebox(0,0)[r]{Requirements Engineering}}
            \rput(-1.3,18){\makebox(0,0)[r]{formale Sprachen, Berechenbarkeit}}
            \rput(-1.3,19){\makebox(0,0)[r]{mathematische Strukturen}}
            \rput(-1.3,20){\makebox(0,0)[r]{mathematische Beweise}}
            \rput(2.1,0.5){\makebox(0,0)[l]{Physik}}
            \rput(4.1,4){\makebox(0,0)[l]{Elektrotechnik}}
            \rput(6.1,8){\makebox(0,0)[l]{Rechnertechnik}}
            \rput(8.1,12.35){\makebox(0,0)[l]{angewandte Informatik}}
            \rput(10.1,16){\makebox(0,0)[l]{\shortstack[l]{Softwaretechnik und\\theoretische Informatik}}}
            \rput(12.1,21){\makebox(0,0)[l]{Mathematik}}
            \psset{linewidth=0.001,linestyle=none,fillstyle=gradient,gradmidpoint=1.0,gradlines=1000}
            \definecolor{RGBwhite}{rgb}{1.0,1.0,1.0}
            \definecolor{RGBblue}{rgb}{0.0,0.0,1.0}
            \definecolor{RGBred}{rgb}{1.0,0.0,0.0}
            \definecolor{RGBgreen}{rgb}{0.0,1.0,0.0}
            \definecolor{RGByellow}{rgb}{1.0,1.0,0.0}
            \definecolor{RGBorange}{rgb}{1.0,0.7,0.0}
            \definecolor{RGBgrey}{rgb}{0.7,0.7,0.7}
            \rput(0,2){\psframe[gradbegin=RGBwhite,gradend=RGBblue](2,2)}
            \rput(0,0){\psframe[fillstyle=solid,fillcolor=RGBblue](2,2.01)}
            \rput(2,6){\psframe[gradbegin=RGBwhite,gradend=RGBred](2,2)}
            \rput(2,2){\psframe[gradbegin=RGBred,gradend=RGBwhite](2,2)}
            \rput(2,3.99){\psframe[fillstyle=solid,fillcolor=RGBred](2,2.02)}
            \rput(4,10){\psframe[gradbegin=RGBwhite,gradend=RGBgreen](2,2)}
            \rput(4,6){\psframe[gradbegin=RGBgreen,gradend=RGBwhite](2,2)}
            \rput(4,7.99){\psframe[fillstyle=solid,fillcolor=RGBgreen](2,2.02)}
            \rput(6,14){\psframe[gradbegin=RGBwhite,gradend=RGByellow](2,2)}
            \rput(6,10){\psframe[gradbegin=RGByellow,gradend=RGBwhite](2,2)}
            \rput(6,11.99){\psframe[fillstyle=solid,fillcolor=RGByellow](2,2.02)}
            \rput(8,18){\psframe[gradbegin=RGBwhite,gradend=RGBorange](2,2)}
            \rput(8,14){\psframe[gradbegin=RGBorange,gradend=RGBwhite](2,2)}
            \rput(8,15.99){\psframe[fillstyle=solid,fillcolor=RGBorange](2,2.02)}
            \rput(10,18){\psframe[gradbegin=RGBgrey,gradend=RGBwhite](2,2)}
            \rput(10,19.99){\psframe[fillstyle=solid,fillcolor=RGBgrey](2,2.01)}
          \end{pspicture}
        \end{pdfpic}
        \vspace{-\bigskipamount}
        \figurecaptionself{Wissenschaftliche Disziplinen mit Bezug zur Informatik,\n
                           angeordnet nach Abstraktionsgrad ihres jeweiligen Gegenstandes
                           \label{Disziplinen}}
      \end{center}
    
      Im Gegensatz zu z.\,B.\ Lebewesen
      werden Computer von Menschen entwickelt und gebaut.
      Daher ist es grundsätzlich möglich, sie durch hardwarenahe Programmierung
      vollständig zu verstehen und zu beherrschen.
    
      \subsection{Programmierung in C}
    
      Ein großer Teil dieser Vorlesung wird der Programmierung in der Programmiersprache C gewidmet sein.
    
      Warum C?
    
      C hat sich als Kompromiß zwischen einer Hochsprache und maximaler Nähe zur Hardware
      sehr weit etabliert.
      Es läuft auf nahezu jeder Plattform (= Kombination aus Hardware und Betriebssystem)
      und stellt somit einen "`kleinsten gemeinsamen Nenner der Programmierung"' dar.
      C orientiert sich sehr eng an der Funktionsweise der Computer-Hardware
      und wird daher auch als "`High-Level-Assembler"' bezeichnet.
    
      Wie die Assembler-Sprache, die Sie in \emph{Grundlagen Rechnertechnik\/} kennenlernen werden,
      ist C ein Profi-Werkzeug und als solches "`leistungsfähig, aber gefährlich"'.
      Programme können in C sehr kompakt geschrieben werden.
      C kommt mit verhältnismäßig wenigen Sprach"-elementen aus,
      die je nach Kombination etwas anderes bewirken.
      Dies hat zur Folge, daß einfache Schreibfehler,
      die in anderen Programmiersprachen als Fehler bemängelt würden,
      in C häufig ein ebenfalls gültiges Programm ergeben,
      das sich aber völlig anders als beabsichtigt verhält.
    
      \breath
    
      C wurde gemeinsam mit dem Betriebssystem Unix entwickelt
      und hat mit diesem wichtige Eigenschaften gemeinsam:
      \begin{itemize}
        \item
          \textbf{Kompakte Schreibweise:}
          Häufig verwendete Konstrukte werden möglichst platzsparend notiert.
          Wie in C, kann auch unter Unix ein falsch geschriebenes Kommando
          ein ebenfalls gültiges Kommando mit anderer Wirkung bedeuten.
        \item
          \textbf{Baukastenprinzip:}
          In C wie in Unix bemüht man sich darum, den unveränderlichen Kern möglichst klein zu halten.
          Das meiste, was man in C tatsächlich benutzt, ist in Form von Bibliotheken modularisiert;
          das meiste, was man unter Unix tatsächlich benutzt, ist in Form von Programmen modularisiert.
        \item
          \textbf{Konsequente Regeln:}
          In C wie in Unix bemüht man sich darum,
          feste Regeln -- mathematisch betrachtet -- möglichst einfach zu halten
          und Ausnahmen zu vermeiden.
          (Beispiel: Unter MS-DOS und seinen Nachfolgern wird eine ausführbare Datei gefunden,
          wenn sie sich \emph{entweder} im aktuellen Verzeichnis \emph{oder} im Suchpfad befindet.
          Unter Unix wird sie gefunden, wenn sie sich im Suchpfad befindet.
          Es ist unter Unix möglich, das aktuelle Verzeichnis in den Suchpfad aufzunehmen;
          aus Sicherheitserwägungen heraus geschieht dies jedoch üblicherweise nicht.)
        \item
          \textbf{Kein "`Fallschirm"':}
          C und Unix führen Befehle ohne Nachfrage aus.
          (Beispiel: Ein eingegebener Unix-Befehl zum Formatieren einer Festplatte
          wird ohne Rückfrage ausgeführt.)
      \end{itemize}
    
      Trotz dieser Warnungen besteht bei Programmierübungen in C
      normalerweise \emph{keine\/} Gefahr für den Rechner.
      Moderne PC-Betriebssysteme überwachen die aufgerufenen Programme
      und beenden sie notfalls mit einer Fehlermeldung ("`Schutzverletzung"').
      Experimente mit Mikrocontrollern, die im Rahmen dieser Lehrveranstaltung stattfinden werden,
      erfolgen ebenfalls in einer Testumgebung, in der kein Schaden entstehen kann.
    
      Bitte nutzen Sie die Gelegenheit, in diesem Rahmen Ihre Programmierkenntnisse zu trainieren,
      damit Sie später in Ihrer beruflichen Praxis,
      wenn durch ein fehlerhaftes Programm ernsthafter Schaden entstehen kann,
      wissen, was Sie tun.
    
      \section{Einführung in C}
    
      \subsection{Hello, world!}
    
      Das folgende Beispiel-Programm (Datei: \gitfile{hp}{script}{hello-1.c})
      gibt den Text "`Hello, world!"' auf dem Bildschirm aus:
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          printf ("Hello, world!\n");
          return 0;
        }
      \end{lstlisting}
      Dieses traditionell erste -- "`einfachste"' -- Beispiel enthält in C bereits viele Elemente,
      die erst zu einem späteren Zeitpunkt zufriedenstellend erklärt werden können:
      \begin{itemize}
        \item
          \lstinline{#include <stdio.h>}
    
          Wir deuten diese Zeile im Moment so, daß uns damit gewisse Standardfunktionen
          (darunter \lstinline{printf()} -- siehe unten) zur Verfügung gestellt werden.
    
          Diese Betrachtungsweise ist nicht wirklich korrekt
          und wird in Abschnitt \ref{Praeprozessor} genauer erklärt.
    
        \item
          \lstinline|int main (void) { ... }|
    
          Dies ist das C-Hauptprogramm.
          Das, was zwischen den geschweiften Klammern steht, wird ausgeführt.
    
          Auch hier wird zu einem späteren Zeitpunkt (Abschnitt \ref{Funktionen})
          genauer erklärt werden, was die einzelnen Elemente bedeuten und welchen Sinn sie haben.
      \end{itemize}
      \goodbreak
      Im folgenden soll nun der eigentliche Inhalt des Programms erklärt werden:
      \begin{lstlisting}
        printf ("Hello, world!\n");
        return 0;
      \end{lstlisting}
      \vspace{-\bigskipamount}
      \begin{itemize}
        \item
          Bei beiden Zeilen handelt es sich um sogenannte \newterm{Anweisungen}.
        \item
          Jede Anweisung wird mit einem Semikolon abgeschlossen.
        \item
          Bei \lstinline{printf()} handelt es sich um einen \newterm{Funktionsaufruf},
          dessen Wirkung darin besteht, daß der zwischen den Klammern angegebene \newterm{Parameter\/}
          (oder: das \newterm{Argument\/}) der Funktion
          auf dem Standardausgabegerät ausgegeben wird.
          (In unserem Fall handelt es sich dabei um einen Bildschirm.)
          Der Name "`\lstinline{printf}"' der Funktion steht für "`print formatted"' -- formatierte Ausgabe.
        \item
          \lstinline{"Hello, world!\n"} ist eine \newterm{Konstante\/}
          vom Typ \newterm{String\/} (= Zeichenkette).
        \item
          \lstinline{\n} ist eine \newterm{Escape-Sequenz}.
          Sie steht für ein einzelnes, normalerweise unsichtbares Zeichen
          mit der Bedeutung "`neue Zeile"'.
        \item
          Die Anweisung \lstinline{return 0} bedeutet:
          Beende die laufende Funktion (hier: \lstinline{main()}, also das Hauptprogramm)
          mit dem Rückgabewert 0.
          (Bedeutung: "`Programm erfolgreich ausgeführt."' --  siehe Abschnitt \ref{Funktionen}.)
      \end{itemize}
    
      \subsection{Programme compilieren und ausführen}
    
      Der Programmtext wird mit Hilfe eines Eingabeprogramms, des \newterm{Texteditors},
      in den Computer eingegeben und als Datei gespeichert.
      Als Dateiname sei hier \gitfile{hp}{script}{hello-1.c} angenommen.
      Die Dateiendung \file{.c} soll anzeigen,
      daß es sich um einen Programmquelltext in der Programmiersprache C handelt.
    
      Die \file{.c}-Datei ist für den Computer nicht direkt ausführbar.
      Um eine ausführbare Datei zu erhalten,
      muß das Programm zuerst in die Maschinensprache des verwendeten Computers übersetzt werden.
      Diesen Vorgang nennt man \newterm{Compilieren}.
    
      In einer Unix-Shell mit installierter GNU-Compiler-Collection
      (GCC; frühere Bedeutung der Abkürzung: GNU-C-Compiler)
      geschieht das Compilieren durch Eingabe der folgenden Zeile, der \newterm{Kommandozeile\/}:
    
      \begin{lstlisting}[style=terminal]
        $ ¡gcc hello-1.c -o hello-1¿
      \end{lstlisting}
    
      Das Zeichen \lstinline[style=terminal]{$} steht für die \newterm{Eingabeaufforderung\/}
      (oder das \newterm{Prompt\/}) der Unix-Shell. Es kann auch anders aussehen, z.\,B.\
      \lstinline[style=terminal]{pc42:~$} oder auch
      \lstinline[style=terminal]{cassini/home/peter/bo/2018ws/hp/script>}.
      Die Eingabe"-aufforderung wird vom Computer ausgegeben;
      die Kommandozeile rechts daneben müssen wir eingeben und mit der Eingabetaste (Enter) bestätigen.
    
      \lstinline[style=cmd]{gcc} ist ein Befehl an den Computer,
      nämlich der Name eines Programms, das wir aufrufen wollen (hier: der Compiler).
      Die darauf folgenden Teile der Kommandozeile heißen die \newterm{Parameter\/}
      oder \newterm{Argumente\/} des Befehls.
    
      Der Parameter \lstinline[style=cmd]{hello-1.c} ist der Name der Datei, die compiliert werden soll.
    
      \lstinline[style=cmd]{-o} ist eine \newterm{Option\/} an den Compiler,
      mit der man ihm mitteilt, daß der nächste Parameter \lstinline[style=cmd]{hello-1}
      der Name der ausführbaren Datei ist, die erzeugt werden soll.
    
      Unter Unix ist es üblich, ausführbaren Dateien \emph{keine\/} Endung zu geben.
      Unter Microsoft Windows wäre es stattdessen üblich,
      die ausführbare Datei \lstinline[style=cmd]{hello-1.exe} zu nennen.
    
      \breath
    
      Um von einer Unix-Shell aus ein Programm aufzurufen,
      gibt man dessen vollständigen Namen
      -- einschließlich Verzeichnispfad und eventueller Endung -- als Kommando ein:
      \begin{lstlisting}[style=terminal]
        $ ¡./hello-1¿
      \end{lstlisting}
      Der Punkt steht für das aktuelle Verzeichnis;
      der Schrägstrich trennt das Verzeichnis vom eigentlichen Dateinamen.
    
      Wenn sich ein Programm im Suchpfad befindet (z.\,B.: \lstinline[style=cmd]{gcc}),
      darf die Angabe des Verzeichnisses entfallen.
      (Den Suchpfad kann man sich mit dem Kommando
      \lstinline[style=cmd]{echo $PATH} anzeigen lassen.)
      Aus Sicherheitsgründen steht das aktuelle Verzeichnis
      unter Unix üblicherweise \emph{nicht\/} im Suchpfad.
    
      \breath
    
      \begin{experts}
        Dateiendungen dienen unter Unix nur der Übersicht,
        haben aber keine technischen Konsequenzen:
        \begin{itemize}
          \item
            Ob eine Datei als ausführbar betrachtet wird oder nicht,
            wird nicht anhand einer Endung, sondern über ein \newterm{Dateiattribut\/} entschieden.
            Die Dateiattribute werden beim Listen des Verzeichnisinhalts angezeigt:
            \begin{lstlisting}[style=terminal,gobble=10]
              $ ¡ls -l¿
              -rwxr-x--- 1 peter ainf 6294  4. Okt 14:34 hello-1
              -rw-r--r-- 1 peter ainf   82  4. Okt 15:11 hello-1.c
            \end{lstlisting}
            Jedes \lstinline[style=terminal]{r} steht für "`read"' (Datei lesbar),
            jedes \lstinline[style=terminal]{w} für "`write"' (Datei schreibbar)
            und jedes \lstinline[style=terminal]{x} für "`execute"' (Datei ausführbar).
            Von links nach rechts stehen die \lstinline[style=terminal]{rwx}-Gruppen für
            den Besitzer der Datei (hier: \lstinline[style=terminal]{peter})
            eine Benutzergruppe (hier: \lstinline[style=terminal]{ainf})
            und für alle anderen Benutzer des Computers.
            
            Im o.\,a.\ Beispiel ist die Datei \gitfile{hp}{script}{hello-1.c}
            für den Benutzer \lstinline[style=terminal]{peter} les- und schreibbar,
            für alle Angehörigen der Gruppe \lstinline[style=terminal]{ainf} nur lesbar
            und für alle anderen Benutzer des Computers ebenfalls nur lesbar.
            Die Datei \file{hello-1} (ohne Endung) ist hingegen
            für den Benutzer \lstinline[style=terminal]{peter} les-, schreib- und ausführbar,
            für alle Angehörigen der Gruppe \lstinline[style=terminal]{ainf} les- und ausführbar,
            aber nicht schreibbar. Alle anderen Benutzer des Computer haben für die Datei
            \file{hello-1} überhaupt keine Zugriffsrechte.
          \item
            Welcher Art der Inhalt der Datei ist,
            entnimmt Unix dem Inhalt selbst.
            Man kann sich dies mit Hilfe des Befehls \lstinline[style=cmd]{file} anzeigen lassen:
            \begin{lstlisting}[style=terminal,gobble=10]
              $ ¡file hello-1¿
              hello-1: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV),
              dynamically linked (uses shared libs), for GNU/Linux 2.6.18,
              not stripped
              $ ¡file hello-1.c¿
              hello-1.c: ASCII C program text
            \end{lstlisting}
          \item
            Eine ausführbare Datei, die Text enthält, ist ein sogenanntes \newterm{Shell-Skript}.
            Der Aufruf eines Shell-Skripts bewirkt i.\,w.\ dasselbe,
            als wenn man den darin enthaltenen Text als Kommandos eingeben würde.
          \item
            Ein C-Quelltext enthält i.\,d.\,R.\ \emph{keine\/} gültigen Unix-Kommandos
            und kann daher \emph{nicht\/} "`einfach so"' ausgeführt werden.
          \item
            Es ist zulässig, aber normalerweise nicht sinnvoll,
            einer ausführbaren Datei die Endung \file{.c} zu geben.
        \end{itemize}
      \end{experts}
    
      \subsection{Elementare Aus- und Eingabe}
    
      Da es möglich ist, mittels der Funktion \lstinline{printf()}
      eine String-Konstante wie z.\,B.\ \lstinline{"Hello, world!\n"} "`einfach so"' auszugeben,
      liegt die Vermutung nahe, Integer-Konstanten auf gleiche Weise ausgeben zu können.
    
      Datei \gitfile{hp}{script}{output-1.c}:
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          printf (42);
          return 0;
        }
      \end{lstlisting}
      Beim Compilieren dieses Programms erhalten wir eine Warnung:
      \begin{lstlisting}[style=terminal]
        $ ¡gcc output-1.c -o output-1¿
        output-12.c: In function 'main':
        output-12.c:5: warning: passing argument 1 of 'printf'
        makes pointer from integer without a cast
        /usr/include/stdio.h:339: note: expected
        'const char * __restrict__' but argument is of type 'int'
      \end{lstlisting}
      \goodbreak
      Es entsteht trotzdem eine ausführbare Datei \file{output-1}.
      Wenn wir diese jedoch ausführen, erhalten wir eine Fehlermeldung:
      \begin{lstlisting}[style=terminal]
        $ ¡./output-12¿
        Segmentation fault
      \end{lstlisting}
      Tatsächlich ist die direkte Übergabe einer Integer-Konstanten an \lstinline{printf()}
      ein grober Fehler: \lstinline{printf()} akzeptiert als ersten Parameter nur Ausdrücke vom Typ String.
      Der C-Compiler nimmt eine implizite Umwandlung der Integer-Konstanten in einen String vor:
      Die Zahl wird als eine Speicheradresse interpretiert, an der sich der Text befindet.
      Dies ist nicht besonders sinnvoll (daher die Warnung), aber in C zulässig.
    
      Wenn nun das Programm ausgeführt wird, versucht es, auf die Speicheradresse Nr.\ 42 zuzugreifen.
      Diese befindet sich normalerweise außerhalb des Programms.
      Das Betriebssystem bemerkt den illegalen Zugriffsversuch
      und bricht das Programm mit einer Fehlermeldung
      ("`Speicherzugriffsfehler"', "`Schutzverletzung"' o.\,ä.) ab.
    
      Auf einer Plattform ohne derartige Schutzmechanismen (z.\,B.\ einem Mikrocontroller)
      wird das fehlerhafte Programm hingegen klaglos ausgeführt.
      Es werden dann sinnlose Texte, die sich zufällig an Speicheradresse Nr.\ 42 befinden,
      auf dem Standardausgabegerät ausgegeben.
    
      \breath
    
      Dieses fehlerhafte Programm illustriert, wie leicht es in der Programmiersprache C ist,
      einen Absturz zu programmieren.
      Die meisten anderen Programmiersprachen würden das fehlerhafte Programm nicht akzeptieren;
      anstelle der o.\,a.\ Warnung bekäme man eine ähnlichlautende Fehlermeldung.
    
      \begin{hint}
        Nehmen Sie nicht nur die Fehlermeldungen,\\
        sondern auch die Warnungen des Compilers ernst!
      \end{hint}
    
      Gerade in graphischen Entwicklungsentwicklungen
      werden Warnungen oft in einem winzigen Fenster angezeigt
      und gehen zwischen anderen Meldungen unter.
      Auch sind die Compiler-Optionen,
      mit denen Sie Warnungen ein- oder ausschalten können,
      oft in tiefen Menü-Strukturen versteckt,
      so daß man als Programmierer den Aufwand scheut,
      diese sinnvoll zu setzen.
    
      Fehlermeldungen \emph{müssen\/} Sie ernstnehmen,
      da Sie sonst kein ausführbares Programm erhalten.
      Warnungen \emph{sollten\/} Sie ebenfalls ernstnehmen,
      \emph{obwohl\/} Sie ein ausführbares Programm erhalten,
      da dieses mit hoher Wahrscheinlichkeit
      in einer nicht-offensichtlichen Weise \emph{fehlerhaft\/} ist.
      Ein derartiges Programm produktiv einzusetzen,
      kann je nach Einsatzgebiet Vermögens-, Sach- oder sogar Personenschäden
      zur Folge haben.
    
      \breath
    
      Wie man nun tatsächlich in C Zahlenwerte ausgibt,
      illustriert das Beispielprogramm \gitfile{hp}{script}{output-2.c}:
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          printf ("Die Antwort lautet: %d\n", 42);
          return 0;
        }
      \end{lstlisting}
      Der erste Parameter von \lstinline{printf()}, der sog.\ \newterm{Format-String},
      enthält das Symbol \lstinline{%d}.
      Diese sog.\ \newterm{Formatspezifikation\/} wird in der Ausgabe
      durch den Zahlenwert des zweiten Parameters von \lstinline{printf()} ersetzt.
      Das \lstinline{d} steht hierbei für "`dezimal"'.
    
      \breath
    
      \begin{experts}
    %    Wenn man anstelle von \lstinline{%d} die Formatspezifikation \lstinline{%x} verwendet,
    %    wird die Zahl in hexadezimaler anstatt in dezimaler Schreibweise ausgegeben.
        Wenn man zwischen das Prozentzeichen un das \lstinline{d} eine Zahl schreibt (z.\,B.\ \lstinline{%3d}),
        gibt man damit die Breite eines Feldes an, in die die auszugebende Zahl rechtsbündig geschrieben wird.
        Wenn man die Feldbreite mit einer Null beginnen läßt (z.\,B.\ \lstinline{%03d})
        wird die auszugebende Zahl von links mit Nullen bis zur Feldbreite aufgefüllt.
    
        Eine vollständige Liste der in \lstinline{printf()} zulässigen Formatspezifikationen
        finden Sie in der Dokumentation des Compiler-Herstellers zu \lstinline{printf()}.
        Von der Unix-Shell aus können Sie diese
        mit dem Befehl \lstinline[style=cmd]{man 3 printf} abrufen.
    %
    %    Umgekehrt können Sie in C Integer-Konstanten
    %    durch Voranstellen von \lstinline{0x} in hexadezimaler anstatt dezimaler Schreibweise eingeben.
    %    Die Hexadezimalzahl \lstinline{0x2a} steht in C für genau dieselbe Konstante
    %    wie die Dezimalzahl \lstinline{42}.
      \end{experts}
    
      \breath
    
      Bemerkungen:
      \begin{itemize}
        \item
          Ein Text darf auch Ziffern enthalten.
          Anhand der Ausgabe sind \lstinline{printf ("42\n");} 
          und \lstinline{printf ("%d\n", 42);} nicht voneinander unterscheidbar.
        \item
          Die Position des \lstinline{\n} ist relevant,
          z.\,B.\ geht \lstinline{printf ("\n42");} zuerst in eine neue Zeile
          und gibt danach den Text aus.
          Auch mehrere \lstinline{\n} in derselben String-Konstanten sind zulässig.
        \item
          C akzeptiert auch sehr seltsame Konstrukte.
          Das folgende Beispiel (Datei: \gitfile{hp}{script}{hello-2.c})
          \begin{lstlisting}[gobble=8]
            #include <stdio.h>
    
            int main (void)
            {
              printf ("Hello, world!\n");
              "\n";
              return 0;
            }
          \end{lstlisting}
          wird vom Compiler akzeptiert.
          (Warum das so ist, wird in Abschnitt \ref{Seiteneffekte} behandelt.)
    
          Bei Verwendung der zusätzlichen Option \lstinline[style=cmd]{-Wall}
          erhalten wir zumindest eine Warnung über eine "`Anweisung ohne Effekt"':
          \begin{lstlisting}[style=terminal,gobble=8]
            $ ¡gcc -Wall hello-2.c -o hello-2¿
            hello-2.c: In function 'main':
            hello-2.c:6: warning: statement with no effect
          \end{lstlisting}
          Es empfiehlt sich, die Option \lstinline[style=cmd]{-Wall} grundsätzlich zu verwenden
          und die Warnungen ernstzunehmen.
      \end{itemize}
    
      \breath
    
      Wenn mehrere Werte ausgegeben werden sollen,
      verwendet man in \lstinline{printf()} mehrere Formatspezifikationen
      und gibt mehrere Werte als Parameter an (Datei: \gitfile{hp}{script}{output-3.c}):
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          printf ("Richtige Antworten wären %d oder %d oder sonstige.\n", 1, 2);
          return 0;
        }
      \end{lstlisting}
      \begin{lstlisting}[style=terminal]
        $ ¡gcc output-3.c -o output-3¿
        $ ¡./output-3¿
        Richtige Antworten wären 1 oder 2 oder sonstige.
        $
      \end{lstlisting}
      Achtung: Zu viele oder zu wenige Werte in der Parameterliste
      ergeben trotzdem ein gültiges, wenn auch fehlerhaftes C-Programm
      (Datei: \gitfile{hp}{script}{output-4.c}):
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          printf ("Richtige Antworten wären %d", 1, " oder %d", 2, " oder sonstige.\n");
          return 0;
        }
      \end{lstlisting}
      Wenn man dieses Programm laufen läßt,
      wird nicht etwa das zweite \lstinline{%d} durch den Zahlenwert 2 ersetzt.
      Vielmehr endet das, was ausgegeben wird, mit dem ersten \lstinline{%d},
      für das der Zahlenwert 1 eingesetzt wird,
      und alles, was nach der 1 kommt, wird schlichtweg ignoriert.
      \begin{lstlisting}[style=terminal]
        $ ¡gcc output-4.c -o output-4¿
        $ ¡./output-4¿
        Richtige Antworten wären 1
        $
      \end{lstlisting}
      Bei Verwendung der Option \lstinline[style=cmd]{-Wall}
      erhalten wir auch hier eine Warnung:
      \begin{lstlisting}[style=terminal]
        $ ¡gcc -Wall output-4.c -o output-4¿
        output-4.c: In function 'main':
        output-4.c:5: warning: too many arguments for format
      \end{lstlisting}
    
      Das Einlesen von Werten erfolgt in C mit der Funktion \lstinline{scanf()}.
    
      Das folgende Beispielprogramm (Datei: \gitfile{hp}{script}{input-1.c})
      liest einen Wert vom Standardeingabegerät (hier: Tastatur) ein
      und gibt ihn wieder aus:
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          int a;
          printf ("Bitte eine Zahl eingeben: ");
          scanf ("%d", &a);
          printf ("Sie haben eingegeben: %d\n", a);
          return 0;
        }
      \end{lstlisting}
    
      Damit \lstinline{scanf()} in die Variable \lstinline{a} einen Wert schreiben kann,
      ist es erforderlich, nicht den aktuellen Wert von \lstinline{a},
      sondern die Variable selbst an \lstinline{scanf()} zu übergeben.
      Dies geschieht durch Voranstellen eines Und-Symbols \lstinline{&}.
      (Genaugenommen handelt es sich um die Übergabe einer Speicheradresse.
      Dies wird in Abschnitt \ref{Zeiger} genauer behandelt.)
    
      Wenn wir das \lstinline{&} vergessen (Beispielprogramm: \gitfile{hp}{script}{input-2.c}),
      kann das C-Programm weiterhin compiliert werden.
      Bei Verwendung der Option \lstinline[style=cmd]{-Wall} erhalten wir eine Warnung.
      Wenn wir das Programm ausführen und versuchen, einen Wert einzugeben, stürzt das Programm ab.
      (Hintergrund: Es betrachtet den aktuellen -- zufälligen -- Wert der Variablen \lstinline{a}
      als Adresse einer Speicherzelle, an der der eingelesene Wert gespeichert werden soll.
      Das Programm greift also schreibend auf eine Speicherzelle außerhalb des ihm zugeteilten Bereichs zu.)
    
      \breath
    
      \begin{experts}
        Die Funktion \lstinline{scanf()} kann, analog zu \lstinline{printf()},
        gleichzeitig mehrere Werte abfragen.
        Hierzu müssen wir im Format-String mehrere Formatspezifikationen angeben
        und die Adressen mehrerer Variabler als Parameter übergeben.
    
        Genau wie bei \lstinline{printf()} werden überzählige Parameter ignoriert,
        und fehlende Parameter führen zu einem Absturz des Programms.
    
        Zeichen zwischen den Formatspezifikationen fungieren als Trennzeichen.
        Damit die Zahlen angenommen werden, muß die Eingabe die Trennzeichen enthalten.
    
        Für doppelt genaue Fließkommazahlen (\lstinline{double})
        lautet die Formatspezifikation \lstinline{%lf};
        für einfach genaue Fließkommazahlen (\lstinline{float})
        lautet sie \lstinline{%f}.
    
        Weitere Informationen zu den Formatspezifikationen von \lstinline{scanf()}
        finden Sie in der Dokumentation zu \lstinline{scanf()}.
        (In der Unix-Shell können Sie diese mit dem Befehl \lstinline[style=cmd]{man 3 scanf} abrufen.)
    
        Für das Einlesen von Strings ist \lstinline{scanf()} eher ungeeignet.
        Hier empfiehlt es sich, stattdessen \lstinline{fgets()} zu benutzen
        (siehe \lstinline[style=cmd]{man 3 fgets}).
      \end{experts}
    
      \subsection{Elementares Rechnen}
    
      Der \newterm{binäre Operator} \lstinline{+} kann in C (und den meisten Programmiersprachen)
      dazu verwendet werden, zwei Integer-Ausdrücke, die sogenannten \newterm{Operanden},
      durch Addition zu einem neuen Integer-Ausdruck zu verknüpfen.
    
      Beispiel: \gitfile{hp}{script}{mathe-1.c}
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          printf ("%d\n", 23 + 19);
          return 0;
        }
      \end{lstlisting}
      \begin{experts}
        (Tatsächlich führt bereits die erste Stufe des Compilers eine Optimierung durch,
        die bewirkt, daß die ausführbare Datei keine Additionsbefehle,
        sondern direkt das Ergebnis der Addition enthält.)
      \end{experts}
    
      Die Operatoren für die Grundrechenarten lauten in C:
      \begin{center}
        \begin{tabular}{cl}
          \lstinline|+| & Addition \\
          \lstinline|-| & Subtraktion \\
          \lstinline|*| & Multiplikation \\
          \lstinline|/| & Division: Bei ganzen Zahlen wird grundsätzlich abgerundet. \\
          \lstinline|%| & Modulo-Operation: Rest bei Division (\lstinline|39 % 4| ergibt \lstinline|3|.)
        \end{tabular}
      \end{center}
    
      Die Verwendung von \newterm{Variablen} erfordert in C eine vorherige Deklaration.
      \begin{lstlisting}[belowskip=0pt]
        int a;
      \end{lstlisting}
      deklariert eine Variable vom Typ Integer,
      \begin{lstlisting}[belowskip=0pt]
        int a, b;
      \end{lstlisting}
      deklariert zwei Variable vom Typ Integer, und
      \begin{lstlisting}[belowskip=0pt]
        int a, b = 3;
      \end{lstlisting}
      deklariert zwei Variable vom Typ Integer und initialisiert \emph{die zweite\/} mit dem Wert 3.
      (Im letzten Beispiel wird insbesondere die erste Variable \lstinline{a} \emph{nicht\/} initialisiert.)
      
      Nicht initialisierte Variable erhalten einen \emph{zufälligen\/} Wert.
      Wenn beim Compilieren mit \lstinline[style=cmd]{gcc}
      zusätzlich zu den Warnungen (Option \lstinline[style=cmd]{-Wall})
      auch die Optimierung (Option \lstinline[style=cmd]{-O}, \lstinline[style=cmd]{-O2} oder \lstinline[style=cmd]{O3})
      aktiviert ist, erkennt \lstinline[style=cmd]{gcc}
      die Verwendung derartiger zufälliger Werte und gibt eine Warnung aus.
    
      \begin{experts}
        Nicht explizit initialisierte \newterm{globale Variable},
        also solche, die außerhalb einer Funktion deklariert werden,
        werden implizit auf Null initialisiert
        (\lstinline{0} für Zahlen, \lstinline{NULL} für Zeiger usw.).
        Es ist trotzdem in Hinblick auf selbstdokumentierenden Quelltext sinnvoll,
        diese ggf.\ explizit auf \lstinline{0} zu initialisieren.
      \end{experts}
    
      \breath
    
      Für Fließkommazahlen verwendet man meistens den Datentyp \lstinline{double}:
      \begin{lstlisting}[belowskip=0pt]
        double x = 3.141592653589793;
      \end{lstlisting}
    
      \bigskip
    
      \begin{experts}
        Die Bezeichnung \lstinline{double} steht für "`doppelt genau"'.
        Daneben gibt es noch einen Datentyp \lstinline{float} für "`einfach genaue"' Fließkommazahlen
        sowie einen Datentyp \lstinline{long double} für noch höhere Genauigkeit.
        Typischerweise folgen Fließkommazahlen in C dem Standard IEEE 754.
        In diesem Fall hat \lstinline{float} eine Genauigkeit von ca.\ 6
        und \lstinline{double} eine Genauigkeit von ca.\ 15 Nachkommastellen.
      \end{experts}
    
      \breath
    
      Zuweisungen an Variable erfolgen in C mit Hilfe des binären Operators \lstinline{=}.
      Es ist ausdrücklich erlaubt, den "`alten"' Wert einer Variablen in Berechnungen zu verwenden,
      deren Ergebnis man dann derselben Variablen zuweist.
    
      Eine Anweisung wie z.\,B.\ \lstinline{a = 2 * a}
      ist insbesondere keine mathematische Gleichung
      (mit der Lösung 0 für die Unbekannte \lstinline{a}),
      sondern die Berechnung des Doppelten des aktuellen Wertes der Variablen \lstinline{a},
      welches dann wiederum in der Variablen \lstinline{a} gespeichert wird.
    
      \subsection{Verzweigungen}
    
      Das Beispielprogramm \gitfile{hp}{script}{if-0.c}
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          int a, b;
          printf ("Bitte a eingeben: ");
          scanf ("%d", &a);
          printf ("Bitte b eingeben: ");
          scanf ("%d", &b);
          printf ("a geteilt durch b ist: %d\n", a / b);
          return 0;
        }
      \end{lstlisting}
      hat den Nachteil, daß bei Eingabe von 0 für die zweite Zahl das Programm abstürzt:
      \begin{lstlisting}[style=terminal]
        $ ¡gcc -Wall if-0.c -o if-0¿
        $ ¡./if-0¿
        Bitte a eingeben: ¡13¿
        Bitte b eingeben: ¡0¿
        Floating point exception
      \end{lstlisting}
      Die Fehlermeldung stammt nicht vom Programm selbst, sondern vom Betriebssystem,
      das auf einen vom Prozessor signalisierten Fehlerzustand reagiert.
      ("`Floating point exception"' ist die Bezeichnung dieses Fehlerzustands.
      In diesem Fall ist die Bezeichnung leicht irreführend,
      da konkret dieser Fehler durch eine Division ganzer Zahlen,
      also insbesondere nicht durch eine Fließkommaoperation, ausgelöst wird.)
    
      Für Programme wie dieses ist es notwendig,
      in Abhängigkeit von den Benutzereingaben unterschiedliche Anweisungen auszuführen.
      Diese sog.\ \newterm{Verzweigung\/} geschieht mittels einer \lstinline{if}-Anweisung.
    
      \goodbreak
      Beispielprogramm: \gitfile{hp}{script}{if-1.c}
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          int a, b;
          printf ("Bitte a eingeben: ");
          scanf ("%d", &a);
          printf ("Bitte b eingeben: ");
          scanf ("%d", &b);
          if (b != 0)
            printf ("a geteilt durch b ist: %d\n", a / b);
          return 0;
        }
      \end{lstlisting}
    
      In den Klammern hinter dem \lstinline{if} steht ein Ausdruck, die sog.\ \newterm{Bedingung}.
      Die auf das \lstinline{if} folgende Anweisung wird nur dann ausgeführt,
      wenn die Bedingung \emph{ungleich Null\/} ist.
      (C kennt keinen eigenen "`Booleschen"' Datentyp.
      Stattdessen steht \lstinline{0} für den Wahrheitswert "`falsch"'
      und alles andere für den Wahrheitswert "`wahr"'.)
    
      Der binäre Operator \lstinline{!=} prüft zwei Ausdrücke auf Ungleichheit.
      Er liefert \lstinline{0} zurück, wenn beide Operanden gleich sind,
      und \lstinline{1}, wenn sie ungleich sind.
    
      \breath
    
      Die \lstinline{if}-Anweisung kennt einen optionalen \lstinline{else}-Zweig.
      Dieser wird dann ausgeführt, wenn die Bedingung \emph{nicht\/} erfüllt ist.
    
      Beispielprogramm: \gitfile{hp}{script}{if-2.c}
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          int a, b;
          printf ("Bitte a eingeben: ");
          scanf ("%d", &a);
          printf ("Bitte b eingeben: ");
          scanf ("%d", &b);
          if (b != 0)
            printf ("a geteilt durch b ist: %d\n", a / b);
          else
            printf ("Bitte nicht durch 0 teilen!\n");
          return 0;
        }
      \end{lstlisting}
    
      \breath
    
      Sowohl auf das \lstinline{if} als auch auf das \lstinline{else}
      folgt nur jeweils \emph{eine\/} Anweisung, die von der Bedingung abhängt.
    
      In dem folgenden Beispielprogramm (Datei: \gitfile{hp}{script}{if-3.c})
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          int a, b;
          printf ("Bitte a eingeben: ");
          scanf ("%d", &a);
          printf ("Bitte b eingeben: ");
          scanf ("%d", &b);
          if (b != 0)
            printf ("a geteilt durch b ist: %d\n", a / b);
          else
            printf ("Bitte nicht durch 0 teilen!\n");
            printf ("Das tut man nicht.\n");
          return 0;
        }
      \end{lstlisting}
      wird die Zeile \lstinline{printf ("Das tut man nicht.\n");} auch dann ausgeführt,
      wenn die Variable \lstinline{b} ungleich 0 ist.
    
      \breath
    
      In C ist die Einrückung der Zeilen im Programmquelltext "`nur"' eine optische Hilfe für Programmierer.
      Welche Anweisung von welcher Bedingung abhängt,
      entscheidet der Compiler allein anhand der Regeln der Programmiersprache,
      und diese besagen eindeutig:
      "`Sowohl auf das \lstinline{if} als auch auf das \lstinline{else}
      folgt nur jeweils \emph{eine\/} Anweisung, die von der Bedingung abhängt."'
    
      Wenn wir möchten, daß mehrere Anweisungen von der Bedingung abhängen,
      müssen wir diese mittels geschweifter Klammern
      zu einem sog.\ \newterm{Anweisungsblock\/} zusammenfassen.
    
      \goodbreak
      Beispielprogramm: \gitfile{hp}{script}{if-4.c}
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          int a, b;
          printf ("Bitte a eingeben: ");
          scanf ("%d", &a);
          printf ("Bitte b eingeben: ");
          scanf ("%d", &b);
          if (b != 0)
            printf ("a geteilt durch b ist: %d\n", a / b);
          else
            {
              printf ("Bitte nicht durch 0 teilen!\n");
              printf ("Das tut man nicht.\n");
            }
          return 0;
        }
      \end{lstlisting}
    
      Aus Sicht des Computers ist die Einrückung
      -- und überhaupt die Anordnung von Leerzeichen und Zeilenschaltungen -- belanglos.
      Die folgende Schreibweise (Datei: \gitfile{hp}{script}{if-5.c}) ist für ihn
      vollkommen gleichwertig zu \gitfile{hp}{script}{if-4.c}:
      \begin{lstlisting}
        #include<stdio.h>
        int main(void){int a,b;printf("Bitte a eingeben: ");scanf("%d",&a);
        printf("Bitte b eingeben: ");scanf("%d",&b);if(b!=0)printf(
        "a geteilt durch b ist: %d\n",a/b);else{printf("Bitte nicht durch 0 teilen!\n");
        printf("Das tut man nicht.\n");}return 0;}
      \end{lstlisting}
      Aus Sicht eines Menschen hingegen kann eine \emph{korrekte\/} Einrückung des Quelltextes
      \emph{sehr\/} hilfreich dabei sein, in einem Programm die Übersicht zu behalten.
    
      \goodbreak
      Daher hier der dringende Rat:
      \begin{hint}
        Achten Sie in Ihren Programmen auf korrekte und übersichtliche Einrückung!
      \end{hint}
    
      \breath
    
      Um zwei Ausdrücke auf Gleichheit zu prüfen,
      verwendet man in C den binären Operator \lstinline{==}.
    
      Die Anweisungen
      \begin{lstlisting}[belowskip=0pt]
        if (b != 0)
          {
            printf ("Die erste Zahl geteilt durch die zweite ergibt: ");
            printf ("%d, Rest %d \n", a / b, a % b);
          }
        else
          printf ("Bitte nicht durch 0 teilen!\n");
      \end{lstlisting}
      sind also äquivalent zu:
      \begin{lstlisting}
        if (b == 0)
          printf ("Bitte nicht durch 0 teilen!\n");
        else
          {
            printf ("Die erste Zahl geteilt durch die zweite ergibt: ");
            printf ("%d, Rest %d \n", a / b, a % b);
          }
      \end{lstlisting}
    
      Achtung: Die Anweisungen
      \begin{lstlisting}[belowskip=0pt]
        if (b = 0)
          printf ("Bitte nicht durch 0 teilen!\n");
        else
          {
            printf ("Die erste Zahl geteilt durch die zweite ergibt: ");
            printf ("%d, Rest %d \n", a / b, a % b);
          }
      \end{lstlisting}
      (mit \lstinline{=} anstelle von \lstinline{==}) sind ebenfalls gültiges C,
      haben jedoch eine andere Bedeutung!
      \goodbreak
    
      Der Hintergrund ist der folgende:
      Alle binären Operatoren, sei es \lstinline{+} oder \lstinline{=} oder \lstinline{==},
      sind in C vom Prinzip her gleichwertig.
      Alle nehmen zwei numerische Operanden entgegen und liefern einen numerischen Wert zurück.
      Wenn wir nun beispielsweise annehmen, daß die Variable \lstinline{a} den Wert 3 hat, dann gilt:
      \begin{center}
        \begin{tabular}{cl}
          \lstinline|a + 7| & ergibt \lstinline|10|. \\
          \lstinline|a = 7| & ergibt \lstinline|7| (und weist \lstinline|a| den Wert 7 zu). \\
          \lstinline|a == 7| & ergibt \lstinline|0|.
        \end{tabular}
      \end{center}
      Das o.\,a.\ Programmfragment bedeutet demnach:
      Weise der Variablen \lstinline{b} den Wert \lstinline{0} zu,
      und führe anschließend \emph{immer\/} eine Division durch \lstinline{b} aus.
      (Die \lstinline{if}-Bedingung bekommt den Wert \lstinline{0}, ist also niemals erfüllt.)
    
      \breath
    
      Daß es sich bei Wahrheitswerten in C tatsächlich um Integer-Werte handelt, wird auch deutlich,
      wenn man sich diese mittels \lstinline{printf()} ausgeben läßt.
    
      Wenn man beispielsweise in dem folgenden Programm \gitfile{hp}{script}{if-6.c}
      den Wert \lstinline{7} für die Variable \lstinline{b} eingibt,
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          int b;
          printf ("Bitte b eingeben: ");
          scanf ("%d", &b);
          printf ("Der Ausdruck b != 0 hat den Wert %d\n", b != 0);
          printf ("Der Ausdruck b == 0 hat den Wert %d\n", b == 0);
          printf ("Der Ausdruck b = 23 hat den Wert %d\n", b = 23);
          return 0;
        }
      \end{lstlisting}
      \goodbreak
      lautet die Ausgabe:
      \goodbreak
      \begin{lstlisting}[style=terminal]
        $ ¡./if-6¿
        Bitte b eingeben: ¡7¿
        Der Ausdruck b != 0 hat den Wert 1
        Der Ausdruck b == 0 hat den Wert 0
        Der Ausdruck b = 23 hat den Wert 23
      \end{lstlisting}
      In der ersten und zweiten Zeile wird geprüft, ob \lstinline{b} den Wert 0 hat,
      und \lstinline{1} für "`ja"' bzw.\ \lstinline{0} für "`nein"' ausgegeben.
      In der dritten Zeile wird \lstinline{b} der Wert \lstinline{23} zugewiesen
      und anschließend der neue Wert von \lstinline{b} ausgegeben.
    
      \subsection{Schleifen}
    
      Mit Hilfe der \lstinline{while}-Anweisung ist es möglich,
      Anweisungen in Abhängigkeit von einer Bedingung mehrfach auszuführen.
    
      Das folgende Beispielprogramm \gitfile{hp}{script}{loop-1.c}
      schreibt die Zahlen von 1 bis einschließlich 10 auf den Bildschirm:
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          int i = 1;
          while (i <= 10)
            {
              printf ("%d\n", i);
              i = i + 1;
            }
          return 0;
        }
      \end{lstlisting}
      Die Auswertung der Bedingung erfolgt analog zur \lstinline{if}-Anweisung.
      Ebenso folgt auf \lstinline{while} nur eine eine einzige Anweisung, die wiederholt ausgeführt wird;
      mehrere Anweisungen müssen mit geschweiften Klammern zu einem Anweisungsblock zusammengefaßt werden.
    
      Der binäre Operator \lstinline{<=} liefert 1 zurück,
      wenn der linke Operand kleiner oder gleich dem rechten ist, ansonsten 0.
      Entsprechend sind die Operatoren \lstinline{>=}, \lstinline{<} und \lstinline{>} definiert.
    
    \if 0
    
      \breath
    
      Wenn man eine Bedingung angibt, die niemals 0 wird,
      erzeugt man eine Endlosschleife (\gitfile{hp}{script}{while-2.c}):
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          int i;
          i = 1;
          while (1)
            {
              i = i + i;
              printf ("%d\n", i);
            }
          return 0;
        }
      \end{lstlisting}
      Das endlos laufende Programm kann nur noch über das Betriebssystem beendet werden.
      Von der Unix-Shell aus geschieht dies durch Eingabe von \lstinline[style=cmd]{Strg+C}.
    
      In der Ausgabe des oben dargestellten Beispielprogramms fällt auf,
      daß die Zweierpotenzen zunächst wie erwartet anwachsen,
      später aber nur noch der Zahlenwert 0 ausgegeben wird:
      \begin{lstlisting}[style=terminal]
        $ ¡gcc -Wall while-2.c -o while-2¿
        $ ¡./while-2¿
        2
        4
        8
        16
        32
        64
        128
        256
        512
        1024
        2048
        4096
        8192
        16384
        32768
        65536
        131072
        262144
        524288
        1048576
        2097152
        4194304
        8388608
        16777216
        33554432
        67108864
        134217728
        268435456
        536870912
        1073741824
        -2147483648
        0
        0
        0
        ...
      \end{lstlisting}
      \goodbreak
      Dies hängt mit der Art und Weise zusammen,
      wie Zahlen in einem Computer gespeichert werden.
      Im Detail ist dies Gegenstand der Vorlesung "`Rechnertechnik"';
      ein paar für uns wichtige Eckdaten seien an dieser Stelle erwähnt:
      \begin{itemize}
        \item
          Computer speichern Zahlen im Binärformat, das nur die Ziffern 0 und 1 kennt.\\
          Beispielsweise lautet die Dezimalzahl 9 in Binärdarstellung 1001.
        \item
          Zweierpotenzen entsprechen jeweils einer 1 mit folgenden Nullen.\\
          Die Dezimalzahlen 2, 4, 8 und 16 haben die Binärdarstellungen 10, 100, 1000 und 10000.
        \item
          Auf einem 32-Bit-Prozessor zeigt die zweiundreißigste Ziffer von rechts das Vorzeichen an.
          Steht hier eine 1, ist die Zahl negativ.
          Dies erklärt, weshalb die Verdopplung von 1073741824 (binär: eine 1 mit 30 Nullen)
          $-$2147483648 ergibt (binär: eine 1 mit 31 Nullen).
        \item
          Bei einer weiteren Verdopplung würde binär eine 1 mit 32 Nullen entstehen,
          die aber von einem 32-Bit-Prozessor nicht mehr dargestellt werden kann.
          Ohne weitere Maßnahmen ist daher das Doppelte von $-$2147483648 auf einem 32-Bit-Prozessor
          die Zahl 0.
      \end{itemize}
    
    \fi
    
      \breath
    
      Ein wichtiger Spezialfall einer \lstinline{while}-Schleife ist die folgende Situation:
      \begin{itemize}
        \item
          Vor dem Betreten der Schleife findet eine Initialisierung statt, z.\,B.\ \lstinline{i = 1}.
        \item
          Am Ende jedes Schleifendurchlaufs wird eine "`Schritt-Anweisung"' durchgeführt,
          z.\,B.\ \lstinline{i = i + 1}.
      \end{itemize}
      Für dieses spezielle \lstinline{while} kennt C die Abkürzung \lstinline{for}:
      \begin{center}
        \begin{minipage}{4cm}
          \begin{lstlisting}[gobble=8]
            int i = 1;
            while (i <= 10)
              {
                printf ("%d\n", i);
                i = i + 1;
              }
          \end{lstlisting}
        \end{minipage}%
        \quad
        ist genau dasselbe wie
        \quad
        \begin{minipage}{4.9cm}
          \begin{lstlisting}[gobble=8]
            int i;
            for (i = 1; i <= 10; i = i + 1)
              printf ("%d\n", i);
          \end{lstlisting}
          \quad oder
          \begin{lstlisting}[gobble=8]
            for (int i = 1; i <= 10; i = i + 1)
              printf ("%d\n", i);
          \end{lstlisting}
          \bigskip
          \quad(Datei: \gitfile{hp}{script}{loop-2.c})
        \end{minipage}
      \end{center}
    
      Achtung: Zwischen den Klammern nach \lstinline{for} stehen zwei Semikolons, keine Kommata.
    
      \begin{hint}
        Die Schreibweise mit der Deklaration \lstinline{int i = 1}
        \emph{innerhalb\/} der \lstinline{for}-Schleife
        ist erst ab dem C-Standard C99 zulässig.
        Beim Compilieren mit älteren Versionen des \lstinline[style=cmd]{gcc}
        muß daher zusätzlich die Option \lstinline[style=cmd]{-std=c99} angegeben werden.
      \end{hint}
    
      \breath
    
      Als eine weitere Schleife kennt C die \lstinline{do}-\lstinline{while}-Schleife:
      \begin{lstlisting}
        i = 1;
        do
          {
            printf ("%d\n", i);
            i = i + 1;
          }
        while (i <= 10)
      \end{lstlisting}
      Der Unterschied zur "`normalen"' \lstinline{while}-Schleife besteht darin,
      daß eine \lstinline{do}-\lstinline{while}-Schleife mindestens einmal ausgeführt wird,
      weil die Bedingung nicht bereits am Anfang, sondern erst am Ende des Schleifendurchlaufs geprüft wird.
    
      \bigbreak
    
      Zwischen einer "`normalen"' \lstinline{while}-Schleife
      und einer \lstinline{for}-Schleife besteht hingegen \emph{kein\/} Unterschied.
      Insbesondere ist eine Schreibweise wie
      \begin{lstlisting}
        for (i = 1; 10; i + 1)
          printf ("%d\n", i);
      \end{lstlisting}
      \vspace{-\smallskipamount}
      zwar zulässiges C, aber nicht sinnvoll (Datei: \gitfile{hp}{script}{loop-3.c}).
      Dies kann man sofort erkennen, indem man die \lstinline{for}-Schleife
      in eine \lstinline{while}-Schleife übersetzt:
      \begin{lstlisting}
        i = 1; 
        while (10)
          {
            printf ("%d\n", i);
            i + 1;
          }
      \end{lstlisting}
      Dieses Programmfragment setzt einmalig \lstinline{i} auf den Wert 1
      und springt danach in eine Endlosschleife zur Ausgabe von \lstinline{i}.
      (Die \lstinline{while}-Bedingung \lstinline{10} ist ungleich Null, hat also stets den Wahrheitswert "`wahr"'.)
      Am Ende jedes Schleifendurchlaufs wird \lstinline{i + 1} berechnet;
      der berechnete Wert wird jedoch nirgendwo verwendet, sondern schlichtweg verworfen.
      Insbesondere ändert \lstinline{i} seinen Wert nicht.
    
      \subsection{Seiteneffekte\label{Seiteneffekte}}
    
      Das Verwerfen berechneter Werte verdient eine nähere Betrachtung
      -- insbesondere in der Programmiersprache C.
      Wie das Beispielprogramm \gitfile{hp}{script}{statements-1.c} illustriert,
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          2 + 2;
          return 0;
        }
      \end{lstlisting}
      ist es anscheinend zulässig, Werte als Anweisung zu verwenden.
    
      Grundsätzlich gilt in C:
      Man kann jeden gültigen Ausdruck als Anweisung verwenden.
      Der Wert des Ausdrucks wird dabei ignoriert.
    
      Die Bedeutung der (gültigen!) C-Anweisung \lstinline{2 + 2;} lautet somit:
      "`Berechne den Wert \lstinline{2 + 2} und vergiß ihn wieder."'
    
      Tatsächlich gilt dasselbe auch für \lstinline{printf()}:
      Die Funktion \lstinline{printf()} liefert eine ganze Zahl zurück.
      Der \lstinline{printf()}-Aufruf ist somit ein Ausdruck,
      dessen Wert ignoriert wird.
    
      "`Nebenbei"' hat \lstinline{printf()} aber noch eine weitere Bedeutung,
      nämlich die Ausgabe des Textes auf dem Standardausgabegerät (Bildschirm).
      Diese weitere Bedeutung heißt \newterm{Seiteneffekt\/} des Ausdrucks.
    
      Das Beispielprogramm \gitfile{hp}{script}{statements-2.c}
      gibt den vom ersten \lstinline{printf()} zurückgegebenen Wert
      mit Hilfe eines zweiten \lstinline{printf()} aus:
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          int x;
          x = printf ("%d\n", 2 + 2);
          printf ("%d\n", x);
          return 0;
        }
      \end{lstlisting}
      Die Ausgabe lautet:
      \begin{lstlisting}[style=terminal]
        4
        2
      \end{lstlisting}
      Bei dem von \lstinline{printf()} zurückgegebenen Wert handelt es sich um die Anzahl der geschriebenen Zeichen.
      In diesem Fall ist sind es zwei Zeichen, nämlich die Ziffer \lstinline{4}
      sowie das Zeilenendesymbol, im Programm als \lstinline{\n} notiert.
    
      \breath
    
      Auch Operatoren können in C Seiteneffekte haben.
    
      \begin{itemize}
        \item
          Der binäre Operator \lstinline{=} (Zuweisung)
          hat als Seiteneffekt die Zuweisung des zweiten Operanden an den ersten Operanden
          und als Rückgabewert den zugewiesenen Wert.
        \item
          Ähnlich funktionieren die binären Operatoren \lstinline{+= -= *= /* %=}.
          Sie wenden die vor dem \lstinline{=} stehende Rechenoperation auf die beiden Operatoren an,
          weisen als Seiteneffekt das Ergebnis dem ersten Operanden zu
          und geben das Rechenergebnis als Wert zurück.
        \item
          Die binären Rechnoperatoren \lstinline{+ - * / %}
          und Vergleichsoperatoren \lstinline{== != < > <= >=}
          haben \emph{keinen\/} Seiteneffekt.
        \item
          Der unäre Rechenoperator \lstinline{-} (arithmetische Negation, Vorzeichen)
          hat ebenfalls \emph{keinen\/} Seiteneffekt.
        \item
          Ein weiterer unärer Operator \emph{ohne\/} Seiteneffekt ist die logische Negation,\\
          in C ausgedrückt durch ein Ausrufezeichen: \lstinline{!}\\
          \lstinline{!a} ist 1, wenn \lstinline{a} den Wert 0 hat; ansonsten ist es 0.\\
          \lstinline{!(a < b)} ist demzufolge dasselbe wie \lstinline{a >= b}.
        \item
          Der Funktionsaufruf \lstinline{()} (Klammerpaar) ist in C ebenfalls ein unärer Operator.
          Er liefert einen Wert zurück (Rückgabewert der Funktion)
          und hat einen Seiteneffekt (Aufruf der Funktion).
        \item
          Die unären Operatoren \lstinline{++} und \lstinline{--} haben den Seiteneffekt,
          daß sie die Variable, vor oder hinter der sie stehen, um 1 erhöhen (\lstinline{++})
          bzw.\ vermindern (\lstinline{--}).
          Wenn der Operator \emph{vor\/} der Variablen steht (\lstinline{++a}),
          ist der Rückgabewert der um 1 erhöhte/verminderte Wert der Variablen.
          Wenn er hingegen \emph{hinter\/} der Variablen steht (\lstinline{a++}),
          ist der Rückgabewert der ursprüngliche Wert der Variablen;
          das Erhöhen/Vermindern findet in diesem Fall erst danach statt.
          
          \begin{experts}
            Da die Reihenfolge, in der ein Ausdruck ausgewertet wird, nicht immer festliegt,
            sollte man darauf achten, daß die Seiteneffekte eines Ausdruck dessen Wert nicht beeinflussen.
            (\lstinline[style=cmd]{gcc} warnt in derartigen Fällen.)
          \end{experts}
    
        \begin{experts}
          \item
            Ein weiterer binärer Operator \emph{ohne\/} Seiteneffekt ist das Komma.
            Der Ausdruck \lstinline{a, b} bedeutet:
            "`Berechne \lstinline{a}, vergiß es wieder, und gib stattdessen \lstinline{b} zurück."'
            Dies ist nur dann sinnvoll, wenn der Ausdruck \lstinline{a} einen Seiteneffekt hat.
        \end{experts}
      \end{itemize}
    
      Die folgenden vier Programmfragmente sind verschiedene Schreibweisen für genau denselben Code.
      \begin{lstlisting}
        int i;
    
        i = 0;
        while (i < 10)
          {
            printf ("%d\n", i);
            i += 1;
          }
    
        for (i = 0; i < 10; i++)
          printf ("%d\n", i);
    
        i = 0;
        while (i < 10)
          printf ("%d\n", i++);
    
        for (i = 0; i < 10; printf ("%d\n", i++));
      \end{lstlisting}
      Sie bewirken nicht nur dasselbe (Ausgabe der Zahlen von 0 bis 9),
      sondern stehen tatsächlich für \emph{genau dasselbe Programm}.
      Sie laufen genau gleich schnell und unterscheiden sich nur hinsichtlich ihrer Lesbarkeit,
      wobei es vom persönlichen Geschmack abhängt, welche Variante man jeweils als lesbarer empfindet.
      \begin{hint}
        Schreiben Sie Ihre Programme stets so lesbar wie möglich.\\
        Platzsparende Schreibweise macht ein Programm nicht schneller.
      \end{hint}
    
      \subsection{Strukturierte Programmierung}
    
      Bei den bisher vorgestellten Verzweigungen und Schleifen
      ist die Reihenfolge, in der die Befehle abgearbeitet werden, klar erkennbar.
      Darüberhinaus kennt C auch Anweisungen,
      die einen Sprung des Programms bewirken, der diese Struktur durchbricht:
      \begin{itemize}
        \item
          Mit der \lstinline{break}-Anweisung kann das Programm
          die nächst"-äußere \lstinline{while}- oder \lstinline{for}-Schleife
          unmittelbar verlassen.
    
          Das folgende Beispielprogramm zählt von 0 bis 9,
          indem es eine Endlosschleife beim Erreichen von 10
          mittels \lstinline{break} unterbricht.
          Der Schleifenzäher \lstinline{i} wird innerhalb des \lstinline{printf()}
          "`nebenbei"' inkrementiert.
          \begin{lstlisting}[gobble=8]
            int i = 0;
            while (1)
              {
                if (i >= 10)
                  break;
                printf ("%d\n", i++);
              }
          \end{lstlisting}
          Eine übersichtlichere Schreibweise derselben Schleife lautet:
          \begin{lstlisting}[gobble=8]
            for (int i = 0; i < 10; i++)
              printf ("%d\n", i++);
          \end{lstlisting}
          (Der erzeugte Code ist in beiden Fällen genau derselbe.)
        \item
          Mit der \lstinline{continue}-Anweisung springt ein Programm
          unmittelbar in den nächsten Durchlauf der nächst"-äußeren Schleife.
        \item
          Mit der \lstinline{return}-Anweisung kann man eine Funktion
          (siehe Abschnitt~\ref{Funktionen}) ohne Umweg direkt verlassen.
        \item
          Mit der \lstinline{goto}-Anweisung springt ein Programm
          direkt an einen \newterm{Label}.
          Dieser besteht aus einem Namen, gefolgt von einem Doppelpunkt.
          \begin{lstlisting}[gobble=8]
              int i = 0;
            loop:
              if (i >= 10)
                goto endloop;
              printf ("%d\n", i++);
              goto loop;
            endloop:
          \end{lstlisting}
      \end{itemize}
    
      Ein Programmquelltext sollte immer so gestaltet werden,
      daß er den Ablauf des Programms unmittelbar ersichtlich macht.
      Ein vorzeitiges \lstinline{return} stellt einen "`Hinterausgang"'
      einer Funktion dar und sollte mit Bedacht eingesetzt werden.
    
      Ähnliches gilt in noch stärkerem Maße für \lstinline{break} und \lstinline{continue}
      als "`Hinterausgänge"' von Schleifen.
      Diese sind sicherlich bequeme Möglichkeiten, zusätzliche \lstinline{if}s
      und zusätzliche Wahrheitswert-Variable zu vermeiden,
      verschleiern aber langfristig den Ablauf der Befehle.
      Statt eine Schleife mit \lstinline{break} zu verlassen
      oder Teile des Schleifeninneren mit \lstinline{continue} zu überspringen,
      ist es besser, die Schleifenbedingung
      und \lstinline{if}-Anweisungen innerhalb der Schleife so zu formulieren,
      daß Sie kein \lstinline{break} oder \lstinline{continue} mehr benötigen.
      Dadurch versteht man auch selbst besser, was das Programm eigentlich tut.
      Das Programm wird übersichtlicher und oft sogar kürzer.
    
      In besonderem Maße gilt dies für die \lstinline{goto}-Anweisung.
      Hier ist nicht erkennbar, ob der Sprung nach oben geht (Schleife) oder nach unten (Verzweigung).
      Verschachtelungen von Blöcken und \lstinline{goto}-Sprüngen
      bereiten dem Compiler zusätzliche Arbeit und stehen somit der Optimierung entgegen.
      (Es stimmt insbesondere nicht, daß Konstruktionen mit \lstinline{goto}
      schneller abgearbeitet würden als Konstruktionen mit \lstinline{if} und \lstinline{while}.)
      Es ist daher besser, \lstinline{goto} nicht zu verwenden
      und stattdessen den Programmablauf mit Hilfe von Verzweigungen und Schleifen
      zu strukturieren.
      (Siehe auch: \url{http://xkcd.com/292/})
    
      Zusammengefaßt:
      \begin{hint}
        Verwenden Sie vorzeitiges \lstinline{return} mit Bedacht.
    
        Vermeiden Sie die Verwendung von \lstinline{break} und \lstinline{continue}.
        
        Verwenden Sie kein \lstinline{goto}.
      \end{hint}
    
      \subsection{Funktionen\label{Funktionen}}
    
      Eine Funktionsdeklaration hat in C die Gestalt:
      \begin{quote}
        Typ Name ( Parameterliste )\\
        \{\\
        \strut\quad Anweisungen\\
        \}
      \end{quote}
    
      Beispielprogramm: \gitfile{hp}{script}{functions-1.c}
      \begin{lstlisting}
        #include <stdio.h>
    
        void foo (int a, int b)
        {
          printf ("foo(): a = %d, b = %d\n", a, b);
        }
    
        int main (void)
        {
          foo (3, 7);
          return 0;
        }
      \end{lstlisting}
      (Das Wort "`foo"' ist eine sog.\ \newterm{metasyntaktische Variable} --
      ein Wort, das absichtlich nichts bedeutet und für einen beliebig austauschbaren Namen steht.)
    
      Mit dem Funktionsaufruf \lstinline{foo (3, 7)} stellt das Hauptprogramm der Funktion \lstinline{foo()}
      die Parameterwerte 3 für \lstinline{a} und 7 für \lstinline{b} zur Verfügung.
    
      Der Rückgabewert der Funktion \lstinline{foo()} ist vom Typ \lstinline{void}.
      Im Gegensatz zu Datentypen wie z.\,B.\ \lstinline{int}, das für ganze Zahlen steht,
      steht \lstinline{void} für "`nichts"'.
    
      Von Ausdrücken zurückgegebene \lstinline{void}-Werte \emph{müssen\/} ignoriert werden.
      (Von Ausdrücken zurückgegebene Werte anderer Typen \emph{dürfen\/} ignoriert werden.)
      
      \breath
    
      Das Hauptprogramm ist in C eine ganz normale Funktion.
      Dadurch, daß sie den Namen \lstinline{main} hat,
      weiß das Betriebssystem, daß es sie bei Programmbeginn aufrufen soll.
      \lstinline{main()} kann dann seinerseits weitere Funktionen aufrufen.
    
      Über seinen Rückgabewert (vom Typ \lstinline{int}) teilt \lstinline{main()} dem Betriebssystem mit,
      ob das Programm erfolgreich beendet werden konnte.
      Der Rückgabewert 0 steht für "`Erfolg"'; andere Werte stehen für verschiedenartige Fehler.
      
      \breath
    
      Je nachdem, wo und wie Variable deklariert werden,
      sind sie von verschiedenen Stellen im Programm aus zugänglich
      und/oder verhalten sich unterschiedlich.
    
      Beispielprogramm: \gitfile{hp}{script}{functions-2.c}
      \begin{lstlisting}[style=numbered]
        #include <stdio.h>
    
        int a, b = 3;
    
        void foo (void)
        {
          b++;
          static int a = 5;
          int b = 7;
          printf ("foo(): a = %d, b = %d\n", a, b);
          a++;
          b++;
        }
    
        int main (void)
        {
          printf ("main(): a = %d, b = %d\n", a, b);
          foo ();
          printf ("main(): a = %d, b = %d\n", a, b);
          a = b = 12;
          printf ("main(): a = %d, b = %d\n", a, b);
          foo ();
          printf ("main(): a = %d, b = %d\n", a, b);
          return 0;
        }
      \end{lstlisting}
      Die Ausgabe dieses Programms lautet:
      \begin{lstlisting}[style=terminal]
        main(): a = 0, b = 3
        foo(): a = 5, b = 7
        main(): a = 0, b = 4
        main(): a = 12, b = 12
        foo(): a = 6, b = 7
        main(): a = 12, b = 13
      \end{lstlisting}
      Erklärung:
      \begin{itemize}
        \item
          Der erste Aufruf der Funktion \lstinline{printf()} in Zeile 17 des Programms
          gibt die Werte der in Zeile 3 deklarierten Variablen aus.
          Diese lauten 0 für \lstinline{a} und 3 für \lstinline{b}.
    
          Weil es sich um sog.\ \newterm{globale Variable\/} handelt
          (Die Deklaration steht außerhalb jeder Funktion.),
          werden diese Variablen \emph{bei Programmbeginn\/} initialisiert.
          Für \lstinline{b} steht der Wert 3 für die Initialisierung innerhalb der Deklaration;
          für \lstinline{a} gilt der implizite Wert 0.
        \item
          Der zweite Aufruf von \lstinline{printf()} erfolgt indirekt über die Funktion \lstinline{foo()},
          die ihrerseits vom Hauptprogramm aus aufgerufen wurde (Zeile 18).
    
          Oberhalb des \lstinline{printf()} (Zeile 10) befinden sich neue Deklarationen für Variable,
          die ebenfalls \lstinline{a} (Zeile 8) und \lstinline{b} heißen (Zeile 9).
          Diese sog.\ \newterm{lokalen Variablen\/} werden auf neue Werte initialisiert,
          die korrekt ausgegeben werden.
    
          Ab den Zeilen 8 und 9 bis zum Ende der Funktion \lstinline{foo()}
          sind die in Zeile 3 deklarierten globalen Variablen \lstinline{a} und \lstinline{b}
          nicht mehr zugreifbar.
        \item
          Der dritte Aufruf von \lstinline{printf()} erfolgt wieder direkt durch das Hauptprogramm (Zeile 19).
    
          \lstinline{a} hat immer noch den Wert 0,
          weil durch das \lstinline{a++} in Zeile 11 eine andere Variable inkrementiert wurde,
          die ebenfalls \lstinline{a} heißt, nämlich die lokale Variable, die in Zeile 8 deklariert wurde.
    
          Dasselbe gilt für \lstinline{b} hinsichtlich der Zeile 12.
          In Zeile 7 jedoch greift die Funktion \lstinline{foo()}
          auf die in Zeile 3 deklarierte globale Variable \lstinline{b} zu,
          die dadurch den Wert 4 (statt vorher: 3) erhält.
        \item
          In Zeile 20 weist das Hauptprogramm beiden in Zeile 3 deklarierten Variablen den Wert 12 zu.
    
          Genauer: Es weist der Variablen \lstinline{a} den Wert \lstinline{b = 12} zu.
          Bei \lstinline{b = 12} handelt es sich um einen Ausdruck mit Seiteneffekt,
          nämlich die Zuweisung des Wertes 12 an die Variable \lstinline{b}.
          Der Wert des Zuweisungsausdrucks ist ebenfalls 12.
        \item
          Der vierte Aufruf von \lstinline{printf()} erfolgt wieder direkt durch das Hauptprogramm (Zeile 21)
          und gibt erwartungsgemäß zweimal den Wert 12 aus.
        \item
          Der fünfte Aufruf von \lstinline{printf()} erfolgt wieder indirekt über die Funktion \lstinline{foo()},
          die ihrerseits vom Hauptprogramm aus aufgerufen wurde (Zeile 22).
    
          Die Funktion \lstinline{foo()} gibt wiederum die Werte
          der in den Zeilen 8 und 9 deklarierten Variablen aus.
    
          Bei \lstinline{b} (Zeile 9) handelt es sich um eine \newterm{automatische Variable}.
          Diese ist nur innerhalb des umgebenden Blockes -- hier der Funktion \lstinline{foo()} -- bekannt.
          Sie wird beim Aufruf der Funktion initialisiert und hat daher in Zeile 10 stets den Wert 7,
          den sie in Zeile 9 bekommen hat.
    
          Die Variable \lstinline{a} (Zeile 8) ist hingegen als \newterm{statisch\/}
          (engl.\ \lstinline{static}) deklariert.
          Sie behält ihren Wert zwischen zwei Aufrufen von \lstinline{foo()},
          wird nur zu Programmbeginn initialisiert
          und ist von außerhalb der Funktion nicht veränderbar.
    
          \begin{experts}
            Ausnahme: Wenn einer anderen Funktion die Adresse der \lstinline{static}-Variablen bekannt ist,
            kann diese die Variable über einen Zeiger verändern -- Siehe Abschnitt~\ref{Zeiger}.
          \end{experts}
    
          Da der Anfangswert 5 der Variablen \lstinline{a} bereits einmal erhöht wurde (Zeile 11),
          wird der Wert 6 ausgegeben.
          (Die Zuweisung des Wertes 12 im Hauptprogramm bezog sich auf ein anderes \lstinline{a},
          nämlich das in Zeile 3 deklarierte.)
        \item
          Der letzte Aufruf von \lstinline{printf()} erfolgt wieder direkt durch das Hauptprogramm (Zeile 23).
    
          \lstinline{a} hat immer noch den Wert 12,
          weil durch das \lstinline{a++} in Zeile 11 eine andere Variable inkrementiert wurde,
          die ebenfalls \lstinline{a} heißt, nämlich die, die in Zeile 8 deklariert wurde.
    
          Dasselbe gilt für \lstinline{b} hinsichtlich der Zeile 12.
          In Zeile 7 jedoch greift die Funktion \lstinline{foo()}
          auf die in Zeile 3 deklarierte Variable \lstinline{b} zu,
          die dadurch den Wert 13 (statt vorher: 12) erhält.
      \end{itemize}
    
      \subsection{Zeiger\label{Zeiger}}
    
      In C können an Funktionen grundsätzlich nur Werte übergeben werden.
      Vom Funktionsrückgabewert abgesehen, hat eine C-Funktion keine Möglichkeit,
      dem Aufrufer Werte zurückzugeben.
    
      Es ist dennoch möglich, eine C-Funktion aufzurufen,
      um eine Variable (oder mehrere) auf einen Wert zu setzen.
      Hierfür übergibt man der Funktion die \newterm{Speicheradresse\/} der Variablen als Wert.
      Der Wert ist ein \newterm{Zeiger\/} auf die Variable.
    
      Wenn einem Zeiger der unäre Operator \lstinline{*} vorangestellt wird,
      ist der resultierende Ausdruck diejenige Variable, auf die der Zeiger zeigt.
      In Deklarationen wird dasselbe Symbol dem Namen vorangestellt,
      um anstelle einer Variablen des genannten Typs
      eine Variable vom Typ "`Zeiger auf Variable des genannten Typs"' zu deklarieren.
      (Das \lstinline{*}-Symbol wirkt jeweils nur auf den unmittelbar folgenden Bezeichner.)
    
      Umgekehrt wird der unäre Operator \lstinline{&} einer Variablen vorangestellt,
      um einen Ausdruck vom Typ "`Zeiger auf Variable dieses Typs"'
      mit dem Wert "`Speicheradresse dieser Variablen"' zu erhalten.
    
      \goodbreak
      Beispielprogramm: \gitfile{hp}{script}{pointers-1.c}
      \begin{lstlisting}
        #include <stdio.h>
    
        void calc_answer (int *a)
        {
          *a = 42;
        }
    
        int main (void)
        {
          int answer;
          calc_answer (&answer);
          printf ("The answer is %d.\n", answer);
          return 0;
        }
      \end{lstlisting}
      Die Funktion \lstinline{calc_answer()} läßt sich vom Hauptprogramm einen Zeiger \lstinline{a}
      auf die lokale Variable \lstinline{answer} des Hauptprogramms übergeben.
      (Aus Sicht des Hauptprogramms ist dieser Zeiger die Adresse \lstinline{&answer}
      der lokalen Variablen \lstinline{answer}.)
      Sie schreibt einen Wert in die Variable \lstinline{*a}, auf die der Zeiger \lstinline{a} zeigt.
      Das Hauptprogramm kann diesen Wert anschließend seiner Variablen \lstinline{answer} entnehmen
      und mit \lstinline{printf()} ausgeben.
    
      Vergißt man beim Aufruf den Adreßoperator \lstinline{&},
      übergibt man den aktuellen Wert der Variablen (hier: eine Zahl)
      anstelle eines Zeigers (und erhält eine Warnung durch den Compiler).
      Dieser Wert wird als eine Speicheradresse interpretiert.
      Diese befindet sich in der Regel außerhalb des Bereichs,
      den das Betriebssystem dem Programm zugewiesen hat.
      Ein Versuch der Funktion, auf diese Speicheradresse zuzugreifen,
      führt dann zum Absturz des Programms (Speicherschutzverletzung).
    
      \subsection{Arrays und Strings\label{Strings}}
    
      \subsubsection{Arrays}
    
      In C ist es möglich, mit einem Zeiger Arithmetik zu betreiben,
      so daß er nicht mehr auf die ursprüngliche Variable zeigt,
      sondern auf ihren Nachbarn im Speicher.
    
      Solche Nachbarn gibt es dann,
      wenn mehrere Variable gleichen Typs gemeinsam angelegt werden.
      Eine derartige Ansammlung von Variablen gleichen Typs heißt \newterm{Array\/} (Feldvariable, Vektor).
    
      Beispielprogramm: \gitfile{hp}{script}{arrays-1.c}
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          int prime[5] = { 2, 3, 5, 7, 11 };
          int *p = prime;
          int i;
          for (i = 0; i < 5; i++)
            printf ("%d\n", *(p + i));
          return 0;
        }
      \end{lstlisting}
    
      Die initialisierte Variable \lstinline{prime} ist ein Array von fünf ganzen Zahlen.
      Der Bezeichner \lstinline{prime} des Arrays wird als Zeiger auf eine \lstinline{int}-Variable verwendet.
      In diesem Sinne sind Arrays und Zeiger in C dasselbe.
    
      \lstinline{p + i} ist ein Zeiger auf den \lstinline{i}-ten Nachbarn von \lstinline{*p}.
      Durch Dereferenzieren \lstinline{*(p + i)} erhalten wir
      den \lstinline{i}-ten Nachbarn von \lstinline{*p} selbst.
    
      Da diese Kombination -- Zeigerarithmetik mit anschließendem Dereferenzieren --
      sehr häufig auftritt, stellt C für die Konstruktion \lstinline{*(p + i)}
      die Abkürzung \lstinline{p[i]} zur Verfügung.
    
      Die von anderen Sprachen her bekannte Schreibweise \lstinline{p[i]}
      für das \lstinline{i}-te Element eines Arrays \lstinline{p}
      ist also in C lediglich eine Abkürzung für \lstinline{*(p + i)},
      wobei man \lstinline{p} gleichermaßen als Array wie als Zeiger auffassen kann.
      
      Wenn wir uns dieser Schreibweise bedienen
      und anstelle des Zeigers \lstinline{p}, der durchgehend den Wert \lstinline{prime} hat,
      direkt \lstinline{prime} verwenden,
      erhalten wir das Beispielprogramm \gitfile{hp}{script}{arrays-2.c}:
      \goodbreak
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          int prime[5] = { 2, 3, 5, 7, 11 };
          int *p = prime;
          int i;
          for (i = 0; i < 5; i++)
            printf ("%d\n", p[i]);
          return 0;
        }
      \end{lstlisting}
    
      Achtung: C prüft \emph{nicht}, ob der Array-Index
      innerhalb des zulässigen Bereichs liegt,
      ob also der durch Addition des Index auf die Array-Adresse erhaltene Zeiger
      noch auf eine Adresse innerhalb des Arrays zeigt.
    
      Übergelaufene Indizes führen nicht immer sofort zum Absturz des Programms,
      sondern können z.\,B.\ andere Variablen des Programms überschreiben.
      Da derartige Fehler äußerst schwer zu entdecken sind,
      lohnt es sich, Array-Indices vor ihrer Verwendung
      mit Hilfe von \lstinline{if}-Anweisungen "`von Hand"' zu prüfen.
    
      \subsubsection{Strings}
    
      Ein wichtiger Spezialfall ist ein Array, dessen Komponenten den Datentyp \lstinline{char} haben.
      In C ist \lstinline{char} wie \lstinline{int} eine ganze Zahl;
      der einzige Unterschied besteht darin, daß der Wertebereich von \lstinline{char} daran angepaßt ist,
      ein Zeichen (Buchstabe, Ziffer, Satz- oder Sonderzeichen, engl.\ character) aufzunehmen.
      Ein typischer Wertebereich für den Datentyp \lstinline{char} ist von $-$128 bis 127.
    
      Ein Initialisierer für ein Array von \lstinline{char}-Variablen kann direkt als Folge von Zeichen
      (Zeichenkette, engl.\ \newterm{String\/}) mit doppelten Anführungszeichen geschrieben werden.
      Jedes Zeichen initialisiert eine ganzzahlige Variable mit seinem ASCII-Wert.
      An das Ende eines in dieser Weise notierten Array-Initialisierers
      fügt der Compiler implizit einen Ganzzahl-Initialisierer für den Zahlenwert 0 an.
      Der Array-Initialisierer \lstinline{"Hello"} ist also gleichbedeutend mit
      \lstinline|{ 72, 101, 108, 108, 111, 0 }|.
      (Die 72 steht für ein großes H, die 111 für ein kleines o. Man beachte die abschließende 0 am Ende!)
    
      Ein String in C ist also ein Array von \lstinline{char}s,
      also ein Zeiger auf \lstinline{char}s,
      also ein Zeiger auf ganze Zahlen, deren Wertebereich daran angepaßt ist, Zeichen aufzunehmen.
    
      Wenn bei der Deklaration eines Arrays die Länge aus dem Initialisierer hervorgeht,
      braucht diese nicht ausdrücklich angegeben zu werden.
      In diesem Fall folgt auf den Bezeichner nur das Paar eckiger Klammern und der Initialisierer.
    
      Das Beispielprogramm \gitfile{hp}{script}{strings-1.c} zeigt,
      wie das Array durchlaufen werden kann, bis die Zahl 0 gefunden wird:
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          char hello_world[] = "Hello, world!\n";
          int i = 0;
          while (hello_world[i] != 0)
            printf ("%d", hello_world[i++]);
          return 0;
        }
      \end{lstlisting}
    
      Durch die Formatangabe \lstinline{%d} wird jedes Zeichen -- korrektermaßen -- als Dezimalzahl ausgegeben.
      Wenn wir stattdessen die Formatangabe \lstinline{%c} verwenden (für \emph{character\/}),
      wird für jedes Zeichen -- ebenso korrektermaßen -- sein Zeichenwert (Buchstabe, Ziffer, \dots) ausgegeben
      (Datei: \gitfile{hp}{script}{strings-2.c}):
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          char hello_world[] = "Hello, world!\n";
          int i = 0;
          while (hello_world[i] != 0)
            printf ("%c", hello_world[i++]);
          return 0;
        }
      \end{lstlisting}
    
      Durch Verwendung von Pointer-Arithmetik
      und Weglassen der überflüssigen Abfrage \lstinline{!= 0}
      erhalten wir das äquivalente Beispielprogramm \gitfile{hp}{script}{strings-3.c}:
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          char hello_world[] = "Hello, world!\n";
          char *p = hello_world;
          while (*p)
            printf ("%c", *p++);
          return 0;
        }
      \end{lstlisting}
      Dieses ist die in C übliche Art, eine Schleife zu schreiben,
      die nacheinander alle Zeichen in einem String bearbeitet.
    
      \breath
    
      Eine weitere Formatangabe \lstinline{%s} dient in \lstinline{printf()} dazu,
      direkt einen kompletten String bis ausschließlich der abschließenden 0 auszugeben.
    
      Beispielprogramm: \gitfile{hp}{script}{strings-4.c}
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          char *p = "Hello, world!";
          printf ("%s\n", p);
          return 0;
        }
      \end{lstlisting}
    
      Anstatt als Array, das dann einem Zeiger zugewiesen wird,
      deklarieren wir die Variable \lstinline{hello_world} direkt als Zeiger.
      Dies ist die in C übliche Art, mit String-Konstanten umzugehen.
    
      Allein die Formatspezifikation entscheidet darüber,
      wie die Parameter von \lstinline{printf()} bei der Ausgabe dargestellt werden:
      \begin{quote}
        \begin{tabular}{cl}
          \lstinline|%d| & Der Parameter wird als Zahlenwert interpretiert und dezimal ausgegeben. \\
          \lstinline|%x| & Der Parameter wird als Zahlenwert interpretiert und hexadezimal ausgegegeben.\\
          \lstinline|%c| & Der Parameter wird als Zahlenwert interpretiert und als Zeichen ausgegeben.\\
          \lstinline|%s| & Der Parameter wird als Zeiger interpretiert und als Zeichenfolge ausgegeben.
        \end{tabular}
      \end{quote}
    
      \subsection{String-Operationen}
    
      Mit \lstinline{#include <string.h>} steht uns eine Sammlung von Funktionen
      zur Bearbeitung von Strings (= Array von \lstinline{char}-Variablen
      $\approx$ Zeiger auf \lstinline{char}-Variable) zur Verfügung:
    
      \begin{itemize}
        \item[\textbf{;\,)}]
          \lstinline{+}-Operationen
    
          Durch Addieren einer ganzen Zahl auf die Startadresse des Strings
          entsteht ein Zeiger auf einen neuen String,
          der erst ein paar Zeichen später beginnt.
          Auf diese Weise kann man in C ganz ohne Benutzung einer Bibliothek
          den Anfang eines Strings abschneiden.
    
          \begin{lstlisting}[gobble=8]
            char hello[] = "Hello, world!\n";
            printf ("%s\n", hello + 7);
          \end{lstlisting}
    
          \textbf{Achtung:} Es findet keinerlei Prüfung statt,
          ob der Zeiger nach der Addition
          noch auf einen Bereich innerhalb des Strings zeigt.
          Wenn man auf diese Weise über den String hinausliest,
          führt dies zu unsinnigen Ergebnissen
          bis hin zu einem Absturz (Speicherzugriffsfehler).
    
          Beispielprogramm: \gitfile{hp}{20161024}{strings-14.c}
    
        \item[\textbf{;\,)}]
          Null-Zeichen in den String schreiben
    
          Durch das Schreiben eines Null-Symbols (Zahlenwert 0) in den String
          kann man diesen ganz ohne Benutzung einer Bibliothek
          an dieser Stelle abschneiden.
    
          \begin{lstlisting}[gobble=8]
            char hello[] = "Hello, world!\n";
            hello[5] = 0;
            printf ("%s\n", hello);
          \end{lstlisting}
    
          \textbf{Achtung:} Es findet keinerlei Prüfung statt,
          ob der Schreibvorgang noch innerhalb des Strings stattfindet.
          Wenn man auf diese Weise über den String hinauschreibt,
          werden andere Variable überschrieben,
          was in der Regel zu einem Absturz führt (Speicherzugriffsfehler).
    
          Beispielprogramm: \gitfile{hp}{20161024}{strings-14.c}
    
        \item
          \lstinline{strlen()} -- Ermitteln der Länge eines Strings
    
          Das abschließende Null-Symbol wird für die Länge \emph{nicht\/} mitgezählt,
          es verbraucht aber natürlich dennoch Speicherplatz.
    
          \begin{lstlisting}[gobble=8]
            char hello[] = "Hello, world!\n";
            printf ("%s\n", strlen (hello));
          \end{lstlisting}
    
          Beispielprogramm: \gitfile{hp}{20161024}{strings-14.c}
    
        \item
          \lstinline{strcmp()} -- Strings vergleichen
    
          Wenn der erste String-Parameter alphabetisch vor dem zweiten liegt,
          gibt \lstinline{strcmp()} den Wert \lstinline{-1} zurück,
          wenn es umgekehrt ist, den Wert \lstinline{1},
          wenn die Strings gleich sind, den Wert \lstinline{0}.
    
          \begin{lstlisting}[gobble=8]
            char *anton = "Anton";
            char *zacharias = "Zacharias";
    
            printf ("%d\n", strcmp (anton, zacharias));
            printf ("%d\n", strcmp (zacharias, anton));
            printf ("%d\n", strcmp (anton, anton));
          \end{lstlisting}
          
          Der Vergleich erfolgt im Sinne des verwendeten Zeichensatzes,
          normalerweise ASCII. Dabei kommen z.\,B.\ Großbuchstaben grundsätzlich
          \emph{vor\/} den Kleinbuchstaben.
    
          Beispielprogramm: \gitfile{hp}{20161024}{strings-15.c}
    
        \item
          \lstinline{strcat()} -- String an anderen String anhängen
    
          Die Funktion \lstinline{strcat()} hängt den zweiten String
          an den ersten an.
    
          \begin{lstlisting}[gobble=8]
            char *anton = "Anton";
            char buffer[100] = "Huber ";
            strcat (buffer, anton);
            printf ("%s\n", buffer);
          \end{lstlisting}
    
          \textbf{Achtung:} Es findet keinerlei Prüfung statt,
          ob der resultierende String noch in den für den ersten Strng reservierten
          Speicherbereich (Puffer) hineinpaßt.
          Wenn man auf diese Weise über den String hinauschreibt,
          werden andere Variable überschrieben,
          was in der Regel zu einem Absturz führt (Speicherzugriffsfehler).
          
          Beispielprogramm: \gitfile{hp}{20161024}{strings-15.c}
    
        \item
          \lstinline{sprintf()} -- in String schreiben
    
          \lstinline{sprintf()} funktioniert ähnlich wie \lstinline{printf()},
          schreibt aber nicht zur Standardausgabe (Bildschirm),
          sondern in einen String hinein, den man als ersten Parameter übergibt.
    
          \begin{lstlisting}[gobble=8]
            char buffer[100] = "";
            sprintf (buffer, "Die Antwort lautet: %d", 42);
            printf ("%s\n", buffer);
          \end{lstlisting}
    
          \textbf{Achtung:} Es findet keinerlei Prüfung statt, ob der Ziel-String
          (Puffer -- \newterm{Buffer\/}) groß genug ist, um die Ausgabe aufzunehmen.
          Wenn dies nicht der Fall ist un man über das Ende des Strings hinausschreibt,
          werden andere Variable des Programms überschrieben (\newterm{Buffer Overflow}),
          was in der Regel zu einem Absturz führt (Speicherzugriffsfehler).
          Derartige Fehler sind schwer zu finden und befinden sich zum Teil bis heute
          in Programmen, die im Internet zum Einsatz kommen
          und Angreifern ermöglichen, Rechner von außen zu übernehmen.
    
          Um dieses Problem zu vermeiden, empfiehlt es sich,
          anstelle von \lstinline{sprintf()} die Funktion \lstinline{snprintf()}
          zu verwenden. Diese erwartet als zweiten Parameter die Länge des Ziel-Strings
          und sorgt dafür, daß nicht über dessen Ende hinausgeschrieben wird.
    
          Beispielprogramm: \gitfile{hp}{20161024}{strings-16.c}
    
        \item
          \lstinline{strstr()} -- in String suchen
    
          Die Funktion \lstinline{strstr()}
          such im ersten String-Parameter nach dem zweiten
          und gibt als Ergebnis einen Zeiger auf diejenige Stelle zurück,
          an der der zweite String gefunden wurde.
    
          \begin{lstlisting}[gobble=8]
            char *answer = strstr (buffer, "Antwort");
            printf ("%s\n", answer);
            printf ("found at: %zd\n", answer - buffer);
          \end{lstlisting}
    
          Wenn man dies in einen Array-Index umrechnen will,
          geschieht dies durch Subtrahieren des Zeigers auf den ersten String.
          Das Ergebnis ist eine Integer vom Typ \lstinline{ssize_t}
          (\emph{signed size type\/}). Um diese mit \lstinline{printf()} auszugeben,
          verwendet man \lstinline{%zd} anstelle von \lstinline{%d}.
    
          Beispielprogramm: \gitfile{hp}{20161024}{strings-16.c}
          
      \end{itemize}
    
      \subsection{Parameter des Hauptprogramms}
    
      Bisher haben wir das Hauptprogramm \lstinline{main()} immer in der Form
      \begin{lstlisting}
        int main (void)
        {
          ...
          return 0;
        }
      \end{lstlisting}
      geschrieben.
      
      Tatsächlich kann das Hauptprogramm vom Betriebssystem Parameter entgegennehmen
      (Datei: \gitfile{hp}{script}{params-1.c}):
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (int argc, char **argv)
        {
          printf ("argc = %d\n", argc);
          for (int i = 0; i < argc; i++)
            printf ("argv[%d] = \"%s\"\n", i, argv[i]);
          return 0;
        }
      \end{lstlisting}
      Bei der ganzen Zahl \lstinline{int argc} handelt es sich um die Anzahl der übergebenen Parameter.
    
      \lstinline{char **argv} ist ein Zeiger auf einen Zeiger auf \lstinline{char}s,
      also ein Array von Arrays von \lstinline{char}s,
      also ein Array von Strings.
      Wenn wir es mit einem Index \lstinline{i} versehen,
      greifen wir auf auf den \lstinline{i}-ten Parameter zu.
      Der Index \lstinline{i} läuft, wie in C üblich, von \lstinline{0} bis \lstinline{argc - 1}.
      Das o.\,a.\ Beispielprogramm gibt alle übergebenen Parameter auf dem Standardausgabegerät aus:
      \begin{lstlisting}[style=terminal]
        $ ¡gcc -std=c99 -Wall -O params-1.c -o params-1¿
        $ ¡./params-1 foo bar baz¿
        argc = 4
        argv[0] = "./params-1"
        argv[1] = "foo"
        argv[2] = "bar"
        argv[3] = "baz"
      \end{lstlisting}
      Genaugenommen übergibt das Betriebssystem dem Programm die gesamte Kommandozeile:
      Der nullte Parameter ist der Aufruf der ausführbaren Datei selbst
      -- in genau der Weise, in der er eingegeben wurde.
    
      Neben \lstinline{argc} gibt es noch einen weiteren Mechanismus,
      mit dem das Betriebssystem dem Programm die Anzahl der übergebenen Parameter mitteilt:
      Als Markierung für das Ende der Liste wird ein zusätzlicher Zeiger übergeben, der auf "`nichts"' zeigt,
      dargestellt durch die Speicheradresse mit dem Zahlenwert 0,
      in C mit \lstinline{NULL} bezeichnet.
    
      Um die Parameter des Programms in einer Schleife durchzugehen,
      können wir also entweder von \lstinline{0} bis \lstinline{argc - 1} zählen
      (Schleifenbedingung \lstinline{i < argc}, Datei: \gitfile{hp}{script}{params-1.c} -- siehe oben)
      oder die Schleife mit dem Erreichen der Endmarkierung abbrechen
      (Schleifenbedingung \lstinline{argv[i] != NULL}, Datei: \gitfile{hp}{script}{params-2.c}).
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (int argc, char **argv)
        {
          printf ("argc = %d\n", argc);
          for (int i = 0; argv[i] != NULL; i++)
            printf ("argv[%d] = \"%s\"\n", i, argv[i]);
          return 0;
        }
      \end{lstlisting}
      Auch für Zeiger gilt: \lstinline{NULL} entspricht dem Wahrheitswert "`falsch"';
      alles andere dem Wahrheitswert "`wahr"'.
      Wir dürfen die Schleifenbedingung also wie folgt abkürzen (Datei: \gitfile{hp}{script}{params-3.c}):
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (int argc, char **argv)
        {
          printf ("argc = %d\n", argc);
          for (char **p = argv; *p; p++)
            printf ("argv[p] = \"%s\"\n", *p);
          return 0;
        }
      \end{lstlisting}
    
      \subsection{Strukturen\label{Strukturen}}
    
      In vielen Situationen ist es sinnvoll,
      mehrere Variable zu einer Einheit zusammenzufassen.
    
      Das folgende Beispielprogramm \gitfile{hp}{script}{structs-1.c}
      faßt drei Variable \lstinline{day}, \lstinline{month} und \lstinline{year}
      zu einem einzigen -- neuen -- Datentyp \lstinline{date} zusammen:
      \begin{lstlisting}
        #include <stdio.h>
    
        typedef struct
        {
          char day, month;
          int year;
        }
        date;
    
        int main (void)
        {
          date today = { 1, 11, 2016 };
          printf ("%d.%d.%d\n", today.day, today.month, today.year);
          return 0;
        }
      \end{lstlisting}
      \begin{picture}(0,0)
        \color{red}
        \put(4,4.95){\makebox(0,0)[l]{$\left.\rule{0pt}{1.4cm}\right\}$ neuer Datentyp: date}}
        \put(4.9,3){\vector(-1,-1){0.5}}
        \put(5,3){\makebox(0,0)[l]{Variable deklarieren und initialisieren}}
        \put(5.55,1.1){\vector(-1,1){0.5}}
        \put(5.65,1.1){\makebox(0,0)[l]{Zugriff auf die Komponente day
                                        der strukturierten Variablen today}}
      \end{picture}%
      (Zur Erinnerung: Der Datentyp \lstinline{char} steht für Zahlen,
      die mindestens die Werte von $-$128 bis 127 annehmen können.
      C unterscheidet nicht zwischen Zahlen und darstellbaren Zeichen.)
    
      Eine wichtige Anwendung derartiger \newterm{strukturierter Datentypen\/} besteht darin,
      zusammengehörige Daten als Einheit an Funktionen übergeben zu können
      (Beispielprogramm: \gitfile{hp}{script}{structs-2.c}):
      \begin{lstlisting}
        #include <stdio.h>
    
        typedef struct
        {
          char day, month;
          int year;
        }
        date;
    
        void set_date (date *d)
        {
          (*d).day = 1;
          (*d).month = 11;
          (*d).year = 2016;
        }
    
        int main (void)
        {
          date today;
          set_date (&today);
          printf ("%d.%d.%d\n", today.day,
                  today.month, today.year);
          return 0;
        }
      \end{lstlisting}
      Die Funktion \lstinline{set_date()} hat die Aufgabe,
      eine \lstinline{date}-Variable mit Werten zu füllen (sog.\ \newterm{Setter\/}-Funktion).
      Damit dies funktionieren kann, übergibt das Hauptprogramm an die Funktion
      einen Zeiger auf die strukturierte Variable.
      Über diesen Zeiger kann die Funktion dann auf alle Komponenten der Struktur zugreifen.
      (Die Alternative wäre gewesen, für jede Komponente einen separaten Zeiger zu übergeben.)
    
      Da die Zeigerdereferenzierung \lstinline{*foo}
      mit anschließendem Komponentenzugriff \lstinline{(*foo).bar}
      eine sehr häufige Kombination ist, kennt C hierfür eine Abkürzung:
      \lstinline{foo->bar}
    
      \goodbreak
      Beispielprogramm: \gitfile{hp}{script}{structs-3.c}
      \goodbreak
      \begin{lstlisting}
        #include <stdio.h>
    
        typedef struct
        {
          char day, month;
          int year;
        }
        date;
    
        void set_date (date *d)
        {
          d->day = 1;
          d->month = 11;
          d->year = 2016;
        }
    
        int main (void)
        {
          date today;
          set_date (&today);
          printf ("%d.%d.%d\n", today.day,
                  today.month, today.year);
          return 0;
        }
      \end{lstlisting}
    
      \goodbreak
      \subsubsection*{Aufgabe}
    
      Schreiben Sie eine Funktion \lstinline{inc_date (date *d)}
      die ein gegebenes Datum \lstinline{d}
      unter Beachtung von Schaltjahren auf den nächsten Tag setzt.
    
      \goodbreak
      \subsubsection*{Lösung}
    
      Wir lösen die Aufgabe über den sog.\ \newterm{Top-Down-Ansatz} ("`vom Allgemeinen zum Konkreten"').
      Als besonderen Trick approximieren wir unfertige Programmteile zunächst durch einfachere, fehlerbehaftete.
      Diese fehlerhaften Programmteile sind in den untenstehenden Beispielen rot markiert.
      (In der Praxis würde man diese Zeilen unmittelbar durch die richtigen ersetzen;
      die fehlerhaften "`Platzhalter"' sollten also jeweils nur für Sekundenbruchteile im Programm stehen.
      Falls man einmal tatsächlich einen Platzhalter für mehrere Sekunden oder länger stehen lassen sollte
      -- z.\,B., weil an mehreren Stellen Änderungen notwendig sind --,
      sollte man ihn durch etwas Uncompilierbares (z.\,B.\ \lstinline{@@@}) markieren,
      damit man auf jeden Fall vermeidet, ein fehlerhaftes Programm auszuliefern.)
    
      Zunächst kopieren wir das Beispielprogramm \gitfile{hp}{script}{structs-3.c}
      und ergänzen den Aufruf der -- noch nicht existierenden -- Funktion \lstinline{inc_date()}
      (Datei: \gitfile{{hp}script}{incdate-0.c}):
      \begin{lstlisting}
        #include <stdio.h>
    
        typedef struct
        {
          char day, month;
          int year;
        }
        date;
      \end{lstlisting}
      \begin{lstlisting}
        void set_date (date *d)
        {
          d->day = 31;
          d->month = 1;
          d->year = 2012;
        }
      \end{lstlisting}
      \begin{lstlisting}
        int main (void)
        {
          date today;
          set_date (&today);
          ¡inc_date (&today);¿
          printf ("%d.%d.%d\n", today.day, today.month, today.year);
          return 0;
        }
      \end{lstlisting}
    
      Als nächstes kopieren wir innerhalb des Programms die Funktion \lstinline{get_date()}
      als "`Schablone"' für \lstinline{inc_date()}:
      \begin{lstlisting}
        void get_date (date *d)
        {
          d->day = 31;
          d->month = 1;
          d->year = 2012;
        }
    
        ¡void inc_date (date *d)
        {
          d->day = 31;
          d->month = 1;
          d->year = 2012;
        }¿
      \end{lstlisting}
      Da die Funktion jetzt existiert, ist der Aufruf nicht mehr fehlerhaft.
      Stattdessen haben wir jetzt eine fehlerhafte Funktion \lstinline{inc_date()}.
    
      Im nächsten Schritt ersetzen wir die fehlerhafte Funktion
      durch ein simples Hochzählen der \lstinline{day}-Kom\-po\-nen\-te (Datei: \gitfile{hp}{script}{incdate-1.c})
      \begin{lstlisting}
        void inc_date (date *d)
        {
          ¡d->day += 1;  /* FIXME */¿
        }
      \end{lstlisting}
      Diese naive Vorgehensweise versagt, sobald wir den Tag über das Ende des Monats hinauszählen.
      Dies reparieren wir im nächsten Schritt,
      wobei wir für den Moment inkorrekterweise annehmen, daß alle Monate 30 Tage hätten
      und das Jahr beliebig viele Monate.
      (Datei: \gitfile{hp}{script}{incdate-2.c}):
      \begin{lstlisting}
        void inc_date (date *d)
        {
          d->day++;
          ¡if (d->day > 31)  /* FIXME */
            {
              d->month++;  /* FIXME */
              d->day = 1;
            }¿
        }
      \end{lstlisting}
      Zunächst reparieren wir den Fehler, der am Ende des Jahres entsteht
      (Datei: \gitfile{hp}{script}{incdate-3.c}).
      \begin{lstlisting}
        void inc_date (date *d)
        {
          d->day++;
          if (d->day > 31)  /* FIXME */
            {
              d->month++;
              d->day = 1;
              ¡if (d->month > 12)
                {
                  d->year++;
                  d->month = 1;
                }¿
            }
        }
      \end{lstlisting}
      Das Problem der unterschiedlich langen Monate gehen wir wieder stufenweise an.
      Zunächst ersetzen wir die Konstante \lstinline{31}
      durch eine Variable \lstinline{days_in_month}.
      (Datei: \gitfile{hp}{script}{incdate-4.c})
      \begin{lstlisting}
        void inc_date (date *d)
        {
          d->day++;
          ¡int days_in_month = 31;  /* FIXME */
          if (d->day > days_in_month)¿
            {
              d->month++;
              d->day = 1;
              if (d->month > 12)
                {
                  d->year++;
                  d->month = 1;
                }
            }
        }
      \end{lstlisting}
      Anschließend reparieren wir den fehlerhaften (konstanten) Wert der Variablen,
      wobei wir zunächst das Problem der Schaltjahre aussparen (Datei: \gitfile{hp}{script}{incdate-5.c}):
      \begin{lstlisting}
        void inc_date (date *d)
        {
          d->day++;
          int days_in_month = 31;
          ¡if (d->month == 2)
            days_in_month = 28;  /* FIXME */
          else if (d->month == 4 || d->month == 6 || d->month == 9 || d->month == 11)
            days_in_month = 30;¿
          if (d->day > days_in_month)
            {
              d->month++;
              d->day = 1;
              if (d->month > 12)
                {
                  d->year++;
                  d->month = 1;
                }
            }
        }
      \end{lstlisting}
      Auf dieselbe Weise lagern wir das Problem "`Schaltjahr oder nicht?"'
      in eine Variable aus. Diese ist wieder zunächst konstant
      (Datei: \gitfile{hp}{script}{incdate-6.c}):
      \begin{lstlisting}
        void inc_date (date *d)
        {
          d->day++;
          int days_in_month = 31;
          if (d->month == 2)
            {
              ¡int is_leap_year = 1;  /* FIXME */
              if (is_leap_year)
                days_in_month = 29;
              else
                days_in_month = 28;¿
            }
          else if (d->month == 4 || d->month == 6 || d->month == 9 || d->month == 11)
            days_in_month = 30;
          if (d->day > days_in_month)
            {
              d->month++;
              d->day = 1;
              if (d->month > 12)
                {
                  d->year++;
                  d->month = 1;
                }
            }
        }
      \end{lstlisting}
      Als nächstes ergänzen wir die Vier-Jahres-Regel für Schaltjahre
      (Datei \gitfile{hp}{script}{incdate-7.c}):
      \begin{lstlisting}
              ¡int is_leap_year = 0;
              if (d->year % 4 == 0)
                is_leap_year = 1;  /* FIXME */¿
              if (is_leap_year)
                days_in_month = 29;
              else
                days_in_month = 28;
      \end{lstlisting}
      Das nun vorliegende Programm arbeitet bereits für den julianischen Kalender
      sowie für alle Jahre von 1901 bis 2099 korrekt,
      nicht jedoch für z.\,B.\ das Jahr 2100 (Datei: \gitfile{hp}{script}{incdate-8.c}).
      Damit das Programm für den aktuell verwendeten gregorianischen Kalender korrekt arbeitet,
      ergänzen wir noch die Ausnahme, daß durch 100 teilbare Jahre keine Schaltjahre sind,
      sowie die Ausnahme von der Ausnahme, daß durch 400 teilbare Jahre
      (z.\,B.\ das Jahr 2000) eben doch Schaltjahre sind (Datei: \gitfile{hp}{script}{incdate-9.c}):
      \begin{lstlisting}
              int is_leap_year = 0;
              if (d->year % 4 == 0)
                ¡{
                  is_leap_year = 1;
                  if (d->year % 100 == 0)
                    {
                      is_leap_year = 0;
                      if (d->year % 400 == 0)
                        is_leap_year = 1;
                    }
                }¿
              if (is_leap_year)
                days_in_month = 29;
              else
                days_in_month = 28;
      \end{lstlisting}
      Damit ist die Aufgabe gelöst.
      Der vollständige Quelltext der Lösung (Datei: \gitfile{hp}{script}{incdate-9.c}) lautet:
      \begin{lstlisting}
        #include <stdio.h>
    
        typedef struct
        {
          char day, month;
          int year;
        }
        date;
      \end{lstlisting}
      \begin{lstlisting}
        void set_date (date *d)
        {
          d->day = 28;
          d->month = 2;
          d->year = 2000;
        }
      \end{lstlisting}
      \begin{lstlisting}
        void inc_date (date *d)
        {
          d->day++;
          int days_in_month = 31;
          if (d->month == 2)
            {
              int is_leap_year = 0;
              if (d->year % 4 == 0)
                {
                  is_leap_year = 1;
                  if (d->year % 100 == 0)
                    {
                      is_leap_year = 0;
                      if (d->year % 400 == 0)
                        is_leap_year = 1;
                    }
                }
              if (is_leap_year)
                days_in_month = 29;
              else
                days_in_month = 28;
            }
          else if (d->month == 4 || d->month == 6 || d->month == 9 || d->month == 11)
            days_in_month = 30;
          if (d->day > days_in_month)
            {
              d->month++;
              d->day = 1;
              if (d->month > 12)
                {
                  d->year++;
                  d->month = 1;
                }
            }
        }
      \end{lstlisting}
      \begin{lstlisting}
        int main (void)
        {
          date today;
          set_date (&today);
          inc_date (&today);
          printf ("%d.%d.%d\n", today.day, today.month, today.year);
          return 0;
        }
      \end{lstlisting}
      Bemerkungen:
      \begin{itemize}
        \item
          Anstatt die Anzahl der Tage in einem Monat
          innerhalb der Funktion \lstinline{set_date()} zu berechnen,
          ist es sinnvoll, hierfür eine eigene Funktion zu schreiben.
          Dasselbe gilt für die Berechnung,
          ob es sich bei einem gegebenem Jahr um ein Schaltjahr handelt.
        \item
          Der Top-Down-Ansatz ist eine bewährte Methode,
          um eine zunächst komplexe Aufgabe in handhabbare Teilaufgaben zu zerlegen.
          Dies hilft ungemein, in längeren Programmen (mehrere Zehntausend bis Millionen Zeilen)
          die Übersicht zu behalten.
        \item
          Der Trick mit dem zunächst fehlerhaften Code hat den Vorteil,
          daß man jeden Zwischenstand des Programms compilieren und somit austesten kann.
          Er birgt andererseits die Gefahr in sich,
          die Übersicht über den fehlerhaften Code zu verlieren,
          so daß es dieser bis in die Endfassung schafft.
          Neben dem bereits erwähnten Trick uncompilierbarer Symbole
          haben sich hier Kommentare wie \lstinline{/* FIXME */} bewährt,
          auf die man seinen Code vor der Auslieferung der Endfassung
          noch einmal automatisch durchsuchen läßt.
    %    \item
    %      Allen an der Berechnung beteiligten Funktionen
    %      wurde hier ein Zeiger \lstinline{d} auf die vollständige \lstinline{date}-Struktur übergeben.
    %      Dies ist ein \newterm{objektorientierter Ansatz},
    %      bei dem man die Funktionen als \newterm{Methoden\/} der \newterm{Klasse\/} \lstinline{date} auffaßt.
    %      (Von sich aus unterstützt die Sprache C -- im Gegensatz zu z.\,B.\ C++ -- keine Klassen und Methoden,
    %      sondern man muß diese bei Bedarf in der oben beschrieben Weise selbst basteln.
    %      Für eine fertige Lösung siehe z.\,B.\ die \file{GObject}-Bibliothek -- \url{http://gtk.org}.)
    %
    %      Alternativ könnte man sich mit den zu übergebenden Parametern auf diejenigen beschränken,
    %      die in der Funktion tatsächlich benötigt werden,
    %      also z.\,B.\ \lstinline{int days_in_month (int month, int year)}
    %      und \lstinline{int is_leap_year (int year)}.
    %      Damit wären die Funktionen allgemeiner verwendbar.
    %
    %      Welcher dieser beiden Ansätze der bessere ist, hängt von der Situation
    %      und von persönlichen Vorlieben ab.
      \end{itemize}
    
      \subsection{Dateien und Fehlerbehandlung}
    
      Die einfachste Weise, in C mit Dateien umzugehen,
      ist über sog.\ \newterm{Streams}.
    
      Die Funktion \lstinline{fopen()}
      erwartet als Parameter einen Dateinamen und einen Modus
      und gibt als Rückgabewert einen Zeiger auf einen Stream
      -- eine Struktur vom Typ \lstinline{FILE} -- zurück:
      \begin{lstlisting}
        FILE *f = fopen ("fhello.txt", "w");
      \end{lstlisting}
      Als Modus übergibt man eine String-Konstante.
      Diese kann die Buchstaben \lstinline{r} für Lesezugriff (\emph{read\/}),
      \lstinline{w} für Schreibzugriff mit Überschreiben (\emph{write\/})
      sowie \lstinline{a} für Schreibzugriff mit Anhängen (\emph{append\/}) enthalten
      und zusätzlich den Buchstaben \lstinline{b} für Binärdaten (im Gegensatz zu Text).
    
      Die in C üblichen Ein-/Ausgabefunktionen wie z.\,B.\ \lstinline{printf()}
      haben Varianten mit vorangestelltem "`f-"', z.\,B.\ \lstinline{fprintf()}.
      Wenn man diesen Funktionen als ersten Parameter einen Zeiger auf ein
      \lstinline{FILE} übergibt, verhalten sie sich in der üblichen Weise,
      nur daß sie nicht zur Standardausgabe schreiben (Bildschirm),
      sondern in die Datei, deren Name beim Öffnen des \lstinline{FILE}
      angegeben wurde (Datei \gitfile{hp}{script}{fhello-1.c}):
    
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          FILE *f = fopen ("fhello.txt", "w");
          fprintf (f, "Hello, world!\n");
          fclose (f);
          return 0;
        }
      \end{lstlisting}
    
      Der von \lstinline{fopen()} zurückgegebene Wert ist ein Zeiger.
      Ein Aufruf von \lstinline{fprintf()} oder \lstinline{fclose()}
      stellt eine Verwendung dieses Zeigers dar.
      Wenn die Datei -- aus welchen Gründen auch immer -- nicht geöffnet werden konnte,
      ist dieser Zeiger \lstinline{NULL}, und seine Verwendung führt
      zum Absturz des Programms.
      Es ist daher dringend empfohlen, diesen Fall zu prüfen
      (Datei: \gitfile{hp}{script}{fhello-2.c}):
    
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          FILE *f = fopen ("fhello.txt", "w");
          if (f)
            {
              fprintf (f, "Hello, world!\n");
              fclose (f);
            }
          return 0;
        }
      \end{lstlisting}
    
      Anstatt einfach nur "`nichts"' zu machen,
      ist es besser, eine sinnvolle Fehlermeldung auszugeben.
      Dabei sind wir nicht allein auf "`Fehler beim Öffnen der Datei"' angewiesen:
      Das Betriebssystem teilt uns über die globale Variable \lstinline{errno} mit,
      was genau beim Öffnen der Datei fehlgeschlagen ist.
      Mit \lstinline{#include <errno.h>} erhält unser Programm
      Zugriff auf diese Variable
      und kann den Fehler-Code in seiner Fehlermeldung mit ausgeben
      (Datei: \gitfile{hp}{script}{fhello-3.c}):
    
      \begin{lstlisting}
        #include <stdio.h>
        #include <errno.h>
    
        int main (void)
        {
          FILE *f = fopen ("fhello.txt", "w");
          if (f)
            {
              fprintf (f, "Hello, world!\n");
              fclose (f);
            }
          else
            fprintf (stderr, "error #%d\n", errno);
          return 0;
        }
      \end{lstlisting}
    
      Die Ausgabe von Fehler erfolgt üblicherweise nicht mit einem "`normalen"'
      \lstinline{printf()}, sondern mit einem \lstinline{fprintf()} in die
      bereits standardmäßig geöffnete Datei \lstinline{stderr}, die
      \newterm{Fehlerausgabe}-Datei.
      Diese landet -- genau wie die Standardausgabe -- zunächst auf dem Bildschirm,
      kann aber separat von der Standardausgabe umgeleitet werden,
      z.\,B.\ in eine separate Datei.
    
      Die Bedeutung der Fehler-Codes ist
      nicht nur in der Dokumentation des Betriebssystems,
      sondern auch in einer C-Bibliothek hinterlegt.
      Mit \lstinline{#include <string.h>} erhalten wir
      eine Funktion \lstinline{strerror()},
      die den Fehler-Code in eine für Menschen lesbare Fehlermeldung umwandelt
      (Datei: \gitfile{hp}{script}{fhello-4.c}):
    
      \begin{lstlisting}
        #include <stdio.h>
        #include <errno.h>
        #include <string.h>
    
        int main (void)
        {
          FILE *f = fopen ("fhello.txt", "w");
          if (f)
            {
              fprintf (f, "Hello, world!\n");
              fclose (f);
            }
          else
            {
              char *msg = strerror (errno);
              fprintf (stderr, "%s\n", msg);
            }
          return 0;
        }
      \end{lstlisting}
    
      Ein häufiger Fall ist, daß das Programm nach Ausgabe der Fehlermeldung
      direkt beendet werden soll.
      Hierbei wird nicht das sonst übliche \lstinline{return 0}
      des Hauptprogramms aufgerufen, sondern \lstinline{return}
      mit einer anderen Zahl als 0, z.\,B.\ \lstinline{return 1}
      für "`allgemeiner Fehler"'.
      Üblich ist es, den Fehler-Code zurückgegeben
      -- \lstinline{return errno} --, um diesen auch an denjenigen,
      der das Programm aufgerufen hat, weiterzureichen.
    
      Für diese standardisierte Reaktion auf Fehler
      steht mit \lstinline{#include <error.h>}
      eine Funktion \lstinline{error()} zur Verfügung,
      die eine zum übergebenen Fehler-Code gehörende Fehlermeldung ausgibt
      und anschließend das Programm mit einem übergebenen Fehler-Code beendet
      (Datei: \gitfile{hp}{script}{fhello-5.c}):
    
      \begin{lstlisting}
        #include <stdio.h>
        #include <errno.h>
        #include <error.h>
    
        int main (void)
        {
          FILE *f = fopen ("fhello.txt", "w");
          if (!f)
             error (1, errno, "cannot open file");
          fprintf (f, "Hello, world!\n");
          fclose (f);
          return 0;
        }
      \end{lstlisting}
    
      In diesem Fall ist \lstinline{1} der Code,
      den das Programm im Fehlerfall zurückgeben soll,
      und \lstinline{errno} ist die Nummer des Fehlers,
      dessen Fehlermeldung auf dem Bildschirm (\lstinline{stderr})
      ausgegeben werden soll.
      (Üblich wäre wie gesagt auch, hier zweimal \lstinline{errno} zu übergeben.)
    
      \textbf{Bitte niemals Fehler einfach ignorieren!}
      Ein Programm, das bereits auf eine nicht gefundene Datei
      mit einem Absturz reagiert, ist der Alptraum jedes Benutzers
      und eines jeden, der versucht, in dem Programm Fehler zu beheben.
      Ein korrekt geschriebenes Programm stürzt \emph{niemals\/} ab,
      sondern beendet sich schlimmstensfalls mit einer aussagekräftigen Fehlermeldung,
      die uns in die Lage versetzt, die Fehlerursache zu beheben.
    
      \section{Bibliotheken}
    
      \subsection{Der Präprozessor\label{Praeprozessor}}
    
      Der erste Schritt beim Compilieren eines C-Programms ist das
      Auflösen der sogenannten Präprozessor-Direktiven und -Macros.
      \begin{lstlisting}
        #include <stdio.h>
      \end{lstlisting}
      \vspace{-\medskipamount}
      bewirkt, daß aus Sicht des Compilers anstelle der Zeile
      der Inhalt der Datei \file{stdio.h} im C-Quelltext erscheint.
      Dies ist zunächst unabhängig von Bibliotheken und auch nicht auf die Programmiersprache C beschränkt.
    
      Beispiel:
      Die Datei \gitfile{hp}{script}{maerchen.c} enthält:
      \begin{lstlisting}[language={}]
        Vor langer, langer Zeit
        gab es einmal
        #include "hexe.h"
        Die lebte in einem Wald.
      \end{lstlisting}
      Die Datei \gitfile{hp}{script}{hexe.h} enthält:
      \begin{lstlisting}[language={}]
        eine kleine Hexe.
      \end{lstlisting}
      Der Aufruf
      \begin{lstlisting}[style=terminal]
        $ ¡gcc -E -P maerchen.c¿
      \end{lstlisting}
      produziert die Ausgabe
      \begin{lstlisting}[style=terminal]
        Vor langer, langer Zeit
        gab es einmal
        eine kleine Hexe.
        Die lebte in einem Wald.
      \end{lstlisting}
      Mit der Option \lstinline[style=cmd]{-E} weisen wir \lstinline[style=cmd]{gcc} an,
      nicht zu compilieren, sondern nur den Präprozessor aufzurufen.
      Die Option \lstinline[style=cmd]{-P} unterdrückt Herkunftsangaben,
      die normalerweise vom Compiler verwendet werden,
      um Fehlermeldungen den richtigen Zeilen in den richtigen Dateien
      zuordnen zu können. Ohne das \lstinline[style=cmd]{-P} lautet die Ausgabe:
      \begin{lstlisting}[style=terminal]
        # 1 "maerchen.c"
        # 1 "<built-in>"
        # 1 "<command-line>"
        # 1 "maerchen.c"
        Vor langer, langer Zeit
        gab es einmal
        # 1 "hexe.h" 1
        eine kleine Hexe.
        # 3 "maerchen.c" 2
        Die lebte in einem Wald.
      \end{lstlisting}
    
      Nichts anderes geschieht, wenn man das klassische \file{hello.c}
      (Datei: \gitfile{hp}{script}{hello-1.c} compiliert:
      \begin{lstlisting}
        #include <stdio.h>
    
        int main (void)
        {
          printf ("Hello, world!\n");
          return 0;
        }
      \end{lstlisting}
      Die Datei \file{stdio.h} ist wesentlich länger als \gitfile{hp}{script}{hexe.txt} in dem o.\,a.\
      Beispiel, und sie ruft weitere Include-Dateien auf,
      so daß wir insgesamt auf über 800 Zeilen Quelltext kommen.
    
      Die spitzen Klammern anstelle der Anführungszeichen bedeuten,
      daß es sich um eine \newterm{Standard-Include-Datei\/} handelt,
      die nur in den Standard-Include-Verzeichnissen gesucht werden soll,
      nicht jedoch im aktuellen Verzeichnis.
    
      \subsection{Bibliotheken einbinden}
    
      Tatsächlich ist von den über 800 Zeilen aus \file{stdio.h} nur eine
      einzige relevant, nämlich:
      \begin{lstlisting}
        extern int printf (__const char *__restrict __format, ...);
      \end{lstlisting}
      Dies ist die Deklaration einer Funktion, die sich von einer
      "`normalen"' Funktionsdefinition nur wie folgt unterscheidet:
      \begin{itemize}
        \item
          Die Parameter \lstinline{__const char *__restrict __format, ...}
          heißen etwas ungewöhnlich.
        \item
          Der Funktionskörper \lstinline|{ ... }| fehlt. Stattdessen folgt auf die
          Kopfzeile direkt ein Semikolon \lstinline{;}.
        \item
          Der Deklaration ist das Schlüsselwort \lstinline{extern} vorangestellt.
      \end{itemize}
      Dies bedeutet für den Compiler:
      "`Es gibt diese Funktion und sie sieht aus, wie beschrieben.
      Benutze sie einfach, und kümmere dich nicht darum, wer die Funktion schreibt."'
    
      \begin{experts}
        Wenn wir tatsächlich nur \lstinline{printf()} benötigen,
        können wir also die Standard-Datei \file{stdio.h} durch eine eigene ersetzen,
        die nur die o.\,a.\ Zeile \lstinline{extern int printf (...)} enthält.
        (Dies ist in der Praxis natürlich keine gute Idee, weil nur derjenige, der die
        Funktion \lstinline{printf()} geschrieben hat, den korrekten Aufruf kennt.
        In der Praxis sollten wir immer diejenige Include-Datei benutzen,
        die gemeinsam mit der tatsächlichen Funktion ausgeliefert wurde.)
      \end{experts}
    
      \breath
    
      Der Präprozessor kann nicht nur \lstinline{#include}-Direktiven auflösen.
      Mit \lstinline{#define} kann man sog.\ \newterm{Makros\/} definieren,
      die bei Benutzung durch einen Text ersetzt werden.
      Auf diese Weise kann man \newterm{Konstante\/} definieren.
    
      Beispiel: \gitfile{hp}{script}{higher-math-1.c}
      \begin{lstlisting}
        #include <stdio.h>
    
        #define VIER 4
    
        int main (void)
        {
          printf ("2 + 2 = %d\n", VIER);
          return 0;
        }
      \end{lstlisting}
    
      Genau wie bei \lstinline{#include} nimmt der Präprozessor auch bei \lstinline{#define}
      eine rein textuelle Ersetzung vor, ohne sich um den Sinn des Ersetzten zu kümmern.
    
      Beispiel: \gitfile{hp}{script}{higher-math-2.c}
      \begin{lstlisting}
        #include <stdio.h>
    
        #define wuppdich printf
        #define holla main
        #define pruzzel return
        #define VIER 4
    
        int holla (void)
        {
          wuppdich ("2 + 2 = %d\n", VIER);
          pruzzel 0;
        }
      \end{lstlisting}
    
      Dies kann zu Problemen führen, sobald Berechnungen ins Spiel kommen.
    
      Beispiel: \gitfile{hp}{script}{higher-math-3.c}
      \begin{lstlisting}
        #include <stdio.h>
    
        #define VIER 2 + 2
    
        int main (void)
        {
          printf ("2 + 3 * 4 = %d\n", 2 + 3 * VIER);
          return 0;
        }
      \end{lstlisting}
      Hier z.\,B.\ sieht man mit \lstinline[style=cmd]{gcc -E rechnen.c},
      daß die Ersetzung des Makros \lstinline{VIER} wie folgt lautet:
      \begin{lstlisting}
          printf ("2 + 3 * 4 = %d\n", 2 + 3 * 2 + 2);
      \end{lstlisting}
      Der C-Compiler wendet die Regel "`Punktrechnung geht vor Strichrechnung"' an
      und erfährt überhaupt nicht, daß das \lstinline{2 + 2} aus einem Makro enstanden ist.
    
      Um derartige Effekte zu vermeiden, setzt man arithmetische
      Operationen innerhalb von Makros in Klammern.
    
      Beispiel: \gitfile{hp}{script}{higher-math-4.c}
      \begin{lstlisting}
        #define VIER (2 + 2)
      \end{lstlisting}
    
      (Es ist in den meisten Situationen üblich, Makros in \lstinline{GROSSBUCHSTABEN} zu benennen,
      um darauf hinzuweisen, daß es sich eben um einen Makro handelt.)
    
      Achtung: Hinter Makro-Deklaration kommt üblicherweise \emph{kein\/} Semikolon.
    
      \begin{experts}
        Wenn man ein Semikolon setzt, gehört dies mit zum Ersetzungstext des Makros.
        Dies ist grundsätzlich zulässig, führt aber zu sehr seltsamen C-Quelltexten.
        -- siehe z.\,B.\ \gitfile{hp}{script}{higher-math-5.c}.
      \end{experts}
    
      \breath
    
      Das nächste Beispiel illustriert, wie man Bibliotheken schreibt und verwendet.
      
      Es besteht aus drei Quelltexten:
    
      \gitfile{hp}{script}{philosophy.c}:
      \begin{lstlisting}
        #include <stdio.h>
        #include "answer.h"
    
        int main (void)
        {
          printf ("The answer is %d.\n", answer ());
          return 0;
        }
      \end{lstlisting}
     
      \goodbreak
      \gitfile{hp}{script}{answer.c}:
      \begin{lstlisting}
        int answer (void)
        {
          return 42;
        }
      \end{lstlisting}
     
      \goodbreak
      \gitfile{hp}{script}{answer.h}:
      \begin{lstlisting}
        extern int answer (void);
      \end{lstlisting}
    
      Das Programm \gitfile{hp}{script}{philosophy.c} verwendet eine Funktion \lstinline{answer()}, die
      in der Datei \gitfile{hp}{script}{answer.h} extern deklariert ist.
    
      Der "`normale"' Aufruf
      \begin{lstlisting}[style=terminal]
        $ ¡gcc -Wall -O philosophy.c -o philosophy¿
      \end{lstlisting}
      liefert die Fehlermeldung:
      \begin{lstlisting}[style=terminal]
        /tmp/ccr4Njg7.o: In function `main':
        philosophy.c:(.text+0xa): undefined reference to `answer'
        collect2: ld returned 1 exit status
      \end{lstlisting}
      Diese stammt nicht vom Compiler, sondern vom \newterm{Linker}.
      Das Programm ist syntaktisch korrekt und wird auch korrekt in eine Binärdatei umgewandelt
      (hier: \file{/tmp/ccr4Njg7.o}).
      Erst beim Zusammenbau ("`Linken"') der ausführbaren Datei (\file{philosophy})
      tritt ein Fehler auf.
    
      Tatsächlich wird die Funktion \lstinline{answer()}
      nicht innerhalb von \gitfile{hp}{script}{philosophy.c}, sondern in einer separaten Datei \gitfile{hp}{script}{answer.c},
      einer sog.\ \newterm{Bibliothek\/} definiert.
      Es ist möglich (und üblich), Bibliotheken separat vom Hauptprogramm zu compilieren.
      Dadurch spart man sich das Neucompilieren,
      wenn im Hauptprogramm etwas geändert wurde, nicht jedoch in der Bibliothek.
    
      Mit der Option \lstinline[style=cmd]{-c} weisen wir \lstinline[style=cmd]{gcc} an,
      nur zu compilieren, jedoch nicht zu linken. Die Aufrufe
      \begin{lstlisting}[style=terminal]
        $ ¡gcc -Wall -O -c philosophy.c¿
        $ ¡gcc -Wall -O -c answer.c¿
      \end{lstlisting}
      produzieren die Binärdateien \file{philosophy.o} und \file{answer.o},
      die sogenannten \newterm{Objekt-Dateien} (daher die Endung \file{.o} oder \file{.obj}).
    
      Mit dem Aufruf
      \begin{lstlisting}[style=terminal]
        $ ¡gcc philosophy.o answer.o -o philosophy¿
      \end{lstlisting}
      bauen wir die beiden bereits compilierten Objekt-Dateien zu einer
      ausführbaren Datei \file{philosophy} (hier ohne Endung) zusammen.
    
      Es ist auch möglich, im Compiler-Aufruf gleich beide C-Quelltexte zu
      übergeben:
      \begin{lstlisting}[style=terminal]
        $ ¡gcc -Wall -O philosophy.c answer.c -o philosophy¿
      \end{lstlisting}
      In diesem Fall ruft \lstinline[style=cmd]{gcc} zweimal den Compiler auf
      (für jede C-Datei einmal) und anschließend den Linker.
    
      \subsection{Bibliotheken verwenden (Beispiel: OpenGL)}
    
      Die \newterm{OpenGL\/}-Bibilothek dient dazu,
      unter Verwendung von Hardware-Unterstützung dreidimensionale Grafik auszugeben.
    
      Die einfachste Art und Weise, OpenGL in seinen Programmen einzusetzen,
      erfolgt über eine weitere Bibliothek, das \newterm{OpenGL Utility Toolkit (GLUT)}.
    
      Die Verwendung von OpenGL und GLUT erfolgt durch Einbinden der Include-Dateien
      \begin{lstlisting}
        #include <GL/gl.h>
        #include <GL/glu.h>
        #include <GL/glut.h>
      \end{lstlisting}
      und die Übergabe der Bibliotheken \lstinline[style=cmd]{-lGL -lGLU -lglut} im Compiler-Aufruf: 
      \begin{lstlisting}[style=terminal]
        $ ¡gcc -Wall -O cube.c -lGL -lGLU -lglut -o cube¿
      \end{lstlisting}
      (Dies ist der Aufruf unter Unix.
      Unter Microsoft Windows ist der Aufruf etwas anders
      und hängt von der verwendeten Version der GLUT-Bibliothek ab.
      Für Details siehe die Dokumentation der GLUT-Bibliothek
      sowie die Datei \gitfile{hp}{20161031}{egal.txt}.)
    
      Die Bibliothek stellt uns fertig geschriebene Programmfragmente zur Verfügung, insbesondere:
      \begin{itemize}
        \item
          Funktionen: z.\,B.\ \lstinline{glutInit (&argc, argv);}
        \item
          Konstante: z.\,B.\ \lstinline{GLUT_RGBA}
        \item
          Datentypen: z.\,B.\ \lstinline{GLfloat}
      \end{itemize}
    
      Manche OpenGL-Funktionen erwarten als Parameter ein Array.
      Dies gilt z.\,B.\ beim Setzen von Farben oder beim Positionieren einer Lichtquelle:
      \begin{lstlisting}
        GLfloat light0_position[] = {1.0, 2.0, -2.0, 1.0};
        glLightfv (GL_LIGHT0, GL_POSITION, light0_position);
      \end{lstlisting}
    
      Ein weiteres wichtiges allgemeines Konzept,
      das in OpenGL eine Rolle spielt, ist die Übergabe einer Funktion an die Bibliothek.
      Man nennt dies das \newterm{Installieren einer Callback-Funktion}.
      \begin{lstlisting}
        void draw (void)
        { ... }
    
        glutDisplayFunc (draw);
      \end{lstlisting}
      Wir übergeben die -- von uns geschriebene -- Funktion \lstinline{draw()}
      an die OpenGL-Funktion \lstinline{glutDisplayFunc()}.
      Dies bewirkt, daß OpenGL immer dann, wenn etwas gezeichnet werden soll, \lstinline{draw()} aufruft.
      Innerhalb von \lstinline{draw()} können wir also unsere Zeichenbefehle unterbringen.
    
      \breath
    
      Die OpenGL-Bibliothek ist sehr umfangreich
      und kann im Rahmen dieser Vorlesung nicht im Detail behandelt werden.
      Um trotzdem damit arbeiten zu können,
      lagern wir bestimmte Teile -- Initialisierung und das Setzen von Farben --
      in eine eigene Bibliothek \file{opengl-magic} aus, die wir als "`Black Box"' verwenden.
      Der Compiler-Aufruf lautet dann:
      \begin{lstlisting}[style=terminal]
        $ ¡gcc -Wall -O cube.c -lGL -lGLU -lglut opengl-magic.c -o cube¿
      \end{lstlisting}
      (Wer in eigenen Projekten mehr mit OpenGL machen möchte,
      ist herzlich eingeladen, die Funktionsweise von \file{opengl-magic} zu studieren.)
    
      \begin{itemize}
        \item
          Das Beispielprogramm \gitfile{hp}{script}{cube-1.c} illustriert,
          wie man grundsätzlich überhaupt ein geometrisches Objekt zeichnet.
          In diesem Fall handelt es sich um einen Würfel der Kantenlänge \lstinline{0.5},
          von dem wir nur die Vorderfläche sehen, also ein Quadrat.
          \begin{lstlisting}[gobble=8]
            #include <GL/gl.h>
            #include <GL/glu.h>
            #include <GL/glut.h>
            #include "opengl-magic.h"
    
            void draw (void)
            {
              glClear (GL_COLOR_BUFFER_BIT + GL_DEPTH_BUFFER_BIT);
              set_material_color (1.0, 0.7, 0.0);
              glutSolidCube (0.75);
              glFlush ();
              glutSwapBuffers ();
            }
    
            int main (int argc, char **argv)
            {
              init_opengl (&argc, argv, "Cube");
              glutDisplayFunc (draw);
              glutMainLoop ();
              return 0;
            }
          \end{lstlisting}
          \begin{picture}(0,0)
            \color{red}
            \put(12.5,6.4){\vector(-1,0){1}}
            \put(12.6,6.4){\makebox(0,0)[l]{Bildschirm löschen}}
            \put(7.5,5.95){\vector(-1,0){1}}
            \put(7.6,5.95){\makebox(0,0)[l]{Rotanteil 100\,\%, Grünanteil 70\,\%, Blauanteil 0\,\%}}
            \put(5.5,5.5){\vector(-1,0){1}}
            \put(5.6,5.5){\makebox(0,0)[l]{Würfel zeichnen}}
            \put(4.0,5.05){\vector(-1,0){1}}
            \put(4.1,5.05){\makebox(0,0)[l]{Zeichnung "`abschicken"'}}
            \put(5.2,4.6){\vector(-1,0){1}}
            \put(5.3,4.6){\makebox(0,0)[l]{fertige Zeichnung zeigen; neues "`Zeichenpapier"' bereitlegen}}
            \put(6.0,2.15){\vector(-1,0){1}}
            \put(6.1,2.15){\makebox(0,0)[l]{Callback-Funktion installieren (s.\,o.)}}
            \put(5.0,1.7){\vector(-1,0){1}}
            \put(5.1,1.7){\makebox(0,0)[l]{Endlosschleife: Ab jetzt werden nur noch Callbacks aufgerufen.}}
          \end{picture}
        \item
          In \gitfile{hp}{script}{cube-2.c} kommt eine Drehung um \lstinline{-30} Grad
          um eine schräge Achse \lstinline{(0.5, 1.0, 0.0)} hinzu.
          Der Würfel ist jetzt als solcher zu erkennen.
    
          Jeder Aufruf von \lstinline{glRotatef()} bewirkt,
          daß alle nachfolgenden Zeichenoperationen gedreht ausgeführt werden.
    
        \item
          In \gitfile{hp}{script}{cube-3.c} kommt als zusätzliches Konzept eine weitere Callback-Funktion hinzu,
          nämlich ein \newterm{Timer-Handler}.
          Durch den \lstinline{glutTimerFunc()}-Aufruf veranlassen wir OpenGL,
          die von uns geschriebene Funktion \lstinline{timer_handler()} aufzurufen,
          sobald \lstinline{50} Millisekunden vergangen sind.
    
          Innerhalb von \lstinline{timer_handler()} rufen wir \lstinline{glutTimerFunc()} erneut auf,
          was insgesamt zur Folge hat, daß \lstinline{timer_handler()} periodisch alle 50 Millisekunden
          aufgerufen wird.
    
          Die "`Nutzlast"' der Funktion \lstinline{timer_handler()} besteht darin,
          eine Variable \lstinline{t} um den Wert \lstinline{0.05} zu erhöhen
          und anschließend mittels \lstinline{glutPostRedisplay()} ein Neuzeichnen anzufordern.
          Dies alles bewirkt, daß die Variable \lstinline{t} die aktuelle Zeit seit Programmbeginn
          in Sekunden enthält und daß \lstinline{draw()} zwanzigmal pro Sekunde aufgerufen wird.
    
    %    \item
    %      Weil das Bild während des Neuzeichnens die ganze Zeit zu sehen ist,
    %      flackert in \gitfile{hp}{script}{cube-3.c} der Bildschirm.
    %      Dies wird in \gitfile{hp}{script}{cube-3a.c} dadurch behoben,
    %      daß die Zeichnung zunächst in einem unsichtbaren Pufferspeicher aufgebaut wird.
    %      Erst die fertige Zeichnung wird mit dem Funktionsaufruf \lstinline{swapBuffers()} sichtbar gemacht.
    %
    %      Damit dies möglich ist, muß beim Initialisieren ein doppelter Puffer angefordert werden.
    %      Zu diesem Zweck ersetzen wir die Bibliothek \gitfile{hp}{script}{opengl-magic.c}
    %      durch \gitfile{hp}{script}{opengl-magic-double.c}.
    %
    %      Der Compiler-Aufruf lautet dann:
    %      \begin{lstlisting}[style=terminal,gobble=8]
    %        $ ¡gcc -Wall -O cube.c -lGL -lGLU -lglut opengl-magic-double.c -o cube¿
    %      \end{lstlisting}
    %
    %      Unabhängig davon heißt die Include-Datei weiterhin \gitfile{hp}{script}{opengl-magic.h}.
    %      Dies illustriert, daß der Include-Mechanismus des Präprozessors
    %      und der Zusammenbau-Mecha"-nismus des Linkers tatsächlich voneinander unabhängig sind.
    %
    %      \begin{experts}
    %        (Durch das Austauschen von Bibliotheken, insbesondere bei dynamischen Bibliotheken
    %        (Endung \file{.so} unter Unix bzw.\ \file{.dll} unter Microsoft Windows)
    %        ist es möglich, das Verhalten bereits fertiger Programme zu beeinflussen,
    %        ohne das Programm neu compilieren zu müssen.
    %        Dies kann zu Testzwecken geschehen, zur Erweiterung des Funktionsumfangs
    %        oder auch zum Einschleusen von Schadfunktionen.)
    %      \end{experts}
    
        \item
          In \gitfile{hp}{script}{cube-3.c} dreht sich der Würfel zunächst langsam, dann immer schneller.
          Dies liegt daran, daß sich jedes \lstinline{glRotatef()}
          auf alle nachfolgenden Zeichenbefehle auswirkt,
          so daß sich sämtliche \lstinline{glRotatef()} aufaddieren.
    
          Eine Möglichkeit, stattdessen eine gleichmäßige Drehung zu erreichen,
          besteht darin, den Wirkungsbereich des \lstinline{glRotatef()} zu begrenzen.
          Dies geschieht durch Einschließen der Rotation in das Befehlspaar \lstinline{glPushMatrix()}
          und \lstinline{glPopMatrix()}:
          Durch \lstinline{glPopMatrix()} wird das System wieder in denjenigen Zustand versetzt,
          in dem es sich vor dem Aufruf von \lstinline{glPushMatrix()} befand.
    
          Dies ist in \gitfile{hp}{script}{cube-4.c} (langsame Drehung) und \gitfile{hp}{script}{cube-5.c} (schnelle Drehung) umgesetzt.
    
      \end{itemize}
    
      \subsubsection*{Aufgabe}
    
      Für welche elementaren geometrischen Körper
      stellt die GLUT-Bibliothek Zeichenroutinen zur Verfügung?
    
      \subsubsection*{Lösung}
    
      Ein Blick in die Include-Datei \file{glut.h}
      verweist uns auf eine andere Include-Datei:
      \begin{lstlisting}
        #include "freeglut_std.h"
      \end{lstlisting}
      Wenn wir darin nach dem Wort \lstinline{glutSolidCube} suchen,
      finden wir die Funktionen:
      \begin{lstlisting}
        glutSolidCube (GLdouble size);
        glutSolidSphere (GLdouble radius, GLint slices, GLint stacks);
        glutSolidCone (GLdouble base, GLdouble height, GLint slices, GLint stacks);
        glutSolidTorus (GLdouble innerRadius, GLdouble outerRadius, GLint sides, GLint rings);
        glutSolidDodecahedron (void);
        glutSolidOctahedron (void);
        glutSolidTetrahedron (void);
        glutSolidIcosahedron (void);
        glutSolidTeapot (GLdouble size);
      \end{lstlisting}
      Zu jeder \lstinline{glutSolid}-Funktion gibt es auch eine \lstinline{glutWire}-Funktion,
      beispielsweise \lstinline{glutWireCube()} als Gegenstück zu \lstinline{glutSolidCube()}.
    
      In demselben Verzeichnis finden wir auch eine Datei \file{freeglut\_ext.h}
      mit weiteren Funktionen dieses Typs:
      \begin{lstlisting}
        glutSolidRhombicDodecahedron (void);
        glutSolidSierpinskiSponge (int num_levels, GLdouble offset[3], GLdouble scale);
        glutSolidCylinder (GLdouble radius, GLdouble height, GLint slices, GLint stacks);
      \end{lstlisting}
    
      Die GLUT-Bibliothek kennt insbesondere standardmäßig eine Funktion zum Zeichnen einer Teekanne
      und als Erweiterung eine Funktion zum Zeichnen eines Sierpinski-Schwamms.
    
      \breath
    
      Die weiteren OpenGL-Beispielprogramme illustrieren den Umgang mit Transformationen.
      \begin{itemize}
        \item
          Die Beispielprogramme \gitfile{hp}{script}{cube-5.c} und \gitfile{hp}{script}{cube-6.c}
          illustrieren eine weitere Transformation der gezeichneten Objekte,
          nämlich die Translation (Verschiebung).
    
          Jeder Transformationsbefehl wirkt sich jeweils
          auf die \emph{danach\/} erfolgenden Zeichenbefehle aus.
          Um sich zu veranschaulichen, welche Transformationen auf ein gezeichnetes Objekt wirken
          (hier z.\,B.\ auf \lstinline{glutSolidCube()}),
          muß man die Transformationen in der Reihenfolge \emph{von unten nach oben\/} ausführen.
    
        \item
          Das Beispielprogramm \gitfile{hp}{script}{orbit-1.c} 
          verwendet weitere Transformationen und geometrische Objekte,
          um die Umlaufbahn des Mondes um die Erde zu illustrieren.
    
          Darüberhinaus versieht es die gezeichneten Objekte "`Mond"' und "`Erde"' mit realistischen Texturen (NASA-Fotos).
          Die hierfür notwendigen doch eher komplizierten Funktionsaufrufe
          wurden wiederum in eine Bibliothek (\file{textured-spheres}) ausgelagert.
          
      \end{itemize}
    
    \iffalse
    
      \subsection{Standard-Pfade}
    
      Wenn eine Bibliothek regelmäßig von vielen Programmierern benutzt
      wird, wird sie üblicherweise an einem Standard-Ort abgelegt, z.\,B.\ in
      dem Verzeichnis \file{/usr/lib}.
    
      \lstinline[style=cmd]{gcc} erwartet, daß die Namen von Bibliotheksdateien mit \file{lib}
      beginnen und die Endung \file{.a} oder \file{.so} haben. (\file{.a} steht für
      "`Archiv"', da eine \file{.a}-Datei mehrere \file{.o}-Dateien enthält.
      \file{.so} steht für "`shared object"' und bezeichnet eine Bibliothek, die
      erst zur Laufzeit eingebunden wird und von mehreren Programmen
      gleichzeitig benutzt werden kann. Andere übliche Bezeichnungen
      sind \file{.lib} anstelle von \file{.a} und \file{.dll} anstelle von \file{.so}.)
    
      Mit der Option \lstinline[style=cmd]{-lfoo} teilen wir \lstinline[style=cmd]{gcc} mit, daß wir eine Datei
      \file{libfoo.a} aus einem der Standardverzeichnisse verwenden möchten.
      ("`foo"' ist eine metasyntaktische Variable und steht für ein
      beliebiges Wort.) Auch der Aufruf \lstinline[style=cmd]{-lm} zum Einbinden der
      Mathematik-Bibliothek ist nichts anderes. Tatsächlich gibt es
      eine Datei \file{libm.a} im Verzeichnis \file{/usr/lib}.
      \begin{verbatim}
        gcc test.c -lm -o test\end{verbatim}
      ist somit dasselbe wie
      \begin{verbatim}
        gcc test.c /usr/lib/libm.a -o test\end{verbatim}
    
      Mit der Option \lstinline[style=cmd]{-L /foo/bar} können wir ein Verzeichnis \file{/foo/bar}
      dem Suchpfad hinzufügen. ("`bar"' ist eine weitere metasyntaktische
      Variable.)
      \begin{verbatim}
        gcc test.c -L /home/joe/my_libs -lmy -o test\end{verbatim}
      compiliert \file{test.c} und linkt es mit einer Bibliothek \file{libmy.a},
      nach der nicht nur in den Standardverzeichnissen (\file{/usr/lib},
      \file{/usr/local/lib} u.\,a.), sondern zusätzlich im Verzeichnis
      \file{/home/joe/my\_libs} gesucht wird.
    
      Auf gleiche Weise kann man mit \lstinline[style=cmd]{-I /foo/bar} Verzeichnisse für
      Include-Dateien (s.\,o.)\ dem Standardsuchpfad hinzufügen.
    
    \fi
    
      \subsection{Projekt organisieren: make}
    
      In größeren Projekten ruft man den Compiler (und Präprozessor und
      Linker) nicht "`von Hand"' auf, sondern überläßt dies einem weiteren
      Programm namens \lstinline[style=cmd]{make}.
    
      \lstinline[style=cmd]{make} sucht im aktuellen Verzeichnis nach einer Datei \file{Makefile}
      (ohne Dateiendung). (Normalerweise gibt es nur ein Makefile pro
      Verzeichnis. Falls es doch mehrere gibt, kann man die Datei, z.\,B.\
      \file{Makefile.1}, mit \lstinline[style=cmd]{-f}
      auch explizit angeben: \lstinline[style=cmd]{make -f Makefile.1}.)
    
      \subsubsection{make-Regeln}
    
      Ein Makefile enthält sog.\ Regeln, um Ziele zu erzeugen.
      Eine Regel beginnt mit der Angabe des Ziels, gefolgt von einem
      Doppelpunkt und den Dateien (oder anderen Zielen), von denen es
      abhängt. Darunter steht, mit einem Tabulator-Zeichen eingerückt, der
      Programmaufruf, der nötig ist, um das Ziel zu bauen.
      \begin{lstlisting}[language=make]
        philosophy.o: philosophy.c answer.h
                gcc -c philosophy.c -o philosophy.o
      \end{lstlisting}
      Achtung: Ein Tabulator-Zeichen läßt sich optisch häufig nicht von
      mehreren Leerzeichen unterscheiden. \lstinline[style=cmd]{make}
      akzeptiert jedoch nur das Tabulator-Zeichen.
    
      Die o.\,a.\ Regel bedeutet, daß jedesmal, wenn sich \gitfile{hp}{script}{philosophy.c} oder
      \gitfile{hp}{script}{answer.h} geändert hat, \lstinline[style=cmd]{make}
      das Programm \lstinline[style=cmd]{gcc} in der beschriebenen Weise aufrufen soll.
    
      Durch die Kombination mehrerer Regeln lernt \lstinline[style=cmd]{make},
      welche Befehle in welcher Reihenfolge aufgerufen werden müssen,
      je nachdem, welche Dateien geändert wurden.
    
      \breath
    
      Beispiel: \file{Makefile.orbit-x1}
    
      Der Aufruf
      \begin{lstlisting}[style=terminal]
        $ ¡make -f Makefile.orbit-x1¿
      \end{lstlisting}
      bewirkt beim ersten Mal:
      \begin{lstlisting}[style=terminal]
        gcc -Wall -O orbit-x1.c opengl-magic-double.c textured-spheres.c \
                  -lGL -lGLU -lglut -o orbit-x1
      \end{lstlisting}
      Beim zweiten Aufruf stellt \lstinline[style=cmd]{make} fest, daß sich keine der Dateien
      auf der rechten Seite der Regeln (rechts vom Doppelpunkt) geändert
      hat und ruft keine Programme auf:
      \begin{lstlisting}[style=terminal]
        make: »orbit-x1« ist bereits aktualisiert.
      \end{lstlisting}
    
      \subsubsection{make-Macros}
    
      Um wiederkehrende Dinge (typischerweise: Listen von Dateinamen oder
      Compiler-Optionen) nicht mehrfach eingeben zu müssen, kennt \lstinline[style=cmd]{make}
      sog.\ Macros:
      \begin{lstlisting}[language=make]
        PHILOSOPHY_SOURCES = philosophy.c answer.h
      \end{lstlisting}
      Um den Macro zu expandieren, setzt man ihn in runde Klammern mit
      einem vorangestellten Dollarzeichen. Die Regel
      \begin{lstlisting}[language=make]
        philosophy.o: $(PHILOSOPHY_SOURCES)
                gcc -c philosophy.c -o philosophy.o
      \end{lstlisting}
      ist also nur eine andere Schreibweise für:
      \begin{lstlisting}[language=make]
        philosophy.o: philosophy.c answer.h
                gcc -c philosophy.c -o philosophy.o
      \end{lstlisting}
    
      \breath
    
      Beispiel: \file{Makefile.blink}
    
      Die Beispielprogramme \file{blink-\lstinline{*}.c} sind dafür gedacht,
      auf einem Mikrocontroller zu laufen.
      Der Compiler-Aufruf erfordert zusätzliche Optionen
      (z.\,B.\ \lstinline[style=cmd]{-Os -mmcu=atmega32}),
      und es müssen zusätzliche Entwicklungswerkzeuge
      (z.\,B.\ \lstinline[style=cmd]{avr-objcopy}) aufgerufen werden --
      ebenfalls mit den richtigen Optionen.
      Der Prozeß des Zusammenbauens wird durch ein Makefile \file{Makefile.blink} verwaltet.
    
      \file{Makefile.blink} speichert den Namen des Quelltextes
      (ohne die Endung \file{.c}) in einem Macro.
      Durch Ändern allein dieses Macros ist es daher möglich,
      das Makefile für ein anderes Projekt einzusetzen.
      
      Zusätzlich führt \file{Makefile.blink} eine neue Regel \lstinline{clean} ein.
      Diese bewirkt üblicherweise, daß alle automatisch erzeugten Dateien
      gelöscht werden:
      \begin{lstlisting}[language=make]
        clean:
                rm -f $(TARGET).elf $(TARGET).hex
      \end{lstlisting}
      Rechts vom Doppelpunkt nach \lstinline[language=make]{clean} befinden sich keine
      Abhängigkeitsdateien. Dies hat zur Folge, daß die Aktion
      (\lstinline{rm -f ...}) bei \lstinline[style=cmd]{make clean}
      grundsätzlich immer ausgeführt wird, also nicht nur, wenn sich irgendeine Datei geändert hat.
    
      \begin{experts}
        Ebenfalls üblich ist eine weitere Regel \lstinline[language=make]{install},
        die bewirkt, daß die Zieldateien
        (bei einem Programm typischerweise eine ausführbare Datei,
        bei einer Bibliothek typischerweise \file{.a}-, \file{.so}- sowie \file{.h}-Dateien)
        an ihren endgültigen Bestimmungsort kopiert werden.
      \end{experts}
    
      \subsubsection{Fazit: 3 Sprachen}
    
      Um in C programmieren zu können, muß man also tatsächlich drei
      Sprachen lernen:
      \begin{itemize}
        \item C selbst,
        \item die Präprozessor-Sprache
        \item und die \lstinline[style=cmd]{make}-Sprache.
      \end{itemize}
      Durch Entwicklungsumgebungen wie z.\,B.\ \file{Eclipse} läßt sich der
      \lstinline[style=cmd]{make}-Anteil teilweise automatisieren. (\file{Eclipse} z.\,B.\ schreibt ein
      Makefile; andere Umgebungen übernehmen die Funktionalität von \lstinline[style=cmd]{make}
      selbst.) Auch dort muß man jedoch die zu einem Projekt gehörenden
      Dateien verwalten.
    
      Wenn sich dann eine Datei nicht an dem Ort befindet,
      erhält man u.\,U.\ wenig aussagekräftige Fehlermeldungen, z.\,B.: 
      \begin{lstlisting}[style=terminal]
        make: *** No rule to make target `MeinProgramm.elf', needed by `elf'.  Stop.
      \end{lstlisting}
      Wenn man dann um die Zusammenhänge weiß ("`Welche Bibliotheken verwendet mein
      Programm? Wo befinden sich diese? Und wie erfährt der Linker davon?"'),
      kann man das Problem systematisch angehen und ist nicht auf Herumraten
      angewiesen.
    
      \section{Hardwarenahe Programmierung}
    
      \subsection{Bit-Operationen}
    
      \setlength{\unitlength}{12pt}
    
      \subsubsection{Zahlensysteme}
    
      \subsubsection*{Dezimalsystem}
      \begin{itemize}
        \item
          Basis: 10
        \item
          Gültige Ziffern: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
      \end{itemize}
      \begin{verbatim}
        137                               137
                                        +  42
                                         ----
                                          179
      \end{verbatim}
      \begin{picture}(0,0)(0,-0.25)
        \color{red}
        \put(5.0,4.25){\vector(-1,1){1.41}}
        \put(5.5,4){\mbox{Einer: $7 \cdot 10^0$}}
        \put(5.5,3.25){\vector(-1,1){2.41}}
        \put(6.0,3){\mbox{Zehner: $3 \cdot 10^1$}}
        \put(6.0,2.25){\vector(-1,1){3.41}}
        \put(6.5,2){\mbox{Hunderter: $1 \cdot 10^2$}}
        \put(2.5,0.5){\mbox{$137_{10} = 1 \cdot 10^2 + 3 \cdot 10^1 + 7 \cdot 10^0
                                      = 100 + 30 + 7 = 137$}}
      \end{picture}
    
      \goodbreak
      \subsubsection*{Hexadezimalsystem}
      \begin{itemize}
        \item
          Basis: 16
        \item
          Gültige Ziffern: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
      \end{itemize}
      \begin{verbatim}
        137                               A380
                                        + B747
                                         -----
                                         15AC7
      \end{verbatim}
      \begin{picture}(0,0)(-0,-0.25)
        \put(18.6,4.2){\mbox{\scriptsize\texttt{1}}}
        \color{red}
        \put(5.0,4.25){\vector(-1,1){1.41}}
        \put(5.5,4){\mbox{$7 \cdot 16^0$}}
        \put(5.5,3.25){\vector(-1,1){2.41}}
        \put(6.0,3){\mbox{$3 \cdot 16^1$}}
        \put(6.0,2.25){\vector(-1,1){3.41}}
        \put(6.5,2){\mbox{$1 \cdot 16^2$}}
        \put(2.5,0.5){\mbox{$137_{16} = 1 \cdot 16^2 + 3 \cdot 16^1 + 7 \cdot 16^0
                                      = 256 + 48 + 7 = 311$}}
      \end{picture}
      \begin{itemize}
        \item
          Schreibweise in C: \quad \texttt{0x137}
      \end{itemize}
    
      \goodbreak
      \subsubsection*{Oktalsystem}
      \begin{itemize}
        \item
          Basis: 8
        \item
          Gültige Ziffern: 0, 1, 2, 3, 4, 5, 6, 7
      \end{itemize}
      \begin{verbatim}
        137                               137
                                        +  42
                                         ----
                                          201
      \end{verbatim}
      \begin{picture}(0,0)(0,-0.25)
        \put(19.6,3.7){\mbox{\scriptsize\texttt{1}}}
        \put(19.1,3.7){\mbox{\scriptsize\texttt{1}}}
        \color{red}
        \put(5.0,4.25){\vector(-1,1){1.41}}
        \put(5.5,4){\mbox{$7 \cdot 8^0$}}
        \put(5.5,3.25){\vector(-1,1){2.41}}
        \put(6.0,3){\mbox{$3 \cdot 8^1$}}
        \put(6.0,2.25){\vector(-1,1){3.41}}
        \put(6.5,2){\mbox{$1 \cdot 8^2$}}
        \put(2.5,0.5){\mbox{$137_8 = 1 \cdot 8^2 + 3 \cdot 8^1 + 7 \cdot 8^0
                                   = 64 + 24 + 7 = 95$}}
        \put(2.5,-0.6){\mbox{$42_8 = 4 \cdot 8^1 + 2 \cdot 8^0
                                   = 32 + 2 = 34$}}
        \put(2.5,-1.7){\mbox{$201_8 = 2 \cdot 8^2 + 0 \cdot 8^1 + 1 \cdot 8^0
                                   = 128 + 1 = 129$}}
      \end{picture}
      \vspace{0.75cm}
      \begin{itemize}
        \item
          Schreibweise in C: \quad \texttt{0137}
      \end{itemize}
    
      \subsubsection*{Rechner für beliebige Zahlensysteme: GNU bc}
      \begin{lstlisting}[style=terminal]
        $ ¡bc
        ibase=8
        137¿
        95
        ¡obase=10
        137 + 42¿
        201
      \end{lstlisting}
      \begin{picture}(0,0)(0.5,1.2)
        \color{red}
        \put(8.0,7.25){\vector(-1,0){3}}
        \put(8.5,7){\mbox{Eingabe zur Basis 8}}
        \put(8.0,6.25){\vector(-1,0){4}}
        \put(8.5,6){\mbox{Ausgabe zur Basis 10}}
        \put(9.0,5.25){\vector(-1,0){2}}
        \put(9.5,5){\mbox{Eingabe zur Basis 8 ($10_8 = 8$)}}
        \put(8.0,3.25){\vector(-1,0){4}}
        \put(8.5,3){\mbox{Ausgabe zur Basis 8}}
      \end{picture}\vspace{-2ex}
    
      \goodbreak
      \subsubsection*{Binärsystem}
      \begin{itemize}
        \item
          Basis: 2
        \item
          Gültige Ziffern: 0, 1
      \end{itemize}
      \begin{verbatim}
        110                                110
                                        + 1100
                                         -----
                                         10010
      \end{verbatim}
      \begin{picture}(0,0)(0,-0.25)
        \put(19.1,3.8){\mbox{\scriptsize\texttt{1}}}
        \put(18.6,3.8){\mbox{\scriptsize\texttt{1}}}
        \color{red}
        \put(5.0,4.25){\vector(-1,1){1.41}}
        \put(5.5,4){\mbox{$0 \cdot 2^0$}}
        \put(5.5,3.25){\vector(-1,1){2.41}}
        \put(6.0,3){\mbox{$1 \cdot 2^1$}}
        \put(6.0,2.25){\vector(-1,1){3.41}}
        \put(6.5,2){\mbox{$1 \cdot 2^2$}}
        \put(2.5,0.5){\mbox{$110_2 = 1 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0
                                      = 4 + 2 + 0 = 6$}}
      \end{picture}
      \begin{itemize}
        \item
          Binär-Zahlen ermöglichen es, elektronisch zu rechnen \dots
        \item
          und mehrere "`Ja/Nein"' (Bits) zu einer einzigen Zahl zusammenzufassen.
        \goodbreak
        \item
          \textbf{Oktal- und Hexadezimal-Zahlen lassen sich ziffernweise
          in Binär-Zahlen umrechnen:}
      \end{itemize}
      \vspace*{-6mm}
      \begin{verbatim}
         000 0        0000 0  1000 8
         001 1        0001 1  1001 9
         010 2        0010 2  1010 A
         011 3        0011 3  1011 B
         100 4        0100 4  1100 C
         101 5        0101 5  1101 D
         110 6        0110 6  1110 E
         111 7        0111 7  1111 F
      \end{verbatim}
      \vspace*{-1cm}
      \begin{itemize}
        \item[]
          Beispiel: $1101011_2 = 153_8 = 6{\rm B}_{16}$
        \item[]
          Anwendungsbeispiel: Oktal-Schreibweise für Unix-Zugriffsrechte\\
          \lstinline[style=terminal]|-rw-r-----| $= 0\,110\,100\,000_2 = 640_8$ \qquad \lstinline[style=terminal]|$ chmod 640 file.c|\\
          \lstinline[style=terminal]|-rwxr-x---| $= 0\,111\,101\,000_2 = 750_8$ \qquad \lstinline[style=terminal]|$ chmod 750 subdir|
      \end{itemize}
    
      \goodbreak
      \subsubsection*{IP-Adressen (IPv4)}
      \begin{itemize}
        \item
          Basis: 256
        \item
          Gültige Ziffern: 0 bis 255, getrennt durch Punkte
        \item
          Kompakte Schreibweise für Binärzahlen mit 32 Ziffern (Bits)
      \end{itemize}
      \begin{verbatim}
        192.168.0.1
    
    
    
    
      \end{verbatim}
      \begin{picture}(0,0)(0,-0.25)
        \color{red}
        \put(8.75,5.25){\vector(-1,1){1.41}}
        \put(9.25,5){\mbox{$1 \cdot 256^0$}}
        \put(8.75,4.25){\vector(-1,1){2.41}}
        \put(9.25,4){\mbox{$0 \cdot 256^1$}}
        \put(8.25,3.25){\vector(-1,1){3.41}}
        \put(8.75,3){\mbox{$168 \cdot 256^2$}}
        \put(7.5,2.25){\vector(-1,1){4.41}}
        \put(8.0,2){\mbox{$192 \cdot 256^3$}}
        \put(2.5,0.5){\mbox{$192.168.0.1_{256} = 11000000\,10101000\,00000000\,00000001_2$}}
      \end{picture}
      \vspace*{-0.5cm}
    
      \goodbreak
      \subsubsection{Bit-Operationen in C}
      \begin{verbatim}
          0110       0110       0110       0110                  0110
        + 1100     | 1100    &  1100    ^  1100    ~  1100   >>     2
         -----      -----      -----      -----      -----      -----
         10010       1110       0100       1010       0011       0001
      \end{verbatim}
      \begin{picture}(0,0)(0,-0.25)
        \color{red}
        \put(2.5,1.0){\mbox{Addition}}
        \put(8.5,1.0){\mbox{Oder}}
        \put(14.0,1.0){\mbox{Und}}
        \put(18.0,1.0){\mbox{Exklusiv-Oder}}
        \put(24.5,1.0){\mbox{Negation}}
        \put(29.0,1.0){\mbox{Bit-Verschiebung}}
      \end{picture}
    
      \begin{verbatim}
          01101100            01101100            01101100
        | 00000010          & 11110111          ^ 00010000
         ---------           ---------           ---------
          01101110            01100100            01111100
      \end{verbatim}
      \begin{picture}(0,0)(0,-0.25)
        \color{red}
        \put(2.5,1.0){\mbox{Bit gezielt setzen}}
        \put(12.5,1.0){\mbox{Bit gezielt löschen}}
        \put(22.5,1.0){\mbox{Bit gezielt umklappen}}
      \end{picture}
      \begin{itemize}
        \item
          Bits werden häufig von rechts und ab 0 numeriert (hier: 0 bis 7),\\
          um die Maskenerzeugung mittels Schiebeoperatoren zu erleichtern.
        \item
          Die Bit-Operatoren (z.\,B.\ \lstinline|&| in C)
          wirken jeweils auf alle Bits der Zahlen.
          \hfill{\color{red}\lstinline|6 & 12 == 4|}\qquad\strut\\
          Die logischen Operatoren (z.\,B.\ \lstinline|&&| in C)
          prüfen die Zahl insgesamt auf $\ne 0$.
          \hfill{\color{red}\lstinline|6 && 12 == 1|}\qquad\strut\\
          Nicht verwechseln!
      \end{itemize}
    
      \bigbreak
      
      Anwendung: Bit 2 (also das dritte Bit von rechts) in einer 8-Bit-Zahl auf 1 setzen:
      \begin{verbatim}
          00000001            01101100
       <<        2          | 00000100
         ---------           ---------
          00000100            01101100
      \end{verbatim}
      \begin{picture}(0,0)(0,-0.25)
        \color{red}
        \put(3.5,1.0){\mbox{Maske für Bit 2}}
        \put(12.5,1.0){\mbox{Bit gezielt setzen}}
      \end{picture}\vspace{-4ex}
      \begin{itemize}
        \item
          Schreibweise in C:\quad
          \lstinline,a |= 1 << 2;,
      \end{itemize}
    
      \bigbreak
      
      Anwendung: Bit 2 in einer 8-Bit-Zahl auf 0 setzen:
      \begin{verbatim}
          00000001                                01101100
       <<        2          ~ 00000100          & 11111011
         ---------           ---------           ---------
          00000100            11111011            01101000
      \end{verbatim}
      \begin{picture}(0,0)(0,-0.25)
        \color{red}
        \put(3.5,1.0){\mbox{Maske zum Löschen von Bit 2 erzeugen}}
        \put(22.5,1.0){\mbox{Bit gezielt löschen}}
      \end{picture}\vspace{-4ex}
      \begin{itemize}
        \item
          Schreibweise in C:\quad
          \lstinline,a &= ~(1 << 2);,
      \end{itemize}
    
      \bigbreak
    
      Anwendung: Bit 2 aus einer 8-Bit-Zahl extrahieren:
      \begin{verbatim}
          00000001            01101100            00000100
       <<        2          & 00000100         >>        2
         ---------           ---------           ---------
          00000100            00000100            00000001
      \end{verbatim}
      \begin{picture}(0,0)(0,-0.25)
        \color{red}
        \put(2.5,1.0){\mbox{Maske für Bit 2}}
        \put(12.5,1.0){\mbox{Bit 2 isolieren}}
        \put(22.5,1.0){\mbox{in Zahl 0 oder 1 umwandeln}}
      \end{picture}\vspace{-4ex}
      \begin{itemize}
        \item
          Schreibweise in C:\quad
          \lstinline,x = (a & (1 << 2)) >> 2;,
      \end{itemize}
    
      \bigbreak
    
      Beispiel: Netzmaske für 256 IP-Adressen
      \begin{verbatim}
          192.168.  1.123
        & 255.255.255.  0
         ----------------
          192.168.  1.  0
      \end{verbatim}
      \begin{picture}(0,0)(0,0)
        \color{red}
        \put(14.0,6.25){\vector(-1,0){2}}
        \put(14.5,6){\mbox{IP-Adresse eines Rechners}}
        \put(14.0,5.25){\vector(-1,0){2}}
        \put(14.5,5){\mbox{Netzmaske: $255 = 11111111_2$}}
        \put(14.0,3.25){\vector(-1,0){2}}
        \put(14.5,3){\mbox{IP-Adresse des Sub-Netzes}}
      \end{picture}\vspace{-6ex}
    
      \bigbreak
    
      Beispiel: Netzmaske für 8 IP-Adressen
      \begin{verbatim}
          192.168.  1.123                                   01111011
        & 255.255.255.248                                 & 11111000
         ----------------                                  ---------
          192.168.  1.120                                   01111000
      \end{verbatim}
      \begin{picture}(0,0)(0,0)
        \color{red}
        \put(14.0,6.25){\vector(-1,0){2}}
        \put(14.5,6){\mbox{IP-Adresse eines Rechners}}
        \put(14.0,5.25){\vector(-1,0){2}}
        \put(14.5,5){\mbox{Netzmaske}}
        \put(14.0,3.25){\vector(-1,0){2}}
        \put(14.5,3){\mbox{IP-Adresse des Sub-Netzes}}
      \end{picture}\vspace{-6ex}
    
      \subsection{Programmierung von Mikrocontrollern}
    
      Ein Mikrocontroller ist ein elektronischer Baustein,
      der einen kompletten Computer mit eingeschränkter Funktionalität enthält.
    
      Mit "`eingeschränkter Funktionalität"' ist gemeint,
      daß auf einem Mikrocontroller kein Universal-Betriebssystem läuft,
      sondern daß darauf nur ein einziges Programm läuft,
      nämlich die Anwendungs-Software.
    
      Wenn ein Baustein einen kompletten Computer enthält,
      der leistungsfähig genug ist,
      daß darauf ein Universal-Betriebssystem laufen kann,
      spricht man normalerweise nicht mehr von einem Mikrocontroller,
      sondern von einem Ein-Chip-Computer.
      Der Übergang ist fließend.
    
      \breath
    
      Da ein Mikrocontroller nicht über die Leistung verfügt,
      einen Compiler laufen zu lassen,
      erfolgt die Entwicklung von Software für Mikrocontroller
      auf einem "`normalen"' Computer.
      Diese Art der Software-Entwicklung,
      bei der ein Computer Software für einen ganz anderen Computer erzeugt,
      bezeichnet man als \newterm{Cross-Entwicklung}.
      Die einzelnen Werkzeuge heißen entsprechend
      \newterm{Cross-Compiler}, \newterm{Cross-Assembler\/} und \newterm{Cross-Linker}.
    
      Beispiel: Erzeugen einer ausführbaren Datei \file{blink.elf}
      aus einem C-Quelltext \file{blink.c}
      für einen Mikrocontroller vom Typ ATmega328P
      \begin{lstlisting}[style=cmd]
        avr-gcc -Wall -Os -mmcu=atmega328p blink.c -o blink.elf
      \end{lstlisting}
    
      Damit der Mikrocontroller die ausführbare Datei ausführen kann,
      muß man sie mit einem speziellen Werkzeug auf den Mikrocontroller
      \newterm{herunterladen}.
      Hierfür ist es oft notwendig, die Datei vorher in ein anderes Dateiformat
      zu konvertieren.
    
      Beispiel: Konvertierung der ausführbaren Datei \file{blink.elf}
      aus dem ELF-Dateiformat in das Intel-HEX-Format:
      \begin{lstlisting}[style=cmd]
        avr-objcopy -O ihex blink.elf blink.hex
      \end{lstlisting}
    
      Anschließend kann die Datei auf den Mikrocontroller heruntergeladen werden.
      Beispiel: Herunterladen der Datei \file{blink.hex}
      in den Flash-Speicher eines ATmega328P-Mikrocontrollers
      auf einem Mikrocontroller-Board vom Typ Arduino Uno
      über die Schnittstelle \file{/dev/ttyACM0}
      \begin{lstlisting}[style=cmd]
        avrdude -P /dev/ttyACM0 -c arduino -p m328p -U flash:w:blink.hex
      \end{lstlisting}
    
      \subsection{I/O-Ports}
    
      Es gibt drei grundlegende Mechanismen für die Kommunikation zwischen dem Prozessor
      und einem externen Gerät:
      \begin{itemize}
        \item
          Über Output-Ports kann der Prozessor das Gerät aktiv steuern,
        \item
          über Input-Ports kann er es aktiv abfragen,
        \item
          und über Interrupts kann das externe Gerät im Prozessor Aktivitäten auslösen.
      \end{itemize}
    
      \begin{center}
        \includegraphics{io-ports-and-interrupts.pdf}
      \end{center}
    
      \setlength{\unitlength}{1cm}
    
      Input- und Output-Ports, zusammengefaßt: I/O-Ports,
      sind spezielle Speicherzellen, die mit einem externen Gerät verbunden sind.
      \begin{itemize}
        \item
          Ein in einen Output-Port geschriebener Wert bewirkt eine Spannungsänderung in einer Leitung,
          die zu einem externen Gerät führt.
        \item
          Wenn ein externes Gerät eine Spannung an eine Leitung anlegt, die zu einer Speicherzelle führt,
          kann der Prozessor diese als Input-Port lesen.
      \end{itemize}
    
      Um z.\,B.\ auf einen Druck auf einen Taster zu warten,
      kann ein Program periodisch in einer Schleife einen Input-Port lesen
      und die Schleife erst dann beenden, wenn der Wert für "`Taster gedrückt"' gelesen wurde.
    
      Diese Methode heißt "`Busy Waiting"': Der Prozessor ist vollständig mit Warten beschäftigt.
      Wenn gleichzeitig noch andere Aktionen stattfinden sollen,
      müssen diese in der Schleife mit berücksichtigt werden.
    
      \bigskip
      \goodbreak
    
      Beispiel für die Verwendung eines Output-Ports: Roboter-Steuerung\\
      Datei: RP6Base/RP6Base\_Examples/RP6Examples\_20080915/RP6Lib/RP6base/RP6RobotBaseLib.c\\
      Suchbegriff: setMotorDir
      \goodbreak
      \begin{lstlisting}
        void setMotorDir(uint8_t left_dir, uint8_t right_dir)
        {
                mleft_dir = left_dir;
                mright_dir = right_dir;
                mleft_des_dir = left_dir;
                mright_des_dir = right_dir;
                if(left_dir)
                        PORTC |= DIR_L;
                else
                        PORTC &= ~DIR_L;
                if(right_dir)
                        PORTC |= DIR_R;
                else
                        PORTC &= ~DIR_R;
        }
      \end{lstlisting}
    
      Die Variable \lstinline|PORTC| ist ein Output-Port.
      Durch Manipulation einzelner Bits in dieser Variablen
      ändert sich die Spannung an den elektrischen "`Beinchen"' des Mikrocontrollers.
      Hierdurch wird die Beschaltung von Elektromotoren umgepolt.
    
      (Die Konstanten \lstinline|DIR_L| und \lstinline|DIR_R| sind "`Bitmasken"',
      d.\,h.\ Zahlen, die in ihrer Binärdarstellung nur eine einzige $1$ und ansonsten Nullen haben.
      Durch die Oder- und Und-Nicht-Operationen werden einzelne Bits in \lstinline|PORTC| auf $1$ bzw.\ $0$ gesetzt.)
    
      \bigskip
    
      Die direkte Ansteuerung von I/O-Ports ist nur auf Mikrocontrollern üblich.
      Auf Personal-Computern erfolgt die gesamte Ein- und Ausgabe über Betriebssystem-"`Treiber"'.
      Anwenderprogramme greifen dort i.\,d.\,R.\ nicht direkt auf I/O-Ports zu.
    
      \subsection{Interrupts}
    
      Ein Interrupt ist ein Unterprogramm, das nicht durch einen Befehl (\lstinline|call|),
      sondern durch ein externes Gerät (über ein Stromsignal) aufgerufen wird.
    
      Damit dies funktionieret, muß die Adresse, an der sich das Unterprogramm befindet,
      an einer jederzeit auffindbaren Stelle im Speicher hinterlegt sein.
      Diese Stelle heißt "`Interrupt-Vektor"'.
    
      Da ein Interrupt jederzeit erfolgen kann,
      hat das Hauptprogramm keine Chance, vor dem Aufruf die Registerinhalte zu sichern.
      Für Interrupt-Unterprogramme, sog.\ Interrupt-Handler,
      ist es daher zwingend notwendig, sämtliche Register vor Verwendung zu sichern
      und hinterher zurückzuholen.
    
      \bigskip
    
      Beispiel für die Verwendung eines Interrupts: Roboter-Steuerung\\
      Datei: RP6Base/RP6Base\_Examples/RP6Examples\_20080915/RP6Lib/RP6base/RP6RobotBaseLib.c\\
      Suchbegriff: ISR
      \begin{lstlisting}
        ISR (INT0_vect)
        {
                mleft_dist++;
                mleft_counter++;
                /* ... */
        }
      \end{lstlisting}
      \begin{itemize}
        \item
          Durch das Schlüsselwort \lstinline|ISR| anstelle von z.\,B.\ \lstinline|void|
          teilen wir dem Compiler mit, daß es sich um einen Interrupt-Handler handelt,
          so daß er entsprechenden Code zum Sichern der Registerinhalte einfügt.
        \item
          Durch die Namensgebung \lstinline|INT0_vect| teilen wir dem Compiler mit,
          daß er den Interrupt-Vektor Nr.\ 0 (also den ersten)
          auf diesen Interrupt-Handler zeigen lassen soll.
      \end{itemize}
      (Tatsächlich handelt es sich bei \lstinline|ISR| und \lstinline|INT0_vect| um Macros.)
    
      Die Schreibweise ist spezifisch für die Programmierung des Atmel AVR ATmega
      unter Verwendung der GNU Compiler Collection (GCC).
      Bei Verwendung anderer Werkzeuge und/oder Prozessoren
      kann dasselbe Programm völlig anders aussehen.
      Wie man Interrupt-Handler schreibt und wie man Interrupt-Vektoren setzt,
      ist ein wichtiger Bestandteil der Dokumentation der Entwicklungswerkzeuge.
    
      \bigskip
    
      Die so geschriebene Funktion wird immer dann aufgerufen, wenn die
      Hardware den Interrupt Nr.\ 0 auslöst. Wann das der Fall ist, hängt
      von der Beschaltung ab. Im Falle des RP6 geschieht es dann, wenn
      ein Sensor an der linken Raupenkette einen schwarzen Streifen auf
      der Encoder-Scheibe registriert, also immer dann, wenn sich die
      linke Raupenkette des Roboters um eine bestimmte Strecke gedreht
      hat.
    
      Jedesmal wenn sich die Raupenkette um einen Teilstrich weitergedreht hat,
      werden also zwei Zähler inkrementiert.
      Wir können dies nutzen, um z.\,B.\ durch Auslesen des Zählers \lstinline|mleft_dist|
      die zurückgelegte Entfernung zu messen.
      (Die RP6-Bibliothek selbst stellt nur eine Zeit- und eine Geschwindigkeitsmessung zur Verfügung.)
      Wie dies konkret geschehen kann, sei im folgenden vorgestellt.
    
      \goodbreak
    
      Methode 1: Verändern des Interrupt-Handlers
      \begin{itemize}
        \item
          Da die Bibliothek \lstinline|RP6RobotBase| im Quelltext vorhanden ist,
          können wir sie selbst ändern und in den Interrupt-Handler
          \lstinline|ISR (INT0_vect)| einen eigenen Zähler für Sensor-Ticks einbauen.
        \item
          Wenn wir diesen zum Zeitpunkt A auf 0 setzen und zum Zeitpunkt B
          auslesen, erfahren wir, wieviele "`Ticks"' der Roboter dazwischen
          zurückgelegt hat.
      \end{itemize}
    
      Methode 2: Verwenden eines vorhandenen Zählers
      \begin{itemize}
        \item
          Tatsächlich enthält \lstinline|ISR (INT0_vect)| bereits zwei Zähler, die
          bei jedem Sensor-"`Tick"' hochgezählt werden: \lstinline|mleft_dist| und
          \lstinline|mleft_counter|.
        \item
          Einer davon (\lstinline|mleft_dist|) wird bei jedem \lstinline|move()| auf 0
          zurückgesetzt. Für diesen Zähler enthält \lstinline|RP6RobotBaseLib.h|
          einen "`undokumentierten"' Makro \lstinline|getLeftDistance()|, um ihn
          auszulesen.
        \item
          Bei sorgfältiger Lektüre von \lstinline|RP6RobotBaseLib.c| erkennt man, daß
          es unproblematisch ist, den Zähler vom Hauptprogramm aus auf 0 zu
          setzen. (Dies ist jedoch mit Vorsicht zu genießen: In einer
          eventuellen Nachfolgeversion der Bibliothek muß dies nicht mehr
          der Fall sein!)
      \end{itemize}
    
      Methode 3: Abfrage der Sensoren mittels Busy Waiting
      \begin{itemize}
        \item
          Alternativ zur Verwendung des Interrupt-Handlers kann man auch
          von der eigenen Hauptschleife aus den Sensor periodisch abfragen
          und bei jeder Änderung einen Zähler hochzählen. 
        \item
          Diese Methode heißt "`Busy Waiting"'. Sie hat den Vorteil der
          Einfachheit aber den Nachteil, daß der Prozessor "`in Vollzeit"'
          damit beschäftigt ist, einen Sensor abzufragen, und eventuelle
          andere Aufgaben nur noch "`nebenher"' erledigen kann. 
        \item
          Wenn aus irgendwelchen Gründen der Interrupt-Mechanismus nicht
          verwendet werden kann (z.B. weil der Prozessor über kein
          Interrupt-Konzept verfügt), könnten wir die Lichtschranke alternativ auch mit einem Input-Port
          verdrahten und mittels Busy Waiting abfragen.
    
          Dies funktioniert nur dann, wenn die Schleife wirklich regelmäßig den Sensor abfragt.
          Sobald der Prozessor längere Zeit mit anderen Dingen beschäftigt ist,
          können beim Busy Waiting Signale der Lichtschranke verlorengehen.
          Dieses Problem besteht nicht bei Verwendung von Interrupts.
      \end{itemize}
    
      \subsection{volatile-Variable}
    
      Im C-Quelltext fällt auf, daß die Zähler-Variablen \lstinline|mleft_dist| und \lstinline|mleft_counter|\\
      als \lstinline|volatile uint16_t mleft_counter| bzw.\ \lstinline|volatile uint16_t mleft_dist| deklariert sind\\
      anstatt einfach nur als \lstinline|uint16_t mleft_counter| und \lstinline|uint16_t mleft_dist|.
    
      Das Schlüsselwort \lstinline|volatile| teilt dem C-Compiler mit,
      daß eine Variable immer im Speicher (RAM) aufbewahrt werden muß
      und nicht in einem Prozessorregister zwischengespeichert werden darf.
    
      Dies ist deswegen wichtig, weil jederzeit ein Interrupt erfolgen
      kann, der den Wert der Variablen im Speicher verändert. Wenn im
      Hauptprogramm alle "`überflüssigen"' Speicherzugriffe wegoptimiert
      wurden, erfährt es nichts von der Änderung.
    
      Entsprechendes gilt für I/O-Ports:
      Wenn ein Programm einen Wert in einen Output-Port schreiben oder aus einem Input-Port lesen soll,
      ist es wichtig, daß der Speicherzugriff auch tatsächlich stattfindet.
    
    \iffalse
    
      \subsection{Software-Interrupts}
     
      Manche Prozessoren verfügen über einen Befehl, um Interrupts "`künstlich"' auszulösen.
    
      Das Betriebssystem MS-DOS verwendet derartige Aufrufe
      anstelle von "`normalen"' Unterprogrammaufrufen,
      um Programmen Funktionen zur Verfügung zu stellen.
    
      \bigskip
      \goodbreak
    
      Beispiel: Assembler-Version von \lstinline| printf ("Hello, world!\n") | unter MS-DOS bzw.\ Unix
    
      \medskip
    
      \lstinline|  |MS-DOS-Version für FASM (gekürzt)\hspace{3cm} Unix-Version für GCC (gekürzt)
      \begin{verbatim}
      hello  db 'Hello, world', 10, 13, '$'     hello:
                                                        .string "Hello, world!\n"
      mov ah, 09h
      mov dx, hello                                     pushl   $hello
      int 21h                                           call    printf\end{verbatim}
    
      \begin{itemize}
        \item
          Die MS-DOS-Version ruft den Interrupt Nr.\ 33 (hexadezimal: 21) auf: \lstinline| int 21h|.\\
          Die Unix-Version verwendet stattdessen einen normalen Unterprogrammaufruf: \lstinline| call printf|.
        \item
          Die MS-DOS-Version übergibt Parameter in Prozessorregistern:\\
          Die Konstante \lstinline|09h| im \lstinline|ah|-Register wählt die Funktion "`Textausgabe"' aus;\\
          das \lstinline|dx|-Register enthält einen Zeiger auf den Text.
    
          Die Unix-Version benutzt den Stack zur Übergabe des Parameters: \lstinline| pushl $hello|.\\
          (\lstinline|$hello| ist ein Zeiger auf den Text.)
        \item
          Obwohl beide Programme auf demselben Prozessor laufen,
          unterscheiden sich die Sprachdialekte der beiden Assember FASM und GCC erheblich voneinander.\\
          (Reihenfolge der Operanden umgekehrt, Suffix \lstinline|l| für "`long"', Präfix \lstinline|$| für Konstanten, \dots)
      \end{itemize}
    
      Derartige "`Software-Interrupts"' verursachen Probleme,
      sobald ein Gerät den Interrupt für seinen eigentlichen Zweck verwendet.
      MS-Windows verwendet -- außer zur Emulation von MS-DOS -- keine Software-Interrupts mehr.
    
      \bigskip
    
      (Ein sehr ähnlicher Mechanismus wird von modernen Betriebssystemen weiterhin für Systemaufrufe genutzt.
      Hier geht es darum, den Übergang von potentiell unsicherem Code in Anwenderprogrammen
      zum vertrauenswürdigen Code des Betriebssystems zu kontrollieren. Für Details siehe:\\
      \url{http://de.wikipedia.org/wiki/Software-Interrupt}, \url{http://de.wikipedia.org/wiki/Systemaufruf})
    
    \fi
    
      \subsection{Byte-Reihenfolge -- Endianness}
    
      \subsubsection{Konzept}
    
      Beim Speichern von Werten,
      die größer sind als die kleinste adressierbare Einheit\\
      (= Speicherzelle oder Speicherwort, häufig 1 Byte), werden mehrere Speicherworte belegt.
    
      Beispiel: 16-Bit-Zahl in 2 8-Bit-Speicherzellen
      \begin{displaymath}
        1027 = 1024 + 2 + 1 = 0000\,0100\,0000\,0011_2 = 0403_{16}
      \end{displaymath}
    
      Diese 16-Bit-Zahl kann auf zwei verschiedene Weisen
      in zwei 8-Bit-Speicherzellen gespeichert werden:
      \begin{center}
        \begin{tabular}{|c|c|l}\cline{1-2}
          \raisebox{-1pt}{04} & \raisebox{-1pt}{03} & \strut \newterm{Big-Endian}, "`großes Ende zuerst"', \\\cline{1-2}
          \multicolumn{2}{c}{} & für Menschen leichter lesbar \\
          \multicolumn{3}{c}{} \\[-5pt]\cline{1-2}
          \raisebox{-1pt}{03} & \raisebox{-1pt}{04} & \strut \newterm{Little-Endian}, "`kleines Ende zuerst"', \\\cline{1-2}
          \multicolumn{2}{c}{} & bei Additionen effizienter \\
          \multicolumn{2}{c}{} & (Schriftliches Addieren beginnt immer beim Einer.)
        \end{tabular}
      \end{center}
      Welche Konvention man verwendet, ist letztlich Geschmackssache
      und hängt von der verwendeten Hardware (Prozessor) und Software ab.
      Man spricht hier von der \newterm{Endianness\/} (Byte-Reihenfolge) der Hardware bzw.\ der Software.
    
      Im Kontext des Datenaustausches ist es wichtig,
      sich auf eine einheitliche Endianness zu verständigen.
      Dies gilt insbesondere für:
      \begin{itemize}
        \item
          Dateiformate
        \item
          Datenübertragung
      \end{itemize}
    
      \goodbreak
      \subsubsection{Dateiformate}
    
      Als Beispiel für Dateiformate, in denen die Reihenfolge der Bytes
      in 16- und 32-Bit-Zahlen spezifiziert ist, seien hier Audio-Formate genannt:
      \begin{itemize}
        \item
          RIFF-WAVE-Dateien (\file{.wav}): Little-Endian
        \item
          Au-Dateien (\file{.au}): Big-Endian
        \goodbreak
        \item
          ältere AIFF-Dateien (\file{.aiff}): Big-Endian
        \item
          neuere AIFF-Dateien (\file{.aiff}): Little-Endian
      \end{itemize}
      Insbesondere ist es bei AIFF-Dateien wichtig, zu prüfen,
      um welche Variante es sich handelt, anstatt sich auf eine bestimmte Byte-Reihenfolge zu verlassen.
    
      Bei Dateiformaten mit variabler Endianness ist es sinnvoll und üblich,
      die Endianness durch eine Kennung anzuzeigen.
      Dies geschieht häufig am Anfang der Datei (im "`Vorspann"' -- "`Header"').
    
      \bigbreak
    
      Als weiteres Beispiel seien zwei Monochrom-Grafik-Formate genannt.
      Hier steht jedes Bit für einen schwarzen bzw.\ weißen Bildpunkt,
      daher spielt die Reihenfolge der Bits in den Bytes eine entscheidende Rolle.
      (Diese Grafik-Formate werden in Übungsaufgaben weiter vertieft.)
      \begin{itemize}
        \item
          PBM-Dateien: Big-Endian, \newterm{MSB first\/} -- die höchstwertige Binärziffer ist im Bild links
        \item
          XBM-Dateien: Little-Endian, \newterm{LSB first\/} -- die höchstwertige Binärziffer ist im Bild rechts
      \end{itemize}
      MSB/LSB = most/least significant bit
    
      Achtung: Die Abkürzungen "`MSB/LSB"' werden manchmal auch für "`most/least significant \emph{byte}"' verwendet.
      Im konkreten Fall ist es ratsam, die verwendete Byte- und Bit-Reihenfolge genau zu recherchieren
      bzw.\ präzise zu dokumentieren.
    
    %  \bigbreak
    %
    %  Weiteres Beispiel: Textdateien im Format "`UTF-16"'.
    %  Hier stehen jeweils zwei aufeinanderfolgende Bytes für eine 16-Bit-Zahl.
    %  Am Dateianfang steht stets der Wert $65279 = \lstinline|FEFF|_{16}$ \dots
    
      \subsubsection{Datenübertragung}
    
      Bei der Übertragung von Daten über Leitungen
      spielt sowohl die Reihenfolge der Bits in den Bytes ("`MSB first"' bzw.\ "`LSB first"')
      als auch die Reihenfolge der Bytes in den übertragenen Zahlen ("`Big-/Little-Endian"') eine Rolle.
    
      Als Beispiele seien genannt:
      \begin{itemize}
        \item
          RS-232 (serielle Schnittstelle): MSB first
        \item
          I$^2$C: LSB first
        \item
          USB: beides
    
          Um Übertragungsfehler erkennen zu können, werden im USB-Protokoll
          bestimmte Werte einmal gemäß der MSB-first- und einmal gemäß der LSB-first-Konvention
          übertragen und anschließend auf Gleichheit geprüft.
        \medskip
        \item
          Ethernet: LSB first
        \item
          TCP/IP (Internet): Big-Endian
      \end{itemize}
      Insbesondere gilt für die Übertragung z.\,B.\ einer 32-Bit-Zahl über das Internet,
      daß die vier Bytes von links nach rechts (Big-Endian) übertragen werden,
      die acht Bits innerhalb jedes Bytes hingegen von rechts nach links (LSB first).
    
      \subsection{Binärdarstellung von Zahlen}
    
      Es gibt unendlich viele verschiedene ganze Zahlen.
      Da Speicherplatz begrenzt ist, können Rechner nur begrenzt viele Zahlen darstellen.
      In der Praxis legt man sich auf eine Anzahl von Bits fest,
      die eine Zahl maximal belegen darf.
      Typischerweise handelt es sich bei dieser Anzahl von Bits
      um eine Zweierpotenz: 8, 16, 32, 64.
    
      Eine 8-Bit-Zahl kann per definitionem Binärzahlen von 0000\,0000 bis 1111\,1111
      darstellen. Dezimal sind dies die Zahlen von 0 bis 255.
      Wenn man die 8-Bit-Zahl 255 inkrementiert (= um 1 erhöht),
      gibt es einen Überlauf, und das Rechenergebnis ist 0:
      Die Binärzahl 1111\,1111 + 1 = 1\,0000\,0000 hat 9 Bits.
      Wenn man das oberste Bit abschneidet, bleibt der Wert 0 übrig.
    
      Auf Computern macht man sich dieses Verhalten
      für die Binärdarstellung negativer Zahlen zunutze:
      Wenn 255 + 1 (dezimal geschrieben, mit 8-Bit-Zahlen berechnet) den Wert 0 ergibt,
      dann ist 255 dasselbe wie $-1$.
    
      Allgemein gilt: Diejenige Zahl $y$, die ich auf eine Zahl $x$ addieren muß,
      um auf einem $n$-Bit-Rechner einen Überlauf und das Rechenergebnis $0$ zu erhalten,
      ist die \emph{$n$-Bit-Binärdarstellung von $-x$\/}).
    
      Um diese Zahl direkt auszurechnen, geht man folgendermaßen vor:
      \begin{enumerate}
        \item
          Man invertiert alle Bits der Zahl.\\
          Aus 0010\,1100 (= Binärdarstellung von 44) wird so zum Beispiel 1101\,0011.
        \item
          Man addiert 1 zu der erhaltenen Zahl:\\
          1101\,0011 + 1 = 1101\,0100 (= 8-Bit-Binärdarstellung von $-44$).
      \end{enumerate}
      Diese Darstellung negativer Zahlen heißt \newterm{Zweierkomplement}.
    
      \goodbreak
    
      Theoretisch kann man jede Zahl bei gegebener Rechengenauigkeit
      sowohl als postive als auch als negative Zahl interpretieren.
      Die folgende Konvention hat sich als sinnvoll heraugestellt:
      \begin{itemize}
        \item
          Entweder betrachtet man alle Zahlen als positiv,
        \item
          oder man betrachtet Zahlen, deren oberstes Bit gesetzt ist, als negativ\\
          und die anderen als positiv.
      \end{itemize}
    
      Für normale Anwendungen ist die genaue Anzahl der Bits einer Ganzzahl-Variablen
      unerheblich, sofern der Wertebereich groß genug für die durchzuführenden
      Rechnungen ist. In diesen Fällen verwendet man in C den Datentyp \lstinline{int}
      für vorzeichenbehaftete ganze Zahlen und \lstinline{unsigned int} (oder kurz:
      \lstinline{unsigned}) für vorzeichenlose. Für die Ausgabe mit \lstinline{printf()}
      verwendet man \lstinline{%d} oder \lstinline{%i} für vorzeichenbehaftete und
      \lstinline{%u} für vorzeichenlose ganze Zahlen.
    
      Für spezielle Situationen, in denen die genaue Anzahl der Bits eine Rolle spielt,
      stellt C (unter Verwendung von \lstinline{#include <stdint.h>}) spezielle Datentypen bereit:
    
      \begin{center}
        \renewcommand{\arraystretch}{1.2}
        \newcommand{\xdots}{\hspace*{-0.7em}\dots,\hspace*{-0.7em}}
        \begin{tabular}{|c|c|c|rcl|}\hline
          C-Datentyp & Bits & Vorzeichen & \multicolumn{3}{c|}{Wertebereich} \\\hline\hline
          \lstinline,int8_t, & 8 & ja & $-128$, & \xdots & $127$ \\\hline
          \lstinline,uint8_t, & 8 & nein & $0$, & \xdots & $255$ \\\hline
          \lstinline,int16_t, & 16 & ja & $-32\,768$, & \xdots & $32\,767$ \\\hline
          \lstinline,uint16_t, & 16 & nein & $0$, & \xdots & $65\,535$ \\\hline
          \lstinline,int32_t, & 32 & ja & $-2\,147\,483\,648$, & \xdots & $2\,147\,483\,647$ \\\hline
          \lstinline,uint32_t, & 32 & nein & $0$, & \xdots & $4\,294\,967\,295$ \\\hline
          \lstinline,int64_t, & 64 & ja & $9\,223\,372\,036\,854\,775\,808$, & \xdots & $9\,223\,372\,036\,854\,775\,807$ \\\hline
          \lstinline,uint64_t, & 64 & nein & $0$, & \xdots & $18\,446\,744\,073\,709\,551\,615$ \\\hline
        \end{tabular}
      \end{center}
    
      Man beachte, daß es keine "`allein richtige"' Binärdarstellung einer negativen Zahl gibt;
      diese hängt vielmehr von der Genauigkeit $n$ des $n$-Bit-Rechenwerks ab.
      Auf einem 8-Bit-Rechner ist $255$ dasselbe wie $-1$,
      auf einem 16-Bit-Rechner ist $255$ eine "`völlig normale"' Zahl;
      stattdessen ist $65535$ dasselbe wie $-1$.
    
      Ebensowenig gibt es einen "`allein richtigen"' Zahlenwert eines Bitmusters.
      Dieser Zahlenwert hängt von der Genauigkeit $n$ des $n$-Bit-Rechenwerks ab
      und davon, ob man überhaupt negative Zahlen zuläßt
      oder vielleicht alle Zahlen als positive Zahlen interpretiert.
    
      \breath
    
      Beispiel: Für welche Zahl steht der Speicherinhalt 1001\,0000\,1100\,0011
      (binär) = 90a3 (hexadezimal)?
    
      Die richtige Antwort auf diese Frage hängt vom Datentyp ab,
      also von der Bitgenauigkeit des Rechenwerks
      und davon, ob wir überhaupt mit Vorzeichen rechnen:
    
      \begin{tabular}{lrl}
        als \lstinline,int8_t,: & $-93$ & (nur unteres Byte, Little-Endian)\\
        als \lstinline,uint8_t,: & $163$ & (nur unteres Byte, Little-Endian)\\
        als \lstinline,int16_t,: & $-28509$\\
        als \lstinline,uint16_t,: & $37027$\\
        \lstinline,int32_t, oder größer: & $37027$
          & (zusätzliche Bytes mit Nullen aufgefüllt)
      \end{tabular}
    
      \breath
    
      Siehe auch: \url{http://xkcd.com/571/}
    
      \subsection{Speicherausrichtung -- Alignment}
    
      Ein 32-Bit-Prozessor kann auf eine 32-Bit-Variable effizienter zugreifen,
      wenn die Speicheradresse der Variablen ein Vielfaches von 32 Bits, also 4 Bytes ist.
      Eine Variable, auf die dies zutrifft, heißt "`korrekt im Speicher ausgerichtet"' ("`aligned"').
    
      "`Effizienter"' kann bedeuten,
      daß Maschinenbefehle zum Arbeiten mit den Variablen schneller abgearbeitet werden.
      Es kann aber auch bedeuten,
      daß der Prozessor gar keine direkte Bearbeitung von inkorrekt ausgerichteten Variablen erlaubt.
      In diesem Fall bedeutet eine inkorrekte Speicherausrichtung,
      daß für jede Operation mit der Variablen anstelle eines einzelnen Maschinenbefehls
      ein kleines Programm aufgerufen werden muß.
    
      \bigskip
    
      Um zu verstehen, welche Konsequenzen dies für die Arbeit mit Rechnern hat,
      betrachten wir die folgenden Variablen:
    
      \begin{lstlisting}
        #include <stdint.h>
    
        uint8_t a;
        uint16_t b;
        uint8_t c;
      \end{lstlisting}
    
      Die Anordnung dieser Variablen im Speicher könnte z.\,B.\ folgendermaßen aussehen:
    
      \begin{quote}
        \newcommand{\bup}{\begin{picture}(0,0)\put(-0.1,0.2){\mbox{\lstinline|b|}}\end{picture}}
        \begin{tabular}{r|ccc|}
                        & & \dots         & \\\cline{2-4}
          \texttt{3005} & &               & \\\cline{2-4}
          \texttt{3004} & &               & \\\cline{2-4}
          \texttt{3003} & & \lstinline|c| & \\\cline{2-4}
          \texttt{3002} & &               & \\\cline{2-2}\cline{4-4}
          \texttt{3001} & & \bup          & \\\cline{2-4}
          \texttt{3000} & & \lstinline|a| & \\\cline{2-4}
          \texttt{2fff} & &               & \\\cline{2-4}
                        & & \dots         &
        \end{tabular}
      \end{quote}
    
      Ein optimierender Compiler wird für eine korrekte Ausrichtung der Variablen \lstinline|b| sorgen,
      beispielsweise durch Auffüllen mit unbenutzten Speicherzellen:
    
      \begin{quote}
        \newcommand{\bup}{\begin{picture}(0,0)\put(-0.1,0.2){\mbox{\lstinline|b|}}\end{picture}}
        \begin{tabular}{r|ccc|}
                        & & \dots         & \\\cline{2-4}
          \texttt{3005} & &               & \\\cline{2-4}
          \texttt{3004} & & \lstinline|c| & \\\cline{2-4}
          \texttt{3003} & &               & \\\cline{2-2}\cline{4-4}
          \texttt{3002} & & \bup          & \\\cline{2-4}
          \texttt{3001} & &               & \\\cline{2-4}
          \texttt{3000} & & \lstinline|a| & \\\cline{2-4}
          \texttt{2fff} & &               & \\\cline{2-4}
                        & & \dots         &
        \end{tabular}
      \end{quote}
    
      Alternativ ist es dem Compiler auch möglich,
      die korrekte Ausrichtung durch "`Umsortieren"' der Variablen herzustellen
      und dadurch "`Löcher"' zu vermeiden:
    
      \begin{quote}
        \newcommand{\bup}{\begin{picture}(0,0)\put(-0.1,0.2){\mbox{\lstinline|b|}}\end{picture}}
        \begin{tabular}{r|ccc|}
                        & & \dots         & \\\cline{2-4}
          \texttt{3005} & &               & \\\cline{2-4}
          \texttt{3004} & &               & \\\cline{2-4}
          \texttt{3003} & &               & \\\cline{2-2}\cline{4-4}
          \texttt{3002} & & \bup          & \\\cline{2-4}
          \texttt{3001} & & \lstinline|c| & \\\cline{2-4}
          \texttt{3000} & & \lstinline|a| & \\\cline{2-4}
          \texttt{2fff} & &               & \\\cline{2-4}
                        & & \dots         &
        \end{tabular}
      \end{quote}
    
      Fazit: Man kann sich als Programmierer nicht immer darauf verlassen,
      daß die Variablen im Speicher in einer spezifischen Weise angeordnet sind.
    
      In vielen existierenden Programmen geschieht dies dennoch.
      Diese Programme sind fehlerhaft.
      Dort kann es z.\,B.\ passieren, daß nach einem Upgrade des Compilers
      schwer lokalisierbare Fehler auftreten.
    
      \bigskip
      \goodbreak
    
      Entsprechende Überlegungen gelten für 64-Bit- und 16-Bit-Prozessoren.
      Die Größe der Variablen, aufgerundet auf die nächste Zweierpotenz, gibt eine Ausrichtung vor.
      Die Registerbreite des Prozessors markiert die größte Ausrichtung, die noch berücksichtigt werden muß.
    
      Bei 8-Bit-Prozessoren stellt sich die Frage nach der Speicherausrichtung normalerweise nicht,
      weil die kleinste adressierbare Einheit eines Speichers selten kleiner als 8 Bits ist.
    
      Beispiele:
      \begin{itemize}
        \item
          Eine 64-Bit-Variable auf einem 64-Bit-Prozessor muß auf 64 Bits ausgerichtet sein.
        \item
          Eine 32-Bit-Variable auf einem 64-Bit-Prozessor braucht nur auf 32 Bits ausgerichtet zu sein.
        \item
          Eine 64-Bit-Variable auf einem 32-Bit-Prozessor braucht nur auf 32 Bits ausgerichtet zu sein.
        \item
          Eine 64-Bit-Variable auf einem 8-Bit-Prozessor braucht nur auf 8 Bits ausgerichtet zu sein.
      \end{itemize}
    
      Bei der Definition von Datenformaten tut man gut daran,
      die Ausrichtung der Daten von vorneherein zu berücksichtigen,
      um auf möglichst vielen -- auch zukünftigen -- Prozessoren
      eine möglichst effiziente Bearbeitung zu ermöglichen.
    
      Wenn ich beispielsweise ein Dateiformat definiere, in dem 128-Bit-Werte vorkommen,
      ist es sinnvoll, diese innerhalb der Datei auf 128 Bits (16 Bytes) auszurichten,
      auch wenn mein eigener Rechner nur über einen 64-Bit-Prozessor verfügt.
    
    \iffalse
    
      \section{Ergänzungen und Ausblicke}
    
      \subsection{String-Operationen}
    
      Die Include-Datei \file{string.h} deklariert eine Sammlung nützlicher Funktionen
      für den Umgang mit Strings (\lstinline{char *}).
    
      In den Sortierprogrammen \file{sort-\lstinline{*}.c} wurde davon bereits
      die Funktion \lstinline{strcmp()} verwendet.
    
      \lstinline{strcmp (foo, bar)} liefert den Wert \lstinline{-1} zurück,
      wenn der String \lstinline{foo} alphabetisch kleiner ist als der String \lstinline{bar},
      sie liefert \lstinline{0} zurück, wenn beide Strings gleich sind,
      und sie liefert \lstinline{1} zurück, wenn \lstinline{foo} alphabetisch größer ist als \lstinline{bar}.
    
      \subsection{Dateien}
    
      \begin{itemize}
        \item
          \file{fhello.c} ist das klassische "`Hello, world!"`-Programm in einer Variante,
          die in eine Datei \file{hello.txt} anstelle der Standardausgabe schreibt.
    
          \begin{experts}
            Auch die Standardausgabe ist übrigens eine "`normale"' Datei.
            \lstinline{printf (foo)} ist nur eine Abkürzung für \lstinline{fprintf (stdout, foo)}.
          \end{experts}
        \item
          \file{fread-1.c} zeigt, wie man zeilenweise aus einer Textdatei liest.
    
          Dieses Programm prüft nicht, ob die Datei tatsächlich
          erfolgreich geöffnet werden konnte.
          Dies hat zur Folge, daß im Fehlerfall versucht wird,
          auf einen \lstinline{NULL}-Pointer zuzugreifen -- also einen Absturz.
    
          Das Programm ist somit grob fehlerhaft.
        \item
          \file{fread-2.c} zeigt, wie es besser geht:
          Wenn die Datei nicht geöffnet werden kann,
          wird eine Fehlermeldung ausgegeben und das Programm kontrolliert beendet.
    
          Es besteht aber weiterhin ein Problem:
          Die Fehlerursache "`Datei nicht gefunden"' wurde lediglich geraten.
          Sie kann falsch sein und somit, anstatt hilfreich zu sein,
          den Benutzer in die Irre führen.
    
          Auch dieses Programm ist also noch grob fehlerhaft.
        \item
          \file{fread-3.c} zeigt die korrekte Vorgehensweise:
          Mit Hilfe der Systemvariablen \lstinline{errno} (deklariert in \file{errno.h})
          und der Funktion \lstinline{strerror()} (deklariert in \file{string.h})
          wird geprüft, welcher Fehler vorliegt.
          Anhand dieser Information wird dann die vom Betriebssystem
          für diesen Fall vorgesehene Fehlermeldung ausgegeben.
      \end{itemize}
    
      Dieselben Überlegungen zur Fehlerbehandlung gelten natürlich auch
      für das Öffnen einer Datei zum Schreiben, hier also auch für \file{fhello.c}.
    
    \fi
    
      \section{Algorithmen}
    
      \subsection{Differentialgleichungen}
    
      Eine mathematische Gleichung mit einer gesuchten Zahl $x$, z.\,B.
      \begin{displaymath}
        x + 2 = -x
      \end{displaymath}
      läßt sich leicht nach der Unbekannten $x$ auflösen.
      (In diesem Fall lautet die Lösung: $x = -1$.)
    
      Wesentlich schwieriger ist es,
      eine mathematische Gleichung mit einer gesuchten Funktion $x(t)$ zu lösen, z.\,B.:
      \begin{displaymath}
        x'(t) = -x(t)\qquad\mbox{mit}\qquad x(0) = 1
      \end{displaymath}
      Um hier auf die Lösung $x(t) = e^{-t}$ zu kommen,
      sind bereits weitreichende mathematische Kenntnisse erforderlich.
    
      Eine derartige Gleichung, die einen Zusammenhang zwischen der gesuchten Funktion
      und ihren Ableitungen vorgibt, heißt \newterm{Differentialgleichung}.
      Viele physikalisch-technische Probleme werden durch Differentialgleichungen beschrieben.
    
      \goodbreak
    
      \subsubsection{Beispiel: Pendelschwingung}
    
      \begin{minipage}{9.4cm}
        \setlength{\parskip}{\smallskipamount}
        Das Verhalten eines Fadenpendels (mathematisches Pendel)
        wird durch seine Auslenkung $\phi$ als Funktion der Zeit $t$ beschrieben.
        Wie kann man $\phi(t)$ berechnen?
    
        Wie aus anderen Veranstaltungen (Grundlagen der Physik, Mechanik) her bekannt sein sollte,
        wirkt auf ein Fadenpendel, das um den Winkel $\phi(t)$ ausgelenkt ist,
        die tangentiale Kraft $F = -m \cdot g \cdot \sin\phi(t)$.
        Gemäß der Formel $F = m \cdot a$ bewirkt diese Kraft
        eine tangentiale Beschleunigung $a = -g \cdot \sin\phi(t)$.
        (Das Minuszeichen kommt daher, daß die Kraft der Auslenkung entgegengesetzt wirkt.)
    
        Wenn das Pendel die Länge $l$ hat, können wir dieselbe tangentiale Beschleunigung
        mit Hilfe der zweiten Ableitung des Auslenkungswinkels $\phi(t)$ berechnen:
        $a = l \cdot \phi''(t)$ (Winkel in Bogenmaß).
        Durch Gleichsetzen erhalten wir eine Gleichung,
        die nur noch eine Unbekannte enthält, nämlich die Funktion $\phi(t)$.
    
        Um $\phi(t)$ zu berechnen, müssen wir also die Differentialgleichung
        \begin{displaymath}
          \phi''(t) = -\frac{g}{l} \cdot \sin\phi(t)
        \end{displaymath}
        lösen.
      \end{minipage}\hfill
      \begin{minipage}{5.5cm}
        \begin{center}
          \begin{pdfpic}
            \psset{unit=1.5cm}%
            \begin{pspicture}(0,0)(0,0)
              \SpecialCoor
              \psline[linewidth=1pt](3;-110)(0,0)
              \rput(3.25;-110){\psline[linewidth=0.5pt,linecolor=lightgray](0.34;-20)(1.00;-90)}
              \rput(3.25;-110){\psline[linewidth=0.5pt,linecolor=lightgray](0.94;-110)(1.00;-90)}
              \rput(3.25;-110){\psline[linewidth=0.5pt,arrows=->](0,0)(0.34;-20)}
              \rput(3.25;-110){\psline[linewidth=0.5pt,arrows=->](0,0)(0.94;-110)}
              \rput(3.25;-110){\psline[linewidth=0.5pt,arrows=->](0,0)(1.00;-90)}
              \rput(3.25;-110){\rput(0.64;-20){\makebox(0,0){$F$}}}
              \rput(3.25;-110){\rput(1.30;-90){\makebox(0,0){$m\cdot g$}}}
              \pscircle*(3;-110){0.07}
              \psline[linewidth=0.5pt,linestyle=dashed](0,0)(0,-1.9)
              \psarc[linewidth=0.5pt,arrows=<-](0,0){1.5}{-110}{-90}
              \rput(1.3;-100){\makebox(0,0){$\phi$}}
              \psarc[linewidth=0.5pt,linestyle=dashed,arrows=<->,arcsepA=0.12](0,0){3}{-110}{-70}
              \rput(0,-4.5){\psstrut}
            \end{pspicture}
          \end{pdfpic}
        \end{center}
      \end{minipage}
    
      \breath
        
      \begin{experts}
        Diese Differentialgleichung läßt sich mit "`normalen"' Mitteln nicht lösen,
        daher verwendet man in der Praxis meistens die Kleinwinkelnäherung
        $\sin\phi \approx \phi$ (für $\phi \ll 1$)
        und löst stattdessen die Differentialgleichung:
        \begin{displaymath}
          \phi''(t) = -\frac{g}{l} \cdot \phi(t)
        \end{displaymath}
        Für ein mit der Anfangsauslenkung $\phi(0)$ losgelassenes Pendel
        lautet dann das Ergebnis:
        \begin{displaymath}
          \phi(t) = \phi(0)\cdot\cos(\omega t)\qquad\mbox{mit}\qquad\omega=\sqrt{\frac{g}{l}}
        \end{displaymath}
        Das Beispielprogramm \gitfile{hp}{script}{pendulum-1.c} illustriert,
        welche Bewegung sich aus diesem $\phi(t)$ ergibt.
      \end{experts}
    
      \subsubsection{Das explizite Euler-Verfahren}
    
      Um eine Differentialgleichung mit Hilfe eines Computers näherungsweise \newterm{numerisch\/} zu lösen,
      stehen zahlreiche Lösungsverfahren zur Verfügung.
      Im folgenden soll das einfachste dieser Verfahren, das \newterm{explizite Euler-Verfahren\/}
      (auch \newterm{Eulersches Polygonzugverfahren\/} genannt) vorgestellt werden.
    
      Wir betrachten das System während eines kleinen Zeitintervalls $\Delta t$.
      Während dieses Zeitintervalls sind alle von der Zeit $t$ abhängigen Funktionen
      -- z.\,B.\ Ort, Geschwindigkeit, Beschleunigung, Kraft -- näherungsweise konstant.
    
      Bei konstanter Geschwindigkeit $v$ ist es einfach,
      aus dem Ort $x(t)$ zu Beginn des Zeitintervalls
      den Ort $x(t + \Delta t)$ am Ende des Zeitintervalls zu berechnen:
      \begin{displaymath}
        x(t + \Delta t) = x(t) + \Delta t \cdot v
      \end{displaymath}
    
      Bei konstanter Kraft $F = m \cdot a$
      und somit konstanter Beschleunigung $a$ ist es ebenso einfach,
      aus der Geschwindigkeit $v(t)$ zu Beginn des Zeitintervalls
      die Geschwindigkeit $v(t + \Delta t)$ am Ende des Zeitintervalls zu berechnen:
      \begin{displaymath}
        v(t + \Delta t) = v(t) + \Delta t \cdot a
      \end{displaymath}
    
      Wenn wir dies in einer Schleife durchführen und jedesmal $t$ um $\Delta t$ erhöhen,
      erhalten wir Näherungen für die Funktionen $x(t)$ und $v(t)$.
    
      \breath
    
      Für das oben betrachtete Beispiel (Fadenpendel)
      müssen wir in jedem Zeitintervall $\Delta t$
      zunächst die tangentiale Beschleunigung $a(t)$ aus der tangentialen Kraft berechnen,
      die sich wiederum aus der momentanen Auslenkung $\phi(t)$ ergibt:
      \begin{displaymath}
        a = -g \cdot \sin\phi
      \end{displaymath}
      Mit Hilfe dieser -- innerhalb des Zeitintervalls näherungsweise konstanten -- Beschleunigung
      berechnen wir die neue tangentiale Geschwindigkeit:
      \begin{displaymath}
        v(t + \Delta t) = v(t) + \Delta t \cdot a
      \end{displaymath}
      Mit Hilfe dieser -- innerhalb des Zeitintervalls näherungsweise konstanten -- Geschwindigkeit
      berechnen wir schließlich die neue Winkelauslenkung $\phi$,
      wobei wir einen kleinen Umweg über den Kreisbogen $x = l\cdot\phi$ machen:
      \begin{displaymath}
        \phi(t + \Delta t) = \frac{x(t + \Delta t)}{l}
                           = \frac{x(t) + \Delta t \cdot v}{l}
                           = \phi(t) + \frac{\Delta t \cdot v}{l}
      \end{displaymath}
    
      Ein C-Programm, das diese Berechnungen durchführt (Datei: \gitfile{hp}{script}{pendulum-2.c}), enthält als Kernstück:
      \goodbreak
      \begin{lstlisting}
        #define g 9.81
        #define l 1.0
        #define dt 0.05
        #define phi0 30.0  /* degrees */
    
        float t = 0.0;
        float phi = phi0 * M_PI / 180.0;
        float v = 0.0;
    
        void calc (void)
        {
          float a = -g * sin (phi);
          v += dt * a;
          phi += dt * v / l;
        }
      \end{lstlisting}
      \goodbreak
      Jeder Aufruf der Funktion \lstinline{calc()}
      versetzt das Pendel um das Zeitintervall \lstinline{dt} in die Zukunft.
     
      Es ist vom Verfahren her nicht notwendig, mit der Kleinwinkelnäherung $\sin\phi\approx\phi$ zu arbeiten.
      Das Beispielprogramm \gitfile{hp}{script}{pendulum-3.c} illustriert,
      welchen Unterschied die Kleinwinkelnäherung ausmacht.
    
      Wie gut arbeitet das explizite Euler-Verfahren?
      Um dies zu untersuchen, lösen wir eine Differentialgleichung,
      deren exakte Lösung aus der Literatur bekannt ist,
      nämlich die Differentialgleichung mit Kleinwinkelnäherung.
      Das Beispielprogramm \gitfile{hp}{script}{pendulum-4.c} vergleicht beide Lösungen miteinander.
      Für das betrachtete Beispiel ist die Übereinstimmung recht gut;
      für Präzisionsberechnungen ist das explizite Euler-Verfahren jedoch nicht genau (und stabil) genug.
      Hierfür sei auf die Lehrveranstaltungen zur numerischen Mathematik verwiesen.
    
      \subsubsection*{Bemerkung}
    
      Das Beispielprogramm \gitfile{hp}{script}{pendulum-4.c} berechnet mit überzeugender Übereinstimmung
      dasselbe Ergebnis für die Auslenkung des Pendels auf zwei verschiedene Weisen:
      \begin{enumerate}
        \item
          über eine Formel, die einen Cosinus enthält,
        \item
          mit Hilfe der Funktion \lstinline{calc()}, die nur Grundrechenarten verwendet.
      \end{enumerate}
      Dies läßt die Natur der Verfahren erahnen, mit deren Hilfe es möglich ist,
      Sinus, Cosinus und andere kompliziertere Funktionen
      nur unter Verwendung der Grundrechenarten zu berechnen.
    
      \goodbreak
    
      \subsection{Rekursion}
    
      Aus der Mathematik ist das Beweisprinzip der \newterm{vollständigen Induktion\/} bekannt:
      \begin{displaymath}
        \hspace*{4cm}
        \left.
          \begin{array}{r}
            \mbox{Aussage gilt für $n = 1$}\\[2pt]
            \mbox{Schluß von $n - 1$ auf $n$}
          \end{array}
        \right\}
        \mbox{Aussage gilt für alle $n\in\mathbb{N}$}
      \end{displaymath}
      Wenn auf diese Weise die Lösbarkeit eines Problems bewiesen wurde,
      ist es direkt möglich, das Problem im Computer \emph{tatsächlich\/} zu lösen,
      nämlich durch einen \newterm{rekursiven Algorithmus}.
    
      \breath
    
      Ein klassisches Beispiel für ein rekursiv lösbares Problem sind die Türme von Hanoi:
      \begin{itemize}
        \item
          64 Scheiben, 3 Plätze, immer 1 Scheibe verschieben
        \item
          Ziel: Turm verschieben
        \item
          Es dürfen nur kleinere Scheiben auf größeren liegen.
      \end{itemize}
    
      \goodbreak
      \begin{center}
        \includegraphics[width=12.2cm]{Tower_of_Hanoi.jpeg}
    
        \small
    
        Bildquelle: \url{http://commons.wikimedia.org/wiki/File:Tower\_of\_Hanoi.jpeg}\\
        Urheber: \url{http://en.wikipedia.org/wiki/User:Evanherk}\\
        Lizenz: GNU FDL (Version 1.2 oder später) oder\\
        Creative Commons Attribution-Share Alike (Version 3.0 Unported)
        
      \end{center}
    
      \goodbreak
      Die rekursive Lösung des Problems lautet:
      \begin{itemize}
        \item
          Wenn $n = 1$ ist, also nur eine Scheibe vorliegt,
          läßt sich diese "`einfach so"' an den Zielplatz verschieben.
          In diesem Fall sind wir direkt fertig.
        \item
          Wenn $n - 1$ Scheiben als verschiebbar vorausgesetzt werden,
          lautet die Vorgehensweise:\\
          verschiebe die oberen $n - 1$ Scheiben auf einen Hilfsplatz,\\
          verschiebe die darunterliegende einzelne Scheibe auf den Zielplatz,\\
          verschiebe die $n - 1$ Scheiben vom Hilfsplatz auf den Zielplatz.
      \end{itemize}
    
      \goodbreak
      Dieser Algorithmus läßt sich unmittelbar in eine Programmiersprache übersetzen:
      \begin{lstlisting}
        void verschiebe (int n, int start, int ziel)
        {
          if (n == 1)
            verschiebe_1_scheibe (start, ziel);
          else
            {
              verschiebe (1, start, hilfsplatz);
              verschiebe (n - 1, start, ziel);
              verschiebe (1, hilfsplatz, ziel);
            }
        }
      \end{lstlisting}
    
    \iffalse
    
      \subsection{Floodfill}
    
      Siehe die Vortragsfolien \file{ainf-20121220.pdf}\\
      sowie die Beispielprogramme \file{fill-\lstinline{*}.c}
    
      \subsection{Stack und FIFO}
    
      Siehe Vortragsfolien und Beispielprogramme
    
      \subsection{Wegfindungsalgorithmus für Roboterfahrzeug}
    
      Siehe die Vortragsnotizen \file{ainf-20130117.txt},\\
      die Beispielprogramme \file{text-parcour-\lstinline{*}.c},
      \file{robotext.c} und \file{robotext.h}\\
      sowie die E-Mails "`Wegfindung"' und "`Weg-Finde-Algorithmus"'
    
    \fi
    
      \subsection{Aufwandsabschätzungen}
    
      \subsubsection{Sortieralgorithmen}
    
      Am Beispiel von Sortieralgorithmen soll hier aufgezeigt werden,
      wie man die Lösung eines Problems schrittweise effizienter gestalten kann.
    
      Als Problem wählen wir das Sortieren eines Arrays (z.\,B.\ von Namen).
    
      \begin{itemize}
        \item
          Minimum/Maximum ermitteln:
          \gitfile{hp}{script}{sort-0.c} (mit "`Schummeln"'),
          \gitfile{hp}{script}{sort-1.c} (lineare Suche),
          \gitfile{hp}{script}{sort-2.c} (mit Visualisierung)
        \item
          Selectionsort:
          \gitfile{hp}{script}{sort-3.c} (bei Minimumsuche Anfang des Arrays überspringen),
          \gitfile{hp}{script}{sort-4.c} (Selectionsort),
          \gitfile{hp}{script}{sort-5.c} (100 Namen),
          \gitfile{hp}{script}{sort-6.c} (100 Namen, ohne Visualisierung)
        \item
          Bubblesort:
          \gitfile{hp}{script}{sort-7.c} (Selectionsort, Minimumsuche mit in der Hauptschleife),
          \gitfile{hp}{script}{bsort-1.c} (Minimumsuche durch Vergleich benachbarter Strings),
          \gitfile{hp}{script}{bsort-2.c} (Abbruch in äußerer Schleife, sobald sortiert),
          \gitfile{hp}{script}{bsort-3.c} (Abbruch auch in innerer Schleife, sobald sortiert)
        \item
          Quicksort:
          \gitfile{hp}{script}{qsort-1.c} (Array in 2 Hälften vorsortieren),
          \gitfile{hp}{script}{qsort-2.c} (rekursiver Aufruf für linke Hälfte),
          \gitfile{hp}{script}{qsort-3.c} (rekursiver Aufruf für beide Hälften)
      \end{itemize}
    
      Bei "`zufällig"' sortierten Ausgangsdaten arbeitet Quicksort schneller als Bubblesort.
      Wenn die Ausgangsdaten bereits nahezu sortiert sind, ist es umgekehrt.
      Im jeweils ungünstigsten Fall arbeiten beide Algorithmen gleich langsam.
    
      \subsubsection{Landau-Symbole}
    
      Das Landau-Symbol $\mathcal{O}(g)$ mit einer Funktion $g(n)$
      steht für die \newterm{Ordnung\/} eines Algorithmus',
      also die "`Geschwindigkeit"', mit der er arbeitet.
      Die Variable $n$ bezeichnet die Menge der Eingabedaten,
      hier also z.\,B.\ die Anzahl der Namen.
    
      \begin{center}
        \begin{pdfpic}
          \psset{unit=1pt}
          \begin{pspicture}(-20,-20)(250,200)
            \psline[arrows=->](-10,0)(200,0)
            \psline[arrows=->](0,-10)(0,200)
            \psplot[plotpoints=200]{1}{125}{2 x 0.06 mul exp}
            \put(100,190){\mbox{$g(n) \sim 2^n$}}
            \psplot[plotpoints=200]{0}{190}{x x mul 0.005 mul}
            \put(190,190){\mbox{$g(n) \sim n^2$}}
            \psplot[plotpoints=200]{1}{190}{x ln x mul 0.1 mul}
            \put(195,100){\mbox{$g(n) \sim n \log n$}}
            \psplot[plotpoints=200]{0}{190}{x 0.4 mul}
            \put(195,75){\mbox{$g(n) \sim n$}}
            \psplot[plotpoints=200]{1}{190}{x ln 10 mul}
            \put(195,50){\mbox{$g(n) \sim \log n$}}
            \put(210,0){\makebox(0,0)[l]{$n$}}
            \put(0,210){\makebox(0,0)[l]{$g(n)$}}
          \end{pspicture}
        \end{pdfpic}
      \end{center}
    
      \begin{itemize}
        \item
          $\mathcal{O}(n)$ bedeutet, daß die Rechenzeit mit der Menge der Eingabedaten linear wächst.
          Um doppelt so viele Namen zu sortieren, benötigt das Programm doppelt so lange.
        \item
          $\mathcal{O}(n^2)$ bedeutet, daß die Rechenzeit mit der Menge der Eingabedaten quadratisch wächst.
          Um doppelt so viele Namen zu sortieren, benötigt das Programm viermal so lange.
        \item
          $\mathcal{O}(2^n)$ bedeutet, daß die Rechenzeit mit der Menge der Eingabedaten exponentiell wächst.
          Für jeden Namen, der dazukommt, benötigt das Programm doppelt so lange.
    
          Ein derartiges Programm gilt normalerweise als inakzeptabel langsam.
        \item
          $\mathcal{O}(\log n)$ bedeutet, daß die Rechenzeit mit der Menge der Eingabedaten logarithmisch wächst.
          Für jede Verdopplung der Namen benötigt das Programm nur einen Rechenschritt mehr.
    
          Ein derartiges Programm gilt als "`traumhaft schnell"'.
          Dies wird jedoch nur selten erreicht.
        \item
          $\mathcal{O}(1)$ bedeutet, daß die Rechenzeit von der Menge der Eingabedaten unabhängig ist:
          1\,000\,000 Namen werden genau so schnell sortiert wie 10.
    
          Dies ist nur in Ausnahmefällen erreichbar.
        \item
          $\mathcal{O}(n \log n)$ liegt zwischen $\mathcal{O}(n)$ und $\mathcal{O}(n^2)$.
    
          Ein derartiges Programm gilt als schnell.
          Viele Sortieralgorithmen erreichen dieses Verhalten.
      \end{itemize}
    
      Wie sieht man einem Programm an, wie schnell es arbeitet?
    
      \begin{itemize}
        \item
          Vorfaktoren interessieren nicht.
    
          Wenn ein Code immer -- also unabhängig von den Eingabedaten -- zweimal ausgeführt wird,
          beeinflußt das die Ordnung des Algorithmus nicht.
    
          Wenn ein Code immer -- also unabhängig von den Eingabedaten -- 1\,000\,000mal ausgeführt wird,
          mag das Programm für kleine Datenmengen langsam erscheinen.
          Für die Ordnung interessiert jedoch nur das Verhalten für große Datenmengen,
          und dort kann dasselbe Programm durchaus schnell sein.
        \item
          Jede Schleife, die von $0$ bis $n$ geht,
          multipliziert die Rechenzeit des innerhalb der Schleife befindlichen Codes mit $n$.
    
          Eine Doppelschleife (Schleife innerhalb einer Schleife) hat demnach $\mathcal{O}(n^2)$.
        \goodbreak
        \item
          Wenn sich die Grenzen einer Schleife ständig ändern, nimmt man den Durschschnitt.
    
          Beispiel:
          \begin{lstlisting}[gobble=8]
            for (int i = 0; i < n; i++)
              for (int j = 0; j < i; j++)
                ...
          \end{lstlisting}
          Die äußere Schleife wird immer $n$-mal ausgeführt,
          die innere \emph{im Durchschnitt\/} $\frac{n}{2}$-mal, was proportional zu $n$ ist.
    
          Zusammen ergibt sich $\mathcal{O}(n^2)$.
        \item
          Bei Rekursionen muß man mitzählen, wie viele Schleifen hinzukommen.
    
          Bei Quicksort wird z.\,B.\ in jeder Rekursion
          eine Schleife von $0$ bis $n$ (aufgeteilt) ausgeführt.
          Bei jeder Rekursion wird das Array "`normalerweise"' halbiert,
          d.\,h.\ die Rekursionstiefe ist proportional zum Logarithmus von $n$ (zur Basis 2).
          Daraus ergibt sich die Ordnung $\mathcal{O}(n\log n)$ für den "`Normalfall"' des Quicksort.
          (Im ungünstigsten Fall kann sich auch $\mathcal{O}(n^2)$ ergeben.)
      \end{itemize}
    
      Für eine präzise Definition der Landau-Symbole siehe z.\,B.:
      \url{http://de.wikipedia.org/wiki/Landau-Symbole}
    
      \section{Objektorientierte Programmierung}
    
    \iffalse
    
      In Abschnitt \ref{Strukturen} haben wir Funktionen geschrieben,
      die eine \lstinline{struct}-Variable bearbeiten.
    
      Das Konzept, Funktionen möglichst eng mit den Daten zu bündeln,
      die sie bearbeiten, ist ein wichtiger Aspekt der \newterm{objektorientierten Programmierung}.
    
      Das Beispielprogramm \file{dates-1.c} illustriert einen Satz von Funktionen
      zur Bearbeitung von \file{date}-Objekten, sog.\ \newterm{Methoden}.
      Methoden erwarten als "`standardisierten"' ersten Parameter das Objekt:
      einen Zeiger \lstinline{this} auf ein C-\lstinline{struct}.
      Wenn der Satz von Funktionen vollständig ist, ist es nicht mehr nötig,
      direkt auf die Datenfelder des \lstinline{struct}s zuzugreifen.
      Dies nennt man \newterm{Kapselung}.
    
      Viele Sprachen (z.\,B.\ C++ als Weiterentwicklung von C)
      unterstützen objektorientierte Programmierung durch Sprachelemente.
      In diesen Sprachen ist der \lstinline{this}-Parameter i.\,d.\,R.\ nicht sichtbar,
      sondern implizit.
    
      Das Beispielprogramm \file{dates-2.c} geht noch einen Schritt weiter
      und verankert im Objekt Zeiger auf Methoden -- sog.\ \newterm{virtuelle Methoden}.
      Dieses mit den Callback-Funktionen vergleichbare Konzept ermöglicht es,
      verschiedenen, miteinander "`verwandten"' Objekten Methoden mit gleichen Namen
      zuzuordnen, die sich aber unterschiedlich verhalten.
      Dies nennt man \newterm{Polymorphie}.
    
      Wenn die o.\,a.\ "`Verwandschaft"' von Objekten darin besteht,
      daß das eine Objekt ein anderes erweitert (zusätzliche Datenfelder und Methoden,
      evtl.\ veränderte, \newterm{überschriebene\/} virtuelle Methoden),
      spricht man von \newterm{Vererbung}.
      Das Objekt, das erweitert wird, ist der \newterm{Vorfahre\/} des anderen Objekts.
    
      In Sprachen wie C, die keine Sprachelemente für objektorientierte Programmierung
      zur Verfügung stellen, kann dennoch Objektorientierung "`zu Fuß"' erreicht werden.
      Die GUI-Bibliothek GTK+,
      die ursprünglich für das Bildverarbeitungsprogramm GIMP entwickelt wurde,
      inzwischen aber in zahlreichen Programmen (z.\,B.\ Mozilla Firefox) ihren Dienst tut,
      funktioniert auf diese Weise.
    
    \fi
    
      \addtocounter{subsection}{-1}
      \subsection{Dynamische Speicherverwaltung}
    
      Variable in C haben grundsätzlich eine feste Größe.
      Dies gilt auch für Arrays:
      Auch mit der Schreibweise ohne Größenangabe, z.\,B.
      \lstinline|int a[] = { 2, 3, 5, 7 };|
      handelt es sich \emph{nicht\/} um ein Array veränderlicher Größe.
      Die \lstinline{[]}-Schreibweise besagt lediglich,
      daß der Compiler die Größe des Arrays anhand des Initialisierers
      (hier: \lstinline|{ 2, 3, 5, 7 }|) selbst berechnen soll.
      Das Beispiel \lstinline|int a[] = { 2, 3, 5, 7 };| ist nur eine andere Schreibweise für
      \lstinline|int a[4] = { 2, 3, 5, 7 };|.
    
      Um \emph{tatsächlich\/} Arrays mit einer variablen Anzahl von Elementen verwenden
      zu können, ist es in C notwendig, durch einen Funktionsaufruf explizit Speicher zu
      reservieren:
      \begin{lstlisting}
        #include <stdlib.h>
        ...
        int *a = malloc (4 * sizeof (int));
        ...
        free (a);
      \end{lstlisting}
    
      \lstinline{malloc()} reserviert Speicher, \lstinline{free()} gibt ihn wieder frei.
       
      Man beachte, daß man in C auf Zeiger mit dem \lstinline{[]}-Operator
      genau wie auf "`normale"' Arrays mit einem Index zugreifen kann:
      \begin{lstlisting}
        int *a = malloc (4 * sizeof (int));
        ...
        for (int i = 0; i < 4; i++)
          printf ("%d\n", a[i]);
      \end{lstlisting}
    
      Es gibt normalerweise keine Möglichkeit, einem Zeiger (hier: \lstinline{a}) anzusehen,
      wie groß der Speicherbereich ist, auf den er zeigt.
      Diesen Wert muß sich das Programm selbst merken, typischerweise in einer Variablen:
      \begin{lstlisting}
        int n = 4;
        int *a = malloc (n * sizeof (int));
        ...
        for (int i = 0; i < n; i++)
          printf ("%d\n", a[i]);
      \end{lstlisting}
    
      \subsection{Konzepte und Ziele}
    
      Für viele Anwendungen ist der o.\,a.\ Mechanismus der \newterm{dynamischen Arrays\/}
      noch nicht flexibel genug: Auch wenn die Anzahl der Elemente nicht mehr festliegt,
      so müssen doch alle genau dieselbe Größe haben. In vielen Situationen möchte man
      jedoch eine vorher nicht festgelegte Anzahl von Objekten unterschiedlichen Typs in
      einer Schleife abarbeiten -- z.\,B.\ verschiedene geometrische Objekte in einem
      Zeichenprogramm oder verschiedene Bedienelemente (Button, Zeichenbereich,
      Eingabefeld, \dots) in einer graphischen Benutzeroberfläche (Graphical User
      Interface -- GUI).
    
      Um dieses Problem zu lösen, speichert man Zeiger auf Objekte unterschiedlicher Größe
      in einem dynamischen Array.
      Dies funktioniert, weil alle Zeiger -- auch wenn sie auf unterschiedlich große
      Objekte zeigen -- die gleiche Größe haben
      und daher in demselben Array koexistieren können.
    
      \breath
    
      Um alle diese Objekte in einer Schleife auf gleiche Weise behandeln zu können,
      benötigt man standardisierte Funktionen, die mit dem Objekt arbeiten.
      Diese nennt man \newterm{Methoden}.
    
      Eine Methode bewirkt unterschiedliche Dinge,
      je nachdem, auf welches Objekt sie angewandt wird.
      Dies hängt vom Typ des Objekts ab.
      Um dies zu realisieren, kann man ein Objekt als \lstinline{struct}-Variable
      speichern, die zusätzlich zum eigentlichen Inhalt
      eine Kennung für den Objekttyp als Datenfeld enthält.
      In der Methode fragt man diese Typkennung ab
      und entscheidet auf dieser Grundlage, was die Methode bewirkt.
    
      Dies kann über \lstinline{if}-Abfragen (oder \lstinline{switch}-Anweisungen)
      geschehen, bei sehr vielen unterschiedlichen Objekttypen entarten derartige
      Methoden jedoch zu sehr unübersichtlichen \lstinline{if}-Ketten.
      Weiter unten werden elegantere Wege zur Realisierung von Methoden vorgestellt.
    
      \breath
    
      Objekte, die einen gemeinsamen Anteil von Eigenschaften haben
      und sich typischerweise in demselben Array befinden,
      bezeichnet man als \newterm{miteinander verwandt}.
      Der "`kleinste gemeinsame Nenner"' dieser Objekte,
      also ein Objekttyp der \emph{nur\/} den gemeinsamen Anteil enthält,
      heißt \newterm{Basisklasse\/} oder \newterm{gemeinsamer Vorfahr\/}
      der Objekte. Umgekehrt heißt ein Objekttyp, der eine Basisklasse um neue
      Eigenschaften erweitert, \newterm{abgeleitete Klasse\/}
      oder \newterm{Nachfahre} der Basisklasse.
    
      Eigenschaften, die ein Objekttyp mit seinem Vorfahren gemeinsam hat,
      bezeichnet man als \newterm{vom Vorfahren geerbt}.
    
      \breath
    
      Ein "`Array von Objekten"' wird zunächst als Array von Zeigern auf die Basisklasse
      realisiert; die Zeiger zeigen aber in Wirklichkeit
      auf Objekte von abgeleiteten Klassen.
      Diese Möglichkeit, unterschiedliche Objekte gemeinsam zu verwalten,
      bezeichnet man als \newterm{Polymorphie} (griechisch: \emph{Vielgestaltigkeit\/}).
    
      \subsection{Beispiel: Zahlen und Buchstaben}
    
      Als Beispiel konstruieren wir eine Struktur,
      die Zahlen und Buchstaben (Strings) gemeinsam verwalten soll,
      also gewissermaßen ein Array,
      das sowohl ganze Zahlen (\lstinline{int})
      als auch Strings (\lstinline{char *}) als Elemente haben kann.
    
      Zu diesem Zweck definieren wir zwei \lstinline{struct}-Datentypen
      \lstinline{t_integer} und \lstinline{t_string},
      die als Inhalt (\lstinline{content}) eine ganze Zahl bzw.\ einen String enthalten
      und zusätzlich eine Typ-Kennung (hier: \lstinline{int type}).
      Weiterhin definieren wir einen gemeinsamen Vorfahren \lstinline{t_base},
      der \emph{nur\/} die Typ-Kennung enthält.
    
      \goodbreak
    
      \begin{center}
        \begin{minipage}{5cm}
          \begin{lstlisting}[gobble=8]
            typedef struct
            {
              int type;
            } t_base;
          \end{lstlisting}
        \end{minipage}\\[0.5cm]
        \begin{minipage}{5cm}
          \begin{lstlisting}[gobble=8]
            typedef struct
            {
              int type;
              int content;
            } t_integer;
          \end{lstlisting}
        \end{minipage}
        \begin{minipage}{5cm}
          \begin{lstlisting}[gobble=8]
            typedef struct
            {
              int type;
              char *content;
            } t_string;
          \end{lstlisting}
        \end{minipage}
      \end{center}
    
      Man beachte, daß diese drei \lstinline{struct}-Datentypen
      trotz der absichtlichen Gemeinsamkeiten
      aus Sicht des C-Compilers nichts miteinander zu tun haben;
      sie sind voneinander vollkommen unabhängige Datentypen.
    
      Unser "`Array von Zahlen und Buchstaben"'
      erzeugen wir nun als Array von Zeigern auf den Basistyp,
      lassen die Zeiger aber in Wirklichkeit
      auf Variablen der abgeleiteten Datentypen zeigen:
    
      \begin{lstlisting}
        #define T_INTEGER 1
        #define T_STRING 2
    
        t_integer i = { T_INTEGER, 42 };
        t_string s = { T_STRING, "Hello, world!" };
    
        t_base *object[] = { (t_base *) &i, (t_base *) &s, NULL };
      \end{lstlisting}
      \begin{picture}(0,0.9)(0,-0.6)
        \color{red}
        \put(2.975,0.75){\mbox{$\underbrace{\rule{1.45cm}{0pt}}_{\shortstack{\strut explizite\\Typumwandlung}}$}}
      \end{picture}
    
      Damit der Compiler dies ohne Warnung akzeptiert,
      ist eine explizite Typumwandlung des jeweiligen Zeigers auf den abgeleiteten Typ
      in einen Zeiger auf den Basistyp erforderlich.
    
      Bei der Benutzung der abgeleiteten Typen
      erfolgt wieder eine explizite Typumwandlung, nur diesmal in umgekehrter Richtung:
    
      \begin{lstlisting}
        void print_object (t_base *this)
        {
          if (this->type == T_INTEGER)
            printf ("Integer: %d\n", ((t_integer *) this)->content);
          else if (this->type == T_STRING)
            printf ("String: \"%s\"\n", ((t_string *) this)->content);
        }
        ...
        for (int i = 0; object[i]; i++)
          print_object (object[i]);
      \end{lstlisting}
    
      (Beispiel-Programm: \gitfile{hp}{20161219}{objects-7.c})
    
      Die expliziten Typumwandlungen sind ein gravierender Nachteil dieser
      Vorgehensweise, denn sie schalten jegliche Überprüfung durch den Compiler aus.
      Der Programmierer ist komplett selbst dafür verantwortlich,
      daß die \lstinline{struct}-Datentypen gemeinsame Felder haben
      und daß der Zeiger jeweils auf den richtigen \lstinline{struct}-Typ zeigt.
    
      Die folgenden Abschnitte stellen Möglichkeiten vor,
      diese Nachteile abzumildern.
    
      \breath
    
      Die Verwendung von Zeigern auf "`normale"' Variable ist in der Praxis unüblich.
      Stattdessen reserviert man mit \lstinline{malloc()} Speicher für die Objekte.
      Es hat sich bewährt, für diesen Zweck eine spezielle Funktion,
      den sog.\ \newterm{Konstruktor\/} zu schreiben.
      Der Konstruktor kann den reservierten Speicher auch direkt
      mit sinnvollen Werten initialisieren, wodurch wieder eine Fehlerquelle wegfällt.
    
      \begin{lstlisting}
        t_integer *new_integer (int i)
        {
          t_integer *p = malloc (sizeof (t_integer));
          p->type = T_INTEGER;
          p->content = i;
          return p;
        }
    
        t_string *new_string (char *s)
        {
          t_string *p = malloc (sizeof (t_string));
          p->type = T_STRING;
          p->content = s;
          return p;
        }
        ...
    
        t_base *object[] = { (t_base *) new_integer (42),
                            (t_base *) new_string ("Hello, world!"),
                            NULL };
      \end{lstlisting}
    
      (Beispiel-Programm: \gitfile{hp}{20161219}{objects-8.c})
    
      \subsection{Unions}
    
      Explizite Typumwandlungen sind unsicher und nach Möglichkeit zu vermeiden.
      Eine Alternative ergibt sich durch Verwendung des Datentyps \lstinline{union}.
    
      Eine \lstinline{union} sieht formal wie ein \lstinline{struct} aus.
      Der Unterschied besteht darin, daß die Datenfelder eines \lstinline{struct}
      im Speicher \emph{hintereinander\/} liegen,
      wohingegen sich die Datenfelder einer \lstinline{union}
      \emph{denselben Speicherbereich teilen}.
    
      \begin{minipage}[b]{6cm}
        \begin{lstlisting}[gobble=6]
          #include <stdio.h>
          #include <stdint.h>
    
          typedef union
          {
            int8_t i;
            uint8_t u;
          } num8_t;
        \end{lstlisting}
      \end{minipage}%
      \begin{minipage}[b]{6cm}
        \begin{lstlisting}[gobble=6]
          int main (void)
          {
            num8_t n;
            n.i = -3;
            printf ("%d\n", n.u);
            return 0;
          }
        \end{lstlisting}
      \end{minipage}
    
      Die im o.\,a.\ Beispiel konstruierte \lstinline{union}
      spricht dieselbe Speicherzelle einerseits als \lstinline{int8_t} an
      und andererseits als \lstinline{uint8_t}.
      Das Beispiel-Programm (Datei: \gitfile{hp}{20161219}{unions-1.c})
      nutzt dies aus, um die negative Zahl \lstinline{-3}
      als positive 8-Bit-Zahl auszugeben (Berechnung des Zweierkomplements).
    
      \breath
    
      In der objektorientierten Programmierung in C
      nutzt man \lstinline{union}-Datentypen,
      um ohne explizite Typumwandlung denselben Speicherbereich
      als Objekte verschiedenen Typs zu interpretieren:
    
      \begin{minipage}[t]{3.5cm}
        \begin{lstlisting}[gobble=6]
    
    
          typedef struct
          {
            int type;
          } t_base;
        \end{lstlisting}
      \end{minipage}%
      \begin{minipage}[t]{3.5cm}
        \begin{lstlisting}[gobble=6]
    
          typedef struct
          {
            int type;
            int content;
          } t_integer;
        \end{lstlisting}
      \end{minipage}%
      \begin{minipage}[t]{3.5cm}
        \begin{lstlisting}[gobble=6]
    
          typedef struct
          {
            int type;
            char *content;
          } t_string;
        \end{lstlisting}
      \end{minipage}%
      \begin{minipage}[t]{4.5cm}
        \begin{lstlisting}[gobble=6]
          typedef union
          {
            t_base base;
            t_integer integer;
            t_string string;
          } t_object;
        \end{lstlisting}
      \end{minipage}
      \begin{center}
        \begin{minipage}{8.5cm}
          \begin{lstlisting}[gobble=8]
            if (this->base.type == T_INTEGER)
              printf ("Integer: %d\n", this->integer.content);
            else if (this->base.type == T_STRING)
              printf ("String: \"%s\"\n", this->string.content);
          \end{lstlisting}
        \end{minipage}
      \end{center}
    
      (Beispiel-Programm: \gitfile{hp}{20161219}{objects-9.c})
    
      Das Ansprechen falscher Speicherbereiche
      wird hierdurch zwar nicht völlig ausgeschlossen;
      der Compiler hat jedoch wesentlich mehr Möglichkeiten
      als bei expliziten Typumwandlungen,
      den Programmierer vor derartigen Fehlern zu bewahren.
    
      Das Problem, von Hand dafür sorgen zu müssen,
      daß die \lstinline{struct}-Datentypen zueinander passende Datenfelder enthalten,
      bleibt weiterhin bestehen.
    
      \breath
    
      Ein alternativer Ansatz besteht darin,
      nur die veränderlichen Eigenschaften der Objekte
      in einer \lstinline{union} zu speichern --
      siehe Aufgabe 1 (c) bis (e) in den Übungen vom 19.\,12.\,2016
      (Datei: \gitfile{hp}{20161219}{hp-uebung-20161219.pdf}).
    
      \goodbreak
    
      \subsection{Beispiel: graphische Benutzeroberfläche (GUI)}
    
      \href{http://www.gtk.org/}{GTK+} ist eine weit verbreitete Bibliothek
      zur Erstellung graphischer Benutzeroberflächen (Graphical User Interface -- GUI).
      Sie wurde ursprünglich
      für das Bildverarbeitungsprogramm \href{http://www.gimp.org}{GIMP} geschrieben,
      kommt aber u.\,a.\ auch im Web-Browser
      \href{http://www.mozilla.org}{Mozilla Firefox} zum Einsatz.
    
      GTK+ ist in C geschrieben und objektorientiert.
      Die Bibliothek verwendet intern einige der hier besprochenen Vorgehensweisen
      zur Realisierung objektorientierter Programmierung in C.
    
      Die Beispielprogramme \href{https://gitlab.cvh-server.de/pgerwinski/hp/tree/master/20161219}%
      {\file{gtk-1.c} bis \file{gtk-7.c}} demonstrieren,
      wie man mit Hilfe von GTK+ ein einfaches GUI-Programm schreibt,
      das graphische Objekte (Rechteck, Kreis, Dreieck) auf den Bildschirm zeichnet
      und sich nach dem Anklicken eines Buttons beendet.
    
      Die Bedienelemente der GUI sind in GTK+ Objekte.
      Hier ein paar Beispiele:
      \begin{itemize}
        \item
          \lstinline{GtkWidget} ist die Basisklasse für alle GUI-Elemente.
        \item
          \lstinline{GtkContainer} ist ein Nachfahre von \lstinline{GtkWidget}.\\
          Dieses Objekt kann, ähnlich einem Array, andere Objekte enthalten.
        \item
          \lstinline{GtkWindow} ist ein Fenster auf dem Bildschirm.\\
          Es ist ein Nachfahre von \lstinline{GtkContainer}
          und kann daher andere Objekte enthalten.
        \item
          \lstinline{GtkDrawingArea} ist ein rechteckiger Zeichenbereich auf dem Bildschirm.
        \item
          \lstinline{GtkButton} ist ein Bedienknopf.\\
          Durch Anklicken des Knopfes kann der Benutzer Aktionen auslösen.
      \end{itemize}
    
      Um bei einer abgeleiteten Klasse (z.\,B.\ \lstinline{GtkWindow})
      Eigenschaften der Basisklasse (z.\,B.\ \lstinline{GtkContainer}) nutzen zu können,
      verwendet GTK+ explizite Typumwandlungen, die in Präprozessor-Macros gekapselt sind.
      Um zum Beispiel ein \lstinline{GtkWindow}-Objekt \lstinline{window}
      als \lstinline{GtkContainer} ansprechen zu können,
      verwendet man \lstinline{GTK_CONTAINER (window)}.
    
      Ähnlich wie in OpenGL/GLUT erfolgt auch in GTK+ das Zeichnen
      sowie die Verarbeitung von Benutzereingaben (Tastatur, Maus)
      über Callbacks.
    
      In \href{https://gitlab.cvh-server.de/pgerwinski/hp/raw/master/20161219/hp-2016ws-p4.pdf}%
      {Praktikumsversuch 4} haben Sie selbst weitere Erfahrungen mit GTK+ gesammelt
      und gleichzeitig eine eigene Objekt-Hierarchie
      (für graphische Objekte: Rechteck, Kreis, Dreieck) programmiert.
    
      \subsection{Virtuelle Methoden}
    
      In großen Programmen wird die Anzahl der verwendeten Objekt-Datentypen
      schnell sehr groß. Eine Methode, die per \lstinline{if} unterscheiden muß,
      welche Art von Objekt sie gerade bearbeitet,
      enthält dann lange \lstinline{if}-Ketten
      und wird dadurch sehr unübersichtlich.
    
      \begin{lstlisting}
        void print_object (t_object *this)
        {
          if (this->base.type == T_INTEGER)
            printf ("Integer: %d\n", this->integer.content);
          else if (this->base.type == T_STRING)
            printf ("String: \"%s\"\n", this->string.content);
        }
      \end{lstlisting}
    
      Es wäre vorteilhaft, wenn alle Methoden,
      die sich auf einen bestimmten Objekttyp beziehen,
      auch nebeneinander im Quelltext stehen könnten,
      anstatt sich über den gesamten Quelltext zu verteilen
      (weil jede Funktion einen \lstinline{if}-Zweig für diesen Objekttyp hat).
    
      \begin{lstlisting}
        void print_integer (t_object *this)
        {
          printf ("Integer: %d\n", this->integer.content);
        }
    
        void print_string (t_object *this)
        {
          printf ("String: \"%s\"\n", this->string.content);
        }
      \end{lstlisting}
    
      Um dies zu realisieren, verwendet man \emph{Zeiger auf Funktionen}:
    
      \begin{lstlisting}
        typedef struct
        {
          void (*print) (union t_object *this);
        } t_base;
    
        typedef struct
        {
          void (*print) (union t_object *this);
          int content;
        } t_integer;
    
        typedef struct
        {
          void (*print) (union t_object *this);
          char *content;
        } t_string;
      \end{lstlisting}
    
      Um in C einen Zeiger auf eine Funktion zu deklarieren,
      deklariert man eine "`normale"' Funktion,
      deren "`Name"' die Gestalt \lstinline{(*print)} hat --
      mit dem vorangestellten Stern und den umschließenden Klammern.
      (Merkregel: Das, worauf \lstinline{print} zeigt -- also \lstinline{*print} --,
      ist eine Funktion.)
    
      Der Aufruf einer derartigen Funktion erfolgt
      über den im Objekt gespeicherten Zeiger:
    
      \begin{lstlisting}
        for (int i = 0; object[i]; i++)
          object[i]->print (object[i]);
      \end{lstlisting}
    
      Eine derartige Funktion, die für verschiedene Objekttypen existiert
      und bei deren Aufruf automatisch "`die passende"' Funktion ausgewählt wird,
      heißt \newterm{virtuelle Methode}.
    
      \breath
    
      Jeder Methode wird ein Zeiger \lstinline{t_object *this} auf das Objekt
      als Parameter mitgegeben.
    
      Bei der Deklaration der virtuellen Methode innerhalb des Objekt-Typs
      wird daher der Union-Typ \lstinline{t_object} bereits benötigt.
      Dieser kann jedoch erst später deklariert werden,
      wenn die darin enthaltenen Objekt-Typen bekannt sind.
    
      Um dieses Problem zu lösen, muß die \lstinline{union t_object}
      "`doppelt"' deklariert werden:
    
      \begin{lstlisting}
        typedef union t_object
        {
          t_base base;
          t_integer integer;
          t_string string;
        } t_object;
      \end{lstlisting}
    
      Dadurch daß \lstinline{t_object} auch oben,
      hinter dem Schlüsselwort \lstinline{union} steht,
      ist neben dem Datentyp \lstinline{t_object}
      auch ein Datentype \lstinline{union t_object}
      (in einem separaten Namensraum) bekannt.
      Derartig deklarierte Typen kann man \newterm{vorwärts-deklarieren\/}:
      Wenn man eine Zeile
      \begin{lstlisting}
        union t_object;
      \end{lstlisting}
      den anderen Deklarationen voranstellt,
      wissen diese, daß es später eine \lstinline{union t_object} geben wird.
      Zeiger auf diese -- noch unbekannte -- \lstinline{union}
      dürfen dann bereits in Deklarationen -- hier: Funktionsparameter --
      verwendet werden.
    
      \breath
    
      Das Beispiel-Programm \gitfile{hp}{20170109}{objects-12.c} illustriert,
      wie man virtuelle Methoden in C realisieren kann.
    
      In größeren Projekten ist es nicht effizient,
      in jeder einzelnen Objektinstanz (= Variable des Objekttyps)
      sämtliche Zeiger auf sämtliche virtuellen Methoden zu speichern.
      Stattdessen speichert man in der Objektinstanz
      lediglich einen Zeiger auf eine Tabelle von Zeigern auf die virtuellen Methoden,
      die sog.\ \newterm{virtuelle Methodentabelle} --
      siehe das Beispiel-Programm \gitfile{hp}{20170109}{objects-13.c}.
    
      \subsection{Einführung in C++}
    
      Objektorientierte Programmierung in C ist sehr mühselig und fehleranfällig:
      Objekt-Datentypen müssen manuell so abgeglichen werden,
      daß sie in ihren ersten Datenfeldern übereinstimmen,
      Konstruktoren müssen manuell erstellt werden, usw.
    
      Um diese Probleme zu beheben, wurden neue Computersprachen entwickelt,
      die objektorientierte Programmierung durch neue Sprachelemente unterstützen.
      Die objektorientierte Weiterentwicklung von C ist C++.
      Andere bekannte objektorientierte Sprachen sind Java, Python, C\#, JavaScript,
      PHP, verschiedene Pascal-Dialekte und viele weitere.
    
      Das Beispiel-Programm \gitfile{hp}{20170109}{objects-14.cpp}
      ist eine direkte Übersetzung von \gitfile{hp}{20170109}{objects-12.c} nach C++.
      In C++ kümmert sich der Compiler um die Vererbung zwischen den Objekt-Datentypen,
      um die Verwaltung der Zeiger auf virtuelle Methoden,
      um korrekte Konstruktoren und um vieles mehr.
      Auch die Übergabe des Objekt-Zeigers \lstinline{this} an Methoden
      erfolgt in C++ automatisch: Aus \lstinline{object[i]->base.print (object[i]);}
      wird \lstinline{object[i]->print ();}.
    
      Dadurch daß der Compiler viele Aufgaben übernimmt,
      die der Programmierer ansonsten manuell abarbeiten müßte,
      wird der Quelltext kürzer und weniger fehleranfällig.
    
      \section{Datenstrukturen}
    
      \subsection{Stack und FIFO}
    
      Eine häufige Situation beim Programmieren ist,
      daß man ein Array für eine gewisse Maximalmenge von Einträgen anlegt,
      aber nur zum Teil nutzt.
    
      Einem derartigen Array ein Element hinzuzufügen, ist einfach:
      Man erhöht die Variable, die die Auslastung des Arrays speichert.
      Ebenso einfach ist das Entfernen des zuletzt eingefügten Elements:
      Man erniedrigt die Variable, die die Auslastung des Arrays speichert.
    
      "`Einfach"' bedeutet hier, daß die benötigte Rechenzeit gering ist.
      Genaugenommen ist die Rechenzeit immer gleich groß,
      egal wie viele Elemente sich bereits im Array befinden.
      Die Komplexität (Landau-Symbol) der Operation,
      am Ende des Arrays ein Element einzufügen oder zu entfernen,
      ist $\mathcal{O}(1)$.
    
      Eine derartige Struktur eignet sich gut,
      um Elemente in der Reihenfolge des Eintreffens zu speichern,
      sie aber in \emph{umgekehrter\/} Reihenfolge wieder abzuarbeiten.
      Man "`stapelt"' gewissermaßen die Elemente in dem Array.
      Aus diesem Grunde heißt diese Struktur \newterm{Stack\/} (engl.: \emph{Stapel})
      oder \newterm{LIFO\/} für \emph{last in, first out}.
    
      Andere Operationen -- z.\,B.\ das Einfügen oder Löschen von Elementen
      in der Mitte -- sind aufwendiger, da man die im Array befindlichen Elemente
      in einer Schleife beiseiteschieben muß.
      Die Rechenzeit ist proportional zur Anzahl der Elemente,
      die sich bereits im Array befinden: $\mathcal{O}(n)$.
    
      Das Suchen in einem bereits sortieren Array ist hingegen in $\mathcal{O}(\log n)$
      möglich: Man beginnt die Suche in der Mitte und prüft,
      ob sich das gesuchte Element in der unteren oder in der oberen Hälfte befindet.
      In der ermittelten Hälfte beginnt man die Suche wieder in der Mitte --
      so lange, bis man nur noch ein einzelnes Element vor sich hat.
    
      Das Beispiel-Programm \gitfile{hp}{20170116}{stack-11.c} illustriert,
      wie man einen Stack mit den o.\,g.\ Funktionalitäten implementieren kann.
    
      \breath
    
      Eine weitere wichtige Situation ist,
      daß man anfallende Daten zwischenspeichern
      und \emph{in derselben Reihenfolge\/} wieder abarbeiten möchte.
      Eine Struktur, die dies ermöglicht, heißt \newterm{FIFO\/}
      für \emph{first in, first out}.
    
      Um einen FIFO zu realisieren, verwendet man nicht eine einzelne Variable,
      die den genutzten Teil des Arrays speichert, sondern zwei:
      Ein Schreib-Index markiert, an welcher Stelle Platz
      für das nächste einzufügende Element ist;
      ein Lese-Index markiert das zuerst eingefügte Element.
      Beide Indizes werden bei Verwendung hochgezählt.
      Wenn sie gleich sind, ist der FIFO leer.
    
      Der entscheidende Trick: Wenn eine der beiden Indexvariablen
      das Ende des Arrays erreicht, wird sie wieder auf 0 gesetzt.
      Die beiden Indexvariablen arbeiten also \emph{ringförmig\/}; 
      der FIFO wird durch einen \newterm{Ringpuffer\/} realisiert.
    
      Beispiel-Programm: \gitfile{hp}{20170116}{fifo-8.c}
    
      \subsection{Verkettete Listen}
    
      In Arrays ist das Einfügen in der Mitte sehr aufwendig ($\mathcal{O}(n)$).
      Um das Einfügen zu vereinfachen, hat man sich die folgende Struktur überlegt:
    
      \begin{itemize}
        \item
          Jeder Datensatz ist ein \lstinline{struct},
          der zusätzlich zum eigentlichen Inhalt noch einen Zeiger
          auf das nächste Element enthält.
        \item
          Beim letzten Element zeigt der Zeiger auf \lstinline{NULL}.
        \item
          Eine Variable (z.\,B.\ \lstinline{first}) zeigt auf das erste Element.
        \item
          Wenn die Liste leer ist, zeigt bereits die \lstinline{first}-Variable
          auf \lstinline{NULL}.
      \end{itemize}
    
      \begin{quote}
        \begin{tikzpicture}
          \color{blendedblue}
          \node(first) at (0,0.5) {first};
          \node[shape=rectangle,draw,line width=1pt](3) at (1,2) {3};
          \node[shape=rectangle,draw,line width=1pt](7) at (3,2) {7};
          \node[shape=rectangle,draw,line width=1pt](137) at (5,2) {137};
          \node(NULL) at (7,2) {NULL};
          \draw[-latex](first)--(3);
          \draw[-latex](3)--(7);
          \draw[-latex](7)--(137);
          \draw[-latex](137)--(NULL);
        \end{tikzpicture}
      \end{quote}
    
      Eine derartige Struktur heißt eine \newterm{(einfach) verkettete Liste}.
    
      Wenn nun ein zusätzliches Element in die Liste eingefügt werden soll,
      geschieht dies durch "`Umbiegen"' der Zeiger,
      die auf das jeweils nächste Element zeigen:
    
      \begin{quote}
        \begin{tikzpicture}
          \color{blendedblue}
          \node(first) at (0,0.5) {first};
          \node[shape=rectangle,draw,line width=1pt](3) at (1,2) {3};
          \node[shape=rectangle,draw,line width=1pt](5) at (2,1) {5};
          \node[shape=rectangle,draw,line width=1pt](7) at (3,2) {7};
          \node[shape=rectangle,draw,line width=1pt](137) at (5,2) {137};
          \node(NULL) at (7,2) {NULL};
          \draw[-latex](first)--(3);
          \draw[-latex](3) to[out=0] (5);
          \draw[-latex](5) to[in=180] (7);
          \draw[-latex](7)--(137);
          \draw[-latex](137)--(NULL);
        \end{tikzpicture}
      \end{quote}
    
      Unabhängig von der Gesamtzahl der Elemente,
      die sich bereits in der Liste befinden,
      müssen für das Einfügen eines Elements genau 2 Zeiger neu gesetzt werden.
      Der Aufwand für das Einfügen beträgt somit $\mathcal{O}(1)$.
    
      Diesem Vorteil steht der Nachteil gegenüber,
      daß es bei einer verketteten Liste nicht mehr möglich ist,
      "`einfach so"' auf das Element mit einem bekannten Index zuzugreifen;
      dies kann nun nur noch über eine Schleife geschehen.
      Während bei einem Array der wahlfreie Zugriff in $\mathcal{O}(1)$ möglich ist,
      geschieht dies bei einer verketteten Liste in $\mathcal{O}(n)$.
    
      Als Konsequenz ist auch das Suchen in $\mathcal{O}(\log n)$ nicht mehr möglich;
      auch dies erfordert nun $\mathcal{O}(n)$.
    
      \subsection{Bäume}
    
      Für datenintensive Anwendungen -- insbesondere Datenbanken --
      ist es wünschenswert, \emph{sowohl\/} den wahlfreien Zugriff
      \emph{als auch\/} das Einfügen in der Mitte \emph{als auch\/}
      das Suchen und das sortierte Einfügen möglichst effizient zu realisieren.
    
      Dies geschieht über rekursive Datenstrukturen, sog.\ \newterm{Bäume}.
    
      \breath
    
      Wie bei einer verketteten Liste sind die Elemente -- die \newterm{Knoten\/} --
      eines Baums \lstinline{struct}-Variable.
      Zusätzlich zum eigentlichen Inhalt speichert man darin noch Zeiger
      auf größere bzw.\ kleinere Elemente.
    
      Im einfachsten Fall enthält jeder Knoten genau einen Inhalt
      und jeweils einen Zeiger auf kleinere bzw.\ größere Elemente:
    
      \begin{lstlisting}
        typedef struct node
        {
          int content;
          struct node *left, *right;
        } node;
      \end{lstlisting}
    
      Ein aus derartigen Knoten aufgebauter Baum
      verzweigt sich an jedem Knoten in jeweils zwei Teilbäume
      und heißt daher \newterm{binärer Baum}.
    
      Die Struktur emöglicht es,
      jeweils "`zwischen"' zwei bereits eingefügten Knoten noch weitere einzufügen.
      Wenn in einen derartigen sortierten binären Baum nacheinander die Zahlen
      7, 3, 137 und 5 eingefügt werden, ergibt sich das folgende Bild:
    
      \begin{quote}
        \begin{tikzpicture}
          \color{blendedblue}
          \node(root) at (0,0) {\lstinline{node *root;}};
          \node[shape=rectangle,draw,line width=1pt](7) at (0,-1.5) {7};
          \draw[-latex](root)--(7);
          \node[shape=rectangle,draw,line width=1pt](137) at (2,-3) {137};
          \draw[-latex](7)--(137);
          \node(137_left) at (1,-4.5) {\lstinline{NULL}};
          \node(137_right) at (3,-4.5) {\lstinline{NULL}};
          \draw[-latex](137)--(137_left);
          \draw[-latex](137)--(137_right);
          \node[shape=rectangle,draw,line width=1pt](3) at (-2,-3) {3};
          \draw[-latex](7)--(3);
          \node(3_left) at (-3,-4.5) {\lstinline{NULL}};
          \draw[-latex](3)--(3_left);
          \node[shape=rectangle,draw,line width=1pt](5) at (-1,-4.5) {5};
          \draw[-latex](3)--(5);
          \node(5_left) at (-2,-6) {\lstinline{NULL}};
          \node(5_right) at (0,-6) {\lstinline{NULL}};
          \draw[-latex](5)--(5_left);
          \draw[-latex](5)--(5_right);
        \end{tikzpicture}
      \end{quote}
    
      Sowohl das Einfügen als auch die Ausgabe und die Suche
      erfolgen in Bäumen \emph{rekursiv}.
      Der Rechenaufwand hängt dabei von der Rekursionstiefe,
      also von der "`Tiefe"' des Baums ab.
      Da die Tiefe mit der maximal möglichen Anzahl der Knoten logarithmisch wächst,
      ist Einfügen und Suchen in $\mathcal{O}(\log n)$ möglich.
      Dies ist ein Kompromiß zwischen den Verhalten eines Arrays
      (Einfügen in $\mathcal{O}(n)$, Suchen in $\mathcal{O}(\log n)$)
      und dem einer verketteten Liste (Einfügen in $\mathcal{O}(1)$,
      Suchen in $\mathcal{O}(n)$).
      Ein sortiertes Einfügen in einen Baum
      ermöglicht eine Sortierung in $\mathcal{O}(n\log n)$.
    
      Dies funktioniert nur, wenn die Tiefe des Baums tatsächlich nur logarithmisch
      mit der Anzahl der Knoten wächst.
      Wenn man in dem oben beschriebenen einfachen Fall eines binären Baums
      die Elemente in bereits sortierter Reihenfolge einfügt,
      entartet der Baum zu einer verketteten Liste.
      Suchen ist dann nur noch in $\mathcal{O}(n)$ möglich
      und Sortieren in $\mathcal{O}(n^2)$.
    
      Um dies zu vermeiden, wurden teils aufwendige Strategien entwickelt,
      den Baum jederzeit \newterm{balanciert},
      d.\,h.\ in logarithmischer Tiefe zu halten.
      Derartige \newterm{balancierte Bäume\/} finden Verwendung
      in realen Datenbank-Programmen.
    
    \end{document}