Aufgabenstellung:

Aufgabenstellung: Entwickeln Sie eine Programm, das in eine verkettete Liste aus einzelnen Buchstaben neue Elemente einfügt. Die Elemente sollen alphabetisch sortiert sein, das heißt nach der Reihenfolge ihrer ASCII-Werte. Es ist möglich, einen Buchstaben mehrmals einzugeben. Eine Mehrfachnennung soll am hinter allen vorhandenen Buchstaben selben Typs eingefügt werden.

Was sind verkettete Listen?
Eine verkettete Liste besteht aus einer Struktur, die ein einen Zeiger auf ihren eigenen Typ enthalten soll. Ein Element a enthält so zum Beispiel den Buchstaben 'x' und einen Zeiger auf das Element b. Um den Anfang einer solchen Liste festzulegen, definieren wir einen Anker, der auf das erste Element zeigt.

typedef struct node
{
struct node *zeiger; // Zeiger auf die Struktur
char zeichen; // Hier wird das Zeichen gespeichert
} elementname;
typedef elementname *anker; // Anker ist ein Zeiger auf ein solches Element

Eine solche Liste könnte schematisch so aussehen:

Der Anker wird im Programmspeicher angelegt, das heißt er steht irgendwo in unserer Funktion main oder eben dort, wo er definiert werden muss. Alle anderen Elemente liegen im HEAP des Programms, dem Stapelspeicher. Die Stelle mit dem Punkt im oberen Kasten markiert das letzte Element. Der rote Strich zeigt eine Verbindung von links nach rechts an. Der Anker kennt also das Element, das ein A beherbergt, dieses kennt ein Element mit einem C usw. Die kleinen Kästen stellen einen Zeiger (struct node *zeiger;) dar, die großen ein Zeichen (char zeichen;). Das letzte Element zeigt ins Nichts (letztes_element.zeiger = NULL;).

Wie füge ich ein Element in eine Liste ein?

Wir gehen vom Anker aus und verfolgen den Pfeil nach rechts. Wir haben also einen Zeiger auf das erste Element, dessen Inhalt wir mit dem einzufügenden Zeichen vergleichen. Ist der ASCII-Wert des Zeichens, das in dem Element steht echt größer als der des Zeichens, das wir einfügen wollen, so haben wir die gesuchte Stelle in der Liste erreicht. Wir müssen nur mit dem malloc-Befehl Speicher für ein neues Element reservieren, den Zeiger, den wir haben auf das neue Element setzten (in unserem Fall hier den Zeiger des Ankers, weil wir ja noch beim ersten Element sind) und den Zeiger des neuen Elementes auf das Element, auf das unser alter Zeiger verwiesen hat. Wir haben also die rote Verbindung an der gewünschten Stelle unterbrochen und ein neues Element dazwischengeschoben.

Sind wir noch nicht fündig geworden, so verfolgen wir eben unsere Zeiger in der Liste weiter, bist wir die richtige Stelle in der Liste gefunden haben. Sind wir am Ende der Liste und haben die Stelle immer noch nicht, so gehört das Zeichen ans Ende. Wir erstellen also ein neues Element mit malloc und setzten dessen Zeiger auf NULL, während der Zeiger des letzten Elementes von nun an auf dieses neue Element verweist.

Sitemap