• Aufgabe 1
  1. Maximum von zwei Zahlen:

     #include <stdio.h>
     int main() {
         int x, y, m;
         scanf("%d", &x);
         scanf("%d", &y);
         
         if ( x < y ) {
             m = y;
         } else { // x >= y
             m = x;
         }
         printf("Das Maximum von %d und %d ist %d.\n", x, y, m);
         return 0;
     }

  2. Fakultät \( n! = n * (n-1) * \dots * 2 * 1\)

     #include <stdio.h>
     
     int main(){
         int n, i, factorial = 1;
         scanf("%d", &n);
     
         for (i = 1; i <= n; i = i + 1){
             factorial = factorial * i;
         }
         
         printf("n! = %d\n", factorial);
     
         return 0;
     }

  3. Multiplikationstabelle

     #include <stdio.h>
     
     int main(){
         int i,j,n;
         scanf("%d", &n);
         
         for ( i=1; i<=n ; i=i+1 ) {
             for ( j=1; j<=n ; j=j+1 ) {
                 printf("%4d", i*j);
             }
             printf("\n");
         }
         return 0;
     }

  4. Primzahltest

     #include <stdio.h>
     
     int main(){
         for (int i = 2; i <= 1000; i++) {
             int j = 2, prime = 1;
             while (j*j <= i) {
                 if (i%j == 0) {
                 prime = 0;
                 break; // nicht notwendig
                 }
             j++;
             }
             if (prime == 1)
             printf("%d ist prim\n", i);
         }
     
         return 0;
     }

• Aufgabe 2:

  #include <stdio.h>
  #include <stdlib.h>
  
  int main() {
  	unsigned int guess, number, n;
  
  	scanf("%u", &n);
  	
      number = 1 + rand() % n;
  	
      while(1) {
  		printf("Zahl raten: ");
  		scanf("%u", &guess);
  		if (guess == number) {
  			printf("Sehr gut!\n");
  			return 0;
  		} else if (guess > number) {
  			printf("Zahl ist kleiner!\n");
  		} else {
  			printf("Zahl ist groesser!\n");
  		}
  	}
  	
      return 0;
  }

• Aufgabe 1
  1. Ackermann-Funktion

     #include <stdio.h>
     
     int ack(int x, int y){
         if ((x == 0) && (y >= 0))
             return y + 1;
         else if ((x > 0) && (y == 0)) 
             return ack(x-1, 1);
         else if ((x > 0) && (y > 0)){
             return ack(x-1, ack(x, y-1));
         }
     }
     
     int main() {
         int x = 0, y = 0, a;
         printf("\nAckermannfunktion\n");
         printf("x = ");
         scanf("%d", &x);
         printf("y = ");
         scanf("%d", &y);
         
         a = ack(x,y);
         
         printf("ack(%i,%i)=%i.\n", x, y, a);
         
         return 0;
     }

  2. Prüfen eines Strings (Character-Array) auf die Palindrom-Eigenschaft

     #include <stdio.h>
     
     void palindrom(char feld[], int l, int *korrekt) {
         int i = 0;
         l = l - 1;
         *korrekt = 1;
         
         while(feld[l] == '\0')
             l = l - 1;
     
         while (i < l && *korrekt) {
             *korrekt = feld[i] == feld[l];
             i = i + 1;
             l = l - 1;
         }
     } // kein return wegen void
     
     int main() {
         #define ANZ 20
     
         char feld[ANZ];
         int korr;
     
         // Einlesen und Prüfen der Eingabe
         scanf("%[^\n]s", feld);
         printf("feld = %s\n",feld);
         
         // berechne Länge des Strings
         int len = 0;
         while(feld[len] != '\0')
             len++; 
     
         // teste Palindrom-Eigenschaft
         palindrom(feld, len, &korr);
     
         // drucke Palindrom-Eigenschaft aus
         if(korr == 1)
             printf("%s ist ein Palindrom.\n", feld);
         else
             printf("%s ist kein Plaindrom.\n", feld);
         
         return 0;
     }

• Aufgabe 2:

  #include <stdio.h>
  
  void swap(int *a, int *b) {  /* hier weist der Stern auf Zeiger hin */
      int tmp;
  
      tmp = *a;
      *a = *b;
      *b = tmp;
      /* Der Stern vor einer Variablen bedeutet: Dereferenzieren
          nutze den Wert, der in der Adresse von x steht (insbes. nicht die Adresse)
      */
  }
  
  int main(){
      int x = 4, y = 6;
  
      printf("x = %d, y = %d \n", x, y);
      swap(&x, &y);
      /* Aufruf mit & vor einer Variablen gibt nur die Adresse 
         der Variablen weiter, nicht aber deren Wert 
         -> Änderung von globalen Variablen durch Funktionen möglich 
         (aber nicht schön - vermeiden)
      */
      printf("x = %d, y = %d \n", x, y);
  
      return 0;
  }

• Aufgabe 1: Listen
  1. Anhängen an eine Liste

     void append(list *lp, int n)
     {
         while (*lp != NULL)
             lp = &((*lp)->next);
         /* gehe bis zum ende der liste */
     
         (*lp) = malloc(sizeof(struct element));
         /* erstelle ein neues element */
         (*lp)->value = n;
         /* fuelle den neuen container mit inhalt */
         (*lp)->next = NULL;
     }

  2. Summe einer Liste

     int sum_it(list l)
     {
         int result = 0;
     
         while (l != NULL)
         {
             result += l->value; /* result = result + l -> value */
             l = l->next;        /* schalte "start"zeiger ein element weiter */
         }
         return result;
     }
     
     int sum_rec(list l)
     {
         if (l == NULL)
             return 0;
         /* nach letztem element nichts mehr addieren */
     
         return l->value + sum_rec(l->next);
         /* nehme immer einen key und addiere die summe der restliste */
     }

  3. Entfernen aller gerade Listenelemente

     void rmEvens_rec(list *lp)
     { /* *lp heißt: wir übergeben einen pointer (list pointer) */
         if (lp == NULL || *lp == NULL)
             return;
         /* keine liste oder liste leer */
     
         if ((*lp)->value % 2 == 0)
         {
             list tmp = *lp;
             /* speicherung des zu löschenden elements (um speicher dann zu befreien, sonst speicherleichen) */
             *lp = (*lp)->next;
             /* weiterschalten des ersten pointers */
             free(tmp);
             /* speicher des zu löschenden elements befreien */
         }
         else
         {
             lp = &(*lp)->next;
             /* startpointer weiterschalten - kein löschen notwendig */
         }
     
         rmEvens_rec(lp); /* verfahre so weiter mit der restlichen liste */
     }
     
     void rmEvens_it(list *lp)
     {
         while (lp != NULL && *lp != NULL)
         {
             if ((*lp)->value % 2 == 0)
             {
                 list tmp = *lp;
                 *lp = (*lp)->next;
                 free(tmp);
             }
             else
                 lp = &(*lp)->next;
         }
     }

• Aufgabe 2: Bäume
  1. Erstellen eines neuen Knotens

     tree createNode(int n, tree l, tree r)
     {
         tree t = malloc(sizeof(struct node));
         t->left = l;
         t->right = r;
         t->key = n;
         return t;
     }

  2. Einfügen eines Knotens am linkesten Blatt

     void insertl(tree *tp, int n)
     {
         if (*tp != NULL)
             insertl(&((*tp)->left), n);
         else
             *tp = createNode(n, NULL, NULL);
     }

  3. Produkt der Blätter

     int leafprod(tree t)
     {
         if (t == NULL)
             return 1;
     
         if (t->left == NULL && t->right == NULL)
             return t->key;
     
         return leafprod(t->left) * leafprod(t->right);
     }

  4. Baum zu Liste umwandeln (nutzt append aus Aufgabe 1)

     void treeToList_rec(tree t, list *lp)
     {
         if (t == NULL)
             return;
         treeToList_rec(t->left, lp);
         if (t->key % 2 == 0)
             append(lp, t->key);
         treeToList_rec(t->right, lp);
     }

• Aufgabe 2: Implementierungen für AVL-Bäume
  1. Ermitteln der Balancefaktoren

     int height(tree t)
     {
         if (t == NULL)
             return 0;
     
         int hl = height(t->left);
         int hr = height(t->right);
     
         return (hl > hr) ? hl + 1 : hr + 1;
     }
     
     tree bfs(tree t)
     {
         if (t == NULL)
             return NULL;
         tree bf = malloc(sizeof(struct node));
         bf->key = height(t->right) - height(t->left);
         bf->left = bfs(t->left);
         bf->right = bfs(t->right);
         return bf;
     }

  2. Linksrotation um die Wurzel

     void lRot(tree *tp)
     {
         if (tp == NULL || *tp == NULL)
             return;
     
         tree rightChild = (*tp)->right;
         (*tp)->right = rightChild->left;
         rightChild->left = *tp;
         *tp = rightChild;
     }

void topsort(int n, int e, struct Edge edges[], int ord[])
{
    int j = 1, node, edge, ok;
    while (j <= n)
    {
        for (node = 0; node < n; ++node)
        {
            if (ord[node] == -1)
            {
                ok = 1;
                for (edge = 0; edge < e; ++edge)
                    if (edges[edge].to == node && ord[edges[edge].from] == -1)
                        ok = 0;
                if (ok)
                {
                    printf("Knoten %d bekommt Nummer %d. \n", node, j);
                    ord[node] = j;
                    j++;
                    break;
                }
            }
        }
    }
}