質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

1回答

2319閲覧

c言語でのリストを用いた課題

peachkun

総合スコア20

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

0クリップ

投稿2017/01/12 13:39

編集2017/01/12 13:41

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などを用いて先頭から取り出していきたいのですが、どのようにすれば良いかいまいちわかりません。

なにか良い方法がございましたら、ぜひ教えてください。よろしくお願いします。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

なにか良い方法

プログラム全体の説明をするのは大切ですが、質問の際に重要なのは実現するのにあたり自分が悩んでいるポイントを明らかにすることです。どのあたりの実現が難しいと感じているのか明記しないことには「このプログラム全体の作り方がわからない」ようにも見えてしまいます。これが書かれていないので読者には「何が難しいのかわからないためアドバイスが難しい」質問になっています。

なお、仕様を詳しく説明しようとはしておられますが今一つ明確なアルゴリズムの説明になっていないように思います。印象としてはプロセスのスケジューリングを優先度付きラウンドロビンで行うためのキュー構造とキューからの取り出しのようなものが題材のように見えましたが・・・

  • エントリーを取り出す機能の詳細な動作仕様

「優先度を指定してエントリーを取り出す」もののようですが、その優先度のエントリーがなかった場合はどうするか(あるいはそういう条件とならないことがあらかじめ保証されているのか?)などが書かれていません。本来はそれも含めて明記しておくべきです。質問文の記述では「こんなふんいき」という程度しか書かれておらずいくつかのケースでどう動くべきかの提示が漏れています。

  • 構造について(優先度が違うリストを接続すること)

なぜ優先度3のリストに優先度2のリストをつなげなければならないかの意義がわかりません。それがわからないのは、上に書いたように「エントリーを取り出す機能の詳細な動作仕様」を書ききれていないからだと思います。例えば「指定優先度のエントリーが存在してなければ次の優先度のエントリーを取り出す仕様」だったりするのでしょうか?
もしそうだとしても優先度が異なるリストを接続するかどうかはアルゴリズムの実装に依存することであって仕様ではないようにも思えます。リストを接続するのが「課題の条件=仕様」であればそうしなければなりませんが、あなたがイメージした実装のようにも見えました。どちらなのかはっきりしないとアドバイスもしにくいと思います。


追記:
なんとなく仕様が想像できるようになりました。作成すべき機能をscehdule関数、それが管理するものをタスクと呼ぶことにすると・・・

  1. ディスパッチした後のタスクは優先度が高いものが高頻度でスケジュールされるようにする
  2. 優先度が高いものを高頻度で呼び出すための仕様は

2.1 sceduleの呼び出し毎に優先度2~1の先頭タスクだけ1つ上の優先度キューへ昇格させる
2.2 ディスパッチ後に最高優先度以外のタスクは自身の優先度キューへ戻す

  1. schedule関数は1回の呼び出しで必ず1つのタスクを取り出す(そしてディスパッチする?)
  2. 2のキューの並べ替えをした上で3~1の中で空でない一番優先度の高いキューからタスクを取り出す

自分が質問者さんの説明をよく読んでれば最初からわかってたかもしれません。失礼しました。
上に書いたのは私なりに表現した仕様ですが、このとおりでよいならそれを素朴に実装できそうな気がします。実装にあたっては主としてキューを実現するところだけ若干面倒があるかも知れません。

  • キュー

出来合いのクラスを利用するのでもかまわないなら簡単ですが、自前で実装するならキューの実現方法を理解しておく必要があります。もし曖昧なのであれば「アルゴリズム キュー」で検索してみると考え方や実装のサンプルが載っているものが見つかると思います。キューが先頭と末尾のエントリーを保持していて要素自体は双方向のチェーンでリンクされた構造や内部的に配列を用い双方向のリンクを必要としないリングバッファのようなものなどいくつかの考え方が見つかると思います。
いずれにせよ必要なのは「空かどうかの判定」「先頭からの取り出し」「末尾への追加」という3つの機能ですね。

投稿2017/01/12 23:48

編集2017/01/14 08:21
KSwordOfHaste

総合スコア18392

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

peachkun

2017/01/14 07:08

回答ありがとうございます。 説明が拙くて申し訳ありませんでした。これは自分がイメージしている実装方法です。課題通りの動きができていれば、どのような仕様でもいいです。 課題としては、呼び出すデータは優先度3のキューにある一番先にいれたデータのみを呼びだします。もし、優先度3のキューにデータが入っていなければ、何も呼び出さずに、次の優先度2のキューを調べて、キューの先頭のデータを一つ上の優先度のキューの一番後ろに入れ、繰上げたデータはキューから削除するということを繰り返します。優先度2か1の優先度を呼び出した場合は、それらの元の優先度のキューの一番後ろに戻します。 自分が悩んでいるのは、優先度のついた構造体をそれぞれの優先度のキューに振り分けたのですが、それらをどのようにして、操作すると、このような機構ができるのかがわかりません。 また、これらの方法は自分がイメージしている実装なので、良い実装方法などがあればぜひ教えていただきたいです。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問