0

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

#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;
}
4

4 回答 4

2

我绝不相信这会解决它，但您的代码中至少存在一个错误。

考虑 L 已初始化但 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.
于 2012-04-11T23:02:43.267 回答
1 
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。

于 2012-04-11T22:46:58.330 回答
0

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

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;

}
于 2012-04-11T23:19:51.863 回答
0

该代码存在列表在某些情况下可能会损坏的问题；很容易使列表进入未正确终止的状态（并且可能从列表中“丢失”节点）。这种情况可能会导致问题，具体取决于其他代码如何操作列表。

如果您尝试在不为空的列表上添加新节点，但新值小于或等于第一个节点的值，则列表最终将成为一个包含两个节点的循环列表。位于列表头部的节点之后的所有节点都将丢失。

发生这种情况是因为在这种情况下，两者p都会在被调用q时指向该节点。返回insert_tete(p,n)后，将指向链表头部的节点。所以当insert_tete(p,n)p-suivantq

q->suivant = p;

执行时，列表将是循环的，“额外”节点将丢失。

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

于 2012-04-11T23:21:45.043 回答