分段错误，在C中的列表

Question

我试图直接使用两个函数直接对我在链接列表中输入的数字进行排序第一个添加元素头部第二个包含分段错误的元素应该利用第一个元素做这项工作。

#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

该代码有一个问题，在某些情况下列表可能会损坏;很容易让列表进入没有正确终止的状态（并且可能会从列表中“失去”节点）。根据其他代码如何操作列表，这种情况可能会导致问题。

如果您尝试在列表中添加一个非空的新节点，但新值小于或等于第一个节点的值，则该列表将最终成为一个包含两个节点的循环列表。位于列表首位之后的任何节点都将丢失。

发生这种情况是因为在那种情况下，p和q将在调用insert_tete(p,n)时指向该节点。在insert_tete(p,n)返回后，p-suivant和q将指向列表头部的节点。所以当

q->suivant = p; 

被执行，列表将是循环和'额外'节点将丢失。

根据您的其他操作如何在列表中执行操作（尤其是如何/如何删除元素），您可能会发现自己在suivant字段中留下了一个悬挂指针（这可能会导致段错误），或者以无限循环。

Answer 2

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

在这里，我们知道，L是不是NULL

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

在这里得到一个合法的段错误的唯一方法是，p后面的指针之一是一个非0指针没有按指向正确分配的struct cellule，但指向一些无法访问的内存。然后尝试访问p->val（或p->suivant）会导致段错误。

最常见的方式（在我有限的经验）陷入这种情况是忘记第一指针初始化为0

Answer 3

绝不做我相信，这将修复它，但至少有一个错误代码。

考虑其中L被初始化的情况下，但Ñ< 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

使用指针到指针简化版本。注意：空列表没有特殊情况。

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; 

}