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()方法，该方法对于看起来少量的代码有相当多的内容。

祝你好运