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

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

変更履歴

2019/5/22: 課題1初出
2019/5/31: 課題1ヘッダファイル修正
2019/6/26: 課題2初出

課題1
課題2

課題2

レポート締切日: 2019年7月26日(金)18:10
提出先: 2 号館 3F レポートボックス

なお、遅れレポートは受け取らない。

レポート作成に当たっては、本課題のために作成したプログラムのみを説明すれば良い。課題1で作成したプログラムは、その旨断るだけで自由に使用して良い。

問題

商品の売上の集計を線形リストで管理する。

URIAGE のポインタと次の要素へのポインタを持つ構造体 URIAGELIST を下記のように定義する。


typedef struct uriagelist {
  struct uriagelist* next;
  URIAGE *uriage;
}URIAGELIST;

これを用いて線形リストを作成する。先頭のノードを指すポインタを変数で管理し、終端のノードからは空のノードに接続し、空のノードの next メンバが NULL であることで、ノードの終端を検出するとする。空のノードにはデータを入れないので、 uriage メンバの初期化は義務付けない。

問題2-1

上記のように定義された線形リストの内容を表示する関数 void printUriageList(URIAGELIST* l) を作成しなさい。

そして、次のテストプログラム、課題1で使用したプログラムと結合し、結果を示しなさい。

テストプログラム2-1


#include <stdio.h>
#include <stdlib.h>
#include "shohin.h"
#include "uriage.h"
#include "uriagelist.h"
int main(void){
  URIAGE u1={1,2};
  URIAGE u2={2,3};
  URIAGE u3={3,4};
  URIAGELIST l0={NULL};
  URIAGELIST l1={&l0,&u1};
  URIAGELIST l2={&l1,&u2};
  URIAGELIST l3={&l2,&u3};
  printf("-----\n");
  printUriageList(&l0);
  printf("-----\n");
  printUriageList(&l1);
  printf("-----\n");
  printUriageList(&l2);
  printf("-----\n");
  printUriageList(&l3);
  return 0;
}

出力例2-1

-----
-----
Orange	単価100円(内税)	2 個	200 円
-----
Banana	単価200円(内税)	3 個	600 円
Orange	単価100円(内税)	2 個	200 円
-----
Book1	単価500円(外税)	4 個	2160 円
Banana	単価200円(内税)	3 個	600 円
Orange	単価100円(内税)	2 個	200 円

問題2-2

URIAGELIST のノードを動的に確保する関数 URIAGELIST* newlist(void) を作成しなさい。ただし、領域を確保できなかった場合は NULL を返しなさい。また、 next メンバは NULL で初期化してください。

そして、次のテストプログラム、課題1で使用したプログラムと結合し、結果を示しなさい。

テストプログラム2-2


#include <stdio.h>
#include <stdlib.h>
#include "shohin.h"
#include "uriage.h"
#include "uriagelist.h"
int main(void){
  URIAGE u1={1,2};
  URIAGE u2={2,3};
  URIAGE u3={3,4};
  URIAGELIST *l0;
  URIAGELIST *l1;
  URIAGELIST *l2;
  URIAGELIST *l3;
  if((l0=newlist())==NULL){
    fprintf(stderr,"領域を確保できませんでした");
    return 2;
  }
  if((l1=newlist())==NULL){
    fprintf(stderr,"領域を確保できませんでした");
    free(l0);
    return 2;
  }
  if((l2=newlist())==NULL){
    fprintf(stderr,"領域を確保できませんでした");
    free(l1);
    free(l0);
    return 2;
  }
  if((l3=newlist())==NULL){
    fprintf(stderr,"領域を確保できませんでした");
    free(l2);
    free(l1);
    free(l0);
    return 2;
  }
  printUriageList(l0);
  printf("-----\n");
  l1->next=l0;
  l1->uriage=&u1;
  printUriageList(l1);
  printf("-----\n");
  l2->next=l1;
  l2->uriage=&u2;
  printUriageList(l2);
  printf("-----\n");
  l3->next=l2;
  l3->uriage=&u3;
  printUriageList(l3);
  printf("-----\n");
  free(l3);
  free(l2);
  free(l1);
  free(l0);
  return 0;
}

出力例2-2

-----
Orange	単価100円(内税)	2 個	200 円
-----
Banana	単価200円(内税)	3 個	600 円
Orange	単価100円(内税)	2 個	200 円
-----
Book1	単価500円(外税)	4 個	2160 円
Banana	単価200円(内税)	3 個	600 円
Orange	単価100円(内税)	2 個	200 円
-----

問題2-3

線形リストにおいて、動的に確保したすべてのノードをfree関数により解放する関数 void freeUriageList(URIAGELIST*l,int purge) を作成しなさい。なお、uriage メンバーは URIAGE 型の領域へのポインタであるが、その領域に関して、purge が 1 ならその領域も free により、開放する。また、 purge が 0 ならその領域は free を行わない。

なお、線形リスト終端に接続した空のノードのuriageは使用しないので、ここは purge が 1 でも free を実施しないこと。

そして、次のテストプログラム、課題1で使用したプログラムと結合し、結果を示しなさい。

テストプログラム2-3


#include <stdio.h>
#include <stdlib.h>
#include "shohin.h"
#include "uriage.h"
#include "uriagelist.h"
int main(void){
  URIAGE u1={1,2};
  URIAGE u2={2,3};
  URIAGE u3={3,4};
  URIAGE *up1;
  URIAGE *up2;
  URIAGE *up3;
  URIAGELIST *l0;
  URIAGELIST *l1;
  URIAGELIST *l2;
  URIAGELIST *l3;
  if((l0=newlist())==NULL){
    fprintf(stderr,"領域を確保できませんでした");
    return 2;
  }
  if((l1=newlist())==NULL){
    fprintf(stderr,"領域を確保できませんでした");
    free(l0);
    return 2;
  }
  if((l2=newlist())==NULL){
    fprintf(stderr,"領域を確保できませんでした");
    free(l1);
    free(l0);
    return 2;
  }
  if((l3=newlist())==NULL){
    fprintf(stderr,"領域を確保できませんでした");
    free(l2);
    free(l1);
    free(l0);
    return 2;
  }
  l1->next=l0;
  l1->uriage=&u1;
  l2->next=l1;
  l2->uriage=&u2;
  l3->next=l2;
  l3->uriage=&u3;
  printUriageList(l3);
  printf("-----\n");
  freeUriageList(l3,0);

  if((l0=newlist())==NULL){
    fprintf(stderr,"領域を確保できませんでした");
    return 2;
  }
  if((l1=newlist())==NULL){
    fprintf(stderr,"領域を確保できませんでした");
    free(l0);
    return 2;
  }
  if((l2=newlist())==NULL){
    fprintf(stderr,"領域を確保できませんでした");
    free(l1);
    free(l0);
    return 2;
  }
  if((l3=newlist())==NULL){
    fprintf(stderr,"領域を確保できませんでした");
    return 2;
  }
  if((up1=malloc(sizeof(URIAGE)))==NULL){
    fprintf(stderr,"領域を確保できませんでした");
    free(l2);
    free(l1);
    free(l0);
    return 2;
  }
  if((up2=malloc(sizeof(URIAGE)))==NULL){
	fprintf(stderr,"領域を確保できませんでした");
    free(l2);
    free(l1);
    free(l0);
    free(up1);
    return 2;
  }
  if((up3=malloc(sizeof(URIAGE)))==NULL){
    fprintf(stderr,"領域を確保できませんでした");
    free(l2);
    free(l1);
    free(l0);
    free(up2);
    free(up1);
    return 2;
  }
  *up1=u1;
  *up2=u2;
  *up3=u3;
  l1->next=l0;
  l1->uriage=up1;
  l2->next=l1;
  l2->uriage=up2;
  l3->next=l2;
  l3->uriage=up3;
  printUriageList(l3);
  printf("-----\n");
  freeUriageList(l3,1);
  return 0;
}

出力例2-3

Book1	単価500円(外税)	4 個	2160 円
Banana	単価200円(内税)	3 個	600 円
Orange	単価100円(内税)	2 個	200 円
-----
Book1	単価500円(外税)	4 個	2160 円
Banana	単価200円(内税)	3 個	600 円
Orange	単価100円(内税)	2 個	200 円
-----

問題2-4

URIAGEのポインターを受け取ると、URIAGELIST のノードで作られた線形リストの先頭に、ノードを追加することで追加する URIAGELIST* add(URIAGELIST* l, URIAGE* u) 関数を作成しなさい。なお、線形リストは、最初に l は空のノードを指しているものとする。また、戻り値は新しく追加したURIAGEのポインタを含むノードのポインタを返すものとし、追加に失敗した場合は NULL を返すものとする。

そして、次のテストプログラム、課題1で使用したプログラムと結合し、結果を示しなさい。

テストプログラム2-4


#include <stdio.h>
#include <stdlib.h>
#include "shohin.h"
#include "uriage.h"
#include "uriagelist.h"
int main(void){
  URIAGE u1={1,2};
  URIAGE u2={2,3};
  URIAGE u3={3,4};
  URIAGE* u[]={&u1,&u2,&u3,NULL};
  URIAGE **p;
  URIAGELIST *l;
  URIAGELIST *m;
  if((l=newlist())==NULL){
    fprintf(stderr,"領域を確保できませんでした");
    return 2;
  }
  for(p=u;*p!=NULL;p++){
    if((m=add(l,*p))==NULL){
      fprintf(stderr,"領域を確保できませんでした");
      freeUriageList(l,0);
      return 2;
    }
    printf("追加%s\n", m->uriage==*p?"Ok":"NG");
    printUriageList(l);
    printf("-----\n");
  }
  freeUriageList(l,0);
  return 0;
}

出力例2-4

追加Ok
Orange	単価100円(内税)	2 個	200 円
-----
追加Ok
Banana	単価200円(内税)	3 個	600 円
Orange	単価100円(内税)	2 個	200 円
-----
追加Ok
Book1	単価500円(外税)	4 個	2160 円
Banana	単価200円(内税)	3 個	600 円
Orange	単価100円(内税)	2 個	200 円
-----

以下、ヘッダファイルを示す。

uriagelist.h


typedef struct uriagelist {
  struct uriagelist* next;
  URIAGE *uriage;
}URIAGELIST;
void printUriageList(URIAGELIST* l);
URIAGELIST* newlist(void);
void freeUriageList(URIAGELIST*l,int purge);
URIAGELIST* add(URIAGELIST* l, URIAGE* u);

課題1

レポート締切日: 2019年6月14日(金)18:10
提出先: 2 号館 3F レポートボックス

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

なお、遅れレポートは教員に直接提出してください。遅れた方が有利にならない範囲内で採点します。遅れレポートの最終期限は7月25日18:10(授業開始時)です。

問題

商品の売上の集計表を出力する。

問題1-1

始めに商品情報のデータ型 SHOHIN を下記のように定める。


#define ZEI (1.08)
typedef struct{
  char* name;
  int tanka;
  int sotozei;
} SHOHIN;

name は商品名を表す文字列、tanka は単価、sotozei は 0 なら単価は消費税を含むが、 1 なら外税表示のため実際の販売単価は tanka*ZEI となることを意味する。

これを表示する void printshohin(SHOHIN p) を作成せよ。但し、この関数で表示するための printf に制御文字列は "%s\t単価%d円(%s)" とし、例えば次のように表示させるとする(改行しない)。

Apple    単価150円(内税)

shohin.h, shohin.c を下記のように定める。配列shohin は商品リストを表し、単価が 0 の項目を番兵とする。

shohin.h


#define ZEI (1.08)
typedef struct{
  char* name;
  int tanka;
  int sotozei;
} SHOHIN;
extern SHOHIN shohin[];
void printshohin(SHOHIN s);

shohin.c


#include <stdio.h>
#include "shohin.h"
SHOHIN shohin[]={{"Apple",150},{"Orange",100},{"Banana",200},{"Book1",500,1},{"",0}};

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

テストプログラム1-1


#include <stdio.h>
#include "shohin.h"
int main(void){
  int i;
  for(i=0;shohin[i].tanka!=0; i++){
    printf("商品コード %d 品名 ",i);
    printshohin(shohin[i]);
    printf("\n");
  }
  return 0;
}

出力例1-1

商品コード 0 品名 Apple	単価150円(内税)
商品コード 1 品名 Orange	単価100円(内税)
商品コード 2 品名 Banana	単価200円(内税)
商品コード 3 品名 Book1	単価500円(外税)

問題1-2

売上を示す構造体を次に示す。


typedef struct {
  int code;
  int num;
}URIAGE;

code は配列 shohin の添字、num は売上個数を示す。

この時、この構造体のポインターを受け取り、商品名、単価、内税／外税の区別、個数、税込み購入価格を表示し、税込み購入価格(int型)を返す int printUriage(URIAGE* q)関数を作りなさい。そして、下記のプログラムと結合し、実行結果を報告せよ。

テストプログラム1-2


#include <stdio.h>
#include "shohin.h"
#include "uriage.h"
int main(void){
  URIAGE u1={0,3};
  URIAGE u2={3,4};
  int shokei;
  shokei = printUriage(&u1);
  printf("\t%d\n",shokei);
  shokei = printUriage(&u2);
  printf("\t%d\n",shokei);
  return 0;
}

出力例1-2

Apple	単価150円(内税)	3 個	450 円
	450
Book1	単価500円(外税)	4 個	2160 円
	2160

問題1-3

番兵としてcode=-1を持つURIAGE の配列を渡すと、各売上を表示し、最後に小計を出力し、さらにその小計を返す int printUriageArray(URIAGE u[]) を作りなさい。そして、下記のプログラムと結合し、実行結果を報告せよ。

テストプログラム1-3


#include <stdio.h>
#include "shohin.h"
#include "uriage.h"
int main(void){
  URIAGE u[]={{0,3},{1,2},{2,1},{3,4},{-1}};
  int shokei;
  shokei = printUriageArray(u);
  printf("\t%d\n",shokei);
  return 0;
}

出力例1-3

Apple	単価150円(内税)	3 個	450 円
Orange	単価100円(内税)	2 個	200 円
Banana	単価200円(内税)	1 個	200 円
Book1	単価500円(外税)	4 個	2160 円
小計:				3010 円
	3010

問題1-4

番兵として NULL を持つ、売上の配列の番地の配列を受け取り、各売上配列ごとに売上の表示と小計を出力し、--------------------で区切って表示し、最後に合計金額を表示し、合計金額を返す int printUriageTrans(URIAGE** u) を作りなさい。そして、下記のプログラムと結合し、実行結果を報告せよ。


#include <stdio.h>
#include "shohin.h"
#include "uriage.h"
int main(void){
  URIAGE uriage0[]={{2,1},{1,6},{-1}};
  URIAGE uriage1[]={{0,3},{1,2},{2,1},{-1}};
  URIAGE uriage2[]={{3,1},{-1}};
  URIAGE uriage3[]={{1,3},{0,1},{-1}};
  URIAGE uriage4[]={{1,3},{0,1},{3,2},{-1}};
  URIAGE* uriage[]={uriage0, uriage1, uriage2, uriage3, uriage4, NULL};
  int total;
  total=printUriageTrans(uriage);
  printf("%d\n",total);
  return 0;
}

出力例1-4

Banana	単価200円(内税)	1 個	200 円
Orange	単価100円(内税)	6 個	600 円
小計:				800 円
------------------
Apple	単価150円(内税)	3 個	450 円
Orange	単価100円(内税)	2 個	200 円
Banana	単価200円(内税)	1 個	200 円
小計:				850 円
------------------
Book1	単価500円(外税)	1 個	540 円
小計:				540 円
------------------
Orange	単価100円(内税)	3 個	300 円
Apple	単価150円(内税)	1 個	150 円
小計:				450 円
------------------
Orange	単価100円(内税)	3 個	300 円
Apple	単価150円(内税)	1 個	150 円
Book1	単価500円(外税)	2 個	1080 円
小計:				1530 円
------------------
合計:		4170 円
4170

以下、ヘッダファイルと補助プログラムを示す。

shohin.h


#define ZEI (1.08)
typedef struct{
  char* name;
  int tanka;
  int sotozei;
} SHOHIN;
extern SHOHIN shohin[];
void printshohin(SHOHIN s);

shohin.c


#include <stdio.h>
#include "shohin.h"
SHOHIN shohin[]={{"Apple",150},{"Orange",100},{"Banana",200},
{"Book1",500,1},{"",0}};

uriage.h


typedef struct {
  int code;
  int num;
}URIAGE;
int printUriage(URIAGE* q);
int printUriageArray(URIAGE q[]);
int printUriageTrans(URIAGE **p);

レポート作成上の注意

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

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