在双向链表数据结构 class 实验项目中实现 append 和 insertAt 函数

Implementing append and insertAt functions in Doubly Linked List Data Structures class lab project

我已经在这个项目上工作了一个星期,但似乎无法使这个项目获得我需要通过这个实验室的预期输出。下面是本文提到的两个函数的脚手架post:

lab04.cpp(具有前置条件和 post 条件的空白脚手架):


#include <ostream>
#include <cassert>
#include "linkedlistd.h"

namespace DS {

//     Precondition: cursor is not NULL
//     Postcondition: A new node is created with the datum of newdatum.
//      The new node next points to cursor->next
//      The new node prev points to cursor
//      The cursor->next prev points to the new node
//      The cursor next points to the new node
//      Returns a pointer to the new node
linkedList::node* linkedList::appendAt (const value_type& newdatum,node* cursor) {


}

//     Precondition: none
//     Postcondition: A new node is created with the datum of newdatum.
//      The new node next points to cursor
//      The new node prev points to cursor->prev
//      The cursor->prev next points to the new node
//      The cursor prev points to the new node
//      Returns a pointer to the new node
linkedList::node* linkedList::insertAt (const value_type& newdatum,node* cursor) {

}
} // end namespace


以下代码是我的文件版本,其中包含我尝试解决这两个函数的尝试:


#include "linkedlistd.h"

namespace DS {

    //     Precondition: cursor is not NULL
    //     Postcondition: A new node is created with the datum of newdatum.
    //      The new node next points to cursor->next
    //      The new node prev points to cursor
    //      The cursor->next prev points to the new node
    //      The cursor next points to the new node
    //      Returns a pointer to the new node
    linkedList::node* linkedList::appendAt(const value_type& newdatum, node* cursor) {
        node* new_node = new node();
        if (cursor->next() != nullptr) {
            node* next_node = cursor->next();
            new_node->setData(newdatum);
            cursor->setNext(new_node);
            new_node->setPrev(cursor);
            new_node->setNext(next_node);
            next_node->setPrev(new_node);
            return next_node;
        }
        else {
            new_node->setPrev(cursor);
            cursor->setNext(new_node);
            new_node->setNext(nullptr);
            return new_node;
        }
    }

    //     Precondition: none
    //     Postcondition: A new node is created with the datum of newdatum.
    //      The new node next points to cursor
    //      The new node prev points to cursor->prev
    //      The cursor->prev next points to the new node
    //      The cursor prev points to the new node
    //      Returns a pointer to the new node
    linkedList::node* linkedList::insertAt(const value_type& newdatum, node* cursor) {
        node* new_node = new node(newdatum);

        if (cursor == nullptr) {
            tail->setPrev(new_node);
            new_node->setNext(tail);
            new_node->setPrev(tail->prev());
            return new_node;
        }

        if (cursor == head) {
            new_node->setNext(head);
            head->setPrev(new_node);
            head = new_node;
            return new_node;
        }
        new_node->setNext(cursor);
        new_node->setPrev(cursor->prev());
        cursor->prev()->setNext(new_node);
        cursor->setPrev(cursor);
        return new_node;
    }
} // end namespace

但是当我运行项目时,我没有输出。

我应该得到的输出是:


->[5]->[10]->[20]--X

X--[20]<-[10]<-[5]<-

--X

->[30]->[5]->[10]->[20]->[7]->[2]--X

X--[2]<-[7]<-[20]<-[10]<-[5]<-[30]<-

->[1]->[2]->[4]->[8]->[16]->[32]->[16]->[8]->[4]->[2]->[1]--X

X--[1]<-[2]<-[4]<-[8]<-[16]<-[32]<-[16]<-[8]<-[4]<-[2]<-[1]<-

请帮助我完成这个项目,因为我对双向链表的理解和通过这个 class 取决于它。请用这两个函数的正确实现来回复,并解释为什么你编写了你为解决问题所做的事情。实验室的项目文件完整包含在下面。非常感谢您提前帮助我,我期待着阅读您的回复。

linkedlistd.h


#ifndef LINKEDDLIST_H
#define LINKEDDLIST_H
#include <cstdlib>
#include <iostream>
#include "node_dll.h"

namespace DS {

    class linkedList
    {
    public:
        typedef int value_type;
        typedef DSDLL::node<value_type> node;
        linkedList();
        virtual ~linkedList();

        node* appendAt(const value_type&, node*);
        node* insertAt(const value_type&, node* = nullptr);
        void insertItem(value_type);
        void makeList(const value_type[], const size_t& count);
        void deleteList();

        //The following two assessors are for testing purpose and implemented inline
        //Therefore, you do not need to implement in the cpp file
        node* getHead() { return head; };
        node* getTail() { return tail; };

        //The following friend function is implemented in lablinklist.cpp
        friend std::ostream& operator<<(std::ostream&, const linkedList&);
        friend std::ostream& operator>>(std::ostream&, const linkedList&);
    private:
        node* head;
        node* tail;
    };

} //end namespace

#endif /* linkedList_H_ */

node_dll.h


#ifndef NODE_DLL_H_
#define NODE_DLL_H_

namespace DSDLL {

    template <typename T>
    class node
    {
    public:
        typedef T value_type;
        node(value_type d = value_type(), node* n = nullptr, node* p = nullptr) : data_field(d), next_ptr(n), prev_ptr(p) {}

        //Assessor/Getters
        const value_type& getData() const { return data_field; }
        node const* getPrev() const { return prev_ptr; }
        node const* getNext() const { return next_ptr; }

        //Mutators/Setters
        void setData(const value_type& d) { data_field = d; }
        void setPrev(node* new_link) { prev_ptr = new_link; }
        void setNext(node* new_link) { next_ptr = new_link; }

        //Other
        value_type& data() { return data_field; }
        node*& prev() { return prev_ptr; }
        node*& next() { return next_ptr; }

    private:
        value_type data_field;
        node* next_ptr;
        node* prev_ptr;
    };

} /* namespace DSDLL */

#endif /* NODE_DLL_H_ */

lablinklist.cpp


#include <iostream>
#include "linkedlistd.h"

using namespace std;
using namespace DS;


int main() {

    linkedList list1;
    linkedList::node* tn1, * tn2;

    //Test of adding items out of order

    list1.insertItem(5);
    list1.insertItem(20);
    list1.insertItem(10);
    cout << list1 << endl;
    cout >> list1 << endl;

    //Test of deleting entire list
    list1.deleteList();
    cout << list1 << endl;

    //Add items again using insertAt and appendAt
    list1.insertAt(5);
    tn1 = list1.appendAt(10, list1.getHead());
    tn2 = list1.appendAt(7, list1.getTail());
    list1.appendAt(20, tn1);
    list1.insertAt(30, list1.getHead());
    list1.appendAt(2, tn2);
    //Output forwards
    cout << list1 << endl;
    //Output reverse
    cout >> list1 << endl;

    //Now replace list with a new one in a specific order
    int pow2[] = { 1,2,4,8,16,32,16,8,4,2,1 };
    list1.makeList(pow2, sizeof(pow2) / sizeof(int));
    cout << list1 << endl;
    cout >> list1 << endl;

    //Returning a non-zero number, if not 3, then we know it seg-faulted
    return 3;
}

namespace DS {

    /*

    The following is provided so that everybody can easily get the same exact output

    */
    std::ostream& operator<<(std::ostream& os, const linkedList& srcList) {

        //Set a current-pointer to the "head".
        const linkedList::node* cursor = srcList.head;

        //While current-pointer is not NULL
        while (cursor != nullptr)
        {
            //Print the data member ("datum") of the current node
            os << "->[" << cursor->getData() << "]";
            //Set the current-pointer to the "next" node in the list.
            cursor = cursor->getNext();
        }
        //Print out a basic termination symbol
        std::cout << "--X" << std::endl;

        return os;
    }

    std::ostream& operator>>(std::ostream& os, const linkedList& srcList) {

        //Set a current-pointer to the "head".
        const linkedList::node* cursor = srcList.tail;
        if (cursor == nullptr)
            return os;

        //Print out a start symbol
        os << "X--[" << cursor->getData() << "]";
        cursor = cursor->getPrev();

        //While current-pointer is not NULL
        while (cursor != nullptr)
        {
            //Print the data member ("datum") of the current node
            os << "<-[" << cursor->getData() << "]";
            //Set the current-pointer to the "next" node in the list.
            cursor = cursor->getPrev();
        }
        //Print out a basic termination symbol
        std::cout << "<-" << std::endl;

        return os;
    }
}

linkedlistd.cpp


#include <ostream>
#include <cassert>
#include "linkedlistd.h"

namespace DS {

    linkedList::linkedList() {
        head = tail = nullptr;
    }

    linkedList::~linkedList() {
        deleteList();
    }

    void linkedList::insertItem(value_type newdatum) {

        node* ccursor = head;
        node* pcursor = nullptr;

        if (head == NULL) {
            insertAt(newdatum, ccursor);
        }
        else {
            while (ccursor != NULL && newdatum > ccursor->getData()) {
                pcursor = ccursor;
                ccursor = ccursor->next();
            }

            appendAt(newdatum, pcursor);
        }

    }

    void linkedList::makeList(const value_type items[], const size_t& count) {

        deleteList();

        if (count == 0) return;

        insertAt(items[0]);

        node* ccursor = head;

        for (size_t i = 1; i < count; ++i) {
            ccursor = appendAt(items[i], ccursor);
        }

    }

    void linkedList::deleteList() {

        node* dcursor;

        while (head != nullptr) {
            dcursor = head;
            head = head->next();
            delete dcursor;
        }
        head = tail = nullptr;

    }

} //end of DS namespace

我认为您的以下代码语句不正确:

if (cursor == nullptr) {
    tail->setPrev(new_node);
    new_node->setNext(tail);
    new_node->setPrev(tail->prev());
    return new_node;
}

    ...
    new_node->setNext(cursor);
    new_node->setPrev(cursor->prev());
    cursor->prev()->setNext(new_node);
    cursor->setPrev(cursor);
    return new_node;

请参阅下文进行更正。

情况一:当光标为nullptr时,即new_node必须插入到'last'处,因为没有找到匹配的位置中间的某个地方。这假设 'tail' 是你的最后一个元素(应该按照命名约定):

if (cursor == nullptr){
    tail->setNext(new_node);
    new_node->setPrev(tail);
    tail = new_node;
    return new_node;
}

情况2:当光标指向中间某处时。它不是空的。 new_node 添加在 cursor.

之前
...
new_node->setNext(cursor);
new_node->setPrev(cursor->prev());
cursor->prev()->setNext(new_node);
cursor->setPrev(new_node);
return new_node;