1

私は2つの単純な構造を持っています:

struct Address
{
    char city[255];
};
typedef Address* AddressPtr;

struct Person
{
    char fullName[255];
    Address* address;
    Person* next;
};
typedef Person* PersonPtr;

Person 構造は、新しい要素がリストの先頭に追加される Linked リストを形成します。私がやりたいのは、それらを でソートすることfullNameです。最初はリンクを交換しようとしましたが、リストの先頭が失われ、その結果、リストが部分的にソートされました。次に、ノードの値を交換してリストをソートすることにしました。しかし、私は奇妙な結果を得ます。名前のリストの場合: Test3, Test2, Test1、取得しTest3, Test3, Test3ます。

これが私のソートコードです：

void sortByName(PersonPtr& head)
{
    TaskPtr currentNode, nextNode;
    for(currentNode = head; currentNode->next != NULL; currentNode = currentNode->next)
    {
        for(nextNode = currentNode->next; nextNode != NULL; nextNode = nextNode->next)
        {
            if(strcmp(currentNode->fullName, nextNode->fullName) > 0)
            {
                swapNodes(currentNode, nextNode);
            }
        }

    }
}

void swapNodes(PersonPtr& node1, PersonPtr& node2)
{
    PersonPtr temp_node = node2;
    strcpy(node2->fullName, node1->fullName);
    strcpy(node1->fullName, temp_node->fullName);

    strcpy(node2->address->city, node1->address->city);
    strcpy(node1->address->city, temp_node->address->city);
}

ソートが完了した後、ノードの値は少し変です。

更新しました

これは私がリンクを交換した方法です：

void swapNodes(PersonPtr& node1, PersonPtr& node2)
{
    PersonPtr temp_person;
    AddressPtr temp_address;

    temp_person = node2;
    node2 = node1;
    node1 = temp_person;

    temp_address = node2->address;
    node2->address = node1->address;
    node1->address = temp_address;
}
4

4 に答える 4

1

片方向リストのノードを交換するには、交換する 2 つのノードだけでは不十分です。変更するポインタが少なくとも3 つあります。

+--------+ next +---------+ next +---------+ next +---------+
| before |----->|  node1  |----->|  node2  |----->|  after  |
+--------+      +---------+      +---------+      +---------+

とを入れ替えるnode1には、 と を入れ替えてからを指すnode2必要があります。もちろん、 を変更するには、 を知る必要があります。(ノードが隣接していない場合は、の親も更新する必要があります。)node1->nextnode2->nextbefore->nextnode2before->nextbeforenode2

ここで、ポインターではなくデータのみを交換する場合は、交換する 2 つのノードだけで問題ありません。しかし、それが目標である場合、あなたは 2 つのことをひどく間違っています。

  1. temp_node== node2。つまり、両方とも同じオブジェクトを指しています。したがって、データを から にコピーすると、同じオブジェクトポイントが変更*node1されます。次に、 からにコピーすると、実際には、上書きしたばかりのデータがコピーされます。最終結果: すべてのノードのアドレス オブジェクトに同じビットが含まれます。*node2temp_node*temp_node*node1

    独立したオブジェクトを指すかtemp_node、単にポインターではなくノードオブジェクトにするか、データをバッファーなどにコピーする必要があります。

  2. 何かを成し遂げたい場合、ポインターの交換とデータの交換は相互に排他的です。ここで、ノード ポインタを交換し、次にデータ ポインタを交換します...? ちょっと目的を破りますよね？

    時計：

        //    node1             node2
    //    +----------+ next +----------+
    //    |   node   |----->|   node   |
    //    +----------+      +----------+
    //          | address        | address
    //          v                v
    //    +----------+      +----------+
    //    | address1 |      | address2 |
    //    +----------+      +----------+

    temp_person = node2;
    node2 = node1;
    node1 = temp_person;

    //    node2             node1
    //    +----------+ next +----------+
    //    |   node   |----->|   node   |
    //    +----------+      +----------+
    //          | address        | address
    //          v                v
    //    +----------+      +----------+
    //    | address1 |      | address2 |
    //    +----------+      +----------+

    ここまでは順調ですね。2 つのポインターが交換されます。つまりnode1->address、2 番目のノードのアドレスが表示されます。

    しかし、待ってください。次に、アドレス ポインターを交換します。

        temp_address = node2->address;
    node2->address = node1->address;
    node1->address = temp_address;

    //    node2             node1
    //    +----------+ next +----------+
    //    |   node   |----->|   node   |
    //    +----------+--+   +----------+
    //           address|        | address
    //          +-------|--------+
    //          v       |
    //    +----------+  |   +----------+
    //    | address1 |  +-->| address2 |
    //    +----------+      +----------+

    では、 をnode1->address指しaddress1ます。データのスワップを解除しました。

    したがって、ポインターまたはデータを交換するかどうかを決定します。データを交換する場合、必要なのは 2 つのノードのポインターだけであり、nextポインターを変更する必要はありません。一方、ノード全体を交換する場合は、「前」ノードが必要であり、データ ポインターには触れないでください。ポインターを交換することの全体的なポイントは、データを再配置することです。

于 2013-11-11T15:59:49.637 に答える
1

strcpy を使用する必要はありません。ノードを交換するときは、.next メンバー変数を交換することで実現できます。リンクされたリストを使用する唯一の理由は、大量のデータをコピーすることです。

こういう時は、紙に状況を描いてみるのもいいですね。複数の箱を一列に描く：

 W["1"] -> X["3"] -> Y["2"] -> Z["4"]

では、W が X を指し、X が Y を指し、Y が Z を指すように、WXY と Z の 4 つのノードを設定しました。

各ノードには文字列値があります。W の値は 1、X の値は 3、Y の値は 2、Z の値は 4 です。

文字列値が昇順 (1、2、3、4) になるようにノードを並べ替えます。

ここで、実際のデータ値を交換することでそれを達成しようとしています。

swap(X.data, Y.data)

... その結果：

W["1"] -> X["2"] -> Y["3"] -> Z["4"]

それはうまくいくでしょうが、多くの理由から、それは良い考えではありません。1つには、非常にバグが発生しやすいです。2 つ目は、連結リストを使用する主な利点、つまりデータではなくリンクを交換することを放棄することです。

ノードのリンケージを交換すると、次のようになります。

 W["1"] -> Y["2"] -> X["3"] -> Z["4"]

どのデータも移動していないことに注意してください。W の値は 1 のまま、X の値は 3 のまま、Y の値は 2 のまま、Z の値は 4 のままです。 X につながり、Z につながり、1、2、3、4 の期待される結果が得られます。

ややこしく聞こえるかもしれませんが、正しい考え方を身につければ簡単です。手順を 1 つずつ分解してみましょう。

私たちの初期状態との違いは何ですか...

 W["1"] -> X["3"] -> Y["2"] -> Z["4"]

...そして私たちの望ましい状態?

 W["1"] -> Y["2"] -> X["3"] -> Z["4"]

違いは、真ん中の 2 つのノードを交換したことです。2 つの隣接するノードをどのように交換しますか?

さて、このように見てみましょう。以前は、W が X につながり、X が Y につながり、X が Z につながりました。

W が Y につながるようにします。Y が X につながることを望みます。X が Z につながるようにします。

見える？これには、3 つのノードの変更が含まれます。ノードのうちの 2 つしか知らない場合は実行できません。3 つ続けて変更できる必要があります。

いくつかの混乱を取り除きましょう：

A -> B -> C -> D

B と C を入れ替えて、次のようにします。

A -> C -> B -> D

どのように？

さて、そのグラフは次のものと同等です。

A -> A.next -> A.next.next -> A.next.next.next

そこで、私たちにできることは次のとおりです。ノードを取得し、その後の 2 つのノードを交換する操作を定義しましょう。したがって、A に対して操作を使用すると、B と C が入れ替わります。または、B で操作を使用すると、C と D が入れ替わります。

方法は次のとおりです。

void swapAfter( Node* node ) {
  Node* A = node;
  Node* B = node->next;
  Node* C = node->next->next;
  Node* D = node->next->next->next;

  A->next = C; // Lead A to C
  C->next = B; // Lead C to B
  B->next = D; // Lead b to D

  // Now we have A->C->B->D!
}

そして、そこに行きます。これで、任意の 2 つのノードを交換する方法ができました。

このように (回りくどく) 説明することにした理由は、リンクされたリストで何が起こっているかを理解して視覚化するのに役立つからです。初心者は、操作中に何が起こるかを精神的に理解するのに苦労することがよくあります。通常、彼らは本に書かれていることをやみくもに実行するだけで、なぜそれが機能するのかを理解することはありません。一方、この例では、各ステップが非常に明白です。

しかし、その「swapAfter」関数を直接使用しようとすると、あまり役に立たないかもしれません。1 つには、エラー チェックがないため、最後のノードで使用しようとするとクラッシュします。ただし、要点は、swapNodes 関数を提供することではなく、リンクされたリストがどのように機能するかを理解することでした。:-)

主な要点は、swapNodes 関数に十分なパラメーターを提供していないことです...「curNode」と「nextNode」を交換したい場合、その時点で、curNode (「prevNode」) の前にあるノードを知る必要があります。次に、次のようにします。

Node* finalNode = nextNode->next;

// right now, we have..
//   prevNode -> curNode -> nextNode -> finalNode

// we want..
//   prevNode -> nextNode -> curNode -> finalNode

// so..
prevNode->next = nextNode;
nextNode->next = curNode;
curNode->next = finalNode;

これを完全に機能させるには、エラー チェックを行う必要があることに注意してください。たとえば、nextNode が NULL の場合はどうなるでしょうか。または、prevNode が NULL の場合 (curNode が最初のノードであることを意味しますか?)、それぞれのケースを 1 つずつ処理します。

この複雑さをすべて回避したい場合は、リンクされたリストを使用する理由はまったくありません。代わりに、ポインターの配列を作成できます。

Person** people = new Person*[4];
for ( int i = 0; i < 4; i++)
  people[i] = new Person();

次に、その要素を交換するだけでその配列をソートできます。

if ( strcmp(people[1]->fullName, people[2]->fullName) > 0 )
  swap( people[1], people[2] );

「次の」ポインタを扱う必要はもうありません。ただし、アレイに 4 人以上を追加する場合は、サイズが固定されているため、再割り当てする必要があります。それがトレードオフです。

とにかく、これが少しでも役に立てば幸いです。これは私の最初の本当のスタック オーバーフロー コメントです。

于 2013-11-11T16:48:22.907 に答える
0

The problem arises from the fact that you are swapping the elements of the list while iterating through it.

Another approach could be to run through the list and swap objects until it runs through the list once without swapping any elements.

于 2013-11-11T15:53:12.930 に答える