Algorithmus zum kopieren von einem Stapel
Ist es möglich, zum kopieren von einem Stapel auf einen anderen, in C ohne Verwendung externer stack oder array?
Ich weiß, dass es getan werden kann mithilfe von Rekursion, aber gibt es andere mögliche Lösung um dies zu tun innerhalb der genannten Einschränkungen?
- Sie sollten den Begriff "stack" hier. ist es eine Daten-Struktur, die Sie kennen? Denn wenn ein stack ist eine black box, die Sie anwenden können
push
undpop
zu, die Sie selbst nicht duplizieren Sie es, ohne mit der Freigabe und dann schieben Sie alles wieder zurück. - Normalerweise wird diese Art von Problemen sind die Hausaufgaben, so dass Sie markiert werden soll, geeignet
- ich fand dieses problem online , seine Hausaufgaben nicht.
- Mit Rekursion ist mit einem externen stack.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ja, es ist möglich, aber es ist gehen zu nehmen
O(N^2)
. Betrachten StapelS
(Quelle) undT
(Ziel).count
nullE
aus dem StapelS
, dann drücken Sie die restlichen Daten auf stackT
verlassencount
Elemente auf stackS
E
obenS
T
zuS
count
S
, gehen Sie zurück zu Schritt 1S
und drücken Sie aufT
Schritte 0 bis 5 reverse stack
S
in place; Schritt 6 bewegt es überT
Umkehr der Ordnung und die Herstellung einer Kopie des Originals. Es ist eine destruktive Kopie, denn das original-stack ist nun leer.count
hier? Ich bin nur in der Lage, dies zu tun für einen festenStack
Größe. Ich hoffe, dass jemand helfen könnte.count
verwendet wird.if
: wir verwenden zwei verschachtelte Schleifen mit einerif
innerhalb der äußeren Schleife. Es wird wieder eine Schleife am Ende der Implementierung Schritt 7.Es ist nicht sehr effizient, aber ja es ist machbar.
Zitieren ugoren, das ist ähnlich wie der Turm des "Hanoi mit 2 Zapfen, plus einer Konstanten Anzahl von 1-Disk-storage-spaces"
Ok, ich werde meine eigene Visualisierung und eine Lösung für eine echte nicht-destruktive Kopie von einem Stapel auf einen anderen.
Also haben wir ein paar stacks
S
undT
können wir uns vorstellen, Sie wachsen in Richtung zu einander wie diese:Betrachten wir die gesamte Datenstruktur als eine Sequenz
(S0, S1, S2, ...., T2, T1, T0)
führen wir Aktionen verschieben oder kopieren, die ein bestimmtes element von positioni
zu positionierenj
. Wie tun wir das? Bewegen wir uns durch diese Folge in kleinen Schritten wie diesem:Dann können wir haben Zugriff auf ein beliebiges element, vergessen Sie es, dann wechseln Sie zu einer anderen position und setzen Sie das element dort. Hier ist die Helfer Funktion:
Also mit diesen Operationen, die wir im Grunde genommen verwandeln die Sequenz
(S0,S1,S2,...,SN)
zu(S0,S1,S2,...,SN,SN,SN-1,...,S2,S1,S0)
.Und hier ist der Algorithmus:
T
sobald Sie fertig sind mit dem Umzug zurück nachS
effektiv duplizieren der Sache.Es ist ein O(N) - operation, weil der stack ist ein kontinuierlicher region bekannt, Anfang und Ende, das kann
memlcpy()
odermemcpy_s()
von einem Prozess auf den gemeinsam genutzten Speicher oder per IPC. Ideal ist es, wenn Sie einige dieser Prozess der Wiedergabe oder live-migration-code, überprüfen Sie, dass die Datenstrukturen und ABI sind nahe genug, bevor etwas zu tun. Auch, kopieren Sie den heap. Dann, der trick ist, die Einstellung eine Magische variable, die irgendwo um anzuzeigen, dass ein Prozess warten sollte, um bereit zu laufen, während der andere sollte Herunterfahren. Datei-handles, Mutexe, Semaphoren und andere kernel-Modus-Staat würde kopiert werden müssen auch. Es ist billiger, entweder a)fork()
was bedeutet all dies für Sie, ODER b) eine checkpoint-Lage Reaktor (stack, heap und externe Ressourcen), das "anhalten der Welt" anhalten aller threads und starten Sie alle in der Kind-Prozess, bevor es zu töten. Ich würde fork() + exec() und kopieren Sie die stack-und heap. Es muss wahrscheinlich sein, ein ergänzender Eintrag Zeiger patch Tabelle (array mit zwei Zeigern: alte pointer -> neuen Zeiger), müssen die patch-Codes, Stapel, Haufen, Konstanten-Tabelle, um nicht zum Absturz.