链接列表按字母顺序排列

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; 
} 

此代码是不完整的，是不是真的不错，但你可以与启动。