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

本講義では 2 通のレポートで評価します。レポートは A4 縦の様式で PDF 形式で作成して下さい。またプログラムは C 言語で作成しなさい。

変更履歴

2021/5/20: 課題1初出
2021/5/27: 提出日訂正、課題1-4 テストプログラムの配列初期化に追記
2021/7/1: 課題2初出

課題1
課題2

課題2

レポート締切日: 2021年7月21日(水)23:59
提出先: BOX にファイル名を 学籍番号-2.pdfとして、アップロードすること

問題

課題1で使用した構造体 RESULT を前提とした、次の構造体 NODE に関する関数を作成する。


typedef struct{
  char* country;
  int medal[3];
} RESULT;
typedef struct node {
  RESULT result;
  struct node* left;
  struct node* right;
} NODE;

ヘッダファイルなどはまとめて後ろに示してある。

なお、レポートにおいては、作成したプログラムの説明が必須であるが、課題1で作成した関数に関しては説明する必要は無い。

問題2-1

以下のプログラム mondai21.c において、以下の問に答えなさい

mondai21.c


#include "kadai2.h"
#include "data.h"

int main(void){
  int i;
  for(i=0;i<=4;i++){
    data[i].left=&data[2*i+1];
    data[i].right=&data[2*i+2];
  }
  printtree(&data[0]);
  return 0;
}

問題2-1-1

printree を呼び出す直前の各データ構造を図で示しなさい。構造体は、漢字の目のように長方形を区切った図として表しなさい。また、 left, right などのポインターに関しては、長方形の中央を始点とし、実際に指している構造体を表す長方形を指すように矢印を書きなさい。

問題2-1-2

NODE型の番地を受け取り、それを二分木として、木の左から順に RESULT 型の値を表示する関数 void printtree(NODE*) を作成せよ。但し、ファイル名を printtree.c とする。また、RESULT 型の値を表示するのに課題1で作成した関数を使用して良い

これと、mondai21.c, kadai2.h, kadai1.h, data.h を結合して実行し、出力結果を示せ。

出力例2-1

CZE: 0 0 1
RUS: 2 0 1
GBR: 1 0 0
CHN: 0 2 1
ETH: 0 1 0
USA: 0 1 0
KEN: 0 0 1
AUS: 1 0 0
TTO: 1 0 0
IRL: 0 0 1
FIN: 0 1 0

問題2-2

2つの RESULT 型の値、 a,b を受け取った時、以下の条件に従って値を返す int compresult(RESULT a, RESULT b) を作成しなさい。但し、 string.h を include するものとする。

a.medal[0]がb.medal[0] より大きければ正の値、小さければ負の値
a.medal[0]とb.medal[0]が等しく、 a.medal[1]がb.medal[1] より大きければ正の値、小さければ負の値
a.medal[0]とb.medal[0]が等しく、a.medal[1]とb.medal[1]も等しく、 a.medal[2]がb.medal[2] より大きければ正の値、小さければ負の値
a.medal[0]とb.medal[0]が等しく、a.medal[1]とb.medal[1]も等しく、 a.medal[2]とb.medal[2] も等しい場合、 strcmp(a.country,b.country) の値

これと、以下のプログラム, kadai1.h, data.h を結合して実行し、出力結果を示せ。

mondai22.c


#include <stdio.h>
#include "kadai2.h"
#include "data.h"

int main(void){
  int i,j,res;
  char out;
  
  for(i=0;data[i].result.country!=0;i++){
    printf("%s ",data[i].result.country);
  }
  printf("\n");
  for(i=0;data[i].result.country!=0;i++){
    for(j=0;data[j].result.country!=0;j++){
      res=compresult(data[i].result,data[j].result);
      if(res==0){
	out='0';
      }else if(res>0){
	out='+'; 
      }else{
	out='-';
      }
      printf(" %c  ",out);
    }
    printresult(&data[i].result);
  }
  return 0;
}

出力例2-2

AUS CHN IRL RUS USA TTO FIN CZE GBR ETH KEN 
 0   +   +   -   +   -   +   +   -   +   +  AUS: 1 0 0
 -   0   +   -   +   -   +   +   -   +   +  CHN: 0 2 1
 -   -   0   -   -   -   -   +   -   -   -  IRL: 0 0 1
 +   +   +   0   +   +   +   +   +   +   +  RUS: 2 0 1
 -   -   +   -   0   -   +   +   -   +   +  USA: 0 1 0
 +   +   +   -   +   0   +   +   +   +   +  TTO: 1 0 0
 -   -   +   -   -   -   0   +   -   +   +  FIN: 0 1 0
 -   -   -   -   -   -   -   0   -   -   -  CZE: 0 0 1
 +   +   +   -   +   -   +   +   0   +   +  GBR: 1 0 0
 -   -   +   -   -   -   -   +   -   0   +  ETH: 0 1 0
 -   -   +   -   -   -   -   +   -   -   0  KEN: 0 0 1

問題2-3

compresult 関数により大小を決定する NODE 型の順序木の根のポインターの番地と、 RESULT 型の値を受け取って、順序木に値を追加する関数 NODE* addtree(NODE **t, RESULT r) を作成しなさい。なお、 addtree の戻り値は付け加えたノードへのポインターで、メモリが確保できなかった時は NULL を返すものとします。

これと、下記のテストプログラム, kadai2.h, printtree, compresult, deltree (後述)を結合して実行し、出力結果を示せ。

mondai23.c


#include <stdio.h>
#include <stdlib.h>
#include "kadai2.h"
#include "data.h"

int main(void){
  NODE* root=NULL;
  int  i;
  for(i=0;data[i].result.country!=0;i++){
    printresult(&data[i].result);
    if(addtree(&root,data[i].result) == NULL){
      fprintf(stderr,"メモリーエラー\n");
      return 1;
    }
  }
  printf("-----\n");
  printtree(root);
  deltree(root);
  return 0;
}

出力例2-3

AUS: 1 0 0
CHN: 0 2 1
IRL: 0 0 1
RUS: 2 0 1
USA: 0 1 0
TTO: 1 0 0
FIN: 0 1 0
CZE: 0 0 1
GBR: 1 0 0
ETH: 0 1 0
KEN: 0 0 1
-----
CZE: 0 0 1
IRL: 0 0 1
KEN: 0 0 1
ETH: 0 1 0
FIN: 0 1 0
USA: 0 1 0
CHN: 0 2 1
AUS: 1 0 0
GBR: 1 0 0
TTO: 1 0 0
RUS: 2 0 1

kadai2.h、data.h、Makefile, deltree.c

kadai2.h


#include "kadai1.h"
typedef struct node {
  RESULT result;
  struct node* left;
  struct node* right;
} NODE;
void printtree(NODE* list);
int compresult(RESULT a, RESULT b);
NODE* addtree(NODE **t, RESULT r);
void deltree(NODE* node);

data.h


NODE data[]={{{"AUS",{1, 0, 0}}},
	     {{"CHN",{0, 2, 1}}},
	     {{"IRL",{0, 0, 1}}},
	     {{"RUS",{2, 0, 1}}},
	     {{"USA",{0, 1, 0}}},
	     {{"TTO",{1, 0, 0}}},
	     {{"FIN",{0, 1, 0}}},
	     {{"CZE",{0, 0, 1}}},
	     {{"GBR",{1, 0, 0}}},
	     {{"ETH",{0, 1, 0}}},
	     {{"KEN",{0, 0, 1}}},
	     {{0}}};

Makefile


CC=gcc
mondai21.exe:	mondai21.o printresult.o printtree.o 
	$(CC) -o $@ $^

mondai22.exe:	mondai22.o printresult.o compresult.o
	$(CC) -o $@ $^

mondai23.exe:	mondai23.o printresult.o printtree.o compresult.o addtree.o deltree.o
	$(CC) -o $@ $^

clean:
	rm	*.o *.exe

mondai21.o: kadai1.h kadai2.h data.h
mondai22.o: kadai1.h kadai2.h data.h
mondai23.o: kadai1.h kadai2.h data.h
printtree.o: kadai1.h kadai2.h
compresult.o: kadai1.h 
addtree.o: kadai1.h kadai2.h
deltree.o: kadai1.h kadai2.h
printresult.o: kadai1.h

deltree.c


#include <stdlib.h>
#include "kadai2.h"

void deltree(NODE* node){
  if(node==NULL){
    return;
  }
  deltree(node->left);
  deltree(node->right);
  free(node);
}

課題1

レポート締切日: 2021年6月2日(水)23:59
提出先: BOX にファイル名を 学籍番号-1.pdfとして、アップロードすること

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

なお、レポートは締め切り後も提出できます。同じファイル名で複数のバージョンが存在できます。締め切り内に採点可能なレポートがある場合は、最も締切に近いものだけを採点します。締め切り内に有効なレポートがない場合、最も新しいレポートを遅れレポートとして減点の上採点します。

問題

次の構造体の配列に関する関数を作成する。


typedef struct{
  char* country;
  int medal[3];
} RESULT;

なお、country メンバーには、ISO 3166-1で規定されている3文字の国名コードが入ることが想定されている（現在249種類）。また、配列の番兵は、country メンバーに NULL を入れることとする。

問題1-1

RESULT型の番地を受け取り、一行表示する関数 void printresult(RESULT*) を作成せよ。但し、ファイル名を printresult.c とする。

これと、下記のテストプログラム, kadai1.h を結合して実行し、出力結果を示せ。

mondai11.c


#include "kadai1.h"
#define NULL 0
int main(void){
  RESULT resultlist[]={{"JPN",{1,2,3}},{"USA",{2,3,4}},{"GBR",{3,4,5}},{NULL}};
  RESULT *r;
  for(r=resultlist;r->country!=NULL;r++){
    printresult(r);
  }
  return 0;
}

出力例1-1

JPN: 1 2 3
USA: 2 3 4
GBR: 3 4 5

問題1-2

番兵で終端するRESULT型の配列の先頭番地と、文字列の番地を受け取り、番兵までの範囲で文字列が一致する要素を見つけ、その要素への番地を返す RESULT* searchresult(RESULT*,char*) を作成せよ。なお、未発見の場合、番兵の入っている要素の番地を返すとする。この関数のファイル名を searchresult.c とする。なお、作成するにあたって、 string.h をインクルードし、 strcmp 関数を使用しても良い。

これと、下記のテストプログラム,printresult, kadai1.h を結合して実行し、出力結果を示せ。

mondai12.c


#include <stdio.h>
#include "kadai1.h"
typedef struct {
  char* country;
  int index;
} DATA;
int main(void){
  RESULT result[]={{"JPN",{1,2,3}},{"USA",{2,3,4}},{"GBR",{3,4,5}},{NULL}};
  char* country[]={"GBR","USA","JPN","USR",NULL};
  char** p;
  RESULT* r;
  for(p=country; *p!=NULL; p++){
    r=searchresult(result, *p);
    if(r->country!=NULL){
      printresult(r);
    }else{
      printf("無し\n");
    }
  } 
  return 0;
}

出力例1-2

GBR: 3 4 5
USA: 2 3 4
JPN: 1 2 3
無し

問題1-3

番兵で終端するRESULT型の配列の先頭番地と、文字列の番地と、添字(0,1,2 のいずれかの数)を受け取り、与えた文字列を含む要素の中の指定した添字のmedal配列の要素を 1増やす関数 RESULT* addresult(RESULT*,char*,int) を作成せよ。なお、文字列が発見できない時は、番兵の部分に、文字列をstrdup関数によりコピーし、さらに、medal 配列をすべて0で初期化した後、指定した添字の要素のみ 1 とする。また、関数の戻り値は、1増やした要素の番地とする。これを作成する際に、searchresult を呼び出して良い。なお、ファイル名を addresult.c とする。

strdup 関数は string.h ヘッダファイルをインクルードして使用する (Visual Studio では _strdup)。引数に文字列を指定すると、その文字列をコピーして先頭番地を返す。但し、コピーに失敗した場合に NULL を返すが、この課題においてはコピーは必ず成功すると仮定し、失敗の処理を省略して良い。

これと、下記のテストプログラム,printresult, searchresult, kadai1.h に加え、あとで示す printresultlist, clearresult も結合して実行し、出力結果を示せ。

mondai13.c


#include <stdio.h>
#include "kadai1.h"
typedef struct {
  char* country;
  int index;
} DATA;
int main(void){
  RESULT resultlist[250]={{NULL,{100,200,300}},{NULL,{9,8,7}}};
  DATA data[]={{"JPN",0},{"USA",1},{"GBR",2},
	       {"USA",0},{"JPN",1},{"USR",2},
	       {"GBR",0},{"USA",1},{"GBR",2},{NULL}};
  DATA *p;
  for(p=data; p->country!=NULL; p++){
    printresult(addresult(resultlist, p->country, p->index));
  }
  printf("-------\n");
  printresultlist(resultlist);
  clearresult(resultlist);
  return 0;
}

出力例1-3

JPN: 1 0 0
USA: 0 1 0
GBR: 0 0 1
USA: 1 1 0
JPN: 1 1 0
USR: 0 0 1
GBR: 1 0 1
USA: 1 2 0
GBR: 1 0 2
-------
JPN: 1 1 0
USA: 1 2 0
GBR: 1 0 2
USR: 0 0 1

問題1-4

文字列４つからなる要素を持つ、文字列の二次元配列を考える。４つの内訳は、「イベント名、１位の国、２位の国、３位の国」である。４つの文字列の配列を受け取って、RESULT の配列に対して、各国のメダル数 medal を加算する関数 void inc(RESULT* char**) を作成せよ。これは、addresult を呼び出して良い。なお、ファイル名を inc.c とする。

これと、下記のテストプログラム,addresult,printresult, searchresult, kadai1.h に加え、あとで示す printresultlist, clearresult も結合して実行し、出力結果を示せ。

mondai14.c


#include <stdio.h>
#include "kadai1.h"
int main(void){
RESULT resultlist[250]={0};
  char* events[][4]= {
		      {"50 Kilometres Race Walk men","AUS","CHN","IRL"},
		      {"20 Kilometres Race Walk women","RUS","CHN","CHN"},
		      {"High Jump women","RUS","USA","RUS"},
		      {"Javelin Throw men","TTO","FIN","CZE"},
		      {"5000 Metres men","GBR","ETH","KEN"},
		      {NULL}
  };
  char* (*p)[4];
  int i;
  for(p=events;(*p)[0]!=NULL;p++){
    inc(resultlist,*p);
  }
  printresultlist(resultlist);
  clearresult(resultlist);
  return 0;
}

出力例1-4

AUS: 1 0 0
CHN: 0 2 1
IRL: 0 0 1
RUS: 2 0 1
USA: 0 1 0
TTO: 1 0 0
FIN: 0 1 0
CZE: 0 0 1
GBR: 1 0 0
ETH: 0 1 0
KEN: 0 0 1

kadai1.h


typedef struct {
  char* country;
  int medal[3];
} RESULT;
void printresultlist(RESULT* r);
RESULT* addresult(RESULT* r, char* c, int i);
void clearresult(RESULT* r);
RESULT* searchresult(RESULT* resultlist, char* name);
void printresult(RESULT* r);
void inc(RESULT* list, char** p);

printresultlist.c


#include <stdio.h>
#include "kadai1.h"
void printresultlist(RESULT* r){
  for(; r->country!=NULL; r++){
    printresult(r);
  }
}

clearlist.c


#include <stdlib.h>
#include "kadai1.h"
void clearresult(RESULT *r){
  while(r->country!=NULL){
    free(r->country);
    r->country=NULL;
    r++;
  }
}

Makefile

$(CC) -o $@ $^の $(CC) の前には TAB 記号が一つだけ入っていることに注意する。これが空白記号に置き換わっていると動作しない。


CC=gcc
mondai14.exe:	mondai14.o printresult.o addresult.o clearresult.o searchresult.o  printresultlist.o inc.o
	$(CC) -o $@ $^

mondai13.exe:	mondai13.o printresult.o addresult.o clearresult.o searchresult.o  printresultlist.o
	$(CC) -o $@ $^

mondai12.exe:	mondai12.o searchresult.o printresult.o clearresult.o
	$(CC) -o $@ $^

mondai11.exe:	mondai11.o printresult.o
	$(CC) -o $@ $^

clean:
	rm	*.o *.exe

mondai13.o: kadai1.h
mondai12.o: kadai1.h
mondai11.o: kadai1.h
clearresult.o: kadai1.h
addresult.o: kadai1.h
addresult.o: searchresult.c
printresult.o: kadai1.h
searchresult.o: kadai1.h
printresultlist.o: kadai1.h
printresultlist.o: printresult.c
inc.o: kadai1.h
inc.o: addresult.c

レポート作成上の注意

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

なお、写したと思われるほど酷似したレポートが複数提出された場合、原著がどれかの調査を行わず、抽選で一通のレポートのみを評価の対象とし、他は提出済みの不合格レポートとして再提出は課しません。自分で意図せずに他人にコピーされてしまった場合も同様ですので、レポートの取り扱いについては十分に注意して下さい。

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

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

変更履歴

課題2

問題

問題2-1

mondai21.c

問題2-1-1

問題2-1-2

出力例2-1

問題2-2

mondai22.c

出力例2-2

問題2-3

mondai23.c

出力例2-3

kadai2.h、data.h、Makefile, deltree.c

kadai2.h

data.h

Makefile

deltree.c

課題1

問題

問題1-1

mondai11.c

出力例1-1

問題1-2

mondai12.c

出力例1-2

問題1-3

mondai13.c

出力例1-3

問題1-4

mondai14.c

出力例1-4

ヘッダファイル、printresultlist, clearlist, Makefile

kadai1.h

printresultlist.c

clearlist.c

Makefile

レポート作成上の注意