Ich wollte eine Radix-Sortierung Implementierung mit Warteschlangen erstellen.
Ich konnte nicht herausfinden, welcher Teil meines Codes Probleme hat oder welche Ressourcen ich lesen sollte. Mein Code kann völlig falsch sein, aber das ist meine Implementierung ohne Hilfe (Ich habe noch keinen Kurs Datenstrukturen und Algorithmen genommen).
Ich habe eine Funktion erstellt, aber es hat nicht funktioniert. Während ich recherchierte, sah ich einige Code-Beispiele, aber sie schienen für mich komplexer zu sein.
Erstens Ich wollte die niedrigste Stelle aller Ganzzahlen finden Dann sortieren Sie sie in das Warteschlangenelement, dessen Index übereinstimmt, then Sortieren Sie nach dem Sortieren alle Warteschlangen bis zum Ende des 11. Warteschlangenelements. Sortiere dies im 11. Queue-Element erneut, bis die höchstwertige Ziffer erreicht ist.
Ich könnte die niedrigste Ziffer finden. Und sortiere nach dieser Ziffer. Aber ich konnte keine anderen Ziffern analysieren. Zum Beispiel; Ich könnte 1, 2, 4, 5, 3 sortieren, aber wenn die Zeit kommt, um 2 oder mehr Ziffern zu sortieren, schlägt es fehl ...
Ich hoffe, ich war klar und erklärte mein Problem kurz.
%Vor%Bearbeiten 1 (Einige Fortschritte gemacht)
Ich folgte den Vorschlägen von William Morris. Ich musste dieselbe Frage in CodeReview stellen und er gab mir einige Anweisungen, um meinen Code klarer zu machen.
Ich habe meine Funktion in Funktionen aufgeteilt und auch die Rekursion gestoppt.
Zuerst habe ich eine Funktion "add_to_q" erstellt, die der verknüpften Warteschlange einen Mehrwert hinzufügt und dazu beigetragen hat, die Code-Duplizierung zu umgehen. Übrigens ist James Khourys Weg der einfachste, aber er benutzt wieder Rekursion.
%Vor%Zweitens Ich habe andere Hilfsfunktionen erstellt. Einer ist add_to_elect, der einfach alle Warteschlangenelemente zu der elften Queue hin hinzufügt. Meiner Meinung nach tut es was die Frage will.
%Vor%Drittens ist meine letzte Hilfsfunktion back_to_ints. Sein Zweck ist, die Elemente in der elften Queue zu nehmen und sie durch zehn zu teilen und sie in einem ganzzahligen Array zurückzugeben.
%Vor%Schließlich meine neue Sortierfunktion, die jetzt die ganzen Zahlen in derselben Ziffer sortiert. So dass Zahlen [7] = {112,133,122,334,345,447,346};
%Vor%Ich habe die Frage teilweise gelöst. Wenn Sie die Zahlen in derselben Ziffer sortieren möchten, funktioniert es. Sonst schlägt es fehl. Zum Beispiel sind Ihre Eingaben 112,133,122,334,345,447,346, dann wird das Ergebnis 112 122 133 334 345 346 447 sein. Aber wenn der Benutzer so etwas sortieren möchte (111,13,12,334,345,447,1), gibt es 111 1 12 13 334 345 447 . Also, wie kann ich dieses Problem überwinden?
Außerdem habe ich meine Header-Datei ein wenig geändert.
%Vor%Danke, dass Sie meinen Thread wieder geöffnet haben ...
Ich habe deine Warteschlange ein wenig verändert. Um den Code besser zu verstehen, verwende ich vorne und hinten als globale Variablen.
%Vor%Der Vorgang des Hinzufügens zur Warteschlange wird also
%Vor%Und fügen Sie eine Operation zum Löschen aus einer Warteschlange hinzu (geben Sie auch die Daten zurück)
%Vor%Nun können wir die Radix-Sortierung implementieren. Es kann einfacher sein, Ihre Daten in die Warteschlange mit den tatsächlichen Zahlen als einer einzelnen Ziffer zu verschieben. Beachten Sie, dass die 11. Warteschlange nicht benötigt wird, wenn Sie Ihr Test-Array * arr ändern können und Ihre radix_sort-Funktion könnte wie folgt aussehen:
%Vor%Und schließlich können Sie testen, indem Sie radix_sort (your_array, your_array_size) aufrufen, der vollständige Code ist
%Vor%und die Ausgabe ist
%Vor%Einige gute Informationen hier schon. Auf einer höheren Ebene wird es schwierig sein, Ihren Code zu debuggen, weil er komplexer ist als er sein muss. Unten ist ein anderer Code, der C verwendet, um den Algorithmus in einem mehr idiomatischen Stil auszudrücken.
Der entscheidende Punkt ist, dass weniger Code normalerweise mehr ist: Einfachheit ist dein Freund. Die hier gezeigten Funktionen:
Hier ist die Art:
%Vor%Und der Rest:
%Vor%Ein kleiner Test main:
%Vor%Haftungsausschluss: Ich habe keine Radix-Sortierung implementiert oder den folgenden Code getestet. Das überlasse ich dir als Übung.
Wenn Sie mehr als einmal etwas kopieren und einfügen, halten Sie inne und denken Sie nach: Es muss ein Muster geben.
Ihre switch-Anweisung ist eine Menge Kopieren-Einfügen. In case 1: hast du eine Zeile:
Ich vermute es sollte sein:
%Vor%Wenn Sie diesen Code überarbeitet haben, könnten Sie dies möglicherweise einfacher gesehen haben?
Was ist mit dem Ersetzen der gesamten switch-Anweisung durch:
%Vor%Das Problem, das ich im ersten Codebeispiel gesehen habe, ist das
curNum = curNodep- & gt; element.key
curNum haben immer die volle Nummer und die switch-Anweisung immer curNum% 10 , und dies ist der einzige Test der letzten Ziffer.
In Ihrer Rekursionslösung (Rekursion ist kein Problem) müssen Sie einen Parameter übergeben, um zu wissen, welche Ziffer Sie behandeln müssen.
Ich kenne diese Technik als Immersion.
Wenn Sie sehen, dass die am Ende der Antwort eingegebenen Samples sehen, dass die letzte Ziffer der Orderer ist, können Sie die Eingabe-Samples ändern, um dies besser zu sehen. Fügen Sie große Zahlen mit einer kleinen letzten Zahl hinzu, Beispiel '901', und sehen Sie das Ergebnis.
Entschuldigung für mein Englisch ...
Tags und Links c queue linked-list radix-sort