Реализация функций append и insertAt в лабораторном проекте класса структур данных с двойной связью.

Question

Я работаю над этим проектом уже неделю, но не могу заставить этот проект получить ожидаемый результат, который мне нужен для прохождения этой лабораторной работы. Ниже приведен каркас для двух функций, упомянутых в этом сообщении:

lab04. cpp (пустые леса с условиями до и после):

#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]<-

Пожалуйста, помогите мне завершить sh этот проект, так как от этого зависит мое понимание двухсвязных списков и прохождения этого класса. Пожалуйста, ответьте с правильной реализацией для этих двух функций с объяснением, почему вы закодировали, что вы сделали для решения проблемы. Файлы проекта для лаборатории приведены ниже. Большое спасибо за помощь мне заранее, и я с нетерпением жду ваших ответов.

connectedlistd.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;
    }
}

connectedlistd. 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

Answer 1

Я думаю, что ваши следующие кодовые выражения неверны:

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;

См. Ниже исправления.

Случай 1: Когда курсор равен nullptr, то есть new_node должен быть вставлен в 'last', так как где-то посередине не найдено подходящего местоположения. Предполагается, что 'tail' - это ваш последний элемент (который должен соответствовать соглашению об именах):

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

Случай 2: Когда курсор указывает где-то посередине. Это не NULL. new_node добавляется непосредственно перед cursor.

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