1. Hauptnavigation
  2. Navigation des Hauptbereiches
  3. Inhalt der Seite
  1. HTW Dresden
  2. Fakultät Informatik/Mathematik
  3. Homepage
  4. Programmierung I

Programmierung I


Die Lehrveranstaltung "Programmierung I" findet  im 1. Semester des Studiengangs Medieninformatik im Umfang von 2/1/2 SWS statt. Es werden keine Programmierkenntnisse vorausgesetzt.
Die Lehrveranstaltung wird mit Hilfe von zwei Teilleistungen bewertet, wobei beide bestanden werden müssen. Im Laufe des Semesters ist ein komplexes Softwareprojekt zu entwickeln (APL-Programmierübung, Beleg, Wichtung 30%). Die Aufgabenstellung und der Bewertungsmaßstab werden im Rahmen der Lehrveranstaltung bekanntgegeben. Im Prüfungszeitraum findet eine schriftliche Prüfung statt (120 Minuten, Wichtung 70%).



Themen der Lehrveranstaltung:

  • Was sind Programmiersprachen?
  • Datentypen, Konstanten, Variablen
  • Funktionen
  • Formatierte Ein- und Ausgabe
  • Kontrollstrukturen
  • Operatoren
  • Arrays und Strings
  • Zeiger
  • strukturierte Datentypen
  • Arbeit mit Dateien
  • symbolische Konstanten und Makros
  • noch einmal Funktionen
  • Datentypumwandlung
  • Bitoperationen
  • Aufzählungstypen
  • Speicherklassen
  • dynamische Speicherverwaltung



Praktikumsaufgaben



Vorbemerkungen


Die vorliegenden Praktikumsaufgaben sollen dem Studenten helfen, das in der Vorlesung vermittelte Wissen zu festigen. Die Aufgaben lehnen sich an die durch Vorlesung und Übung besprochenen Stoffgebiete an. Es wurde Wert darauf gelegt, die Programmieraufgaben klein zu halten. Damit wird angestrebt, dass der Student möglichst viele verschiedene Programme pro Praktikumseinheit erstellen kann. Die Lösungen zu den Aufgaben wurden bewusst nicht mit in die Aufgabenstellung aufgenommen, um nicht von vornherein die Kreativität der eigenen Programmlösung zu lähmen. Es wird empfohlen, zur Lösung der Aufgaben die Lehrhefte "Einführung in die Programmiersprache C" und "Kurzbeschreibung ausgewählter C-Bibliotheksfunktionen" oder diverse C-Lehrbücher zu verwenden.Bitte versuchen Sie ANSI-C konforme Quelltexte zu schreiben. Um im MS Visual Studio entsprechende Sicherheitswarnungen bei ANSI-C Bibliotheksfunktionen zu unterdrücken, fügen Sie das folgende Compiler-Pragma ein:

#pragma warning (disable: 4996)

Um in der Debugger-Konsole des MS Visual Studio die Umlaute ohne korrekt dargestellt zu bekommen, schalten Sie bitte am Anfang der main()-Funktion die CodePage um:

system("chcp 1252 > NUL");




Einstieg und lexikale Grundlagen


Aufgabe 1:
Erstellen Sie ein C-Programm, das nacheinander die folgenden Zeichenkettenkonstanten auf dem Bildschirm ausgibt: 
	Eine Meinungsumfrage unter Löwen ergab:
	Die Mehrheit lehnt den Käfig ab,
	wünscht jedoch eine geregelte Verpflegung!
Beachten Sie den Zeilenumbruch nach jeder Zeile! Machen Sie sich mit dem Debugger vertraut, und schauen Sie sich die sequentielle schrittweise Abarbeitung Ihres Programms im Debugger an.
 
Aufgabe 2:
Das folgende Programm enthält mehrere syntaktische Fehler: 
	#inklude


	void main() {
		printf("Das Zukünftige ist viel zu unbestimmt,"\n)
		printf("um als präzise Handlungsmaxime zu dienen).
	}
Korrigieren Sie die Fehler und testen Sie die Lauffähigkeit des Programms.
 
Aufgabe 3:
Definieren Sie den Tag, den Monat und das Jahr Ihres Geburtstages als "konstante Variablen" vom Typ int und geben Sie den Satz: 
           Ich wurde am tt.mm.jjjj geboren.
auf dem Bildschirm aus.

Überlegen Sie sich nun, ob andere Datentypen für die Variablen besser geeignet sind.
 
Aufgabe 4:
Schreiben Sie ein Programm, dass mit Hilfe von Tabulatoren, möglicht wenigen Variablen :-) und 3 Ausgabeanweisungen folgende Tabelle auf dem Bildschirm ausgibt: 
	1 2 3 4
	2 4 6 8
	3 6 9 12
Lösen Sie die Aufgabe in mehreren Schritten und legen Sie sich für jeden Versionsschritt eine eigene Funktion an:
  • Version 1.0: Nutzen Sie 3 printf-Anweisungen und konstante Zahlenwerte für die Ausgabe.
  • Version 2.0: Nutzen Sie eine Variable für die zu berechnenden Zahlenwerte.

Zwischenaufgabe: Schauen Sie sich die Abarbeitung und den Wert der Variable im Debugger an.
  • Version 3.0: Schreiben Sie eine Funktion, die zur Ausgabe einer Zeile dient und als Parameter die Zeilennummer übergeben bekommt. Der return-Wert ist die um 1 erhöhte Zeilennummer.
 
Aufgabe 5:
Erweitern Sie das Programm aus Aufgabe 4 indem Sie sich zusätzlich die Gleitkommakonstante pi mit dem Wert 3.1415926 definieren, jeden Wert in der Tabelle vor seiner Ausgabe mit pi multiplizieren und das Ergebnis als Gleitkommazahl ebenfalls mit Tabulatoren und 3 Ausgabeanweisungen tabellarisch darstellen. Auch hier ist eine möglichst einfache Lösung anzustreben.


 

Datentypen, Variablendefinition, Ein- und Ausgabe


Aufgabe 1:
Schreiben Sie ein Programm, dass Sie nacheinander zur Eingabe von 2 Integerzahlen auffordert, die von Ihnen eingegebenen Zahlen auf zwei Variablen vom Typ int abspeichert und danach die Summe, die Differenz, das Produkt und den Quotienten ausgibt.
 
Aufgabe 2:
Ändern Sie das Programm aus Aufgabe 1, indem Sie Gleitkommazahlen für Eingabe und Ausgabe verwenden.
 
Aufgabe 3:
Erstellen Sie ein Programm, das eine Integerzahl einliest und dann sowohl von dieser als auch von ihren 4 direkten Nachfolgern die Quadratwurzel berechnet und zusammen mit der Zahl in einer kleinen Tabelle ausgibt. Verwenden Sie zur Berechnung die Funktion sqrt() der Standardbibliothek "math.h", die im Lehrheft beschrieben ist.
 
Aufgabe 4:
Schreiben Sie ein Programm, dass den n-ten Buchstaben des Alphabetes auf dem Bildschirm ausgibt, nachdem es Sie nach der Zahl n gefragt hat.
 
Aufgabe 5:
Lesen Sie mit nur einem scanf()-Funktionsaufruf Ihr Geburtstag auf 3 Variablen ein und geben Sie es zur Kontrolle noch einmal aus. Testen Sie Möglichkeiten der Fehlerbehandlung bei Falscheingaben durch den Nutzer.
 
Aufgabe 6:
Dividieren Sie zwei Integerzahlen, die Sie von der Tastatur eingelesen haben, einmal mit und einmal ohne erzwungene Typumwandlung zur Gleitkommazahl und speichern Sie das Ergebnis jeweils auf eine Variable vom Typ float. Geben Sie das Ergebnis aus und erklären sich die Abweichung der beiden Werte, wenn die eine Integerzahl nicht durch die andere teilbar ist.
 
Aufgabe 7:
Schreiben Sie ein Programm, das von Ihnen einen float-Wert einliest, von diesem Wert 1 subtrahiert und das Ergebnis als float-Wert wieder ausgibt. Geben Sie nach Abfrage durch das Programm den Wert 1.23456e10 ein. Welches Ergebnis erwarten Sie, wenn Ihr Programm eine Millionen mal die 1 von Ihrem Wert subtrahieren würde?



Ausdrücke, Operatoren und Anweisungen

 
Aufgabe 1: Würfel
Erstellen Sie ein Programm zur Berechnung von Eigenschaften eines Würfels, das bei gegebener (d.h. in Ihrem Fall einzugebender) Kantenlänge a
  • den Flächenumfang (=6a*a),
  • das Volumen (=a*a*a) und
  • die Länge der Raumdiagonale (=a*sqrt(3))
berechnet und ausgibt.
 
Aufgabe 2: Kreiszylinder
In Analogie zur vorangegangen Würfel-Aufgabe ist ein Programm für gerade Kreiszylinder zu schreiben, das bei gegebener (einzugebender) Höhe und Durchmesser
  • die Mantelfläche (=pi*d*h),
  • Oberfläche (=0.5pi*d*(d+2h)) und
  • das Volumen (=0.25*pi*d*d*h) berechnet und ausgibt.
 
Aufgabe 3: Einfache Werteberechnungen
Welchen Wert haben die folgenden arithmetischen Ausdrücke? 
      3/4   15%4   15/2.0   3+5%4   3*7%4
 
Aufgabe 4: Operatorprioritäten
Wie werden die Operanden und Operatoren im folgenden Ausdruck zusammengefasst? 
      x = -4 * ++i - 6 % 4
Setzen Sie entsprechende Klammern und überprüfen Sie, ob das Programm noch den gleichen Wert für x ermittelt.
 
Aufgabe 5: Fehlersuche
Bestimmen und erklären Sie sich die Bildschirmausgaben des nachstehenden Programms. 

      #include <stdio.h>

      void main() {
    	 int erg, a, b, c;
    	 int y=5;
    	 printf("Wert von 7||(y==0): %d\n",7||(y==0));
    	 printf("Wert von y: %d\n\n",y);
    	 a = b = c = 0;
    	 erg = ++a || ++b && ++c;
    	 printf("erg = %d, a = %d, b = %d, c = %d\n", erg, a, b, c);
    	 a = b = c = 0;
    	 erg = ++a && ++b || ++c;
    	 printf("erg = %d, a = %d, b = %d, c = %d\n", erg, a, b, c);
      }
Aufgabe 6: Logische Ausdrücke
Schreiben Sie ein Programm mit dessen Hilfe Sie für einer Integervariablen x=7 den Wert der folgenden logischen Ausdrücke berechnen und anzeigen können. Erklären Sie sich die ermittelten Ausgaben. 
      x < 9 && x >= -5
      !x && x >= 3
      x++ == 8 || x == 7
Aufgabe 7: Bitoperatoren
Erstellen Sie ein kurzes Programm, das folgende Tabelle erstellt. 
      z num hex  binär      z num hex  binär
    --------------------------------------------
      a  97  61  01100001 | A  65  41  01000001
      b  98  62  01100010 | B  66  42  01000010
      c  99  63  01100011 | C  67  43  01000011
      d 100  64  01100100 | D  68  44  01000100
      e 101  65  01100101 | E  69  45  01000101
      f 102  66  01100110 | F  70  46  01000110
      g 103  67  01100111 | G  71  47  01000111
      h 104  68  01101000 | H  72  48  01001000
      i 105  69  01101001 | I  73  49  01001001
      j 106  6a  01101010 | J  74  4a  01001010
      k 107  6b  01101011 | K  75  4b  01001011
      l 108  6c  01101100 | L  76  4c  01001100
      m 109  6d  01101101 | M  77  4d  01001101
      n 110  6e  01101110 | N  78  4e  01001110
      o 111  6f  01101111 | O  79  4f  01001111
      p 112  70  01110000 | P  80  50  01010000
      q 113  71  01110001 | Q  81  51  01010001
      r 114  72  01110010 | R  82  52  01010010
      s 115  73  01110011 | S  83  53  01010011
      t 116  74  01110100 | T  84  54  01010100
      u 117  75  01110101 | U  85  55  01010101
      v 118  76  01110110 | V  86  56  01010110
      w 119  77  01110111 | W  87  57  01010111
      x 120  78  01111000 | X  88  58  01011000
      y 121  79  01111001 | Y  89  59  01011001
      z 122  7a  01111010 | Z  90  5a  01011010
    --------------------------------------------
In der Tabelle wird für Groß- und Kleinbuchstaben jeweils die dezimale, hexadezimale und binäre Darstellung ausgegeben.

Aufgabe 8: Maximum
Schreiben Sie ein Programm, dass zwei int-Werte von der Tastatur einliest und mit Hilfe der if-Anweisung das Maximum dieser zwei Werte bestimmt und ausgibt. Sind beide Werte gleich, so ist auch dies zu erkennen.
Nutzen Sie nun den bedingten Operator zur Lösung des Problems.

Aufgabe 9: Noch einmal Maximum
Modifizieren Sie Ihr Programm aus der vorangegangen Aufgabe derart, dass das Programm nach der Ausgabe des Maximums den Benutzer fragt, ob weitere Werte zu bearbeiten sind, und ggf. wieder von vorn beginnt. Nutzen Sie zur Lösung zunächst die do-while-Schleife, dann die while-Schleife und zum Schluss die for-Schleife. Machen Sie sich die Unterschiede klar!

Aufgabe 10: Arithmetisches Mittel
Erstellen Sie ein Programm, das zyklisch in beliebiger Anzahl int-Werte einliest, dabei intern das arithmetische Mittel bildet und dieses zum Schluss ausgibt. Sie können den Nutzer am Anfang ihres Programms nach der Anzahl der einzulesenden Zahlen fragen oder die Eingabe mit einem Buchstaben (z.B. ‘q’) beenden lassen.
 
Aufgabe 11: Funktionstabellen
Schreiben Sie ein Programm, das auf Wunsch Funktionstabellen für (mindestens 3) trigonometrische Funktionen generieren kann. Der Nutzer soll dabei die Funktion, die untere und obere Schranke und die Schrittweite wählen können. Achten Sie auf eine übersichtliche Darstellung auf dem Bildschirm. Sind mehr Daten anzuzeigen, als auf dem Bildschirm passen, so ist der Bildschirm erst nach Tastendruck durch den Nutzer weiter zu scollen.
 
Aufgabe 12: Fibonacci-Zahlen
Die Fibonacci-Zahlen sind wie folgt definiert: 
	fib(0)=0;
	fib(1)=1;
	fib(i)=fib(i-1)+fib(i-2) für 2<=i<=n
Berechnen Sie mit Hilfe der oben genannten rekusiven Definition zyklisch die ersten n Fibonacci-Zahlen (eine Zahl n>=0 ist vom Nutzer zu erfragen). Erhöhen Sie die Effizienz Ihres Programms, indem Sie anstatt der Rekursion mit einer for-Schleife arbeiten.
 
Aufgabe 13: Das "kleine Einmaleins"
Schreiben Sie ein C-Programm, welches das "kleine Einmaleins" in einer Tabelle (wie unten angegeben) vollständig auf dem Bildschirm ausgibt. Nutzen Sie hierzu mehrere for-Anweisungen.
    ******* DAS KLEINE EINMALEINS *******

          ___ 1___ 2___ 3___ 4___ 5___ 6___ 7___ 8___ 9___10
      1 |     1    2    3    4    5    6    7    8    9   10
      2 |     2    4    6    8   10   12   14   16   18   20
      3 |     3    6    9   12   15   18   21   24   27   30
      4 |     4    8   12   16   20   24   28   32   36   40
      5 |     5   10   15   20   25   30   35   40   45   50
      6 |     6   12   18   24   30   36   42   48   54   60
      7 |     7   14   21   28   35   42   49   56   63   70
      8 |     8   16   24   32   40   48   56   64   72   80
      9 |     9   18   27   36   45   54   63   72   81   90
     10 |    10   20   30   40   50   60   70   80   90  100
 
Aufgabe 14: ein einfaches Zahlenspiel
Der Computer berechnet sich eine Zufallszahl zwischen 1 und 15, die der Spieler (=Benutzer) erraten soll.

Der Spieler hat insgesamt drei Versuche. Nach jedem falschen Versuch gibt der Computer an, ob die angegebene Zahl zu klein oder zu groß ist. Ist auch der 3. Versuch erfolglos, wird die gesuchte Zahl ausgegeben. Der Spieler hat gewonnen, wenn er innerhalb der 3 Versuche, die Zahl errät. Er soll das Spiel beliebig oft wiederholen können.

Hinweis: Zur Initialisierung des Zufallszahlengenerators verwenden Sie die Systemzeit.  
	#include <time.h>   /* Prototyp von time()                */
	#include <stdlib.h> /* Prototypen von srand() und rand()  */
	...
	srand(time(NULL));        /* Initialisierung mit der Systemzeit */
Die Zufallszahl selbst erhalten Sie in ANSI-C unter Nutzung der Funktion rand() (siehe Lehrheft, Abschnitt 12.2).



Zeiger und Arrays


Aufgabe 1: Arrayrotation
Gegeben ist ein eindimensionales Array arr mit n Elementen vom Typ int. Dieses Array ist in der main()-Funktion anzulegen und zu initialisieren. Schreiben Sie zunächst eine Funktion, die der Ausgabe von int-Arrays auf dem Bildschirm dient. Welche Parameter benötigen Sie, um solche Arrays an die Funktion zu übergeben?
  1. Führen Sie eine einfache Rotation des Arrays nach links durch, d.h. das letzte Element bekommt den Wert des ersten Elementes zugewiesen, das erste den des zweiten, das zweite den des dritten usw. Kein Wert darf dabei verloren gehen.
  2. Führen Sie eine einfache Rotation des Arrays nach rechts durch, d.h. das erste Element bekommt den Wert des n-ten Elementes zugewiesen, das zweite den des ersten usw.
  3. Verallgemeinern Sie Ihr Programm dahingehend, dass eine m-fache Rotation (m<n) in eine beliebige Richtung des Arrays möglich ist. Die Rotationsrichtung und die Rotationsweite m sind vom Nutzer abzufragen.
Gestalten Sie Ihr Programm robust. Nutzen Sie die bisher erarbeiteten Eingabe- und Menu-Funktionen.

Aufgabe 2: Einfügen und Löschen von Arrayelementen
Gegeben ist ein eindimensionales Array der Länge n mit m Elementen (m<n) vom Typ int.
  1. Schreiben Sie ein Programm, das das k-te Element (k<=m) aus dem Array entfernt und die entstandene Lücke durch heranziehen der restlichen Arrayelemente schließt.
  2. Erweitern Sie Ihr Programm dahingehend, dass hinter dem k-ten Element (k<=m) ein neuer int-Wert eingefügt werden kann.
Das Programm gibt jeweils den Arrayinhalt auf dem Bildschirm aus, fragt den Nutzer, ob ein Element einzufügen oder zu löschen ist und welches Element betroffen ist. Testen Sie jeweils die Konsistenz der Nutzereingaben (m<n; k<=m). Überlegen Sie sich, ob ggf. die bereits implementierte Arrayrotation genutzt werden kann.

Aufgabe 3: Entfernen von Duplikaten
Gegeben ist ein eindimensionales Array mit n Elementen vom Typ int, der bei der Variablendefinition initialisiert wird. Schreiben Sie ein Programm, das alle Duplikate aus dem Array entfernt, wenn
  1. das Array aufsteigend sortiert ist,
  2. das Array unsortiert vorliegt.

Aufgabe 4: Häufigkeit von Arrayelementen
In einem eindimensionalen Array sind n Elemente vom Typ int gespeichert. Schreiben Sie ein Programm, das das häufigste Element und dessen absolute Häufigkeit ermittelt, unter der Voraussetzung,
  1. dass das Array bereits aufsteigend sortiert vorliegt (bei gleichen Häufigkeiten das kleinste Element),
  2. das Array unsortiert vorliegt (bei gleicher Häufigkeit das zuerst aufgetretene Element).

Aufgabe 5: k-kleinstes Element
Gegeben ist ein unsortiertes eindimensionales Array mit n Elementen vom Typ int. Erstellen Sie ein Programm, das das k-kleinste Element ermittelt, wobei 1<=k<=n gilt und das Array
  1. keine Duplikate enthält,
  2. Duplikate enthalten darf.
Beispiel: In einem Array mit dem Inhalt 4 1 5 3 8 7 6 müsste die Suche nach dem zweitkleinsten Element den Wert 3 liefern.

Aufgabe 6: monotone Teilfolgen
Gegeben ist ein unsortiertes eindimensionales Array, dessen n Elemente vom Typ int vom Nutzer einzugeben sind und voneinander unterschiedliche Werte besitzen. Gesucht ist die längste monoton steigende Teilfolge des Arrays. Die Indizes des ersten und letzten Elementes sowie die gesuchte Teilfolge selbst sind auf dem Bildschirm auszugeben.

Beispiel: Für eine Arraybelegung mit 2 9 3 8 10 11 4 13 6 sind als Indizes 2 und 5 sowie als Teilfolge 3 8 10 11 zu ermitteln und auszugeben.


Aufgabe 7: Geldautomat
Programmieren Sie einen Geldautomat unter Nutzung einer Struktur, die alle für den Geldautomat relevanten Werte enthält:
  1. Ein Array mit 8 int-Elementen: Das erste Element gibt an, wieviel 2 Euro Stücke noch vorhanden sind, das zweite Element ist ein Zähler für 1 Euro-Stücke usw. Jeder Münztyp ist in der entsprechenden Anzahl vorrätig (Initialisierung des Arrays bei der Strukturdefinition, z.B. jeweils mit 20 Münzen).
  2. Ein zweites Array mit 8 int-Elementen: Die Elemente geben den Wert der jeweiligen Münze in Cent an (200, 100, 50, 20, 10, 5, 2, 1).
  3. Ein Array mit 8 Zeigern auf Zeichenketten: Die Elemente bezeichnen die Münzen ("2 Euro Münze", "1 Euro Münze", "50 Cent Münze", ...) und dienen der Kommunikation mit dem Nutzer, z.B.

    Es werden ausgezahlt:
          2 Stück der 2 Euro Münze,
          3 Stück der 10 Cent Münze,
          ...
  4. Eine int-Variable, deren Wert der Summe aller "ausgezahlten" Geldbeträge entspricht.
Das Auszahlungsproblem besteht hier darin, mit den vorrätigen Münzen einen gegebenen Betrag zusammenzustellen, per Text auszugeben (siehe oben) und die Daten der Strukturvariablen aktuell zu halten. Steuern Sie den Geldautomat über ein kleines Menü, das die Darstellung des aktuellen Geldautomateninhalts und das "Auszahlen" ermöglicht.

Aufgabe 8: Magisches Quadrat
Gegeben sei ein zweidimensionales Array von int-Werten mit n Zeilen und n Spalten.
  1. Die konkrete Wertebelegung des Arrays ist vom Nutzer nach dem Programmstart einzulesen ist. Überprüfen Sie in Ihrem Programm, ob die eingelesenen Werte ein Magisches Quadrat bilden, d.h. ob die Summen der int-Werte in jeder Spalte, in jeder Zeile und in den Hauptdiagonalen gleich groß sind.
  2. Berechnen Sie in Ihrem Programm eine Arraybelegung, die für m*m-Elemente (m<=n) ein Magisches Quadrat ergibt. Der Wert m ist vom Nutzer einzulesen.

Aufgabe 9: "Video on demand"
Wir nehmen an, dass eine digitale Videothek n Filme an seine Kunden zu übertragen habe und hierfür m Datenkanäle zur Verfügung stehen. Um die Aufgabe praxisrelevant und interessant zu gestalten, nehmen wir an, dass m<n gelte. In einem entsprechend initialisierten Übertragungsarray transmit sind die zur Übertragung der Filme notwendigen Zeiten abgespeichert, d.h. der Film i (i<=n) benötigt zur Übertragung die Zeit transmit[i]. Berechnen Sie mit Ihrem Programm, welche Filme auf welchen Datenkanälen in welcher Reihenfolge zu übertragen sind, so dass die Gesamtübertragungszeit aller Filme minimiert wird.

Aufgabe 10: Life
Das Bionikspiel "Life" wurde 1970 vom britischen Mathematiker J.H. Conway erfunden. Wir betrachten ein zweidimensionales Array mit n*m Elementen des Typs char. Enthält eine Zelle ein Leerzeichen, dann ist sie "tot". Es handelt sich um eine "lebende" Zelle, wenn in ihr ein "*" eingetragen ist. Mehrere benachbarte lebende Zellen bilden einen Organismus. Eine Zelle ist von 8 Nachbarzellen umgeben, wenn sie sich nicht gerade am Rand der Matrix befinden. Um die Gestalt eines Organismus in der nächsten Generation zu ermitteln, gelten folgende Regeln, die auf die gesamte Matrix gleichzeitig anzuwenden sind:
  • Besitzt eine lebende Zelle 0, 1 oder mehr als 3 lebende Nachbarzellen, stirbt sie an Vereinsamung oder Überbevölkerung.
  • Besitzt eine lebende Zelle 2 oder 3 lebende Nachbarzellen, dann existiert sie in der nächsten Generation weiter.
  • Ist eine tote Zelle von genau 3 lebenden Zellen umgeben, dann entsteht aus ihr eine neue lebende Zelle.
Schreiben Sie ein Programm, mit dem Sie einen Organismus eingeben und (schrittweise) eine beliebige Anzahl von Generationen ableiten und auf dem Bildschirm nachvollziehen können.


Funktionen


Aufgabe 1: Funktionsdekomposition
Ändern Sie mindestens eines Ihrer Programme aus dem Abschnitt "Ausdrücke, Operatoren, Anweisungen" dahingehend, dass Ihre main-Funktion nur Aufrufe eigener Funktionen beinhaltet, die dann den eigentlichen Programmkode enthalten. Achten Sie auf eine sinnvolle Verteilung des Programmkodes auf die jeweiligen Funktionen.

Aufgabe 2: Funktionsparameter
Schreiben Sie ein Programm, das neben der main-Funktion noch 3 weitere Funktionen enthält, die nacheinander aufgerufen werden. Die erste Funktion lese eine Zahl von der Tastatur ein, die zweite Funktion quadriere die eingelesene Zahl, und die dritte Funktion gebe das Ergebnis mit einer Erklärung auf dem Bildschirm aus.
  1. Nutzen Sie für den Werteaustausch zwischen den Funktionen externe Variablen.
  2. Lösen Sie die Aufgabe ohne externe Variablen. Zur Werteübermittlung zwischen den Funktionen sind entsprechende Funktionsparameter einzuführen und zu verwenden.

Aufgabe 3: Programmparameter
Das von Ihnen zu erstellende Programm soll lediglich den Namen, unter dem es aufgerufen wurde, und alle Programmparameter auf dem Bildschirm ausgeben. Benennen Sie Ihr erstelltes Programm um und rufen Sie es unter dem neuen Namen mit anderen Parametern auf.

Aufgabe 4: Minirechner
Schreiben Sie ein Programm calc, das 3 Programmparameter erwartet. Für den ersten Parameter sind +,-,*,/ und % zulässig. Die beiden anderen Parameter müssen int-Werte sein. Testen Sie in Ihrem Programm die gegebenen Parameter. Falls die Parameter beim Programmaufruf korrekt sind, wenden Sie den angebenen Operator auf die int-Werte an und geben das Ergebnis auf dem Bildschirm aus. Falls das Programm falsch parametrisiert wurde, geben Sie entsprechende Nutzungshinweise aus.

Aufgabe 5: erweiterter Minirechner
Erweitern Sie das calc-Programm (aus der Aufgabe 4) um einen optionalen Parameter (-fo, -fh bzw. -fd), der Ihr Rechenprogramm zwischen oktaler, hexadezimaler und dezimaler Zahlendarstellung umschaltet. Standardmäßig (d.h. falls dieser Parameter nicht verwendet wurde) ist die dezimale Zahlendarstellung. Achten Sie auf eine zweckmäßige Dekomposition in entsprechende Funktionen, so dass Programmerweiterungen (weitere Parameter, weitere Operatoren) nach Möglichkeit nur geringfügige Änderungen zur Folge haben.

Aufgabe 6: Funktionsbibliothek für Arrays
Fassen Sie die aus dem Abschnitt "Zeiger und Arrays" programmierte Funktionalität zur Arraymanipulation (Rotation, Einfügen und Löschen von Elementen, Entfernen von Dublikaten, Häufigkeit von Arrayelementen, ...) in einer Funktionsbibliothek für Arrays mit Elementen des Typs int zusammen. Implementieren Sie pro Funkionalität genau eine C-Funktion, die als Parameter mindestens das Array und dessen Länge erhält. Schreiben Sie die Prototypen der implementierten Funktionen in eine Headerdatei (z.B. array.h).

Fügen Sie Ihrer Funktionsbibliothek eine Funktion zur Sortierung des Arrays hinzu, wobei über einen Parameter entschieden werden kann, ob auf- oder absteigend sortiert werden soll. Schreiben Sie ein kleines Testprogramm.


Aufgabe 7: Sortieren mit Rekursion
Schreiben Sie eine rekursive Version der unten stehenden Funktion insort(), die eine mögliche Implementierung des Algorithmus "insertion-sort" darstellt. Testen Sie die rekursive Funktion mit im Dialog eingelesenen Zahlen oder mit Zufallszahlen.

Hinweis: Beim "insertion-sort" wird zunächst ein Array nach dem kleinsten Element durchsucht und dieses dann mit dem ersten Element getauscht. Dieses Prinzip wiederholt sich für jedes Restarray, das jeweils aus den Arrayelementen ab dem Index i>0 beginnt.

    void insort(int a[], int len)
    {
       int i, j, mini, temp;

       for( i = 0; i < len-1; ++i) /* Jeweils ab Index i das */
       {             /* kleinste Element suchen.*/
           mini = i; /* mini ist der Index mit */
                     /* dem bis dahin kleinsten */
           for( j = i+1; j < len; ++j) /* Arrayelement. */
                if(a[j] < a[mini])
                    mini = j;
           /* a[i] und a[mini] vertauschen: */
           temp = a[i];
           a[i] = a[mini];
           a[mini] = temp;
       }
    }


Statische und dynamische Datenstrukturen


Aufgabe 1: dynamische Arrays
Schreiben Sie ein Programm für Arrays mit variabler Arraylänge. Der Nutzer wird zu Beginn nach der Anzahl der gewünschten Arrayelemente gefragt. Das Programm allokiert den Speicher für die benötigten Arrayelemente dynamisch und gibt diesen vor dem Programmende wieder frei. Danach wird das Array mit fortlaufenden Zahlenwerten initialisiert. Testen Sie nun die von Ihnen bereits für statische Arrays implementierte Ausgabefunktion.

Ändern Sie nun abschließend Ihre Einfügeoperation dahingehend, dass fehlender Speicherplatz beim Einfügen von Elementen durch neu angelegten Speicher kompensiert wird. Auch soll beim Löschen von Elementen der nicht mehr benötigte Speicherplatz wieder freigegeben werden.

Zusatz: Implementieren Sie nun noch eine Funktion zum Laden eines Vektors aus einer Textdatei. Auf der ersten Zeile der Datei steht die Anzahl der Arrayelemente. Auf der zweiten Zeile folgen dann die durch ein Leerzeichen getrennten Elemente des Arrays. Zum Beispiel: 

  10
  1 2 3 4 5 6 7 8 9 10

Überlegen Sie sich, welche Parameter die Funktion benötigt und welcher Rückgabewert sinnvoll ist. Natürlich allokiert die Funktion den benötigten Speicher dynamisch.

Aufgabe 2: Einfach verkettete Listen
Schreiben Sie ein Programm, das dem Nutzer über ein Menü das Einfügen und Löschen von Listenelementen und das Anzeigen der Liste zur Auswahl gibt. Implementieren Sie diese Funktionalität mit Hilfe einer einfach verketteten Liste und Zeichenketten im Infoteil der Listenelemente. Arbeiten Sie nur mit lokalen Variablen.


Aufgabe 3: Doppelt verkettete Listen
Implementieren Sie die Funktionalität der vorangegangenen Aufgabe mit Hilfe einer doppelt verketteten Liste. Fügen Sie Ihrem Programm einen weiteren Menüpunkt zum Löschen eines vorher gesuchten und gefundenen Elementes aus der Liste hinzu und implementieren Sie dessen Funktionalität.

Aufgabe 4: Binäre Bäume
Implementieren Sie die in der Vorlesung erarbeiteten Funktionen für binäre Bäume und testen Sie die Funktionen mit einem kleinen Programm. Schreiben Sie eine weitere Funktion, die die maximale Tiefe eines Baumes ermittelt und als int-Wert zur Verfügung stellt. Lösen Sie das Problem rekursiv, ohne globale Variablen und testen Sie Ihre Lösung im Debugger.

Ändern Sie die Ausgabefunktion dahingehend, dass eine "baumartige" Darstellung erzielt wird, die vor dem Wert des Knotens immer noch dessen Position im Baum, d.h. den "Weg der Rekursion" ausgibt, z.B. 
	  1
	  -l 2
	  -l-l 4
	  -l-r 5
	  -r 3
	  -r-l 6
	  -r-r 7
	  -r-r-l 8
Fällt Ihnen noch etwas besseres (anschaulicheres) ein?
Testen Sie mit Ihrer Ausgabefunktion das Erstellen eines sich selbst sortierenden binären Baumes entsprechend der in der Vorlesung entwickelten Funktionalität.

Aufgabe 5: Kontoverwaltung
Eine Tabelle T soll insgesamt maximal n Elemente enthalten. Jedes Element besteht aus einer Kontonummer (ganzzahlig), dem Kontostand und einer Folge vom maximal 10 Buchungen mit Buchungstext (max. 25 Zeichen), Buchungsbetrag und Buchungsdatum, die sich noch nicht im Kontostand niedergeschlagen haben.
  1. Legen Sie eine geeignete Datenstruktur für die Tabelle T fest.
  2. Schreiben Sie ein dialogfähiges und gegenüber Fehleingaben stabiles Programm, das folgende Teilaufgaben realisiert:
  3. Einrichten eines Kontos, sofern die Kapazität der Tabelle noch nicht erschöpft ist, d.h. Vergabe einer Kontonummer und Initialisierung des nächsten freien Elementes in T.
  4. Aufheben eines Kontos mit Freigabe der Kontonummer und des zugehörigen Elementes in der Tabelle sowie "Auszahlen" des Guthabens.
  5. Anfertigen eines Kontoauszuges. Inhalt des Auszuges sollten die Kontonummer, der alte Kontostand, der neue Kontostand, welcher sich aus der Summe des alten Kontostandes mit der Folge von Buchungen berechnet, die Folge der Buchungen mit Betrag, Buchungstext und Buchungsdatum.
  6. Eingabe und Abarbeitung von Buchungen.

Aufgabe 6: Kellerspeicher
Als Kellerspeicher (LIFO-„last in first out") bezeichnet man einen Speicherbereich, der über die folgenden 3 Funktionen verfügt:
  1. push: "Einkellern" (Abspeichern) eines Elementes
  2. pop: "Auskellern" (Abrufen) des zuletzt eingekellerten Elementes
  3. count: Ermitteln der Elementanzahl im Kellerspeicher
Es ist ein Programm zu schreiben, das einen Kellerspeicher für Elemente vom Typ long bereitstellt. Treffen Sie hierzu geeignete Knotenvereinbarungen und implementieren Sie die Funktionen push, pop und count unter Nutzung:
  1. einer statischen Datenstruktur mit einer maximalen Anzahl von 5 Kellerelementen, wobei die push-Funktion diese Grenze natürlich zu beachten hat;
  2. einer dynamischen Datenstruktur, die nur für die jeweils enthaltenen Kellerelemente Speicher reserviert.
Das Programm soll über ein kleines Menü bedienbar sein.

Aufgabe 7: Multimedia-Datenserver (Warteschlange)
Für einen Multimedia-Datenserver ist unter Nutzung dynamischer Datenstrukturen eine Warteschlange (FIFO-"first in first out") für Dienstanforderungen zu implementieren, die folgende Funktionen bereitstellt:
  1. wait: nimmt eine Dienstanforderung (einen Listenknoten) in die Warteschlange auf, wobei die Daten der Funktion als Parameter zu übergeben sind;
  2. activate: löscht das am längsten in der Warteschlange (Liste) befindliche Element und gibt dessen Daten auf dem Bildschirm aus;
  3. count: ermittelt die Anzahl der wartenden Dienstanforderungen der Warteschlange
  4. show: zeigt den Inhalt der Warteschlange auf dem Bildschirm an.
Für jede Dienstanforderung sind in der Warteschlage die folgenden Werte abzuspeichern:
  1. Internetadresse der Dienstanforderung (char[15])
  2. Name des Kunden (char[30])
  3. Kennung für Dienstklassen ('V'-Video, 'A'-Audio, 'P'-Photo, 'T'-Text, '*'- heterogene Dokumentanforderung)
  4. Suchstring (char[100])
Treffen Sie eine geeignete Knotentypvereinbarung und implementieren Sie die Funktionen wait, activate, count und show. Das Programm soll über ein kleines Menü bedienbar sein.

Aufgabe 8: Multimedia-Datenserver (Inhaltsrecherche)
Es ist ein Programm zu schreiben, das Informationen über die auf einem Multimedia-Server verfügbaren Titel (Videos, Audiofiles, usw.) verwaltet. Die Informationen seien sortiert in einer doppelt verketteten Ringliste gespeichert. Folgende Funktionen sind über ein Menü zur Verfügung zu stellen:
  1. insert: Einfügen eines Informationsknotens in die Liste, wobei die Listenposition anhand des Titelnames zu bestimmen ist;
  2. delete: Löschen eines Informationsknotens aus der Liste;
  3. search: Suche eines Knotens anhand des Titelnames
  4. show: Ausgabe aller Informationen eines Knotens
  5. showall: Ausgabe aller Titelnamen zu denen Informationensknoten in der Liste abgespeichert wurden.
  6. showselect: Ausgabe aller Titelnamen von Informationsknoten, die einen entsprechenden Suchbegriff (Deskriptor) enthalten.
Pro Informationsknoten sind folgende Informationen abzuspeichern:
  1. Titel des Dokumentes (char[25]);
  2. Kennung für den Typ des Dokumentes ('V'-Video, 'A'-Audio,'P'-Photo, 'T'-Text, '*'- heterogenes Dokument);
  3. Autor des Dokumentes (char[25]);
  4. Server/Dateiname des Dokumentes (char[100]);
  5. Schlagwörter (Deskriptoren) zur Inhaltsangabe (char[50]);
Gestalten Sie das Programm stabil gegenüber Eingabefehlern und vermeiden Sie Mehrfacheinträge unter dem gleichen Titel.


Dateizugriff


Aufgabe 1: Dateien lesen
Das von Ihnen zu erstellende Programm soll den Inhalt einer gegebenen Textdatei auf dem Bildschirm zur Anzeige bringen. Fertigen Sie hierzu zwei Lösungsvarianten an: (a) zeichenweises lesen, (b) zeilenweises lesen.

Aufgabe 2: Textausgabe
Erstellen Sie ein Programm, das folgenden Text in eine Datei schreibt: 
      Menschliches Denken ist vom Irrtum begleitet,
      menschliches Handeln ist an das Unzulängliche gebunden,
      also sind Fehler prinzipiell unvermeidlich.
Der Dateiname ist vom Nutzer zu erfragen. Gab es bereits eine Datei mit diesem Namen, dann
  1. wird sie überschrieben.
  2. wird der Text an die Datei angefügt.

Aufgabe 3: Dateistatistik
Schreiben Sie ein Programm, das in einer gegebenen Textdatei die Anzahl der Zeichen, der Worte und Zeilen ermittelt und auf dem Bildschirm ausgibt. Als Worte zählen beliebige Folgen von druckbaren Zeichen, die von mindestens einem Leerzeichen, Punkt, Komma oder Semikolon abgeschlossen sind.

Aufgabe 4: Umlautersetzung
Ersetzen Sie in einer gegebenen Textdatei die Umlaute Ä, Ü, Ö , ä, ü ,ö und ß durch Ae, Ue, Oe, ae, oe, ue und sz. Der Dateiname ist als Programmparameter anzugeben oder ggf. vom Nutzer abzufragen. Die Zieldatei hat den gleichen Namen wie die Originaldatei, die unter dem alten Namen, aber mit der Extension ".old" abzuspeichern ist.

Aufgabe 5: Leerzeichenkomprimierung
In einer gegebenen Textdatei soll jede Folge von Leerzeichen durch ein einziges Leerzeichen ersetzt werden. Der Dateiname ist als Programmparameter anzugeben oder ggf. vom Nutzer abzufragen. Die Zieldatei hat den gleichen Namen wie die Originaldatei, die unter dem alten Namen, aber mit der Extension ".old" abzuspeichern ist.

Aufgabe 6: Tabulatorersetzung
Tabulatorzeichen wirken sich störend aus, wenn ASCII-Dateien ausgedruckt oder per SMTP verschickt werden. Schreiben Sie ein Filterprogramm, das alle Tabulatorzeichen in einem Text durch die richtige Anzahl von Leerzeichen ersetzt. Gehen Sie von der Standard-Tabulatorbreite 8 aus. Die "Tab-Stopps" befinden sich also in den Spalten 8, 16, 24 usw. Statt einem Tabulatorzeichen '\t' müssen bis zum nächsten Tab-Stopp Leerzeichen ausgegeben werden (immer mindestens eins).

Aufgabe 7: Ver- und Entschlüsseln von Textdateien
Schreiben Sie ein Programm zum Verschlüsseln bzw. Entschlüsseln von Textdateien. Die Verschlüsselung wird erreicht, indem jeder Buchstabe im Bereich a-z und A-Z um einen "geheimen" Wert verschoben wird. Das heißt zum Beispiel für eine Verschiebung um 5 für das Wort "Atom" eine Verschlüsselung nach "Fytr". Die Verschiebung ist zyklisch, d.h. z um den Wert 1 verschoben ergibt a. Das Programm wird mit einem Parameter -v (zum Verschlüsseln) oder -e (zum Entschlüsseln) und dem Namen der Textdatei parametrisiert. Der "geheime" Wert der Verschiebung ist als Konstante fest in das Programm zu integrieren. Die Zieldatei hat den gleichen Namen wie die Originaldatei, die zu löschen ist. Reimplementieren Sie das Programm, indem Sie Verschlüsslungstabellen verwenden (siehe Übung).

Aufgabe 8: Primzahlenberechnung
Zu implementieren ist ein C-Programm, das alle Primzahlen bis 100000 berechnet und sowohl auf dem Bildschirm als auch in eine Textdatei ausgibt. Das Programm sollte effizient arbeiten und auch die Anzahl der ermittelten Primzahlen auf den Bildschirm schreiben.

Aufgabe 9: Lesen und Schreiben von Arrayinhalten
Im Praktikumsabschnitt zu Zeigern und Arrays haben Sie ein menugeführtes Programm mit umfassender Funktionalität für Arrays von int-Werten entwickelt. Fügen Sie zwei weitere Menüpunkte zum Speichern und Laden von Arrays hinzu. Der Dateiname ist vom Nutzer zu erfragen. Eingabe- und Dateifehler sind zu behandeln. Implementieren Sie zwei Varianten:
  1. auf der Basis von Textdateien
  2. unter Nutzung von Binärdateien
Machen Sie sich die Unterschiede (die Vor- und Nachteile) deutlich.


Preprozessoranweisungen


Aufgabe 1: mehrsprachige Menüführung
Ändern Sie ein Programm aus dem Aufgabenkomplex "Statische und dynamische Datenstrukturen" dahingehend, dass die Sprache der Menüführung zum Übersetzungszeitpunkt durch bedingte Übersetzung gewählt werden kann.



CGI-Programmierung


Aufgabe 1: statische CGI-Skripte
Schreiben Sie ein C-Programm, dass als CGI-Skript auf dem WWW-Server des Fachbereiches Informatik (iaix5.informatik.htw-dresden.de) arbeiten soll. Arbeiten Sie hierzu unter Ihrem Login im Verzeichnis public_html/cgi-bin. Nutzen Sie den C-Compiler z.B. mit folgendem Aufruf 'cc -o prakt.cgi prakt.c'.

Ihr CGI-Skript dient der Ausgabe einer einfachen "Homepage", die einen kurzen Lebenslauf und mindestens ein Bild (z.B. Passbild oder Hintergrundbild) enthält.
Testen Sie Ihr CGI-Skript mit einem WWW-Browser und der Adresse: www.informatik.htw-dresden.de/~htwXXXX/cgi-bin/prakt.cgi.

Aufgabe 2: CGI-Skripte mit externen Programmaufrufen
Schreiben Sie ein CGI-Skript, dass über den aktuellen WWW-Server informiert. Auszugeben ist die Systemzeit ("/bin/date") und eine Liste aller am System angemeldeten Nutzer ("/bin/who"). Beachten Sie, dass diese Informationen als vorformatierter Text in das HTML-Dokument einzubetten sind.

Aufgabe 3: rekursive CGI-Skripte
Erweitern Sie Ihr CGI-Skript aus der Aufgabe 1 um die folgende Funktionalität. Wird Ihr CGI-Skript ohne Parameter aufgerufen, dann soll Ihr Lebenslauf in Kurzform dargestellt werden. Für mindestens zwei mit einem entsprechenden Icon markierte Einträge Ihres Lebenslaufes existieren vertiefende Informationen. Die Icons sind als "rekursive" Referenzen auf das eigene CGI-Skript angelegt und enthalten definierte Parameter. Wird das CGI-Skript mit diesen Parametern referenziert, dann wird anstelle des Icons die zusätzliche Information zum entsprechenden Eintrag des Lebenslaufes angezeigt.

Erweitern Sie Ihr CGI-Skript dahingehend, dass die zusätzlichen Informationen Ihres Lebenslaufes nur für "authorisierte Nutzer" zugänglich gemacht werden. Werten Sie für die Authorisierung wahlweise die Umgebungsvariablen REMOTE_ADDR, REMOTE_IDENT oder REMOTE_USER aus.

Aufgabe 4: Gästebuch
Schreiben Sie ein CGI-Skript, dass die Funktionalität eines Gästebuches implementiert. Zu erfassen sind Anrede, Name und der Text des Eintrages. Abzuspeichern sind diese Informationen in einer Textdatei (z.B. gbuch.txt), an die jeweils der letzte Eintrag anzuhängen ist.

Lösen Sie das Problem, indem Sie die Funktionen der nachfolgend aufgeführten main()-Funktion implementieren: 
  void main() {
	 char *env;
	 htmlkopf("Gästebuch");
	 if ((env = getenv("QUERY_STRING")) != NULL)
	   if (strcmp("getdata", env) == 0)    /* Parameter == getdata ? */
				 getdata();
	 formular_anzeigen();
	 gbuch_ausgeben();
	 htmlende();
      }