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

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

課題2

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

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

課題1で作成した SCHEDULE をデータとして持つ SCHEDULELIST を作成する。 そのため、課題1 で作成したプログラム(テストプログラムを除く)を schedule.c などと一つのファイルにまとめておくと便利である。

SCHEDULELIST を次のように定義する。 


typedef struct node {
  struct node* next;
  SCHEDULE schedule;
} SCHEDULELIST;

課題2-1

下記のテストプログラム test21.c に示すように SCHEDULELIST を用いた線形リストを指すポインタが与えられたときにすべての SCHEDULE を表示する void printAllList(SCHEDULELIST* p) を作成せよ。

テストプログラム21


#include <stdio.h>
#include "schedulelist.h"
int main(void){
  SCHEDULELIST *schedulelist;
  SCHEDULELIST s0,s1,s2,s3,nil;
  DATE date[]={{2012,1,1,12,30},{2013,1,18,3,40},{2013,6,1,23,50},
	    {2013,6,6,12,10}};
  schedulelist = &s0;

  s0.schedule.nichiji = date[0];
  s0.schedule.naiyou ="初詣";
  s0.next = &s1;

  s1.schedule.nichiji = date[1];
  s1.schedule.naiyou ="試験";
  s1.next = &s2;

  s2.schedule.nichiji = date[2];
  s2.schedule.naiyou ="予定確認";
  s2.next = &s3;

  s3.schedule.nichiji = date[3];
  s3.schedule.naiyou ="食事";
  s3.next = &nil;

  nil.next = NULL;
  
  printAllList(schedulelist);
  return 0;
}
出力例21
2012/01/01 12:30 [初詣]
2013/01/18 03:40 [試験]
2013/06/01 23:50 [予定確認]
2013/06/06 12:10 [食事]

課題2-2

下記のテストプログラム test22.c に示すように SCHEDULELIST を用いた線形リストを指すポインタと、 DATE 型の日付がが与えられたとき、与えられた日付以降のすべての SCHEDULE を表示する void printList(SCHEDULELIST* p, DATE d) を作成せよ。

テストプログラム22


#include <stdio.h>
#include "schedulelist.h"
int main(void){
  SCHEDULELIST *schedulelist;
  SCHEDULELIST s0,s1,s2,s3,nil;
  DATE date[]={{2012,1,1,12,30},{2013,1,18,3,40},{2013,6,1,23,50},
	    {2013,6,6,12,10}};
  schedulelist = &s0;

  s0.schedule.nichiji = date[0];
  s0.schedule.naiyou ="初詣";
  s0.next = &s1;

  s1.schedule.nichiji = date[1];
  s1.schedule.naiyou ="試験";
  s1.next = &s2;

  s2.schedule.nichiji = date[2];
  s2.schedule.naiyou ="予定確認";
  s2.next = &s3;

  s3.schedule.nichiji = date[3];
  s3.schedule.naiyou ="食事";
  s3.next = &nil;

  nil.next = NULL;
  
  printList(schedulelist,date[1]);
  return 0;
}
出力例22
2013/01/18 03:40 [試験]
2013/06/01 23:50 [予定確認]
2013/06/06 12:10 [食事]

課題2-3

下記のテストプログラム test23.c に示すように SCHEDULELIST を用いた線形リストを指すポインタと、 DATE 型の日付がが与えられたとき、与えられた日付以降のすべての SCHEDULE の件数を数える int countList(SCHEDULELIST* p, DATE d) を作成せよ。

テストプログラム23


#include <stdio.h>
#include "schedulelist.h"
int main(void){
  SCHEDULELIST *schedulelist;
  SCHEDULELIST s0,s1,s2,s3,nil;
  DATE date[]={{2012,1,1,12,30},{2013,1,18,3,40},{2013,6,1,23,50},
	    {2013,6,6,12,10}};
  schedulelist = &s0;

  s0.schedule.nichiji = date[0];
  s0.schedule.naiyou ="初詣";
  s0.next = &s1;

  s1.schedule.nichiji = date[1];
  s1.schedule.naiyou ="試験";
  s1.next = &s2;

  s2.schedule.nichiji = date[2];
  s2.schedule.naiyou ="予定確認";
  s2.next = &s3;

  s3.schedule.nichiji = date[3];
  s3.schedule.naiyou ="食事";
  s3.next = &nil;

  nil.next = NULL;
  
  printDate(date[1]);
  printf("以降のスケジュールは %d 件\n",countlist(schedulelist,date[1]));
  return 0;
}
出力例23
2013/01/18 03:40以降のスケジュールは 3 件

課題2-4

下記のテストプログラム test24.c に示すように SCHEDULELIST を用いた線形リストを指すポインタと、 DATE 型の日付と、文字列が与えられたとき、与えられた日付と文字列からスケジュールを作成し、線形リストに追加する SCHEDULELIST* addSchedule(SCHEDULELIST* p, DATE d, char* naiyo) を作成せよ。但し、 addSchedule の戻り値は追加した SCHEDULELIST の番地を返すこと。 なお、 newNode, freeSchedule は別に与えた。

テストプログラム24


#include <stdio.h>
#include <stdlib.h>
#include "schedulelist.h"
SCHEDULELIST* newNode(void){
  SCHEDULELIST* newnode = malloc(sizeof(SCHEDULELIST));
  if(newnode!=NULL){
    newnode->next = NULL;
  }
  return newnode;
}
void freeSchedule(SCHEDULELIST* p){
  if(p->next!=NULL) freeSchedule(p->next);
  free(p);
}

int main(void){
  SCHEDULELIST *schedulelist;
  DATE date[]={{2012,1,1,12,30},{2013,1,18,3,40},{2013,6,1,23,50},
	    {2013,6,6,12,10}};
  if((schedulelist = newNode()) &&
     addSchedule(schedulelist, date[0],"初詣") &&
     addSchedule(schedulelist, date[1],"試験") &&
     addSchedule(schedulelist, date[2],"予定確認") &&
     addSchedule(schedulelist, date[3],"食事")){
    printDate(date[2]);
    printf("以降のスケジュールは %d 件\n",countList(schedulelist,date[2]));
    printList(schedulelist,date[2]);
    printf("\n");
    printAllList(schedulelist);
    freeSchedule(schedulelist);
  }
  return 0;
}
出力例24
2013/06/01 23:50以降のスケジュールは 2 件
2013/06/01 23:50 [予定確認]
2013/06/06 12:10 [食事]

2012/01/01 12:30 [初詣]
2013/01/18 03:40 [試験]
2013/06/01 23:50 [予定確認]
2013/06/06 12:10 [食事]

schedulelist.hについて

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


#include "schedule.h"

typedef struct node {
  struct node* next;
  SCHEDULE schedule;
} SCHEDULELIST;

void printAllList(SCHEDULELIST* p);
void printList(SCHEDULELIST* p, DATE d);
int countList(SCHEDULELIST* p, DATE d);
SCHEDULELIST* addSchedule(SCHEDULELIST* p, DATE d, char* yotei);
void freeSchedule(SCHEDULELIST* p);

課題1

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

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

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

スケジュール管理を行うために、日時を示す構造体と、一つのスケジュールを表す構造体を次のように定義した。 


typedef struct {
  int year;
  int month;
  int day;
  int hour;
  int minute;
} DATE;

typedef struct {
  DATE nichiji;
  char* naiyou;
}SCHEDULE ;

課題1-1

日付を出力する関数 printDateを作成しなさい。 そして、次のテストプログラムと結合し、正常な出力が得られることを確認しなさい。 (schedule.h は後述)

テストプログラム1


#include <stdio.h>
#include "schedule.h"
int main(void){
  DATE d1 = {2013,6,6,18,10};
  DATE d2 = {2013,6,26,20,0};
  printDate(d1);
  printf("に出されたレポートの提出期限は");
  printDate(d2);
  printf("です\n");
  return 0;
}
出力例1
2013/06/06 18:10に出されたレポートの提出期限は2013/06/26 20:00です

あるいは次の出力でも良い。 

2013/6/6 18:10に出されたレポートの提出期限は2013/6/26 20:0です

課題 1-2

SCHEDULE を出力する関数 printSchedule を作成しなさい。 そして、次のテストプログラムと結合し、正常な出力が得られることを確認しなさい。 なお、課題1-1で作成した printDate を活用すること。

テストプログラム2


#include <stdio.h>
#include "schedule.h"
int main(void){
  DATE d={2013,6,6,18,10};
  SCHEDULE s;
  s.nichiji = d;
  s.naiyou="データ構造とアルゴリズムI";
  printSchedule(s);
  printf("\n");
  return 0;
}
出力例2
2013/6/6 18:10 [データ構造とアルゴリズムI]

課題 1-3

二つの DATE 型変数 d1, d2 に対して、次の関数 cmpDate を作成せよ。

d1<d2
負の数を返す
d1==d2
0を返す
d1>d2
正の数を返す

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

テストプログラム3


#include <stdio.h>
#include "schedule.h"
#define N 6
void printDateInBracket(DATE a){
  printf("[");
  printDate(a);
  printf("]");
}
void printResult(DATE a, DATE b, char op, int res){
  printDateInBracket(a);
  printf(" %c ",op);
  printDateInBracket(b);
  if(res){
    printf(" :\tOk\n");
  }else{
    printf(" :\tNG\n");
  }
}
int main(void){
  DATE d[N]={{2012,1,1,12,30},{2013,1,18,3,40},{2013,6,1,23,50},
	     {2013,6,6,12,10},{2013,6,6,18,0},{2013,6,6,18,10}};
  int i,j,result;
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      result=cmpDate(d[i],d[j]);
      if(i==j){
	printResult(d[i],d[j],'=',result==0?1:0);
      }else if(i<j){
	printResult(d[i],d[j],'<',result<0?1:0);
      }else{
	printResult(d[i],d[j],'>',result>0?1:0);
      }

    }
  }
  return 0;
}
出力例3
[2012/01/01 12:30] = [2012/01/01 12:30] :	Ok
[2012/01/01 12:30] < [2013/01/18 03:40] :	Ok
[2012/01/01 12:30] < [2013/06/01 23:50] :	Ok
[2012/01/01 12:30] < [2013/06/06 12:10] :	Ok
[2012/01/01 12:30] < [2013/06/06 18:00] :	Ok
[2012/01/01 12:30] < [2013/06/06 18:10] :	Ok
[2013/01/18 03:40] > [2012/01/01 12:30] :	Ok
[2013/01/18 03:40] = [2013/01/18 03:40] :	Ok
[2013/01/18 03:40] < [2013/06/01 23:50] :	Ok
[2013/01/18 03:40] < [2013/06/06 12:10] :	Ok
[2013/01/18 03:40] < [2013/06/06 18:00] :	Ok
[2013/01/18 03:40] < [2013/06/06 18:10] :	Ok
[2013/06/01 23:50] > [2012/01/01 12:30] :	Ok
[2013/06/01 23:50] > [2013/01/18 03:40] :	Ok
[2013/06/01 23:50] = [2013/06/01 23:50] :	Ok
[2013/06/01 23:50] < [2013/06/06 12:10] :	Ok
[2013/06/01 23:50] < [2013/06/06 18:00] :	Ok
[2013/06/01 23:50] < [2013/06/06 18:10] :	Ok
[2013/06/06 12:10] > [2012/01/01 12:30] :	Ok
[2013/06/06 12:10] > [2013/01/18 03:40] :	Ok
[2013/06/06 12:10] > [2013/06/01 23:50] :	Ok
[2013/06/06 12:10] = [2013/06/06 12:10] :	Ok
[2013/06/06 12:10] < [2013/06/06 18:00] :	Ok
[2013/06/06 12:10] < [2013/06/06 18:10] :	Ok
[2013/06/06 18:00] > [2012/01/01 12:30] :	Ok
[2013/06/06 18:00] > [2013/01/18 03:40] :	Ok
[2013/06/06 18:00] > [2013/06/01 23:50] :	Ok
[2013/06/06 18:00] > [2013/06/06 12:10] :	Ok
[2013/06/06 18:00] = [2013/06/06 18:00] :	Ok
[2013/06/06 18:00] < [2013/06/06 18:10] :	Ok
[2013/06/06 18:10] > [2012/01/01 12:30] :	Ok
[2013/06/06 18:10] > [2013/01/18 03:40] :	Ok
[2013/06/06 18:10] > [2013/06/01 23:50] :	Ok
[2013/06/06 18:10] > [2013/06/06 12:10] :	Ok
[2013/06/06 18:10] > [2013/06/06 18:00] :	Ok
[2013/06/06 18:10] = [2013/06/06 18:10] :	Ok

課題 1-4

指定の DATE の値 date と SCHEDULE の配列を受け取り、指定の DATE 以降(指定日時は含む)だけを表示する printYotei 関数を作成せよ。 但し、 SCHEDULE の配列の nichiji.year に -1 が入っていたら、それを番兵とすること。

以下のプログラムと結合し、正常に動くことを報告せよ。

テストプログラム4


#include <stdio.h>
#include "schedule.h"
int main(void){
  DATE d[]={{2012,1,1,12,30},{2013,1,18,3,40},{2013,6,1,23,50},
	    {2013,6,6,12,10},{2013,6,6,18,0},{2013,6,6,18,10},
	    {-1,0,0,0,0}};

  SCHEDULE s[10];
  s[0].nichiji=d[0];
  s[0].naiyou="初詣";
  s[1].nichiji=d[5];
  s[1].naiyou="授業";
  s[2].nichiji=d[3];
  s[2].naiyou="レストラン";
  s[3].nichiji=d[2];
  s[3].naiyou="締切り";
  s[4].nichiji=d[1];
  s[4].naiyou="番組録画";
  s[5].nichiji=d[4];
  s[5].naiyou="入室チェック";
  s[6].nichiji=d[5];
  s[6].naiyou="課題";
  s[7].nichiji=d[3];
  s[7].naiyou="手紙の投函";
  s[8].nichiji=d[2];
  s[8].naiyou="6月の予定確認";
  s[9].nichiji=d[6];
  s[9].naiyou="";
  printYotei(d[0],s);
  printf("-----\n");
  printYotei(d[3],s);
  printf("-----\n");
  printYotei(d[5],s);
  return 0;
}
出力例4
2012/01/01 12:30 [初詣]
2013/06/06 18:10 [授業]
2013/06/06 12:10 [レストラン]
2013/06/01 23:50 [締切り]
2013/01/18 03:40 [番組録画]
2013/06/06 18:00 [入室チェック]
2013/06/06 18:10 [課題]
2013/06/06 12:10 [手紙の投函]
2013/06/01 23:50 [6月の予定確認]
-----
2013/06/06 18:10 [授業]
2013/06/06 12:10 [レストラン]
2013/06/06 18:00 [入室チェック]
2013/06/06 18:10 [課題]
2013/06/06 12:10 [手紙の投函]
-----
2013/06/06 18:10 [授業]
2013/06/06 18:10 [課題]

schedule.hについて

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


typedef struct {
  int year;
  int month;
  int day;
  int hour;
  int minute;
} DATE;

typedef struct {
  DATE nichiji;
  char* naiyou;
}SCHEDULE ;
void printDate(DATE d);
void printSchedule(SCHEDULE s);
int cmpDate(DATE a, DATE b);
void printDateInBracket(DATE a);
void printResult(DATE a, DATE b, char op, int res);
void printYotei(DATE d, SCHEDULE* array);

レポート作成上の注意

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