指针在链表深拷贝构造函数中永远不会到达 null

Question

我目前正在构建一个名为 Sequence 的链表 class。有四个私有节点 - headPtr、tailPtr、cursor（当前节点）和 precursor（前一个节点）。

当光标是列表中的最后一项时，我的复制构造函数工作正常，但是当光标出于某种原因位于中间时，该函数永远不会退出 while 循环。

复制构造函数如下：

Sequence::Sequence(const Sequence& copyMe) {
        copy(copyMe);
    }

void Sequence::copy(const Sequence& copyMe) {

        numitems = 0;

        if (copyMe.headPtr == nullptr) {
            cursor = precursor = headPtr = tailPtr = nullptr;
        }
        else {

            // allocate a new node for the new sequence
            node* newPtr = new node;
            newPtr -> data = copyMe.headPtr -> data;
            numitems++;

            // start the new sequence with this node
            headPtr = newPtr;
            precursor = nullptr;
            cursor = headPtr;
            tailPtr = headPtr;

            // create a node to traverse the origin sequence
            node* originPtr = copyMe.headPtr -> next;

            while (originPtr != nullptr) {

                // add node to the new list, make it the current, & assign data
                newPtr->next = new node;
                newPtr = newPtr->next;
                newPtr->data = originPtr->data;
                numitems++;

                // Correct cursor and precursor positions
                if(originPtr == copyMe.cursor) {
                    this->cursor = newPtr;
                }
                else if (originPtr == copyMe.precursor) {
                    this->precursor = newPtr;
                }
                originPtr = originPtr->next;

                // if the thing being copied is the last thing, make it tailptr    
                if (originPtr == nullptr) {

                    tailPtr = newPtr->next;
                    cout << "tail assigned" << endl;

                    newPtr->next = nullptr;
                    originPtr = nullptr;
                }         
            }     
        }
    }

这里是 driver 程序：


    const size_t TESTSIZE = 30;
    Sequence original; // A Sequence that we'll copy.
    double items[2 * TESTSIZE];
    size_t i;

    // Set up the items array to conatin 1...2*TESTSIZE.
    for (i = 1; i <= 2 * TESTSIZE; i++)
        items[i - 1] = i;

    // This section works fine //
    // Test copying of an empty Sequence. After the copying, we change original.
    cout << "Copy constructor test: for an empty Sequence." << endl;
    Sequence copy1(original);
    original.attach(1); // Changes the original Sequence, but not the copy.

    // Test copying of a Sequence with current item at the tail.
    cout << "Copy constructor test: for a Sequence with cursor at tail." << endl;
    for (i = 2; i <= 2 * TESTSIZE; i++) {
        original.attach(i);
    }
    Sequence copy2(original);
    original.remove_current(); 
    original.start();
    original.advance();
    original.remove_current(); // Delete 2 from original, but not the copy.

    // This section gets stuck in the while loop of my copy constructor //
    // Test copying of a Sequence with cursor near the middle.
    cout << "Copy constructor test: with cursor near middle." << endl;
    original.insert(2);
    for (i = 1; i < TESTSIZE; i++)
        original.advance();
    // Cursor is now at location [TESTSIZE] (counting [0] as the first spot).
    Sequence copy3(original);

我很困惑为什么光标的位置会影响 originPtr 的前进，以及为什么 originPtr 不会变为 null 并分配尾巴。我尝试输出它指向的内容，但它似乎只是以循环方式不断地在内存插槽中前进。一旦达到 60，它会立即返回到从 2 添加而不是终止。

感谢您的帮助！

编辑：这是在添加一些 cout 语句后最后使用游标时输出的样子：

Copy constructor test: for a Sequence with cursor at tail.
Copy constructor test: for a Sequence with cursor at tail.
newPtr is: 0x7fa6dcd00140 and originPtr is: 0x7fa6dcd00000
newPtr is: 0x7fa6dce00010 and originPtr is: 0x7fa6dcd00020
newPtr is: 0x7fa6dce00020 and originPtr is: 0x7fa6dcd00030
newPtr is: 0x7fa6dce00030 and originPtr is: 0x7fa6dcd00040
newPtr is: 0x7fa6dce00040 and originPtr is: 0x7fa6dcd00050
newPtr is: 0x7fa6dce00050 and originPtr is: 0x7fa6dcd00060
newPtr is: 0x7fa6dce00060 and originPtr is: 0x7fa6dcd00070
newPtr is: 0x7fa6dce00070 and originPtr is: 0x7fa6dcd00080
newPtr is: 0x7fa6dce00080 and originPtr is: 0x7fa6dcd00090
newPtr is: 0x7fa6dce00090 and originPtr is: 0x7fa6dcd000a0
newPtr is: 0x7fa6dce000a0 and originPtr is: 0x7fa6dcd000b0
newPtr is: 0x7fa6dce000b0 and originPtr is: 0x7fa6dcd000c0
newPtr is: 0x7fa6dce000c0 and originPtr is: 0x7fa6dcd000d0
newPtr is: 0x7fa6dce000d0 and originPtr is: 0x7fa6dcd000e0
newPtr is: 0x7fa6dce000e0 and originPtr is: 0x7fa6dcd000f0
newPtr is: 0x7fa6dce000f0 and originPtr is: 0x7fa6dcd00100
newPtr is: 0x7fa6dce00100 and originPtr is: 0x7fa6dcd00110
newPtr is: 0x7fa6dce00110 and originPtr is: 0x7fa6dcd00120
NULL REACHED
tail assigned

与光标在中间的下一个测试

newPtr is: 0x7fa6dcf00030 and originPtr is: 0x7fa6dcd00000
newPtr is: 0x7fa6dcf00040 and originPtr is: 0x7fa6dcd00020
newPtr is: 0x7fa6dcf00050 and originPtr is: 0x7fa6dcd00030
newPtr is: 0x7fa6dcf00060 and originPtr is: 0x7fa6dcd00040
newPtr is: 0x7fa6dcf00070 and originPtr is: 0x7fa6dcd00050
newPtr is: 0x7fa6dcf00080 and originPtr is: 0x7fa6dcd00060
newPtr is: 0x7fa6dcf00090 and originPtr is: 0x7fa6dcd00070
newPtr is: 0x7fa6dcd00010 and originPtr is: 0x7fa6dcd00080
newPtr is: 0x7fa6dcd00120 and originPtr is: 0x7fa6dcd00090
newPtr is: 0x7fa6dcd00150 and originPtr is: 0x7fa6dcd000a0
newPtr is: 0x7fa6dcd00160 and originPtr is: 0x7fa6dcd000b0
newPtr is: 0x7fa6dcd00170 and originPtr is: 0x7fa6dcd000c0
newPtr is: 0x7fa6dcd00180 and originPtr is: 0x7fa6dcd000d0
newPtr is: 0x7fa6dcd00190 and originPtr is: 0x7fa6dcd000e0
newPtr is: 0x7fa6dce00120 and originPtr is: 0x7fa6dcd000f0
newPtr is: 0x7fa6dce00130 and originPtr is: 0x7fa6dcd00100
newPtr is: 0x7fa6dce00140 and originPtr is: 0x7fa6dcd00110
newPtr is: 0x7fa6dce00150 and originPtr is: 0x7fa6dcd00120
newPtr is: 0x7fa6dce00160 and originPtr is: 0x7fa6dcd00150
newPtr is: 0x7fa6dce00170 and originPtr is: 0x7fa6dcd00160
newPtr is: 0x7fa6dce00180 and originPtr is: 0x7fa6dcd00170
newPtr is: 0x7fa6dce00190 and originPtr is: 0x7fa6dcd00180
newPtr is: 0x7fa6dce001a0 and originPtr is: 0x7fa6dcd00190
newPtr is: 0x7fa6dce001b0 and originPtr is: 0x7fa6dce00120
newPtr is: 0x7fa6dce001c0 and originPtr is: 0x7fa6dce00130
newPtr is: 0x7fa6dce001d0 and originPtr is: 0x7fa6dce00140
newPtr is: 0x7fa6dce001e0 and originPtr is: 0x7fa6dce00150
newPtr is: 0x7fa6dce001f0 and originPtr is: 0x7fa6dce00160
newPtr is: 0x7fa6dce00200 and originPtr is: 0x7fa6dce00170
newPtr is: 0x7fa6dce00210 and originPtr is: 0x7fa6dce00180
newPtr is: 0x7fa6dce00220 and originPtr is: 0x7fa6dce00190
newPtr is: 0x7fa6dce00230 and originPtr is: 0x7fa6dce001a0
// and so on forever because its stuck in a loop and endlessly advancing somehow

Answer 1

复制构造函数的正确语法是：

Sequence::Sequence(const Sequence& copyMe) {...}

您写了：

void Sequence::copy(const Sequence& copyMe) {...}

这意味着你定义了一个成员函数而不是构造函数。所以你的构造函数永远不会被调用。当您创建 copy1、copy2 和 copy3 时，将使用默认构造函数。

更新

if (originPtr == nullptr) {

  tailPtr = newPtr->next; // newPtr->next is not initialized here
                          // consider tailPtr = newPtr instead
  cout << "tail assigned" << endl;

  newPtr->next = nullptr; // good
  originPtr = nullptr;    // originPtr is nullptr here because of if condition
}

更新2

我无法检查您移动光标当前位置和先前位置的实现，但请注意，在您的复制构造函数中，您假定当前指针和先前指针始终不同。

else if (originPtr == copyMe.precursor) { // consider removing 'else' here

更新3

Sequence copy2(original);
original.remove_current(); // here you remove the last element

看起来问题出在 remove_current()。构造函数中的循环不依赖于光标位置。但这取决于原始序列的 node->next 值。所以创建副本的错误不会导致死循环。无限循环的唯一原因是原始序列格式错误。我怀疑您在从序列中删除最后一个元素后忘记更新最后一个节点的 next 值。在您发布 remove_current().

的代码之前，我无法证明我的话

更新4

void Sequence::remove_current() {
        if (is_item()) {

            node* temp;
            temp = cursor;

            if (cursor == headPtr && cursor == tailPtr) {
                cursor = nullptr;
                precursor = nullptr;
                headPtr = nullptr;
                tailPtr = nullptr;
            }
            else if (cursor == headPtr) {
                headPtr = cursor->next;
                cursor = headPtr;
                precursor = nullptr;
            }
            else {
                if (cursor == tailPtr) {
                    precursor->next = nullptr;
                    tailPtr = precursor;
                    cursor = precursor;
                    if (precursor == headPtr) {
                        precursor = nullptr;
                    }
                    else {
                        for(precursor = headPtr; precursor->next->next; precursor = precursor->next);
                    }
                }
                else {      
                    precursor->next = cursor->next;
                    cursor = cursor->next;

                }    
            }
            delete temp;
            numitems--;
        }
    }

指针在链表深拷贝构造函数中永远不会到达 null

Pointer never reaches null in linked list deep copy constructor

c++

pointers

linked-list

copy-constructor