转载

数组和矩阵1--数组

继续是《数据结构算法与应用：C++语言描述》，第四章数组和矩阵的笔记。本小节介绍数组的内容。

数组

抽象数据类型

数据对象 array 的每个实例都是形如 (index, value) 的数据对集合，其中任意两对数据的 index 值都各不相同。

数组的抽象数据类型描述如下所示：

抽象数据类型 Array{
实例
形如 (index , value)的数据对集合，其中任意两对数据的 index 值都各不相同
操作
$/color{red}{Create()}$：创建一个空的数组
$/color{red}{Store(index, value)}$：添加数据(index, value)，同时删除具有相同index值的数据对（如果存在）
$/color{red}{Retrieve(index)}$：返回索引值为 index的数据对
}

C++数组

在C++中数组是一个标准的数据结构，但C++数组的索引(也称为下标)必须采用如下形式：$[i_1][i_2][i_3]/ldots [i_k]$.
$i_j$是一个非负整数，如果k为1，则数组是一个一维数组，如果k是2，则是二维数组。$i_1$是索引的第一个坐标，$i_2$是第二个，$i_k$是第k个。在C++中，值为整数类型的k维数组 score 可用如下语句来创建：
$$
int/; /; score[u_1][u_2][u_2]/ldots [u_k]
$$
该数组最大可用容纳$n = u_1u_2u_2/ldots u_k$个值。由于数组是存储int类型的整数，所以每个元素需要 sizeof(int) 个字节，因此，整个数组所需要的存储空间为 sizeof(score) = n * sizeof(int) 个字节。C++编译器将为数组预留这么多空间。加入预留空间的起始地址为 start ，则该空间将延伸至 start+sizeof(score)-1 。

行主映射和列主映射

为了实现与数组相关的函数 Store 和 Retrieve ，必须确定 索引值 在 [start,start+sizeof(score)-1] 中的相应位置。实际上就是把数组索引$[i_1][i_2][i_3]/ldots [i_k]$映射到 [0,n-1] 中的某个数$map(i_1,i_2,i_3,/ldots ,i_k)$,使得该索引所对应的元素值存储在以下位置$start+map(i_1,i_2,i_3,/ldots ,i_k)*sizeof(int)$。

当数组维数是1时，即k=1，使用以下函数：$map(i_1) = i_1$

当数组维数是2时，各索引可按下图所示的表格形式进行排列。第一个坐标相同的位于同一行，第二个坐标相同的索引位于同一列。
数组和矩阵1--数组
对上图从第一行开始，依次对每一行中的每个索引从左至右进行连续编号，即可得到下图a所示的映射结果。这种把二维数组中的位置映射为[0,n-1]中某个数的方式被称为行主映射。C++中即采用了这种行主映射模式。而下图b则给出了另一种模式，称为列主映射。
数组和矩阵1--数组

行主映射中所对应的映射函数为：$map(i_1,i_2) = i_1 * u_2 + i_2$

其中$u_2$是数组的列数。这里的$i_1,i_2$都是从0开始。

根据上述的行主映射模式可以得到二维以上的映射函数。比如对于三维数组，其行主映射函数为$map(i_1,i_2,i_3) = i_1u_2u_3+i_2u_3+i_3$

对于k维数组，其行主映射函数为$map(i_1,i_2,i_3,/ldots ,i_k) = i_1u_2u_3/ldots u_k + i_2u_3/ldots u k+/dots+i {k-1}u_k+i_k$

类Array1D

C++中虽然支持一维数组，但是这种支持还不够，比如不能使用超出正常范围之外的索引值，如索引值必须都是正整数，不能使用负数。

为了克服这些不足，定义了类Array1D,代码如下所示。

#ifndef ARRAY1D_H_ #define ARRAY1D_H_  #include<iostream>  template<class T> class Array1D{ private:     int size;     T *element;     // 一维数组 public:     Array1D(int size = 0);     // 复制构造函数     Array1D(const Array1D<T>& x);        ~Array1D(){ delete[] element; }     T& operator[](int i)const;     int Size(){ return size; }     Array1D<T>& operator=(const Array1D<T>& v);     // 一元加法操作符     Array1D<T> operator+()const;     Array1D<T> operator+(const Array1D<T>& v)const;     // 一元减法操作法     Array1D<T> operator-() const;     Array1D<T> operator-(const Array1D<T>& v)const;     Array1D<T> operator*(const Array1D<T>& v)const;     Array1D<T>& operator+=(const T& x); }; #endif

该类每个实例X都是一个一维数组。X的元素都存储在数组 X.element 中，第i个元素为于 X.element[i] ，$0 /le i /lt size$。

这个类的共享成员包括: 构造函数，复制构造函数，析构函数，下标操作法[]，返回数组大小的函数Size，算术操作符+、-、*和+=。下面首先是给出构造函数和复制构造函数的代码。

template<class T> Array1D<T>::Array1D(int sz){     if (sz <= 0)         throw BadInitializers();     size = sz;     element = new T[size]; }  template<class T> Array1D<T>::Array1D(const Array1D<T>& v){     // 复制构造函数     size = v.size;     element = new T[size];     for (int i = 0; i < size; i++)         element[i] = v.element[i]; }

下面给出重载操作符[]的代码，该操作符用来返回指向第i个元素的引用，可以使存储和查询操作很自然干的方式进行。

template<class T> T& Array1D<T>::operator[](int i)const{     // 返回第i个元素的引用     if (i < 0 || i >= size)         throw OutOfBounds();     return element[i]; }

接下来给出赋值操作符的代码。首先需要避免进行自我赋值，然后需要先释放目标数组 *this 所占用的空间，然后再分配一个新的空间，并进行赋值。

template<class T> Array1D<T>& Array1D<T>::operator=(const Array1D<T>&ｖ){     // 重载赋值运算符     if (this != &v){         // 不是自我赋值         size = v.size;         delete[] element;         element = new T[size];         // 复制元素         for (int i = 0; i < size; i++)             element[i] = v.element[i];     }     return *this; }

当T是一个内部C++数据类型(如int，float和char)时，构造函数和析构函数的复杂性是$/theta(1)$,而当T是一个用户自定义的类时，构造函数和析构函数的复杂性是$O(size)$。存在这种差异的原因是：当T是一个用户自定义类时，在用new(delete)创建(删除)数组element的过程中，对于element的每个元素都要调用一次T的构造函数(析构函数)。下标操作法[]的复杂性是$/theta(1)$,其他操作符的复杂性均为$O(size)$（注意复杂性不会是$/theta(size)$，因为所有操作符的代码都可以引发一个异常并提前终止）。

下面给出测试的代码及结果。

void testArray1D(){     Array1D<int> a(10);     Array1D<int> b(10);      for (int i = 0; i < 10; i++)         a[i] = i * 2;          cout << "a is /n";     for (int i = 0; i < 10; i++)         cout << a[i] <<" ";     cout << endl;      b = a;     cout << "b=a, so b is /n";     for (int i = 0; i < 10; i++)         cout << b[i] << " ";     cout << endl;      cout << "c= a+b,so c :/n";     Array1D<int> c(10);     c = a + b;     for (int i = 0; i < 10; i++)         cout << c[i] << " ";     cout << endl;      Array1D<int> d(10) ;     cout << "a*c = /n";     d = a*c;     for (int i = 0; i < 10; i++)         cout << d[i] << " ";     cout << endl;      Array1D<int> e(10);     cout << "c-b = /n";     e = c - b;     for (int i = 0; i < 10; i++)         cout << e[i] << " ";     cout << endl; }

输出结果如下图所示：
数组和矩阵1--数组

完整例子可以查看我的 Github .

类Array2D

对于二维数组，可以定义一个类Array2D。程序如下所示。

#ifndef ARRAY2D_H_ #define ARRAY2D_H_ #include<iostream>  template<class T> class Array2D{ private:     int rows, cols; // 数组维数     Array1D<T> *row;        // 一维数组的数组 public:     Array2D(int r = 0, int c = 0);     Array2D(const Array2D<T>& m);     ~Array2D() { delete[] row; }     int Rows() const{ return rows; }     int Columns() const{ return cols; }     Array1D<T> & operator[](int i)const;     Array2D<T>& operator=(const Array2D<T>& v);     // 一元加法操作符     Array2D<T> operator+()const;     Array2D<T> operator+(const Array2D<T>& v)const;     // 一元减法操作法     Array2D<T> operator-() const;     Array2D<T> operator-(const Array2D<T>& v)const;     Array2D<T> operator*(const Array2D<T>& v)const;     Array2D<T>& operator+=(const T& x); }; #endif

在定义中使用一维数组 row 来存储每个行数组。

下面给出构造函数实现的代码，其中的方法 Resize 是 Array1D 新增加的一个成员函数，其实现如下：

template<class T> Array1D<T>& Array1D<T>::Resize(int sz){     delete[] element;     size = sz;     element = new T[sz];     return *this; }

template<class T> Array2D<T>::Array2D(int r, int c){     if (r < 0 || c < 0)         throw BadInitializers();     if ((!r || !c) && (r || c))         throw BadInitializers();     rows = r;     cols = c;     row = new Array1D<T>[r];     for (int i = 0; i < r; i++)         row[i].Resize(c); }

下面则是给出复制构造函数的实现，复制构造函数首先会创建一个具有给定位置数的数组 row ，然后利用一维数组的赋值操作符复制二维数组中的每一行数组。

template<class T> Array2D<T>::Array2D(const Array2D<T>& m){     rows = m.rows;     cols = m.cols;     // 分配指向一维数组的数组     row = new Array1D<T>[rows];     // 复制每一行     for (int i = 0; i < rows; i++)         row[i] = m.row[i]; }

乘法操作符的实现类似于矩阵乘，如下所示：

// 矩阵乘 template<class T> Array2D<T> Array2D<T>::operator*(const Array2D<T>& m)const{     if (cols != m.cols)         throw SizeMismatch();     Array2D<T> w(rows, m.cols);     for (int i = 0; i < rows; i++){             for (int j = 0; j < m.cols; j++){                 T sum = (*this)[i][0] * m[0][j];                 for (int k = 1; k < cols; k++)                     sum += (*this)[i][k] * m[k][j];                 w[i][j] = sum;             }     }     return w; }