荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: Second (石开), 信区: Program
标  题: C++中的动态多维数组
发信站: 荔园晨风BBS站 (Wed Jun  6 07:11:29 2001), 转信

    C++的new操作符是该语言一个非常好的语法特性,然而实际使用中却发现new操作
符有不少限制,
最为突出的一点便是用new操作符分配多维数组空间时,不能让数组的每一维都动态可
变。本文将对此
提出一个简单直观的解决方案,在一个实际问题的简化模型中加以说明,并以此释清许
多初学者对C++
中new操作符与多维数组的误区。
1. 问题的提出--多维可变数组的实际用途
    下面是实际编程中遇到问题的一个简化模型。ChessBoard是一个棋盘类,其中的
m_board是用来保
存棋盘上棋子信息的二维数组。DIMENSION是棋盘的尺寸或者维数,因为要用于数组声
明,所以它必须
是一个编译期间可以确定其值的常量,这里我们使用了无名枚举。对于不同种类棋的棋
盘大小是不同的
,对于黑白棋,DIMENSION定义为8,对于五子棋,DIMENSION应该为15,而围棋呢,又
得是19。对此这
段代码采用了条件编译来确定DIMENSION常量的值,以保证这段代码具有较好的可重用
性。
    由于m_board必须是编译期常量,于是在程序运行时刻m_board数组的大小是不可改
变的。如果程序
中要同时实现黑白棋、五子棋和围棋就不能这样来做了--当然这样有点夸张,不过就
算光是围棋也有
9x9、13x13、19x19几种棋盘,而且应当能让用户在程序运行时自由选择。
class ChessBoard
{
private:
    enum{
#ifdef  OTHELLO
        DIMENSION=8         file://如果是黑白棋,棋盘大小为8x8
#endif
#ifdef  PENTE
        DIMENSION=15        file://如果是五子棋,棋盘大小为15x15
#endif
    };
    int m_board[DIMENSION][DIMENSION];
public:
    /*其它成员函数
    ......
    */
}
    对此我们必须用new操作符或者malloc函数在程序运行时刻为m_board动态分配空
间,由于new支持更
多的C++特性,因此我们的程序采用了new操作符。
2. MSDN中用new申请多维数组的说明--进一步认识new操作符
    下面的代码摘自MSDN中的“new operator”,其中第二行在VC6.0中编译将得到一
个错误信息,对
此MSDN中的说明是new操作符返回的类型为float(*)[25][10],即指向float[25][10]的
指针(去掉最左
边的一维)。正确代码应当如3、4行所示。
1. float *fp;
2. fp = new float[10][25][10];      file://错误信息:cannot convert from
'float (*)[25][10]' to 'float *'
3. float (*cp)[25][10];
4. cp = new float[10][25][10];
    参考此代码我们来考虑我们的棋盘问题,照葫芦画瓢我们可以得到如下代码:
int (*m_board)[DIMENSION];          file://在类的成员变量中声明
m_board = new int[Changeable][DIMENSION];   file://根据用户选择来确定相应的
Changeable值
    不难看出,由于仍然必须用编译期常量DIMENSION来声明数组,所以m_board数组只
能有一维可变,
这种方法对我们的问题是毫无用处的。
3. 解决方案
    这里给出两种解决方案,并对第二种方案给出具体代码。
1).  我们可以申请大小为XSIZE*YSIZE的一维数组,然后自己通过对xy下标换算来定位
相应的存储单元,
代码如下:
int *p=new int[YSIZE*XSIZE];    file://XSIZE和YSIZE应该定义为常量
file://但是对于p[y][x]的引用便成了语法错误,应该为
p[y*XSIZE + x]=y*1000 + x;
    这种方法最大的好处是数组维数可以自由确定,甚至可以动态确定,因为都是转换
为一维数组。但
是它的最大的不便之处就是下标转换的繁琐,在多维数组的情况下更为明显。如下面这
段代码是一段检
验下标转换是否正确的程序,其输出结果应该为每个数组单元的地址都不相同,而且都
落在“开始地址
”和“结束地址”之间。
const int YSIZE=6;
const int XSIZE=7;
const int ZSIZE=9;
int *p=new int[ YSIZE*XSIZE*ZSIZE ];
file://但是对于p[y][x]的引用便成了语法错误,应该为
cout << (int)p << "开始地址\n";
cout << ((int)p)+sizeof(int)*YSIZE*XSIZE*ZSIZE << "结束地址\n";
for(int z=0;z<ZSIZE;z++){
    for(int y=0;y<YSIZE;y++){
        for(int x=0;x<XSIZE;x++){
            p[z*YSIZE*XSIZE+y*XSIZE + x]=(z+1)*1000+y*10 + x;
            cout << "当前单元地址:" << (int)&p[z*YSIZE*XSIZE+y*XSIZE + x]
                << "----" << p[z*YSIZE*XSIZE+y*XSIZE + x] << "\t";
        }
    }
}
    可以看到其中的数组p仅仅是一个三维数组的但是其下标转换
z*YSIZE*XSIZE+y*XSIZE+x已经相当繁
琐了,使用上的繁琐常常会成为程序中Bug的来源。因此这种方法对初学者并不适用,
但它的灵活性与
简单性使我们不能忽视它。利用这种方法可以将多维数组封装成一个通用类,不但可以
动态改变数组每
一维的大小,而且连数组的维数都可以动态改变(这个通用数组类正在笔者的计划之
中)。
2). 将多维数组当作多个一维数组。
    这里我们直接给出前面提出棋盘类问题的代码,构造函数ChessBoard、析构函数
~ChessBoard和输
出函数Output中分别对应给出了二维数组m_board的空间分配,空间释放和单元引用的
相关代码。而且
可以看出虽然这种方法需要用循环来分配、释放空间并且需要额外的存储空间,但从
Output函数可以看
到,它的使用与常规数组使用的语法是一致的,较上面的第一种方法繁琐的下标转换要
方便得多。
    由于代码并不复杂,除了代码中的注释外,就不再另外详细说明。虽然这里给出的
是二维数组,但
也不难将其扩充到多维数组。其中m_board数组的数据结构可以直观的由图一看到。
                        图一、数组m_board的数据结构
class ChessBoard{
private:
    const int DIMENSION;
    int **m_board;
public:
    void Output();
    ~ChessBoard();
    ChessBoard(int BoardSize);
};
ChessBoard::ChessBoard(int BoardSize=8):
DIMENSION(BoardSize){
    m_board = new int*[DIMENSION];  file://为m_board数组分配空间
    for(int y=0;y<DIMENSION;y++){
        m_board[y] = new int[DIMENSION];
        for(int x=0;x<DIMENSION;x++){
            m_board[y][x]=0;    file://对每个元素初始化
        }
    }
}
ChessBoard::~ChessBoard(){      file://释放m_board的空间
    for(int y=0;y<DIMENSION;y++){
        delete []m_board[y];
    }
    delete []m_board;
}
void ChessBoard::Output(){      file://输出所有元素,其访问方法与常规数组一
样,无需下标转换
    for(int y=0;y<DIMENSION;y++){
        for(int x=0;x<DIMENSION;x++){
            switch(m_board[y][x]){
            case 1: cout << "●";   break;
            case 0: cout << "  ";   break;
            case 2: cout << "○";   break;
            }
        }
    }
}

--
                            既然热爱生命
                            那么,
                            一切都在意料之中。

※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.28.190]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店