切换链表中的两个节点

Question

我对编程相当陌生，我有这个任务，目标是打印出0123456789然后使用这些函数9876543210

bool List::SortSwap()
{
    bool doswap = true;
    ListElement *i =this-> head;
    ListElement *prev =this-> head;
    ListElement *b = i->next;
    while (doswap= true) {
        for (i; i != NULL; i = i->next) {
            if (i != this-> head) {
                prev->next = i;
            }
            if (i->value < b->value) {
                swap(prev, i, b);
                doswap = true;
            }
        }
        doswap= false;
    }
    return doswap;
} 

void List::swap(ListElement * prev, ListElement * a, ListElement * b)
{
    prev->next = b;
    b->next = a;
}

因此，如果

doswap 为真，它应该通过我的链表并交换元素，如果它的值小于后面的值，当我运行程序时没有任何反应，我的列表不会打印到屏幕上

Answer 1

如果b是a的继承者并且a prev的继承者，那么你必须将b作为prev的继承者，a作为b的继承者，交换a和b：

void List::swap( ListElement * prev, ListElement * a, ListElement * b)
{
    a->next = b->next; // put successor of b in place of succesor of a
    b->next = a;       // put a in place of successor of b
    prev->next = b;    // put b in place of succesor of prev
}

要按顺序交换列表的元素，您必须处理列表的前两个元素。所以列表的其余部分一步一步。如果到达最后一个列表元素的前置项，则终止。

bool List::SortSwap()
{
    if ( head == nullptr || head->next == nullptr )
        return false;
    bool anySwapped = false;
    // hadle head of list and its successor
    if ( head->value < head->next->value )
    {
        ListElement *temp = head;
        head = head->next;       // successor of head becomes new head
        temp->next = head->next; // successor of old head becomes successor of new head
        head->next = temp;       // new head becomes succesor of old head
        anySwapped = true;
    }
    // continue until predecessor of tail is found
    ListElement *prev = head;
    while ( prev->next != nullptr && prev->next->next != nullptr )
    {
        ListElement *a = prev->next;
        ListElement *b = a->next;
        if ( a->value < b->value )
        {
            swap( prev, a, b );
            anySwapped = true;
        }
        prev = prev->next; // step one forward
    }
    return anySwapped;
}

请注意，(doswap= true)是一项分配。循环while (doswap= true)是无限的。

Answer 2

假设这是节点当前排列的方式，在交换之前：

prev --> a --> b

此外，假设这是交换后节点应该的样子：

prev --> b --> a

如果以上是交换应该更改的内容，则代码在您的交换函数中需要保存节点"B"作为其下一个节点指针：

void List::swap(ListElement * prev, ListElement * a, ListElement * b)
{
     ListElement * temp = b->next;
     prev->next = b;
     b->next = a;
     a->next = temp;
}

Answer 3

所以你要做的是反转列表我做过这样的事情。

void LinkList::ReverseList()
{
    int Length=0;
    current=Head;
    while (current!=NULL)
    {
        current=current->link;
        Length++;
    }
    cout<<"Length is:"<<Length<<endl;
    Prev=current=Head;
    Temp=Head;
    Temp=Temp->link;
    for (int i= 0; i<Length-1; i++)
    {
        if (i==0)
        {
            Prev=Temp;
            current->link=NULL;
            Temp=Temp->link;
            Prev->link=current;
            current=Prev;
        }
        else
        {
            Prev=Temp;
            if (Temp->link!=NULL)
           {
              Temp=Temp->link;
           }
               Prev->link=current;
             current=Prev;
        }

    }
    Head=current;
}