Hi. Ich bin gerade dabei eine linked list zu erstellen als Übung mit
Pointern. Leider komm ich nicht mehr weiter, da das verketten nicht ganz
klappt. Vielleicht könnt ihr mal einen Blick darauf werfen:
1
#include<stdio.h>
2
#include<stdlib.h>
3
4
typedefstructitem{
5
structitem*next;
6
intid;
7
8
}item;
9
10
typedefstructList{
11
item*first;
12
}List;
13
14
/* Add item to list */
15
voidaddElement(List*list,intid){
16
/* get first item */
17
item*p=list->first;
18
19
/* go to the end of the list */
20
while(p!=NULL){
21
p=malloc(sizeof(item));
22
p=p->next;
23
}
24
25
/* create new item */
26
p=malloc(sizeof(item));
27
p->next=NULL;
28
p->id=id;
29
30
/* if this is the first item we'll recognize that */
31
if(list->first==NULL){
32
p->next=malloc(sizeof(item));
33
list->first=p;
34
35
}
36
37
printf("added item with id %d at %p - my next is %p\n",p->id,&p,&p->next);
38
printf("now are %d elements in the list\n",countItemsfromList(list));
39
}
40
41
/* Print all items */
42
voidprintList(List*list){
43
/* get first item */
44
item*p=list->first;
45
46
/* go to the end of the list */
47
while(p!=NULL){
48
/* print the id of the curren item */
49
printf("%i\n",p->id);
50
p=p->next;
51
}
52
}
53
54
/* get an specific item from list per key */
55
intgetItemfromList(List*list,intcid){
56
/* get first item */
57
item*p=list->first;
58
59
/* go to the end of the list */
60
while(p!=NULL){
61
/* if the key applies to these we'll return the key */
62
if(p->id==cid){
63
returnp->id;
64
}
65
p=p->next;
66
}
67
return0;
68
}
69
70
/* returns the number of items in the list */
71
intcountItemsfromList(List*list){
72
/* get first item */
73
item*p=list->first;
74
intcount=1;
75
76
/* go to the end of the list */
77
while(p!=NULL){
78
p=p->next;
79
count++;
80
}
81
returncount;
82
}
83
84
intmain(intargc,constchar*argv[]){
85
intrResult=0;
86
//struct List liste = { NULL };
87
structList*liste=(List*)malloc(sizeof(List));
88
89
addElement(liste,1);
90
addElement(liste,2);
91
addElement(liste,3);
92
93
94
rResult=getItemfromList(liste,3);
95
printf("ID ist : %d",rResult);
96
printList(liste);
97
98
}
Von Bedeutung ist nur erstmal addElement().
Ich hoffe jemand kann mir helfen.
Fang mal bei addElement /* go to the end of the list */ an, die real
existierenden Funktion des gezeigten Codes zu verstehen. Beispielsweise
bei der Frage, was das malloc da soll.
An nächstes zeig mal die Zeile, in der du das neu erzeugte Element an
das Ende einer nicht leere Liste hängst.
Das malloc macht da sehr wenig Sinn, wenn dort wirklich zum Ende
navigiert wird... das stimmt.
mit
p = malloc(sizeof(item));
wir ein neues item erzeugt.
Wenn die Liste leer ist, wird schonmal ein weiteres Element angelegt und
first zeigt auf das erste item.
Hi,
Ich suche noch nach der Stelle, wo Du das liste->first initialisierst.
Gerade wenn du die Liste selbst auch dynamisch erzeugst.
malloc macht das nicht automatisch.
int main (int argc, const char * argv[]) {
int rResult = 0;
//struct List liste = { NULL };
struct List *liste = (List*)malloc(sizeof(List));
liste->first =NULL;
addElement(liste, 1);
Christian Q. schrieb:> Leider komm ich nicht mehr weiter, da das verketten nicht ganz> klappt.
Dann spiel Computer, schnapp dir einen Zettel (das ist dein Speicher)
und einen Bleistift und Radiergummi (mit dem du deinen Speicher
manipulierst) und arbeite deine Funktion genau so ab, wie es auch ein
Computer macht.
Am Anfang hast du eine Liste erzeugt
> struct List *liste = (List*)malloc(sizeof(List));
also mach das mal auf dem Zettel:
Da gibt es also eine Variable liste. Hier ist sie
1
liste
2
+--------+
3
| |
4
+--------+
dieser Variablen weist du einen Pointer zu, den du von malloc bekommst.
malloc hat Speicher allokiert, der für ein struct List ausreicht. Also
so
1
liste
2
+--------+
3
| |
4
+--------+
5
6
7
+--------------+
8
| struct List |
9
+--------------+
10
| first: |
11
+--------------+
und diesen Pointer weißt du an liste zu:
1
liste
2
+--------+
3
| o |
4
+---|----+
5
|
6
+--+
7
|
8
v
9
+--------------+
10
| struct List |
11
+--------------+
12
| first: |
13
+--------------+
Das ist alles, was du am Anfang machst. Sieh dir das Bild an, sieht es
richtig aus? Nein, sieht nicht richtig aus. Der first Pointer in der
struct List sollte NULL sein, was er nicht ist. Also korrigieren wir das
mal.
> struct List *liste = (List*)malloc(sizeof(List));> liste->first = NULL;
der erste Teil läuft wieder wie vorher, nur wird jetzt der first Pointer
noch auf NULL gesetzt. Auf deinem Papier symbolisierst du das dadurch,
dass du da einfach einen Strich reinmachst.
1
liste
2
+--------+
3
| o |
4
+---|----+
5
|
6
+--+
7
|
8
v
9
+--------------+
10
| struct List |
11
+--------------+
12
| first: / |
13
+--------------+
Also: Aus einer Pointervariablen kommt entweder ein Pfeil raus (der auch
irgendwo hinzeigen muss) oder aber dort ist ein Strich. In allen anderen
Fällen hast du einen ungültigen Pointer entdeckt, mit dem du nicht
sinnvoll arbeiten kannst.
Weiter gehts.
> addElement(liste, 1);
dann machen wird as mal. Wie gehts in der Funktion weiter
> void addElement(List* list, int id) {
Dort wird also eine Kopie der Variablen liste angelegt und list genannt.
Machen wir gleich mal auf dem Papier. Neue Variable anlegen (Rechteck
hinmalen) und auf dieselbe Stelle zeigen lassen, auf die auch liste
zeigt
1
liste list
2
+--------+ +------+
3
| o | | o |
4
+---|----+ +---|--+
5
| |
6
+--+ +------+
7
| |
8
v v
9
+--------------+
10
| struct List |
11
+--------------+
12
| first: / |
13
+--------------+
weiter
> /* get first item */> item* p = list->first;
ok. Noch eine Variable, die diesmal den Inhalt von dem Feld 'first'
erbt, auf welches list zeigt.
erster SChritt: variable anlegen
1
liste list
2
+--------+ +------+
3
| o | | o |
4
+---|----+ +---|--+
5
| |
6
+--+ +------+
7
| |
8
v v
9
+--------------+
10
| struct List |
11
+--------------+
12
| first: / |
13
+--------------+
14
15
16
17
p
18
+-------+
19
| |
20
+-------+
zweiter schritt: rausfinden, was da rein muss.
Nun, schau auf dein Papier. Worauf zeigt list? In der dortigen Struktur
muss es ein first Feld geben. Und dessen Inhalt kopierst du nach p.
In diesem Fall ist in first ein / enthalten, also kommt der nach p
1
liste list
2
+--------+ +------+
3
| o | | o |
4
+---|----+ +---|--+
5
| |
6
+--+ +------+
7
| |
8
v v
9
+--------------+
10
| struct List |
11
+--------------+
12
| first: / |
13
+--------------+
14
15
16
17
p
18
+-------+
19
| / |
20
+-------+
Beachte: Wenn list nicht auf irgendetwas gezeigt hätte (weil es entweder
leer oder ein / gewesen wäre), dann wäre das ein schwerer Fehler
gewesen. Bei
list->first
MUSS list auf etwas Sinnvolles zeigen. Nur dann gibt es das
entsprechende first Feld.
> /* go to the end of the list */> while (p != NULL) {
Schau auf deine Zeichnung. Ist p NULL?
Ja ist es, also wird die Schleife erst gar nicht betreten
> /* create new item */> p = malloc(sizeof(item));
Aha: p kriegt einen neuen Wert. malloc erzeugt wieder eine Struktur
1
liste list
2
+--------+ +------+
3
| o | | o |
4
+---|----+ +---|--+
5
| |
6
+--+ +------+
7
| |
8
v v
9
+--------------+
10
| struct List |
11
+--------------+
12
| first: / |
13
+--------------+
14
15
16
17
p +-------------+
18
+-------+ | struct item |
19
| / | +-------------+
20
+-------+ | next: |
21
| id: |
22
+-------------+
und seine Adresse wird bei p eingetragen
1
liste list
2
+--------+ +------+
3
| o | | o |
4
+---|----+ +---|--+
5
| |
6
+--+ +------+
7
| |
8
v v
9
+--------------+
10
| struct List |
11
+--------------+
12
| first: / |
13
+--------------+
14
15
16
17
p +-------------+
18
+-------+ +------->| struct item |
19
| o------------+ +-------------+
20
+-------+ | next: |
21
| id: |
22
+-------------+
> p->next = NULL;
p in der Zeichnung aufsuchen, dem Pfeil folgen und in der STruktur in
der du landest beim next Feld einen NULL Pointe eintragen
1
liste list
2
+--------+ +------+
3
| o | | o |
4
+---|----+ +---|--+
5
| |
6
+--+ +------+
7
| |
8
v v
9
+--------------+
10
| struct List |
11
+--------------+
12
| first: / |
13
+--------------+
14
15
16
17
p +-------------+
18
+-------+ +------->| struct item |
19
| o------------+ +-------------+
20
+-------+ | next: / |
21
| id: |
22
+-------------+
> p->id = id;
wieder: p aufsuchen, dem Pfeil folgen und im id Feld die 1 (vom
Funktionsaufruf eintragen)
1
liste list
2
+--------+ +------+
3
| o | | o |
4
+---|----+ +---|--+
5
| |
6
+--+ +------+
7
| |
8
v v
9
+--------------+
10
| struct List |
11
+--------------+
12
| first: / |
13
+--------------+
14
15
16
17
p +-------------+
18
+-------+ +------->| struct item |
19
| o------------+ +-------------+
20
+-------+ | next: / |
21
| id: 1 |
22
+-------------+
> /* if this is the first item we'll recognize that */> if(list->first == NULL) {
Schau auf die Zeichnung und such dir die Variable list. Dem Pfeil folgen
und das first Feld ansehen. Ist es NULL?
ja, ist es.
Also wird dieser Code ausgeführt
> p->next = malloc(sizeof(item));
ein neues Feld wird allokiert
1
liste list
2
+--------+ +------+
3
| o | | o |
4
+---|----+ +---|--+
5
| |
6
+--+ +------+
7
| |
8
v v
9
+--------------+
10
| struct List |
11
+--------------+
12
| first: / |
13
+--------------+
14
15
16
17
p +-------------+
18
+-------+ +------->| struct item |
19
| o------------+ +-------------+
20
+-------+ | next: |
21
| id: 1 |
22
+-------------+
23
24
25
+-------------+
26
| struct item |
27
+-------------+
28
| next: |
29
| id: |
30
+-------------+
und p->next soll darauf zeigen.
Also: p in der Zeichnung suchen, dem Pfeil folgen und dort im next Feld
einen Zeiger auf diese neue Struktur eintragen
1
liste list
2
+--------+ +------+
3
| o | | o |
4
+---|----+ +---|--+
5
| |
6
+--+ +------+
7
| |
8
v v
9
+--------------+
10
| struct List |
11
+--------------+
12
| first: / |
13
+--------------+
14
15
16
17
p +-------------+
18
+-------+ +------->| struct item |
19
| o------------+ +-------------+
20
+-------+ | next: o-------+
21
| id: 1 | |
22
+-------------+ |
23
+------------------------------+
24
v
25
+-------------+
26
| struct item |
27
+-------------+
28
| next: |
29
| id: |
30
+-------------+
> list->first = p;
und zu guter letzt soll auch noch list->first auf das zeigen, wo auch p
hinzeigt.
Ok. Erst mal p aufsuchen und feststellen, wo der Zeiger hinführt.
Dann list aufsuchen, wieder dem Pfeil einmal folgen, und dann vom first
Feld ausgehend einen Pfeil einrichten, der dort endet, wo auch p
hinzeigt.
1
liste list
2
+--------+ +------+
3
| o | | o |
4
+---|----+ +---|--+
5
| |
6
+--+ +------+
7
| |
8
v v
9
+--------------+
10
| struct List |
11
+--------------+
12
| first: o----------+
13
+--------------+ |
14
|
15
|
16
v
17
p +-------------+
18
+-------+ +------->| struct item |
19
| o------------+ +-------------+
20
+-------+ | next: o-------+
21
| id: 1 | |
22
+-------------+ |
23
+------------------------------+
24
v
25
+-------------+
26
| struct item |
27
+-------------+
28
| next: |
29
| id: |
30
+-------------+
Damit ist deine Funktion (im wesentlichen) zu Ende und alle lokalen
Variablen (list und p) werden zerstört. Also radierst du die aus deiner
Zeichnung raus:
1
liste
2
+--------+
3
| o |
4
+---|----+
5
|
6
+--+
7
|
8
v
9
+--------------+
10
| struct List |
11
+--------------+
12
| first: o----------+
13
+--------------+ |
14
|
15
|
16
v
17
+-------------+
18
| struct item |
19
+-------------+
20
| next: o-------+
21
| id: 1 | |
22
+-------------+ |
23
+------------------------------+
24
v
25
+-------------+
26
| struct item |
27
+-------------+
28
| next: |
29
| id: |
30
+-------------+
So. Jetzt verlässt du deinen Computermode und schaltest wieder zurück
auf Entwickler. Betrachte dein Werk. Sieht es richtig aus?
Nein. Tut es nicht. Du wolltest in eine leere Liste 1 neues ELement
einfügen, bist aber mit 2 items rausgekommen, wobei im letzten item
weder der next Pointer noch das id Feld einen sinnvollen Wert haben.
Das kann nicht stimmen.
Geh noch mal jeden Schritt durch und sieh dir an, wie es dazu gekommen
ist, dass das als falsch identifizierte entstanden ist. Und dann
korrigiere den Code entsprechend diesen Erkentnissen. In diesem Fall ist
der Hauptfehler, dass da 2 item-Strukturen erzeugt wurden. Das das 2.te
keine sinnvollen Werte enthält ist zwar Tatsache aber trotzdem
irrelevant, denn wenn es nicht mehr erzeugt wird spielt das keine Rolle
mehr.
Wenn dann der erste addElement ein richtiges Ergebnis abliefert, dann
rufst du addElement erneut auf und simulierst auf dem Papier weiter, was
da so vor sich geht, wenn das nächste Element eingefügt wird.
Genau so debuggt man Code, der Datenstrukturen dynamisch aufbaut,
solange man das alles noch nicht im Kopf simulieren kann. Schaut auf den
ersten Blick aufwändig aus, ist aber um einiges schneller als rumraten
und den Code per Zufall zu verändern. Und hat den Vorteil, dass man
hinterher auch versteht, was man da eigentlich programmiert hat, warum
etwas funktioniert und warum etwas nicht funktioniert.
Wichtig ist, dass du das und nur das machst, was auch im Code steht!
Weder werden Variablen von alleine auf irgendwelche Werte gesetzt noch
passieren sonst irgendwelche Automatismen. Dein Computer macht sie
nicht, wenn er dein Programm ausführt, also darfst du sie auf dem Papier
auch nicht machen. Du tust genau das, was auch dein Computer macht: stur
das Programm abarbeiten und alle Aktionen so ausführen wie sie dort
stehen.
Christian Q. schrieb:> /* Add item to list */> void addElement(List* list, int id) {> /* get first item */> item* p = list->first;>
soweit ok!
das ist nicht ok
> /* go to the end of the list */> while (p != NULL) {> p = malloc(sizeof(item));> p = p->next;> }
erst ende finden kein malloc
/* go to the end of the list */
while (p != NULL) {
p = p->next;
}
dann Neuen eintrag erstellen; das passt dann wieder
> /* create new item */> p = malloc(sizeof(item));> p->next = NULL;> p->id = id;>
den nächsten Block kannst du löschen, weil p bei einer leeren liste noch
auf list->first zeigt, und somit bereits das erste element auf
list->first erstellt wurde.
> /* if this is the first item we'll recognize that */> if(list->first == NULL) {> p->next = malloc(sizeof(item));> list->first = p;>> }>
p und p->next sind bereits zeiger! ich glaube nicht, dass du die Adresse
der Zeiger ausgeben willst, sondern vielmehr deren destination?
> printf("added item with id %d at %p - my next is %p\n", p->id, &p, &p->next);> printf("now are %d elements in the list\n", countItemsfromList(list));> }
Vielen Dank für eure Mühe!!
Aber so richtig komm ich nicht voran. Wenn ich einen Weg einschlage
fehlt mir immer mindestens 1 Element zum "verknüpfen". Entweder ich
möchte das Element mit dem nächsten schon verbinden (deswegen die 2
struct item) oder ich will auf das vorherige Element zugreifen.
1
/* create new item */
2
p=malloc(sizeof(item));
3
p->next=NULL;
4
p->id=id;
irgendwie muss ich bei dem p->next ja etwas setzen so in der Art
p->next = zeige auf das Element vor mir; oder
p->next = zeige auf das Element nach mir;
das Element vor mir habe ich nicht mehr zur Verfügung .. und das Element
nach mir kann ich nicht voraussagen an welcher Stelle es im Speicher
stehen wird.
Hilfe.. ich will das echt verstehen.
Deine Methode zur Suche nach dem Ende der Liste findet nicht das letzte
Element, sondern den dort enthaltenen Zeiger - und der ist Null.
Du solltest als besser nach dem letzten Element selbst suchen. Das ist
das Element mit Null im next. Also sowas wie
while (p->next != NULL)
Danach zeigt p auf das letzte Element und du kannst die Liste
verlängern.
A. K. schrieb:> das Element mit Null im next. Also sowas wie> while (p->next != NULL)
So hab ich mir das am Anfang auch gedacht, aber da bekam (und bekomme
jetzt auch wieder) einen Segmentation fault.
Ich denke ich muss p->next anders ansprechen.. bzw. den Pointer anders
ansprechen.
N.H. schrieb:> p und p->next sind bereits zeiger! ich glaube nicht, dass du die Adresse> der Zeiger ausgeben willst, sondern vielmehr deren destination?
Ich wollte die Speicheradressen anzeigen zu denen die Pointer zeigen.
Aber nicht die Adresse der Pointer selbst (was hier wohl der Fall ist.)
Christian Q. schrieb:> Hilfe.. ich will das echt verstehen.
Du machst einen grundlegenden Fehler:
Du fängst viel zu früh an Code zu schreiben. Du beginnst damit noch ehe
dir klar ist, wie eine Funktionalität überhaupt ablaufen muss.
Ein Weg dazu, der zb bei mir gut funktioniert, ist es, die geplante
Operation erst einmal auf Schmierpapier durchzuspielen. Du glaubst gar
nicht, was du alles intuitiv kannst, ohne dir darüber bewusst zu sein,
wie du das macht. Und genau das musst du ändern. Du musst dir erst mal
selbst über die Schulter schauen und rausfinden, wie DU die Aktion
machst.
Du willst an eine Liste was hinten drann hängen. Wie machst du das, wenn
du als Mensch das tun würdest? Das ist deine erste Frage die du
beantworten musst. Daraus entwickelst du dann einen Plan (und überprüfst
ihn mit deinem Schmierpapier) und erst DANN beginnt die Umsetzung in
Code.
Code hinzuschreiben ohne einen Plan davon zu haben, wie die Operation
(von einer hohen Warte aus gesehen) überhaupt ablaufen soll, ist ein
sicherer Weg ins Desaster und in eine Programmierung ala: Ich probier
einfach x Varianten aus und verändere nach Zufall mein Programm;
irgendwann wird schon was rauskommen, was so aussieht als ob es
funktionieren könne.
Diese Strategie haben schon Milliarden anderer Programmierer vor dir
versucht. Es hat noch nie funktioniert.
> So hab ich mir das am Anfang auch gedacht, aber da bekam> (und bekomme jetzt auch wieder) einen Segmentation fault.
Ich hab dir schon gezeigt, wie man solchen Dingen auf den Grund geht.
Dein Problem: Du hast keinen Plan, wie die Operation in groben Zügen
ablaufen soll, welche Sonderfälle es dabei gibt.
Warum hast du den nicht? Weil du selbst niemals ausprobiert hast (auf
Papier) wie die Operation 'hinten an eine Liste anhängen' völlig
losgelöst von irgendeiner Programmiersprache überhaupt ablaufen muss.
Hi nochmals,
sorry, aber vorhin war auch noch ein fehler drin, aber den Code jetzt
hab ich schnell im debugger gecheckt, und ich glaube, der ist einfacher
zu versteheh als Deiner
int main (void) {
int rResult = 0;
//struct List liste = { NULL };
struct List *liste = (List*)malloc(sizeof(List));
liste->first=NULL;
addElement(liste, 1);
addElement(liste, 2);
addElement(liste, 3);
}
/* Add item to list */
void addElement(List* list, int id) {
/* get first item */
item* newitem;
item* p = list->first;
/* create new item */
newitem = malloc(sizeof(item));
newitem->next = NULL;
newitem->id = id;
/* ist liste empty ?*/
if(list->first == NULL)
{
list->first =newitem;
}
else
{
/* search for last element*/
while(p->next !=0)
{
p=p->next;
}
p->next = newitem;
}
}
Karl Heinz Buchegger schrieb:> Wie machst du das, wenn> du als Mensch das tun würdest? Das ist deine erste Frage die du> beantworten musst.
Ich schau erstmal wo der Anfang der Liste ist und wo das Ende.
Dann entscheide ich wo ich es platzieren möche (anhängen = an das Ende
der Liste).
Ich such mir nun das letzte Element in der Liste und füge es darunter
an.
Portiert auf Computersicht:
Ich navigier zum Ende der Liste indem ich mich vom Ersten Element immer
weiter "durchhangel" bis ich feststelle, dass kein weiteres Element
folgt (p->next == NULL - es gibt keinen Nachfolger dieses Elements)
Also kann ich nun sagen ich lege einen Nachfolger an.
so in der Art: newitem = p->next = malloc(sizeof(item);
Da ist deine Liste
+-----------+
| first / |
+-----------+
du willst einen Knoten "5" anhängen.
Was tust du und warum tust du es?
Zunächst mal wirst du einen Listenknoten erzeugen. Das sollte noch klar
sein. Ohne Listenknoten hast du nichts zum anhängen.
Also hast du
+-----------+
| first / |
+-----------+
+-----------+
| / |
| 5 |
+-----------+
wie kommt der jetzt in die Liste?
Einfach. Einen Pointer von first zum Knoten und fertig
+-----------+
| first o |
+---------|-+
|
+-------+
|
v
+-----------+
| / |
| 5 |
+-----------+
Warum geht das so einfach?
Na, weil ganz offensichtlich die Liste leer war (first war gleich NULL).
In dem Fall gibt es kein letztes Element und das neu erzeugt ist somit
gleichzeitig das erste und das letzte Element nach dem Einfügen.
Was ist wenn die Liste nicht leer war, first also auf schon vorhandene
Knoten zeigt
+-----------+
| first o |
+---------|-+
|
+-------+
|
v
+-----------+ +---------+ +--------+
| o------------>| o---------->| / |
| 5 | | 8 | | 2 |
+-----------+ +---------+ +--------+
wie gehst du vor?
Du fängst beim ersten Element an und tatscht mit dem Finger drauf. Das
erste Element findest du ganz leicht, denn first zeigt ja drauf.
Dann wanderst du mit dem Finger von einem Knoten zum nächsten, bis du
beim letzten bist. Woran erkennst du den letzten? Vergleich ihn mit den
anderen! Was ist anders? Na, offenbar hat der letzte Knoten einen NULL
Zeiger, wo die anderen einen Zeiger zum nächsten haben.
Das ist also dein Erkennungskriterium.
Und dort hängst du den neuen Knoten
+-----------+
| first o |
+---------|-+
|
+-------+
|
v
+-----------+ +---------+ +--------+
| o------------>| o---------->| / |
| 5 | | 8 | | 2 |
+-----------+ +---------+ +--------+
+---------+
| 9 |
| / |
+---------+
dann an, indem du einen Zeiger einrichtest
+-----------+
| first o |
+---------|-+
|
+-------+
|
v
+-----------+ +---------+ +--------+
| o------------>| o---------->| o--------+
| 5 | | 8 | | 2 | |
+-----------+ +---------+ +--------+ |
v
+---------+
| 9 |
| / |
+---------+
fertig. Ergebnis ansehen. Ist offensichtlich richtig.
Also haben wir einen Plan
1
neuen Knoten erzeugen und befüllen
2
3
ist die Liste leer?
4
ja -> neuen Knoten einfach als ersten KNoten in die Liste
5
einfügen
6
7
nein -> Ende der Liste suchen
8
neuen Knoten dort anhängen
Der Unterpunkt "Ende der Liste suchen" war was?
Das war: solange den Knoten folgen, bis einer auftaucht, der einen NULL
Pointer in next stehen hat.
Also: neuer Plan
1
neuen Knoten erzeugen und befüllen
2
3
ist die Liste leer?
4
ja -> neuen Knoten einfach als ersten KNoten in die Liste
5
einfügen
6
7
nein -> Knotenliste abklappern bis einer
8
auftaucht, der in next NULL stehen hat.
9
neuen Knoten dort anhängen
Und mit dem Plan kannst du dann schon in die Implementierung gehen.
Edit: Oder noch ein Zwischenschritt
Der Unterpunkt
"Das war: solange den Knoten folgen, bis einer auftaucht, der einen NULL
Pointer in next stehen hat."
Wie hast du das ganz genau auf dem Papier gemacht:
du hast mit dem Finger auf den ersten getatscht. Woher wusstest du
welcher der erste ist? Welcher der erste ist, hast du aus der Listen
Struktur selber erfahren. Da gibt es einen Pfeil drauf.
und bist dann solange mit den Fingern den Pfeilen nachgefahren, bis du
mit dem Finger auf ein Rechteck getatscht hast, dessen next Feld NULL
war.
> ja -> neuen Knoten einfach als ersten KNoten in die Liste
5
> einfügen
6
>
7
> nein -> Knotenliste abklappern bis einer
8
> auftaucht, der in next NULL stehen hat.
9
> neuen Knoten dort anhängen
10
>
>> Und mit dem Plan kannst du dann schon in die Implementierung gehen.
Du fängst damit an, dass du den Plan in Form von Kommentaren übernimmst
1
voidaddElement(List*list,intid){
2
// neuen Knoten erzeugen und befüllen
3
4
// ist die Liste leer?
5
// ja -> neuen Knoten einfach als ersten KNoten in die Liste
6
einfügen
7
//
8
// nein -> Knotenliste abklappern bis einer
9
// auftaucht, der in next NULL stehen hat.
10
// neuen Knoten dort anhängen
11
}
und dann anfängst die Details einzusetzen
1
voidaddElement(List*list,intid){
2
// neuen Knoten erzeugen und befüllen
3
item*newItem=malloc(sizeof(item));
4
newItem->id=id;
5
newItem->next=NULL;
6
7
// ist die Liste leer?
8
if(list->first==NULL)
9
// ja -> neuen Knoten einfach als ersten KNoten in die Liste
10
// einfügen
11
list->first=newItem;
12
13
// nein ->
14
else{
15
// Knotenliste abklappern bis einer
16
// auftaucht, der in next NULL stehen hat.
17
item*last=list->first;
18
while(last->next!=NULL)
19
last=last->next;
20
21
// neuen Knoten dort anhängen
22
last->next=newItem;
23
}
24
}
Die Selbstbeobachtung dessen was man getan hat, das daraus folgende
Entwickeln eines Planes hat ganz von alleine zu einer IMplementierung
geführt, die man versteht, die genau so funktioniert wie sie es am
Papier getan hat (deswegen muss man auch am Papier möglichst viele/alle
Sonderfälle entdecken) und die gleichzeitig auch noch sinnvoll
kommentiert ist :-)
Christian Q. schrieb:> ch wollte die Speicheradressen anzeigen zu denen die Pointer zeigen.> Aber nicht die Adresse der Pointer selbst (was hier wohl der Fall ist.Christian Q. schrieb:>> p und p->next sind bereits zeiger! ich glaube nicht, dass du die Adresse>> der Zeiger ausgeben willst, sondern vielmehr deren destination?>> Ich wollte die Speicheradressen anzeigen zu denen die Pointer zeigen.> Aber nicht die Adresse der Pointer selbst (was hier wohl der Fall ist.)
ist leider nicht so, Du zeigst an, auf welcher Adresse die Zeiger
liegen, und nicht wohin sie zeigen; das '&' davor ist zuviel :)
aber Du solltest zuerst das 1.Problem Liste lösen, dann kommt die
Ausgabe :)
Klappt wunderbar und ich verstehe sogar was ich mache :D
Ich werd demnächst versuchen besser zu planen. Das "in den Computer
hineinversetzen" hilft auch ungemein. Mit diesen tollen Zeichnungen muss
ich mich noch ein wenig auseinandersetzen. Wenn man es sieht kann man es
gut nachvollziehen, aber wenn ich es selbst aufzeiche weiß häufig oft
nicht ob ich jetzt ein neues Element anlegen muss oder es nur ein
Pointer in einem Elemet ist.
Was ich jedoch nicht verstehen ist diese Zeile
1
structList*liste=(List*)malloc(sizeof(List));
Ich würd es so verstehen, dass malloc die Größe zurückgibt die sie im
Speicher allokiert hat und in Liste* speichert was wiederum direkt vor
liste steht und somit eine liste erzeugt und dem Compiler mitteilt wie
groß diese ist.
Gibt es einen unterschied zwischen
List *liste = (List*)malloc(sizeof(List)); und
struct List *liste = (List*)malloc(sizeof(List)); ?
Vielen Dank!
Hier der Code
1
#include<stdio.h>
2
#include<stdlib.h>
3
4
typedefstructitem{
5
structitem*next;
6
intid;
7
}item;
8
9
typedefstructList{
10
item*head;
11
}List;
12
13
/* Add item to list */
14
voidaddElement(List*list,intid){
15
16
/* create new item */
17
item*newitem=malloc(sizeof(item));
18
newitem->next=NULL;
19
newitem->id=id;
20
21
/* find the end */
22
if(list->head==NULL){
23
list->head=newitem;
24
printf("added head item with id %d at %p\n",newitem->id,newitem);
25
}else{
26
item*last=list->head;
27
/* go to the end of the list */
28
while(last->next!=NULL){
29
last=last->next;
30
}
31
last->next=newitem;
32
printf("added item with id %d at %p - my previous is %p\n",newitem->id,last->next,last);
33
}
34
printf("now are %d elements in the list\n",countItemsfromList(list));
> aber wenn ich es selbst aufzeiche weiß häufig oft> nicht ob ich jetzt ein neues Element anlegen muss> oder es nur ein Pointer in einem Elemet ist.
Du wirst gerade bei Listenmanipulationen noch oft in die Situation
kommen, dass du mit der Zeichnung ein wenig tüfteln musst, in welcher
Reihenfolge was zu geschehen hat.
Das Aufzeichnen hilft dir dabei, weil du ein unmittelbares Feedback
hast, ohne dich um Details wie Syntax kümmern zu müssen.
Ansonsten: Mach die Dinge auf dem Papier so, wie sie dir logisch
vorkommen. Dann formulierst du deinen Plan und probierst ihn mit einem
leeren Blatt nochmal aus. Das zeigt dir dann ganz von alleine, ob dein
Plan was taugt oder nicht.
Kein Meister ist vom Himmel gefallen und man muss alles üben. Das gilt
für nichts so sehr wie für dynamische Datenstrukturen. Und mit der Zeit
wirst du immer wiederkehrende Programmmuster bemerken
zb
T* pLoop = irgendwas->first;
while( pLoop ) {
mach was mit *pLoop;
pLoop = pLoop->next;
}
das arbeitet eine Liste komplett ab. Jedes einzelne Element
wohingegen das hier
T* pLoop = irgendwas->first;
if( pLoop ) {
while( pLoop->next ) {
mach was mit *pLoop;
pLoop = pLoop->next;
}
}
das letzte Element ausnimmt und nix damit macht.
Ebenfalls wichtig:
Bei Listen gibt es immer 2 Sonderfälle, die man möglicherweise
unterscheiden muss:
* das eine ist die leere Liste
* das andere ist eine Liste, in der schon was drinnen ist.
D.h. wenn man seinen Plan testet, dann testet man diese beiden Fälle.
Leere Liste und Liste mit was drinnen. Ob in der Liste 2, 5, 10, 1000
Knoten sitzen, spielt meistens keine Rolle, d.h. du nimmst einfach mal 2
oder 3 vorhandene Knoten an und probierst deinen Plan damit durch. Zu
viele sind nicht sinnvoll, sonst testest du dich dumm und dämlich.
> struct List *liste = (List*)malloc(sizeof(List));> Ich würd es so verstehen, dass malloc die Größe zurückgibt
No.
Malloc reserviert Speicher. Punkt
Das vor dem malloc in den Klammern ist ein Cast. In C ist der nicht
notwendig und an dieser Stelle sogar keine gute Idee. Lass ihn weg
struct List *liste = malloc(sizeof(List));
> Gibt es einen unterschied zwischen> List *liste = (List*)malloc(sizeof(List)); und> struct List *liste = (List*)malloc(sizeof(List)); ?
ohne den typedef wäre das erste ein Syntaxfehler. Strukturnamen sind in
C nicht automatisch neue Datentypen.
Christian Q. schrieb:> Was ich jedoch nicht verstehen ist diese Zeilestruct List *liste =
(List*)malloc(sizeof(List));Ich würd es so verstehen, dass malloc die Größe
zurückgibt die sie im
> Speicher allokiert hat und in Liste* speichert was wiederum direkt vor> liste steht und somit eine liste erzeugt und dem Compiler mitteilt wie> groß diese ist.
Hm, dein C-Buch hast du aber mal gelesen? Mir schwant, dir fehlen noch
ein paar Grundlagen, die lange vor Zeigern kommen...
xXx schrieb:> Hm, dein C-Buch hast du aber mal gelesen? Mir schwant, dir fehlen noch> ein paar Grundlagen, die lange vor Zeigern kommen...
öhm .. Pointer sind auf Seite 39. Casting auf 393. ;-))
Spaß, ich bin Anfänger aber in manchen Situationen verschiebt sich die
Grenze zwischen Bekanntem und Neuem .. und ob man dadurch dümmer wird
weiß ich nicht.
Thread beobachten
Seitenaufteilung abschalten