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

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

課題2

レポート締切日: 2007年7月19日(木)20:00

提出先: 7 号館 3F レポートボックス

なお、遅れレポートは受け付けません。

問

コンピュータのメモリが許す限り文字を扱う仕組を作りたい。そこで、文字を入れる線形リストを作成する。

線形リストの構造体は typedef で ST と名付ける。

管理変数は以下のような構造体である。


typedef struct str{
    ST * top;
    ST * bottom;
    int count;
} STR;

STR* newstr(void) は管理変数を初期化し、長さ 0 の文字列を作る関数である。
int straddchar(STR* s, char c) は管理変数のポインタと文字 c から、文字列の最後に c を付加する関数である。成功したら 1 を、失敗したら 0 を返す。
void strdisp(STR* s) は文字列を表示する関数である。
int strcount(STR* s) は次のような文字列の文字数を返す関数である。
```
int strcount(STR* s){
    return s->count;
}
```
void strfree(STR* s) は文字列を確保したメモリーを開放する関数である。

設問 2-1

以上の構造体 ST, STR の定義と newstr(), straddchar(), strdisp(), strcount(), strfree() のプロトタイプ宣言を含むヘッダファイル str.h を作成しなさい。

設問 2-2

newstr(), straddchar(), strdisp(), strfree() の実際の定義を書いた str.c を作成しなさい。各関数の説明では特にポインタの利用法や線形リストの構造などを詳しく説明しなさい。

設問 2-3

作成した関数と以下のプログラム kadai2-3.c を結合し、結果を求めなさい。


#include <stdio.h>
#include <stdlib.h>
#include "str.h"
int main(void){
  FILE* f;
  char c;
  STR * s;
  s=newstr();
  f=fopen("kadai2-3.c","r");
  while((c=getc(f))!=EOF){
    straddchar(s,c);
  }
  strdisp(s);
  printf("\nThe number of characters is %d.\n",strcount(s));
  strfree(s);
  fclose(f);
  return 0;
}

設問 2-4

作成した関数と以下のプログラム kadai2-4.c を結合し実行させ、確保する文字数とかかる時間の関係を次のようにして調べなさい。プログラム中の MOJISU を例えば 100万、 200万、 500 万、 1000万、2000万、 5000万、1億など値を変え、両対数グラフで表しなさい。(秒以下は切り捨てられるため、 0 秒や 1 秒だと誤差が大きいです)。計測点はあくまでも例で、実測する際はコンピュータの動作速度などにより調整しなさい。おおよそ 10 秒以上、 10 分以内、測定点を 4 点以上になるようにしなさい。


#define MOJISU 10000000
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "str.h"
int main(void){
  STR * s;
  time_t from,to;
  int i;
  s=newstr();
  time(&from);
  for(i=0; i<MOJISU; i++){
    if(!straddchar(s,'x')){
      break;
    }
  }
  time(&to);
  printf("It took %d seconds",to-from);
  printf(" to make a string of length %d.\n",i);
  strfree(s);
  return 0;
}

課題1

レポート締切日: 2007年6月14日(木)20:00

提出先: 7 号館 3F レポートボックス

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

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

課題 1-1

次の条件を満たす関数 dispArray() を作りなさい。

入力は整数型のポインタ
入力されたポインタに対して、順に格納されている正の整数を 10 個ずつで改行しながら表示する。
入力の参照先に -1 が入っていたら終了する

例えば整数型の配列 a[] が 1 から 15 まで順に入っていて、最後に -1 が入っている時、dispArray(a) は次のような出力をします。

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15

なお、実際に関数を作成したら、このデータを与えるテストプログラムを作り、正常に動作することを確認し、報告すること。与えるデータの個数として、 0 個、 1個、 10 個、 11 個、20 個、21個などを試して下さい。

課題 1-2

次の条件を満たす関数 void compnext(int*)を作りなさい。

入力は整数型のポインタ
入力データはポインタから順に正の整数が並び、最後に -1 の値で終了する
ポインタの指している値(x とする)のとなりの値(y とする)が -1 で無い限り以下を繰り返す。
1. x>y の時、 x と y の値を交換する。
2. ポインタが y を指すようにする。

例えば、 {3,2,1,-1} を入力したときは次のようになります。

x=3, y=2: x>y なので、値は交換され、 {2,3,1,-1} となります。
x=3, y=1: x>y なので、値は交換され、 {2,1,3,-1} となります。
x=3, y=-1: y==-1 なので、終了します。

したがって、最終的に {2,1,3,-1} となります。

作成した compnext() と既に作成した disparray() と以下のテストプログラムを結合し、正常に動作するか確かめなさい。また動作結果を元に、この compnext() はどのような性質を持つか説明しなさい。


#include <stdio.h>
void disparray(int *p);
void compnext(int *p);
int main(void){
  int a[24][5]={
    {1,2,3,4,-1},{1,2,4,3,-1},{1,3,2,4,-1},
    {1,3,4,2,-1},{1,4,2,3,-1},{1,4,3,2,-1},
    {2,1,3,4,-1},{2,1,4,3,-1},{2,3,1,4,-1},
    {2,3,4,1,-1},{2,4,1,3,-1},{2,4,3,1,-1},
    {3,2,1,4,-1},{3,2,4,1,-1},{3,1,2,4,-1},
    {3,3,4,1,-1},{3,4,2,1,-1},{3,4,1,2,-1},
    {4,2,3,1,-1},{4,2,1,3,-1},{4,3,2,1,-1},
    {4,3,1,2,-1},{4,1,2,3,-1},{4,1,3,2,-1}};
  int i;
  for(i=0;i<24;i++){
    compnext(a[i]);
    disparray(a[i]);
  }
  return 0;
}

課題 1-3

次の条件を満たす関数 void bubble(int* p) を作りなさい。

入力は整数型のポインタ
入力されたポインタを整数の配列の先頭番地とみなし、 -1 が来るまでの要素数と同じ回数 compnext(p) を呼びます。

例えば p が {3,2,1-1} という配列の先頭番地を示している時、 bubble(p) は compnext(p) を 3 回呼び出します。

課題 1-4

disparray, compnext, bubble と以下のプログラムを結合し、実行させ、実行結果を報告しなさい。なお、プログラムの冒頭部分の #define 文で学籍番号の下3桁の値を与えなさい。


#include <stdio.h>
#define N 999
void disparray(int *p);
void compnext(int *p);
void bubble(int *p);
int main(void){
  int a[N+1];
  int i, k;
  for(i=0,k=3;i<N;i++){
    a[i]=k=(k*3)%N;
    if((k==0)||(k==1)){
      a[i+1]=-1;
      printf("%d %d\n",a[i],i);
      break;
    }
  }
  a[N]=-1;
  disparray(a);
  bubble(a);
  printf("-----------------\n");
  disparray(a);
  return 0;
}

課題 1-5

関数 bubble() は何をする関数なのか、 compnext() の性質を踏まえて、考察しなさい。

レポート作成上の注意

プログラミングのレポートでは必ずプログラムの説明をすること。その時に、一行一行を日本語に直訳するのではなく、プログラムを機能毎に区分し、機能の実現方法を説明すること。プログラムに一行ずつコメントを入れてもプログラムの説明とは見なしません。
「問題を解きなさい」という問に対して「解きました。合ってました」は正解ではなありません。「プログラムを作りなさい」という問題については、作成の手順の説明をすること。「テストをしなさい」という問題については、(1)テスト設計(なにを行うと正当性が示せるのか、根拠を示す)、(2)テストの手法の実現方法、(3)予想されるテスト結果、(4)得られたテスト結果、(5)テストの成否の判定などを要領良く説明して下さい。
レポートは手書きでも良いですが、プログラムの実行結果だけは必ずコンピュータの出力の印刷にして下さい。
考察は必ず書いて下さい。ネタがない人は以下を参考にして下さい。
- 途中失敗を経験した場合、その失敗した内容となぜ失敗したのか
- 学籍番号以外の数を入れた時の観察(特に小さい数を入れた時)
- ポインタ、関数、配列などの仕組みについて、新しく分かったこと

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