プログラミングＣ
第13回 演習問題

問題１
問題２ 問題３
問題４ 問題５

A問題(50点)

演習問題１（２次元配列の動的確保と文字列）

(提出ファイル名: prog01.c)

ハンドアウトLec13-6 (p.145）のサンプルプログラムlec13-4.cは2次元配列を動的に確保する方法の一例である。この方法はハンドアウトにあるとおり、行によって長さが違う場合にも応用ができる。この特徴を使って、各行に単語を一つづつ格納し、かつ各行の長さはその単語の長さちょうどになるような2次元配列を作成するプログラムを完成させよ。

以下に、このプログラムを完成させる際の考え方を列挙する

サンプルデータとして、aizu1.txt, aizu2.txtを 用意してあるので、必要なら、自分のディレクトリにコピーすること。 

% cp /home/course/prog1/public_html/2024/ex/ex13/aizu*.txt .



実行例：
% ./a.out
to Advance Knowledge for Humanity
control+d
 0: to [2]
 1: Advance [7]
 2: Knowledge [9]
 3: for [3]
 4: Humanity [8]
% cat aizu1.txt
The University of Aizu opened in 1993 and was the first university in Japan to specialize in computer science and engineering.
% ./a.out < aizu1.txt
 0: The [3]
 1: University [10]
 2: of [2]
 3: Aizu [4]
 4: opened [6]
 5: in [2]
 6: 1993 [4]
     :
     :
  以下省略
% ./a.out < aizu2.txt
 0: In [2]
 1: the [3]
 2: Edo [3]
 3: era, [4]
 4: the [3]
 5: Aizu [4]
 6: region [6]
     :
     :
  以下省略
%

ハンドアウトに掲載されているサンプルプログラムでは、malloc関数の戻り値を、
arr[i] = (int *)malloc(yoko * sizeof(int));
のように代入先の変数型に合うようにキャストしている。 一方、lec13-4.cの中ではそのようなキャストを行わず、 
arr[i] = malloc(sizeof(int)*yoko);
のようにそのまま代入している。
malloc関数のプロトタイプ宣言を確認（コマンドman mallocで確認できる）すると、 
void *malloc(size_t size);
となっている。void *型は、明示的にキャストをする必要なく任意のポインタ型に変換することができるので、本来はハンドアウトの掲載例のようなキャストを行う必要はなく、lec13-4.cのように書いて問題ない。
ハンドアウトの掲載例のような明示的なキャストを行うことの利点は、malloc関数で確保しようとしている領域の大きさが適切かどうかをコンパイラが確認し、問題がある（意図しない動作をしたり、セキュリティホールの原因となることもある）場合は警告が出せるようになることである。このようなプログラムの書き方についての詳細はコンピュータのセキュリティに関する情報を取りまとめているJPCERT/CCの記事などが参考になる。

B問題(50点)

演習問題２

問題１の続き
問題１のプログラムは標準入力から入力された単語を 適切なサイズの文字配列を確保しつつ格納するものであった。 問題２では、単語の頻度（出現回数）も記録するようにし、 重複した単語があった場合は頻度情報を更新するようなプログラムに 変更する。

(提出ファイル名: prog02.c)

具体的な手順は以下の通り
str[]は保持済みの単語、nは登録済み単語数、cnt[]は単語の頻度とする。

１、１単語を読み込む。EOFならループ脱出。
２、読み込んだ文字列を全て小文字に統一し、",.（カンマ、ピリオド）"を 含まない形に変換する。 この変換を行う関数void lconv(char *)は自分で作成すること。
　　この関数では、引数で与えられた文字列内の 大文字を小文字に変換すると共に",.(カンマ、ピリオド）"の場合は ヌル文字で置き換える処理を行なう。
３、登録済みの単語と同じものがあるか探索する。
４、同じものがあった場合、該当する単語の頻度に１加算。
５、無かった場合、入力文字を格納するための領域確保し、内容をstr[n]にコピー。
　　該当する単語頻度を１に設定（１個目が登録されたので）。nをインクリメント。
６、１に戻る。
７、結果を表示し、プログラムを終了する。

実行例：
%  ./a.out < aizu1.txt
 0: the [3](2)
 1: university [10](2)
 2: of [2](1)
 3: aizu [4](1)
 4: opened [6](1)
 5: in [2](3)
 6: 1993 [4](1)
 7: and [3](2)
 8: was [3](1)
 9: first [5](1)
10: japan [5](1)
11: to [2](1)
12: specialize [10](1)
13: computer [8](1)
14: science [7](1)
15: engineering [11](1)
%

演習問題３

最初に、ハンドアウト lec13-11,12 (p146) 中のプログラムlec13-7.cをコピーし、lec13-13 (p147) に示されたコンパイルオプションをつけた場合に例示された通りの動作になることを確認せよ。

まず、以下のコマンドで画像データを自分のディレクトリにコピーすること。 

% cp /home/course/prog1/public_html/2024/ex/ex13/pbms/* .

次にlec13-7.cを以下のようにコンパイルオプションでマクロ定義を変えてコンパイルし、Lec13-13に例示されている四種類の実行ファイルを生成する。 

% gcc lec13-7.c -DINV -o inv
% gcc lec13-7.c -DINV -DROTL -o invrotl
% gcc lec13-7.c -DFLIPLR -o fliplr
% gcc lec13-7.c -DINV -DFLIPLR -DROTL -o invfliplrrotl

コピーした画像データを使って、Lec13-13に載っている通りの動作をするかを確認する。 

% cat p1.pbm | ./inv | display - 
% cat p1.pbm | ./invrotl | display - 
% cat p1.pbm | ./fliplr | display - 
% cat p1.pbm | ./invfliplrrotl | display -

確認が完了したら、以下の説明をよく読んで問題に取り組むこと。

テンプレートprog03_template.cはlec13-7.cを再設計し、メモリの確保と画像データの読み込みを別々の関数に分離している。 また、lec13-7.cが備えていた画像処理の機能に代えて、 読み込んだ画像に対し指定した正方形内の白黒を反転させてから出力する機能を追加した。 ただし、いくつかの関数は未完成のままになっている。 このテンプレートを元に、２ステップでプログラムを完成させよ。

(提出ファイル名: prog03a.c, prog03b.c)

各関数の内容は以下のとおりである。未完成、完成の別も表示している。未完成の関数は完成させること。完成済みの関数は変更してはならない。


ステップ１: テンプレートをprog3a.cにコピーして、 img_allocとimg_readを実装（作成）する。
　　このとき、img_squareとimg_xdotには何も追加しない。
　　ステップ１が完成した時点で、実行例のように実行してみると、 元の画像が表示されるはずである。
　　これで、img_alloc, img_readが正しく動作しているかが確認できる。
ステップ２: prog03a.cをprog03b.cにコピーし、prog03b.c内のimg_squareとimg_xdotを実装し、 最終的な結果になることを確認する。

char **img_alloc(int x, int y)
（未完成）大きさx×yのchar型の2次元配列を確保しそのアドレスを返す。領域の確保に失敗したら、 それまでにこの関数で確保した領域を解放し、NULLを返す。
完成済みimg_freeとの整合を取るように、 ハンドアウトP145の「動的確保（３）」の方法を使って下さい。
void img_free(char **pbm, int x, int y)
（完成済み）大きさx×yの2次元配列pbmを解放する。引数 x,y はここでは使用されていないが、他の関数と整合性を とるために入れてある。
void img_write(char **pbm, int x, int y)
（完成済み）大きさx×yのchar型の2次元配列をPBM画像として出力する。2次元配列の要素には'1'か'0'（それぞれ黒、白の画素に対応）が 入っていると仮定している。
char **img_read(int *x, int *y)
（未完成）この関数はまず、標準入力から入力されたPBM形式のヘッダと画像の大きさを読み取り、 その画像を格納できるchar型の２次元配列を確保する。
続いて標準入力から入力される画素値を読み取り、確保した２次元配列に格納する。
PBM形式では、画像データ部分に余分な空行、空白を入れてよいことになっている。このような場合でも scanf関数のフォーマット指示子" %c"（"(空白文字)%c", %cの前にスペースを入れる） を用いることでこれを読み飛ばせるので、この通り実装して空行、空白の有無に関わらず正しくデータを読み取れるようにすること。
最後に入力されたx,yのポインタが示す変数に画像の横幅と高さを代入し、 確保した2次元配列のポインタを返す。
この関数を作る際、画像の入力の処理はlec13-7.cを参考にすると良いが、 img_read関数内での２次元配列の確保はmalloc関数を直接呼び出さず、 上のimg_alloc関数を用いて関数を作成すること。
また、読み込みに失敗した場合は、エラーメッセージを表示せず、 それまでにこの関数で確保したメモリ領域を解放し、NULLを返すようにせよ。
void img_square(char **pbm, int x, int y, int cx, int cy, int d)
（未完成）大きさx×yの画像pbmに、中心点(cx, cy)で半辺長（一辺の長さの半分）dの正方形内を白黒反転する。実際の点の描画はimg_xdot関数を利用する。
void img_xdot(char **pbm, int x, int y, int px, int py)
（未完成）大きさx×yの画像pbmの 点(px, py)が画像範囲内であれば、この点を白黒反転する（lec13-7.c参照）。 この関数内で画像範囲内かを判定するので、img_square関数内の処理が 簡単になる。
int main(int argc, char *argv[])
（完成済み）上の関数を使い、データ処理の全体制御を行う。コマンドライン引数としてimg_square関数で描画する正方形の中心座標と半辺長（一辺の長さの半分）を受け取る。

テンプレートはそのままコンパイルが出来るように作ってあるので、ダウンロードしたらまずコンパイルしてみるとよい。 ただし、未完成の関数を埋めない限り、例の通りに動作するわけではない。 まずはテンプレートをファイル名prog03a.cにコピーして、 変更を進めること。 変更の際は、少しずつ処理を足しながらこまめにコンパイルして いくことで、文法の誤りを早く見つけることが出来るはずである。

ステップ１の実行例：（コマンドライン引数の数値はステップ１では実質的に利用してないので、何でも良い。）
% cat p1.pbm | ./a.out 300 200 100 | display -





ステップ２の実行例：
% cat p1.pbm | ./a.out 300 200 100 | display -



% cat p1.pbm | ./a.out 140 200 100 | ./a.out 200 300 80 |display -


%

確認のため、他の画像でも同様に実行してみること。


Extra問題

演習問題4

(提出ファイル名: prog04.c)

問題3を応用し、別の画像処理を行なうプログラムを作成する。 下記に、この問題で使用するヘッダファイル、マクロ定数、関数のプロトタイプ 宣言を示す。関数定義は、問題3までの関数の中から必要なものを コピーして使用する。 

#include <stdio.h>
#include <stdlib.h>

#define BLACK '1'
#define WHITE '0'

char **img_alloc(int, int);
void   img_free(char **,int, int);
char **img_read(int *, int *);
void   img_write(char **, int, int);
本問題では白黒２値画像に対してモルフォロジと呼ばれる処理の一部を作成する。 これから作る処理は、画像上の画素一つを取り出してP(x,y)とするとき、 その周辺の画素値を読み出し、それらの値に対してある演算を行い。 その結果を新たな画像の画素P'(x,y)とするものである。 この処理は、画像上の画素すべてに対して１回ずつ行う。 下図は注目する画素の「周辺」の定義を、注目する画素の上下左右としたときの説明図である。

このとき、大きさW×Hの画像内の点P(x,y)に注目するとすると、 座標値x=0となる点、x=W-1となる点、y=0となる点、y=H-1となる点の 周辺画素は画像をはみ出したところに位置してしまう。 画像の上下左右の端の画素に注目する際、参照できない周辺画素は、 その注目する画素の値を用いることとする。

注目している画素とその周辺の画素の値を計算して、新たな画像の画素の値を決めるわけだが、 この計算方法によって画像処理の性質が決まる。ここでは、モルフォロジ処理の中から、黒い点に対しての2種類の処理をつくろう。

名前発音意味操作
erosionエロージョン収縮注目する画素とその周辺の画素が全て黒なら結果を黒に、それ以外は白にする
dilationダイレーション膨張注目する画素とその周辺の画素が一つでも黒なら結果を黒に、それ以外は白にする

エロージョンは黒い線や領域を細く，ダイレーションは太くする効果がある。白黒２値画像に２つの処理を適用した結果を下に示す。

エロージョン 元画像 ダイレーション

それでは、実際にこれらの処理を行う関数を作成していく。 関数名には動詞のerodeとdilateを使ったほうが良いので以下のように定義する。 

char **img_erode(char **pbm, int x, int y);  /* エロージョンを行う関数 */
char **img_dilate(char **pbm, int x, int y); /* ダイレーションを行う関数 */
pbmは入力する画像の配列。x,yは画像の横幅と高さである。 関数の中で入力する画像と同じ大きさの２次元配列をimg_alloc関数で確保し、 その配列に結果を書き込む。操作を行ったあとは新しい配列のポインタを返すように作る。 各関数の中身は以下のように作成せよ。

画像の端の処理、 ループの範囲の設定(横は0からx-1、縦は0からy-1の範囲である)、 論理演算等を間違えやすいので気をつけること。

作成した関数を呼び出すようにしたmain関数を示すので、これを用いよ。 #elifは、#elseと#ifdefが複合したもので、 C言語での「else if」に相当する。 ここに作成した2つの関数を入れ、コンパイル時にERODEかDILATEを定義し、 どちらの関数を呼ぶかを決定する。 

int main(){
  char **pbm1, **pbm2;
  int ix,iy;

  pbm1 = img_read(&ix,&iy);
  if(pbm1==NULL){
    fprintf(stderr,"Invalid image format.");
    exit(1);
  }

  #ifdef ERODE
  pbm2=img_erode(pbm1,ix,iy);
  img_free(pbm1,ix,iy);
  #elif DILATE
  pbm2=img_dilate(pbm1,ix,iy);
  img_free(pbm1,ix,iy);
  #else
  pbm2=pbm1;
  #endif

  /* 画像を書きだす */
  img_write(pbm2,ix,iy);
  /* 画像領域の解放 */
  img_free(pbm2,ix,iy);
  return 0;
}
最後にコンパイルと実行の例を示す。-Dオプションは定義するマクロ名の指定、 -oオプションは生成されるファイルの名前を指定するオプションである。 
実行例：
%  gcc prog04.c -DERODE -o erode 
%  gcc prog04.c -DDILATE -o dilate 
%  cat p1.pbm | ./erode | display - 

%  cat p1.pbm | ./dilate | display -

演習問題5

(提出ファイル名: prog05.c)

この問題は、問題4の続きである。

問題4で作成したエロージョンとダイレーションの処理は、複数回繰り返すことで より効果を大きく出すことができる。 また、エロージョンの後にダイレーションを行うとオープニングという演算になり、 孤立点や細い線の除去ができる。逆、つまり、ダイレーションの後にエロージョンを行うと クロージングという演算になり、不連続な点の接続と穴埋めができる。

以下に、例を挙げる

% cat ryo.pbm | ./erode | ./erode | display - % cat ryo.pbm | ./dilate | ./dilate | display -
% cat ryo.pbm | ./erode | ./dilate | display - % cat ryo.pbm | ./dilate | ./erode | display -

エロージョンとダイレーションを繰り返せば、白黒画像の画質をいろいろと調整することができるが、 コマンドの連結で表現するのは少し大変である。そこで、コマンドライン引数でエロージョンと ダイレーションの処理をどの順序で行うのかを与えることにしよう。ついでに、コマンドライン引数に ファイル名が与えられたら、標準入力ではなく、そのファイルから画像データを取得するようにする。 例えば、実行ファイル名をmorphとして以下のような利用方法を想定する。 

実行例：
% ./morph - ryo.pbm | display -

% ./morph -eeeddd ryo.pbm | display -

% cat ryo.pbm | ./morph -dddddeeeee | display -

% ./morph ryo.pbm
Error: Invalid operation 'r'
Usage: ./morph -[ed...] [filename]
% ./morph -cde ryo.pbm
Error: Invalid operation 'c'
実行ファイル名の後に、第1引数としてハイフンの後にeとdで構成された文字列を与える。これが、eがエロージョン、 dがダイレーションの処理を行うことを表す。ハイフンのみの場合は、処理をせずに入力画像を そのまま出力する。また、第2引数として文字列が存在すれば、 それをファイル名として画像を読み込むようにする。出力は前回までと変わらず、標準出力に 出力することとする。以下のリストを参考にして、プログラムを完成させよ。 
// プロトタイプ宣言とmainのおおよその流れ
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BLACK '1'
#define WHITE '0'

char **img_alloc(int, int);
void   img_free(char **,int, int);
void   img_write(char **, int, int);
char **img_read(FILE *, int *x, int *y); /* 要変更 */
char **img_dilate(char **pbm, int x, int y);
char **img_erode(char **pbm, int x, int y);
//（外部変数は使用しない）

int main(int argc, char *argv[])
{
//  （変数宣言）

//  （コマンドライン解析）

//  （行うべき処理が指定されていない場合はエラー）

//  （ファイルが指定されていない場合はstdinを、それ以外はファイルをopenし
//  　ファイルポインタを得て、img_read関数の引数とする）

//  （指定された処理の実行：複数指定された場合は処理の繰返し。
//  　img_dilate, img_erode関数を繰り返し呼ぶと、メモリの解放が必要になる。）

//  （最後に結果の出力）

//  （メモリの解放）

  return 0;
}

//（各関数の記述）

[ Last Updated: 2024年10月25日 by Programming C teaching group]