分段錯誤，在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; 

}