2005-12-23

実行中に大きくなったり小さくなったり出来ることである。配列も可変長配列のアルゴリズムを使えば出来なくはないが、リストの場合、最大の大きさがわかっている必要すらない。これによりいくつかのデータ構造が記憶領域を共有するのに、あまり相互の大きさに注意を払わなくてよい。
項目の並べ替えが楽である。配列がいちいち全ての項目を一つづつずらさねばならないのに対して

                  ________________
　　　　　　　　 ↓　             |
ー----①-----    ②----→③ 　　 ④
            |____________________↑

こんな具合に調整できる。
デメリット（リストに向いていない動作）として入れ替えが自由に行えることにより、特定の項目を参照する（search）能力が相対的に落ちる。

リストのやり方として最初と最後の点を考える。つまりダミーを置いてやるのだ
仮に最初をheadとし、終わりをzと置く（セジウィック先生流）と、これにより先頭や末尾の接点も中の要素同様に入れ替えなどの操作が可能になる。

                           __________
 　　             ________|________  |
 head 　　　　　 ↓　     |       |  |     z
 □--------　    ①----→② 　　 ③  ------□
            |____________________↑

①→②→③から③→①→②へと変換

リストによる挿入はもっと簡単である。

                          
 　　             　　_⑥_
 head 　　            |  |        z
 □-------→①----→② 　 ③------□

①→②→③から①→②→⑥→③へと変換

削除は書くまでも無く⑥を消す動作である。②と③を繋げればよい。
実装してみるとこうなる。

#include<stdio.h>
#include<stdlib.h>

struct node
{int key;struct node *next;};    /*最後が次の構造体をさす*/
struct node *head,*z,*t;

listinitialize()
{
	head=(struct node *)malloc(sizeof *head);
	z=(struct node *)malloc(sizeof *z);
	head->next=z;
	z->next=z;
}

deletenext(struct node *t)
{t->next=t->next->next;}

struct node *insertafter(int v,struct node *t)
{
	struct node *x;
	x=(struct node *)malloc(sizeof *x);
	x->key=v;
	x->next=t->next;
	t->next=x;
	return x;
}
main(){}

ヘッダファイルなんかに入れてやると使えるかもしれない。
ただ、リストは実装が簡単なので毎回直接書くことが多い。
特に今は何もやっていない。
説明するとリストはnode(節点)いくつかからなり、各々の接点は整数一つとリストの次のnodeを指すリンクからなる。最初にheadとzを定義して後々増やしていく又は消していくプログラム。

>等の意味が分からなければ構造体の項なんかを参照すればよい。

例えばhead->next->keyはリストの最初の番号をさし、head->next->next->keyはリスト二番目をさす。

この実装において与えられた項目の直前の項目を見つける操作を直接出来るようにしたものを両方向リスト(doubly linked list)という。
ただ、これを実装させると各々の項目に２つのリンクを保持しなければならないので基本操作におけるリンクの回数が２倍になる。
又この実装においてzがheadを指してぐるぐる回すことも出来る。
この時のリストのことを循環リスト(circular list)と呼ぶ。
代表的なアルゴリズムにJosephus problemがある。

配列での実装

配列はコンピュータの記憶装置で直接実現できるので配列でデータ構造を実現する方法を調べればより低レベルでの実現できる。
ここで並列的配列を用いると便利なことが多い。
これは一つの配列の添え字の部分にさらに配列を入れるというもの。
例えばkey[next[head]]が一番目の項目をあらわし、key[next[next[head]]]が次の項目をあらわすと言う具合である。
この利点はkeyにはデータのみ入れておき、データ構造の部分はnextの中で作れること。

#include<stdio.h>
#define max	3
	
int key[max+2],next[max+2];
int x,head,z;
listinitialize()
{
	head=0;z=1;x=2;
	next[head]=z;next[z]=z;
}
deletenext(int t)
{
	next[t]=next[next[t]];
}
int insertafter(int v,int t)
{
	key[x]=v;
	next[x]=next[t];
	next[t]=x;
	return x++;
}

main(){}

こんな感じになる。

2005-12-23

Josephus problem（ジョセファスの問題）

アルゴリズム

いまN人が集団自殺しようとしているとして、まず全員が円陣に並び、その円の中のM番目の人を順に処刑する。一人死ぬと取り除かれ、円の大きさが１へることになる。
今N=９（つまり全員で９人）M=５（つまり５番づつ）とする。処刑される順番を求めよ。

解き方
円陣を引き伸ばして考えると全員で９と言うことは最後の一人になるまで9+8+7+6+5+4+3+2+1=45回隣に移動する。そこでいわゆる循環リストを円陣に見立てて割り当てる。

#include<stdio.h>
#include<stdlib.h>
struct node{int key;struct node *next;};
main()
{
	int i,N,M;
	struct node *t,*x;
	scanf("%d %d",&N, &M);
	t=(struct node *)malloc(sizeof *t);
	t->key=1;/*１番目の番号付け*/
	x=t;
	for(i=2;i<=N;i++)
	{
		t->next=(struct node *)malloc(sizeof *t);
		t=t->next;
		t->key=i;/*番号付け2番からN番まで*/
	}
	t->next=x; /*最後の次は最初へ・・循環させる。*/
	
	while(t!=t->next)/*t->next==tとなれば後一人しかいないということ*/
	{
		for(i=1;i<M;i++)
			t=t->next;/*死のルーレットM-1番目でストップ*/
		printf("%d\n",t->next->key); /*次はあなたの番*/
		x=t->next;/*殺人個室へ連れて行かれるところ・・*/
		t->next=t->next->next; /*円の中では彼は居なかったことになる。*/
		free(x); /*殺害*/
	}
	printf("%d\n",t->key);/*最後の一人を表示*/
}

非常に解読が面白いクイズだった。

2005-12-23

①-2スタック

リスト

メモリの項で散々スタックの説明をしたがリストを使ったスタックの実装について説明する。
データ構造として最も重要なスタックだが、基本的な操作は２つだけで、プッシュとポップと言う概念からなる。プッシュはリストで言えば項目の挿入であり、ポップは項目の取出しである。
スタックを使った算術式を述べると
仮に
5*(((9+8)*(4*6)+7)と言う式
9+8をやってから4*6をやり続いて掛け算をしてから７を加え、最後に５を掛ける。
この手順をオペラントも含めて並べてみると

５を入れる。
９を入れる
８を入れる
９＋８の答えを入れる
４を入れる
６を入れる
４＊６の答えを入れる
９＋８の答えと４＊６の答えを掛けたものを入れる
７を入れる
９＋８の答えと４＊６の答えを掛けた答えに七を加える
５を掛ける

この手順をpushとpopで表すと

push(5);
push(9);
push(8);
push(pop()+pop());
push(4);
push(6);
push(pop()*pop());
push(pop()*pop());
push(7);
push(pop()+pop());
push(pop()*pop());

こうなる。
pushとpopを除いて算術式で書くと

598+46**7+*

こうなることが分かる。
これをreverse Polish notation(逆ポーランド記法)もしくは後置記法と呼ぶ。
（これに対し通常の書き方をinfix(中置記法)という。）
逆ポーランドの利点は括弧が必要ではないことに尽きる。
これによりプッシュ、ポップの２つだけで簡単に算術式が書ける。
この一連の操作をリストを用いて実現する。

2005-12-21

Eukleides（ユークリッド）のアルゴリズム

アルゴリズム

Elements(原論)の中の解法を用いて既約分数（これ以上割れない分数）を計算する。

難しく書いたが要するに
最大公約数は何か？と言う回答を吐き出すプログラムを作れればよい。
解答に至る手順として最大公約数（Greatest Common Divisor。以下gcd）を求めればそれを分子、分母共に割ってやればおのずと既約分数が出てくる。
さて、最大公約数を求める能率的な方法として古代ギリシャ人の解法を用いる。
これは「分母と分子を比べ分母が大きいなら分母と分子の最大公約数が分子と分母-分子の最大公約数に等しい。」ということに基づく。
混乱しないように例を挙げると、200/300という分数の最大公約数は200と100の最大公約数と等しいということだ。ただ、世の中こんなに単純な最大公約数ばかりではない。

そこから考えて、分母ー分子で出てきた答えを使えないだろうか？
さらに分子で引くと同様に「（分母ー分子）と分子ー（分母ー分子）の最大公約数」が「分子と分母-分子の最大公約数」に等しいのは分かる。
即ちこれを繰り返していけばいずれ引く値が同じになるところまで来る。
例として85/136は分母ー分子＝51。85-51=34。51-34=17。34-17=17。17-17=0//
見やすくする為、一般化した式で書けば


分母をuと置き分子をｖと置く。
vとu-v ｛但しu>v｝のgcdはuとvのgcdに等しい。
u-vとv-(u-v)｛但しv>(u-v)｝のgcdはvとu-v｛但しu>v｝のgcdに等しい。
この動作を繰り返していき引く数と引かれる数が等しくなったときその数がuとvのgcdとなる。

ただ、これは常に引かれる数のほうが小さいと言う前提がある。
引かれる数の方が引く数より大きくなってしまった場合、
仮に41/161など161-41=120など。v<(u-v)となってしまったらプログラム内でその２つをひっくり返す動作（スワップ処理）をしなければならない。
一番簡単な処理として


temp=a;
a=b;
b=temp;

と言うaとbの入れ替え動作があるので知っておくと便利。

では同様に6536/7144は分母ー分子＝608。6536-608=5928。5928-608=5320。5320-608=4712。4712-608=4104。4104-608=3496。3496-608=2888。2888-608=2280。2280-608=1672。1672-608=1064。1064-608=456。608-456=152。456-152=304。304-152=152 152-152=0//
合っていてよかった。2888や456なんかが出てきてくれて嬉しい。ともかくこんな感じである。gcdは152。

プログラム例は

#include<stdio.h>
int gcd(int u,int v)
{
	int t;
	while (u>0)
	{
		if(u<v)
		{t=u;u=v;v=t;}  /*swap処理*/
		u=u-v;
	}
	return v;
}
main()
{
	int x,y;
	while(scanf("%d %d",&x,&y)!=EOF)
	{
		if(x>0&&y>0)
		printf("x=%d y=%d gcd=%d\n",x,y,gcd(x,y));
	}
}

結果
6 4
x=6 y=4 gcd=2
200 300
x=200 y=300 gcd=100
6536 7144
x=6536 y=7144 gcd=152

といった感じである。

2005-12-20

②型モデル

型

宣言はいつでもリストで似たような図をかける。

上の例で言えば

int(*func[10])(int a);

という宣言があったら、これを
fanc is array[10] of pointer to function(a is int) returning int.
fancはint型を返す関数（aはint）へのポインタの配列[10]
とよめた。ではリストで図示してみると、

___ 返す____ への ________  の________
int| →|関数| → |ポインタ| →|配列   |
￣￣   |int |     ￣￣￣￣    |要素10 |
        ￣￣                  ￣￣￣￣

こんな具合である。
K&Rではオブジェクトの生成法は一般的に再帰的に適用可能である。
とあり、つまり大概の宣言はどんどん繰り返してくっつけていけますといっている。
この先頭を基本型と呼び、常にintやcharなどの型が来る。
そして２つ目以降を派生型とよぶ。
派生型は考えれば分かるが関数、ポインタ、配列、構造体、共用体がある。
また、最後の型（上の場合では配列[10]）は型全体がどんなものか決めるもので、他に対し特に重要な意味を持っているので型分類と呼ぶ。

[型]不完全型

Cの型分類は

オブジェクト型
関数型
不完全型

不完全型とは方のサイズが決まらない型の中で、関数型以外のものを指す。

逆にサイズが特定できるものを「オブジェクト型」と呼ぶ。
典型例として構造体のタグ宣言が挙げられる。
例えばこんな感じである。

	struct a{
		struct b *bb;
	};

	struct b{
		struct a *aa;
	};

こうなった時、どちらを先に宣言しても宣言がないと言われるだろう。
対処法はもちろんある。

#include<stdio.h>
main(){
	
	struct b;　//*タグだけ先に宣言*//

	struct a{
		struct b *bb;
	};

	struct b{
		struct a *aa;
	};
}

とタグだけ先に宣言してやると良い。
タグだけ宣言された時点ではその内容が分からない。
もちろんサイズも決められない。このような型を不完全型という。
サイズが決められないことにより、不完全型は変数や配列を取ることが出来ない。
ただしポインタだけは取ることが出来る。

又、関数型はサイズが特定できない。ということは上の「不完全型は変数や配列を取ることが出来ない。ただしポインタだけは取ることが出来る。」という言葉を当てはめると

関数型はポインタ型以外に派生できない。

という結論に達する。
不完全型とは方のサイズが決まらない型の中で、関数型以外のものと最初に述べたが、少し他と仕様が違うところがあるからである。
つまり、関数は引数の型を持つので関数は関数型と特別のものになる。

fanc(int a)←aが引数。

2005-12-20

②Cの宣言解読

型

前橋和弥氏の書いた「C言語ポインタ完全制覇」では非常に面白い宣言の解読法がある。

ややこしい宣言は英語で読め。

というものである。


int *f(); /*f:intへのポインタを返す関数
int (*pf)(); /*pf:intを返す関数へのポインタ

と書かれても一行目は何とか読めても２行目がよく分からない。
2行目のpfの宣言を英語で読むと
pf is pointer to function returning int
(pfはintを返す関数へのポインタ)
と読める。
機械的に読む方法を載せる。

まず、識別子に着目する(変数名や関数名)
続いて識別子に近いほうから優先順位に従って派生型（ポインタ、配列、関数）を解釈する。優先順位について少しだけ述べると（これだけ抑えれば読める。）
1. 宣言をまとめるための括弧
2. 配列を意味する[],関数を意味する()/*関数なら引数解釈に入る*/
3. ポインタを意味する*
派生型を解釈したら、それを「of」または「to」または「returning」で連結する。
最後に、型指定子（左にあるintやdouble）を追加する。
日本語で解釈する。（逆から読む！）

と言うものであった。
非常に有用なので是非活用すると共に前橋氏に感謝する。

int hoge[10][3];

hoge is array[10] of array[3] returning int.

int *hoge[10];

hoge is array[10] of pointer returning int.
ホゲはint型を返すポインタの配列[10]。

int (*hoge)[3];

hoge is pointer of array returning int.
ホゲはint型を返す配列[3]のポインタ

int(*func_p)(double)

まずfunc_pに着目。
宣言をまとめる括弧の中を見る。[is]
続いて*をみる。[to]
次に関数を意味する()をつける。[()の中を解釈]
関数の引数の中(double)を見る。[returning]
最後に左端の型指定子を追加する。
func_p is a pointer to function(double) returning int
逆から読むと
func_pはint型を返す（引数がダブル型）関数のポインタ

atexit()のプロトタイプ宣言
int atexit(void(*func)(void));

同様にして
atexit is a function(func is a pointer to function(void) returning void)returning int.
atexitはint型を返す関数(fancはvoid型を返す関数(void)のポインタ)
因みにatexitはプログラムが正常終了したときに登録した関数を呼び出してもらう関数。

signal()のプロトタイプ宣言
void (*signal(int sig,void (*func)(int)))(int);

signal is function(sig is int,func is pointer to function(int)returning void) **returning** pointer to function(int) returning void

こうなるようなのですが私には何故signal is function() *returning*←となるのか理解できなかった。ｽﾐﾏｾﾝ

2005-12-18

①プリプロセッサ

プリプロセッサ

ソースファイルから実行ファイルが出来上がるまでにはプリプロセッサ、コンパイル、リンク、という段階を踏む。（下図）

  　　　　　　　　プリプロセッサ　　　　コンパイラ
{ソースファイル}→　{プリプロセス}　→{コンパイル}
　　　　　　　　　#ifdef等の処理　　　オブジェクト
　　　　　　　　　　　　　　　　　　ファイルの生成


　　  　リンカ
　→　  {リンク}　  →    {実行ファイル}
　　オブジェクトファ
　　イル同士の結合

これから分かるようにまずプリプロセッサが起動される。
つまりプリプロセッサがコンパイラすら行わせないような処理が出来るということだ。
このメリットはバグがあろうが無かろうがそもそもコンパイルをしないで飛ばせる。
プリプロセッサで行える主な処理は次のものである。

ディレクティブ	機能
#define	define名を定義する
#undef	define名を解除する
#include	インクルードする
#if〜#elif〜#else〜#endif	条件式の結果で分岐する
#ifdef〜#else〜#endif	define名の定義状態で条件分岐する
#ifndef〜#else〜#endif	define名の定義状態で条件分岐する
#error	エラーメッセージを表示する

#includeと#defineは見慣れているので省略。

#ifも感覚で使えるだろうが式の評価結果に応じてソースファイルをスキップさせる。

#include<stdio.h>
main(){
	int n=1;
	printf("test-->");
#if 0
	printf("n=%d\n",n);
#endif
}

結果
test-->

１にしたら

#include<stdio.h>
main(){
	int n=1;
	printf("test-->");
#if 1
	printf("n=%d\n",n);
#endif
}　

結果
test-->n=1

となり#if〜#endifの間が出てくる。
もちろんコンパイル前の処理なので定数以外使えない。

#ifdefはifとdefineをつなぎ合わせたもの。

#ifndefは#ifdefの否定版。if !defineをつなぎ合わせたもの。

#undefはdefineを無くす

#errorは「コンパイラ時」にエラーメッセージを表示

#include<stdio.h>
#define FALSE 0
#define TRUE 1

#if defined(TRUE)||defined(FALSE)
#undef TRUE
#undef FALSE

typedef enum{FALSE,TRUE}BOOL;
#else
#error "not defined"

#endif

main()
{
	BOOL flag=FALSE;
	printf("%s\n",flag==TRUE?"TRUE":"FALSE");
}
結果
FALSE

こんな感じだがたとえば#if defined(TRUE)||defined(FALSE)を
#if defined(2RUE)||defined(4ALSE)
とかに変えて見るとコンパイラ時に

致命的エラー F1003 priprosessa.c 11: error 指令: "not defined"

と出てくる。
また定義済みdefineといって勝手に最初っから定義されて使えるものがいくつかある。

define名	中身
__LINE__	参照したソースファイルの行番号
__FILE__	参照したファイルの名前
__DATA__	コンパイルしたときの日付（文字列）
__TIME__	コンパイルしたときの時刻（文字列）
__STDC__	ANSI Cに準拠したコンパイラである。

使い道はあまりないが

#include<stdio.h>
main()
{
	printf("このファイルは%s\n",__FILE__);
	printf("ただいま%d行目\n",__LINE__);
	printf("只今の時間は%s\t%s\n",__DATE__,__TIME__);
#if defined(__STDC__)
	puts("準拠コンパイラ");
#endif
}

結果
このファイルはdefine__.c
ただいま5行目
只今の時間はDec 15 2005 15:17:44

こんなことも出来る。