Sortieren von doppelt verketteter Liste?

Guten Tag,

ich soll einen simplen Algorithmus schreiben, der eine doppelt verkettete Liste, in der sich nur Nullen und Einsen befinden, sortiert (zuerst Nullen, dann Einsen).

Da ich schon ziemlich müde bin und mir immer gerne Leichtsinnsfehler passieren wollte ich fragen, ob vielleicht noch jemand ein paar kontrollierende Blicke auf meinen (Pseudo-)Code werfen kann.

Vielen Dank im Voraus!

function sort(List binList)
    begin
        pntr <- binList.head
        for (i=1, i<=n, i++){
            if(pntr.value = 0){
                pntr <- pntr.next
            }
            else{
                pntr.next.prev <- pntr.prev
                pntr.prev.next <- pntr.next
                pntr.next <- null
                pntr.prev <- tail
                tail <- pntr
            }
        }

12.05.2020, 10:02

Besonders unsicher bin ich mir, wenn man das erste oder letzte Element ein "Eins"-Element ist, muss ich dafür eine Sonderbedingung schreiben, da es ja kein pntr.next.prev bzw. pntr.prev.next gibt?

1 Antwort

Vom Fragesteller als hilfreich ausgezeichnet

Destranix

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer, Informatik

12.05.2020, 16:06

Du dürftest Probleme bekommen, da du pntr.next überschreibst wenn pntr.value == 1.

Außerdem musst du selbstverständlich die Spezialfälle abdecken, in denen pntr.next oder pntr.prev nicht existieren.

Das machst du am besten so, dass du erst eine Schleife schaltest, die durchläuft, bis die erste 0 kommt, dann entsprechend alles bis dahin ans Ende hängt und dann mit deiner jetzigen Schleife anfängt.

Die jetzige Schliefe lässt du dann auch nur bis zum vorletzen Element laufen und prüfst beim letzten Element gesondert.

AOMkayyy

Fragesteller

12.05.2020, 16:34

Ich habe die Abgabe vor ein paar Stunden bereits eingereicht und die Spezialfälle habe ich einmal durch ein weiteres if-else-Statement (für den Fall, dass head auf eine 1 zeigt) abgefangen und das Problem mit dem letzten Element habe ich dadurch gelöst, dass ich die for-Schleife nur bis n-1 habe laufen lassen, das das letzte Element ja zw. den Nullen und den Einsen liegt und somit ist es irrelevant, welchen Wert dieses Element nun hat.

Was meinst du mit deinem ersten Satz, dass habe ich noch nicht so ganz verstanden?

Destranix

12.05.2020, 16:43

@AOMkayyy

Wenn du pntr.value == 1 hast, dann setzt du pntr nicht neu. Du bleibst also bei dem einen Element hängen.

AOMkayyy

Fragesteller

12.05.2020, 17:02

@Destranix

Stimmt, dass habe ich leider komplett übersehen. Naja, schade :P Danke dir!

Das Programm ist fast fertig. Benötige Hilfe mit dem Bubblesortunterprogramm.

...zur Frage

Ich soll bei einer doppelt verketteten Liste prüfen ob der Stapel(Stack) leer ist, bevor ich das erste Element lösche,was ist hierbei mit Stapel gemeint?(Java)?

Aufgabenstellung: "Sie haben eine doppelt verkettete liste, fügen Sie bei der Unterklasse Stapel eine Methode ein, die dafür sorgt, dass das erste Listenelement Ihrer Liste gelöscht wird! Zuvor überprüfen Sie, ob der Stapel (Stack) leer ist, ist der Stapel (Stack) leer, so geben Sie eine Nullreferenz zurück, andernfalls löschen Sie das erste Listenelement Ihrer liste und geben Sie gefolgt das Datenelement des ersten Elements als Ergebnis aus!"

Was ist damit gemeint, dass ich schauen soll ob der Stapel leer ist?

(Ist eine selbst erzeugte doppelt verkettete Liste)

...zur Frage

Doppelt verkettete Liste, Java?

Wir haben in Informatik einfach und doppelt verkettete Listen gemacht. In den Folien gibt es auch ein Implementierungsbeispiel einer einfach verketteten Liste. Ich soll jetzt die gleichen bzw. ähnlichen Methoden für eine doppelt verkettete Liste programmieren.

Mein Problem ist, dass ich nicht verstehe, wie ich das machen soll. Ich habe mir verschiedene Beispiele angeguckt und versucht mich schlau zu lesen, aber die Beispiele schienen mir (jedenfalls bei der Implementierung) furchtbar umständlich.

Überall steht, dass sowohl auf den Nachfolger als auch auf den Vorgänger gezeigt wird. Ok, klingt logisch bei doppelt verkettet.

Aber wie sieht bei der Implementierung aus ?

Ich muss ein Element einfügen, entfernen und suchen.

...zur Frage

Wie lösche ich doppelt verkettete Liste in C++ rekursiv?

Hey. Ich möchte ein Funktion void clear_rek() implementieren, aber leider funktioniert es noch nicht. Beim dem rekursiven Aufruf clear_rek(head->next) kommt eine Fehlermeldung. Eigentlich müsste das doch gehen, weil Head ein Attribut der Klasse ist oder? Kann mir vielleicht jemand sagen, wie ich das umsetze?

...zur Frage

Algorithmus zum Sortieren von Spielkarten

Hallo, wir sollen in unserem Informatikkurs einen "Algorithmus zum Sortieren von Spielkarten" erstellen, anfangs in einem Struktogramm. Allerdings habe ich hier keinerlei Anhaltspunkte, kann mir da jemand helfen?

...zur Frage

Wie bei Python mit "If" überprüfen ob Variable mit bestimmten Wert in Liste enthalten ist?

Ich muss für die Schule ein Spiel in Python programmieren. Problem dabei: Uns wurde noch nicht wirklich viel beigebracht und daher verstehe ich nicht, wie ich gewisse Sachen programmieren soll.

Folgendes Szenario bereitet mir nun Schwierigkeiten:

Das Programmierte ist kein Ausschnitt aus meinem Spiel, sondern einfach das gleiche Schema, wie die eine Stelle in meinem Spiel (sonst wäre es zu kompliziert zum verstehen). x hat z.B nicht immer den Wert 5, dieser ändert sich im Verlaufe des Programms.

Ich möchte überprüfen, ob eine der Variable in der Liste einen Wert zwischen 0 und 10 hat. Ist es möglich, dies mit einem "if" Befehl zu lösen? Was müsste bei "Bedingung_erfüllendes_Element" stattdessen stehen? Ich kann da ja nicht ">=0 and <=10" hinschreiben. Das einzige, was ich überprüfen kann, ist ob eine bestimmte Variable in der Liste ist. (z.B if x in liste), aber das möchte ich ja nicht, ich möchte auf den WERT der vorhandenen Variablen überprüfen.

Ich habe es auch schon mit einer For-Schleife probiert, aber da ist da Problem, dass wenn zwei Elemente, welche die Bedingung erfüllen, vorkommen, dass die folgenden Befehle doppelt ausgeführt werden. Es soll aber, für jedes Element, welches die Bedingung erfüllt, ein anderer Text geprintet werden.

Ich brauche wirklich nur diesen einen, eigentlich simplen Befehl, der überprüft, ob es in der Liste mindestens ein Element hat, welches einen bestimmten Wert hat.

...zur Frage

Pyhton - Sortieralgorithmus?

Hallo Zusammen,

Aktuell müssen wir in der Berufsschule ein Lottozahlen Generator schreiben, das dieser 6 Zahlen ausgibt hab ich schon geschafft.

Das zweite wäre das wir die Ausgaben in der in der gezogenen sowie aufsteigend sortierten Reihenfolge ausgeben sollen. Ich hatte schon im Netz gesucht aber nichts gefunden, und jeder Lottozaglengenerator verweist auf die "sort" Funktion hin die wir nicht benutzen dürfen.

Weiß jemand daher wie man diesen Algorithmus schreibt ?

Grüße, YouGetMyAnswer

...zur Frage

C++ / CPP ->Einfach verkettete Liste aufbauen und bearbeiten, wie?

Ich muss verstehen, wie ich einfach verkettete Listen und später noch doppelt verkettete Listen aufbaue, um später Stacks und Queues zu realisieren.

Diese Klasse erzeugt mir ja ein einzelnes Objekt. Ich möchte nun mit der Methode "append" nach und nach eine Liste aufbauen, um dann mit weiteren Methoden mit dieser Liste arbeiten zu können.

Die Methoden, mit denen ich die Liste aufbauen, modifizieren, etc. kann müssen also noch Teil einer neuen weiteren Klasse sein?

Heißt das ich muss über eine Klasse und dessen Methoden auf die Klasse ListElement zugreifen, um dann eine Liste aufzubauen?

Ich bin mit den verschiedenen Klassen und Pointer echt verwirrt, kann mir da jemand helfen? Wie genau muss ich das aufbauen? Sollten die Klassen in einer eigenen Header-Datei liegen oder kann ich auch alles in einer .cpp Datei aufbauen?

...zur Frage

Excel: Ist es möglich Buchstaben innerhalb einer Zelle zu vertauschen?

Und zwar habe ich eine Liste von verschiedenen Zahlen (01;10;101;001;101;011000) und ich möchte sie so sortieren,dass sie zuerst mit den Einsen und danach die Nullen erscheinen ohne die Anzahl der Zahlen zu verändern (10;10;110;100;110;110000).. Aber es klappt bei mir nicht so richtig,,, könnte mir einer helfen?

...zur Frage

Quicksort vs mergesort laufzeit?

Quicksort : worst case (n^2) , average case/best case (n log n) Mergesort : immer n log n

Ich versteh nicht wieso man sagt dass quicksort besser sein soll, wenn mergesort immer mindestens genau so schnell ist wie der best case von quicksort. Hat da jemand eine ahnung wann es sinn macht quicksort zu benutzen ?

...zur Frage

Wie in Python die Quersumme einer Ganzzahl berechnen?

zahl = 123
quersumme = 0
while len(str(zahl)) >= 1:
  str_zahl = str(zahl)
  quersumme = int(str_zahl[0]) + int(str_zahl[1])

????

...zur Frage

Doppelt verkettete Liste?

Hi,

ich verstehe nicht, warum das Entfernen eines Elements in einer doppelt verketteten Liste in der Laufzeit O(1) geschehen kann und nicht, wie bei einer einfach verketteten Liste nur in O(n).

Wenn ich bei einer doppelt verketteten Liste das letzte Element entfernen möchte, müsste ich doch auch über alle Vorgänger iterieren. Genau so wie bei einer einfach verketteten Liste, oder nicht?

...zur Frage

Wie teilt man ein Bild in einzelne Pixel auf?

Wie kann ich ein digitales Bild - keine Ahnung, welches Format; JPG, PNG oder so - vom Computer in einzelne Pixel aufteilen lassen, so dass ich (der Einfachheit halber gehe ich einfach einmal von einem Schwarzweiß-Bild aus) eine einfache Liste Einsen für Schwarz und Nullen für Weiß rausbekomme?

Es geht um viele Bilder, ich kann es also nicht per Hand machen, auch wenn es pro Bild nicht sehr viele Pixel sind.

(Für diejenigen, denen MNIST was sagt: Es geht darum. Wenn ihr eine Methode kennt, die nicht allgemeingültig ist, für MNIST aber funktioniert, habe ich nichts dagegen...)

...zur Frage

Unterschied Algorithmus - Logik?

Gibt es einen Unterschied zwischen den beiden Begriffen? Und wie wirkt er sich aus? Man spricht ja auch in der Softwareentwicklung bei einer Abfolge von Befehlen von Logik. Ist Algorithmus nur ein Unterelement der Logik oder ist Logik sogar auf die gleiche Stufe zu stellen wie Algorithmus?

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen