C/C++ - 動態配置二維陣列解析 Dynamic 2D arrays in C++

動態配置二維陣列是十分常使用的方法，上網爬了一下文，把這個常用的技巧做一個整理，以後使用起動態配置的二維陣列會更加輕巧優雅！

ㄧ、動態配置二維陣列：基礎方法

基礎方法是比較直覺的寫法，不過釋放記憶體稍嫌複雜，有一些現成函式不能直接套用，而且有可能有記憶體碎片化的風險。

1. 配置記憶體空間

int i;
int data_height, data_width;
int **data;
p = new int*[data_height];
for(i = 0; i < data_height; i++)
    data[i] = new int[data_width];

2. 釋放記憶體空間

for(i = 0; i < data_height; i++)
    delete [] data[i];
delete [] data;

[用心去感覺] 基礎方法的缺點

不能使用 memset() 初始值為 0
不能使用 memcpy() 複製值至另一個陣列

二、動態配置二維陣列：進階方法

法二加入把二維陣列寫成一維陣列，不僅可以使用眾多現成函式，且加上Macro讓程式碼更簡潔優雅，釋放記憶體方法也更簡潔。

1. 配置記憶體空間

void* new2d(int h, int w, int size)
{
    int i;
    void **p;

    p = (void**)new char[h*sizeof(void*) + h*w*size];
    for(i = 0; i < h; i++)
        p[i] = ((char *)(p + h)) + i*w*size;

    return p;
}

上面的記憶體配置情形可以以下圖來說明 (感謝耕竹大大提供)：

呼叫上述函式建立動態二維陣列，在程式前頭增加Macro更可簡化剛剛動態配置二維陣列寫法。

#define NEW2D(H, W, TYPE) (TYPE **)new2d(H, W, sizeof(TYPE))

//...

int **data = NEW2D(data_height, data_width, int);

//original : int **data = (int **)new2d(data_height, data_width, sizeof(int));

2. 釋放記憶體空間

釋放記憶體十分簡潔。

delete [] data;

三、動態配置二維陣列：例題

1. SLG 題目

あなたはクライアントから画像分析の仕事を受けました。

N × N ピクセルの白黒画像と M × M ピクセルの白黒画像が与えられます。白黒画像の各画素は 0 または 1 のいずれかです。 N × N ピクセルの画像を入力、M × M ピクセルの画像をパターンと呼ぶことにします。

あなたの仕事は、入力からパターンとの完全一致を探すことです。

入力とパターンがピクセルの位置 (y, x) で完全一致するとは、全ての i, j (i = 0, 1, ... M - 1, j = 0, 1, ... M - 1) について、 (入力の位置 (y + j, x + i) におけるピクセル) = (パターンの位置 (j, i) におけるピクセル) が成立することをいいます。

また、依頼主からは、入力にはパターンと完全一致する箇所は必ず 1 つだけ存在するということを伝えられています。

ここで、N = 4 の入力の例を見てみましょう。

2. 解答

main.cpp

#include <iostream>
#define NEW2D(H, W, TYPE) (TYPE **)new2d(H, W, sizeof(TYPE))
using namespace std;

void* new2d(int h, int w, int size)
{
    int i;
    void **p;

    p = (void**)new char[h*sizeof(void*) + h*w*size];
    for(i = 0; i < h; i++)
        p[i] = ((char *)(p + h)) + i*w*size;

    return p;
}

void getInput(int **cur_data, int size)
{
    for(int i = 0 ; i < size; i++)
        for(int j = 0; j < size; j++)
            cin>>cur_data[i][j];

    return;
}

int CheckSubMatrix(int **data_a,int **data_b,int size_b,int i,int j)
{
    for(int k = 0; k < size_b; k++)
        for(int m = 0; m < size_b; m++)
            if(data_a[k+i][m+j] != data_b[k][m]) return 0;

    return 1;
}

int* CheckEqual(int **data_a,int **data_b,int size_a,int size_b, int *ans)
{
    for(int i = 0 ; i <= size_a - size_b ; i++)
        for(int j = 0 ; j <= size_a - size_b ; j++)
        {
            int is_same = CheckSubMatrix(data_a,data_b,size_b,i,j);

            if(is_same)
            {
                ans[0] = i;
                ans[1] = j;
                return ans;
            }
        }

    return ans;
}

int main(void){

    int size_a;
    cin>>size_a;

    int **data_a = NEW2D(size_a, size_a, int);
    getInput(data_a,size_a);



    int size_b;
    cin>>size_b;

    int **data_b = NEW2D(size_b, size_b, int);
    getInput(data_b,size_b);



    int ans[2];
    CheckEqual(data_a,data_b,size_a,size_b,ans);

    cout<<ans[0]<<" "<<ans[1];



    delete [] data_a;
    delete [] data_b;

    return 0;
}

test.txt

Ans : 1 0

References

下面除了動態配置二維陣列外，還有一些轉型和指標的延伸閱讀。

C++ 動態配置二維陣列
http://blog.xuite.net/csiewap/cc/16696000-C%2B%2B+%E5%8B%95%E6%85%8B%E9%85%8D%E7%BD%AE%E4%BA%8C%E7%B6%AD%E9%99%A3%E5%88%97

C 語言常見誤解/指標/表示法與轉型
https://zh.wikibooks.org/zh-tw/C_%E8%AA%9E%E8%A8%80%E5%B8%B8%E8%A6%8B%E8%AA%A4%E8%A7%A3/%E6%8C%87%E6%A8%99/%E8%A1%A8%E7%A4%BA%E6%B3%95%E8%88%87%E8%BD%89%E5%9E%8B

批踢踢實業坊›看板 C_and_CPP [心得] 轉型、指標、enum 跟 handle
https://www.ptt.cc/bbs/C_and_CPP/M.1377530099.A.EA7.html

懷舊C語言:1988 The C Programming Language 2nd Edition(PART VII)
http://ithelp.ithome.com.tw/question/10082674

C++ 的顯性轉型與隱性轉型 - Explicitly/ImplicitlyType Conversion
http://ot-note.logdown.com/posts/173174/note-cpp-named-type-convertion

指標與記憶體位址
http://openhome.cc/Gossip/CppGossip/Pointer.html

paizaの女の子(安藤杏たん)にRubyを使って水着をプレゼントしよっ
http://qiita.com/iguchi1124/items/be4d8b1e770e3edf1ac3

Pages

2015年12月12日星期六