5.3特殊矩阵的压缩存储.ppt

第5章 数组和串 ;5.1 数 组 ?; 在定义动态数组时也必须给出数组个数，系统在用户使用new函数申请时为用户分配存储空间。无论是静态数组还是动态数组，系统都是分配一块地址连续的存储空间给用户。C++中的数组下标均从0开始。 C++提供的数组的操作主要有存储和提取。当数组操作符［］处于赋值号左边时表示数组的存储操作，当它处于赋值号右边时表示数组的提取操作。例如， 我们定义有一个数组a，a［i］ = a［i+1］就表示把数组元素a［i+1］中的数值提取出来并存储到数组元素a［i］中。 ; 对一个有n个数据元素的一维数组，设a0是下标为0的数组元素，Loc(a0)是a0的存储地址，k是每个数据元素所需的存储单元，则数组中任一数据元素ai的存储地址Loc(ai)可由下边公式求出： Loc(ai) = Loc(a0) + i * k (0≤in) (5―1) 对一个m行n列的二维数组，由于计算机的存储单元都是一维的，就有一个二维向一维的映射问题，用计算机的术语叫做行主序还是列主序存放的问题。 ; C++中的数组元素是行主序的存放方法，即一行存完后再存放下一行。设a00是行列下标均为0的数组元素，Loc(a00)是a00的存储地址，k是每个数据元素所需的存储单元，则数组中任一数据元素aij的存储地址Loc(aij)可由下边公式求出： Loc(aij) = Loc(a00) + (i * n + j) * k (0≤im, 0≤jn) (5―2) ; 式(5―2)可按如下思路理解：数组是从基地址Loc(a00)开始存放的；数组元素aij前已存放了i行，即已存放了i * n个数据元素，占用了i * n * k个存储单元；数组元素aij前已存放了j列，即已存放了j个数据元素，占用了j * k个存储单元，所以数组元素aij的存储地址Loc(aij)为上述三部分之和。 ; 5.1.2 安全数组类的定义和实现 C++提供的数组方法能满足大多数应用程序的设计需求，但C++提供的数组方法有两个缺点： (1) C++提供的静态数组方法需要预先给出数组元素个数，数组大小在编译时就已确定，且在运行时无法修改。 (2) C++提供的数组方法不进行数组下标越界判断，当数组下标越???时程序照常运行。 ; 本节我们利用C++提供的动态数组方法设计一个一维安全数组类。一维安全数组类在基本数组功能的基础上考虑了数组下标越界问题，且可以重新定义数组元素个数。一维安全数组类的定义和实现如下： ＃include iostream.h ＃include stdlib.h //定义enum类型的错误类型。 注意, 其顺序和错误信息数组的顺序相同 enum Error Type{InvalidArraySize, MemoryAllocationError, IndexOutOfRange}; //定义错误信息数组并赋值;char *errorMsg［］ ={Invalid Array Size, Memory Allocation Error, Index Out Of Range};  template class T class Array //Array类定义 { private: T* arr; //数组指针 int size; //数组个数 //错误处理 void Error(ErrorType , int badIndex = 0) const; ?; public: Array(int sz = 100); //一般构造函数 Array(const ArrayT a); //拷贝构造函数 ~Array(void); //析构函数 ?ArrayT operator=(const ArrayT a); //赋值操作符重载 T operator［］(int i); //下标操作符重载 ? int ArraySize(void)const; //返回数组个数 void ReSize(int sz); //重新定义数组大小 };;//错误处理，打印出errorComm所对应的错误信息 templa