２次元配列の動的確保
やねのすずめ
japan.sci.algorithm にもクロスポストしています。
TAKE1 さんの <9k6i96$r69$1...@news.stnet.ad.jp> より...
>２次元配列の動的確保の方法で困っています。
>
>１行１列、２行２列、、、、ｎ行ｎ列
>というように動的に行列を増やす。
>
>配列は別確保しない。（本当に１つの配列をふやしていく）
>
>配列に入れた内容は、初期化しない。
>
>例
>r[1][1],r[2][2].....r[n][n]
>
>ということをしたいのですが、
>どのようにすればよいでしょうか。
２次元配列 a[y,x] の要素に図のような順序で番号を付けます。
x 0 1 2 3 4
y
+---+---+---+---+---+
0 | 0| 1| 4| 9| 16| …
+---+-↓+-↓+-↓+-↓+
1 | 3← 2| 5| 10| 17|
+---+---+-↓+-↓+-↓+
2 | 8← 7← 6| 11| 18|
+---+---+---+-↓+-↓+
3 | 15←14←13←12| 19|
+---+---+---+---+-↓+
4 | 24←23←22←21←20|
+---+---+---+---+---+
：
番号 i は
x <= y のとき i = ( y + 1 ) * ( y + 1 ) - x - 1
x >= y のとき i = x * x + y
で計算できますので、１次元配列 b[i] に置き換えれば
明示的にデータをコピーすることなく
Ｃ言語の realloc() 関数（メモリ割り当てサイズの変更）で
（擬似）２次元配列 a[y,x] が拡張できます。
x の最大値と y の最大値に差があると無駄な領域が必要ですが…。
--
(^v^) (.. )(o^< >^o) ふと思いついて
(( ))//^ ))(( ))(( ))
= //林 //林 //林 //林 ================================^
mid...@mtg.biglobe.ne.jp やねのすずめ // ＼
http://www5a.biglobe.ne.jp/~espoir/ (ホームページ)// ＼
やねのすずめ
# いまさらながら思いついたので、自己フォローです
TAKE1 さんの <9k6i96$r69$1...@news.stnet.ad.jp> より...
>１行１列、２行２列、、、、ｎ行ｎ列
>というように動的に行列を増やす。
>
>配列は別確保しない。（本当に１つの配列をふやしていく）
>
>配列に入れた内容は、初期化しない。
>
>例
>r[1][1],r[2][2].....r[n][n]
>
>ということをしたいのですが、
添字を付け直し、１次元配列として扱って
Ｃ言語の realloc() 関数（メモリ割り当てサイズの変更）を使うのは
同じですが、
x, y を２進法で表して
... x2 x1 x0, ... y2 y1 y0
となるとき、
i = ... y2 x2 y1 x1 y0 x0
を新しい添字とすれば良いですね。
つまり、下図のように番号をつけるわけです:
０ １ ４ ５ ...
２ ３ ６ ７ ...
８ ９ １２ １３ ...
１０ １１ １４ １５ ...
： ： ： ：
この方法は、３次元以上でも応用できます。
また、３進法でも１０進法でもできます。
そのかわり、配列のサイズが 4 (=2^2) のべき乗になったりします。
# 半導体メモリ的
処理はシフト演算の繰返しでしょう。
# ハードウェア化すると速いかも（線の入れ換えですむので）
--
(^v^) (.. )(o^< >^o)
(( ))//^ ))(( ))(( ))
= //林 //林 //林 //林 ================================^
http://www5a.biglobe.ne.jp/~espoir/ やねのすずめ // ＼