Mit single-versus double-Zeiger in verketteten Listen implementiert in C

Ich dies Schreibe code für das hinzufügen element am Ende der verlinkten Liste:

struct node{
    int info;
    struct node* link;
};

void append ( struct node **q, int num )  
{

struct node *temp, *r ;

if ( *q == NULL )       //if the list is empty, create first node
{
    temp = (struct node*) malloc ( sizeof ( struct node ) ) ;
    temp -> info = num ;
    temp -> link = NULL ;
    *q = temp ;        
}
else{
    temp = *q ;         

    /* go to last node */
    while ( temp -> link != NULL )
        temp = temp -> link ;

    /* add node at the end */
    r = (struct node *)malloc ( sizeof ( struct node ) ) ;
    r -> info = num ;
    r -> link = NULL ;
    temp -> link = r ;
}
}

und ich rufe die append Funktion so:
append(&list, 10); wo list ist der Zeiger auf die verkettete Liste

Dieser code funktioniert, aber wenn ich einzelnen Zeiger im append-Funktion(mit *q anstelle von ** * * f) und nehmen Sie entsprechende änderungen vor (wie unten getan und auch wenn ich es nennen), es funktioniert nicht. Was ist falsch mit dem code unten?:

void append ( struct node *q, int num )  
{

struct node *temp, *r ;

if ( q == NULL )       //if the list is empty, create first node
{
    temp = (struct node*) malloc ( sizeof ( struct node ) ) ;
    temp -> info = num ;
    temp -> link = NULL ;
    q = temp ;        
}
else{
    temp = q ;         

    /* go to last node */
    while ( temp -> link != NULL )
        temp = temp -> link ;

    /* add node at the end */
    r = (struct node *)malloc ( sizeof ( struct node ) ) ;
    r -> info = num ;
    r -> link = NULL ;
    temp -> link = r ;
}
}
  • Warum ist diese Kennzeichnung als C++?
  • da C und C++ sind eng miteinander verbunden, und ich war der Annahme, jemand mit dem wissen von C++ könnten in der Lage sein, mir zu helfen hier.
  • Übrigens, dies ist ein schlechter Ansatz, um das Anhängen eines Elements zu der Liste, weil die Laufzeit steigt Linear mit der Anzahl der Elemente. Der traditionelle Ansatz ist es, stets einen Zeiger auf beide enden der Liste, die es ermöglicht das Anhängen geschieht in konstanter Zeit.
InformationsquelleAutor Jatin | 2012-04-06
  1. 3

    Weil im zweiten Beispiel q ist ein kopieren der übergebene Zeiger von dem Anrufer. Der Anrufer ist original Zeiger wird nie geändert.

    • Aber list ist der Zeiger zu einem Knoten. Also, er speichert eine Adresse. Also, wenn ich rufe append(list, 10); ich bin vorbei an der Adresse, so sollte dies nicht ändern, die ursprüngliche verknüpfte Liste.
    • Nicht für den Teil des code gekennzeichnet ", Wenn die Liste leer ist, erstellen Sie den ersten Knoten."
    • Also, vorausgesetzt, ich habe mindestens 1 element in der Liste, dann der zweite code funktioniert, richtig?
    • und @Oli, könntest du bitte näher auf Sie letzter Kommentar?
    • Die if Abschnitt ändert sich der Wert von q, aber das wird nicht werden, spiegelt sich in dem Wert, den der Aufrufer übergibt, weil es eine Kopie). Jedoch, die else Abschnitt dies nicht tut, so ist dieser Teil funktioniert wohl ok.
    InformationsquelleAutor Oliver Charlesworth
  2. 1

    In deinem ersten snippet (das ist richtig), sind Sie zu viel zu tun.

    void append ( struct node **q, int num )  
{

struct node *new ;

    /* go to last node */
    for ( ; *q; q = &(*q)->link ) {;}

    /* add node at the end */
    new = malloc ( sizeof *new );
    if (!new) { barf_now(); return; }

    new->info = num ;
    new->link = NULL ;
    *q = new; ;
    }
}

    Die grundlegende Idee ist: Sie wollen zum Anhängen an den Schwanz der Liste; Sie müssen:

    • finde das erste NULL-Zeiger
    • setzen Sie den Wert auf den Wert des neuen Zeiger

    Die "leere Liste" der Fall ist nichts besonderes, es bedeutet nur, dass Sie finden den NULL-Zeiger null Schritte. Codierung es auf diese Weise es gibt keine speziellen Fall, und keine Notwendigkeit für eine if (...) ... else ... konstruieren.

    InformationsquelleAutor wildplasser
Schreibe einen Kommentar