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

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

課題2

レポート締切日: 2010年7月15日(木)20:00
提出先: 7 号館 3F レポートボックス

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

課題 2-2 の最後の出力文に誤りがあったため、修正しました(2010/7/7)。

stringToChararray で得た文字配列を正しく free するように、修正しました(2010/7/8)。

可変長文字列を扱うため、線形リストによる実装を考える。下記の構造体を定義し、String 型変数を文字列として扱うこととする。


typedef struct node {
  struct node * next;
  char moji;
} Node;
typedef struct string {
  Node * top;
} String;

課題2-1

与えられた String 型文字列に対して、文字列の文字数を返す関数 int stringLength(String s) を作りなさい。そして、下記のテストプログラムで正常に動作することを確かめなさい。

テストプログラム


#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  struct node * next;
  char moji;
} Node;
typedef struct string {
  Node * top;
} String;
int stringLength(String s){
/* ここにプログラムを書く */
}
int main(void){
  Node nil,a,b,c;
  String s;
  nil.next=NULL;
  nil.moji='\0';
  c.next=&nil;
  c.moji='C';
  b.next=&c;
  b.moji='B';
  a.next=&b;
  a.moji='A';
  s.top=&a;
  printf("%d\n",stringLength(s));
  return 0;
}

出力例

課題2-2

与えられた String 型文字列に対して、通常の C 言語の文字配列を返す関数 char* stringToChararray(String s) を作りなさい。そして、下記のテストプログラムで正常に動作することを確かめなさい。なお、 malloc でメモリを確保できないときは exit(1) で終了しなさい。

テストプログラム


#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  struct node * next;
  char moji;
} Node;
typedef struct string {
  Node * top;
} String;
int stringLength(String s){
/* 課題 2-1 のプログラム */
}
char * stringToChararray(String s){
/* ここにプログラムを書く */
}
int main(void){
  Node nil,a,b,c;
  String s;
  char *carray;
  nil.next=NULL;
  nil.moji='\0';
  c.next=&nil;
  c.moji='C';
  b.next=&c;
  b.moji='B';
  a.next=&b;
  a.moji='A';
  s.top=&a;
  carray=stringToChararray(s);
  printf("%s\n",carray);
  free(carray);
  return 0;
}

出力例

ABC

課題2-3

C 言語の文字配列を String 型に変換する String chararrayToString(char * s) を作りなさい。そして、下記のプログラムと結合して、正常に動作することを確認しなさい。なお、 malloc でメモリを確保できないときは exit(1) で終了しなさい。


#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  struct node * next;
  char moji;
} Node;
typedef struct string {
  Node * top;
} String;
int stringLength(String s){
/* 課題 2-1 のプログラム */
}
char* stringToChararray(String s){
/* 課題 2-2 のプログラム */
}
String chararrayToString(char* s){
/* ここにプログラムを書く */
}
void deleteNodes(Node *p){
  if(p->next==NULL) return;
  deleteNodes(p->next);
  free(p);
}
void deleteString(String s){
  deleteNodes(s.top);
}
int main(void){
  String s;
  char *carray;
  s=chararrayToString("ABCD");
  carray=stringToChararray(s);
  printf("%s\n",carray);
  free(carray);
  deleteString(s);
  s=chararrayToString("");
  carray=stringToChararray(s);
  printf("%s\n",carray);
  free(carray);
  deleteString(s);
  return 0;
}

出力例

ABCD

課題 2-4

String である dest, source に対して、 dest の直後に source をつなげる void appendString(String *dest, String source) 関数を作りなさい。そして、以下のプログラムと結合し、正しく動作することを確かめなさい。


#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  struct node * next;
  char moji;
} Node;
typedef struct string {
  Node * top;
} String;
int stringLength(String s){
/* 課題 2-1 のプログラム */
}
char* stringToChararray(String s){
/* 課題 2-2 のプログラム */
}
String chararrayToString(char* s){
/* 課題 2-3 のプログラム */
}
void appendString(String *dest, String source){
/*ここにプログラムを書く*/
}
    
void deleteNodes(Node *p){
  if(p->next==NULL) return;
  deleteNodes(p->next);
  free(p);
}
void deleteString(String s){
  deleteNodes(s.top);
}
int main(void){
  String s,t;
  int i;
  char *carray;
  s=chararrayToString("");
  for(i=0; i<4; i++){
    t=chararrayToString("ABCD");
    appendString(&s,t);
  }
  carray=stringToChararray(s);
  printf("%s\n",carray);
  free(carray);
  deleteString(s);
  return 0;
}

出力例

ABCDABCDABCDABCD

おまけ

なお、次の関数を利用するとデータ構造がよく分かりプログラムの動きがつかみやすくなるので、適宜利用してよい。


void printStructure(String s){
  Node *p;
  printf("start:%p\n",s.top);
  p=s.top;
  while(p!=NULL){
    printf("next=%p, moji=%c\n",p->next,p->moji);
    p=p->next;
  }
  printf("---------------\n");
}

課題1

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

次の 4 つの課題を合わせて行い、報告しなさい。

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

注: init の引数に学籍番号の下 3 桁を入れる場合、先頭の 0 を取り除いて入れてください。先頭に 0 がある整数は 8 進数として別の数に解釈されてしまいます(2010/6/15)。

なお、1-5 のテストプログラムに一行追加しました。 (2010/6/10)

構造体 SEISEKI が定義され、その配列がグローバルに定義されているとします。但し、配列の番兵は文字ポインタ型メンバに NULL が入っているものとします。 (なお、配列の先頭には init 関数により学籍番号から計算した値を入れます)


#include <stdlib.h>
typedef struct seiseki {
  char* id;
  int suugaku;
  int eigo;
  int rika1;
  int rika2;
} SEISEKI;
SEISEKI soten[]={
  {NULL},
  {"kc10001",80,60,70,60},
  {"kc10002",70,90,50,100},
  {"kc10003",100,50,70,30},
  {"kc10004",20,30,40,50},
  {"kc10005",70,70,70,70},
  {"kc10006",60,65,70,75},
  {NULL}};
char id0[10];
double getTensu(){
  return (double)rand()/RAND_MAX*101;
}
void init(int no){
  srand(no);
  sprintf(id0,"kc10%03d",no+200);
  soten[0].id=id0;
  soten[0].suugaku=getTensu();
  soten[0].eigo=getTensu();
  soten[0].rika1=getTensu();
  soten[0].rika2=getTensu();
}

この時、この配列に対して成績処理をするプログラムを考えます。但し、このデータはあくまでもテスト用のデータであるので、データが 7 こしかないことを仮定するなど、データの自由度を奪うようなプログラムを作成してはならない。

課題1-1

点数の集計方法を決める double kijun(SEISEKI s) を作ります。ここでは、構造体 s に対して、suugaku の1.5 倍したものと、eigo はそのまま、 rika1 とrika2 は多い方だけの3つの数の合計を double 型で返す関数を作ります。そして、以下のプログラムと結合して正しいかどうかを確かめなさい。

テストプログラム


#include <stdio.h>
#include <stdlib.h>
typedef struct seiseki {
  char* id;
  int suugaku;
  int eigo;
  int rika1;
  int rika2;
} SEISEKI;
double kijun(SEISEKI s){
/* ここにプログラムを書く */
}
int main(void){
  SEISEKI s1={"kc10001",1,2,3,4};
  SEISEKI s2={"kc10002",5,6,8,7};
  printf("%f %f\n",kijun(s1),kijun(s2));
  return 0;
}

これにより、 7.5 と 21.5 が出れば良い。

課題 1-2

学籍番号と各点数とそれから計算される kijun 点数を表示する hyouji(SEISEKI* p) を作成しなさい。 p は SEISEKI の配列を指します。一つの学籍番号に対する成績は一行に表示するようにします。そして、以下のプログラムと結合し、出力結果が以下の出力例と同じようにになることを確認しなさい。但し、下記のプログラムにおいて、 init 関数の引数には学籍番号の下3桁を入れて実行しなさい。

プログラム


#include <stdio.h>
#include <stdlib.h>
typedef struct seiseki {
  char* id;
  int suugaku;
  int eigo;
  int rika1;
  int rika2;
} SEISEKI;
SEISEKI soten[]={
  {NULL},
  {"kc10001",80,60,70,60},
  {"kc10002",70,90,50,100},
  {"kc10003",100,50,70,30},
  {"kc10004",20,30,40,50},
  {"kc10005",70,70,70,70},
  {"kc10006",60,65,70,75},
  {NULL}};
char id0[10];
double getTensu(){
  return (double)rand()/RAND_MAX*101;
}
void init(int no){
  srand(no);
  sprintf(id0,"kc10%03d",no+200);
  soten[0].id=id0;
  soten[0].suugaku=getTensu();
  soten[0].eigo=getTensu();
  soten[0].rika1=getTensu();
  soten[0].rika2=getTensu();
}

ここまでは上で示した物と同じ


double kijun(SEISEKI s){
 /* 課題 1-1 で作成したもの */
}
void hyouji(SEISEKI* p){
 /* ここにプログラムを書く */
}
int main(void){/* テストプログラム */
  init(000 /* 学籍番号を入れる */ );
/* 先頭の 0 は取り除いてください */
  hyouji(soten);
  return 0;
}

出力例

kc10200: 84 39 79 80 245.000000
kc10001: 80 60 70 60 250.000000
kc10002: 70 90 50 100 295.000000
kc10003: 100 50 70 30 270.000000
kc10004: 20 30 40 50 110.000000
kc10005: 70 70 70 70 245.000000
kc10006: 60 65 70 75 230.000000

最初の行は各自の学籍番号により異なります。

課題 1-3

課題 1-2 で表示された kijun の値について、手計算、電卓、または表計算ソフトにより、平均値を求めなさい。

課題 1-4

人数を求める関数 int ninzu(SEISEKI* p) を作成しなさい。そして下記のプログラムを実行し、出力が 7 になることを確認しなさい。

テストプログラム

上記のプログラムの main 関数部分だけを差し替えます。


int main(void){
  init(000 /* 学籍番号を入れる */ );/* 先頭の 0 は取り除いてください */
  printf("%d\n",ninzu(soten));
  return 0;
}

課題1-5

各 kijun で計算した値を元に、平均点を返す double heikin(SEISEKI* p) を作成しなさい。そして次のテストプログラムと結合して、結果を表示させなさい。そして、課題 1-3 で求めた平均値と一致しているか確かめなさい。

テストプログラム


int main(void){
  init(000 /* 学籍番号を入れる */ );/* 先頭の 0 は取り除いてください */
  printf("%f\n",heikin(soten));
  return 0;
}

注

マイクロソフトの Visual Studio で上記のプログラムを動かすと大抵 suugaku が 0 点になってしまいますが、これは Visual Studio の乱数生成の問題です。データが 0 点なのは問題ありません。

レポート作成上の注意

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

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