Datenstrukturen für Pointer zeichnen



  • Hallöle. Habe ein Programm geschrieben, dass folgendes macht:

    Zufallszahlen zwischen 1 und 999 werden generiert und in eine verkettete Liste eingefügt. Eingabe von...:

    'a': ein neues Element soll am Anfang der Liste eingefügt werden
    'e‘: ein neues Element soll am Ende der Liste eingefügt werden
    's‘: die gesamte Liste soll mit BubbleSort aufsteigend sortiert werden
    'i‘: ein neues Element soll sortiert in eine bereits aufsteigend sortierte Liste eingefügt werden (ohne diese nochmals komplett zu sortieren)
    'q‘: Programm verlassen

    Hier das Programm:

    #include <stdlib.h>
    #include <iostream>
    
    using namespace std;
    
    
    struct Node {
      int item;
      struct Node* next;
    };
    
    void printList(struct Node* node) {
      while (node != NULL) {
        cout << node->item << " ";
        node = node->next;
      }
    }
    
    void InsertAtBegin(struct Node** ref, int data) {
    
    
      struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    
      new_node->item = data;
      new_node->next = (*ref);
    
    
      (*ref) = new_node;
      printList(*ref);
    }
    
    
    
    void InsertAtEnd(struct Node** ref, int data) {
      struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
      struct Node* last = *ref;
    
      new_node->item = data;
      new_node->next = NULL;
    
      if (*ref == NULL) {
        *ref = new_node;
        return;
      }
    
      while (last->next != NULL)
        last = last->next;
    
      last->next = new_node;
      printList(*ref);
      return;
    }
    
    void insertSorted(struct Node** ref, int data) {
      struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
      struct Node* last = *ref;
    
      new_node->item = data;
      new_node->next = NULL;
    
      if (*ref == NULL) {
        *ref = new_node;
        printList(*ref);
        return;
      }
    
      while (last->next != NULL)
        last = last->next;
    
      last->next = new_node;
    
       printList(*ref);
      return;
    }
    
    void bubbleSort(struct Node **start)
    {
         struct Node *a= *start;
         struct Node *b= *start;
    
         while (a != NULL) {
         	b=*start;
       	while (b != NULL) {
        if(a->item<b->item){
    
    	    int temp = a->item ;
    	    a->item=b->item ;
    	    b->item =temp;
    	}
    b=b->next;
      }
      a=a->next;
    
      }
      printList(*start);
    }
    
    
    
    
    int main() {
      struct Node* head = NULL;
    
    
      char choice;
      int data;
      int b=1;
      while(b==1){
    
      	cout<<endl<<"a"<<endl<<"e"<<endl<<"s"<<endl<<"i"<<endl<<"q"<<endl<<"Enter your choice"<<endl;
      	cin>>choice;
      	switch(choice){
      			case 'a':
      				 data = 100+rand() % 899;
      				InsertAtBegin(&head,data);
      			break;
      			case 'e':
      				 data = 100+rand() % 899;
      				InsertAtEnd(&head,data);
      			break;
      			case 's':
      				bubbleSort(&head);
      			break;
      			case 'i':
      				 data = 100+rand() % 899;
      				insertSorted(&head,data);
      			break;
      			case 'q':
      				b=2;
      			break;
    
    	  }
    
    
      }
    }
    
    

    Jetzt muss ich noch für jede Funktion eine Handskizze für die Datenstruktur anfertigen, in der aufgezeigt wird in welcher Reihenfolge Pointer gesetzt oder "verbogen" werden. Ich gebe zu, dass ich gar nicht weiß, was von mir verlangt wird und dazu auch nichts verwertbares im Internet gefunden habe. Kann mir jemand sagen, wie ich hier vorgehen soll bzw wie das auszusehen hat? Das Programm sollte eigentlich einwandfrei laufen, aber vielleicht kann da auch nochmal jemand drüberschauen. Dankeschön schon mal 😛



  • Dein insertSorted() hängt doch auch nur am Ende an statt einzusortieren.
    Ein Konstruktor für Node und new statt malloc wäre toll.

    cout << endl << "a" << endl << "e" << endl << "s" << endl << "i" << endl << "q" << endl << "Enter your choice" << endl;
    

    Wie oft willst Du noch hintereinander flushen??

    cout << "\na\ne\ns\n\ni\nq\nEnter your choice\n";
    


  • @Swordfish Sorry, habe nicht die gesamte Aufgabe gepostet. Voll verpeilt. Die Funktion soll am Ende einfügen ohne einzusortieren oder erneut zu sortieren. Hier die gesamte Aufgabenstellung:

    Schreiben Sie ein Programm, dass Zufallszahlen (Integer ,Wertebereich 1...999)schrittweise in eine einfach verkettete Liste einfügt: Menüoptionen - Benutzereingaben:
    'a': ein neues Element soll am Anfang der Liste eingefügt werden
    'e‘: ein neues Element soll am Ende der Liste eingefügt werden
    's‘: die gesamte Liste soll mit BubbleSort aufsteigend sortiert werden
    'i‘: ein neues Element soll sortiert in eine bereits aufsteigend sortierte Liste eingefügt werden (ohne diese nochmals komplett zu sortieren)
    'q‘: Programm verlassen
    Gehen Sie hierbei wie folgt vor:
    Schreiben Sie eine Funktion InsertAtBegin (int x)
    Schreiben Sie eine Funktion InsertAtEnd (int x)
    Schreiben Sie eine Funktion Insert Sorted (int x) (Einfügen eines neuen Elements in eine bereits sortiert vorliegende Liste)
    Für jede der zuvor genannten Funktionen fertigen Sie zunächst eine Handskizze der Datenstruktur an und welche Zeiger in welcher Reihenfolge gesetzt /verbogen werden müssen (die Handskizzen sind für die Testierung vorzulegen)
    Schreiben Sie eine Funktion PrintList, die den Listeninhalt zeilenweise auf dem Bildschirm ausgib t– rufen Sie diese Funktion immer nach jedem Menübefehl auf um unmittelbar das Resultat auf der Konsole auszugeben
    Schreiben Sie eine Funktion BubbleSort, die den Listeninhalt aufsteigend sortiert (beim Austausch zweier Elemente tauschen Sie nur die Dateninhalte zweier benachbarter Listenelemente, nicht aber die Listenelemente an sich).



  • 	while (b == 1) {
            // ...
    	}
    

    ->

    do {
        // ...
    } while (choice != 'q');
    

    ?

    @IkeIkeIke sagte in Datenstrukturen für Pointer zeichnen:

    Die Funktion soll am Ende einfügen ohne einzusortieren oder erneut zu sortieren.

    @IkeIkeIke sagte in Datenstrukturen für Pointer zeichnen:

    Schreiben Sie eine Funktion Insert Sorted (int x) (Einfügen eines neuen Elements in eine bereits sortiert vorliegende Liste)

    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.



  • Danke für die Antwort. Ja du hast natürlich recht. Das sind gute Änderungsvorschläge.



  • @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.


Log in to reply