Twitter und Facebook-Anbindung
X
Tweet Follow @twitterapi
!!! Anbindung an twitter und facebook öffnen !!!

Wenn Ihnen mein Online-Buch gefällt,
dann bedanken Sie sich doch mit einer kleinen Spende...

10 Variablen IV

10 Variablen IV

Da Sie nun die grundlegenden Datentypen kennen, werde ich Ihnen in den folgenden Kapiteln zeigen, was Sie mit den gegebenen Werkzeugen anstellen können, denn jetzt kommen die wirklich abstrakten Geschichten, nähmlich die Listen und Bäume.

Zum Seitenanfang
Zum Inhaltsverzeichnis

10.3 Bäume

10.3 Bäume

Ein Baum besteht aus einer "Wurzel", welche auf andere Bäume werweist. Die Liste ist ein Spezialfall des Baumes. Man hat wieder ein Wurzelelement mit mehreren Zeigern, welche auf unterschiedliche Elemente verweisen. Dieses Prinzip lässt sich an einem Stammbaum gut veranschaulichen.

Grundschema eines Binärbaumes

Das erste Element heißt wie gesagt "Wurzel" oder auch "Vaterelement". Die Zeiger sind "Zweige" und verweisen auf die "Tochterelemente" oder auch "Knotenpunkt" genannt. Jene können ihrerseits Wurzelelemente von Unterbäumen, also "Ästen" sein. Die letzten Elemente an einem Baum, nennt man "Blätter". Die zwei Zeiger in den Blattelementen, zeigen auf "NULL".

Zum Anlegen und Löschen von Elementen in einem Baum, ist es zwingend notwendig zu wissen, wie man erst einmal ein Element findet, an welches man ein weiteren Baum anhängen oder löschen will. Hierfür gibt es drei Methoden, mit denen man wirklich jedes Element in einem Baum findet.

Alle drei Methoden funktionieren ähnlich und sind Rekursiv. Man geht immer nach links, bis man "NULL" erreicht. Danach schaut man, ob es nach rechts geht. Ist dies der Fall, tut man dies einmal und geht wieder immer nach links, bis man letztendlich ein Blatt erreicht, also eines der letzten Elemente. Danach geht man wieder einen Schritt zurück, also zum Vaterelement des Blattes. Dort wieder angelangt, geht man nach rechts, es sei denn, man war dort schon. In diesem Fall geht man wieder ein Schritt zurück und so weiter. Der Unterschied zwischen diesen drei Verfahren, ist der Zeitpunkt der Ausgabe der Werte. Ich werde dies nun an einem Beispiel verdeutlichen:

Ausgeglichener Binärbaum mit sortierten numerischen Elementen

Zum Seitenanfang
Zum Inhaltsverzeichnis

10.3.2 Inorder

10.3.2 Inorder

Inorder heißt, die Ausgabe erfolgt mittendrin, also erst das nach links gehen, dann die Ausgabe und schließlich das nach rechts Gehen.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
					
// ...

// Erst links, dann Ausgabe, dann rechts //////////////////////////////////////
void InorderPrint(PIntegerTreeItem pHelpItem) {
	// Rekursionsbedingung
	if (pHelpItem != NULL)  {
		// Selbstaufruf der Funktion (nach links gehen)
		InorderPrint(pHelpItem->pLeftItem);

		printf("%i ", pHelpItem->iValue);

		// Selbstaufruf der Funktion (nach rechts gehen)
		InorderPrint(pHelpItem->pRightItem);
	} // end of if
} // InorderPrint /////////////////////////////////////////////////////////////

// ...

InorderPrint(pRootItem);

// ...
					

Ausgabe:

25 50 75 100 125 150 175
		

Dieses Verfahren ist das am häufigsten verwendetest. Wenn der Computer z.B. ein Verzeichnis mit allen Unterverzeichnissen und seinen Dateien auf ein Schlüsselwort durchsucht, geht er so vor.

Zum Seitenanfang
Zum Inhaltsverzeichnis

10.3.1 Preorder

10.3.1 Preorder

Preorder heißt, es erfolgt erst die Ausgabe, dann das nach links Gehen und schließlich das nach rechts Gehen.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
					
// ...

// Erst Ausgabe, dann links, dann rechts //////////////////////////////////////
void PreorderPrint(PIntegerTreeItem pHelpItem) {
	// Rekursionsbedingung
	if (pHelpItem != NULL)  {
		printf("%i ", pHelpItem->iValue);
		
		// Selbstaufruf der Funktion (nach links gehen)
		PreorderPrint(pHelpItem->pLeftItem);
		// Selbstaufruf der Funktion (nach rechts gehen)
		PreorderPrint(pHelpItem->pRightItem);
	} // end of if
} // PreorderPrint ////////////////////////////////////////////////////////////

// ...

PreorderPrint(pRootItem);

// ...
					

Ausgabe:

100 50 25 75 150 125 175
		

Erklärung

Wird die Funktion aufgerufen, wird zunächst einmal der Zeiger übergeben, welcher auf das Wurzelelement verweist. Die Variable "pHelpItem" erhält nun diese Adresse/Referenz. Nun beginnt die Suche, es sei denn, der Baum ist leer. Als erstes wird der erste Wert ausgegeben, die "100". Jetzt ruft sich die Funktion erneut auf und übergibt den Zeiger, welcher auf den linken Baum zeigt. Die Variable "pHelpItem" zeigt nun auf das linke Tochterelement. Da hier noch nicht Schluss ist, wird die "50" ausgegeben und der Zeiger nach links wird wieder, im Selbstaufruf der Funktion, übergeben. Das Laufelement verweist wiederum auf die nächste linke Tochter (Enkelin). Auch hier ist noch nicht Schluss, also das Hilfselement ist nicht "NULL". Die "25" wird ausgegeben. Auch jetzt findet wieder der Selbstaufruf statt. Da aber nun "NULL" übergeben wird, läuft die Funktion normal durch, überspringt aber die if Anweisung. Die Funktion ist beendet. Aber nun sind ja noch Aufgaben offen. Der Computer springt zurück an die Stelle, wo er das letzte Mal nach links gegangen ist und setzt dort gleich wieder mit dem nächsten Befehl ein. In diesem Fall wäre dies jetzt der Selbstaufruf nach Rechts. Auch hier wird "NULL" übergeben. Dieser Unterast ist nun abgearbeitet. Der Computer springt ein weiteres Mal zurück, weil immer noch Aufgaben ausstehen. Wiederum steht als nächstes der Selbstaufruf an und ein Zeiger nach rechts wird wieder übergeben. Das Hilfselement verweist nun auf das rechte Tochterelement, des linken Tochterelementes des Wurzelelementes. Nun wird die "75" ausgegeben und es findet wieder ein Selbstaufruf nach links statt.
...

Hat der Computer alle Aufgaben erledigt, so ist die Rekursion beendet und man hat alle Werte.

Zum Seitenanfang
Zum Inhaltsverzeichnis

10.3.4 Löschen von Elementen

10.3.4 Löschen von Elementen

Das Erstellen von Bäumen kann man nicht verallgemeinern, da die Kriterien für die Ordnung im Baum je nach Aufgabenstellung unterschiedlich sein können. Oftmals ist der Baum auch nicht sortiert und oder ausgeglichen, also der linke Ast ist beispielsweise viel größer als der rechte.

Das Löschen eines kompletten Baumes ist jedoch einfach. Um alle Elemente zu löschen, muss man erst einmal alle finden. Wie dies funktioniert, habe ich eben beschrieben. Man nimmt hierfür immer die Postorder. Anstatt der Ausgabe steht nun ein "delete" (bzw. ein "free", wenn man mit "malloc" arbeitet).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
					
// ...

// Löscht ein Element/Ast aus dem Baum ////////////////////////////////////////
void DeleteTree(PIntegerTreeItem pHelpItem) {
	// Rekursionsbedingung
	if (pHelpItem != NULL) {
		DeleteTree(pHelpItem->pLeftItem);
		DeleteTree(pHelpItem->pRightItem);

		delete pHelpItem;
	} // end of if
} // DeleteTree ///////////////////////////////////////////////////////////////

// ...

DeleteTree(pRootItem);

// ...
					

Andere Verfahren würden die Knotenpunkte frühzeitig löschen und man könnte alle Unterbäume an ihnen nicht mehr freigeben. Mit Preorder würde beispielsweise gleich das Wurzelelement gelöscht werden, jedoch nicht seine Äste. Was dies zur Folge hat, wurde von mir bereits erwähnt.

Wenn man ein einzelnes Element aus dem Baum löschen will, so bedarf es ein wenig Denkarbeit. Zunächst muss man das entsprechende Element suchen (wie, ist egal) und dann muss man prüfen, um was es sich für ein Element handelt. Hierbei können vier Fälle auftreten.

Abschließend möchte ich zu diesem Thema noch sagen, dass das Sortieren von Bäumen mindestens genauso spaßig ist, wie das Löschen. Im Endeffekt läuft es aber darauf hinaus, dass man so lange Element sucht, welche nicht an der richtigen Stelle stehen, bis alles ok ist. Die falsch positionierten Elemente löscht man aus dem Baum (also nur abhängen und nicht freigeben) und sortiert sie anschließend neu ein (man lässt sie durch rieseln). Alternativ kann man auch einen komplett neuen Baum aufbauen, was aber nicht unbedingt schneller sein muss (auch wenn man es im ersten Moment vermuten könnte). Allerdings sortiert man nicht im Nachhinein Bäume, sondern sorgt gleich beim aufbauen, dass eine Sortierung vorliegt. Dafür gibt es auch verschiedene Konzepte, wie z.B. s.g. AVL-Bäume, Rot-Schwarz-Bäume oder die s.g. B bzw. B* Bäume. Für die entsprechenden Konzepte gibt es dann auch spezielle Regeln, wie Elemente gelöscht werden. Da dies aber eher in die theoretische Informatik geht und ich mich mehr auf C bzw. C++ konzentrieren möchte, belasse ich es hiermit dabei. Notfalls wissen Sie jetzt aber, über welche Themen Sie sich noch informieren müssten.

Zum Seitenanfang
Zum Inhaltsverzeichnis

10.3.3 Postorder

10.3.3 Postorder

Postorder heißt, die Ausgabe erfolgt als letztes, also erst das nach links gehen, dann das nach rechts gehen und erst danach die Ausgabe.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
					
// ...

// Erst links, dann rechts, dann Ausgabe //////////////////////////////////////
void PreorderPrint(PIntegerTreeItem pHelpItem) {
	// Rekursionsbedingung
	if (pHelpItem != NULL)  {
		// Selbstaufruf der Funktion (nach links gehen)
		PostorderPrint(pHelpItem->pLeftItem);
		// Selbstaufruf der Funktion (nach rechts gehen)
		PostorderPrint(pHelpItem->pRightItem);

		printf("%i ", pHelpItem->iValue);
	} // end of if
} // PreorderPrint ////////////////////////////////////////////////////////////

// ...

PostorderPrint(pRootItem);

// ...
					

Ausgabe:

25 75 50 125 175 150 100
		
Zum Seitenanfang
Zum Inhaltsverzeichnis

10.1 Zeichenketten / Strings

10.1 Zeichenketten / Strings

Die Strings sind mit die wichtigsten Datentypen in der Programmierung, da viele Problemstellungen auf den Umgang mit solchen Zeichenketten beruhen. Das fängt beim Bearbeiten von Dateien an und hört bei der Netzwerkkommunikation auf. Allerdings ist dieses Kapitel, gerade in C, eines der kompliziertesten überhaupt. Wenn Sie mit Strings umgehen können, können Sie behaupten, Pointer verstanden zu haben. Komplizierter wird es dann nicht mehr.

Die Grundidee von Strings ist, sie in einem Array abzubilden, sodass jedes Zeichen in einem separaten Feld steht. Im Gegensatz zu anderen Programmiersprachen, gibt es in C nur s.g. Null-Terminierte-Strings (in C++ gibt es dann auch andere klassenbasierte Strings). Dies bedeutet, dass jeder Zeichenkette, das ASCII-Zeichen "\0" (also der Wert nul und nicht die Zahl null) an gehangen wird, um zu signalisieren, dass das Wort bzw. der Satz, zu Ende ist. Dies muss immer berücksichtigt werden, wenn man Speicher reserviert bzw. eine Puffergröße angeben soll.

Ein Stringarray anhand eines Zuges

Zum Seitenanfang
Zum Inhaltsverzeichnis

10.1.2 Dynamische Strings

10.1.2 Dynamische Strings

Da Strings ja, wie bereits erwähnt, nur Felder sind, kann man auch sie dynamisch erzeugen und verwalten.

Das Schema sieht so aus:
char* <Variable> [= "<Zeichenkette>"]|[= new char[<AnzahlDerZeichen>]]

 1
 2
 3
 4
 5
					
char* pcstrZeigerAufKonstante	= "Ich bin ein Zeiger auf eine statische Konstante.";
printf("%s\n", pcstrZeigerAufKonstante);

pcstrZeigerAufKonstante		= "Jetzt zeige ich auf eine andere Konstante.";
printf("%s\n", pcstrZeigerAufKonstante);
					

Ausgabe:

Ich bin ein Zeiger auf eine statische Konstante.
Jetzt zeige ich auf eine andere Konstante.
		

Obwohl ich in Zeile 1 einen Pointer deklariert haben, darf dieser in diesem Spezialfall nicht freigegeben werden! Der Grund dafür ist folgender. Intern legt der Compiler eine Konstante an und die Referenz auf diese Konstante wird an den Pointer übergeben. Versuchen man jetzt, den Speicher freizugeben, wird dies zu einer Schutzverletzung führen, da man mit Konstanten nichts machen darf.

Genauso dürfen Sie jetzt nicht den Inhalt der Zeichenkette ändern, weder per Funktion noch per Indexzugriff. Das einzige was Sie machen dürfen ist, wie in Zeile 4 gezeigt, den Zeiger auf eine andere Konstante zeigen lassen. Dabei sei erwähnt, dass dabei kein Speicher verloren geht, weil sich der Compiler um die Speicherverwaltung von Konstanten kümmert. Das war auch der Grund, warum ich hier keine Größe für den String angeben musste.

 1
 2
 3
 4
 5
 6
 7
 8
					
char* pstrZeigerAufDynamischenString	= new char[80];

strcpy_s(pstrZeigerAufDynamischenString, 80, "Ich bin ein dynamischer String.");
printf("%s\n", pstrZeigerAufDynamischenString);

pstrZeigerAufDynamischenString[30]	= '!';
printf("%s\n", pstrZeigerAufDynamischenString);
delete [] pstrZeigerAufDynamischenString;
					

Ausgabe:

Ich bin ein dynamischer String.
Ich bin ein dynamischer String!
		

In diesem Beispiel zeige ich, wie man selbst die Speicherverwaltung für Strings übernimmt und genau das, sehen Sie in Zeile 1 und 8. Jetzt muss man allerdings aufpassen, dass man erstens genug Speicher reserviert und man darf unter keinen Umständen, dem String eine Referenz auf eine Konstante zuweisen, wie ich das im Vorherigen Beispiel getan habe. Der Grund dafür liegt auf der Hand. Mit dem Zuweisen einer neuen Referenz, verliert man den Bezug zum vorher reservierten Speicher und somit kann jener nicht mehr freigegeben werden (Speicherleck).

Jetzt darf man aber wieder Stringfunktionen benutzen und man kann auch wieder den Inhalt über den Indexzugriff manipulieren. Dies zeige ich in Zeile 3 und 6.

Zum Seitenanfang
Zum Inhaltsverzeichnis

10.1.1 Statische Strings

10.1.1 Statische Strings

Wie Sie das von Arrays kennen, kann man logischerweise auch die Strings statisch erzeugen. Dies hat zur Folge, dass Sie sich nicht um die Speicherreservierung kümmern müssen.

Die statischen Arrays sind am leichtesten zu verwalten und man braucht auch nicht so viele Dinge zu beachten, aber leider werden sie im Stack des Arbeitsspeichers gehalten und somit kann man keine Massen an Informationen halten, wie das z.B. eine Textverarbeitung macht. Nichts desto trotz, werde ich kurz demonstrieren, was man machen kann und Hinweise geben, was Sie unterlassen sollten.

Vorab sei noch erwähnt, dass man einzelne Zeichen in einfache Anführungszeichen setzt, wohingegen ganze Zeichenketten, in doppelte Anführungszeichen gesetzt werden. Man kann auch ein einzelnes Zeichen in doppelte Anführungszeichen setzen, allerdings wird dieses Zeichen dann wie ein String behandelt und somit wird noch das ASCII Zeichen "0" an gehangen, wodurch zwei Byte benutzt werden, um einen Buchstaben zu speichern. Seien Sie sich dessen immer bewusst.

Das Schema sieht so aus: char <Variable>[<AnzahlDerZeichen>] [= "<Zeichenkette>"]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
					
#include <string.h>

// ...

char astrStatischerString1[80]		= "Mein Inhalt wurde von einer Konstante kopiert.";
printf("%s\n", astrStatischerString1);

astrStatischerString1[45]		= '!';	// Einzelnes Zeichen wird manipuliert
printf("%s\n", astrStatischerString1);

char astrStatischerString2[20];
strcpy_s(astrStatischerString2, 20, "Ich bin statisch.");
printf("%s\n", astrStatischerString2);

astrStatischerString2[16]		= '!';
printf("%s\n\n", astrStatischerString2);

char astrStatischerString3[1001];
printf("Bitte Satz eingeben (max 1000 Zeichen):\n");

gets_s(astrStatischerString3, 1001);
printf("Ihre Eingabe lautet:\n%s\n", astrStatischerString3);
					

Ausgabe:

Mein Inhalt wurde von einer Konstante kopiert.
Mein Inhalt wurde von einer Konstante kopiert!
Ich bin statisch.
Ich bin statisch!

Bitte Satz eingeben (max 1000 Zeichen):
Hallo Welt
Ihre Eingabe lautet:
Hallo Welt
		

Ihnen ist vielleicht aufgefallen, dass meine Arrays alle größer sind, als sie es sein müssten. In Zeile 5 reserviere ich 80 Elemente, obwohl 46 + 1 (Terminator) ausreichen würden. Diese Vorgehensweise ist allerdings üblich, da man zum einen zu faul zum zählen ist und zum Anderen nie weiß, was noch kommen könnte. Wie der Name "statisch" bereits suggeriert, kann man die Größe im Nachhinein nicht mehr ändern. Des Weiteren sehen Sie, wie ich gleich eine Konstante zuweise, oder um ganz korrekt zu sein, dem Compiler in Auftrag gebe, den Inhalt einer konstanten Zeichenkette, in mein Array zu kopieren.

In Zeile 8 und 15 manipuliere ich den Inhalt meines Arrays. Ich mache aus dem Punkt im Satz, ein Ausrufezeichen. Sie lernen also daraus, dass Sie statische Zeichenketten nach Belieben manipulieren können.

In den Zeilen 6, 9, 13, 16, 19 und 22 zeige ich, wie man Strings einfach ausgeben kann, ohne das Array durch iterieren zu müssen. Man benutzt "%s". Achtung! Dies funktioniert nur mit Zeichenketten. Arrays mit Integern z.B. können nicht so ausgegeben werden.

Zeile 12 zeigt, wie Sie mit Stringfunktionen umgehen müssen, wenn Sie statische Arrays benutzen. Entscheidend bei den Funktionen mit "_s" ist, dass man immer noch die Größe des Arrays angeben muss. (Achtung - Nicht die Länge des Wortes, welches ja unter Umständen kürzer sein kann!)

Im dritten Abschnitt, ab Zeile 21 zeige ich, wie man in einen String Werte/Sätze einlesen kann. Hierbei gibt es zwei Besonderheiten. Zum einen braucht man den "&" Operator nicht, da ein Array ja schon ein Zeiger ist und es besser ist die Funktion "gets" bzw. "gets_s" zu benutzen, da "scanf" bzw. "scanf_s" lediglich ein Wort einlesen. Sobald in der Eingabe ein Leerzeichen auftaucht, wird der String abgeschnitten.

Zum Seitenanfang
Zum Inhaltsverzeichnis

10.1.4 Konstante Strings und Stringkonstanten

10.1.4 Konstante Strings und Stringkonstanten

Um noch einen drauf zu setzen, möchte ich Ihnen noch die konstanten Strings zeigen. Sie werden in einem separaten Konstantenspeicher gehalten und vom Compiler verwaltet. Im Stack befindet sich dann nur noch eine Referenz, also ein Pointer auf diese Konstante. Man hat also einen quasi dynamischen String. Als es eben um dynamische Strings ging, habe ich schon kurz gezeigt, dass man einen Pointer auf einen konstanten Wert zeigen lassen kann. Ich habe auch dazu gesagt, dass es möglich ist, diesen Zeiger dann zur Laufzeit auf eine andere Konstante umzubiegen. Wenn man aber bei der Variablendeklaration den Modifikator "const" mit vor den Typ schreibt, ist dies auch nicht mehr möglich. Dies wird in der Regel aber nur in Funktionsköpfen getan, um den Nutzer der Funktion zu garantieren, dass sein String unverändert bleibt.

An folgendem Quelltext möchte ich noch einmal die Unterschiede klar machen.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
					
const char*	astrConstString		= "konstant";
char*		pcstrConstString	= "konstant";
char		aStaticString[10]	= "statisch";

char*	pstrDynamicString		= new char[10];
strcpy(pstrDynamicString, "dynamisch");

printf("%s\n", astrConstString);	
printf("%s\n", pcstrConstString);
printf("%s\n", astrStaticString);
printf("%s\n", pstrDynamicString);

aConstString2				= "Konstant";	// Verweis auf neue Konstante
aStaticString[0]			= 'S';		// Zeichen Austauschen
pstrDynamicString[0]			= 'D';		// Zeichen Austauschen

printf("%s\n", aConstString2);
printf("%s\n", aStaticString);
printf("%s\n\n", pstrDynamicString);

delete [] pstrDynamicString;
					

Ausgabe:

konstant
konstant
statisch
dynamisch

Konstant
Statisch
Dynamisch
		

Speicherverwaltung verschiedener Stringtypen vor Änderungen

Hier sind zunächst die drei Speicherbereiche gut ersichtlich. Der Stack ist ja der Speicher, welcher zwar nicht so groß ist, aber auf welchem wir bedenkenlos Daten anlegen können, ohne uns um deren Verwaltung zu kümmern.

Der Const-Speicher ist ein Speicherbereich, welcher vom Compiler bereit gestellt wird und mit jedem Programmstart reserviert wird. Der Zugriff ist ausschließlich lesend und die Verwaltung übernimmt der Compiler. Er ist es auch, welcher für eine automatische Größe sorgt. Versucht man einen String auf eine Konstante zu löschen, geht das zwar im ersten Moment, aber spätestens beim Programmende, wird es einen Fehler geben, weil der Compiler Code eingefügt hat, um dies zu tun (und somit würde es doppelt passieren).

Der Heap ist der größte Bereich des Speichers und auf ihn kann man nur über eine Referenzierung heran kommen. Speicherplatz muss selbst erstellt und freigegeben werden. Wenn man versucht einen Zeiger auf einen solchen String auf eine Konstante biegt, ist das zwar im Moment ok, aber der reservierte Platz kann nicht mehr freigegeben werden, da man nicht mehr weiß, wo der Speicherbereich ist, der freizugeben ist.

In der Grafik ist auch schön zu erkennen, dass sowohl der Zeiger auf die Konstante, als auch der Zeiger auf den dynamischen String, im Stack liegen, aber dann wo anders hin verweisen. Lediglich der statische String wird komplett im Stack gehalten. Schaut man sich aber den Quelltext dazu an, sieht man nicht so schnell den Unterschied.

Gerade der Unterschied zwischen Zeile 2 und 3 ist wichtig. Ich hatte ja mal gesagt, dass man ein Array bei der Definition entweder mit dem Stern am Variablentyp oder mit den eckigen Klammern am Variablenname setzen kann. Der Unterschied bei Strings ist nun, dass die Angabe mit den eckigen Klammern und einer Größenangabe, ein Array im Stack anlegt. Zusätzlich existiert eine Konstante im Const-Speicher, welche dann in das Array kopiert wird. Somit kann man den Inhalt verändern, wie in Zeile 14 gezeigt. Die Angabe mit dem Punk ist lediglich ein Zeiger. Hier kann kein Array im Stack angelegt werden, da ja die Größe nicht explizit angegeben wird. Somit wird ein Verweis auf den Inhalt im Const-Speicher gesetzt. Dieser Verweis kann zwar zur Laufzeit umgebogen werden, wie in Zeile 13 gezeigt, aber man kann den Inhalt nicht ändern, solange der Zeiger auf den Const-Speicher zeigt.

Auch wenn das Verwirrend klingt, aber Sie müssen immer unterscheiden zwischen einem konstanten String und einer Stringkonstante. Ein konstanter String ist ein nicht veränderbarer Pointer auf einen String und dieser kann nicht umgebogen werden. Falls der Zeiger aber auf einen Bereich im Stack oder Heap zeigt, kann man den Inhalt durchaus ändern. Eine Stringkonstante hingegen ist ein Bereich im Const-Speicher. Die Referenz kann umgebogen werden, aber der Inhalt kann nicht manipuliert werden.

Um noch einen drauf zu setzen, gibt es auch konstante Stringkonstanten. Das sieht man in Zeile 1. Hier habe ich einen String definiert, welcher auf eine Stringkonstante zeigt. Dieser Zeiger kann auch später nicht mehr umgebogen werden und der String selbst ist nicht änderbar.

Nach den änderungen ab Zeile 13, sieht der Speicher wie folgt aus.

Speicherverwaltung verschiedener Stringtypen nach Änderungen

Sie sehen hier sehr schön, dass "pcstrConstString" zwar scheinbar geändert wurde, er aber im Grunde nur auf einen anderen Bereich im Const-Speicher verweist. Bei dem statischen und dem dynamischen String hingegen, wurde tatsächlich der Inhalt geändert.

Ich kann gut verstehen, wenn Sie jetzt einen Knoten im Kopf haben sollten. Wenn dem so ist, lesen Sie dieses Kapitel einfach noch einmal in Ruhe durch. Ich muss selber auch zugeben, dass ich jedes Mal aufs Neue nachdenken muss. Jetzt verstehen Sie vielleicht warum man sagt, dass Strings in C das komplizierteste Thema ist.

Zum Seitenanfang
Zum Inhaltsverzeichnis

10.1.3 Einlesen von Strings

10.1.3 Einlesen von Strings

Bisher habe ich Werte immer mit der Funktion "scanf" bzw. "scanf_s" eingelesen. Dies funktioniert auch mit Strings, allerdings ergeben sich daraus ein paar Fallstricke, was folgendes Beispiel demonstrieren soll.

statische Variante dynamische Variante
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
					
#define DEF_MAX_LENGTH 80

char astrKurzerSatz[DEF_MAX_LENGTH];

printf("Bitte schreiben Sie einen kurzen Satz:\n");
fflush(stdin);
scanf_s("%s", astrKurzerSatz, DEF_MAX_LENGTH);
printf("Sie schrieben:\n%s\n\n", astrKurzerSatz);

printf("Bitte schreiben Sie noch einen kurzen Satz:\n");
fflush(stdin);
gets_s(astrKurzerSatz, DEF_MAX_LENGTH);
printf("Sie schrieben: \n%s", astrKurzerSatz);
					
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
					
#define DEF_MAX_LENGTH 80

char* pstrKurzerSatz = new char[DEF_MAX_LENGTH];

printf("Bitte schreiben Sie einen kurzen Satz:\n");
fflush(stdin);
scanf_s("%s", pstrKurzerSatz, DEF_MAX_LENGTH);
printf("Sie schrieben:\n\"%s\"\n\n", pstrKurzerSatz);

printf("Bitte schreiben Sie noch einen kurzen Satz:\n");
fflush(stdin);
gets_s(pstrKurzerSatz, DEF_MAX_LENGTH);
printf("Sie schrieben: \n\"%s\"", pstrKurzerSatz);

delete [] pstrKurzerSatz;
					

Ausgabe:

Bitte schreiben Sie einen kurzen Satz:
Hallo Welt
Sie schrieben:
"Hallo"

Bitte schreiben Sie noch einen kurzen Satz:
Hallo Welt
Sie schrieben:
"Hallo Welt"
		

Wie Sie sehr schön im ersten Teil sehen können, ließt die Funktion "scanf_s" nur ein Wort ein und keinen ganzen Satz. Genauso kritisch ist es, wenn man so versucht ein einzelnes Leerzeichen einzulesen. Dies leistet diese Funktion nicht, im Gegenteil, es ist von den Entwicklern sogar so gewollt. Um also ein einzelnes Leerzeichen oder einen Satz einlesen zu können, muss man die Funktion "gets" bzw. "gets_s" benutzen.

Besonders auffällig ist, dass beim Einlesen von Strings, die Variable normal übergeben wird und nicht ihre Adresse, also mit einem "&" Operator. Dies liegt daran, dass ein Array ja quasi schon ein Zeiger ist. Streng genommen sind zwar nur dynamische Arrays Zeiger, aber in diesem Fall läuft es auf das Gleiche hinaus.

Ein weiterer bedeutender Fakt ist, dass bei den "_s" Funktionen immer eine Puffergröße mit angegeben werden muss, da es sonst zu Abstürzen kommt (gerade bei "scanf_s"). Dabei bezieht sich der Puffer auf die Variable, welche den Wert bekommen soll, oder im Falle von "strcat_s" oder "strcpy_s", auf die erste Variable, also das Ziel (Target). Wählt man einen kleineren Puffer, so wird die entsprechende Operation abgeschnitten oder es kommt auch zu Abstürzen. Hier ist also höchste Aufmerksamkeit geboten.

Zum Seitenanfang
Zum Inhaltsverzeichnis

10.2 Listen

10.2 Listen

Bisher wurden Listen immer nur in Arrays abgebildet. Dies ist allerdings sehr unvorteilhaft, da die Erweiterung oder Verkürzung umständlich ist. Deswegen hat man sich überlegt, ein neues Konstrukt zu erfinden, um eine bessere Implementierung zu erreichen.

Zum Seitenanfang
Zum Inhaltsverzeichnis

10.2.1 Einfach verkettete Listen

10.2.1 Einfach verkettete Listen

Die grundlegende Idee der Listen ist, ein Zeiger auf eine Struktur verweisen zu lassen, welches u.a. einen Zeiger desselben Typs beinhaltet. So erhält man die Grundlage einer Liste. Ich verdeutliche dies mal einem Beispiel.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
					
// Listenelement
struct SItemStudent {
	char		astrFirstName[80];
	char		astrLastName[80];
	int		iAge;
	SItemStudent*	pNextItem;
};

// Zeiger auf ein/das erste Element der Liste
typedef SItemStudent* PListOfStudents;
					

"pNextItem" ist der besagte Zeiger in der Struktur, welcher auf eine andere gleichartige Liste verweist. Die Definition einer Liste ist also: "Eine Liste besteht aus einem Element, welches auf eine weitere Liste verweist". Das erste Element einer Liste nennt man "Wurzel" bzw. "Wurzelelement", denn von der Wurzel geht alles aus. Die Definition einer Liste ist also rekursiv.

Grundschema einer einfachen Liste

Im Bezug auf mein Beispiel, zeigt der erste Student der Liste, auf den Rest der Liste/Studenten, also auf die "Restliste". Bildlich gesehen würde dieser Student auf die Position/Adresse einer der anderen Studenten seines Jahrgangs, mit dem Finger zeigen. Jener andere Studenten würde nun auch auf die Position eines anderen (dem nächsten) Studenten seines Jahrgangs zeigen. Nun stellt sich die Frage, wohin der letzte noch übrig bleibende Student zeigen soll. Die Antwort ist schlicht und einfach, "auf nichts", also auf "NULL".

Im folgenden Beispiel werde ich zeigen, wie man eine solche Studentenliste mit 3 Studenten anlegt.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
					
// Befüllen eines Eintrages ///////////////////////////////////////////////////
void FillItem(PListOfStudents pItem) {
	// Wenn ein Listenelement initialisiert wird,
	// sollte der Zeiger in ihm auf NULL gesetzt werden
	pItem->pNextItem	= NULL;

	// Wurzel verweist auf den Namen des Schülerelementes der Liste
	printf("Vorname:  ");
	fflush(stdin);
	scanf_s("%s", pItem->astrFirstName, 80);

	printf("Nachname: ");
	fflush(stdin);
	scanf_s("%s", pItem->astrLastName, 80);

	printf("Alter:    ");
	scanf_s("%i", &pItem->iAge);
	
	printf("\n");
} // FillItem /////////////////////////////////////////////////////////////////



// Ausgabe eines Eintrages ////////////////////////////////////////////////////
void OutputItem(PListOfStudents pItem) {
	printf("\n%s ", pItem->astrFirstName);
	printf("%s ", pItem->astrLastName);
	printf("- %i\n", pItem->iAge);
} // OutputItem ///////////////////////////////////////////////////////////////



// Hauptfunktion der Anwendung ////////////////////////////////////////////////
int main(int argc, char** argv) {
	PListOfStudents	pRootItem	= NULL;
	PListOfStudents	pHelpItem	= NULL;

	// Speicher wird für erstes Element reserviert
	pRootItem			= new SItemStudent;
	FillItem(pRootItem);

	// Speicher wird für nüchstes Element reserviert
	pHelpItem			= new SItemStudent;
	FillItem(pHelpItem);

	// Der Zeiger im ersten Element zeigt auf die nächste Liste, die Hilfsliste
	pRootItem->pNextItem		= pHelpItem;

	// Speicher wird für nächstes Element reserviert
	pHelpItem			= new SItemStudent;
	// Die Variable Hilfselement zeit nun nicht mehr auf das alte Element, 
	// also das zweite in der Liste, sondern auf eine neue Liste,
	// welche dann wieder an das zweite Element der ersten Liste angehängt wird.

	FillItem(pHelpItem);

	pRootItem->pNextItem->pNextItem	= pHelpItem;

	// ...
					

Gerade die Zeile 57 zeigt, dass es sinnvoll wäre, gerade bei langen Listen, zusätzlich einen Laufzeiger zu definieren. Jener würde immer am letzten Element der Hauptliste warten, bis alle Einträge in der Hilfsliste eingetragen sind. Somit ist das Anhängen einfacher.

Wie vorhin schon erwähnt, muss am Ende der gesamte Speicher für die Elemente, welcher reserviert wurden, wieder freigegeben werden. Dies sähe in meinem Beispiel mit drei Studenten, wie folgt aus.

59
60
61
62
63
64
65
66
67
68
69
70
71
					
	//...

	pHelpItem 			= pRootItem->pNextItem->pNextItem;
	OutputItem(pHelpItem);
	delete pHelpItem;

	pHelpItem 			= pRootItem->pNextItem;
	OutputItem(pHelpItem);
	delete pHelpItem;

	OutputItem(pRootItem);
	delete pRootItem;
} // main /////////////////////////////////////////////////////////////////////
					

Wichtig! Listen sollten wie im Beispiel, immer von hinten nach vorne gelöscht werden. Würde man das erste Element zuerst löschen, also den Speicher wieder Freigeben, würde so auch der Zeiger des ersten Elementes nicht mehr existiert und so hat man keine Chance mehr, die Position, also die Adresse, der anderen Elemente herauszubekommen. Somit kann man sie nicht mehr löschen und der Speicherplatz im RAM wäre, wie bereits erwähnt, bis zum Programmende sinnlos vergeben und könnte nicht mehr genutzt werden. Auch hier macht es bei längeren Listen Sinn, eine Laufvariable zu benutzen. Jene könnte immer zum letzten Element durchlaufen und es dann löschen. Dies könnte folgendermaßen aussehen.

59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
					
	PListOfStudents	pWalkPointer;

	// Solange, bis nichts mehr am Wurzelelement dran hängt
	while (pRootItem->pNextItem != NULL) {
		pWalkPointer		= pRootItem;
		pHelpItem		= pRootItem;

		// Solange, bis das Ende der Liste erreicht wurde
		while (pWalkPointer->pNextItem != NULL) {
			pHelpItem	= pWalkPointer;
			pWalkPointer	= pWalkPointer->pNextItem;
		} // end of while

		OutputItem(pWalkPointer);

		delete pWalkPointer;
		pHelpItem->pNextItem	= NULL;
		pWalkPointer		= NULL;
	} // end of while

	OutputItem(pRootItem);
	delete pRootItem;
} // main /////////////////////////////////////////////////////////////////////
					

Das sieht zwar jetzt viel komplizierter aus, stellt aber sicher, dass alle Elemente der Liste entfernt werden und das für beliebig lange Listen.

Problematischer ist es schon, wenn man ein Element löschen will, welches sich mitten in einer Liste befindet. Dies kann leicht dazu führen, dass man nicht nur das einzelne Element löscht, sondern auch den Rest der Liste unzugänglich macht. Ein Laufzeiger müsste wiederum bis zu dem Element davor Laufen. Die Abfrage hierfür hängt davon ab, nach welchem Kriterium man ein bestimmtes Element, welches es zu löschen gilt, sucht. Der Zeiger "pHelpItem" soll dann auf "pWalkPointer->pNextItem" zeigen. Jetzt sagt man, dass der Zeiger des Laufelementes, auf das Übernächste zeigen soll.

 1
 2
 3
					
pWalkPointer->pNextItem	= pWalkPointer->pNextItem->pNextItem 
// oder
pWalkPointer->pNextItem	= pHelpItem->pNextItem
					

"pHelpItem" kann nun mit "delete" gelöscht werden.

Ich empfehle Ihnen drinend, sich für Listen eine Skizze anzufertigen, da man schnell durcheinander kommt, wie man nun was abruft und der Gleichen.

Löschen aus einer Liste I

Löschen aus einer Liste II

Zum Seitenanfang
Zum Inhaltsverzeichnis

10.2.2 Doppelt verkettete Listen

10.2.2 Doppelt verkettete Listen

Bei einfach verketteten Listen, befindet sich in der Struktur ein Zeiger, welcher auf die Restliste verweist. Bei doppelt verketteten Listen, ist dies derselbe Fall, nur dass es nun noch einen zusätzlichen Zeiger gibt, welcher auf das vorhergehende Element verweist. Man muss hier nur beachten, dass der "Previous-Zeiger" im Wurzelelement, auf "NULL" zeigt.

Grundschema einer doppelt verketteten Liste

Natürlich muss man beim bearbeiten dieser Listen (einfügen, vertauschen und löschen), doppelt so sehr aufpassen, dass man alle Zeiger richtig umbiegt.

Zum Seitenanfang
Zum Inhaltsverzeichnis

10.2.3 Ringlisten

10.2.3 Ringlisten

Ringlisten sind im Grunde genommen das Gleiche wie einfach verkettete Listen, nur dass das der Zeiger des letzten Elementes nicht auf "NULL", sondern auf das "Wurzelelement" verweist. Somit gibt es kein richtiges Wurzelelement mehr, da ein Ring, also ein Kreis, keinen Anfang und kein Ende besitzt. Jedoch sollte man immer darauf achten, dass ein Zeiger immer auf ein Element der Liste verweist, da man sonst keinen Zugriff mehr erhält. Auf welches Element ein Zeiger verweist, ist hierbei relativ egal.

Grundschema einer einfachen Ringliste

Zum Seitenanfang
Zum Inhaltsverzeichnis

10.4 Übungsaufgaben VIII

10.4 Übungsaufgaben VIII

  1. Schreiben Sie ein kleines Programm, welches aus einem konstanten String die Anzahl des Vorkommens eines gewünschten Buchstabes z%auml;hlt. Schreiben Sie zu diesen Zweck eine extra Funktion mit folgender Signatur:
    int CountSign(const char* const pcstrSource, const char& cSign);
    Testen Sie Ihr Programm mit sinnvollen Werten und fangen Sie auch den Fall ab, dass "NULL" übergeben wird (Rückgabewert -1).
  2. Schreiben Sie ein kleines Programm, welches aus einem konstanten String die Startposition eines anderen konstanten Strings sucht und zurückgibt. Benutzen Sie folgende Signatur:
    int strpos(const char* const pcstrSource, const char* const pcstrSearch); Falls irgendetwas nicht ok ist, soll -1 zurückgegeben werden.
    TIPP: Die Funktion "strstr" ist ganz hilfreich.
  3. In den folgenden Aufgaben wird es darum gehen, eine Warteschlange zu implementieren. Erstellen Sie dafür ein Programm und legen Sie schon per Konstante fest, wie viele Einträge maximal möglich sind (vier Einträge reichen für den Anfang). Zudem soll diese Warteschlange als ringförmige Liste abgebildet werden, wobei die Elemente dynamische Strings enthalten sollen. Erzeugen Sie alle notwendigen Datentypen.
    TIPP: Speichern Sie sich irgendwo, wie viele Strings momentan enthalten sind. Das wird Ihnen später ein paar Abfragen erleichtern.
  4. Schreiben Sie eine Funktion "Initialize", welche die Ringliste anlegt und die Zeiger auf die Strings der Elemente, auf "NULL" zeigen lässt. Geben Sie die erzeugte Ringliste zurück. Beachten Sie, dass es auch möglich sein soll, dass die Warteschlange nur ein oder gar kein Element aufnehmen soll/kann.
    TIPP: Malen Sie sich das Verhalten auf, um mehr Durchblick zu erhalten.
  5. Schreiben Sie nun eine Funktion "Append", welche einen übergebenen String kopiert und diese Kopie hinten anhängt. Falls die Warteschlange voll ist, soll "false" zurückgegeben werden. Achten Sie darauf, dass die Stringkopie nicht unnötig groß ist. Beachten Sie, dass das Ende der Schlange jetzt wo anders ist, da sich die Anzahl der Einträge erhöht.
  6. Schreiben Sie als nächstes eine Funktion "Remove", welche den vordersten String aus der Warteschlange löscht. Die Funktion soll "false" zurückgeben, wenn es nichts zum Entfernen gibt. Beachten Sie, dass der Anfang der Schlange jetzt wo anders ist, da sich die Anzahl der Einträge verringert.
  7. Schreiben Sie eine Funktion "PrintFirst", welche das erste Element auf der Konsole ausgibt.
  8. Schreiben Sie anschließend eine Funktion "Finalize", welche alle noch in der Schlange befindlichen Strings löscht und die Warteschlange, samt aller Elemente, frei gibt.
  9. Schreiben Sie abschließend eine Funktion "main", um Ihre eben erstellten Funktionen zu testen. Besonders wichtig ist dabei, dass nichts mehr hinzugefügt werden kann, wenn die Liste voll ist und dass das Hinzufügen wieder funktioniert, sobald wieder ein Platz frei ist.
Zum Seitenanfang
Zum Inhaltsverzeichnis

© Copyright by Thomas Weiß, 2009 - 2012