問題タブ [skip-lists]

スキップ リストの削除メソッドが無限ループに陥っています。このウェブサイトhttp://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Map/skip-list-impl.htmlの疑似コードに従いました。他の方法は、削除を除いて正常に機能しているようです。これは私のコードです：

これは私のコード全体ですhttp://pastebin.com/StJRzixN
ありがとう

私は CS の学生ですが、ハロウィーンの週末は、デバッグできないプログラミングの課題によって台無しになりました。これは、ここですぐに「重複」とマークされない数少ない質問の 1 つかもしれません。

割り当ては、「スキップ リスト」、またはランダムな「コイン」トスによって決定されるポインタの可変サイズ配列が各ノードにある単一リンク リスト (C でプログラム) です。トスが 3 回成功すると、高さは 3 などになります。次に、各配列は同様の高さの他の配列にリンクされます。7 番目のレベルは次の 7 番目のレベルにリンクされ、6 番目から次の 6 番目のレベルにリンクされ、最初のレベルまで、または配列要素にリンクされます。 0 は、リスト内の次の項目に自然にリンクされます。

ほとんどのアイテムにはより高いレベルがないため、これは単純に n ではなく log(n) 時間で検索するための優れた方法として機能します。挿入、削除、および検索が劇的に高速になりますが、メモリのコストが高くなります。これは単なる理論です - ここに写真があります:スキップリスト

皆さんの多くはすでにこのことを知っているでしょうが、少し説明して、ここで起こっていることの基本を実際に理解していることを示したかっただけです.

この問題は、提供されたすべてのテストを "CODE 6 - ABORT" メッセージで台無しにするランダムなセグメンテーション違反です。メイン ファイルを実行すると、コード内の指定された場所 (<-----Segfaults) でランダムに segfaults が発生します。これは約半分の時間で発生し、いずれかの行で発生する可能性があります。テストでは、多くの「不良ポインター」および「minmap チャンク エラー」メッセージも表示されます。

私はこれで頭がいっぱいです。私はクラスで 93 を持っていますが、この忌まわしいことを終わらせることができなければ、それは 87 に落ちます。

コードは次のとおりです。

定義

ランダムフォルトの主な原因

...そして最後に、悪魔のデータ構造:

他のものもあるかもしれませんが、Contains と Add が問題です。奇妙なことに、これは通常、別のリストを解放した後に発生しますが、コード内にそのリストからのアーティファクトが見つかりません。

あなたがこれを解決してくれたら、20 ドルと 1 皿のクッキーをあなたの選んだ住所に郵送します。

だから私は学校でスキップリストを勉強していて、スキップリストで公平なコインではなく「不公平なコイン」を使うべきかどうかについて簡単に話しました. 0 < p < 1 である p に設定されます (したがって、「裏」の確率は 1 −p になります)。

これについて疑問に思った点がいくつかありますが、このトピックについてはすぐに説明してしまったので、よくわかりません。

1. これを行った場合、スキップ リストの高さ/サイズはどうなりますか? 確率が歪めば、明らかに状況が変わりますよね？任意の n 個の要素が含まれているとします。明らかに、公正なコインを使用した場合とは高さが異なります。

2. 任意のノードをスキップ リストに追加すると、そのノードが受け取るプロモーションの期待数はどのように変化しますか? このシナリオでそうなるかどうかはわかりませんが、話題になりました。

私が実際に理解せずに答えを出すだけの人を探しているわけではありませんが、確率の変化によってどのように影響を受けているかを理解できるように、これらの変化がなぜ起こっているのかを実際に説明していただければ幸いです.

編集: Pat Morin の Open Data Structures book の 99 ページに記載されている方程式とさまざまな確率を比較した後、理解できたと思います。同じ質問で他の人を助けるために、解決策を見つけたらコメントに投稿します。

Javaでのスキップリストの実装に苦労しています。基本的にすべて正常に動作しますが、putメソッドの実行に時間がかかりすぎます。これが私のコードです。チュートリアルを行って、何人かのコードを見てきましたが、どこに問題があるのか​​ わからないようです（100000個のランダムな要素を入れて測定すると、動作するのに時間がかかります）。

なぜそんなに時間がかかるのですか？

http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Map/skip-list-impl.htmlの擬似コードを使用して、PHP でスキップ リストを実装しようとしています。Javaでは問題なく動作しましたが、PHPではうまく動作しませんでした。put メソッドは常に null を返すため、get メソッドも null を返します。
どこが間違っているのかよくわからないので、助けていただければ幸いです！

ありがとうございました！

skip-list を使用してアルファベット順にデータを表示する場合の時間の複雑さはどうなりますか? クアッドノードを使用して実装した場合、スキップリストの時間の複雑さはどれくらいになりますか?

テンプレート クラスのセンチネル ノードを作成する必要があるという要件があります。それ自体への参照が必要なもの

今、私は次のようなことをしたい

そして、渡す必要はありません。デフォルトのコンストラクターが利用できないことがわかります。

スキップリストを作成するために必要です。境界歩哨が必要です。

スキップ リストのコピー関数を作成しようとしているときに問題が発生しました。クラスのほとんどはすでに完了しているので、デザインを変更したくない.

各ノードには 2 つのポインタがあり、1 つは同じレベルの次のノードへのポインタで、もう 1 つは 1 レベル下の同等のノードへのポインタです。私のクラスには、各レベルのヘッド ノードへのポインタを格納するベクトルがあります。

私のプライベートコピー機能：

この関数は、すべての単一ノードがコピーされて相互にリンクされている状態で水平方向に正常に機能しますが、垂直方向のリンクは設定しません。
curr->below誰でもこれを機能させる方法についていくつかの提案を得ることができますか?