Aufgabe 1: (40 Punkte) Schreiben Sie ein Programm bsort das mit Hilfe des "Bubble-Sort"-Algorithmus ein Array (= Feld) von ganzen Zahlen sortiert. Beim Aufruf soll man dem Programm auf der Kommandozeile mitteilen können, wieviele Zahlen einzulesen sind und ob sie in aufsteigender (Voreinstellung) oder absteigender Reihenfolge (Option -u angegeben) sortiert werden sollen. Ein Programmaufruf könnte z.B. wie folgt aussehen: bsort -u 15 D.h. der Benutzer soll 15 Zahlen eingeben, die anschließend in absteigender Reihenfolge sortiert werden. Ihnen sind die untenstehende main-Funktion sowie die Deklarationen der benötigten Funktionen vorgegeben. Sie sollen nun die deklarierten Funktionen implementieren, sowie zu den Funktionen init_array und sort_array jeweils ein Struktogramm erstellen. (Achtung: Verwenden Sie keine globalen Variablen!) Beschreibung der einzelnen Funktionen: a) parse_ops: Bearbeitet die Kommandozeilenoptionen. Ist die Option -u vorhanden, soll flag_u den Wert 1 erhalten, andernfalls 0. Wenn eine Zahl vorhanden ist wird num auf den entsprechenden Wert gesetzt, ansonsten wird 10 eingestellt. Bei Fehlaufrufen (z.B. wenn die Zahl<=0 ist, etc.) soll das Programm eine Fehlermeldung ausgeben und terminieren. Zur Wandlung einer Ziffernfolge in einen Integerwert kann die Funktion int atoi(char *str) verwendet werden (wobei str einen Zeiger auf den zu konvertierenden String darstellt). Hinweis: Falls str keine Zahl repräsentiert liefert atoi den Wert 0. b) init_array: Hier muß Speicher für das Array beschafft werden. Anschließend sollen vom Benutzer die Werte in das Array eingetragen werden. Die Funktion liefert als Ergebnis einen Zeiger auf das Array. (zuerst Struktogramm erstellen!) c) sort_array: Die Werte im Array werden sortiert, indem das Array wiederholt von vorne durchlaufen wird und je zwei benachbarte Werte ihren Platz tauschen, falls der erste grö- ßer (bzw. kleiner bei gesetzter Option -u) als der zweite ist. So steigt in einem Durchlauf das größte (kleinste) Element wie eine "Blase" ans Ende des Arrays. Das wird wiederholt, bis in einem Durchlauf keine Elemente mehr getauscht werden mußten. (Struktogramm nicht vergessen!) d) print_array: Funktion zum Ausgeben aller Zahlen des Feldes. e) swap: Funktion zum Tauschen zweier Integerwerte. f) main: Ergänzen Sie die main-Funktion so, daß der dynamisch belegte Speicher wieder freigegeben wird. #include void parse_ops(int argc, char *argv[], int *num, int *flag_u); int *init_array(int num); void sort_array(int *arr, int num, int flag_u); void print_array(int *arr, int num); void swap(int *a, int *b); int main(int argc, char *argv[]) { int num, flag_u; int *arr; parse_ops(argc, argv, &num, &flag_u); printf("num = %d, flag_u = %d\n", num, flag_u); arr = init_array(num); sort_array(arr, num, flag_u); print_array(arr, num); /* Speicher freigeben (Teilaufgabe f): */ return 0; } Aufgabe 2: (10 Punkte) Markieren und verbessern Sie die Fehler (nicht mehr als 20!) in dem untenstehenden Programm, welches aus Personendaten einen Login-Namen erzeugt. Der Login-Name wird aus dem ersten und letzten Buchstaben des Vornamens und den ersten sechs Buchstaben des Nachnamens gebildet. Der Benutzer Brian Kernighan würde so z.B. BnKernig als Login-Namen erhalten. Falsch erkannte Fehler werden negativ gewertet! #include define NAME_LEN 30; struct name { vn[NAMELEN], nn[NAMELEN], int alter } int main() { int j = 6; char loginname[9]; struct name name = (' ', ' ', 0); struct *n = &name; printf("Vorname: "); scanf("%s", n->vn); printf("Nachname: "); scanf("%s", n->nn); printf("Alter: "); scanf("%d", n->alter); loginname[0] = name.vn[0]; for(i=0, n.vn[i], i++) ; loginname[1] = n->vn[i-1]; i = 0; while(name.nn[i] & (i 2 int f(char *a, char *b); 3 int main(int argc, char *argv[]) 4 { 5 int i, j=0; 6 char a[256]; 7 for(i=argc-1; i>=0; i--) 8 j += f(&a[j], argv[i]); 9 printf("count: %d, string: %s\n", j, a); 10 return j; 11 } 12 int f(char *a, char *b) 13 { 14 int c = 0; 15 while(*b) 16 { 17 *a = *b; 18 a++; b++; c++; 19 } 20 *a = '\0'; 21 return c; 22 } +-------++-------+-------+-------------------+------+----------+----------+ | Zeile || imain | jmain | amain | cf | af | bf | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ | || | | | | | | +-------++-------+-------+-------------------+------+----------+----------+ Aufgabe 4: (7 Punkte) Die Binomialkoeffizienten lassen sich durch folgende rekursive Berechnungsvorschrift ermitteln: Schreiben Sie eine Funktion, die rekursiv - analog der oben angegebenen Formel - den Binomialkoeffizienten berechnet. Aufgabe 5: (10 Punkte) a) Nennen Sie zwei Gründe für die Verwendung von Funktionen b) Erstellen Sie eine Struktur, mit der Personendaten (Vorname, Nachname, Geburtsdatum) in einer verketteten Liste verwaltet werden können. Gehen Sie davon aus, daß ein Name aus maximal 40 und ein Geburtsdatum aus maximal 8 Zeichen besteht. Die Teilaufgaben c) bis e) beziehen sich auf die folgenden Programmodule, die zu einem lauffähigen Programm zusammengefügt werden (z.B. durch den Compileraufruf cc -Aa -o prog prog.c mod.c). Datei prog.c: Datei mod.c 1 #include "mod.h " 1 #include "mod.h" 2 2 3 int c = 0; 3 int a; 4 4 static int b; 5 int main() 5 6 { 6 int f(int i) 7 a = 0; 7 { 8 b = 0; 8 static int a = 0; 9 c = f(a); 9 int b = 0; 10 return 0; 10 a++; 11 } 11 b++; 12 c++; Datei mod.h 13 return a; 14 } 1 extern int a; 2 extern int c; 3 int f(int i); Kreuzen Sie bei den folgenden Teilaufgaben alle wahren Aussagen an. Es können pro Teilaufgabe mehrere Antworten richtig sein! Falsche Antworten zählen negativ. c) o In prog.c darf in Zeile 7 nicht auf a zugegriffen werden. o In mod.c, Zeile 8, darf kein neues a angelegt werden da bereits global ein a existiert (mod.c, Zeile 3). o Die Erhöhung von a in mod.c, Zeile 10 ist nutzlos, da beim nächsten Aufruf von f() in Zeile 8 a wieder auf 0 gesetzt wird. o Die Erhöhung von a in mod.c, Zeile 10 hat keinen Einfluß auf das in main angesprochene a. d) o In prog.c, Zeile 8, kann nicht auf b zugegriffen werden, der Compiler liefert deshalb eine Fehlermeldung. o In der Funktion f() (mod.c, Zeile 9) darf kein neues b angelegt werden, da bereits global ein b existiert (mod.c, Zeile 4). o In mod.c, Zeile 4, meldet der Compiler einen Fehler, da static nur innerhalb von Funktionen verwendet werden darf. o Die Erhöhung von b in mod.c, Zeile 11 ist nutzlos, da einem weiteren Aufruf von f() die Variable b in Zeile 9 wieder auf 0 gesetzt werden würde. e) o Zeile 3 in prog.c ist fehlerhaft, da globale Variablen bei ihrer Definition nicht initialisiert werden können. o Durch Zeile 3 in prog.c wird eine globale Variable angelegt, auf die auch in mod.c zugegriffen werden darf. o Zeile 3 in prog.c steht im Konflikt mit Zeile 2 in mod.h. o Der Ausdruck c++ in mod.c, Zeile 12, erhöht den Wert der in prog.c definierten globalen Variable c. o Der Ausdruck c++ in mod.c, Zeile 12, erzeugt einen Fehler, da zwar eine globale Variable c existiert, diese aber in mod.c nicht bekannt ist.