問題タブ [xor-linkedlist]

XORリンクリスト（ウィキペディアから）を読ん でいますが、理解するのに問題があります。

次の段落が表示されません。

ある時点からいずれかの方向にリストのトラバースを開始するには、1つだけでなく、2つの連続するアイテムのアドレスが必要です。2つの連続するアイテムのアドレスが逆になると、リストを反対方向にトラバースすることになります。

私はそれについていくつか質問があります：

1. それ（XORリンクリスト自体）は実際にどのように機能しますか？

   （いくつかの例を挙げて答えを正当化するとよいでしょう。つまり、いくつかの住所を取得し、それに応じていくつかの計算を実行します。）

2. どうすれば実装できますか？実装についての簡単なアイデア。

3. 実際にどこにあるのか、どこで使用できるのか？どうやら本当に参考になりますか？

xor-linked list のJava コードを書きたいと思っています。誰かが参照間で xor 操作を実行する方法を教えてもらえますか?

私は最近、非常に興味深いと思った以下のリンクに出くわしました。

http://en.wikipedia.org/wiki/XOR_linked_list

• 汎用デバッグツールはXORチェーンをたどることができないため、デバッグがより困難になります。[1]
• メモリ使用量の減少の代償は、コードの複雑さの増加であり、メンテナンスがより高価になります。
• ほとんどのガベージコレクションスキームは、リテラルポインタを含まないデータ構造では機能しません。
• ポインターのXORは、一部のコンテキスト（C言語など）では定義されていませんが、多くの言語では、ポインターと整数の間で何らかの型変換が提供されています。
• リストをトラバースしていない場合、たとえば、リストアイテムへのポインタが別のデータ構造に含まれている場合、ポインタは読み取り不能になります。
• リストをトラバースしている間、次のノードのアドレスを計算するために、以前にアクセスしたノードのアドレスを覚えておく必要があります。

今、それが低水準言語専用なのか、それともC＃内でも可能なのか疑問に思っています。

C＃で同じ結果を生成するための同様のオプションはありますか？

これがxorリンクリスト実装の私のコードです

しかし、コンパイルすると、このようなエラーが発生します

あいまいなシンボルの終わりはなぜですか?このエラーはどういう意味ですか?

私は XOR リンク リストについて読んでいて、1 つの疑問が頭に浮かびIs it possible to have a circular XOR linked list?ました。どうにかしてそのようなリストを作成したとしても、リストのヘッド ノードが与えられた場合、それをトラバースすることは不可能であるように思われます。たとえば、リンクされたリストに A、B、C の 3 つのノードが含まれているとします。

headリストが与えられているため、つまりこの場合は、移動するためにorAの少なくとも 1 つを知る必要があるため、前後に移動することはできません。トラバースできないため、ビルドもできません。BC

私の考えは正しいですか？または、何か不足していますか？

これが私の XOR 連結リスト構造体であるとします...

xor リンク リストのサイズが 1 または 2 の場合、何をxor含める必要がありますか?

xor 連結リストのコードを書きます。プロパティ C.link = A XOR B を使用してポインタを取得する関数があります。この関数のコードは次のとおりです。

しかし、最終的にセグメンテーション違反が発生します。GDB を使用したデバッグでは、この理由はreturn (Node<T>*)((int)prev ^ (int)curr->np); 値などの変数の行にあることが示されています

xorの終わりに

私の意見では、有効なポインターがないため、セグメンテーション違反に従います。どうすれば修正できますか？ありがとう

問題は解決されました。問題は代入演算子にありました

これらの2行を削除すると、問題はなくなりました。

メイン プログラムは代入演算子と呼ばれ、古いオブジェクトの先頭と末尾の値を新しいオブジェクトに割り当てます。

Data Structures and Algorithms Made Easyでは、struct次のように指定されたメモリ効率の高いメモリ リストについて、

ではptrdiff、前のノードと次のノードの xor が実行されます。たとえば、前のノードのアドレスは100で、次のノードのアドレスは500です。

したがって、ptrdiff のアドレスは400になります。アドレスの xor を知るだけで、どのようにして次または前のノードに移動できるのでしょうか (二重リンク リストで行うように)。

ここで何かステップがありませんか？

そのため、XOR リンク リストを作成しています。新しいノードにメモリを割り当てようとすると、プログラムがクラッシュします。挿入関数のコードは次のとおりです。

これは XORList の定義です:

そして、これは XORListNode の定義です:

私はまだポインターの経験がないので、コードに関する他のコメントもいただければ幸いです。

ご協力ありがとうございました。