Sortierprogramm für LinkedList

[flori65817]

Danke ich versuche es nochmal , auch wenn ich noch nicht so den durchblick habe , ich melde mich dann einfach nochmal

[flori65817]

ich muss mich zurück melden also ich versteh eure Gedankengänge aber ich kann es immer noch nicht umsetzten ,ich will hier niemanden zwingend irgendwelche Aufgaben zu lösen und ihr habt auch schon versucht viel zu erklären aber ich würde mich freuen wenn ihr mal eine Lösung nach den Vorgaben schreibt , es muss um Gotteswillen nicht das komplette Programm sein nur die Daten laden Objekte erzeugen und eine verkettete Liste soll entstehen .Vlt verstehe ich dann den Ablauf, ihr müsst das natürlich nicht und ich bin keiner der nur seine Aufgaben gemacht haben will! Ich möchte es verstehen und wenn ich einen Kompletten Code und die Aufgabenstellung dazu lese verstehe ich den Sinn besser .

Ich bedanke mich im Voraus für eine Lösung mit Erklärung

[__blackjack__]

@flori65817: Was ist denn am ersten Teilschritt „Verkettete Liste mit drei Autos erstellen und eine Funktion zur Ausgabe der Liste“ konkret das Problem? Wo genau kommst Du bei folgendem ”Lückentext” nicht weiter und warum? Was hast Du versucht? Was passiert beim Ablauf? Und an welcher Stelle verhält sich das dann nicht mehr so wie von Dir erwartet?

Code: Alles auswählen

#!/usr/bin/env python3

...


def zeige_fahrzeuge(fahrzeuge):
    ...


def main():
    zeige_fahrzeuge(None)  # Sollte nichts ausgeben.

    aston_martin = Fahrzeug("Aston Martin", "silber")
    print("----")
    zeige_fahrzeuge(aston_martin)  # Sollte "Aston Martin (silber)" ausgeben.

    bentley = Fahrzeug("Bentley", "schwarz")
    vauxhall = Fahrzeug("Vauxhall", "blau")
    ...
    fahrzeuge = ...
    print("----")
    zeige_fahrzeuge(fahrzeuge)  # Sollte alle drei Fahrzeuge+Farbe auf jeweils einer Zeile ausgeben.


if __name__ == "__main__":
    main()

`Fahrzeug` ist hier die Klasse die vorgegeben ist.

Bei Datenstrukturen wie verketteten Listen macht es irgendwann auch Sinn sich das mal aufzumalen um sie besser zu verstehen. Für mich ist das bis hier hin noch nicht nötig, aber für das vertauschen von zwei benachbarten Fahrzeugen beim Bubblesort hatte ich mir eine Zeichnung gemacht. Für Anfänger kann das für das traversieren der verketten Liste vielleicht schon hilfreich sein, sich eine Zeichnung zu machen.

[__blackjack__]

Das ganze mal in der Programmiersprache Vala gelöst:

Code: Alles auswählen

public class Vehicle {
    public string make { get; private set; }
    public string colour { get; private set; }
    public weak Vehicle? previous { get; private set; }
    public Vehicle? next { get; private set; }

    public bool has_previous { get { return this.previous != null; } }
    public bool has_next { get { return this.next != null; } }
    public bool is_first { get { return this.previous == null; } }
        
    public Vehicle (string make, string colour)
    {
        this.make = make;
        this.colour = colour;
    }

    public VehicleIterator iterator () { return new VehicleIterator (this); }
    
    public class VehicleIterator {
        private Vehicle? current_vehicle;
        
        public VehicleIterator (Vehicle vehicle)
            requires (vehicle.is_first)
        {
            this.current_vehicle = vehicle;
        }
        
        public Vehicle? next_value () {
            var result = this.current_vehicle;
            if (this.current_vehicle != null) {
                this.current_vehicle = result.next;
            }
            return result;
        }
    }

    public void append (Vehicle vehicle)
        requires (!vehicle.has_previous)
        requires (!this.has_next)
        ensures (vehicle.previous == this)
        ensures (this.next == vehicle)
    {
        vehicle.previous = this;
        this.next = vehicle;
    }
    
    public void swap_with_next ()
        requires (this.has_next)
    {
        if (this.has_previous) {
            this.previous.next = this.next;
        }
        if (this.next.has_next) {
            this.next.next.previous = this;
        }
        var next_but_one = this.next.next;
        this.next.previous = this.previous;
        this.next.next = this;
        this.previous = this.next;
        this.next = next_but_one;
    }
    
    public string to_string () { return @"$make ($colour)"; }
    
    public static Vehicle? read (FileStream stream) {
        Vehicle? vehicle = null;
        var make = stream.read_line ();
        if (make != null) {
            var colour = stream.read_line ();
            if (colour != null) {
                vehicle = new Vehicle (make.strip (), colour.strip ());
            }
        }
        return vehicle;
    }
}


public int compare_vehicles (Vehicle a, Vehicle b) {
    var result = strcmp(a.make, b.make);
    if (result == 0) result = strcmp(a.colour, b.colour);
    return result;
}


public bool vehicles_are_sorted (Vehicle? vehicles) {
    if (vehicles != null) {
        foreach (var vehicle in vehicles) {
            if (
                vehicle.has_next && compare_vehicles(vehicle, vehicle.next) > 0
            ) {
                return false;
            }
        }
    }
    return true;
}


public static void print_vehicles (Vehicle? vehicles) {
    if (vehicles != null) {
        foreach (var vehicle in vehicles) print ("%s\n", vehicle.to_string ());
    }
}


public static Vehicle? load_vehicles (string filename)
    requires (filename.length != 0)
{
    var stream = FileStream.open (filename, "r");
    assert_nonnull (stream);
    var first_vehicle = Vehicle.read (stream);
    if (first_vehicle != null) {
        var vehicle = first_vehicle;
        Vehicle? next_vehicle = null;
        while ((next_vehicle = Vehicle.read (stream)) != null) {
            vehicle.append (next_vehicle);
            vehicle = next_vehicle;
        }
    }
    return first_vehicle;
}


public static Vehicle? sort_vehicles (Vehicle? vehicles)
    ensures (vehicles_are_sorted (result))
{
    var first_vehicle = vehicles;
    if (first_vehicle != null) {
        var done = false;
        while (!done) {
            done = true;
            var vehicle = first_vehicle;
            while (vehicle.has_next) {
                if (compare_vehicles (vehicle, vehicle.next) > 0) {
                    if (vehicle.is_first) first_vehicle = vehicle.next;
                    vehicle.swap_with_next ();
                    done = false;
                } else {
                    vehicle = vehicle.next;
                }
            }
        }
    }
    return first_vehicle;
}


public static void main () {
    var vehicles = load_vehicles ("test.txt");
    if (vehicles != null) {
        print_vehicles (vehicles);
        print ("----\n");
        vehicles = sort_vehicles (vehicles);
        print_vehicles (vehicles);
    } else {
        print ("Die Datei enthielt keine Fahrzeuge.");
    }
}