第5章 数组和串.ppt

第5章 数组和串 5.1 数 组 ? 5.2 间接地址 5.3 特殊矩阵的压缩存储 5.4 稀疏矩阵的压缩存储 5.5 串 5.1 数 组 ? 5.1.1 C++的数组 C++中的数组有静态数组和动态数组两种。在定义静态数组时必须给出数组个数，系统在编译时为用户分配存储空间。 在定义动态数组时也必须给出数组个数，系统在用户使用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) = ？ (5―1) 对一个m行n列的二维数组，由于计算机的存储单元都是一维的，就有一个二维向一维的映射问题，用计算机的术语叫做行主序还是列主序存放的问题。 C++中的数组元素是行主序的存放方法，即一行存完后再存放下一行。设a00是行列下标均为0的数组元素，Loc(a00)是a00的存储地址，k是每个数据元素所需的存储单元，则数组中任一数据元素aij的存储地址Loc(aij)可由下边公式求出： Loc(aij) = ？ (0≤im, 0≤jn) (5―2) 三维或更高维数组中任一数组元素存储地址的推导类同。 三维数组Am n p，即m×n×p数组，对于数组元素aijk其物理地址为： LOC(aijk)=LOC(a000)+( i *n*p+ j*p +k)*k 5.1.2 安全数组类的定义和实现 C++提供的数组能满足大多数应用程序的设计需求，但C++提供的数组方法有两个缺点： (1) C++提供的静态数组方法需要预先给出数组元素个数，数组大小在编译时就已确定，且在运行时无法修改。 (2) C++提供的数组方法不进行数组下标越界判断，当数组下标越界时程序照常运行。 因此本节利用C++提供的动态数组方法设计一个一维安全数组类。一维安全数组类在基本数组功能的基础上考虑了数组下标越界问题，且可以重新定义数组元素个数。一维安全数组类的定义和实现如下： //定义enum类型的错误类型。 注意, 其顺序和错误信息数组的顺序相同 enum ErrorType{InvalidArraySize, MemoryAllocationError, IndexOutOfRange}; //定义错误信息数组并赋值 char *errorMsg[3]={Invalid Array Size, Memory Allocation Error,Index Out Of Range}; template class T class Array //Array类定义 { private: T *arr; //数组指针 int size; //数组个数 //错误处理 void Error(ErrorType errorComm) const { cout errorMsg[errorComm] endl; } public: Array(int sz); //一般构造函数 Array(const ArrayT a); //拷贝构造函数 ~Array(void); //析构函数 int ArraySize(void)const; //返回数组个数 void ReSize(int sz); //重新定义数组大小 ArrayT operator=(const ArrayT a); //赋值操作符重载 T operator[](int i); //下标操作符重载 }; //构造函数，申请sz个元素空间给arr template class T ArrayT::Array(int sz)