继续是《数据结构算法与应用：C++语言描述》，第四章数组和矩阵的笔记。本小节介绍数组的内容。
数组
抽象数据类型
数据对象array的每个实例都是形如(index, value)的数据对集合，其中任意两对数据的index值都各不相同。
数组的抽象数据类型描述如下所示：1
2
3
4
5
6
7
8抽象数据类型 Array{
实例
形如 (index , value)的数据对集合，其中任意两对数据的 index 值都各不相同
操作
Create()：创建一个空的数组
Store(index, value)：添加数据(index, value)，同时删除具有相同index值的数据对（如果存在）
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可用如下语句来创建：
该数组最大可用容纳$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时，各索引可按下图所示的表格形式进行排列。第一个坐标相同的位于同一行，第二个坐标相同的索引位于同一列。
对上图从第一行开始，依次对每一行中的每个索引从左至右进行连续编号，即可得到下图a所示的映射结果。这种把二维数组中的位置映射为[0,n-1]中某个数的方式被称为行主映射。C++中即采用了这种行主映射模式。而下图b则给出了另一种模式，称为列主映射。
行主映射中所对应的映射函数为：$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,代码如下所示。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28#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，算术操作符+、-、*和+=。下面首先是给出构造函数和复制构造函数的代码。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16template<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个元素的引用，可以使存储和查询操作很自然干的方式进行。1
2
3
4
5
6
7template<class T>
T& Array1D<T>::operator[](int i)const{
// 返回第i个元素的引用
if (i < 0 || i >= size)
throw OutOfBounds();
return element[i];
}
接下来给出赋值操作符的代码。首先需要避免进行自我赋值，然后需要先释放目标数组*this所占用的空间，然后再分配一个新的空间，并进行赋值。1
2
3
4
5
6
7
8
9
10
11
12
13
14template<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)$，因为所有操作符的代码都可以引发一个异常并提前终止）。
下面给出测试的代码及结果。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39void 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;
}
输出结果如下图所示：
完整例子可以查看我的Github.
类Array2D
对于二维数组，可以定义一个类Array2D。程序如下所示。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27#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新增加的一个成员函数，其实现如下：1
2
3
4
5
6
7template<class T>
Array1D<T>& Array1D<T>::Resize(int sz){
delete[] element;
size = sz;
element = new T[sz];
return *this;
}
1 | template<class T> |
下面则是给出复制构造函数的实现，复制构造函数首先会创建一个具有给定位置数的数组row，然后利用一维数组的赋值操作符复制二维数组中的每一行数组。1
2
3
4
5
6
7
8
9
10template<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];
}
乘法操作符的实现类似于矩阵乘，如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16// 矩阵乘
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;
}
小结
本小节介绍了数组，并自定义了一个一维数组类Array1D以及二维数组类Array2D。
虽然是增加了不少方法，但是感觉用起来是没有C++的数组那么方便。