按升序将值插入排序后的链表

Question

该函数将要求用户输入一个整数，然后按升序将其插入到链表中。如果当前值已经存在，将不会插入。

typedef struct _listnode{ 
    int item; 
    struct _listnode *next; 
} ListNode;   

typedef struct _linkedlist{ 
    int size; 
    ListNode *head; 
} LinkedList;   

void insertSortedLinkedList(LinkedList *l) 
{ 
    ListNode *cur = l->head; 
    ListNode* newNode = malloc(sizeof(ListNode)); // create the node to be inserted 
    int x; 
    printf("please input an integer you want to add to the linked list:"); 
    scanf("%d", &x); 
    newNode->item = x; 
    newNode->next = NULL; 

    if (l->head == NULL) // linkedlist is empty, inserting as first element 
    { 
     l->head = malloc(sizeof(ListNode)); 
     l->head->item = x; 
     l->head->next = NULL; 
     l->size++; 
    } 
    else 
    { 

     if (x < l->head->item) // data is smaller than first element, we will insert at first element and update head. 
     { 
      newNode->next = l->head; 
      l->head = newNode; 
      l->size++; 
      return; 
     } 
     while (cur->next != NULL) // loop through the linkedlist 
     { 
      if (cur->next->item > x) // next element is bigger than data, we will insert it now. 
      { 
       if (cur->item != x) // if current element is not same as data, it must not have already existed. 
       { 
        newNode->next = cur->next; 
        cur->next = newNode; 
        l->size++; 
        return; 
       } 
      } 
      if (cur->next == NULL) // we have reached the last element and data is even greater than that. we will then insert it as last element. 
      { 
       cur->next = newNode; 
       l->size++; 
       return; 
      } 
      cur = cur->next; 
     } 
    } 
} 

不知何故，它有一个错误。当我尝试插入以下内容时，我得到了这些结果。如果数据大于存在的数据，它也不会插入。

Insert : 10 
Result : 10 
Insert : 5 
Result : 5 10 
Insert : 8 
Result : 5 8 10 
Insert : 10 
Result : 5 8 10 
Insert : 7 
Result : 5 7 8 10 
Insert : 9 
Result : 5 7 8 9 10 
Insert : 6 
Result : 5 6 7 8 9 10 
Insert : 5 
Result : 5 6 5 7 8 9 10 << why? 

Answer 1

您在错误的地方测试了相等性：您总是跳过第一个节点。您还需要改进分配方案：为头节点分配两次内存，如果整数已经在列表中，则忘记释放内存。

这里是一个改进版本：

void insertSortedLinkedList(LinkedList *l) 
{ 
    ListNode *cur, *newNode; 
    int x; 

    printf("please input an integer you want to add to the linked list:"); 
    if (scanf("%d", &x) != 1) 
     return; 

    newNode = malloc(sizeof(ListNode)); // create the node to be inserted 
    newNode->item = x; 
    newNode->next = NULL; 

    if (l->head == NULL) 
    { 
     // linkedlist is empty, inserting as first element 
     l->head = newNode; 
     l->size++; 
     return; 
    } 
    if (x < l->head->item) 
    { 
     // data is smaller than first element, we will insert at first element and update head. 
     newNode->next = l->head; 
     l->head = newNode; 
     l->size++; 
     return; 
    } 
    for (cur = l->head;; cur = cur->next) // loop through the linkedlist 
    { 
     if (cur->item == x) 
     { 
      // element already in the list 
      free(newNode); 
      return; 
     } 
     if (!cur->next || cur->next->item > x) 
     { 
      // next element is bigger than data or end of list, we will insert it now. 
      newNode->next = cur->next; 
      cur->next = newNode; 
      l->size++; 
      return; 
     } 
    } 
} 

这个代码可以使用指向链接缩短：

void insertSortedLinkedList(LinkedList *l) 
{ 
    ListNode **curp, *cur, *newNode; 
    int x; 

    printf("please input an integer you want to add to the linked list:"); 
    if (scanf("%d", &x) != 1) 
     return; 

    for (curp = &l->head; (cur = *curp) != NULL; curp = &cur->next) { 
     if (cur->item == x) 
      return; 
     if (cur->item > x) 
      break; 
    } 
    // cur element is bigger than data or end of list, we will insert it now. 
    newNode = malloc(sizeof(ListNode)); // create the node to be inserted 
    newNode->item = x; 
    newNode->next = cur; 
    *curp = newNode; 
    l->size++; 
} 

Answer 2

问题是，你永远达不到你的，如果条件因为cur->next == NULL你的循环中断时：

while (cur->next != NULL) // loop through the linkedlist 
    .... 
     if (cur->next == NULL) // we have reached the last element and data is even greater than that. we will then insert it as last element. 
     { 
      ... 
     } 
    ... 
    } 

相反，你应该使用while(cur != NULL)的循环，并设置cur->next == NULL为第一个if条件，这样(cur->next->item在cur == NULL时不会崩溃你的程序。

注意：在这种情况下，您的环路条件将不重要，因为if (cur->next == NULL)中的return将打破循环。在你执行那个if条件之前，不要退出循环。