Datenstrukturen für Pointer zeichnen



  • @Swordfish

    Doch, insertSorted() soll das neue Element so einfügen daß die vor dem Einfügen sortierte Liste danach auch noch sortiert ist. Also nicht zwangsweise immer am Ende.

    Das kann ich aus der Aufgabenstellung so nicht herauslesen. Ich meine es ist schon so gemeint, dass das neue Element tatsächlich immer am Ende stehen soll.



  • @IkeIkeIke sagte in Datenstrukturen für Pointer zeichnen:

    Ich meine es ist schon so gemeint, dass das neue Element tatsächlich immer am Ende stehen soll.

    Sicher nicht.



  • @IkeIkeIke sagte in Datenstrukturen für Pointer zeichnen:

    data = 100+rand() % 899;

    Das ist ja auch kaput:

    Wertebereich 1...999

    Vorschlag:

    #include <cstdlib>
    #include <ctime>
    #include <iostream>
    
    struct Node {
        int value;
        Node *next;
    
        Node(int value, Node *next = nullptr)
        : value{ value },
          next{ next }
        {}
    
        Node(Node const&) = delete;
        ~Node() { delete next; }
    };
    
    void printList(Node *node)
    {
        for(; node; node = node->next)
            std::cout << node->value << ' ';
    }
    
    void InsertAtBegin(Node **root, int value)
    {
        *root = new Node{ value, *root };
        printList(*root);
    }
    
    void InsertAtEnd(Node **root, int value)
    {
        if (!*root) {
            *root = new Node{ value };
            return;
        }
    
        auto last = *root;
        while (last->next)
            last = last->next;
    
        last->next = new Node{ value };
        printList(*root);
    }
    
    void insertSorted(Node **root, int value)
    {
        if (!*root) {
            InsertAtBegin(root, value);
            return;
        }
    
        auto current = *root;
        while (current->next && current->next->value < value)
            current = current->next;
    
        current->next = new Node{ value, current->next };
        printList(*root);
    }
    
    void bubbleSort(Node *root)
    {
        for (auto a = root; a; a = a->next) {
            for (auto b = a->next; b; b = b->next) {
                if (a->value > b->value) {
                    auto temp = a->value;
                    a->value = b->value;
                    b->value = temp;
                }
            }
        }
        printList(root);
    }
    
    int main()
    {
        Node* root = nullptr;
        std::srand(static_cast<unsigned>(std::time(nullptr)));
    
        char choice;
        do {
            std::cout << "\na\ne\ns\ni\nq\nYour choice: ";
            std::cin >> choice;
            int value = 1 + rand() % 999;
            switch (choice) {
            case 'a':
                InsertAtBegin(&root, value);
                break;
            case 'e':
                InsertAtEnd(&root, value);
                break;
            case 's':
                bubbleSort(root);
                break;
            case 'i':
                insertSorted(&root, value);
                break;
            }
        } while (choice != 'q');
    
        delete root;
    }
    


  • @Swordfish

    @Swordfish sagte in Datenstrukturen für Pointer zeichnen:

    @IkeIkeIke sagte in Datenstrukturen für Pointer zeichnen:

    data = 100+rand() % 899;

    Das ist ja auch kaput:

    Wertebereich 1...999

    Vorschlag:

    #include <cstdlib>
    #include <ctime>
    #include <iostream>
    
    struct Node {
        int value;
        Node *next;
    
        Node(int value, Node *next = nullptr)
        : value{ value },
          next{ next }
        {}
    
        Node(Node const&) = delete;
        ~Node() { delete next; }
    };
    
    void printList(Node *node)
    {
        for(; node; node = node->next)
            std::cout << node->value << ' ';
    }
    
    void InsertAtBegin(Node **root, int value)
    {
        *root = new Node{ value, *root };
        printList(*root);
    }
    
    void InsertAtEnd(Node **root, int value)
    {
        if (!*root) {
            *root = new Node{ value };
            return;
        }
    
        auto last = *root;
        while (last->next)
            last = last->next;
    
        last->next = new Node{ value };
        printList(*root);
    }
    
    void insertSorted(Node **root, int value)
    {
        if (!*root) {
            InsertAtBegin(root, value);
            return;
        }
    
        auto current = *root;
        while (current->next && current->next->value < value)
            current = current->next;
    
        current->next = new Node{ value, current->next };
        printList(*root);
    }
    
    void bubbleSort(Node *root)
    {
        for (auto a = root; a; a = a->next) {
            for (auto b = a->next; b; b = b->next) {
                if (a->value > b->value) {
                    auto temp = a->value;
                    a->value = b->value;
                    b->value = temp;
                }
            }
        }
        printList(root);
    }
    
    int main()
    {
        Node* root = nullptr;
        std::srand(static_cast<unsigned>(std::time(nullptr)));
    
        char choice;
        do {
            std::cout << "\na\ne\ns\ni\nq\nYour choice: ";
            std::cin >> choice;
            int value = 1 + rand() % 999;
            switch (choice) {
            case 'a':
                InsertAtBegin(&root, value);
                break;
            case 'e':
                InsertAtEnd(&root, value);
                break;
            case 's':
                bubbleSort(root);
                break;
            case 'i':
                insertSorted(&root, value);
                break;
            }
        } while (choice != 'q');
    
        delete root;
    }
    

    Ja tatsächlich. Das habe ich mir wohl richtig unnötig erschwert.

    Kannst du mir vielleicht auch etwas zu den Handskizzen für die Datenstruckturen sagen? Ich schätze, dass das in genau der Vorlesung erwähnt wurde, in der ich nicht da war. Deswegen weiß ich gerade da gar nicht was ich machen soll...



  • Sowas in der Richtung wird sich der Aufgabensteller wohl vorstellen: https://www.geeksforgeeks.org/linked-list-set-2-inserting-a-node/



  • @Swordfish ah okay dankeschön. Habe ich in der Form noch nicht gesehen. Das dürfte aber nich all zu schwer sein. Scheint ja im Prinzip genau das zu sein, was programmiert werden sollte.



  • @Swordfish sagte in Datenstrukturen für Pointer zeichnen:

    @IkeIkeIke sagte in Datenstrukturen für Pointer zeichnen:

    Ich meine es ist schon so gemeint, dass das neue Element tatsächlich immer am Ende stehen soll.

    Sicher nicht.

    Ich glaube mittlerweile doch, dass du recht gehabt hast 😅



  • @Swordfish Hey. Ich würde gerne nochmal etwas bei dir nachfragen. Undzwar wie ich am besten den obigen Code so umstrukturiere, sodass eine doppelt verkettete Liste herauskommt... Ich glaube ich lerne diesen ganzen Listenkram erst dann, wenn ich sehe, wie der richtig geschrieben wird 😵 . Unser Prof hat vor der vorlesungsfreien Zeit kaum Zeit gehabt etwas zu doppelt verketteten Listen zu sagen, wollte aber, dass wir uns bereits dsamit auseinandersetzen.



  • Dann fang doch einmal an das ganze selbst umzusetzen. So schwierig ist es doch nicht jetzt noch die Zeiger für die Rückrichtung zu integrieren.



  • @IkeIkeIke
    Eine doppelt verkettete Liste hat pro Element einen Zeiger auf das nächste Element sowie einen Zeiger auf das vorherige Element.
    D.h. um ein Element einzufügen muss neben dem einzufügenden Element auch das Element vor der Einfügeposition sowie das Element nach der Einfügeposition angepasst werden.
    Um ein Element zu löschen müssen ebenso zwei Elemente angepasst werden (das vor dem zu löschenden Element und das danach).

    Wenn man den Code einfach halten möchte, dann kann man folgendes machen:

    • Man trennt die beiden Zeiger aus dem Element heraus und packt sie in eine "List Node" Struktur.
    • Das Element enthält dann neben den Nutzdaten eine "List Node" Struktur statt direkt die beiden Zeiger
    • Als Listen-Kopf kann man dann ebenso die "List Node" Struktur verwenden. Der "next" Zeiger zeigt dann auf das erste Element in der Liste und der "previous" Zeiger zeigt auf das letzte Element.

    Eine weitere übliche Vereinfachung ist dann dass man den "next" Zeiger des letzten Elements nicht NULL setzt sondern auf den Listen-Kopf zeigen lässt und analog dazu den "previous" Zeiger des ersten Elements ebenso auf den Listen-Kopf zeigen lässt. Dadurch ergibt sich ein "Ring" - man nennt das ganze dann eine Ring-Liste. Dadurch fallen bei der Implementierung viele Sonderfälle weg.

    Zum Test ob man am Ende (oder Anfang) der Liste angekommen ist braucht man dann natürlich immer den Zeiger auf den Listen-Kopf - aber das ist meist ein guter Kompromiss.

    Tip: zum Einfügen und Löschen braucht man den Zeiger auf den Listen-Kopf nicht.

    Damit solltest du es schaffen das ganze selbst zu implementieren.
    Zeichne dir das ganze einfach auf und dann schreib dir auf welche Zeiger in welchen Elementen beim Einfügen bzw. Löschen angepasst werden müssen - und auf welches Element sie danach zeigen müssen. Und dann implementiere es.


Anmelden zum Antworten