文档介绍：Arrays
Matrices
Special Matrices
Sparse Matrices
Chapter4 Arrays and Matrices
3/6/2018
1
矩阵ADT
特殊矩阵
稀疏矩阵
本章重点
3/6/2018
2
数组的抽象数据类型描述
抽象数据类型Array{
实例
形如(index,value)的数据对集合,其中任意两对数据的index值都各不相同
操作
Create():创建一个空的数组
Store(index,value):添加数据(index,value),同时删除具有相同index值的数据对(如果存在)
Retrieve(index):返回索引值为index的数据对
Arrays
3/6/2018
3
在C++中,值为整数类型的k维数组score可用如下语句来创建:
int score[u1][u2][u3]...[uk]
为实现与数组相关的函数Store和Retrieve,必须把数组索引[i1][i2][i3]...[ik]映射到[0,n-1]中的某个数map(i1,i2,i3,...,ik),使得该索引所对应的元素值存储在以下位置:start+map(i1,i2,i3,...,ik)*sizeof(int)
C++数组
3/6/2018
4
当数组维数为1时(即k=1),使用以下函数:map(i1)=i1
一维数组
3/6/2018
5
行主映射和列主映射 Row- and Column-Major Mappings
3/6/2018
6
行主次序所对应的映射函数为:map(i1,i2)=i1u2+i2
其中u2是数组的列数。
在行主映射模式中,在对索引[i1][i2]进行编号时,第0,...i1-1行中的i1u2个元素以及第i1行中的前i2个元素都已经被编号。
二维数组行主映射
3/6/2018
7
三维数组的行主映射函数为:map(i1,i2,i3)=i1u2u3+i2u3+i3
三维数组行主映射
3/6/2018
8
template<class T>
class Array1D {
public:
Array1D(int size = 0);
Array1D(const Array1D<T>& v); // 复制构造函数
~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);
一维数组的类定义
3/6/2018
9
private:
int size;
T *element; //一维数组
};
一维数组的类定义
3/6/2018
10