C语言 链表按字母顺序插入

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

这段代码不完整，也不是很好，但你可以从它开始。