按升序將值插入排序後的鏈表

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條件之前，不要退出循環。