このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。
C 言語では変数の宣言は常に関数の先頭に書く必要があります(C++ や Java では使う前であればどこでも宣言できます)。 また配列変数は常にあらかじめサイズが決められていました。 C 言語で、手続きが始まった後に変数領域を確保することは可能でしょうか?
このために用意されているのが、malloc 関数です。 利用する時は stdlib.h ヘッダファイルを読み込む必要があります。 malloc 関数は引数にサイズを指定するとそのメモリを動的に確保して、その メモリの先頭番地をポインタの形で返す関数です。 但し、戻ってきた値は (void *) 型のポインタなので、適切なポインタ型にキャ ストする必要があります。 また、確保した領域を使い終えたら free 関数で解放する必要 があります。 解放をきちんとやらないとメモリの利用状況が不安定になります。この状態を メモリリークと言います。 解放しないとプログラムが突然終了したり、 OS が不安定になったりしますの で、このmalloc と free は気をつけて使う必要があります。 但し、プログラムが終了する時は、 OS が free の処理をしますので、プログ ラムが終了時に free をする必要はありません。
例えば、二つの文字列つなげるのに、あらかじめ多めに領域を取らずに動的に 割り当てるには次のようにします。 なお処理の途中で malloc が領域確保に失敗した時は NULL が返ります。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void){
char x[]="abcd"; /* 配列は領域を確保する */
char y[]="efgh";
char *z; /* ポインタは領域を確保しない */
int i,j;
i=strlen(x);
j=strlen(y);
if((z=(char *)malloc((i+j+1)*sizeof(char))!=NULL){
strcpy(z,x);
strcat(z,y);
printf("文字列 %s と %s をつなげると %s。\n",x,y,z);
free(z);
return 0;
}else{
fprintf(stderr,"領域を確保できませんでした\n");
return 1;
}
}
なお、どれくらいのメモリーを取得できるのでしょうか? 次のプログラムは NULL が返ってくるまで 1MB のメモリーを取得し続けるプ ログラムです。 著者のノートパソコンは512MB のメモリを持っていますが、それで実行した場 合 1000 を越える値が出ました。 最近の OS はみな仮想記憶をサポートしているため、実メモリよりも多くの領 域を確保できます。
#include <stdio.h>
#include <stdlib.h>
int main(void){
long int i;
for(i=0;malloc(1024*1024)!=NULL;i++);
printf("%d\n",i);
/* OS に free を任す */
return 0;
}
FIFO(First In First Out)とは、データの処理の順番として、先に 入ったものは先に出されるという意味です。 これは順番待ちなどで起きることです。 この仕組みを実現するには、来たデータを順番に並べて、来た順にアクセスす るようにします。 このようなデータ記憶の方式をキュー(queue)と言います。 また、待ち行列とも言います。 キューはデータを送る側と受ける側が同期していないような状況で良く使われ ます。 例えば、プリンタ出力やメールの送受などの通信のやりとりの他、プログラム の内部処理でもイベントやファイルの入出力でも使用されます。
キューに対する操作は、次の 3 つからなります。
C 言語で、まず配列を使用して実現する方法を考えます。 配列を使うと言うことは、最初から有限の領域になりますので、キューが溢れ る可能性があります。 そこで、とりあえずそれは考慮しないで実装することにします。 始めに、大きな配列が用意されているとします。 この配列を利用してキューを作ります。 キューに要素を入れるには、要素を入れるべき位置(ポインタ)に要素を入れ、 位置(ポインタ)を一つずらします。 これを素朴にプログラムで書くと次のようになります。
#define MAX 50
int q[MAX];
int *e=q;
void enqueue(int x){
*e++=x;
return;
}
但し、これではまずいです。 というのは、書き込む要素が多くなると配列で確保した領域をはみ出してしま うからです。 そのため後ほどなんらかの措置をすることにします。 次に、 dequeue の仕組みを考えましょう。 一つの考え方は常に配列の先頭から取り出す方式です。 しかし、このためには、配列の先頭から要素を取り出す度に、 queue の内容を前に詰めて、取り出したあとを埋めなければなりません。 この手間は毎回配列の長さ分だけ要素を動かさなければならないので、ばかに なりません。したがって、詰めずに済ませる方法が必要です。 そこで、 enqueue と同様に要素を取り出すためのポインタを考えます。 要素を取り出したら次の要素を指すようにします。すると、前に詰める必要が なくなるため速く要素を取り出せます。 さて、最後に残った問題は、配列の容量をはみ出してしまうことです。
ここで、 dequeue の動作を考えると、一回要素を取り出してしまった部分は 使用しません。そこで、これを再利用することを考えます。 そのために、配列で用意した領域を使い切ったら、配列の先頭に戻るようにし ます。こうすることにより、毎回取り出す手間はポインタを移動することだけ で、配列内の要素を移動したりする必要がありません。 したがって、多くのデータを高速に処理することができます。 以下に配列を用いたキューのプログラムを示します。
#define MAX 50
int q[MAX];
int *e=q;
int *d=q;
int enqueue(int x){
int *next;
next=e+1;
if(next>=q+MAX){next=q;}
if(next!=d){
*e=x;
e=next;
return 1;
}else{
return 0;
}
}
int empty(void){
return e==d;
}
int dequeue(void){
int value;
if(!empty()){
value=*d++;
if(d>=q+MAX){
d=q;
}
return value;
}
/* 要素がないのに要素を取り出そうとした時 */
return 0; /* C++ ならエラーを発生できるのだが…… */
}
この queue をテストするため、次のプログラムを用意しました。 これを実際に実行して正常に動くか確かめなさい。
#include <stdio.h>
int enqueue(int x);
int empty(void);
int dequeue(void);
int main(void){
enqueue(5);
enqueue(2);
enqueue(8);
while(!empty()){
printf("%d\n",dequeue());
}
return 0;
}
配列を使用したキューは、あらかじめ配列の容量を決めておく必要があるため、 見積りより多くの要素が来た場合破綻します。 コンピュータのメモリが許す限りデータを受け入れられるようにしたい場合、あ らかじめ全てのメモリを確保するようなプログラムはすべてのメモリの容量を 計算して与える必要がありますし、他のプログラムとの共存が難しくなります。 従って、多くのデータを受け入れるためには、メモリを動的に確保して使用す るテクニックが必要です。 さて、上のプログラムで示したように、キューを実現するには、注目している場所の データの出し入れと、次の領域の計算できれば良いわけで、これさえできれば、 別に配列のように整数変数で特定の要素を取り出すことなどの機能は必要はあ りません。 そこで、ここでは線形リストという構造を使うテクニックを学び ます。 線形リストとは要素が一直線に並んでいて、隣接している要素が関連づいてい るものです。 構造として、「値」と「次の要素の位置」の二つを持ちます。
このような構造を使ってメモリを大量に使うことができるキューを実現します。 C 言語で線形リストを作るには構造体とポインタを使用します。 構造体には、値を入れる要素と、次の要素を指すためのポインタ を持たせます。このポインタの型はそのポインタを含む構造体自身 を指すポインタの型になります。
struct llist {
int value;
struct llist *pointer;
};
一方、キューに対する各処理は次のように書けます。
新しい領域を確保し、
値を代入、
ポインタは NULL にする。
今、dequeue に指しているものがある時は、
enqueue の指している領域のポインタに新しい領域を代入することでつなげ、
enqueue ポインタを新しい領域を指すようにする。
ない場合は初めの一個目の要素なので、
dequeue ポインタに新しい領域の番地を入れて、
enqueue ポインタも新しい領域を指すようにする。
これを実現すると下記のようになります。llist は自分自身の型を指すポイン タを含んでいることに注意して下さい。
#include <stdlib.h>
struct llist {
int value;
struct llist *pointer;
};
struct llist *e=NULL; /* グローバル変数 */
struct llist *d=NULL;
int empty(void){
return d==NULL;
}
int enqueue(int x){
struct llist* next;
next = (struct llist *) malloc( sizeof (struct llist));
if(next!=NULL){ /* メモリが確保できないと NULL が返される */
next->value=x;
next->pointer=NULL;
if(d==NULL){
d=next;
}else{
e->pointer=next;
}
e=next;
return 1;
}else{
return 0;
}
}
int dequeue(void){
int x;
struct llist *next;
if(!empty()){
x=d->value;
next=d->pointer;
free(d);
d=next;
return x;
}else{
/* 要素がないのに要素を取り出そうとした時 */
return 0; /* C++ ならエラーを発生できるのだが…… */
}
}
なお、ここで、typedef struct llist { ... } LLIST; とする
と、それ以降 struct llist と書かなければならない部分を LLIST と短く書
くことが出来ます。
書き直すと次のようになります。
#include <stdlib.h>
typedef struct llist {
int value;
struct llist *pointer;
} LLIST;
LLIST *e=NULL;
LLIST *d=NULL;
int empty(void){
return d==NULL;
}
int enqueue(int x){
LLIST* next;
next = (LLIST *) malloc( sizeof (LLIST));
if(next!=NULL){ /* メモリが確保できないと NULL が返される */
next->value=x;
next->pointer=NULL;
if(d==NULL){
d=next;
}else{
e->pointer=next;
}
e=next;
return 1;
}else{
return 0;
}
}
int dequeue(void){
int x;
LLIST *next;
if(!empty()){
x=d->value;
next=d->pointer;
free(d);
d=next;
return x;
}else{
/* 要素がないのに要素を取り出そうとした時 */
return 0; /* C++ ならエラーを発生できるのだが…… */
}
}
演習5-1 で使ったテストを利用し、上のプログラムのテストをし、正常に動作 するか確かめなさい。
FILO(First In Last Out)とは、データ処理の順番として、一番最後 に来たものから順に遡って処理をするという意味です。 そして、これを実現するデータ構造をスタックと言います。 スタックにデータを入れることを pushと言い、データを取り出す ことを popと言います。 また、データを入れる位置と取り出す位置は常に同じ位置になりますが、そこ を指すポインタをスタックポインタと言います。 スタックも直線的にデータを並べれば実現できるので、キューと同様に配列や 線形リストを使うと実現できます。 スタックを実現するプログラムを以下に示します。
#define MAX 50
int q[MAX];
int stackpointer=0;
int push(int x){
if(stackpointer+1<MAX){
q[++stackpointer]=x;
return 1;
}else{
return 0;
}
}
int empty(void){
return stackpointer==0;
}
int pop(void){
if(!empty()){
return q[stackpointer--];
}
/* 要素がないのに要素を取り出そうとした時 */
return 0; /* C++ ならエラーを発生できるのだが…… */
}
#include <stdlib.h>
typedef struct st {
int value;
struct st *pointer;
} STACK;
STACK *stackpointer=NULL;
int empty(void){
return stackpointer==NULL;
}
int push(int x){
STACK *next=(STACK *) malloc(sizeof(STACK));
if(next!=NULL){ /* メモリが確保できないと NULL が返される */
next->value = x;
next->pointer=stackpointer;
stackpointer=next;
return 1;
}else{
return 0;
}
}
int pop(void){
int x=stackpointer->value;
STACK *p=stackpointer;
stackpointer=p->pointer;
free(p);
return x;
}
スタックを実現するこれらのコードをテストしなさい。
スタックは、式やプログラムの解釈と密接な関係がありとても重要です。 サブルーチンを呼び出す時などに利用されます。 一方、式の処理にも利用されています。
まずカッコの処理について考えてみます。 カッコの処理の基本として正しく閉じているか閉じてないかを判断することを 考えます。 カッコが一種類だけなら、スタックを使わずとも、整数変数を一つ用意して、 開きカッコで数を足し、閉じカッコで数を減らしていき、一回もマイナスにな らずに最後 0 で終るかどうか判断することで処理できます。 しかし、 HTML や XML のタグのように対応する開始タグと終了タグの種類が 多い場合どうすれば良いでしょうか? この場合、閉じカッコは一番近い開きカッコに対応するということを利用し、 開きカッコをスタックに順に push していき、閉じカッコが出現したらスタッ クから開きカッコを pop して対応しているかを調べることで処理できます。 開きタグと閉じタグの文法は次のようになっています。
この文法を踏まえ、開きタグと閉じタグの対応を確認するプログラムを示しま す。スタックには要素名を指す文字のポインタを入れます。 なお、このプログラムでは要素名を解釈中かそうでないかという状態を保持す るフラグという手法を使っています。 あと、要素名を取り出すたびに文字列の領域を確保し、要素名をスタックから 取り出した後領域を解放してます。
なお、C 言語の string.h には strdup という関数があります。 これは文字列へのポインタを引数とするとその文字列を複製し、 複製先の先頭番地を返すものです。 これを使うと文字列のコピーが簡単に作れます。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int push(char *);
char * pop(void);
int empty(void);
void error(int i){
fprintf(stderr,"error %d\n",i);
exit(i);
}
int main(void){
int flag=0;
int l;
char buffer[50];
int c;
char *p,*q;
while((c=getchar())!=EOF){
if(!flag){ /* flag==1 タグの外 */
if(c=='<'){
p=buffer;
flag=1;
}
}else{ /* flag==1 タグ内解析中 */
if((c!=' ')&&(c!='>')){/* タグの要素名の採集 */
*p++=c;
}else{ /* 要素名終了 */
*p='\0';
flag=0;
if(buffer[0]!='/'){
/* 開始タグ処理(プッシュ) */
/*
l=strlen(buffer);
if((q=(char *)malloc((l+1)*sizeof(char)))!=NULL){
strcpy(q,buffer);
*/
if((q=strdup(buffer))!=NULL){
push(q);
printf("%s pushed\n",q);
}else{
error(4);
}
}else{ /* 終了タグ処理 */
if(empty()){error(1);}/* 開始タグ無し */
else{
q=pop();
printf("%s popped\n",q);
if(strcmp(q,buffer+1)==0){
free(q);/* Ok */
}else{
error(2); /* 不一致 */
}
}
}
}
}
}
if(empty()){
printf("Ok.\n");
}else{
error(3);
}
return 0;
}
なお、HTML、 XML とも DOCTYPE 宣言 <!DOCTYPE ... > という終了タ グのないタグを冒頭に置きますので、上記のプログラムでは不十分です。 また、 HTML では開始タグや終了タグを省略できます。一方 XML では基本的 に終了タグは省略できませんが、 <hr /> のように最後に / を付けて 開始タグと終了タグを兼用出来ます。 したがって、これらに対応しなければ実用的ではありません。 なお、XML 対応はそれなりに簡単にできますが、 HTML 対応はかなり複雑になります。
stack に入れられる要素を文字へのポインタに改造し、上のプログラムを動か しなさい。 そして、テストデータを作り、正常に動作することを確かめなさい。 但し、上のプログラムでは終了状態として Ok, error 1, error 2, error 3 があるので、これら全てが正常に発生するようにテストデータを作りなさい。
次に、数式を考えます。 数式は数と演算子と呼ばれるものからできています。 +,-,*,/ など我々が使う演算子は、通常、その演算子をはさむ両方の値に対し て計算を行い、答を出します。 その際、どのような順番で計算しても良いわけではなく、各演算子には優先順 位があります。 また、数式はカッコを利用して演算の順序を指定できます。 例えば、 2*3+4*5 を考えた時、これは ((2*3)+(4*5))と同じ意味になります。 これは演算子の優先順位を考慮すれば冗長な表現ですが、一方で厳密に演算の 順序を定めていることになります。 このように厳密に演算順序をカッコにより定められた式は、各カッコの中の値 を順に計算していけば全体の式の値を計算することができます。
ここで、カッコつきの演算を抽象的に考えてみます。 演算子というのは両隣の値から一つの値を計算するものなので、これは二つの 引数を持つ関数と考えることができます。 つまり、 (2*3) は 2 と 3 が引数になるわけです。 いまのところカッコの中は数が 2 つと演算子がひとつという関係です。 そこで、演算子が真中にあるという書き方の他に、先頭に置くという方式と、 最後に置くと言う方式も考えられます。
このうち注目したいのは逆ポーランド記法です。 演算子が閉じカッコの前にあるので、 演算子が現れたら、直前の二つの値に対して計算をすることで、カッコの中の値が求まります。 演算子があると必ずカッコが閉じるので、実際、最も最初に計算しなければな らない演算子が先に現れ、括弧が閉じられます。 そのため、一番内側のカッコから自然に計算が出来ます。 演算子の直後に必ず閉じ括弧があるということを利用すると、逆ポーランド記 法では演算子の優先順位を決めなくても、カッコ無しの式で計算の順序に曖昧 さは生じません。 つまり 2 3 * 4 5 * + と書いても正しく計算が可能です。 このような記法に対して、左から式を見ていき、演算子が現れたら一番近い二 つの値に対して計算を行えばいいので、スタックを利用すれば計算が出来ます。
逆ポーランド記法を(足し算だけ)計算するプログラムを以下に示します。
#include <stdio.h>
#include <stdlib.h>
typedef struct st {
int num;
struct st *pointer;
} stack;
stack *stackpointer=NULL;
int empty(void){
return stackpointer==NULL;
}
int push(int x){
stack *next=(stack *) malloc(sizeof(stack));
if(next!=NULL){ /* メモリが確保できないと NULL が返される */
next->num = x;
next->pointer=stackpointer;
stackpointer=next;
return 1;
}else{
return 0;
}
}
int pop(void){
int x=stackpointer->num;
stack *p=stackpointer;
stackpointer=p->pointer;
free(p);
return x;
}
int main(void){
char *p;
char first;
int i;
int x,y;
char *formula[] ={"1","2","+","3","+",NULL};
for(i=0; formula[i]!=NULL; i++){
first=*(formula[i]);
switch(first){
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
push(atoi(formula[i]));
break;
case '+':
y=pop();
x=pop();
push(x+y);
break;
}
}
printf("%d\n",pop());
return 0;
}
上のプログラムを改造してかけ算も計算できるようにしなさい。 そして、 2 3 * 4 5 * + が正しく計算できるか確かめなさい。
C++ では STL でキューとスタックが用意されています。 以下のプログラムはその使用例です。 キューでは enqueue, dequeue の代わりに push(), pop() が使われ、 先頭の要素は pop() で得ずに front() をつかいます。
#include <iostream>
#include <queue>
#include <deque> // または list
int main(void){
std::queue<int, std::deque<int> > q;
q.push(5);
q.push(2);
q.push(8);
while(!q.empty()){
std::cout << q.front() << std::endl;
q.pop();
}
return 0;
}
一方スタックでも pop() で値を取り出さずに top() で取り出してから pop() で値を取り除きます。
#include <iostream>
#include <stack>
#include <deque> // または list か vector
int main(void){
std::stack<int, std::deque<int> > q;
q.push(5);
q.push(2);
q.push(8);
while(!q.empty()){
std::cout << q.top() << std::endl;
q.pop();
}
return 0;
}
Java では java.util.LinkedList という線形リストのクラスに先頭と最後の 要素の出し入れをするメソッドが実装されています。 また C++ と同様に要素を取り出すメソッドと、要素を消すメソッドは別になっ ています。
Java は version 5 から型を引数にしたクラスを使用できるようになりました。 これは総称(Generics)と呼ばれる機能です。 LinkedList のような複数の要素を取り扱うクラスを使う場合、あらかじめ取 り扱う型を宣言して使用します。これは C++ の Template と同様です。 但し、C++ と違い、総称で指定できる型はオブジェクトに限られ、int や double のような基本型は指定できません。これらに対してはラッパークラス を指定します。 但し、 Java 5 からはオートボクシング/アンボクシング機能と呼 ばれる、ラッパークラスと基本型の自動変換を実現しています。 そのため、宣言時にはラッパークラスで宣言して、手続きでは基本型をそのまま 使用しても、自動的に変換が行われます。
なお、 Java 1.4 まではこの総称の機能はありませんでした。 そのため、従来の LinkedList など Collection 型のクラスライブラリは要素 に java.lang.Object 型の要素を取ることになっていました。 オブジェクト指向言語では親クラスの変数はサブクラスのオブジェクトを指す ことができるからです。 そのため、格納時はオブジェクトなら何でも格納することができます。但し通 常複数の種類のオブジェクトを入れるような使い方はしないことが多いです。 さて、取り出す時は java.lang.Object 型として得られるため、そのままでは もとのオブジェクトの機能を使うことが出来ません。 そのため、元の型にキャストをして使うことになります。 但し、 java.lang.Object 型に対してはどんなクラスでもキャストできてしま うため、もし間違ったキャストを指定しても、コンパイル時のチェックは出来 ず、実行時にキャストに関するエラーが発生していまいます。
さらに int などの基本型はオブジェクトではないので、そのままでは java.lang.Object 型の変数に代入できません。 この場合、ラッパークラスというクラスを使って基本型を java.lang.Object のサブクラスのインスタンスへ変換する必要があります。 int であれば java.lang.Integer というクラスを使ってオブジェクトに変換 します。 これで、格納することができます。 一方、値を取り出す時は、java.lang.Object 型の値として取り出したあと、 java.lang.Integer でキャストし、インタフェースである intValue() メソッ ドで元の値に変換します。
以下は Java でのプログラム例です。
class TestQueue {
public static void main(String arg[]){
java.util.LinkedList<Integer> l
= new java.util.LinkedList<Integer>();
l.addLast(5);
l.addLast(2);
l.addLast(8);
while(!l.isEmpty()){
System.out.println(l.removeFirst());
}
}
}
class TestQueue {
public static void main(String arg[]){
java.util.LinkedList l = new java.util.LinkedList();
l.addLast(new java.lang.Integer(5));
l.addLast(new java.lang.Integer(2));
l.addLast(new java.lang.Integer(8));
while(!l.isEmpty()){
System.out.println(((java.lang.Integer)l.removeFirst()).intValue());
}
}
}
class TestStack {
public static void main(String arg[]){
java.util.LinkedList<Integer> l
= new java.util.LinkedList<Integer>();
l.addFirst(5);
l.addFirst(2);
l.addFirst(8);
while(!l.isEmpty()){
System.out.println(l.removeFirst());
}
}
}
class TestStack {
public static void main(String arg[]){
java.util.LinkedList l = new java.util.LinkedList();
l.addFirst(new java.lang.Integer(5));
l.addFirst(new java.lang.Integer(2));
l.addFirst(new java.lang.Integer(8));
while(!l.isEmpty()){
System.out.println(((java.lang.Integer)l.removeFirst()).intValue());
}
}
}