C ++：按字母顺序将节点添加到双向链表

Question

我正在尝试将节点添加到按字母顺序排列的双向链表（相对于节点的 title 元素）。到目前为止，我已经尝试遍历列表并检查大小写 (strcmp(title, currTitle) > 0)。但是，迭代不起作用（出于我不确定的原因），因为下面列出的尝试不会将任何项目添加到链接列表中。

if - else 块的四个条件集在排序尝试未实现时成功将项目添加到列表中。

void SongList::addSongSorted(const Song &aSong)
{
    //sort inputs to the list by alphabetical order of the entire title
    char title[MAX_CHAR];
    char currTitle[MAX_CHAR];
    aSong.getTitle(title);

    Node * newNode = new Node(aSong);

    Node * curr = head;
    //Increment through list as added...this does not work
    for(curr = head; curr; curr = curr->next)
    {

        if(strcmp(title, currTitle) > 0)
        {

            if(!head)
            {
                head = newNode;
                tail = newNode;
                head->next = NULL;
                head->prev = NULL;
            }
            else if(head->prev == NULL)
            {
                newNode->next = head;
                head = newNode;
                newNode->prev = NULL;
            }

            else if(head->next == NULL)
            {
                curr->next = newNode;
                newNode->prev = curr;
                newNode->next = NULL;
                tail = newNode;
            }

            else
            {
                newNode->next = curr->next;
                newNode->prev = curr;
            }
        }
    }
}

为什么在列表中递增并在基于元素比较的节点处添加不起作用？什么是解决方案？

Answer 1

正如@verbose 所说，您从未真正为 currTitle 赋值，请尝试在循环开始时使用 curr.getTitle(currTitle)，或在其位置使用 curr->title。

关于顺序插入，不用担心head的前一个值，只要head本身为null，或者标题在head之前。您应该遍历列表，如果标题出现在当前节点之后，并且下一个节点为空，则将 curr 设置为下一个元素（在 for 循环中完成）并再次检查。如果下一个元素为 NULL，并且标题出现在当前元素之后，则您已到达列表的末尾，可以插入歌曲，然后中断。如果歌曲标题出现在当前歌曲之前，或者相等，则将新歌曲插入当前歌曲之前并且 return。示例代码如下：

if(!head)
{
    // set head to currnode, as you have
    head = newNode;
    tail = head;
    next = NULL;
    prev = NULL;
    return; // no need to iterate through the list
}
bool inserted = false;
while (!inserted) 
{
    curr->song.getTitle(currTitle);
    if(strcmp(title, currTitle) > 0)
    {
        // If the title goes after the current title 
        if(curr->next == NULL)
        {
            // End of the list, insert after this node
            curr->next = newNode;
            newNode->prev = curr;
            newNode->next = NULL;
            tail = newNode;
            inserted = true;
        }
        // If we don't insert here, we iterate again
        curr = curr->next;
    }
    else 
    {
        // If the title is the same, or comes before the current title, insert before curr
        newNode->prev = curr->prev;
        newNode->next = curr;
        curr->prev = newNode;
        if (curr == head)
        {
            head = newNode;
        }
        inserted = true
    }
}

Answer 2

您正在比较两个字符串，但第二个字符串似乎从未被初始化。大概 aSong.getTitle(title) 将当前歌曲的标题复制到 title[] 数组中。但是什么时候复制到 currTitle[]?

所以currTitle[]的元素都是垃圾，比较不通。要解决此问题，请将要插入的歌曲的标题与列表中已有歌曲的标题进行比较。你可能想要像 strcmp(title, curr->title) 这样的东西。

当然，在进行比较之前，您首先需要检查歌曲是否确实存在。首先检查 head 处是否存在歌曲，如果不存在，则将歌曲作为头曲插入。如果头部已经有一首歌曲，比较两个标题并确定新歌曲是否应该是新的头部，或者它是否应该在头部之后的某个地方。其余的逻辑应该很简单。

C ++：按字母顺序将节点添加到双向链表

C++: Adding node to doubly linked list in alphabetical order

c++

sorting

linked-list

doubly-linked-list