verlinkte Liste - Stapel Building - C - Ist das Tutorial richtig

Question

Ich versuche, ein durch einen Informatikkurs auf coursebuffet.com zu arbeiten, die mich saylor.org bezeichnet, die this gab mir zu erfahren, wie ein implementieren Stack mit einer verketteten Liste in C.

Erstens, ich glaube, ich habe das Konzept verstanden, aber wenn Sie so nett sein und unten in den Link scrollen, finden Sie am Ende davon einen Link zu einer Hauptdatei, mit denen Sie Ihre Implementierung testen sollten. Und was absolut verblüfft mich für die letzten zwei Tage (ja, das ist, wie viel Zeit ich schon in diesem einen Problem sank) ist die folgende Passage:

/* 
    * Initialize the stack. Make it at least 
    * big enough to hold the string we read in. 
*/ 
StackInit(&stack, strlen(str)); 

Ich kann nicht verstehen, wie eine verknüpfte Liste zu initialisieren. Ich meine, das ist gegen sein Konzept, nicht wahr? Ich würde struct Elemente erstellen müssen, bevor sie mit Push-Befehlen gefüllt werden, aber wenn ich das tue, muss ich dem Stapel in zwei Richtungen folgen. Eine Richtung zum Schieben und die entgegengesetzte Richtung zum Knacken. Das würde zwei Zeiger benötigen. Ich dachte, das ganze Konzept wäre ein Datenelement und ein Zeiger pro ADT-Einheit.

Kann mir bitte jemand das erklären?

Answer 1

Wenn Sie Liste initialisieren Länge der Zeichenfolge, die Sie lesen möchten, sein, werden Sie noch Zeiger haben Stack auf das erste Element der Liste zeigt. Also im Grunde ist nichts verloren. Wie auch immer, Sie haben Recht, es ist sinnlos, so etwas zu tun.

Es ist keine doppelte verkettete Liste erforderlich. Der Stapelzeiger zeigt immer auf das erste Element. Grundsätzlich, wann immer Sie wollen push() werden Sie neue Knoten an den Anfang der Liste hinzufügen, und wann immer Sie möchten, pop() werden Sie den ersten Knoten der Liste entfernen.

Answer 2

Angenommen, Stapel bedeutet nur LIFO-Betrieb. d. h. der letzte wird der Erste sein, der herauskommt.

Lassen Sie uns nun überlegen, wie wir es umsetzen möchte.

Erste Wahl: Nur ein internes Array fester Größe haben. In diesem Fall haben Sie nie die Möglichkeit, die Größe im Handumdrehen zu ändern. Daher ist der Kommentar über Stack-Init gültig, dass Sie eine Größe zuweisen sollten, von der Sie denken, dass sie für diesen Zweck sicher ist.

Zweite Wahl: Mit einem Array, aber mit dynamischen Speicher. In diesem Fall können Sie, selbst wenn Sie das Limit des vorhandenen Stapels erreichen, die Größe immer durch Realloc erweitern. Kommentar macht also keinen Sinn.

Dritter Wahl: Mit Linkliste, also in der Theorie, auch wenn Sie den Stack mit 0 Größe initialisieren, sollte es auf jeden Knoten Einfügen erweitern, so der Kommentar ist irreführend. Nur um hinzuzufügen, oben ist immer der Kopf der Linkliste, und mit jeder Einfügung wird neuer Knoten neuer Kopf.

So Ihre Frage zu beantworten, ist der Kommentar über verwirrend und nur dann sinnvoll, wenn die interne Implementierung Array basiert.

Aber in den gesunden Menschenverstand und allgemeine Wahrnehmung assoziiert DS Stack, ist Stack-DS, die immer Tiefe Stack zugeordnet ist. Und wenn dies implementiert wird, ist es immer sicher, maximale Anzahl von Elementen zu haben, die geschoben werden können, und ich denke, das könnte ein Kommentar sein.

Um es mit einem realen Beispiel weiter zu veranschaulichen, müssen Sie von Callstack von Funktionen gehört haben, obwohl es in der Theorie erweitert, aber MAX mögliche Grenze hat, und das ist der Grund, dass wir Stapelüberlauffehler sehen, wenn wir unendliche Rekursion durchführen.