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

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

変更履歴

2024/5/23 18:10:00: 課題1初出
2024/6/27 21:00:00: 課題2初出
2024/7/4 21:30:00: 課題2補足説明追加

課題1
課題2

課題2

レポート締切日: 2024年7月24日(水)23:59
提出先: https://tdu.app.box.com/f/248d8df9ce21492a92c0548be2fb21e2 にファイル名を 学籍番号-2.pdfとして、アップロードすること

解答法は課題1と同等である。但し、課題1で作成したプログラムを使用、結合して良く、またその際には、課題1のプログラムの詳細の説明は省いてよい。

問題の最後に、本課題で必要なヘッダファイル kadai2.h, ekilist.h と Makefile を示す。課題で作成する関数は「関数名.c」というファイルに入れられる前提としている。

本課題で使用するヘッダファイル kadai2.h (後述)には次の構造体が定義されている。


typedef struct list {
  char* eki;
  struct list* next;
} LIST;

これを使用した線形リストを処理するプログラムを作成する

また、プログラムテスト用にekilist.h(後述)が定義されている。

問題2-1

LIST を用いて作成した線形リストについて、中に入っている駅名を eki1 --- eki2 --- eki3 のように３つのハイフンで区切って表示し、最後、改行する関数 void printekilist(LIST* p)を作成をprintekilist.cというファイルに作成せよ。なお、空のリストを受け取った場合は、改行のみすることとする。

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

ex21.c


#include <stdlib.h>
#include "kadai2.h"
#include "ekilist.h"
int main(void){
  LIST **p;
  for(p=ekilists;*p!=NULL;p++){
    printekilist(*p);
  }
  return 0;
}

出力例2-1


kitasenju
ueno --- kitasenju
tokyo --- ueno --- kitasenju
ikebukuro --- tokyo --- ueno --- kitasenju
shinjuku --- ikebukuro --- tokyo --- ueno --- kitasenju

問題2-2

LIST を用いて作成した線形リストについて、中に入っている駅間の料金を課題1で示した二次元配列 ryokin に基づいて取得し、合算した値を返す関数int listryokin(LIST* p) をlistryokin.cというファイルに作成せよ。なお、空のリストを受け取った場合、１駅だけのリストの場合は 0 を返すこととする。

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

なお、課題1で作成した ekikan, search などを使用しても良い

ex22.c


#include <stdio.h>
#include <stdlib.h>
#include "kadai2.h"
#include "ekilist.h"
int main(void){
  LIST **p;
  for(p=ekilists;*p!=NULL;p++){
    printekilist(*p);
    printf("%d\n",listryokin(*p));
  }
  return 0;
}

出力例2-2


0
kitasenju
0
ueno --- kitasenju
180
tokyo --- ueno --- kitasenju
350
ikebukuro --- tokyo --- ueno --- kitasenju
560
shinjuku --- ikebukuro --- tokyo --- ueno --- kitasenju
730

問題2-3

LIST の空のノードを作る関数LIST* newnode(void) をnewnode.cというファイルに作成せよ。

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

ex23.c


#include <stdio.h>
#include <stdlib.h>
#include "kadai2.h"
void delnode(LIST* p){
  if(p==NULL)return ;
  delnode(p->next);
  free(p);
}
int main(void){
  LIST *p;
  LIST *q;
  int i;
  if((p=newnode())==NULL){
    fprintf(stderr,"メモリが確保できませんでした\n");
    return 2;
  }
  for(i=0;i<N;i++){
    if((q=newnode())==NULL){
      fprintf(stderr,"メモリが確保できませんでした\n");
      return 2;
    }
    q->next=p;
    q->eki=eki[i];
    p=q;
    printekilist(p);
  }
  delnode(p);
  return 0;
}

出力例2-3

kitasenju
ueno --- kitasenju
tokyo --- ueno --- kitasenju
ikebukuro --- tokyo --- ueno --- kitasenju
shinjuku --- ikebukuro --- tokyo --- ueno --- kitasenju

問題2-4

LIST で作成された線形リストの管理変数 p と文字列を指すポインター e より、線形リストの最後にeを追加する関数LIST* add(LIST* p, char* e) をadd.cというファイルに作成せよ。なお、戻り値として、新たな要素を追加した構造体のポインタを返すこと。

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

なお、課題1で作成した ekikan, search などを使用しても良い

ex24.c


#include <stdio.h>
#include <stdlib.h>
#include "kadai2.h"
void delnode(LIST* p){
  if(p==NULL)return ;
  delnode(p->next);
  free(p);
}
int main(void){
  LIST *p, *q;
  int i;
  if((p=newnode())==NULL){
    fprintf(stderr,"メモリが確保できませんでした\n");
    return 2;
  }
  for(i=0;i<N;i++){
    if((q=add(p,eki[i]))==NULL){
      fprintf(stderr,"メモリが確保できませんでした\n");
      return 2;
    }
    printf("追加した駅は%s\n",q->eki);
    printekilist(p);
    printf("%d\n",listryokin(p));
  }
  delnode(p);
  return 0;
}

出力例2-4

追加した駅はkitasenju
kitasenju
0
追加した駅はueno
kitasenju --- ueno
180
追加した駅はtokyo
kitasenju --- ueno --- tokyo
350
追加した駅はikebukuro
kitasenju --- ueno --- tokyo --- ikebukuro
560
追加した駅はshinjuku
kitasenju --- ueno --- tokyo --- ikebukuro --- shinjuku
730

ヘッダファイル、Makefile

kadai2.h


#include "kadai1.h"
typedef struct list {
  char* eki;
  struct list* next;
} LIST;
void printekilist(LIST* p);
int listryokin(LIST* p);
LIST* newnode(void);
LIST* add(LIST* p, char* e);

ekilist.h


LIST l0={NULL,NULL};
LIST l1={"kitasenju",&l0};
LIST l2={"ueno",&l1};
LIST l3={"tokyo",&l2};
LIST l4={"ikebukuro",&l3};
LIST l5={"shinjuku",&l4};
LIST* ekilists[]={&l0,&l1,&l2,&l3,&l4,&l5,NULL};

Makefile

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


ex24.exe: ex24.o printekilist.o eki.o newnode.o add.o listryokin.o ekikan.o search.o
	$(CC) -o $@ $^
ex23.exe: ex23.o printekilist.o eki.o newnode.o
	$(CC) -o $@ $^
ex22.exe: ex22.o printekilist.o listryokin.o eki.o ekikan.o search.o
	$(CC) -o $@ $^
ex21.exe: ex21.o printekilist.o
	$(CC) -o $@ $^
ex13.exe: ex13.o eki.o search.o ekikan.o keiyuryokin.o
	$(CC) -o $@ $^
ex12.exe: ex12.o eki.o search.o ekikan.o
	$(CC) -o $@ $^
ex11.exe: ex11.o eki.o search.o
	$(CC) -o $@ $^
ex21.o: kadai2.h ekilist.h
ex22.o: kadai2.h ekilist.h 
ex23.o: kadai2.h 
ex24.o: kadai2.h 
printekilist.o: kadai2.h
ryokin.o: ekikan.c
newnode.o: kadai2.h
add.o: kadai2.h
ex11.o: kadai1.h
ex12.o: kadai1.h
ex13.o: kadai1.h
ex14.o: kadai1.h
eki.o: kadai1.h
search.o: kadai1.h
ekikan.o: kadai1.h
keiyuryokin.o: kadai1.h

課題1

レポート締切日: 2024年6月12日(水)23:59
提出先: BOX https://tdu.app.box.com/f/bfd0b8f6b8014522b78f68bd00f5cc68 にファイル名を 学籍番号-1.pdfとして、アップロードすること

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

問題とテストプログラムの改変は不合格である。なお、Makefile は使用してもしなくても良い。また、プログラムを結合するためなどのやむを得ない必要な変更(include の代わりにプログラムを埋め込むなど)は許される。

問題の最後に、本課題で必要なヘッダファイル kadai1.h と Makefile を示す。課題で作成する関数は「関数名.c」というファイルに入れられる前提としている。

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

eki.c に駅名の配列と、駅間の運賃の二次元配列が記述されている。

eki.c


#include "kadai1.h"
char* eki[N]={"kitasenju", "ueno", "tokyo", "ikebukuro", "shinjuku"};
int ryokin[N][N]={{0,180,230,230,320},
		  {180,0,170,180,210},
		  {230,170,0,210,210},
		  {230,180,210,0,170},
		  {320,210,210,170,0}};

問題1-1

文字配列の先頭番地を受け取り、配列ekiの中の該当する要素の添え字を返す int search(char* name) をsearch.cというファイルに作成せよ。なお、発見できなかった場合は -1を返すものとする。

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

ex11.c


#include <stdio.h>
#include <stdlib.h>
#include "kadai1.h"
int main(void){
  char* testeki[]={"","ikebukuro","kitasenju",  "shinjuku",
		   "shibuya","tokyo", "ueno",NULL};
  char** p;
  int e;
  
  for(p=testeki; *p!=NULL; p++){
    e = search(*p);
    printf("%s駅の駅番号は%d\n",*p,e);
  }
  return 0;
}

出力例1-1

駅の駅番号は-1
ikebukuro駅の駅番号は3
kitasenju駅の駅番号は0
shinjuku駅の駅番号は4
shibuya駅の駅番号は-1
tokyo駅の駅番号は2
ueno駅の駅番号は1

問題1-2

二つの駅名の文字配列の先頭番地を受け取り、その駅間の運賃を返す int ekikan(char* name0, char* name1) 関数を作成せよ。この関数のファイル名を ekikan.c とする。

これと、下記のテストプログラム, ekikan.c, eki.c, kadai1.h と必要ならば search.c を結合して実行し、出力結果を示せ。

ex12.c


#include <stdio.h>
#include <stdlib.h>
#include "kadai1.h"
int main(void){
  char* testekipair[][2]={{"ikebukuro","kitasenju"},
			  {"shinjuku","kitasenju"},
			  {"shinjuku","ueno"},
			  {"kitasenju","kitasenju"},
			  {"tokyo", "ueno"},
			  NULL};
  char *(*p)[2];
  int r;
  for(p=testekipair; **p!=NULL; p++){
    r = ekikan(**p,*(*p+1));
    printf("%s駅と%s駅間の料金は%d\n",**p,*(*p+1),r);
  }
  return 0;
}

出力例1-2

ikebukuro駅とkitasenju駅間の料金は230
shinjuku駅とkitasenju駅間の料金は320
shinjuku駅とueno駅間の料金は210
kitasenju駅とkitasenju駅間の料金は0
tokyo駅とueno駅間の料金は170

問題1-3

駅名を表す文字配列へのポインタの配列がNULLを番兵に持つものとする (NULL は stdlib.h に定義されているものとする)。


char* a[]={"kitasenju", "ueno", "tokyo", NULL};

このような文字配列ポインタの配列の番地を受け取り、各駅を順に訪れる場合の運賃の合計を返す int keiyuryokin(char** p) を作成せよ。この関数のファイル名を keiyuryokin.c とする。

これと、下記のテストプログラム, eki.c, kadai1.h の他、必要に応じて前問で作成した関数を結合して実行し、出力結果を示せ。

ex13.c


#include <stdio.h>
#include <stdlib.h>
#include "kadai1.h"
int main(void){
  char* eki1[]={"kitasenju",NULL};
  char* eki2[]={"kitasenju","ikebukuro",NULL};
  char* eki3[]={"kitasenju","ueno","tokyo",NULL};
  char* eki4[]={"kitasenju","shinjuku","tokyo","ueno",NULL};
  char** testekiretsu[]={eki1,eki2,eki3,eki4,NULL};

  char ***p;
  char **q;
  int r;
  for(p=testekiretsu; *p!=NULL; p++){
    for(q=*p; *q!=NULL; q++){
      printf("%s駅",*q);
    }
    r = keiyuryokin(*p);
    printf("間の料金は%d\n",r);
  }
  return 0;
}

出力例1-3

kitasenju駅間の料金は0
kitasenju駅ikebukuro駅間の料金は230
kitasenju駅ueno駅tokyo駅間の料金は350
kitasenju駅shinjuku駅tokyo駅ueno駅間の料金は700

kadai1.h


#define N 5
extern char* eki[N];
extern int ryokin[N][N];
int search(char* name);
int ekikan(char* name0, char* name1);
int keiyuryokin(char** p);

Makefile

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


ex13.exe: ex13.o eki.o search.o ekikan.o keiyuryokin.o
	$(CC) -o $@ $^
ex12.exe: ex12.o eki.o search.o ekikan.o
	$(CC) -o $@ $^
ex11.exe: ex11.o eki.o search.o
	$(CC) -o $@ $^
ex11.o: kadai1.h
ex12.o: kadai1.h
ex13.o: kadai1.h
ex14.o: kadai1.h
eki.o: kadai1.h
search.o: kadai1.h
ekikan.o: kadai1.h
keiyuryokin.o: kadai1.h

レポート作成上の注意

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

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

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