3

二重リンクリストの順序を逆にする方法を模索してきましたが、何らかの理由で、関数void reverse()でwhileループが1回実行された後、何らかの理由でクラッシュします。先のいくつかの質問に答えるために、私は兄弟の助けを借りて自分自身を教えています。これはすべてのコードではありませんが、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;
    }
}
4

10 に答える 10

7

これを試して：

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;
}
于 2010-07-07T20:41:03.550 に答える
3

編集：私の最初の実装は正しかったが完璧ではなかった。 実装はかなり複雑です。代わりにこれを試すことができますか？

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で受け入れていたということでした。それは私がそれのローカルコピーを返していたことを意味します。これで動作するはずです。

于 2010-07-07T20:45:43.947 に答える
2

あなたはあなたの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へのリンクを交換することです。次のノードに移動するときは、次のノードを格納する必要があります。これにより、に設定したときにそのノードへのポインタが残ります。previousnextcurrNodecurr.nextprev

于 2010-07-07T20:42:21.207 に答える
1

シンプルなソリューション。リスト全体の反復回数の半分未満で反転します

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;
}
于 2013-01-18T05:57:36.257 に答える
0

pswap関数が間違っているので、一時オブジェクトを作成してスワップしようとしないで、ポインタをスワップする必要があります。そのようにする必要があります（後で他の間違いがあるかもしれません）

void pswap (node *&pa, node *&pb)
{
    node* temp = pa;
    pa = pb;
    pb = temp;
    return;
}
于 2010-07-07T20:45:50.233 に答える
0

最後のノードへのリンクを維持することをお勧めします。
そうでない場合は、最後のノードを見つけます。「前の」リンク（またはあなたの場合はprv）を使用してリストをトラバースします。

実際にリンクを変更する必要はありません。ポインタを使用してトラバースするprvと、逆の順序でノードに自動的にアクセスします。

于 2010-07-07T20:46:23.207 に答える
0

見る

valuesnextone=nextone->nxt->nxt;

ここでnextone->nxtはnullになる可能性があります。

それとは別に、スワップ関数でポインタへのポインタを使用してみてください。

于 2010-07-07T20:46:35.770 に答える
0

2つのポインタを使用した非常に単純な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;
}
于 2015-12-30T09:19:53.373 に答える
0

二重リンクリストを逆にするための私のコード、

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;
}
于 2016-04-14T08:14:00.323 に答える
0

ここに再帰的なソリューションを追加しようと思いました。

node* reverse_and_get_new_head(node* head) {
    if (head == nullptr) { return nullptr; } 
      // This can be avoided by ensuring the initial,
      // outer call is with a non-empty list
    std::swap(head->prev, head->next);
    if (head->prev == nullptr) { return head; }
    return reverse_and_get_new_head(head->prev);
}

void reverse() {
    start_ptr = reverse_and_get_new_head(start_ptr);
}
于 2019-11-17T20:45:18.980 に答える