C中的單個鏈接列表

Question

我想在C中編寫一個單向鏈表。到目前爲止，我只是得到分段錯誤。 我可能設置指針錯了，但我只是不知道如何正確地做到這一點。

該列表應該用於從最高優先級（在列表的開始處）到最低優先級（在列表的末尾）排序的「處理器」。頭應該指向第一個元素，但不知何故我做錯了。

的一切都在這裏首先是代碼：

struct process { 
    int id; 
    int priority; 
    struct process *next; 
} 

struct process *head = NULL; 

void insert(int id, int priority) { 
    struct process * element = (struct process *) malloc(sizeof(struct process)); 

    element->id = id; 
    element->priority = priority; 

    while(head->next->priority >= priority) 
     head = head->next; 

    element->next = head->next; 
    head->next = element; 
    // I put here a printf to result, which leads to segmenatition fault 
    // printf("%d %d\n", element->id, element->priority); 
} 

/* This function should return and remove element with the highest priority */ 
int pop() { 
    struct process * element = head->next; 
    if(element == NULL) 
     return -1; 
    head->next = element->next; 
    free(element); 
    return element->id; 
} 
/* This function should remove a element with a given id */ 
void popId(int id) { 
    struct process *ptr = head; 
    struct process *tmp = NULL; 

    while(prt != NULL) { 
     if(ptr->id == id) { 
      ptr->next = ptr->next->next; 
      tmp = ptr->next; 
     } else { 
      prt = ptr->next; 
     } 
    } 
    free(tmp); 
} 

不幸的是，我不能嘗試pop()和popId()由於分段錯誤。

有人可以告訴我我做錯了什麼？

編輯：現在，我編輯了插入功能。它看起來像這樣：

void insert(int id, int priority) { 
    struct process * element = (struct process *) malloc(sizeof(struct process)); 
    struct process * temp = head; 

    element->id = id; 
    element->priority = priority; 

    if(head == NULL) { 
     head = element; // edited due to Dukeling 
     element->next = NULL; 
    } else { 

     while(temp->next != NULL && temp->next->priority >= priority) 
      temp = temp->next; 

     element->next = head->next; 
     head->next = element; 
    } 
    // I put here a printf to result, which leads to segmenatition fault 
    // printf("%d %d\n", element->id, element->priority); 
} 

但我仍然得到分段故障爲pop（）和popId（）。我在這裏錯過了什麼？

Answer 1

對於insert：

對這些行：

while(head->next->priority >= priority) 
    head = head->next; 

• 如果head是NULL，這是行不通的。如果head永遠不可能是NULL（無論哪種原因）（例如，它提供了一個像上面提到的gruszczy的虛擬元素），這可能實際上不成問題。

• 您正在更改head，因此每次插入時都會排除前幾個元素。你可能需要一個臨時變量。

• 如果您到達列表末尾，還需要檢查NULL。

所以，我們得到：

struct process *temp = head; 
while (temp->next != NULL && temp->next->priority >= priority) 
    temp = temp->next; 

對於pop：

如果第一個元素是不是一個虛設的元素，那麼你就應該返回的head的ID，而不是head->next（並且您試圖返回已經釋放的變量的值 - 這是未定義的行爲）。

if (head == NULL) 
    return -1; 
int id = head->id; 
struct process *temp = head; 
head = head->next; 
free(temp); 
return id; 

對於popId：

• 你檢查ptr的ID，但是，如果這是我們正在尋找的，你卸下下一個元素，而不是ptr的一個。你應該檢查下一個人的ID。

• head == NULL將再次需要是一個特例。

• free應該在if語句中。如果不是，則需要迎合它未找到或找到具有相同ID的多個元素。

• 如果只能有一個帶有該ID的元素，或者只想刪除第一個這樣的元素，則應該跳出if語句中的循環。

我會給你解決，但這裏是一個使用雙指針的版本。

void popId(int id) 
{ 
    struct process **ptr = &head; 

    while (*ptr != NULL) 
    { 
     if ((*ptr)->id == id) 
     { 
      struct process *temp = *ptr; 
      *ptr = (*ptr)->next; 
      free(temp); 
     } 
     else 
     { 
      prt = &(*ptr)->next; 
     } 
    } 
} 

請注意，上述代碼不會在if語句中跳出循環。如果你保證只有一個元素在列表中有一個給定的ID，或者你想刪除第一個這樣的元素，那麼可以添加這個元素。

Answer 2

你不檢查是否head是NULL在insert。

實際上，您不檢查head是否爲NULL的任何函數。除非您想在head上放置一些虛擬元素，否則應該簡化代碼。

Answer 3

您在訪問其取消引用的值之前未檢查您的指針。如果指針無效（NULL或不確定），這會自動導致未定義的行爲。下面每個實現，注意，我們不通過取消引用訪問數據，除非指針第一稱爲有效：

實現：insert()

void insert(int id, int priority) 
{ 
    struct process **pp = &head; 
    struct process *element = malloc(sizeof(*element); 
    element->id = id; 
    element->priority = priority; 

    while (*pp && (*pp)->priority >= priority) 
     pp = &(*pp)->next; 

    element->next = *pp; 
    *pp = element; 
} 

實現：pop()

你函數pop()似乎被設計爲返回彈出的值。雖然這並不罕見，但它具有不希望的副作用，因爲沒有任何機制與主叫方進行通信，表明隊列爲空而沒有某種類型的標記值（例如（-1））。是大多數隊列具有top(),pop()和isempty()功能接口的主要原因。無論如何，假設（-1）是作爲一個錯誤條件可接受：

int pop() 
{ 
    struct process *tmp = head; 
    int res = -1; 
    if (head) 
    { 
     head = head->next; 
     res = tmp->id; 
     free(tmp); 
    } 
    return res; 
} 

實現：popId()

再次，尋找一個特定的節點可以與一個指針到指針以完成相當簡潔的算法，並適當使用實際的物理指針，而不僅僅是他們的價值觀爲你做自動更新：

void popId(int id) 
{ 
    struct process ** pp = &head, *tmp = NULL; 
    while (*pp && (*pp)->id != id) 
     pp = &(*pp)->next; 

    if (*pp) 
    { 
     tmp = *pp; 
     *pp = tmp->next; 
     free(tmp); 
    } 
} 

我強烈建議通過調試程序逐步完成其中的每一個工作，以瞭解它們的工作方式，特別是insert()方法，該方法對於看起來少量的代碼有相當多的內容。

祝你好運