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.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

© Copyright by Thomas Weiß, 2009 - 2012