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

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

課題2

課題2-1の実行例が間違っていましたので、訂正しました(2015/7/13)

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

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

時間を表わすため、構造体を次のように定義した。


typedef struct {
  int hour;
  int minute;
  int second;
} JIKAN;

なお、jikan.h や、他に必要な関数は後述する。

課題2-1

時間の大小関係を比較する int compare(JIKAN* a, JIKAN* b) を作成しなさい。ただし、これは a,b とも JIKAN 型の変数を指すポインターで、 *a < *b の時は負の整数、 *a == *b の時は0、 *a > *b の時は正の整数を返しなさい。

なお、以下のプログラムと結合してテストを行い、実行結果を示しなさい。

テストプログラム


#include <stdio.h>
#include "jikan.h"
int main(void){
  JIKAN jikan[]={{1,2,3},{1,2,2},{1,4,3},{2,2,3}};
  int arraysize = sizeof(jikan) / sizeof(JIKAN);
  int i;
  int j;
  for(j=0;j<arraysize;j++){
    printf("\t");
    print(jikan+j);
  }
  printf("\n");
  for(i=0;i<arraysize;i++){
    print(jikan+i);
    for(j=0;j<arraysize;j++){
      printf("\t%d",compare(jikan+i,jikan+j));
    }
    printf("\n");
  }
  return 0;
}

実行例(正)

	1:2:3	1:2:2	1:4:3	2:2:3
1:2:3	0	1	-2	-1
1:2:2	-1	0	-2	-1
1:4:3	2	2	0	-1
2:2:3	1	1	1	0

実行例(誤)

~~1:2:3 1:2:2 1:4:3 2:2:3 1:2:3 0 -1 2 1 1:2:2 1 0 2 1 1:4:3 -2 -2 0 1 2:2:3 -1 -1 -1 0~~

なお、compare 関数では返す整数の符号が一致していれば良く、実行例で示した整数値と一致する必要はない。

課題2-2

JIKAN* を含む線形リストを作成するために、次の構造体を定義した。


typedef struct list {
  JIKAN* jikan;
  struct list*  next;
}LIST;

この構造体で作られた線形リストのJIKANを \t で区切って表示する関数 void printlist(LIST* l) を作成しなさい。但し、後に示す void print(JIKAN* j) を使用してよい。また、先頭に \t が来ても構わない（以下実行例では先頭に\tが来ている）。そして、以下のテストプログラムと結合して、テスト結果を示しなさい。

テストプログラム


#include <stdio.h>
#include <stdlib.h>
#include "jikan.h"
int main(void){
  JIKAN jikan[]={{1,2,3},{1,2,2},{1,4,3},{2,2,3}};
  LIST lnull={NULL,NULL};
  LIST l3={jikan+3,&lnull};
  LIST l2={jikan+2,&l3};
  LIST l1={jikan+1,&l2};
  LIST l0={jikan,&l1};

  printlist(&l0);
  printf("\n");
  printlist(&l1);
  printf("\n");
  printlist(&l2);
  printf("\n");
  printlist(&l3);
  printf("\n");
  printlist(&lnull);
  printf("\n");
  return 0;
}

実行例

	1:2:3	1:2:2	1:4:3	2:2:3
	1:2:2	1:4:3	2:2:3
	1:4:3	2:2:3
	2:2:3

課題2-3

JIKAN のポインター now と JIKAN の線形リストの先頭を指すポインターから、与えた時間 *now より長い時間のみからなる新たな線形リストを返す関数 LIST* longtimelist(JIKAN* now, LIST* l) を作成しなさい。但し、後に示す関数を使用してよい。そして、以下のテストプログラムと結合して、テスト結果を示しなさい。

テストプログラム


#include <stdio.h>
#include <stdlib.h>
#include "jikan.h"
int main(void){
  int i;
  JIKAN jikan[]={{1,2,3},{1,2,2},{1,4,3},{2,2,3}};
  int arraysize = sizeof(jikan) / sizeof(JIKAN);
  LIST lnull={NULL,NULL};
  LIST l3={jikan+3,&lnull};
  LIST l2={jikan+2,&l3};
  LIST l1={jikan+1,&l2};
  LIST l0={jikan,&l1};
  LIST* p;

  for(i=0; i<arraysize; i++){
    print(jikan+i);
    printf("\t<");
    p=longtimelist(jikan+i,&l0);
    printlist(p);
    printf("\n");
    freelist(p);
  }
  return 0;
}

実行例

1:2:3	<	1:4:3	2:2:3
1:2:2	<	1:2:3	1:4:3	2:2:3
1:4:3	<	2:2:3
2:2:3	<

jikan.h


typedef struct {
  int hour;
  int minute;
  int second;
} JIKAN;
typedef struct list {
  JIKAN* jikan;
  struct list*  next;
}LIST;
void print(JIKAN* v);
void add(JIKAN* v,JIKAN* w);
void normalize(JIKAN* v);
int compare(JIKAN* a, JIKAN* b);
void printlist(LIST* l);
JIKAN* dupjikan(JIKAN* j);
LIST* newlist();
void freelist(LIST* l);
LIST* duplist(LIST* l);
LIST* longtimelist(JIKAN* now, LIST* l);

利用可能な関数


#include <stdio.h>
#include <stdlib.h>
#include "jikan.h"
void print(JIKAN* j){
  printf("%d:%d:%d",j->hour,j->minute,j->second);
}
JIKAN* dupjikan(JIKAN* j){
  JIKAN* result = malloc(sizeof(JIKAN));
  if(result !=NULL){
    result->hour = j->hour;
    result->minute = j->minute;
    result->second = j->second;
  }
  return result;
}
LIST* newlist(){
  LIST* result = malloc(sizeof(LIST));
  if(result!=NULL){
    result->jikan= NULL;
    result->next = NULL;
  }
  return result;
}
void freelist(LIST* l){
  if(l->next != NULL){
    freelist(l->next);
  }
  if(l->jikan != NULL){
    free(l->jikan);
  }
  free(l);
}
LIST* duplist(LIST* l){
  LIST* result=newlist();
  LIST* p;
  if(result==NULL) return NULL;
  for(p=result; l->next!=NULL; l = l->next){
    if((p->jikan = dupjikan(l->jikan))==NULL){
      freelist(result);
      return NULL;
    }
    if((p->next = newlist())==NULL){
      freelist(result);
      return NULL;
    }
    p = p->next;
  }
  return result;
}

レポート作成上の注意

レポートには自ら作成した関数の説明をし、テストプログラムと結合して実行した結果を載せること。

課題1

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

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

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

問題

時間を表わすため、構造体を次のように定義した。


typedef struct {
  int hour;
  int minute;
  int second;
} JIKAN;

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

課題1-1

JIKAN 型の変数のポインターを受け取り、「hour:minute:second」の書式で表示する void print(JIKAN* j) 関数を作りなさい。

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

テストプログラム1


#include <stdio.h>
#include "jikan.h"

int main(void){
  JIKAN j[]={{12,34,56},{1,60,60},{100,58,120},{-1,-1,-1}};
  JIKAN* p;
  for(p=j; p->hour!=-1; p++){
    print(p);
    printf("\n");
  }
  return 0;
}

出力例1

12:34:56
1:60:60
100:58:120

課題 1-2

JIKAN型の変数のポインターを二つ受け取り、1番目の変数に2番目の変数の値を足し込む void add(JIKAN* v, JIKAN* w) 関数を作りなさい。

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

テストプログラム2


#include <stdio.h>
#include <stdlib.h>
#include "jikan.h"
int main(void){
  JIKAN j[]={{12,34,56},{1,60,60},{100,58,120},{-1,-1,-1}};
  JIKAN* p;
  JIKAN q={5,6,7};
  for(p=j; p->hour!=-1; p++){
    print(p);
    printf(" + ");
    print(&q);
    printf(" = ");
    add(p,&q);
    print(p);
    printf("\n");
  }
  return 0;
}

出力例2

12:34:56 + 5:6:7 = 17:40:63
1:60:60 + 5:6:7 = 6:66:67
100:58:120 + 5:6:7 = 105:64:127

課題 1-3

JIKAN型の変数のポインターを受け取り、秒、分に関して60以上だった時にそれぞれ分、時に換算して、秒、分を正規化させる void normalize(JIKAN* v) 関数を作りなさい。

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

テストプログラム3


#include <stdio.h>
#include <stdlib.h>
#include "jikan.h"
int main(void){
  JIKAN j[] = {{12,34,56},{1,60,60},{100,58,120},{-1,-1,1}};
  JIKAN* p;
  JIKAN q = {5,6,7};
  for(p=j; p->hour!=-1; p++){
    print(p);
    printf(" + ");
    print(&q);
    printf(" = ");
    add(p,&q);
    print(p);
    normalize(p);
    printf(" -> ");
    print(p);
    printf("\n");
  }
  return 0;
}

出力例3

12:34:56 + 5:6:7 = 17:40:63 -> 17:41:3
1:60:60 + 5:6:7 = 6:66:67 -> 7:7:7
100:58:120 + 5:6:7 = 105:64:127 -> 106:6:7

jikan.hについて

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


typedef struct {
  int hour;
  int minute;
  int second;
} JIKAN;
void print(JIKAN* v);
void add(JIKAN* v,JIKAN* w);
void normalize(JIKAN* v);

レポート作成上の注意

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

坂本直志 <[email protected]>
東京電機大学工学部情報通信工学科