C 语言中的链表 - 第一个节点数据不正确，无法弄清楚

Question

我有一个多线程C程序，其中一个线程创建随机时间和数字，并将它们存储在一个排序的链表中，第二个线程将第一个节点中的时间与当前系统时间进行比较，并在时间相等时删除节点。然而，0 0首先被添加到链表中，我找不到在哪里。据我所知，它并没有被添加到插入函数中。任何帮助都将非常感激。以下是相关代码:

#include <pthread.h> 
#include <stdio.h>
#include <stdlib.h> 
#include <unistd.h> 
#include <time.h>
#include <signal.h> 
pthread_mutex_t count_mutex;
/* Link list node */
struct node
{
    int roomNo;
    time_t time;
    struct node* next;
};
void printList(struct node *node)
{
  while(node!=NULL)
  {
    printf("%d ", node->roomNo);
    printf("%dn ", node->time);
    node = node->next;
  }
}
/* Function to insert a node at the beginging of the linked list */
void insert(struct node** head_ref, int new_room, time_t new_time)
{
  /* allocate node */
  struct node* new_node =
  (struct node*) malloc(sizeof(struct node));
  /* put in the data  */
  new_node->roomNo  = new_room;
  new_node->time  = new_time;
  /* link the old list off the new node */
  new_node->next = (*head_ref);    
  /* move the head to point to the new node */
  (*head_ref)    = new_node;
    MergeSort(&(*head_ref));
} 

/* sorts the linked list by changing next pointers (not data) */
void MergeSort(struct node** headRef)
{
  struct node* head = *headRef;
  struct node* a;
  struct node* b;
  /* Base case -- length 0 or 1 */
  if ((head == NULL) || (head->next == NULL))
  {
     return;
  }
    /* Split head into 'a' and 'b' sublists */
  FrontBackSplit(head, &a, &b); 
  /* Recursively sort the sublists */
  MergeSort(&a);
  MergeSort(&b);
  /* answer = merge the two sorted lists together */
  *headRef = SortedMerge(a, b);
}

struct node* SortedMerge(struct node* a, struct node* b)
{
  struct node* result = NULL;
  /* Base cases */
  if (a == NULL)
    return(b);
  else if (b==NULL)
    return(a);
  /* Pick either a or b, and recur */
  if (a->time <= b->time)
  {
    result = a;
    result->next = SortedMerge(a->next, b);
  }
  else
  {
    result = b;
    result->next = SortedMerge(a, b->next);
  }
  return(result);
 }

void FrontBackSplit(struct node* source,
                     struct node** frontRef, struct node** backRef)
{
  struct node* fast;
  struct node* slow;
  if (source==NULL || source->next==NULL)
  {
    /* length < 2 cases */
    *frontRef = source;
    *backRef = NULL;
  }
  else
  {
    slow = source;
    fast = source->next;
    /* Advance 'fast' two nodes, and advance 'slow' one node */
    while (fast != NULL)
    {
       fast = fast->next;
      if (fast != NULL)
      {
        slow = slow->next;
        fast = fast->next;
      }
    }
    /* 'slow' is before the midpoint in the list, so split it in two
     at that point. */
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
  }
}
void * addThread(void *n) 
{  
  struct node *llnode = n;
  int i;
        for(i = 0; i <4; i++)
    { 
             pthread_mutex_lock(&count_mutex);
             printf("Adding node.n");
             insert(&llnode, getRandRoom(), getRandTime());
     sleep(1);
             printf("the list is...n");
             printList(llnode);
             pthread_mutex_unlock(&count_mutex);
    }
}
struct node* head;
int main()
{
    signal(SIGINT, ctrlc_catch);
    pthread_t addWakeup, makeWakeup;
    pthread_create(&addWakeup, NULL, addThread, (void*)&head);
    pthread_create(&makeWakeup, NULL, wakeThread, (void*)&head);
    pthread_join(addWakeup, NULL);
    pthread_join(makeWakeup, NULL);
      return 0;
}

示例输出如下:

Adding node.
the list is...
0 0
 4000 1323882918
 Adding node.
the list is...
 0 0
 809 1323882890
 4000 1323882918
 Adding node.
the list is...
0 0
 809 1323882890
 7617 1323882908
 4000 1323882918
 Adding node.
the list is...
0 0
 809 1323882890
 7617 1323882908
 4000 1323882918
 4426 1323882926

Answer 1

你的问题很可能是由于传递head(即~ struct node**)而不是head(即struct node*)的地址给线程函数，其中void *被类型转换为struct node*。将此调用pthread_create(&addWakeup, NULL, addThread, (void*)&head);更改为pthread_create(&addWakeup, NULL, addThread, (void*)head); &下一个电话也是类似的。不幸的是在当前的情况下您没有看到崩溃。在我的系统上，我观察到将head初始化为NULL会使程序崩溃。@wildplasser已经提出了类似的建议。尝试此更改并检查打印的列表。
希望这对你有帮助!

Answer 2

函数addthread创建了其参数n的本地副本llnode，并使用指向llnode的指针来调用insert()。Insert可以修改llnode，但是这个更改只会影响本地副本。

你应该改变addThread的参数类型为struct node**，而不是struct node*。

Answer 3

虽然它可能存在于未显示的代码中，但代码可能需要调用pthread_mutex_init来初始化互斥量。变量count_mutex的内容有可能被"偶然"初始化为实际工作的值，但依赖于此并不好。