Обратный список двойных ссылок в C ++

Question

Я пытался выяснить, как изменить порядок двусвязного списка, но по какой-то причине в моей функции void reverse() выполняется цикл while один раз, а затем по какой-то причине происходит сбой. Чтобы ответить на некоторые вопросы впереди, я самоучка с помощью моих братьев. Это не весь код, но у меня есть функция display(), которая печатает все узлы в хронологическом порядке из start_ptr и переключатель, который активирует определенные функции, такие как

    case 1 : add_end(); break;
    case 2 : add_begin(); break;
    case 3 : add_index(); break;
    case 4 : del_end(); break;
    case 5 : del_begin(); break;
    case 6 : reverse(); break;

Это основа моего кода:

#include <iostream>
using namespace std;

struct node
{
    char name[20];
    char profession[20];
    int age;
    node *nxt;
    node *prv;
};

node *start_ptr = NULL;

void pswap (node *pa, node *pb)
{
    node temp = *pa;
    *pa = *pb;
    *pb = temp;
    return;
}

void reverse()
{
    if(start_ptr==NULL)
    {
        cout << "Can't do anything" << endl;
    }
    else if(start_ptr->nxt==NULL)
    {
        return;
    }
    else
    {
        node *current = start_ptr;
        node *nextone = start_ptr;
        nextone=nextone->nxt->nxt;
        current=current->nxt;
        start_ptr->prv=start_ptr->nxt;
        start_ptr->nxt=NULL;
        //nextone=nextone->nxt;
        while(nextone->nxt!= NULL)
        {
            pswap(current->nxt, current->prv);
            current=nextone;
            nextone=nextone->nxt;
        }
        start_ptr=nextone;
    }
}

Answer 1

Попробуйте это:

node *ptr = start_ptr;
while (ptr != NULL) {
    node *tmp = ptr->nxt;
    ptr->nxt = ptr->prv;
    ptr->prv = tmp;
    if (tmp == NULL) {
        end_ptr = start_ptr;
        start_ptr = ptr;
    }
    ptr = tmp;
}

Answer 2

РЕДАКТИРОВАТЬ: Моя первая реализация, которая была правильной, но не идеальной. Ваша реализация довольно сложна. Можете ли вы попробовать это вместо:

node * reverse(Node * start_ptr)
{
    Node *curr = start_ptr; 
    Node * prev = null;
    Node * next = null;
    while(curr)
    {
        next = curr->nxt;
        curr->nxt = prev;
    curr->prv = next;
        prev = curr;
        curr = next;
    }
    return start_ptr=prev;
}

Вот мое обновленное решение:

node * reverse()
{
    node *curr = start_ptr; 
    node * prev = NULL;
    node * next = NULL;
    while(curr)
    {
        next = curr->nxt;
        curr->nxt = prev;
        curr->prv = next;
        prev = curr;
        curr = next;
    }
    return start_ptr=prev;
}

Логика была правильной. Но проблема была в том, что я принимал входной аргумент start_ptr. Что означает, что я возвращал местную копию этого. Теперь это должно работать.

Answer 3

Вы можете немного упростить ваш reverse().Я бы сделал что-то вроде этого:

void reverse()
{
    if(start_ptr == NULL)
    {
        cout << "Can't do anything" << endl;
    }
    else
    {
        node *curr = start_ptr;
        while(curr != NULL)
        {
            Node *next = curr->next;
            curr->next = curr->prev;
            curr->prev = next;
            curr = next;
        }
        start_ptr = prev;       
    }
}

Объяснение: Основная идея - просто посетить каждый Node и поменять местами ссылки на previous и next.Когда мы перемещаем curr к следующему Node, нам нужно сохранить следующий узел, чтобы у нас все еще был указатель на него, когда мы устанавливаем curr.next в prev.

Answer 4

Простое решение.переворачивает менее половины общего количества итераций по списку

template<typename E> void DLinkedList<E>::reverse() {
    int median = 0;
    int listSize = size();
    int counter = 0;

    if (listSize == 1)
    return;

    DNode<E>* tempNode = new DNode<E>();

    /**
     * A temporary node for swapping a node and its reflection node
     */
    DNode<E>* dummyNode = new DNode<E>();

    DNode<E>* headCursor = head;
    DNode<E>* tailCursor = tail;

    for (int i = 0; i < listSize / 2; i++) {
        cout << i << "\t";

        headCursor = headCursor->next;
        tailCursor = tailCursor->prev;

        DNode<E>* curNode = headCursor;
        DNode<E>* reflectionNode = tailCursor;

        if (listSize % 2 == 0 && listSize / 2 - 1 == i) {
            /**
             * insert a dummy node for reflection
         * for even sized lists
         */
        curNode->next = dummyNode;
        dummyNode->prev = curNode;

        reflectionNode->prev = dummyNode;
        dummyNode->next = reflectionNode;

    }
    /**
     * swap the connections from previous and 
             * next nodes for current and reflection nodes
     */

    curNode->prev->next = curNode->next->prev = reflectionNode;

    reflectionNode->prev->next = reflectionNode->next->prev = curNode;

    /**
     * swapping of the nodes
     */

    tempNode->prev = curNode->prev;
    tempNode->next = curNode->next;

    curNode->next = reflectionNode->next;
    curNode->prev = reflectionNode->prev;

    reflectionNode->prev = tempNode->prev;
    reflectionNode->next = tempNode->next;

    if (listSize % 2 == 0 && listSize / 2 - 1 == i) {
        /**
         * remove a dummy node for reflection
         * for even sized lists
         */
        reflectionNode->next = curNode;
        curNode->prev = reflectionNode;
    }

    /**
     * Reassign the cursors to position over the recently swapped nodes
     */
        tailCursor = curNode;
        headCursor = reflectionNode;

    }

    delete tempNode, dummyNode;
}

template<typename E> int DLinkedList<E>::size() {
    int count = 0;
    DNode<E>* iterator = head;

    while (iterator->next != tail) {
        count++;
        iterator = iterator->next;
    }
    return count;
}

Answer 5

Мой код для реверсирования двусвязного списка,

Node* Reverse(Node* head)
{
// Complete this function
// Do not write the main method. 


if(head != NULL) {

    Node* curr = head;
    Node* lastsetNode = curr;
    while(curr != NULL) {

        Node* frwdNode = curr->next;
        Node* prevNode = curr->prev;


        if(curr==head) {                
            curr->next = NULL;
            curr->prev = frwdNode;
            lastsetNode = curr;
        }
        else {
            curr->next = lastsetNode;
            curr->prev = frwdNode;
            lastsetNode = curr;
        }



        curr = frwdNode;
    }

    head = lastsetNode;
}


return head;
}

Answer 6

Очень простое и O (n) решение с использованием двух указателей:

старт = голова вдвойне LL

struct node *temp, *s;
s = start;

while(s != NULL){
  temp = s->prev;
  s->prev = s->next;
  s->next = temp;
  s = s->prev;
}

//if list has more than one node
if(current != NULL){
  start = temp->prev;
}

Answer 7

Посмотрите на

valuesnextone=nextone->nxt->nxt;

Здесь nextone->nxt может быть нулевым.

Кроме того, попробуйте использовать указатели на указатели в функции подкачки.

Answer 8

Я предлагаю сохранить ссылку на последний узел.
Если нет, найдите последний узел. Перейдите по списку, используя «предыдущие» ссылки (или в вашем случае prv).

Нет необходимости менять ссылки. Обход с использованием указателя prv автоматически посещает узлы в обратном порядке.

Answer 9

Ваша функция pswap неверна Вы должны поменять указатель, не пытайтесь создавать временные объекты и менять их местами Должно быть так (позже может быть другая ошибка)

void pswap (node *&pa, node *&pb)
{
    node* temp = pa;
    pa = pb;
    pb = temp;
    return;
}