Segmentierungsfehler, Listen in C

Question

Ich habe versucht, die Zahlen, die ich in eine verkettete Liste eingeben, direkt mit zwei Funktionen zu sortieren: die erste fügt das Element am Kopf hinzu, die zweite, die den Segmentierungsfehler enthält, soll den ersten ausnutzen mach den Job.

#include <stdio.h> 
#include <stdlib.h> 
typedef struct cellule 
{ 
    int val; 
    struct cellule *suivant; 
} cellule; 
typedef struct cellule* liste; 

liste insert_tete(liste L,int n) 
{ 

    liste p; 

    p=malloc(sizeof(cellule)); 
    p->val=n; 
    p->suivant=L; 
    return p; 
}//ok :) 
liste insert_croissant(liste L,int n) 
{ 
    if(!L) 
    { 
     L=insert_tete(L,n); 
     return L; 
    } 

    liste p,q; 
    for(q=L,p=L; (p!=NULL)&&(n> (p->val)) ; q=p,p=p->suivant); // 

    p=insert_tete(p,n); 
    q->suivant=p; 
    return L; 
} 

Answer 1

Der Code hat ein Problem, wo die Liste in bestimmten Fällen beschädigt werden kann; Es ist einfach, die Liste in einen Zustand zu bringen, in dem sie nicht ordnungsgemäß beendet wird (und möglicherweise Knoten aus der Liste verliert). Und diese Situation könnte Probleme verursachen, abhängig davon, wie anderer Code die Liste manipulieren könnte.

Wenn Sie versuchen, einen neuen Knoten in einer Liste hinzuzufügen, die nicht leer ist, aber der neue Wert kleiner oder gleich dem Wert des ersten Knotens ist, wird die Liste eine kreisförmige Liste mit zwei Knoten sein . Alle Knoten nach demjenigen, der an der Spitze der Liste war, sind verloren.

Dies passiert, weil in diesem Fall sowohl als auch q auf diesen Knoten zeigen, wenn insert_tete(p,n) aufgerufen wird. Nach insert_tete(p,n) kehrt zurück, p-suivant und q wird auf den Knoten am Anfang der Liste zeigen. Wenn also

ausgeführt wird, wird die Liste kreisförmig sein und 'zusätzliche' Knoten werden verloren gehen.

Je nachdem, wie Ihre anderen Operationen auf die Liste wirken (insbesondere wenn/wie Sie Elemente löschen), können Sie sich mit einem unbelegten Zeiger in einem suivant Feld befinden (was zu einem Segmentfehler führen kann) Endlosschleife.

Answer 2

liste insert_croissant(liste L,int n) 
{ 
    if(!L) 
    { 
     L=insert_tete(L,n); 
     return L; 
    } 

Hier wissen wir, dass L nicht NULL

liste p,q; 
    for(q=L,p=L; (p!=NULL)&&(n> (p->val)) ; q=p,p=p->suivant); // 

ist

Die einzige Möglichkeit, hier ein berechtigtes segfault zu erhalten, ist, dass einer der Zeiger p folgt, ist eine Nicht-0-Zeiger, der doesn nicht auf einen korrekt zugewiesenen struct cellule, sondern auf einen nicht zugänglichen Speicher zeigen. Wenn Sie versuchen, auf p->val (oder p->suivant) zuzugreifen, wird ein Segmentfehler verursacht.

Die häufigste Art und Weise (in meiner begrenzten Erfahrung) in diese Situation zu erhalten ist, zu vergessen, die ersten Zeiger auf 0

Answer 3

Keineswegs zu initialisieren glaube ich das es beheben, aber es ist zumindest ein Fehler in Ihrem Code.

Betrachten wir den Fall, wo L initialisiert, aber n < L-> val:

// p = L, q = L; 
// Let L = [val|->... 
p=insert_tete(p,n); 
// p = [n|->[val|->... 
q->suivant=p; 
// q = L 
// Therefore [val|->[n|->L 
// And you've just made your linked list circular. 

Answer 4

Vereinfachte Version Zeiger-to-Zeiger verwenden. Hinweis: Es gibt keinen speziellen Fall für die leere Liste.

struct cellule { 
    int val; 
    struct cellule *suivant; 
    }; 

struct cellule *insert_croissant(struct cellule **LL, int val) 
{ 

    struct cellule *p,**pp; 

    for(pp=LL ; *pp && (*pp)->val < val ; pp = &(*pp)->suivant) {;} 
     /* When we arrive here, pp points to whatever pointer happens 
     ** to point to our current node. 
     ** - If the list was empty, *pp==NULL 
     ** - if the place to insert happens to be the tail of the list, *p is also NULL   
     ** - in all cases, *pp should be placed after the new node, and the new node's pointer should be assigned to *pp 
     */ 
    p = malloc(sizeof *p); 
    p->val = val; 
    p->suivant = *pp; 
    *pp = p; 

    return *LL; 

}