Lehrreiche C-Programme zum herunterladen!

Hier werden ein paar lehrreiche C-Programme veröffentlicht, die möglicherweise interessanten Code enthalten. Es sind reine Demonstrationen zum Herunterladen.
Achtung: Die C-Programme wurden mit Turbo-C unter DOS erstellt und haben daher ggf. die falsche Code-Page, wenn man sie einfach kopiert.

Ein Funktionsplotter

Dieses Programm demonstriert die Rekurision ebenfalls eindrucksvoll und stellt zudem einen Parser für mathematische Funktionen bereit. Im Ergebnis wird die Funktion dann in ein Koordinatensystem geplottet. Das, was heute Google "mal eben so" anbietet, war damals nur durch eigene Entwicklung möglich. Wir hatten ja nix...

Downloads:
Graphische Ausgabe von Funktionen
[Compilat als ZIP]
Der Funktionsparser als #include

Die Infix- und die Postfix-Form

Dieses Programm demonstriert, wie ein Compiler einen mathematischen Ausdruck verarbeiten würde. Er bringt ihn zu erst in eine für ihn leserliche Form und wandelt diese in Assemblerbefehle um.

Dabei simuliert dieses Programm die Aufgabe äußerst stur und ohne weitreichende Syntaxüberprüfung, die eigentlich von einem vorgeschalteten Scanner erledigt werden müßte.

Um die Reaktionen auf Operatoren bequem zu erledigen, wird als konstante eine Matrix definiert. Dieses Array "action" legt fest, wie die im Hauptteil befindliche switch-Anweisung reagieren soll. Die Variable "translat" dient nur dazu, den Index in das Array "action" zu errechnen, da dies die Position des Zeichens im String "translat" ist.

Das Programm simuliert zudem den Datentyp STACK, der hier als ein Array mit 256 Elementen definiert wird. Als Pointer auf das oberste LEERE Element dient die Variable stk_count. Zur Stackmanipulation verwende ich jeweils Routinen, obwohl zwei davon auch ebenso gut als #define-Anweisung hätten definiert werden können, da es sich schlicht um dir Rückgabe des obersten Elementes handelt, was in einem Befehl erledigt werden kann.

Das ausgeben der Assemblerbefehle funktioniert nun recht einfach, da man sich keinen Kopf mehr um die Reihenfolge der Operatoren machen muss. Es ist bereits in der Postfixform festgehalten, was auf den Stapel muss, und was dann damit passieren muss. Die Routine erklärt sich sicher von selbst.

Downloads:
Die Infix- und Postfixform
[Compilat]

Rekursion vs. Iteration - Beispiele Fakultät und binäres Suchen

Als Beispiel zum Vergleich der rekursiven und iterativen Lösung eines Problemes.

Jedes Problem läßt sich sowohl iterativ, wie auch rekursiv lösen, wobei jeweils eine davon die elegantere und einfachere ist. Die Rekursion kann man sehr gut verwenden, wenn ein Teilproblem im Prinzip auch ein Gesamtproblem sein kann und damit mit der selben Funktion zu lösen ist. Das Standardbeispiel hierzu ist die Fakultätsberechnung.
Denn:
5! = 5 * {4! = 4 * [3! = 3 * (2! = 2 * 1)]}
Die Klammern deuten auf den neuen Aufruf. Es ist sicher einleuchtend, daß 5! als 5*4! zu schreiben ist. 4! stellt aber wieder das gleiche Problem dar und ist daher ganz genau so zu lösen, nämlich als 4*3!. Und so weiter. Allgemein also:
n! = n * (n-1)!, gell?

Wenn man nun im ersten Moment vernachlässigt, daß es sich ja um die selbe Funktion handelt, die man aufruft, ist das Problem sicher nicht mehr ganz so groß.

Das wichtigste bei der Rekursion ist grundsätzlich die Abruchsbedingung. In diesem Fall ist man bei der 2 schließlich fertig, da man 2! ja kennt. Man kann auch noch einen Schritt weiter gehen und statt 2! auch 1! mit einschließen. Da 0!(=1) auch definiert ist, sollte man hier ebenfalls rücksicht drauf nehmen. Das Programm ist dem entsprechend angelegt worden. Wenn man aber auf die ein oder andere Sicherheitsabfrage (negative Werte) verzichtet, wird das Programm noch etwas kürzer.

Ich persönlich empfinde die rekursive Lösung eines Problems (sofern es eine sinnvolle gibt) als ausgesprochen elegant und zudem bestechend, da keine Schleifenkonstrukte das wesentliche verkleiden. Es ist aber jedem selbst überlassen, in welchen Bahnen er lieber denkt. Der iterative Typ, der lieber alle Operationen in Schleifen baut und vor allem die Kontrolle über zu speichernde Variablen selber haben will, ist mit der Rekursion schlecht bedient. Ich kann aber nur jedem raten, sich mit beiden Algorithmen anzufreunden, denn das binäre Suchen ist stark an das durchsuchen von binären Bäumen angelehnt, was sehr schnell in einem rekursiven Algorithmus zu lösen ist. Eine vergleichbare iterative Lösung wäre sicherlich wesentlich schwieriger zu gestalten, vor allem unter der Prämisse, sortiert auszugeben...

Downloads:
Fakultät und Binäres Suchen (rekursiv und iterativ)
[Compilat]

Stack- und Listendemonstration

Dieses Programm ist so gestrickt, daß es jegliche Art von Datentypen verdauen kann, wie die beiden Testprogramme auch zeigen. Erst wird sowohl beim Stack, wie auch bei der Liste erst ein einfacher Integer eingestellt und wieder ausgelesen, dann aber auch der Datentyp Structur.

Das Programm erläutert sich soweit selbst. Sollten unbekannte Funktionen (sizeof, sprintf, etc...) so ist bitte die Hilfestellung der intigrierten Entwicklungsumgebung zu konsultieren...

Wie gefordert, werden Over- und Underflows, also der Versuch, zu viele Elemente einzustellem oder auszulesen, abgefangen und mit einer Meldung bestraft.

Ebenso ist zu sehen, daß bei dem Stack die Zahlen logischerweise in umgekehrter Reihenfolge nach dem LiFo-Prinzip ausgelesen werden, wogegen bei der Liste nach dem FiFo-Prinzip diese Umkehrung selbstverständlich nicht auftritt.

Da sich Ringlisten vornehmlich bei der Datenauslesung (z.B. Spooler, Tastaturpuffer, o.ä.) finden, ist das Testprogramm nicht ganz am Einsatzgebiet einer Liste, aber es wäre nicht leicht, variables ein- und auslesen zu demonstrieren. Ich denke, es genügt auch so. Wer immer Lust verspürt, diese Anwendung unter realeren Bedingungen zu testen, sei dazu aufgefordert. Dazu ist das ganze hier ja veröffentlicht. Dazu muss einfach die Routine list_demo() verändert werden. Dabei ist darauf zu achten, daß bei dieser variablen Konstruktion eine Listeninitialisierung erfolgen muss, ebenso wie ein Freigeben.

Es wäre ebenfalls noch schön, dazu zu sorgen, daß mehrere Listen nebeneinander mit den gleichen Funktionen verarbeitet werden könnten. Dazu müßten z.B. die Pointer zu Arrays erweitert werden und die Listenfunktion jeweils mit einem Index angesprochen werden, damit klar wird, auf welche Liste man sich bezieht, ähnlich den Dateihandle.

Viel Spaß beim experimentieren...

Downloads:
Stacks und Listen und doppelt verkettete Liste
[Compilat Stack] und [Compilat Liste]