kramann.info
© Guido Kramann

Inhalte zur Vorlesungswoche #6, Informatik 1 im Wintersemester 2024/25

(EN google-translate)

(PL google-translate)

Themen

Wir setzen das Thema Algorithmen fort, mit dem Ziel schon bald soweit zu sein, dass Neuronale Netze und Genetische Algorithmen behandelt werden können.

Wiederholung Bubble-Sort
Theoretische Einführung von Insertion-Sort
char-Arrays und das speichern und vergleichen von Texten
Theoretische Einführung doppelt verketteter Listen
Der Datentyp struct
Zeiger
Praktische Umsetzung doppelt verketteter Listen mit Hilfe von struct und Zeigern
Implementierung von Insertion-Sort mittels struct, char-Arrays und Zeigern
Der Begriff der Komplexität von Algorithmen am Beispiel von Insertion-Sort und Bubble-Sort
Zeitmessung durch Abrufen der Systemzeit
Vertiefung zu Pseudozufallszahlen
Vergleich von Bubble-Sort und Insertion-Sort im praktischen Test

1 Wiederholung Bubble-Sort

Bei Bubble-Sort vertauscht man benachbarte Elemente, wenn sie in der falschen Reihenfolge stehen.
Dazu geht man die ganze Folge der zu sortierenden Elemente solange durch, bis nichts mehr gefunden wird, das getauscht werden muss.
Die maximale Dauer benötigt der Algorithmus, wenn die Elemente in absteigender Reihenfolge vorliegen, sie jedoch in aufsteigender Reihenfolge sortiert werden müssen, oder umgekehrt.
Um herauszufinden, ob bei einem Durchgang noch etwas getauscht werden musste, kann eine boolean-Variable "gefunden" verwendet werden.

#include <iostream>
using namespace std;
int main(void)
{
    int arr[] = {9,8,7,6,5,4,3,2,1,0};
    bool gefunden = true;
    cout<<endl;
    while(gefunden)
    {
        for(int i=0;i<10;i++)
            cout<<arr[i];
        cout<<endl;
        gefunden = false;
        for(int i=0;i<9;i++)
        {
            if(arr[i]>arr[i+1])
            {
                int merker = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = merker;
                gefunden = true;
            }
        }
    }
    return 0;
}

Code 0-1: Beispielimplementierung zu Bubble-Sort.

Code 0-2: Ausgabe des Programms.

2 Theoretische Einführung von Insertion-Sort

Von der gegebenen Folge nimmt man in der natürlichen Reihenfolge Element für Element weg und bildet eine neue Folge.
Ein neues Element fügt man in die neue Folge immer so ein, dass das vorangehende Element kleiner oder gleich ist, das nachfolgende größer oder gleich.

Bild 0-1: Beispielhaftes Vorgehen bei Insertion-Sort.

3 char-Arrays und das speichern und vergleichen von Texten

Um Text speichern zu können, können char-Arrays verwendet werden.
Die Array-Größe muss groß genug gewählt werden, damit die Zeichen des zu speichernden Textes Platz haben.
Um das Ende einer Zeichenkette zu markieren, wird automatisch eine -1 hinter das letzte Zeichen eingefügt.
Um zwei Texte alphabetisch miteinander zu vergleichen, steht die Bibliotheksfunktion compare zur Verfügung.

#include <iostream>
#include <cstring>
#define N 4
using namespace std;
int main(void)
{
    char texte[N][100];

    strcpy(texte[0],"Mueller, Felix");
    strcpy(texte[1],"Ahrens, Meike");
    strcpy(texte[2],"Meier, Felicitas");
    strcpy(texte[3],"Seger, Max");

    for(int i=0;i<N;i++)
        cout<<texte[i]<<endl;

    cout<<"strcmp(\"A\",\"B\") liefert:"<<strcmp("A","B")<<endl;
    cout<<"strcmp(\"B\",\"A\") liefert:"<<strcmp("B","A")<<endl;
    cout<<"strcmp(\"B\",\"B\") liefert:"<<strcmp("B","B")<<endl;
    cout<<endl;
    for(int i=0;i<N;i++)
        for(int k=0;k<N;k++)
           cout<<"Vergleich "<<texte[i]<<" "<<texte[k]<<": "<<strcmp(texte[i],texte[k])<<endl;

    for(int i=0;i<=strlen(texte[0]);i++)
        cout<<(int)texte[0][i]<<" ";
    cout<<endl;

    return 0;
}

Code 0-3: Verwendung von Text.

Mueller, Felix
Ahrens, Meike
Meier, Felicitas
Seger, Max
strcmp("A","B") liefert:-1
strcmp("B","A") liefert:1
strcmp("B","B") liefert:0

Vergleich Mueller, Felix Mueller, Felix: 0
Vergleich Mueller, Felix Ahrens, Meike: 12
Vergleich Mueller, Felix Meier, Felicitas: 16
Vergleich Mueller, Felix Seger, Max: -6
Vergleich Ahrens, Meike Mueller, Felix: -12
Vergleich Ahrens, Meike Ahrens, Meike: 0
Vergleich Ahrens, Meike Meier, Felicitas: -12
Vergleich Ahrens, Meike Seger, Max: -18
Vergleich Meier, Felicitas Mueller, Felix: -16
Vergleich Meier, Felicitas Ahrens, Meike: 12
Vergleich Meier, Felicitas Meier, Felicitas: 0
Vergleich Meier, Felicitas Seger, Max: -6
Vergleich Seger, Max Mueller, Felix: 6
Vergleich Seger, Max Ahrens, Meike: 18
Vergleich Seger, Max Meier, Felicitas: 6
Vergleich Seger, Max Seger, Max: 0
77 117 101 108 108 101 114 44 32 70 101 108 105 120 0

Code 0-4: Programmausgabe.

4 Theoretische Einführung doppelt verketteter Listen

Um Insertion-Sort zu implementieren, könnte man beim Einfügen die umgebenden Elemente in einem Array mittels ineinander geschachtelter Schleifen passend verschieben.
Eine solche Implementierung wäre aber kompliziert und das ständige Verschieben würde viel Zeitkosten.
Eine andere, effizientere Möglichkeit liegt darin, so genannte Listen zu verwenden.
Listen im Sinne des Sprachgebrauchs in der Informatik liegen vor, wenn Speicherelemente nicht nur Daten enthalten, sondern auch den Ort, wo im Arbeitsspeicher ihr Vorgänger-Elemente und/oder Nachfolger-Element zu finden ist.
Dies kann erreicht werden, wenn ein Datenelement neben dem Dateneintrag noch die Speicheradressen des Vorgängers und nachfolgers aufnehmen kann.
Das Einfügen eines Elements an eine bestimmte Stelle in eine existierende Liste, erfolgt dann durch Anpassen der Verweise auf die Vorgänger und Nachfolger:
Das Anfangselement ist oft leer.

Bild 0-2: Einfügen eines neuen Elements in eine doppelt verkettete Liste.

5 Der Datentyp struct

Der Datentyp struct ermöglicht es Variablen verschiedenen Datentyps miteinander zu einem Element zu kombinieren.
Wir nutzen das, um in einem solchen Element zum einen einen Text zu speichern und zum anderen die Adresse des Nachfolgers zu merken.

#include <iostream>
#include <cstring>
using namespace std;

struct Element
{
    char text[100];
    Element *nachfolger = 0;
};

int main(void)
{
    Element e0,e1,e2,e3,e4;
    e0.nachfolger = &e1;
    e1.nachfolger = &e2;
    e2.nachfolger = &e3;
    e3.nachfolger = &e4;

    strcpy(e1.text,"Mueller, Felix");
    strcpy(e2.text,"Ahrens, Meike");
    strcpy(e3.text,"Meier, Felicitas");
    strcpy(e4.text,"Seger, Max"); 

    Element *x=e0.nachfolger;

    while(x!=0)
    {
        cout<<(*x).text<<endl;
        x=(*x).nachfolger;
    }
    cout<<"-----------------------"<<endl;

    return 0;
}

Code 0-5: Programmbeispiel zu struct, in dem ein Text und zwei Zeiger gespeichert werden.

6 Zeiger

10_Informatik1/07_Sprachen/03_Zeiger

7 Praktische Umsetzung einfach verketteter Listen mit Hilfe von struct und Zeigern

Folgendes Beispiel setzt unter Verwendung eines struct Bubble-Sort von Texten um.

#include <iostream>
#include <cstring>
using namespace std;

struct Element
{
    char text[100];
    Element *nachfolger = 0;
};

int main(void)
{
    Element e0,e1,e2,e3,e4;
    e0.nachfolger = &e1;
    e1.nachfolger = &e2;
    e2.nachfolger = &e3;
    e3.nachfolger = &e4;

    strcpy(e1.text,"Mueller, Felix");
    strcpy(e2.text,"Ahrens, Meike");
    strcpy(e3.text,"Meier, Felicitas");
    strcpy(e4.text,"Seger, Max"); 

    //Sortieren mit bubble-Sort.
    //Im Unterricht ergänzt: Sortieren mit Insertion-Sort
    bool gefunden = true;

    while(gefunden)
    {
        //Texte aller Elemente vor jedem Sortierschritt ausgeben:
        Element *x=e0.nachfolger;
        while(x!=0)
        {
            cout<<(*x).text<<endl;
            x=(*x).nachfolger;
        }
        cout<<"-----------------------"<<endl;

        gefunden = false;

        Element *v=&e0;
        Element *e=e0.nachfolger;
        cout<<"(*e).nachfolger="<<(*e).nachfolger<<endl;
        while((*e).nachfolger!=0)
        {
            Element *a = e;
            Element *b = (*e).nachfolger;
            cout<<"Pruefe: "<<(*a).text<<" | "<<(*b).text<<" "<<strcmp((*a).text,(*b).text)<<endl;
            if(strcmp((*a).text,(*b).text)>0)
            {
                 Element *n = (*b).nachfolger;
                 (*v).nachfolger = b;
                 (*b).nachfolger = a;
                 (*a).nachfolger = n;
                 gefunden=true;                 
            }            
            v=e;
            e=(*e).nachfolger;
        }
        cout<<"##########################"<<endl;

    }    
    cout<<"Alles sortiert:"<<endl;
    Element *x=e0.nachfolger;
    while(x!=0)
    {
        cout<<(*x).text<<endl;
        x=(*x).nachfolger;
    }
    cout<<"-----------------------"<<endl;

    return 0;
}

Code 0-6: Verwendung eines struct Bubble-Sort von Texten

Mueller, Felix
Ahrens, Meike
Meier, Felicitas
Seger, Max
-----------------------
(*e).nachfolger=0x7ffdb7383980
Pruefe: Mueller, Felix | Ahrens, Meike 12
Pruefe: Meier, Felicitas | Seger, Max -6
##########################
Ahrens, Meike
Mueller, Felix
Meier, Felicitas
Seger, Max
-----------------------
(*e).nachfolger=0x7ffdb7383910
Pruefe: Ahrens, Meike | Mueller, Felix -12
Pruefe: Mueller, Felix | Meier, Felicitas 16
##########################
Ahrens, Meike
Meier, Felicitas
Mueller, Felix
Seger, Max
-----------------------
(*e).nachfolger=0x7ffdb73839f0
Pruefe: Ahrens, Meike | Meier, Felicitas -12
Pruefe: Meier, Felicitas | Mueller, Felix -16
Pruefe: Mueller, Felix | Seger, Max -6
##########################
Alles sortiert:
Ahrens, Meike
Meier, Felicitas
Mueller, Felix
Seger, Max
-----------------------

Code 0-7: Ausgabe des Programms.

8 Implementierung von Insertion-Sort mittels struct, char-Arrays und Zeigern

Folgendes Programm ist ganz ähnlich zu dem vorangehenden, setzt aber Insertion-Sort um:

#include <iostream>
#include <cstring>
#define N 4
using namespace std;

struct Element
{
    char text[100];
    Element *nachfolger = 0;
};

int main(void)
{
    Element z; //Leeres Element, das den Beginn der Ergebnisliste repräsentiert.
    Element e0,e1,e2,e3,e4;
    e0.nachfolger = &e1;
    e1.nachfolger = &e2;
    e2.nachfolger = &e3;
    e3.nachfolger = &e4;

    strcpy(e1.text,"Mueller, Felix");
    strcpy(e2.text,"Ahrens, Meike");
    strcpy(e3.text,"Meier, Felicitas");
    strcpy(e4.text,"Seger, Max"); 

    //Sortieren mit bubble-Sort.
    //Im Unterricht ergänzt: Sortieren mit Insertion-Sort
    bool gefunden = true;

    //for(int i=0;i<N;i++) //Durchgänge entspricht Anzahl in Ausgangsliste
    while(e0.nachfolger!=0) //alternativ
    {
        //Texte aller Elemente der Ergebnislicte vor jedem Sortierschritt ausgeben:
        Element *x=z.nachfolger;
        while(x!=0)
        {
            cout<<(*x).text<<endl;
            x=(*x).nachfolger;
        }
        cout<<"-----------------------"<<endl;

        Element *a = e0.nachfolger;//erstes Element aus verbleibender Liste holen.
        e0.nachfolger = (*a).nachfolger; //Umhängen: Beginn mit zweitem Element.
        //Ergebnisliste durchgehen, bis aktuelles Element >= vorangehendes.
        Element *vor = &z;            
        Element *y = z.nachfolger;            
        while(y!=0 && strcmp( (*y).text, (*a).text)<0 )
        {
            vor=y;
            y=(*y).nachfolger;
        }
        (*a).nachfolger = (*vor).nachfolger;
        (*vor).nachfolger = a;
    
        cout<<"##########################"<<endl;

    }    
    cout<<"Alles sortiert:"<<endl;
    Element *x=z.nachfolger;
    while(x!=0)
    {
        cout<<(*x).text<<endl;
        x=(*x).nachfolger;
    }
    cout<<"-----------------------"<<endl;

    return 0;
}

Code 0-8: Insertion-Sort.

-----------------------
##########################
Mueller, Felix
-----------------------
##########################
Ahrens, Meike
Mueller, Felix
-----------------------
##########################
Ahrens, Meike
Meier, Felicitas
Mueller, Felix
-----------------------
##########################
Alles sortiert:
Ahrens, Meike
Meier, Felicitas
Mueller, Felix
Seger, Max
-----------------------

Code 0-9: Ausgabe des Programms.

9 Der Begriff der Komplexität von Algorithmen am Beispiel von Insertion-Sort und Bubble-Sort

Um zu messen, wie aufwändig es ist, mit verschiedenen Algorithmen das gleiche Ziel zu erreichen, kann man die notwendige Anzahl an Rechenschritten miteinander vergleichen, aber alternativ auch den notwendigen Speicherbedarf.

Ein Algorithmus ist weniger komplex, als ein anderer, wenn er zum Erreichen des gleichen Ziels weniger Rechenschritte benötigt, beispielsweise, um eine ungeordnete Folge zu sortieren.

siehe auch:

https://de.wikipedia.org/wiki/Komplexit%C3%A4tstheorie

https://de.wikipedia.org/wiki/Sortierverfahren

https://de.wikipedia.org/wiki/Insertionsort

https://de.wikipedia.org/wiki/Bubblesort

10 Zeitmessung durch Abrufen der Systemzeit

#include <iostream>
#include<time.h>
#include<math.h>
using namespace std;
int main(void)
{
    clock_t start, end;
    start=clock();
    cout<<"Vergangene Millisekunden seit Start des Programms: "<<start<<endl;
    double x=0;
    for(int i=0;i<1000;i++)
       x=sin((double)i);
    cout<<x<<endl;
    end=clock();
    cout<<"Vergangene Millisekunden seit Start des Programms: "<<end<<endl;
    return 0;
}

Code 0-10: Zeit in Millisekunden erfassen.

11 Vertiefung zu Pseudozufallszahlen

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <math.h>
using namespace std;
int main(void)
{
    srand(0);
    for(int i=0;i<10;i++)
       cout<<(rand()%100)<<" ";
    cout<<endl;
    srand(0);
    for(int i=0;i<10;i++)
       cout<<(rand()%100)<<" ";
    cout<<endl;
    srand(time(NULL));
    for(int i=0;i<10;i++)
       cout<<(rand()%100)<<" ";
    cout<<endl;
    srand(time(NULL));
    for(int i=0;i<10;i++)
       cout<<(rand()%100)<<" ";
    cout<<endl;
    for(int i=0;i<10000000;i++)
      for(int k=0;k<1000;k++)
        sin(3.5);
    srand(time(NULL));
    for(int i=0;i<10;i++)
       cout<<(rand()%100)<<" ";
    cout<<endl;
    return 0;
}

Code 0-11: Beispielprogramm.

83 86 77 15 93 35 86 92 49 21 
83 86 77 15 93 35 86 92 49 21 
84 93 83 2 11 25 21 41 44 81 
84 93 83 2 11 25 21 41 44 81 
97 0 29 83 99 13 4 97 65 46

Code 0-12: Ausgabe.

12 Vergleich von Bubble-Sort und Insertion-Sort im praktischen Test

#include <iostream>
#include <stdlib.h>
#include<time.h>
#define N 100
using namespace std;

void zufallswerte(int arr[], int n)
{
    srand(0);
    for(int i=0;i<n;i++)
        arr[i]=rand()%100;
}

void ausgabe(int arr[], int n)
{
    for(int i=0;i<n;i++)
        cout<<arr[i]<<" ";
    cout<<endl;   
    cout<<endl;   
}

void bubblesort(int arr[], int n)
{
    bool gefunden = true;
    while(gefunden)
    {
        gefunden = false;
        for(int i=0;i<n-1;i++)
        {
             if(arr[i]>arr[i+1])
             {
                 int x = arr[i];
                 arr[i]=arr[i+1];
                 arr[i+1]=x;
                 gefunden=true;
             }
        }
    }
}

void insertionsort(int arr[], int n)
{
    for(int i=1;i<n;i++)
    {
        for(int k=0;k<i;k++)
        {
            if(arr[k]>arr[i])
            {
                //davor einfügen (ansonsten bleibt arr[i] wo es ist und bildet den bis dahin letzten Eintrag).
                int merk = arr[i]; //merken, da dorthin verschoben wird
                for(int p=i;p>k;p--)//Rest verschieben
                    arr[p]=arr[p-1];
                arr[k]=merk;//neues Element einfügen
                break;
            }
        }
    }
}

int main(void)
{
    int arr[N];

    zufallswerte(arr,N);
    cout<<"unsortiert:"<<endl;
    ausgabe(arr,N);

    clock_t t=clock();
    bubblesort(arr,N);
    clock_t tdiff = clock()-t;
    cout<<"sortiert mit Bubblesort:"<<endl;
    ausgabe(arr,N);
    cout<<"Dauer Bubblesort in Millisekunden:"<<tdiff<<endl;

    zufallswerte(arr,N);
    arr[0]=99;
    cout<<"unsortiert:"<<endl;
    ausgabe(arr,N);

    t=clock();
    insertionsort(arr,N);
    tdiff = clock()-t;
    cout<<"sortiert mit Insertionsort:"<<endl;
    ausgabe(arr,N);
    cout<<"Dauer Insertionsort in Millisekunden:"<<tdiff<<endl;
    
    return 0;
}

Code 0-13: Vergleich von Bubble-Sort mit Insertion-Sort.

unsortiert:
83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 11 68 67 29 82 30 62 23 67 35 29 2 22 58 69 67 93 56 11 42 29 73 21 19 84 37 98 24 15 70 13 26 91 80 56 73 62 70 96 81 5 25 84 27 36 5 46 29 13 57 24 95 82 45 14 67 34 64 43 50 87 8 76 78 88 84 3 51 54 99 32 60 76 68 39 12 26 86 94 39 

sortiert mit Bubblesort:
2 3 5 5 8 11 11 12 13 13 14 15 15 19 21 21 22 23 24 24 25 26 26 26 26 27 27 29 29 29 29 30 32 34 35 35 36 36 37 39 39 40 42 43 45 46 49 50 51 54 56 56 57 58 59 60 62 62 62 63 64 67 67 67 67 68 68 69 70 70 72 73 73 76 76 77 78 80 81 82 82 83 84 84 84 86 86 86 87 88 90 91 92 93 93 94 95 96 98 99 

Dauer Bubblesort in Millisekunden:79
unsortiert:
99 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 11 68 67 29 82 30 62 23 67 35 29 2 22 58 69 67 93 56 11 42 29 73 21 19 84 37 98 24 15 70 13 26 91 80 56 73 62 70 96 81 5 25 84 27 36 5 46 29 13 57 24 95 82 45 14 67 34 64 43 50 87 8 76 78 88 84 3 51 54 99 32 60 76 68 39 12 26 86 94 39 

sortiert mit Insertionsort:
2 3 5 5 8 11 11 12 13 13 14 15 15 19 21 21 22 23 24 24 25 26 26 26 26 27 27 29 29 29 29 30 32 34 35 35 36 36 37 39 39 40 42 43 45 46 49 50 51 54 56 56 57 58 59 60 62 62 62 63 64 67 67 67 67 68 68 69 70 70 72 73 73 76 76 77 78 80 81 82 82 84 84 84 86 86 86 87 88 90 91 92 93 93 94 95 96 98 99 99 

Dauer Insertionsort in Millisekunden:31

Code 0-14: Ausgabe.

ÜBUNGSAUFGABEN (18.11.-21.11.)

AUFGABE 1 (Zeiger)

Analysieren Sie nachfolgendes Programm und geben an, was auf der Konsole ausgegeben wird.
Kompilieren und starten Sie nun das Programm und vergleichen das Ergebnis mit Ihrer Vorhersage.
Machen Sie sich ggf. klar, wo Sie flasch lagen und warum.

#include <iostream>
using namespace std;
int main(void)
{
    int x=1,y=0,z=0;
    int *px=&x;
    int *py=&y;
    int *pz=&z;
    cout<<"1. Ausgabe:"<<endl;
    cout<<"x="<<x<<" y="<<y<<" z="<<z<<endl;
    cout<<"*px="<<*px<<" *py="<<*py<<" *pz="<<*pz<<endl;

    int *p=px;
    px=py;
    py=p;
    y=5;
    cout<<"2. Ausgabe:"<<endl;
    cout<<"x="<<x<<" y="<<y<<" z="<<z<<endl;
    cout<<"*px="<<*px<<" *py="<<*py<<" *pz="<<*pz<<endl;

    int h=x;
    x=z;
    z=h;
    cout<<"3. Ausgabe:"<<endl;
    cout<<"x="<<x<<" y="<<y<<" z="<<z<<endl;
    cout<<"*px="<<*px<<" *py="<<*py<<" *pz="<<*pz<<endl;

    px=pz;
    py=pz;
    x=7;

    cout<<"4. Ausgabe:"<<endl;
    cout<<"x="<<x<<" y="<<y<<" z="<<z<<endl;
    cout<<"*px="<<*px<<" *py="<<*py<<" *pz="<<*pz<<endl;

    return 0;
}

Code 0-15: Hütchenspiel mit Zeigern.

AUFGABE 2 (struct)

Analysieren und testen Sie das nachfolgende Programm.
Erweitern Sie das Programm so, dass ein Benutzer die Komponenten u.x und u.y eingibt und die Länge des entstandenen Vektors ausgegeben wird.
Verlagern Sie die Berechnung der Vektorlänge nun in eine Funktion deren Kopf so aussicht: double berechneLaenge(Vektor v).

#include <iostream>
#include <math.h>
using namespace std;

struct Vektor
{
   double x,y;
};

int main(void)
{
    Vektor u;

    u.x = 3.0;
    u.y = 4.0;

    double laenge = sqrt(u.x*u.x+u.y*u.y);
    cout<<"Länge des Vektors ["<<u.x<<"|"<<u.y<<"] ist: "<<laenge<<endl;

    return 0;
}

Code 0-16: struct zur Repräsentation von Vektoren.

Studentische Lösung:

#include <iostream>
#include <math.h>
using namespace std;

struct Vektor
{
   double x,y;
};

double berechneLaenge(Vektor v)
{
    return sqrt(v.x * v.x + v.y * v.y);
}

int main(void)
{
    Vektor p;

    cout<<"Geben Sie die X koordinate des Punktes P an:"<<endl;
    cin>>p.x;
    cout<<"Geben Sie die Y koordinate des Punktes P an:"<<endl;
    cin>>p.y;

   // p.x = 3.0;
   // up.y = 4.0;

    double laenge = berechneLaenge (p);
    
    cout<<"Länge des Vektors ["<<p.x<<"|"<<p.y<<"] ist: "<<laenge<<endl;

    return 0;
}

Code 0-17: Studentische Lösung zu Aufgabe 2.

AUFGABE 3 (Text)

Analysieren und testen Sie nachfolgenden Quelltext.
Schreiben Sie nun ein eigenes Programm, bei dem immer zwei Wörter eingegeben werden und ausgegeben wird, welches der beiden Wörter länger als das andere ist.
Erweitern Sie Ihr Programm nun so, dass auch verglichen und ausgegeben wird, welches der beiden Wörter im Alphabet früher kommt. Schauen Sie sich dazu noch einmal Quelltext "Code 0-3: Verwendung von Text." weiter oben an.
Lagern Sie schließlich das Zählen der Wortlänge und das alphabetische Vergleichen der Wörter jeweils in sinnvoller Weise in eine eigene Funktion aus.

#include <iostream>
using namespace std;
int main(void)
{
    char text[100];

    cout<<"Geben Sie ein Wort mit weniger als 100 Zeichen ein und bestätigen Sie mit ENTER:"<<endl;
    cin>>text;

    cout<<"Sie haben folgendes Wort eingegeben:"<<endl;
    cout<<text<<endl;

    int anzahl=-1;
    char c;
    do
    {
        c = text[++anzahl];
    } while(c!=0);

    cout<<"Ihr Wort enthält "<<anzahl<<" Zeichen."<<endl;

    return 0;
}

Code 0-18: Buchstabenzähler.

Studentische Lösung

#include <iostream>
#include <cstring>
using namespace std;
//int textLaenge(const char* text)
int textLaenge(char text[])
{
	int anzahl=-1;
	char c;
	do
	{
		c = text[++anzahl];
	} while(c!=0);
	return anzahl;
};

int AlphabetVergleich(char text1[], char text2[])
{
	int cmp;
	cmp = strcmp(text1, text2);
	return cmp;
};

int main(void)
{
	char text1[100], text2[100];
	cout<<"Geben Sie ein Wort mit weniger als 100 Zeichen ein und bestätigen Sie mit ENTER:"<<endl;
	cin>>text1;
	cout<<"Geben Sie ein weiteres Wort mit weniger als 100 Zeichen ein und bestätigen Sie mit ENTER:"<<endl;
	cin>>text2;
	cout<<endl;
	int anzahl1, anzahl2;
	anzahl1 = textLaenge(text1);
	anzahl2 = textLaenge(text2);
	if (anzahl1>anzahl2)
	{
		cout<<"Das längere Wort "<<text1<<" besitzt "<<anzahl1<<" Zeichen."<<endl;
	}
	else if (anzahl2>anzahl1)
	{
		cout<<"Das längere Wort "<<text2<<" besitzt "<<anzahl2<<" Zeichen."<<endl;
	}
	else
	{
		cout<<text1<<" und "<<text2<<" sind gleich lang."<<endl;
	}
	cout<<endl;

	int cmp;
	cmp = AlphabetVergleich(text1, text2);
	if (cmp>0)
	{
		cout<<text2<<" kommt im Alphabet zuerst vor."<<endl;
	}
	else if (cmp<0)
	{
		cout<<text1<<" kommt im Alphabet zuerst vor."<<endl;
	}
	else
	{
		cout<<text2<<" und "<<text1<<" sind gleich."<<endl;
	}

	return 0;
}

Code 0-19: Stdentische Lösung zu Aufgabe 3.

AUFGABE 4 (Insertionsort)

ACHTUNG: "Code 0-13: Vergleich von Bubble-Sort mit Insertion-Sort." wurde korrigiert: Zeile vor break;: ALT: arr[k]=arr[i]; NEU: arr[k]=merk;

Analysieren und testen Sie "Code 0-13: Vergleich von Bubble-Sort mit Insertion-Sort.".
Entwickeln Sie auf dieser Grundlage ein Programm, das mittels Inertionsort die Buchstaben in einem Text sortiert.
Nutzen Sie dazu auch das Beispiel und die Methodik des folgenden Programms aus (kompilieren und testen Sie es zuvor):

#include <iostream>
#define N 26
using namespace std;
int main(void)
{
    char text[] = "zyxwvutsrqponmlkjihgfedcba";

    for(int i=0;i<N;i++)
        cout<<text[i];
    cout<<endl;

    if(text[0]>text[1]) 
        cout<<text[0]<<">"<<text[1]<<endl;
    else if(text[0]<text[1]) 
        cout<<text[0]<<"<"<<text[1]<<endl;
    else
        cout<<text[0]<<"=="<<text[1]<<endl;

    return 0;
}

Code 0-20: Umgang mit einem Array aus Buchstaben.

Studentische Lösung zu Aufgabe 4

#include <iostream>
#include <cstring>
using namespace std;
void ausgabe (char arr[], int n)
{
	for(int i=0; i<n; i++)
		cout << arr[i] << " "; // Ausgabe jedes Array-Elements mit einem Leerzeichen dazwischen
	cout << endl << endl; // Zwei Zeilenumbrüche für bessere Lesbarkeit der Ausgabe
}

void insertionsort(char arr[], int n)
{
	for(int i=1;i<n;i++) // for-Schleife von Platz 2 zur Festlegung der Höchstgrenze
	{
		for(int k=0;k<i;k++) // Überprüfung aller Elemente vor der Höchstgrenze
		{
			if(arr[k]>arr[i])
			{
				char merk = arr[i]; // temporäre Variable, wenn ein Wert vor der Höchstgrenze > Wert in der Höchstgrenze
				for(int p=i;p>k;p--)
					arr[p]=arr[p-1]; // Überschreiben aller vorherigen Werte bis zum Element k
				arr[k]=merk; // Wert im Element k mit temporärer Variable überschreiben.
				break;
			}
		}
	}
}


int main(void)
{
	char text[] = "zyxwvutsrqponmlkjihgfedcba";
	int N = strlen(text); //Auslesen der Arraylänge
	cout<<"Die Elementanzahl des Arrays ist: "<<N<<endl<<endl;

	insertionsort(text, N); //Verwendung der Insertionsort-Funktion zum Sortieren der Zeichen
	cout<<"Sortiert:"<<endl;

	ausgabe(text,N); //Verwendung der Ausgabefunktion

	return 0;
}

Code 0-21: Studentische Lösung zu Aufgabe 4.