Die meisten Anfänger gehen davon aus, dass Datenstrukturen statisch sind. Das sind sie nicht. Ein verknüpfter Stapel ist ein dynamisches Biest. Es wächst und schrumpft im Handumdrehen. Sie weisen keinen Speicher vorab zu. Sie greifen zu, wenn Sie es brauchen. Lassen Sie es los, wenn Sie fertig sind.
In diesem Beispiel werden Ganzzahlen verwendet. Ändern Sie „typedef int stack_data“ in „float“ oder „char“, wenn Sie möchten. Die Logik bleibt dieselbe.
Die Schnittstelle
Schauen Sie sich die Kopfzeile an. Es ist ein Vertrag.
„c
/ Stapelbibliothek – Diese Bibliothek bietet die minimalen Stapeloperationen für einen Stapel von Ganzzahlen /
typedef int stack_data;
extern void stack_init();
extern void stack_clear();
extern int stack_empty();
extern void stack_push(stack_data d);
externe stack_data stack_pop();
„
„stack_init“ sorgt für das Chaos. „stack_clear“ löscht es. „stack_empty“ sagt Ihnen, ob noch etwas übrig ist. „push“ schiebt Daten hinein. „pop“ reißt sie heraus.
Einfach. Sauber.
Der Motor
Die Codedatei verbirgt den Mut.
„c
struct stack_rec {
stack_data-Daten;
struct stack_rec *next;
};
struct stack_rec *top = NULL;
„
„top“ zeigt auf das neueste Element. „NULL“ bedeutet leer.
„stack_init“ setzt „top“ einfach auf „NULL“ zurück. Erledigt.
„stack_clear“ wird angezeigt, bis es leer ist. Es ist eine Schleife. Es ist billig.
„stack_empty“ prüft, ob „top“ „NULL“ ist. Gibt 1 zurück, wenn wahr. 0, wenn falsch.
„stack_push“ übernimmt die schwere Arbeit.
„c
void stack_push(stack_data d) {
struct stack_rec temp;
temp = (struct stack_rec )malloc(sizeof(struct stack_rec));
temp->data = d;
temp->next = top;
oben = temp;
}
„
Es reserviert Speicher. Legt die Daten fest. Verbindet es mit dem alten Oberteil. Updates „oben“.
„stack_pop“ kehrt den Vorgang um.
„c
stack_data stack_pop() {
struct stack_rec *temp;
stack_data d = 0;
if (top != NULL) {
d = top->data;
temp = oben;
top = top->next;
frei(vorübergehend);
}
return(d);
}
„
Es erfasst die Daten. Bewegt sich von oben nach unten. Gibt den alten Knoten frei. Gibt den Wert zurück.
Ist der Stapel leer? Es gibt Müll zurück. Springen Sie nicht von einem leeren Stapel.
Informationen verbergen
Das ist der Schlüssel.
Sie sehen nur die Kopfzeile. Sie sehen den Code nicht.
Der Stapel könnte Arrays verwenden. Hinweise. Dateien. Eine verknüpfte Liste. Es spielt keine Rolle.
Solange die Schnittstelle funktioniert, ist es Ihnen egal, wie sie aufgebaut ist.
Das sind Informationen, die versteckt werden. Es ist nicht nur ein Schlagwort. Auf diese Weise erstellen Sie Software, die nicht kaputt geht, wenn Sie die Interna ändern.
C Fallstricke
C verzeiht keine Fehler.
- Klammern sind wichtig. „(p).i“ ist nicht dasselbe wie „ p.i“. Man dereferenziert zuerst den Zeiger. Der andere greift auf das Mitglied zu und dereferenziert es dann. Wenn man es falsch macht, stürzt man ab.
- Speicherlecks. Setzen Sie niemals einfach „top = NULL“. Sie verwaisten jeden Knoten in der Liste. Sie verlieren die Daten. Du verlierst die Erinnerung. Verwenden Sie „kostenlos“. Stets.
- Header einschließen. „NULL“ lebt in „stdio.h“. Wenn Sie es vergessen, wird Ihr Code möglicherweise auf einigen Compilern kompiliert. Bei anderen wird es das nicht tun. Oder es definiert „NULL“ auf seltsame Weise als Null. Schließen Sie „
“ ein, wenn Sie Zeiger verwenden.
Was kommt als nächstes?
Der Grundstapel ist einfach. Echte Stacks brauchen mehr.
Fügen Sie „dup“ hinzu. Duplizieren Sie das obere Element. Fügen Sie „count“ hinzu. Gibt die Anzahl der Artikel zurück. Fügen Sie „hinzufügen“ hinzu. Platzieren Sie die oberen beiden, fügen Sie sie hinzu und drücken Sie das Ergebnis.
Erstellen Sie ein Treiberprogramm. Schreiben Sie ein Makefile. Kompilieren Sie es. Führen Sie es aus.
Wenn es abstürzt, haben Sie ein „kostenloses“ verpasst. Oder Sie haben auf freigegebenen Speicher zugegriffen. Debuggen Sie es.
Der Realitätscheck
Die dynamische Zuordnung erfolgt schnell. Bis es nicht mehr so ist.
„malloc“ und „free“ haben Overhead. In engen Schleifen summiert es sich.
Aber für den allgemeinen Gebrauch? Es ist flexibel. Es ist Standard. Das ist es, was Sie in den meisten C-Codebasen sehen werden.
Der verknüpfte Stapel ist ein Baustein.
Sie verwenden es für Funktionsaufrufe. Zur Ausdrucksauswertung. Für Schaltflächen zum Rückgängigmachen.
Es ist überall.
Denken Sie daran: Wenn Sie es zuweisen, geben Sie es frei. Oder aber.
„Code ist wie Humor.“
