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

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

課題1について

課題 1 のレポートで 1 回で受け取りになった人は 5 人だけです。 まだ、返却してない再レポートが多数あります。 レポートの結果を聞いてない人は早めに坂本まで(授業中、または 11 号館 12 階 1206 室)結果を聞きに来てレポートを受け取って下さい。

課題1

レポート締切日: 2005年11月10日(木)

次の 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

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

1. 入力は整数型のポインタ
2. 入力データはポインタから順に正の整数が並び、最後に -1 の値で終了す る
3. この関数は入力されたポインタに対して、一番最後の正の整数値を 先頭に移動し、残りのデータは一つずつ後ろにずらす。

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

課題 1-3

課題 1-1, 1-2 で作成した dispArray(), rotate() に対して次のプログラム を動かし結果を報告しなさい。

#include <stdio.h>
void dispArray(int *p);
void rotate(int *p);
#define N 99
main(){
  int *a[5];
  int b[]={-1};
  int c[]={1,-1};
  int d[]={1,2,3,-1};
  int e[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</*学籍番号の下 3 桁*/; j++){
      rotate(a[i]);
    }
    dispArray(a[i]);
  }
}

課題2

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

問題

プログラム 2 は指定したファイルを読み込み、英数字(AからZとaからzと0か ら9)の塊を表示するプログラムです。ここで isalnum 関数は文字を読み、文 字が英字が数字だった時は 0 以外、英字でも数字でもなかった場合は 0 を返 すものです。 このプログラムと strcmp 関数(string.h を include)を利用して、この塊が 出て来る頻度を大文字小文字を区別した辞書順(strcmp が定める文字列の順序) に並べるプログラムを作りたい。

課題2-1

プログラム 2 にある if 文(10行目、13行目、14行目、15 行目、29行目)それ ぞれの意味を詳しく説明しなさい。 「fhにfopenの結果を入れ……」という単なる直訳日本語は不可。

課題2-2

プログラム2にデータ3を入力して実行させ、出力を求めなさい。 そして、どうしてそのような出力が出るかという観点で、プログラム 2 を説 明しなさい。

課題2-3

題意を満たすプログラムを作る前に、テスト方法を考えます。 もしプログラムが完成したとして、そのプログラムにはデータ3 を入力すると どのような出力をしますか? コンピュータを使わず、自分の頭で考えて結果を書きなさい。

なお辞書順とは、文字列の比較法の一つで、文字列の先頭から順に比較してい き、最初に異なった文字の大小関係とします。 但し、途中で文字が無くなった場合は無い方が小さいとします。

例

• 0<9<A<Z<a<z
• aaa<aaaa
• aaa0<aaa1

def abc
abc def ghi

abc: 2
def: 2
ghi: 21

課題2-4

題意を満たすプログラムを作成しなさい。 なお、strcmp関数は二つの文字配列へのポインタを引数に取り、左側の引数の方が小 さい時は負の整数値、等しい時は 0、大きい時は正の正数値を返す関数です。

課題2-5

課題2-4 で完成したプログラムにデータ 3を入力し出力結果を示しなさい。 そして、自分で計算した結果と一致するか確認しなさい。

課題2-6

作成したプログラムのソースコード自身を作成したプログラムに入力し、出力 を示しなさい。

プログラム2

#include <stdio.h>
#include <ctype.h>
#define MAX 80
int main(){
  int c,i;
  int mozi=0;
  char buffer[MAX+1];
  char filename[]="div.c";
  FILE *fh;
  if((fh=fopen(filename,"r"))!=NULL){
    i=0;
    while((c=getc(fh))!=EOF){
      if(mozi){
	if(isalnum(c)){
	  if(i<MAX){
	    buffer[i++]=c;
	  }else{
	    fprintf(stderr,"Overflow\n");
	    fclose(fh);
	    return 1;
	  }
	}else{
	  mozi=0;
	  buffer[i]='\0';
	  i=0;
	  printf("%s\n",buffer);
	}
      }else{
	if(isalnum(c)){
	  mozi=1;
	  buffer[i++]=c;
	}
      }
    }
    fclose(fh);
    return 0;
  }else{
    fprintf(stderr,"%s:File Not Found\n",filename);
    return 2;
  }
}

データ3

#include <stdio.h>
int main(){
  int i,a[]={2,3,1,-1};
  for(i=0;a[i]!=-1;i++){
    printf("%d\n",a[i]);
  }
  return 0;
}