問題タブ [singly-linked-list]

私は最近、すでに書かれているいくつかのコードでプロジェクトを開始しました。彼の実装を調べることにしたところ、彼が単一リンク リストを使用してプライオリティ キューを実装していることがわかりました。

SLL についての私の理解では、リスト全体を反復処理する必要がある場合があるため、そのように実装するのは非効率的です。そのため、ヒープが好まれます。しかし、おそらく私はその背後にある何らかの理由を見逃しており、優先度キューにヒープではなく SLL を選択したことがある人がいるかどうか疑問に思っていましたか?

メモリの断片化をシミュレートするプログラムを書いています。入力ファイルは、どのセグメントをいつ入力する必要があるかを示します。

サンプル ファイルは次のとおりです。

ここCで、 はメモリ サイズ、Pは順序 (サイズ、開始時間、およびライフ タイム) のセグメントであり、R(すべき) どのセグメントを示すレポートを出力し、メモリのどこにホールがあるかを示します。

この割り当てのルールの 1 つは、イベントのリンク リストを作成することです。ここでは、セグメントの挿入と削除がイベントとして作成され、イベント リストをトラバースする必要があります。更新: 何か違うことがありますが、イベントがイベント リストに挿入されていないことは確かです。理由がわかりません。私のロジックがオフになっている場所を誰かが見ていますか?

最初に、私がやろうとしていることについて少し説明します。

私の計画は、boost:spirit::qi を使用して実装されたパーサーにデータを供給する、boost::asio ライブラリを使用して実装されたソケット ストリームを持つプログラムを作成することです。パーサーはパケットを受け取り、パケット オブジェクトを埋めてから、そのオブジェクトをパケット オブジェクトのリンク リストの末尾に追加します。パケット プロセッサは、リスト内の最初のオブジェクトを読み取り、その処理を実行してから、次の項目に移動して最初のオブジェクトを削除します。

リンク リストを使用することにしたのは、std::queue を使用した場合、ストリームがパケットを追加するたびに、またはプロセッサがパケットを削除するたびにコンテナー全体をロックする必要があり、2 つのスレッドが多かれ少なかれ連続して実行されるためです。避けたいと思います。さらに、キュー クラスにはオブジェクト全体をコピーする傾向がありますが、リンク リストのアイデアには、オブジェクトを一度作成してからそれを指すだけでよいという利点があります。このビジネス全体のシリアライズを避けるために、boost:mutex ミューテックスを各ノードに配置し、そこからロックするつもりです。アイデアは、ソケット ストリームでリストを作成し、すぐに最初のノードをロックし、パーサーからノードに入力し、次のノードを作成してロックし、最初のノードのロックを解除して次のノードに移動して作業を行うことです。こっちへ」ソケット ストリーム ノーズの下でパケット プロセッサがジャンプして削除する可能性がある、ロックされていないノードが最後にぶら下がることは決してありません。パケット プロセッサは最初のノードをチェックしてロックしようとします。ロックされている場合は、処理を行ってからロックを解除し、次のノードを取得して最初のノードを削除します。このように、シリアライゼーションは、パケット プロセッサがソケット ストリーム クラスに追いついた時点に限定されます。

さて、私の質問は、これを実際に実装する作業を行う前に、これは良いアイデアのように聞こえますか? 簡単なテストで試してみましたが、問題なく動作するようです。例外処理を実装し、割り当てたメモリを解放するように注意している限り、これに関する重大な問題は考えられませんが、誰かが考えられる場合私が見落としていたこのアイデアに関する問題があれば、ご意見をいただければ幸いです。また、代替案として、またはこのアイデアをよりうまく機能させる可能性のある他の提案をいただければ幸いです。

前もって感謝します！

私が何かを見逃していない限り、 SGIslistとC++11はどちらも私と同じように見えます。std::forward_listどちらも単一リンクリストを実装しています。

C ++標準委員会は名前slistを採用せず、代わりにC ++ 0xの標準ライブラリにコンテナを追加したときに新しい名前forward_listを選択したため、違いがあると思います。

私はC++でデータ構造を開始していて、読んでいるときに次のスニペットに出くわしました。

作者が実装のためにクラスではなく構造を選択する理由を誰かが詳しく説明できますsingly linked listか？ありがとう。

単方向にリンクされたリストが与えられた場合、指定されたノード (たとえば、ノード 4 など) からヘッド ノードを決定する方法。ノードの総数: 10.Thanks. ロジックで十分です。コードは高く評価されます。

ヘッド ノードが与えられた場合、順方向トラバースを実行して次のノードを簡単に決定できることがわかっています。

この場合、二重にリンクされたリストを使用する方が簡単ですが、単一にリンクされたリストを使用してヘッドノードを追跡できるかどうか疑問に思っていました.Thank.

リンクされたリストに関する以前の質問でこれを理解していると思っていましたが、ひどく間違っていました。最初に投稿したときと同じように迷っています。

技術的には 2 つの質問をしていることは理解していますが、少なくとも 1 つを取得することで、もう 1 つの質問が簡単になることを願っています (それらが互いに逆であると仮定して)。

私にはすでに 3 つのクラスが与えられています。それらは次のとおりです。

SLinkedList.java

Node.javaもあります

そして最後に GameEntry.java

編集ポイント Scores.java というドライバーを作成しました。これまでのところ、クラスに必要だと思うものを追加しましたが、おそらく間違っています。

ScoresTest.java という名前のテスト ドライバーがあり、ほとんどの項目を記入しました。

パッケージ Project_1;

chapter3.linkedList.SLinkedList をインポートします。

これで完全に終了しました。追加するものが何も残っていないことは確かです。

答えてくれる人を探しているわけではありませんが、どこから始めればいいのか、追加または削除機能をどのように作成すればよいのかわかりません。これは中級者向けのコースであり、リンクされたリストについては何も説明していません (信じられない場合は、自分で調べてください。テキストは Datastructures and Algorithms in Java, 5th edition と呼ばれています)。配列を使ってこれを行う方法を非常に簡単に示しています...これはリンクされたリストに対しては完全に機能しますが、どうやら教師はこの方法でそれを行うことを望んでいないようです.

こことグーグルで他の人の回答を見てみましたが、これまでのところ何もクリックされていないか、まったく意味がありません。それがどのように機能するかを理解できません。ボード、リンクされたリスト用にコード化された並べ替え、追加、または削除機能を見たことがない...教えられていないか、見つけられないものがわからない。

どんな助けでも大歓迎です、そして前もって感謝します！

編集

import java.util.*; を見ました。リンクされたリストのためのその中のコマンドは、非常に簡単に思えます。削除するには、 list.sublist(i, i).clear(); を使用します。そして、削除したい値が削除されました。非常に簡単です。slinkedlist.java と node.java を利用しようとしているだけのようですが、どのような形や形でもそれらに従うことができないようです。私は先生が本当にそれらを書いたと信じています. 助けてくれてありがとう！

編集

これが漠然としているように見える場合もお詫びしますが、混乱がリンクしているように見える特定のポイントはありません.java.util.linkedList;について話している場合、リンクリストを理解していますが、何を使用するかについては私はこの状況で与えられました.論理をまったくたどることができず、どこから始めればよいのかわからなくなり、かなり迷ってしまいます.

要素（整数など）の最後の出現を見つけて、リストを1回（前方）トラバースするだけでこのノードを削除することは可能ですか？

最初のmapListノードを追加し、その後にノードを追加するようですが、その後に追加されたすべてのノードは、* nextが正しく設定されているように見えても、毎回その3番目の位置に配置されます（私はまだ新しいです）ポインタとC）で、他のノードにアクセスしたいときにセグメンテーションエラーが発生します。私はpatronNodeの追加作業を持っていますが、これははるかに複雑で、これを正しく行うことができないようで、出力するものは私に冒涜を吐きます=（

これが2つの構造です。

これが追加機能です

私の出力は次のようになります。

キーでADDMAPNODEを入力=OrsonScott Card

キーでADDMAPNODEを入力=フランクハーバート-オーソンスコットカードの後に​​キーを追加-フランクハーバートを追加

キーでADDMAPNODEを入力=アイザックアシモフ-現在のキーはオーソンスコットカード-フランクハーバートの後にキーを追加-アイザックアシモフを追加

キーを使用してADDMAPNODEを入力=ダグラスアダムズ-現在のキーはオーソンスコットカード-フランクハーバートの後にキーを追加-ダグラスアダムズを追加

キーでADDMAPNODEを入力=ジョージオーウェル-現在のキーはオーソンスコットカード-フランクハーバートの後にキーを追加-ジョージオーウェルを追加

キーを使用してADDMAPNODEを入力=RobertA.Heinlein-現在のキーはOrsonScottCardです-FrankHerbertの後にキーを追加します-RobertA.Heinleinを追加しました

キーを使用してADDMAPNODEを入力=レイブラッドベリ-現在のキーはオーソンスコットカード-フランクハーバートの後にキーを追加-レイブラッドベリを追加

ect ....すべてのキーがFrankHerbertの後に追加されます。これは、コードがHerbertの-> nextがNULLであると見なしているためです。ただし、新しいノードに対して=を作成しただけです... CONFIZZZLED