Как создать функцию insertAfter для двусвязного списка c ++ - PullRequest
Новая
       29

Как создать функцию insertAfter для двусвязного списка c ++

0 голосов
/ 10 февраля 2019

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

Ниже приведен файл заголовка и то, что я пробовал, но он не компилируется. 

#include <iostream>
#include <string>

class DoublyLinkedList {
public:
    DoublyLinkedList();
    ~DoublyLinkedList();
    void append (const string& s);
    void insertBefore (const string& s);
    void insertAfter (const string& s);
    void remove (const string& s);
    bool empty();
    void begin();
    void end();
    bool next();
    bool prev();
    bool find(const string& s);
    const std::string& getData() const;
private:
    class Node
    {
    public:
        Node();
        Node(const string& data);
        ~Node();
        Node* next;
        Node* prev;
        string* data;
    };
    Node* head;
    Node* tail;
    Node* current;
};

void DoublyLinkedList::insertAfter(const string& s)
{
    // Node *temp, *var;
    //var=(Node *)malloc(sizeof(Node));
    if(head == NULL)
    {
        append(s);
    }
    temp->data=current;
}

void DoublyLinkedList::append(const string& s)
{
    //create a new Node
    current = new Node(s);
    if (this->empty())//check if it is empty or not
    {
        this->head = this->tail = current;
    }else{
        //append to tail
        current->prev = tail;
        tail->next = current;
        tail = current;
    }
}

#endif

1 Ответ

0 голосов
/ 10 февраля 2019

-Создать новый узел и сохранить переданные данные. Установить текущий указатель на заголовок. 

Node * newNode = new Node(s);
current=head;

-Вы должны пройти через LinkedList, используя цикл, который проверяет значения каждого узла, используя 2указатели, один из которых следует за тем, который проверяет значения узла. 

while(current->data != insertAfter- 
>data)
{
current=current->next;}

-Как только правильный узел найден с током, цикл должен остановиться.Установите следующий указатель нового узла на следующий указатель insertAfter и указатель prev на узел insertAfter.

newNode->next = insertAfterNode->next;
newNode->prev = insertAfterNode;

-Вы затем установите следующий указатель тока на узел, который хотите вставить. 

current->next = newNode;

Кроме того, обязательно добавьте каждый потенциальный случай.Если это хвост, который был вставлен после, убедитесь, что указатель хвоста установлен в newNode и такой же, если он вставлен в заголовок.После обхода цикла поместите: 

if(tail->data==current->data)
{
    tail = newNode;
}

if(head->data==current->data)
{
    head=newNode;
}

Edit: поскольку это дважды LinkedList, вместо trailCurrent может быть реализован указатель prev, который вообще не нужен.

...