プログラミング応用演習 第 5 回演習
前回までのお話 ポインタ ポインタを用いた文字列処理 構造体 ファイル 再帰的構造体 リスト構造 動的メモリ管理
今日のお題 ポインタやファイルなど これまでの内容の練習
教材 以前 以下に単語を収録したファイルがあることを紹介した : /usr/share/dict/words この中からランダムに単語を取り出したファイルを用意した http://sun.ac.jp/prof/yamagu/2019app/ の今日の日付のあたり ( いつものように tar+gz で固めてあるので適宜展開すること ) 以下 これらを 辞書ファイル と呼ぶ
問 1 辞書ファイルの行数 ( 復習 +α) 辞書ファイルの行数を数えるプログラムを 書きなさい 昨年のプログラミング基礎演習第 10 回を参照 http://sun.ac.jp/prof/yamagu/2018fpp/ 辞書ファイルはコマンドライン引数から指定できるようにすること ( 以降の問でも同様とする ) 実行例 ) $./a.out /usr/share/dict/words 99171 ) 辞書ファイルの場合 行数は収録されている単語数に等しい
辞書ファイルの読み込み readdict.c #include <stdio.h> #include <stdlib.h> typedef struct { unsigned char s[24]; } word; int main(int argc, char **argv) { word dict[100000]; FILE *fp; int i,c,k; if (argc < 2) { fprintf(stderr,"usage:./a.out dictfile\n"); exit(1); } if ((fp=fopen(argv[1],"r")) == NULL) { fprintf(stderr,"cannot open file %s\n",argv[1]); exit(1); } i=0; k=0; while((c=fgetc(fp))!= EOF) { if (c == '\n') { dict[i].s[k] = 0; i++; k=0; } else { dict[i].s[k] = c; k++; } } fclose(fp); printf("%s\n",dict[0].s); printf("%s\n",dict[i-1].s); return 0; 単語を覚えておくための構造体 word word の配列 辞書を覚えておく i 番目の単語の k 番目の文字 改行を読んだら 単語の終端にヌル文字を入れ i を増やし k を 0 にする 試しに最初と最後の 最大 23 文字と分かっているので 最後のヌル文字を入れて大きさ 24 で充分 全部で 99171 行と分かっているので 大きさ 10 万あれば充分 } 単語を表示
問 2 単語の取り出し 正整数値 n を入力すると コマンドラインに与えた辞書ファイルの n 行目の単語を表示するプログラムを書きなさい 実行例 ) $./a.out /usr/share/dict/words 72833 program $./a.out words10 5 grape ここでは行の番号を 1 から数えている 配列の添え字は 0 からなので 注意すること $
問 3 単語の取り出し 2 問 2 と同様の単語取り出しを 標準入力が閉じるまで繰り返すプログラムを書きなさい 実行例 ) $./a.out /usr/share/dict/words 72833 program 1 A 10675 Nagasaki ^D $ Ctrl を押しながら D を入れると 標準入力を閉じる
実行結果の確認 diff コマンド : 二つの入力の異なる部分を出力する 問 3 への入力 ( 数値の列 ) 例と それに対応する正解をファイルにしてある ( 辞書ファイルごとに一つずつ ) 入力例をリダイレクトで流し込み その出力を正解と比較する 実行例 ) $./a.out words10 < toi3-10.prb diff - toi3-10.ans $ 何も表示されずに終了すれば a.out の出力が正解ファイルの中身と同一である
文字列の比較 メモリ上の異なる位置に 同じ内容のデータが記憶されている H e l l o \0 H e l l o \0 中身が同じでも ポインタ値が違うことがある ) ポインタが同じ場合は 同じ文字列である ポインタが異なっても 同じ文字列である可能性がある
文字列比較の注意点 : 多バイト文字 char は 8bit:-128~127の整数値を表す utf8 では top bit が 0 なら 1バイトの文字 ASCII コードだと思ってよい utf8 で top bit が 1 の場合は多バイト文字例 )é は 11000011 10101001 の2バイト文字 é と A (01000001) を比較すると? 11000011 を -87 だと思えば é の方が小さい 11000011 を 169 だと思えば A の方が小さい辞書ファイル内の単語は文字コード順に並んでいる 多バイト文字を扱うときは unsigned char を使う
文字列を比較するプログラム例 標準入力から入力された文字列が Hello であれば Hello と出力し それ以外の文字列であれば Good bye と出力するプログラム : compare.c #include <stdio.h> int main() { unsigned char *h = "Hello"; unsigned char s[10], *p, *r; fgets(s,10,stdin); for(p=s ; *p!= 0 ; p++) { } if (*p == '\n') *p=0; // s に文字列を入力 // s の中に改行文字があれば消しておく } p=s; r=h; // p は入力文字列を r は比較対象 ("Hello") を先頭から順に指す while( (*p == *r) && (*p!= 0) && (*r!= 0) ) { // 同じ文字が入っていて どちらも終端に至ってない p++; r++; // p と r の両方を進める } if ((*p == 0) && (*r == 0)) { printf("hello\n"); } else { printf("good bye\n"); } return 0; // p と r の両方が終端なら s と h は同じ文字列
文字列の比較 s p H e l l o \0 h r H e l l o \0
問 4 単語の検索 標準入力から単語を入力すると その単語が辞書ファイルの何行目にあるかを出力するプログラムを書きなさい 辞書ファイルに収録されていない単語が入力されたときは -1 を出力するものとする 実行例 ) $./a.out /usr/share/dict/words A 1 $ A を入力すると A は 1 行目にあると出力される
問 5 単語の検索 2 問 4 と同様の単語検索を 標準入力が閉じるまで繰り返すプログラムを書きなさい 実行例 ) $./a.out /usr/share/dict/words A 1 program 72833 foo -1 ^D $ foo は辞書にない Ctrl を押しながら D を入れると 標準入力を閉じる
実行結果の確認 問 5 への入力 ( 数値の列 ) 例と それに対応する正解をファイルにしてある ( 辞書ファイルごとに一つずつ ) 入力例をリダイレクトで流し込み その出力を正解と比較する 実行例 ) $./a.out words100 < toi5-100.prb diff - toi5-100.ans $ 何も表示されずに終了すれば a.out の出力が正解ファイルの中身と同一である )toi5-all.prb と toi5-all.ans は元々の辞書ファイルへの入力例および正解 これを実行すると 時間がかかるかも知れない
問 6 単語の検索 3 問 5 と同様の単語検索を 辞書の単語をリスト構造に入れておくやり方で実現してみよう 行番号 単語 次のセルへのポインタ typedef struct _wordcell { int line; char str[24]; struct _wordcell *next; } wordcell; 99171 études 99170 étude's 99169 étude 99168 épées
次回予告 二分探索