Listen



  • Hallo.

    Ich habe folgende Tabelle

    0 1 2 3 <-- array index
    4 | 1 | 3 | 2 | <-- Zahlen
    0 | 3 | 0 | 2 | <-- tabelle

    Von Zahlen 1 ist das nächst höhere Element die 2.
    Zahlen 1 hat den Index 1 Zahlen 2 hat den Index 3.
    Also kommt in die tabelle unter Zahlen 2 eine 2.

    Vom Zahlen 3 ist das nächst höhere Element Zahlen 4.
    Zahlen 3 hat den Index 2 Zahlen 4 hat den Index 0.

    ( Ich hoffe man konnte es verstehen was ich meine 😕 )

    Wie könnte ich das in C++ realisieren ?

    Bis hierhin bin ich gekommen aber mit den ganzen if Abfragen ist das ja irgendwie nicht Sinn der Übung:

    #include <iostream>
    using namespace std;
    
    int main(int argc, char* argv[])
    {
    int speicher;
    int tabelle[5] = {0,0,0,0};
    int zahlen [5] = {4,1,3,2};
    
    for (int i=0;i<4;i++)
    {
    cout<<zahlen[i]<<" ";
    }
    
    cout<<endl;
    
    for (int l=0;l<4;l++)
    {
               for (int j=0;j<4-1;j++)
               {
                     if ( zahlen[j] > zahlen[j+1] )
                     {
                         speicher = zahlen[j];
                         zahlen[j] = zahlen[j+1];
                         zahlen[j+1] = speicher;
                     }
               }
    
    }
    
            for (int k=0;k<4;k++)
            {
                    cout<<zahlen[k]<<" ";
            }
    
    cout<<endl<<endl;
    
                    if (zahlen[0] == 1 && zahlen[1] == 2 )
                    {
                      tabelle[1] = 3;
                      tabelle[3] = 2;
                    }
    
                    if (zahlen[1] == 2 && zahlen[2] == 3 )
                    {
                      tabelle[2] = 0;
                    }
    
                    if (zahlen[2] == 3 && zahlen[0] == 4 )
                    {
                      tabelle[0] = 0;
                    }
    
            for (int i=0;i<4;i++)
            {
            cout<<tabelle[i]<<" ";
            }
    
    return 0;
    }
    


  • list schrieb:

    ( Ich hoffe man konnte es verstehen was ich meine 😕 )

    Leider nicht. Was Zahlen 1 und Zahlen 2 usw. sein soll hast du nicht erklärt. und was du unter den Indizes verstehst auch nicht, genausowenig was das "höchste Element" sein soll.

    Versuch lieber mal zu erklären was das eigentliche Problem ist was du lösen möchtest, du scheinst hier eher schon eine vage Vorstellugn zu haben wie du es lösen möchtest, bist aber auf halbem Weg stecken geblieben.



  • Ich habe folgende Tabelle

    0 1 2 3 <-- array index

    4 | 1 | 3 | 2 | <-- Zahlen

    Von 1 ist das nächst höhere Element die 2 ( 1 < 2 die Zahlen aus dem Array ).
    1 hat den Index 1. 2 hat den Index 3.

    1 < 3 <-- array index
    1 < 2 <-- zahlen

    0 | 1 | 2 | 3 |<-- array index
    4 | 1 | 3 | 2 | <-- Zahlen
    2 Index 3

    Also kommt in die Tabelle unter Zahlen 2 eine 2.

    Denn von Zahl 2 ist der Index höher als von Zahl 1.

    Von 3 ist das nächst höhere Element 4.
    3 hat den Index 2 . 4 hat den Index 0.

    0 < 2 <-- array index
    4 > 3 <-- zahlen

    Weil 4 > 3 ist kommt unter die 4 die 0 aus dem Index.

    In diesem Fall ist Zahl bei allem größer als Zahl 1 ( höher in der Zahl selbst und der Index ist auch höher )

    1 < 3 <-- array index
    1 < 2 <-- zahlen

    Zahl 2 ist größer als Zahl 1 und Zahl 2 hat einen höheren Index als Zahl 1.
    Also kommt unter die 2 eine 2.

    Hier ist 4 > 3 der Index ist zwar kleiner aber das ist egal.

    0 < 2 <-- array index
    4 > 3 <-- zahlen



  • Ach ja der Lehrer nannte das ganze Verkettete Listen ...



  • Also aus dem was du da machen möchtest, erkenne ich leider keine verkettete Liste. Und aus der erklärung werde ich auch nicht schlau.

    Schau mal hier



  • Da hab ich schon gekuckt. 😡

    Aber unser Lehrer versteht unter Verkettete Listen wohl was anderes.



  • Dann ist er blöd, tut mir Leid, aber was du machen willst, wird hier wohl so einigen nicht ganz klar.



  • Ich frag den Lehrer einfach nochmal.



  • list schrieb:

    Ich habe folgende Tabelle
    0 1 2 3 <-- array index
    4 | 1 | 3 | 2 | <-- Zahlen
    0 | 3 | 0 | 2 | <-- tabelle

    Von Zahlen 1 ist das nächst höhere Element die 2.
    Zahlen 1 hat den Index 1 Zahlen 2 hat den Index 3.
    Also kommt in die tabelle unter Zahlen 2 eine 2.

    Vom Zahlen 3 ist das nächst höhere Element Zahlen 4.
    Zahlen 3 hat den Index 2 Zahlen 4 hat den Index 0.

    Es ist eine gewisse Herausforderung aus dieser Erklärung auf das bestehende Problem zu schließen. Ich habe das bestimmt ein paar Mal durch gelesen, bis der Tipp mit der verketteten Liste kam. Ich glaub' ich hab's jetzt.

    Die Werte in der Tabelle sind die Indizes auf das jeweils nächste Element in der Liste der Zahlen. Der Startindex ist 1 - also array index == 1 (weil zufällig die Zahl 1 - in 'Zahlen' - auch das kleinste Element in 'Zahlen' ist). Demzufolge sollte es eigenlich

    +---  index0 = 1
         v
     0   1   2   3   <-- array index
     4 | 1 | 3 | 2 |  <-- Zahlen
    -1 | 3 | 0 | 2 |  <-- tabelle (nächster Index; -1:=Ende)
    

    heißen.

    Aus dem von Dir geposteten Programmcode schließe ich, dass das Array 'Zahlen' gegeben ist (der Input) und das Array 'tabelle' gesucht ist - also der Output sein soll.
    Aus der Tatsache, dass dort ein 'Bubblesort' für das Array 'Zahlen' implementiert ist, schließe ich, dass das Array 'tabelle' derart mit Indizes versehen werden soll, dass die Werte aus 'Zahlen' in einer aufsteigend sortierten Reihenfolge vorliegen - beginnend mit der kleinsten Zahl.

    Wenn das so ist, wie ich vermute (s.o.), dann ist das für einen Anfänger eine recht schwierige Aufgabe. Der Kern von Bubblesort besteht im Vertauschen von zwei Elementen in einer Sequenz. Wenn man nicht unmittelbar die Elemente tauscht, sondern die Verweise (hier Indizes) auf das nächste Element, so muss man drei Indizes tauschen. Das ganze sähe dann so aus:

    #include <iostream>
    using namespace std;
    
    int main()
    {
        const int NIL = -1; // Index für 'Not In List'
        const int SIZE = 4; // Anzahl der Werte im Array 'zahlen'
        int tabelle[SIZE+1] = {0,0,0,0,0};
        int zahlen [SIZE] = {4,1,3,2};
    
        // --   Zahlen ausgeben
        for (int i=0; i<SIZE; ++i)
        {
            cout<<zahlen[i]<<" ";
        }
        cout<<endl;
    
        int index0 = 0;
        // --   Sortieren
        {
            // --   beliebige Vorbelegung der Listenindizes; Listenanfang steht in tabelle[SIZE]
            tabelle[0] = NIL;
            for( int i=1; i<SIZE+1; ++i )
                tabelle[i] = i-1;
    
            // --   Bubblesort - getauscht werden nur die Indizes (hier Dreiertausch)
            for( bool getauscht; ; )
            {
                getauscht = false;
                for( int prevIdx = SIZE; ; prevIdx = tabelle[prevIdx] )
                {
                    int j1 = tabelle[prevIdx];
                    int j2 = tabelle[j1];
                    if( j2 == NIL )
                        break;
                    if( zahlen[j2] < zahlen[j1] )
                    {
                        // --   Index-Tausch durchführen
                        tabelle[prevIdx] = j2;
                        tabelle[j1] = tabelle[j2];
                        tabelle[j2] = j1;
                        getauscht = true;
                    }
                }
                if (!getauscht)
                    break;
            }
            index0 = tabelle[SIZE];
        }
    
        // --   Indizes ausgeben
        for (int i=0; i<SIZE; ++i)
        {
            cout<<tabelle[i]<<" ";
        }
        cout<<endl;
    
        // --   Zahlen sortiert ausgeben
        for (int k=index0; k!=NIL; k=tabelle[k])
        {
            cout<<zahlen[k]<<" ";
        }
        cout<<endl<<endl;
        return 0;
    }
    

    Zur Vereinfachung habe ich einen weitern Index eingeführt (tabelle[SIZE] alias index0), der den Index auf das erste Element enthält. Anderenfalls müsste man beim Tauschen unübersichtliche Fallunterscheidungen machen.

    Die Ausgabe von dem Programm ist:

    4 1 3 2
    -1 3 0 2
    1 2 3 4
    

    wie man in der letzten Zeile sieht werden die Zahlen sortiert ausgegeben.

    Normal ist nicht, aber mal 'ne interessante Problemstellung. 😉

    Gruß
    Werner


Log in to reply