質問: C言語でリストを用いて優先度のついた構造体を用いたプログラムを作りたいと思っています。 簡単に言うと、呼ぶたびに優先度順にリストの先頭にある構造体のデータを取り出す関数とその機構を作成したいと考えています。どうしてもわからなかったので質問させていただきました。 作る機構は、優先度を整数値で1-3まで持っている同じ型の構造体が幾つかあり、その構造体は線形リストになっており、自分の型の構造体のポインタをメンバとして持っています。 それらの構造体の優先度を調べて、その構造体のポインタの型の配列に3段階で振り分けます。このとき、同じ優先度の構造体があったら、構造体を後ろにつなげていきます。 その後、関数を呼ぶと、リストの一番先頭にあるデータを取り出した後、優先度3の構造体を、再び、優先度3のリストの一番後ろに、次に、優先度2の構造体を優先度3のリストの一番後ろに、優先度1の構造体を優先度2のリストの一番後ろにつなげます。優先度1か2の構造体が呼び出された後、もとの優先度のリストの一番後ろに戻ります。 例えば 構造体1優先度3 構造体2優先度2 構造体3優先度1 構造体4優先度1 の4つの構造体があるとしたら、 優先度の配列3つにそれぞれ振り分けて、 優先度の高い構造体の先頭のデータを取り出す関数を呼ぶごとに、 優先度3 1 1 2 2 3 4 1 3 4 1 4 1 2 優先度2 2 -> 3 4 -> -> 2 -> 優先度1 3 4 3 とリストを変更して、最終的に1123412・・・ と、優先度が高い構造体のデータを多くとり出せるような機構を作りたいです。 queueなどを用いて先頭から取り出していきたいのですが、どのようにすれば良いかいまいちわかりません。 なにか良い方法がございましたら、ぜひ教えてください。よろしくお願いします。
回答: > > なにか良い方法 > > > プログラム全体の説明をするのは大切ですが、質問の際に重要なのは**実現するのにあたり自分が悩んでいるポイントを明らかにする**ことです。どのあたりの実現が難しいと感じているのか明記しないことには「このプログラム全体の作り方がわからない」ようにも見えてしまいます。これが書かれていないので読者には「何が難しいのかわからないためアドバイスが難しい」質問になっています。 なお、仕様を詳しく説明しようとはしておられますが今一つ明確なアルゴリズムの説明になっていないように思います。印象としてはプロセスのスケジューリングを優先度付きラウンドロビンで行うためのキュー構造とキューからの取り出しのようなものが題材のように見えましたが・・・ * エントリーを取り出す機能の詳細な動作仕様 「優先度を指定してエントリーを取り出す」もののようですが、その優先度のエントリーがなかった場合はどうするか(あるいはそういう条件とならないことがあらかじめ保証されているのか?)などが書かれていません。本来はそれも含めて明記しておくべきです。質問文の記述では「こんなふんいき」という程度しか書かれておらずいくつかのケースでどう動くべきかの提示が漏れています。 * 構造について(優先度が違うリストを接続すること) なぜ優先度3のリストに優先度2のリストをつなげなければならないかの意義がわかりません。それがわからないのは、上に書いたように「エントリーを取り出す機能の詳細な動作仕様」を書ききれていないからだと思います。例えば「指定優先度のエントリーが存在してなければ次の優先度のエントリーを取り出す仕様」だったりするのでしょうか? もしそうだとしても優先度が異なるリストを接続するかどうかはアルゴリズムの実装に依存することであって仕様ではないようにも思えます。リストを接続するのが「課題の条件=仕様」であればそうしなければなりませんが、あなたがイメージした実装のようにも見えました。どちらなのかはっきりしないとアドバイスもしにくいと思います。 追記: なんとなく仕様が想像できるようになりました。作成すべき機能をscehdule関数、それが管理するものをタスクと呼ぶことにすると・・・ 1. ディスパッチした後のタスクは優先度が高いものが高頻度でスケジュールされるようにする 2. 優先度が高いものを高頻度で呼び出すための仕様は 2.1 sceduleの呼び出し毎に優先度2~1の先頭タスクだけ1つ上の優先度キューへ昇格させる 2.2 ディスパッチ後に最高優先度以外のタスクは自身の優先度キューへ戻す 3. schedule関数は1回の呼び出しで必ず1つのタスクを取り出す(そしてディスパッチする?) 4. 2のキューの並べ替えをした上で3~1の中で空でない一番優先度の高いキューからタスクを取り出す 自分が質問者さんの説明をよく読んでれば最初からわかってたかもしれません。失礼しました。 上に書いたのは私なりに表現した仕様ですが、このとおりでよいならそれを素朴に実装できそうな気がします。実装にあたっては主としてキューを実現するところだけ若干面倒があるかも知れません。 * キュー 出来合いのクラスを利用するのでもかまわないなら簡単ですが、自前で実装するならキューの実現方法を理解しておく必要があります。もし曖昧なのであれば「アルゴリズム キュー」で検索してみると考え方や実装のサンプルが載っているものが見つかると思います。キューが先頭と末尾のエントリーを保持していて要素自体は双方向のチェーンでリンクされた構造や内部的に配列を用い双方向のリンクを必要としないリングバッファのようなものなどいくつかの考え方が見つかると思います。 いずれにせよ必要なのは「空かどうかの判定」「先頭からの取り出し」「末尾への追加」という3つの機能ですね。