Not logged in. · Lost password · Register

weißnix
Member since Jul 2012
2 posts
Subject: Klausur vom 23.02.2012 Aufgabe 4
Ich  habe zwar die Lösung im Klausurvorbereitungkurs verfolgt, dennoch habe ich ein paar Verständnisfragen zur Teilaufgabe c) ( a) und b) sind soweit nachvollzogen und verstanden worden)

Ich habe mir folgende Lösung notiert:


Knoten kopf = entferneMax();
Knoten schlepp = kopf;

while(wurzel != null) {
      
       Knoten max = entferneMax();
       schlepp.rechts = max;
       schlepp = max;  // hier meine Frage
}

return kopf;
 
-> Sind meine Notizen überhaupt korrekt?, kann sein, dass ich mich verschrieben hab und meine Verwirrung nur daraus resultiert.

Ich verstehe nun nicht ganz wie obiger Code sicherstellt, dass wir einen absteigend, zu einer Liste degnerierten Baum erhalten.
Mit "entferneMax()" wird ja das Maximum des aktuellen Heaps entfernt und anschließen (auf nicht näher erlauterte weiße) die MaxHeap-Eigenschaft hergestellt.
Dabei wird der Knoten aus dem Heap entfernt und all seine Verbindungen auf null gesetzt.


-> hab ich das soweit überhaupt richtig verstanden?

Wenn ich aber nun wiederholt in der Schleife das Maximum entferne und im Knoten max speichere und diesen dann an schlepp.rechts anhänge und anschließend schlepp = max setze, so erhalte ich doch lauter einzelne Knoten mit jeweils nur einem rechten Nachfolger und keinen Baum.

Ich denke mir das ungefähr so, dass wenn ich schlepp = max setze , schlepp anschließend der aktuelle durch entferneMax() erzeugte Knoten ohne Verbindungen wird.

Ich weiß nicht wo mein Denkfehler liegt oder aus welchem Grund ich obigen Code nicht nachvollziehen kann und bitte daher um Hilfe!

Klappt oberer Code vlt auch so?:

while(wurzel != null){

       Knoten max = entferneMax();
       schlepp.rechts = max ;
       schlepp = schlepp.rechts;
}
wiedehopf
Member since May 2012
77 posts
a=b;
c=b;

ist gleichwertig mit

a=b;
c=a;

dabei spielt es keine rolle ob in den variablen pointer drinstehen oder primitive datentypen.

um deine zweite frage mal zu beantworten.

zur ersten frage:

schau dir mal das bild der aufgabe an.
und wie ein zur Liste degenerierter Baum aussieht.
matze_
Member since Oct 2011
113 posts
Will mal jemand seine Lösung zu den anderen Teilaufgaben posten? Hier https://fsi.informatik.uni-erlangen.de/dw/pruefungen/bache… fehlt die Aufgabe leider noch.
weißnix
Member since Jul 2012
2 posts
A4)a)

private void versickern(Knoten k) {

         Knoten groesser = null;

         groesser = k.links;

         if(k.rechts != null){
               if(k.links != null && k.links.wert < k.rechts.wert || k.links == null) {
                                 groesser = k.rechts;
               }
        }


        if(groesser == null) {
             return;
        }


        if(groesser.wert <k.wert) return;

        vertausche (groesser, k);

        
        versickern(groesser);

}

4)b)


private void erzeugeHalde(Knoten k) {

       if(k.left != null){
           erzeugeHalde(k.left);
       }

       if(k.right !=null){
           erzeugeHalde(k.right);
       }

       versickern (k);

}
Ahuevo
Member since Apr 2017
10 posts
in Aufgabe 2c) ist ein kleiner Fehler in der Lösung:

// Gehe alle Nachbarknoten einmal durch
        for(Node n : neighbors) {

statt neighbors müsste es heißen current.neighbors.


Funktioniert hat der Code aber bei mir trotzdem nicht in Java, falls es wem hilft, ich habe noch diese alternative Lösung:

import java.util.*;
import static java.awt.Color.*;

public class derGraph {

    public boolean color(Node v) {
        LinkedList<Node> q = new LinkedList<Node>();
        v.color = BLACK;
        q.addLast(v);

        while (q.isEmpty() != true) {
            Node current = q.removeFirst();

            for (Node n : current.neighbors) {

                if (n.color == current.color) {
                    return false;

                }

                if (n.color == WHITE) {
                    n.color = (current.color == BLACK ? GRAY : BLACK);
                    q.addLast(n);
                }

            }
            System.out.println("Bearbeitet:" + current);
        }
        return true;
    }
}
This post was edited on 2017-04-29, 13:30 by Ahuevo.
gaku
Member since Oct 2011
693 posts
+1 Ahuevo
Du kannst im Übrigen selbst die Lösungen korrigieren, wenn du einen Fehler findest.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen