網頁

2006年2月20日 星期一

《陣列》多維動態陣列

《陣列》多維動態陣列

多維動態陣列在 C 中 大概只能用 malloc,但這在一維時尚
不構成問題,但需要多維陣列時怎麼辦呢?這算是程式論壇
最常被問到的問題之一了。
我把它整理了相關的回覆,都只用二維做說明,更多維的陣列
類推即可。
就從 C 談起吧!

動態產生一個[m][n]陣列 Array 的方法


code:------------------------------------------------------------------
int i;
int **Array;
Array= (int **)malloc(m*sizeof(void *));
for (i=0; i<m; i++)
Array=(int *)malloc(n*sizeof(int *));
--------------------------------------------------------------------------

這樣你就有一個 int Array[m][n]; 可以用了
是C 喔!不是 C++
但這不夠好,若你要的是一個較大的mXn陣列,那麼太多的malloc
會使記憶體碎片化(memory fragment)!沒關係,窮則變,變則通!
問題既出在for loop不斷的 memory allocation,就從那兒下手:

code:---------------------------------------------------------------------
int i;
int **Array, *pData;
Array= (int **)malloc(m*sizeof(int *));
pData= (int *)malloc(m*n*sizeof(int));
for (i=0; i<m; i++, pData+=n)
Array[i]=pData;
---------------------------------------------------------------------------

注意到嗎?這次只用了二次的malloc。
當要release memory也只要free Array[0] 和 Array 就成了!
(注意先free Array[0] 再 free Array)
如果嫌兩個alloc/free還是太多,也可簡單併成一個:

code:-----------------------------------------------------------------------
int i;
int **Array, *pData;
Array= (int **)malloc(m*sizeof(int *)+m*n*sizeof(int));
for (i=0,pData= (int *)(Array+m); i<m; i++, pData+=n)
Array[i]=pData;
----------------------------------------------------------------------------

要 free 時只要 free Array 就行了,帥吧?
如果用的是C++,那可用的方法就更多了!

《幼幼班》嘗試錯誤的階段
?> int Array[][] = new int [10][20];//這樣行ㄇ?
當然不行! int Array[][]不是一個指標,而且只能有
一維為不定大小。

《小班》終於會從1數到100了
?> 那...
?> int *Array[] = new int [10][20];//這樣行ㄇ?
有點想法了!但可惜的是 '*' 在 C++的語法是修飾前面的
識別字,所以 int *Array[]的意思是 "Array是一個 int 指標
的一維陣列!"

如果能使那個 '*' 以獨立指標型態去宣告Array,就會變成
"Array是一個指標,指向一維 int 的陣列",而我們知道指標
本身就可以當做一維的陣列,那麼是不是就成了"Array是一個二維
的int陣列"?
對了!這正是我們要的!問題是怎麼讓'*'成為獨立指標型態,
不會去修飾前面的int識別字?答案是使用括號:
int (*Array)[20] = new int [10][20];//這是正解!

但問題又來了, new 運算子可以使用 new int [m][n],但
int (*Array)[20] 的 [20]卻沒辦法以 [n] 來取代,所以就
沒辦法做到不定大小的宣告了。所以這只能算是小班的答案,
要做到不定大小的動態多維宣告,加上 STL 的運用,是不錯
的想法。

《中班》vector 模板的運用
vector<int> *array=new vector<int>[m];
for (int i=0; i<n; i++) array[i].reserve(n);
嘿嘿...不錯吧!?不定大小的二維陣列,而且每個維度還
可以隨時調整大小喔!
不過還是有缺點ㄟ!!那行 for loop 看起來有點礙眼,不能
拿掉嗎?拿掉的話,基本上Array 還是二維陣列,但第二維
並沒有預留空間放東西你可以用push.back等成員函式來增加
空間和存放data,但不能在還沒有空間時使用像
array[5][3]=3; 這種陣列的存取方式。沒更好的方法了嗎?
vector 不是有預留空間大小的建構子嗎?像一維的宣告:
vector<int> *Array= new vector <int>(n);
//這不是預留了 n 個元素的陣列了嗎?
只可惜,這是一維的宣告,若你嘗試做這樣的宣告:
vector<int> *Array= new vector <int>[m](n);
編譯器會給你無情的嘲諷:陣列不能呼叫帶參數的建構子!
這是很令人失望的!為十麼不行?不是邏輯的問題,或許下
一版本的C++會可以這樣宣告吧!但為今之計只能自力救濟
了。

《大班》使用模板在模版中
仔細觀察下面的宣告:
vector<vector<int> > Array(m, vector<int>(n));

沒有留言:

張貼留言