C言語でリストを用いて優先度のついた構造体を用いたプログラムを作りたいと思っています。
簡単に言うと、呼ぶたびに優先度順にリストの先頭にある構造体のデータを取り出す関数とその機構を作成したいと考えています。どうしてもわからなかったので質問させていただきました。
作る機構は、優先度を整数値で1-3まで持っている同じ型の構造体が幾つかあり、その構造体は線形リストになっており、自分の型の構造体のポインタをメンバとして持っています。
それらの構造体の優先度を調べて、その構造体のポインタの型の配列に3段階で振り分けます。このとき、同じ優先度の構造体があったら、構造体を後ろにつなげていきます。
その後、関数を呼ぶと、リストの一番先頭にあるデータを取り出した後、優先度3の構造体を、再び、優先度3のリストの一番後ろに、次に、優先度2の構造体を優先度3のリストの一番後ろに、優先度1の構造体を優先度2のリストの一番後ろにつなげます。優先度1か２の構造体が呼び出された後、もとの優先度のリストの一番後ろに戻ります。
例えば
構造体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などを用いて先頭から取り出していきたいのですが、どのようにすれば良いかいまいちわかりません。
なにか良い方法がございましたら、ぜひ教えてください。よろしくお願いします。
-
気になる質問をクリップする
クリップした質問は、後からいつでもマイページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
クリップを取り消します
-
良い質問の評価を上げる
以下のような質問は評価を上げましょう
- 質問内容が明確
- 自分も答えを知りたい
- 質問者以外のユーザにも役立つ
評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。
質問の評価を上げたことを取り消します
-
評価を下げられる数の上限に達しました
評価を下げることができません
- 1日5回まで評価を下げられます
- 1日に1ユーザに対して2回まで評価を下げられます
質問の評価を下げる
teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。
- プログラミングに関係のない質問
- やってほしいことだけを記載した丸投げの質問
- 問題・課題が含まれていない質問
- 意図的に内容が抹消された質問
- 過去に投稿した質問と同じ内容の質問
- 広告と受け取られるような投稿
評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。
質問の評価を下げたことを取り消します
この機能は開放されていません
評価を下げる条件を満たしてません
質問の評価を下げる機能の利用条件
この機能を利用するためには、以下の事項を行う必要があります。
- 質問回答など一定の行動
-
メールアドレスの認証
メールアドレスの認証
-
質問評価に関するヘルプページの閲覧
質問評価に関するヘルプページの閲覧
checkベストアンサー
+1
なにか良い方法
プログラム全体の説明をするのは大切ですが、質問の際に重要なのは実現するのにあたり自分が悩んでいるポイントを明らかにすることです。どのあたりの実現が難しいと感じているのか明記しないことには「このプログラム全体の作り方がわからない」ようにも見えてしまいます。これが書かれていないので読者には「何が難しいのかわからないためアドバイスが難しい」質問になっています。
なお、仕様を詳しく説明しようとはしておられますが今一つ明確なアルゴリズムの説明になっていないように思います。印象としてはプロセスのスケジューリングを優先度付きラウンドロビンで行うためのキュー構造とキューからの取り出しのようなものが題材のように見えましたが・・・
エントリーを取り出す機能の詳細な動作仕様
「優先度を指定してエントリーを取り出す」もののようですが、その優先度のエントリーがなかった場合はどうするか（あるいはそういう条件とならないことがあらかじめ保証されているのか？）などが書かれていません。本来はそれも含めて明記しておくべきです。質問文の記述では「こんなふんいき」という程度しか書かれておらずいくつかのケースでどう動くべきかの提示が漏れています。構造について（優先度が違うリストを接続すること）
なぜ優先度３のリストに優先度２のリストをつなげなければならないかの意義がわかりません。それがわからないのは、上に書いたように「エントリーを取り出す機能の詳細な動作仕様」を書ききれていないからだと思います。例えば「指定優先度のエントリーが存在してなければ次の優先度のエントリーを取り出す仕様」だったりするのでしょうか？
もしそうだとしても優先度が異なるリストを接続するかどうかはアルゴリズムの実装に依存することであって仕様ではないようにも思えます。リストを接続するのが「課題の条件＝仕様」であればそうしなければなりませんが、あなたがイメージした実装のようにも見えました。どちらなのかはっきりしないとアドバイスもしにくいと思います。
追記：
なんとなく仕様が想像できるようになりました。作成すべき機能をscehdule関数、それが管理するものをタスクと呼ぶことにすると・・・
- ディスパッチした後のタスクは優先度が高いものが高頻度でスケジュールされるようにする
- 優先度が高いものを高頻度で呼び出すための仕様は
2.1 sceduleの呼び出し毎に優先度2～1の先頭タスクだけ1つ上の優先度キューへ昇格させる
2.2 ディスパッチ後に最高優先度以外のタスクは自身の優先度キューへ戻す - schedule関数は1回の呼び出しで必ず1つのタスクを取り出す(そしてディスパッチする?)
- 2のキューの並べ替えをした上で3～1の中で空でない一番優先度の高いキューからタスクを取り出す
自分が質問者さんの説明をよく読んでれば最初からわかってたかもしれません。失礼しました。
上に書いたのは私なりに表現した仕様ですが、このとおりでよいならそれを素朴に実装できそうな気がします。実装にあたっては主としてキューを実現するところだけ若干面倒があるかも知れません。
- キュー
出来合いのクラスを利用するのでもかまわないなら簡単ですが、自前で実装するならキューの実現方法を理解しておく必要があります。もし曖昧なのであれば「アルゴリズム キュー」で検索してみると考え方や実装のサンプルが載っているものが見つかると思います。キューが先頭と末尾のエントリーを保持していて要素自体は双方向のチェーンでリンクされた構造や内部的に配列を用い双方向のリンクを必要としないリングバッファのようなものなどいくつかの考え方が見つかると思います。
いずれにせよ必要なのは「空かどうかの判定」「先頭からの取り出し」「末尾への追加」という３つの機能ですね。
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
15分調べてもわからないことは、teratailで質問しよう！
- ただいまの回答率 88.09%
- 質問をまとめることで、思考を整理して素早く解決
- テンプレート機能で、簡単に質問をまとめられる
2017/01/14 16:08
説明が拙くて申し訳ありませんでした。これは自分がイメージしている実装方法です。課題通りの動きができていれば、どのような仕様でもいいです。
課題としては、呼び出すデータは優先度3のキューにある一番先にいれたデータのみを呼びだします。もし、優先度3のキューにデータが入っていなければ、何も呼び出さずに、次の優先度2のキューを調べて、キューの先頭のデータを一つ上の優先度のキューの一番後ろに入れ、繰上げたデータはキューから削除するということを繰り返します。優先度2か1の優先度を呼び出した場合は、それらの元の優先度のキューの一番後ろに戻します。
自分が悩んでいるのは、優先度のついた構造体をそれぞれの優先度のキューに振り分けたのですが、それらをどのようにして、操作すると、このような機構ができるのかがわかりません。
また、これらの方法は自分がイメージしている実装なので、良い実装方法などがあればぜひ教えていただきたいです。