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

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

課題1

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

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

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

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

課題 1-1

文字配列の文字数(空白などを含む)を返す関数 count(char *s) を作成しなさい。 また、下記のプログラムによりテストを行い、結果を示しなさい。

#include <stdio.h>
int count(char *s){
  /* ここにプログラムを書く */
}
int main(void){
  char a[]="This is a pin.";
  printf("文字列 %s の文字数は %d です。\n",a,count(a));
  return 0;
}

課題 1-2

課題 1-1 で作成した count 関数を使い、次のプログラムAを改造して、各文字 列の長さを表示するようにしなさい。 なお、 a は char * 型の配列で、各要素 a[0], a[1], ... にはそれぞれ、 "This is a pin." の先頭番地、 "This question ..." の先頭番地, ... が入る。

プログラムA

#include <stdio.h>
void dispStrings(char **s){
  char **p;
  for(p=s; *p!=NULL; p++){
    printf("%s\n",*p);
  }
}
int main(void){
  char *a[]={"This is a pin.", "This question is not so difficult.",
    "You should understand what the pointer is.",NULL};
  dispStrings(a);
  return 0;
}

改造の仕方は次のようにすること。

1. count 関数を加える
2. dispStrings という関数名を dispCount に換える
3. 表示を「文字列 xxx の長さは n」のようにする

課題 1-3

文字列を大文字にして表示する関数 void dispInCapitals(char *s) を作りなさい。 そして、以下のプログラムでテストを行い、結果を示しなさい。

#include <stdio.h>
int dispInCapitals(char *s){
  /* ここにプログラムを書く */
}
int main(void){
  char a[]="This is a pin.";
  dispInCapitals(a);
  return 0;
}

課題 1-4

課題 1-3 で作成した dispInCapitals 関数を利用して、文字列(文字ポインタ) の配列を受け取り、全ての文字列を大文字で表示する dispStringsInCapitals を作りなさい。 この関数は必ず dispInCapitals 関数を必ず呼ぶこと。 また、以下のプログラムでテストを行いなさい。

プログラムB

#include <stdio.h>
void dispInCapitals(char *s){
  /* 課題 1-3 で作成したもの */
}
void dispStringsInCapitals(char **s){
/* この部分を作成する */
}
int main(void){
  char *a[]={"This is a pin.", "This question is not so difficult.",
    "You should understand what the pointer is.",NULL};
  dispStringsInCapitals(a);
  return 0;
}

課題2

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

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

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

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

課題 2-1

ファイルハンドルを引数にし、 getc 関数で一文字ずつ文字を読み取り、Enter または EOF で終了し、入力文 字列を線形リストのポインターで返す getline 関数を作成しなさい。 但し、メモリーが獲得できなかったら異常終了をし、入力が空だったら NULL を返しなさい。 なお、下記の定義を使用しなさい。

typedef struct string {
  struct string* next;
  char c;
} STRING;
STRING* getline(FILE* fh);

ヒント

行が改行のみで終了した場合、NULL を返さなければなりません。 しかし、線形リストを作る準備をした場合、改行を検知したときには既に malloc で領域の確保が完了している状況が起こり得ます。

この場合の措置として次のような方法があります。

1. 空行を検知したら、線形リストを破棄して、 NULL を返す。 つまり、 malloc した領域を free してから、 return NULL を行う。

   
   STRING *str;
   str=newnode();
   while(c=getc(fh),c!=EOF && c!='\n'){
     add(str,c);
   }
   if(kugyo(str)){
     delnode(str);
     return NULL;
   }
   return str;
   

2. 線形リストの管理変数に NULL を入れておく。 文字を追加する場合、線形リストの管理変数が NULL かどうか調べる。 NULL の場合は線形リストの初期化を行う。 その後で、改めて文字を追加する。

   
   STRING *str=NULL;
   while(c=getc(fh),c!=EOF && c!='\n'){
     if(str==NULL){
       str=newnode();
     }
     add(str,c);
   }
   return str;
   

課題2-2

上記の STRING 型の線形リストを表示する printstring 関数とメモリーを開 放する freestring 関数を作りなさい。 そして、 getline, printstring, freestring を下記のプログラムと結合し、 テストを行いなさい。

#include <stdio.h>
typedef struct string {
  struct string* next;
  char c;
} STRING;
STRING* getline(FILE* fh);
void printstring(STRING* s);
void freestring(STRING* s);
int main(void){
  STRING* string;
  while((string=getline(stdin))!=NULL){
    printstring(string);
    printf("\n");
    freestring(string);
  }
  return 0;
}

課題2-3

STRING 型の線形リストを逆順に保存する push 関数を作りなさい。 但し、メモリーが獲得できなかったら異常終了しなさい。 なお、下記の定義を使用しなさい。

typedef struct stack {
  struct stack* prev;
  STRING *str;
} STACK;
STACK* stackpointer;
void push(STRING* s);

課題2-4

重大な誤りが発見されました。宣言文と実行文の順序がおかしくて、厳密な C コンパイラではコンパイルできませんでした。 下記の通り stackpointer の初期化はファイル名の宣言の後に持ってきてください。

#include <stdio.h>
#include <stdlib.h>
typedef struct string {
  struct string* next;
  char c;
} STRING;
STRING* getline(FILE* fh);
void printstring(STRING* s);
void freestring(STRING* s);
typedef struct stack {
  struct stack* prev;
  STRING *str;
} STACK;
STACK* stackpointer;
void push(STRING* s);
int empty(void);
STRING* pop(void);
int main(void){
  STRING* string;
  FILE * fh;
  stackpointer=NULL;
  char filename[]="thisfile.c"; /* このプログラムのファイル名を入れる */
  stackpointer=NULL;
  if((fh=fopen(filename,"r"))==NULL){
    fprintf(stderr,"ファイル%sを開けません\n",filename);
    exit(1);
  }
  while((string=getline(fh))!=NULL){
  /* printstring(string); */
    push(string);
  }
  while(!empty()){
    string=pop();
    printstring(string);
    printf("\n");
    freestring(string);
  }
  return 0;
}

課題2-5

作成したプログラムは空行があるとファイルの途中で終了してしまう。 空行があってもファイルの終わりまで処理するにはどのように仕様を変えれば 良いか、検討しなさい。

ヒント

getline 関数は特殊な関数ではなく、さまざまなプログラミング言語で用意さ れている関数です。 それらの仕様を調べ、本課題での仕様と比較すると解決策がわかります。

レポート作成上の注意

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