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

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

課題1

レポート締切日: 2006年11月16日(木)20:00

提出先: 授業中に直接手渡し、またはレポートボックス

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

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

課題 1-1

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

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

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

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

なお、実際に関数を作成したら、このデータを与えるテストプログラムを作り、 正常に動作することを確認し、報告すること。

課題 1-2

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

1. 入力は整数型のポインタと整数値 n
2. 入力データはポインタから順に正の整数が並び、最後に -1 の値で終了す る
3. この関数は入力されたポインタが参照する正の整数の要素に対して、 要素の値を二乗して、 n で割った余りを求め、その得られた値を要素の値と して格納する。

例えば 1, 2, 3, -1 という配列の先頭番地と 3 を square() に与えると 1, 1, 0, -1 となります。

課題 1-3

課題 1-1, 1-2 で作成した dispArray(), square() に対して次のプログラム を結合して動かし、結果を報告しなさい。 また、なぜそのような出力が得られるのか、手計算で計算の要領を示すなどし て、説明しなさい。

#include <stdio.h>
void dispArray(int *p);
void square(int *p, int n);
#define N 64
int main(void){
  int *a[5];
  int b[]={-1};
  int c[]={1,-1};
  int d[]={1,2,3,-1};
  int e[N+1];
  int size[]={1,2,4,N+1};
  int i,j;
  for(i=0;i<N;i++){
    e[i]=i;
  }
  e[N]=-1;
  a[0]=b; a[1]=c; a[2]=d; a[3]=e; a[4]=NULL;
  for(i=0;a[i]!=NULL;i++){
    dispArray(a[i]);
    for(j=0;j</* 学籍番号の下三桁 */; j++){
      square(a[i],size[i]-1);
    }
    dispArray(a[i]);
  }
  return 0;
}

レポート作成上の注意

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

課題2

レポート締切日: 2007年1月11日(木)20:00 但し、 4 年生以上で卒業するため にどうしても単位が必要な人は、冬休み中にやりとり可能なメールアドレ スをレポート表紙に書いて 2006年12月21日(木)までに出して下さい。

提出先: レポートボックス

問題: 可変長文字列ライブラリ作成し、テストを行いたい。以下の課題に答えなさい。

課題 2-1

以下の仕様を満たす strsize, addchararray,appendstr,fputstr を作成しなさい。

仕様

STR* newstr(void)

空の文字列を表す構造体をメモリ上に作り、その番地を返す。 確保できなかったときは NULL を返す。

int addchar(STR *s, char c)

文字列の終わりに一文字加える。 付け加えるのに成功したら 1、失敗したら 0 を返す。

int strsize(STR *s)

このプログラムを作成すること。 文字列の長さを返す。

int addchararray(STR *s,char *c)

このプログラムを作成すること。 C 言語の文字配列や、文字列定数を文字列の終わりに付け加える。 付け加えるのに成功したら 1、失敗したら 0 を返す。

void appendstr(STR *s, STR *t)

このプログラムを作成すること。 文字列 s の後ろに t を接続する。 なお、文字列 t は失われる(関数の最後で free(t) を実施する)。

int fputstr(FILE *fh, STR *s)

このプログラムを作成すること。 ファイルハンドルに対し文字列を出力する。 出力した文字数を返す。

int putstr(STR *s)

標準出力に対し文字列を出力する。 出力した文字数を返す(fputstr より作られる)。

str.h

#include <stdio.h>
typedef struct slist {
  char moji;
  struct slist *next;
} SLIST;
typedef struct str {
  SLIST *begin, *end;
  int size;
} STR;
STR* newstr(void);
int strsize(STR *s);
int addchar(STR *s, char c);
int addchararray(STR *s,char *c);
void appendstr(STR *s, STR *t);
int fputstr(FILE *fh, STR *s);
#define putstr(s) fputstr(stdout,s)

str.c(訂正しました(2006/12/14))

#include <stdio.h>
#include <stdlib.h>
#include "str.h"
STR* newstr(void){
  STR *newstr;
  SLIST *newlist;
  newlist=(SLIST*)malloc(sizeof(SLIST));
  if(newlist==NULL){
    return NULL;
  }
  newstr=(STR*)malloc(sizeof(STR));
  if(newstr==NULL){
    free(newlist);
    return NULL;
  }
  newlist->next=NULL;
  newstr->begin=newstr->end=newlist;
  newstr->size=0;
  return newstr;
}
int addchar(STR *s, char c){
  SLIST *newlist;
  newlist = (SLIST*) malloc(sizeof(SLIST));
  if(newlist==NULL){return 0;}
  s->size++;
  newlist->moji=c;
  newlist->next=NULL;
  s->end->moji=c;
  s->end->next=newlist;
  s->end=newlist;
  return 1;
}
int strsize(STR *s){
 /*自分で作る*/
}
int addchararray(STR *s,char *c){
 /* 自分で作る */
}
void appendstr(STR *s, STR *t){
  /*自分で作る*/
  free(t);
}
int fputstr(FILE *fh, STR *s){
  /* 自分で作る */
}

課題2-2

作成したライブラリを使用した下記のサンプルプログラムを動かし、結果を報告しなさい。

サンプルプログラム

#include <stdio.h>
#include "str.h"
#define nullcheck(a) if((a)==NULL){fprintf(stderr,"memory error\n");return 1;}
#define zerocheck(a) if(!(a)){fprintf(stderr,"memory error\n");return 1;}
int main(void){
  STR *s1, *s2;
  nullcheck(s1=newstr());
  nullcheck(s2=newstr());
  zerocheck(addchararray(s1,"abcdef"));
  zerocheck(addchararray(s2,"ghijklmn"));
  printf("文字列");
  putstr(s1);
  printf("(長さ %d)",strsize(s1));
  printf("と文字列");
  putstr(s2);
  printf("(長さ %d)",strsize(s2));
  printf("を接続したら、文字列");
  appendstr(s1,s2);
  putstr(s1);
  printf("(長さ %d)になります。\n",strsize(s1));
  return 0;
}

ヒント

fprintf は出力した文字数を返します。