[解決済み]
そこで、ソートされた二重リンクスキップリストを作成してみることにしました...
どのように機能するかをよく理解していると確信しています。x を挿入すると、プログラムは x を配置する適切な場所をベース リストから検索し (ソートされているため)、(概念的には) コインを裏返し、「コイン」が に落ちた場合、その要素はその上のリストに追加されます。 (または要素を含む新しいリストが作成されます)、その下の要素にリンクされ、コインが再び裏返されます。「コイン」がいつでも b に着地すると、挿入は終了します。また、すべてのリストに -infinite を開始点として格納して、開始点より小さい値を挿入できないようにする必要があります (つまり、値が見つからないことを意味します)。
x を検索するには、「左上」(最も高いリストの最も低い値) から開始し、「右に移動」して次の要素に移動します。値が x より小さい場合は、「行き過ぎ」て値が x より大きいまで、次の要素に進みます。この場合、最後の要素に戻って 1 レベル下に移動し、x が見つかるか、x がまったく見つからなくなるまで、この連鎖を続けます。
x を削除するには、単に x を検索し、リストに表示されるたびに削除します。
今のところ、番号を格納するスキップ リストを作成するだけです。STL には私を支援できるものは何もないと思うので、整数値を保持し、検索、削除、および挿入のメンバー関数を持つクラス List を作成する必要があります。
私が抱えている問題は、リンクを扱うことです。前の要素と前の要素へのポインターを使用して「水平」リンクを処理するクラスを作成できると確信していますが、「垂直」リンクを処理する方法がわかりません (対応する要素を指す他のリストに?)
私の論理に欠陥がある場合は教えてください。主な質問は次のとおりです。
- 縦リンクの対処法とリンクの考え方が正しいかどうか
- クラス List のアイデアを読んだので、List は単一の整数ではなく、整数のベクトルを保持する必要があると考えています。実際、私はかなり前向きですが、検証が必要です。
- コイントスは int 関数を呼び出すだけで、rand()%2 が 0 または 1 の値を返し、それが 0 の場合は値が「レベルアップ」し、0 の場合は挿入が終了したと想定しています。これは間違っていますか？
- -infinite に似た値を格納する方法は?
編集:私はいくつかのコードを書き始め、List コンストラクターの処理方法を検討しています....その構築では、「-infinite」値を vectorname[0] 要素に格納する必要があると推測しています。作成後に insert を呼び出すだけで、x を適切な場所に配置できます。