c++ - 具有复制构造函数和指针的无限复制列表循环

Question

在尝试将“b”插入列表后，我有一个无限循环。

根据我运行“make test | more”时的输出，它插入“a”就好了，但是当它到达“b”并尝试再次调用复制构造函数时，那就是它进入无限循环

这是我的头文件

#define DLIST_HEADER

#include <string>

struct DListNodeT;

class DListT{
    public:
        DListT();
        DListT(const DListT & src);
        ~DListT();

        DListT & operator = (const DListT & rhs);

        void Home();
        void Left();
        void Right();

        std::string Data() const;
        size_t Size() const;

        void Insert(std::string newData);
        void InsertAfter(std::string newData);
        void Delete();

    private:
        DListNodeT* head;
        DListNodeT* current;
        size_t nodeCount;
};
#endif

这是我的 cpp 文件

#include "DListT.h"

using namespace std;

void DeleteList(DListNodeT * list);
DListNodeT * CopyList(DListNodeT * src);
void AdjustCurrent(DListNodeT * srcList, DListNodeT * destList, DListNodeT * srcCurrent, DListNodeT * & destCurrent);

struct DListNodeT
{
    string data;
    DListNodeT * next{nullptr};
    DListNodeT * prev{nullptr};
};

DListT::DListT()
{
    //DListNodeT * tmp{nullptr};
    //tmp.data = "hi"; 
    
    //tmp = new DListNodeT;
    head = nullptr;
    current = nullptr;
    nodeCount = 0;
}

DListT::DListT(const DListT & src)
{
    cout << "calling copy constructor" << endl;
    
    //this was added after this was graded
    nodeCount = src.nodeCount;
    
    head = CopyList(src.head);
    
    AdjustCurrent(src.head, head, src.current, current);
    
    cout << "exiting copy constructor" << endl;
        
    /*DListNodeT * travel{nullptr};
    DListNodeT * tmp{nullptr};
    DListNodeT * tail{nullptr};
    
    head = nullptr;
    travel = src.head;
    
    while (travel != nullptr)
    {
        tmp = new DListNodeT;
        tmp->data = travel->data;
        tmp->next = nullptr;
        //tmp->prev = nullptr;
        
        if (head == nullptr)
        {
            head = tmp;
        }
        else
        {
            tail->next = tmp;
            //tail->prev = tmp;
        }
        
        tail = tmp;
        travel = travel->next;
        //travel = travel->prev;
    }    
    
    nodeCount = src.nodeCount;*/
}

DListT::~DListT()
{
    DeleteList(head);
}

DListT & DListT::operator = (const DListT & rhs)
{
    if (this != &rhs)
    {
        DeleteList(head);
        head = CopyList(rhs.head);
        nodeCount = rhs.nodeCount;
        AdjustCurrent(rhs.head, head, rhs.current, current);
    }
    
    return *this;    
}

void DeleteList(DListNodeT * list)
{
    DListNodeT * tmp{nullptr};
    DListNodeT * garbage{nullptr};
    
    if (list != nullptr) 
    {
        tmp = list;

        do 
        {
            garbage = tmp;
            tmp = garbage->next;
            delete garbage;
        } while (tmp != list);
    }
}

DListNodeT * CopyList(DListNodeT * src)
{
    DListNodeT * head{nullptr};
    DListNodeT * trace1{nullptr}; 
    DListNodeT * trace2{nullptr};
    DListNodeT * tmp{nullptr};
    
    if (src == nullptr)
    {
        head = nullptr;
    }
    else
    {
        //set up head pointer
        cout << "setting up new head" << endl;
        head = new DListNodeT;
        cout << "set new head" << endl;
        cout << "setting head's data to src's data" << endl;
        head->data = src->data;
        cout << "set head's data to src's data" << endl;
        cout << "setting head's next to head" << endl;
        head->next = head;
        cout << "set head's next to head" << endl;
        cout << "setting head's prev to head" << endl;
        head->prev = head;
        cout << "set head's prev to head" << endl;
                            
        //copy rest of list
        cout << "setting trace1 to src's next" << endl;   
        trace1 = src->next;
        cout << "set trace1 to src's next" << endl;
        cout << "setting trace2 to head" << endl;
        trace2 = head;
        cout << "set trace2 to head" << endl;
        
        while (/*trace1 != head*/ trace1 != src)
        {
            cout << "in copylist while loop" << endl;
            //build new nodes
            cout << "creating a new tmp node" << endl;
            
            tmp = new DListNodeT;
            
            cout << "created the tmp node" << endl;
            cout << "setting tmp's data to trace1's data" << endl;
            
            tmp->data = trace1->data;
            
            cout << "set tmp's data to trace1's data" << endl;
            cout << "setting tmp's next to null" << endl;
            
            tmp->next = nullptr;
            
            cout << "set tmp's next to null" << endl;
            cout << "data is: " << tmp->data << endl;
            
            //link into list
            cout << "setting trace2's next to tmp" << endl;
            
            trace2->next = tmp;
            
            cout << "set trace2's next to tmp" << endl;
            cout << "settings tmp's prev to trace2" << endl;
            
            tmp->prev = trace2;
            
            cout << "set tmp's prev to trace2" << endl;
            cout << "data is: " << tmp->data << endl;
            
            //make it circular
            cout << "setting tmp's next to head" << endl;
            
            tmp->next = head;
            
            cout << "set tmp's next to head" << endl;
            cout << "setting head's prev to tmp" << endl;
            
            head->prev = tmp;
            
            cout << "set head's prev to tmp" << endl;
            cout << "data is: " << tmp->data << endl;
            
            //advance next two pointers
            cout << "setting trace2 to tmp" << endl;
            
            trace2 = tmp;
            
            cout << "set trace2 to tmp" << endl;
            cout << "setting trace1 to trace1's next" << endl;
            
            trace1 = trace1->next;
            
            cout << "set trace1 to trace1's next" << endl;
            cout << "data is: " << tmp->data << endl;
            
            //cout << "nodecount is: " << nodeCount << endl;
        }
    }
    
    return head;
}

void AdjustCurrent(DListNodeT * srcList, DListNodeT * destList, DListNodeT * srcCurrent, DListNodeT * & destCurrent)
{
    DListNodeT * tmp{nullptr};
    
    if (srcCurrent == nullptr)
    {
        destCurrent = nullptr;
    }
    else
    {
        tmp = srcList;
        destCurrent = destList;
        
        while (tmp != nullptr and tmp != srcCurrent)
        {
            tmp = tmp->next;
            destCurrent = destCurrent->next;
        }
    }
}

void DListT::Insert(string newData)
{
    cout << "entering insert function" << endl;
    DListNodeT * tmp{nullptr};
    DListNodeT * tail{nullptr};
    
    tmp = new(DListNodeT);
    tmp->data = newData;
    tmp->next = nullptr;
    tmp->prev = nullptr;
    cout << "inserting an element into list" << endl;
    nodeCount++;
    
    // ASSUME
    // INVARIANT: (head == nullptr) == (current == nullptr)
    //         if head is null, current is null.
    //         if head is NOT null, current is NOT null

    if (head == nullptr)
    {
        cout << "entering if statement for empty list" << endl;
        // we have an empty list, there are no nodes.
        // the node we just created becomes the head/tail/current
        tmp->next = tmp;
        tmp->prev = tmp;
        current = tmp;
        head = tmp;
        cout << "exiting if statment for empty list" << endl;
    }
    else if (current == head)
    {
        cout << "enterting if state where current is equal to the head of the list" << endl;
        // this is a special case: when current points to the head, 
        // we will insert the new node _before_ the current one (head of the list)
        tmp->next = head;
        tmp->prev = head->prev;
        head->prev = tmp;
        current = tmp;
        head = tmp;
        cout << "exiting if statement where current is equal to the head of the list" << endl;
    }
    else
    {
        cout << "entering else statment from insert function" << endl;
        // we have a non-empty list and we want to append to the end
        // so we insert the new node at the current node
        tail = current->prev;
        tmp->prev = tail;
        tmp->next = current;
        tail->next = tmp;
        current->prev = tmp;
        current = tmp;
        cout << "exiting else statement from insert function" << endl;
    }
    
    cout << "exiting insert function" << endl;
}

void DListT::Delete()
{
    DListNodeT * tmp{nullptr};
    DListNodeT * next{nullptr};
    DListNodeT * prior{nullptr};
    
    if (current == nullptr)
    {
        cout << "Error: Attempt to delete in an Empty List.";
    }
    else if (nodeCount == 1)
    {
//USELESS        current = tmp;
        current = nullptr;
        head = nullptr;
        delete tmp;
    }
    else
    {
        // the node we're about to delete is also the head...
        // reposition the head to the node after; otherwise it would
        // point to the node we just deleted.
        if (current == head) {
            head = current->next;
        }
        // unlink the current node
        prior = current->prev;
        next = current->next;
        prior->next = next;
        next->prev = prior;
        tmp = current;
        current = prior;
        delete tmp;    
    } 
}

size_t DListT::Size() const
{
    return nodeCount;
}

void DListT::Home()
{
    if (head != nullptr)
    {
        current = head;
    }
}

void DListT::Right()
{
    if (current != nullptr)
    {
        current = current->next; 
    }
}

void DListT::Left()
{
    if (current != nullptr)
    {
        current = current->prev; 
    }
}

void DListT::InsertAfter(string newData)
{
    DListNodeT * tmp{nullptr};
    DListNodeT * seek{nullptr};
    
    tmp = new(DListNodeT);
    tmp->data = newData;
    tmp->next = nullptr;
    tmp->prev = nullptr;
    nodeCount++;
    
    if (head == nullptr)
    {
        tmp->next = tmp;
        tmp->prev = tmp;
        current = tmp;
        head = tmp; 
    }
    else
    {

        // node after current; will now be after tmp
        seek = current->next;
        tmp->next = seek;
        tmp->prev = current;
        current->next = tmp;
        seek->prev = tmp;

        current = tmp;    
    } 
}

string DListT::Data() const
{
    string data;
    
    if (current != nullptr)
    {
        data = current->data;
    }
    else
    {
        cout << "Error: Attempt to access Empty List.";
        data = "NO DATA";
    }
    
    return data;
}

这是我教授的测试代码

#include<boost/test/included/unit_test.hpp>
#include<boost/test/unit_test.hpp>
#include <boost/test/output_test_stream.hpp>
#include <vector>

#include "DListT.h"

using namespace std;
using boost::test_tools::output_test_stream;


void Header(string s) {
   cout << endl;
   cout << "******* Running " << s << " *******" << endl;
}

void Footer(string s) {
   cout << "******* Finished with " << s << " *******" << endl;
   cout << endl;
}

BOOST_AUTO_TEST_SUITE( DListTTest )

BOOST_AUTO_TEST_CASE(constructor_test) {
    DListT list;

    Header("Constructor Test");

    BOOST_CHECK_MESSAGE(list.Size() == 0, "Constructor Test, Size not 0");

    Footer ("Constructor Test");
}

void Compare(DListT list, vector<string> check) {
    size_t i;

    cout << "in compare" << endl;
    if (list.Size() != check.size()) {
        BOOST_FAIL("Sizes not the same in Compare");
    } else {
        for(i = 0; i < check.size(); i++) {
             BOOST_CHECK(list.Data() == check[i]);
             list.Right();
        }
    }

    cout << "exiting compare" << endl;
    return;
    
}

void CompareHome(DListT list, vector<string> check) {
    // we don't know that current is pointing to the right thing.
    list.Home();
    cout << "entering comparehome" << endl;
    Compare(list, check);
    cout << "exiting comparehome" << endl;
}

// not really checking current directly.
// since both are at the "same" value of current, they should be the same.
// this will not work if the pattern repeats and the current pointer is at
// a offset
//

void CompareLists(DListT & a, DListT & b) {
    size_t i;

    if (a.Size() != b.Size()) {
        BOOST_FAIL("Sizes not the same in CompareLists");
    } else { 
        for(i = 0; i < a.Size(); i++) {
             BOOST_CHECK(a.Data() == b.Data());
             a.Right();
             b.Right();
        }
        BOOST_CHECK(a.Data() == b.Data());
    }
}

BOOST_AUTO_TEST_CASE(insert_test) {
    DListT list;
    vector<string> check;

    Header("Insert Test");

    CompareHome(list, check);

    //   head->A
    list.Insert("A");
    cout << "inserting a" << endl;
    check = {"A"};
    CompareHome(list, check);

    // head->B<->A
    list.Insert("B");
    cout << "inserting b" << endl;
    
    for (size_t i = 0; i <= list.Size(); i++)
    {
        cout << "list has: " << list.Data() << endl;
        cout << "i is: " << i << endl;
        list.Right();
        
    }
    
    list.Home();
    check = {"B","A"};
    CompareHome(list, check);

    // head->B<->C<->A
    list.Home();
    list.Right();
    list.Insert("C");
    check = {"B","C","A"};
    CompareHome(list, check);

    // head->D<->B<->C<->A
    list.Home();
    list.Insert("D");
    check = {"D","B","C","A"};
    CompareHome(list, check);

    // head->D<->B<->C<->E<->A
    list.Home();
    list.Left();
    list.Insert("E");
    check = {"D","B","C","E","A"};
    CompareHome(list, check);

    // head->D<->B<->C<->E<->A
    list.Home();
    list.Left();
    list.Left();
    list.Left();
    list.Insert("F");
    check = {"D","B","F","C","E","A"};
    CompareHome(list, check);

    Footer("Insert Test");
}

BOOST_AUTO_TEST_CASE(copy_test) {
    DListT list1, list2;

    Header("Copy-Copy Constructor Test");

    // check empty lists
    // the first case should have an output error for now.  Just supress it 
    output_test_stream output; 
    streambuf * old = cout.rdbuf(output.rdbuf());
    CompareLists(list1, list2);
    cout.rdbuf(old);  

    // check list with single element
    list1.Insert("A");
    list2 = list1;
    CompareLists(list1, list2);

    DListT list3(list1);
    CompareLists(list1, list3);


    // check lists with two elements
    list1.Insert("B");
    list2 = list1;
    CompareLists(list1, list2);

    DListT list4(list1);
    CompareLists(list1, list4);

    // let's try a handful of elements.
    list1.Insert("C");
    list1.Insert("D");
    list1.Insert("E");
    list2 = list1;
    CompareLists(list1, list2);

    DListT list5(list1);
    CompareLists(list1, list5);

    // did we get the current pointer right?
    list1.Right();
    list1.Right();
    list1.Right();
    list2 = list1;
    CompareLists(list1, list2);

    DListT list6(list1);
    CompareLists(list1, list6);

    Footer("Copy-Copy Constructor Test");
}

BOOST_AUTO_TEST_CASE(empty_data_access_test) {
    DListT list;

    Header("Empty Data Access Test");

    // set up a stream buffer to capture the output
    output_test_stream output; 

    // cause output to occur.
    streambuf * old = cout.rdbuf(output.rdbuf());

    string x = list.Data();

    // restore the stdout buffer
    cout.rdbuf(old);  

    BOOST_CHECK( !output.is_empty( false ) );
    BOOST_CHECK( output.is_equal( "Error: Attempt to access Empty List.\n" ) );
    BOOST_CHECK( x == "NO DATA");

    Footer("Empty Data Access Test");
}

BOOST_AUTO_TEST_CASE(left_right_home_test) {
    Header("Movement Test");

    DListT list, listCopy;

    vector<string> check;

    list.Insert("D");
    list.Insert("C");
    list.Insert("B");
    list.Insert("A");

    list.Home();
    check = {"A","B","C","D"};
    listCopy = list;
    Compare(listCopy,check);

    list.Right();
    check = {"B","C","D","A"};
    listCopy = list;
    Compare(listCopy,check);

    list.Right();
    check = {"C","D","A","B"};
    listCopy = list;
    Compare(listCopy,check);

    list.Right();
    check = {"D","A","B","C"};
    listCopy = list;
    Compare(listCopy,check);

    list.Right();
    check = {"A","B","C","D"};
    listCopy = list;
    Compare(listCopy,check);

    list.Home();
    list.Left();
    check = {"D", "A","B","C"};
    Compare(list,check);

    list.Left();
    check = {"C", "D", "A","B"};
    Compare(list,check);

    list.Left();
    check = {"B", "C", "D", "A"};
    Compare(list,check);

    list.Left();
    check = {"A", "B", "C", "D"};
    Compare(list,check);

    Footer("Movement Test");
}

BOOST_AUTO_TEST_CASE(delete_test) {
    Header("Delete Test");

    DListT list;
    vector<string> check;

    list.Insert("G");
    list.Insert("F");
    list.Insert("E");
    list.Insert("D");
    list.Insert("C");
    list.Insert("B");
    list.Insert("A");

    check = {"A","B","C","D","E","F","G"};

    CompareHome(list,check);

    // delete the head of the list
    list.Home();
    list.Delete();

    // delete the last item in the list;
    list.Home();
    list.Left();
    list.Delete();
    check = {"B","C","D","E","F"};
    CompareHome(list,check);

    // delete the second to last item
    list.Home();
    list.Left();
    list.Left();
    list.Delete();
    check = {"B","C","D","F"};
    CompareHome(list,check);

    // delete the second item
    list.Home();
    list.Right();
    list.Delete();
    check = {"B","D","F"};
    CompareHome(list,check);

    list.Home();
    list.Delete();
    check = {"D","F"};
    CompareHome(list,check);

    list.Home();
    list.Delete();
    check = {"F"};
    CompareHome(list,check);

    list.Delete();
    check = {};
    CompareHome(list,check);

    Footer("Delete Test");
}

BOOST_AUTO_TEST_SUITE_END()

这是我的makefile

CXXFLAGS =  -g -O3 -Wpedantic -Wall -Wextra -Wmisleading-indentation -Wunused -Wuninitialized -Wshadow -Wconversion -Werror -std=c++17

OBJS = DListTTest 

all: ${OBJS}

test: DListTTest
    ./DListTTest

memcheck: DListTTest
    valgrind --leak-check=summary ./DListTTest
        
DListTTest: DListT.o

clean:
    rm -f ${OBJS} *.o 

标签： c++pointersinfinite-loop