2 部データ構造とアルゴリズムI レポート課題

本講義では 2 通のレポートで評価します。 レポートは A4 の紙を縦に使い、適宜表紙を付けて提出すること。 またプログラムは C 言語で作成しなさい。

課題2

レポート締切日: 2014年7月16日(水)20:00
提出先: 2 号館 3F レポートボックス

なお、遅れレポートは原則受けとりません。

一行が高々200文字のテキストファイル input.txt に対して、 逆順に表示するプログラムを作成しなさい。 なお、行数の上限は仮定してはならない。 また、ファイルが存在しないとき、あるいはメモリーを確保できない時はそれ ぞれその旨のエラーメッセージを出力し、リターンコード -1, -2で異常終了しなさい。 なお、ファイル中に日本語が含まれる場合は正常に動作しなくてよい。

なお、プログラムの実行例として、次のケースすべてについて示しなさい。

  1. input.txt ファイルが存在しない時
  2. input.txt が空のファイルの時
  3. 作成したプログラムのソースコードをinput.txt として保存して与えた時

実行例

入力

abc
def
ghi

出力

ihg
fed
cba

課題1

レポート締切日: 2014年6月18日(水)20:00
提出先: 2 号館 3F レポートボックス

本課題では、 strcmp などの文字列関係の組み込み関数を使用してはい けない。 また、解答法として、分割コンパイルによる別ファイルにプログラムを書く方 法と、下記のテストプログラムに関数を追記する方法の二通りがあるがどちら でも良い。 プログラムの解説は、自分で作成した関数について行うこと。 こちらで提供したテストプログラムの説明は基本的には不要である。 但し、自分で作成した関数を説明するのに必要な内容には言及すること。

なお、遅れレポートは教員に直接提出してください。 遅れた方が有利にならない範囲内で採点します。

路線の駅までの所要時間を表わすため、構造体を次のように定義した。


typedef struct {
  char* name;
  int jikan;
} EKI;

また、これにより、路線の所要時間を表わす配列変数をグローバルに定義する。 但し、配列の最後には番兵として jikan が -1 となっているものを必ず入れるとする。


#include <stdlib.h>
#include "rosen.h"
EKI rosen[]={
    {"上野",0},
    {"日暮里",3},
    {"三河島",6},
    {"南千住",9},
    {"北千住",11},
    {"松戸",20},
    {"柏",28},
    {"我孫子",32},
    {"天王台",35},
    {"取手",39},
    {NULL,-1}};

なお、rosen.h は後述する。

課題1-1

EKI* 型の値(EKIのポインター)を受け取り、指す内容を[(名前): (時間)分]の書式 (丸括弧内はデータの値)で表示する void print_eki(EKI* eki) 関数を作りなさい。 但し、NULLが与えられた時は"[無効]"を表示しなさい。

そして、テストプログラム1と結合して正しく動作していることを確認しなさい。

テストプログラム1


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

int main(void){
  EKI* eki = rosen;
  while(eki->jikan!=-1){
    print_eki(eki);
    printf("\n");
    eki++;
  }
    print_eki(NULL);
    printf("\n");
  return 0;
}
出力例1
[上野: 0分]
[日暮里: 3分]
[三河島: 6分]
[南千住: 9分]
[北千住: 11分]
[松戸: 20分]
[柏: 28分]
[我孫子: 32分]
[天王台: 35分]
[取手: 39分]
[無効]

課題 1-2

二つの文字配列を受け取り、完全に一致している時は 1、そうでないときは 0 を返す int namematch(char* x, char* y) 関数を作りなさい。 なお、x, y のいずれかが NULL の場合は 0 を返しなさい。

そして、下記のテストプログラム2と結合して、正しく動作することを確かめなさい。

テストプログラム2


#include <stdio.h>
#include "rosen.h"
void printline(char* name){
  EKI* y=rosen;
    printf("%s\t",name);
    while(y->jikan!=-1){
      printf("%1d ",namematch(name,y->name));
      y++;
    }
    printf("%1d ",namematch(NULL,y->name));
    printf("\n");
}
int main(void){
  EKI* x = rosen;
  while(x->jikan!=-1){
    printline(x->name);
    x++;
  }
  printline(NULL);
  return 0;
}
出力例2
上野	1 0 0 0 0 0 0 0 0 0 0 
日暮里	0 1 0 0 0 0 0 0 0 0 0 
三河島	0 0 1 0 0 0 0 0 0 0 0 
南千住	0 0 0 1 0 0 0 0 0 0 0 
北千住	0 0 0 0 1 0 0 0 0 0 0 
松戸	0 0 0 0 0 1 0 0 0 0 0 
柏	0 0 0 0 0 0 1 0 0 0 0 
我孫子	0 0 0 0 0 0 0 1 0 0 0 
天王台	0 0 0 0 0 0 0 0 1 0 0 
取手	0 0 0 0 0 0 0 0 0 1 0 
(null)	0 0 0 0 0 0 0 0 0 0 0 

課題 1-3

駅の配列と文字配列を受け取って、文字配列の示す駅のポインタを返す EKI* find_eki(EKI* rosen, char* name) 関数を作成しなさい。 但し、見つからない場合は NULL を返しなさい。

そして次のテストプログラム3と結合して結果が正しいことを確認しなさい。

テストプログラム3


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

int main(void){
  EKI* x = rosen;
  char* test[]={"東京","千住","上野駅",NULL};
  char **p;
  while(x->jikan!=-1){
    print_eki(find_eki(rosen,x->name));
    printf("\n");
    x++;
  }
  p=test;
  while(*p!=NULL){
    print_eki(find_eki(rosen,*p));
    printf("\n");
    p++;
  }
  return 0;
}
出力例3
[上野: 0分]
[日暮里: 3分]
[三河島: 6分]
[南千住: 9分]
[北千住: 11分]
[松戸: 20分]
[柏: 28分]
[我孫子: 32分]
[天王台: 35分]
[取手: 39分]
[無効]
[無効]
[無効]

課題 1-4

駅の配列と二つの文字配列を与えると、二つの文字配列の示す駅間の所要時間を返す int distance(EKI* rosen, char* x, char* y) 関数を作りなさい。 但し、該当する駅が存在しない場合は -1 を返しなさい。

そして、テストプログラム4と結合して正しいことを確認しなさい。

テストプログラム4


#include <stdio.h>
#include <stdlib.h>
#include "rosen.h"
void printline(char* name){
  EKI* y=rosen;
  printf("%s\t",name);
  while(y->jikan!=-1){
    printf("%2d ",distance(rosen, name, y->name));
    y++;
  }
  printf("%2d ",distance(rosen, name, NULL));
  printf("\n");
}
int main(void){
  EKI* x = rosen;
  while(x->jikan!=-1){
    printline(x->name);
    x++;
  }
  printline(NULL);
  return 0;
}
出力例4
上野	 0  3  6  9 11 20 28 32 35 39 -1 
日暮里	 3  0  3  6  8 17 25 29 32 36 -1 
三河島	 6  3  0  3  5 14 22 26 29 33 -1 
南千住	 9  6  3  0  2 11 19 23 26 30 -1 
北千住	11  8  5  2  0  9 17 21 24 28 -1 
松戸	20 17 14 11  9  0  8 12 15 19 -1 
柏	28 25 22 19 17  8  0  4  7 11 -1 
我孫子	32 29 26 23 21 12  4  0  3  7 -1 
天王台	35 32 29 26 24 15  7  3  0  4 -1 
取手	39 36 33 30 28 19 11  7  4  0 -1 
(null)	-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 

rosen.hについて

rosen.h は次のように上記の構造体と作るべき関数のすべてのプロトタイプ 宣言が入っているファイルとする。


typedef struct {
  char* name;
  int jikan;
} EKI;
extern EKI rosen[];
void print_eki(EKI* eki);
int namematch(char* x, char* y);
EKI* find_eki(EKI* rosen, char* name);
int distance(EKI* rosen, char* x, char* y);

レポート作成上の注意

  1. レポートはグラフの表現など特殊な事情がない限り、必ず白黒で作成する こと。
  2. プログラミングのレポートでは必ずプログラムの説明をすること。その時 に、一行一行を日本語に直訳するのではなく、プログラムを機能毎に区分し、 機能の実現方法を説明すること。 プログラムに一行ずつコメントを入れてもプログラムの説明とは見なしません。
  3. 「問題を解きなさい」という問に対して「解きました。合ってました」は 正解ではありません。 「プログラムを作りなさい」という問題については、作成の手順の説明をする こと。 「テストしなさい」という問題についてはテストの手法、合否判定の基準、結 果の検討などを説明しなさい。
  4. プログラムが短くて説明がしづらい場合は、ポインタなどの関係を図示す るなどして工夫してください。
  5. 出力例は個々に異なりますので、手計算であらかじめ正しい値の求め方を 示し、値を提示してテストの合否を判定しなさい。
  6. レポートは手書きでも良いですが、プログラムの実行結果だけは必ずコン ピュータの出力の印刷にして下さい。
  7. 考察は必ず書いて下さい。ネタがない人は以下を参考にして下さい。

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科