練習 5(提出プログラム名:p1405a.c)※必須ではない
この問題は中級クラスの受講生は必須ではない(提出しなくてもよい)が,
上級クラスの受講生は必須とする.
なお,どちらのクラスであっても適切に正解すれば加点対象として扱う.
まず,このプログラム(p1405a.c)をダウンロードしなさい.
このプログラムの中では HEAP という構造体が定義されている.
この構造体は「データ構造とアルゴリズム」で習う簡単な「ヒープ」を表しており,
そこでは SIZE 個の整数を int 配列に格納するようになっている
(SIZE はマクロで定義されており,ヒープでは配列の添字 0 を使わないため +1 してある).
また,ヒープでは配列内に現在いくつの整数を格納しているかを把握しておく必要があるため,
構造体では count というメンバでこれを実現している.
このプログラムでは整数をいくつか読み込み,いったんすべてをヒープに格納した後,1 つずつヒープから取り出すことで整数を昇順に出力しようとしている.つまり,ヒープソートを簡易的に実現している.
以下の仕様で関数 append を完成させなさい.それ以外の関数は一切変更しないこと.
【関数 append】
引数 p はヒープを表す構造体のポインタであり,x はそのヒープに追加すべき整数である.
「データ構造とアルゴリズム」のテキストを参考にして,ヒープにデータを追加する関数として仕上げなさい.なお,この問題ではヒープ内での親子関係として親の方が小さな値を持つものとする.
- 【プログラムの実行例】(その1)※赤字は実行時にキーボードから入力する内容
いくつか整数を入力してください(-1 で終了):⏎ 8 1 7 4 6 2 -1 ヒープソートの結果:⏎ 1 2 4 6 7 8 ⏎
- 【プログラムの実行例】(その2)※赤字は実行時にキーボードから入力する内容
いくつか整数を入力してください(-1 で終了):⏎ 9 8 7 6 5 -1 ヒープソートの結果:⏎ 5 6 7 8 9 ⏎
【過去にあったミス(減点となり,やり直しを命じられる)】
■ 上に示した実行例を確認せずに提出してしまっている.
■ 別の関数(main や get_min)も書き換えてしまっている.
■ インデントに不備がある(VSCode 上でインデントを自動で揃える作業をやっていない).
第14回(Cプログラミング;3 限目の方)の練習問題は以上の5問です.
p1401a.c ~ p1405a.h を Moodle から提出してください.
※ただし,p1405a.c は必須ではないです.
くれぐれも各問題で記載されている注意事項や「過去にあったミス」を見落とさないようにしてください.
なお,コンパイルエラーや無限ループになるプログラムを 1 個でも提出した場合は総合評価を 0 点とするので十分に注意すること.
なお,提出後に間違いに気付いた場合,〆切前であれば差し替え(上書き)は可能です.