[C] elementen toevoegen aan begin van linked list

[Verwijderd]

Ik heb het volgende stuk C-code geschreven:

C:

#include<stdlib.h>
#include<stdio.h>

typedef struct node {
  int val;
  node * next;
} nodeType;

nodeType * root;
nodeType * ptr;

int main() {
  root = (nodeType *) malloc(sizeof(nodeType));
  ptr = root;

  for (int i=0; i<=10; i++) {
    ptr->val = i;
    root = (nodeType *) malloc(sizeof(nodeType));
    root->next = ptr;
    ptr = root;
  }

  ptr = root;
  while (ptr->next != 0) {
    printf("%d\n", ptr->val);
    ptr = ptr->next;
  }

  return 1;
}

Met deze code voeg ik dus in een for-loop steeds een nieuw element toe aan het begin van de linked list.

Maar de while-loop geeft de volgende output:

0
10
9
8
7
6
5
4
3
2
1

Hoe komt het dat hij begint met de 0, terwijl deze juist aan het einde zou moeten staan

[ Voor 26% gewijzigd door Verwijderd op 13-03-2003 01:02 ]

[johnwoo]

C:

root = (nodeType *) malloc(sizeof(nodeType *));

Haal eerst die * op het eind maar eens weg, je maakt nu nergens ruimte voor een volledige nodeType; je maakt nu ruimte voor een pointer ernaartoe. Aangenomen dat je op een 32-bits platform werkt maak je dus in feite net genoeg ruimte voor de int val.

[edit]
Arg, snel weg-editen he

Overigens lijkt het me verstandig om in je main code zelf niet direct de nodes te gebruiken; meestal worden daar head(), tail() functies voor gebruikt, dat schermt de implementatie van je eigen programmacode af, waardoor deze code overzichtelijker wordt.

[ Voor 33% gewijzigd door johnwoo op 13-03-2003 01:01 ]

[Verwijderd]

a) Het laatst toegevoegde element heeft geen val dus wijst 't naar 'n random stuk geheugen waar nu toevallig 0 bij jou staat (in vc staat er crap)
b) het eerst toegevoegde(0) element print je niet doordat je naar ptr->next kijkt ipv naar ptr

[Verwijderd]

johnwoo schreef op 13 March 2003 @ 00:57:

C:

root = (nodeType *) malloc(sizeof(nodeType *));

Haal eerst die * op het eind maar eens weg, je maakt nu nergens ruimte voor een volledige nodeType; je maakt nu ruimte voor een pointer ernaartoe. Aangenomen dat je op een 32-bits platform werkt maak je dus in feite net genoeg ruimte voor de int val.
[edit]
Arg, snel weg-editen he

Hehe, zag het ook net. Tikfoutje, maar het probleem blijft

[curry684]

Knappe code, step er maar eens met de debugger doorheen. Als laatste wordt nog een element toevoegt waarvan je de value niet initialiseert. En omdat je in debugmode zit te builden heb je 'geluk' met dat die op 0 wordt geinitialiseerd, oftewel dat is die 0 waarde op de head.

Kort samengevat: klopt niet veel van

De reden dat het laatste element niet verschijnt: zie Yarvieh (khad ff fout gelezen).

[ Voor 38% gewijzigd door curry684 op 13-03-2003 01:13 . Reden: foutje ]

[Verwijderd]

curry684 schreef op 13 March 2003 @ 01:01:
/edit
snel editen he?

Hmmmm, net voor het eerst even wat zitten kloten met gdb, maar daar begrijp ik nog niet heel erg veel van.

Kun je misschien een voorbeeld geven van hoe het wel zou werken? Want ik zie niet helemaal in wat ik nou doe met overbodige entries.

Pfff, ik zit me hier ook alweer veel te lang op blind te staren, moest maar eens gaan lunchen ofzo...

/edit
D'OH, Ik was duidelijk te lang bezig hier.... Maar nu werkt het wel ok

[ Voor 42% gewijzigd door Verwijderd op 13-03-2003 01:31 ]

[curry684]

Vergelijk je code eens met deze:

C:

#include<stdlib.h> 
#include<stdio.h> 

typedef struct node { 
  int val; 
  node * next; 
} nodeType; 

nodeType * root = NULL; 

int main() { 
  nodeType * ptr;

  for (int i=0; i<=10; i++) { 
    ptr = root;
    root = (nodeType *) malloc(sizeof(nodeType)); 
    root->val = i; 
    root->next = ptr;
  } 

  ptr = root; 
  while (ptr) { 
    printf("%d\n", ptr->val); 
    ptr = ptr->next; 
  } 

  return 1; 
}

Tis ff notepad hobbywerk dus kweetniet eens of het compiled maar volgens mij klopt ie zo. Leg ze maar eens naast mekaar om de verschillen te zien.

[MSalters]

't Is overigens C++
In C moet het

code:

typedef struct node {  
  int val;  
  struct node * next;  
} nodeType;

zijn.

[Verwijderd]

Als je slim bent maak je het voor jezelf overzichtelijk met subfuncties, zoals in de GList API (linked list in glib). Bijvoorbeeld:

C:

nodeType *
node_prepend (nodeType *root, int val)
{
  nodeType *ptr = (nodeType *) malloc(sizeof(nodeType));
  ptr->value = val;

  /* prepending means that the rest follows from here */
  ptr->next = root;

  return ptr;
}

etc. - dat is een stuk overzichtelijker voor jezelf, lijkt me.

[curry684]

Verwijderd schreef op 13 maart 2003 @ 10:36:
Als je slim bent maak je het voor jezelf overzichtelijk met subfuncties, zoals in de GList API (linked list in glib). Bijvoorbeeld:

Ik denk niet dat het 'm gaat om de best mogelijke implementatie van een linked list maar om te leren programmeren en te snappen hoe zo'n ding werkt.