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

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

課題2

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

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

下記の構造体を利用した線形リストを作り、文字列の頻度を計算するプログラムを作成することを考えます。


typedef struct node {
  char *str;
  int hindo;
  struct node *next;
} Node;

このため、以下のヘッダファイルの名前を hindo.h とするとき、以下の 3 つの課題に答えなさい。

hindo.h


typedef struct node {
  char *str;
  int hindo;
  struct node *next;
} Node;
Node* newnode();
void dispHindo(Node* p);
int countHindo(Node* p, char *key);
void delList(Node*p);

課題2-1

Node のポインタを与えると、そのポインタが指す線形リストを解釈し、頻度を出力した後 ---------- を出力する void dispHindo(Node* pointer) を作成しなさい。書式は一行ずつ「文字列: 頻度」となるようにしなさい。なお、線形リストの最終ノードの next には NULL が入っていることとし、この場合他のメンバの値は使用しないものとします。

そして下記のプログラムと結合し、実行例と同じものが出ることを確認しなさい。

テストプログラム2-1


#include <stdio.h>
#include "hindo.h"
int main(void){
  Node x, y , z, end;
  x.str="abc";
  x.hindo=2;
  x.next=&y;
  y.str="def";
  y.hindo=3;
  y.next=&z;
  z.str="ghi";
  z.hindo=1;
  z.next=&end;
  end.next=NULL;
  dispHindo(&end);
  dispHindo(&x);
  return 0;
}

実行例

----------
abc: 2
def: 3
ghi: 1
----------

課題2-2

新たに Node 型の変数の領域を確保し、next に NULL を入れたポインタを返す Node* newnode() 関数を作りなさい。なお、新たな領域を確保できなかったときは、 NULL を返しなさい。

また、 Node のポインタ型と文字列を与えると、そのポインタの指している線形リストに対し、(1) 同じ文字列があれば頻度を加算し、(2)もし、存在しなければ新たにその文字列の頻度が 1 であることを示すノードを追加する int countHindo(Node* pointer, char* key) を作りなさい。なお、頻度の計算に成功したら 1, 領域確保に失敗するなど、正常に計算できなかったときは、0 を返しなさい。但し、文字列が一致するかどうかを判定するのに、 strcmp 関数を使用しても良い。

そして、下記のプログラムと結合して、実行例と同じ動作になるか確認しなさい。 (注意: 6/27 にプログラムを修正しました)

テストプログラム 2-2


#include <stdio.h>
#include <stdlib.h>
#include "hindo.h"
void delList(Node *p){
   char *s;
   if(p==NULL){
     return;
   }
   delList(p->next);
   s=p->str;
   free(p);
   if(s!=NULL){
      free(s);
   }
}
int main(void){
  char *test[]={"abc", "def", "abc", "def", "def", "ghi", NULL};
  int i;
  Node* root;
  if((root=newnode())==NULL){
    fprintf(stderr,"メモリーが確保できませんでした\n");
    return 1;
  }
  dispHindo(root);
  for(i=0;test[i]!=NULL;i++){
    if(!countHindo(root,test[i])){
      fprintf(stderr,"頻度計算に失敗しました\n");
      return 2;
    }
  }
  dispHindo(root);
  delList(root);
  return 0;
}

実行例

----------
abc: 2
def: 3
ghi: 1
----------

課題2-3

下記の関数 char* getword(FILE* f)は、オープンしたファイルに対して、ファイル中の「名前」を順に取り出すものです。但し、ファイルを読み終わると NULL を返します。また、 1024 文字以上の名前は 1024 文字目までで切られて、そのあと改めて解釈が行われます。ここで、「名前」とは、一文字目が英字で二文字目以降が英字か数字の文字列です。なお、このプログラムは引用符とか直前の文字とか気にしていないので、"%s" なら s を取り出し、 123abc456 であれば、 abc456 を取り出します。

getword.c


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAXSIZE 1024
#define START (EOF-1)

typedef enum state { NOWORD, WORD } STATE;
char* getword(FILE* f){
  char buffer[MAXSIZE]={0};
  int index=0;
  static int prev = START;
  STATE s = NOWORD;
  while(1){
    switch(s){
    case NOWORD:
      if(prev == EOF){
	return NULL;
      }
      if(prev == START){
        break;
      }
      if(isalpha(prev)){
	s=WORD;
	buffer[index++]=prev;
      }
      break;
    case WORD:
      if(isalnum(prev)){
	buffer[index++]=prev;
	if(index>=MAXSIZE-1){
	  buffer[MAXSIZE-1]='\0';
	  prev=getc(f);
	  return strdup(buffer);
	}
      }else{
	buffer[index]='\0';
	return strdup(buffer);
      }
      break;
    }
    prev = getc(f);
  }
}

この関数の動きを動作させて知りたい場合は、下記のテストプログラムを結合させてみて下さい。

getword 用のテストプログラム


#include <stdio.h>
#include <stdlib.h>
char* getword(FILE* f);
int main(void){
  char *p;
  FILE *f;
  if((f=fopen("getword.c","r"))==NULL){
    fprintf(stderr,"ファイルが開けませんでした\n");
    return 1;
  }
  while((p=getword(f))!=NULL){
    printf("%s\n",p);
    free(p);
  }
  fclose(f);
  return 0;
}

さて、この getword と newnode, countHindo, dispHindo, delList とを組み合わせて、「ファイル中の各名前の頻度を計算するプログラム」を作成しなさい。そして、作成したプログラム自身を読み込ませ、そのプログラム中で使用されている名前の頻度を示しなさい。

なお、 getword では返す文字列は毎回領域を確保していますので、返ってきた文字列を使用しなくなったら free しなければならないことに注意して下さい。

課題1

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

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

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

int 型のグローバルな配列 hindo[95] が定義されているとします。但し、hindo[k] は文字コード k+32(十進法)の文字の出現回数を表すこととします。以下の問いに答えなさい。

課題 1-1

頻度を出力する void dispHindo(void) を作成しなさい。書式は一行ずつ「'文字': 頻度」となるようにしなさい。但し、頻度が 0 の文字は出力をしないようにしてください。そして、以下のプログラムと結合し、出力結果が以下の出力例と同じになることを確認しなさい。

プログラム


#include <stdio.h>
int hindo[95]={0,1,0,2,0,3};
void dispHindo(void){
/* ここにプログラムを書く */
}
int main(void){
  dispHindo();
  return 0;
}

出力例

'!': 1
'#': 2
'%': 3

課題 1-2

文字配列のポインタを受け取り、文字出現の頻度を計算する void countHindo(char*) を作成しなさい。なお、文字列の中に改行記号などのコントロールコードが含まれることも想定し、文字コードが 32 から 126 以内であるときだけ頻度を数えるようにしなさい。そして、下記のテストプログラムと結合して、結果を報告しなさい。

テストプログラム


#include <stdio.h>
int hindo[95]={0};
void dispHindo(void){
  /* 課題1-1 のプログラム */
}
void countHindo(char* str){
  /* ここにプログラムを書く */
}
int main(void){
  countHindo("This is a pin.");
  dispHindo();
  return 0;
}

課題1-3

開いたファイルのファイルハンドルをもらい、ファイル中の各文字の頻度を計算する void fCountHindo(FILE*) を作成しなさい。そして、作成したプログラムのファイル名を kadai13.c とした時、以下のプログラムと結合して結果を求めなさい。なお、これも入力のチェックは行ってください。

テストプログラム


#include <stdio.h>
int hindo[95]={0};
void dispHindo(void){
  /* 課題 1-1 のプログラム */
}
void fCountHindo(FILE* input){
  /* この部分を作成する */
}
int main(void){
  FILE* input;
  if((input=fopen("kadai13.c","r"))==NULL){
    fprintf(stderr,"Can't open the file.\n");
    return 1;
  }
  fCountHindo(input);
  dispHindo();
  fclose(input);
  return 0;
}

課題1-4

課題1-3 で作成した void fCountHindo(FILE*) に対して、英小文字を大文字として数える void fCountHindoIgnoreCase(FILE *) を作りなさい。これも入力のチェックが必要です。作成したプログラムに対して、課題 1-3 と同じ kadai13.c を読ませて出力を求めなさい。

テストプログラム


#include <stdio.h>
int hindo[95]={0};
void dispHindo(void){
  /* 課題 1-1 のプログラム */
}
void fCountHindoIgnoreCase(FILE* input){
  /* この部分を作成する */
}
int main(void){
  FILE* input;
  if((input=fopen("kadai13.c","r"))==NULL){
    fprintf(stderr,"Can't open the file.\n");
    return 1;
  }
  fCountHindoIgnoreCase(input);
  dispHindo();
  fclose(input);
  return 0;
}

レポート作成上の注意

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

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