next up previous
Next: 5 木構造と再帰的アルゴリズム Up: 計算天文学 II 第10回 データ構造とアルゴリズム(1) Previous: 3 ツリー法の原理

Subsections


4 粒子データと線形リスト

というわけで、計算法をきわめて簡単に説明したが、プログラムとしてはどん なふうになるだろうか?以下、実際例を見ていくことにする。

実際のプログラムを書く関係上、どうしても準備が多くなるがまあちょっと我 慢を。以下は、「粒子」のデータ構造である。

pt minus 1 pt

#ifndef  PARTICLE_H
#  define   PARTICLE_H
/*-----------------------------------------------------------------------------
 *  nbody-particle : basic class for simple nbody implementation
 *  J. Makino 1998/11/29
 *  Modified  2005/01/16
 *-----------------------------------------------------------------------------
 */
#include "myvector.h"

class particle
    {
    public:
        myvector pos;
        myvector vel;
        myvector acc;
        real phi;
        real mass;
        particle *  next;
        particle *  subnext;
        particle(){
            pos = 0.0;
            vel = 0.0;
            acc = 0.0;
            phi =  mass =  0.0;
        }
        void predict(real dt){
            real dt2 = dt*dt*0.5;
            pos = pos + dt*vel + dt2*acc;
            vel +=  (dt*0.5)*acc;
        }
        void correct(real dt){
            vel +=  (dt*0.5)*acc;
        }
};
#endif
これは、一応 C++ の「クラス」の文法には従っているが、実際には C の構造 体であると思っていい。 private メンバはなくてすべてのデータメンバが外から見 えるし、メンバー関数も初期設定以外にはなにも使っていないからである。

余談になるが、「粒子」クラスのような、物理的な実体とプログラムの中での 構造がほぼ直接に対応するものについては、 C++ で一般的に使われるような 大げさなデータ構造が適切なものであるかどうかはちょっと疑問である。

ここで、 myvector は前に使ったものとほぼ同じだが、3次元用に書き下 したものを使っている。

あ、それから、 nextsubnext が、「粒子」クラスへのポイン タになっている。ここでポインタというのは、単純には、ある変数の計算機メ モリ内でのアドレスを保持するような変数である。 C/C++ の場合には、 Fortran とは違ってポインタ変数を極めて柔軟に使うことができ、複雑なアル ゴリズムやデータ構造を表現可能にすると同時にプログラムを難解なものにす ることにもなっている。

4.1 ポインタとリスト

と、ごたくを並べてもしょうがない。簡単な例で説明してみよう。以下のよう なコード断片を考えてみる。

pt minus 1 pt

    particle a, b, c;
    a.next = &b;
    b.next = &c;
    c.next = NULL;
    for (particle * p = &a; p!= NULL; p = p->next){
        setup_particle(p);
        cout << p->pos << endl;
    }
ここで、 & は、ある変数のアドレスを返す「演算子」であり、演算結 果の型はその変数に対するポインタ型になる。逆に、 * はある変数へ のポインタ型がさしているアドレスにあるもともとの変数そのものとして使え る。

うーむ、いまいち意味がわかりませんね、、、上のコードが何をするかを見て いこう。まず、 a, b, c というparticle 型の変数 3 個 を宣言する。これらにはそれぞれどこか適当なメモリアドレスがコンパイラに よって割り当てられるわけである。ここで、a.next = &b; とすると、 nextparticle 型へのポインタであったので、クラス変数 a のメンバ next の値がb のアドレスである、つまり a.nextb を指しているということになる。この状態では、例 えばa.next->posb.pos は同じように b のメンバ pos になる。NULL は、「このポインタはどこも指していない」ということ を示すために使われる特別な値である。

Figure 2: 粒子の線形リスト
\begin{figure}\begin{center}
\leavevmode
\epsfxsize =12cm
\epsffile{linear_list.eps}\end{center}\end{figure}

このように、ある構造体(クラス)のメンバに、その構造体自体を指すポイン タ変数を入れておくことで、構造体変数を数珠つなぎにしておいてずるずるたどって いくようなことができる。この、数珠つなぎ構造のことを、「線形リスト」と いう。

この例では配列とどう違うのかわからないが、主な利点は並べかえ(途中に新 しい要素を入れたり、抜いたりする)時の手間がデータの数によらないことで ある。欠点は、最初から順番に見ていくことしかできないことで、途中のデー タをぱっと見たいというような時には具合がわるい。

このツリー法のプログラムでは、next によって作ら れる線形リスト構造を、ツリーの各セルの中に入っている粒子の集合を表現す るのに使う。

詳しくはもうちょっとあとで。そのまえに、木構造の表現のほうにいこう。



Jun Makino
平成18年12月17日