鏈接列表按字母順序排列

Question

我試圖將節點插入鏈表，以便每個節點的數據中包含的字符串按字母順序排序。如果輸入了重複的單詞，則會增加節點的「count」整數。我得到了一個創建節點的makeLnode（）函數，一個比較兩個字符串的isGreater（）函數和一個返回每個節點字符串的getLnodeValue（）函數。

lnode insertWord(char * word, lnode head) { 
    /* Your code to insert a word in the linked list goes here */ 

    lnode temp = makeLnode(word); 

    if(head == NULL) // if head is null, make head=temp 
    { 
      head = temp; 
    } 

    else if(isGreater(getLnodeValue(temp),getLnodeValue(head)) == -1) // if temp < head, place temp before head 
    { 
      temp->next = head; 
      head = temp; 
    } 

    else 
    { 
      lnode curr; 
      for(curr = head; curr; curr = curr->next) // loop through linked list 
      { 

        if(isGreater(getLnodeValue(temp),getLnodeValue(curr)) == 0) // if curr = temp, increment curr 
        { 
          curr->count++; 
          break; 
        } 

        else if(isGreater(getLnodeValue(temp),getLnodeValue(curr)) == -1) // if temp < curr, place temp before curr 
        { 
          temp->next = curr->next; 
          curr->next = temp; 
          break; 
        } 

        else if(curr->next == NULL) // if we reach the end of the list and temp > all other nodes, place temp at end of list 
        { 
          curr->next = temp; 
          break; 

        } 
      } 
    } 


    return head; 
} 

只有一些單詞增加了一些單詞的倍數。我的輸出如下：

1. - 2 - a 
2. - 2 - is 
3. - 1 - broadcasting 
4. - 1 - emergency 
5. - 1 - be 
6. - 1 - for 
7. - 2 - this 
8. - 1 - system 
9. - 1 - system 
10. - 1 - the 
11. - 1 - testing 
12. - 1 - seconds 
13. - 1 - sixty 
14. - 1 - next 
15. - 1 - the 
16. - 1 - test 
17. - 1 - only 
18. - 1 - test 
19. - 1 - well 

Answer 1

你說// if temp < curr, place temp before curr但實際上是把它之後：

temp->next = curr->next; 
curr->next = temp; 

正如你看到的，因爲你的輸出沒有排序。

也可能存在isGreater的問題，也有內存泄漏，但這應該是第一個要解決的問題。

我不想在這裏重構整個代碼，因爲這不是問題，請隨時詢問是否仍有問題。

Answer 2

首先，您甚至在檢查是否需要創建節點之前創建節點：如果該單詞出現在列表中，則不需要該新節點。

然後，您應該瀏覽列表，直到您找到更大的值或達到最終。然後你插入你的節點。無需測試這三種情況。

例如：

// check for the following base cases : no node, one node, then : 
lnode node = head; 
while (node->next && (isGreater(word,getLnodeValue(node->next)) == 1)) 
{ 
    node = node->next; 
} 

// check if the next node value is the same as your word and if it is, increment its count. 
if (isGreater(word,getLnodeValue(node->next)) == 0) 
{ 
    node->next->count++; 
} 

// Else, create a node with the word and insert the new node after the current node : 
else 
{ 
    lnode new_node = makeLnode(word); 
    new_node->next = node->next; 
    node->next = new_node; 
} 

此代碼是不完整的，是不是真的不錯，但你可以與啓動。