0

C++ で二重リンク リストを実装しています。挿入前は、印刷ノード機能は正常に機能しますが、前面への挿入を行うと、印刷が永遠に続きます。

たとえば、1、2、3 のデータのノードがあり、データを 5 の前に挿入します。次に、印刷しようとすると、3 番目のノード 2 に移動することなく、5、1、INFINITE LOOP のみが表示されます。

これが私の構造です。

    struct dl_node
    {
        int               data;
        struct dl_node*   prev;
        struct dl_node*   next;

        dl_node(dl_node* prev, dl_node* next, int data)
        {
            // here, prev is the parameter
            // this->prev is from an object
            this->prev = prev;
            this->next = next;
            this->data = data;
        }

        // constructor, without pointer parameter
        explicit dl_node(int data)
        {
            this->prev = this;
            this->next = this;
            this->data = data;
        }
    };

これが私の挿入機能です。

    // "push-front" operation
    dl_node* insert_node(dl_node* head, int data)
    {
        if (nullptr == head)
                    return new dl_node(data);

            auto insertion
            = new dl_node(head->prev, head, data);
            // previous node of this insertion is head's prev
            // next node of this insertion is head

            insertion->prev->next = insertion;
            insertion->next->prev = insertion;

            return insertion;
    }

これが私の初期化です。

    struct dl_node* head   = new dl_node(NULL);
    struct dl_node* node_1 = new dl_node(NULL);
    struct dl_node* node_2 = new dl_node(NULL);

    head  ->data = 1;
    head  ->next = node_1;
    node_1->prev = head;

    node_1->data = 2;
    node_1->next = node_2;
    node_2->prev = node_1;

    node_2->data = 3;
    node_2->next = nullptr;

ここに私の挿入があります。

    // we insert to FRONT
    head = insert_node(head, 5);

これが私の印刷ループです。

struct dl_node* current_node_2 = head;
while ( current_node_2 != nullptr )
    {
            cout << current_node_2->data << ", ";
            current_node_2 = current_node_2->next;
    }
    // 5, 1, I get infinite loop from here....

誰でも何か考えがありますか？

4

2 に答える 2

1

問題は、デフォルトのdl_nodeコンストラクターが と の両方prevをnextに設定することthisです。

呼び出すinsert_node(head, 5)と、次の状態になります。

insertion->prev = head->prev;  // assigned in constructor, but head->prev == head
insertion->next = head;
insertion->prev->next = insertion;
insertion->next->prev = insertion;

しかしinsertion->prev == head->prev、そして私たちは知っているhead->prev == headので、

insertion->prev->next = insertion

次のようになります。

head->next = insertion;

したがって、次のようなリストになります。

insertion -> head -> insertion -> ...

デフォルトのコンストラクターを両方とも NULL に設定するように変更する必要がnextありprevます。また、挿入関数では、逆参照する前にinsertion->prevとinsertion->nextが非 NULL であることを確認する必要があります。

于 2013-08-23T20:47:14.823 に答える
0

あなたが持っているもので私が目にする唯一の本当の問題は、あなたがヨル挿入をしているとき、あなたは次のことをしているということです:

    newnode.next = head
    newnode->prev = head.prev
    newnode->data = 5

    head.prev = newnode (missing)

ただし、head.prev を newnode に設定することは決してありません。これにより、ヘッドがヌル ポインターのままになります。また、このコードが何のためにあるのかよくわかりませんが、ポインターを誤って変更している可能性があります。

    insertion->prev->next = insertion;
    insertion->next->prev = insertion;
于 2013-08-23T20:44:27.920 に答える