c++ - 链表遍历跳过值

Question

我是指针的新手，我有点困惑。我写了一个函数来合并和排序两个排序的链表。但是，当我在调用函数后打印列表时，它没有新合并列表的所有值。在调试代码并检查变量和内存位置时，它看起来像是跳过了这些位置，只是跳转到了最后一个内存位置。函数执行后，我需要将值放在新列表中并将 list1 和 list2 留空。这是我在头文件中的方法:

template <class Type>
void orderedLinkedList<Type>::mergeLists(orderedLinkedList<Type> &list1, orderedLinkedList<Type> &list2)
{
    nodeType<Type> *lastSmall; //pointer to the last node of the merged list.
    nodeType<Type> *first1 = list1.first;
    nodeType<Type> *first2 = list2.first;

    if (list1.first == NULL){ //first sublist is empty
        this->first = list2.first;
        list2.first = NULL;
    }
    else if (list2.first == NULL){ // second sublist is empty
        this->first = list1.first;
        list1.first = NULL;
    }
    else{
        if (first1->info < first2->info){ //Compare first nodes
            this->first = first1;
            first1 = first1->link;
            lastSmall = this->first;
        }
        else{
            this->first = first2;
            first2 = first2->link;
            lastSmall = this->first;
        }


    while (first1 != NULL && first2 != NULL)
    {
        if(first1->info < first2->info){
            lastSmall->link = first1;
            lastSmall = lastSmall->link;
            first1 = first1->link;
        }
        else{
            lastSmall->link = first2;
            lastSmall = lastSmall->link;
            first2 = first2->link;
        }
    } //end while

    if (first1 == NULL) //first sublist exhausted first
        lastSmall->link = first2;
    else //second sublist exhausted first
        lastSmall->link = first1;

    list1.first = NULL;
    list1.last = NULL;

    list2.first = NULL;
    list2.last = NULL;
    }
}

然后在我的 main.cpp 中我有:

int main()
{

    orderedLinkedList<int> list1;
    orderedLinkedList<int> list2;
    orderedLinkedList<int> newList;

    list1.insert(2);
    list1.insert(6);
    list1.insert(7);
    list2.insert(3);
    list2.insert(5);
    list2.insert(8);

    newList.mergeLists(list1, list2);
    newList.print();
    return 0;
}

我的打印功能以防万一:

template <class Type>
void linkedListType<Type>::print() const
{
    nodeType<Type> *current; //pointer to traverse the list

    current = first;    //set current so that it points to
                        //the first node
    while (current != NULL) //while more data to print
    {
        cout << current->info << " ";
        current = current->link;
    }
}//end print

有人可以告诉我我做错了什么吗？输出应该是 2 3 5 6 7 8 但实际上是 2 3 7 8。

谢谢

编辑:这是我的插入功能。请注意，此功能来 self 正在使用的书。它包含在我需要添加 mergeLists 方法的同一个类中。它是专门为有序列表编写的:

template<class Type>
void orderedLinkedList<Type>::insert(const Type& newItem)
{
    nodeType<Type> *current;
    nodeType<Type> *trailCurrent;
    nodeType<Type> *newNode;

    bool found;

    newNode = new nodeType<Type>;
    newNode->info = newItem;
    newNode->link = NULL;

    //case1 list is empty
    if(this->first == NULL)
    {
        this->first = newNode;
        this->last = newNode;
        this->count++;
    }
    else //if the list is not empty
    {
        current = this->first;
        found = false;

        while(current != NULL && !found)
        {
            if(current->info >= newItem)
                found = true;
            else
            {
                trailCurrent = current;
                current = current->link;
            }

        //case2 insert newNode at the head
        if(current == this->first)
        {
            newNode->link = this->first;
            this->first = newNode;
            this->count++;
        }
        else //case 3 
        {
            trailCurrent->link = newNode;
            newNode->link = current;

            if(current == NULL)
                this->last = newNode;

        this->count++;
        }
        }
    }
}

书上的3个案例是:

• 案例一:

  列表最初是空的。包含新项目的节点是唯一的节点因此，列表中的第一个节点。

• 案例 2:

  新项小于列表中最小的项。新项目在列表的开头。在这种情况下，我们需要调整列表的头指针——也就是说，首先。此外，计数增加 1。

• 案例三:

  该项目将被插入到列表的某处。

• 案例 3a:

  新项目比列表中的所有项目都大。在这种情况下，新项目被插入到列表的末尾。因此，current 的值为 NULL新项目插入到 trailCurrent 之后。此外，计数增加1.

• 案例 3b:

  新项目将被插入到列表中间的某处。在这个在这种情况下，新项目插入到 trailCurrent 和 current 之间。此外，计数增加 1。

Answer 1

错误在您的插入方法中。插入后在列表上调用 print 时，您会注意到最后一个值被覆盖:

list1.insert(2); list1.print();
list1.insert(6); list1.print();
list1.insert(7); list1.print();
list2.insert(3); list2.print();
list2.insert(5); list2.print();
list2.insert(8); list2.print();

将输出:

2
2 6
2 7
3
3 5
3 8

这是因为每次迭代 trailCurrent->link = newNode; 都会被调用，并在第一次发生时切断列表。

例如，当 7 被插入 list1 时，循环将首先将 trailCurrent->link 设置为 7 当 trailCurrent 为 2 时，然后继续并设置 trailCurrent->link 为 7 当 trailCurrent 为 6。但是由于 2 现在指向 7 而不是 6，链丢失了，你只能使用 2 和 7。

再买一本书

您用来学习此内容的书已过时。 C 风格的指针和手动内存分配不应在现代 C++ 中使用。尝试获得一本教授如何使用智能指针和现代集合以及教授正确调试技术的现代书籍，这样您就可以像现在遇到的问题一样轻松地检测到问题。